boot2

Playing with the boostrap
git clone https://git.ryansepassi.com/git/boot2.git
Log | Files | Refs | README

commit 413966a3ad56085de31311652ee172f73d7ed787
parent e9a91f83be3d3feb121489e70b1ec7386b97b4f3
Author: Ryan Sepassi <rsepassi@gmail.com>
Date:   Tue, 28 Apr 2026 14:33:21 -0700

cc: clear four tcc.flat.c blockers, hit asm_instrs scratch wall

- tentative-def merge: file-scope `int x;` / `static int x;` now
  record as tentative (defined?=#f) and add to a new world-tentatives
  list; cg-finish emits .bss for any without a real definition,
  letting `static int gnu_ext;` + `static int gnu_ext = 1;` coexist.
- anonymous union/struct members: %cg-find-field and %find-field
  recurse into name=#f members with composed offsets; local-struct
  init zero-pass got an anon-aware skip helper.
- sizeof EXPR in const-expr context: delegates to the regular
  parser under a cg snapshot/rewind, matching parse-unary's sizeof.
- FP softening: %cg-fp-reject! is now a named no-op so fp ctypes
  flow through size-dispatched load/store and same-size casts as raw
  bit patterns; arithmetic is wrong but tcc-lispcc never executes
  its own float paths when compiling float-free input.

Next blocker documented in docs/TCC-TODO.md: scratch exhaustion in
the 333-row asm_instrs[] table at line 14527 (~700 KB scratch per
row, source unconfirmed).

Diffstat:
Mcc/cc.scm | 198+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------------
Mdocs/TCC-TODO.md | 113+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------
Atests/cc/124-tentative-static.c | 24++++++++++++++++++++++++
Atests/cc/124-tentative-static.expected-exit | 1+
Atests/cc/125-anon-union.c | 45+++++++++++++++++++++++++++++++++++++++++++++
Atests/cc/125-anon-union.expected-exit | 1+
6 files changed, 326 insertions(+), 56 deletions(-)

diff --git a/cc/cc.scm b/cc/cc.scm @@ -398,20 +398,22 @@ ;; -------------------------------------------------------------------- ;; world — cross-decl persistent parser/cg state. The same world record -;; is shared by pstate and cg so its three slots — scope (var/typedef +;; is shared by pstate and cg so its slots — scope (var/typedef ;; bindings), tags (struct/union/enum tags), str-pool (interned string -;; literals) — can be reasoned about as one boundary contract. +;; literals), tentatives (file-scope tentative defs awaiting end-of-TU +;; BSS emission) — can be reasoned about as one boundary contract. ;; Phase 3's promote walkers deep-copy from this single root. ;; -------------------------------------------------------------------- (define-record-type world - (%world scope tags str-pool) + (%world scope tags str-pool tentatives) world? - (scope world-scope world-scope-set!) - (tags world-tags world-tags-set!) - (str-pool world-str-pool world-str-pool-set!)) + (scope world-scope world-scope-set!) + (tags world-tags world-tags-set!) + (str-pool world-str-pool world-str-pool-set!) + (tentatives world-tentatives world-tentatives-set!)) (define (make-world) - (%world (list '()) (list '()) '())) + (%world (list '()) (list '()) '() '())) ;; -------------------------------------------------------------------- ;; pstate — parser state. Owned by parse.scm; read-only to cg. @@ -2775,13 +2777,17 @@ (cond ((eq? k 'flt) #t) ((eq? k 'dbl) #t) ((eq? k 'ldbl) #t) (else #f)))) -;; Floating-point ops are parsed but the cg refuses to emit anything that -;; would touch fp bits. Any ld/st/cast/load involving an fp ctype trips -;; this. Caught up front in tcc.flat.c via mes-header prototypes only; -;; if a real fp use leaks through we want a crisp diagnostic, not silent -;; integer codegen. -(define (%cg-fp-reject! op-name ty) - (if (%ctype-fp? ty) (die #f "fp not codegen'd" op-name (ctype-kind ty)))) +;; Floating-point softening. Real FP arithmetic is not implemented; +;; instead the cg silently treats fp ctypes as same-sized integer +;; bit patterns (flt as 4-byte, dbl/ldbl as 8-byte). Loads, stores, +;; and same-size casts round-trip the bytes; widening int→fp casts +;; leave the int bit-pattern in the wider slot; binops use integer +;; ALU ops. tcc.flat.c contains real fp code paths (parse_number, +;; ieee_finite, …) that the bootstrap tcc-lispcc never executes when +;; compiling float-free programs, so producing valid-but-semantically- +;; wrong P1pp here is sufficient. Kept as a named no-op so the call +;; sites stay grep-able if a future bootstrap target needs real FP. +(define (%cg-fp-reject! op-name ty) #t) (define (%ctype-size t) (ctype-size t)) @@ -2808,6 +2814,10 @@ #f)) ; in-fn? (define (cg-finish cg) + ;; Tentative file-scope defs (`int x;` / `static int x;` with no + ;; initializer and not later defined with `=`) get their .bss slot + ;; here at end of TU. C 6.9.2 — see cg-flush-tentatives!. + (cg-flush-tentatives! cg) ;; Entry stub. P1's program-entry contract (docs/P1.md §Program Entry) ;; delivers argc in a0 and argv in a1 at p1_main. %call doesn't ;; clobber a0/a1, so falling straight through to cc__main forwards @@ -3118,12 +3128,34 @@ ;; la(L)+fo ;; In all cases the resulting lval has the field's ctype. +;; Look up FNAME in FIELDS. C11 §6.7.2.1: a struct/union member with no +;; declarator (e.g. `union { int a; int b; };` inside another struct) is +;; an "anonymous member" — its members are addressed as if they belonged +;; directly to the enclosing aggregate. We recurse into any name=#f +;; member of struct/union kind, composing the outer member's offset with +;; the inner field's offset, and return a synthetic (name ctype off) +;; triple so callers can stay agnostic about anonymity. (define (%cg-find-field fields fname) (let loop ((xs fields)) (cond ((null? xs) #f) - ((bv= (car (car xs)) fname) (car xs)) - (else (loop (cdr xs)))))) + (else + (let* ((f (car xs)) + (fn (car f))) + (cond + ((and fn (bv= fn fname)) f) + ((and (not fn) + (let ((k (ctype-kind (cadr f)))) + (or (eq? k 'struct) (eq? k 'union)))) + (let* ((sub-ext (ctype-ext (cadr f))) + (sub-fields (car (cddr sub-ext))) + (hit (%cg-find-field sub-fields fname))) + (cond + (hit (list (car hit) + (cadr hit) + (+ (car (cddr f)) (car (cddr hit))))) + (else (loop (cdr xs)))))) + (else (loop (cdr xs))))))))) (define (cg-push-field cg fname) (let* ((s (cg-pop cg)) @@ -3931,6 +3963,34 @@ (define (cg-emit-extern cg sym) 0) +;; Record `n` as a tentative file-scope definition: don't emit BSS yet, +;; but if no full definition appears by end of TU, cg-finish will emit +;; zero-init storage for it. Idempotent — extra entries with the same +;; name are harmless (cg-finish dedupes via scope-lookup). +(define (cg-add-tentative! cg n) + (let* ((w (cg-world cg)) + (cur (world-tentatives w))) + (cond + ((member n cur) #t) + (else (world-tentatives-set! w (cons n cur)))))) + +;; End-of-TU pass: for each pending tentative, look up the latest sym +;; binding. If it's still `defined?=#f`, no real definition replaced it, +;; so emit zero-init storage now. Otherwise the .data emission already +;; covered it. +(define (cg-flush-tentatives! cg) + (let* ((w (cg-world cg)) + (top (car (world-scope w)))) + (for-each + (lambda (n) + (let ((sm (alist-ref n top))) + (cond + ((and sm + (eq? (sym-kind sm) 'var) + (not (sym-defined? sm))) + (cg-emit-global cg sm #f))))) + (world-tentatives w)))) + (define (cg-intern-string cg bv-content) (let ((p (alist-ref bv-content (cg-str-pool cg)))) (cond @@ -4593,10 +4653,15 @@ ((_n ty) (parse-declarator ps bty))) (expect-punct ps 'rparen) (cons (max (ctype-size ty) 0) %t-u64))) - (else (die (tok-loc t) - "const-expr: only sizeof(TYPENAME) supported")))) - (else (die (tok-loc t) - "const-expr: only sizeof(TYPENAME) supported")))) + (else + ;; sizeof(EXPR) in const-expr context. Operand is not + ;; evaluated (C11 §6.5.3.4) — snapshot the cg, parse the + ;; expr through the regular parser to recover its ctype, + ;; then rewind to discard any emission/vstack pushes. + (cons (%const-sizeof-expr ps #t) %t-u64)))) + (else + ;; `sizeof EXPR` (no parens). Same no-eval rule. + (cons (%const-sizeof-expr ps #f) %t-u64)))) (else (parse-const-primary ps))))) (define (%const-tok-is-decl? ps) @@ -4637,6 +4702,21 @@ (else (die (tok-loc t) "const-expr: bad operand" (tok-value t)))))) +;; sizeof EXPR / sizeof(EXPR) in const-expr context. Delegates to the +;; regular expression parser under a cg snapshot/rewind — same contract +;; as parse-unary's sizeof: the operand is parsed to learn its type but +;; not evaluated, so any emission or vstack push from the parse is +;; discarded. Returns the operand's byte size as a non-negative int. +;; If `paren?`, consumes the closing `)` after parsing. +(define (%const-sizeof-expr ps paren?) + (let ((tag (cg-snapshot (ps-cg ps)))) + (cond (paren? (parse-expr ps) (expect-punct ps 'rparen)) + (else (parse-unary ps))) + (let* ((tp (cg-top (ps-cg ps))) + (sz (max (ctype-size (opnd-type tp)) 0))) + (cg-rewind (ps-cg ps) tag) + sz))) + ;; Convenience: returns the integer value alone (callers that don't ;; need the type half of parse-const-expr's (value . ctype) result). (define (parse-const-int ps) (car (parse-const-expr ps))) @@ -4776,7 +4856,8 @@ (world-tags-set! w (cons (deep-copy ctx (car tn)) (cdr tn)))) (let ((sn (world-scope w))) (world-scope-set! w (cons (deep-copy ctx (car sn)) (cdr sn)))) - (world-str-pool-set! w (deep-copy ctx (world-str-pool w)))) + (world-str-pool-set! w (deep-copy ctx (world-str-pool w))) + (world-tentatives-set! w (deep-copy ctx (world-tentatives w)))) ;; Iter-buffer carryover. The pp-iter / lex-iter records themselves ;; live in main from cc-init; only their tok-iter-buf slots and the @@ -4800,6 +4881,11 @@ (cond ((eq? (tok-kind (peek ps)) 'EOF) #t) (else + (cond + ((debug-log?) + (let ((loc (tok-loc (peek ps)))) + (debug-log "decl" "line" (loc-line loc) + "heap" (heap-usage))))) (parse-decl-or-fn ps) (use-main-heap!) (let ((ctx (make-deep-copy-context))) @@ -4866,10 +4952,16 @@ (else (cond ((not (ps-fn-ctx ps)) - ;; defined? = #f for `extern` decls without `=`; everything else - ;; (initializer present, or no `extern` keyword) is a definition - ;; or tentative def, so the merge logic in scope-bind! treats it - ;; as the authoritative binding. + ;; File-scope decls. Three cases: + ;; (a) initializer present -> full external definition. + ;; (b) `extern` no init -> declaration only. + ;; (c) no init, no `extern` -> tentative definition. + ;; (a) emits to .data immediately. (b) is recorded but emits + ;; nothing. (c) is recorded as `defined?=#f` and added to + ;; world-tentatives; cg-finish emits .bss at end of TU only if + ;; no full definition appeared. This lets two `static int x;` + ;; or a `static int x;` followed by `static int x = 1;` + ;; coexist (C 6.9.2 tentative-def merge). (cond ((at-punct? ps 'assign) (advance ps) @@ -4877,13 +4969,14 @@ (let ((sm (%sym n 'var (or sto 'extern) ty2 #f #t))) (scope-bind! ps n sm) (cg-emit-global (ps-cg ps) sm pieces)))) + ((eq? sto 'extern) + (let ((sm (%sym n 'var 'extern ty #f #f))) + (scope-bind! ps n sm) + (cg-emit-extern (ps-cg ps) sm))) (else - (let* ((def? (not (eq? sto 'extern))) - (sm (%sym n 'var (or sto 'extern) ty #f def?))) + (let ((sm (%sym n 'var (or sto 'extern) ty #f #f))) (scope-bind! ps n sm) - (cond - ((eq? sto 'extern) (cg-emit-extern (ps-cg ps) sm)) - (else (cg-emit-global (ps-cg ps) sm #f))))))) + (cg-add-tentative! (ps-cg ps) n))))) (else (let* ((sz (max (ctype-size ty) 1)) (al (max (ctype-align ty) 1)) @@ -5016,9 +5109,27 @@ (else (die #f "init: not a struct" ty))))) (define (%find-field fields nm) - (cond ((null? fields) #f) - ((equal? (car (car fields)) nm) (car fields)) - (else (%find-field (cdr fields) nm)))) + ;; Anon-member-aware lookup; mirrors %cg-find-field. Designated init + ;; (`.foo = ...`) on a struct with anonymous members descends through + ;; them and returns a (name ctype offset) triple with composed offset. + (cond + ((null? fields) #f) + (else + (let* ((f (car fields)) (fn (car f))) + (cond + ((and fn (equal? fn nm)) f) + ((and (not fn) + (let ((k (ctype-kind (cadr f)))) + (or (eq? k 'struct) (eq? k 'union)))) + (let* ((sub-ext (ctype-ext (cadr f))) + (sub-fields (car (cddr sub-ext))) + (hit (%find-field sub-fields nm))) + (cond + (hit (list (car hit) + (cadr hit) + (+ (car (cddr f)) (car (cddr hit))))) + (else (%find-field (cdr fields) nm))))) + (else (%find-field (cdr fields) nm))))))) (define (%pad-piece nbytes) (make-bytevector nbytes 0)) @@ -5363,6 +5474,25 @@ ((equal? bv (car xs)) #t) (else (%bv-in-list? bv (cdr xs))))) +;; Does any leaf-name of `f` (a struct/union field tuple, possibly with +;; a nameless anon-aggregate type) appear in `seen`? Used by the +;; local-struct zero-pass to skip an anonymous member whose sub-field +;; was already written through a designator like `.a` (C11 §6.7.2.1). +(define (%anon-touched? f seen) + (let ((fn (car f))) + (cond + (fn (%bv-in-list? fn seen)) + (else + (let ((k (ctype-kind (cadr f)))) + (cond + ((or (eq? k 'struct) (eq? k 'union)) + (let lp ((xs (car (cddr (ctype-ext (cadr f)))))) + (cond + ((null? xs) #f) + ((%anon-touched? (car xs) seen) #t) + (else (lp (cdr xs)))))) + (else #f))))))) + (define (%emit-zero-field ps base-off f) ;; Note: scheme1's `+` is binary-only — `(+ a b c)` returns (+ a b) ;; and silently drops the rest. Compute absolute byte offsets via @@ -5395,7 +5525,7 @@ (advance ps) (for-each (lambda (f) - (cond ((not (%bv-in-list? (car f) seen)) + (cond ((not (%anon-touched? f seen)) (%emit-zero-field ps base-off f)))) fields)) (else diff --git a/docs/TCC-TODO.md b/docs/TCC-TODO.md @@ -37,30 +37,99 @@ head -c 50000 build/cc-bootstrap/X86_64/tcc.flat.c \ # then re-run the podman invocation against tcc.head.c ``` -## Blocker — `static` tentative-def merge for `gnu_ext` +## Blocker — scratch exhaustion on `asm_instrs[]` (line 14527) -With `__attribute__` parse-and-discard in place, parse runs further -into the TU and trips on `gnu_ext`: +After fixing the four blockers below, parse advances to the +`static const ASMInstr asm_instrs[] = { … };` table at line 14527 +(~333 entries spanning lines 14528–14860) and aborts with +`scheme1: scratch exhausted` partway through. Per-element scratch +growth measured (heap-mark deltas): ``` -error: redefinition: gnu_ext +elem 16 → scratch 287 503 672 +elem 176 → scratch 400 656 488 +delta 113 152 816 over 160 elements ≈ 707 KB / elem ``` -tcc.c has the textbook tentative-definition pattern: - -``` -static int gnu_ext; // line 1613 — tentative -... -static int gnu_ext = 1; // line 1919 — actual definition +Each row writes ~12 bytes of static data but consumes ~700 KB of +scratch to do it. tcc.c entries are dense: + +```c +{ TOK_ASM_cmpsb, + ((uint64_t) ((((0xa6) & 0xff00) == 0x0f00) + ? ((((0xa6) >> 8) & ~0xff) | ((0xa6) & 0xff)) + : (0xa6))), + (((0x01 | 0x1000)) | ((0) << 13) + | ((((0xa6) & 0xff00) == 0x0f00) ? 0x100 : 0)), + 0, { 0 } }, ``` -C allows multiple tentative definitions of the same `static`/external -object as long as at most one carries an initializer; the cc currently -treats the second decl as a redefinition. The fix lives in -`scope-bind!` / `sym-merge` (cc.scm) — when both old and new are -non-`extern` `var` decls and only the new one is `defined?`, merge -rather than reject. Same shape as the existing extern-fn / -extern-var redecl handling. +The whole array sits inside one parse-decl-or-fn boundary, so scratch +never resets between rows; per-element parse-const-expr / lex / pp / +init-piece allocations all pile up. 128 MiB scratch cap covers ~176 +rows out of 333. + +**Likely fix shape — streaming init emission.** Currently +`parse-init-global` builds a flat `pieces` list across the whole +top-level array (with each row's struct-init merged into a small +sub-list) and `cg-emit-global` walks it once at the end. For an +array-of-struct init with no designators (which asm_instrs is), per-row +pieces could stream directly to `cg-data` (a fixed-storage main-heap +buf) and the per-row scratch state could be reset between elements. +The non-pieces scratch state is small (token buffer, ps, cg vstack +empty between top-level decls) but is currently mingled with init +state, so a clean streaming variant of `%parse-init-array-list` plus a +mid-decl scratch-reset hook is the substantive change. + +Diagnostic note: the source of the per-row 700 KB has not been pinned +down by static reading. tok+loc per token (~80–120 B) × ~50 tokens/row +predicts ~5 KB/row; const-expr cons cells predict another ~1 KB/row; +the merge_init_entries / append-pair traffic is a few hundred bytes. +The remaining ~690 KB is unaccounted-for and worth a deeper instrument +pass before committing to a refactor — there may be a simpler O(N)-vs- +O(N²) bug hiding in lex/pp/parse. + +## Resolved — `static` tentative-def merge + +Done. handle-decl now records file-scope `int x;` / `static int x;` +(no init, non-extern) as tentative defs (`defined?=#f`) and adds the +name to a new `world-tentatives` list rather than emitting BSS at decl +time. `cg-finish` walks the list and emits `.bss` for any tentative +that didn't get a real definition, so two `static int gnu_ext;` +followed by `static int gnu_ext = 1;` merges cleanly via the existing +`sym-merge` (defined? wins). Test: `tests/cc/124-tentative-static.c`. + +## Resolved — anonymous union/struct members (`s->d`, `s->c`) + +Done. tcc.c's `struct Sym` uses three back-to-back anonymous unions +(`union { long c; int *d; }` etc.) and accesses them as if they were +direct members. `%cg-find-field` and `%find-field` now recurse into +nameless struct/union members, returning a synthetic +`(name ctype composed-offset)` triple. `%parse-init-local-struct-list`'s +zero-pass also got an anon-aware `%anon-touched?` helper so a +designator like `.a = 10` on a struct with anon-union members no +longer gets clobbered by the trailing zero-fill. +Test: `tests/cc/125-anon-union.c`. + +## Resolved — `sizeof EXPR` in const-expr context + +Done. `char buf1[sizeof file->filename];` (line 3867) and similar. +The existing `parse-unary` sizeof handler already used cg +snapshot/rewind to recover the operand's ctype without evaluating it; +const-expr now does the same via `%const-sizeof-expr`. Both +parens-form and bare-`sizeof EXPR` work. + +## Resolved — FP softening (cast-to dbl at line 4205) + +Done. `parse_number` declares `double d; d = 0;` which triggered the +`cg-cast` FP rejection. `%cg-fp-reject!` is now a named no-op so +fp ctypes flow through size-dispatched load/store and same-size casts +as raw bit patterns. Real FP arithmetic is still wrong (binops emit +integer ALU ops on the underlying bits), but tcc-lispcc's runtime +never executes its own float code paths when compiling float-free +programs, so producing valid-but-semantically-wrong P1pp here is +sufficient. Comment in cc.scm flags the call sites for any future +target that needs real FP. ## Resolved — `__attribute__` decl-spec at line 1628 @@ -129,14 +198,14 @@ enum constants) overflowed even 128 MiB of scratch because O(N²) in member count. The recent scratch / alist work makes that decl complete with parse heap at ~31 MB on the 1612-line cut. -## Suspected next-tier blockers (not yet observed) +## Suspected next-tier blockers (past asm_instrs) -Past the `gnu_ext` tentative-def merge, the next wave we expect: +Once the asm_instrs scratch issue is past, the remaining wave we expect: - **`_Bool`, bitfield-typed struct fields, `setjmp.h` typedefs** — - same "parse, don't codegen" softening already applied to floats. - tcc.c carries all of these under `HAVE_BITFIELD` / `HAVE_SETJMP` - gates that are off but leave the declarations in the flattened text. + same "parse, don't codegen" softening as floats. tcc.c carries + these under `HAVE_BITFIELD` / `HAVE_SETJMP` gates that are off but + leave the declarations in the flattened text. - **Throughput / wall-clock** — lex+pp+parse on 18 896 lines under scheme1 is going to be slow even after heap residency drops. diff --git a/tests/cc/124-tentative-static.c b/tests/cc/124-tentative-static.c @@ -0,0 +1,24 @@ +/* C 6.9.2 — file-scope tentative definitions can repeat and may be + * later replaced by an initialized definition. tcc.c relies on this + * pattern (`static int gnu_ext;` early, `static int gnu_ext = 1;` + * later). */ + +static int s_dup; /* tentative */ +static int s_dup; /* tentative again — must merge, not redefine */ + +static int s_init; /* tentative ... */ +static int s_init = 7; /* ... promoted to a real def with initializer */ + +int g_dup; /* tentative, no storage class */ +int g_dup; /* tentative again */ + +int g_init; /* tentative ... */ +int g_init = 11; /* ... real def */ + +int main(int argc, char **argv) { + if (s_dup != 0) return 1; + if (s_init != 7) return 2; + if (g_dup != 0) return 3; + if (g_init != 11) return 4; + return 0; +} diff --git a/tests/cc/124-tentative-static.expected-exit b/tests/cc/124-tentative-static.expected-exit @@ -0,0 +1 @@ +0 diff --git a/tests/cc/125-anon-union.c b/tests/cc/125-anon-union.c @@ -0,0 +1,45 @@ +/* C11 §6.7.2.1 — members of an anonymous struct/union are addressed + * as if they were members of the enclosing aggregate. tcc.c's + * `struct Sym` relies on this: it has three back-to-back anonymous + * unions and code accesses `s->r`, `s->c`, `s->d`, etc. directly. */ + +struct S { + int v; + union { + int a; + long b; + }; + union { + long c; + int *d; + }; + int trailing; +}; + +int main(int argc, char **argv) { + struct S s; + s.v = 1; + s.a = 7; /* into anon union 1 (offset 8) */ + s.c = 100; /* into anon union 2 (offset 16) */ + s.trailing = 99; + + if (s.v != 1) return 1; + if (s.a != 7) return 2; + if (s.b != 7) return 3; /* a and b alias */ + if (s.c != 100) return 4; + if (s.trailing != 99) return 5; + + /* Pointer-form access through the anon union. */ + struct S *p = &s; + p->c = 200; + if (s.c != 200) return 6; + + /* Designated init through the anonymous member. */ + struct S t = { .v = 9, .a = 10, .c = 11, .trailing = 12 }; + if (t.v != 9) return 7; + if (t.a != 10) return 8; + if (t.c != 11) return 9; + if (t.trailing != 12) return 10; + + return 0; +} diff --git a/tests/cc/125-anon-union.expected-exit b/tests/cc/125-anon-union.expected-exit @@ -0,0 +1 @@ +0