mc

Spec M49 -- the optimizer: --opt, a register allocator over the callee-saved half, a machine-private peephole, loop-invariant hoisting -- and the two roads

Written against minicompiler/mc main at 63e3e86 (M48 C2), read-only session, 2026-09-06, on the host docs/comparison.md measured (Apple M4, macOS 26.6.2, Apple clang 21.0.0). docs/plan.md's M49 row is an ESTIMATE ("within 1.3x of clang -O2"); this spec replaces the estimate with measurements taken before anything was designed (§ 1), and every design decision below cites the number it rests on.

The one-paragraph version. The 2.2x gap is three separate gaps. mix (the LCG/xorshift loop) is 0.39 s of the 0.60 s, and it is the store-then-load chain through the frame -- every local read and written through [sp, #k] -- that a register allocator removes: hand-emitting what the walker plus an allocator would produce and timing it gives 0.63 s -> 0.38 s with registers alone, 0.28 s with the peephole on top, 0.26 s with the loop-invariant constants hoisted. primes is 0.13 s of the gap, half of it clang -O2's NEON vectorisation of the count loop, which nothing here reaches; the allocator plus peephole gives 0.29 -> 0.21, hoisting 0.20. fib is 0.08 s of the gap and is NOT a codegen-quality gap: mc's cost per call (1.42 ns) is already below clang's (1.58 ns); clang makes half as many calls because it turns the second recursive call into a loop. Registers buy 0.18 -> 0.17 there and nothing else in this milestone reaches the rest. The sum, 0.26 + 0.20 + 0.17 = 0.63 s against 0.49 s = 1.29x, is what the design below is sized to deliver; without hoisting it is 0.66 s = 1.35x. And the peephole ALONE, on today's code, buys nothing measurable (0.66/0.30/0.19 against 0.63/0.29/0.18) -- the loops are latency-bound on the frame round trip, not on instruction count -- which inverts the order the plan row implied: the allocator lands first, the peephole after it.

0. What this stands on (read, not assumed) #

1. The measurements (step 0), and what they decide #

1.1 Today, on this host (best of 3, build/mc1 at 63e3e86) #

mc --execlang -O0clang -O2gap mc - O2
whole workload (bench/mc/bench.mc)1.11 s1.08 s0.49 s0.62 s
mix alone (200M iterations)0.63 s0.60 s0.24 s0.39 s
primes alone (sieve + count over 50M)0.29 s0.27 s0.16 s0.13 s
fib(38) alone0.18 s0.20 s0.10 s0.08 s
self-compile build/mc1 src/mc.mc -o x.o0.93-0.95 s (page: 0.88 s, same tree, quieter host)

(docs/comparison.md recorded 1.09 / 1.02 / 0.49; the three per-phase variants were made by trimming main in the scratchpad, bench/* untouched.)

build/mc1 --dump-asm bench/mc/bench.mc, 370 instructions, per function (ld = ldr/ldrb, st = str/strb):

functioninsldstmovmovz/movkblb/cbzcmpcset
_mix6813102200422
_primes9117921501288
_fib3252732311
_main39001829100
_putu64/_putnum46 each75581311
_puts/_strlen22 / 264 / 53 / 37 / 21 / 32 / 00 / 40 / 10 / 1

What a register allocator removes and what a peephole removes, counted on the hot loops:

1.2 What each technique buys -- hand-emitted from today's dump, assembled, timed #

Each variant is today's --dump-asm text with ONE transformation applied by hand, exactly the instructions the walker plus that mechanism would emit (no clang, no other change), assembled with clang -O0 x.s and timed the same way. Scratchpad files mixA.s mixB.s mixC.s mixD.s primesB.s primesC.s fibA.s todayP3.s.

variantwhat changedmixprimesfib
today--0.630.290.18
P peephole only (cset/cmp/cset/cbz -> b.cond, 191 -> 176 instructions)on today's code0.660.300.19
A allocator only: locals in x19..x22, every ldr/str [sp] a mov to/from the register, everything else as today (50 -> 50 per iteration, no memory)0.38--0.17
B = A + peephole (b.cond fusion; mov x19, x9; mov x9, x19 collapsed; the ALU result written straight into the local's register) -- 28 per iteration0.280.21--
C = B + immediate operands (lsr #13, add #1) -- 24 per iteration0.28----
D = B + loop-invariant hoisting (the two 64-bit constants and ITERS in x23..x25; sieve's address and N in x22/x23) -- 18 per iteration0.260.20--
clang -O20.240.160.10
clang -O1 -fno-vectorize -fno-unroll-loops -fno-inline (an upper bound: registers + hoisting + shifted operands + fib-to-loop)0.240.180.07

Read:

  1. The allocator is the lever: 0.25 s of mix's 0.39 s gap (A), and the remaining instruction-count reductions only pay once the frame round trip is gone: P alone is noise, B on top of A is another 0.10 s. The M4 is wide enough to absorb 50 instructions per iteration; what it cannot absorb is str -> ldr forwarding on the loop-carried x.
  2. Immediate operands buy nothing (C = B). Not in scope.
  3. Hoisting buys 0.02 + 0.01 s (D) and is what takes the projected sum from 1.35x to 1.29x. In scope, last.
  4. fib's floor is 0.17 s. Per call mc already spends less than clang (0.18 s / 126.5M = 1.42 ns; clang 0.10 s / ~63.2M = 1.58 ns); the gap is the call count, i.e. the recursion-to-loop rewrite clang applies to the second call, which is outside this milestone. Small-leaf inlining does not apply (the function is recursive).
  5. primes' floor without vectorisation is about 0.20 s (D); clang -O2's 0.16 is the NEON count loop and the 4x-unrolled inner loop, neither in scope.

Projected with A + B + D: 0.26 + 0.20 + 0.17 = 0.63 s, 1.29x of 0.49 s (§ 9 makes 1.3x the acceptance, with the per-phase numbers as the diagnostic when it misses). Without D: 0.66 s, 1.35x.

1.3 The cost side, before designing #

2. Where it lives -- decision (design question 1) #

roadwhat it can expressmeasured gain on the workloadprice (lines of src/)decision
(a) an Ins-level pass between gen_lower and gen_encode_allmachine-specific patterns over I_* -- which the WALKER may not read (the I_* vocabulary is the machine's, machine.md § 2 "the walker owns I_LABEL and nothing else")alone: 0 (variant P); with (b): 0.10 s on mix~120 in machine_arm64.mcyes, but machine-private and at emission time, not a pass and not a slot: the machine asks walk_opt() (§ 6)
(b) walker-level register allocation of locals over the callee-saved registerswhat the resolver and the walker already know: which declarations are locals, which have their address taken, how often and how deep each is used; the machine knows which registers are callee-saved0.25 s (mix), 0.08 s (primes, with the peephole), 0.01 s (fib)~260 walker + ~120 arm64 + ~110 x86-64yes -- the milestone
(b') loop-invariant constants and symbol addresses as pseudo-locals of the same allocator0.03 s~80 walkeryes, last (§ 4.8)
(c1) AST-level constant propagation (pass())x = 5; y = x + 1 -> y = 6; nothing in the workload has that shape (its constants are already literals fold handles)0 measurable~150deferred; priced, no consumer measured
(c2) AST-level small-leaf inlining (pass())copy a leaf body at the call, params to gensym locals, return -> assign + break N out of a wrapping loop0 on the workload (no small leaf in a hot path; ld8/st8 are intrinsics, fib is recursive); self-compile: the accessors (nd_kind, ld64) are the obvious win, unmeasured~300deferred to a follow-up with its own measurement on src/mc.mc

The allocator goes in the walker because the walker is the only place that knows liveness by construction -- it hands out depths and frees them, it drops a block's locals at the closing brace, it sees res_addr_taken -- and because docs/comparison.md § Where to improve and the plan row both named that seam. The machine keeps what is the machine's: WHICH registers are callee-saved, how many, how to move a depth into one and back, and how to save and restore them; and the copy propagation that makes an allocated register usable as an operand directly (the difference between A and B) is register knowledge and stays inside the machine (§ 4.6).

3. The switch, the seed and the two roads (design question 2) #

3.1 The switch #

3.2 The seed gates do not move #

check-obj (32/32 against build/mc0), check-asm, check-lex, check-ast and bootstrap never pass a flag, and the optimizer with walk_opt() == 0 runs no pre-pass, issues no v5 task and matches no pattern (the guards are if (walk_opt() == 0) return at the four entry points, § 4.2, § 4.4, § 6). Inertness is therefore by construction, and it is proved the M17 way anyway: scripts/check-inert.sh build/mc1.pre build/mc1 before each commit lands (§ 7).

The plain golden tests/golden/mc2.sha256 moves with every commit of this milestone -- the compiler's own body changes -- and is rewritten only after the empty --dump-asm diff between mc1 and mc2 and cmp build/mc2.o build/mc3.o, as always. It does NOT move because instruction selection changed for any program, which check-inert is what says.

3.3 The second golden, and the cross-road identity #

scripts/bootstrap.sh gains a second chain after the first (skipped with a message when the compiler refuses --opt=, so the seed and any pre-M49 release still run stage 1-3):

build/mc1  --opt=1 src/mc.mc -o build/mc2o.o     (+ link -> build/mc2o)
build/mc2o --opt=1 src/mc.mc -o build/mc3o.o
cmp build/mc2o.o build/mc3o.o                    <- the optimized road's fixed point
sha256 build/mc2o.o == tests/golden/mc2-opt.sha256
build/mc2o          src/mc.mc -o build/mc2o-plain.o
cmp build/mc2o-plain.o build/mc2.o               <- the cross-road identity

The last line is the strongest correctness statement this milestone can make and it costs one compile: an optimized compiler computes exactly the compiler the unoptimized one computes. A miscompiled allocator that changes any decision anywhere in the 1745 functions of src/mc.mc shows up here as a byte difference, with diff <(mc2 --dump-asm src/mc.mc) <(mc2o --dump-asm src/mc.mc) as the bisection tool (docs/determinism.md § Fixed-point diagnosis applies unchanged). The foreign goldens (mc2-linux-*, mc2-windows-*) get their -opt twins when D2 lands (§ 10); until then --opt=1 on an x86-64 machine is a no-op by the null-slot rule (§ 5) and the arm64 Linux/Windows twins are recorded in D1's commit.

3.4 check-inert on both roads #

scripts/check-inert.sh PRE POST runs its one/taught loops a second time with --opt=1 appended whenever BOTH compilers accept --opt=0 (probe: "$c" --opt=0 --host), reporting ok 33 objects identical (--opt=1). Across a change that touches the optimizer, the plain road must be identical and the optimized road is expected to differ only for the programs the change targets -- the script prints the list, and the commit message says which and why (the M45 discipline: "the diff is exactly these two instructions").

4. The allocator, in the walker #

4.1 What is a candidate #

A declaration -- N_PARAM, or a scalar N_VAR (nd_val == 0, no array) -- whose type has kind TK_INT or TK_SINT and width 8 or less (uptr included: a pointer is the machine's word; i32/u8 included: the register holds the extended eight bytes, the slot invariant of machine.md § The AVR implementation), whose declaring node is not res_addr_taken, in a function that contains no RK_OPCODE call and no emit()/reloc() (the resolver already classifies every call; the pre-pass sets a per-function flag on the first one it meets and stops). Excluded by kind: TK_FLOAT, TK_WIDE, TK_OPAQUE locals stay in memory, so <float>'s machines never see a v5 task for a value of theirs.

callp does not exclude a function. AAPCS64, System V and Win64 all make x19..x28 / rbx r12..r15 the CALLEE's to preserve; the pointer target of a callp is an ordinary function that keeps that promise whether it was written in mc, in C, or in a #opcode body -- and a #opcode body that writes x19 already breaks every C caller it has, with or without this milestone. Excluding the 43 callp functions of src/mc.mc would exclude the walker's own gen_* family, the hottest code in the compiler, for a risk the ABI already assigns to the callee. The owner may prefer the stricter rule (D5); it is one line in the pre-pass.

4.2 The pre-pass: opt_scan(f), before MTASK_PROLOGUE #

One walk over the function's body, in node order, carrying the loop nesting depth (N_LOOP increments on entry, decrements on exit). For every candidate declaration it counts weighted uses: each N_IDENT bound to it (res_kind == RK_LOCAL, res_decl matched against the declaring node's index AT THAT POINT -- the walk replays the same push/pop of block scope res_func did, which is what res_local_slot already relies on), each N_ASSIGN to it, and its own initialiser, at weight 8^depth capped at 8^3. Scores are integers, candidates are kept in declaration order in a per-function arena list (opt record, § 4.9), and selection is "repeat n times: take the highest score not yet taken, first in declaration order on a tie" -- no qsort, no hashing, stable by construction (docs/determinism.md rule 1 and 2). A candidate is taken only if its score is at least 3 (a parameter read once costs a mov in, a str/ldr pair around, and buys nothing). n is the machine's answer to MTASK_REG_COUNT (§ 5), 0 when the slot is null.

The result is written into the resolver's side table: RES_SIZE 32 -> 40, a fifth field RES_REG on the DECLARING node (0 = none, r + 1 otherwise). res_tab is allocated from nnodes and zeroed, and nothing outside gen_resolve.mc knows its stride.

4.3 What the walker emits #

gen_func, with walk_opt() != 0 and at least one allocated register (opt_nreg > 0):

MTASK_PROLOGUE
for each parameter i, in order:
    allocated to r  -> MTASK_PARAM_REG(ty, i, r)              // x(19+r) = x_i, x0..x7 only READ
    otherwise       -> slot_new + MTASK_PARAM(ty, i, off)     // as today
for each allocated r, in order:  off = slot_new(8); MTASK_REG_SAVE(r, off)   // the save area is ordinary frame slots
for each hoisted value (§ 4.8):  MTASK_CONST(0, v) / MTASK_SYM_ADDR(0, sym); MTASK_REG_STORE(TY_I64, 0, r)
body:
    gen_ident on an allocated local   -> MTASK_REG_LOAD(d, r)             // instead of LOCAL_LOAD
    gen_assign / gen_var initialiser  -> MTASK_REG_STORE(ty, d, r)        // instead of LOCAL_STORE; truncates to the width, extends by the kind
    N_CALL / N_RETURN / everything else unchanged
MTASK_LABEL(lepi)
for each allocated r, in REVERSE order: MTASK_REG_RESTORE(r, off)        // loads only; x0 untouched
MTASK_EPILOGUE
MTASK_FRAME_FIX(frame)

Why the save area is frame slots and not stp x19, x20, [sp, #-16]! pairs: the frame record stays stp x29, x30; mov x29, sp; sub sp and the epilogue stays add sp; ldp x29, x30; ret -- every ABI assertion of objects.md § 4 holds verbatim on the optimized road too, the saves are plain str/ldr forms every encoder already has (no new instruction in the sweep for them, no change to lib/backend_arm64.mc), fix_frame addresses them like any slot, and a debugger (M30) finds them at a fixed [sp, #k]. The cost is one instruction per register instead of one per pair, which § 1.3's size bound covers.

The Local record gets a fifth field, LOC_REG (LOC_SIZE 32 -> 40, -1 = not allocated), written by set_loc_reg right after local_add at the two sites; local_add's signature does not move (it is a lowering function objects.md § 3 lists). gen_ident/gen_assign test loc_reg(e) >= 0 before the existing branches, so the plain road's two calls are byte-identical text.

4.4 Inertness of the walker half, by construction #

opt_scan returns immediately when walk_opt() == 0; opt_nreg is then 0; every branch above tests loc_reg(e) >= 0, which is never true because nothing set it. No slot is called, no slot_new is issued, no node is touched. That is what check-inert confirms and what lib/machine_probe.mc will assert (§ 7).

4.5 Narrow types in a register #

MTASK_REG_STORE(ty, d, r) is "the value at d, truncated to type_width(ty) and extended by type_kind(ty), into r" -- the machine emits mov then gen_cast(x(19+r), ty) for widths 1, 2, 4 (and #0xff, sxth, mov w, w...), nothing more for 8. Today u8 x = 300 is strb (truncation in memory) then ldrb (zero-extension on the way back); the register version performs the same two steps at the store and none at the load, so x == 44 on both roads. MTASK_REG_LOAD(d, r) carries no type: the register already holds the extended eight bytes, exactly as a spill slot does.

4.6 The arm64 machine: x19..x28, the alias table, the store rewrite #

4.7 The x86-64 machines (D2) #

rbx r12 r13 r14 r15 -> 5; the same x86_reg_* functions serve x86_64-win through the copied table, so Win64 answers 5 as well and leaves rdi/rsi alone (they are argument registers 1 and 2 on System V; a count that depended on which prologue last ran would be stale for the first function of a unit, and two registers are not worth a second code path -- D11). Saves are mov [rbp-k], rbx (X_ST64), the alias table and the store rewrite are the same logic over x86_desc forms. No new x86 instruction form: jcc already exists for... it does not -- x86_jz emits test; jz; the peephole's cmp; setcc; test; jz -> cmp; jcc needs the jcc rel32 row, one x86_desc line, added to the sweep like b.cond.

4.8 Hoisting: loop-invariant constants and symbol addresses as pseudo-locals (step C) #

Inside a loop (nesting depth >= 1), two kinds of node re-materialise the same value on every iteration: an N_INT whose gen_imm needs two or more instructions (any 16-bit part above the low one non-zero -- ITERS, N, the two LCG constants), and the address of a global array, a string literal or &global (adrp + add). opt_scan records each distinct value (constants by value, symbols by symbol index, in first-occurrence order) as a candidate with the same weighted score as a local and the same threshold; a taken one gets a register after the locals, is materialised once at function entry after the saves (MTASK_CONST/MTASK_SYM_ADDR at depth 0 + MTASK_REG_STORE), and its uses become MTASK_REG_LOAD. Entry materialisation runs even when the loop is never entered -- a few instructions, never a fault (a symbol address is a relocation, not a load). Measured: mix 0.28 -> 0.26, primes 0.21 -> 0.20; it is the step that makes 1.3x from 1.35x.

4.9 State: arena records, zero net globals #

The optimizer's state is one arena record, opt (per-function candidate list and its count, opt_nreg, the flag the pre-pass sets, the hoist list), allocated on first use like drv_state/sb_state, with accessors -- ONE file-level global for the pointer. It is paid for twice over by the walker diet this milestone carries as its step A: pend_type pend_sym pend_node prel_base (the four reloc()-pending fields nobody outside gen_walk.mc reads, measured § 0) move into a wk record behind one pointer, net -3; the flag walk_opt() reads is a field of wk. Result: 445 -> 443 on the seed's globals row, measured by build/mc1 limits src/mc.mc before and after, check-limits at 17/17. The diet is byte-identical by nature and is proved by check-inert in the same commit (the M48 C0 precedent, "twelve globals became one").

5. Contract version 5 (design question 3) #

Version 4 -> 5 appends six slots and changes no signature; the version's second obligation is a rule about null slots, its third a sentence about val_reg.

slotsignaturemeaning
MTASK_REG_COUNT (31)i64 f()how many callee-saved registers this machine lets the walker allocate; 0 = none, and a NULL slot reads as 0
MTASK_REG_LOAD (32)void f(i64 d, i64 r)depth d = the value in allocatable register r (0 .. count-1)
MTASK_REG_STORE (33)void f(i64 ty, i64 d, i64 r)register r = depth d, truncated to type_width(ty) and extended by type_kind(ty)
MTASK_REG_SAVE (34)void f(i64 r, i64 off)write register r into the frame slot at off (prologue side, after the parameters)
MTASK_REG_RESTORE (35)void f(i64 r, i64 off)read it back (epilogue side, before MTASK_EPILOGUE; must not touch the result register)
MTASK_PARAM_REG (36)void f(i64 ty, i64 i, i64 r)argument i straight into register r, extended by kind; argument registers are read, never written

MTASK_COUNT 31 -> 37; mtask_names[] gains the six names; --dump-machine prints - for a null slot where it prints bundled/taught.

The null-slot rule. mach(task) stays as it is for slots 0..30 (a missing one is a bug in the machine and dies as today); for slots 31..36 the walker reads the entry itself and treats 0 as "the machine does not do this": REG_COUNT answers 0 and the other five are never called. That is the "0 = no allocatable registers" road, and it is what keeps examples/kernel/machine_riscv64.mc and examples/avr/machine_avr.mc byte-identical with --opt=1 and without, with no edit -- their tables are zero-filled globals of MTASK_COUNT entries and they fill 31 (§ 0). A machine that wants the allocator fills the six; riscv64 has s1..s11 and could, in a later commit of its own.

The derived machines. lib/machine_arm64_float.mc, lib/machine_x86_64_float.mc and lib/machine_probe.mc copy MTASK_COUNT entries out of the bundled table and therefore inherit the six slots -- integer locals get allocated in a <float> program exactly as in any other, and float locals never reach a v5 task (§ 4.1). What they must honour is the third obligation: since version 5, when in_reg(d) is true the value of depth d may live in a register other than REG_BASE + d; a derived machine reads a depth through val_reg(d, scratch) -- the function version 3 published for exactly this -- and never computes REG_BASE + d itself. lib/machine_arm64_float.mc does that computation in three lines today (§ 0); D1 fixes them (its fa_save_live/fa_restore_live become calls to the bundled pair through fa_of, and the stack-argument path uses val_reg), and check-float with --opt=1 on all its legs is the proof. Nothing else in lib/ or examples/ names a depth register.

The ABI assertions (docs/reference/objects.md § 4 and scripts/check-surface.sh):

6. The peephole -- machine-private, emission-time, walk_opt()-gated #

Not a slot and not a pass: the machine already sees the last instruction it emitted, and the four patterns below are all "the instruction I am about to emit consumes the one just emitted and nothing else can". Each is guarded by walk_opt() != 0 -- published in machine.md § 3 beside walk_depth_type, the same "a function, not a slot" shape -- and by "no I_LABEL between" (a label means another path arrives).

patternrewritewhereforms added
P1cmp; cset rd, cc then MTASK_JZ(d, L) with rd == val_reg(d)drop the cset, emit b.!cc L (JNZ: b.cc L)a64_jz/a64_jnzb.<cond> (I_BCOND, encoded, dumped and in lib/backend_arm64.mc already; never emitted before)
P2cset rd, cc then MTASK_UN(MUN_LNOT, d) on the same rdflip cc in place, emit nothinga64_unnone
P3the alias table (§ 4.6): MTASK_REG_LOAD emits nothinga64_reg_load, val_regnone
P4the store rewrite (§ 4.6): an ALU result then MTASK_REG_STOREretarget rda64_reg_storenone

P1 + P2 together turn the prelude's five-instruction while condition into cmp; b.ge. The cset's register is dead after a JZ/JNZ in every walker site (gen_if at depth 0, gen_logic overwrites the depth on both paths), so P1 needs no liveness beyond adjacency. A peephole here only deletes, rewrites in place, or replaces cset + cbz by one branch; it never reorders across a label or a call and never introduces a form the sweep has not seen (P1's b.cond is the one addition, swept in D1's commit).

Measured: P1 + P2 alone, 0; on top of the allocator, 0.10 s on mix and part of primes' 0.08 s. Landing order follows the measurement (§ 10).

7. Correctness tooling (design question 4) #

  1. scripts/check-inert.sh on both roads (§ 3.4), run before every commit of the milestone with build/mc1.pre from origin/main.
  2. scripts/check-opt.sh MC -- the differential test, in make check after check-surface: for every tests/*.mc (32) and tests/mc/*.mc (12), compile plain and with --opt=1, link, run both, compare exit code and stdout with each other AND with the expect-* header; tests/float/*.mc (16) through the float compiler on the macOS leg; examples/api, lang, conc, desktop built with --opt=1 on both halves (--compiler-only then --entry-only, the check-inert shape) and their own test.sh run; examples/kernel and examples/avr images cmp-identical with and without --opt=1 (null slots); src/mc.mc itself is § 3.3's cross-road identity. It also asserts the plan row's clause: --dump-asm and --dump-asm --opt=1 are IDENTICAL for every corpus program with no candidate (no local scoring 3, no loop constant) -- the script prints the two lists and the count is recorded in the commit.
  3. The sweep: every distinct instruction of --dump-asm --opt=1 src/mc.mc (and of the bench) re-assembled under llvm-mc -triple=arm64-apple-macos and aarch64-linux-musl, the way M45 swept its 16 new forms; expected new forms: b.<cond> only (D1), jcc on x86-64 (D2). str/ldr xN, [sp, #k] with N in 19..28 are existing forms with other registers.
  4. lib/machine_probe.mc extended: on the plain road it asserts no alias is ever set and no v5 slot is ever called over the whole of src/mc.mc; with --opt=1 it asserts the alias invariant of § 4.6 after every task (an aliased depth's REG_BASE + d is never named as a source by the machine) and that every REG_SAVE has its REG_RESTORE in the same function.
  5. Address-taken and excluded functions: tests/mc/094-opt-addr.mc (a local whose address is taken and mutated through the pointer stays in memory: the value read after the store is the stored one), 095-opt-narrow.mc (u8/i32/u16 locals in registers: truncation and sign at every store, mixed with calls), 096-opt-live-call.mc (locals live across callp and across a call that itself allocates the same registers, nested three deep), 097-opt-opcode.mc (a function with #opcode is left alone: its dump is identical on both roads), 098-opt-hoist.mc (a loop constant and a global array address hoisted, the loop never entered), each with expect-* headers and run on both roads on every leg tests/mc/0[89]*.mc already reaches (test-linux.sh, test-windows.sh loops).
  6. Determinism: the same source compiled twice with --opt=1 is the same object (the check-surface determinism case, repeated with the flag); the allocator hashes nothing and orders by declaration/first occurrence (§ 4.2).
  7. The ABI sweep with --opt=1 (§ 5, the tenth assertion) and check-surface's 32 objects compared between macho and arm64-surface with --opt=1 too -- the surface encoder must encode what the peephole makes, and it already can.

8. What this does to --dump-asm, the docs and the diagnosis recipe #

docs/determinism.md § Fixed-point diagnosis gains one line: there are two roads, and a divergence on the optimized one is bisected with --dump-asm --opt=1 exactly as the plain one; the cross-road identity (§ 3.3) says which half is broken. docs/reference/cli.md (two rows: --opt=N, -O), docs/reference/toml.md (project.opt), docs/reference/machine.md (the version 5 header, the six rows, the null-slot rule, walk_opt() in § 3, the val_reg obligation, a "what the arm64 allocator does" paragraph), docs/reference/objects.md § 4 (the rewritten x18..x28 paragraph and the withdrawn sentence), docs/comparison.md (the workload table gains an mc --exe --opt=1 row and § Where to improve item 1 is rewritten from estimate to measurement), bench/RESULTS.md § A/C (the new row, the per-phase table, the self-compile with and without), docs/guide/ one page ("-O: what it does and what it does not"), docs/plan.md's M49 row and CLAUDE.md § State.

9. Acceptance (runnable; numbers, not adjectives) #

  1. The plain road does not move. check-obj 32/32 against the frozen seed; check-asm/check-lex/check-ast at their current counts with no new seed-skip; bootstrap at a fixed point; check-inert build/mc1.pre build/mc1 identical for the 33 objects and the five taught examples on the plain road, at every commit; git diff --stat stage0/ empty.
  2. The workload, this host, best of 3, build/mc1 --exe --opt=1 bench/mc/bench.mc: within 1.3x of clang -O2 (0.64 s against 0.49 s), and the three phases recorded: mix <= 0.28 s, primes <= 0.21 s, fib <= 0.18 s -- the projection is 0.26 / 0.20 / 0.17. A miss is reported per phase against § 1.2, not as one number. The plain row stays in the table, so the page shows both roads.
  3. The optimizer's own cost: build/mc1 --opt=1 src/mc.mc -o x.o under 1.3x the plain road's time (target 1.1x); and the optimized compiler compiles src/mc.mc faster than the plain one -- both numbers recorded in bench/RESULTS.md § C.
  4. The second golden and the cross-road identity (§ 3.3): cmp build/mc2o.o build/mc3o.o, tests/golden/mc2-opt.sha256 recorded once per commit after the diff review, and cmp build/mc2o-plain.o build/mc2.o identical. After D2, the four foreign -opt goldens the same way.
  5. check-opt green on every leg (macOS objects and --exe, linux/aarch64, linux/x86_64, windows/arm64, windows/x86_64 through the existing scripts), the five new tests included; the --dump-asm identity for candidate-free programs with the two lists in the commit.
  6. The sweep: 0 mismatches; the set of new forms is exactly {b.<cond>} on arm64 and {jcc} on x86-64.
  7. The third-party road: examples/kernel's image (3304 B) and examples/avr's ELF cmp-identical with and without --opt=1, no edit to either machine; check-float green on every leg with --opt=1 after the three-line fix; check-surface 32/32 plus inert plus the tenth assertion.
  8. check-limits 17/17 under 90%, globals at or below 443/512 (§ 4.9), measured by build/mc1 limits src/mc.mc in the commit.
  9. Code size: __text of src/mc.mc with --opt=1 within +5% of the plain 461 420 B; bench.mc's --dump-asm --opt=1 instruction count recorded beside the 370.
  10. Docs (§ 8) with check-docs green: the two flags, the key, walk_opt, set_walk_opt, loc_reg, the six task names documented; every mc sample compiles; site/check-site green.

10. Steps -- gated commits, each with its own measurable gain (design question 6) #

Landing order is by measurement, not by the plan row's lettering: the peephole alone buys nothing (§ 1.2, variant P), so it lands after the allocator.

orderstepcontentlines (src/ code, est.)gain (measured basis)gate
1A the flag, the record, the two roads--opt=N/-O/[project].opt; wk record + walker diet (-3 globals); opt record; walk_opt()/set_walk_opt; MTASK_COUNT 37 with six null slots on every machine, mtask_names, --dump-machine's -; the null-slot rule in the walker; bootstrap.sh's second chain and mc2-opt.sha256 (identical to mc2.sha256's object at this step, which is the proof the flag is inert); check-inert both roads; check-opt.sh skeleton (differential over the corpus, trivially green)~140 walker/cli/driver/hooks + ~120 scripts0 by design; globals 445 -> 443A1, A4 (identical objects), A8
2D1 the allocator, arm64§ 4.1-4.6 (pre-pass, RES_REG, LOC_REG, the walker's emission; a64_reg_*, the alias table, the store rewrite); the machine_arm64_float.mc three-line fix; tests 094-097; the probe; the tenth ABI assertion; the sweep; machine.md v5~260 walker + ~130 arm64 + ~60 resolver + ~40 float/probe + testsmix 0.63 -> ~0.38 (variant A); fib -> 0.17; with P3/P4 (they are part of the alias table) closer to 0.30all of § 9 except the ratio
3B the peephole P1 + P2 — LANDEDa64_jz/jnz/un, b.cond in the sweep (and its --dump-asm text, which d_head padded to b. lt)39 added / 22 code in machine_arm64.mc (est. ~60)mix 0.22 -> 0.21, primes 0.20 -> 0.19, fib 0.13 unchanged (best of 7 interleaved with the D1 compiler, at the edge of a 10 ms timer -- § 1.2's "P1 + P2 alone, 0" holds); --dump-asm of the workload 330 -> 312 lines; new sweep forms exactly the six b.<cond>, 0 mismatches§ 9.5-9.6 ✔
4C hoisting -- LANDED§ 4.8 (constants and GLOBAL addresses; a string's and a function's address are out, see the note below), test 101 (098 was taken by D1)149 added / 99 code in src/gen_walk.mc (est. ~80); 0 new globals, 7 new functionswhole workload 0.548 s against clang -O2's 0.420 = 1.30x (three runs: 1.29x, 1.31x, 1.29x -- the host's 2% spread straddles it); mix 0.216 (parity with clang's 0.215), primes 0.202, fib 0.132; step C's own share is 0.551 -> 0.548 whole, mix 0.220 -> 0.216, primes 0.205 -> 0.202, each at the edge of a 10 ms timer; --dump-asm of the workload 312 -> 319 lines (the entry materialisation) with the mix body 24 -> 18 per iteration; src/mc.mc's __text 535 720 -> 480 420 B; 2413 distinct instructions of the optimized object re-assemble byte for byte, 0 new mnemonics against step B§ 9.2 per phase ✔, the aggregate ratio at 1.30x
5D2 the allocator, x86-64 and Win64 -- LANDEDx86_reg_* (5 registers on both ABIs), the alias table, the store rewrite, P1/P2 on x86_jz/x86_un, fx_param_reg/xw_param_reg and the four val_reg corrections in lib/, the four foreign -opt goldens, the --opt=1 pass on the four foreign legs218 added / 110 code in src/machine_x86_64.mc (est. ~110) + 62 added / 40 code in lib/ + 337 in scriptsnot measured on this host (no x86-64 bench cell; M50's job); correctness through the --opt=1 pass of test-linux.sh, test-windows.sh and check-float.sh on the four foreign legs. --dump-asm --machine=x86_64 src/mc.mc 148 042 -> 130 846 lines; the sweep is 1666 (System V) / 1643 (Win64) distinct instructions re-assembled byte for byte, 0 mismatches, and the mnemonic delta against the plain road is exactly four -- jl jge jle jg§ 9.4-9.5 foreign ✔
--E small-leaf inlining, constant propagationpass()-level, ~300 + ~1500 on the workload; a self-compile candidatedeferred: its own spec with its own measurement on src/mc.mc first

Needed for § 9.2: A, D1, B, C. Needed to close the milestone: D2 as well (the flag must mean the same thing on every target mc ships) -- done. Optional: E.

11. Files and estimated deltas #

filelineswhat
src/gen_walk.mc+330 (~200 code)wk/opt records + accessors; walk_opt; the six MTASK_*, names, null-slot read; opt_scan; LOC_REG; the emission in gen_func/gen_ident/gen_assign/gen_var; hoisting
src/gen_resolve.mc+30RES_REG, RES_SIZE 40, res_reg/set_res_reg
src/machine_arm64.mc+190dalias, val_reg alias branch, the six a64_reg_*/a64_param_reg, P1/P2/P4, dslot reset
src/machine_x86_64.mc+130the same six, jcc row, P1/P2
src/cli.mc, src/driver.mc, src/limits.mc+25the flag, the key, set_walk_opt before gen_lower
src/hooks.mc+5--dump-machine's null-slot -
lib/machine_arm64_float.mc+3/-3val_reg in the three direct reads
lib/machine_probe.mc+40the alias and null-slot assertions
scripts/bootstrap.sh+45the second chain, cross-road identity, mc2-opt.sha256
scripts/check-inert.sh+20both roads
scripts/check-opt.sh~140new
scripts/check-surface.sh+30the tenth assertion; --opt=1 on the 32 objects and determinism
scripts/test-linux.sh, test-windows.sh, check-float.sh+10 each--opt=1 pass over tests/mc/09[4-8] and tests/float
Makefile+6check-opt in make check
tests/mc/094..098-opt-*.mc~200new
tests/golden/mc2-opt.sha256 (+4 foreign after D2)new
src/bundle_data.mc, five goldensregenerated
docs (§ 8)~220cli.md, toml.md, machine.md, objects.md, determinism.md, comparison.md, bench/RESULTS.md, one guide page, plan.md, CLAUDE.md

Net new src/ code: about 700 lines (A ~140, D1 ~450, B ~60, C ~80), plus D2's ~130. stage0/: 0.

12. Risks (design question 7) #

  1. Seed parity. Guarded by construction (no flag, no code path) and by check-inert at every commit; the one way to break it is a refactor that moves a plain-road byte -- the walker diet of step A is exactly that kind of change and lands FIRST, alone, so its inertness is proved on its own.
  2. Third-party machines. riscv64/avr are covered by the null-slot rule and cmp-identical images (§ 9.7). The float machines inherit the slots and MUST read depths through val_reg (§ 5); the three-line fix is in-tree, but a machine derived from arm64 OUTSIDE this tree that computes REG_BASE + d would read a stale x9 under --opt=1 -- said plainly in machine.md v5 and in the release note. The plain road is unaffected either way.
  3. Debugging (M30). A register-resident local has no frame slot; DWARF needs DW_OP_reg19 for it and DW_OP_fbreg for the saved copy of the register in the prologue. LOC_REG is exactly the information M30's writer needs, and the fixed [sp, #k] save area keeps a stack walker's view unchanged. M30's spec should read this section.
  4. The #opcode/emit() escape. Functions with either are never allocated; the residual risk is a #opcode body CALLED from an allocated function that writes x19..x28 -- a body that already breaks every C caller. objects.md says so; lib/sys_svc.mc's words name x16 and x0..x2 only (checked).
  5. Code size grows by two instructions per allocated register per function and shrinks by the removed frame traffic; § 9.9's 5% bound on src/mc.mc is the check, and --dump-asm --opt=1 bench.mc's count is recorded.
  6. Determinism. No hashing, declaration and first-occurrence order, an integer score, a stable "take the max" loop; the twice-compiled cmp and the fixed point on the optimized road are the gates.
  7. The alias table's correctness is the milestone's real risk: a stale alias reads the wrong register with no diagnostic. Three independent nets: the probe's invariant on every task over src/mc.mc, check-opt's run-equality over 60 programs and the four examples, and the cross-road identity over the 1745 functions of the compiler itself.
  8. Self-compile time: bounded at +30% (§ 9.3); the pre-pass is linear and the peephole is O(1) per instruction.
  9. Globals: net -2 (§ 4.9), measured at every commit.
  10. Two roads in the diagnosis recipe (docs/determinism.md): one added paragraph; the cross-road identity says which road to bisect.
  11. Win64 rdi/rsi left unallocated (D11): a measured decision can revisit it when M50's x86-64 cell exists.
  12. Runtimes keeping state in x19..x28: none in the tree today (grep, § 0); the contract sentence is withdrawn for --opt=1 only.
  13. check-surface's hard-coded prologue/epilogue expectations hold on both roads by the save-area design (§ 4.3); the tenth assertion covers what changes.
  14. The 1.3x itself: a projection from hand-emitted code, 1.29x with C and 1.35x without; the host's run-to-run spread is about 5% on these three binaries (§ 1.1's three runs). If D1 + B land at 1.35x, C is what closes it; if C lands and the ratio is still above 1.3x, § 9.2's per-phase numbers say where, and the next measured lever is mix's shifted-operand eor (variant D's loop is 18 instructions against clang's 7, latency-bound at the mul/add chain either way).

13. Decisions (architect) -- to ratify with the owner #

Implementation notes -- step C (hoisting) #

Written after the code, against what the code does.

  1. A literal's TYPE decides, not its immediate -- and getting that wrong was this step's one defect. § 4.8 says "an N_INT whose gen_imm needs two or more instructions", and read literally that includes a taught literal: <float>'s f64 is an N_INT whose type is TK_FLOAT and whose val is the IEEE bit pattern. Hoisting one puts a double in x19..x28 and hands the float machine an integer alias for a value that belongs in v16..v23 -- measured through build/mc-float before the guard existed: 0.0 + 2.5 three times gave 0x56e6e8cc4576e6a1 with --opt=1 against 0x401e000000000000 on the plain road. opt_lit_hoistable(n) is the rule (TK_INT or TK_SINT, type_width <= 8 -- exactly opt_eligible's test for a local, so a 16-byte TK_WIDE literal is out too), and it is ONE predicate read by the pre-pass AND by the use site: two copies of the test could disagree about which literals a register stands for. tests/float/028-lit-in-loop.mc gates it on both roads and on all five legs. The GLOBAL half was probed for the same hazard and does not have it: an f64 tab[8] indexed inside a loop is identical on both roads, because an array's decay is typed uptr whatever its elements are.
  1. Two of § 4.8's four kinds are out, and the reason is symbol creation. The section names an N_INT, a global array's address, a string literal's address and &global. The first, the second and the fourth are implemented; a STRING literal's address and a FUNCTION's address are not. Both would have to be keyed by a symbol index, and both CREATE their symbol on first use -- str_sym interns the bytes into __cstring and appends a l_strN, sym_ref appends an undefined symbol -- so hoisting one moves symbol creation and literal PLACEMENT from the middle of a function to its entry. That is deterministic and it would not be wrong, but it moves bytes for a gain § 1.2 never measured: the benchmark's invariants are the two LCG constants, ITERS, N and sieve's address. A global's symbol already exists when gen_func runs (gen_globals is earlier in gen_lower) and glb_sym is a plain read, which is why that kind is free.
  1. The test is tests/mc/101-opt-hoist.mc, not 098. D1 had already taken 097 through 100.
  1. The candidate list is four more columns of the opt record, not a table of its own, so step C adds zero globals (build/mc1 limits src/mc.mc reports globals 446/512 before and after) and seven functions. OPT_HMAX is 32 -- four times what any machine can lend -- and, like OPT_MAX, it is a CAPACITY: past it a value is simply not considered and the function still compiles on the plain road's rules.
  1. A use OUTSIDE the loop also becomes a register read. Candidates are only RECORDED at loop depth >= 1 (a value materialised once in straight-line code costs nothing where it stands), but once a value has a register, every N_INT of that value and every use of that global's address anywhere in the function reads it. That is sound because the register holds exactly that value for the whole function, and it is what mixed() in the test asserts.
  1. The entry materialisation goes after the parameters, not before them. MTASK_CONST and MTASK_SYM_ADDR write depth 0, and although no arm64 task touches x0..x7 there, the parameters must have been consumed before anything else writes a depth register -- the same argument that put D1's saves before the parameters, applied in the other direction.
  1. --dump-asm of the workload goes UP, 312 -> 319 lines, while the loop bodies go down: the entry of each function that hoists pays two to four instructions once. The measure that matters is per iteration -- mix's body 24 -> 18 -- and the object, whose __text falls 10%.
  1. The aggregate ratio is AT the gate, not under it. § 9.2 asks for 1.3x and the workload measures 0.548 s against clang -O2's 0.420 s. Three runs at growing repetition counts gave 1.297x (best of 11), 1.305x (best of 9) and 1.291x (best of 15): the host's spread of about 2% straddles the number. All three PER-PHASE figures are met with margin -- mix 0.216 against a 0.28 ceiling, primes 0.202 against 0.21, fib 0.132 against 0.18 -- and § 1.2's own projection for the sum was 0.63 s, which this beats. mix is at parity with clang -O2 (0.216 against 0.215). What remains is primes' NEON count loop and fib's call count, both named out of scope in § 1.2.

