code wiki / (root) / nx_x86_regalloc.nx
`nx_x86_regalloc.nx` source

↩ module page · 1833 lines · 84573 B
1// nx_x86_regalloc.nx -- genuine x86_64 register allocation (G1 keystone).
2//
3// FRESH, x86_-prefixed, self-host-isolated: re-implements the proven IDEAS of
4// nx_regalloc.nx (Interval shape, def-to-last-use scan, mark_crosses_call,
5// ValueLoc lowering) with ZERO shared symbols and NO `import "nx_regalloc.nx"`,
6// because regalloc_function is on the live RISC-V self-host bootstrap host
7// (nx_nxc.nx:139, nx_main.nx:64) that compiles the x86 compiler -- re-binding a
8// shared name there would corrupt the host. See docs/NX_G1_X86_REGALLOC_PLAN.
9//
10// ALLOCATE-not-COPY: a homed value LIVES in a callee-saved GPR for its whole
11// live range (producing op computes straight into it -- zero copy), unlike the
12// reverted K=1 cache (movq %reg,%rbx per result, +2018 insns -> net-negative).
13//
14// Home pool = the 5 SysV callee-saved GPRs {r12,r13,r14,r15,rbx} (home idx
15// 0..4) -- none used as scratch/operand/arg/clobber by the x86 backend, so they
16// survive every CALL/SYSCALL/TAIL_CALL/clone with no save-around-call logic.
17// FIX-12 INVARIANT: never add rcx/rdx/rbp/r10/r11 to this pool.
18//
19// THIS IS STEP 1b: full interval analysis (build_intervals + mark_crosses_call
20// + single_block) RUNS over every function -- crash-tested by the self-host
21// fixpoint over the whole corpus -- but its result is DISCARDED: every value
22// lowers to {VL_SPILLED,-1}, mask 0, so emitted code is byte-identical to the
23// pre-regalloc backend. Home selection + emit-path retarget land in STEP 2.
24
25import "nx_syscalls.nx"
26import "nx_types.nx"
27
28// ----- home register pool (SysV callee-saved GPRs) -----------------
29const X86_HOME_CAP: i64 = 5     // {r12,r13,r14,r15,rbx}
30// ----- caller-saved pool (arc stage 2) -----------------------------
31// {rsi,rdi,r8,r9} = home idx 5..8. Only for crosses_call==0 intervals in
32// clobber-intrinsic-free functions; NOT saved in prologue.
33// STAGE 2+3 EXPERIMENTS (2026-07-15) -- BOTH gated OFF (byte-identical to
34// blessed, NO regression). PROVEN by measurement, both crypto-CORRECT (gauntlet
35// 19/19 + fixpoint + bit-exact vs gcc/clang):
36//   - CALLER_POOL (single-block, +4 regs): PERF-NEUTRAL (matmul's pressure is
37//     cross-block, not single-block temps).
38//   - ALLOW_CROSSBLOCK (relax single_block): REGRESSES matmul 4.7x->5.1x (+~6%)
39//     but IMPROVES fnv 0.97x->0.93x. Root: this allocator gives each homed value
40//     a DEDICATED reg for its whole [start,end]; a cross-block value (i*N) then
41//     ties up a reg across the blocks between def and use where it's unused,
42//     starving the k-loop. Crude whole-range homing wastes registers.
43// CONCLUSION: the matmul win needs a REAL allocator (loop-weighted spill cost +
44// live-interval mgmt with holes/splitting), NOT these flags. See
45// project-nishi-nxcc-register-allocation-arc-2026-07-15 "STAGE 4 = the rewrite".
46const X86_CALLER_POOL_ENABLE: i64 = 1
47const X86_ALLOW_CROSSBLOCK: i64 = 1
48// Caller-saved is only worth its home-move overhead for DEEP-loop values. A
49// call-free value may take a caller-saved reg only if wcost >= this (=~ a use at
50// loop depth 2+, 16^2). Keeps tight scalar loops (fnv/divpow2, depth 1) on the
51// baseline callee-only path while matmul's depth-3 k-loop temps (wcost ~4096)
52// still get the extra registers. Callee-saved keeps the lower X86_HOME_MIN_USES.
53const X86_CALLER_MIN_WCOST: i64 = 256
54// NEGATIVE CONTROL: 1 = let cross-call SSA values take caller-saved regs (rsi/rdi/
55// r8/r9) that the call clobbers -> the gauntlet register-survival KAT + crypto
56// KATs MUST go RED. Proves the crosses_call gate is load-bearing. Ships at 0.
57const X86_NEGCTL_CALLER_IGNORE_CALL: i64 = 0
58const X86_CALLER_BASE: i64 = 5
59const X86_CALLER_CAP:  i64 = 4  // idx 5,6,7,8
60// Caller-saved homes have NO save/restore cost, so even a single-use value wins
61// (avoids a spill store + a reload). Lower than X86_HOME_MIN_USES(3), which only
62// existed to amortize the callee-saved prologue push/pop.
63const X86_CALLER_MIN_USES: i64 = 1
64// G20 SLACK ADMISSION -- ATTEMPTED 2026-07-16, REFUTED BY MEASUREMENT, REVERTED.
65// Homing in-loop temps (div results + non-adjacent single-use) into idle caller
66// regs converted divpow2's 12 spill/reload into +7 copies (39->38, ~nothing)
67// AND regressed collatz 17->18 + fnv 13->14: a home INSERTS a movq exactly
68// where the G1/G4/G16 rax-forwarding was already zero-cost, and no static
69// adjacency test can see emitter forwarding state (phase order). The honest
70// fix is the STAGE-4 allocator rewrite; until then, EXTEND forwarding
71// (commute-consume, cmov-dance) instead of blanket-homing. Arc memo rung 26.
72
73func x86_home_reg_name(idx: i64) -> *u8 {
  if idx == 0 { return "r12" as *u8 }
  if idx == 1 { return "r13" as *u8 }
  if idx == 2 { return "r14" as *u8 }
  if idx == 3 { return "r15" as *u8 }
  if idx == 4 { return "rbx" as *u8 }
  // CALLER-SAVED pool (2026-07-15, reg-alloc arc stage 2): home idx 5..8.
  // Assigned ONLY to intervals with crosses_call==0 in functions with no
  // GP-clobbering intrinsic -> never live across a call/intrinsic that would
  // clobber them -> need NO prologue save (kept OUT of used_cs_mask). Verified
  // the common emit path (load/store/binop) never touches these; they appear
  // only in intrinsics (thread-clone=call-class, f32x8-dot, byte-shuffle,
  // mul256) and _start. rdx/rcx/r10/r11 stay scratch (FIX-12).
  if idx == 5 { return "rsi" as *u8 }
  if idx == 6 { return "rdi" as *u8 }
  if idx == 7 { return "r8"  as *u8 }
  if idx == 8 { return "r9"  as *u8 }
  return 0 as *u8
91}
92
93// Compare two short register-name strings (<= 7 chars + NUL). 1 = equal.
94func x86_reg_eq(a: *u8, b: *u8) -> i64 {
  var i: i64 = 0
  while i < 8 {
      if a[i] != b[i] { return 0 }
      if a[i] == 0 { return 1 }
      i = i + 1
  }
  return 1
102}
103
104// FIX-6: COMPACTED save offset, keyed on the running slot_index 0..n_saved-1
105// (ascending mask-bit order), NOT on the home index -- ONE scheme for save AND
106// restore so a non-contiguous home subset still maps cleanly.
107func x86_home_save_off(slot_index: i64) -> i64 {
  return 0 - (8 * (slot_index + 1))
109}
110
111func x86_popcount(mask: i64) -> i64 {
  var n: i64 = 0
  var m: i64 = mask
  var b: i64 = 0
  while b < X86_HOME_CAP {
      if (m & 1) == 1 { n = n + 1 }
      m = m >> 1
      b = b + 1
  }
  return n
121}
122
123// ----- per-value live interval (x86-local; 7 i64 = 56 bytes) -------
124struct X86Interval {
  v:            i64,
  start:        i64,
  end:          i64,
  reg:          i64,    // home index 0..4, or -1
  slot:         i64,
  crosses_call: i64,
  single_block: i64,    // 1 iff every def/use of v lives in one basic block
  use_count:    i64,    // # of operand appearances (reload-density proxy)
133}
134
135func x86_intv_at(buf: *X86Interval, id: i64) -> *X86Interval {
  let base: i64 = buf as i64
  return (base + id * 64) as *X86Interval
138}
139
140// value/block accessors (own copies -- NOT the ctx's, which is imported AFTER us)
141func x86_val_at(f: *Function, id: i64) -> *Value {
  let base: i64 = f.values as i64
  return (base + id * 48) as *Value           // Value = 48 bytes
144}
145func x86_block_at(f: *Function, id: i64) -> *BasicBlock {
  let base: i64 = f.blocks as i64
  return (base + id * 96) as *BasicBlock       // BasicBlock = 96 bytes
148}
149
150// k-th operand slot (op0..op15).
151func x86_operand_k(inst: *Instr, k: i64) -> i64 {
  if k == 0  { return inst.op0 }
  if k == 1  { return inst.op1 }
  if k == 2  { return inst.op2 }
  if k == 3  { return inst.op3 }
  if k == 4  { return inst.op4 }
  if k == 5  { return inst.op5 }
  if k == 6  { return inst.op6 }
  if k == 7  { return inst.op7 }
  if k == 8  { return inst.op8 }
  if k == 9  { return inst.op9 }
  if k == 10 { return inst.op10 }
  if k == 11 { return inst.op11 }
  if k == 12 { return inst.op12 }
  if k == 13 { return inst.op13 }
  if k == 14 { return inst.op14 }
  if k == 15 { return inst.op15 }
  if k == 16 { return inst.op16 }
  if k == 17 { return inst.op17 }
  if k == 18 { return inst.op18 }
  if k == 19 { return inst.op19 }
  if k == 20 { return inst.op20 }
  if k == 21 { return inst.op21 }
  if k == 22 { return inst.op22 }
  if k == 23 { return inst.op23 }
  return 0 - 1
177}
178
179// FIX-3: how many LEADING operands are real Value ids (not block ids).
180// OP_BR's operand is a block id; OP_BR_COND is (cond_value, true_bb, false_bb)
181// -> only op0 is a Value. Everything else: op0..op(n_operands-1), capped at 24.
182func x86_n_value_operands(inst: *Instr) -> i64 {
  if inst.op == OP_BR { return 0 }
  if inst.op == OP_BR_COND { return 1 }
  let n: i64 = inst.n_operands
  if n > 24 { return 24 }
  if n < 0 { return 0 }
  return n
189}
190
191// True for caller-saved-clobbering ops whose value operands must be flagged
192// not-homeable in cut 1 (FIX-3/FIX-5): CALL, TAIL_CALL, SYSCALL, THREAD_CLONE.
193func x86_is_call_class(op: i64) -> i64 {
  if op == OP_CALL { return 1 }
  if op == OP_TAIL_CALL { return 1 }
  if op == OP_SYSCALL { return 1 }
  if op == OP_THREAD_CLONE { return 1 }
  if op == OP_CALL_INDIRECT { return 1 }
  return 0
200}
201
202func x86_touch_bb(first_bb: *i64, last_bb: *i64, v: i64, bi: i64) -> i64 {
  if first_bb[v] < 0 { first_bb[v] = bi }
  last_bb[v] = bi                            // blocks scanned ascending -> max
  return 0
206}
207
208// ===== SOTA allocator core (2026-07-15): loop-depth-weighted spill cost =====
209// The matmul win: rank homing candidates by DYNAMIC hotness (uses weighted by
210// loop nesting depth) so the deep-loop values (s,k,i*N at depth 3) beat cold
211// setup temps (depth 0) for the scarce registers. Without this, ranking by raw
212// textual use_count homes cold high-count values and spills the hot loop-carried
213// ones. Loop depth is a back-edge heuristic (SAFE: only affects PRIORITY, never
214// correctness -- a wrong depth = suboptimal alloc, never a miscompile).
215
216// Loop nesting depth per block. A back-edge = a terminator branch to a block
217// with id <= the source (RPO-ish block order); its body = [tid, bi] gets +1.
218func x86_compute_loop_depth(f: *Function, depth: *i64) -> i64 {
  var bi: i64 = 0
  while bi < f.n_blocks { depth[bi] = 0; bi = bi + 1 }
  bi = 0
  while bi < f.n_blocks {
      let b: *BasicBlock = x86_block_at(f, bi)
      let t: *Instr = b.tail
      if t != (0 as *Instr) {
          var nt: i64 = 0
          var t0: i64 = 0 - 1
          var t1: i64 = 0 - 1
          if t.op == OP_BR { t0 = t.op0; nt = 1 }
          if t.op == OP_BR_COND { t0 = t.op1; t1 = t.op2; nt = 2 }
          var ti: i64 = 0
          while ti < nt {
              var tid: i64 = t0
              if ti == 1 { tid = t1 }
              if tid >= 0 { if tid <= bi {
                  var j: i64 = tid
                  while j <= bi { depth[j] = depth[j] + 1; j = j + 1 }
              } }
              ti = ti + 1
          }
      }
      bi = bi + 1
  }
  return 0
245}
246
247// 16^depth, capped at depth 10 (=2^40, safe in i64). Each loop level ~16x.
248func x86_weight_for_depth(d: i64) -> i64 {
  var dd: i64 = d
  if dd > 10 { dd = 10 }
  return 1 << (dd * 4)
252}
253
254// wcost[v] = Σ over every operand appearance of v of 16^(loop depth of that use's
255// block). This is the spill-cost proxy that ranks homing candidates.
256func x86_compute_wcost(f: *Function, depth: *i64, wcost: *i64) -> i64 {
  let n: i64 = f.n_values
  var v: i64 = 0
  while v < n { wcost[v] = 0; v = v + 1 }
  var bi: i64 = 0
  while bi < f.n_blocks {
      let w: i64 = x86_weight_for_depth(depth[bi])
      let b: *BasicBlock = x86_block_at(f, bi)
      var inst: *Instr = b.head
      while inst != (0 as *Instr) {
          let nv: i64 = x86_n_value_operands(inst)
          var k: i64 = 0
          while k < nv {
              let u: i64 = x86_operand_k(inst, k)
              if u >= 0 { if u < n { wcost[u] = wcost[u] + w } }
              k = k + 1
          }
          inst = inst.next
      }
      bi = bi + 1
  }
  return 0
278}
279
280// ----- interval construction (def-to-last-use + single_block) ------
281// Mirrors nx_regalloc.nx:175-267 with FIX-3 (opcode-aware operands), FIX-4
282// (independent single_block scan), FIX-5 (all call-class sites), FIX-8 (bounds).
283func x86_build_intervals(f: *Function, intv: *X86Interval,
                       calls: *i64, n_calls_ptr: *i64, any_call: *i64,
                       bb_start: *i64, bb_end: *i64) -> i64 {
  let n: i64 = f.n_values
  var v: i64 = 0
  while v < n {
      let iv: *X86Interval = x86_intv_at(intv, v)
      iv.v = v
      iv.start = 0 - 1
      iv.end = 0 - 1
      iv.reg = 0 - 1
      iv.slot = 0 - 1
      iv.crosses_call = 0
      iv.single_block = 0
      iv.use_count = 0
      any_call[v] = 0
      v = v + 1
  }
  // Parameters are live from index 0.
  v = 0
  while v < n {
      let vv: *Value = x86_val_at(f, v)
      if vv.kind == VK_PARAM {
          let iv: *X86Interval = x86_intv_at(intv, v)
          iv.start = 0
          iv.end = 0
      }
      v = v + 1
  }
312
  // Pass 1: linear def-to-last-use, call-site recording, bb ranges.
  var idx: i64 = 1
  var bi: i64 = 0
  var n_calls: i64 = 0
  while bi < f.n_blocks {
      let b: *BasicBlock = x86_block_at(f, bi)
      bb_start[bi] = idx
      var inst: *Instr = b.head
      while inst != (0 as *Instr) {
          // Def: the instruction's (non-void) result.
          if inst.ty != (0 as *Type) {
              if inst.ty.kind != 0 {
                  let r: i64 = inst.result
                  if r >= 0 { if r < n {
                      let rv: *X86Interval = x86_intv_at(intv, r)
                      if rv.start < 0 { rv.start = idx }
                      if rv.end < idx { rv.end = idx }
                  } }
              }
          }
          // Uses: opcode-aware value operands (FIX-3), bounds-guarded (FIX-8).
          let nv: i64 = x86_n_value_operands(inst)
          var k: i64 = 0
          while k < nv {
              let u: i64 = x86_operand_k(inst, k)
              if u >= 0 { if u < n {
                  let uv: *X86Interval = x86_intv_at(intv, u)
                  if uv.start < 0 { uv.start = idx }
                  if uv.end < idx { uv.end = idx }
                  uv.use_count = uv.use_count + 1
              } }
              k = k + 1
          }
          // Call-class sites (FIX-5) + flag their value operands (FIX-3).
          if x86_is_call_class(inst.op) == 1 {
              calls[n_calls] = idx
              n_calls = n_calls + 1
              var ck: i64 = 0
              while ck < nv {
                  let cu: i64 = x86_operand_k(inst, ck)
                  if cu >= 0 { if cu < n { any_call[cu] = 1 } }
                  ck = ck + 1
              }
          }
          idx = idx + 1
          inst = inst.next
      }
      bb_end[bi] = idx - 1
      bi = bi + 1
  }
  *n_calls_ptr = n_calls
364
  // Pass 2 (FIX-4): single_block via an INDEPENDENT full op0..op(nv-1) scan of
  // every instruction -- NOT derived from the (possibly truncated) use record.
  let fb_raw: *u8 = sys_mmap(n * 8 + 16)
  let first_bb: *i64 = fb_raw as *i64
  let lb_raw: *u8 = sys_mmap(n * 8 + 16)
  let last_bb: *i64 = lb_raw as *i64
  v = 0
  while v < n { first_bb[v] = 0 - 1; last_bb[v] = 0 - 1; v = v + 1 }
  bi = 0
  while bi < f.n_blocks {
      let b: *BasicBlock = x86_block_at(f, bi)
      var inst: *Instr = b.head
      while inst != (0 as *Instr) {
          if inst.ty != (0 as *Type) {
              if inst.ty.kind != 0 {
                  let r: i64 = inst.result
                  if r >= 0 { if r < n { x86_touch_bb(first_bb, last_bb, r, bi) } }
              }
          }
          let nv2: i64 = x86_n_value_operands(inst)
          var k2: i64 = 0
          while k2 < nv2 {
              let u2: i64 = x86_operand_k(inst, k2)
              if u2 >= 0 { if u2 < n { x86_touch_bb(first_bb, last_bb, u2, bi) } }
              k2 = k2 + 1
          }
          inst = inst.next
      }
      bi = bi + 1
  }
  v = 0
  while v < n {
      let iv: *X86Interval = x86_intv_at(intv, v)
      if first_bb[v] >= 0 {
          if first_bb[v] == last_bb[v] { iv.single_block = 1 }
      }
      v = v + 1
  }
  return idx
404}
405
406// ===== BACK-EDGE INTERVAL EXTENSION (2026-07-15, STOP-SHIP fix) ======
407// ROOT CAUSE of the br_table-zeroing miscompile (found by S18 via the wat
408// lane; bisected to R10): build_intervals' [start,end] is def-to-last-use in
409// LINEAR order, but a value live ACROSS A BACK-EDGE (def before/hoisted out
410// of a loop, used inside it) is live through the WHOLE loop body at runtime
411// -- including CALLS positioned after its last linear use. crosses_call then
412// under-counts -> the value gets a CALLER-SAVED reg -> the uncounted call
413// clobbers it -> next iteration reads garbage/zero. The old single_block gate
414// masked exactly this; R10's cross-block relaxation exposed it. FIX: for
415// every backward branch bi -> tid, any interval that overlaps the loop span
416// [bb_start[tid], bb_end[bi]] but ends inside it is EXTENDED to the loop end,
417// so crosses_call sees every call in the loop. Conservative: extension can
418// only DENY caller-saved (push a value to callee-saved/spill), never allow
419// more. Callee-saved homes were never affected (dedicated + call-preserved).
420// ⚠MOVED UP 2026-07-20 -- THIS NEGATIVE CONTROL COULD NEVER FIRE. It was declared ~827 lines BELOW
421// (beside its siblings) while its ONLY reader is the very next line. A module const read ABOVE its
422// declaration silently resolves to 0, so flipping it to 1 was ignored: the negctl could not
423// reintroduce the miscompile it exists to reintroduce, and any gate row leaning on it was VACUOUSLY
424// GREEN. Its own sibling comment says this family "kills the 'the guard never fires, green is
425// vacuous' liar" -- this member WAS that liar. Found by the new forward-const diagnostic.
426// NEGATIVE CONTROL: 1 = skip the back-edge interval extension -> reintroduces the br_table-zeroing
427// miscompile (caller-saved clobbered across a back-edge) -> the gauntlet's WAT byte-exact row goes
428// RED. Ships at 0.
429const X86_NEGCTL_NO_BACKEDGE_EXT: i64 = 0
430
431func x86_extend_backedge_intervals(f: *Function, intv: *X86Interval,
                                 bb_start: *i64, bb_end: *i64) -> i64 {
  if X86_NEGCTL_NO_BACKEDGE_EXT == 1 { return 0 }
  var bi: i64 = 0
  while bi < f.n_blocks {
      let b: *BasicBlock = x86_block_at(f, bi)
      let t: *Instr = b.tail
      if t != (0 as *Instr) {
          var nt: i64 = 0
          var t0: i64 = 0 - 1
          var t1: i64 = 0 - 1
          if t.op == OP_BR { t0 = t.op0; nt = 1 }
          if t.op == OP_BR_COND { t0 = t.op1; t1 = t.op2; nt = 2 }
          var ti: i64 = 0
          while ti < nt {
              var tid: i64 = t0
              if ti == 1 { tid = t1 }
              if tid >= 0 { if tid <= bi { if tid < f.n_blocks {
                  let H: i64 = bb_start[tid]
                  let P: i64 = bb_end[bi]
                  var v: i64 = 0
                  while v < f.n_values {
                      let iv: *X86Interval = x86_intv_at(intv, v)
                      if iv.start >= 0 {
                          if iv.start <= P { if iv.end >= H { if iv.end < P {
                              iv.end = P
                          } } }
                      }
                      v = v + 1
                  }
              } } }
              ti = ti + 1
          }
      }
      bi = bi + 1
  }
  return 0
468}
469
470// crosses_call: any call index strictly after start and at/before end.
471func x86_mark_crosses_call(intv: *X86Interval, n_values: i64,
                         calls: *i64, n_calls: i64) -> i64 {
  var v: i64 = 0
  while v < n_values {
      let iv: *X86Interval = x86_intv_at(intv, v)
      if iv.start >= 0 {
          var c: i64 = 0
          while c < n_calls {
              let ci: i64 = calls[c]
              if ci > iv.start { if ci <= iv.end { iv.crosses_call = 1 } }
              c = c + 1
          }
      }
      v = v + 1
  }
  return 0
487}
488
489// ----- home selection ---------------------------------------------
490// Cut-1 restricts homeable values to results of PURE-RAX binops (the ops whose
491// emitter threads FIX-1 x86ctx_result_reg). Everything else stays spilled.
492func x86_is_pure_rax_binop(op: i64) -> i64 {
  if op == OP_ADD { return 1 }
  if op == OP_SUB { return 1 }
  if op == OP_MUL { return 1 }
  if op == OP_AND { return 1 }
  if op == OP_OR  { return 1 }
  if op == OP_XOR { return 1 }
  return 0
500}
501
502// A value is homeable (cut-1) iff it has a live interval, is single-basic-block,
503// is not a call/syscall/tail/clone operand (FIX-3), is not an alloca (FIX-10),
504// and is produced by a pure-rax binop (so result_reg threading covers it).
505func x86_is_homeable(f: *Function, intv: *X86Interval, alloca_off: *i64,
                   any_call: *i64, v: i64) -> i64 {
  let iv: *X86Interval = x86_intv_at(intv, v)
  if iv.start < 0 { return 0 }
  // STAGE 3: cross-block values are homeable too (dedicated reg for the whole
  // live range is sound under SSA dominance). Old code required single_block.
  if X86_ALLOW_CROSSBLOCK == 0 { if iv.single_block != 1 { return 0 } }
  // NB: a value that is a CALL operand is STILL homeable -- the home is a
  // callee-saved register, so it survives the call (loaded into the arg reg
  // from %home at the call site, retained after). any_call is computed but no
  // longer excludes (the cut-1 exclusion was over-conservative); the register-
  // survival KAT + the self-host fixpoint guard correctness.
  if alloca_off[v] >= 0 { return 0 }
  let val: *Value = x86_val_at(f, v)
  if val.kind != VK_INSTR { return 0 }
  let inst: *Instr = val.instr
  if inst == (0 as *Instr) { return 0 }
  // STAGE 5 attempt (2026-07-15) REVERTED: homing 8-byte LOAD results (emit_load
  // targets result_reg) showed NO matmul benefit (3.40× vs 3.42×) AND broke the
  // self-host fixpoint [C] (miscompiles the compiler on some pattern the KATs
  // don't hit). Not worth a self-host miscompile for zero gain. The emit_load
  // dst-plumbing is left in (inert: result_reg = rax for every unhomed value, so
  // dst==rax for all loads now that loads aren't homeable -> byte-identical). To
  // retry: re-add OP_LOAD here + root-cause the self-host miscompile first.
  if x86_is_pure_rax_binop(inst.op) == 0 { return 0 }
  return 1
531}
532
533// Does function f contain any op whose hand-written intrinsic emitter clobbers a
534// GP caller-saved reg (rsi/rdi/r8/r9)? CONSERVATIVE: the whole SIMD/crypto
535// intrinsic family (nx_x86_64_ctx dispatch 2439-2455) is treated as clobbering,
536// so a function using ANY of them keeps the current 5-callee-saved behavior and
537// the caller-saved pool is disabled for it. OP_THREAD_CLONE/SYSCALL are already
538// call-class (caught by crosses_call), so they need not appear here. matmul uses
539// none -> gets the full pool. The gauntlet + negative control validate soundness.
540func x86_op_clobbers_caller_saved(op: i64) -> i64 {
  if op == OP_F32X4_DOT { return 1 }
  if op == OP_I8DOT32 { return 1 }
  if op == OP_I8DOT32A { return 1 }
  if op == OP_I8FMA32 { return 1 }
  if op == OP_Q8ROWDOT { return 1 }
  if op == OP_Q5UNPACK32 { return 1 }
  if op == OP_F32X8_DOT { return 1 }
  if op == OP_F32X8_FMA { return 1 }
  if op == OP_F32X8_HSUM { return 1 }
  if op == OP_I16X16_MADD { return 1 }
  if op == OP_AES128_ENC_BLOCK { return 1 }
  if op == OP_SHA256_NI_BLOCK { return 1 }
  if op == OP_MUL256_WIDE { return 1 }
  if op == OP_CLMUL_LL { return 1 }
  if op == OP_CLMUL_HH { return 1 }
  if op == OP_CLMUL_LH { return 1 }
  if op == OP_CLMUL_HL { return 1 }
  return 0
559}
560
561func x86_fn_has_clobber_intrinsic(f: *Function) -> i64 {
  var bi: i64 = 0
  while bi < f.n_blocks {
      let b: *BasicBlock = x86_block_at(f, bi)
      var inst: *Instr = b.head
      while inst != (0 as *Instr) {
          if x86_op_clobbers_caller_saved(inst.op) == 1 { return 1 }
          inst = inst.next
      }
      bi = bi + 1
  }
  return 0
573}
574
575// HOMING GATE -- ON. The full register-allocation machinery (consume-side op1
576// folding, use-count top-K selection, multi-home r12..rbx, call-operand values
577// allowed since homes are callee-saved) COMPOSES with the optimizer (opt_run,
578// enabled in nx_compile_x86.nx) for the WIN: opt's mem2reg promotes alloca'd
579// state to SSA values, and this allocator homes them. Measured on the point-loop
580// vs the pre-opt baseline (bench/nx_codegen_ab.sh): -672 insns (-13%), -266
581// reloads (-14%) [noise-free], wall-clock 2.5-5.9% faster. CORRECT + determin-
582// istic: full self-host gauntlet green (13/13 differential KATs + byte-stable
583// 2nd-gen fixpoint + register-survival KAT), 5/5 identical sha256 compiles.
584// Neither pass alone wins -- regalloc-alone is neutral (allocas stay in memory),
585// opt-alone REGRESSES ~6% (promoted SSA values spill without a register home);
586// only TOGETHER do they win. See docs/NX_G1_X86_REGALLOC_PLAN_2026_05_29.md.
587const X86_HOME_CAP_ENABLE: i64 = 1     // ON: composes with opt_run for the measured crypto win
588const X86_HOME_MIN_USES:   i64 = 3     // require >= this many uses to beat save/restore
589
590// Home up to X86_HOME_CAP eligible values, highest use_count first (most reloads
591// to eliminate), requiring use_count >= X86_HOME_MIN_USES so the per-function
592// callee-saved save/restore is amortised. Assigns home indices 0..K-1 (r12..rbx)
593// and sets the corresponding mask bits. Deterministic: strict > keeps the lowest
594// id on ties (ascending scan).
595func x86_select_homes(f: *Function, intv: *X86Interval, alloca_off: *i64,
                    any_call: *i64, used_cs_mask_out: *i64, wcost: *i64) -> i64 {
  *used_cs_mask_out = 0
  if X86_HOME_CAP_ENABLE == 0 { return 0 }
  var assigned: i64 = 0
  var stop0: i64 = 0
  while assigned < X86_HOME_CAP {
      if stop0 == 0 {
          var best: i64 = 0 - 1
          var best_uc: i64 = 0 - 1
          var v: i64 = 0
          while v < f.n_values {
              let iv: *X86Interval = x86_intv_at(intv, v)
              if iv.reg < 0 {
                  if x86_is_homeable(f, intv, alloca_off, any_call, v) == 1 {
                      // RANK BY LOOP-DEPTH-WEIGHTED COST (SOTA): a deep-loop
                      // value beats a cold high-textual-count one.
                      if wcost[v] > best_uc {
                          best = v
                          best_uc = wcost[v]
                      }
                  }
              }
              v = v + 1
          }
          if best < 0 { stop0 = 1 }
          if best_uc < X86_HOME_MIN_USES { stop0 = 1 }
          if stop0 == 0 {
              let biv: *X86Interval = x86_intv_at(intv, best)
              biv.reg = assigned
              *used_cs_mask_out = *used_cs_mask_out | (1 << assigned)
              assigned = assigned + 1
          }
      }
      if stop0 == 1 { assigned = X86_HOME_CAP }
  }
  // ===== CALLER-SAVED pool (arc stage 2, 2026-07-15) ==============
  // Runs only when all 5 callee-saved were assigned (>5 homeable values =
  // exactly when leftovers exist). Assigns idx 5..8 (rsi/rdi/r8/r9) to the
  // next-highest-use homeable values that DON'T cross a call, in functions
  // with no GP-clobbering intrinsic. NO used_cs_mask bit -> no prologue save
  // (sound: the interval never spans a call/intrinsic that clobbers them).
  if X86_CALLER_POOL_ENABLE == 1 {
      if x86_fn_has_clobber_intrinsic(f) == 0 {
          var cassigned: i64 = 0
          var cstop: i64 = 0
          while cassigned < X86_CALLER_CAP {
              if cstop == 0 {
                  var cbest: i64 = 0 - 1
                  var cbest_uc: i64 = 0 - 1
                  var cv: i64 = 0
                  while cv < f.n_values {
                      let civ: *X86Interval = x86_intv_at(intv, cv)
                      if civ.reg < 0 {
                          if civ.crosses_call == 0 {
                              if x86_is_homeable(f, intv, alloca_off, any_call, cv) == 1 {
                                  if wcost[cv] > cbest_uc {
                                      cbest = cv
                                      cbest_uc = wcost[cv]
                                  }
                              }
                          }
                      }
                      cv = cv + 1
                  }
                  if cbest < 0 { cstop = 1 }
                  if cbest_uc < X86_CALLER_MIN_USES { cstop = 1 }
                  if cstop == 0 {
                      let cbiv: *X86Interval = x86_intv_at(intv, cbest)
                      cbiv.reg = X86_CALLER_BASE + cassigned
                  }
              }
              cassigned = cassigned + 1
          }
      }
  }
  return 0
672}
673
674// ===== G2: ALLOCA HOMING (loop-carried scalar registerization) ======
675// The 2026-05-29 plan's DEEPEST FINDING: in this SSA-no-phi IR the loop-
676// carried hot state lives in ALLOCAS (memory), untouched by SSA-value homing
677// and unreachable by opt_mem2reg_simple (needs phis). G2 homes the alloca's
678// STORAGE ITSELF in a leftover callee-saved register: every full-qword
679// load/store of the var becomes a register move -- no phis needed; loop-
680// carried correctness is by construction (the register IS the storage).
681// Measured motivation: the LCG grounding loop (reference-nishilang-vs-c-
682// codegen-grounding-2026-07-14) runs 20 memory ops/iter, 6 of them the
683// x/acc/i alloca round-trips on the critical dependence chain.
684//
685// Eligibility is a strict WHITELIST -- anything unrecognised disqualifies:
686//   base: the alloca's declared storage type is exactly 8 bytes (i64/ptr).
687//   uses: every appearance of the alloca's value id must be one of
688//     OP_LOAD  op0, 8-byte type  (var read;  emitted as movq %home,%rax)
689//     OP_STORE op0, 8-byte type  (var write; emitted as movq %src,%home)
690//     OP_STORE op1               (value-read; load_value_v derefs the home)
691//     a value-consume operand of a whitelisted op (binop/unop/cmp/br_cond/
692//     return/call/tail_call/call_indirect/copy, syscall args k>=1) -- all
693//     of these materialise operands via x86ctx_load_value_v, which reads
694//     the home register directly.
695//   disqualifiers: OP_GEP base, OP_ADDR_OF (the address escapes), OP_SYSCALL
696//     k==0 (as-address load path), subword load/store, and EVERY op not
697//     whitelisted (SIMD/crypto/atomic/clone: unknown consumption idiom ->
698//     conservatively keep the stack slot).
699// Belt+braces: the as-address path (x86ctx_load_value) plants an undefined-
700// label jump for a homed alloca, so an eligibility miss FAILS THE ASSEMBLE
701// loudly instead of silently miscompiling (the 2026-05-30 SEV1 lesson).
702
703// Value-consume whitelist: ops PROVEN to materialise operands via
704// x86ctx_load_value_v (the home-aware as-value path).
705func x86_ah_value_consume_ok(op: i64) -> i64 {
  if op == OP_ADD { return 1 }
  if op == OP_SUB { return 1 }
  if op == OP_MUL { return 1 }
  if op == OP_DIV_S { return 1 }
  if op == OP_DIV_U { return 1 }
  if op == OP_REM_S { return 1 }
  if op == OP_REM_U { return 1 }
  if op == OP_NEG { return 1 }
  if op == OP_NOT { return 1 }
  if op == OP_AND { return 1 }
  if op == OP_OR  { return 1 }
  if op == OP_XOR { return 1 }
  if op == OP_SHL { return 1 }
  if op == OP_SHR_S { return 1 }
  if op == OP_SHR_U { return 1 }
  if op == OP_EQ { return 1 }
  if op == OP_NE { return 1 }
  if op == OP_LT_S { return 1 }
  if op == OP_LE_S { return 1 }
  if op == OP_GT_S { return 1 }
  if op == OP_GE_S { return 1 }
  if op == OP_BR_COND { return 1 }
  if op == OP_RETURN { return 1 }
  if op == OP_CALL { return 1 }
  if op == OP_TAIL_CALL { return 1 }
  if op == OP_CALL_INDIRECT { return 1 }
  if op == OP_SYSCALL { return 1 }
  if op == OP_COPY { return 1 }
  return 0
735}
736
737// Base eligibility: an OP_ALLOCA whose declared storage is an 8-byte scalar.
738func x86_ah_base_ok(f: *Function, v: i64) -> i64 {
  let val: *Value = x86_val_at(f, v)
  if val.kind != VK_INSTR { return 0 }
  let inst: *Instr = val.instr
  if inst == (0 as *Instr) { return 0 }
  if inst.op != OP_ALLOCA { return 0 }
  let t: *Type = inst.ty
  if t == (0 as *Type) { return 0 }
  if t.kind == TY_VOID { return 0 }
  if t.size != 8 { return 0 }
  return 1
749}
750
751// 1 iff this load/store moves a full 8-byte qword (subword access of a
752// homed register-var has no lowering -> disqualifies).
753func x86_ah_ldst_sz8(inst: *Instr) -> i64 {
  let t: *Type = inst.ty
  if t == (0 as *Type) { return 0 }
  if t.size != 8 { return 0 }
  return 1
758}
759
760// Scan every operand appearance of every alloca; leave elig[v]=1 only for
761// allocas whose EVERY use is whitelisted. cnt[v] = safe-use count (the
762// reload-elimination payoff proxy that ranks candidates).
763func x86_ah_scan(f: *Function, alloca_off: *i64, elig: *i64, cnt: *i64) -> i64 {
  let n: i64 = f.n_values
  var v: i64 = 0
  while v < n {
      elig[v] = 0
      cnt[v] = 0
      if alloca_off[v] >= 0 { elig[v] = x86_ah_base_ok(f, v) }
      v = v + 1
  }
  var bi: i64 = 0
  while bi < f.n_blocks {
      let b: *BasicBlock = x86_block_at(f, bi)
      var inst: *Instr = b.head
      while inst != (0 as *Instr) {
          let nv: i64 = x86_n_value_operands(inst)
          var k: i64 = 0
          while k < nv {
              let u: i64 = x86_operand_k(inst, k)
              if u >= 0 { if u < n { if alloca_off[u] >= 0 {
                  var ok: i64 = 0
                  if inst.op == OP_LOAD { if k == 0 { ok = x86_ah_ldst_sz8(inst) } }
                  if inst.op == OP_STORE {
                      if k == 0 { ok = x86_ah_ldst_sz8(inst) }
                      if k == 1 { ok = 1 }
                  }
                  if ok == 0 { ok = x86_ah_value_consume_ok(inst.op) }
                  if inst.op == OP_SYSCALL { if k == 0 { ok = 0 } }
                  if ok == 1 { cnt[u] = cnt[u] + 1 }
                  if ok == 0 { elig[u] = 0 }
              } } }
              k = k + 1
          }
          inst = inst.next
      }
      bi = bi + 1
  }
  return 0
800}
801
802// Assign LEFTOVER callee-saved homes (bits not taken by SSA-value homing)
803// to eligible allocas, highest safe-use count first, >= X86_HOME_MIN_USES.
804// Deterministic: strict > keeps the lowest value id on ties; lowest free
805// bit each round.
806func x86_ah_select(f: *Function, elig: *i64, cnt: *i64,
                 alloca_home: *i64, mask_ptr: *i64, wcost: *i64) -> i64 {
  if X86_HOME_CAP_ENABLE == 0 { return 0 }
  var round: i64 = 0
  var stopr: i64 = 0
  while round < X86_HOME_CAP {
      if stopr == 0 {
          var bit: i64 = 0 - 1
          var b: i64 = 0
          while b < X86_HOME_CAP {
              if bit < 0 { if ((mask_ptr[0] >> b) & 1) == 0 { bit = b } }
              b = b + 1
          }
          if bit < 0 { stopr = 1 }
          if stopr == 0 {
              var best: i64 = 0 - 1
              var best_c: i64 = 0 - 1
              var v: i64 = 0
              while v < f.n_values {
                  if elig[v] == 1 { if alloca_home[v] < 0 {
                      // RANK BY LOOP-DEPTH-WEIGHTED COST (SOTA): a loop-carried
                      // alloca (s,k used every k-iter) beats a cold one; cnt
                      // (safe-use count) stays the eligibility signal via elig.
                      if wcost[v] > best_c { best = v; best_c = wcost[v] }
                  } }
                  v = v + 1
              }
              if best < 0 { stopr = 1 }
              if best_c < X86_HOME_MIN_USES { stopr = 1 }
              if stopr == 0 {
                  alloca_home[best] = bit
                  mask_ptr[0] = mask_ptr[0] | (1 << bit)
                  round = round + 1
              }
          }
      }
      if stopr == 1 { round = X86_HOME_CAP }
  }
  return 0
845}
846
847// ===== G4: single-use next-instruction temp ELISION =================
848// The emitter materialises EVERY instruction result into a stack slot even
849// when the value is consumed once by the IMMEDIATELY FOLLOWING instruction
850// through the G1 rax-forwarding path -- a dead store per temp (the dominant
851// remaining memory traffic after G2: ~8 dead stores/iter in the LCG loop).
852// elide[v]=1 marks values whose slot store may be SKIPPED because the single
853// consumer is guaranteed to take the G1 path: use_count==1, the use is in
854// the textually NEXT instruction (same block), at a position whose emission
855// loads that operand into RAX as its FIRST rax-touching action. store_result
856// keeps the G1 contract (sets G1_RAX_SLOT without the store); any slot LOAD
857// of an elided value = criterion bug -> loud undefined-label tripwire.
858
859// Ops whose emit loads op0 into rax first via load_value_v (or load_value
860// with the G1 check, for GEP). Binops additionally require the consumer's
861// result to be UNHOMED (dst==rax); cmp/unop/gep results are never homed.
862func x86_g4_is_binop(op: i64) -> i64 {
  if op == OP_ADD { return 1 }
  if op == OP_SUB { return 1 }
  if op == OP_MUL { return 1 }
  if op == OP_DIV_S { return 1 }
  if op == OP_DIV_U { return 1 }
  if op == OP_REM_S { return 1 }
  if op == OP_REM_U { return 1 }
  if op == OP_AND { return 1 }
  if op == OP_OR  { return 1 }
  if op == OP_XOR { return 1 }
  if op == OP_SHL { return 1 }
  if op == OP_SHR_S { return 1 }
  if op == OP_SHR_U { return 1 }
  return 0
877}
878func x86_g4_is_cmp(op: i64) -> i64 {
  if op == OP_EQ { return 1 }
  if op == OP_NE { return 1 }
  if op == OP_LT_S { return 1 }
  if op == OP_LE_S { return 1 }
  if op == OP_GT_S { return 1 }
  if op == OP_GE_S { return 1 }
  return 0
886}
887// dst OP src == src OP dst -- the ops the emitter may operand-swap (G11 chain
888// commute + G21 commuted rax-consume). Defined here (before x86_g4_pos_ok and
889// x86_chain_scan, its two caller clusters) per the defined-before-use rule.
890func x86_chain_op_commutative(op: i64) -> i64 {
  if op == OP_ADD { return 1 }
  if op == OP_MUL { return 1 }
  if op == OP_AND { return 1 }
  if op == OP_OR  { return 1 }
  if op == OP_XOR { return 1 }
  return 0
897}
898// PRODUCER whitelist: ops whose emit leaves the result in RAX with
899// G1_RAX_SLOT still valid at the NEXT instruction -- the only ops whose slot
900// store is safe to elide. EXCLUDES every op whose dispatch clears
901// G1_RAX_SLOT after store (CPUID/RDTSC/CALL/SYSCALL/f32/SIMD/crypto) and every
902// op that produces in a non-rax reg (REM/UMULHI -> rdx). Mirrors the
903// consumer whitelist; both sides must be clean-rax for forwarding to hold.
904func x86_g4_producer_ok(op: i64) -> i64 {
  if op == OP_ADD { return 1 }
  if op == OP_SUB { return 1 }
  if op == OP_MUL { return 1 }
  if op == OP_DIV_S { return 1 }
  if op == OP_DIV_U { return 1 }
  if op == OP_AND { return 1 }
  if op == OP_OR  { return 1 }
  if op == OP_XOR { return 1 }
  if op == OP_SHL { return 1 }
  if op == OP_SHR_S { return 1 }
  if op == OP_SHR_U { return 1 }
  if op == OP_EQ { return 1 }
  if op == OP_NE { return 1 }
  if op == OP_LT_S { return 1 }
  if op == OP_LE_S { return 1 }
  if op == OP_GT_S { return 1 }
  if op == OP_GE_S { return 1 }
  if op == OP_NEG { return 1 }
  if op == OP_NOT { return 1 }
  if op == OP_LOAD { return 1 }
  if op == OP_GEP { return 1 }
  if op == OP_COPY { return 1 }
  return 0
928}
929func x86_g4_pos_ok(jop: i64, k: i64, jres_homed: i64) -> i64 {
  if x86_g4_is_binop(jop) == 1 {
      if jres_homed == 1 { return 0 }
      if k == 0 { return 1 }
      // G21 COMMUTED CONSUME: a commutative consumer reads its op1 straight
      // from rax -- the emitter swaps operands (op0 becomes the src, rax is
      // the dst seed), so the op1 slot store is dead exactly like the k==0
      // case. MUST mirror the emit-side g21 gate in x86ctx_emit_binop (both
      // sides clean-rax, unhomed result); the .G4_elided_slot_load_bug
      // tripwire catches any divergence loudly.
      if k == 1 { if x86_chain_op_commutative(jop) == 1 { return 1 } }
      return 0
  }
  if x86_g4_is_cmp(jop) == 1 {
      if k == 0 { return 1 }
      return 0
  }
  if jop == OP_NEG { if k == 0 { return 1 } return 0 }
  if jop == OP_NOT { if k == 0 { return 1 } return 0 }
  if jop == OP_BR_COND { if k == 0 { return 1 } return 0 }
  if jop == OP_RETURN { if k == 0 { return 1 } return 0 }
  if jop == OP_COPY { if k == 0 { return 1 } return 0 }
  if jop == OP_GEP { if k == 0 { return 1 } return 0 }
  if jop == OP_STORE { if k == 1 { return 1 } return 0 }
  return 0
954}
955
956func x86_g4_elide_scan(f: *Function, locs: *ValueLoc, alloca_off: *i64,
                     intv: *X86Interval, elide: *i64,
                     chain_home: *i64, chain_swap: *i64, fwd_home: *i64) -> i64 {
  let n: i64 = f.n_values
  var v: i64 = 0
  while v < n { elide[v] = 0; v = v + 1 }
  var bi: i64 = 0
  while bi < f.n_blocks {
      let b: *BasicBlock = x86_block_at(f, bi)
      var inst: *Instr = b.head
      while inst != (0 as *Instr) {
          let nxt: *Instr = inst.next
          if nxt != (0 as *Instr) {
              let r: i64 = inst.result
              if r >= 0 { if r < n {
                  var ok: i64 = 1
                  if inst.ty == (0 as *Type) { ok = 0 }
                  if ok == 1 { if inst.ty.kind == TY_VOID { ok = 0 } }
                  if x86_g4_producer_ok(inst.op) == 0 { ok = 0 }
                  let rv: *Value = x86_val_at(f, r)
                  if rv.kind != VK_INSTR { ok = 0 }
                  if alloca_off[r] >= 0 { ok = 0 }
                  if ok == 1 {
                      let rl: *ValueLoc = ((locs as i64) + r * 16) as *ValueLoc
                      if rl.kind == VL_REGISTER { ok = 0 }
                  }
                  if ok == 1 {
                      let riv: *X86Interval = x86_intv_at(intv, r)
                      if riv.use_count != 1 { ok = 0 }
                  }
                  if ok == 1 {
                      var jres_homed: i64 = 0
                      let jr: i64 = nxt.result
                      if jr >= 0 { if jr < n {
                          let jl: *ValueLoc = ((locs as i64) + jr * 16) as *ValueLoc
                          if jl.kind == VL_REGISTER { jres_homed = 1 }
                      } }
                      let nv: i64 = x86_n_value_operands(nxt)
                      var found: i64 = 0
                      var k: i64 = 0
                      while k < nv {
                          if x86_operand_k(nxt, k) == r {
                              if found == 0 {
                                  if x86_g4_pos_ok(nxt.op, k, jres_homed) == 1 { found = 1 }
                              }
                              // G16: a CHAIN-FUSED consumer materializes its
                              // SRC operand via load_value_v(rax) as its FIRST
                              // rax touch (op0 is never materialized -- it IS
                              // the home), so the G1 contract holds at the src
                              // position (op1 normal, op0 swapped). r must not
                              // be homed (checked above) nor forwarded (would
                              // read a home, not rax).
                              if found == 0 {
                                  let cj: i64 = nxt.result
                                  if cj >= 0 { if cj < n { if chain_home[cj] >= 0 {
                                      var srcpos: i64 = 1
                                      if chain_swap[cj] == 1 { srcpos = 0 }
                                      if k == srcpos {
                                          if fwd_home[r] < 0 { found = 1 }
                                      }
                                  } } }
                              }
                          }
                          k = k + 1
                      }
                      if found == 1 { elide[r] = 1 }
                  }
              } }
          }
          inst = nxt
      }
      bi = bi + 1
  }
  return 0
1030}
1031
1032// ===== G5: BIG-CONSTANT HOMING ======================================
1033// A VK_CONST_INT too big for imm32 is re-materialised with a 10-byte movabsq
1034// at EVERY use (per-iteration in loops). Home the hottest such constants in
1035// LEFTOVER callee-saved regs: one movabsq in the prologue, and op1-direct
1036// binop consumption reads the home register with ZERO per-use instructions
1037// (imulq %r15,%rax instead of movabsq+imulq). imm32-fitting constants are
1038// handled by the immediate-folding path in the emitter instead (no reg cost).
1039func x86_g5_imm32_ok(v: i64) -> i64 {
  if v > 2147483647 { return 0 }
  if v < (0 - 2147483648) { return 0 }
  return 1
1043}
1044
1045func x86_g5_select_const_homes(f: *Function, intv: *X86Interval,
                             locs: *ValueLoc, mask_ptr: *i64) -> i64 {
  if X86_HOME_CAP_ENABLE == 0 { return 0 }
  let n: i64 = f.n_values
  // Loop-block map: for every BACKWARD branch bj -> bi (bi <= bj), blocks
  // bi..bj are loop-resident (blocks lay out in creation order; a NishiLang
  // while parses to a contiguous cond..body range, so the interval IS the
  // loop body). A constant's payoff is per-EXECUTION, not per-site: one
  // in-loop movabsq costs every iteration, so in-loop uses weigh 8x --
  // a single hot-loop use clears X86_HOME_MIN_USES; cold single uses don't.
  let lb_raw: *u8 = sys_mmap(f.n_blocks * 8 + 16)
  let lb: *i64 = lb_raw as *i64
  var lbi: i64 = 0
  while lbi < f.n_blocks {
      let lbb: *BasicBlock = x86_block_at(f, lbi)
      var linst: *Instr = lbb.head
      while linst != (0 as *Instr) {
          var tgt: i64 = 0 - 1
          var tgt2: i64 = 0 - 1
          if linst.op == OP_BR { tgt = linst.op0 }
          if linst.op == OP_BR_COND { tgt = linst.op1; tgt2 = linst.op2 }
          if tgt >= 0 { if tgt <= lbi { if tgt < f.n_blocks {
              var m: i64 = tgt
              while m <= lbi { lb[m] = 1; m = m + 1 }
          } } }
          if tgt2 >= 0 { if tgt2 <= lbi { if tgt2 < f.n_blocks {
              var m2: i64 = tgt2
              while m2 <= lbi { lb[m2] = 1; m2 = m2 + 1 }
          } } }
          linst = linst.next
      }
      lbi = lbi + 1
  }
  // direct-consumable op1 uses per value (the payoff metric), loop-weighted
  let du_raw: *u8 = sys_mmap(n * 8 + 16)
  let du: *i64 = du_raw as *i64
  var bi: i64 = 0
  while bi < f.n_blocks {
      let b: *BasicBlock = x86_block_at(f, bi)
      var inst: *Instr = b.head
      while inst != (0 as *Instr) {
          if x86_is_pure_rax_binop(inst.op) == 1 {
              let u: i64 = inst.op1
              if u >= 0 { if u < n {
                  if lb[bi] == 1 { du[u] = du[u] + 8 }
                  if lb[bi] == 0 { du[u] = du[u] + 1 }
              } }
          }
          inst = inst.next
      }
      bi = bi + 1
  }
  var round: i64 = 0
  while round < X86_HOME_CAP {
      var bit: i64 = 0 - 1
      var b2: i64 = 0
      while b2 < X86_HOME_CAP {
          if bit < 0 { if ((mask_ptr[0] >> b2) & 1) == 0 { bit = b2 } }
          b2 = b2 + 1
      }
      if bit < 0 { return 0 }
      var best: i64 = 0 - 1
      var best_c: i64 = 0 - 1
      var v: i64 = 0
      while v < n {
          let val: *Value = x86_val_at(f, v)
          if val.kind == VK_CONST_INT {
              let lv: *ValueLoc = ((locs as i64) + v * 16) as *ValueLoc
              if lv.kind != VL_REGISTER {
                  if x86_g5_imm32_ok(val.const_int) == 0 {
                      if du[v] > best_c { best = v; best_c = du[v] }
                  }
              }
          }
          v = v + 1
      }
      if best < 0 { return 0 }
      if best_c < X86_HOME_MIN_USES { return 0 }
      let bl: *ValueLoc = ((locs as i64) + best * 16) as *ValueLoc
      bl.kind = VL_REGISTER
      bl.idx = bit
      mask_ptr[0] = mask_ptr[0] | (1 << bit)
      round = round + 1
  }
  return 0
1130}
1131
1132// ===== G17: NON-NEGATIVE RANGE ANALYSIS (2026-07-16) =================
1133// The auto-scientist's PROVEN 2.063x spot: signed division by 2^k pays a
1134// 4-instruction sign-bias dance that a provably NON-NEGATIVE dividend never
1135// needs -- gcc -O2 pays it too wherever range isn't visible. This lattice is
1136// DELIBERATELY conservative: only ops that STRUCTURALLY clear or preserve a
1137// zero sign bit qualify; anything that can overflow into the sign bit
1138// (ADD/SUB/MUL/SHL) is EXCLUDED by design, loads are excluded in v1 (the
1139// alloca-store fixpoint is G17b). Wrong answers here are MISCOMPILES -- the
1140// negctl (treat everything as nonneg) must go RED on the battery.
1141const X86_NEGCTL_NONNEG_ALWAYS: i64 = 0
1142
1143func x86_const_ge(f: *Function, v: i64, lo: i64) -> i64 {
  if v < 0 { return 0 }
  if v >= f.n_values { return 0 }
  let val: *Value = x86_val_at(f, v)
  if val.kind != VK_CONST_INT { return 0 }
  if val.const_int >= lo { return 1 }
  return 0
1150}
1151
1152func x86_val_nonneg(f: *Function, v: i64, depth: i64) -> i64 {
  if X86_NEGCTL_NONNEG_ALWAYS == 1 { return 1 }
  if depth <= 0 { return 0 }
  if v < 0 { return 0 }
  if v >= f.n_values { return 0 }
  let val: *Value = x86_val_at(f, v)
  if val.kind == VK_CONST_INT {
      if val.const_int >= 0 { return 1 }
      return 0
  }
  if val.kind != VK_INSTR { return 0 }
  let inst: *Instr = val.instr
  if inst == (0 as *Instr) { return 0 }
  // AND with ANY nonneg operand: a zero sign bit ANDed in stays zero.
  if inst.op == OP_AND {
      if x86_val_nonneg(f, inst.op0, depth - 1) == 1 { return 1 }
      if x86_val_nonneg(f, inst.op1, depth - 1) == 1 { return 1 }
      return 0
  }
  // Logical shift right by a CONST >= 1 kills the sign bit outright; by any
  // count it preserves nonneg. Arithmetic shift right preserves the sign.
  if inst.op == OP_SHR_U {
      if x86_const_ge(f, inst.op1, 1) == 1 { return 1 }
      if x86_val_nonneg(f, inst.op0, depth - 1) == 1 { return 1 }
      return 0
  }
  if inst.op == OP_SHR_S {
      if x86_val_nonneg(f, inst.op0, depth - 1) == 1 { return 1 }
      return 0
  }
  // Signed div of a nonneg by a positive const is nonneg (magnitude shrinks).
  if inst.op == OP_DIV_S {
      if x86_const_ge(f, inst.op1, 1) == 1 {
          if x86_val_nonneg(f, inst.op0, depth - 1) == 1 { return 1 }
      }
      return 0
  }
  // Unsigned div by a const >= 2 clears the top bit regardless of input.
  if inst.op == OP_DIV_U {
      if x86_const_ge(f, inst.op1, 2) == 1 { return 1 }
      return 0
  }
  // rem_u by a positive const is in [0, const) -- nonneg.
  if inst.op == OP_REM_U {
      if x86_const_ge(f, inst.op1, 1) == 1 { return 1 }
      return 0
  }
  // rem_s follows the dividend's sign.
  if inst.op == OP_REM_S {
      if x86_val_nonneg(f, inst.op0, depth - 1) == 1 { return 1 }
      return 0
  }
  return 0
1205}
1206
1207// ===== G10: HOME-FORWARDING (2026-07-15) ============================
1208// The gap tool's verdict: 59-68% of every hot loop is materialization waste,
1209// led by the load-of-homed-alloca triple `movq %home,%rax; movq %rax,slot;
1210// movq slot,%reg`. G10 kills it: a SINGLE-USE, 8-byte LOAD of a G2-HOMED
1211// alloca whose one consumer is IN THE SAME BLOCK at an AUDITED operand
1212// position, with NO intervening store to that alloca and NO intervening
1213// call-class op, emits NOTHING -- the consumer reads the alloca's home
1214// register directly (load_value_v/load_value check fwd_home first).
1215// SOUNDNESS: the home register is DEDICATED to the alloca (never shared,
1216// callee-saved, never scratch), so between the load site and the consumer
1217// site its content changes ONLY on a store-to-the-alloca -- exactly what the
1218// scan forbids. The audited-consumer whitelist guarantees the operand is
1219// materialized via load_value_v/load_value (where the fwd check lives), and
1220// the SIB-shape exclusions below keep displaced-emission folds out.
1221const X86_FWD_ENABLE: i64 = 1
1222// NEGATIVE CONTROL: 1 = scan ignores intervening stores-to-the-alloca -> a
1223// STALE home is forwarded -> nx_homefwd_adversary T1 answers WRONG and the
1224// battery goes RED. Proves the store-guard is load-bearing. Ships at 0.
1225const X86_NEGCTL_FWD_IGNORE_STORE: i64 = 0
1226// NEGATIVE CONTROL 2: 1 = forward from the WRONG home register (idx rotated
1227// within the callee-saved pool) -> every forwarded read yields garbage -> the
1228// battery MUST go RED wherever forwarding fires. Kills the "forwarding never
1229// actually fires, green is vacuous" liar. Ships at 0.
1230const X86_NEGCTL_FWD_WRONG_HOME: i64 = 0
1231
1232// ===== G11: CHAIN IN-PLACE FUSION (2026-07-15, rung 12) =============
1233// The gap tool's next rock (cp=7-9 copies/loop): the loop-carried update
1234// `load A -> binop chain -> store A` still costs a head copy (movq %hA,%dst)
1235// and a tail copy (movq %dst,%hA) plus per-step dst shuffling. G11 fuses the
1236// WHOLE chain onto the home register: each chain binop emits `op src1,%hA`
1237// IN PLACE (op0 never materialized -- it IS hA), the head load and the tail
1238// store emit NOTHING. `x = x*A + C` -> imulq+addq straight on %hx; `i = i+1`
1239// -> one `addq $1,%hi`. SOUNDNESS: the scan requires (a) head load of a
1240// G2-homed 8-byte alloca, result single-use consumed at op0 of an
1241// ADD/SUB/MUL/AND/OR/XOR whose result is again single-use at the next step's
1242// op0, ... terminating in `store A, final`; (b) NO other access to A (load
1243// OR store) inside the window -- hA holds INTERMEDIATE values mid-chain, so
1244// any other reader would see garbage; (c) no call-class op inside; (d) all
1245// same-block. Interleaved instructions that don't touch A are fine (they
1246// write rax/rcx/their own homes, never hA -- homes are dedicated).
1247const X86_CHAIN_ENABLE: i64 = 1
1248// NEGATIVE CONTROL: 1 = ignore the mid-window load-of-A abort -> a chain
1249// containing a second read of A fuses anyway -> that read sees the MUTATED
1250// home -> nx_homefwd_adversary T4 answers WRONG -> battery RED. Ships at 0.
1251const X86_NEGCTL_CHAIN_IGNORE_READ: i64 = 0
1252// NEGATIVE CONTROL: 1 = drop the self-ref chain guard -> `z = z & (z-1)` fuses
1253// in place again (subq $1,%home; andq %home,%home) -> Kernighan popcount
1254// degrades to a decrement -> nx_chain_selfref_adversary goes RED. Kills the
1255// "the guard never fires, green is vacuous" liar. Ships at 0.
1256const X86_NEGCTL_CHAIN_SELFREF_OFF: i64 = 0
1257// (X86_NEGCTL_NO_BACKEDGE_EXT MOVED UP to sit beside its only reader -- it was declared here and
1258//  read 827 lines earlier, so it silently resolved to 0 and could never fire. Do NOT move it back.)
1259
1260func x86_chain_op_ok(op: i64) -> i64 {
  if op == OP_ADD { return 1 }
  if op == OP_SUB { return 1 }
  if op == OP_MUL { return 1 }
  if op == OP_AND { return 1 }
  if op == OP_OR  { return 1 }
  if op == OP_XOR { return 1 }
  return 0
1268}
1269
1270// Commutative subset: the chain value may sit at op1 (const-first canonical
1271// forms like MUL(3,n)); `op src,dst` then computes dst OP src = src OP dst.
1272// SUB excluded (3-n != n-3).
1273// Marks: chain_home[v] = the home idx for IN-PLACE emission of chain binop
1274// results (-1 otherwise); the head load is killed via fwd_home[head]=hA (the
1275// existing G10 kill path); the tail store is suppressed in emit_store via
1276// chain_home[op1] == alloca_home[op0]. Runs AFTER x86_fwd_scan (which inits
1277// fwd_home) so the head-kill write survives.
1278func x86_chain_scan(f: *Function, alloca_off: *i64, alloca_home: *i64,
                  intv: *X86Interval, fwd_home: *i64, chain_home: *i64,
                  chain_swap: *i64) -> i64 {
  var vz: i64 = 0
  while vz < f.n_values { chain_home[vz] = 0 - 1; chain_swap[vz] = 0; vz = vz + 1 }
  if X86_CHAIN_ENABLE == 0 { return 0 }
  var bi: i64 = 0
  while bi < f.n_blocks {
      let b: *BasicBlock = x86_block_at(f, bi)
      var inst: *Instr = b.head
      while inst != (0 as *Instr) {
          if inst.op == OP_LOAD {
              let a: i64 = inst.op0
              if a >= 0 { if a < f.n_values { if alloca_home[a] >= 0 {
                  let lt: *Type = inst.ty
                  if lt != (0 as *Type) { if lt.size == 8 {
                      let r: i64 = inst.result
                      if r >= 0 { if r < f.n_values {
                          let riv: *X86Interval = x86_intv_at(intv, r)
                          if riv.use_count == 1 {
                              // Walk the op0-thread to a store-back of A.
                              var cur: i64 = r
                              var steps: i64 = 0
                              var J: *Instr = inst.next
                              var verdict: i64 = 0   // 0=scan 1=fuse 2=no
                              var term: *Instr = 0 as *Instr
                              while verdict == 0 {
                                  if J == (0 as *Instr) { verdict = 2 }
                                  if verdict == 0 {
                                      if J.op == OP_LOAD { if J.op0 == a {
                                          if X86_NEGCTL_CHAIN_IGNORE_READ == 0 { verdict = 2 }
                                      } }
                                  }
                                  if verdict == 0 {
                                      if J.op == OP_STORE { if J.op0 == a {
                                          if J.op1 == cur {
                                              if steps >= 1 { verdict = 1; term = J }
                                              if steps < 1 { verdict = 2 }
                                          }
                                          if J.op1 != cur { verdict = 2 }
                                      } }
                                  }
                                  if verdict == 0 {
                                      if x86_is_call_class(J.op) == 1 { verdict = 2 }
                                  }
                                  if verdict == 0 {
                                      // Does J consume cur anywhere?
                                      let nv: i64 = x86_n_value_operands(J)
                                      var kk: i64 = 0
                                      var found: i64 = 0
                                      while kk < nv {
                                          if x86_operand_k(J, kk) == cur { found = 1 }
                                          kk = kk + 1
                                      }
                                      if found == 1 {
                                          var ok: i64 = 0
                                          if x86_chain_op_ok(J.op) == 1 {
                                              // straight: chain value at op0
                                              if J.op0 == cur { if J.op1 != cur { ok = 1 } }
                                              // commuted: chain value at op1
                                              // of a COMMUTATIVE op (const-
                                              // first canonical MUL(3,n) etc.)
                                              if ok == 0 {
                                                  if x86_chain_op_commutative(J.op) == 1 {
                                                      if J.op1 == cur { if J.op0 != cur { ok = 1 } }
                                                  }
                                              }
                                              if ok == 1 {
                                                  let civ: *X86Interval = x86_intv_at(intv, cur)
                                                  if civ.use_count != 1 { ok = 0 }
                                                  let jr: i64 = J.result
                                                  if jr < 0 { ok = 0 }
                                                  if jr >= f.n_values { ok = 0 }
                                                  // SELF-REF GUARD (fixes z = z & (z-1) miscompile):
                                                  // the SRC operand (the non-chain operand) must NOT read
                                                  // the alloca `a` being chained. The chain mutates a's home
                                                  // IN PLACE, so any src that resolves to a's value (the head
                                                  // load r, OR any other LOAD of a) reads the MUTATED home,
                                                  // not the original z -- `z&(z-1)`, `(z-1)&z`, `z^(z+1)` all
                                                  // route a second read of z into a step's src. Legit chains
                                                  // (s += arr[i]) load a DIFFERENT alloca, so are unaffected.
                                                  if X86_NEGCTL_CHAIN_SELFREF_OFF == 0 {
                                                      var chsrc: i64 = J.op1
                                                      if J.op0 != cur { chsrc = J.op0 }
                                                      if chsrc == r { ok = 0 }
                                                      if chsrc >= 0 { if chsrc < f.n_values {
                                                          let sv: *Value = x86_val_at(f, chsrc)
                                                          if sv.kind == VK_INSTR {
                                                              let si: *Instr = sv.instr
                                                              if si != (0 as *Instr) {
                                                                  if si.op == OP_LOAD { if si.op0 == a { ok = 0 } }
                                                              }
                                                          }
                                                      } }
                                                  }
                                              }
                                          }
                                          if ok == 1 { cur = J.result; steps = steps + 1 }
                                          if ok == 0 { verdict = 2 }
                                      }
                                  }
                                  if verdict == 0 { J = J.next }
                              }
                              if verdict == 1 {
                                  // Final value must be single-use (the store).
                                  let fiv: *X86Interval = x86_intv_at(intv, cur)
                                  if fiv.use_count == 1 {
                                      let hA: i64 = alloca_home[a]
                                      fwd_home[r] = hA           // kill the head load
                                      // Mark every chain binop for in-place emit.
                                      var C2: *Instr = inst.next
                                      var prev: i64 = r
                                      var marking: i64 = 1
                                      while marking == 1 {
                                          if C2 == (0 as *Instr) { marking = 0 }
                                          if marking == 1 {
                                              if C2 == term { marking = 0 }
                                          }
                                          if marking == 1 {
                                              if x86_chain_op_ok(C2.op) == 1 {
                                                  var mk: i64 = 0
                                                  var sw: i64 = 0
                                                  if C2.op0 == prev { if C2.op1 != prev { mk = 1 } }
                                                  if mk == 0 {
                                                      if x86_chain_op_commutative(C2.op) == 1 {
                                                          if C2.op1 == prev { if C2.op0 != prev { mk = 1; sw = 1 } }
                                                      }
                                                  }
                                                  if mk == 1 {
                                                      chain_home[C2.result] = hA
                                                      chain_swap[C2.result] = sw
                                                      prev = C2.result
                                                  }
                                              }
                                              C2 = C2.next
                                          }
                                      }
                                  }
                              }
                          }
                      } }
                  } }
              } } }
          }
          inst = inst.next
      }
      bi = bi + 1
  }
  return 0
1427}
1428
1429// Is value id `u` a VK_CONST_INT equal to one of up to 4 given values?
1430func x86_fwd_const_in(f: *Function, u: i64, a: i64, b: i64, c2: i64, d: i64) -> i64 {
  if u < 0 { return 0 }
  if u >= f.n_values { return 0 }
  let v: *Value = x86_val_at(f, u)
  if v.kind != VK_CONST_INT { return 0 }
  let x: i64 = v.const_int
  if x == a { return 1 }
  if x == b { return 1 }
  if x == c2 { return 1 }
  if x == d { return 1 }
  return 0
1441}
1442
1443// Is value id `u` produced by an instruction that a SIB fold could consume
1444// (SHL by 0..3 / MUL by 1,2,4,8)? Used to keep forwarded values out of any
1445// shape the G8 SIB probe might fold (folds emit DISPLACED, at the load/store
1446// site, possibly past a store-to-the-alloca -- unsound for forwarding).
1447func x86_fwd_is_sibish(f: *Function, u: i64) -> i64 {
  if u < 0 { return 0 }
  if u >= f.n_values { return 0 }
  let v: *Value = x86_val_at(f, u)
  if v.kind != VK_INSTR { return 0 }
  let inst: *Instr = v.instr
  if inst == (0 as *Instr) { return 0 }
  if inst.op == OP_SHL {
      if x86_fwd_const_in(f, inst.op1, 0, 1, 2, 3) == 1 { return 1 }
  }
  if inst.op == OP_MUL {
      if x86_fwd_const_in(f, inst.op1, 1, 2, 4, 8) == 1 { return 1 }
      if x86_fwd_const_in(f, inst.op0, 1, 2, 4, 8) == 1 { return 1 }
  }
  return 0
1462}
1463
1464// AUDITED consumer positions: (op, k) pairs whose emission materializes the
1465// operand via load_value_v (verified in nx_x86_64_ctx.nx: binop op0 -> dst,
1466// binop op1 -> rcx/direct, cmp op0 -> rax + op1 -> rcx/direct, STORE op1 on
1467// all four paths, RETURN op0). Everything else (GEP/LOAD/STORE addresses,
1468// calls, syscalls, branches, unops, SIMD) is NOT forwarded. SIB exclusions:
1469//  - (SHL,0) with shift 0..3 and (MUL,*) by 1/2/4/8: the instr itself can be
1470//    folded into a SIB address -> displaced emission -> skip.
1471//  - (ADD,k) whose OTHER operand is such a SHL/MUL: LOAD(ADD(ptr,SHL(i,3)))
1472//    folds the ADD too -> skip. (ADD with a non-sib MUL, e.g. k*192, is fine.)
1473func x86_fwd_consumer_ok(f: *Function, J: *Instr, k: i64) -> i64 {
  let op: i64 = J.op
  if op == OP_STORE {
      if k == 1 { return 1 }
      return 0
  }
  if op == OP_RETURN {
      if k == 0 { return 1 }
      return 0
  }
  var binop: i64 = 0
  if op == OP_ADD { binop = 1 }
  if op == OP_SUB { binop = 1 }
  if op == OP_MUL { binop = 1 }
  if op == OP_AND { binop = 1 }
  if op == OP_OR  { binop = 1 }
  if op == OP_XOR { binop = 1 }
  if op == OP_SHL { binop = 1 }
  if op == OP_SHR_S { binop = 1 }
  if op == OP_SHR_U { binop = 1 }
  if op == OP_DIV_S { binop = 1 }
  if op == OP_DIV_U { binop = 1 }
  if op == OP_REM_S { binop = 1 }
  if op == OP_REM_U { binop = 1 }
  var cmp: i64 = 0
  if op == OP_EQ { cmp = 1 }
  if op == OP_NE { cmp = 1 }
  if op == OP_LT_S { cmp = 1 }
  if op == OP_LE_S { cmp = 1 }
  if op == OP_GT_S { cmp = 1 }
  if op == OP_GE_S { cmp = 1 }
  if binop == 0 { if cmp == 0 { return 0 } }
  if k > 1 { return 0 }
  // SIB exclusion 1: the consumer itself is a sib-foldable SHL/MUL.
  if op == OP_SHL {
      if x86_fwd_const_in(f, J.op1, 0, 1, 2, 3) == 1 { return 0 }
  }
  if op == OP_MUL {
      if x86_fwd_const_in(f, J.op1, 1, 2, 4, 8) == 1 { return 0 }
      if x86_fwd_const_in(f, J.op0, 1, 2, 4, 8) == 1 { return 0 }
  }
  // SIB exclusion 2: an ADD whose OTHER operand is a sib-ish SHL/MUL.
  if op == OP_ADD {
      var other: i64 = J.op1
      if k == 1 { other = J.op0 }
      if x86_fwd_is_sibish(f, other) == 1 { return 0 }
  }
  return 1
1521}
1522
1523// The scan. fwd_home[v] = the source alloca's home index for a forwarded
1524// load result, else -1. Runs after select_all (alloca_home final).
1525func x86_fwd_scan(f: *Function, alloca_off: *i64, alloca_home: *i64,
                intv: *X86Interval, fwd_home: *i64) -> i64 {
  var vz: i64 = 0
  while vz < f.n_values { fwd_home[vz] = 0 - 1; vz = vz + 1 }
  if X86_FWD_ENABLE == 0 { return 0 }
  var bi: i64 = 0
  while bi < f.n_blocks {
      let b: *BasicBlock = x86_block_at(f, bi)
      var inst: *Instr = b.head
      while inst != (0 as *Instr) {
          var hidx: i64 = 0 - 1
          if inst.op == OP_LOAD {
              let a: i64 = inst.op0
              if a >= 0 { if a < f.n_values { if alloca_home[a] >= 0 {
                  let lt: *Type = inst.ty
                  if lt != (0 as *Type) { if lt.size == 8 {
                      let r: i64 = inst.result
                      if r >= 0 { if r < f.n_values {
                          let riv: *X86Interval = x86_intv_at(intv, r)
                          if riv.use_count == 1 {
                              // Walk forward to the single consumer.
                              var J: *Instr = inst.next
                              var verdict: i64 = 0    // 0=scan 1=fwd 2=no
                              while verdict == 0 {
                                  if J == (0 as *Instr) { verdict = 2 }
                                  if verdict == 0 {
                                      if J.op == OP_STORE { if J.op0 == a {
                                          if X86_NEGCTL_FWD_IGNORE_STORE == 0 { verdict = 2 }
                                      } }
                                  }
                                  if verdict == 0 {
                                      if x86_is_call_class(J.op) == 1 { verdict = 2 }
                                  }
                                  if verdict == 0 {
                                      let nv: i64 = x86_n_value_operands(J)
                                      var kk: i64 = 0
                                      var found: i64 = 0
                                      var okpos: i64 = 1
                                      while kk < nv {
                                          if x86_operand_k(J, kk) == r {
                                              found = 1
                                              if x86_fwd_consumer_ok(f, J, kk) == 0 { okpos = 0 }
                                          }
                                          kk = kk + 1
                                      }
                                      if found == 1 {
                                          if okpos == 1 { verdict = 1 }
                                          if okpos == 0 { verdict = 2 }
                                      }
                                  }
                                  if verdict == 0 { J = J.next }
                              }
                              if verdict == 1 {
                                  hidx = alloca_home[a]
                                  if X86_NEGCTL_FWD_WRONG_HOME == 1 {
                                      hidx = hidx + 1
                                      if hidx >= X86_HOME_CAP { hidx = 0 }
                                  }
                              }
                          }
                      } }
                  } }
              } } }
          }
          if hidx >= 0 { fwd_home[inst.result] = hidx }
          inst = inst.next
      }
      bi = bi + 1
  }
  return 0
1595}
1596
1597// ===== UNIFIED SOTA SELECTION (2026-07-15) ==========================
1598// Rank ALL homing candidates -- homeable SSA values (iv.reg) AND eligible
1599// allocas (alloca_home) -- TOGETHER by loop-weighted wcost, greedily giving each
1600// the best LEGAL register. Constraints: allocas home their whole-function
1601// storage so they MUST use callee-saved (survives the setup calls); a
1602// cross-call SSA value also needs callee-saved; a call-free SSA value prefers a
1603// caller-saved reg (rsi/rdi/r8/r9, no prologue save) to leave callee-saved for
1604// those that need them. Each homed value gets a DEDICATED register for its whole
1605// range (no two share) -> sound under SSA dominance. This replaces the old
1606// SSA-first-then-alloca two-pass scheme that let cold single-use SSA temps grab
1607// the callee-saved regs the hot loop-carried allocas needed.
1608func x86_select_all(f: *Function, intv: *X86Interval, alloca_off: *i64,
                  any_call: *i64, elig: *i64, alloca_home: *i64,
                  used_cs_mask_out: *i64, wcost: *i64) -> i64 {
  *used_cs_mask_out = 0
  if X86_HOME_CAP_ENABLE == 0 { return 0 }
  let fn_clob: i64 = x86_fn_has_clobber_intrinsic(f)
  var caller_mask: i64 = 0
  var done: i64 = 0
  while done == 0 {
      // Current register availability.
      var free_callee: i64 = 0
      var cb: i64 = 0
      while cb < X86_HOME_CAP {
          if ((used_cs_mask_out[0] >> cb) & 1) == 0 { free_callee = free_callee + 1 }
          cb = cb + 1
      }
      var free_caller: i64 = 0
      if X86_CALLER_POOL_ENABLE == 1 { if fn_clob == 0 {
          var qb: i64 = 0
          while qb < X86_CALLER_CAP {
              if ((caller_mask >> qb) & 1) == 0 { free_caller = free_caller + 1 }
              qb = qb + 1
          }
      } }
      // Pick the highest-wcost PLACEABLE candidate.
      var best: i64 = 0 - 1
      var best_w: i64 = 0 - 1
      var best_alloca: i64 = 0
      var best_needs_callee: i64 = 0
      var v: i64 = 0
      while v < f.n_values {
          let iv: *X86Interval = x86_intv_at(intv, v)
          var is_cand: i64 = 0
          var is_alloca: i64 = 0
          if alloca_off[v] >= 0 {
              if elig[v] == 1 { if alloca_home[v] < 0 { is_cand = 1; is_alloca = 1 } }
          }
          if alloca_off[v] < 0 {
              if iv.reg < 0 { if x86_is_homeable(f, intv, alloca_off, any_call, v) == 1 { is_cand = 1 } }
              // G13 (2026-07-16): BIG CONSTANTS compete for homes by wcost
              // like everything else -- a non-imm32 const re-materializes a
              // 10-byte movabsq at EVERY use (per-iteration in loops). The
              // prologue materializer + VL_REGISTER read path already exist
              // (G5); the old G5 selector only got LEFTOVER regs, which the
              // unified allocator never leaves. crosses_call gates caller-
              // saved exactly as for SSA values (read-only, but a clobbered
              // caller-saved home would still read garbage).
              if is_cand == 0 { if iv.reg < 0 { if iv.start >= 0 {
                  let g13v: *Value = x86_val_at(f, v)
                  if g13v.kind == VK_CONST_INT {
                      if x86_g5_imm32_ok(g13v.const_int) == 0 { is_cand = 1 }
                  }
              } } }
          }
          if is_cand == 1 {
              var nc: i64 = 0
              if is_alloca == 1 { nc = 1 }
              if is_alloca == 0 { if iv.crosses_call == 1 { if X86_NEGCTL_CALLER_IGNORE_CALL == 0 { nc = 1 } } }
              var placeable: i64 = 0
              if nc == 1 { if free_callee > 0 { placeable = 1 } }
              if nc == 0 {
                  if free_callee > 0 { placeable = 1 }
                  if free_caller > 0 { if wcost[v] >= X86_CALLER_MIN_WCOST { placeable = 1 } }
                  // G13: call-free CONSTANTS take caller-saved at ANY wcost --
                  // read-only, so a caller-saved home has zero move overhead
                  // (no store-back ever; one prologue movabsq). MUST mirror
                  // the chosen-branch exemption below or the pick loop hangs.
                  if placeable == 0 { if free_caller > 0 {
                      let g13p: *Value = x86_val_at(f, v)
                      if g13p.kind == VK_CONST_INT { placeable = 1 }
                  } }
              }
              if placeable == 1 { if wcost[v] > best_w {
                  best = v; best_w = wcost[v]; best_alloca = is_alloca; best_needs_callee = nc
              } }
          }
          v = v + 1
      }
      if best < 0 { done = 1 }
      if best >= 0 { if best_w < X86_HOME_MIN_USES { done = 1 } }
      if done == 0 {
          var chosen: i64 = 0 - 1
          // Deep-loop call-free SSA prefers caller-saved (leave callee for those
          // needing it); shallow values (wcost < threshold) fall through to
          // callee-only, matching the baseline for tight scalar loops.
          // G13: constants are caller-eligible at ANY wcost (mirrors placeable).
          var cpref: i64 = 0
          if best_needs_callee == 0 { if free_caller > 0 {
              if best_w >= X86_CALLER_MIN_WCOST { cpref = 1 }
              if cpref == 0 {
                  let g13b: *Value = x86_val_at(f, best)
                  if g13b.kind == VK_CONST_INT { cpref = 1 }
              }
          } }
          if cpref == 1 {
              var qb2: i64 = 0
              while qb2 < X86_CALLER_CAP {
                  if chosen < 0 { if ((caller_mask >> qb2) & 1) == 0 {
                      chosen = X86_CALLER_BASE + qb2
                      caller_mask = caller_mask | (1 << qb2)
                  } }
                  qb2 = qb2 + 1
              }
          }
          if chosen < 0 {
              var cb2: i64 = 0
              while cb2 < X86_HOME_CAP {
                  if chosen < 0 { if ((used_cs_mask_out[0] >> cb2) & 1) == 0 {
                      chosen = cb2
                      used_cs_mask_out[0] = used_cs_mask_out[0] | (1 << cb2)
                  } }
                  cb2 = cb2 + 1
              }
          }
          if best_alloca == 1 { alloca_home[best] = chosen }
          if best_alloca == 0 { let biv: *X86Interval = x86_intv_at(intv, best); biv.reg = chosen }
      }
  }
  return 0
1727}
1728
1729// ----- allocator entry (STEP 2b + G2: SSA homes, then alloca homes) ----
1730// alloca_off (authoritative alloca map, FIX-10). alloca_home[v] receives the
1731// G2 home index (0..4) for a registerized alloca, or -1. elide[v]=1 marks
1732// G4 dead-store temps (see x86_g4_elide_scan).
1733func x86_regalloc_function(f: *Function, alloca_off: *i64,
                         locs: *ValueLoc, used_cs_mask_out: *i64,
                         alloca_home: *i64, elide: *i64,
                         fwd_home: *i64, chain_home: *i64, chain_swap: *i64) -> i64 {
  let n: i64 = f.n_values
  let intv_raw: *u8 = sys_mmap(n * 64 + 16)
  let intv: *X86Interval = intv_raw as *X86Interval
  let calls_raw: *u8 = sys_mmap(f.n_instrs * 8 + 32)
  let calls: *i64 = calls_raw as *i64
  let nc_raw: *u8 = sys_mmap(16)
  let nc: *i64 = nc_raw as *i64
  *nc = 0
  let ac_raw: *u8 = sys_mmap(n * 8 + 16)
  let any_call: *i64 = ac_raw as *i64
  let bs_raw: *u8 = sys_mmap(f.n_blocks * 8 + 16)
  let bb_start: *i64 = bs_raw as *i64
  let be_raw: *u8 = sys_mmap(f.n_blocks * 8 + 16)
  let bb_end: *i64 = be_raw as *i64
1751
  x86_build_intervals(f, intv, calls, nc, any_call, bb_start, bb_end)
  // G13: a homed CONST is materialized in the PROLOGUE -- its effective live
  // range is [0, last use], NOT [first use, last use]. Stretch starts to 0 so
  // crosses_call counts SETUP calls too (a caller-saved const home clobbered
  // by a pre-loop syscall's arg setup = the sha256/lcg/fnv miscompile the
  // battery caught 2026-07-16; call-free functions still go caller-saved).
  var g13i: i64 = 0
  while g13i < n {
      let g13iv: *X86Interval = x86_intv_at(intv, g13i)
      if g13iv.start > 0 {
          let g13val: *Value = x86_val_at(f, g13i)
          if g13val.kind == VK_CONST_INT { g13iv.start = 0 }
      }
      g13i = g13i + 1
  }
  // STOP-SHIP fix: extend intervals across back-edges BEFORE the call scan,
  // so loop-internal calls are counted for values live across the edge.
  x86_extend_backedge_intervals(f, intv, bb_start, bb_end)
  x86_mark_crosses_call(intv, n, calls, *nc)
  // SOTA: loop-depth-weighted spill cost drives BOTH SSA and alloca selection.
  let dep_raw: *u8 = sys_mmap(f.n_blocks * 8 + 16)
  let depth: *i64 = dep_raw as *i64
  let wc_raw: *u8 = sys_mmap(n * 8 + 16)
  let wcost: *i64 = wc_raw as *i64
  x86_compute_loop_depth(f, depth)
  x86_compute_wcost(f, depth, wcost)
  // UNIFIED SOTA selection: SSA values AND allocas ranked TOGETHER by
  // loop-weighted wcost. ah_scan first (computes alloca eligibility `elig`),
  // then one pass gives each candidate the best legal register (allocas +
  // cross-call SSA -> callee-saved; call-free SSA prefers caller-saved).
  var ai: i64 = 0
  while ai < n { alloca_home[ai] = 0 - 1; ai = ai + 1 }
  let el_raw: *u8 = sys_mmap(n * 8 + 16)
  let elig: *i64 = el_raw as *i64
  let ct_raw: *u8 = sys_mmap(n * 8 + 16)
  let acnt: *i64 = ct_raw as *i64
  x86_ah_scan(f, alloca_off, elig, acnt)
  x86_select_all(f, intv, alloca_off, any_call, elig, alloca_home, used_cs_mask_out, wcost)
  // G10: home-forwarding scan (needs the FINAL alloca_home + use counts).
  x86_fwd_scan(f, alloca_off, alloca_home, intv, fwd_home)
  // G11: chain fusion scan (runs AFTER fwd_scan -- it writes fwd_home[head]
  // for the chain-head kill and must not be wiped by fwd_scan's init).
  x86_chain_scan(f, alloca_off, alloca_home, intv, fwd_home, chain_home, chain_swap)
1795
  // Lower SSA intervals to ValueLocs: homed (iv.reg>=0) -> VL_REGISTER else spill.
  let lbase: i64 = locs as i64
  var k: i64 = 0
  while k < n {
      let iv: *X86Interval = x86_intv_at(intv, k)
      let l: *ValueLoc = (lbase + k * 16) as *ValueLoc
      if iv.reg >= 0 {
          l.kind = VL_REGISTER
          l.idx = iv.reg
      }
      if iv.reg < 0 {
          l.kind = VL_SPILLED
          l.idx = 0 - 1
      }
      k = k + 1
  }
1812
  // G5: big constants take whatever homes remain.
  x86_g5_select_const_homes(f, intv, locs, used_cs_mask_out)
1815
  // G4: dead single-use temp stores (needs the FINAL locs -- runs last).
  x86_g4_elide_scan(f, locs, alloca_off, intv, elide, chain_home, chain_swap, fwd_home)
  // G10 tripwire: a forwarded (killed) load's slot is NEVER written; flag it
  // elide so any unaudited slot read hits the loud .G4_elided_slot_load_bug
  // link failure instead of silently reading stale stack garbage. (The fwd
  // check in load_value_v/load_value runs BEFORE the elide tripwire, so the
  // one legitimate consumer is unaffected.)
  var tw: i64 = 0
  while tw < n {
      if fwd_home[tw] >= 0 { elide[tw] = 1 }
      // G11 tripwire: chain-internal values never materialize anywhere (the
      // next chain step operates on the home in place); an unaudited slot
      // read must fail loud, not read stale garbage.
      if chain_home[tw] >= 0 { elide[tw] = 1 }
      tw = tw + 1
  }
  return 0
1833}
nx_x86_regalloc.nx source

`nx_x86_regalloc.nx` source
