kit

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

Slimming the vtable stack to close the tcc gap — a redesign plan

Companion to PERF.md (running standings) and PERF-TCC-GAP.md (structural diagnosis). Those establish where the 2.22 B vs 0.66 B (3.35×) instruction gap lives and why. This doc is the redesign: a concrete, ranked, dependency-ordered campaign to slim every layer of the pipeline so each does tcc-spare work per operation — keeping the layered architecture, not deleting it.

The brief that scoped this plan: keep the vtable stack, but slim it down significantly to match tcc's more spare construction; structural wins, 3× fewer instructions. Written after a six-strand code-path audit (lex+pp+intern, parse+ sema+cg_adapter, the CG value-stack/type machinery, NativeDirectTarget, the CgTarget seam, MCEmitter+objwrite).

1. The shape we drive toward — keep the layers, remove the redundancy

The architecture is the asset; the per-operation work is the liability. tcc is fast because 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 pays for pluggability (multiple backends share one frontend through the CgTarget seam) and for a typed value model — and those are worth keeping. What is not worth keeping is the redundant work piled on top: re-interning every token, re-decoding every type 8–12× per statement, copying a 56 B value node and a 48 B location descriptor per operand, and crossing three indirect-call layers per emitted primitive where one would do.

The single most important structural finding — and where an early framing had to be corrected: not all three "layers" are real vtables. Two are genuinely polymorphic and earn their indirection; one is monomorphic and the indirection is pure overhead.

So "keep the vtable stack, slim it" resolves to:

Layer Polymorphic? Decision
CgTarget yes (NDT / opt-recorder / c_target / wasm / check) KEEP — one vtable, untouched signatures
NativeTarget yes — per arch (aa64 / x64 / rv64 / check) KEEP — NDT correctly holds it; slim the NativeLoc marshalling + crossing count, not the dispatch
MCEmitter no — one impl (mc.c) DEVIRTUALIZE — static inline the hot base-only ops, direct-call the rest, delete the 16 pointers

At -O0 the descent becomes one indirect call (CgTarget seam) + one indirect arch dispatch (NativeTarget, real) + one inline byte store (MCEmitter, devirtualized), instead of three indirect calls + a NativeLoc marshalling round-trip. Two real vtables survive; the fake one and the copies do not.

2. The honest arithmetic — what this gets us, and what it does not

Summing the strands' own (deliberately conservative) per-track estimates, with overlaps de-duplicated:

phase now est. after campaign residual ratio vs tcc
lex + pp 0.97 B ~0.74 B ~2.1×
parse + sema + CG-drive 0.87 B ~0.54 B ~2.2×
native emit + objwrite 0.37 B ~0.24 B ~4.8×
total 2.22 B ~1.52 B ~2.3×

The emit-phase number is deliberately conservative: keeping the NativeTarget per-arch dispatch (it is real, §1) means the indirection savings there come only from devirtualizing the monomorphic MCEmitter (F2) and slimming marshalling (F3) — not from collapsing the whole descent. The bulk of the remaining emit headroom is the o0-codesize track (fewer emitted bytes), which is out of this plan's scope but compounds with it (below).

This campaign, fully landed, credibly takes kit from 3.35× to ~2.3× tcc — it does not reach parity by itself. That is the truth the plan must own. Closing the last ~2× requires two things this plan sets up but does not finish:

  1. The o0-codesize track (Track B) compounding. kit emits ~2× tcc's machine bytes; that inflates emit, objwrite, and assemble multiplicatively. Track B has already taken the object 3.45×→1.71× tcc; every further byte removed shrinks the 0.37 B emit phase below the per-op wins counted above. The two tracks multiply, they don't add.
  2. Re-profiling after each landing. The phase shares shift as work is removed; the highest lever moves. Treat the estimates as a starting order, not a budget — re-measure on RELEASE best-of-7 after every shippable step and re-rank.

