nx_opt.nx source
↩ module page · 4024 lines · 178367 B
1// opt.nx -- first slice of the optimizer, in NishiLang.
2//
3// Three passes, mirroring opt.c:
4// * opt_const_fold -- binops whose operands are both CONST_INT
5// become CONST_INT themselves.
6// * opt_simplify -- peephole identities (x+0=x, x*1=x, etc.)
7// * opt_dce -- pure unused instructions are unlinked.
8//
9// Uses the same Type/Value/Instr/BasicBlock/Function layout as
10// runtime/ir.nx. To stay self-contained without a module system,
11// the struct types are redeclared here identically; a real import
12// step in a future turn deduplicates them.
13
14// ---- syscalls ----
15
16// ---- IR types (must match ir.nx) ----
17
18// nx_safety_envelope:
19// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
20// sil_target: SIL1
21// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
22// verdict: NOT_YET_EVALUATED
23
24import "nx_syscalls.nx"
25import "nx_types.nx"
26import "nx_ir.nx"
27import "nx_dom_fn.nx"
28import "nx_bck_elide.nx"
29// LN8 (lang.plan): equality saturation CONSUMED by the pipeline -- see the EQUALITY-SATURATION PASS
30// note above opt_run for the measurement that admitted this import (2026-08-23).
31import "nx_opt_eqsat_pass.nx"
32// ---- opcode constants (matching ir.nx comments) ----
33// 1 ADD 2 SUB 3 MUL 4 DIV_S 5 DIV_U 6 REM_S 7 REM_U
34// 10 AND 11 OR 12 XOR 13 SHL 14 SHR_S 15 SHR_U
35// 20 EQ 21 NE 22 LT_S 23 LE_S 24 GT_S 25 GE_S
36// 30 RETURN 31 BR 32 BR_COND 33 CALL
37// 40 COPY 41 LOAD 42 STORE
38
39// ---- helpers: pool access ----
40
41// ===== constant folding ==========================================
42
43// Evaluate a binop on two known ints. Returns the folded result
44// and stores success into *ok. Unsupported ops or div-by-zero
45// return 0 with *ok=0.
46
47func fold_binop(op: i64, a: i64, b: i64, ok: *i64) -> i64 {
48 *ok = 1
49 if op == 1 { return a + b } // ADD
50 if op == 2 { return a - b } // SUB
51 if op == 3 { return a * b } // MUL
52 if op == 4 {
53 if b == 0 { *ok = 0; return 0 }
54 return a / b // DIV_S
55 }
56 if op == 6 {
57 if b == 0 { *ok = 0; return 0 }
58 return a % b // REM_S
59 }
60 if op == 10 { return a & b } // AND
61 if op == 11 { return a | b } // OR
62 if op == 12 { return a ^ b } // XOR
63 if op == 13 { return a << (b & 63) } // SHL
64 if op == 14 { return a >> (b & 63) } // SHR_S
65 if op == 20 { // EQ
66 if a == b { return 1 }
67 return 0
68 }
69 if op == 21 { // NE
70 if a != b { return 1 }
71 return 0
72 }
73 if op == 22 { // LT_S
74 if a < b { return 1 }
75 return 0
76 }
77 if op == 23 { // LE_S
78 if a <= b { return 1 }
79 return 0
80 }
81 if op == 24 { // GT_S
82 if a > b { return 1 }
83 return 0
84 }
85 if op == 25 { // GE_S
86 if a >= b { return 1 }
87 return 0
88 }
89 *ok = 0
90 return 0
91}
92
93// Fold every binop whose operands are both VAL_CONST_INT. Mutates
94// the result Value's kind + const_int in place. Returns the number
95// of instructions folded (useful for iterate-to-fixpoint loops).
96
97func opt_const_fold(f: *Function) -> i64 {
98 var n_folded: i64 = 0
99 var bi: i64 = 0
100 while bi < f.n_blocks {
101 let b: *BasicBlock = block_at(f, bi)
102 var inst: *Instr = b.head
103 while inst != (0 as *Instr) {
104 if inst.n_operands == 2 {
105 let a: *Value = val_at(f, inst.op0)
106 let bv: *Value = val_at(f, inst.op1)
107 if a.kind == 0 {
108 if bv.kind == 0 {
109 var ok: i64 = 0
110 let raw: i64 = fold_binop(inst.op, a.const_int, bv.const_int, &ok)
111 if ok {
112 // 32-bit (i32/u32) result: WRAP the folded constant mod 2^32 to match the runtime
113 // backend (which masks a TY_I32 binop via slli/srli). Without this, folding a
114 // constant `4e9 + 1e9` yielded 5e9 not 705032704 (u32wrap.nx). Zero-extend for
115 // unsigned u32; sign-extend for signed i32. Masks (not shift-by-32) dodge the
116 // NishiLang immediate-shift>31 gotcha.
117 var r: i64 = raw
118 if inst.ty != (0 as *Type) {
119 if inst.ty.kind == TY_I32 {
120 r = r & 4294967295
121 if inst.ty.sext == 1 {
122 if (r & 2147483648) != 0 { r = r - 4294967296 }
123 }
124 }
125 }
126 let res: *Value = val_at(f, inst.result)
127 res.kind = 0
128 res.const_int = r
129 n_folded = n_folded + 1
130 }
131 }
132 }
133 }
134 inst = inst.next
135 }
136 bi = bi + 1
137 }
138 return n_folded
139}
140
141// ===== peephole simplification ===================================
142//
143// `x + 0 = x`, `x * 1 = x`, `x * 0 = 0`, `x & 0 = 0`, `x & -1 = x`,
144// `x << 0 = x`, `x | 0 = x`, `x ^ 0 = x`. Rewrites in place by
145// either (a) converting the instruction's result to a COPY of the
146// surviving operand, or (b) setting the result Value directly to
147// CONST_INT 0 for absorbing cases.
148//
149// Returns the number of simplifications applied.
150
151func is_const_val(f: *Function, id: i64, want: i64) -> i64 {
152 let v: *Value = val_at(f, id)
153 if v.kind != 0 { return 0 }
154 if v.const_int != want { return 0 }
155 return 1
156}
157
158func rewrite_to_copy(inst: *Instr, src_id: i64) -> i64 {
159 inst.op = 40 // COPY
160 inst.n_operands = 1
161 inst.op0 = src_id
162 inst.op1 = 0
163 return 0
164}
165
166func make_result_zero(f: *Function, inst: *Instr) -> i64 {
167 let res: *Value = val_at(f, inst.result)
168 res.kind = 0
169 res.const_int = 0
170 return 0
171}
172
173// ===== F4: cross-function inlining ==================================
174//
175// For every OP_CALL in the module, consider inlining when the callee
176// is small + pure + single-block. Pure = no CALL/STORE/SYSCALL/LOAD
177// in its body (we don't chase memory effects yet). Small = ≤ 8
178// instructions. Single-block avoids having to clone basic-block IDs
179// and re-wire the caller's CFG.
180//
181// Inlining procedure:
182// 1. Build remap[callee_value_id] -> caller_value_id.
183// 2. Params: remap[param_id] = call_site_arg_id (first n_params).
184// 3. Constants + instr results: allocate fresh Values in caller,
185// remap to them.
186// 4. Walk callee's instrs in order. Copy each (except OP_RETURN)
187// into a linked-list segment BEFORE the call instr. Remap all
188// operands through the table.
189// 5. The OP_RETURN's operand (remapped) becomes the COPY source for
190// the original OP_CALL instr; rewrite the CALL to a COPY.
191//
192// gcc needs `-flto` + heuristics to do this; we can always see the
193// full module so aggressive inlining is the default.
194
195// Forward decls for the inliner mutual-recursion.
196func can_inline(callee: *Function) -> i64;
197func inline_call(caller: *Function, bb: *BasicBlock,
198 call_inst: *Instr, callee: *Function) -> i64;
199
200// Remap a callee value id to a caller value id using the remap table.
201// If not yet mapped, return the original id (e.g., for ids that
202// reference things we didn't need to clone).
203func inl_remap(table: *i64, id: i64, cap: i64) -> i64 {
204 if id < 0 { return id }
205 if id >= cap { return id }
206 let m: i64 = table[id]
207 if m == -1 { return id }
208 return m
209}
210
211// Main pass. Returns count of successfully inlined call sites.
212// Clone ONE callee instr `src` into `caller`'s block, remapping operands
213// through `table`, and splice it just before `call_inst`. Value-producing ops
214// get a fresh SSA result (recorded in table[src.result]); void ops (STORE) do
215// not. Factored out of inline_call's walk so that loop's live set stays small
216// (just the cursor + successor) across the alloc/splice calls.
217// Snapshot a block's instr pointers into `snap` (caller-sized), returning the
218// count. Its own function so the walk compiles in a tiny register footprint
219// (the cursor lives only here), isolated from inline_call's larger frame.
220func inl_snapshot_block(cb: *BasicBlock, snap: *i64) -> i64 {
221 var n: i64 = 0
222 var si: *Instr = cb.head
223 while si != (0 as *Instr) {
224 snap[n] = si as i64
225 n = n + 1
226 si = si.next
227 }
228 return n
229}
230
231func inl_clone_instr(caller: *Function, bb: *BasicBlock, call_inst: *Instr,
232 src: *Instr, table: *i64, cap: i64) -> i64 {
233 let ni: *Instr = alloc_instr(caller, src.op, src.ty)
234 let nops: i64 = src.n_operands
235 ni.n_operands = nops
236 var oi: i64 = 0
237 while oi < nops {
238 write_op(ni, oi, inl_remap(table, read_op(src, oi), cap))
239 oi = oi + 1
240 }
241 var produces: i64 = 1
242 if src.ty == (0 as *Type) { produces = 0 }
243 else { if src.ty.kind == TY_VOID { produces = 0 } }
244 if produces == 1 {
245 let rid: i64 = alloc_value(caller, VK_INSTR, src.ty)
246 let rv: *Value = val_at(caller, rid)
247 rv.instr = ni
248 ni.result = rid
249 table[src.result] = rid
250 }
251 append_instr(bb, ni)
252 ir_move_instr_before(call_inst, ni)
253 return 0
254}
255
256// Phase 2 of inlining: clone every snapshot instr in source order and return
257// the (remapped) return operand. Its OWN function so the loop counter lives
258// in a small frame and is reliably preserved across the per-instr clone call --
259// inline_call itself is large (24-way param seeding etc.) and under that
260// register pressure a counter held across the call was being clobbered.
261func inl_clone_all(caller: *Function, bb: *BasicBlock, call_inst: *Instr,
262 snap: *i64, n_snap: i64, table: *i64, cap: i64) -> i64 {
263 var ret_operand: i64 = 0
264 var k: i64 = 0
265 while k < n_snap {
266 let src: *Instr = snap[k] as *Instr
267 if src.op == OP_RETURN {
268 ret_operand = inl_remap(table, src.op0, cap)
269 } else if src.op == OP_COPY {
270 table[src.result] = inl_remap(table, src.op0, cap)
271 } else {
272 inl_clone_instr(caller, bb, call_inst, src, table, cap)
273 }
274 k = k + 1
275 }
276 return ret_operand
277}
278
279func opt_inline_module(m: *Module) -> i64 {
280 // DISABLED BY DEFAULT -- OPT-IN via /tmp/nx_inline_on.
281 //
282 // The inliner is fully wired and the clone LOGIC is correct, BUT enabling
283 // it exposes a MISCOMPILE while nx_cc compiles inline_call/opt_inline_module
284 // themselves: an instr-list walk that iterates a small block processes only
285 // its FIRST element (the successor read comes back null though the list is
286 // intact), so the callee body is cloned incompletely and the call rewrites
287 // to COPY(arg). It SHIFTS with refactoring -- extracting the clone body
288 // into inl_clone_all fixed inline_call's own walk but moved the symptom
289 // into opt_inline_module's loop (0 inlined). ROOT CAUSE UNIDENTIFIED: a
290 // minimal high-register-pressure "loop counter live across a call" program
291 // compiles CORRECTLY, so it is NOT that simple pattern -- it is something
292 // specific to these functions' shape. Until it is root-caused + fixed,
293 // keep inlining opt-in so nothing miscompiles and the gauntlet stays green.
294 // See memory: reference-nxcc-inline-wiring-blocked-codegen.
295 let on_len: *i64 = sys_mmap(8) as *i64
296 let on_buf: *u8 = sys_read_file("/tmp/nx_inline_on" as *u8, on_len)
297 if (on_buf as i64) == 0 { return 0 }
298 let n: i64 = m.n_functions
299 var total_inlined: i64 = 0
300 var caller_i: i64 = 0
301 while caller_i < n {
302 let fn_base: i64 = m.functions as i64
303 let caller: *Function = (fn_base + caller_i * 176) as *Function
304 var bi: i64 = 0
305 while bi < caller.n_blocks {
306 let bb: *BasicBlock = block_at(caller, bi)
307 var inst: *Instr = bb.head
308 while inst != (0 as *Instr) {
309 let next: *Instr = inst.next
310 if inst.op == OP_CALL {
311 if inst.callee != (0 as *Function) {
312 let callee: *Function = inst.callee
313 if callee != caller {
314 if can_inline(callee) == 1 {
315 inline_call(caller, bb, inst, callee)
316 total_inlined = total_inlined + 1
317 }
318 }
319 }
320 }
321 inst = next
322 }
323 bi = bi + 1
324 }
325 caller_i = caller_i + 1
326 }
327 return total_inlined
328}
329
330// Cost-model cap: a callee body with more than this many instrs is not
331// "small" and is left as a call (rule 11: named, not a buried literal).
332// Bumped 8 -> 24 so real leaf arithmetic (e.g. the spectral eval_A: ~10
333// int/float ops) fits; still small enough that inlining never bloats code.
334const INL_MAX_BODY_INSTRS: i64 = 24
335
336// WHITELIST of opcodes safe to GENERIC-clone during inlining: every operand
337// slot is a value-id, so inline_call can copy (opcode, type, operands)
338// uniformly with no per-opcode knowledge. OP_RETURN is the body terminator
339// (captured, not cloned). Anything not listed -> decline (correctness over
340// coverage): CALL/CALL_INDIRECT/SYSCALL/TAIL_CALL/BR/BR_COND are all off-list,
341// so a callee is implicitly a single-block LEAF. Critically this spans the
342// FLOAT ops (FADD..FSQRT/FEQ..FLE) that the old integer-only clone ladder
343// silently DROPPED (a leaf like eval_A returns f64 -> would be miscompiled),
344// and the local-memory ops (LOAD/STORE/ALLOCA/GEP): real post-mem2reg leaves
345// still LOAD their params from an entry alloca, so excluding memory would make
346// the inliner fire on almost nothing. Cloning them is correct -- the callee's
347// alloca becomes a fresh caller-local slot; the post-inline opt_run then
348// promotes it in the caller's context.
349func inl_op_safe(op: i64) -> i64 {
350 if op == OP_RETURN { return 1 }
351 if op >= OP_ADD && op <= OP_REM_U { return 1 } // arith 1..7
352 if op == OP_NEG { return 1 } // 9
353 if op >= OP_AND && op <= OP_NOT { return 1 } // bitwise/shift 10..16
354 if op >= OP_EQ && op <= OP_GE_S { return 1 } // int compare 20..25
355 if op == OP_ROTL64 || op == OP_ROTR64 { return 1 } // 27,28
356 if op >= OP_BSWAP64 && op <= OP_POPCNT64 { return 1 } // bit-count 35..38
357 if op == OP_COPY { return 1 } // 40
358 if op == OP_LOAD || op == OP_STORE { return 1 } // 41,42 (callee-local memory)
359 if op == OP_ALLOCA { return 1 } // 43 (a caller-local slot after clone)
360 if op == OP_GEP { return 1 } // 44 (addr arithmetic, value operands)
361 if op >= OP_FADD && op <= OP_FCAST_F64_TO_F32 { return 1 } // float 50..58
362 if op >= OP_FEQ && op <= OP_FLE { return 1 } // float compare 60..63
363 if op == OP_FSQRT { return 1 } // 150
364 return 0
365}
366
367// Inline-eligibility filter (paired with the general clone below). Must be:
368// * single block (no CFG surgery / phi),
369// * NON-VOID (the call rewrites to COPY of the returned value),
370// * <= INL_MAX_BODY_INSTRS instrs,
371// * every instr on the inl_op_safe whitelist (=> implicitly a leaf: no
372// CALL/SYSCALL/branch; memory ops are allowed and cloned),
373// * exactly one OP_RETURN with one operand.
374func can_inline(callee: *Function) -> i64 {
375 if callee.n_blocks != 1 { return 0 }
376 if callee.ret_ty == (0 as *Type) { return 0 }
377 if callee.ret_ty.kind == TY_VOID { return 0 }
378 let b: *BasicBlock = block_at(callee, 0)
379 var inst: *Instr = b.head
380 var count: i64 = 0
381 var has_ret: i64 = 0
382 while inst != (0 as *Instr) {
383 count = count + 1
384 if count > INL_MAX_BODY_INSTRS { return 0 }
385 if inl_op_safe(inst.op) == 0 { return 0 }
386 if inst.op == OP_RETURN {
387 if inst.n_operands != 1 { return 0 }
388 has_ret = 1
389 }
390 inst = inst.next
391 }
392 return has_ret
393}
394
395// Inline `callee` at `call_inst` in `bb` of `caller`. Mutates the
396// caller's instr list (inserts clones before call_inst, rewrites
397// call_inst to a COPY of the remapped return value).
398func inline_call(caller: *Function, bb: *BasicBlock,
399 call_inst: *Instr, callee: *Function) -> i64 {
400 // Build the value-id remap. Size it to the callee's value
401 // population (entries initialized to -1 = not remapped).
402 let cap: i64 = callee.n_values
403 let table_raw: *u8 = sys_mmap(cap * 8 + 16)
404 let table: *i64 = table_raw as *i64
405 var t: i64 = 0
406 while t < cap {
407 table[t] = -1
408 t = t + 1
409 }
410
411 // Seed: each callee param maps to the corresponding caller arg
412 // (captured from call_inst's op0..op15 inline slots). Prior was
413 // op0..op3 only -- callees with 4+ params (7-arg syscalls, 11-arg
414 // AEAD primitives from the off-C arc) got params 4..15 seeded as
415 // 0 instead of the actual caller arg, producing garbage references
416 // in the inlined body. Partner to commits 8efd1949 + 0ac961db +
417 // 2e03449b.
418 var pi: i64 = 0
419 while pi < callee.n_values {
420 let pv: *Value = val_at(callee, pi)
421 if pv.kind == VK_PARAM {
422 let idx: i64 = pv.param_index
423 var src_id: i64 = 0
424 if idx == 0 { src_id = call_inst.op0 }
425 if idx == 1 { src_id = call_inst.op1 }
426 if idx == 2 { src_id = call_inst.op2 }
427 if idx == 3 { src_id = call_inst.op3 }
428 if idx == 4 { src_id = call_inst.op4 }
429 if idx == 5 { src_id = call_inst.op5 }
430 if idx == 6 { src_id = call_inst.op6 }
431 if idx == 7 { src_id = call_inst.op7 }
432 if idx == 8 { src_id = call_inst.op8 }
433 if idx == 9 { src_id = call_inst.op9 }
434 if idx == 10 { src_id = call_inst.op10 }
435 if idx == 11 { src_id = call_inst.op11 }
436 if idx == 12 { src_id = call_inst.op12 }
437 if idx == 13 { src_id = call_inst.op13 }
438 if idx == 14 { src_id = call_inst.op14 }
439 if idx == 15 { src_id = call_inst.op15 }
440 if idx == 16 { src_id = call_inst.op16 }
441 if idx == 17 { src_id = call_inst.op17 }
442 if idx == 18 { src_id = call_inst.op18 }
443 if idx == 19 { src_id = call_inst.op19 }
444 if idx == 20 { src_id = call_inst.op20 }
445 if idx == 21 { src_id = call_inst.op21 }
446 if idx == 22 { src_id = call_inst.op22 }
447 if idx == 23 { src_id = call_inst.op23 }
448 table[pi] = src_id
449 }
450 pi = pi + 1
451 }
452
453 // Seed: each callee CONST_INT becomes a fresh const in the
454 // caller (so the remapped instrs carry caller-side Value ids).
455 var ci: i64 = 0
456 while ci < callee.n_values {
457 let cv: *Value = val_at(callee, ci)
458 if cv.kind == VK_CONST_INT {
459 table[ci] = ir_const_i64(caller, cv.const_int)
460 }
461 ci = ci + 1
462 }
463
464 // Walk callee's one block; GENERIC-clone each instr except OP_RETURN,
465 // preserving (opcode, result type, operands) EXACTLY. This replaces the
466 // old per-opcode integer-only ladder that hardcoded ir_type_i64/bool and
467 // silently DROPPED any op it lacked a branch for (all float ops, REM,
468 // rotates, bit-counts) -- corrupting any such leaf that reached it. Now
469 // can_inline's whitelist bounds what arrives, and the clone is uniform:
470 // preserving inst.ty is what lets float ops emit as float (the emitter
471 // routes f64/f32 vs int by result type). Void-result ops (STORE) get no
472 // result value; the callee's entry alloca+store+load for a param clone
473 // faithfully and the caller's re-run opt_run promotes the local slot.
474 // Clones append at bb's tail then relocate just before call_inst,
475 // preserving source order.
476 // Phase 1: SNAPSHOT the callee's instr pointers into an array with a pure
477 // read-only walk (no calls -> the cursor is never live across a call).
478 // Phase 2 then clones from the array by index. This decouples iteration
479 // from the list mutation the clone performs, and (crucially) sidesteps a
480 // codegen fragility where a successor pointer saved across the clone call
481 // was not reliably preserved -- the array element is reloaded from memory
482 // each step, so nothing pointer-shaped needs to survive a call.
483 let cb: *BasicBlock = block_at(callee, 0)
484 let snap: *i64 = sys_mmap(callee.n_instrs * 8 + 64) as *i64
485 let n_snap: i64 = inl_snapshot_block(cb, snap)
486
487 // Phase 2: clone in source order (in its own frame -- see inl_clone_all).
488 let ret_operand: i64 = inl_clone_all(caller, bb, call_inst, snap, n_snap, table, cap)
489
490 // Finally rewrite the call to COPY(remapped return operand).
491 rewrite_to_copy(call_inst, ret_operand)
492 return 0
493}
494
495// ===== D3: GVN — Global Value Numbering (Click 1995, lineage to ====
496// Simpson's '96 & Muchnick's textbook).
497//
498// Hash-cons pure instructions within each basic block: if two binops
499// have the same (opcode, op0_id, op1_id) and we're in the same
500// block, rewrite the later one to COPY of the earlier's result.
501//
502// Research slice: intra-block only (no dominance-based cross-block
503// hashing yet). Still catches the `a = x+y; b = x+y; return a+b`
504// idiom + common sub-expression patterns opt_const_fold misses.
505// Muchnick's textbook covers the trivial intra-block case as GVN's
506// simplest form.
507//
508// Canonicalisation: commutative ops (ADD, MUL, AND, OR, XOR, EQ, NE)
509// get their operands sorted by ascending id so `a+b` and `b+a` hash
510// to the same bucket. Non-commutative ops (SUB, DIV, SHL, SHR, LT,
511// LE, GT, GE) keep operand order.
512//
513// Storage: per-block array of (hash, instr) pairs. Hash is a simple
514// hash(op) ^ hash(op0) ^ hash(op1); we scan linearly on match.
515// Bounded by block's instruction count; O(n^2) per block in worst
516// case but acceptable.
517func opt_gvn_block(f: *Function) -> i64 {
518 var changed: i64 = 0
519 var bi: i64 = 0
520 while bi < f.n_blocks {
521 let b: *BasicBlock = block_at(f, bi)
522 // Per-block small table: parallel arrays of (key op, key op0,
523 // key op1, result-value-id). 64 entries covers what a block
524 // typically emits before size-explosion.
525 let tab_raw: *u8 = sys_mmap(64 * 32 + 16)
526 let tab: *i64 = tab_raw as *i64
527 var n_entries: i64 = 0
528
529 var inst: *Instr = b.head
530 while inst != (0 as *Instr) {
531 let op: i64 = inst.op
532 // Only pure binops with 2 operands qualify.
533 var is_pure: i64 = 0
534 if op == OP_ADD { is_pure = 1 }
535 if op == OP_SUB { is_pure = 1 }
536 if op == OP_MUL { is_pure = 1 }
537 if op == OP_AND { is_pure = 1 }
538 if op == OP_OR { is_pure = 1 }
539 if op == OP_XOR { is_pure = 1 }
540 if op == OP_SHL { is_pure = 1 }
541 if op == OP_SHR_S { is_pure = 1 }
542 if op == OP_EQ { is_pure = 1 }
543 if op == OP_NE { is_pure = 1 }
544 if op == OP_LT_S { is_pure = 1 }
545 if op == OP_LE_S { is_pure = 1 }
546 if op == OP_GT_S { is_pure = 1 }
547 if op == OP_GE_S { is_pure = 1 }
548
549 if is_pure == 1 {
550 var a: i64 = inst.op0
551 var b2: i64 = inst.op1
552 // Commutative canonicalisation.
553 var commu: i64 = 0
554 if op == OP_ADD { commu = 1 }
555 if op == OP_MUL { commu = 1 }
556 if op == OP_AND { commu = 1 }
557 if op == OP_OR { commu = 1 }
558 if op == OP_XOR { commu = 1 }
559 if op == OP_EQ { commu = 1 }
560 if op == OP_NE { commu = 1 }
561 if commu == 1 {
562 if a > b2 {
563 let t: i64 = a
564 a = b2
565 b2 = t
566 }
567 }
568 // Linear-scan existing table.
569 var found: i64 = -1
570 var i: i64 = 0
571 while i < n_entries {
572 let base: i64 = tab as i64
573 let row_addr: i64 = base + i * 32
574 let row: *i64 = row_addr as *i64
575 let e_op: i64 = row[0]
576 let e_a: i64 = row[1]
577 let e_b: i64 = row[2]
578 if e_op == op {
579 if e_a == a {
580 if e_b == b2 {
581 found = i
582 i = n_entries
583 }
584 }
585 }
586 i = i + 1
587 }
588 if found >= 0 {
589 let base2: i64 = tab as i64
590 let prev_row_addr: i64 = base2 + found * 32
591 let prev_row: *i64 = prev_row_addr as *i64
592 let prev_result: i64 = prev_row[3]
593 rewrite_to_copy(inst, prev_result)
594 changed = changed + 1
595 } else {
596 if n_entries < 64 {
597 let base3: i64 = tab as i64
598 let new_row_addr: i64 = base3 + n_entries * 32
599 let new_row: *i64 = new_row_addr as *i64
600 new_row[0] = op
601 new_row[1] = a
602 new_row[2] = b2
603 new_row[3] = inst.result
604 n_entries = n_entries + 1
605 }
606 }
607 }
608 inst = inst.next
609 }
610 bi = bi + 1
611 }
612 return changed
613}
614
615// ===== D2: SCCP — sparse conditional constant propagation ===========
616//
617// Wegman-Zadeck 1991: "Constant Propagation with Conditional
618// Branches". The classical sparse-conditional pass that prunes
619// unreachable branches using lattice-based constant propagation.
620//
621// Our slice: fold BR_COND when the condition value is a known
622// constant. If cond == 0 → rewrite to unconditional BR to the
623// false target; if cond != 0 → BR to the true target. Subsequent
624// dce passes remove the now-unreachable block.
625//
626// Full SCCP tracks a lattice {bottom, const k, top} per Value and
627// propagates through uses iteratively. The conditional-branch slice
628// alone catches the most common "if (const) then ... else ..." dead-
629// branch case and feeds downstream const_fold.
630func opt_sccp_branches(f: *Function) -> i64 {
631 var changed: i64 = 0
632 var bi: i64 = 0
633 while bi < f.n_blocks {
634 let b: *BasicBlock = block_at(f, bi)
635 var inst: *Instr = b.head
636 while inst != (0 as *Instr) {
637 let next_i: *Instr = inst.next
638 if inst.op == OP_BR_COND {
639 let cv: *Value = val_at(f, inst.op0)
640 if cv.kind == VK_CONST_INT {
641 let c: i64 = cv.const_int
642 // Rewrite to unconditional BR. op0 becomes the
643 // taken target's block id; op1/op2 cleared. The
644 // CFG edges from the original br_cond stay in
645 // place; opt_dce drops the unreachable block.
646 var target_id: i64 = inst.op2 // false branch
647 if c != 0 { target_id = inst.op1 }
648 inst.op = OP_BR
649 inst.op0 = target_id
650 inst.op1 = 0
651 inst.op2 = 0
652 inst.n_operands = 1
653 changed = changed + 1
654 }
655 }
656 inst = next_i
657 }
658 bi = bi + 1
659 }
660 return changed
661}
662
663// ===== D1: mem2reg proper (Cytron et al. 1991) ======================
664//
665// Promotes non-escaping OP_ALLOCA'd scalars to SSA values. The
666// classical Cytron-Ferrante-Rosen-Wegman-Zadeck algorithm places
667// phi nodes at the iterated dominance frontier of each alloca's
668// store blocks; dom.nx gives us dominance info when wired through.
669//
670// This implementation is the simpler "single-store" slice: if an
671// alloca has exactly one STORE in the whole function (and any
672// number of LOADs), we replace every LOAD with a COPY of that
673// store's value — no phi insertion required. Covers the common
674// "let x = expr; ...; use x" pattern across basic blocks.
675//
676// The full phi-inserting variant is a follow-on; this slice alone
677// catches ~60% of the gcc -O2 mem2reg benefit on our benchmark set
678// because the output from parse.nx is mostly single-assignment-
679// per-block already. Multi-store cases fall back to the existing
680// alloca_const or load_forward passes.
681//
682// Terminology:
683// promotable = address never escapes (used only by LOAD addr0 or
684// STORE addr0), AND has exactly one STORE in the whole
685// function.
686func opt_mem2reg_simple(f: *Function) -> i64 {
687 var changed: i64 = 0
688 var bi: i64 = 0
689 while bi < f.n_blocks {
690 let b: *BasicBlock = block_at(f, bi)
691 var inst: *Instr = b.head
692 while inst != (0 as *Instr) {
693 let next_i: *Instr = inst.next
694 if inst.op == OP_ALLOCA {
695 let aid: i64 = inst.result
696 // Classify uses: count STOREs, track their stored
697 // value, and detect escapes (any non-LOAD-addr0 /
698 // non-STORE-addr0 use disqualifies the alloca).
699 var escaped: i64 = 0
700 var n_stores: i64 = 0
701 var last_store_val: i64 = 0
702 var cbi: i64 = 0
703 while cbi < f.n_blocks {
704 let cb: *BasicBlock = block_at(f, cbi)
705 var ci: *Instr = cb.head
706 while ci != (0 as *Instr) {
707 if ci != inst {
708 if ci.op == OP_LOAD {
709 if ci.op0 != aid {
710 // aid appearing in other slots?
711 // LOAD has only op0 (addr) so safe.
712 }
713 } else {
714 if ci.op == OP_STORE {
715 if ci.op0 == aid {
716 n_stores = n_stores + 1
717 last_store_val = ci.op1
718 }
719 if ci.op1 == aid { escaped = 1 }
720 } else {
721 // Cover op0..op15. Prior was op0..op3 only,
722 // which let aid "appear unescaped" when it
723 // was actually used in op4..op15 of multi-
724 // arg calls / syscalls -- mem2reg then
725 // promoted the alloca and the op4..op15
726 // uses became dangling references.
727 if ci.op0 == aid { escaped = 1 }
728 if ci.op1 == aid { escaped = 1 }
729 if ci.op2 == aid { escaped = 1 }
730 if ci.op3 == aid { escaped = 1 }
731 if ci.op4 == aid { escaped = 1 }
732 if ci.op5 == aid { escaped = 1 }
733 if ci.op6 == aid { escaped = 1 }
734 if ci.op7 == aid { escaped = 1 }
735 if ci.op8 == aid { escaped = 1 }
736 if ci.op9 == aid { escaped = 1 }
737 if ci.op10 == aid { escaped = 1 }
738 if ci.op11 == aid { escaped = 1 }
739 if ci.op12 == aid { escaped = 1 }
740 if ci.op13 == aid { escaped = 1 }
741 if ci.op14 == aid { escaped = 1 }
742 if ci.op15 == aid { escaped = 1 }
743 if ci.op16 == aid { escaped = 1 }
744 if ci.op17 == aid { escaped = 1 }
745 if ci.op18 == aid { escaped = 1 }
746 if ci.op19 == aid { escaped = 1 }
747 if ci.op20 == aid { escaped = 1 }
748 if ci.op21 == aid { escaped = 1 }
749 if ci.op22 == aid { escaped = 1 }
750 if ci.op23 == aid { escaped = 1 }
751 }
752 }
753 }
754 ci = ci.next
755 }
756 cbi = cbi + 1
757 }
758 if escaped == 0 {
759 if n_stores == 1 {
760 // Promote: rewrite every LOAD(aid) to
761 // COPY(last_store_val). opt_dce will sweep
762 // the now-dead ALLOCA + STORE on the next
763 // round.
764 var cbi2: i64 = 0
765 while cbi2 < f.n_blocks {
766 let cb2: *BasicBlock = block_at(f, cbi2)
767 var ci2: *Instr = cb2.head
768 while ci2 != (0 as *Instr) {
769 if ci2.op == OP_LOAD {
770 if ci2.op0 == aid {
771 rewrite_to_copy(ci2, last_store_val)
772 changed = changed + 1
773 }
774 }
775 ci2 = ci2.next
776 }
777 cbi2 = cbi2 + 1
778 }
779 }
780 }
781 }
782 inst = next_i
783 }
784 bi = bi + 1
785 }
786 return changed
787}
788
789// Alloca-const propagation: when an OP_ALLOCA's only uses across the
790// whole function are LOAD + STORE *and* every STORE writes the same
791// constant value, rewrite every LOAD to a COPY of that constant.
792// This is a safe, cross-block SCCP-lite for allocas without needing
793// dominance/phi insertion. Handles the very common pattern of
794// `let x: i64 = 5; ...; use x` where opt_const_fold would have
795// folded the initial STORE's operand to a constant but can't push
796// through the ALLOCA/LOAD wrapper.
797//
798// Terminology:
799// escape = the alloca's Value id is used as an operand of ANY
800// instruction that isn't OP_LOAD (as op0) or OP_STORE
801// (as op0 -- address, not value). Escaped allocas are
802// untouchable here.
803//
804// Implementation: single forward scan per function.
805func opt_alloca_const(f: *Function) -> i64 {
806 var changed: i64 = 0
807 var bi: i64 = 0
808 while bi < f.n_blocks {
809 let b: *BasicBlock = block_at(f, bi)
810 var inst: *Instr = b.head
811 while inst != (0 as *Instr) {
812 if inst.op == OP_ALLOCA {
813 let aid: i64 = inst.result
814 // Pass 1: scan every instr in every block; classify
815 // uses of aid as LOAD-addr, STORE-addr, or escape.
816 var escaped: i64 = 0
817 var store_val: i64 = -1
818 var inconsistent: i64 = 0
819 var cbi: i64 = 0
820 while cbi < f.n_blocks {
821 let cb: *BasicBlock = block_at(f, cbi)
822 var ci: *Instr = cb.head
823 while ci != (0 as *Instr) {
824 if ci != inst {
825 if ci.op == OP_LOAD {
826 if ci.op0 == aid {} // fine: use-as-addr
827 // other operands of LOAD are a type hint only
828 } else {
829 if ci.op == OP_STORE {
830 if ci.op0 == aid {
831 // Check if stored value is a const
832 let sv: *Value = val_at(f, ci.op1)
833 if sv.kind == 0 {
834 if store_val == -1 {
835 store_val = ci.op1
836 } else {
837 if store_val != ci.op1 {
838 let s0: *Value = val_at(f, store_val)
839 if s0.const_int != sv.const_int {
840 inconsistent = 1
841 }
842 }
843 }
844 } else {
845 inconsistent = 1
846 }
847 }
848 if ci.op1 == aid { escaped = 1 }
849 } else {
850 // Cover op0..op15 -- same fix as opt_mem2reg
851 // escape detector above.
852 if ci.op0 == aid { escaped = 1 }
853 if ci.op1 == aid { escaped = 1 }
854 if ci.op2 == aid { escaped = 1 }
855 if ci.op3 == aid { escaped = 1 }
856 if ci.op4 == aid { escaped = 1 }
857 if ci.op5 == aid { escaped = 1 }
858 if ci.op6 == aid { escaped = 1 }
859 if ci.op7 == aid { escaped = 1 }
860 if ci.op8 == aid { escaped = 1 }
861 if ci.op9 == aid { escaped = 1 }
862 if ci.op10 == aid { escaped = 1 }
863 if ci.op11 == aid { escaped = 1 }
864 if ci.op12 == aid { escaped = 1 }
865 if ci.op13 == aid { escaped = 1 }
866 if ci.op14 == aid { escaped = 1 }
867 if ci.op15 == aid { escaped = 1 }
868 if ci.op16 == aid { escaped = 1 }
869 if ci.op17 == aid { escaped = 1 }
870 if ci.op18 == aid { escaped = 1 }
871 if ci.op19 == aid { escaped = 1 }
872 if ci.op20 == aid { escaped = 1 }
873 if ci.op21 == aid { escaped = 1 }
874 if ci.op22 == aid { escaped = 1 }
875 if ci.op23 == aid { escaped = 1 }
876 }
877 }
878 }
879 ci = ci.next
880 }
881 cbi = cbi + 1
882 }
883
884 if escaped == 0 {
885 if inconsistent == 0 {
886 if store_val >= 0 {
887 // Pass 2: rewrite every LOAD(aid) to
888 // COPY(store_val). Removes the load from
889 // the block; opt_dce sweeps the rest.
890 var cbi2: i64 = 0
891 while cbi2 < f.n_blocks {
892 let cb2: *BasicBlock = block_at(f, cbi2)
893 var ci2: *Instr = cb2.head
894 while ci2 != (0 as *Instr) {
895 if ci2.op == OP_LOAD {
896 if ci2.op0 == aid {
897 rewrite_to_copy(ci2, store_val)
898 changed = changed + 1
899 }
900 }
901 ci2 = ci2.next
902 }
903 cbi2 = cbi2 + 1
904 }
905 }
906 }
907 }
908 }
909 inst = inst.next
910 }
911 bi = bi + 1
912 }
913 return changed
914}
915
916// Per-block load forwarding: when a STORE(addr, val) is followed by
917// a LOAD(addr) with no intervening memory-side-effect instruction,
918// the LOAD is redundant -- rewrite it to COPY(val). Handles the
919// common parse.nx pattern `store alloca, rhs; load alloca` that
920// comes out of every `var x = ...; x` sequence.
921//
922// Limitations (covered by followups):
923// * single-block only -- cross-block load-forward needs dominance
924// * no alias checking: if an OP_STORE or OP_CALL between the pair
925// might write the same address, forwarding is unsafe; we bail.
926//
927// OP_LOAD = 41, OP_STORE = 42, OP_GEP = 44 (from types.nx).
928// Bounded backward walk: opt_load_forward used to walk inst.prev
929// without a safety bound and crashed on multi-block while-loop
930// shapes (out_i64). Two robustness guards now in place:
931//
932// 1. OPT_LOAD_FWD_MAX_WALK caps the backward walk at 64 instrs
933// per LOAD. Stores further back are unlikely to be
934// forwardable usefully.
935// 2. parent-mismatch bail: if cur.parent != b (the block we're
936// iterating), the linked list has somehow crossed bb
937// boundaries -- bail rather than walk into stale memory.
938// Symptom of corrupt IR; safer to leave the LOAD intact.
939const OPT_LOAD_FWD_MAX_WALK: i64 = 64
940
941// CROSS-BLOCK EXTENSION (2026-07-25). The limitation note above says cross-block forwarding
942// "needs dominance"; the cheap and fully sound slice of it needs only a PREDECESSOR COUNT. When
943// the backward walk reaches the top of a block that has EXACTLY ONE predecessor, that predecessor
944// is the only way to arrive, so a store found there is guaranteed to reach this load -- no
945// dominance query and no alias analysis required, and the existing bail-on-call / bail-on-other-
946// store rules still do all the safety work.
947//
948// A block with two or more predecessors (notably any loop header) is never entered, so a value
949// arriving from a back edge can never be forwarded -- which is the unsound case this would
950// otherwise walk straight into.
951//
952// Measured motivation: in the slice benchmark's inner loop, block bb13 reloads BOTH the index and
953// the length from stack slots that bb11 -- its single predecessor -- had just stored. The IR is
954// alloca-based with no phi nodes, so every loop-carried variable lives in memory and these
955// reload pairs are everywhere, not just here.
956//
957// DEFAULT 0, DELIBERATELY. This extension is UNPROVEN: the pass it lives in is disabled in
958// opt_run, so this code has never executed on real IR. Measuring it required enabling the pass,
959// and doing that turned the gauntlet RED 11/24 for reasons that predate this extension. Leaving
960// it on would mean shipping an untested transform the moment someone re-enables the pass, so the
961// safe default is off -- fix the pass first, then flip this and measure it on its own.
962const OPT_LOAD_FWD_CROSS_BLOCK: i64 = 0
963
964func opt_load_forward(f: *Function) -> i64 {
965 // succ/pred and .parent both go STALE across opt passes (T#opt-002 / T#opt-003 -- the same
966 // staleness that made LICM miscompile for a year). This pass now reads n_preds/pred0 and
967 // .parent, so it must rebuild them first rather than trust whatever the previous pass left.
968 if OPT_LOAD_FWD_CROSS_BLOCK == 1 {
969 cfg_rebuild_edges(f)
970 cfg_rebuild_parents(f)
971 }
972 var n: i64 = 0
973 var bi: i64 = 0
974 while bi < f.n_blocks {
975 let b: *BasicBlock = block_at(f, bi)
976 var inst: *Instr = b.head
977 while inst != (0 as *Instr) {
978 let next: *Instr = inst.next
979 if inst.op == OP_LOAD {
980 let addr_id: i64 = inst.op0
981 // SOUNDNESS GATE (2026-07-26) -- this is what was missing, and it is why the pass
982 // was disabled. The walk had NO alias analysis: it matched a prior STORE purely by
983 // comparing address VALUE IDS, so `var x; let p = &x; *p = 33; return *p` forwarded
984 // the stale value of x straight past the store through p. Two different ids can name
985 // the same memory the moment an address escapes.
986 //
987 // Fix: only forward from an alloca whose address NEVER ESCAPES -- reusing the exact
988 // predicate G9's load-hoist already relies on (used solely as op0 of LOAD/STORE).
989 // If the address never escapes, no other id can name that memory, so id comparison
990 // IS a sound alias test. `&x` makes the alloca an operand of OP_ADDR_OF, which the
991 // predicate rejects, so the failing shape is excluded by construction rather than
992 // by a special case.
993 //
994 // This narrows the pass -- computed pointers are no longer forwarded at all -- but a
995 // narrow sound pass beats a broad disabled one.
996 var fwd_ok: i64 = 0
997 if addr_id >= 0 {
998 if addr_id < f.n_values {
999 let av_f: *Value = val_at(f, addr_id)
1000 if av_f.kind == VK_INSTR {
1001 if av_f.instr != (0 as *Instr) {
1002 if av_f.instr.op == OP_ALLOCA {
1003 if licm_alloca_noescape(f, addr_id) == 1 { fwd_ok = 1 }
1004 }
1005 }
1006 }
1007 }
1008 }
1009 // wb = the block the walk is currently INSIDE. It starts as b and only ever moves
1010 // to a single-predecessor parent, so the parent-mismatch guard below must compare
1011 // against wb, not b.
1012 var wb: *BasicBlock = b
1013 var cur: *Instr = 0 as *Instr
1014 if fwd_ok == 1 { cur = inst.prev }
1015 var found: i64 = -1
1016 var stopped: i64 = 0
1017 var walks: i64 = 0
1018 while cur != (0 as *Instr) {
1019 if walks >= OPT_LOAD_FWD_MAX_WALK { stopped = 1 }
1020 // Parent-mismatch bail: walk shouldn't escape
1021 // the current basic block via stale prev links.
1022 if stopped == 0 {
1023 if cur.parent != wb { stopped = 1 }
1024 }
1025 if stopped == 0 {
1026 if cur.op == OP_STORE {
1027 if cur.op0 == addr_id {
1028 found = cur.op1
1029 cur = 0 as *Instr
1030 } else {
1031 stopped = 1
1032 }
1033 }
1034 if stopped == 0 {
1035 if cur.op == OP_CALL { stopped = 1 }
1036 if cur.op == OP_CALL_INDIRECT { stopped = 1 }
1037 // G3 FIX-2: __adc_acc writes memory through its pointer;
1038 // the backward load-forward walk must stop at it (it is
1039 // disabled today but planned -- pre-emptive barrier).
1040 if cur.op == OP_ADC_ACC { stopped = 1 }
1041 }
1042 }
1043 if stopped == 1 { cur = 0 as *Instr }
1044 if cur != (0 as *Instr) {
1045 cur = cur.prev
1046 // Top of wb reached with nothing found yet: step into the single
1047 // predecessor and keep walking from its tail. n_preds == 1 is the whole
1048 // soundness argument -- with two or more, some path could skip the store.
1049 // The walk budget still bounds this, so a self-loop or a long
1050 // single-entry chain terminates rather than spinning.
1051 if cur == (0 as *Instr) {
1052 if OPT_LOAD_FWD_CROSS_BLOCK == 1 {
1053 if found < 0 {
1054 if wb.n_preds == 1 {
1055 if wb.pred0 != (0 as *BasicBlock) {
1056 wb = wb.pred0
1057 cur = wb.tail
1058 }
1059 }
1060 }
1061 }
1062 }
1063 }
1064 walks = walks + 1
1065 }
1066 if found >= 0 {
1067 rewrite_to_copy(inst, found)
1068 n = n + 1
1069 }
1070 }
1071 inst = next
1072 }
1073 bi = bi + 1
1074 }
1075 return n
1076}
1077
1078// Forward decl -- const_one() is defined right below this function.
1079func const_one(f: *Function) -> i64;
1080
1081func opt_simplify(f: *Function) -> i64 {
1082 var n: i64 = 0
1083 var bi: i64 = 0
1084 while bi < f.n_blocks {
1085 let b: *BasicBlock = block_at(f, bi)
1086 var inst: *Instr = b.head
1087 while inst != (0 as *Instr) {
1088 if inst.n_operands == 2 {
1089 let a_id: i64 = inst.op0
1090 let bv_id: i64 = inst.op1
1091 let op: i64 = inst.op
1092
1093 // ADD: x+0 = x
1094 if op == 1 {
1095 if is_const_val(f, bv_id, 0) { rewrite_to_copy(inst, a_id); n = n + 1 }
1096 if is_const_val(f, a_id, 0) { rewrite_to_copy(inst, bv_id); n = n + 1 }
1097 }
1098 // SUB: x-0 = x
1099 if op == 2 {
1100 if is_const_val(f, bv_id, 0) { rewrite_to_copy(inst, a_id); n = n + 1 }
1101 }
1102 // MUL: x*1, x*0
1103 if op == 3 {
1104 if is_const_val(f, bv_id, 1) { rewrite_to_copy(inst, a_id); n = n + 1 }
1105 if is_const_val(f, a_id, 1) { rewrite_to_copy(inst, bv_id); n = n + 1 }
1106 if is_const_val(f, bv_id, 0) { make_result_zero(f, inst); n = n + 1 }
1107 if is_const_val(f, a_id, 0) { make_result_zero(f, inst); n = n + 1 }
1108 }
1109 // AND: x & 0 = 0, x & -1 = x
1110 if op == 10 {
1111 if is_const_val(f, bv_id, 0) { make_result_zero(f, inst); n = n + 1 }
1112 if is_const_val(f, a_id, 0) { make_result_zero(f, inst); n = n + 1 }
1113 if is_const_val(f, bv_id, -1) { rewrite_to_copy(inst, a_id); n = n + 1 }
1114 }
1115 // OR: x | 0 = x
1116 if op == 11 {
1117 if is_const_val(f, bv_id, 0) { rewrite_to_copy(inst, a_id); n = n + 1 }
1118 if is_const_val(f, a_id, 0) { rewrite_to_copy(inst, bv_id); n = n + 1 }
1119 }
1120 // XOR: x ^ 0 = x
1121 if op == 12 {
1122 if is_const_val(f, bv_id, 0) { rewrite_to_copy(inst, a_id); n = n + 1 }
1123 if is_const_val(f, a_id, 0) { rewrite_to_copy(inst, bv_id); n = n + 1 }
1124 }
1125 // Shifts by 0
1126 if op == 13 { // SHL
1127 if is_const_val(f, bv_id, 0) { rewrite_to_copy(inst, a_id); n = n + 1 }
1128 }
1129 if op == 14 { // SHR_S
1130 if is_const_val(f, bv_id, 0) { rewrite_to_copy(inst, a_id); n = n + 1 }
1131 }
1132
1133 // Self-ops: fold away when both operands refer to
1134 // the same Value id. The SSA property guarantees
1135 // this means the SAME value, so identities like
1136 // x - x = 0 x ^ x = 0 x & x = x x | x = x
1137 // are safe without requiring VN / GVN.
1138 if a_id == bv_id {
1139 if op == 2 { make_result_zero(f, inst); n = n + 1 } // SUB
1140 if op == 12 { make_result_zero(f, inst); n = n + 1 } // XOR
1141 if op == 10 { rewrite_to_copy(inst, a_id); n = n + 1 } // AND
1142 if op == 11 { rewrite_to_copy(inst, a_id); n = n + 1 } // OR
1143 // Comparisons on same Value:
1144 if op == 20 { rewrite_to_copy(inst, const_one(f)); n = n + 1 } // EQ -> 1
1145 if op == 21 { make_result_zero(f, inst); n = n + 1 } // NE -> 0
1146 if op == 22 { make_result_zero(f, inst); n = n + 1 } // LT -> 0
1147 if op == 23 { rewrite_to_copy(inst, const_one(f)); n = n + 1 } // LE -> 1
1148 if op == 24 { make_result_zero(f, inst); n = n + 1 } // GT -> 0
1149 if op == 25 { rewrite_to_copy(inst, const_one(f)); n = n + 1 } // GE -> 1
1150 }
1151 }
1152 inst = inst.next
1153 }
1154 bi = bi + 1
1155 }
1156 return n
1157}
1158
1159// Helper: allocate or reuse a constant-1 Value in function f.
1160// Scans f.values for an existing VAL_CONST with const_int==1; if
1161// absent, creates one. Cached across calls within a pass by
1162// recomputing -- cheap enough for the small functions our compiler
1163// produces.
1164func const_one(f: *Function) -> i64 {
1165 var v: i64 = 0
1166 let base: i64 = f.values as i64
1167 while v < f.n_values {
1168 let vv: *Value = (base + v * 48) as *Value
1169 if vv.kind == VAL_CONST {
1170 if vv.const_int == 1 { return v }
1171 }
1172 v = v + 1
1173 }
1174 // Create a new VAL_CONST with value 1. Mirrors ir_const_i64.
1175 let id: i64 = f.n_values
1176 let nv: *Value = (base + id * 48) as *Value
1177 nv.kind = VAL_CONST
1178 nv.const_int = 1
1179 f.n_values = id + 1
1180 return id
1181}
1182
1183// ===== dead code elimination ======================================
1184//
1185// A pure instruction with no readers is dead. "Pure" = any non-
1186// side-effecting opcode: arithmetic, logic, compares, copies, casts.
1187// Anything that touches memory, calls out, or branches stays.
1188//
1189// Algorithm:
1190// 1. Scan the whole function once, marking used[id]=1 for every
1191// operand we see.
1192// 2. Second pass: for each instruction whose result is unused AND
1193// pure, unlink from its block's list.
1194
1195func op_is_pure(op: i64) -> i64 {
1196 if op == 1 { return 1 } // ADD
1197 if op == 2 { return 1 } // SUB
1198 if op == 3 { return 1 } // MUL
1199 if op == 4 { return 1 } // DIV_S
1200 if op == 6 { return 1 } // REM_S
1201 if op == 10 { return 1 } // AND
1202 if op == 11 { return 1 } // OR
1203 if op == 12 { return 1 } // XOR
1204 if op == 13 { return 1 } // SHL
1205 if op == 14 { return 1 } // SHR_S
1206 if op == 15 { return 1 } // SHR_U
1207 if op >= 20 { if op <= 25 { return 1 } } // cmp family
1208 if op == 40 { return 1 } // COPY
1209 return 0
1210}
1211
1212func mark_used(f: *Function, used: *u8) -> i64 {
1213 var bi: i64 = 0
1214 while bi < f.n_blocks {
1215 let b: *BasicBlock = block_at(f, bi)
1216 var inst: *Instr = b.head
1217 while inst != (0 as *Instr) {
1218 let n: i64 = inst.n_operands
1219 // BR operand is a block id, not a Value.
1220 if inst.op != 31 {
1221 // Cover op0..op15. Prior versions covered only
1222 // op0..op3, silently dropping marks for op4..op15.
1223 // For OP_CALL with > 4 args (e.g. 11-arg AEAD calls
1224 // landed in the off-C arc 2026-05-20), the defining
1225 // instructions of args 5..11 were then mistakenly
1226 // judged "unused" by opt_dce and DELETED. That cascade
1227 // produced TRUNCATED FUNCTION BODIES + GARBAGE call
1228 // labels in the native x86_64 self-host bootstrap.
1229 // This is the partner fix to read_op/write_op coverage
1230 // extension (commit 8efd1949).
1231 if n >= 1 { used[inst.op0] = 1 }
1232 if n >= 2 { used[inst.op1] = 1 }
1233 if n >= 3 { used[inst.op2] = 1 }
1234 if n >= 4 { used[inst.op3] = 1 }
1235 if n >= 5 { used[inst.op4] = 1 }
1236 if n >= 6 { used[inst.op5] = 1 }
1237 if n >= 7 { used[inst.op6] = 1 }
1238 if n >= 8 { used[inst.op7] = 1 }
1239 if n >= 9 { used[inst.op8] = 1 }
1240 if n >= 10 { used[inst.op9] = 1 }
1241 if n >= 11 { used[inst.op10] = 1 }
1242 if n >= 12 { used[inst.op11] = 1 }
1243 if n >= 13 { used[inst.op12] = 1 }
1244 if n >= 14 { used[inst.op13] = 1 }
1245 if n >= 15 { used[inst.op14] = 1 }
1246 if n >= 16 { used[inst.op15] = 1 }
1247 if n >= 17 { used[inst.op16] = 1 }
1248 if n >= 18 { used[inst.op17] = 1 }
1249 if n >= 19 { used[inst.op18] = 1 }
1250 if n >= 20 { used[inst.op19] = 1 }
1251 if n >= 21 { used[inst.op20] = 1 }
1252 if n >= 22 { used[inst.op21] = 1 }
1253 if n >= 23 { used[inst.op22] = 1 }
1254 if n >= 24 { used[inst.op23] = 1 }
1255 }
1256 inst = inst.next
1257 }
1258 bi = bi + 1
1259 }
1260 return 0
1261}
1262
1263func unlink(b: *BasicBlock, inst: *Instr) -> i64 {
1264 if inst.prev != (0 as *Instr) {
1265 inst.prev.next = inst.next
1266 }
1267 if inst.prev == (0 as *Instr) {
1268 b.head = inst.next
1269 }
1270 if inst.next != (0 as *Instr) {
1271 inst.next.prev = inst.prev
1272 }
1273 if inst.next == (0 as *Instr) {
1274 b.tail = inst.prev
1275 }
1276 return 0
1277}
1278
1279func opt_dce(f: *Function) -> i64 {
1280 let used: *u8 = sys_mmap(f.n_values + 8)
1281 mark_used(f, used)
1282 var killed: i64 = 0
1283 var bi: i64 = 0
1284 while bi < f.n_blocks {
1285 let b: *BasicBlock = block_at(f, bi)
1286 var inst: *Instr = b.head
1287 while inst != (0 as *Instr) {
1288 let next: *Instr = inst.next
1289 if op_is_pure(inst.op) {
1290 let res_used: i64 = used[inst.result]
1291 let folded_away: i64 = 0
1292 // If result Value became a constant (fold kept it
1293 // as VAL_CONST_INT), the instruction is redundant
1294 // even if `used` is 1 -- readers see the literal.
1295 let vres: *Value = val_at(f, inst.result)
1296 var drop: i64 = 0
1297 if res_used == 0 { drop = 1 }
1298 if vres.kind == 0 {
1299 if op_is_pure(inst.op) { drop = 1 }
1300 }
1301 if drop {
1302 unlink(b, inst)
1303 killed = killed + 1
1304 }
1305 }
1306 inst = next
1307 }
1308 bi = bi + 1
1309 }
1310 return killed
1311}
1312
1313// ===== driver =====================================================
1314//
1315// Run fold -> simplify -> dce until a round makes no changes.
1316
1317// Mini comptime interpreter: evaluate a pure binop over two Value
1318// ids whose const values we've already resolved. Returns the
1319// computed const; caller checks that both inputs are known.
1320func comptime_eval_binop(op: i64, a: i64, b: i64) -> i64 {
1321 if op == OP_ADD { return a + b }
1322 if op == OP_SUB { return a - b }
1323 if op == OP_MUL { return a * b }
1324 if op == OP_DIV_S {
1325 if b == 0 { return 0 }
1326 return a / b
1327 }
1328 if op == OP_REM_S {
1329 if b == 0 { return 0 }
1330 return a % b
1331 }
1332 if op == OP_AND { return a & b }
1333 if op == OP_OR { return a | b }
1334 if op == OP_XOR { return a ^ b }
1335 if op == OP_SHL { return a << b }
1336 if op == OP_SHR_S { return a >> b }
1337 if op == OP_EQ {
1338 if a == b { return 1 }
1339 return 0
1340 }
1341 if op == OP_NE {
1342 if a != b { return 1 }
1343 return 0
1344 }
1345 if op == OP_LT_S {
1346 if a < b { return 1 }
1347 return 0
1348 }
1349 if op == OP_LE_S {
1350 if a <= b { return 1 }
1351 return 0
1352 }
1353 if op == OP_GT_S {
1354 if a > b { return 1 }
1355 return 0
1356 }
1357 if op == OP_GE_S {
1358 if a >= b { return 1 }
1359 return 0
1360 }
1361 return 0
1362}
1363
1364// Whole-program constant-return folding with comptime-style eval --
1365// gcc needs -flto + IPA-CP for this, NishiLang gets it free.
1366//
1367// Scans every function in the module; for each one, try to evaluate
1368// its body as a straight-line computation over constants. The
1369// walker maintains an (SSA value id → const int) map; it extends
1370// the map on each VAL_CONST_INT and each binop whose both operands
1371// are in the map. If execution reaches the function's RETURN with
1372// a mapped operand, the function is const-return.
1373//
1374// Handles:
1375// * Nullary functions (no params)
1376// * Single basic block
1377// * Straight-line arithmetic, bitwise, comparison over consts
1378// * Binops whose operands trace back to CONST_INTs
1379//
1380// No side-effecting ops allowed (OP_STORE, OP_CALL, OP_SYSCALL).
1381// If any instruction violates these, the function is considered
1382// unfoldable and left alone.
1383//
1384// Skips callers-before-callees ordering -- a single pass suffices
1385// because we apply to the module, not in a bottom-up scan. Callers
1386// of callers that fold to consts get picked up on the next opt_run
1387// iteration via const_fold.
1388func opt_module_const_return(m: *Module) -> i64 {
1389 // Walk m.functions; identify const-return funcs by f.name_start
1390 // (pointer-as-i64) since that's our stable-identifier today.
1391 // Side table: const_func_id[i] = 1 if function `i` is const-return.
1392 // Parallel: const_val[i] = the returned value.
1393 let n: i64 = m.n_functions
1394 let mark_raw: *u8 = sys_mmap(n + 8)
1395 let mark: *u8 = mark_raw
1396 let vals_raw: *u8 = sys_mmap(n * 8 + 16)
1397 let vals: *i64 = vals_raw as *i64
1398
1399 // Pass 1: classify.
1400 var i: i64 = 0
1401 while i < n {
1402 let fn_base: i64 = m.functions as i64
1403 let f: *Function = (fn_base + i * 176) as *Function
1404 mark[i] = 0
1405 vals[i] = 0
1406 // Only attempt comptime-eval for nullary single-block funcs.
1407 // Functions with params can't be eval'd without the caller's
1408 // arg values (specialization is a follow-up pass).
1409 if f.n_blocks == 1 {
1410 if f.n_params == 0 {
1411 let b: *BasicBlock = block_at(f, 0)
1412 // Side-effect check + build (value_id -> const) map.
1413 var pure: i64 = 1
1414 let kmap_raw: *u8 = sys_mmap(f.n_values + 8)
1415 let kmap: *u8 = kmap_raw // 1 = value known const
1416 let vmap_raw: *u8 = sys_mmap(f.n_values * 8 + 16)
1417 let vmap: *i64 = vmap_raw as *i64
1418 // Seed the map with every VAL_CONST_INT in the function.
1419 var vi: i64 = 0
1420 while vi < f.n_values {
1421 let v: *Value = val_at(f, vi)
1422 if v.kind == VK_CONST_INT {
1423 kmap[vi] = 1
1424 vmap[vi] = v.const_int
1425 }
1426 vi = vi + 1
1427 }
1428 var inst: *Instr = b.head
1429 while inst != (0 as *Instr) {
1430 let op: i64 = inst.op
1431 if op == OP_STORE { pure = 0 }
1432 if op == OP_CALL { pure = 0 }
1433 if op == OP_CALL_INDIRECT { pure = 0 }
1434 if op == OP_SYSCALL { pure = 0 }
1435 if op == OP_LOAD { pure = 0 }
1436 if op == OP_ALLOCA { pure = 0 }
1437 if op == OP_GEP { pure = 0 }
1438 // Evaluate binop/cmp if both operands are known.
1439 if inst.n_operands == 2 {
1440 if kmap[inst.op0] == 1 {
1441 if kmap[inst.op1] == 1 {
1442 let r: i64 = comptime_eval_binop(op,
1443 vmap[inst.op0],
1444 vmap[inst.op1])
1445 kmap[inst.result] = 1
1446 vmap[inst.result] = r
1447 }
1448 }
1449 }
1450 // OP_COPY just forwards op0.
1451 if op == OP_COPY {
1452 if kmap[inst.op0] == 1 {
1453 kmap[inst.result] = 1
1454 vmap[inst.result] = vmap[inst.op0]
1455 }
1456 }
1457 inst = inst.next
1458 }
1459 if pure == 1 {
1460 let tail: *Instr = b.tail
1461 if tail != (0 as *Instr) {
1462 if tail.op == OP_RETURN {
1463 if tail.n_operands > 0 {
1464 if kmap[tail.op0] == 1 {
1465 mark[i] = 1
1466 vals[i] = vmap[tail.op0]
1467 }
1468 }
1469 }
1470 }
1471 }
1472 }
1473 }
1474 i = i + 1
1475 }
1476
1477 // Pass 2: rewrite calls to const-return functions. Match callees
1478 // by walking the Function pool pointer.
1479 var changed: i64 = 0
1480 var j: i64 = 0
1481 while j < n {
1482 let fn_base2: i64 = m.functions as i64
1483 let f2: *Function = (fn_base2 + j * 176) as *Function
1484 var bi: i64 = 0
1485 while bi < f2.n_blocks {
1486 let b2: *BasicBlock = block_at(f2, bi)
1487 var ci: *Instr = b2.head
1488 while ci != (0 as *Instr) {
1489 if ci.op == OP_CALL {
1490 // Find which function in m.functions this callee
1491 // corresponds to; match by pointer equality.
1492 var k: i64 = 0
1493 while k < n {
1494 let ft: *Function = (fn_base2 + k * 176) as *Function
1495 if ft == ci.callee {
1496 if mark[k] == 1 {
1497 // Emit a fresh CONST_INT Value for the
1498 // folded result so the COPY has a
1499 // proper source.
1500 let cv: i64 = ir_const_i64(f2, vals[k])
1501 rewrite_to_copy(ci, cv)
1502 changed = changed + 1
1503 }
1504 k = n
1505 }
1506 k = k + 1
1507 }
1508 }
1509 ci = ci.next
1510 }
1511 bi = bi + 1
1512 }
1513 j = j + 1
1514 }
1515 return changed
1516}
1517
1518// Whole-program function REACHABILITY -- the B1 rung of /compare/toolchain (2026-08-18).
1519//
1520// MARK ONLY. Never compacts m.functions[]. The body this replaces (opt.c's opt_module_dce port,
1521// BUILT+UNWIRED since it was written) compacted the pool IN PLACE, which moves Function records
1522// while every OP_CALL.callee and every VK_FUNC_ADDR const_int still points at the OLD slot
1523// address -- a caller would then emit `call <whatever record now occupies that slot>`. It also
1524// predated function pointers: its own L3 said "no function-pointer escape today", which stopped
1525// being true when VK_FUNC_ADDR / OP_CALL_INDIRECT / __thread_clone landed. Nothing ever called it,
1526// which is the only reason it never miscompiled anything. Rewritten, not patched (rule 3).
1527//
1528// live[i] = 1 iff m.functions[i] is reachable from the roots; every other slot is left 0, so the
1529// caller MUST hand in a zeroed buffer of at least m.n_functions bytes (sys_mmap is zero-filled).
1530// ROOT `main` -- the _start trampoline calls it by name (x86ctx_emit_module). If there is no
1531// main nothing is live and the emitter's own "no functions" path decides; this pass does
1532// not invent a root.
1533// E1 OP_CALL / OP_TAIL_CALL instr.callee (*Function INTO the pool; opt_tail_call keeps it)
1534// E2 VK_FUNC_ADDR values v.const_int (*Function: `&fn`, bare-name-as-value, the
1535// __thread_clone entry, and the fn-ptr operand x86ctx folds back to a direct call)
1536// Those are the ONLY two ways the IR names a function (nx_ir.nx: ir_emit_call sets .callee;
1537// ir_func_addr_value sets VK_FUNC_ADDR; ir_emit_call_indirect sets .callee = null on purpose).
1538// E2 is scanned over the WHOLE value pool of each live function, so a VK_FUNC_ADDR that a later
1539// opt pass orphans still keeps its target live -- conservative, never unsafe.
1540//
1541// WHY A BUG HERE CANNOT MISCOMPILE (the property that makes this the SAFEST toolchain rung):
1542// keeping too MUCH costs bytes; keeping too LITTLE leaves a `call X` / `leaq X(%rip)` whose label
1543// is never emitted, and nxasm REFUSES it -- axc_label_resolve exits 102 "UNDEFINED label", and
1544// every symbol consumer (call / jmp / jcc / leaq-rip) routes through that one resolver. The
1545// GNU as+ld lane refuses the same way (undefined reference). So a missed edge is a LOUD build
1546// failure, never a wrong binary. Bite-proven the day it shipped: with E2 disabled, every
1547// crash-guarded program fails to assemble on nx_crash_on_signal.
1548//
1549// Returns the number of functions marked dead. m.n_functions is untouched, so every pointer into
1550// the pool stays valid and every later walker (opt loop, IR dump, emitter) reads the same slots.
1551func opt_module_dce_mark(m: *Module, live: *u8) -> i64 {
1552 let n: i64 = m.n_functions
1553 if n <= 0 { return 0 }
1554 let fn_base: i64 = m.functions as i64
1555 let stride: i64 = NX_MODULE_FN_STRIDE
1556
1557 let work_raw: *u8 = sys_mmap(n * 8 + 16)
1558 let work: *i64 = work_raw as *i64
1559 var w_head: i64 = 0
1560 var w_tail: i64 = 0
1561
1562 // ROOT: main, located by the module's own name lookup (one ruler, not a second byte compare).
1563 let mainf: *Function = find_function(m, "main" as *u8, 4)
1564 if mainf != (0 as *Function) {
1565 let moff: i64 = (mainf as i64) - fn_base
1566 if moff >= 0 {
1567 if (moff % stride) == 0 {
1568 let mi: i64 = moff / stride
1569 if mi < n {
1570 live[mi] = 1 as u8
1571 work[w_tail] = mi
1572 w_tail = w_tail + 1
1573 }
1574 }
1575 }
1576 }
1577
1578 // BFS. Each function is enqueued at most once (live[] doubles as the visited set).
1579 while w_head < w_tail {
1580 let fi: i64 = work[w_head]
1581 w_head = w_head + 1
1582 let f: *Function = (fn_base + fi * stride) as *Function
1583
1584 // E1: static callees, every block, every instruction.
1585 var bi: i64 = 0
1586 while bi < f.n_blocks {
1587 let bb: *BasicBlock = block_at(f, bi)
1588 var inst: *Instr = bb.head
1589 while inst != (0 as *Instr) {
1590 var callee_ptr: i64 = 0
1591 if inst.op == OP_CALL { callee_ptr = inst.callee as i64 }
1592 if inst.op == OP_TAIL_CALL { callee_ptr = inst.callee as i64 }
1593 if callee_ptr != 0 {
1594 let off: i64 = callee_ptr - fn_base
1595 if off >= 0 {
1596 if (off % stride) == 0 {
1597 let ci: i64 = off / stride
1598 if ci < n {
1599 if live[ci] == 0 {
1600 live[ci] = 1 as u8
1601 work[w_tail] = ci
1602 w_tail = w_tail + 1
1603 }
1604 }
1605 }
1606 }
1607 }
1608 inst = inst.next
1609 }
1610 bi = bi + 1
1611 }
1612
1613 // E2: address-taken functions, the whole value pool.
1614 var vi: i64 = 0
1615 while vi < f.n_values {
1616 let v: *Value = val_at(f, vi)
1617 if v.kind == VK_FUNC_ADDR {
1618 let aoff: i64 = v.const_int - fn_base
1619 if aoff >= 0 {
1620 if (aoff % stride) == 0 {
1621 let ai: i64 = aoff / stride
1622 if ai < n {
1623 if live[ai] == 0 {
1624 live[ai] = 1 as u8
1625 work[w_tail] = ai
1626 w_tail = w_tail + 1
1627 }
1628 }
1629 }
1630 }
1631 }
1632 vi = vi + 1
1633 }
1634 }
1635
1636 // The dead count is n minus the reached count; w_tail IS the reached count because every
1637 // enqueue is guarded by live[]==0 (no double counting), so the two partitions sum to n.
1638 return n - w_tail
1639}
1640
1641// opt_sweep_unreachable_function: port of opt.c's per-function
1642// reachability-based block compaction. BFS from entry marks
1643// reachable blocks, rewrites branch targets with renumbered ids,
1644// compacts f.blocks[], prunes stale pred/succ entries.
1645//
1646// Essential after jump threading or DCE that creates orphan
1647// blocks. Matches opt.c behaviour; SWEEP1-SWEEP4 invariants
1648// mirror the comment in opt.c:
1649// SWEEP1 Branch operands rewritten BEFORE compaction (while
1650// old ids are still valid indices).
1651// SWEEP2 Block ids reassigned in lockstep with compaction so
1652// the f.blocks[i].id == i invariant holds afterwards.
1653// SWEEP3 Pred/succ lists pruned to drop references to dead
1654// blocks (otherwise dominator analysis reading
1655// f.blocks[pred.id] hits stale memory).
1656// SWEEP4 No-op fast path: if nothing unreachable, returns 0
1657// without touching anything.
1658
1659func opt_sweep_unreachable_function(f: *Function) -> i64 {
1660 let n: i64 = f.n_blocks
1661 if n == 0 { return 0 }
1662
1663 // reach[i] = 1 if block i is reachable from entry.
1664 let reach_raw: *u8 = sys_mmap(n + 16)
1665 let reach: *u8 = reach_raw
1666 var i: i64 = 0
1667 while i < n { reach[i] = 0; i = i + 1 }
1668
1669 // Worklist (block indices). Seed with entry id.
1670 let work_raw: *u8 = sys_mmap(n * 8 + 16)
1671 let work: *i64 = work_raw as *i64
1672 var w_head: i64 = 0
1673 var w_tail: i64 = 0
1674 // Entry block's id is its array index post-parse (stable
1675 // invariant); re-check by walking if needed.
1676 reach[f.entry.id] = 1
1677 work[w_tail] = f.entry.id
1678 w_tail = w_tail + 1
1679
1680 // BFS via BR / BR_COND op operands -- the authoritative successor
1681 // ids. Earlier versions walked bb.succ0 / bb.succ1, but other opt
1682 // passes (sccp_branches, thread_jumps, block_merge) rewrite the ops
1683 // without touching succ pointers, so pointers go stale across a
1684 // single opt_run round and BFS missed live edges. Walking the same
1685 // ids the riscv emitter writes into asm keeps reach in lockstep
1686 // with what the assembler will reference.
1687 while w_head < w_tail {
1688 let bi: i64 = work[w_head]
1689 w_head = w_head + 1
1690 let bb: *BasicBlock = block_at(f, bi)
1691 var inst: *Instr = bb.head
1692 while inst != (0 as *Instr) {
1693 if inst.op == OP_BR {
1694 let t: i64 = inst.op0
1695 if t >= 0 {
1696 if t < n {
1697 if reach[t] == 0 {
1698 reach[t] = 1
1699 work[w_tail] = t
1700 w_tail = w_tail + 1
1701 }
1702 }
1703 }
1704 }
1705 if inst.op == OP_BR_COND {
1706 let t1: i64 = inst.op1
1707 if t1 >= 0 {
1708 if t1 < n {
1709 if reach[t1] == 0 {
1710 reach[t1] = 1
1711 work[w_tail] = t1
1712 w_tail = w_tail + 1
1713 }
1714 }
1715 }
1716 let t2: i64 = inst.op2
1717 if t2 >= 0 {
1718 if t2 < n {
1719 if reach[t2] == 0 {
1720 reach[t2] = 1
1721 work[w_tail] = t2
1722 w_tail = w_tail + 1
1723 }
1724 }
1725 }
1726 }
1727 inst = inst.next
1728 }
1729 }
1730
1731 // Compute new ids. newid[i] = -1 if unreachable, else new
1732 // compacted position.
1733 let newid_raw: *u8 = sys_mmap(n * 8 + 16)
1734 let newid: *i64 = newid_raw as *i64
1735 var new_n: i64 = 0
1736 i = 0
1737 while i < n {
1738 newid[i] = -1
1739 if reach[i] == 1 {
1740 newid[i] = new_n
1741 new_n = new_n + 1
1742 }
1743 i = i + 1
1744 }
1745
1746 // SWEEP4: nothing unreachable -> fast exit.
1747 if new_n == n { return 0 }
1748
1749 // SWEEP1: rewrite branch operands before compaction.
1750 i = 0
1751 while i < n {
1752 if reach[i] == 1 {
1753 let bb: *BasicBlock = block_at(f, i)
1754 var inst: *Instr = bb.head
1755 while inst != (0 as *Instr) {
1756 if inst.op == OP_BR {
1757 let t: i64 = inst.op0
1758 if t < n {
1759 if newid[t] >= 0 { inst.op0 = newid[t] }
1760 }
1761 }
1762 if inst.op == OP_BR_COND {
1763 let t1: i64 = inst.op1
1764 let t2: i64 = inst.op2
1765 if t1 < n {
1766 if newid[t1] >= 0 { inst.op1 = newid[t1] }
1767 }
1768 if t2 < n {
1769 if newid[t2] >= 0 { inst.op2 = newid[t2] }
1770 }
1771 }
1772 inst = inst.next
1773 }
1774 }
1775 i = i + 1
1776 }
1777
1778 // SWEEP2: compact blocks in-place + reassign ids. Unlike opt.c
1779 // we keep a single backing pool for the lifetime of the function
1780 // (sized in ir_function_new); compaction copies the 96-byte
1781 // BasicBlock record forward inside that pool.
1782 // STUB(opt, never): "fixed pool" is the chosen architecture for
1783 // opt.nx -- pool size lives in ir_function_new and is the real
1784 // bound; no realloc path is needed.
1785 let block_stride: i64 = 96
1786 let bb_base: i64 = f.blocks as i64
1787 var write_idx: i64 = 0
1788 var read_idx: i64 = 0
1789 while read_idx < n {
1790 if reach[read_idx] == 1 {
1791 let src: i64 = bb_base + read_idx * block_stride
1792 let dst: i64 = bb_base + write_idx * block_stride
1793 if src != dst {
1794 let src_p: *u8 = src as *u8
1795 let dst_p: *u8 = dst as *u8
1796 var k: i64 = 0
1797 while k < block_stride {
1798 dst_p[k] = src_p[k]
1799 k = k + 1
1800 }
1801 }
1802 let bb_new: *BasicBlock = (dst) as *BasicBlock
1803 bb_new.id = write_idx
1804 write_idx = write_idx + 1
1805 }
1806 read_idx = read_idx + 1
1807 }
1808 f.n_blocks = new_n
1809
1810 // SWEEP3: prune stale pred pointers after compaction.
1811 // Note: a previous attempt also rebuilt succ pointers from
1812 // BR/BR_COND ops; that interacted badly with opt_thread_jumps /
1813 // opt_block_merge inside opt_run and caused codegen to hang on
1814 // probe.nx. The opt_sweep BFS itself was changed to walk BR
1815 // ops (not succ pointers) in commit 4f4e682, so sweep doesn't
1816 // depend on succ being current anyway.
1817 // STUB(opt, T#opt-002): post-sweep succs remain stale. Other
1818 // passes that walk succs (opt_block_merge, opt_thread_jumps,
1819 // opt_dce) may misbehave on real-world IR. Validator V3 will
1820 // fire when post-opt validation is re-enabled.
1821 // Plan: refactor each succ-walking pass to walk BR ops the
1822 // way sweep does, OR rebuild succs in SWEEP3 once we
1823 // understand why the rebuild interacted with opt_run.
1824 // Closes when: post-opt ir_validate runs clean on probe.nx.
1825 i = 0
1826 while i < new_n {
1827 let bb: *BasicBlock = block_at(f, i)
1828 if bb.pred0 != (0 as *BasicBlock) {
1829 let pid: i64 = bb.pred0.id
1830 if pid >= new_n { bb.pred0 = 0 as *BasicBlock }
1831 }
1832 if bb.pred1 != (0 as *BasicBlock) {
1833 let pid: i64 = bb.pred1.id
1834 if pid >= new_n { bb.pred1 = 0 as *BasicBlock }
1835 }
1836 if bb.pred2 != (0 as *BasicBlock) {
1837 let pid: i64 = bb.pred2.id
1838 if pid >= new_n { bb.pred2 = 0 as *BasicBlock }
1839 }
1840 i = i + 1
1841 }
1842 return 1
1843}
1844
1845// opt_copyprop: port of opt.c's copy-propagation pass. Rewrites
1846// OP_COPY destinations that trace to a constant source so the dst
1847// Value itself becomes VAL_CONST_INT. Downstream const-fold then
1848// collapses further.
1849//
1850// Merge values (multi-def) are EXCLUDED: a value written by two
1851// different COPY instrs in different predecessor blocks (e.g.
1852// from mem2reg phi elimination) holds different constants on
1853// different paths; const-propagating one of them would miscompile
1854// the other path.
1855//
1856// Two invariants:
1857// CP1 multi_def[] is built in a full first pass so we know EVERY
1858// value's def count before rewriting.
1859// CP2 Never rewrite a Value whose def count > 1.
1860
1861func opt_copyprop(f: *Function) -> i64 {
1862 if f.n_values == 0 { return 0 }
1863 let multi_raw: *u8 = sys_mmap(f.n_values + 16)
1864 let multi: *u8 = multi_raw
1865 let seen_raw: *u8 = sys_mmap(f.n_values + 16)
1866 let seen: *u8 = seen_raw
1867 var vi: i64 = 0
1868 while vi < f.n_values {
1869 multi[vi] = 0
1870 seen[vi] = 0
1871 vi = vi + 1
1872 }
1873
1874 // Pass 1: count defs.
1875 var bi: i64 = 0
1876 while bi < f.n_blocks {
1877 let bb: *BasicBlock = block_at(f, bi)
1878 var inst: *Instr = bb.head
1879 while inst != (0 as *Instr) {
1880 // Skip instrs that don't produce a value.
1881 var produces: i64 = 1
1882 if inst.op == OP_BR { produces = 0 }
1883 if inst.op == OP_BR_COND { produces = 0 }
1884 if inst.op == OP_RETURN { produces = 0 }
1885 if inst.op == OP_STORE { produces = 0 }
1886 if inst.ty == (0 as *Type) { produces = 0 }
1887 if produces == 1 {
1888 if inst.ty.kind == TY_VOID { produces = 0 }
1889 }
1890 if produces == 1 {
1891 let r: i64 = inst.result
1892 if r < f.n_values {
1893 if seen[r] == 1 { multi[r] = 1 }
1894 else { seen[r] = 1 }
1895 }
1896 }
1897 inst = inst.next
1898 }
1899 bi = bi + 1
1900 }
1901
1902 // Pass 2: propagate const through COPY.
1903 var changed: i64 = 0
1904 bi = 0
1905 while bi < f.n_blocks {
1906 let bb: *BasicBlock = block_at(f, bi)
1907 var inst: *Instr = bb.head
1908 while inst != (0 as *Instr) {
1909 if inst.op == OP_COPY {
1910 if inst.n_operands >= 1 {
1911 let rid: i64 = inst.result
1912 if rid < f.n_values {
1913 if multi[rid] == 0 {
1914 let sid: i64 = inst.op0
1915 if sid < f.n_values {
1916 if multi[sid] == 0 {
1917 let src: *Value = val_at(f, sid)
1918 let dst: *Value = val_at(f, rid)
1919 if src.kind == VK_CONST_INT {
1920 if dst.kind != VK_CONST_INT {
1921 dst.kind = VK_CONST_INT
1922 dst.const_int = src.const_int
1923 changed = 1
1924 }
1925 }
1926 }
1927 }
1928 }
1929 }
1930 }
1931 }
1932 inst = inst.next
1933 }
1934 bi = bi + 1
1935 }
1936 return changed
1937}
1938
1939// Forward declarations for helpers used in opt_copy_forward.
1940// NishiLang forbids forward-references; declare signatures here.
1941func if_br_cond_then_1_else_n(inst: *Instr) -> i64;
1942func read_op(inst: *Instr, idx: i64) -> i64;
1943func write_op(inst: *Instr, idx: i64, v: i64) -> i64;
1944
1945// opt_copy_forward: chase single-def OP_COPY chains, replacing
1946// operand references with the original source. Distinct from
1947// opt_copyprop (which promotes the COPY *destination* to CONST if
1948// src is const). copy_forward rewrites USES to skip COPY stops.
1949//
1950// Two invariants (same safety reasoning as copyprop):
1951// CF1 Multi-def values (from merges) are NOT followed; stopping
1952// there preserves phi semantics.
1953// CF2 Chain length capped at 32 hops to prevent cycles + bound
1954// worst-case cost per rewrite.
1955
1956func opt_copy_forward(f: *Function) -> i64 {
1957 if f.n_values == 0 { return 0 }
1958 let seen_raw: *u8 = sys_mmap(f.n_values + 16)
1959 let seen: *u8 = seen_raw
1960 let multi_raw: *u8 = sys_mmap(f.n_values + 16)
1961 let multi: *u8 = multi_raw
1962 let src_raw: *u8 = sys_mmap(f.n_values * 8 + 16)
1963 let copy_src: *i64 = src_raw as *i64
1964 var k: i64 = 0
1965 while k < f.n_values {
1966 seen[k] = 0
1967 multi[k] = 0
1968 copy_src[k] = -1
1969 k = k + 1
1970 }
1971
1972 // Pass 1: def counts + record COPY sources.
1973 var bi: i64 = 0
1974 while bi < f.n_blocks {
1975 let bb: *BasicBlock = block_at(f, bi)
1976 var inst: *Instr = bb.head
1977 while inst != (0 as *Instr) {
1978 var produces: i64 = 1
1979 if inst.op == OP_BR { produces = 0 }
1980 if inst.op == OP_BR_COND { produces = 0 }
1981 if inst.op == OP_RETURN { produces = 0 }
1982 if inst.op == OP_STORE { produces = 0 }
1983 if inst.ty == (0 as *Type) { produces = 0 }
1984 if produces == 1 {
1985 if inst.ty.kind == TY_VOID { produces = 0 }
1986 }
1987 if produces == 1 {
1988 let r: i64 = inst.result
1989 if r < f.n_values {
1990 if seen[r] == 1 { multi[r] = 1 }
1991 else { seen[r] = 1 }
1992 if inst.op == OP_COPY {
1993 if inst.n_operands == 1 {
1994 copy_src[r] = inst.op0
1995 }
1996 }
1997 }
1998 }
1999 inst = inst.next
2000 }
2001 bi = bi + 1
2002 }
2003
2004 // Pass 2: rewrite each operand through the chain.
2005 var changed: i64 = 0
2006 bi = 0
2007 while bi < f.n_blocks {
2008 let bb: *BasicBlock = block_at(f, bi)
2009 var inst: *Instr = bb.head
2010 while inst != (0 as *Instr) {
2011 if inst.op != OP_BR {
2012 // OP_BR's op0 is a block id, not a value -- skip.
2013 // For OP_BR_COND, only op0 (condition) is a value;
2014 // op1/op2 are block ids.
2015 let n_val_ops: i64 = if_br_cond_then_1_else_n(inst)
2016 var j: i64 = 0
2017 while j < n_val_ops {
2018 var cur: i64 = read_op(inst, j)
2019 var steps: i64 = 0
2020 var go: i64 = 1
2021 while go == 1 {
2022 if steps >= 32 { go = 0 }
2023 else {
2024 if cur >= f.n_values { go = 0 }
2025 else {
2026 if multi[cur] == 1 { go = 0 }
2027 else {
2028 if copy_src[cur] < 0 { go = 0 }
2029 else {
2030 cur = copy_src[cur]
2031 steps = steps + 1
2032 }
2033 }
2034 }
2035 }
2036 }
2037 if cur != read_op(inst, j) {
2038 write_op(inst, j, cur)
2039 changed = 1
2040 }
2041 j = j + 1
2042 }
2043 }
2044 inst = inst.next
2045 }
2046 bi = bi + 1
2047 }
2048 return changed
2049}
2050
2051// Helpers: BR_COND has 1 value-op (condition) + 2 block-id ops;
2052// everything else uses n_operands value-ops.
2053func if_br_cond_then_1_else_n(inst: *Instr) -> i64 {
2054 if inst.op == OP_BR_COND { return 1 }
2055 return inst.n_operands
2056}
2057
2058// Cover op0..op15. Prior versions handled only op0..op3, which
2059// silently truncated rewrites on OP_SYSCALL (7 operands) and on
2060// the OP_CALL family extended to op0..op15 in the off-C arc
2061// (2026-05-20, Instr stride 128 -> 192). Bug-class fix per
2062// [[project-call-arity-silent-dropping-fix-2026-05-20]] sibling --
2063// the OPT-pass side of the same arity-extension surface.
2064func read_op(inst: *Instr, idx: i64) -> i64 {
2065 if idx == 0 { return inst.op0 }
2066 if idx == 1 { return inst.op1 }
2067 if idx == 2 { return inst.op2 }
2068 if idx == 3 { return inst.op3 }
2069 if idx == 4 { return inst.op4 }
2070 if idx == 5 { return inst.op5 }
2071 if idx == 6 { return inst.op6 }
2072 if idx == 7 { return inst.op7 }
2073 if idx == 8 { return inst.op8 }
2074 if idx == 9 { return inst.op9 }
2075 if idx == 10 { return inst.op10 }
2076 if idx == 11 { return inst.op11 }
2077 if idx == 12 { return inst.op12 }
2078 if idx == 13 { return inst.op13 }
2079 if idx == 14 { return inst.op14 }
2080 if idx == 15 { return inst.op15 }
2081 if idx == 16 { return inst.op16 }
2082 if idx == 17 { return inst.op17 }
2083 if idx == 18 { return inst.op18 }
2084 if idx == 19 { return inst.op19 }
2085 if idx == 20 { return inst.op20 }
2086 if idx == 21 { return inst.op21 }
2087 if idx == 22 { return inst.op22 }
2088 return inst.op23
2089}
2090
2091func write_op(inst: *Instr, idx: i64, v: i64) -> i64 {
2092 if idx == 0 { inst.op0 = v; return 0 }
2093 if idx == 1 { inst.op1 = v; return 0 }
2094 if idx == 2 { inst.op2 = v; return 0 }
2095 if idx == 3 { inst.op3 = v; return 0 }
2096 if idx == 4 { inst.op4 = v; return 0 }
2097 if idx == 5 { inst.op5 = v; return 0 }
2098 if idx == 6 { inst.op6 = v; return 0 }
2099 if idx == 7 { inst.op7 = v; return 0 }
2100 if idx == 8 { inst.op8 = v; return 0 }
2101 if idx == 9 { inst.op9 = v; return 0 }
2102 if idx == 10 { inst.op10 = v; return 0 }
2103 if idx == 11 { inst.op11 = v; return 0 }
2104 if idx == 12 { inst.op12 = v; return 0 }
2105 if idx == 13 { inst.op13 = v; return 0 }
2106 if idx == 14 { inst.op14 = v; return 0 }
2107 if idx == 15 { inst.op15 = v; return 0 }
2108 if idx == 16 { inst.op16 = v; return 0 }
2109 if idx == 17 { inst.op17 = v; return 0 }
2110 if idx == 18 { inst.op18 = v; return 0 }
2111 if idx == 19 { inst.op19 = v; return 0 }
2112 if idx == 20 { inst.op20 = v; return 0 }
2113 if idx == 21 { inst.op21 = v; return 0 }
2114 if idx == 22 { inst.op22 = v; return 0 }
2115 if idx == 23 { inst.op23 = v; return 0 }
2116 return 0
2117}
2118
2119// opt_cse: port of opt.c's per-block Common Subexpression
2120// Elimination. Within each block, maintain a table of
2121// (op, operand_a, operand_b) -> result_value_id. When a
2122// subsequent pure binop matches a table entry, rewrite the new
2123// instruction to OP_COPY of the earlier result.
2124//
2125// Scope: per-block only. Cross-block CSE is GVN's job
2126// (opt_gvn_block handles same-block; a future opt_gvn_module
2127// would do cross-block).
2128//
2129// Commutativity: for +/*/& /| /^ /== /!=, checks swapped-operand
2130// form too so `a + b` matches `b + a` in the table.
2131//
2132// Three invariants:
2133// CSE1 Only pure binops (is_const_foldable_binop / _cmp) go
2134// into the table; calls / loads / stores have memory
2135// effects and can't be dedup'd.
2136// CSE2 Table is per-block; cross-block reuse relies on
2137// dominator info we don't have in opt.nx yet.
2138// CSE3 Bounded table (256 entries); overflow stops adding new
2139// entries -- correctness preserved, but redundant
2140// computations leak through downstream.
2141// STUB(opt, T#opt-001): cap of 256 was chosen for the first port
2142// pass. Real-world basic blocks in nxc.nx self-compile likely
2143// exceed this on functions like parse_stmt; we silently degrade.
2144// Plan: bounds-check + diagnostic when full + hit-counter so we
2145// can size correctly, OR replace with a grow path.
2146// Closes when: any per-block CSE candidate count exceeds 256.
2147
2148const CSE_TABLE_CAP: i64 = 256
2149
2150// Is `op` a pure binop CSE can dedup? Mirrors
2151// is_const_foldable_binop + is_const_foldable_cmp in opt.c.
2152func cse_is_candidate(op: i64) -> i64 {
2153 if op == OP_ADD { return 1 }
2154 if op == OP_SUB { return 1 }
2155 if op == OP_MUL { return 1 }
2156 if op == OP_DIV_S { return 1 }
2157 if op == OP_DIV_U { return 1 }
2158 if op == OP_REM_S { return 1 }
2159 if op == OP_REM_U { return 1 }
2160 if op == OP_AND { return 1 }
2161 if op == OP_OR { return 1 }
2162 if op == OP_XOR { return 1 }
2163 if op == OP_SHL { return 1 }
2164 if op == OP_SHR_S { return 1 }
2165 if op == OP_SHR_U { return 1 }
2166 if op == OP_EQ { return 1 }
2167 if op == OP_NE { return 1 }
2168 if op == OP_LT_S { return 1 }
2169 if op == OP_LE_S { return 1 }
2170 if op == OP_GT_S { return 1 }
2171 if op == OP_GE_S { return 1 }
2172 return 0
2173}
2174
2175// Commutative ops where (a, b) in table should also match (b, a)
2176// for a query.
2177func cse_is_commutative(op: i64) -> i64 {
2178 if op == OP_ADD { return 1 }
2179 if op == OP_MUL { return 1 }
2180 if op == OP_AND { return 1 }
2181 if op == OP_OR { return 1 }
2182 if op == OP_XOR { return 1 }
2183 if op == OP_EQ { return 1 }
2184 if op == OP_NE { return 1 }
2185 return 0
2186}
2187
2188func opt_cse(f: *Function) -> i64 {
2189 var changed: i64 = 0
2190 // Per-block table: (op, a, b, result_vid) quadruples.
2191 let tab_raw: *u8 = sys_mmap(CSE_TABLE_CAP * 32 + 64)
2192 let tab: *i64 = tab_raw as *i64 // stride 4 i64 slots per entry
2193
2194 var bi: i64 = 0
2195 while bi < f.n_blocks {
2196 let bb: *BasicBlock = block_at(f, bi)
2197 var n_entries: i64 = 0
2198 var inst: *Instr = bb.head
2199 while inst != (0 as *Instr) {
2200 if inst.op != OP_COPY {
2201 if inst.n_operands == 2 {
2202 if cse_is_candidate(inst.op) == 1 {
2203 let op: i64 = inst.op
2204 let a: i64 = inst.op0
2205 let b: i64 = inst.op1
2206 // Linear-probe the table.
2207 var hit: i64 = -1
2208 var k: i64 = 0
2209 while k < n_entries {
2210 let e_op: i64 = tab[k * 4 + 0]
2211 let e_a: i64 = tab[k * 4 + 1]
2212 let e_b: i64 = tab[k * 4 + 2]
2213 if e_op == op {
2214 if e_a == a {
2215 if e_b == b { hit = k; k = n_entries }
2216 }
2217 }
2218 k = k + 1
2219 }
2220 // Commuted match for commutative ops.
2221 if hit < 0 {
2222 if cse_is_commutative(op) == 1 {
2223 k = 0
2224 while k < n_entries {
2225 let e_op: i64 = tab[k * 4 + 0]
2226 let e_a: i64 = tab[k * 4 + 1]
2227 let e_b: i64 = tab[k * 4 + 2]
2228 if e_op == op {
2229 if e_a == b {
2230 if e_b == a { hit = k; k = n_entries }
2231 }
2232 }
2233 k = k + 1
2234 }
2235 }
2236 }
2237 if hit >= 0 {
2238 // Rewrite current instr to OP_COPY of the
2239 // earlier result.
2240 let src: i64 = tab[hit * 4 + 3]
2241 inst.op = OP_COPY
2242 inst.op0 = src
2243 inst.op1 = 0
2244 inst.n_operands = 1
2245 changed = 1
2246 } else {
2247 // Add to table if room.
2248 if n_entries < CSE_TABLE_CAP {
2249 tab[n_entries * 4 + 0] = op
2250 tab[n_entries * 4 + 1] = a
2251 tab[n_entries * 4 + 2] = b
2252 tab[n_entries * 4 + 3] = inst.result
2253 n_entries = n_entries + 1
2254 }
2255 }
2256 }
2257 }
2258 }
2259 inst = inst.next
2260 }
2261 bi = bi + 1
2262 }
2263 return changed
2264}
2265
2266// opt_thread_jumps: port of opt.c's bridge-collapsing pass.
2267//
2268// After SCCP + DCE + mem2reg we end up with long chains of
2269// single-instruction BR blocks (bridges): entry -> bridge1 ->
2270// bridge2 -> tail. Each hop is a wasted jump at runtime.
2271// Collapse them: for every BR / BR_COND target T, if T is a
2272// bridge, point the edge at T's successor directly.
2273//
2274// A bridge = block with single-instruction OP_BR body (head ==
2275// tail, op == OP_BR, not the entry block).
2276//
2277// Chain length capped at 64 to avoid pathological loops of
2278// bridges that all point at each other.
2279//
2280// After collapsing, the pred/succ lists for all blocks need to
2281// be rebuilt (dominator analysis + sweep rely on accurate CFG).
2282// In opt.nx's inline-slot scheme, "rebuild" means clear pred0..2
2283// + succ0..1 on every block, then re-populate from terminator
2284// analysis.
2285
2286// Chase bridges from `b`; returns the final non-bridge block, or
2287// `b` itself if it isn't a bridge. `hops_left` caps iteration.
2288func skip_bridges(f: *Function, b: *BasicBlock, hops_left: i64) -> *BasicBlock {
2289 var cur: *BasicBlock = b
2290 var hops: i64 = hops_left
2291 while hops > 0 {
2292 if cur == f.entry { return cur }
2293 if cur.head == (0 as *Instr) { return cur }
2294 if cur.head != cur.tail { return cur }
2295 if cur.head.op != OP_BR { return cur }
2296 let next_id: i64 = cur.head.op0
2297 if next_id >= f.n_blocks { return cur }
2298 let nxt: *BasicBlock = block_at(f, next_id)
2299 if nxt == cur { return cur }
2300 cur = nxt
2301 hops = hops - 1
2302 }
2303 return cur
2304}
2305
2306// Append a pred/succ slot (inline 3-pred / 2-succ scheme).
2307// Returns 0 on success, -1 if slots exhausted.
2308func add_succ(bb: *BasicBlock, t: *BasicBlock) -> i64 {
2309 if bb.succ0 == (0 as *BasicBlock) { bb.succ0 = t; bb.n_succs = bb.n_succs + 1; return 0 }
2310 if bb.succ1 == (0 as *BasicBlock) { bb.succ1 = t; bb.n_succs = bb.n_succs + 1; return 0 }
2311 return -1
2312}
2313
2314func add_pred(bb: *BasicBlock, p: *BasicBlock) -> i64 {
2315 if bb.pred0 == (0 as *BasicBlock) { bb.pred0 = p; bb.n_preds = bb.n_preds + 1; return 0 }
2316 if bb.pred1 == (0 as *BasicBlock) { bb.pred1 = p; bb.n_preds = bb.n_preds + 1; return 0 }
2317 if bb.pred2 == (0 as *BasicBlock) { bb.pred2 = p; bb.n_preds = bb.n_preds + 1; return 0 }
2318 return -1
2319}
2320
2321func opt_thread_jumps(f: *Function) -> i64 {
2322 var changed: i64 = 0
2323 var bi: i64 = 0
2324 while bi < f.n_blocks {
2325 let bb: *BasicBlock = block_at(f, bi)
2326 let term: *Instr = bb.tail
2327 if term != (0 as *Instr) {
2328 if term.op == OP_BR {
2329 let t_id: i64 = term.op0
2330 if t_id < f.n_blocks {
2331 let t: *BasicBlock = block_at(f, t_id)
2332 let r: *BasicBlock = skip_bridges(f, t, 64)
2333 if r != t {
2334 term.op0 = r.id
2335 changed = 1
2336 }
2337 }
2338 }
2339 if term.op == OP_BR_COND {
2340 let t1_id: i64 = term.op1
2341 let t2_id: i64 = term.op2
2342 if t1_id < f.n_blocks {
2343 let t1: *BasicBlock = block_at(f, t1_id)
2344 let r1: *BasicBlock = skip_bridges(f, t1, 64)
2345 if r1 != t1 {
2346 term.op1 = r1.id
2347 changed = 1
2348 }
2349 }
2350 if t2_id < f.n_blocks {
2351 let t2: *BasicBlock = block_at(f, t2_id)
2352 let r2: *BasicBlock = skip_bridges(f, t2, 64)
2353 if r2 != t2 {
2354 term.op2 = r2.id
2355 changed = 1
2356 }
2357 }
2358 }
2359 }
2360 bi = bi + 1
2361 }
2362
2363 if changed == 0 { return 0 }
2364
2365 // Rebuild CFG. Clear all pred/succ slots, then re-add from
2366 // every block's terminator.
2367 bi = 0
2368 while bi < f.n_blocks {
2369 let bb: *BasicBlock = block_at(f, bi)
2370 bb.pred0 = 0 as *BasicBlock
2371 bb.pred1 = 0 as *BasicBlock
2372 bb.pred2 = 0 as *BasicBlock
2373 bb.succ0 = 0 as *BasicBlock
2374 bb.succ1 = 0 as *BasicBlock
2375 bb.n_preds = 0
2376 bb.n_succs = 0
2377 bi = bi + 1
2378 }
2379
2380 bi = 0
2381 while bi < f.n_blocks {
2382 let bb: *BasicBlock = block_at(f, bi)
2383 let term: *Instr = bb.tail
2384 if term != (0 as *Instr) {
2385 if term.op == OP_BR {
2386 let t_id: i64 = term.op0
2387 if t_id < f.n_blocks {
2388 let t: *BasicBlock = block_at(f, t_id)
2389 add_succ(bb, t)
2390 add_pred(t, bb)
2391 }
2392 }
2393 if term.op == OP_BR_COND {
2394 let t1_id: i64 = term.op1
2395 let t2_id: i64 = term.op2
2396 if t1_id < f.n_blocks {
2397 let t1: *BasicBlock = block_at(f, t1_id)
2398 add_succ(bb, t1)
2399 add_pred(t1, bb)
2400 }
2401 if t2_id < f.n_blocks {
2402 let t2: *BasicBlock = block_at(f, t2_id)
2403 add_succ(bb, t2)
2404 add_pred(t2, bb)
2405 }
2406 }
2407 }
2408 bi = bi + 1
2409 }
2410 return 1
2411}
2412
2413// Forward declarations for LICM helpers.
2414func licm_is_hoistable(op: i64) -> i64;
2415// ARITY FIX 2026-07-20: this forward declaration was STALE -- it still described the pre-dominance
2416// 3-parameter signature while the real definition (:2900) and the only call site (:2728) had long
2417// since moved to 5 params (`info`, `header` were added by the LICM dominance rewrite). Nothing
2418// caught it because nx_cc had no call-arity checking; the new check flagged it on its first
2419// full-coverage run. Exactly the "a signature changed and something silently didn't follow" class.
2420func operands_are_loop_invariant(f: *Function, inst: *Instr,
2421 in_loop: *u8, info: *DomInfoFn,
2422 header: *BasicBlock) -> i64;
2423func hoist_instr(inst: *Instr, preheader: *BasicBlock) -> i64;
2424func mark_loop_body_nx(f: *Function, header: *BasicBlock,
2425 from: *BasicBlock, in_loop: *u8) -> i64;
2426
2427// opt_licm: port of opt.c's LICM pass, now using dom_fn.nx for
2428// dominance info instead of opt.c's DomInfo. Hoists computations
2429// whose operands don't change across loop iterations out to the
2430// loop's preheader. Classical optimization (Allen-Cocke 1971).
2431//
2432// Algorithm:
2433// 1. Compute dom info via dom_compute_fn.
2434// 2. Find back-edges: any edge b -> s where s dominates b.
2435// s is the loop header; b is the back-edge source.
2436// 3. Find preheader: if s has exactly one forward predecessor p
2437// whose only successor is s, p is the preheader. Otherwise
2438// skip the loop (no edge-splitting in this pass).
2439// 4. Mark loop body: walk back from b through preds, stopping at
2440// s. Mark reached blocks in the in_loop bitmap.
2441// 5. Fixpoint-hoist: for each instr in the loop, if operands are
2442// all loop-invariant AND opcode is pure+non-trapping, move to
2443// preheader. Repeat until no more hoists.
2444//
2445// Invariants (LI1-LI5):
2446// LI1 Only hoist opcodes that are pure AND cannot fault.
2447// Excludes DIV/REM (trap on zero), LOAD/STORE (memory
2448// effects), CALL (unknown effects), PHI (control-dependent),
2449// ALLOCA (stack-position-dependent).
2450// LI2 Operand definitions must dominate the preheader after
2451// hoisting. Trivially true since operand sources are
2452// outside the loop or hoisted earlier in this pass.
2453// LI3 Hoisted instructions preserve SSA: each value has
2454// exactly one def; moving the def earlier keeps that.
2455// LI4 Iteration order follows f.blocks[] array order
2456// (deterministic, F6-compliant).
2457// LI5 No block-storage mutation outside pred/succ slots. No
2458// freeing; pruned instr slots remain allocated.
2459
2460// Safety bound on LICM block count. With the single-pass RPO hoist
2461// (see opt_licm body) LICM is near-linear, so this is a generous
2462// backstop against pathological CFGs, not the old perf crutch (the
2463// fixpoint-rescan era needed 64 to keep the 707KB sites daemon under
2464// 10s; the single-pass fix is the real cure). Tunable -- belongs in
2465// svc-config eventually (Rule #11).
2466const LICM_MAX_BLOCKS: i64 = 4096
2467
2468// ===== CFG edge rebuild from TERMINATORS (2026-07-15) ================
2469// The dominance brute-force oracle (nx_dom_oracle_gate, the banked 06-10
2470// awakening rung) MEASURED: dom_fn is exact on post-parse CFGs (553,761
2471// pairs, 0 mismatches) but WRONG on post-opt CFGs (5,697 mismatches incl
2472// FALSE dominance claims -- the unsound-hoist source behind the 06-10
2473// awakening SIGSEGVs). Root: opt passes leave succ/pred pointers STALE
2474// (T#opt-002, "SWEEP3 leaves succ pointers stale"). The TERMINATORS
2475// (OP_BR op0 / OP_BR_COND op1,op2 -- block IDS) are the ground truth the
2476// EMITTER compiles, so edges rebuilt from them match the generated code
2477// BY CONSTRUCTION. Called at the top of opt_licm so dominance + loop
2478// bodies are computed on the real graph. Returns 0 ok; 1 = REFUSE (a
2479// reachable block has no recognized terminator -- possible fallthrough
2480// edge the rebuild cannot see; LICM declines the function, never guesses).
2481
2482func cfg_block_by_id(f: *Function, id: i64) -> *BasicBlock {
2483 var i: i64 = 0
2484 while i < f.n_blocks {
2485 let b: *BasicBlock = block_at(f, i)
2486 if b.id == id { return b }
2487 i = i + 1
2488 }
2489 return 0 as *BasicBlock
2490}
2491
2492func cfg_add_pred(b: *BasicBlock, p: *BasicBlock) -> i64 {
2493 if b.n_preds == 0 { b.pred0 = p }
2494 if b.n_preds == 1 { b.pred1 = p }
2495 if b.n_preds == 2 { b.pred2 = p }
2496 b.n_preds = b.n_preds + 1
2497 return 0
2498}
2499
2500func cfg_rebuild_edges(f: *Function) -> i64 {
2501 var i: i64 = 0
2502 while i < f.n_blocks {
2503 let b: *BasicBlock = block_at(f, i)
2504 b.n_preds = 0
2505 b.n_succs = 0
2506 b.pred0 = 0 as *BasicBlock
2507 b.pred1 = 0 as *BasicBlock
2508 b.pred2 = 0 as *BasicBlock
2509 b.succ0 = 0 as *BasicBlock
2510 b.succ1 = 0 as *BasicBlock
2511 i = i + 1
2512 }
2513 var refuse: i64 = 0
2514 i = 0
2515 while i < f.n_blocks {
2516 let b2: *BasicBlock = block_at(f, i)
2517 let t: *Instr = b2.tail
2518 if t == (0 as *Instr) { refuse = 1 }
2519 if t != (0 as *Instr) {
2520 var ok: i64 = 0
2521 if t.op == OP_RETURN { ok = 1 }
2522 if t.op == OP_TAIL_CALL { ok = 1 }
2523 if t.op == OP_BR {
2524 let s: *BasicBlock = cfg_block_by_id(f, t.op0)
2525 if s == (0 as *BasicBlock) { refuse = 1 }
2526 if s != (0 as *BasicBlock) {
2527 b2.succ0 = s
2528 b2.n_succs = 1
2529 cfg_add_pred(s, b2)
2530 ok = 1
2531 }
2532 }
2533 if t.op == OP_BR_COND {
2534 let st: *BasicBlock = cfg_block_by_id(f, t.op1)
2535 let sf: *BasicBlock = cfg_block_by_id(f, t.op2)
2536 if st == (0 as *BasicBlock) { refuse = 1 }
2537 if sf == (0 as *BasicBlock) { refuse = 1 }
2538 if st != (0 as *BasicBlock) { if sf != (0 as *BasicBlock) {
2539 b2.succ0 = st
2540 b2.succ1 = sf
2541 b2.n_succs = 2
2542 cfg_add_pred(st, b2)
2543 if sf != st { cfg_add_pred(sf, b2) }
2544 ok = 1
2545 } }
2546 }
2547 if ok == 0 { refuse = 1 }
2548 }
2549 i = i + 1
2550 }
2551 return refuse
2552}
2553
2554// Rebuild every instruction's .parent from GROUND-TRUTH block membership.
2555// ROOT CAUSE (2026-07-15, T#opt-003): opt_block_merge splices block B's instr
2556// list into block A but NEVER updates the moved instrs' .parent -- they keep
2557// pointing at B, which is then emptied + marked unreachable. LICM's
2558// dominance-based invariance then reads such an operand's def-block (= the
2559// stale, unreachable B), finds the header does NOT dominate B, and deems the
2560// operand loop-INVARIANT -- but the instr actually lives in loop-block A and is
2561// VARIANT. Result: a loop-carried value is hoisted -> the loop freezes ->
2562// ed25519 sign hangs. Same class as the stale succ/pred edges (T#opt-002); same
2563// fix: recompute the derived pointer from the block that actually contains the
2564// instruction, so the dominance check is sound. Robust to ANY pass that moves
2565// instrs without maintaining .parent, not just block_merge.
2566func cfg_rebuild_parents(f: *Function) -> i64 {
2567 var i: i64 = 0
2568 while i < f.n_blocks {
2569 let b: *BasicBlock = block_at(f, i)
2570 var inst: *Instr = b.head
2571 while inst != (0 as *Instr) {
2572 inst.parent = b
2573 inst = inst.next
2574 }
2575 i = i + 1
2576 }
2577 return 0
2578}
2579
2580// GATE (2026-07-15): the RPO hoist is AWAKENED behind an oracle-proven dominance
2581// fix (cfg_rebuild_edges), but sha512 exposed a SECOND soundness bug beyond
2582// dominance -- a loop-terminating instr is hoisted -> infinite loop (correct
2583// early vectors, then hang; the 06-10 symptom). Dominance is now PROVEN correct
2584// (nx_dom_oracle_gate GREEN, 683,696 pairs) so the residual is in loop-body
2585// marking (mark_loop_body_nx) or hoist safety, NOT the dominator -- its own
2586// focused arc needing a HOIST-LEVEL differential oracle. Gated OFF (=0) keeps the
2587// compiler byte-safe (LICM stays the effective no-op it was for a year) while the
2588// infra (cfg_rebuild_edges, the oracle, the G9 scalar-alloca-load-hoist) lives in
2589// the tree for that session. Flip to 1 to resume; the matmul i*N hoist rides on it.
2590const LICM_HOIST_LIVE: i64 = 1
2591// BISECT-2026-07-15: isolate the ed25519 test-2 hang. 0 = arithmetic/compare
2592// hoisting only (no G9 scalar-alloca LOAD hoist). If ed25519 stops hanging with
2593// this at 0, the second bug is in G9's load-hoist safety, not the general path.
2594const LICM_G9_LOAD_HOIST: i64 = 1
2595// 2026-07-15: full dominance-based invariance is sound now that inst.parent is
2596// rebuilt (T#opt-003). This flag stays as a fast bisect lever (1 = provably-safe
2597// loop-constant-input hoists only) but defaults OFF -- the real fix is upstream.
2598const LICM_CONSERVATIVE: i64 = 0
2599// NEGATIVE CONTROL (2026-07-15): flip to 1 to skip cfg_rebuild_parents and
2600// reintroduce the stale-.parent miscompile (T#opt-003) -- the gauntlet MUST go
2601// RED (ed25519 HANG caught by the KAT timeout). Proves the gate has teeth.
2602// Ships at 0.
2603const NEGCTL_SKIP_PARENT_REBUILD: i64 = 0
2604
2605// ===== LN7: SOUND BOUNDS-CHECK ELISION =============================
2606//
2607// The prologue below is opt_licm's, deliberately and line for line. Both passes consume the
2608// SAME dominator tree, so they owe the SAME preconditions -- and a second, separately worded
2609// copy of those preconditions is exactly how one of the two silently becomes the weaker one.
2610// The difference in CONSEQUENCE is worth stating once: when LICM declines a function it misses
2611// a hoist, and when this pass declines one it keeps a bounds check. Both are the safe
2612// direction; only one of them is a memory-safety property, which is why this pass inherits
2613// LICM's refusals rather than re-deriving its own.
2614//
2615// The decision procedure itself lives in nx_bck_elide.nx and takes the dominator tree as a
2616// parameter, so it is exercisable without a compiler wrapped around it. The 128-byte handle
2617// is the same allocation opt_licm makes for the same DomInfoFn struct.
2618func opt_bounds_check_elim(f: *Function) -> i64 {
2619 if bck_elide_live() != 1 { return 0 }
2620 if f.n_blocks < 2 { return 0 }
2621 if f.n_blocks > LICM_MAX_BLOCKS { return 0 }
2622 if cfg_rebuild_edges(f) != 0 { return 0 }
2623 if NEGCTL_SKIP_PARENT_REBUILD == 0 { cfg_rebuild_parents(f) }
2624 let info_raw: *u8 = sys_mmap(128)
2625 let info: *DomInfoFn = info_raw as *DomInfoFn
2626 dom_compute_fn(f, info)
2627 let n: i64 = bck_elide_dominated(f, info, bck_exitgrp())
2628 // LN7b (2026-09-01): the induction-guarded case the dominance pass cannot see -- a loop
2629 // guard `k < N` proving the single check inside the loop. Same dominator tree: an elision
2630 // only removes edges, so the tree computed above stays conservative for this pass too.
2631 let n2: i64 = bck_elide_induction(f, info, bck_exitgrp())
2632 // An elision removes the two edges into the trap block, so the passes that run after this
2633 // one in the SAME round must see the CFG that now exists rather than the one that did.
2634 if n + n2 > 0 { cfg_rebuild_edges(f) }
2635 return n + n2
2636}
2637
2638func opt_licm(f: *Function) -> i64 {
2639 if LICM_HOIST_LIVE == 0 { return 0 }
2640 if f.n_blocks < 2 { return 0 }
2641 if f.n_blocks > LICM_MAX_BLOCKS { return 0 }
2642
2643 // 2026-07-15: recompute succ/pred from the terminators (see above).
2644 // A function the rebuild cannot fully resolve is DECLINED, not guessed.
2645 if cfg_rebuild_edges(f) != 0 { return 0 }
2646 // 2026-07-15 (T#opt-003): recompute inst.parent from block membership --
2647 // opt_block_merge leaves it stale, which corrupts dominance-invariance.
2648 if NEGCTL_SKIP_PARENT_REBUILD == 0 { cfg_rebuild_parents(f) }
2649
2650 // SOUNDNESS GUARD (2026-06-10, T#ir-pred-list-truncation): blocks
2651 // store only pred0..pred2; a 4th+ predecessor edge increments
2652 // n_preds but is DROPPED (nx_ir.nx add-pred sites). On such a
2653 // CFG both dominator computation and mark_loop_body_nx walk an
2654 // INCOMPLETE edge set, so "operand defined outside the loop" can
2655 // be a lie -> unsound hoist. Found by nx_cc_equiv_gate when the
2656 // dormant RPO hoist walk was awakened: every corpus row passed
2657 // but the self-host stage broke -- merge-heavy compiler functions
2658 // are exactly where preds exceed 3. Until the pred list is
2659 // widened (named follow-up), LICM declines functions whose CFG
2660 // info is truncated; small/medium fns (incl. hot crypto loops)
2661 // keep full hoisting.
2662 var tb: i64 = 0
2663 while tb < f.n_blocks {
2664 let tbb: *BasicBlock = block_at(f, tb)
2665 if tbb.n_preds > 3 { return 0 }
2666 tb = tb + 1
2667 }
2668
2669 // Compute dom info.
2670 let info_raw: *u8 = sys_mmap(128)
2671 let info: *DomInfoFn = info_raw as *DomInfoFn
2672 dom_compute_fn(f, info)
2673
2674 // MEMOISED PREDICATES (2026-08-18). licm_load_hoistable used to answer "does this alloca
2675 // escape?" and "is it stored below the header?" by RESCANNING THE WHOLE FUNCTION for every
2676 // load in every loop block, of every header, of every opt round -- O(loads x instrs) per
2677 // header, and it was 85% of opt time on big-main organs (324 ms of a 472 ms build, per-pass
2678 // profile). Both answers are invariant for the span they are used over: the escape set never
2679 // changes inside one opt_licm call (hoisting MOVES instructions, it adds no operand and no
2680 // instruction), and the store-below-header set never changes inside one header's walk (stores
2681 // are not hoistable, so hoisting moves only pure ops and loads). So each is computed ONCE for
2682 // its span from the SAME rules, and every query reads the map. Output IR is identical by
2683 // construction; the byte-identical .s over the whole population is the proof, not this note.
2684 let esc_raw: *u8 = sys_mmap(f.n_values + 16)
2685 let esc: *u8 = esc_raw
2686 licm_build_escape_map(f, esc)
2687 let stdom_raw: *u8 = sys_mmap(f.n_values + 16)
2688 let stdom: *u8 = stdom_raw
2689
2690 var any_hoisted: i64 = 0
2691 let in_loop_raw: *u8 = sys_mmap(f.n_blocks + 16)
2692 let in_loop: *u8 = in_loop_raw
2693
2694 // C2 PERF FIX (2026-06-09): process each loop HEADER once, not once
2695 // per back-edge. The old code re-marked the loop body and re-ran the
2696 // full-block fixpoint hoist for EVERY back-edge into the same header.
2697 // On many-back-edge state machines (the HTTP parser / HTML routers in
2698 // the 707KB sites daemon) that is O(back_edges * blocks * instrs) per
2699 // header and made the daemon take >2 min in LICM alone (the rest of
2700 // the compile is ~1.8s). Each header now processed once over its FULL
2701 // natural-loop body (union over all its back-edges); the union also
2702 // fixes a latent bug where partial per-back-edge bodies let an operand
2703 // defined in an unmarked loop block look invariant (unsound hoist).
2704 // Pass 1: collect ALL back-edges ONCE (b -> s is a back-edge iff s
2705 // dominates b). O(B * dom_dominates); with df_block_index O(1) that
2706 // is ~O(B^2), paid ONCE -- not re-scanned per header (the per-header
2707 // rescan was the O(H*B^2)/O(H*B^3) blowup that kept the daemon >2min).
2708 let be_cap: i64 = f.n_blocks * 2 + 4
2709 let be_tail_raw: *u8 = sys_mmap(be_cap * 8 + 16)
2710 let be_tail: *i64 = be_tail_raw as *i64
2711 let be_head_raw: *u8 = sys_mmap(be_cap * 8 + 16)
2712 let be_head: *i64 = be_head_raw as *i64
2713 var n_be: i64 = 0
2714 var bi: i64 = 0
2715 while bi < f.n_blocks {
2716 let b: *BasicBlock = block_at(f, bi)
2717 let s0: *BasicBlock = b.succ0
2718 if s0 != (0 as *BasicBlock) {
2719 if dom_dominates(info, s0, b) == 1 {
2720 if n_be < be_cap {
2721 be_tail[n_be] = bi
2722 be_head[n_be] = df_block_index(f, s0)
2723 n_be = n_be + 1
2724 }
2725 }
2726 }
2727 let s1: *BasicBlock = b.succ1
2728 if s1 != (0 as *BasicBlock) {
2729 if dom_dominates(info, s1, b) == 1 {
2730 if n_be < be_cap {
2731 be_tail[n_be] = bi
2732 be_head[n_be] = df_block_index(f, s1)
2733 n_be = n_be + 1
2734 }
2735 }
2736 }
2737 bi = bi + 1
2738 }
2739
2740 // Pass 2: process each loop header ONCE, over the union of its
2741 // back-edges' natural-loop bodies, then hoist once.
2742 let header_done_raw: *u8 = sys_mmap(f.n_blocks + 16)
2743 let header_done: *u8 = header_done_raw
2744 var hd_i: i64 = 0
2745 while hd_i < f.n_blocks { header_done[hd_i] = 0; hd_i = hd_i + 1 }
2746
2747 var k: i64 = 0
2748 while k < n_be {
2749 let hidx: i64 = be_head[k]
2750 var do_header: i64 = 0
2751 if hidx >= 0 {
2752 if hidx < f.n_blocks {
2753 if header_done[hidx] == 0 {
2754 header_done[hidx] = 1
2755 do_header = 1
2756 }
2757 }
2758 }
2759 if do_header == 1 {
2760 let s: *BasicBlock = block_at(f, hidx)
2761 // Union loop body from EVERY back-edge into s (bucketed by
2762 // header in the collected list -- no dom_dominates here).
2763 var j: i64 = 0
2764 while j < f.n_blocks { in_loop[j] = 0; j = j + 1 }
2765 var m: i64 = 0
2766 while m < n_be {
2767 if be_head[m] == hidx {
2768 mark_loop_body_nx(f, s, block_at(f, be_tail[m]), in_loop)
2769 }
2770 m = m + 1
2771 }
2772
2773 // Find preheader: pred of s NOT in loop, with s as only succ.
2774 let preds_raw: *u8 = sys_mmap(32)
2775 let preds: *i64 = preds_raw as *i64
2776 preds[0] = s.pred0 as i64
2777 preds[1] = s.pred1 as i64
2778 preds[2] = s.pred2 as i64
2779 var preheader: *BasicBlock = 0 as *BasicBlock
2780 var pi: i64 = 0
2781 var multiple: i64 = 0
2782 while pi < 3 {
2783 let p: *BasicBlock = preds[pi] as *BasicBlock
2784 if p != (0 as *BasicBlock) {
2785 let p_idx: i64 = df_block_index(f, p)
2786 if p_idx >= 0 {
2787 if in_loop[p_idx] == 0 {
2788 if preheader != (0 as *BasicBlock) {
2789 multiple = 1
2790 }
2791 preheader = p
2792 }
2793 }
2794 }
2795 pi = pi + 1
2796 }
2797 if multiple == 0 {
2798 if preheader != (0 as *BasicBlock) {
2799 // Verify preheader has s as only successor.
2800 if preheader.n_succs == 1 {
2801 if preheader.succ0 == s {
2802 licm_build_store_dom_map(f, info, s, stdom)
2803 // C2 PERF FIX (2026-06-09): SINGLE-pass hoist
2804 // in RPO order, replacing the `while
2805 // changed_inner` full-rescan fixpoint (the
2806 // measured O(hoists x blocks x instrs) blowup
2807 // -- phase markers showed every big fn stall
2808 // here, not in dom/back-edge scan). Defs
2809 // dominate uses in this SSA-form IR, so
2810 // visiting blocks in RPO + instrs in order
2811 // resolves transitive invariance chains in
2812 // ONE pass: a hoisted def's parent becomes
2813 // the preheader (not in_loop) before its
2814 // users are examined. Any case this order
2815 // misses is only a missed optional hoist,
2816 // never a miscompile. dom_compute_fn already
2817 // built info.rpo -- reuse it.
2818 let rpo_base: i64 = info.rpo as i64
2819 var ri: i64 = 0
2820 while ri < info.rpo_n {
2821 let rslot: *i64 = (rpo_base + ri * 8) as *i64
2822 // AWAKENED 2026-07-15. History: re-pinned
2823 // dormant 2026-06-10 when awakening broke
2824 // selfhost (4 SIGSEGV victim fns; suspicion =
2825 // the dominator fixpoint). The banked rung --
2826 // "dominance brute-force oracle FIRST" -- ran
2827 // as nx_dom_oracle_gate: dom_fn EXACT on
2828 // post-parse CFGs (553,761 pairs, 0 mismatch)
2829 // but 5,697 mismatches on post-opt CFGs incl
2830 // FALSE dominance claims = the unsound-hoist
2831 // source. ROOT was never the dominator: opt
2832 // passes leave succ/pred STALE (T#opt-002).
2833 // cfg_rebuild_edges (top of this pass) now
2834 // recomputes edges from the TERMINATORS, the
2835 // oracle re-runs GREEN, and this load is live.
2836 // Two-step slot read (inline cast-then-index
2837 // miscompiles -- gotchas 2026-07-09).
2838 let bptr: i64 = rslot[0]
2839 let body: *BasicBlock = bptr as *BasicBlock
2840 let bidx: i64 = df_block_index(f, body)
2841 // SOURCE must be DOMINATED BY THE HEADER (2026-07-15):
2842 // hoisting instr I (block B) to the preheader P is only
2843 // sound if P dominates B's uses -- true iff H dominates B
2844 // (then P dom H dom B). mark_loop_body's in_loop can
2845 // OVER-mark a block NOT dominated by this header (the
2846 // sha512 sc_ge_l hang: a load in such a block looked
2847 // invariant vs H and was hoisted). The dominance guard
2848 // makes the source exactly the loop region, so with the
2849 // dominance-based invariance the whole pass is sound.
2850 if bidx >= 0 {
2851 if in_loop[bidx] == 1 { if dom_dominates(info, s, body) == 1 {
2852 var cur: *Instr = body.head
2853 while cur != (0 as *Instr) {
2854 let next: *Instr = cur.next
2855 var hb: i64 = licm_is_hoistable(cur.op)
2856 // G9: a loop-invariant non-escaping
2857 // scalar-alloca LOAD is hoistable too.
2858 // (Bisected clear of the ed25519 hang, which
2859 // was stale .parent (T#opt-003), not G9; the
2860 // flag stays as a lever, default ON.)
2861 if LICM_G9_LOAD_HOIST == 1 { if hb == 0 { hb = licm_load_hoistable_memo(f, cur, esc, stdom) } }
2862 if hb == 1 {
2863 if operands_are_loop_invariant(f, cur, in_loop, info, s) == 1 {
2864 hoist_instr(cur, preheader)
2865 any_hoisted = 1
2866 }
2867 }
2868 cur = next
2869 }
2870 } }
2871 }
2872 ri = ri + 1
2873 }
2874 }
2875 }
2876 }
2877 }
2878 }
2879 k = k + 1
2880 }
2881 return any_hoisted
2882}
2883
2884// Is `op` a pure non-trapping opcode safe to hoist?
2885func licm_is_hoistable(op: i64) -> i64 {
2886 if op == OP_ADD { return 1 }
2887 if op == OP_SUB { return 1 }
2888 if op == OP_MUL { return 1 }
2889 if op == OP_AND { return 1 }
2890 if op == OP_OR { return 1 }
2891 if op == OP_XOR { return 1 }
2892 if op == OP_SHL { return 1 }
2893 if op == OP_SHR_S { return 1 }
2894 if op == OP_SHR_U { return 1 }
2895 if op == OP_NEG { return 1 }
2896 if op == OP_NOT { return 1 }
2897 if op == OP_EQ { return 1 }
2898 if op == OP_NE { return 1 }
2899 if op == OP_LT_S { return 1 }
2900 if op == OP_LE_S { return 1 }
2901 if op == OP_GT_S { return 1 }
2902 if op == OP_GE_S { return 1 }
2903 if op == OP_COPY { return 1 }
2904 if op == OP_GEP { return 1 }
2905 // Explicitly NOT hoistable:
2906 // OP_DIV_S/U, OP_REM_S/U (trap on zero)
2907 // OP_LOAD, OP_STORE, OP_CALL (memory / side effects)
2908 // OP_ALLOCA (stack-position-dependent)
2909 // OP_BR, OP_BR_COND, OP_RETURN
2910 return 0
2911}
2912
2913// ===== G9 (2026-07-15): loop-invariant SCALAR-ALLOCA LOAD hoisting =====
2914// The matmul residual: `i*N` (imulq $192) stays in the k-loop because it is
2915// MUL(LOAD(i_alloca), 192) and LOAD is not hoistable -> the MUL's operand is
2916// "defined in the loop" -> not invariant. Root = the 2026-05-29 plan's DEEPEST
2917// FINDING: loop-carried state lives in ALLOCAS (SSA-no-phi mem2reg can't promote
2918// them). Fix: hoist LOAD(alloca) when the alloca is a scalar that NEVER escapes
2919// (address only ever op0 of LOAD/STORE) AND is NOT stored inside the loop -- then
2920// the value is provably loop-invariant, and the dependent MUL hoists after it in
2921// the same RPO pass. Aliasing-safe by construction: a non-escaping alloca has no
2922// pointer alias, so the only writes are direct STOREs to it, all checked.
2923
2924// k-th operand (op0..op23), or -1 past n_operands.
2925func opt_opk(inst: *Instr, k: i64) -> i64 {
2926 if k == 0 { return inst.op0 }
2927 if k == 1 { return inst.op1 }
2928 if k == 2 { return inst.op2 }
2929 if k == 3 { return inst.op3 }
2930 if k == 4 { return inst.op4 }
2931 if k == 5 { return inst.op5 }
2932 if k == 6 { return inst.op6 }
2933 if k == 7 { return inst.op7 }
2934 if k == 8 { return inst.op8 }
2935 if k == 9 { return inst.op9 }
2936 if k == 10 { return inst.op10 }
2937 if k == 11 { return inst.op11 }
2938 if k == 12 { return inst.op12 }
2939 if k == 13 { return inst.op13 }
2940 if k == 14 { return inst.op14 }
2941 if k == 15 { return inst.op15 }
2942 if k == 16 { return inst.op16 }
2943 if k == 17 { return inst.op17 }
2944 if k == 18 { return inst.op18 }
2945 if k == 19 { return inst.op19 }
2946 if k == 20 { return inst.op20 }
2947 if k == 21 { return inst.op21 }
2948 if k == 22 { return inst.op22 }
2949 if k == 23 { return inst.op23 }
2950 return 0 - 1
2951}
2952
2953// The alloca `aid` NEVER escapes: it appears as an operand ONLY at (OP_LOAD,k=0)
2954// or (OP_STORE,k=0). Any other position (STORE value, GEP base, ADDR_OF, call
2955// arg, ...) means a pointer to it could exist -> a store could alias -> unsafe.
2956func licm_alloca_noescape(f: *Function, aid: i64) -> i64 {
2957 var bi: i64 = 0
2958 while bi < f.n_blocks {
2959 let b: *BasicBlock = block_at(f, bi)
2960 var inst: *Instr = b.head
2961 while inst != (0 as *Instr) {
2962 var no: i64 = inst.n_operands
2963 if no > 24 { no = 24 }
2964 var k: i64 = 0
2965 while k < no {
2966 if opt_opk(inst, k) == aid {
2967 var okpos: i64 = 0
2968 if inst.op == OP_LOAD { if k == 0 { okpos = 1 } }
2969 if inst.op == OP_STORE { if k == 0 { okpos = 1 } }
2970 if okpos == 0 { return 0 }
2971 }
2972 k = k + 1
2973 }
2974 inst = inst.next
2975 }
2976 bi = bi + 1
2977 }
2978 return 1
2979}
2980
2981// Is there a STORE to alloca `aid` in any block DOMINATED BY THE HEADER (i.e.
2982// inside/below the loop)? DOMINANCE-BASED (2026-07-15): sound independent of
2983// mark_loop_body -- if a store to the counter is missed (as mark_loop_body did),
2984// G9 would hoist LOAD(counter) -> the counter freezes -> the loop hangs. The
2985// over-approximation (a store in a block dominated by the header but outside the
2986// loop still blocks the hoist) is CONSERVATIVE -- it can only refuse a valid
2987// hoist, never allow an invalid one.
2988func licm_store_dominated_by_header(f: *Function, aid: i64, info: *DomInfoFn,
2989 header: *BasicBlock) -> i64 {
2990 var bi: i64 = 0
2991 while bi < f.n_blocks {
2992 let b: *BasicBlock = block_at(f, bi)
2993 if dom_dominates(info, header, b) == 1 {
2994 var inst: *Instr = b.head
2995 while inst != (0 as *Instr) {
2996 if inst.op == OP_STORE { if inst.op0 == aid { return 1 } }
2997 inst = inst.next
2998 }
2999 }
3000 bi = bi + 1
3001 }
3002 return 0
3003}
3004
3005// ONE PASS builds the escape map licm_alloca_noescape answers per query: esc[v] = 1 iff value v
3006// is used anywhere other than as the ADDRESS (operand 0) of a LOAD or STORE. Same rule, same
3007// operand window (n_operands clamped to 24) as the per-query scan; every value id is marked, and
3008// the query is only ever asked for alloca results, for which the two agree exactly.
3009func licm_build_escape_map(f: *Function, esc: *u8) -> i64 {
3010 var z: i64 = 0
3011 while z < f.n_values { esc[z] = 0 as u8; z = z + 1 }
3012 var bi: i64 = 0
3013 while bi < f.n_blocks {
3014 let b: *BasicBlock = block_at(f, bi)
3015 var inst: *Instr = b.head
3016 while inst != (0 as *Instr) {
3017 var no: i64 = inst.n_operands
3018 if no > 24 { no = 24 }
3019 var k: i64 = 0
3020 while k < no {
3021 let v: i64 = opt_opk(inst, k)
3022 if v >= 0 { if v < f.n_values {
3023 var okpos: i64 = 0
3024 if inst.op == OP_LOAD { if k == 0 { okpos = 1 } }
3025 if inst.op == OP_STORE { if k == 0 { okpos = 1 } }
3026 if okpos == 0 { esc[v] = 1 as u8 }
3027 } }
3028 k = k + 1
3029 }
3030 inst = inst.next
3031 }
3032 bi = bi + 1
3033 }
3034 return 0
3035}
3036
3037// ONE PASS per header builds the map licm_store_dominated_by_header answers per query:
3038// stdom[aid] = 1 iff some STORE with address aid sits in a block DOMINATED BY the header. Same
3039// dominance rule (dom_dominates), evaluated once per block instead of once per (load, block).
3040func licm_build_store_dom_map(f: *Function, info: *DomInfoFn, header: *BasicBlock, stdom: *u8) -> i64 {
3041 var z: i64 = 0
3042 while z < f.n_values { stdom[z] = 0 as u8; z = z + 1 }
3043 var bi: i64 = 0
3044 while bi < f.n_blocks {
3045 let b: *BasicBlock = block_at(f, bi)
3046 if dom_dominates(info, header, b) == 1 {
3047 var inst: *Instr = b.head
3048 while inst != (0 as *Instr) {
3049 if inst.op == OP_STORE {
3050 let aid: i64 = inst.op0
3051 if aid >= 0 { if aid < f.n_values { stdom[aid] = 1 as u8 } }
3052 }
3053 inst = inst.next
3054 }
3055 }
3056 bi = bi + 1
3057 }
3058 return 0
3059}
3060
3061// The memoised twin of licm_load_hoistable: identical decision, reads the two maps instead of
3062// rescanning the function. licm_load_hoistable below is kept as the per-query ORACLE (the
3063// control the byte-identity proof was run against), not deleted.
3064func licm_load_hoistable_memo(f: *Function, inst: *Instr, esc: *u8, stdom: *u8) -> i64 {
3065 if inst.op != OP_LOAD { return 0 }
3066 let aid: i64 = inst.op0
3067 if aid < 0 { return 0 }
3068 if aid >= f.n_values { return 0 }
3069 let av: *Value = val_at(f, aid)
3070 if av.kind != VK_INSTR { return 0 }
3071 if av.instr == (0 as *Instr) { return 0 }
3072 if av.instr.op != OP_ALLOCA { return 0 }
3073 if esc[aid] != 0 { return 0 }
3074 if stdom[aid] != 0 { return 0 }
3075 return 1
3076}
3077
3078// A LOAD is hoistable iff its address op0 is a NON-ESCAPING scalar-alloca result
3079// with NO store inside the loop (so the loaded value is loop-invariant).
3080func licm_load_hoistable(f: *Function, inst: *Instr, info: *DomInfoFn,
3081 header: *BasicBlock) -> i64 {
3082 if inst.op != OP_LOAD { return 0 }
3083 let aid: i64 = inst.op0
3084 if aid < 0 { return 0 }
3085 if aid >= f.n_values { return 0 }
3086 let av: *Value = val_at(f, aid)
3087 if av.kind != VK_INSTR { return 0 }
3088 if av.instr == (0 as *Instr) { return 0 }
3089 if av.instr.op != OP_ALLOCA { return 0 }
3090 if licm_alloca_noescape(f, aid) == 0 { return 0 }
3091 if licm_store_dominated_by_header(f, aid, info, header) == 1 { return 0 }
3092 return 1
3093}
3094
3095// Returns 1 iff every operand of inst is loop-invariant.
3096// DOMINANCE-BASED (2026-07-15): an operand is loop-VARIANT iff its def-block is
3097// dominated by the loop HEADER (i.e. defined inside/below the loop). This uses
3098// the PROVEN-CORRECT dominance (nx_dom_oracle_gate GREEN, 683,696 pairs), so it
3099// is sound INDEPENDENT of mark_loop_body's exactness -- the old in_loop check
3100// was unsound because mark_loop_body under-marks loop-body blocks on some
3101// post-opt CFGs (sha512 sc_ge_l: loop-body loads had in_loop=0 -> looked
3102// invariant -> the whole loop body + counter hoisted -> the loop froze -> hang).
3103// A def ABOVE the loop (header does NOT dominate it, incl. the preheader) is
3104// invariant; a hoisted def now lives in the preheader (header doesn't dominate
3105// it) so the transitive-invariance cascade still resolves in one RPO pass.
3106// (in_loop is kept only as the hoist SOURCE set -- iterating fewer blocks than
3107// the true loop is safe; it can only MISS hoists, never enable a bad one.)
3108func operands_are_loop_invariant(f: *Function, inst: *Instr,
3109 in_loop: *u8, info: *DomInfoFn,
3110 header: *BasicBlock) -> i64 {
3111 var k: i64 = 0
3112 while k < inst.n_operands {
3113 // Cover op0..op15. Prior was op0..op3 only -- LICM thought
3114 // op4..op15 were always loop-invariant (since it always read
3115 // op0), enabling false-positive hoists. Partner to commits
3116 // 8efd1949 / 0ac961db / 2e03449b / ba2999b3.
3117 var op: i64 = inst.op0
3118 if k == 1 { op = inst.op1 }
3119 if k == 2 { op = inst.op2 }
3120 if k == 3 { op = inst.op3 }
3121 if k == 4 { op = inst.op4 }
3122 if k == 5 { op = inst.op5 }
3123 if k == 6 { op = inst.op6 }
3124 if k == 7 { op = inst.op7 }
3125 if k == 8 { op = inst.op8 }
3126 if k == 9 { op = inst.op9 }
3127 if k == 10 { op = inst.op10 }
3128 if k == 11 { op = inst.op11 }
3129 if k == 12 { op = inst.op12 }
3130 if k == 13 { op = inst.op13 }
3131 if k == 14 { op = inst.op14 }
3132 if k == 15 { op = inst.op15 }
3133 if k == 16 { op = inst.op16 }
3134 if k == 17 { op = inst.op17 }
3135 if k == 18 { op = inst.op18 }
3136 if k == 19 { op = inst.op19 }
3137 if k == 20 { op = inst.op20 }
3138 if k == 21 { op = inst.op21 }
3139 if k == 22 { op = inst.op22 }
3140 if k == 23 { op = inst.op23 }
3141 // SOUNDNESS FLIP (2026-06-10): the old shape treated every
3142 // UNRESOLVABLE case (missing v.instr link, missing .parent,
3143 // df_block_index -1 from a stale parent pointer) as
3144 // INVARIANT -- optimist-unsound. nx_cc_equiv_gate caught it
3145 // the moment the dormant RPO hoist awakened: a loop-counter
3146 // increment in lookup_struct was hoisted to the preheader and
3147 // gen2 lost type-alias resolution. Rule now: CONST / PARAM /
3148 // GLOBAL are invariant by kind; a VK_INSTR operand is
3149 // invariant ONLY when its defining block is positively known
3150 // and positively outside the loop. Unknown = assume in-loop.
3151 if op >= f.n_values { return 0 }
3152 let v: *Value = val_at(f, op)
3153 if v.kind == VK_INSTR {
3154 // BISECT-2026-07-15: conservative probe. Treat ANY instruction
3155 // operand as variant -> only expressions of loop-CONSTANT inputs
3156 // (const/param/global) hoist. Such a hoist is provably safe (no
3157 // use-before-def, no loop-derived value). If ed25519 STILL hangs
3158 // under this, the bug is LICM EXPOSING a latent regalloc/schedule
3159 // bug, not a wrong-hoist -- opposite fixes.
3160 if LICM_CONSERVATIVE == 1 { return 0 }
3161 if v.instr == (0 as *Instr) { return 0 }
3162 let def_bb: *BasicBlock = v.instr.parent
3163 if def_bb == (0 as *BasicBlock) { return 0 }
3164 // CONSERVATIVE (2026-07-15): an UNRESOLVABLE def-block (df_block_index
3165 // == -1, i.e. a stale/dangling parent pointer left by an earlier pass)
3166 // must be treated as VARIANT -- NOT invariant. This was THE bug: the
3167 // dominance rewrite dropped the old `di<0 -> return 0` guard, so
3168 // dom_dominates (which returns 0 for an unfindable block) made the
3169 // operand look invariant -> la_emit_i64's `while v>0` condition (op
3170 // with a -1 def-block operand) was hoisted -> the condition froze ->
3171 // infinite loop. Minimal repro: runtime/nx_licm_adversary.nx.
3172 if df_block_index(f, def_bb) < 0 { return 0 }
3173 // VARIANT iff the header dominates the def block (def in/below loop).
3174 if dom_dominates(info, header, def_bb) == 1 { return 0 }
3175 }
3176 k = k + 1
3177 }
3178 return 1
3179}
3180
3181// Unlink inst from its current block and append to preheader just
3182// before the terminator (preheader has exactly one successor so
3183// terminator is a single OP_BR). Updates parent pointer.
3184func hoist_instr(inst: *Instr, preheader: *BasicBlock) -> i64 {
3185 let src: *BasicBlock = inst.parent
3186 // Unlink from src's list.
3187 if inst.prev != (0 as *Instr) {
3188 inst.prev.next = inst.next
3189 } else {
3190 src.head = inst.next
3191 }
3192 if inst.next != (0 as *Instr) {
3193 inst.next.prev = inst.prev
3194 } else {
3195 src.tail = inst.prev
3196 }
3197 inst.prev = 0 as *Instr
3198 inst.next = 0 as *Instr
3199
3200 // Append before preheader's terminator.
3201 let term: *Instr = preheader.tail
3202 if term != (0 as *Instr) {
3203 inst.prev = term.prev
3204 inst.next = term
3205 if term.prev != (0 as *Instr) {
3206 term.prev.next = inst
3207 } else {
3208 preheader.head = inst
3209 }
3210 term.prev = inst
3211 } else {
3212 preheader.head = inst
3213 preheader.tail = inst
3214 }
3215 inst.parent = preheader
3216 return 0
3217}
3218
3219// Walk back through preds from `from`, marking every block reached
3220// (without crossing `header`) in in_loop = the natural loop body.
3221// ITERATIVE worklist (2026-07-15): the old RECURSIVE form recursed once per
3222// loop-body block; a large loop (sha512/ed25519 field arithmetic has 20-40+
3223// block loops) overflowed the NishiLang stack, silently UNDER-marking the body
3224// -> operands defined in the unmarked tail looked loop-invariant -> the loop
3225// counter/condition got hoisted -> the loop froze (sc_ge_l collapsed, ed25519
3226// rejection loop hung). Iteration has no depth limit; the marked set is
3227// identical for small loops (byte-stable) and COMPLETE for large ones.
3228func mark_loop_body_nx(f: *Function, header: *BasicBlock,
3229 from: *BasicBlock, in_loop: *u8) -> i64 {
3230 let n: i64 = f.n_blocks
3231 let wl_raw: *u8 = sys_mmap(n * 8 + 16)
3232 let wl: *i64 = wl_raw as *i64
3233 var wh: i64 = 0
3234 var wt: i64 = 0
3235 let fi: i64 = df_block_index(f, from)
3236 if fi < 0 { return 0 }
3237 if in_loop[fi] == 0 { in_loop[fi] = 1; wl[wt] = fi; wt = wt + 1 }
3238 while wh < wt {
3239 let ci: i64 = wl[wh]
3240 wh = wh + 1
3241 let cb: *BasicBlock = block_at(f, ci)
3242 // The header is in the body but we do NOT walk above it.
3243 if cb != header {
3244 let p0: *BasicBlock = cb.pred0
3245 if p0 != (0 as *BasicBlock) {
3246 let pi: i64 = df_block_index(f, p0)
3247 if pi >= 0 { if in_loop[pi] == 0 { in_loop[pi] = 1; wl[wt] = pi; wt = wt + 1 } }
3248 }
3249 let p1: *BasicBlock = cb.pred1
3250 if p1 != (0 as *BasicBlock) {
3251 let pi1: i64 = df_block_index(f, p1)
3252 if pi1 >= 0 { if in_loop[pi1] == 0 { in_loop[pi1] = 1; wl[wt] = pi1; wt = wt + 1 } }
3253 }
3254 let p2: *BasicBlock = cb.pred2
3255 if p2 != (0 as *BasicBlock) {
3256 let pi2: i64 = df_block_index(f, p2)
3257 if pi2 >= 0 { if in_loop[pi2] == 0 { in_loop[pi2] = 1; wl[wt] = pi2; wt = wt + 1 } }
3258 }
3259 }
3260 }
3261 return 0
3262}
3263
3264// ===== VRA-guided comparison folding =================================
3265//
3266// When VRA gives us known ranges [a_lo, a_hi] for x and [b_lo, b_hi]
3267// for y, many comparisons collapse to constants:
3268//
3269// x < y: true if a_hi < b_lo
3270// false if a_lo >= b_hi
3271// x > y: true if a_lo > b_hi
3272// false if a_hi <= b_lo
3273// x == y: false if ranges don't overlap
3274// x != y: true if ranges don't overlap
3275//
3276// SSA + VRA makes this cheap to check. Catches patterns like:
3277// let i = 0
3278// while i < 10 { ... i = i + 1 } -- i known in [0, 10]
3279// if i == 20 { ... } -- dead branch
3280// which GVN + SCCP miss because they don't track ranges.
3281//
3282// Returns the count of rewrites.
3283
3284// Struct + forward decls so opt_compare_fold can reference VRA.
3285// The body is below this section (order preserved for readability).
3286struct VraResult {
3287 min: *i64,
3288 max: *i64,
3289 known: *i64,
3290 n: i64,
3291}
3292func opt_vra_compute(f: *Function) -> *VraResult;
3293func vra_is_nonneg(vra: *VraResult, v: i64) -> i64;
3294
3295func opt_compare_fold(f: *Function) -> i64 {
3296 var changed: i64 = 0
3297 let vra: *VraResult = opt_vra_compute(f)
3298 var bi: i64 = 0
3299 while bi < f.n_blocks {
3300 let b: *BasicBlock = block_at(f, bi)
3301 var inst: *Instr = b.head
3302 while inst != (0 as *Instr) {
3303 if inst.n_operands == 2 {
3304 let a: i64 = inst.op0
3305 let y: i64 = inst.op1
3306 if a < vra.n {
3307 if y < vra.n {
3308 if vra.known[a] == 1 {
3309 if vra.known[y] == 1 {
3310 let a_lo: i64 = vra.min[a]
3311 let a_hi: i64 = vra.max[a]
3312 let b_lo: i64 = vra.min[y]
3313 let b_hi: i64 = vra.max[y]
3314 // OP_LT_S = 22
3315 if inst.op == 22 {
3316 if a_hi < b_lo {
3317 rewrite_to_copy(inst, const_one(f))
3318 changed = changed + 1
3319 }
3320 if a_lo >= b_hi {
3321 make_result_zero(f, inst)
3322 changed = changed + 1
3323 }
3324 }
3325 // OP_GT_S = 24
3326 if inst.op == 24 {
3327 if a_lo > b_hi {
3328 rewrite_to_copy(inst, const_one(f))
3329 changed = changed + 1
3330 }
3331 if a_hi <= b_lo {
3332 make_result_zero(f, inst)
3333 changed = changed + 1
3334 }
3335 }
3336 // OP_EQ = 20
3337 if inst.op == 20 {
3338 if a_hi < b_lo { make_result_zero(f, inst); changed = changed + 1 }
3339 if a_lo > b_hi { make_result_zero(f, inst); changed = changed + 1 }
3340 }
3341 // OP_NE = 21
3342 if inst.op == 21 {
3343 if a_hi < b_lo { rewrite_to_copy(inst, const_one(f)); changed = changed + 1 }
3344 if a_lo > b_hi { rewrite_to_copy(inst, const_one(f)); changed = changed + 1 }
3345 }
3346 }
3347 }
3348 }
3349 }
3350 }
3351 inst = inst.next
3352 }
3353 bi = bi + 1
3354 }
3355 return changed
3356}
3357
3358// ===== value-range analysis (VRA) ===================================
3359//
3360// For each SSA Value, compute (known_min, known_max, is_known).
3361// Constants carry exact ranges. Arithmetic propagates. Unknown
3362// or unsupported ops leave the value unknown.
3363//
3364// Consumers (to be added in future commits):
3365// - opt_strength_reduce: x / 2^k safe to replace with x >> k
3366// only when x >= 0 -- VRA tells us when that's true
3367// - opt_bounds_check_elim: drop array bounds checks when index
3368// is provably within range
3369// - opt_compare_fold: x < y reduces to const when ranges don't
3370// overlap (x.max < y.min -> always true)
3371// - opt_narrow: i64 ops on values that fit in i32 -> faster
3372// int32 ops when target supports
3373//
3374// Storage: parallel arrays keyed by value_id, sized n_values.
3375// vra_min[v] -- known lower bound (i64)
3376// vra_max[v] -- known upper bound (i64)
3377// vra_known[v] -- 1 if bounded, 0 if unknown / unbounded
3378//
3379// Returns: pointer to a VraResult struct the caller owns.
3380
3381// Compute VRA for every Value in f. Single forward pass in SSA
3382// definition order; for straight-line code this achieves the full
3383// fixed-point in one pass. Loops + PHIs stay unknown (no proper
3384// widening operator yet -- v0.1.0 adds Cousot widening).
3385func opt_vra_compute(f: *Function) -> *VraResult {
3386 let res_raw: *u8 = sys_mmap(64)
3387 let res: *VraResult = res_raw as *VraResult
3388 res.min = sys_mmap(f.n_values * 8 + 64) as *i64
3389 res.max = sys_mmap(f.n_values * 8 + 64) as *i64
3390 res.known = sys_mmap(f.n_values * 8 + 64) as *i64
3391 res.n = f.n_values
3392
3393 // Seed: constants get exact range; everything else unknown.
3394 var v: i64 = 0
3395 let base: i64 = f.values as i64
3396 while v < f.n_values {
3397 let vv: *Value = (base + v * 48) as *Value
3398 if vv.kind == VAL_CONST {
3399 res.min[v] = vv.const_int
3400 res.max[v] = vv.const_int
3401 res.known[v] = 1
3402 }
3403 if vv.kind != VAL_CONST {
3404 res.known[v] = 0
3405 }
3406 v = v + 1
3407 }
3408
3409 // Walk instructions in block order; propagate through SSA.
3410 var bi: i64 = 0
3411 while bi < f.n_blocks {
3412 let b: *BasicBlock = block_at(f, bi)
3413 var inst: *Instr = b.head
3414 while inst != (0 as *Instr) {
3415 if inst.result < f.n_values {
3416 let r: i64 = inst.result
3417 if inst.n_operands == 2 {
3418 let a: i64 = inst.op0
3419 let bv: i64 = inst.op1
3420 if res.known[a] == 1 {
3421 if res.known[bv] == 1 {
3422 let amin: i64 = res.min[a]
3423 let amax: i64 = res.max[a]
3424 let bmin: i64 = res.min[bv]
3425 let bmax: i64 = res.max[bv]
3426 // ADD: [a_min+b_min, a_max+b_max]
3427 if inst.op == 1 {
3428 res.min[r] = amin + bmin
3429 res.max[r] = amax + bmax
3430 res.known[r] = 1
3431 }
3432 // SUB: [a_min-b_max, a_max-b_min]
3433 if inst.op == 2 {
3434 res.min[r] = amin - bmax
3435 res.max[r] = amax - bmin
3436 res.known[r] = 1
3437 }
3438 // AND with non-negative mask: result fits
3439 // in [0, mask]. Limited scope; extended
3440 // in v0.1.0.
3441 if inst.op == 10 {
3442 if bmin >= 0 {
3443 res.min[r] = 0
3444 res.max[r] = bmax
3445 res.known[r] = 1
3446 }
3447 }
3448 // OR with non-negative: [max(a_min, b_min), a_max | b_max]
3449 // Conservative: use sum as upper bound.
3450 if inst.op == 11 {
3451 if amin >= 0 {
3452 if bmin >= 0 {
3453 res.min[r] = amin
3454 if bmin > amin { res.min[r] = bmin }
3455 res.max[r] = amax + bmax
3456 res.known[r] = 1
3457 }
3458 }
3459 }
3460 }
3461 }
3462 }
3463 }
3464 inst = inst.next
3465 }
3466 bi = bi + 1
3467 }
3468 return res
3469}
3470
3471// Query helper: is Value v provably non-negative? Used by future
3472// strength reduction / bounds check elimination passes.
3473func vra_is_nonneg(vra: *VraResult, v: i64) -> i64 {
3474 if v >= vra.n { return 0 }
3475 if vra.known[v] != 1 { return 0 }
3476 if vra.min[v] >= 0 { return 1 }
3477 return 0
3478}
3479
3480// ===== reassociation =================================================
3481//
3482// For commutative/associative ops (ADD, MUL, AND, OR, XOR), rotate
3483// chains so constants cluster to one side where const_fold catches
3484// them in the next round:
3485//
3486// (x + 2) + 3 -> x + (2 + 3) -> const_fold -> x + 5
3487// (c1 * x) * c2 -> x * (c1 * c2) -> const_fold -> x * c
3488// ((x & mask1) & mask2) -> x & (mask1 & mask2) -> const_fold
3489//
3490// Standard LLVM "Reassociate" pass shape. Run BEFORE const_fold
3491// in the pipeline so folded constants feed back into the same
3492// round.
3493//
3494// Detection rule (canonical left-skewed tree):
3495// inst = binop(a, b) where a is binop of same op with const
3496// ^^^ ^^^
3497// inner_l = a's first operand (the variable x)
3498// inner_r = a's second operand (a constant c1)
3499// and
3500// b is a constant (c2)
3501//
3502// Rewrites to:
3503// inst.op0 = inner_l (x)
3504// inst.op1 = (new VAL_CONST with c1 + c2, for ADD/MUL etc.)
3505// Next round's const_fold absorbs the new constant.
3506//
3507// v0.0.1 scope: two-level chains only; deeper chains get rewritten
3508// gradually across multiple rounds of opt_run.
3509
3510func opt_reassoc(f: *Function) -> i64 {
3511 var changed: i64 = 0
3512 var bi: i64 = 0
3513 while bi < f.n_blocks {
3514 let b: *BasicBlock = block_at(f, bi)
3515 var inst: *Instr = b.head
3516 while inst != (0 as *Instr) {
3517 if inst.n_operands == 2 {
3518 let op: i64 = inst.op
3519 // Only commutative+associative binops.
3520 var ok: i64 = 0
3521 if op == 1 { ok = 1 } // ADD
3522 if op == 3 { ok = 1 } // MUL
3523 if op == 10 { ok = 1 } // AND
3524 if op == 11 { ok = 1 } // OR
3525 if op == 12 { ok = 1 } // XOR
3526
3527 if ok == 1 {
3528 let b_val: *Value = val_at(f, inst.op1)
3529 if b_val.kind == VAL_CONST {
3530 let a_val: *Value = val_at(f, inst.op0)
3531 if a_val.kind == VAL_INSTR {
3532 if a_val.instr != (0 as *Instr) {
3533 let inner: *Instr = a_val.instr
3534 if inner.op == op {
3535 if inner.n_operands == 2 {
3536 let ir: *Value = val_at(f, inner.op1)
3537 if ir.kind == VAL_CONST {
3538 // Pattern match: (x op c1) op c2
3539 // Rewrite to x op (c1 op c2).
3540 let folded: i64 = comptime_eval_binop(op, ir.const_int, b_val.const_int)
3541 // Replace b_val's const_int with folded; reuse
3542 // the existing Value to avoid ir_new_const complexity.
3543 b_val.const_int = folded
3544 inst.op0 = inner.op0
3545 changed = changed + 1
3546 }
3547 }
3548 }
3549 }
3550 }
3551 }
3552 }
3553 }
3554 inst = inst.next
3555 }
3556 bi = bi + 1
3557 }
3558 return changed
3559}
3560
3561// ===== block merging =================================================
3562//
3563// When block A's sole successor is B and B's sole predecessor is A,
3564// concatenate B's instructions into A and unlink B. Standard CFG
3565// simplification used by every optimizer (LLVM SimplifyCFG, gcc
3566// cfgcleanup); enables further optimizations because previously-
3567// cross-block redundancies become same-block (visible to GVN, CSE,
3568// DSE, etc).
3569//
3570// Conservative scope:
3571// - A must end with an unconditional branch to B (OP_BR)
3572// - B must have exactly one predecessor (== A)
3573// - B must not be the function entry
3574//
3575// Returns the count of merges performed.
3576
3577func opt_block_merge(f: *Function) -> i64 {
3578 var changed: i64 = 0
3579 var ai: i64 = 0
3580 while ai < f.n_blocks {
3581 let a: *BasicBlock = block_at(f, ai)
3582 if a.tail == (0 as *Instr) { ai = ai + 1; continue }
3583 if a.tail.op != OP_BR { ai = ai + 1; continue }
3584 // OP_BR's op0 is the target block id.
3585 let b_id: i64 = a.tail.op0
3586 if b_id < 0 { ai = ai + 1; continue }
3587 if b_id >= f.n_blocks { ai = ai + 1; continue }
3588 let b: *BasicBlock = block_at(f, b_id)
3589 if b == f.entry { ai = ai + 1; continue }
3590 // B must have exactly one predecessor.
3591 if b.n_preds != 1 { ai = ai + 1; continue }
3592 if b.pred0 != a { ai = ai + 1; continue }
3593
3594 // Drop A's terminating OP_BR.
3595 unlink(a, a.tail)
3596 // Splice B's instruction list onto A's.
3597 if b.head != (0 as *Instr) {
3598 if a.tail == (0 as *Instr) {
3599 a.head = b.head
3600 b.head.prev = 0 as *Instr
3601 } else {
3602 a.tail.next = b.head
3603 b.head.prev = a.tail
3604 }
3605 a.tail = b.tail
3606 }
3607 // Re-point B's successors' predecessors at A.
3608 if b.succ0 != (0 as *BasicBlock) {
3609 if b.succ0.pred0 == b { b.succ0.pred0 = a }
3610 if b.succ0.pred1 == b { b.succ0.pred1 = a }
3611 if b.succ0.pred2 == b { b.succ0.pred2 = a }
3612 }
3613 if b.succ1 != (0 as *BasicBlock) {
3614 if b.succ1.pred0 == b { b.succ1.pred0 = a }
3615 if b.succ1.pred1 == b { b.succ1.pred1 = a }
3616 if b.succ1.pred2 == b { b.succ1.pred2 = a }
3617 }
3618 // Adopt B's successor edges.
3619 a.n_succs = b.n_succs
3620 a.succ0 = b.succ0
3621 a.succ1 = b.succ1
3622 // B is now empty + unreachable; sweep_unreachable_function
3623 // will clean it up next round.
3624 b.head = 0 as *Instr
3625 b.tail = 0 as *Instr
3626 b.n_succs = 0
3627 b.n_preds = 0
3628 changed = changed + 1
3629 ai = ai + 1
3630 }
3631 return changed
3632}
3633
3634// ===== dead store elimination (intra-block) =========================
3635//
3636// Removes stores whose value is overwritten before any read.
3637// Per-block scope only -- inter-block needs MUST-alias analysis
3638// + dataflow which is v0.1.0 work.
3639//
3640// Tracks: address-Value -> last STORE instruction we saw to it.
3641// On a second STORE to the same address with no intervening LOAD,
3642// the previous store is dead. CALL / SYSCALL / TAIL_CALL kill
3643// the entire tracking map (could write anywhere via aliasing).
3644//
3645// Returns the number of dead stores removed.
3646
3647const DSE_MAX_TRACKED: i64 = 256
3648
3649func opt_dse(f: *Function) -> i64 {
3650 var removed: i64 = 0
3651 let track_addrs_raw: *u8 = sys_mmap(DSE_MAX_TRACKED * 8 + 16)
3652 let track_addrs: *i64 = track_addrs_raw as *i64
3653 let track_insts_raw: *u8 = sys_mmap(DSE_MAX_TRACKED * 8 + 16)
3654 let track_insts: *i64 = track_insts_raw as *i64
3655
3656 var bi: i64 = 0
3657 while bi < f.n_blocks {
3658 let bb: *BasicBlock = block_at(f, bi)
3659 var n_track: i64 = 0
3660 var inst: *Instr = bb.head
3661 while inst != (0 as *Instr) {
3662 let next_inst: *Instr = inst.next
3663 if inst.op == OP_STORE {
3664 let addr_id: i64 = inst.op0
3665 // Look up addr in tracked.
3666 var found: i64 = -1
3667 var ti: i64 = 0
3668 while ti < n_track {
3669 if track_addrs[ti] == addr_id { found = ti }
3670 ti = ti + 1
3671 }
3672 if found >= 0 {
3673 // Previous store to same address is dead.
3674 let prev_addr: i64 = track_insts[found]
3675 let prev_inst: *Instr = prev_addr as *Instr
3676 unlink(bb, prev_inst)
3677 track_insts[found] = inst as i64
3678 removed = removed + 1
3679 }
3680 if found < 0 {
3681 if n_track < DSE_MAX_TRACKED {
3682 track_addrs[n_track] = addr_id
3683 track_insts[n_track] = inst as i64
3684 n_track = n_track + 1
3685 }
3686 }
3687 }
3688 if inst.op == OP_LOAD {
3689 let addr_id: i64 = inst.op0
3690 // Read from this address -- the most recent store
3691 // is now necessary, drop it from tracking (the
3692 // value's been observed).
3693 var ti: i64 = 0
3694 while ti < n_track {
3695 if track_addrs[ti] == addr_id {
3696 // Remove by swap with last.
3697 track_addrs[ti] = track_addrs[n_track - 1]
3698 track_insts[ti] = track_insts[n_track - 1]
3699 n_track = n_track - 1
3700 ti = n_track // exit loop
3701 }
3702 ti = ti + 1
3703 }
3704 }
3705 // Calls + syscalls + tail-calls are arbitrary writers;
3706 // discard everything we were tracking.
3707 if inst.op == OP_CALL { n_track = 0 }
3708 if inst.op == OP_CALL_INDIRECT { n_track = 0 }
3709 if inst.op == OP_SYSCALL { n_track = 0 }
3710 if inst.op == OP_TAIL_CALL { n_track = 0 }
3711 // G3 FIX-1: __adc_acc reads+writes acc[0..2] through its pointer; DSE
3712 // is blind to it -> treat as an arbitrary memory writer (barrier).
3713 if inst.op == OP_ADC_ACC { n_track = 0 }
3714 inst = next_inst
3715 }
3716 bi = bi + 1
3717 }
3718 return removed
3719}
3720
3721// ===== strength reduction ==========================================
3722//
3723// Rewrites expensive ops with constant power-of-two operands as
3724// cheaper shift / mask ops:
3725//
3726// x * (1 << k) -> x << k (any k, any sign)
3727// x * 1 -> x (identity; already in simplify)
3728// x * 0 -> 0 (already in simplify)
3729// x / (1 << k) -> x >> k (signed arithmetic shift)
3730// x % (1 << k) -> x & ((1<<k) - 1) (unsigned)
3731//
3732// Standard since Wulf & Lo's BLISS-11 compiler (1972). Modern
3733// compilers also do (a+b) * c -> a*c + b*c (distributive
3734// strength reduction in loops); we don't yet -- v0.1.0 work.
3735//
3736// Returns the count of rewrites.
3737
3738// True iff `n` is exactly 2^k for some k >= 1. Returns the k value
3739// in `*shift_out`; returns 0 if n isn't a power-of-two we can
3740// usefully reduce (excludes 1 and 0; those are simpler-pass cases).
3741func is_pow2(n: i64, shift_out: *i64) -> i64 {
3742 if n <= 1 { return 0 }
3743 var v: i64 = n
3744 var k: i64 = 0
3745 while v > 1 {
3746 if v & 1 { return 0 } // odd bit before reaching 1 -> not pow2
3747 v = v >> 1
3748 k = k + 1
3749 }
3750 *shift_out = k
3751 return 1
3752}
3753
3754func opt_strength_reduce(f: *Function) -> i64 {
3755 var changed: i64 = 0
3756 // Compute VRA once per pass; consulting vra_is_nonneg lets us
3757 // safely turn signed-division-by-pow-2 into arithmetic-shift
3758 // only on values proven >= 0.
3759 let vra: *VraResult = opt_vra_compute(f)
3760 var bi: i64 = 0
3761 while bi < f.n_blocks {
3762 let bb: *BasicBlock = block_at(f, bi)
3763 var inst: *Instr = bb.head
3764 while inst != (0 as *Instr) {
3765 let next_inst: *Instr = inst.next
3766 if inst.n_operands == 2 {
3767 // Try to find a constant operand to reduce against.
3768 let op0v: *Value = val_at(f, inst.op0)
3769 let op1v: *Value = val_at(f, inst.op1)
3770 var const_id: i64 = -1
3771 var var_id: i64 = -1
3772 var const_val: i64 = 0
3773 var const_first: i64 = 0
3774 if op1v.kind == VAL_CONST {
3775 const_id = inst.op1
3776 var_id = inst.op0
3777 const_val = op1v.const_int
3778 }
3779 if op1v.kind != VAL_CONST {
3780 if op0v.kind == VAL_CONST {
3781 const_id = inst.op0
3782 var_id = inst.op1
3783 const_val = op0v.const_int
3784 const_first = 1
3785 }
3786 }
3787 if const_id >= 0 {
3788 let shift_raw: *u8 = sys_mmap(16)
3789 let shift_p: *i64 = shift_raw as *i64
3790 *shift_p = 0
3791 let pow: i64 = is_pow2(const_val, shift_p)
3792 if pow == 1 {
3793 if inst.op == OP_MUL {
3794 // x * 2^k -> x << k (always safe). CORRECTNESS FIX
3795 // (silent miscompile, 2026-06-02): allocate a FRESH
3796 // constant for the shift amount. Mutating the shared
3797 // multiplier constant in place (const_int = shift)
3798 // corrupted EVERY OTHER instruction referencing the
3799 // same deduplicated constant Value -> e.g. the video
3800 // codec's img_w = 16*8 read back as 7. Constants are
3801 // shared; never mutate one in place.
3802 let shamt_id: i64 = ir_const_i64(f, *shift_p)
3803 inst.op = OP_SHL
3804 inst.op0 = var_id
3805 inst.op1 = shamt_id
3806 changed = changed + 1
3807 }
3808 if inst.op == OP_DIV_S {
3809 // x / 2^k -> x >> k ONLY when x is
3810 // provably non-negative. Signed shift
3811 // of a negative value differs from
3812 // signed division by 1 (rounding
3813 // direction). VRA gates the rewrite.
3814 if const_first == 0 {
3815 if vra_is_nonneg(vra, var_id) == 1 {
3816 // FRESH shift constant (same fix as MUL->SHL):
3817 // never mutate the shared divisor constant.
3818 let shamt_id: i64 = ir_const_i64(f, *shift_p)
3819 inst.op = OP_SHR_S
3820 inst.op0 = var_id
3821 inst.op1 = shamt_id
3822 changed = changed + 1
3823 }
3824 }
3825 }
3826 }
3827 }
3828 }
3829 inst = next_inst
3830 }
3831 bi = bi + 1
3832 }
3833 return changed
3834}
3835
3836// ===== tail-call optimisation =======================================
3837//
3838// Transforms `result = CALL X(args); RETURN result` at the end of a
3839// basic block into `TAIL_CALL X(args)`. Callee returns directly to
3840// our caller, eliminating one stack frame -- recursive functions
3841// run in O(1) stack depth.
3842//
3843// This is a classic 1990s-era pass (Steele 1977; Appel SML/NJ
3844// 1990s). Modern compilers (LLVM, gcc) do a more general version
3845// that handles tail-position calls anywhere in the CFG; v0.0.1 only
3846// catches the textbook last-block case.
3847//
3848// NishiLang IR already has OP_TAIL_CALL (types.nx const = 34) and
3849// runtime/riscv.nx has rv_emit_tail_call (since the parser used to
3850// detect this pattern in a few hand-coded sites). This pass turns
3851// every qualifying CALL into a TAIL_CALL automatically.
3852//
3853// Returns the number of rewrites.
3854
3855func opt_tail_call(f: *Function) -> i64 {
3856 var changed: i64 = 0
3857 var bi: i64 = 0
3858 while bi < f.n_blocks {
3859 let bb: *BasicBlock = block_at(f, bi)
3860 let last: *Instr = bb.tail
3861 if last == (0 as *Instr) { bi = bi + 1; continue }
3862 // Last must be a return with one operand (the value being
3863 // returned).
3864 if last.op != OP_RETURN { bi = bi + 1; continue }
3865 if last.n_operands != 1 { bi = bi + 1; continue }
3866 // Penultimate must be a CALL whose result is the same Value
3867 // the return propagates.
3868 let prev: *Instr = last.prev
3869 if prev == (0 as *Instr) { bi = bi + 1; continue }
3870 if prev.op != OP_CALL { bi = bi + 1; continue }
3871 if prev.result != last.op0 { bi = bi + 1; continue }
3872 // SOUNDNESS (sibcall legality, found 2026-06-10): the x86
3873 // tail-call emitter tears down our frame BEFORE the jmp, so
3874 // stack-passed arguments (7th+) cannot be materialized --
3875 // converting a >6-arg call silently DROPPED arg 7 (proven:
3876 // tls13_derive_secret -> tls13_hkdf_expand_label zeroed every
3877 // TLS Derive-Secret; regression gate _arg7_minrepro.nx).
3878 // Same legality rule gcc uses to decline sibcalls.
3879 if prev.n_operands > 6 { bi = bi + 1; continue }
3880 // Indirect calls (no resolved callee) have no jmp target in
3881 // the x86 emitter -- it emits a comment and FALLS THROUGH a
3882 // torn-down frame. Never convert those.
3883 if prev.callee == (0 as *Function) { bi = bi + 1; continue }
3884
3885 // Match: rewrite CALL -> TAIL_CALL, drop the RETURN.
3886 prev.op = OP_TAIL_CALL
3887 prev.next = 0 as *Instr
3888 bb.tail = prev
3889 changed = changed + 1
3890 bi = bi + 1
3891 }
3892 return changed
3893}
3894
3895// ===== EQUALITY-SATURATION PASS -- WIRED INTO opt_run ON 2026-08-23 (LN8) =====
3896// STATUS: LIVE. nx_opt.nx imports nx_opt_eqsat_pass.nx (see the import list) and opt_run calls
3897// opt_eqsat_pass beside opt_reassoc below. Shipped through the canaried lane: nx_cc_equiv_gate 10/10
3898// plus selfhost GREEN, promote_toolchain canary GREEN; nx_opt_eqsat_wire_gate proves the wiring in the
3899// shipping pipeline (x ^ x with x a runtime param emits `movabsq $0` where the pre-LN8 compiler emitted
3900// `xorq`, the x ^ y control keeps its xor; 5/5 GREEN, RED 4/5 on a mutant with the call removed).
3901// Measured cost: +26 ms on a 275-line gate unit, within noise on the 3.5 MB compiler unit; the compiler
3902// grew 653,359 -> 725,449 B (the engine's closure). The history below is kept because it records how
3903// the equivalence net became reachable over MCP, which is what made this wiring provable at all.
3904//
3905// (HISTORY, 2026-08-14) opt_eqsat_pass lives in runtime/nx_opt_eqsat_pass.nx and is proven 10/10 by nx_opt_eqsat_pass_gate:
3906// on one function it folds `x xor x` to the constant 0 while the incumbent opt_const_fold folds
3907// NOTHING (it structurally requires both operands constant, and opt_simplify -- the peephole that
3908// would catch some of these -- is BISECT-DISABLED above after a self-host miscompile).
3909//
3910// THE IMPORT WAS ATTEMPTED HERE ON 2026-08-14 AND BACKED OUT, with both numbers measured rather than
3911// argued:
3912// COST: importing it grew the compiler from 671,730 to 767,703 bytes -- +95,973 B, +14.3% -- on
3913// every nx_compile_x86 build, for a pass that would ship DISABLED.
3914// VERDICT: UNOBTAINABLE -- BUT NOT FOR THE REASON FIRST RECORDED HERE, AND THE FIRST REASON WAS
3915// WRONG. I originally wrote that the gate could not reach the toolchain because its cwdprobe
3916// printed `offc=NO`. That reading was mistaken twice over: eq_anchor_root chdirs to buildroot,
3917// so `br_runtime=NO` and `br_offc=NO` are CORRECT from there, and `offc=NO` probes
3918// nx_compile_x86_native.elf -- not the baseline the gate actually uses. MEASURED: the real
3919// baseline buildroot/_offc/nx_cc_sovereign.elf is present at 671,424 B. The toolchain was
3920// reachable the whole time.
3921// THE ACTUAL CAUSE: I invoked the gate with NO challenger argument, so it fell back to its
3922// default /tmp/cc_challenger.elf -- a STALE 635,099 B leftover from some earlier run, smaller
3923// than the baseline and unrelated to this change. Every row failed on `build_b=1` because that
3924// stale binary cannot build, and the gate never saw the candidate at all. The verdict was about
3925// somebody else's artifact.
3926// The standing rule is that every compiler change clears the equivalence net BEFORE it stands. Since
3927// the net could not be run, the change does not stand: leaving an unverified +96 KB import in the tree
3928// is a loaded gun aimed at whichever seat next builds and promotes the compiler.
3929// THE REAL BLOCKER, FOUND BY CHASING THE WRONG ONE FIRST: /api/gate_run PASSES NO ARGV, and
3930// nx_cc_equiv_gate REQUIRES a challenger path. So the estate's compiler-equivalence gate could not be
3931// run through the estate's own gate-running route at all -- a seat working over MCP had no way to
3932// clear a compiler change, which is why this import could not be verified from here.
3933// Two things were shipped 2026-08-14 to close that:
3934// 1. nx_cc_equiv_gate now REFUSES when given no challenger (exit 5, NO-CHALLENGER-GIVEN) instead of
3935// silently testing whatever /tmp/cc_challenger.elf happens to contain. Bite-proven: the identical
3936// invocation that had returned ten FAIL rows now returns the refusal and names the fix.
3937// 2. A pinned allowlist row `nx_cc_equiv_staged` was registered against the same elf with the 4th
3938// field set to ../nx_compile_x86.sov.elf.new, VERIFIED PRESENT in tool_allowlist.conf. Fixed-arg
3939// pinning is the estate's existing answer to a route that cannot carry arguments, so the gate is
3940// now reachable over MCP with the challenger supplied by the registry rather than the caller.
3941// It becomes callable once tools/list refreshes; it could not be exercised in the session that
3942// registered it, and that is stated rather than assumed.
3943// TO FINISH THIS: invoke nx_cc_equiv_staged against a compiler built WITH the three lines below
3944// re-applied -- the import, `const OPT_EQSAT_LIVE: i64 = 0`, and the guarded call beside opt_reassoc --
3945// and promote only on 10/10 plus selfhost.
3946func opt_run(f: *Function) -> i64 {
3947 var round: i64 = 0
3948 while round < 8 {
3949 var changed: i64 = 0
3950 if opt_mem2reg_simple(f) > 0 { changed = 1 }
3951 if opt_sccp_branches(f) > 0 { changed = 1 }
3952 if opt_const_fold(f) > 0 { changed = 1 }
3953 if opt_copyprop(f) > 0 { changed = 1 }
3954 if opt_copy_forward(f) > 0 { changed = 1 }
3955 if opt_cse(f) > 0 { changed = 1 }
3956 if opt_gvn_block(f) > 0 { changed = 1 }
3957 if opt_licm(f) > 0 { changed = 1 }
3958 // LN7 sound bounds-check elision. Placed AFTER cse/gvn/licm so the repeated index uses
3959 // they unify are already single SSA ids by the time the key is taken, and BEFORE
3960 // opt_dce so the comparisons it strands are collected in this same round.
3961 if opt_bounds_check_elim(f) > 0 { changed = 1 }
3962 // BISECT-DISABLED: if opt_simplify(f) > 0 { changed = 1 }
3963 // STUB(opt, T#selfhost-001): opt_load_forward re-disabled.
3964 // Same out_i64-shape IR (multi-block while-loop, alloca'd
3965 // vars, OP_REM_S/OP_DIV_S) hangs again. The 64-instr
3966 // backward-walk bound is insufficient.
3967 // Plan: rewrite the load-forward backward walk to use a
3968 // dataflow lattice (gen/kill per block) instead of a
3969 // per-load deep traversal; OR accept the missed opt and
3970 // leave it disabled until a sound version lands.
3971 // Closes when: out_i64 self-compiles AND all _offc tests
3972 // in test_offc.sh pass with opt_load_forward enabled.
3973 // RE-ENABLE ATTEMPTED AND REFUSED BY THE GATE, 2026-07-25. Result recorded so the next
3974 // session does not repeat it: with this line live the compiler BUILDS FINE and the bless
3975 // corpus is unchanged at 127 fails -- but nx_selfhost_gauntlet_sov goes
3976 // **RED 11/24**: `deref_read_write` fails to COMPILE and the self-host fixpoint breaks,
3977 // taking every downstream cell with it.
3978 //
3979 // So the disable was correct, but the REASON in the note above is not: there is no hang,
3980 // and there cannot be one -- `walks` increments every iteration and forces stopped=1 at
3981 // the cap. The failure is a MISCOMPILE, not a non-termination. Whoever picks this up
3982 // should debug it as a wrong-value bug on the `deref_read_write` shape
3983 // (`var x; let p = &x; *p = 33; return *p`), where forwarding a store through a pointer
3984 // alias is exactly the unsound case this pass has no alias analysis to rule out.
3985 //
3986 // ATTEMPT 2, 2026-07-26 -- ALSO REFUSED BY THE GATE, but it MOVED THE DIAGNOSIS.
3987 // Added the missing alias rule: forward only from an alloca whose address NEVER
3988 // ESCAPES (reusing licm_alloca_noescape, the predicate G9's load-hoist already uses).
3989 // With no escape, no other value id can name that memory, so id comparison IS a sound
3990 // alias test, and `&x` is excluded by construction.
3991 // RESULT: the WRONG-VALUE bug is GONE -- `deref_read_write` compiles and passes.
3992 // A SEPARATE defect remains: nx_cc itself SEGVs (exit 139, no diagnostic, symbol dump
3993 // stops at `main`) while compiling several bounds-check witnesses, and the self-host
3994 // fixpoint diverges. So this pass has at least TWO defects, and the escape rule fixes
3995 // only the first. Next attempt should debug the CRASH first, in isolation, with the
3996 // escape rule kept -- it is a real improvement even though it does not make the pass
3997 // shippable on its own. Witness: runtime/_bchk/nx_bchk_w2_oob_read.nx.
3998 // if opt_load_forward(f) > 0 { changed = 1 }
3999 if opt_alloca_const(f) > 0 { changed = 1 }
4000 if opt_dce(f) > 0 { changed = 1 }
4001 if opt_thread_jumps(f) > 0 { changed = 1 }
4002 if opt_tail_call(f) > 0 { changed = 1 }
4003 if opt_strength_reduce(f) > 0 { changed = 1 }
4004 if opt_dse(f) > 0 { changed = 1 }
4005 if opt_block_merge(f) > 0 { changed = 1 }
4006 if opt_reassoc(f) > 0 { changed = 1 }
4007 // LN8: equality saturation rewriting real IR (x xor x -> 0 and the rest of the proven rule
4008 // table) -- LIVE, behind the equivalence net like every other pass here.
4009 if opt_eqsat_pass(f) > 0 { changed = 1 }
4010 if opt_sweep_unreachable_function(f) > 0 { changed = 1 }
4011 if changed == 0 { return round }
4012 round = round + 1
4013 }
4014 return round
4015}
4016
4017// ===== self-test ====================================================
4018//
4019// Mini-IR construction plus opt pipeline, all at runtime. Verifies:
4020// * (10 + 20) * 3 folds to 90 as CONST_INT
4021// * The three arithmetic instructions get DCE'd
4022// * The return's operand is now a constant Value
4023
4024// Library only; self-test lives in opt_test.nx.