kit

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

Performance: the fastest C compiler

Goal. kit should be the fastest C compiler at -O0, and emit code at least as dense as the bar. Generated-code quality (runtime speed) is irrelevant; only correctness, compile+link throughput, and emitted code size matter. The bar on both axes is tcc — the fastest mainstream C compiler. The structural bet is already in place (single-pass no-AST C frontend, single-pass emission with patch-ups, a format-neutral linker), so the work is measurement-driven: profile a real workload, find where the instructions/bytes go, remove them.

Two rules hold everywhere:

The real workload is the sqlite amalgamation — one ~9 MB / 263 K-line C file (tmp/projects/sqlite-amalg/sqlite3.c, v3.50.2): real, huge, declaration/macro/ type-heavy, and doubling as a correctness test (compile + link the shell, run a query). All commands assume SDK=$(xcrun --sdk macosx --show-sdk-path) and a release kit at build/release/kit (make bin RELEASE=1).

1. Current standings

Compile speed — the open frontier (~2.6× tcc)

Apple-silicon arm64 / Darwin 25.3, refreshed 2026-06-15. instructions is the metric to trust — load-independent (/usr/bin/time -l, best-of-7); cycles/wall are low-load readings shown only for context. The kit row is after the CG-type-interaction pass + the arena geometric/retain rework (see §3). Each perf step left the sqlite object byte-identical, but the object has grown to 1.75 MB (from ~1.70 MB) because aa64 codegen correctness fixes landed in the same window — the far-slot address-build fallback and the aggregate-return place fix — which add a fixed per-function reserved patch region (see Code size below).

compiler instructions cycles † wall † object
tcc 0.9.28rc 0.663 B 0.190 B 0.06 s 2.11 MB
kit 1.744 B 0.522 B 0.16 s 1.75 MB
Apple clang 21 8.824 B 2.775 B 0.88 s 1.50 MB

† low-load; instructions is the figure to trust. kit instructions over the CG-type-interaction pass: 1.939 B → 1.864 B (slot-query dedup + memory-align contract + builtin ABI-layout cache + resolve/predicate fast paths) → 1.760 B (abi_cg_type_info inline builtin fast path + by-pointer layout cache) = −179 M total (−9.2 %); then the arena geometric-block/retain-on-reset rework

kit beats clang and is the fastest general backend, but tcc is ~2.6× (instructions) ahead — this is the whole game. The gap is instructions, not cache: kit's IPC (3.3) is on par with tcc's (3.5), so both are compute-bound on a wide core and there is no hidden cache-miss penalty to claw back. The payoff mechanism is fewer retired instructions (fewer copies, indirect calls, redundant recomputations) — denser structures help only because they cost fewer load/store/move instructions.