The destination beyond this plan is PERF-TCC-GAP.md Track 4 (tcc's single-pass data-flow shape: a shared mutable token slot, symbols resolved through pointers on the interned token, a thin value stack the parser drives by calling emit directly into the final section image). The moves below are independently shippable, byte-identical-gated steps toward that shape — several of them (the contiguous section buffer, the binding-on-Sym cache, the intern-once cache) are literally the first bricks of Track 4.

3. Foundational shared changes — do these first, they unblock multiple tracks

Three changes are depended on by more than one strand. Land them first so the per-phase tracks build on them and nobody double-implements.

F1. One packed {size, align, regclass} memo on the type id

The highest shared-leverage change in the whole plan. Today abi_cg_type_info (src/abi/abi.c:27) is an uncached recursive switch with alias/enum chasing; abi_cg_sizeof/abi_cg_alignof (abi.c:90-95) each call it independently, and it is hit several times per statement from all three downstream layers:

Only the 1-byte api_type_class is memoized today (type.c:289-307, with a CACHED bit + builtin fast path). Extend exactly that proven mechanism to a packed {u32 size, u16 align, u8 regclass} word on CgApiType, primed for builtins in cg_api_init_builtins and filled lazily for user types. Route abi_cg_sizeof/ abi_cg_alignof/abi_cg_type_info and the parser's pcg_* through it; collapse the double-call sites to one read.

F2. Devirtualize MCEmitter (the fake vtable) — direct calls + static inline hot path

MCEmitter is monomorphic (mc.h:10; only mc.c assigns slots; mc_new is the sole constructor) — its 16 function pointers are pure indirection across 386 call sites with zero polymorphism. Convert:

This removes an indirect call plus its caller-save churn from every emitted instruction. It is the one genuinely-redundant indirection of the three layers.

F3. Slim the NDT ↔ NativeTarget seam — kill the NativeLoc round-trip, batch crossings (NOT the dispatch)

NativeTarget is a real per-arch vtable — keep it. The waste is the marshalling and the crossing count, not the indirect call. NDT already resolves operands to a Reg (nd_dst_reg/nd_materialize_operand), then wraps each in a 48 B NativeLoc, passes it by value, and the arch immediately unwraps it to a register number (aa64/native.c:2288). Two moves, both keeping d->native->X:

  1. Narrow register-only entry points — binop_rr(NativeTarget*, BinOp, RegLoc dst, RegLoc a, RegLoc b) with a 12 B RegLoc, for the post-materialization ops (the contract already guarantees they receive only NATIVE_LOC_REG, native_target.h:484-488). Keep the fat binop for the opt replay path (opt.c:990-1018, unchanged).
  2. Batch the cold frame-operand case into one fused NT call (binop_mem) instead of load+load+binop, so a cold a+b is one crossing not three.

4. Track A — lex + pp + intern (0.97 B)

The binding/resolution model is already tcc-shaped — macros (MacroTab) and keywords (KwTab) are O(1) Sym-indexed loads via KIT_SYMTAB (the Round-8 sym-centric work). Do not rebuild resolution. The gap is production-side intern-once and copy density.

# Change Payoff Gate Notes
A1 Per-lexer last-spelling intern cache + promote the punct cache to the PP layer so includes don't re-intern. Real C is enormously repetitive at the token level; a 16–64 entry direct-mapped cache keyed on (first_byte,len) catches the dominant fraction before pool_intern_slice (lex.c:594,573,784,679,1029; pool.c:120). −0.06…0.10 B byte-identical (full byte-compare on hit; never cache digraphs) biggest lex+pp lever; pool_intern_slice is 14% of self-time
A2 Self-sufficient interner probe slot — put {hash, sym} (optionally +len+SSO prefix) in the table slot so a probe rejects without the random entries[sym] load (pool.c:139-142). {hash,sym} is the safe floor; SSO width needs an A/B (PERF.md's "inline-prefix" dead-end was entry-side, not slot-side — the distinction matters). −0.02…0.05 B byte-identical complements A1 (A1 = hits, A2 = misses/probes)
A3 pp_next_into(Pp*, Tok*) out-pointer mirroring pp_next_raw_into; collapse the 3 sret copies in pp_next→fetch_tok→advance. −0.02…0.04 B byte-identical bounded (pull-fusion was ~5%); co-owned with the parser strand (it owns fetch_tok/advance/p->cur)
A4 Tok 24→16 B via an inline-packed 32-bit position (NOT a side table — the side-table LocId attempt was the documented regression), lazy (file,line,col) decode only at diagnostics + pcg_set_loc. −0.03…0.06 B or neutral byte-identical, gate HARD (DWARF, -E line markers, __LINE__/#line, diag-across-splice) highest-risk item. Needs a genuinely O(1) decode helper at the warm pcg_set_loc site (34 expr sites) or it repeats history. Do after A1–A3 + jointly with the parser strand
A5 Kill the manufactured TOK_NEWLINE on the cc path (fold BOL/space into the next token's flags + a line counter; -E keeps a newline-emitting variant) and skip the macro-body pre-copy for paste-free bodies (has_paste flag set at definition; replay immutable body directly — pp_expand.c:374,633). −0.03…0.07 B byte-identical (-E newline placement; macro corpus) lower priority; BOL/directive/invocation semantics are subtle

Track A subtotal: ~0.16–0.32 B.

5. Track B — parse + sema + cg_adapter (0.87 B)

No re-introduced superlinear axis was found (scope_lookup, declare_function, typedef/global intern, make_local_aligned are all O(1)-amortized). The gap is pure constant factor: redundant type queries, struct zeroing, and stack-copy bandwidth.

# Change Payoff Gate Notes
B1 Route pcg_mem/pcg_sizeof/pcg_alignof through F1's memo instead of raw kit_cg_type_size/align cross-API calls; build KitCgMemAccess from one c_abi_type_info call (cg_adapter.c:9-39). Halves the per-memop type work. ~3–6% of phase byte-identical depends on F1; keep volatile read inline
B2 Lazy/right-sized PcgLvAux clear — most pushes are rvalues that never read aux; clear the 32 B aux only when a slot is tagged lvalue, drop the 5 explicit pad[] writes, use designated-init (cg_adapter.c:41-51,497,678,993). Attacks the 8% memset. ~4–7% of phase byte-identical (audit aux readers behind was_lvalue/lvalue tag) parser-side, independent
B3 Shrink PcgSlot 48→~24 B (bit-field/subobject riders off-node) in lockstep with cg's ApiSValue shrink (C3); memoize {rank,signed,bits} in a 24-entry TypeKind table so integer usual-arithmetic-conversions read array slots, not 6 hashmap probes (cg_adapter.h:65, cint_common_type 613-627). ~3–5% of phase low (table) / medium (slot split — bitfield+member corpus) co-own with cg strand — the two stacks are kept symmetric (cg_adapter.h:8)
B4 Classify the leading keyword once into a CKw then switch, instead of a ~13-deep is_kw chain in parse_stmt/parse_unary (parse_stmt.c:885-959). tcc's switch(tok). ~1–3% of phase very low (pure control-flow) independent
B5 Cache the resolved binding on the interned Sym (parser-side KIT_SYMTAB(BindingTab, SymEntry*) with push/restore on scope enter/exit) so scope_lookup becomes one pointer load instead of an N-scope hash walk (parse.c:369-380). tcc's sym_identifier. ~5–10% of phase (depth-dependent) medium-high (save/restore + shadow/redef discipline; full corpus) parser-side, no pool change needed — coordinate with intern strand only if you prefer the on-Sym layout
B6 Hoist pcg_convert's src==dst early-out above its size/tid queries (cg_adapter.c:882-892). ~1–2% of phase very low stacks with B1

Track B subtotal: ~0.17–0.33 B (some also visible in -fsyntax-only).

6. Track C — the CG value-stack + type machinery (part of 0.87 B)

The CgTarget seam sits above all this, so even -fsyntax-only pays it. Note the load-bearing caveat resolved in §8: the fold ladder is a deliberate -O0 peephole, not dead weight — slim the decision, keep the effect.

# Change Payoff Gate Notes
C1 F1 applied inside CG — collapse api_alloc_temp_local's double size+align decode and api_mem_for_lvalue to single memo reads. ~0.05–0.10 B (counted in F1) byte-identical this is F1's CG-side consumption
C2 Single type-classify per binop — stamp {foldable-width, is_int, is_float} on the value node at api_push (alongside the existing cached wide_kind), then read once in api_cg_binop; pass the decoded width into api_can_delay_int_arith/api_try_strength_reduce/api_try_collapse_binop_identity so they skip re-deriving it. Removes 6–9 alias-chases per integer binop (arith.c:29-107). Also drop the 4 i128/wide64 stack probes per op in kit_cg_int_binop (arith.c:1103-1121) for the i32/i64-native common case. ~0.04–0.08 B low (cached width must match api_int_like_width's int-vs-int-like distinction exactly) the correct form of "slim the fold ladder" — see §8
C3 Shrink ApiSValue 56→~24 B — move bitfield (12 B) + source_local off-node behind a sparse rider keyed by slot (PLACEs are the minority); make pinned a transient local in dup (its only reader). Lockstep with B3. ~0.02–0.06 B medium (riders must survive dup/swap/rot3/pop; bitfield + source-local corpus) PERF Round 7 found the delayed-payload shrink neutral — do this for copy bandwidth, measure before committing; most invasive, land after C1/C2
C4 Designated-init the per-op memsets in api_alloc_temp_local / api_mem_for_lvalue (the idiom api_op_imm already uses, value.c:22-25). ~0.01–0.025 B very low stacks with C1

Track C subtotal: ~0.07–0.18 B net new (excl. the F1 portion already counted).

7. Track D — NDT register discipline + descriptor + emit/objwrite

# Change Payoff Gate Notes
D1 F2 (MCEmitter devirtualization — direct/inline the monomorphic byte sink). counted in F2 byte-identical the genuine indirection win; highest-frequency call in the backend
D2 Replace the LRU register-cache with a fixed round-robin write-back cache — drop use_tick/last_use/reg_last_use/nd_touch_local and the linear nd_pick_cache_victim scan; keep the consumer-resident write-back mechanism the recent commits (f75874cb/3516b3d3) built — swap only the victim policy (native_direct_target.c:516-930). ~5–10% of emit phase run-correctness + determinism (changes reg selection → different bytes; compile sqlite twice + cmp, run 84|2, toy/parse/smoke) coarser eviction may cost a few emitted bytes — measure both ways
D3 F3 (slim the NDT↔NativeTarget marshalling: NativeLoc 48 B → 12 B RegLoc register-only hooks + batch the cold frame-operand crossings; native_target.h:234,258,484-488). Keep the per-arch dispatch — it is real. counted in F3 byte-identical (narrow hooks) / run-correctness (x64 fused mem-operand) coordinate the NativeTarget struct change once across archs + the opt path
D4 NDT reads F1's memo for nd_type_mem, and carries is64/size_log2 on the NativeLoc pad so the arch's loc_is_64/type_size32 stop re-querying (aa64/native.c:349,374). ~0.02 B byte-identical depends on F1
D5 Zero-copy section write — buf_write_to_writer(Buf*, Writer*) walks chunks straight to the Writer, eliminating the buf_flatten temp-buffer second copy of all machine code (macho/emit.c:814-829, elf/emit.c:730-742). Stretch: a single contiguous geometric section buffer so mc_emit32 stores into the final image (full tcc shape) — larger lift, shared cursor with F3. ~4–8 M (chunk-walk) up to ~8 M (contiguous) byte-identical (test-elf test-macho test-link) decide the buffer type once with F3
D6 Index relocations by section at obj_finalize (stable bucketing) to kill the O(n_sections × n_relocs) rescan in object write (obj.c:1121-1128, macho/emit.c:538-550, elf/emit.c:468-479). A latent superlinear axis — grows with -ffunction-sections/literal fan-out. tens of M on section-heavy objects byte-identical (stable buckets preserve order) independent; a "bug" by PERF.md's rule
D7 Single-pass symbol-table emission + chunk-walk the string table (drop the recount pass + the strtab flatten, macho/emit.c:392-534,854-857); add the rv64 if (mc->debug) guard aa_emit32 already has (riscv/native.c:81); mc_emit_words for multi-word idioms (F3). ~0.01–0.02 B byte-identical mop-up, all in the 7× phase

Track D subtotal: ~0.16–0.27 B (incl. the F2 portion).

8. The one resolved conflict — do NOT gate the fold ladder "off"

The CgTarget strand proposed gating the -O0 fold/strength-reduce/identity ladder off; the CG strand flagged this as a trap, and it is right:

The ladder at arith.c:48-99 is not a no-op at -O0. It const-folds immediates, strength-reduces, and collapses identities — which reduces emitted machine bytes. The o0-codesize track (Track B in the standings, 3.45×→1.71× object) depends on it. Gating it off would change emitted bytes, fail the byte-identity gate, and regress the worst-ratio emit phase — moving backward on the exact phase with the most headroom.

Resolution: keep the ladder's byte-producing effects; slim only the decision cost. That is C2 (classify once, drop the delay-node bookkeeping whose product is never read at -O0), not "turn it off." Any future "fuse the seam" work must preserve the ladder's output and the untyped_values bitcast-elision flag (arith.c:276). This is the one place a naive implementation shoots itself in the foot — flagged here so it doesn't.

9. Sequencing & dependency graph

WAVE 0 (foundations, byte-identical, unblock everything):
  F1 (type memo)            ──> B1, C1, C4, D4
  F2 (MCEmitter devirt + inline cursor)   [the fake-vtable removal; F3's sink]
  D6 (reloc index, independent superlinear fix)

WAVE 1 (high-leverage, mostly byte-identical):
  F3/D3 (NDT↔NativeTarget marshalling slim)   [lands in F2's inline emit]
  C2 (classify-once binop)          [independent of F1, but co-measure]
  A1 (intern last-spelling cache)
  B2 (PcgLvAux right-size), B4 (kw switch), B6 (convert early-out)
  D5 (zero-copy section write), D7 (symtab/emit mop-up)

WAVE 2 (medium risk, lockstep pairs):
  B3 + C3  (PcgSlot + ApiSValue shrink — MUST land together, symmetric stacks)
  A2 (probe slot), A3 (pp_next_into — co-own fetch_tok with parser)
  D2 (round-robin cache — switches to run-correctness gate)

WAVE 3 (highest risk, gate hard, do last & jointly):
  A4 (Tok 16B — needs O(1) decode at pcg_set_loc, joint lex+parser)
  B5 (binding-on-Sym cache)
  A5 (TOK_NEWLINE / macro pre-copy)
  D5-stretch (contiguous section buffer → emit into final image)

Re-profile (RELEASE best-of-7, tmp/projects/sqlite-amalg/sqlite3.c) after each wave and re-rank — the phase shares shift as work is removed.

10. Gate strategy

10b. Measured results (first implementation pass)

Wave 0 + the reloc fix were implemented and measured on sqlite3.c -c (best-of-7, instruction metric is deterministic to ±0.2M on a fixed binary; each change byte-identical via the 60-category gate). The actuals came in 1–2 orders of magnitude below §2's estimates — the estimates assumed the hot paths were fat, but they were already tight:

change estimate measured note
D6 (reloc index) tens of M −5.6M also a real superlinear fix; grows with section count
F1 (type memo) ~80–120M −2.1M cg_type_get already memoized size/align on the CgType; only the alias/enum recursion + double-calls remained
F2 (MCEmitter devirt) ~5–10M −1.2M the indirect calls were single-target → branch-predicted to near-free; the win is removing the fn-ptr load
cumulative D6+F1+F2 −8.9M (−0.41%) 2160.7M → 2151.8M

Two findings worth keeping:

Implication for the remaining micro-levers (F3, the rest of Track A/B/C): they will each land in the single-digit-M range for substantial churn. The instruction gap to tcc (~1500M) is not closable by per-operation slimming; it needs the codesize track (fewer emitted bytes → less emit/objwrite/ assemble, the multiplicative lever) and the value-stack/coalescing redesign. Treat the micro-levers as cleanups that compound, not as the path to parity.

10c. Measured results — -O0 value-stack residency (the high-value lever)

§10b flagged the real lever as "the value-stack/coalescing redesign," not the per-op micro-slimming. That redesign landed as four staged, run-correctness + determinism-gated commits on the brief "stop homing intermediates in frame slots: keep them register-resident on the value stack and spill only the live set at calls." The diagnosis (from emitted -O0 asm) was three round-trip classes, all instances of frame-home every intermediate + flush-everything at every barrier:

commit change sqlite3.c -c -O0 effect
93aafda3 register-resident return — nd_ret sources the value from its live register and drops the cache without spilling (every cached local is dead at a return); was stur w8,[home]; ldur x0,[home] emitted 526,681 → 520,854; obj −0.9%
2b1b03c2 assignment coalescing — pcg_store_void (no dup of a discarded assignment result) + kit_cg_store materializes a delayed arith/cmp straight into the destination local; kills the temp→local routing mov for x = <expr> compile −5.9M; emitted → 518,757
98b1f010 register-resident call args + spill-only-live-set — a provably-dead arg (CGCallDesc.arg_dead_mask from api_temp_dead) flows reg→arg-reg via the existing native_arg_shuffle; only the live-across set is spilled, not the whole cache compile −10.4M; emitted → 479,263; obj −6.4%
f61d252b register-resident call result — the scalar result is cached (claimed reg, written by the post-call ret move) instead of stored to its home + reloaded emitted → 474,752; obj → 2.29 MB

Cumulative: compile 2,153M → 2,134M (−18.8M, −0.87%); emitted instructions 526,681 → 474,752 (−9.9%); object 2,501,224 → 2,293,504 B (−8.3%, now 1.09× tcc); emitted-instruction count 1.54× → 1.39× tcc. All four byte-deterministic; green across toy/parse/smoke-x64/smoke-rv64/cg-api/libc(musl+glibc)/opt, sqlite e2e 84|2 at -O0 and -O1, and a clang-differential call probe (shared-arg- live-across, >8-arg stack calls, varargs, struct sret/byval, recursion, fn-pointer dispatch).

Two lessons:

10d. Measured results — lazy transient frame homes (Stage 4)

The §10c-deferred follow-up landed: a plain transient temp (CG_LOCAL_TRANSIENT && !address_taken && !memory_required) reserves no frame slot at creation; nd_alloc_local leaves home = NONE and a single ensure-accessor nd_home() mints the slot on first demand. Every NDT read of a transient's home (loc/addr builders, the spill in nd_flush_local, the scratch→home store, the nd_call capture-then-flush, nd_ret) routes through nd_home; the va_arg/va_*/inline-asm boundaries call nd_home_operand on each operand before crossing into arch code that reads home directly (the va_arg destination and asm reg outputs are fresh store-target transients with no prior spill — without this they hit NATIVE_FRAME_SLOT_NONE → "bad frame slot"). The lazily-minted slots carry NATIVE_FRAME_SLOT_TRANSIENT, so they feed the existing statement-boundary free-list reuse (nd_reclaim_temps) with no new mechanism. Declared locals/params and address-taken/wide8 temps keep eager homes (debug-loc + stable-address needs; they also spill at the first barrier anyway).

sqlite3.c -c -O0, arm64-mac, RELEASE, vs the copy+convert-coalescing baseline:

metric base lazy Δ
emitted instructions (text/4) 457,115 455,546 −0.34%
object bytes 2,222,960 2,216,680 −0.28%
mean frame size 136 B 112 B −17.6%
frames > 256 B (need x29-relative addr) 236 181 −23.3%
sub xNN, x29 (frame-address building) 27,403 25,954 −5.3%
functions with a stack frame 2,630 2,605 25 frameless

Exactly as §10c predicted: the emitted-instruction win is small (coalescing already prevents most spills, so eager homes were near-benign for the instruction count), but the frame shrinks materially — mean −17.6 %, a quarter fewer frames past the ±256 unscaled window, and 25 functions become frameless. That chips the Fix-B sub xNN,x29 residual (§ in PERF-TCC-GAP) by 5.3 % without touching addressing. Byte-deterministic (two compiles cmp-identical); compile-time within wall-clock noise. Green across toy(1392)/parse-ok(3920)/parse-err(129)/cg-api/opt/smoke-x64/smoke-rv64/debug/ dwarf/libc(musl 18+glibc 9), plus a clang-differential probe (va_arg mixed int/double lanes, inline-asm reg output, struct return, shared-arg-live-across).

11. What this is not