Closing the tcc gap — a structural map

Companion to PERF.md. That doc tracks the running standings and the constant-factor sprints; this one is the structural diagnosis: where the 2.22 B vs 0.66 B (3.35×) instruction gap to tcc actually lives, why (grounded in code paths), and the redesign tracks that can close it. Written after a measured phase decomposition + a four-strand code-path audit (kit token pipeline, kit codegen, tcc baseline, kit memory density).

The headline finding: it is instructions, not cache

Measured on the sqlite amalgamation (sqlite3.c, arm64 macOS, best-of-7, /usr/bin/time -l), low load:

compiler	instructions	cycles	IPC	peak RSS
kit -c	2.216 B	0.598 B	3.70	70.6 MB
tcc -c	0.663 B	0.190 B	3.48	13.7 MB

kit's IPC (3.70) is higher than tcc's (3.48). Despite 5× the RSS and pointer-chasing data structures, kit is not cache/stall-bound relative to tcc — both are compute-bound on an 8-wide core. The gap is purely instruction count: kit executes 3.35× more instructions and retires them slightly more efficiently. The "denser, cache-friendlier design" intuition is the right direction, but the payoff mechanism is fewer instructions (fewer copies, fewer indirect calls, fewer redundant recomputations) — not recovering memory stalls. There is no large hidden cache-miss penalty to claw back; do not chase that ghost. Smaller/denser structures help because they cost fewer load/store/move instructions, and they keep IPC high.

The phase decomposition (instruction-grounded)

The wall-clock sample profile in PERF.md is single-peaked on lex_next (62 %) — but that is a wall-clock artifact of one huge inlined leaf function on a single-peaked workload. The instruction truth (load-independent, the metric to trust) is very different and is derived by subtraction:

