commit 942c3090611c0ac05b3c024bb3a5b8c380863d86
parent 3dbbfcf1bb2cc2e23eee8a8f147c107b5d3d84bc
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Sat, 13 Jun 2026 16:23:55 -0700
doc(plan): PERF-O0-CODESIZE.md — record landed Lever 2 + re-rank §4
Lever 2 (eager dead-operand drop + nd_cmp_branch materialize-before-flush
reorder + 2c) landed: 1.16x -> 1.091x tcc, +55,698 -> +31,117 excess
insns. Refresh §1 standings, §2 landed table, §3 diagnosis (mov +44,877
is now #1 by far; spill mnemonics dropped ~9 K each), re-rank §4 (Lever 1
is now the single biggest remaining win; add §4.6 reorder-the-other-
barriers and §4.7 in-place-binop-into-killed-reg follow-ons), and mark §6
landed.
Diffstat:
1 file changed, 94 insertions(+), 44 deletions(-)
diff --git a/doc/plan/PERF-O0-CODESIZE.md b/doc/plan/PERF-O0-CODESIZE.md
@@ -25,12 +25,13 @@ follow once the design is proven.
| metric | kit | tcc 0.9.28 | ratio |
|---|--:|--:|--:|
-| **machine code (`.text`)** | **1,593,732 B / 398,433 insns** | **1,370,940 B / 342,735 insns** | **1.16×** |
+| **machine code (`.text`)** | **1,495,408 B / 373,852 insns** | **1,370,940 B / 342,735 insns** | **1.091×** |
**The honest size metric is the `.text` machine code**, and there kit is now
-**1.16× tcc, +55,698 excess instructions** — down from 1.33× / +112,811 at the
-start of this campaign (half the excess removed; §2). The object file (Mach-O vs
-tcc's ELF) is not comparable, and compile-speed lives in `PERF.md`.
+**1.091× tcc, +31,117 excess instructions** — down from 1.16× / +55,698 after
+Lever 2 landed (§2; ~44% of that excess removed), and 1.33× / +112,811 at the
+start of this campaign. The object file (Mach-O vs tcc's ELF) is not comparable,
+and compile-speed lives in `PERF.md`.
**Reproduce:**
@@ -60,6 +61,14 @@ clang-differential probes). Design rationale lives in each commit message.
| **L4-P2** | copy source materialized straight into the destination register (was scratch-load + `mov`) | −16,151 | shared |
| **L3** | elide the zero-extend after a narrow zero-extending load (`uxtb`/`uxth`/`ubfx`) | −3,587 | shared |
+**Lever 2 — spill reduction (§6), landed as one commit:** −24,581 (−6.17%).
+
+| sub-change | what | aa64 insns | where |
+|---|---|--:|---|
+| **2a** | eager dead-operand drop: `api_op_kill_if_dead` sets `OPK_FLAG_KILL` on dead-transient binop/cmp/unop/store operands; `nd_drop_killed_operand` drops them after the op with no write-back (so they are not flush-stored at the next barrier) | −2,533 | shared |
+| **2a-branch** | `nd_cmp_branch` materializes the compare operands **before** the flush (a cached operand is read from its register instead of spilled-then-reloaded; a dead one is dropped), and `control.c` flags dead branch operands | −21,987 (mostly `ldur`/`stur`) | shared |
+| **2c** | skip the value-cache flush at pure memory barriers (volatile/atomic/fence) — the cache holds only non-escaped locals, which they cannot alias | ~0 on sqlite | shared |
+
¹ L4-P1 is gated to a new `NativeRegInfo.ndt_result_reg_stable` capability —
**on** for aa64 (x0 is clobbered only at calls) and sound for rv64 (a0), **off**
for x86-64 (RAX is an implicit div/mul operand: a result left there is clobbered
@@ -77,19 +86,21 @@ ratio 3.45×→1.33× before this campaign.
---
-## 3. Diagnosis — where the remaining 55,698 excess lives
+## 3. Diagnosis — where the remaining 31,117 excess lives
-Per-mnemonic signed diff (kit − tcc) on the current `.text`:
+Per-mnemonic signed diff (kit − tcc) on the current `.text` (post-Lever-2):
| mnemonic | kit | tcc | **excess** | what it is |
|---|--:|--:|--:|---|
-| `mov` | 48,561 | 3,701 | **+44,860** | reg-reg copies — **#1 remaining**: arg setup into x0–x7 (~30 K) + residual materialize/value-stack copies |
-| `ldur` | 71,934 | 37,994 | **+33,940** | frame reloads — register pressure |
-| `stur` | 48,913 | 15,899 | **+33,014** | frame spills (≈3× tcc) — register pressure |
-| `str` | 22,668 | 8,211 | **+14,457** | "" (more spills) |
-| `sub` | 11,484 | 6,713 | +4,771 | residual `sub xN,x29` (byte/half far slots + &local) |
-| `movk` | 2,371 | 357 | +2,014 | far-offset builds in the residual `sub` paths |
-| `sxtb`+`sxth` | 1,341 | 99 | +1,242 | sign-extend after a narrow load (L3 did the unsigned half only) |
+| `mov` | 48,578 | 3,701 | **+44,877** | reg-reg copies — **now #1 by far**: arg setup into x0–x7 (~30 K) + residual materialize/value-stack copies. Untouched by Lever 2 (spill-focused); this is **Lever 1** (§4.1) |
+| `ldur` | 62,851 | 37,994 | **+24,857** | frame reloads — register pressure (was +33,940; Lever 2's branch reorder cut ~9 K) |
+| `stur` | 39,867 | 15,899 | **+23,968** | frame spills (was +33,014; Lever 2's dead-operand drop cut ~9 K) |
+| `str` | 20,123 | 8,211 | **+11,912** | "" (more spills; was +14,457) |
+| `cbz` + `b.eq`/`b.ne`/… | — | — | (not excess) | kit fuses `if(x)`/compares into `cbz`/`b.cc` (tcc materializes a bool then tests) — *fewer* total insns; ignore the per-mnemonic split |
+| `sub` | 11,116 | 6,713 | +4,403 | residual `sub xN,x29` (byte/half far slots + &local) — **Lever 3** |
+| `movk` | 2,365 | 357 | +2,008 | far-offset builds in the residual `sub` paths — **Lever 3** |
+| `sturb`+`sturh` | 2,990 | 738 | +2,252 | narrow-type frame spills — register pressure on byte/half locals |
+| `sxtb`+`sxth` | 1,341 | 99 | +1,242 | sign-extend after a narrow load — **Lever 4** (L3 did the unsigned half only) |
Where **kit already beats tcc** (do not touch — structural wins):
@@ -112,34 +123,49 @@ was how each reached a *far* local (past `stur`'s ±256): kit built the address
one insn, no address build) — so kit now does far addressing *better* than tcc
(`movn` 0 vs 6,720; 28 K `[sp]` accesses are the migrated slots).
-**The remaining gap is register pressure, not addressing.** kit emits ~72 K
-stores vs tcc's ~25 K (3×) and 102 K loads vs 87 K: it keeps fewer live values in
-registers across statements than tcc's value stack, so it stores-and-reloads the
-frame far more. That excess (`mov` arg-setup + `stur`/`ldur`/`str`) is the
-compute-into-place / value-residency frontier (§4).
+**The remaining gap split, post-Lever-2.** Lever 2 closed most of the *barrier*
+spill/reload excess (stores 72 K→63 K, loads 102 K→90 K; the `nd_cmp_branch`
+reorder alone removed ~9 K reloads by not spilling-then-reloading every compare
+operand). What is left is two distinct frontiers:
+
+1. **`mov` (+44,877) — now #1 by a wide margin.** This is `mov`-into-place, not
+ spilling: ~30 K is arg setup into x0–x7, the rest residual value-stack copies.
+ Lever 2 (spill-focused) does not touch it; it is **Lever 1** (§4.1,
+ destination-hint placement).
+2. **Residual spills (`stur`+24 K, `str`+12 K, `ldur`+25 K).** kit still spills
+ more than tcc's value stack keeps resident across *statements* and across
+ *control-flow joins*. Closing that is register allocation at joins (`§4.2`
+ note 2b), explicitly **out of single-pass -O0 scope** — the dead-operand part
+ that *was* in scope is now landed.
**Concentration.** The excess still clusters in the giant functions
(`_sqlite3VdbeExec` etc.); per-function spill counts dominate there.
---
-## 4. Remaining levers (ranked)
+## 4. Remaining levers (ranked, post-Lever-2)
| # | Lever | Est. saving | Risk | §|
|---|---|--:|---|---|
| **1** | Args materialized into arg regs (L4 Phase 3) | ~30 K `mov` | high (frontend/CG-API + arg-shuffle correctness) | §4.1 |
-| **2** | Reduce frame spilling / extend value residency | up to ~50 K (stores+reloads) | high (register-allocation reach) | §4.2 |
-| **3** | byte/half far slots → positive-scaled (extend L1) | ~1,940 `sub` + some `movk` | med (overflow fallback) | §4.3 |
+| **3** | byte/half far slots → positive-scaled (extend L1) | ~4.4 K `sub` + ~2 K `movk` + narrow spills | med (overflow fallback) | §4.3 |
+| **6** | extend the §6 reorder to other flush-first barriers (switch-selector residency, indirect-branch) | ~few K (per-case reloads) | med (selector pinning) | §4.6 |
+| **7** | in-place binop/cmp into a killed operand's register (reuse the freed reg as dst) | moderate (eviction spills) | med | §4.7 |
| **4** | Signed load-with-extend (`ldrsb`/`ldrsh`) | ~1,242 `sxtb`/`sxth` | med (frontend widening load) | §4.4 |
| **5** | rv64 L4-P1 (flip `ndt_result_reg_stable`) | rv64 only | low (on-target check) | §4.5 |
-Levers 1–2 are the bulk of what's left and both reduce to one structural change:
-**demand-driven value placement** — keep a value where its consumer wants it,
-materialized at the point of use, instead of producing into a cache-allocator
-register and relocating. tcc gets this from its lazy `SValue`/`gv(rc)` model
-(`tcc.h:479`, `tccgen.c:1844`); kit's NDT cache is already a lazy-location model
-but is missing the destination-hint handoff (below). Re-profile after each
-landing — the highest lever moves as work is removed.
+**Lever 2 (§4.2 / §6) is landed** — the in-scope, no-new-analysis part of "reduce
+frame spilling." The deep residency reach (keep a *live* value resident across a
+control-flow join) is register allocation and stays out of single-pass -O0 scope
+(§6.4 2b). **Lever 1 is now the single biggest remaining win** (`mov` +44,877) and,
+like Lever 2, reduces to **demand-driven value placement** — keep a value where
+its consumer wants it, materialized at the point of use, instead of producing into
+a cache-allocator register and relocating. tcc gets this from its lazy
+`SValue`/`gv(rc)` model (`tcc.h:479`, `tccgen.c:1844`); kit's NDT cache is already
+a lazy-location model but is missing the destination-hint handoff (§4.1). The
+landed dead-operand drop is the *foundation* for it: a killed operand's freed
+register is the natural destination for the next producer (§6.5). Re-profile after
+each landing — the highest lever moves as work is removed.
### 4.1 Lever 1 — args into arg-regs (L4 Phase 3)
@@ -161,22 +187,14 @@ remaining win; most plumbing (frontend + CG API + backend); highest correctness
surface (arg marshalling). The general destination-hint mechanism it introduces
also subsumes the residual materialize/value-stack `mov`s.
-### 4.2 Lever 2 — reduce frame spilling / extend value residency
+### 4.2 Lever 2 — reduce frame spilling (LANDED, §6)
-The deepest structural gap: kit spills ~3× as much as tcc (§3). The NDT register
-cache flushes the live-across set at every call and holds a bounded set across
-statements; tcc's value stack keeps more operands unmaterialized and threads them
-through. Closing this is the path to ~1.0× parity, and it overlaps Lever 1 (both
-are "place the value where it's used, don't relocate"). It is the highest-reach
-change to the -O0 register model.
-
-**→ §6 is the grounded hand-off plan for this lever** — a code-traced root-cause
-(the 3× spill is dead transients flush-stored at mid-statement barriers) plus a
-concrete, mostly-already-built fix (eager dead-operand drop via the existing
-`OPK_FLAG_KILL`/`api_temp_dead` machinery). The deep "extend residency across
-barriers" reach (register allocation at joins) stays out of -O0 scope; §6 carves
-out the part that does *not* need new analysis and can land independently of
-Lever 1.
+The in-scope part of this lever is **landed** (§2, §6): eager dead-operand drop +
+the `nd_cmp_branch` materialize-before-flush reorder + 2c. Result −24,581 insns;
+stores 72 K→63 K, loads 102 K→90 K. The deep residency reach (keep a *live* value
+in a register across a control-flow join) is register allocation and stays out of
+single-pass -O0 scope (§6.4 2b) — pursue it only as a separate -O1-style pass, not
+within the NDT. §6 remains the code-traced record of the landed change.
### 4.3 Lever 3 — byte/half far slots (extend L1)
@@ -213,6 +231,31 @@ operands), so result-in-result-register caching is sound there — flip
(build the p1-x64 probe for rv64 and run it through the emulator / a rv64 host).
Small, low-risk, rv64-only win.
+### 4.6 Lever 6 — extend the §6 reorder to the other flush-first barriers
+
+§6's `nd_cmp_branch` win was *materialize-before-flush* (read the operand from its
+register instead of spill-then-reload). The same pattern is still un-applied at the
+other ops that flush *before* reading an operand, all single-pass-local:
+- **switch selector residency.** `nd_switch` flushes, then `cg_lower_switch_default`
+ emits one `cmp_branch` per case — each reloads the selector (the cache was just
+ emptied). Pin the selector across the case chain (or don't flush at `nd_switch`
+ and let it stay cached) so it is read once. Helps the big `VdbeExec`-style
+ dispatch chains; bounded by the chain-vs-jumptable threshold in `cg_plan_switch`.
+- **indirect branch** (`nd_indirect_branch`, computed goto) flushes then
+ materializes the target address — same reorder applies. Rare; low value.
+
+### 4.7 Lever 7 — in-place binop/cmp into a killed operand's register
+
+§6's dead-operand drop *frees* a killed operand's register after the op; the
+natural next step is to **reuse that register as the op's destination** in the same
+instruction — the binop/cmp analog of `nd_rename_killed_to_dst` (already done for
+copy/convert). aa64 binops are 3-register (`add dst,a,b`), so when operand `a`
+carries `OPK_FLAG_KILL` and `dst` is a fresh cacheable transient, rename `a`'s reg
+to `dst` instead of allocating a fresh `dst` reg — avoiding the `nd_dst_reg`
+allocation (and its eviction spill under pressure). Soundness mirrors the existing
+rename (the op reads both operands before writing `dst`, so a self-referential
+`dst==a` is fine). Composes with Lever 1's destination hint.
+
---
## 5. Gate & measurement methodology
@@ -236,7 +279,14 @@ Small, low-risk, rv64-only win.
---
-## 6. Lever 2 in depth — spill reduction via eager dead-operand drop (hand-off plan)
+## 6. Lever 2 in depth — spill reduction via eager dead-operand drop (LANDED)
+
+**Status: landed** (§2; commit on `main`). 2a + the `nd_cmp_branch`
+materialize-before-flush reorder + branch-operand kill + 2c, −24,581 insns
+(−6.17%), gated (§5) on aa64/x64/rv64. The branch reorder — *not* in the original
+plan below — turned out to be the bulk of the win (the flush-first `nd_cmp_branch`
+was spilling-then-reloading every compare operand; ~21 K of the 24.6 K). The
+sections below are the code-traced design that led there, kept as the record.
A code-traced plan for §4.2's "reduce frame spilling" lever, scoped to the part
that needs **no new dataflow analysis** because the liveness it relies on is
