nx_opt.nx source

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