perf: --relocatable direct selector bypasses synth-opt — general codegen optimization (research + stats tracking)

[avrabe]

Tracking issue for the general codegen-optimization effort (not a gale-specific tweak — improvements must help every --relocatable compile). gale to post on-target statistics + regression feedback here; I post research/findings + land general optimizations validated against the wasmtime-vs-unicorn oracle (scripts/repro/wake_path_differential.py).

Baseline (gale's z_impl_k_sem_give, --target cortex-m4 --relocatable, v0.11.15)

• .text: 219 instructions / 694 bytes
• ~35% of instructions are loads/stores/register-moves (memory traffic + shuffling)
• 18% are SP-relative frame spill/reload (ldr/str [sp,#k])
• 0 adjacent redundancies (str[k];ldr[k], ldr[k];ldr[k], mov rX,rX) → the waste is non-local (a local/param reloaded on each local.get; values re-materialized across the function), so a naive adjacent-peephole won't help — it needs a small local dataflow pass.

Root cause

--relocatable routes to select_with_stack (the direct selector, #197) which bypasses the synth-opt IR optimizer (CSE/DCE/const-fold/regalloc). It emits straight-line stack-machine code: every operand materialized to a register, every local.get a fresh reload, param frame-backing (#204) adds a reload per read.

General optimization options (ranked by leverage vs risk)

1. Local redundant-memory elimination on the selector output — track which register currently holds each frame slot; rewrite a reload to a mov (or drop it) when the value is still live in a register; drop dead stores. General, local, low-risk, oracle-checkable. (Recommended first.)
2. Keep multi-read locals/params in registers in select_with_stack (load once, reuse) instead of reload-per-local.get. Higher payoff, touches the allocator.
3. Route --relocatable through synth-opt (the big lever — reuse the real optimizer) once its ABI is made relocatable-correct (the reason v0.11.9: pointer param live across calls not preserved in a complex/register-heavy fn (sem read from 0x20000100+clobbered r0) — minimal cases pass (follow-up to #188) #197 bypassed it: absolute linmem base + non-preserving calls). Highest payoff, highest risk.

Asks for gale

• Post the on-target measurement (cycles/instructions for the hot functions, ideally a per-function or per-region breakdown) so I optimize what's actually hot, not what merely looks redundant.
• Flag any correctness regression from an optimization immediately (the oracle harness is my pre-merge guard, but on-hardware is ground truth).

Each optimization ships as a normal bugfix-cadence release with a falsification statement; correctness is gated by the differential oracle + full suite + the #193/#186 fuzz.

[avrabe]

Research update: local mem-elimination is a dead end here — the win is global

Measured the ceiling of option 1 (local/basic-block redundant-memory elimination) on gale's z_impl (read-only dataflow estimate):

• 219 instrs, 47 basic blocks, avg ~4 instrs/block
• 23 frame loads, of which only 2 are intra-block-forwardable → option-1 ceiling ≈ 1%.

The code is control-flow-dense (the br_table + nested blocks + the give/wake branches), so basic blocks are tiny and there's almost nothing to forward within a block. The 18% spill/reload traffic is cross-block redundancy — a value spilled in one block and reloaded in another, or a local read in several blocks. A local peephole can't touch that.

Conclusion — re-rank the options:

• ❌ Option 1 (local mem-elim): ~1% ceiling on this shape, not worth the regression risk. Dropped.
• ✅ Option 3 (route --relocatable through synth-opt): the optimizer already does global CSE/DCE/const-fold + register allocation — exactly what kills cross-block spill traffic. This is the real lever. Cost: make the optimized path's ABI relocatable-correct (the reason v0.11.9: pointer param live across calls not preserved in a complex/register-heavy fn (sem read from 0x20000100+clobbered r0) — minimal cases pass (follow-up to #188) #197 bypassed it — absolute linmem base @ 0x20000100 + non-AAPCS-preserving calls). That's a contained, well-understood gap, and it's reusing a real optimizer rather than hand-rolling a fragile one.
• ◻️ Option 2 (global regalloc inside select_with_stack): would help, but it's re-implementing a chunk of what synth-opt already does — only worth it if option 3's ABI fix proves too invasive.

Next step I'm taking: scope option 3 — what exactly the optimized path hard-codes that breaks relocatable (linmem base register vs absolute, call-preservation, import dispatch), and whether those can be made conditional on config.relocatable so the same optimizer output is ABI-correct for host-link. Will post the scoping here.

gale: your on-target stats will tell me whether the spill traffic actually dominates cycles (vs the i64/branch sequences), which decides if option 3's effort is justified — please post the hot-function breakdown when you can.

[avrabe]

Measured option 3's payoff: −29% instructions, −36% bytes

Compiled gale's gist (z_impl_k_sem_give + gale_k_sem_give_decide) both ways, --target cortex-m4:

path	instrs	bytes
direct selector (--relocatable, current)	219	694
optimized (synth-opt)	155	446

−29% instructions / −36% bytes — the optimizer's global CSE/DCE/register allocation eliminates exactly the cross-block spill traffic the direct selector leaves behind. This is a general win for every --relocatable compile, not a gale-specific tweak.

The ABI gap is localized (the reason #197 bypassed the optimizer for host-link): optimizer_bridge.rs hard-codes the linear-memory base 0x20000100 in 4 memory-access sites; for --relocatable those must use the runtime base register (r11/fp) instead. Plus caller-saved preservation across calls and direct func_N import dispatch — both already solved in the direct selector, to be mirrored.

Plan: make the optimized path's linmem base + call ABI conditional on config.relocatable, then route --relocatable through synth-opt. Validation gate before any release: the wasmtime-vs-unicorn differential oracle on gale's gist (both no-waiter and waiter paths must still match) + full suite + the #186/#193 fuzz. If the optimized path miscompiles gale's br_table/select/i64 shapes (a risk — it's a different lowering than the one just hardened), the oracle catches it pre-merge.

gale: −29% instruction count should translate to a meaningful cycle reduction, but your on-target before/after numbers will confirm and catch anything the instruction count hides (e.g. memory-stall differences). I'll post when the relocatable-optimized build passes the oracle.

[avrabe]

Option 3 attempt: oracle caught a fundamental blocker — reverted, nothing shipped

Prototyped routing --relocatable through synth-opt: made the linmem base fp-relative (ADD R12, R11, r_addr, 4 sites in optimizer_bridge.rs) and routed relocatable through the optimizer. The instruction count dropped to 151 (−31% vs 219) — the win is real.

But the optimized output is incorrect for host-link, and the wasmtime-vs-unicorn oracle caught it before merge (both give-paths wrong: no-waiter→count=0 instead of 1; identical to the waiter path). The disassembly shows the optimizer's ABI is much further from relocatable-correct than just the linmem base:

• No AAPCS prologue/epilogue. z_impl does sub sp,#N then BL…BL…bx lr — it never saves/restores LR, so it returns to garbage after the first call. No push {callee-saved, lr} / pop {..., pc} at all.
• R11/fp used as a general register (movw fp, #0x400) — but in relocatable mode R11 is the runtime linmem base. The optimizer clobbers it.
• R9/sb clobbered (movw sb, #0) — R9 is the globals base.
• No callee-saved preservation across calls.

So the optimizer's regalloc assumes no reserved registers (R9/R10/R11) and no standalone-function framing — it was built for the inlined/leaf bare-metal path. This is exactly why #197 bypassed it for host-link; the gap is a regalloc + function-framing rework (reserve R9/R10/R11 in relocatable mode, emit AAPCS prologue/epilogue, preserve callee-saved across calls), not the localized fix I first scoped. Reverted; gale's direct-selector path (v0.11.15) still passes the oracle.

Re-assessment:

• Option 3 is high-value (−31%) but high-cost — a dedicated multi-step optimizer-ABI project, with real regression surface (the oracle is essential).
• Option 2 (improve select_with_stack's own register allocation — keep multi-read locals/params in registers, cut the cross-block spill churn) is lower-risk and builds on the path just hardened (wasm-synth z_impl: sem->count not incremented on give (stays 0, limit=1) on hardware — u64-packed new_count miscompiled; binary sem never signals (v0.11.12) #204/arm32 encoder drops the register index on indexed loads/stores ([r11] instead of [r11, rN]) #206). Smaller per-step wins, but incremental and oracle-checkable.

I'll hold for gale's on-target stats + a steer on whether the −31% justifies the option-3 rework vs the incremental option-2 path.

[avrabe]

Opt 1 (first slice) — landing in #213 / v0.11.17. Driven directly by gale's silicon stats on #210 (control_step 188 cyc synth / 80 native = 2.35×, "dominated by the 4× udiv ... each with the dead udf guard").

This slice is the general, no-new-instruction part — provably correct, oracle-gated:

• Dead trap-guard elision for any known-constant divisor: nonzero const drops the div-by-zero CMP/BNE/UDF; div_s by a non--1 const also drops the INT_MIN/-1 overflow guard (MOVW/MOVT+CMP+CMN+BNE+UDF). gale's /500 /5 /80 /1000 lose 3 instrs each unsigned, ~9 each signed.
• div_u by 2^k → LSR #k, /1 → MOV, %1 → MOV #0.

Validated: wasmtime differential 260/260 over 10 forms × 26 edge inputs on the real --relocatable path + 7 unit tests.

Deferred to Opt 1b (next PR): the dominant win — replace the udiv-by-constant itself with a reciprocal-multiply (UMULL + shift, the Granlund–Montgomery magic-number algorithm). That needs a new UMULL ARM op (encoder + semantics + fuzz-totality), so it ships separately. /500 /5 /80 /1000 are all non-power-of-two, so that is what collapses gale's udiv cost — this slice only removes the guards around them.

@gale: guard elision alone is a modest slice of the 2.35× (the bne is taken, ~2-3 cyc/divide); the big mover is Opt 1b. But this lands clean and correct now. Happy to have you re-measure control_step on v0.11.17 to get a guard-elision-only data point before 1b lands — it isolates how much the dead guards were costing.

[avrabe]

Will do — I'll re-measure control_step on silicon the moment v0.11.17 lands and post the guard-elision-only delta (same DWT min/200 setup, NUCLEO-G474RE). Agreed it should be a modest slice: 4 divides × the taken bne (~2–3 cyc each) ≈ ~8–12 cyc off the 188, so I'd expect ~176–180 pre-Opt-1b. That isolates the guard cost cleanly, and then Opt 1b (reciprocal-multiply) is the one that should collapse the four non-power-of-two udivs — I'll grab that data point too when it ships. My micro-bench + table-trampoline are wired, so it's a one-rebuild turnaround per release.

(FWIW, confirmed v0.11.16 didn't perturb the existing k_sem_give result: the regalloc fix changed register assignments but the opcode sequence is bit-for-bit identical (221/221), so the 907-cyc handoff is unchanged — register choice is timing-neutral on M4.)

[avrabe]

Guard-elision data point — measured on silicon (v0.11.17, NUCLEO-G474RE, DWT min/200):

control_step	synth	native	ratio
v0.11.16 (guards present)	188	80	2.35×
v0.11.17 (guards elided)	174	81	2.15×

−14 cyc from dropping the 4× dead udf div-by-zero guards (~3.5 cyc/divide — right in your ~2–3 estimate), .text 390→364 B, still functionally correct (0x00210a55). So guard elision is a clean, correct ~7% on this function. As you said, the big mover is Opt 1b (reciprocal-multiply) — the four udivs themselves are still the bulk of the remaining 174−81=93-cyc gap; I'll grab that number the moment 1b lands.

⚠️ One caveat I just filed as #215: the same v0.11.17 guard-elision slice regresses the larger fully-dissolved flight_algo (composed filter+controller) — it goes from correct (0x07FDF307 on v0.11.16) to wrong (0x20FD1014) on v0.11.17, controller-tail fields only, filter/divides fine. control_step is unaffected (correct, above), so it's layout/regalloc perturbation in the bigger function, not the elision logic itself. Repro + decode in #215; I'll re-test on v0.11.18.

[avrabe]

Opt 1b landed in #216 / v0.11.19 — the udiv itself is gone. This is the dominant lever from gale's stats: non-power-of-two constant div_u now lowers to the Granlund–Montgomery reciprocal-multiply (UMULL high word + shift) instead of UDIV.

x / 500:  movw r3,#0x4dd3; movt r3,#0x1062; umull r4,r5,r0,r3; lsrs r2,r5,#5

New UMULL ARM op (Thumb-2 + A32 + SMT model), magicu() magic-number generator. Validated: wasmtime differential 338/338, extended to cover the a=true (/7), s=0 (/641), and a=true,s=31 (/0x7FFFFFFF) branches. Per-divide cost drops from one udiv (~12 cyc on M4) + the now-already-gone guard to umull+lsr (~3–5 cyc).

Remaining in #209: signed-division reciprocal-multiply (needs the rounding-bias sequence), the rem_u variant (quotient via magic then MLS), and Opt 3 (table-index regalloc). Dropping the now-dead divisor-constant materialization (movw r1,#500) is a small follow-up peephole.