Implementation notes -- step D2 (x86-64 and Win64) #

Written after the code, against what the code does.

  1. jcc rel32 was already there, and § 4.7 was wrong about it. The section says the peephole "needs the jcc rel32 row, one x86_desc line, added to the sweep like b.cond". It does not: x86_jz/x86_jnz have emitted test rd, rd followed by X_JCC since M17 step B, so the descriptor row, the encoder branch (0x0f, 0x80 + cc, rel32), MTASK_INS_SIZE, MTASK_RELOC_OFF and the dump were all in place and already swept. Step D2 adds no instruction form at all, on either machine. What it adds is four new CONDITION VALUES of that form -- jl (0f 8c), jge (0f 8d), jle (0f 8e), jg (0f 8f), beside the je/jne the plain road already emitted -- and the four were checked against llvm-mc's own object (llvm-mc -filetype=obj of jl L at a distance gives 0f 8c ..., and so on for the other three). Measured mnemonic sets over src/mc.mc: System V 38 plain -> 42 optimized, Win64 38 -> 42, the delta exactly those four on both.

  1. The store rewrite is a much smaller whitelist than AArch64's, because x86 is two-operand. add rd, rn means rd = rd + rn: retargeting its destination at the local's register would add to a register that does not hold the old value. So the eleven forms that make AArch64's rewrite pay (add, sub, mul, the two divides, and, orr, eor, the three shifts) are all OUT here, along with neg, not, imul and the shifts; so is every store (its rd is its SOURCE), setcc (one byte), call r (its rd is the target) and idiv/div (the divisor). What is left is every form that only WRITES: mov, mov32, mov imm, the two leas, the five register movzx/movsx and the seven loads. So x = x + 1 costs one mov on x86-64 where it costs none on AArch64, and x = <a constant>, x = g, x = *p and x = a < b cost none on either. Only the 64-bit mov collapses to nothing when retargeted onto its own source: mov32 rbx, rbx is a TRUNCATION to 32 bits, not a no-op.

    The next lever, measured and NOT taken. n = n + a with both in registers lowers to mov r8, r12; add r8, rbx; mov r12, r8 -- three instructions where AArch64 emits add x19, x9, x10. A THIRD peephole would collapse it: when the instruction before the ALU op is a mov rd, <the allocatable register this store is about to write>, the pair is add r12, rbx. It is sound (the mov came from an MTASK_REG_LOAD of that same register and the depth is consumed by this store) but it is a two-instruction window rather than one, and § 10 row 5 does not measure speed on this host -- so it belongs to whichever milestone owns an x86-64 bench cell (M50), with a number in front of it.

  1. Far more tasks have to materialise an aliased depth first, for the same reason. x86_own(d) is a64_own's counterpart and is called by MTASK_BIN (whose destination IS its left operand), MTASK_UN, MTASK_BOOL and MTASK_CAST. On AArch64 only a64_un and a64_cast need it. x86_bool in particular used x86_val_reg for both the test and the setcc, which would have written a local's own register.
  1. x86_arg_to became one line, and that is the version 5 obligation applied to the bundled machine itself. It was if (x86_in_reg(d)) x86_mov(r, XREG_BASE + d); else em(X_LD64, r, ...); it is x86_mov(r, x86_val_reg(d, r)), which for a spilled depth loads into the argument register it was given -- exactly the em(X_LD64, r, ...) it used to do by hand -- and for an aliased one answers the allocatable register. x86_push_args could not be reduced the same way (its non-register case pushes straight from memory with no register at all) and carries a three-way branch.
  1. The five registers are not contiguous, so r goes through arithmetic and not a base. x86_allocreg_at(r) is r == 0 ? rbx(3) : r + 11. A five-entry table would read better and would cost one more file-level global, which is the frozen seed's tight row -- measured: build/mc1 limits src/mc.mc says globals 446/512 with the arithmetic and 447 with the table.
  1. The alias vector went into xdslot, which grew from MAXDEPTH to MAXDEPTH * 2 -- the same trick src/machine_arm64.mc uses, for the same reason. Zero new file-level globals in the whole step, on either side.
  1. Both derived x86 machines owed MTASK_PARAM_REG, and one of them for a third reason. D1's obligation (a machine that overrides MTASK_PARAM must override MTASK_PARAM_REG) was written down for the float ABI's NGRN/NSRN counters; lib/i128.mc's xw_param counts argument SLOTS of its own because a 16-byte value takes two registers on System V and a pointer on Win64, and on Win64 lib/machine_x86_64_float.mc shares one slot counter between the integer and float files. Three different reasons, one rule. fx_param_reg and xw_param_reg each mirror their own machine's integer branch.
  1. Four direct XREG_BASE + d reads existed in lib/ and all four are corrected: fx_save_live, fx_restore_live, fx_push_args (lib/machine_x86_64_float.mc) and xw_call's argument spill (lib/i128.mc). The restore keeps XREG_BASE + d, exactly as fa_restore_live does: it WRITES the depth's own register, and an aliased depth still answers its allocatable register through val_reg, so the value is the same either way. examples/avx/avx.mc needed nothing -- it already read through x86_val_reg -- and examples/kernel's riscv64 and examples/avr's AVR are null-slot machines that never see an alias.
  1. The --opt=1 pass on the foreign legs is one variable and one loop per script. [project] opt = 1 in the generated TOML is the whole of it (optkey in scripts/test-linux.sh and scripts/test-windows.sh, a third argument to build_float_obj in scripts/check-float.sh), and each case is a SECOND artefact named <name>-opt in the same manifest, judged against the same expect-* header. No workflow change was needed: the CI legs are --build-only on macOS and --run-only on the runner, so the new objects travel in the artifacts that already existed and the run half picks them up from the manifest. That is the only place a Win64 --opt=1 binary is ever executed.
  1. The tenth ABI assertion was VACUOUS, and step D2 found it. scripts/check-surface.sh's --opt=1 sweep matched registers with /x(19|2[0-8])\y/; \y is a GNU awk word boundary which the awk on macOS and the one in alpine:3 both ignore, so used was empty for every function and the check could not fail. Writing the x86 twin (which has no \y and therefore worked) reported 2895 "violations" on the first run, every one a false positive, which is what exposed it. Both are correct now -- a non-word character on each side, and used really is filled -- and two more mistakes came out with it: the arm64 save/restore patterns required [sp, #, so the slot at offset 0 (str x20, [sp]) was never recorded as saved; and pro was cleared by the frame record itself, three lines before the first save could arrive. The real numbers: arm64 1929 functions / 3556 allocated registers, x86_64 1929 / 2860, x86_64-win 1929 / 2860, every one saved and restored, x18 named nowhere and rdi/rsi named nowhere at all on Win64.
  1. rdi/rsi can only be asserted on Win64. D11 gives both ABIs the same five registers, so the claim "the allocator never hands out rdi/rsi" is observable only where they are not argument registers: on System V they appear 15 810 times in the optimized dump of src/mc.mc as arguments 1 and 2, and on Win64 zero times. The System V half of the claim is x86_allocreg_at's range, which is {3, 12, 13, 14, 15} by construction.
  1. Performance is not measured, and that is the step's own row in § 10. There is no x86-64 machine in this repository's development loop; the one number available is instruction count, and --dump-asm --machine=x86_64 src/mc.mc goes from 148 042 to 130 846 lines (-11.6%) with --opt=1, with 20 700 mentions of rbx/r12..r15 against 0 on the plain road. A reproducible x86-64 bench cell is M50's job.

Edit this page