commit 04a3a3a7d5a09b7fe3059e94abcb8009e9936fec
parent 8826982db37ad31cf01fc2249e1006f31a351daf
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Mon, 15 Jun 2026 21:09:11 -0700
doc/plan/O1.md: roadmap for closing the -O1 code-quality gap to clang
Captures the disassembly-audit analysis: the gap to clang -O1 (~1.25x text
aggregate but bimodal; concentrated in large high-pressure functions like
luaV_execute at 5.6x), the dominant root cause (heavy spilling + negative-fp
`sub x17,x29,#imm; ldur` spill addressing = 36% of lvm / 12% of sqlite insns),
and a ranked, linear-feasible worklist (W1 positive-offset/SP-relative spill
addressing + interim sub-CSE, W2 rematerialization, W3 linear coalescing, W4
inline-pressure cap, W5 local load/CSE, W6 cmp-imm/addr-mode peepholes), with
the SSA-only opts (GVN/DSE/LICM/IV) called out as O2 territory. Indexed in
doc/plan/README.md and cross-referenced with OPTIMIZER.md/PERF.md/OPT.md.
Diffstat:
2 files changed, 800 insertions(+), 0 deletions(-)
diff --git a/doc/plan/O1.md b/doc/plan/O1.md
@@ -0,0 +1,799 @@
+# O1 code quality: closing the gap to clang `-O1`
+
+**Goal.** Improve the *runtime quality* (density + efficiency) of kit's `-O1`
+emitted code **without making the `-O1` compile superlinear**. `-O1` is, by
+design, a no-SSA pipeline (Section 3 of [doc/OPT.md](../OPT.md)): local + linear-scan
+machinery only, no dominance-frontier phi insertion, no value numbering. Every
+item here must keep that property — a transform that needs SSA, a full
+interference graph, or any O(n²) analysis belongs in the parked **O2 mid-end**,
+not here.
+
+This doc is the forward-looking worklist. The design reference for the passes it
+touches is [doc/OPT.md](../OPT.md); the *compile-speed* roadmap (a separate axis —
+that doc explicitly does not care about generated-code quality) is
+[PERF.md](PERF.md). The broader optimizer roadmap (completing the O2 SSA mid-end,
+machine register-constraint work) is [OPTIMIZER.md](OPTIMIZER.md) — this doc is
+the narrow, near-term slice: `-O1` density within the linear/no-SSA budget. Read
+the first two before starting.
+
+Two rules, mirroring PERF.md:
+
+- **A superlinear axis is a bug.** `-O1` compile time must stay ≈ linear in
+ function size/count. A small per-function sort over side tables (for example,
+ frame slots) is acceptable only if it stays immaterial in sqlite timing; no
+ transform should add an O(n²) or per-instruction superlinear axis. Validate
+ with the synthetic sweep in OPT.md §8 and by timing sqlite `-O1` before/after
+ (it is ~1.6 s today; a quality change should not move it materially).
+- **Gate every change on correctness, not byte-identity.** These changes
+ deliberately alter emitted bytes, so the gate is: `make test-opt test-toy`,
+ the ecosystem golden + vs-clang run at `-O0`/`-O1` (`make test-ecosystem`,
+ 28/0), and `make test-smoke-x64 test-smoke-rv64`. Add a structural disasm
+ guard per change under `test/opt/` (see `redundant_copy_ext.sh`).
+
+---
+
+## 1. Methodology
+
+All numbers below: Apple-silicon arm64 / Darwin, `-O1`, release kit at
+**`build/release/kit`** (`make bin RELEASE=1`). Pitfalls that cost real time:
+
+- `make bin RELEASE=1` writes **`build/release/kit`**, *not* `build/kit`
+ (`build/kit` may be a stale debug binary). Measure with the release binary.
+- A kit binary copied outside the build tree fails with `support dir not found`
+ (the rt/support dir resolves relative to the exe path). To A/B two builds, keep
+ both binaries **inside `build/release/`** (e.g. `kit_baseline`, `kit_fixed`).
+- clang on macOS needs `-isysroot "$(xcrun --sdk macosx --show-sdk-path)"`; kit
+ needs `--sysroot "$SDK"`.
+
+Per-file comparison (text size + instruction mix):
+
+```sh
+SDK="$(xcrun --sdk macosx --show-sdk-path)"
+kit cc -O1 -c f.c -I... --sysroot "$SDK" -o k.o
+clang -O1 -c f.c -I... -isysroot "$SDK" -o c.o
+size -m k.o | awk '/__text/{print $NF}' # __TEXT bytes
+kit objdump -d k.o | grep -cE ':\t' # instruction count
+```
+
+The ecosystem sources are provisioned at `scripts/ecosystem.sh srcdir <name>`
+(lua, sqlite, cjson, lz4, miniz, yyjson, tinyexpr). **TODO:** codify the A/B
+harness as `scripts/o1_quality.sh` (build baseline+fixed into `build/release/`,
+diff text/mix across the corpus) — it was ad-hoc for this analysis.
+
+---
+
+## 2. Current standings (2026-06-15, after commit 8826982d)
+
+**Aggregate `__TEXT` ≈ 1.25× clang `-O1`** across the corpus — but the ratio is
+bimodal and the aggregate understates the truth:
+
+| file | kit/clang | note |
+|---------|----------:|------|
+| lz4 | **0.39×** | clang unrolls/inlines hot loops → *clang* is bigger |
+| lapi | 0.83× | kit smaller |
+| yyjson | 0.88× | kit smaller |
+| lparser | 1.09× | ~par |
+| sqlite | 1.27× | |
+| cjson | 1.33× | |
+| miniz | 1.94× | |
+| lvm | **4.66×** | pathological — the lua interpreter loop |
+
+On **small-function code kit is competitive or smaller** than clang (clang `-O1`
+trades size for speed via inlining + loop unrolling — not a kit deficiency). The
+real gap — *removable work kit emits that clang does not* — concentrates in
+**large, high-register-pressure functions**:
+
+- `luaV_execute` alone is **5.6× clang (22,175 vs 3,980 insns)** and is **92% of
+ lvm's gap**. sqlite's big interpreter-style functions behave the same.
+
+### The dominant symptom: spilling + spill addressing
+
+| file | insns | `sub xN,x29,#` | % of insns | `[x17]` spill accesses |
+|--------|--------:|---------------:|-----------:|-----------------------:|
+| lvm | 24,197 | 8,774 | **36%** | 8,053 |
+| sqlite | 292,039 | 35,426 | **12%** | 29,361 |
+| miniz | 29,074 | 2,181 | 8% | 2,014 |
+| cjson | 5,302 | 33 | ~1% | 0 |
+| yyjson/lz4/lapi/lparser | — | ~0 | ~0% | ~0 |
+
+Two compounding problems, both visible in `luaV_execute`:
+
+1. **kit spills far more than clang.** lvm: ~8,053 stack accesses (kit) vs ~236
+ (clang) — a ~34× difference in stack traffic. Root cause: a giant
+ post-inlining function + a linear-scan allocator with no splitting/coalescing.
+2. **Each spill is addressed with two instructions.** Spill slots sit at
+ *negative* offsets from the frame pointer `x29`, beyond `ldur`'s ±256 unscaled
+ range, so kit emits:
+
+ ```asm
+ sub x17, x29, #552 ; recompute slot address
+ stur x11, [x17]
+ sub x17, x29, #552 ; ← recomputed again for the very next access
+ ldur x9, [x17]
+ ```
+
+ clang addresses the same slots as `str [sp, #0x88]` — a single **scaled,
+ positive** offset (`ldr`/`str` reach 0..32760). ~**2,478 of lvm's subs are
+ immediately redundant** (same offset recomputed back-to-back).
+
+Instruction-mix delta that follows from this (lvm, kit vs clang): `sub` 8,887 vs
+78; everything else is within ~1.1–1.5× (`ldr` 1,072 vs 933, `mov` 820 vs 691,
+`add` 573 vs 512). **The gap is not broad — it is spill addressing on big
+functions, plus the spilling that feeds it.**
+
+Problem (2) is **arch-specific**, which shapes W1 (see §3): it is acute on aa64
+(`ldur` reaches only ±256, so any far slot needs an address recompute) and
+present-but-milder on rv64 (`ld` reaches ±2 KB). **x64 has it for free** — `mov
+[rbp-disp32]` always addresses any slot in one instruction (and auto-selects the
+1-byte `disp8` form when in range), so x64 emits no frame-address recompute at
+all. Problem (1), the over-spilling, is arch-neutral.
+
+---
+
+## 3. Worklist (linear-feasible), in priority order
+
+Each item: mechanism · where · expected impact · why it stays linear · risks.
+
+### W1 — Optimal known-frame layout: hot-slot-low ordering + positive-offset addressing ★ highest leverage
+
+**The reframing.** At `-O1` the frame is *fully known before the body is emitted*
+— `*_func_begin_known_frame` fixes `frame_size_final` and sets `frame.frame_final`
+before any body instruction (aa64 `native.c:2070/2094`). That is a standing asset
+the `-O0` single-pass path lacks, and the optimal known-frame design exploits it
+two ways — one shared across all three arches, one aa64-specific:
+
+1. **(shared) Hot-slot-low frame ordering.** Order the body frame slots so the
+ most-frequently-accessed spills get the *smallest final displacement from the
+ addressing base used by that layout*. Small offsets are cheapest to encode on
+ every arch: `disp8` vs `disp32` on x64 (3-byte vs 7-byte access), inside the
+ scaled reach on aa64, inside the ±2 KB `imm12` window on rv64. This is a
+ layout *choice* — zero added analysis; just do not confuse raw slot-allocation
+ order with the final displacement when a backend uses a bottom-record or
+ positive-offset layout.
+2. **(aa64) A uniform x29-at-bottom frame.** Anchor x29 below the static slots so
+ every slot is a one-instruction positive `ldr/str [x29,#k]`, for every known
+ frame — replacing the `sub x17,x29,#k; ldur` fallback. x29 is the (always
+ reserved, alloca-stable) frame pointer, so this needs no register and no
+ regalloc change, and alloca falls out for free (W1.1).
+
+The addressing story differs sharply per arch — **measure before assuming a gap**:
+
+| arch | in-range access | far-slot path today | W1 work |
+|------|-----------------|---------------------|---------|
+| aa64 | `ldur` ±256 only | `sub x17,x29,#k; ldur` (2–4 insns, recomputed each access) | **uniform x29-at-bottom (big)** + ordering |
+| rv64 | `ld off(s0)` ±2 KB | `lui;addi;add x; ld 0(x)` (2–4 insns, each access) | ordering (then assess positive layout) |
+| x64 | `mov [rbp-disp32]` (always 1 insn, auto disp8) | — none — | ordering only (disp8 density) |
+
+x64 has **no** address-recompute path (`x64_emit_mem`, `x64/native.c:638`; disp8/
+disp32 auto-selected in `x64/isa.h:414`), so for x64, W1 is *only* the shared
+ordering and purely a density micro-win.
+
+#### W1.0 — Hot-slot-low frame ordering (shared; all arches)
+
+**Mechanism.** Thread a per-slot priority from the allocator's spill-cost metric
+into frame layout, and present body slots to the backend in the order that gives
+hot slots the smallest final displacement. For today's x64/rv64/fp-relative
+layouts this is the same as handing the bump allocator
+(`native_frame_slot_alloc`, `cg/native_frame.c:45` — monotonic `cum_off`) hot
+slots first; for a positive/bottom-record layout, verify the final offset formula
+before assuming the same order.
+
+**Where + how.**
+- Add a priority field to `IRFrameSlot` (`src/opt/ir.h`) and to
+ `NativeFrameSlotDesc` (`src/arch/native_target.h:41` — there is a spare `u8 pad`
+ at line 49 to widen).
+- Stamp it from the allocator's final spill-slot assignment, not just first
+ creation. `spill_slot_for` (`pass_lower.c:578`) sees the first PReg that creates
+ a frame slot, but `alloc_assign_group_stack` can later reuse that same slot for
+ non-overlapping PRegs. The slot priority should aggregate the traffic of every
+ PReg/group assigned to that slot (saturating sum, or max if measurement shows
+ sum is too noisy), using the metric `pass_live.c:844` computes:
+ `2*use_freq + def_freq + live_across_call_freq + live_block_freq`. Homed
+ (address-taken) locals keep priority 0 for v1 — the hot traffic is spills, not
+ homed locals.
+- Copy `priority` through the desc-build loop in `opt_emit_native`
+ (`pass_native_emit.c:~1513`).
+- Just before `t->func_begin_known_frame(...)` (`pass_native_emit.c:~1544`), build
+ an index permutation over the slot descs, **stable-sort by descending
+ priority** (skip any `NATIVE_FRAME_SLOT_FIXED_OFFSET` slot), and present descs
+ in that order. Map each returned `NativeFrameSlot` back through the permutation
+ so `e->slot_map[frame_slots[order[k]].id]` stays correct.
+
+The backend body list (`frame->slots[]`) holds only LOCAL/SPILL slots; the
+constrained slots (callee-saves, sret/va homes, aa64 atomic scratch,
+alloca/outgoing areas) are reserved by the backend *outside* this list and are
+untouched by the sort. No target analysis changes, but validate the final offset
+formula per backend (especially after W1.1's bottom-record aa64 layout) before
+claiming a slot is "low."
+
+**Impact.** rv64: keeps the hottest spills inside the ±2 KB `imm12` window so they
+stay single-instruction. x64: more accesses encode as disp8 (−4 bytes each) —
+density only. aa64: mostly subsumed by W1.1 (every slot ≤32 KB is already
+single-instruction there); ordering is insurance only for >32 KB frames.
+
+**Linear?** Effectively yes — one `O(nslots·log nslots)` sort per function, off
+the hot per-instruction path. If the synthetic sweep or sqlite timing shows this
+is visible, switch to a linear bucket/radix ordering over the integer priority.
+
+**Risk.** Low — the gate is correctness, not byte-identity, so reordering internal
+slot offsets is free. The hazards: the `slot_map` permutation must be exact (a
+transposed mapping silently miscompiles every spill), and priority aggregation
+must include reused spill slots rather than only the first PReg that allocated
+the slot. Add an assert that every IR slot id maps to a distinct native slot.
+
+#### W1.1 — aa64 uniform x29-at-bottom known-frame layout (the big win)
+
+**Root cause (measured).** aa64's only wide single-instruction memory form is the
+*unsigned scaled* `ldr/str [base,#pos]` (reach 0..32760 by size); its signed
+unscaled `ldur` reaches only ±256. So one-instruction slot access requires the
+base to sit **below** the slots (positive offsets). Today the known-frame path
+anchors x29 at the *top* (top-record), so slots are at *negative* x29 offsets past
+±256 → the `sub x17,x29,#k; ldur` fallback (`native.c:1009`) that is 36% of lvm /
+12% of sqlite. The existing positive forms don't cover the functions that matter:
+`fp_at_bottom` is gated to ≤504-byte, `out_stack==0` frames (`native.c:2085`), and
+the single-pass `slot_sp_base` far-slot patch can't run on the known-frame path
+(it *panics* if a patch is left pending, `native.c:1923`). `luaV_execute` — big
+frame + `out_stack>0` — qualifies for none of them.
+
+**Design: one stable base below the slots, for every known frame.** Anchor x29 at
+the bottom of the static slots (just above the outgoing-arg area), uniformly, so
+every slot is `ldr/str [x29,#pos]` — one instruction within the 32 KB scaled
+reach, with the `add x16,x29,#hi; ldr [x16,#lo]` build only past it. The payoff is
+that x29 is the **frame pointer**: already reserved (never in `aa_int_allocable`,
+`native.c:4128`) and **stable across alloca** (set once; the body never moves it).
+Two consequences make this the clean choice:
+
+- **No optimizer/regalloc change — contained in the aa64 backend.** Unlike an
+ sp-base + x28-anchor scheme, there is no register to reserve and `machinize` is
+ untouched. The known-frame contract is honored by construction:
+ `aa_func_begin_known_frame` already has the *complete* frame
+ (`frame_size_final`, `max_outgoing`, `has_alloca`, the slot list, callee-saves)
+ and emits the final prologue in one pass — exactly what "known frame" means.
+- **alloca falls out for free.** x29 never moves, so `[x29,#k]` stays valid after
+ `alloca` lowers sp. No anchor register, no special path, no v2.
+
+**Layout** (`os` = `out_stack` = max outgoing-arg bytes, `fs` = frame_size):
+
+```
+high addr
+ incoming stack args (caller) ← CFA = x29 + (fs − os)
+ saved x29, x30 ← at [x29] / [x29+8] (frame-pointer chain)
+ static slots (locals/spills/saves/va-save) ← [x29+16 …], positive
+ x29 ───────────────────────────── ← anchor = sp_entry + os
+ outgoing args (os) ← [sp, #0 …], sp-relative
+ sp
+low addr
+```
+
+The saved pair sits **at** x29 so `[x29]` = caller fp and `[x29+8]` = caller lr —
+the frame-pointer chain kit's unwinder / `__kit_backtrace` walks (uniform
+fp[0]/fp[1]). This invariant is non-negotiable; it is *why* the pair is
+co-located with the anchor rather than left at the top. Outgoing args stay
+sp-relative (`[sp,#k]`), so calls after an alloca still address their arg area at
+the current sp.
+
+**Where + how (aa64 backend only — `src/arch/aa64/native.c`).**
+1. **Generalize the bottom-record layout** beyond today's `fp_at_bottom` gate:
+ make it the layout for *all* known frames except the Windows-variadic
+ `top_home` case (its GP home area must sit above the saved pair → keep that one
+ on top-record / fp-relative). Anchor `x29 = sp_entry + os`; `aa_fp_off_slot`
+ already returns a positive value in this mode (`frame_size − slot_off`),
+ generalized for the `+ os` shift.
+2. **Prologue** (`aa_build_prologue_words`): general form `sub sp,sp,#fs` (scratch-
+ materialized / Windows-probed for huge `fs`) · `stp x29,x30,[sp,#os]` ·
+ `add x29,sp,#os` · callee-save stores at positive x29 offsets. Keep today's
+ folded `stp [sp,#-fs]!` + `mov x29,sp` as an encoding fast-path when
+ `os==0 && fs≤504`.
+3. **Epilogue** — uniform sp recovery from the anchor, correct with or without
+ alloca (replaces the current two-path teardown; the post-indexed `ldp [sp],#fs`
+ can't be used once alloca floated sp): after callee-restores,
+ `mov x16,x29` · `ldp x29,x30,[x16]` · `add sp,x16,#(fs − os)` · `ret`.
+4. **Addressing** (`aa_emit_mem`): a frame slot is always `ldr/str [x29,#base_off]`,
+ `base_off = aa_fp_off_slot(slot) (+ extra)` (positive), emitted **directly**
+ (frame is final) — scaled when `≤32760`, else `add x16,x29,#hi; ldr/str
+ [x16,#lo]`. No `slot_sp_base`, no deferred `AA_PATCH_SLOT`, no `sub x17` on the
+ known-frame path. (Single-pass `-O0` keeps `slot_sp_base` + the patch — its
+ frame isn't final at emit time.)
+5. **CFI**: `CFA = x29 + (fs − os)`; saved fp/lr at `[x29]`/`[x29+8]`. Generalizes
+ the existing bottom-record CFI (the `os==0` case, `native.c:1929–1936`) to
+ `os > 0`.
+
+**Impact.** Removes essentially all of lvm's 8,774 and sqlite's 35,426
+frame-address `sub`s — for *every* function, alloca included. The single biggest
+`-O1` density lever; each slot access 2–4 insns → 1.
+
+**Linear?** Yes — a layout + per-access addressing choice; zero added analysis.
+
+**Risk — the highest blast radius in this doc.** It touches the prologue/epilogue,
+CFI, the bottom-record gate, tail calls (`AA_PATCH_TAIL`) and the slim tiers. Gate
+hard: aa64 smoke + toy corpus + ecosystem run-and-diff + `test/opt/prologue_tier.sh`
++ an unwinding/backtrace check (the fp-chain invariant) + a `test/opt/` disasm
+guard asserting large *and* alloca functions emit `ldr/str [x29,#…]` (or the
+add-build) and **no** `sub xN,x29,#…` for spill access. Re-verify the slim/leaf
+tiers and tail-call teardown against the generalized epilogue. Include structural
+cases at the scaled-offset boundary, past the 32 KB scaled reach, signed narrow
+loads, under-aligned aggregate chunks, `top_home`/Windows-variadic fallback, and
+an alloca-after-call path that proves outgoing args remain addressed from the
+current sp.
+
+#### W1.2 — rv64: order first, assess positive layout
+
+**Assessment first.** rv64's `imm12` window is ±2 KB — 8× aa64's `ldur` ±256 — so
+a hot slot is single-instruction (`ld off(s0)`, `rv64/native.c:819`) for any
+realistic hot working set. After W1.0 lands, **measure** rv64 far-slot traffic
+(`lui;…;add` builds, `riscv/native.c:807`) in hot loops on the corpus before
+building more. Expectation: hot-low ordering captures most of the win; the
+residual is cold-slot tail.
+
+**If measurement shows a real gap:** rv64 has no positive-offset layout and no
+patch infra today (all `s0`-relative negative). Two options, in order: (a) the
+W1a per-access local CSE (don't rebuild the identical `lui;addi;add` for
+back-to-back accesses to the same far slot); (b) a known-frame positive layout
+(slots at `frame_size - off` above the saved pair, `s0 = sp`) gated like aa64's,
+with `rv_s0_off_slot` branching on a layout flag — heavier, lower ROI given the
+wide window. Do **not** build (b) speculatively.
+
+#### W1.3 — x64: ordering only
+
+W1.0 is the entire x64 story: more spill accesses fall in `disp8` range
+(−4 bytes/access). No addressing change — `x64_emit_mem` is already
+single-instruction. Skip if x64 density is not a priority.
+
+#### W1a — local frame-address-`sub` CSE (interim / harness bootstrap)
+
+**Status: largely subsumed by W1.1.** Once aa64 addresses far slots positively,
+the back-to-back `sub x17,x29,#k` recomputes vanish for spill slots. W1a keeps two
+narrow uses: (a) a **safe first PR** that stands up the gate + a `test/opt/`
+structural guard before the larger W1.1 change, and (b) mop-up for the *residual*
+recompute cases W1.1 doesn't touch — far slots past the scaled reach (huge
+frames), GOT/global address rebuilds, and the rv64 `lui;…;add` rebuild (W1.2a).
+
+**Mechanism.** A per-block post-emit peephole: track "x17 currently holds base−K";
+drop a re-`sub`/re-build of the same K while x17 is unclobbered. Natural home:
+`mir_combine` (`src/opt/pass_combine.c`) tracking, or a tiny aa64/rv64 post-emit
+peephole. Bounded per-block state → linear.
+
+### W2 — Rematerialization instead of spilling
+
+**Mechanism.** At a use of a spilled value whose single definition is *cheaper to
+recompute than to reload*, emit the recompute at the use instead of a slot
+reload; drop the spill store when every use rematerializes. Conservative v1 set
+(input-less or frame-only producers, recompute ≤ reload cost):
+- `IR_LOAD_IMM` whose immediate is ≤2 insns (`movz`, or `movz;movk`);
+- `IR_ADDR_OF` of an `OPK_LOCAL` (one `add` off the frame base).
+
+Defer `IR_ADDR_OF(global)` (2 insns + reloc; `addr_of_global_cse` already hoists
+it) and large `IR_LOAD_CONST` (a 4-insn `movz;movk;movk;movk` is *worse* than a
+1-insn reload) for v1.
+
+**Where + how.**
+1. Linear pre-pass `opt_mark_remat(f)` (new, in `pass_lower.c`): for each PReg
+ record `remat_def[v] = InstId` iff it has exactly one def and that def is in
+ the v1 set above (no register inputs). One scan over all insts.
+2. Add one shared helper for "materialize this spilled/remat PReg at this use",
+ and route **every** spilled-use path through it. Do not only hook
+ `rewrite_one_operand` (`pass_lower.c:1383`): call args
+ (`rewrite_call_arg_operand`) and store values (`rewrite_store_value_operand`)
+ currently turn spilled PRegs into direct frame operands, and would still read
+ the slot if the defining store were removed.
+3. At ordinary reload/store insertion:
+ - On a **use** of a spilled remat PReg: clone the recorded def into `c->before`
+ with `dst = scratch` instead of appending an `IR_LOAD`.
+ - On the **def** of a spilled remat PReg: rewrite the def operand to scratch.
+ **Skip** the `IR_STORE` only when every later use is known to rematerialize;
+ otherwise keep the store for the remaining frame-use sites. The original
+ pure def then writes a dead scratch and `mir_dce` (already in the pipeline)
+ removes it when the store is skipped.
+
+**Impact.** Cuts spill reloads and, when every use rematerializes, spill stores on
+high-pressure functions; compounds with W1. A v1 implemented during MIR rewrite
+does **not** reduce allocator pressure by itself — it attacks stack traffic after
+the spill decision, and frame size only if a later cleanup removes now-unused
+slots. Reducing spill count requires feeding remat costs back into allocation
+later.
+
+**Linear?** Yes — a per-def classification pre-pass + a local choice at each spill
+site. No global analysis.
+
+**Risk.** The recompute must be input-less so it is valid anywhere (the v1 set is).
+A constant bigger than its reload must *not* rematerialize — the ≤2-insn cost gate
+enforces it. The correctness trap is dropping the spill store while any direct
+frame use remains. Keep the set conservative; measure reload/store counts before/
+after, separately from total spill-slot count.
+
+### W3 — Linear move coalescing
+
+**The hook is already there.** The O1 allocator consults a union-find via
+`alloc_coalesce_root` / `alloc_group_member` (`pass_lower.c:742/755`) and assigns
+one location per class (`alloc_assign_group_hard/_stack`). At `-O1`
+`f->opt_coalesce_parent` is NULL, so every PReg is its own root (identity → no
+coalescing). W3 is a **linear pass that populates that parent array before
+`opt_assign_ranges`** — the allocator then merges copy-related values onto one
+register for free. The existing `opt_coalesce_ranges` (`pass_coalesce.c:257`) does
+this *correctly* but builds an O(n²) conflict **matrix** — that is the O2-only
+path; W3 must not call it.
+
+**Mechanism (linear).** Reuse unchanged: `collect_move` (eligible `IR_COPY`: same
+class+type, both have ranges, not `IRF_NO_COALESCE`; `pass_coalesce.c:238`),
+`coalesce_find`/`coalesce_union` (`:26/:209`), and `opt_ranges_overlap_kind` (`:54`,
+the cheap on-demand range-overlap test). New driver:
+1. Init `opt_coalesce_parent[v]=v`, `opt_coalesce_size[v]=1` (as `:265`).
+2. Per root, maintain its **merged live-range list** (sorted by `raw_start`,
+ initially the PReg's own ranges) and **aggregated constraint masks** (`tied` /
+ `forbidden` / `allowed`).
+3. Collect moves; sort hottest-first by block frequency.
+4. For each move (dst,src): `ra=find(dst)`, `rb=find(src)`; skip if equal. Test
+ `can_merge(ra,rb)`:
+ - merge-scan the two sorted range lists: any overlap wider than one point, or a
+ *second* unit-length overlap, is a conflict (this mirrors
+ `opt_ranges_overlap_kind`'s 0/1/2 result lifted to the group level — the one
+ benign unit overlap is the copy itself);
+ - constraint check: `forbidden_a | forbidden_b` compatible with the merged
+ `allowed` and any `tied` (mirrors `group_constraints_compatible`, `:176`).
+ If mergeable, `coalesce_union`, then merge the smaller root's range list and OR
+ its masks into the larger (union-by-size).
+
+**Why this is linear (not the O2 matrix).** No `nrelated²` conflict bitmap. Each
+merge-scan is `O(|A|+|B|)`; union-by-size makes total work `O(N log N)` in ranges.
+**Conservative fallback** if the range-list bookkeeping proves fiddly: cap class
+size at a constant K and do the K²-bounded pairwise `opt_ranges_overlap_kind` per
+merge — still linear in moves, missing coalesces only in classes > K.
+
+**Impact.** Removes the cross-block `mov x,x` copies the per-block `mir_combine`
+cannot retire (~668 in lvm) *and* lowers pressure (→ fewer spills), compounding
+with W1/W2.
+
+**Linear?** Yes (above). Never coalesce an `IRF_NO_COALESCE` (phi-edge) copy.
+
+**Risk — bounded, but not zero.** Non-overlapping ranges mean the merged values are
+never simultaneously live, so the live set does not grow at any program point.
+But forcing two disjoint values to share one location can still make the merged
+group harder to place (combined constraints, one common hard register, callee-save
+costs) and can spill a group that two independent values would not have spilled.
+Mitigate by merging only when the combined constraints leave at least one plausible
+hard register, or by rolling back / splitting a coalesced class that falls to the
+stack. Gate on correctness + spill-count-not-worse on the corpus.
+
+Two implementation details must be made explicit:
+- `opt_verify_alloc` currently describes and checks the "O1 no-coalesce" shape;
+ it must treat PRegs in the same coalesce root as one value, not as an
+ interference violation.
+- `mir_combine` currently uses `!f->opt_coalesce_parent` as a proxy for "O1 may
+ fold `load_imm` through copies". Once O1 has a union-find, replace that with an
+ explicit mode/flag so enabling coalescing does not silently disable useful O1
+ immediate folding.
+
+### W4 — Inline-pressure cap
+
+**Mechanism.** A size/pressure-aware inline cost cap — back off inlining into an
+already-large caller, or whose inlining pushes estimated live-set past the
+register file — trims pressure before regalloc. This is **not** the primary lvm
+fix in the current measurements: a targeted `lvm.c` metrics run showed
+`opt.inline.inlined=0` (75 candidates refused by shape), so `luaV_execute` is
+large from source structure rather than O1 inlining. The policy knob is still
+relevant for sqlite-style files, where the whole-program inliner does inline many
+small callees and there is no SSA post-inline cleanup at `-O1`.
+
+**Where.** `src/opt/pass_inline.c` (the `opt_inline` cost/growth/policy gates;
+see the policy table in OPT.md §8). A new "caller already huge / pressure" gate
+alongside the existing cost caps.
+
+**Impact.** Indirect; potentially useful on sqlite/inline-heavy files, near-zero
+on lvm as currently measured. Tune against the corpus — must not regress the
+files where inlining is currently a win (lz4/yyjson).
+
+**Linear?** Yes — a cheap size/pressure estimate per call site.
+
+**Risk.** Regressing runtime speed on hot inlined loops. This is a policy knob;
+measure both size *and* (ideally) a runtime proxy before committing thresholds.
+
+### W5 — Local (same-block) redundant-load + CSE elimination
+
+**Mechanism.** A forward scan within a block that reuses the last load of an
+address (and the last result of a pure expression) until a store / call / memory
+barrier invalidates it. Catches same-block reload and recompute redundancy.
+
+**Where.** `mir_combine` (`src/opt/pass_combine.c`) already tracks per-block
+producers and a clobber barrier (`inst_is_clobber_barrier`, `inst_writes_memory`)
+— extend it with an address→last-load map and a value→last-compute map. Keep this
+distinct from the existing adjacent spill compaction in `opt_combine_compact_block`
+(store/load, load/store, load/load, store/store pairs); W5 is the broader
+same-block map-based form.
+
+**Impact.** Modest at `-O1` (much redundancy in lvm is *cross-block* → needs GVN,
+out of scope), but cheap and broadly applicable.
+
+**Linear?** Yes — single forward pass, bounded per-block state.
+
+**Risk.** Alias correctness — only reuse a load when no intervening store may
+alias (reuse the existing `AliasRoot`/`inst_writes_memory` conservativism;
+calls/volatile/atomics are barriers).
+
+### W6 — Peephole tightening (modest, easy)
+
+- **cmp-immediate folding.** Register-compares like `movz w9,#k; cmp w8,w9` that
+ fit the target immediate form should be `cmp w8,#k`. The current aa64 immediate
+ policy already knows `NATIVE_IMM_CMP`; the missed cases are materialized too
+ late for the existing operand-immediate path. A recent targeted audit found the
+ opportunity mostly in sqlite (hundreds of small constants) rather than lvm after
+ the latest copy/extension folds. Fold a `load_imm` feeding a `cmp` into the
+ cmp's immediate operand when legal.
+- **Address-mode folding gaps.** `add xN,xM,#k; ldr [xN,#j]` →
+ `ldr [xM,#k+j]` when `k+j` is a legal scaled offset. `mir_combine`'s
+ addressing-mode synthesis already does most of this; close the constant-add +
+ offset case.
+
+**Where.** `src/opt/pass_combine.c` (`try_addr_synth`, and a new const-into-cmp
+fold). **Linear?** Yes — per-instruction peephole.
+
+### W7 — Switch-chain immediate compares
+
+**Mechanism.** `IR_SWITCH` replay currently materializes every case value into a
+scratch register before `cmp_branch`:
+
+```c
+load_imm scratch, case_value
+cmp_branch EQ, selector, scratch, case_label
+```
+
+That loses the immediate path the normal `IR_CMP_BRANCH` emitter already has, and
+it differs from the CG fallback switch chain (`cg/control.c`), which passes the
+case value as an immediate operand. Replay should build an immediate operand per
+case and route it through the same `operand_imm_or_reg(..., NATIVE_IMM_CMP, ...)`
+logic as `IR_CMP_BRANCH`; only materialize to a scratch when the target says the
+compare immediate is illegal.
+
+**Where.** `IR_SWITCH` in `src/opt/pass_native_emit.c` (`emit_one`, around the
+case loop). This is an emitter-local change; no IR analysis required.
+
+**Impact.** Removes one constant materialization per case in non-jump-table switch
+chains, especially sparse switches and small chains below the jump-table
+threshold. On aa64 this is often a `movz` before every `cmp_branch`; x64 already
+has rich cmp-immediate forms and benefits from density; rv64 will still
+materialize when the immediate cannot fit the branch/compare lowering.
+
+**Linear?** Yes — still one pass over switch cases.
+
+**Risk.** Keep the fallback materialization path for targets/immediates that do
+not accept the case value directly. Preserve selector pinning: the selector should
+still be materialized once before the case chain, not reloaded per case.
+
+### W8 — Same-block stack dead-store elimination
+
+**Mechanism.** A forward MIR scan deletes a stack store when a later store in the
+same block fully overwrites the same stack slot before any possible read:
+
+```text
+store spill#17, r8
+... no read/barrier for spill#17 ...
+store spill#17, r9 ; first store is dead
+```
+
+This is deliberately narrower than O2 DSE. V1 should handle exact direct frame
+stores only:
+- `IR_STORE` with `opnds[0] == OPK_LOCAL(slot)`;
+- `!opt_mem_observable(&mem)`, `mem.alias.kind == ALIAS_LOCAL`, and
+ `mem.alias.v.local_id == slot`;
+- exact same `{slot, size, addr_space}` and no bit-field rider;
+- start with `FS_SPILL` slots only. Optionally add `FS_LOCAL` later only when the
+ slot is proven non-escaped (`!FSF_ADDR_TAKEN`) and every access remains direct.
+
+**Fast design.** Do not use a hash table per block. Frame slot ids are dense, so
+keep per-function side arrays indexed by `FrameSlot`:
+- `seen_gen[slot]`, `last_store_idx[slot]`, `last_size[slot]`,
+ `last_addr_space[slot]`;
+- increment `gen` at each block start and on a full memory barrier instead of
+ clearing `O(nslots)` state;
+- keep a touched-slot list only if compaction/reset bookkeeping needs it.
+
+On an accepted store:
+1. If `seen_gen[slot] == gen` and the stored key matches, mark the previous store
+ `IR_NOP`.
+2. Record the current store as the new `last_store_idx[slot]`.
+3. If the same slot is accessed with a different size/address-space/bit-field
+ shape, clear that slot's entry rather than reasoning about partial overlap.
+
+On an accepted direct load from the same slot, clear that slot's entry. On any
+unknown memory op, call, asm, intrinsic, atomic, volatile access, aggregate op, or
+non-direct local access, bump `gen` and forget all pending stores in O(1).
+
+**Where.** `src/opt/pass_combine.c`, either as a new helper called from
+`opt_combine_block`/`opt_combine_compact_block`, or as a separate same-block
+MIR cleanup immediately before the existing compact pass. Let the existing NOP
+compaction and `mir_dce` clean up the store's now-dead source producer.
+
+**Impact.** Smaller than W1/W2, but it directly cuts spill/local stack traffic and
+can expose dead rematerializations/copies to `mir_dce`. It compounds with W2:
+rematerialization removes reloads; stack DSE removes overwritten stores that
+remain.
+
+**Linear?** Yes — one scan over block instructions, O(1) per instruction, no
+per-block clear over all frame slots.
+
+**Risk.** The correctness boundary is aliasing and partial overlap. Keep v1 exact
+and spill-only; treat anything uncertain as a barrier. Do not delete volatile,
+atomic, bit-field, aggregate, or escaped-local stores. Add structural tests for:
+same-slot overwrite deleted, intervening load preserved, different size preserved,
+call/asm/unknown store barrier preserved.
+
+### W9 — One-pass branch cleanup subset
+
+**Mechanism.** O2 has `opt_jump_opt`, but its fixed-point loop is intentionally
+not an O1 fit. O1 can still import the single-pass, obviously-linear subset:
+1. Collapse `IR_CONDBR` / `IR_CMP_BRANCH` whose two successors are the same into
+ a plain `IR_BR`.
+2. Forward successors through trivial pass-through blocks once:
+ - unconditional `IR_BR` targets;
+ - conditional taken targets (`succ[0]`);
+ - conditional fallthrough targets (`succ[1]`) only when preserving fallthrough
+ semantics is explicit: the old fallthrough block is physically next and is
+ empty/pass-through, or the predecessor already had to emit an explicit jump
+ to the false target.
+3. Optionally include `IR_SWITCH` successor forwarding through single-jump blocks,
+ using the same label-address guard as existing jump cleanup.
+
+**Fast design.** Reuse `JumpCleanupCtx` and its memoized `forward_jump_target_ex`
+style, but run it once. No `for (iter < nblocks)` loop, no repeated CFG rebuilds.
+The shape should be:
+
+```text
+build_cfg
+one_pass_forward_branch_targets
+one_pass_collapse_same_target_branches
+build_cfg if changed
+existing cleanup_branch_targets / layout cleanup
+```
+
+The forwarding walk is bounded by `nblocks` per queried target today, but the
+memo table makes repeated queries amortized linear for the function. Keep the
+label-address guard (`has_label_addr_ref`) so computed-goto-visible blocks are
+not bypassed.
+
+**Where.** `src/opt/pass_jump.c`. Either extend `OPT_JUMP_CLEANUP_CFG` with this
+one-shot subset or add a named O1 cleanup helper called from the O1 prepare path
+after CFG construction. Do **not** call `opt_jump_opt` from O1.
+
+**Impact.** Mostly density/control-flow cleanup: fewer jump-only blocks survive
+to layout, fewer explicit jumps after branch forwarding, and better fallthrough
+shape for later MIR layout cleanup. It should also reduce verifier/debug noise by
+canonicalizing same-target branches early.
+
+**Linear?** Yes if it is one shot with memoized forwarding and at most one CFG
+rebuild after changes.
+
+**Risk.** Fallthrough correctness. Rewriting a conditional false edge can turn an
+implicit fallthrough into an explicit jump or skip a block; allow it only for
+empty/pass-through blocks with no label-address references. Accept missed
+multi-hop opportunities rather than adding a fixed-point loop.
+
+### W10 — Constant `cmp_branch` folding
+
+**Mechanism.** Fold branch conditions that are statically known without SSA:
+- `IR_CMP_BRANCH` with two immediate operands;
+- integer same-register comparisons (`x == x`, `x <= x`, `x < x`, etc.).
+
+Rewrite the terminator to `IR_BR` targeting the selected successor. This is the
+branch form of the existing local `IR_CMP x,x -> load_imm` simplification, but it
+must update CFG successors, so it belongs with branch cleanup rather than as a
+pure expression fold.
+
+**Where.** `src/opt/pass_jump.c` near the W9 one-pass cleanup. Use the shared
+integer compare evaluator/masking helpers where possible. V1 should not chase
+`IR_LOAD_IMM` definitions in PReg form; O1 PRegs are mutable, so direct operands
+and same-reg identities keep the pass local and safe.
+
+**Impact.** Low ceiling, but cheap. It removes dead conditional branches produced
+by macro/static-configuration code and exposes unreachable blocks to the existing
+CFG cleanup.
+
+**Linear?** Yes — a local terminator scan.
+
+**Risk.** Do not fold FP same-register comparisons: NaN makes `x == x` and
+ordered relations non-trivial. For immediate/immediate compares, use the operand
+type width and signedness semantics; if the width is unknown, skip.
+
+---
+
+## 4. Out of scope (SSA-only — belongs in the O2 mid-end)
+
+These are where most of clang's *remaining* advantage on value-heavy code lives,
+and none is cheaply doable without SSA. They are already designed/parked in the
+O2 schedule (OPT.md §3, `src/opt/pass_o2.c`):
+
+- **Global GVN** — cross-block redundant load / value elimination (the bulk of
+ the lvm redundancy that W5 can't reach).
+- **General DSE** — cross-block, alias-aware dead-store elimination. W8 is only
+ exact same-block stack overwrite cleanup.
+- **LICM** — loop-invariant hoisting.
+- **Induction-variable strength reduction.**
+
+If a chunk of the gap turns out to *require* one of these, the answer is to wire
+up / ship the O2 path for that workload, not to bolt a non-linear analysis onto
+`-O1`.
+
+---
+
+## 5. Already landed
+
+- **commit 8826982d** — three local, target-agnostic copy/extension folds:
+ `addr_of [base+0] → copy` and same-width same-class `convert → copy`
+ (`pass_simplify.c`), and `ZEXT(zero-extending load) → copy`
+ (`pass_combine.c`). **−2.4% `__TEXT`** across the corpus (lapi −9.1%, yyjson
+ −4.3%, sqlite −1.9%, lvm −3.2%), compile time unchanged. Guarded by
+ `test/opt/redundant_copy_ext.sh`. See OPT.md §4/§8.
+
+---
+
+## 6. Suggested sequencing
+
+The structural set (the user-prioritized work) is W1a → W1 → W3 → W2. W4–W10
+remain the lighter / opportunistic sketches above, scheduled after or alongside
+that set when file ownership allows.
+
+1. **W1a** (local `sub`-CSE) — first PR: stands up the gate + a `test/opt/`
+ structural guard with a small, safe aa64/rv64 peephole. Proves the harness.
+ Keep it minimal — W1.1 subsumes most of it.
+2. **W1.0** (hot-slot-low ordering) — shared frequency-threaded layout; lands
+ mostly in shared code, with backend offset validation. Immediate disp8/window
+ wins and sets up W1.1.
+3. **W1.1** (aa64 uniform x29-at-bottom known-frame layout) — the big structural
+ win (~36% lvm / ~12% sqlite `sub`s), and the highest blast radius
+ (prologue/epilogue/CFI). Contained in the aa64 backend; alloca included, no
+ regalloc change.
+4. **W3** (linear coalescing) — lowers pressure → fewer spills → fewer slots for
+ W1 to place; removes surviving cross-block moves.
+5. **W2** (rematerialization) — attacks spill *traffic* directly; feed its costs
+ into allocation later if spill count remains the bottleneck.
+6. **W1.2** (rv64) — assess far-slot traffic after W1.0; build the rv64 residual
+ work only if measurement shows a gap. **W1.3** (x64) is W1.0 alone.
+
+Then, opportunistically: **W7** (switch immediates — tiny emitter PR), **W10**
+(constant branch folding), **W9** (one-pass branch cleanup), **W8** (same-block
+stack DSE), **W6** (peepholes — cheap polish, anytime, and a good small PR if
+W1.1 is too large to take first), **W4** (inline cap — needs threshold tuning
+against the corpus + ideally a runtime proxy), **W5** (local load/CSE — low
+ceiling at `-O1`).
+
+**Definition of done per item:** measurable `__TEXT`/instruction reduction on the
+affected corpus files, sqlite `-O1` compile time unchanged (linearity held), all
+correctness gates green, and a `test/opt/` structural guard added.
+
+### Parallel flow (agent fan-out)
+
+Parallelism is bounded by **file ownership** (kit's parallel-agent rule: disjoint
+files or worktree isolation), not by logical dependencies — the only hard
+ordering is W1.2 after W1.0.
+
+| item | exclusive owner | also touches (shared) |
+|------|-----------------|------------------------|
+| Harness (`o1_quality.sh`) | `scripts/` + `test/opt/` | — |
+| W1.1 aa64 | `src/arch/aa64/native.c` | — |
+| W1a sub-CSE | `src/opt/pass_combine.c` + `test/opt/` | — |
+| W3 coalescer | `src/opt/pass_coalesce.c` | `pass_lower.c` (1-line call site, ~:1887) |
+| W1.0 ordering | `src/opt/pass_native_emit.c` | `ir.h` + `native_target.h` (add field); `pass_lower.c` (`spill_slot_for` ~:578) |
+| W2 remat | `src/opt/pass_lower.c` (`rewrite_one_operand` ~:1383 + new fn) | — |
+| W1.2 rv64 | `src/arch/rv64/native.c` | — |
+| W7 switch immediates | `src/opt/pass_native_emit.c` | conflicts with W1.0 owner |
+| W8 stack DSE | `src/opt/pass_combine.c` | conflicts with W1a/W5/W6 owner |
+| W9/W10 branch cleanup | `src/opt/pass_jump.c` | — |
+
+**Wave 1 (up to 6 agents, worktree-isolated):** Harness, W1.1, W1a, W1.0, W2, W3.
+- Harness, W1.1, W1a own fully private files → trivially parallel. (W1a must take
+ the `pass_combine.c` route, **not** an aa64 peephole, so W1.1 stays the sole
+ owner of `native.c`.)
+- W1.0 / W2 / W3 share `pass_lower.c` but in **disjoint functions** → worktrees
+ merge cleanly in any order; if you want zero friction, let W2 own `pass_lower.c`
+ and fold in W1.0/W3's one-spot edits.
+
+**Wave 2 (gated):** W1.2 — only after W1.0 lands *and* a measurement shows rv64
+far-slot traffic worth removing (may be a no-op). W1.3 (x64) is W1.0 alone.
+
+**Opportunistic wave:** W7 and W9/W10 are file-disjoint from the structural work
+except W7's `pass_native_emit.c` overlap with W1.0; land them as small isolated
+PRs. W8 should share the `pass_combine.c` owner with W1a/W5/W6 to avoid churn in
+the same post-RA cleanup machinery.
+
+**Merge discipline:** parallelize *development*, but **merge + re-measure one at a
+time** against the harness — these change emitted bytes (gate = correctness, not
+byte-identity), so single-item integration keeps any regression attributable.
+Land the harness first.
diff --git a/doc/plan/README.md b/doc/plan/README.md
@@ -10,6 +10,7 @@ shrinks to whatever remains open.
|---------|-------|------------|
| [RELEASE.md](RELEASE.md) | Cross-cutting initial-release punchlist: release scope, deferred features, and per-subsystem completion/validation items. | — |
| [OPTIMIZER.md](OPTIMIZER.md) | Completing the O2 SSA mid-end, expanded inlining, -O0/-O1 performance work, machine register-constraint improvements. | [../OPT.md](../OPT.md) |
+| [O1.md](O1.md) | Closing the `-O1` *generated-code quality* gap to clang `-O1` within the no-SSA/linear-compile constraint: measured gap, the spill-addressing root cause, and a ranked worklist (positive-offset spill addressing, rematerialization, linear coalescing, peepholes). | [../OPT.md](../OPT.md) |
| [PERF.md](PERF.md) | Making kit the fastest `-O0` C compiler with code as dense as tcc: current compile-speed + code-size standings, how to reproduce them (macOS instruction counts, Linux callgrind, the `make bench-cc` scaling guard), and the ranked forward-looking levers on both axes. | [../ARCH.md](../ARCH.md) |
| [CG-TYPES.md](CG-TYPES.md) | Clean-break redesign of the public CG type/type-id system: direct-index handles, real void types, explicit alias/storage semantics, ABI-owned layout, and two-phase nominal records. | [../CODEGEN.md](../CODEGEN.md), [../INTERFACES.md](../INTERFACES.md) |
| [CG-TYPE-DEBUG-SPLIT.md](CG-TYPE-DEBUG-SPLIT.md) | Make `KitCgTypeId` storage/ABI-only and move source spelling (primitive sign+name, typedefs, enum underlying) onto a separate debug-type channel: deletes `ALIAS`/`SOURCE_BASE`, `api_unalias_type`, and the per-backend unalias boilerplate. Resolves CG-TYPES.md §10 Q1. | [../CODEGEN.md](../CODEGEN.md), [../DWARF.md](../DWARF.md) |
