kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

Performance by ideal flow — rewrite to the conservation law, don't patch around it

Companion to PERF.md (standings + methodology), PERF-TCC-GAP.md (structural diagnosis), and PERF-TCC-SLIM.md (the patch-oriented slimming campaign). This doc reframes the whole effort around a single discipline:

For each entity the compiler handles, name the work that should happen exactly once per entity — the conservation law / ideal flow — then rewrite the subsystem to obey it, instead of memoizing or short-cutting around a structure that re-does the work N times.

This is tcc's secret stated as invariants: each source byte is touched ~once, each token is an int, each operator is a vtop adjustment plus ≤1 four-byte store, and there is no second copy of the program anywhere. kit is ~3.1× tcc in retired instructions (the metric — load-independent, Linux callgrind Ir); kit's IPC already exceeds tcc's, so the gap is instructions, not cache. Each violated conservation law below is a slice of that 3×.

One refinement up front: the objective is minimum instructions, not minimum passes

"Touch each byte exactly once" is a proxy for "do the minimum work," and usually the two agree — but not always. The splice pre-scan (§A) is the case that separates them: the literal one-pass ideal (fuse \<newline> handling into the tokenizer, tcc-style) would reintroduce a per-byte splice test into the hot tokenizer loops that the raw-cursor rewrite deliberately made splice-free — taxing every token to save a pass. A separate SIMD-cheap pre-sweep (memchr, ~1 instruction per 16–32 bytes) does the same job for fewer total instructions. So the law we optimize is minimum retired instructions per entity; "touch once" is how we reason about it, not a goal in itself. Where the two diverge, instructions win — and we say so explicitly.

The fresh profile (the evidence base)

kit cc -c sqlite3.c (the real benchmark), callgrind at HEAD de8c3b62, 2.04 B Ir total. Self-time buckets (trust self/exclusive — inclusive is garbage here because lex↔pp↔parse form one mutual-recursion cycle callgrind double-counts):

area self % conservation law it violates
types / CG-drive 20.7% each type decoded/classified once; all ancillary info cached on the id
lexer scan (lex_next+finish_ident) 16.3% each byte classified once into one token
pp pump + relay 11.6% a token lives in one place, never copied frame-to-frame
splice pre-scan (lex_open_mem) 10.6% bytes not destined for a token are not walked by a scalar pass
intern (pool_intern_slice) 4.2% each lexeme hashed once, then it is an int forever
native emit (NDT path) 3.9% each machine byte written once into the final image
other (parse/sema/objwrite long tail) 26.3% —

Artifacts: build/linux-prof/cg.annot.txt (flat self-Ir), build/linux-prof/cg.tree.txt (caller/callee + call counts). Recipe + gotchas: PERF.md §6. Every rewrite gates byte-identical (scripts/perf_identity_gate.sh) unless it deliberately changes emitted bytes (then: run-correctness + determinism).

§A — Source bytes: classify once; never scalar-walk a byte that isn't becoming a token

Ideal flow. A source byte is loaded, classified via cclass[256], and consumed into exactly one token body — once. Bytes that exist only to be skipped (whitespace, the rare line-continuation) cost a table test, not a separate scalar pass.

Violation (10.6%, lex_open_mem). Every opened buffer is walked twice. lex_fold_splices (lang/cpp/lex/lex.c:149, inlined into lex_open_mem:281) runs a scalar, 2×-unrolled byte loop (lex.c:156-157, for(i;i+1<len;++i) if(src[i]=='\\' && src[i+1]=='\n') ++nspl;) over the entire buffer to count \<newline> splices — which are almost always zero — and then lex_next walks every byte again to tokenize. Confirmed by disassembly of the profiled binary: the count loop is ldurb;cmp #0x5c;ldrb;cmp #0xa;cset;..., ~4–5 instr/byte, no NEON. Across the ~3,140 file opens of the sqlite amalgamation's transitive header closure (file_register → lex_open_mem, cg.tree.txt:56) this is tens of millions of bytes scalar-walked for nothing. (PERF.md:278-279's claim that the splice-free path "pays nothing" is true of lex_next during tokenization but false for the open-time pre-scan — the doc overlooked this counting pass.)

