kit

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

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): 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; the compile-speed roadmap (a separate axis — that doc explicitly does not care about generated-code quality) is PERF.md. The broader optimizer roadmap (completing the O2 SSA mid-end, machine register-constraint work) is 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:

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:

Per-file comparison (text size + instruction mix):

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

Update (2026-06-16): the §3 worklist is fully landed (see §5). Aggregate __TEXT is now ≈ 1.09× clang -O1 (down from 1.25×, a −12.8% reduction in kit's emitted __TEXT). The dominant symptom below — spill-address sub x29 at 36% of lvm / 12% of sqlite — is eliminated on aa64 (lvm 8,774 → 0, sqlite 35,360 → 0; lvm __TEXT 96,788 → 59,276, 4.66× → 2.86×; sqlite 1.27× → 1.11×; miniz 1.94× → 1.67×; the clang-favored lz4/yyjson held at 0.38×/0.86×). sqlite -O1 compile stayed ≈1.6→1.67s (linear; W3 the main contributor). The pre-campaign analysis below is retained for context. The residual gap is now catalogued in O1-PATTERNS.md — a kit-vs-clang disassembly audit of what remains, ranking the further linear/ no-SSA wins (L1–L10) and separating them from the parked-O2 SSA gaps.

[Pre-campaign] 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:

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:

    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.

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:

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 subs — 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

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):

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:

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)

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:

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:

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:

Fast design. Do not use a hash table per block. Frame slot ids are dense, so keep per-function side arrays indexed by FrameSlot:

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:

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:

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):

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

The §3 worklist (2026-06-16) — all items shipped

Implemented in parallel (worktree-isolated), merged one-at-a-time against the scripts/o1_quality.sh harness, each correctness-gated (test-opt structural guard + test-toy 1392/0 + ecosystem 28/0 + smoke-x64/rv64). Cumulative: aggregate __TEXT 1.25× → 1.09× clang; lvm 4.66× → 2.86×; sqlite sub x29 35,360 → 0; sqlite -O1 compile ≈1.6s → ≈1.67s (linear).

Earlier

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 subs), 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.

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.