• emit+objwrite = (-c) − (-fsyntax-only) = 2.216 − 1.846 = 0.372 B (exact).
• Compile the already-preprocessed source as a .c (re-preprocesses only trivial # line markers, so PP work ≈ 0; kit produces the same 3.7 MB object, rc=0): -c(exp) 1.589 B, -fsyntax(exp) 1.217 B, -E(exp) 0.343 B. So parse+sema+types+CG-drive = -fsyntax(exp) − -E(exp) ≈ 0.874 B and emit+objwrite(exp) = 1.589 − 1.217 = 0.372 B (matches — same program).
• lex+pp = remainder = 2.216 − 0.372 − 0.874 = ~0.97 B (≈ kit -E raw 0.974 B — independently consistent).

phase	kit -c instr	share	tcc (est. within 0.663 B)	ratio
lex + pp (scan, include, macro expand)	~0.97 B	~44 %	~0.35 B	~2.8×
parse + sema + types + CG value-stack drive	~0.87 B	~39 %	~0.25 B	~3.5×
native emit + obj write	0.37 B	~17 %	~0.05 B	~7×
total	2.22 B	100 %	0.66 B	3.35×

(tcc's phases are fused; its per-phase figures are estimates from tcc -E 1.152 B and its structure. The point is the shape, not the third digit.)

Two facts reframe the whole effort:

1. The gap is roughly uniform (~3×) across all three phases — there is no single hot function to crush. Closing 3.35× is a campaign across the pipeline, not one patch.
2. Post-PP work alone (≥ -c − -E = 1.24 B) is already ~1.87× tcc's entire compile. Even a free lexer+pp leaves kit at ≥1.87× tcc. The lexer is not the sole frontier — the prior "scanner is THE lever" framing (true for wall-clock self-time, and the recent raw-cursor rewrite was a real −84 M win) does not close the tcc gap. The post-PP pipeline must be attacked too.

Why each phase is ~3× tcc (structural, file:line-grounded)

tcc's target model — one pass, no second representation

tcc fuses lex+preprocess+parse+codegen into one recursive-descent pass with no IR and no token objects (tmp/tinycc/tccpp.c, tccgen.c, arm64-gen.c):

• The current token is a single global int tok + CValue tokc (16 B union). next() returns void and mutates globals — no struct returned or copied per token. Identifiers are interned to small ints while being scanned (hash_ident, one inline hash fold), and the TokenSym caches sym_define/_struct/_identifier/_label pointers directly — so macro/symbol resolution is a pointer load off the interned token, not a per-occurrence hash lookup.
• The value stack is a fixed SValue _vstack[513] (48 B entries); push is vtop++ + four field writes, pop is vtop--. gen_op('+') constant-folds / strength-reduces in place and otherwise calls the backend gen_opi directly (a ST_FUNC, no vtable). The backend's o() writes one 4-byte instruction straight into cur_text_section->data — the final image.
• Macro bodies are pre-tokenized int[] streams replayed by pointer-swap (begin_macro/end_macro push/pop macro_ptr), no per-expansion copy.

Net: each source byte is touched ~once, each token is an int, each operator is a vtop adjustment plus ≤1 four-byte store. There is no second copy of the program anywhere.

kit lex+pp (~0.97 B, ~2.8×) — lang/cpp/lex/lex.c, lang/cpp/pp/*, lang/c/parse/parse.c

• 24 B Tok returned by value across a 4-frame relay: lex_next → pp_next (pp.c:182) → fetch_tok (parse.c:165) → advance (parse.c:185). The same Tok is copied ~3 extra times through frames that never mutate it (~72 B of redundant motion/token). Caveat: PERF.md records that collapsing these pull wrappers alone measured ~5 % (a near-dead-end) — the copies are real but a bounded constant factor; weight this below interning and Tok-size.
• Per-occurrence re-interning: every content token re-runs FNV-1a + a pool probe (pool_intern_slice, pool.c:120), even the millionth int/;. Punctuators are cached (punct_sym[]); identifiers and numbers are not. tcc hashes once during the scan, then it's an int. This is the single biggest lex+pp lever (~14 % of total self-time).
• Tok is 24 B, half of it SrcLoc {file,line,col} (12 B) copied through every layer (lex.h:67, core.h:64). Packing it to a 32-bit position (lazy decode on diagnostics) shrinks Tok to 16 B → 33 % less token-copy bandwidth.
• TOK_NEWLINE is materialized, copied up 3 layers, then dropped in pp_next (pp.c:194) — a full Tok produced+copied+discarded per source line.
• Object-macro expansion double-copies the body (tmp[i]=m->body[i] + subst_phase2, pp_expand.c:374) even with no ##; function-macro args take 3–4 copies/token (pp_expand.c:620).
• Interner table/entry split: the open-addressed table slot holds only a 4 B Sym; the hash+len guard lives in a separate entries[] array at a hash-scattered index, so every occupied probe slot pays a random entries[sym] line (pool.c:140). Dense at the table, pointer-chasing at the entry. (At IPC 3.7 this is extra loads, not stalls.)

kit parse+sema+types+CG-drive (~0.87 B, ~3.5×) — src/cg/*, lang/c/parse/cg_adapter.c

At -O0 no IR is recorded — the bare NativeDirectTarget is installed and opt_cgtarget_new is skipped (src/cg/session.c:147). So this 0.87 B is the value-stack + type machinery itself, run to drive emission:

• 56 B ApiSValue per operand (internal.h:99) carrying delayed-arith, bitfield (12 B), and source-local riders the common a+b never uses — vs tcc's 48 B register-resident SValue. Every push/pop moves 56 B.
• A fold / delay / strength-reduce / identity ladder runs on the hot path even at -O0 (arith.c:48-99), plus 4 type-class probes before any work in kit_cg_int_binop (arith.c:1105). -O0 wants none of this value-quality work.
• Type re-decoded ~8–12× per statement, and abi_cg_type_info (size/align) is not memoized — a recursive cg_type_get + alias chase every call (abi.c:90), hit from alloc_temp_local, nd_type_mem, class_for_type, … Only the packed api_type_class byte is cached (type.c:289).
• The CgTarget seam sits above all this (per PERF Round 7): even routed to the no-op check backend, the value-stack drive pays the full cost.

kit native emit + objwrite (0.37 B, ~7× — worst ratio) — native_direct_target.c, src/arch/aa64/native.c, src/arch/mc.c

• Three stacked vtable layers: CgTarget → NativeTarget → MCEmitter, each an indirect call per primitive. x = a + b; costs ~7–9 indirect calls (nd_binop 1542 → aa_binop → m_emit_bytes 298, ×{add, store, operand materializations}) where tcc does a couple of direct o() byte appends. Three indirections where tcc has zero.
• The NDT runs an LRU register-cache — reg_owner/cache_head/touch_local /flush/writeback/pick_victim (native_direct_target.c:516-930) — a mini register allocator at -O0, where tcc keeps top-of-stack in a fixed reg and spills on demand.
• kit emits ~2× tcc's machine-code bytes (unoptimized -O0 codegen: 4.26 MB vs 2.11 MB object) → ~2× the emit + objwrite volume. Track B (o0-codesize-vs-tcc) is already shrinking this (3.45×→2.42× text) and directly reduces this phase.

The roadmap — tracks to close the gap

No single change closes 3.35×; this is a campaign. Ranked by instruction-payoff × structural leverage. Every track gates on scripts/perf_identity_gate.sh byte-identical output (or, where it changes codegen, run-correctness + determinism) and is measured on RELEASE best-of-7 instructions.

Track 1 — Collapse the codegen vtable stack + the -O0 value machinery (biggest lever: ~0.37 B emit at 7× + much of the 0.87 B middle)

The worst ratio and the densest cluster of redundant work. Structural moves:

1. Fuse CgTarget+NativeTarget into one direct -O0 emit path — remove 2 of 3 indirect calls per primitive and the NativeLoc re-marshalling between the layers (native_direct_target.c:1542-1648 ↔ aa64/native.c). The CgTarget seam exists to share the frontend with the opt-IR / C-source / Wasm backends; at -O0 it is pure overhead. Consider a compile-time-selected direct emitter for the native -O0 path.
2. Memoize size/align/regclass on the type id (extend the api_type_class memo, type.c:289) → kills the uncached recursive abi_cg_type_info (abi.c:90) and the per-operand class_for_type vtable hops.
3. Gate the fold/delay/strength-reduce ladder OFF at -O0 (arith.c:48-99, 1105-1114) → binop becomes pop,pop,emit.
4. Replace the NDT LRU register-cache with a tcc-style fixed TOS-register discipline at -O0 (native_direct_target.c:516-930).
5. Shrink ApiSValue 56→~24 B — move bitfield/delayed/source-local fully off-node (internal.h:99).
6. Couples with Track B (o0-codesize-vs-tcc): fewer emitted bytes → less emit + objwrite + assembler work.

Track 2 — Densify the token relay (lex+pp, 0.97 B)

1. Per-occurrence intern cache / deferred intern (highest lex+pp payoff, ~14 %): stop re-hashing hot identifiers. Cache the last-interned Sym by spelling start+len, or intern lazily only when the parser needs the Sym. (lex.c intern sites, pool.c:120.)
2. Pack SrcLoc → 32-bit position; Tok 24→16 B — 33 % less token-copy bandwidth through PP/macro-expansion/parser; lazy file:line:col decode on the diagnostic path only (lex.h:67, core.h:64).
3. Collapse the 4-frame pull into one inlined pp_pull writing straight into p->cur — eliminate ~3 Tok copies/token and fold newline filtering into the scanner so newlines never become parser-facing Toks. (Bounded: pull-wrapper fusion alone measured ~5 % before — do it for the copy elimination, not as the main lever.)

Track 3 — Interner self-sufficiency (part of lex+pp; ~14 %)

Put hash+len (and an inline small-string prefix, SSO for ≤14 B identifiers) in the probe slot so a probe rejects without the random entries[sym] line (pool.c:31-45,139). Converts a ~2–3 cache-line intern into ~1–2 lines and removes the scattered-entry loads — fewer instructions and a smaller LLC footprint (shrinks the ~2–3 MB entries[]+arena).

Track 4 — The end-state bet: adopt tcc's single-pass data-flow shape

Tracks 1–3 are the incremental path; the destination is tcc's shape: a shared mutable token slot fed by both the scanner and the macro replayer (no per-stage Tok structs), identifiers resolved through symbol pointers cached on the interned token, and a thin SValue[] value stack the parser drives by calling the backend's emit directly (no vtable), writing bytes into the final section image. This is the "clean structural redesign" the project prizes; it subsumes Tracks 1–3 and is the larger lift. Treat Tracks 1–3 as independently shippable, byte-identical-gated steps toward it.

What this corrects / supersedes

• PERF.md's "the scanner is THE lever (58–62 %)" is wall-clock; the instruction-grounded gap is ~uniform across phases and codegen-density is the highest-leverage single track. The raw-cursor scanner rewrite was still a real −84 M win and kit -E now beats tcc -E — but it is not the path to tcc parity.
• The "fused lex→pp→parse pull pipeline = dead end (~5 %)" note stands for the pull wrappers; it does not cover interning, Tok-size, or the codegen vtable stack, which are the actual levers.
• This is an instruction-reduction program (kit IPC ≥ tcc IPC). Density is the means; fewer retired instructions is the metric.

Reproduce the decomposition

SDK=$(xcrun --sdk macosx --show-sdk-path); cd tmp/projects/sqlite-amalg
K=build/release/kit
# best-of-7 instr+cycles helper `mc` as in PERF.md, plus IPC
$K cc -E sqlite3.c -o /tmp/e.c --sysroot "$SDK"; cp /tmp/e.c /tmp/exp.c   # preprocessed -> .c
mc $K cc -c sqlite3.c -o /tmp/k.o --sysroot "$SDK"          # 2.216 B  (full)
mc $K cc -fsyntax-only sqlite3.c --sysroot "$SDK"           # 1.846 B  (− emit/objwrite)
mc $K cc -c /tmp/exp.c -o /tmp/ke.o --sysroot "$SDK"        # 1.589 B  (no PP work)
mc $K cc -fsyntax-only /tmp/exp.c --sysroot "$SDK"          # 1.217 B
mc $K cc -E /tmp/exp.c -o /dev/null --sysroot "$SDK"        # 0.343 B  (lex+trivpp+detok)
mc tmp/tinycc/tcc -c sqlite3.c -o /tmp/t.o                  # 0.663 B  (tcc, all phases)