The rewrite.

  1. memchr-driven splice sweep (the instruction-ideal — see the refinement above). Replace the scalar count loop with memchr(p,'\\',...) to skip non-backslash spans at glibc-NEON speed; backslash is rare in C, so the sweep consumes the buffer at ~1 instruction per 16–32 bytes. Byte-identical (same nspl, same fold table; the fold path is entered only when nspl>0). 215M → ~20–40M Ir ≈ −8.5…9.5% of the whole compile. This is the single biggest lever in the profile and near-zero risk. The full tcc-style fuse is explicitly rejected: it taxes the splice-free hot loops (lex_next, skip_ws_fast, scan_ident_run, scan_pp_number, header-name scan) with a per-byte test and would force spelling reconstruction for spliced tokens.
  2. Delete the per-lexer Pool. lex_open_mem mints l->pool = c_pool_new(c) (lex.c:288) — a 64 B Pool + a kit_arena_new — on each of 6,000 opens, but the lexer touches l->pool only as l->pool->c (the Compiler) at three sites, and l->c already holds it. Drop the field; replace l->pool->c → l->c. **20–30M Ir**, byte-identical, clean cutover. (Identifier interning is unaffected — it already targets the shared c->global symtab via kit_sym_intern, not the per-lexer pool; the pool was dead weight.)
  3. Hoist the punctuator-spelling cache to per-compile. struct Lexer is 1216 B, ~1184 of it Sym punct_sym[], memset-zeroed per open and re-interned cold each time — so the same ~60 punctuators are re-interned across ~6,000 lexers (the "classify once" law: a punctuator spelling should be interned once per compilation, not once per lexer). Move punct_sym[] to a per-compile LexShared; Lexer shrinks to ~32 B, its per-open memset collapses, and punctuators are interned 60 times total. **5–15M Ir** + relief on the 2% memset. More invasive (threads a shared ctx into lex_open_mem); preserve the digraph-bypass and the "entry 0 = not-yet-seen" sentinel. Do third.

Floor. The irreducible work is one classified pass over each distinct buffer's bytes (the tokenize pass) + a near-free SIMD splice sweep. The rewrite reaches it. Area est.: ~10–11% of the whole compile, all byte-identical (gate + the line-splice battery: mid-token / mid-string / leading / trailing / consecutive continuations + a diagnostic line across a splice).

§B — Identifiers: each lexeme hashed once, then it is an integer forever

Ideal flow. The first time a spelling is scanned it is hashed → Sym (a small int); every later occurrence is already that int. Macro/keyword/symbol resolution is a load off the interned token, never a re-hash. (tcc: the token leaves the scanner as an int.)

Violation (4.2%, pool_intern_slice). Every occurrence of every identifier/number re-runs FNV-1a + an open-addressed probe — ~628K calls × ~135 Ir — on a token stream with 22.4× reuse (measured on real sqlite3.c: 440,942 id+num occurrences, 19,700 distinct). The probe's sym_eq (src/core/pool.h) loads a hash-scattered ents[sym] line per occupied slot tested. (Note: the interner is already per-compile-shared — c->global, api/core.c:222. The per-lexer Pool from c_pool_new is the frontend pool (arena + type/abi cache), a different type, not a string interner — so there is no per-buffer intern fragmentation to recover; the cache below belongs on c->global.)

The rewrite — a direct-mapped, byte-verified intern cache inside pool_intern_slice. An array of {u32 keyhash; Sym sym}, N a power of two, keyed on a cheap fold of len + the first ≤4 bytes (not full FNV). On lookup: index = fold & (N-1); if the slot is occupied, byte-verify the candidate via pool_slice(sym) (the same compare the probe's sym_eq does) — on match return, having skipped FNV and the probe. On miss, fall through to the existing FNV+probe and populate the slot. Placing it inside pool_intern_slice (not the lexer) serves frontend and codegen interns alike — e.g. aa_plan_call re-interns ABI helper names (__floatditf, …) 19,455× — which a lexer-local cache would miss. Pure accelerator: every hit byte-verifies, so it can never return a wrong Sym (digraph-safe by construction — <: and [ differ in bytes and fail verify); store only {keyhash, sym}, never a borrowed in.s pointer (it aims at transient lexer buffers).

Measured hit rates on real sqlite3.c: 256-slot ≤4-byte-fold = 78.7%, 1024-slot = 85.3%. This is explicitly not PERF-TCC-SLIM's A1 single "last-spelling" slot — that measured 3.4% (real C alternates: sqlite3 . pVfs -> xOpen (), so a 1-slot cache never hits. It is also distinct from the documented dead ends (the entry-side inline-prefix cache and the word-at-a-time hash, which don't remove the per-occurrence hash+probe): this removes both the hash and the probe for ~79% of calls.

Floor. Steady state = one cache load + a 6-byte verify per occurrence (20–25 Ir); one FNV+probe per distinct lexeme + collisions. At 78.7% × ~564K × ~110 Ir saved minus the cache's own overhead: −30…45M (1.5–2.2%) — the single biggest lever in this area. Byte-identical (gate + a digraph spelling check: <: :> <% %> %: %:%: must stay distinct).