Lean-token lexer/PP rewrite (landed, byte-identical, net win). The lexer/preprocessor boundary was rewritten to the doc/plan/LEX-PP-API.md "lean token" design (compact LocRef byte-offset locations materialized on demand; TextRef spellings; slot-based pulls). sqlite -E, -c object, -g, -S, and diagnostics are bit-for-bit identical to the pre-rewrite snapshot (perf-gate green incl. the splice/#line/diagnostic battery), so code size is unchanged. The boundary-only landing was initially a −3.35 % -c regression — lazy line/col was a loss because line numbers are needed in the happy path anyway (sqlite expands __LINE__ pervasively, and the parser stamps a CG loc per statement) and the first cut built the line index with a scalar \n rescan + a per-loc binary search. Fixing the implementation of laziness (build the index with memchr; cursor the materializer — §4.1) turned it into a campaign-local −24 M -c win (1.865 B → 1.841 B), since the scanner no longer builds a SrcLoc per token. The remaining ~+19 M parse+CG residual (per-statement loc lookups the old eager-on-token loc got for free) is the optional Stage-2 target in §4.1.

Code size — below tcc (0.986×)

The honest metric is .text machine code (the object file is format-skewed — Mach-O vs tcc's ELF — and not comparable; kit's object is actually smaller).

metric kit tcc ratio
.text 1,352,356 B / 338,089 4-byte slots 1,370,940 B / 342,735 4-byte slots 0.986× (−4,646 slots)

kit still clears the code-size bar overall, but the margin shrank from 0.951×: the recent aa64 far-slot/large-frame fix reserves a branched-over 5-instruction patch region in every qualifying function's prologue (a b over five nops when the long address-build path is unused), and 2,587 functions pay it. That alone adds **+12,897 nops (52 KB)** — i.e. the entire .text growth is this padding; net of nops, real instructions actually shrank slightly. The genuine excess remains the same instruction families as before (per-mnemonic, kit − tcc):

heavier in kit Δ what it is
stur+ldur+str (spills) +47,095 #1: register pressure — the single-pass NDT spills more than tcc keeps resident across statements / control-flow joins
mov +13,666 residual arg / value-stack copies the arg0-first placement can't reach (nested-call results already in x0, pressure spills)
nop +12,897 new — branched-over 5-nop patch region reserved per qualifying function by the far-slot/large-frame fallback; likely over-reserved (see §4.2)
sub+movk +3,474 residual far-frame addressing (byte/half slots, &local in big frames)

…offset by where kit already beats tcc (structural wins — do not touch): ldr −24,214 (far slots fold into [sp,#scaled]), add −20,899 (folds offsets into displacements), cset −17,226 / cbnz −10,817 / cmp −9,421 (kit fuses compares straight into cbz/b.cc; tcc materializes a bool then tests — the cost side is cbz +6,294 and the b.eq/b.ne/b.ge/b.le/b.lt family +6,936, still a large net win), movn −6,720 / movz −4,644 / stp −3,722. The mnemonic histogram nets −5,058 decoded instructions; kit also has 412 4-byte padding slots, so the byte metric nets −4,646 slots — the +12,897 reserved-patch nops are what eroded the old −16,897.

2. Where the cost is (current profile)

Compile is frontend-bound — lex+pp ~2.0× tcc, post-PP ~3.6× tcc

Phase split measured directly (instructions, best-of-7), not estimated from -E. -E is a bad lex+pp proxy: it re-serializes the token stream to text, work neither compiler does at -c, and the two serialize at wildly different cost (tcc's -E 1.17 B is ~0.79 B serialization via get_tok_str re-stringify + whitespace logic, so tcc -E even exceeds tcc -c; kit's -E serializes for ~0.06 B since tokens carry TEXT_SRC spans → emit is a memcpy). To isolate lex+pp we drain the token stream to EOF with no parse and no output in both compilers (tcc: -bench hook, patched to use -c parse_flags; kit: KIT_PP_DRAIN, see §3):

phase kit -c tcc -c kit / tcc
lex + pp 0.80 B 0.40 B ~2.0×
parse + sema + types + CG-drive 0.71 B ┐ 0.26 B —
native emit + object write 0.24 B ┘ (post-PP) —
post-PP total 0.94 B 0.26 B ~3.6×
total 1.74 B 0.66 B ~2.6×

So both halves are real frontiers — lex+pp is not at parity (an earlier claim from the misleading -E proxy was wrong). The post-PP ratio is larger, but lex+pp is ~46 % of kit's -c and a clean 2.0× behind. Note kit's lex+pp drain does less than tcc's — kit defers number/string decode to the parser (tcc decodes in the lexer; bare tcc scan+expand is 0.38 B, +decode 0.40 B) — yet is still ~2.0× heavier, so the gap is pure per-token engine overhead, not extra work:

The post-PP 3.6× is the bigger slice: tcc drives a thin SValue[] straight into a one-pass emitter, while kit routes through the CgTarget→NativeTarget→MCEmitter seam and a richer type/ABI layer (§4). Closing either is a campaign, not one hot function.

In the lean-token rewrite + loc-materialization fix A/B (golden→candidate, best-of-7): lex+pp −44 M (the scanner no longer builds a SrcLoc per token — loc is a byte offset), parse+sema+CG +19 M (the residual: a per-statement cursor lookup at pcg_set_loc the old eager-on-token loc got for free), emit flat → −24 M total (−1.3 %).

Linux callgrind (inclusive, instruction-grounded — the tool that sees what wall-clock sample hides; total 1.547 B Ir, glibc/ELF; self-Ir summed across callgrind's '2 symbol splits). This is after the CG-type-interaction pass (slot-query dedup + memory-align contract + builtin ABI-layout cache + resolve/predicate fast paths + the api_type_layout_get follow-up) and the arena geometric/retain rework: the type cluster went 1.741 B → 1.608 B → 1.566 B (−175 M, −10.1 %), then the arena change shaved heap/memset churn to 1.547 B (−19 M), all byte-identical for the perf steps (perf-identity gate green on every non--g category; the Linux/ELF total is not comparable to the macOS hardware count — different libc/format — but the distribution is the point).

self % function(s) subsystem
12.3 lex_next scanner
6.4 malloc hosted heap
4.5 / 4.4 src_next_raw_into / pool_intern_slice pp + interning
3.9 pp_pull_into preprocessor
2.8 finish_ident scanner
2.0 / 1.6 / 0.3 __GI_memset / __GI_memchr / __GI_memcpy libc memory
1.9 / 1.8 abi_cg_type_info / api_type_pred_bits types/ABI
1.6 / 1.3 / 1.2 pp_materialize_loc / api_const_from_sv / api_sv_adjust_refs lazy-loc / value-stack
1.2 arena_alloc arena bump path
1.1 / 1.0 / 1.0 / 0.4 cg_type_get / api_type_layout_ref / api_type_class / resolve_type types
1.1 aa_emit_mem codegen
0.78 (Σ) kit_cg_slot_lang_type 0.53 / kit_cg_slot_lang_flags 0.16 / kit_cg_slot_cg_type 0.09 CG slot queries (zero-copy accessors)

What moved (vs the pre-pass profile above each arrow): kit_cg_slot_info 3.2 % → gone (the by-value struct copy is retired; the C frontend now reads single facts through the narrow accessors above, Σ 0.75 %), cg_type_get 3.0 → 1.1, resolve_type 1.8 → 0.4, __GI_memset 3.0 → 1.9. The ABI-layout lookup was first consolidated into api_type_layout_get (1.3 → 3.9 in the intermediate profile) — one memoized indexed load per type for builtins and user types instead of the abi_cg_type_info_compute → cg_type_get → per-call resolve_type spread — then the follow-up retired that 5-field out-param marshalling: api_type_layout_ref returns a borrowed pointer to the cached ABITypeInfo, and abi_cg_type_info resolves a builtin with one inline indexed load off Compiler.cg_builtin_layout (no cross-TU call). Combined abi_cg_type_info + layout cache: 5.5 % → 2.9 % (−43 M, the whole program-total drop this step); api_type_layout_get 3.9 → _ref 1.0, abi_cg_type_info 1.6 → 1.9 (it absorbed the inline load). Net of the targeted leaves: 15.0 % → ~9 %.

Subsystem rollup: scanner ~15 % (lex_next+finish_ident), pp+interning ~13 % (src_next_raw_into+pp_pull_into+pool_intern_slice), CG/types/ABI metadata ~9 % (down from ~15 %), libc allocation/memory helpers ~10 %, lazy-loc (pp_materialize_loc) ~1.6 %, arena bump path (arena_alloc) ~1.2 %, direct codegen emit ~1 %. The type layer is no longer a top-tier frontier — the remaining leaves (abi_cg_type_info register-struct returns, api_type_pred_bits, cg_type_get) are already at/under ~2 % and were explicitly not micro-optimized. The next frontiers are the scanner (lex_next ~15 %) and the hosted heap (malloc ~6 %, call frequency already addressed by the arena rework — see below). Trust callgrind for where; trust macOS instructions for how much.

Allocator (hosted heap). malloc is 6 % of Ir but only **4,278 calls** for the whole sqlite TU (KIT_METRICS=1 heap counters): the cost is in large, churned blocks, not call frequency. Most allocation never reaches the heap — arenas bump-allocate, and the variable-count structures (interner table/entries, vectors, segvecs) already grow geometrically (351 reallocs total, all grows). The one gap was fixed-size 64 KiB arena blocks. The arena now (a) grows blocks geometrically (64 KiB doubling to a 1 MiB cap, so a large arena needs O(log n) heap calls not O(n)) and (b) arena_reset retains the high-water blocks — it rewinds the bump cursor and frees nothing; only arena_fini returns memory, so reset/refill cycles (per-statement fold, per-function MC, per-expansion pp scratch) reuse their blocks with zero heap traffic. Effect on the sqlite compile (KIT_METRICS): large (≥32 KiB) block allocs 440 → 124 (−72 %), total allocs 4,278 → 3,967, frees 4,571 → 4,260; macOS instructions −0.22 %, byte-identical (isolated golden-vs-candidate). Small on the instruction metric (Apple malloc is cheap) but it corrects the reset-vs-free semantics and cuts heap pressure/fragmentation. Heap counters reuse the KitProfiler machinery (embedder counter range), opt-in via KIT_METRICS=1.

SQLite -O1 optimizer profile (Linux callgrind, self Ir, optimizer-finalize only). Full sqlite -O1 callgrind collection on the default 2 GiB Podman VM overflows Valgrind's brk segment and dies with rc 137, so the useful profile toggles collection at opt_on_finalize and forces glibc malloc onto mmap (MALLOC_MMAP_THRESHOLD_=1 MALLOC_ARENA_MAX=1). That captures the whole-program O1 sweep (reachability/internalization, CGIR lowering, inlining, per-function O1 pipeline, native emit) but excludes frontend recording, so it is a distribution profile, not a total comparable to the -O0 full-compile profile above. Command and raw output are in build/linux-prof/cg.sqlite_o1.opt_finalize.mmap.*.

Profiled command: kit cc -O1 -c sqlite3.c -DSQLITE_THREADSAFE=0 -DSQLITE_OMIT_LOAD_EXTENSION -lc. Total collected inside opt_on_finalize: 15.496 B Ir.

self % function(s) subsystem
24.5 opt_regalloc_place physical register placement
18.7 opt_func_from_cg_ir CGIR -> optimizer Func lowering
7.8 alloc_assign_group_hard hard-register assignment grouping
7.4 ir_note_emit IR/lowering record construction
4.5 opt_build_loop_tree loop analysis
3.2 / 1.7 / 1.6 / 1.5 opt_bitset_has / opt_bitset_union / opt_bitset_copy / opt_bitset_union_and_not liveness/range bitsets
2.4 opt_live_ranges_build live-range construction
2.1 / 0.8 msort_with_tmp / u32_cmp sorting in optimizer hot paths
1.6 / 0.3 __GI_memset / __GI_memcpy libc memory
1.5 / 0.2 inline_call_site / opt_inline whole-program inliner
1.2 / 1.0 / 0.3 / 0.2 metrics_count / metrics_scope_from_name / metrics_scope_from_name'2 / metrics_count'2 profiling string-name lookup
1.1 arena_alloc arena bump path
1.0 opt_addr_xform_pregs address transform
0.1 opt_emit_native native emit self-time

Interpretation: sqlite -O1 compile time is dominated by the optimizer's middle/back half, not native emission. Register allocation alone is at least 32 % (opt_regalloc_place + alloc_assign_group_hard, excluding the shared bitset/range helpers), while CGIR lowering plus record construction is another 26 %. Built-in metrics on the same TU report 2,522 functions, 121,075 blocks, 98,516 PRegs, 1,049,079 ranges, and 29.1 M live bitset words touched, which explains why the liveness/range bitset helpers are visible. A cheap cleanup from this profile was the disabled metrics fast path: metrics_scope_from_name and metrics_count burned ~2.7 % of O1 finalization with KIT_METRICS unset because each hot scope/counter call string-decoded the name before discovering the profiler sink was null. metrics_* now checks the sink before name decoding; enum-specific wrappers would still make metrics-on collection cheaper.

Follow-up cleanup on the same sqlite -O1 workload made the hot shapes cheaper: CGIR lowering precomputes local address-use, param lookup, emit order, and fallthrough successors; regalloc builds coalesce-group member lists before candidate scoring and uses them in group scans; loop-tree construction precomputes backedges and uses generation-marked loop bodies. Bounded macOS release timing for the single amalgamation compile is now 0.93 s best / 0.96 s mean (7 runs, 5 s per-run timeout); the ecosystem-style two-TU sqlite O1 build is 1.20 s best / 1.22 s mean (5 runs, 8 s timeout), down from the previous 2.78 s best row. KIT_METRICS=1 ticks on the same single-amalgamation command: opt.o1.total 27.09 M → 16.78 M (−38 %), opt.regalloc 13.81 M → 7.83 M (−43 %), opt.o1.cg_ir_lower 4.94 M → 1.16 M (−77 %), and opt.build_loop_tree 1.41 M → 0.20 M (−86 %). Linux callgrind rerun was blocked in this pass because podman machine started then immediately stopped at 3 GiB, 2.5 GiB, and the restored 2 GiB setting; the VM was left configured at 2 GiB/stopped.

Code size is still locally spill-bound

Even with aggregate .text now smaller than tcc, the remaining per-mnemonic excess is dominated by spills (register pressure in the single-pass cache, +47 K) then residual movs (+14 K). Both concentrate in the giant functions (_sqlite3VdbeExec etc.) where per-function pressure is highest.

3. Reproducing the metrics

Build tcc (the bar) from the mob mirror as an optimized binary:

git clone --depth 1 https://github.com/tinycc/tinycc tmp/tinycc && cd tmp/tinycc
export SDKROOT=$(xcrun --sdk macosx --show-sdk-path)   # else "stdio.h not found"
sed -i 's|^CFLAGS=.*|CFLAGS=-Wall -O3 -DNDEBUG -Wdeclaration-after-statement|' config.mak
./configure ; make clean ; make CC=cc        # CC=cc = Apple clang (xcrun-aware)
# binary at tmp/tinycc/tcc ; compile with: tcc -c sqlite3.c -o x.o

Instructions / cycles / wall — /usr/bin/time -l is the macOS perf stat; best-of-N filters scheduling noise:

m(){ local bi=9e18 bc=9e18 br=9e18; for i in $(seq 1 7); do
       /usr/bin/time -l "$@" >/dev/null 2>/tmp/m.txt
       local I=$(awk '/instructions retired/{print $1}' /tmp/m.txt)
       local C=$(awk '/cycles elapsed/{print $1}' /tmp/m.txt)
       local R=$(awk '/real/{print $1}' /tmp/m.txt)
       awk "BEGIN{exit !($I<$bi)}"&&bi=$I; awk "BEGIN{exit !($C<$bc)}"&&bc=$C
       awk "BEGIN{exit !($R<$br)}"&&br=$R; done; echo "instr=$bi cycles=$bc real=${br}s"; }
cd tmp/projects/sqlite-amalg
m build/release/kit cc -c sqlite3.c -o /tmp/k.o --sysroot "$SDK"
m tmp/tinycc/tcc -c sqlite3.c -o /tmp/t.o

Caveat: Apple clang spawns a cc1 that /usr/bin/time does not count — measure it with cc -fintegrated-cc1 -c …. kit and tcc are single-process.

Phase decomposition. Do not use -E as the lex+pp number — it adds token→text serialization neither compiler does at -c, and tcc/kit serialize at very different cost (§2). Instead drain the token stream to EOF (lex+pp only, no parse, no output) in each compiler:

# kit: KIT_PP_DRAIN runs pp_next_parse to EOF then returns (lang/c/c.c)
m env KIT_PP_DRAIN=1 build/release/kit cc -c sqlite3.c --sysroot "$SDK" -o /dev/null  # lex+pp
m build/release/kit cc -fsyntax-only        sqlite3.c --sysroot "$SDK"  # lex+pp +parse/sema/types/CG
m build/release/kit cc -c -o /tmp/k.o       sqlite3.c --sysroot "$SDK"  # +emit+objwrite
# tcc: the -bench hook drains next() to EOF; patched (tccpp.c tcc_preprocess)
# to use -c parse_flags. TCC_DRAIN_FLAGS=c also decodes literals in the lexer.
m env TCC_DRAIN_FLAGS=c tmp/tinycc/tcc -E -bench sqlite3.c -o /dev/null   # tcc lex+pp
m tmp/tinycc/tcc -c sqlite3.c -o /tmp/t.o                                 # tcc full -c

macOS hotspot sample (self-time leaves only — see the callgrind caveat). One -c is too fast for sample; merge ~80 runs:

make RELEASE=1 PROFILE=1 CC=clang BUILD_DIR=build/bench bin   # -g + frame ptrs, no strip
cd tmp/projects/sqlite-amalg ; KIT=build/bench/kit ; rm -f /tmp/p_*.txt
for i in $(seq 1 80); do
  $KIT cc -c sqlite3.c -o /tmp/kk.o --sysroot "$SDK" 2>/dev/null & pid=$!
  sample $pid 5 1 -file /tmp/p_$i.txt -mayDie >/dev/null 2>&1 ; wait $pid; done
for f in /tmp/p_*.txt; do awk '/Sort by top of stack/{f=1;next}/Binary Images/{f=0}f' "$f"; done \
 | sed -E 's/\(in [^)]*\)//' | grep -oE '[A-Za-z_][A-Za-z0-9_]*[[:space:]]+[0-9]+' \
 | awk '{c[$1]+=$2;t+=$2} END{for(k in c) printf "%.1f%% %s\n",100*c[k]/t,k}' | sort -rn | head -25

Linux callgrind — the inclusive, instruction-grounded profiler (no valgrind on macOS). scripts/perf_callgrind.sh codifies the recipe; one-time scripts/perf_callgrind.sh image bakes the container, then:

scripts/perf_callgrind.sh run <tag>   # builds kit in-container, runs callgrind, prints total Ir
                                      # → build/linux-prof/cg.<tag>.annot.txt (self Ir + callers)

For the sqlite -O1 optimizer-finalize profile, use podman machine explicitly to give the VM enough memory for Valgrind, and force malloc away from brk:

podman machine stop || true
podman machine set --memory 3072
podman machine start
podman run --rm --platform linux/arm64 -v "$PWD":/work:Z kit-prof sh -c '
  set -eu
  cd /work/tmp/projects/sqlite-amalg
  env MALLOC_MMAP_THRESHOLD_=1 MALLOC_ARENA_MAX=1 \
    valgrind --tool=callgrind --cache-sim=no --branch-sim=no --dump-instr=no \
      --collect-jumps=no --collect-atstart=no --toggle-collect=opt_on_finalize \
      --callgrind-out-file=/work/build/linux-prof/cg.sqlite_o1.opt_finalize.mmap.out \
      /work/build/linux-prof/kit cc -O1 -c sqlite3.c \
        -DSQLITE_THREADSAFE=0 -DSQLITE_OMIT_LOAD_EXTENSION -lc -o /tmp/sqlite_o1.o \
      2>/work/build/linux-prof/cg.sqlite_o1.opt_finalize.mmap.vg.log
  callgrind_annotate --threshold=99.5 \
    /work/build/linux-prof/cg.sqlite_o1.opt_finalize.mmap.out \
    >/work/build/linux-prof/cg.sqlite_o1.opt_finalize.mmap.annot.txt
'
# restore the default local VM shape after the run
podman machine stop
podman machine set --memory 2048
podman machine start

Gotchas baked into the script (do not relearn): (a) pass -lc so kit finds the glibc sysroot even for -c; use bookworm (glibc 2.36), not ubuntu 24.04 (glibc 2.39's bits/math-vector.h uses a vector-typedef attribute the C frontend rejects). (b) strip --strip-debug the kit binary in place before profiling (valgrind 3.19 chokes on clang DWARF5; callgrind needs only .symtab) — strip in place, kit resolves support/rt relative to its own path. (c) trust self/exclusive Ir, not inclusive % (recursion in the recursive-descent parser makes --inclusive=yes double-count to absurd numbers). The Linux/ELF total is not comparable to the macOS/Mach-O hardware figure (different libc, sysroot, format; counts glibc + loader + the -lc probe) — the distribution is the point.

Heap allocation counts — KIT_METRICS=1 prints the hosted-heap counters (allocs / large allocs ≥32 KiB / reallocs / frees) at exit; the counts are host-independent (kit issues the same h->alloc calls everywhere):

KIT_METRICS=1 build/release/kit cc -c sqlite3.c --sysroot "$SDK" -o /tmp/k.o
# -> kit heap metrics: heap.allocs=… heap.large_allocs=… heap.reallocs=… heap.frees=…

Code size (.text machine code, the honest metric):

build/release/kit cc -c sqlite3.c --sysroot "$SDK" -o /tmp/k.o ; build/release/kit size /tmp/k.o
tmp/tinycc/tcc -c sqlite3.c -o /tmp/t.o ; build/release/kit size /tmp/t.o
# per-mnemonic excess:
hist(){ build/release/kit objdump -d "$1" | grep -E '^[[:space:]]+[0-9a-f]+:' \
  | sed -E 's/.*\t([a-z][a-z0-9._]*).*/\1/' | grep -E '^[a-z]' | sort | uniq -c | sort -rn; }
diff <(hist /tmp/k.o) <(hist /tmp/t.o)

End-to-end correctness (sqlite as a correctness test, both opt levels):

build/release/kit cc sqlite3.c shell.c -o /tmp/sq --sysroot "$SDK" -lc
/tmp/sq :memory: "create table t(a,b); insert into t values(2,40),(10,32);
                  select sum(a)+sum(b), count(*) from t;"   # -> 84|2

Synthetic scaling guard (make bench-cc): sweeps each input dimension (fn-count, body-size, global-decl, type-decl, locals-per-fn, pp-macro, pp-include, ref-density, obj-count, symbol-count) over a geometric series, fits a scaling exponent (p ≈ 1.0 goal, p ≥ 1.4 flagged SUPERLINEAR — treat as a bug), samples hotspots, and records a clang reference. Output in build/bench/cc/ (scaling.md, hotspots.md). Use it to catch a re-introduced O(n²); use the sqlite profile to decide where to optimize (the synthetic axes over-weight codegen vs real code). Sources of truth: scripts/cc_bench_gen.py (axis catalog), scripts/cc_bench.sh (harness), scripts/cc_bench_report.py (fit/verdicts).

4. Ideas for improvement (forward-looking, ranked)

Ordered by instruction/byte-payoff × structural leverage. The architecture's asset — the CgTarget→NativeTarget polymorphism (one frontend; aa64/x64/rv64/rv32 + wasm + c_target + check backends, plus the opt-IR recorder at -O1) — stays. Everything below lives in one of: the front half, the type subsystem, inside the concrete NativeDirectTarget/MCEmitter (the -O0 register machinery + byte sink, not the swappable vtable), or the code-size track (which bytes the NDT emits).

4.1 Compile speed (frontend-bound)

Lean-token loc-materialization fix — Stage 1 DONE (-c −24 M net win). The boundary rewrite's initial +62 M -c regression was two lazy-loc implementation costs, both now fixed byte-identically (frontend-only, no CG-API change):

Result: lex+pp −44 M (the scanner no longer builds a SrcLoc per token), parse+CG +19 M residual, net −24 M (§1, §2), perf-gate byte-identical.

Stage 2 (optional, ~+19 M parse+CG residual). The residual is the per-statement loc lookup at pcg_set_loc (CG source-loc) that the old eager-on-token loc got for free. g->cur_loc is consumed only by DWARF (gated on g->debug), descriptor locs, and cold CG compiler_panics — so with -g off and no error it is discarded. Carrying it as a LocRef (a kit_cg_set_locref + a "resolve LocRef→SrcLoc" callback the frontend registers, so cold CG diagnostics still materialize exactly) would skip those per-statement lookups entirely. Smaller payoff than Stage 1, needs a contained CG-API addition + the parser loc-plumbing; gate: byte-identical (-g DWARF + diag battery unchanged).

Status (prior campaign). Most of §4.1 has now landed, byte-identical, for a combined −43.7 M -c instructions (−2.29 %) on sqlite vs the pre-campaign snapshot (sqlite .o + -E bit-for-bit identical; 60/60 gate; full parse/pp/cg /toy/smoke-x64/rv64/debug/dwarf suites green). Item-by-item below: #1 ✅ (landed earlier, 5ff33ea3); #2 ◐ (a+c landed d07e43a3+c8ee9133; b deferred — near-zero payoff, see note); #3 ✅ (object-macro replay 7ada3f62, function-macro replay d59dff08, lexer-level newline elision 811351c2); #4 ◐ (Cut A f368c7f8 + Cut B 94e642e3 landed; the dead paste-file-id register, Cut C, left as a small follow-on); #5 ○ open.

  1. ✅ [DONE — 5ff33ea3] Symbol-binding cache on the interned Sym — the highest-value front-half brick. scope_lookup is an N-scope chain walk per identifier (lang/c/parse/ parse.c, ~12 call sites); tcc caches the binding on the interned token. A Sym-keyed binding stack with push/restore on scope enter/exit makes resolution a pointer load. Medium-high risk (save/restore + shadow/redef/typedef-vs-ident discipline); byte-identical gate, full parse corpus.
  2. ◐ [a+c DONE; b deferred] Type subsystem (#2 self-Ir cluster, ~14 %). Done: single-decode the per-op predicate gauntlet — hoist one api_type_pred_bits per id and test API_PRED_* masks locally instead of re-calling cg_type_is_* (each a fresh id→entry+unalias decode) on the load/store/convert hot paths (d07e43a3); fuse the redundant resolve_type into the following api_unalias_type, and route the hot cg_adapter helpers through the slot's cached cg_id instead of the uncached pcg_tid bridge (c8ee9133). Deferred: collapsing the duplicate c_abi_record_layout (frontend) vs abi_cg_record_layout (backend) memos — both are already memoized at O(#distinct records), so the collapse saves only the duplicate build (< 0.01 % of total) against real boundary/byte-identity risk; not worth it now. Optional remaining: cache pred_bits on the ApiSValue slot itself (free ApiBitField.pad bytes) — measure first, retype-invalidation surface.
  3. ✅ [DONE] Token relay (lex+pp). Macro bodies with no ## now replay by pointer (object-like 7ada3f62; function-like skips the subst_phase2 copy, d59dff08). Non-directive newlines are no longer materialized by the lexer on the cc path (811351c2, −32 M -c): an emit_newlines lexer mode suppresses them while still emitting the one newline that terminates a directive line (Option B2 — no cross-frame coupling); -E/cpp keep them. Line numbers safe by construction (counter advances on byte-consume, loc rides every token); verified bit-identical on -E, -c, and -c -g DWARF.
  4. ◐ [Cut A+B DONE; Cut C open] lex_open_mem per-open work (~6,000 opens: 3,140 files + 2,796 macro-paste buffers). Done: paste buffers skip the lex_fold_splices memchr scan via a guarded splice-free fast path (f368c7f8, they are interned already-folded spellings — provably splice-free); the per-file-open full-struct memset is right-sized to just the punct_sym sentinel array (94e642e3). Open (Cut C): the dead paste file-id registration could become a bare nfiles++ after auditing no diagnostic ever queries a paste file-id.
  5. ◑ [arena churn LANDED; memset OPEN] memset / arena churn (~2–3 %). Arena churn done: blocks now grow geometrically and arena_reset retains the high-water capacity instead of freeing all-but-head (large block allocs −72 %, byte-identical) — see §2 Allocator. Still open: right-size per-expression / per-emit struct zeroing (designated-init the per-op clears). (memset here is explicit zero-init, not -ftrivial-auto-var-init — proven by rebuilding with the flag off; attack call sites, keep the hardening flag.)

Near-dead-ends for instructions (revisit only under a cache-stall study, not expected to pay): the pool_intern_slice probe/insert side (the self-sufficient {hash,sym} slot measured ~0 Ir); lex_next itself (raw-cursor scanner is optimal); aa_emit_mem typed-store micro-levers.

4.2 Code size (run-correctness-gated; multiplicative — each byte cut shrinks emit + objwrite + assemble together)

  1. Trim the over-reserved far-slot/large-frame patch region (new, +12,897 nop / ~52 KB — the whole 0.951×→0.986× erosion). The aa64 far-slot address-build / large-frame fallback now reserves a fixed branched-over 5-instruction patch region in ~2,587 functions' prologues (a b over five nops when the long path is unused), so every qualifying function pays 24 B of padding even when the short path suffices. This is correctness-first and probably over-reserved: reserve only when the frame/slot actually needs the long form, or shrink the reservation to the real worst case (and patch the branch away when unused). Investigate before touching spills — it's likely the cheapest byte win on the board. Gate: run-correctness + determinism (this is the codegen path the recent correctness fixes added).
  2. Spill reduction — the #1 remaining local code-size excess (+47 K). The single-pass NDT spills more than tcc keeps resident across statements and control-flow joins. The no-new-analysis wins (dead-operand drop, materialize-before-flush) are done; deeper residency = keeping a live value in a register across a join, which is register allocation and out of simple single-pass scope. Pursue as a separate -O1-style pass over the NDT, or a cheaper "pin the hot local across a straight-line run" heuristic.
  3. Positive-offset frame addressing (kills the residual sub xN,x29+movk, ~3.5 K). The machinery already exists — aa64 has a bottom-record layout (fp_at_bottom, frame_size−off) + an AAPatch deferred-patch list, currently gated to -O1 known-frame. Extend to -O0 by deferring per-slot offsets (emit scaled str/ldr with an imm12 placeholder, patch (N−off)>>scale at func_end; scaled imm12 reaches 32,760 B so the placeholder is always one word). alloca-safe via a stable base anchor (the fp-at-bottom / a callee-saved frame base plays tcc's stable-x29 role). Compile-speed risk (per-access bookkeeping) — gate it.
  4. Residual arg/value movs (+13.7 K). Forward-order materialization places straightforward args directly in their ABI register; what's left is args it can't place — a nested-call result already in x0, or a value spilled under pressure. A per-arg destination hint (abstract arg-slot threaded frontend→CG-API→backend, resolved to the physical reg) would let the producer target the exact register in those cases. High plumbing, high correctness surface; the win is the residual only.
  5. Signed load-with-extend ldrb;sxtb→ldrsb (the unsigned zero-extend cases are done). Structurally blocked: needs a load-with-extend rider on MemAccess (kit's CG integer types are sign-agnostic, so nd_load can't know the value feeds a sign-extend) — a frontend widening signed load, not a register rename.
  6. Smaller, self-contained: indexed-addressing fold (collapse base+index+disp into one EA where a member offset currently forces an extra add), NOP/alignment-pad trimming, call-argument stack-spill reduction.

4.3 The end-state bet (large lift, optional)

tcc's shape: a shared mutable token slot fed by both scanner and macro replayer (no per-stage Tok structs), identifiers resolved through symbol pointers cached on the interned token, a thin SValue[] the parser drives by calling emit directly. This is the "clean structural redesign" the project prizes and subsumes §4.1. But the value-stack→direct-emit vtable collapse is explicitly out of scope here: the two real indirect calls per primitive are the price of the seven-backend modularity and are kept. The seam-preserving items above plus the code-size track are the campaign from here; the ~2× headroom a full tcc-shape collapse might reach is not pursued.

Measured dead ends — do not retry

5. Methodology notes