Deferred — not an Ir lever: the self-sufficient {hash, sym} probe slot (PERF-TCC-SLIM A2 / PERF-TCC-GAP Track 3). Measured ~0 on instructions — it trades an ents[sym].hash load for a slot.hash load (same instruction, better locality), so it is a D1-miss / wall-clock play the Ir metric cannot see, and the cache above already absorbs ~79% of probes. Revisit only under a dedicated cache-stall investigation. (This corrects PERF-TCC-SLIM's framing of A2 as an instruction lever.)

§C — Tokens: produce only tokens the parser consumes — never build one that's always dropped

Ideal flow. The pump emits, into a fixed out-pointer slot, only tokens the parser will read; a token that is always discarded downstream is never built or relayed. The "lives in one place, never copied" half of the ideal is already met — and the work to do here is removing a token class, not restructuring the relay.

The copy half is already at the ideal (measured — relay rewrite is a confirmed dead end). The lex→pp→parse relay already uses out-pointer (_into) forms (pp.c:72, pp_expand.c:935) precisely to kill inter-frame sret copies. The ~206M Ir in src_next_raw_into / pp_next_raw_into / fetch_tok / advance is per-token macro / directive / include-guard / #line logic, not copy bandwidth — it survives any relay restructuring (PERF.md's "fused pull pipeline = ~5% dead end", reconfirmed). Likewise Tok 24→16 B is a dead end: loc.line is read/written on the hot PP path (#line delta pp.c:123, __LINE__ pp_expand.c:1021), so an inline-packed position forces a per-token decode that costs more than the copy it saves — the LocId side-table regression, reconfirmed.

The real violation — 51% of produced tokens are discarded. lex_next is called 1,424,699× but only 684,790 tokens reach the parser (pp_next): ~740K (51%) are dropped inside PP, overwhelmingly TOK_NEWLINE — each built by lex_next (24 B), sret-relayed through src_next_raw_into + pp_next_raw_into, then continue'd in pp_next. TOK_NEWLINE cannot be removed outright (the directive scanner needs line boundaries: #define / #if / read_directive_line scan to it), but the non-directive ~95% need not be materialized as parser-facing Toks.

The rewrite.

Floor. The pump's irreducible cost is the per-token macro/directive/guard logic over the content tokens only; newlines collapse to a flag on the next token. Area est.: −5…12M now (3a), −15…25M follow-up (3b). Gate: byte-identical -E + the directive corpus (test/pp/) + the line-splice battery.

§D — Types: decode/classify once; all ancillary info cached on the id

Ideal flow. At construction, a type is classified once and carries — on a stable id — its size, align, regclass, predicate bitset (is_int/float/ptr/void/record/aggregate/i128), unaliased id, lowered CgId, and record layout. Every later query is one load. There is one type representation the whole pipeline reads, not a Type*→CgId→CgType re-crossing per operand.

Violation (20.7% — the single largest area). Predicates re-derive recursively through cg_type_get ↔ api_unalias_type ↔ abi_cg_type_info: cg_type_get recurses on itself 610K×, api_unalias_type is called ~660K×, cg_type_is_aggregate 31M self over ~550K calls — each re-decoding the id through a two-level segvec index. Root causes the prior "F1 memo" missed (it memoized abi_cg_type_info, which sat on already-flat field reads — hence its measured −2.1M):

The rewrite.

  1. Memoize c_abi_record_layout (highest leverage, lowest risk) — mirror the AbiInfoMap pattern (c_abi.c:22) or, better, cache the layout pointer on the Type node itself (it already carries a mutable cg_id slot, type.h:94). The O(M·N) rebuild collapses to one build per distinct record. −40…80M. Byte-identical.
  2. A flat per-id descriptor — extend the proven cached_class byte (type.c:33, with its pad[3]) to a packed {unalias_is_self, pred_bitset, unaliased_id} stamped once (eagerly at construction for builtins/records). Predicates become builtin-fast-path OR one api_type_from_id + a byte test; api_unalias_type returns e->unaliased. −15…30M. Byte-identical.
  3. Carry the lowered CgId on the PcgSlot alongside const Type*, filled once at push — operands stop re-crossing the bridge. Plus hoist the t->cg_id cache check above the type_cg_lower switch. −15…30M (P3a byte-identical; P3b re-stamp cg_id whenever slot->type is written; couples with the PcgSlot/ApiSValue shrink so net size is neutral).
  4. Collapse c_abi_type_info into a thin reader off the descriptor once (2) and (3) land — delete the AbiInfoMap probe. −8…14M. Byte-identical.

Floor. The irreducible work is one decode + classify + layout per distinct type, then O(1) loads. The rewrite reaches it. Area est.: ~80…140M (−4…7%) — the first credible double-digit-M win in this campaign, because (1) attacks genuine recomputation, not a constant factor. Sequence: (1) first and independent; (2) and (3a) independent; (4) after (2)+(3b). Re-profile after (1).

§E — Operands & emit (the -O0 NDT path): pop, pop, emit — one real dispatch, one byte-store

Ideal flow. An operand is a small fixed stack record; an operator is pop,pop,emit with exactly one indirect call (the real per-arch NativeTarget dispatch) and ≤1 four-byte store into the final section image. No marshalling round-trip, no fake vtable, no mini register-allocator on the hot path. The fold/strength-reduce ladder stays (it removes emitted bytes — the multiplicative codesize lever); only its decision cost is slimmed.

Already at the ideal (verified — do not re-propose). F2 (MCEmitter devirtualized to direct extern calls; the static inline form regressed +21M and is documented out-of-line), D6 (relocations indexed by section — the O(n_sections × n_relocs) rescan is gone, the latent superlinear axis closed), and the value-stack residency + coalescing + lazy-home work (object now 1.09× tcc) are done.

Violation that remains.

The rewrite.

  1. Typed-store byte sink (the "F2 second half," never built): add direct mc_emit32(MCEmitter*, u32) / mc_emit_word(…, u64, n) against a {cur,end} cursor cached on the base — if (cur+4<=end){ wr_u32_le(cur,word); cur+=4; } else slow(). aa_emit32/rv64 call it directly: one 4-byte store, no staging, no libc call. ~5–6M, compounds with codesize (per emitted word). Risk: cursor↔Buf::used coherence across the slow path / buf_patch / mc_pos (sync before any random-access read). Byte-identical + a -g check.
  2. Stamp is64/size_log2 on the NativeLoc pad (native_target.h:261 has free pad[2]) at the native_loc_reg choke point; the arch reads the bits instead of loc_is_64/type_size32. ~4–6M, byte-identical, low risk (falls back to loc.type where unset). The arch-side elimination is independent of §D's descriptor.
  3. Narrow register-only NativeTarget hooks (binop_rr etc., 16–24 B with the imm rider vs 144 B/op) for the post-materialization ops; keep the fat vtable for the opt replay path, gate on opt_level==0. **3–5M**, additive across all arches; synergistic with (2) (the hook carries exactly what the arch reads). Byte-identical for the rr refactor; defer the x64 fused mem-operand sub-case (changes selection → run-correctness gate).

Explicitly dropped (measured/judged not worth it): D2 round-robin victim (the LRU is inlined, invisible to Ir, and coarser eviction risks the codesize track — instead a policy-neutral free-register bitmap for the nd_cache_alloc free-pool scan is ~1–2M, byte-identical); C3 ApiSValue shrink (Round-7-neutral; api_sv_adjust_refs at 0.67% is the load-bearing liveness refcount that drives coalescing, not copy bandwidth); D5 zero-copy section write (buf_flatten is only 0.25M Ir — invisible to the metric).

Floor. This subsystem's micro-levers each land single-digit-M (as PERF-TCC-SLIM §10b warned); items 1–3 + the bitmap total ~13–19M (−0.6…0.9%). The real emit-phase lever is the codesize track (fewer emitted bytes → multiplicatively less byte-sink/objwrite/assemble), already most-realized by the value-stack work. Item 1 leads because it compounds with codesize. Do not touch the fold ladder (arith.c:48-99) — PERF-TCC-SLIM §8 holds.

§F — Emitted bytes / objwrite: each machine byte written once into the final image

Ideal flow. Machine code is built once in the final section buffer; symbols, strings, relocations are each bucketed once. No flatten-to-temp second copy, no O(n²) rescan.

Status. The two historical O(n²) violations are closed: obj_strtab_add (shared content-hashed ObjStrtab) and the reloc-by-section rescan (D6, obj_reloc_index_ensure, a counting sort — verified). The residual buf_flatten second copy of all machine code at ELF/Mach-O write is real but only ~0.25M Ir (one big 2.2 MB copy, cheap per byte) — below the metric's noise; not worth the Writer-API surface change unless a future wall-clock/cache pass resurfaces it. The full tcc-shape ideal (mc_emit32 stores into one contiguous geometric section buffer = the final image, no chunked Buf at all) is the §E-item-1 cursor taken to its conclusion; revisit only if §E-1's chunked cursor still shows the spill path hot.

Sequencing by leverage (re-profile after each — the frontier moves)

WAVE 1 (biggest, cleanest, all byte-identical):
  §A.1  memchr splice sweep            ~ -8.5…9.5%   (largest single lever)
  §D.1  memoize c_abi_record_layout     ~ -40…80M    (the F1-missed recomputation)
  §B.1  direct-mapped intern cache      ~ -30…45M    (79% of interns are redundant)

WAVE 2 (high-leverage, byte-identical):
  §A.2  delete per-lexer (frontend) Pool ~ -20…30M
  §D.2  flat per-id type descriptor      ~ -15…30M
  §D.3  CgId on PcgSlot + cg_id hoist    ~ -15…30M
  §E.1  typed-store byte sink            ~ -5…6M
  §E.2  is64/size_log2 on NativeLoc       ~ -4…6M
  §C.3a newline drop one frame lower     ~ -5…12M

WAVE 3 (more invasive / structural follow-ups):
  §A.3  per-compile punct table          ~ -5…15M
  §D.4  collapse c_abi_type_info          ~ -8…14M
  §E.3  narrow register-only NT hooks    ~ -3…5M
  §C.3b non-directive newlines never Tok ~ -15…25M

DROPPED / not Ir levers (measured — do not pursue):
  §B self-sufficient {hash,sym} slot (~0 Ir, D1-only) · relay-copy rewrite (dead) ·
  Tok 24→16B (hot-path line decode) · §E D2 round-robin / C3 ApiSValue / D5 zero-copy

WAVE 1 alone is ~13–15% off the 2.04 B compile (moving kit from ~3.1× toward ~2.7× tcc) for three low-risk, byte-identical rewrites. All three attack genuine recomputation — an unmemoized O(M·N) layout rebuild (§D.1), a redundant scalar pass over every byte (§A.1), and 79%-redundant per-occurrence hashing (§B.1) — not constant factors. Those are the rewrites-to-the-ideal; WAVE 2–3 compound. Re-profile after each landing — the frontier moves, and several WAVE-2 items shrink once their WAVE-1 neighbor lands.

Measured results — WAVE 1–2 landing (2026-06-13, 9 commits 325a68b5..bcdbeba3)

All of WAVE 1 plus most of WAVE 2 landed as 9 byte-identical commits (5 parallel in-tree agents on disjoint file sets). Cumulative, Linux callgrind, sqlite3.c -c:

Ir vs tcc (0.663 B)
baseline (de8c3b62) 2,038,845,542 3.08×
after WAVE 1–2 (bcdbeba3) 1,796,553,239 2.71×
delta −242,292,303 (−11.88%)

Gate: the full 60-category byte-identity gate PASSes and the sqlite -O0 object is bit-for-bit identical to golden (2,216,680 B) — i.e. −11.88% instructions for zero output change. Green: toy / parse / pp / cg-api / opt / smoke-x64 / smoke-rv64.

Per-change, measured vs. estimated (estimates ran high, as the docs warned — trust measured):

change est. measured (self-Ir move)
§A.1 memchr splice sweep 215M→20–40M lex_open_mem 215.0M → 78.9M (−136M; residual is the per-open memset)
§D.1 memoize c_abi_record_layout −40…80M kit_cg_type_record_field 48.0M → out of top, kit_cg_type_size 35.7M→13.2M
§B.1 intern cache −30…45M pool_intern_slice 84.7M → 71.6M (−13M; under estimate)
§E.1 typed-store byte sink −5…6M mc_emit_bytes 16.3M → below threshold
§C.3a newline drop −5…12M old relay → pp_pull_into (consolidated)
§D.2/§D.3a descriptor + hoist −15…30M predicates collapsed into api_type_pred
§A.2 / §E.2 −20…30M / −4…6M folded into the cumulative total

The re-profile surfaced the next frontier (re-rank after every wave — the discipline holds):

Measured results — WAVE 3 (2026-06-13, 5 commits fb17391c..bfa30f77)

The second-order levers, landed by 3 more parallel in-tree agents (type-hub / lexer-path / emit-hooks). Diminishing returns, exactly as the docs warn second-order levers do:

Ir vs tcc
after WAVE 1–2 1,796,553,239 2.71×
after WAVE 3 1,785,778,881 2.69×
WAVE 3 delta −10,774,358 (−0.60%)
cumulative (from de8c3b62) −253,066,661 (−12.41%) 3.08× → 2.69×

Gate: full 60-category byte-identity PASS, sqlite object still 2,216,680 B.

change commit measured
builtin pred_bits memo + §D.3b CgId-on-slot fb17391c,486575cf api_type_pred 66.8M → 61.9M (−4.9M)
§A.3 punct cache (struct Lexer 1208→288 B) 3e0e8146 __GI_memset 28.7M → 26.5M (−2.2M)
§C.3b drain non-directive newlines bfa30f77 shows in kit_arena_reset (per-newline reset removed)
§E.3 narrow register-only NT hooks d953be12 ~3–5M in the nd_binop/cmp/convert crossing

Honest correction (the re-profile earned it): §A.3 was mis-diagnosed. The lex_open_mem 78.9M residual was assumed to be the per-open memset of the 1208 B struct Lexer. It is not — memset is an out-of-line libc call, so shrinking the struct to 288 B only moved __GI_memset (−2.2M); lex_open_mem self stayed at 79.2M. That 79M is genuine per-open work other than the memset (field init, the splice-fold loop control, kit_source_add_memory, lex_catchup_splices) and needs a fresh diagnosis before it can be cut. §A.3 was still a real −2.2M and shrank the struct 4.2×, but it did not touch the residual it targeted. Likewise the §D.2/§D.3b hub work moved api_type_pred only −5M — the per-call id → entry decode is more stubborn than the builtin-reclassify was.

The frontier is now genuinely hard. The remaining top costs are the irreducible scan (lex_next 16.5%), lex_open_mem 79M (needs re-diagnosis — not the memset), pool_intern_slice 71.6M (probe side, measured 0-Ir improvable), src_next_raw_into 86M + pp_pull_into 74M (per-token PP logic), and api_type_pred/cg_type_get/api_unalias_type decode (115M, the next type lever is the id→entry decode itself). No remaining single structural lever of the WAVE-1 class (the O(M×N) rebuild, the redundant scalar pass) is visible — closing the last 2.69× → ~2× needs the codesize track (fewer emitted bytes, the multiplicative lever) and/or Track 4 (tcc's shared-token single-pass shape), not more per-op slimming.

Measured results — §R-A/§R-B/§R-C implemented (2026-06-13, 8 commits 209596b8..fe54567a)

The seam-preserving backlog below was worked in full: 8 byte-identical items landed (4 parallel isolated-worktree tracks PP/PARSE/TYPE/OBJ, each per-item byte-identity-gated against a shared golden) and 5 items were skip-justified with the diagnosis verified against current source (they are not byte-identical- achievable, are ~0 Ir, are already done, or — for one — the doc's literal design was a latent miscompile). The "no per-op lever left" pessimism above was too strong: the seam-preserving per-op work still found −1.86% before the codesize track.

Cumulative, Linux callgrind, sqlite3.c -c:

Ir vs tcc (0.663 B)
after WAVE 3 (b50e883e) 1,785,778,688 2.69×
after §R landing (fe54567a) 1,752,564,544 2.64×
§R delta −33,214,144 (−1.86%)
cumulative (from de8c3b62) −286,280,998 (−14.04%) 3.08× → 2.64×

Gate: full 60-category byte-identity PASS; sqlite -O0 object still bit-identical (2,216,680 B). Green: pp / parse / toy (1392/0/35skip) / cg-api / opt / elf / macho / link / ar / debug / dwarf / smoke-x64 / smoke-rv64.

Landed (8 items, all byte-identical):

item commit mechanism
A1 Sym-keyed binding cache 5ff33ea3 scope_lookup → one BindingTab_get; shadow saved on SymEntry.shadowed, head-first unwind in scope_pop
A3 macro body pointer-replay 7ada3f62 no-## object bodies replayed by pointer (has_paste cache + TokSrc loc/flag override + push_buf_replay); 2 copies/expansion removed
A2 paste-path slimming 39c384b1 reuse one per-Pp paste lexer (lex_reset_mem) + cache the <paste> Sym; file_id ordering preserved (DWARF gate is the proof)
A5 skip no-op arena_reset 209596b8 arena_is_empty pristine predicate + early-out + pp_pull_into guard
B1 one decode per id 9a060c6c CG-internal api_type_pred_bits (one decode → full bitset) at multi-predicate sites + hoist non-CSE-able api_unalias_type
B2 fold dual ABI memo 9bd45ea5 delete c_abi_type_info + its Type*-keyed AbiInfoMap; size/align via the per-id memo; signed_ → type_is_signed_integer
B3 type-lower micro 407e8ac9 field-init TypeCgLower (drop memset) + stamp the builtin cg_id on the Type node
C4 objwrite mop-up fe54567a single-pass Mach-O/ELF symtab counts + direct Mach-O strtab write (no flatten copy)

Per-item attribution caveat (PERF.md §6). The naive per-function self-Ir diff between the two builds over-counts wildly (its group-sum is −125M vs the real −33.2M PROGRAM TOTALS) because each item moves work into a new function the diff double-counts: api_type_pred 61.85M → api_type_pred_bits 48.83M (B1), lex_open_mem self collapses into lex_reset_mem+callees (A2), arena_reset 11.81M→0.44M but a new arena_is_empty +7.3M (A5), subst_phase2 −4.07M but a new push_buf_replay +2.09M (A3), c_abi_type_info 19.13M removed but redistributed to the cheaper per-id memo (B2). Trust the −33.2M total. The one clean isolation is A1 = net −6.8M (scope_lookup 8.91M→0.99M, bookkeeping +1.11M — its work stays inside the four scope functions), which refutes the doc's worry that the per-scope emap indexes already amortized it: scope_lookup was a real 8.9M chain-walk, and tcc's binding-on-the-symbol technique cut it.

Skip-justified — verified against current source, NOT implemented:

Remaining opportunities — modularity-preserving (the backend seam STAYS)

The CgTarget → NativeTarget polymorphism is the architecture's asset (one frontend, seven backends: aa64/rv64/rv32/x64 native + wasm + c_target + check, plus the opt-IR recorder at -O1) and is out of scope — we are not collapsing the value-stack→direct-emit seam, not monomorphizing it, not adding a parallel -O0 fast path that bypasses the public kit_cg_* API. Everything below respects that line. It lives in one of four places that are not the swappable seam: (a) the front half (lex/pp/intern/parse), (b) inside the concrete NativeDirectTarget and the monomorphic MCEmitter (the -O0 register machinery and byte sink — these are not the polymorphic vtable), (c) the type subsystem, or (d) the codesize track (which bytes the NDT chooses to emit, not how it dispatches).

Reframe that governs this list (verified): kit is already AST-free and IR-free at -O0 (session.c:148 gates the opt IR behind opt_level > 0; the parser emits as it parses; the p->replay[] buffer is bounded local lookahead for incomplete-array brace-init sizing only, parse_type.c:1746). tcc's "no second copy of the program" property is already true here. So none of the items below is "delete a second representation" — they are thin-the-unit / classify-once / emit-fewer-bytes, the same conservation laws as the rest of this doc.

The re-profile shows no remaining single function of the WAVE-1 class. The biggest remaining lever is the codesize track (§R-D, multiplicative); the highest-value single brick is the symbol-binding cache (§R-A1).

§R-A — Front half: lex / pp / intern / parse (~50% of self-Ir)

# opportunity where character gate
A1 Symbol-binding cache on the interned Sym (the front-half "single-pass brick"; SLIM §B5). scope_lookup is an N-scope chain walk per identifier (parse.c:378, 12 call sites); tcc caches sym_identifier on the interned token. A Sym-keyed binding stack with push/restore on scope enter/exit makes resolution a pointer load. parse.c:301-380 (scope), interner structural, high value (depth-dependent, ~5-10% of parse phase) byte-identical; medium-high risk — save/restore + shadow/redef/typedef-vs-ident discipline; full parse corpus
A2 Re-diagnose lex_open_mem's 79M (WAVE-3 proved it is NOT the memset). It is genuine per-open work over ~6,000 opens (3,140 files + 2,796 macro-paste buffers): field init, the splice-fold loop control, kit_source_add_memory, lex_catchup_splices. Profile what, then cut per-open setup — esp. whether macro-paste buffers (<paste>) need a full lex_open_mem at all. lex.c:281-305, pp_expand.c paste sites unknown until re-profiled; potentially structural byte-identical
A3 Macro body replay by pointer-swap (gap #3 / SLIM §A5). subst_phase2 copies the object-macro body even with no ##; function-macro args take 3-4 copies/token. A has_paste flag set at definition → replay the immutable body directly (tcc's model). pp_expand.c (subst_phase2, arg subst) structural, PP-contained byte-identical (macro corpus)
A4 Stop materializing non-directive newlines (deeper §C.3b). Today they are drained in place (bfa30f77); the full version never builds them as Toks on the cc path (lexer sets TF_AT_BOL; -E keeps a newline-emitting variant). ~51% of lexer outputs are newlines. lex.c:644, pp.c/pp_directive.c structural, med-high risk (cc-vs--E split; directive-line contract) byte-identical, gate the -E categories hard
A5 PP per-token micro-levers: gate the kit_arena_reset reset-check on "xarena actually grew" (fires ~every 5 tokens); tighten the #line-delta + include-guard state machine on the src_next_raw_into/pp_pull_into hot path. pp.c:949, pp_expand.c:935 cleanup (~1-3M) byte-identical
A6 pool_intern_slice probe/insert side (71.6M; the WAVE-1 cache took the hash side). Diminishing — the self-sufficient {hash,sym} slot is measured ~0 Ir (a D1/wall-clock play, not instructions). Only revisit under a cache-stall study. pool.c near-dead-end for Ir —
— lex_next (16.5%, the dominant fn) and the Tok relay (gap #1) are already optimal — raw-cursor scanner; _into out-pointer relay; Tok-16B was a measured dead end. No structural lever left. — done —

§R-B — Type subsystem (~14% of self-Ir)

# opportunity where character gate
B1 Kill the per-call id → entry decode that is now the residual hub cost (api_type_pred 61.9M, cg_type_get 26.6M, api_unalias_type 53.7M). §D.2 made the result O(1); §D.3b carried the CgId on the parser slot — go one further and carry the decoded CgApiType* entry (or inline api_type_from_id's segvec double-index) so a predicate is a direct field read, not a decode. src/cg/type.c (api_type_from_id, api_type_pred), cg_adapter structural-ish (the next type lever) byte-identical
B2 Collapse c_abi_type_info into a descriptor reader (§D.4, deferred). Two memos compute the same facts on two keys (Type* vs CgId). Blocked by a layer boundary (frontend has no KitCompiler*→TargetABI* accessor) + the signed_ divergence + a scalar_kind ALIAS edge — needs a small public accessor first. lang/c/abi/c_abi.c:34, src/abi/abi.c cleanup (~8M), boundary work byte-identical
B3 resolve_type 26.7M / type_cg_lower 16M / type_cg_id_in_pool 13.4M — the Type*→CgId bridge. §D.3b cut the operand re-crossings; resolve_type (frontend type resolution) is separate and still hot. Audit for a re-resolve that a per-Type cache would remove. lang/c/type/type.c, cg_adapter cleanup byte-identical

§R-C — Inside the concrete NDT + the monomorphic MCEmitter (NOT the vtable, ~7%)

These are the -O0 register machinery and byte sink within NativeDirectTarget / MCEmitter — concrete, not the swappable dispatch. Fair game.

# opportunity where character gate
C1 Free-register bitmap for nd_cache_alloc's free-pool scan (the policy-neutral half — find-first-set on caller_saved & ~owned instead of the linear scan). The LRU victim policy (D2 round-robin) was dropped — it is inlined/invisible to Ir and risks the codesize track. native_direct_target.c (nd_cache_alloc 0.75%, nd_dst_reg, nd_dst_writeback) cleanup (~1-2M) byte-identical
C2 Typed-store for memory-op emit — §E.1's mc_emit32 covered the fixed-width path; aa_emit_mem (0.81%) and the other multi-byte idioms still stage+mc_emit_bytes. Extend the cursor store to them. aa64/native.c (aa_emit_mem), mc.c cleanup (~few M) byte-identical
C3 Contiguous section image (gap #5 / D5-stretch) — a single geometric section buffer so mc_emit32 stores into the final image (the full tcc shape for emit), eliminating buf_flatten at objwrite. MCEmitter is monomorphic, so this never touches the seam. mc.c (cursor), obj/{elf,macho}/emit.c structural (the emit brick); Ir win small (~0.25M flatten) but it is the last "emit into final image" piece byte-identical (test-elf/macho/link)
C4 objwrite mop-up (D7): single-pass symtab emission, chunk-walk the strtab. obj/macho/emit.c, obj/elf/emit.c cleanup byte-identical
— ApiSValue 56→24 B shrink (C3) — the value node is CG-layer infra (not the vtable, so technically in scope) but the shrink was measured neutral (Round 7) and api_sv_adjust_refs (0.77%) is the load-bearing liveness refcount that drives coalescing, not copy bandwidth. Leave it. src/cg/internal.h, value.c measured-neutral —

§R-D — The codesize track (the BIGGEST remaining lever — multiplicative, seam-independent)

kit's -O0 __TEXT for sqlite is 1.88 MB, ~2.4× tcc's (o0-codesize-vs-tcc). This is the what-bytes-NDT-emits axis — it does not touch the dispatch seam, and it is multiplicative: every byte removed cuts emit + objwrite + assemble together. The value-stack residency + coalescing + lazy-homes work already took the object 4.26 MB → 2.22 MB (~1.0× tcc object); the remaining ~2.4× text bloat is the single largest lever left after the front half. Open items (from PERF-TCC-SLIM Track B / the o0-codesize track):

This is the track to open next: it is the largest remaining lever, it is entirely within the NDT's byte choices (seam untouched), and it directly shrinks the worst- ratio phase.

§R-E — Memset / arena churn (~2-3%)

# opportunity where character
E1 Right-size the per-expression / per-emit struct zeroing (__GI_memset ~26.5M); designated-init the per-op clears (the idiom api_op_imm/the B2 PcgLvAux work already use). cg_adapter.c, value.c, native_direct_target.c cleanup
E2 Arena churn (arena_alloc 20.4M, arena_reset 14.2M) — audit per-statement/per-temp allocation vs reuse. src/core/arena.c consumers cleanup

Explicitly OUT of scope (the seam stays modular)

The gap-#4 value-stack→direct-emit collapse — removing/monomorphizing the CgTarget/NativeTarget vtable indirection, or adding a parallel -O0 native path that bypasses the public kit_cg_* API. The two real indirect calls per primitive (the CgTarget seam + the per-arch NativeTarget dispatch) are the price of the seven-backend modularity and are kept. The ~2× instruction headroom that a full tcc-shape collapse might reach is not pursued; the seam-preserving items above plus the codesize track are the campaign from here.

Appendix — claims verified against source (not docs)