nx_x86_regalloc.nx source
↩ module page · 2218 lines · 103312 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// STAGE 5: are 8-byte-and-subword LOAD RESULTS eligible for a home register?
31// Named rather than inlined so the retry is one flip in both directions and the
32// equiv net can bisect it. See x86_is_homeable for the root-caused blocker.
33const X86_HOME_LOADS: i64 = 1
34// ----- caller-saved pool (arc stage 2) -----------------------------
35// {rsi,rdi,r8,r9} = home idx 5..8. Only for crosses_call==0 intervals in
36// clobber-intrinsic-free functions; NOT saved in prologue.
37// STAGE 2+3 EXPERIMENTS (2026-07-15) -- BOTH gated OFF (byte-identical to
38// blessed, NO regression). PROVEN by measurement, both crypto-CORRECT (gauntlet
39// 19/19 + fixpoint + bit-exact vs gcc/clang):
40// - CALLER_POOL (single-block, +4 regs): PERF-NEUTRAL (matmul's pressure is
41// cross-block, not single-block temps).
42// - ALLOW_CROSSBLOCK (relax single_block): REGRESSES matmul 4.7x->5.1x (+~6%)
43// but IMPROVES fnv 0.97x->0.93x. Root: this allocator gives each homed value
44// a DEDICATED reg for its whole [start,end]; a cross-block value (i*N) then
45// ties up a reg across the blocks between def and use where it's unused,
46// starving the k-loop. Crude whole-range homing wastes registers.
47// CONCLUSION: the matmul win needs a REAL allocator (loop-weighted spill cost +
48// live-interval mgmt with holes/splitting), NOT these flags. See
49// project-nishi-nxcc-register-allocation-arc-2026-07-15 "STAGE 4 = the rewrite".
50const X86_CALLER_POOL_ENABLE: i64 = 1
51const X86_ALLOW_CROSSBLOCK: i64 = 1
52// Caller-saved is only worth its home-move overhead for DEEP-loop values. A
53// call-free value may take a caller-saved reg only if wcost >= this (=~ a use at
54// loop depth 2+, 16^2). Keeps tight scalar loops (fnv/divpow2, depth 1) on the
55// baseline callee-only path while matmul's depth-3 k-loop temps (wcost ~4096)
56// still get the extra registers. Callee-saved keeps the lower X86_HOME_MIN_USES.
57const X86_CALLER_MIN_WCOST: i64 = 256
58// NEGATIVE CONTROL: 1 = let cross-call SSA values take caller-saved regs (rsi/rdi/
59// r8/r9) that the call clobbers -> the gauntlet register-survival KAT + crypto
60// KATs MUST go RED. Proves the crosses_call gate is load-bearing. Ships at 0.
61const X86_NEGCTL_CALLER_IGNORE_CALL: i64 = 0
62const X86_CALLER_BASE: i64 = 5
63const X86_CALLER_CAP: i64 = 4 // idx 5,6,7,8
64// Caller-saved homes have NO save/restore cost, so even a single-use value wins
65// (avoids a spill store + a reload). Lower than X86_HOME_MIN_USES(3), which only
66// existed to amortize the callee-saved prologue push/pop.
67const X86_CALLER_MIN_USES: i64 = 1
68// G20 SLACK ADMISSION -- ATTEMPTED 2026-07-16, REFUTED BY MEASUREMENT, REVERTED.
69// Homing in-loop temps (div results + non-adjacent single-use) into idle caller
70// regs converted divpow2's 12 spill/reload into +7 copies (39->38, ~nothing)
71// AND regressed collatz 17->18 + fnv 13->14: a home INSERTS a movq exactly
72// where the G1/G4/G16 rax-forwarding was already zero-cost, and no static
73// adjacency test can see emitter forwarding state (phase order). The honest
74// fix is the STAGE-4 allocator rewrite; until then, EXTEND forwarding
75// (commute-consume, cmov-dance) instead of blanket-homing. Arc memo rung 26.
76
77func x86_home_reg_name(idx: i64) -> *u8 {
78 if idx == 0 { return "r12" as *u8 }
79 if idx == 1 { return "r13" as *u8 }
80 if idx == 2 { return "r14" as *u8 }
81 if idx == 3 { return "r15" as *u8 }
82 if idx == 4 { return "rbx" as *u8 }
83 // CALLER-SAVED pool (2026-07-15, reg-alloc arc stage 2): home idx 5..8.
84 // Assigned ONLY to intervals with crosses_call==0 in functions with no
85 // GP-clobbering intrinsic -> never live across a call/intrinsic that would
86 // clobber them -> need NO prologue save (kept OUT of used_cs_mask). Verified
87 // the common emit path (load/store/binop) never touches these; they appear
88 // only in intrinsics (thread-clone=call-class, f32x8-dot, byte-shuffle,
89 // mul256) and _start. rdx/rcx/r10/r11 stay scratch (FIX-12).
90 if idx == 5 { return "rsi" as *u8 }
91 if idx == 6 { return "rdi" as *u8 }
92 if idx == 7 { return "r8" as *u8 }
93 if idx == 8 { return "r9" as *u8 }
94 return 0 as *u8
95}
96
97// Compare two short register-name strings (<= 7 chars + NUL). 1 = equal.
98func x86_reg_eq(a: *u8, b: *u8) -> i64 {
99 var i: i64 = 0
100 while i < 8 {
101 if a[i] != b[i] { return 0 }
102 if a[i] == 0 { return 1 }
103 i = i + 1
104 }
105 return 1
106}
107
108// FIX-6: COMPACTED save offset, keyed on the running slot_index 0..n_saved-1
109// (ascending mask-bit order), NOT on the home index -- ONE scheme for save AND
110// restore so a non-contiguous home subset still maps cleanly.
111func x86_home_save_off(slot_index: i64) -> i64 {
112 return 0 - (8 * (slot_index + 1))
113}
114
115func x86_popcount(mask: i64) -> i64 {
116 var n: i64 = 0
117 var m: i64 = mask
118 var b: i64 = 0
119 while b < X86_HOME_CAP {
120 if (m & 1) == 1 { n = n + 1 }
121 m = m >> 1
122 b = b + 1
123 }
124 return n
125}
126
127// ----- per-value live interval (x86-local; 7 i64 = 56 bytes) -------
128struct X86Interval {
129 v: i64,
130 start: i64,
131 end: i64,
132 reg: i64, // home index 0..4, or -1
133 slot: i64,
134 crosses_call: i64,
135 single_block: i64, // 1 iff every def/use of v lives in one basic block
136 use_count: i64, // # of operand appearances (reload-density proxy)
137}
138
139func x86_intv_at(buf: *X86Interval, id: i64) -> *X86Interval {
140 let base: i64 = buf as i64
141 return (base + id * 64) as *X86Interval
142}
143
144// value/block accessors (own copies -- NOT the ctx's, which is imported AFTER us)
145func x86_val_at(f: *Function, id: i64) -> *Value {
146 let base: i64 = f.values as i64
147 return (base + id * 48) as *Value // Value = 48 bytes
148}
149func x86_block_at(f: *Function, id: i64) -> *BasicBlock {
150 let base: i64 = f.blocks as i64
151 return (base + id * 96) as *BasicBlock // BasicBlock = 96 bytes
152}
153
154// k-th operand slot (op0..op15).
155func x86_operand_k(inst: *Instr, k: i64) -> i64 {
156 if k == 0 { return inst.op0 }
157 if k == 1 { return inst.op1 }
158 if k == 2 { return inst.op2 }
159 if k == 3 { return inst.op3 }
160 if k == 4 { return inst.op4 }
161 if k == 5 { return inst.op5 }
162 if k == 6 { return inst.op6 }
163 if k == 7 { return inst.op7 }
164 if k == 8 { return inst.op8 }
165 if k == 9 { return inst.op9 }
166 if k == 10 { return inst.op10 }
167 if k == 11 { return inst.op11 }
168 if k == 12 { return inst.op12 }
169 if k == 13 { return inst.op13 }
170 if k == 14 { return inst.op14 }
171 if k == 15 { return inst.op15 }
172 if k == 16 { return inst.op16 }
173 if k == 17 { return inst.op17 }
174 if k == 18 { return inst.op18 }
175 if k == 19 { return inst.op19 }
176 if k == 20 { return inst.op20 }
177 if k == 21 { return inst.op21 }
178 if k == 22 { return inst.op22 }
179 if k == 23 { return inst.op23 }
180 return 0 - 1
181}
182
183// FIX-3: how many LEADING operands are real Value ids (not block ids).
184// OP_BR's operand is a block id; OP_BR_COND is (cond_value, true_bb, false_bb)
185// -> only op0 is a Value. Everything else: op0..op(n_operands-1), capped at 24.
186func x86_n_value_operands(inst: *Instr) -> i64 {
187 if inst.op == OP_BR { return 0 }
188 if inst.op == OP_BR_COND { return 1 }
189 let n: i64 = inst.n_operands
190 if n > 24 { return 24 }
191 if n < 0 { return 0 }
192 return n
193}
194
195// True for caller-saved-clobbering ops whose value operands must be flagged
196// not-homeable in cut 1 (FIX-3/FIX-5): CALL, TAIL_CALL, SYSCALL, THREAD_CLONE.
197func x86_is_call_class(op: i64) -> i64 {
198 if op == OP_CALL { return 1 }
199 if op == OP_TAIL_CALL { return 1 }
200 if op == OP_SYSCALL { return 1 }
201 if op == OP_THREAD_CLONE { return 1 }
202 if op == OP_CALL_INDIRECT { return 1 }
203 return 0
204}
205
206func x86_touch_bb(first_bb: *i64, last_bb: *i64, v: i64, bi: i64) -> i64 {
207 if first_bb[v] < 0 { first_bb[v] = bi }
208 last_bb[v] = bi // blocks scanned ascending -> max
209 return 0
210}
211
212// ===== SOTA allocator core (2026-07-15): loop-depth-weighted spill cost =====
213// The matmul win: rank homing candidates by DYNAMIC hotness (uses weighted by
214// loop nesting depth) so the deep-loop values (s,k,i*N at depth 3) beat cold
215// setup temps (depth 0) for the scarce registers. Without this, ranking by raw
216// textual use_count homes cold high-count values and spills the hot loop-carried
217// ones. Loop depth is a back-edge heuristic (SAFE: only affects PRIORITY, never
218// correctness -- a wrong depth = suboptimal alloc, never a miscompile).
219
220// Loop nesting depth per block. A back-edge = a terminator branch to a block
221// with id <= the source (RPO-ish block order); its body = [tid, bi] gets +1.
222func x86_compute_loop_depth(f: *Function, depth: *i64) -> i64 {
223 var bi: i64 = 0
224 while bi < f.n_blocks { depth[bi] = 0; bi = bi + 1 }
225 bi = 0
226 while bi < f.n_blocks {
227 let b: *BasicBlock = x86_block_at(f, bi)
228 let t: *Instr = b.tail
229 if t != (0 as *Instr) {
230 var nt: i64 = 0
231 var t0: i64 = 0 - 1
232 var t1: i64 = 0 - 1
233 if t.op == OP_BR { t0 = t.op0; nt = 1 }
234 if t.op == OP_BR_COND { t0 = t.op1; t1 = t.op2; nt = 2 }
235 var ti: i64 = 0
236 while ti < nt {
237 var tid: i64 = t0
238 if ti == 1 { tid = t1 }
239 if tid >= 0 { if tid <= bi {
240 var j: i64 = tid
241 while j <= bi { depth[j] = depth[j] + 1; j = j + 1 }
242 } }
243 ti = ti + 1
244 }
245 }
246 bi = bi + 1
247 }
248 return 0
249}
250
251// 16^depth, capped at depth 10 (=2^40, safe in i64). Each loop level ~16x.
252func x86_weight_for_depth(d: i64) -> i64 {
253 var dd: i64 = d
254 if dd > 10 { dd = 10 }
255 return 1 << (dd * 4)
256}
257
258// wcost[v] = Σ over every operand appearance of v of 16^(loop depth of that use's
259// block). This is the spill-cost proxy that ranks homing candidates.
260func x86_compute_wcost(f: *Function, depth: *i64, wcost: *i64) -> i64 {
261 let n: i64 = f.n_values
262 var v: i64 = 0
263 while v < n { wcost[v] = 0; v = v + 1 }
264 var bi: i64 = 0
265 while bi < f.n_blocks {
266 let w: i64 = x86_weight_for_depth(depth[bi])
267 let b: *BasicBlock = x86_block_at(f, bi)
268 var inst: *Instr = b.head
269 while inst != (0 as *Instr) {
270 let nv: i64 = x86_n_value_operands(inst)
271 var k: i64 = 0
272 while k < nv {
273 let u: i64 = x86_operand_k(inst, k)
274 if u >= 0 { if u < n { wcost[u] = wcost[u] + w } }
275 k = k + 1
276 }
277 inst = inst.next
278 }
279 bi = bi + 1
280 }
281 return 0
282}
283
284// ----- interval construction (def-to-last-use + single_block) ------
285// Mirrors nx_regalloc.nx:175-267 with FIX-3 (opcode-aware operands), FIX-4
286// (independent single_block scan), FIX-5 (all call-class sites), FIX-8 (bounds).
287func x86_build_intervals(f: *Function, intv: *X86Interval,
288 calls: *i64, n_calls_ptr: *i64, any_call: *i64,
289 bb_start: *i64, bb_end: *i64) -> i64 {
290 let n: i64 = f.n_values
291 var v: i64 = 0
292 while v < n {
293 let iv: *X86Interval = x86_intv_at(intv, v)
294 iv.v = v
295 iv.start = 0 - 1
296 iv.end = 0 - 1
297 iv.reg = 0 - 1
298 iv.slot = 0 - 1
299 iv.crosses_call = 0
300 iv.single_block = 0
301 iv.use_count = 0
302 any_call[v] = 0
303 v = v + 1
304 }
305 // Parameters are live from index 0.
306 v = 0
307 while v < n {
308 let vv: *Value = x86_val_at(f, v)
309 if vv.kind == VK_PARAM {
310 let iv: *X86Interval = x86_intv_at(intv, v)
311 iv.start = 0
312 iv.end = 0
313 }
314 v = v + 1
315 }
316
317 // Pass 1: linear def-to-last-use, call-site recording, bb ranges.
318 var idx: i64 = 1
319 var bi: i64 = 0
320 var n_calls: i64 = 0
321 while bi < f.n_blocks {
322 let b: *BasicBlock = x86_block_at(f, bi)
323 bb_start[bi] = idx
324 var inst: *Instr = b.head
325 while inst != (0 as *Instr) {
326 // Def: the instruction's (non-void) result.
327 if inst.ty != (0 as *Type) {
328 if inst.ty.kind != 0 {
329 let r: i64 = inst.result
330 if r >= 0 { if r < n {
331 let rv: *X86Interval = x86_intv_at(intv, r)
332 if rv.start < 0 { rv.start = idx }
333 if rv.end < idx { rv.end = idx }
334 } }
335 }
336 }
337 // Uses: opcode-aware value operands (FIX-3), bounds-guarded (FIX-8).
338 let nv: i64 = x86_n_value_operands(inst)
339 var k: i64 = 0
340 while k < nv {
341 let u: i64 = x86_operand_k(inst, k)
342 if u >= 0 { if u < n {
343 let uv: *X86Interval = x86_intv_at(intv, u)
344 if uv.start < 0 { uv.start = idx }
345 if uv.end < idx { uv.end = idx }
346 uv.use_count = uv.use_count + 1
347 } }
348 k = k + 1
349 }
350 // Call-class sites (FIX-5) + flag their value operands (FIX-3).
351 if x86_is_call_class(inst.op) == 1 {
352 calls[n_calls] = idx
353 n_calls = n_calls + 1
354 var ck: i64 = 0
355 while ck < nv {
356 let cu: i64 = x86_operand_k(inst, ck)
357 if cu >= 0 { if cu < n { any_call[cu] = 1 } }
358 ck = ck + 1
359 }
360 }
361 idx = idx + 1
362 inst = inst.next
363 }
364 bb_end[bi] = idx - 1
365 bi = bi + 1
366 }
367 *n_calls_ptr = n_calls
368
369 // Pass 2 (FIX-4): single_block via an INDEPENDENT full op0..op(nv-1) scan of
370 // every instruction -- NOT derived from the (possibly truncated) use record.
371 let fb_raw: *u8 = sys_mmap(n * 8 + 16)
372 let first_bb: *i64 = fb_raw as *i64
373 let lb_raw: *u8 = sys_mmap(n * 8 + 16)
374 let last_bb: *i64 = lb_raw as *i64
375 v = 0
376 while v < n { first_bb[v] = 0 - 1; last_bb[v] = 0 - 1; v = v + 1 }
377 bi = 0
378 while bi < f.n_blocks {
379 let b: *BasicBlock = x86_block_at(f, bi)
380 var inst: *Instr = b.head
381 while inst != (0 as *Instr) {
382 if inst.ty != (0 as *Type) {
383 if inst.ty.kind != 0 {
384 let r: i64 = inst.result
385 if r >= 0 { if r < n { x86_touch_bb(first_bb, last_bb, r, bi) } }
386 }
387 }
388 let nv2: i64 = x86_n_value_operands(inst)
389 var k2: i64 = 0
390 while k2 < nv2 {
391 let u2: i64 = x86_operand_k(inst, k2)
392 if u2 >= 0 { if u2 < n { x86_touch_bb(first_bb, last_bb, u2, bi) } }
393 k2 = k2 + 1
394 }
395 inst = inst.next
396 }
397 bi = bi + 1
398 }
399 v = 0
400 while v < n {
401 let iv: *X86Interval = x86_intv_at(intv, v)
402 if first_bb[v] >= 0 {
403 if first_bb[v] == last_bb[v] { iv.single_block = 1 }
404 }
405 v = v + 1
406 }
407 return idx
408}
409
410// ===== BACK-EDGE INTERVAL EXTENSION (2026-07-15, STOP-SHIP fix) ======
411// ROOT CAUSE of the br_table-zeroing miscompile (found by S18 via the wat
412// lane; bisected to R10): build_intervals' [start,end] is def-to-last-use in
413// LINEAR order, but a value live ACROSS A BACK-EDGE (def before/hoisted out
414// of a loop, used inside it) is live through the WHOLE loop body at runtime
415// -- including CALLS positioned after its last linear use. crosses_call then
416// under-counts -> the value gets a CALLER-SAVED reg -> the uncounted call
417// clobbers it -> next iteration reads garbage/zero. The old single_block gate
418// masked exactly this; R10's cross-block relaxation exposed it. FIX: for
419// every backward branch bi -> tid, any interval that overlaps the loop span
420// [bb_start[tid], bb_end[bi]] but ends inside it is EXTENDED to the loop end,
421// so crosses_call sees every call in the loop. Conservative: extension can
422// only DENY caller-saved (push a value to callee-saved/spill), never allow
423// more. Callee-saved homes were never affected (dedicated + call-preserved).
424// ⚠MOVED UP 2026-07-20 -- THIS NEGATIVE CONTROL COULD NEVER FIRE. It was declared ~827 lines BELOW
425// (beside its siblings) while its ONLY reader is the very next line. A module const read ABOVE its
426// declaration silently resolves to 0, so flipping it to 1 was ignored: the negctl could not
427// reintroduce the miscompile it exists to reintroduce, and any gate row leaning on it was VACUOUSLY
428// GREEN. Its own sibling comment says this family "kills the 'the guard never fires, green is
429// vacuous' liar" -- this member WAS that liar. Found by the new forward-const diagnostic.
430// NEGATIVE CONTROL: 1 = skip the back-edge interval extension -> reintroduces the br_table-zeroing
431// miscompile (caller-saved clobbered across a back-edge) -> the gauntlet's WAT byte-exact row goes
432// RED. Ships at 0.
433const X86_NEGCTL_NO_BACKEDGE_EXT: i64 = 0
434
435func x86_extend_backedge_intervals(f: *Function, intv: *X86Interval,
436 bb_start: *i64, bb_end: *i64) -> i64 {
437 if X86_NEGCTL_NO_BACKEDGE_EXT == 1 { return 0 }
438 var bi: i64 = 0
439 while bi < f.n_blocks {
440 let b: *BasicBlock = x86_block_at(f, bi)
441 let t: *Instr = b.tail
442 if t != (0 as *Instr) {
443 var nt: i64 = 0
444 var t0: i64 = 0 - 1
445 var t1: i64 = 0 - 1
446 if t.op == OP_BR { t0 = t.op0; nt = 1 }
447 if t.op == OP_BR_COND { t0 = t.op1; t1 = t.op2; nt = 2 }
448 var ti: i64 = 0
449 while ti < nt {
450 var tid: i64 = t0
451 if ti == 1 { tid = t1 }
452 if tid >= 0 { if tid <= bi { if tid < f.n_blocks {
453 let H: i64 = bb_start[tid]
454 let P: i64 = bb_end[bi]
455 var v: i64 = 0
456 while v < f.n_values {
457 let iv: *X86Interval = x86_intv_at(intv, v)
458 if iv.start >= 0 {
459 if iv.start <= P { if iv.end >= H { if iv.end < P {
460 iv.end = P
461 } } }
462 }
463 v = v + 1
464 }
465 } } }
466 ti = ti + 1
467 }
468 }
469 bi = bi + 1
470 }
471 return 0
472}
473
474// crosses_call: any call index strictly after start and at/before end.
475func x86_mark_crosses_call(intv: *X86Interval, n_values: i64,
476 calls: *i64, n_calls: i64) -> i64 {
477 var v: i64 = 0
478 while v < n_values {
479 let iv: *X86Interval = x86_intv_at(intv, v)
480 if iv.start >= 0 {
481 var c: i64 = 0
482 while c < n_calls {
483 let ci: i64 = calls[c]
484 if ci > iv.start { if ci <= iv.end { iv.crosses_call = 1 } }
485 c = c + 1
486 }
487 }
488 v = v + 1
489 }
490 return 0
491}
492
493// ----- home selection ---------------------------------------------
494// Cut-1 restricts homeable values to results of PURE-RAX binops (the ops whose
495// emitter threads FIX-1 x86ctx_result_reg). Everything else stays spilled.
496func x86_is_pure_rax_binop(op: i64) -> i64 {
497 if op == OP_ADD { return 1 }
498 if op == OP_SUB { return 1 }
499 if op == OP_MUL { return 1 }
500 if op == OP_AND { return 1 }
501 if op == OP_OR { return 1 }
502 if op == OP_XOR { return 1 }
503 return 0
504}
505
506// A value is homeable (cut-1) iff it has a live interval, is single-basic-block,
507// is not a call/syscall/tail/clone operand (FIX-3), is not an alloca (FIX-10),
508// and is produced by a pure-rax binop (so result_reg threading covers it).
509func x86_is_homeable(f: *Function, intv: *X86Interval, alloca_off: *i64,
510 any_call: *i64, v: i64) -> i64 {
511 let iv: *X86Interval = x86_intv_at(intv, v)
512 if iv.start < 0 { return 0 }
513 // STAGE 3: cross-block values are homeable too (dedicated reg for the whole
514 // live range is sound under SSA dominance). Old code required single_block.
515 if X86_ALLOW_CROSSBLOCK == 0 { if iv.single_block != 1 { return 0 } }
516 // NB: a value that is a CALL operand is STILL homeable -- the home is a
517 // callee-saved register, so it survives the call (loaded into the arg reg
518 // from %home at the call site, retained after). any_call is computed but no
519 // longer excludes (the cut-1 exclusion was over-conservative); the register-
520 // survival KAT + the self-host fixpoint guard correctness.
521 if alloca_off[v] >= 0 { return 0 }
522 let val: *Value = x86_val_at(f, v)
523 if val.kind != VK_INSTR { return 0 }
524 let inst: *Instr = val.instr
525 if inst == (0 as *Instr) { return 0 }
526 // STAGE 5 attempt (2026-07-15) REVERTED: homing 8-byte LOAD results (emit_load
527 // targets result_reg) showed NO matmul benefit (3.40× vs 3.42×) AND broke the
528 // self-host fixpoint [C] (miscompiles the compiler on some pattern the KATs
529 // don't hit). Not worth a self-host miscompile for zero gain. The emit_load
530 // dst-plumbing is left in (inert: result_reg = rax for every unhomed value, so
531 // dst==rax for all loads now that loads aren't homeable -> byte-identical). To
532 // RETRIED AND LANDED 2026-08-14, with the blocker ROOT-CAUSED rather than guessed.
533 // Both stated reasons for the revert were artifacts of the workload, not properties
534 // of the change:
535 // (a) "NO matmul benefit" -- matmul's loads fold into the G8 SIB addressing path,
536 // which already took `dst`, so homing load results could not have moved that
537 // number in either direction. The benchmark could not see the change.
538 // (b) "miscompiles the compiler on a pattern the KATs don't hit" -- the subword
539 // load paths in x86ctx_emit_load hardcoded rax as their destination and then
540 // called store_result(result, dst). store_result emits NOTHING when reg is
541 // already the home, so a homed subword load left its home NEVER WRITTEN and
542 // every consumer read garbage. The compiler byte-walks source through *u8 and
543 // *i32 loads constantly; the matmul KATs are all 8-byte and cannot reach those
544 // branches. Fixed at the source (both subword blocks now write dst), proven
545 // inert by 7/7 byte-identical emitted assembly BEFORE this flag was enabled.
546 // Measured: a bounds-checked scalar loop spent 7 of its stack accesses per iteration
547 // moving values into and out of slots for registers that already held them, because
548 // the LOAD RESULT -- not the alloca -- is what gets spilled. Now 0. Self-host
549 // fixpoint S2==S3 byte-identical, gauntlet 49/49, checked hot loop 8493 -> 7106 us.
550 if x86_is_pure_rax_binop(inst.op) == 0 {
551 if X86_HOME_LOADS == 0 { return 0 }
552 if inst.op != OP_LOAD { return 0 }
553 }
554 return 1
555}
556
557// Does function f contain any op whose hand-written intrinsic emitter clobbers a
558// GP caller-saved reg (rsi/rdi/r8/r9)? CONSERVATIVE: the whole SIMD/crypto
559// intrinsic family (nx_x86_64_ctx dispatch 2439-2455) is treated as clobbering,
560// so a function using ANY of them keeps the current 5-callee-saved behavior and
561// the caller-saved pool is disabled for it. OP_THREAD_CLONE/SYSCALL are already
562// call-class (caught by crosses_call), so they need not appear here. matmul uses
563// none -> gets the full pool. The gauntlet + negative control validate soundness.
564func x86_op_clobbers_caller_saved(op: i64) -> i64 {
565 if op == OP_F32X4_DOT { return 1 }
566 if op == OP_I8DOT32 { return 1 }
567 if op == OP_I8DOT32A { return 1 }
568 if op == OP_I8FMA32 { return 1 }
569 if op == OP_Q8ROWDOT { return 1 }
570 if op == OP_Q5UNPACK32 { return 1 }
571 if op == OP_Q4KUNPACK32S { return 1 }
572 if op == OP_F32X8_DOT { return 1 }
573 if op == OP_F32X8_FMA { return 1 }
574 if op == OP_F32X8_HSUM { return 1 }
575 if op == OP_I16X16_MADD { return 1 }
576 if op == OP_AES128_ENC_BLOCK { return 1 }
577 if op == OP_SHA256_NI_BLOCK { return 1 }
578 if op == OP_MUL256_WIDE { return 1 }
579 if op == OP_CLMUL_LL { return 1 }
580 if op == OP_CLMUL_HH { return 1 }
581 if op == OP_CLMUL_LH { return 1 }
582 if op == OP_CLMUL_HL { return 1 }
583 return 0
584}
585
586func x86_fn_has_clobber_intrinsic(f: *Function) -> i64 {
587 var bi: i64 = 0
588 while bi < f.n_blocks {
589 let b: *BasicBlock = x86_block_at(f, bi)
590 var inst: *Instr = b.head
591 while inst != (0 as *Instr) {
592 if x86_op_clobbers_caller_saved(inst.op) == 1 { return 1 }
593 inst = inst.next
594 }
595 bi = bi + 1
596 }
597 return 0
598}
599
600// HOMING GATE -- ON. The full register-allocation machinery (consume-side op1
601// folding, use-count top-K selection, multi-home r12..rbx, call-operand values
602// allowed since homes are callee-saved) COMPOSES with the optimizer (opt_run,
603// enabled in nx_compile_x86.nx) for the WIN: opt's mem2reg promotes alloca'd
604// state to SSA values, and this allocator homes them. Measured on the point-loop
605// vs the pre-opt baseline (bench/nx_codegen_ab.sh): -672 insns (-13%), -266
606// reloads (-14%) [noise-free], wall-clock 2.5-5.9% faster. CORRECT + determin-
607// istic: full self-host gauntlet green (13/13 differential KATs + byte-stable
608// 2nd-gen fixpoint + register-survival KAT), 5/5 identical sha256 compiles.
609// Neither pass alone wins -- regalloc-alone is neutral (allocas stay in memory),
610// opt-alone REGRESSES ~6% (promoted SSA values spill without a register home);
611// only TOGETHER do they win. See docs/NX_G1_X86_REGALLOC_PLAN_2026_05_29.md.
612const X86_HOME_CAP_ENABLE: i64 = 1 // ON: composes with opt_run for the measured crypto win
613const X86_HOME_MIN_USES: i64 = 3 // require >= this many uses to beat save/restore
614
615// Home up to X86_HOME_CAP eligible values, highest use_count first (most reloads
616// to eliminate), requiring use_count >= X86_HOME_MIN_USES so the per-function
617// callee-saved save/restore is amortised. Assigns home indices 0..K-1 (r12..rbx)
618// and sets the corresponding mask bits. Deterministic: strict > keeps the lowest
619// id on ties (ascending scan).
620func x86_select_homes(f: *Function, intv: *X86Interval, alloca_off: *i64,
621 any_call: *i64, used_cs_mask_out: *i64, wcost: *i64) -> i64 {
622 *used_cs_mask_out = 0
623 if X86_HOME_CAP_ENABLE == 0 { return 0 }
624 var assigned: i64 = 0
625 var stop0: i64 = 0
626 while assigned < X86_HOME_CAP {
627 if stop0 == 0 {
628 var best: i64 = 0 - 1
629 var best_uc: i64 = 0 - 1
630 var v: i64 = 0
631 while v < f.n_values {
632 let iv: *X86Interval = x86_intv_at(intv, v)
633 if iv.reg < 0 {
634 if x86_is_homeable(f, intv, alloca_off, any_call, v) == 1 {
635 // RANK BY LOOP-DEPTH-WEIGHTED COST (SOTA): a deep-loop
636 // value beats a cold high-textual-count one.
637 if wcost[v] > best_uc {
638 best = v
639 best_uc = wcost[v]
640 }
641 }
642 }
643 v = v + 1
644 }
645 if best < 0 { stop0 = 1 }
646 if best_uc < X86_HOME_MIN_USES { stop0 = 1 }
647 if stop0 == 0 {
648 let biv: *X86Interval = x86_intv_at(intv, best)
649 biv.reg = assigned
650 *used_cs_mask_out = *used_cs_mask_out | (1 << assigned)
651 assigned = assigned + 1
652 }
653 }
654 if stop0 == 1 { assigned = X86_HOME_CAP }
655 }
656 // ===== CALLER-SAVED pool (arc stage 2, 2026-07-15) ==============
657 // Runs only when all 5 callee-saved were assigned (>5 homeable values =
658 // exactly when leftovers exist). Assigns idx 5..8 (rsi/rdi/r8/r9) to the
659 // next-highest-use homeable values that DON'T cross a call, in functions
660 // with no GP-clobbering intrinsic. NO used_cs_mask bit -> no prologue save
661 // (sound: the interval never spans a call/intrinsic that clobbers them).
662 if X86_CALLER_POOL_ENABLE == 1 {
663 if x86_fn_has_clobber_intrinsic(f) == 0 {
664 var cassigned: i64 = 0
665 var cstop: i64 = 0
666 while cassigned < X86_CALLER_CAP {
667 if cstop == 0 {
668 var cbest: i64 = 0 - 1
669 var cbest_uc: i64 = 0 - 1
670 var cv: i64 = 0
671 while cv < f.n_values {
672 let civ: *X86Interval = x86_intv_at(intv, cv)
673 if civ.reg < 0 {
674 if civ.crosses_call == 0 {
675 if x86_is_homeable(f, intv, alloca_off, any_call, cv) == 1 {
676 if wcost[cv] > cbest_uc {
677 cbest = cv
678 cbest_uc = wcost[cv]
679 }
680 }
681 }
682 }
683 cv = cv + 1
684 }
685 if cbest < 0 { cstop = 1 }
686 if cbest_uc < X86_CALLER_MIN_USES { cstop = 1 }
687 if cstop == 0 {
688 let cbiv: *X86Interval = x86_intv_at(intv, cbest)
689 cbiv.reg = X86_CALLER_BASE + cassigned
690 }
691 }
692 cassigned = cassigned + 1
693 }
694 }
695 }
696 return 0
697}
698
699// ===== G2: ALLOCA HOMING (loop-carried scalar registerization) ======
700// The 2026-05-29 plan's DEEPEST FINDING: in this SSA-no-phi IR the loop-
701// carried hot state lives in ALLOCAS (memory), untouched by SSA-value homing
702// and unreachable by opt_mem2reg_simple (needs phis). G2 homes the alloca's
703// STORAGE ITSELF in a leftover callee-saved register: every full-qword
704// load/store of the var becomes a register move -- no phis needed; loop-
705// carried correctness is by construction (the register IS the storage).
706// Measured motivation: the LCG grounding loop (reference-nishilang-vs-c-
707// codegen-grounding-2026-07-14) runs 20 memory ops/iter, 6 of them the
708// x/acc/i alloca round-trips on the critical dependence chain.
709//
710// Eligibility is a strict WHITELIST -- anything unrecognised disqualifies:
711// base: the alloca's declared storage type is exactly 8 bytes (i64/ptr).
712// uses: every appearance of the alloca's value id must be one of
713// OP_LOAD op0, 8-byte type (var read; emitted as movq %home,%rax)
714// OP_STORE op0, 8-byte type (var write; emitted as movq %src,%home)
715// OP_STORE op1 (value-read; load_value_v derefs the home)
716// a value-consume operand of a whitelisted op (binop/unop/cmp/br_cond/
717// return/call/tail_call/call_indirect/copy, syscall args k>=1) -- all
718// of these materialise operands via x86ctx_load_value_v, which reads
719// the home register directly.
720// disqualifiers: OP_GEP base, OP_ADDR_OF (the address escapes), OP_SYSCALL
721// k==0 (as-address load path), subword load/store, and EVERY op not
722// whitelisted (SIMD/crypto/atomic/clone: unknown consumption idiom ->
723// conservatively keep the stack slot).
724// Belt+braces: the as-address path (x86ctx_load_value) plants an undefined-
725// label jump for a homed alloca, so an eligibility miss FAILS THE ASSEMBLE
726// loudly instead of silently miscompiling (the 2026-05-30 SEV1 lesson).
727
728// Value-consume whitelist: ops PROVEN to materialise operands via
729// x86ctx_load_value_v (the home-aware as-value path).
730func x86_ah_value_consume_ok(op: i64) -> i64 {
731 if op == OP_ADD { return 1 }
732 if op == OP_SUB { return 1 }
733 if op == OP_MUL { return 1 }
734 if op == OP_DIV_S { return 1 }
735 if op == OP_DIV_U { return 1 }
736 if op == OP_REM_S { return 1 }
737 if op == OP_REM_U { return 1 }
738 if op == OP_NEG { return 1 }
739 if op == OP_NOT { return 1 }
740 if op == OP_AND { return 1 }
741 if op == OP_OR { return 1 }
742 if op == OP_XOR { return 1 }
743 if op == OP_SHL { return 1 }
744 if op == OP_SHR_S { return 1 }
745 if op == OP_SHR_U { return 1 }
746 if op == OP_EQ { return 1 }
747 if op == OP_NE { return 1 }
748 if op == OP_LT_S { return 1 }
749 if op == OP_LE_S { return 1 }
750 if op == OP_GT_S { return 1 }
751 if op == OP_GE_S { return 1 }
752 if op == OP_BR_COND { return 1 }
753 if op == OP_RETURN { return 1 }
754 if op == OP_CALL { return 1 }
755 if op == OP_TAIL_CALL { return 1 }
756 if op == OP_CALL_INDIRECT { return 1 }
757 if op == OP_SYSCALL { return 1 }
758 if op == OP_COPY { return 1 }
759 return 0
760}
761
762// Base eligibility: an OP_ALLOCA whose declared storage is an 8-byte scalar.
763func x86_ah_base_ok(f: *Function, v: i64) -> i64 {
764 let val: *Value = x86_val_at(f, v)
765 if val.kind != VK_INSTR { return 0 }
766 let inst: *Instr = val.instr
767 if inst == (0 as *Instr) { return 0 }
768 if inst.op != OP_ALLOCA { return 0 }
769 let t: *Type = inst.ty
770 if t == (0 as *Type) { return 0 }
771 if t.kind == TY_VOID { return 0 }
772 if t.size != 8 { return 0 }
773 return 1
774}
775
776// 1 iff this load/store moves a full 8-byte qword (subword access of a
777// homed register-var has no lowering -> disqualifies).
778func x86_ah_ldst_sz8(inst: *Instr) -> i64 {
779 let t: *Type = inst.ty
780 if t == (0 as *Type) { return 0 }
781 if t.size != 8 { return 0 }
782 return 1
783}
784
785// Scan every operand appearance of every alloca; leave elig[v]=1 only for
786// allocas whose EVERY use is whitelisted. cnt[v] = safe-use count (the
787// reload-elimination payoff proxy that ranks candidates).
788func x86_ah_scan(f: *Function, alloca_off: *i64, elig: *i64, cnt: *i64) -> i64 {
789 let n: i64 = f.n_values
790 var v: i64 = 0
791 while v < n {
792 elig[v] = 0
793 cnt[v] = 0
794 if alloca_off[v] >= 0 { elig[v] = x86_ah_base_ok(f, v) }
795 v = v + 1
796 }
797 var bi: i64 = 0
798 while bi < f.n_blocks {
799 let b: *BasicBlock = x86_block_at(f, bi)
800 var inst: *Instr = b.head
801 while inst != (0 as *Instr) {
802 let nv: i64 = x86_n_value_operands(inst)
803 var k: i64 = 0
804 while k < nv {
805 let u: i64 = x86_operand_k(inst, k)
806 if u >= 0 { if u < n { if alloca_off[u] >= 0 {
807 var ok: i64 = 0
808 if inst.op == OP_LOAD { if k == 0 { ok = x86_ah_ldst_sz8(inst) } }
809 if inst.op == OP_STORE {
810 if k == 0 { ok = x86_ah_ldst_sz8(inst) }
811 if k == 1 { ok = 1 }
812 }
813 if ok == 0 { ok = x86_ah_value_consume_ok(inst.op) }
814 if inst.op == OP_SYSCALL { if k == 0 { ok = 0 } }
815 if ok == 1 { cnt[u] = cnt[u] + 1 }
816 if ok == 0 { elig[u] = 0 }
817 } } }
818 k = k + 1
819 }
820 inst = inst.next
821 }
822 bi = bi + 1
823 }
824 return 0
825}
826
827// Assign LEFTOVER callee-saved homes (bits not taken by SSA-value homing)
828// to eligible allocas, highest safe-use count first, >= X86_HOME_MIN_USES.
829// Deterministic: strict > keeps the lowest value id on ties; lowest free
830// bit each round.
831func x86_ah_select(f: *Function, elig: *i64, cnt: *i64,
832 alloca_home: *i64, mask_ptr: *i64, wcost: *i64) -> i64 {
833 if X86_HOME_CAP_ENABLE == 0 { return 0 }
834 var round: i64 = 0
835 var stopr: i64 = 0
836 while round < X86_HOME_CAP {
837 if stopr == 0 {
838 var bit: i64 = 0 - 1
839 var b: i64 = 0
840 while b < X86_HOME_CAP {
841 if bit < 0 { if ((mask_ptr[0] >> b) & 1) == 0 { bit = b } }
842 b = b + 1
843 }
844 if bit < 0 { stopr = 1 }
845 if stopr == 0 {
846 var best: i64 = 0 - 1
847 var best_c: i64 = 0 - 1
848 var v: i64 = 0
849 while v < f.n_values {
850 if elig[v] == 1 { if alloca_home[v] < 0 {
851 // RANK BY LOOP-DEPTH-WEIGHTED COST (SOTA): a loop-carried
852 // alloca (s,k used every k-iter) beats a cold one; cnt
853 // (safe-use count) stays the eligibility signal via elig.
854 if wcost[v] > best_c { best = v; best_c = wcost[v] }
855 } }
856 v = v + 1
857 }
858 if best < 0 { stopr = 1 }
859 if best_c < X86_HOME_MIN_USES { stopr = 1 }
860 if stopr == 0 {
861 alloca_home[best] = bit
862 mask_ptr[0] = mask_ptr[0] | (1 << bit)
863 round = round + 1
864 }
865 }
866 }
867 if stopr == 1 { round = X86_HOME_CAP }
868 }
869 return 0
870}
871
872// ===== G4: single-use next-instruction temp ELISION =================
873// The emitter materialises EVERY instruction result into a stack slot even
874// when the value is consumed once by the IMMEDIATELY FOLLOWING instruction
875// through the G1 rax-forwarding path -- a dead store per temp (the dominant
876// remaining memory traffic after G2: ~8 dead stores/iter in the LCG loop).
877// elide[v]=1 marks values whose slot store may be SKIPPED because the single
878// consumer is guaranteed to take the G1 path: use_count==1, the use is in
879// the textually NEXT instruction (same block), at a position whose emission
880// loads that operand into RAX as its FIRST rax-touching action. store_result
881// keeps the G1 contract (sets G1_RAX_SLOT without the store); any slot LOAD
882// of an elided value = criterion bug -> loud undefined-label tripwire.
883
884// Ops whose emit loads op0 into rax first via load_value_v (or load_value
885// with the G1 check, for GEP). Binops additionally require the consumer's
886// result to be UNHOMED (dst==rax); cmp/unop/gep results are never homed.
887func x86_g4_is_binop(op: i64) -> i64 {
888 if op == OP_ADD { return 1 }
889 if op == OP_SUB { return 1 }
890 if op == OP_MUL { return 1 }
891 if op == OP_DIV_S { return 1 }
892 if op == OP_DIV_U { return 1 }
893 if op == OP_REM_S { return 1 }
894 if op == OP_REM_U { return 1 }
895 if op == OP_AND { return 1 }
896 if op == OP_OR { return 1 }
897 if op == OP_XOR { return 1 }
898 if op == OP_SHL { return 1 }
899 if op == OP_SHR_S { return 1 }
900 if op == OP_SHR_U { return 1 }
901 return 0
902}
903func x86_g4_is_cmp(op: i64) -> i64 {
904 if op == OP_EQ { return 1 }
905 if op == OP_NE { return 1 }
906 if op == OP_LT_S { return 1 }
907 if op == OP_LE_S { return 1 }
908 if op == OP_GT_S { return 1 }
909 if op == OP_GE_S { return 1 }
910 return 0
911}
912// dst OP src == src OP dst -- the ops the emitter may operand-swap (G11 chain
913// commute + G21 commuted rax-consume). Defined here (before x86_g4_pos_ok and
914// x86_chain_scan, its two caller clusters) per the defined-before-use rule.
915func x86_chain_op_commutative(op: i64) -> i64 {
916 if op == OP_ADD { return 1 }
917 if op == OP_MUL { return 1 }
918 if op == OP_AND { return 1 }
919 if op == OP_OR { return 1 }
920 if op == OP_XOR { return 1 }
921 return 0
922}
923// PRODUCER whitelist: ops whose emit leaves the result in RAX with
924// G1_RAX_SLOT still valid at the NEXT instruction -- the only ops whose slot
925// store is safe to elide. EXCLUDES every op whose dispatch clears
926// G1_RAX_SLOT after store (CPUID/RDTSC/CALL/SYSCALL/f32/SIMD/crypto) and every
927// op that produces in a non-rax reg (REM/UMULHI -> rdx). Mirrors the
928// consumer whitelist; both sides must be clean-rax for forwarding to hold.
929func x86_g4_producer_ok(op: i64) -> i64 {
930 if op == OP_ADD { return 1 }
931 if op == OP_SUB { return 1 }
932 if op == OP_MUL { return 1 }
933 if op == OP_DIV_S { return 1 }
934 if op == OP_DIV_U { return 1 }
935 if op == OP_AND { return 1 }
936 if op == OP_OR { return 1 }
937 if op == OP_XOR { return 1 }
938 if op == OP_SHL { return 1 }
939 if op == OP_SHR_S { return 1 }
940 if op == OP_SHR_U { return 1 }
941 if op == OP_EQ { return 1 }
942 if op == OP_NE { return 1 }
943 if op == OP_LT_S { return 1 }
944 if op == OP_LE_S { return 1 }
945 if op == OP_GT_S { return 1 }
946 if op == OP_GE_S { return 1 }
947 if op == OP_NEG { return 1 }
948 if op == OP_NOT { return 1 }
949 if op == OP_LOAD { return 1 }
950 if op == OP_GEP { return 1 }
951 if op == OP_COPY { return 1 }
952 return 0
953}
954func x86_g4_pos_ok(jop: i64, k: i64, jres_homed: i64) -> i64 {
955 if x86_g4_is_binop(jop) == 1 {
956 if jres_homed == 1 { return 0 }
957 if k == 0 { return 1 }
958 // G21 COMMUTED CONSUME: a commutative consumer reads its op1 straight
959 // from rax -- the emitter swaps operands (op0 becomes the src, rax is
960 // the dst seed), so the op1 slot store is dead exactly like the k==0
961 // case. MUST mirror the emit-side g21 gate in x86ctx_emit_binop (both
962 // sides clean-rax, unhomed result); the .G4_elided_slot_load_bug
963 // tripwire catches any divergence loudly.
964 if k == 1 { if x86_chain_op_commutative(jop) == 1 { return 1 } }
965 return 0
966 }
967 if x86_g4_is_cmp(jop) == 1 {
968 if k == 0 { return 1 }
969 return 0
970 }
971 if jop == OP_NEG { if k == 0 { return 1 } return 0 }
972 if jop == OP_NOT { if k == 0 { return 1 } return 0 }
973 if jop == OP_BR_COND { if k == 0 { return 1 } return 0 }
974 if jop == OP_RETURN { if k == 0 { return 1 } return 0 }
975 if jop == OP_COPY { if k == 0 { return 1 } return 0 }
976 if jop == OP_GEP { if k == 0 { return 1 } return 0 }
977 if jop == OP_STORE { if k == 1 { return 1 } return 0 }
978 return 0
979}
980
981func x86_g4_elide_scan(f: *Function, locs: *ValueLoc, alloca_off: *i64,
982 intv: *X86Interval, elide: *i64,
983 chain_home: *i64, chain_swap: *i64, fwd_home: *i64) -> i64 {
984 let n: i64 = f.n_values
985 var v: i64 = 0
986 while v < n { elide[v] = 0; v = v + 1 }
987 var bi: i64 = 0
988 while bi < f.n_blocks {
989 let b: *BasicBlock = x86_block_at(f, bi)
990 var inst: *Instr = b.head
991 while inst != (0 as *Instr) {
992 let nxt: *Instr = inst.next
993 if nxt != (0 as *Instr) {
994 let r: i64 = inst.result
995 if r >= 0 { if r < n {
996 var ok: i64 = 1
997 if inst.ty == (0 as *Type) { ok = 0 }
998 if ok == 1 { if inst.ty.kind == TY_VOID { ok = 0 } }
999 if x86_g4_producer_ok(inst.op) == 0 { ok = 0 }
1000 let rv: *Value = x86_val_at(f, r)
1001 if rv.kind != VK_INSTR { ok = 0 }
1002 if alloca_off[r] >= 0 { ok = 0 }
1003 if ok == 1 {
1004 let rl: *ValueLoc = ((locs as i64) + r * 16) as *ValueLoc
1005 if rl.kind == VL_REGISTER { ok = 0 }
1006 }
1007 if ok == 1 {
1008 let riv: *X86Interval = x86_intv_at(intv, r)
1009 if riv.use_count != 1 { ok = 0 }
1010 }
1011 if ok == 1 {
1012 var jres_homed: i64 = 0
1013 let jr: i64 = nxt.result
1014 if jr >= 0 { if jr < n {
1015 let jl: *ValueLoc = ((locs as i64) + jr * 16) as *ValueLoc
1016 if jl.kind == VL_REGISTER { jres_homed = 1 }
1017 } }
1018 let nv: i64 = x86_n_value_operands(nxt)
1019 var found: i64 = 0
1020 var k: i64 = 0
1021 while k < nv {
1022 if x86_operand_k(nxt, k) == r {
1023 if found == 0 {
1024 if x86_g4_pos_ok(nxt.op, k, jres_homed) == 1 { found = 1 }
1025 }
1026 // G16: a CHAIN-FUSED consumer materializes its
1027 // SRC operand via load_value_v(rax) as its FIRST
1028 // rax touch (op0 is never materialized -- it IS
1029 // the home), so the G1 contract holds at the src
1030 // position (op1 normal, op0 swapped). r must not
1031 // be homed (checked above) nor forwarded (would
1032 // read a home, not rax).
1033 if found == 0 {
1034 let cj: i64 = nxt.result
1035 if cj >= 0 { if cj < n { if chain_home[cj] >= 0 {
1036 var srcpos: i64 = 1
1037 if chain_swap[cj] == 1 { srcpos = 0 }
1038 if k == srcpos {
1039 if fwd_home[r] < 0 { found = 1 }
1040 }
1041 } } }
1042 }
1043 }
1044 k = k + 1
1045 }
1046 if found == 1 { elide[r] = 1 }
1047 }
1048 } }
1049 }
1050 inst = nxt
1051 }
1052 bi = bi + 1
1053 }
1054 return 0
1055}
1056
1057// ===== G5: BIG-CONSTANT HOMING ======================================
1058// A VK_CONST_INT too big for imm32 is re-materialised with a 10-byte movabsq
1059// at EVERY use (per-iteration in loops). Home the hottest such constants in
1060// LEFTOVER callee-saved regs: one movabsq in the prologue, and op1-direct
1061// binop consumption reads the home register with ZERO per-use instructions
1062// (imulq %r15,%rax instead of movabsq+imulq). imm32-fitting constants are
1063// handled by the immediate-folding path in the emitter instead (no reg cost).
1064func x86_g5_imm32_ok(v: i64) -> i64 {
1065 if v > 2147483647 { return 0 }
1066 if v < (0 - 2147483648) { return 0 }
1067 return 1
1068}
1069
1070func x86_g5_select_const_homes(f: *Function, intv: *X86Interval,
1071 locs: *ValueLoc, mask_ptr: *i64) -> i64 {
1072 if X86_HOME_CAP_ENABLE == 0 { return 0 }
1073 let n: i64 = f.n_values
1074 // Loop-block map: for every BACKWARD branch bj -> bi (bi <= bj), blocks
1075 // bi..bj are loop-resident (blocks lay out in creation order; a NishiLang
1076 // while parses to a contiguous cond..body range, so the interval IS the
1077 // loop body). A constant's payoff is per-EXECUTION, not per-site: one
1078 // in-loop movabsq costs every iteration, so in-loop uses weigh 8x --
1079 // a single hot-loop use clears X86_HOME_MIN_USES; cold single uses don't.
1080 let lb_raw: *u8 = sys_mmap(f.n_blocks * 8 + 16)
1081 let lb: *i64 = lb_raw as *i64
1082 var lbi: i64 = 0
1083 while lbi < f.n_blocks {
1084 let lbb: *BasicBlock = x86_block_at(f, lbi)
1085 var linst: *Instr = lbb.head
1086 while linst != (0 as *Instr) {
1087 var tgt: i64 = 0 - 1
1088 var tgt2: i64 = 0 - 1
1089 if linst.op == OP_BR { tgt = linst.op0 }
1090 if linst.op == OP_BR_COND { tgt = linst.op1; tgt2 = linst.op2 }
1091 if tgt >= 0 { if tgt <= lbi { if tgt < f.n_blocks {
1092 var m: i64 = tgt
1093 while m <= lbi { lb[m] = 1; m = m + 1 }
1094 } } }
1095 if tgt2 >= 0 { if tgt2 <= lbi { if tgt2 < f.n_blocks {
1096 var m2: i64 = tgt2
1097 while m2 <= lbi { lb[m2] = 1; m2 = m2 + 1 }
1098 } } }
1099 linst = linst.next
1100 }
1101 lbi = lbi + 1
1102 }
1103 // direct-consumable op1 uses per value (the payoff metric), loop-weighted
1104 let du_raw: *u8 = sys_mmap(n * 8 + 16)
1105 let du: *i64 = du_raw as *i64
1106 var bi: i64 = 0
1107 while bi < f.n_blocks {
1108 let b: *BasicBlock = x86_block_at(f, bi)
1109 var inst: *Instr = b.head
1110 while inst != (0 as *Instr) {
1111 if x86_is_pure_rax_binop(inst.op) == 1 {
1112 let u: i64 = inst.op1
1113 if u >= 0 { if u < n {
1114 if lb[bi] == 1 { du[u] = du[u] + 8 }
1115 if lb[bi] == 0 { du[u] = du[u] + 1 }
1116 } }
1117 }
1118 inst = inst.next
1119 }
1120 bi = bi + 1
1121 }
1122 var round: i64 = 0
1123 while round < X86_HOME_CAP {
1124 var bit: i64 = 0 - 1
1125 var b2: i64 = 0
1126 while b2 < X86_HOME_CAP {
1127 if bit < 0 { if ((mask_ptr[0] >> b2) & 1) == 0 { bit = b2 } }
1128 b2 = b2 + 1
1129 }
1130 if bit < 0 { return 0 }
1131 var best: i64 = 0 - 1
1132 var best_c: i64 = 0 - 1
1133 var v: i64 = 0
1134 while v < n {
1135 let val: *Value = x86_val_at(f, v)
1136 if val.kind == VK_CONST_INT {
1137 let lv: *ValueLoc = ((locs as i64) + v * 16) as *ValueLoc
1138 if lv.kind != VL_REGISTER {
1139 if x86_g5_imm32_ok(val.const_int) == 0 {
1140 if du[v] > best_c { best = v; best_c = du[v] }
1141 }
1142 }
1143 }
1144 v = v + 1
1145 }
1146 if best < 0 { return 0 }
1147 if best_c < X86_HOME_MIN_USES { return 0 }
1148 let bl: *ValueLoc = ((locs as i64) + best * 16) as *ValueLoc
1149 bl.kind = VL_REGISTER
1150 bl.idx = bit
1151 mask_ptr[0] = mask_ptr[0] | (1 << bit)
1152 round = round + 1
1153 }
1154 return 0
1155}
1156
1157// ===== G17: NON-NEGATIVE RANGE ANALYSIS (2026-07-16) =================
1158// The auto-scientist's PROVEN 2.063x spot: signed division by 2^k pays a
1159// 4-instruction sign-bias dance that a provably NON-NEGATIVE dividend never
1160// needs -- gcc -O2 pays it too wherever range isn't visible. This lattice is
1161// DELIBERATELY conservative: only ops that STRUCTURALLY clear or preserve a
1162// zero sign bit qualify; anything that can overflow into the sign bit
1163// (ADD/SUB/MUL/SHL) is EXCLUDED by design, loads are excluded in v1 (the
1164// alloca-store fixpoint is G17b). Wrong answers here are MISCOMPILES -- the
1165// negctl (treat everything as nonneg) must go RED on the battery.
1166const X86_NEGCTL_NONNEG_ALWAYS: i64 = 0
1167
1168func x86_const_ge(f: *Function, v: i64, lo: i64) -> i64 {
1169 if v < 0 { return 0 }
1170 if v >= f.n_values { return 0 }
1171 let val: *Value = x86_val_at(f, v)
1172 if val.kind != VK_CONST_INT { return 0 }
1173 if val.const_int >= lo { return 1 }
1174 return 0
1175}
1176
1177func x86_val_nonneg(f: *Function, v: i64, depth: i64) -> i64 {
1178 if X86_NEGCTL_NONNEG_ALWAYS == 1 { return 1 }
1179 if depth <= 0 { return 0 }
1180 if v < 0 { return 0 }
1181 if v >= f.n_values { return 0 }
1182 let val: *Value = x86_val_at(f, v)
1183 if val.kind == VK_CONST_INT {
1184 if val.const_int >= 0 { return 1 }
1185 return 0
1186 }
1187 if val.kind != VK_INSTR { return 0 }
1188 let inst: *Instr = val.instr
1189 if inst == (0 as *Instr) { return 0 }
1190 // AND with ANY nonneg operand: a zero sign bit ANDed in stays zero.
1191 if inst.op == OP_AND {
1192 if x86_val_nonneg(f, inst.op0, depth - 1) == 1 { return 1 }
1193 if x86_val_nonneg(f, inst.op1, depth - 1) == 1 { return 1 }
1194 return 0
1195 }
1196 // Logical shift right by a CONST >= 1 kills the sign bit outright; by any
1197 // count it preserves nonneg. Arithmetic shift right preserves the sign.
1198 if inst.op == OP_SHR_U {
1199 if x86_const_ge(f, inst.op1, 1) == 1 { return 1 }
1200 if x86_val_nonneg(f, inst.op0, depth - 1) == 1 { return 1 }
1201 return 0
1202 }
1203 if inst.op == OP_SHR_S {
1204 if x86_val_nonneg(f, inst.op0, depth - 1) == 1 { return 1 }
1205 return 0
1206 }
1207 // Signed div of a nonneg by a positive const is nonneg (magnitude shrinks).
1208 if inst.op == OP_DIV_S {
1209 if x86_const_ge(f, inst.op1, 1) == 1 {
1210 if x86_val_nonneg(f, inst.op0, depth - 1) == 1 { return 1 }
1211 }
1212 return 0
1213 }
1214 // Unsigned div by a const >= 2 clears the top bit regardless of input.
1215 if inst.op == OP_DIV_U {
1216 if x86_const_ge(f, inst.op1, 2) == 1 { return 1 }
1217 return 0
1218 }
1219 // rem_u by a positive const is in [0, const) -- nonneg.
1220 if inst.op == OP_REM_U {
1221 if x86_const_ge(f, inst.op1, 1) == 1 { return 1 }
1222 return 0
1223 }
1224 // rem_s follows the dividend's sign.
1225 if inst.op == OP_REM_S {
1226 if x86_val_nonneg(f, inst.op0, depth - 1) == 1 { return 1 }
1227 return 0
1228 }
1229 return 0
1230}
1231
1232// ===== G10: HOME-FORWARDING (2026-07-15) ============================
1233// The gap tool's verdict: 59-68% of every hot loop is materialization waste,
1234// led by the load-of-homed-alloca triple `movq %home,%rax; movq %rax,slot;
1235// movq slot,%reg`. G10 kills it: a SINGLE-USE, 8-byte LOAD of a G2-HOMED
1236// alloca whose one consumer is IN THE SAME BLOCK at an AUDITED operand
1237// position, with NO intervening store to that alloca and NO intervening
1238// call-class op, emits NOTHING -- the consumer reads the alloca's home
1239// register directly (load_value_v/load_value check fwd_home first).
1240// SOUNDNESS: the home register is DEDICATED to the alloca (never shared,
1241// callee-saved, never scratch), so between the load site and the consumer
1242// site its content changes ONLY on a store-to-the-alloca -- exactly what the
1243// scan forbids. The audited-consumer whitelist guarantees the operand is
1244// materialized via load_value_v/load_value (where the fwd check lives), and
1245// the SIB-shape exclusions below keep displaced-emission folds out.
1246const X86_FWD_ENABLE: i64 = 1
1247// NEGATIVE CONTROL: 1 = scan ignores intervening stores-to-the-alloca -> a
1248// STALE home is forwarded -> nx_homefwd_adversary T1 answers WRONG and the
1249// battery goes RED. Proves the store-guard is load-bearing. Ships at 0.
1250const X86_NEGCTL_FWD_IGNORE_STORE: i64 = 0
1251// NEGATIVE CONTROL 2: 1 = forward from the WRONG home register (idx rotated
1252// within the callee-saved pool) -> every forwarded read yields garbage -> the
1253// battery MUST go RED wherever forwarding fires. Kills the "forwarding never
1254// actually fires, green is vacuous" liar. Ships at 0.
1255const X86_NEGCTL_FWD_WRONG_HOME: i64 = 0
1256
1257// ===== G11: CHAIN IN-PLACE FUSION (2026-07-15, rung 12) =============
1258// The gap tool's next rock (cp=7-9 copies/loop): the loop-carried update
1259// `load A -> binop chain -> store A` still costs a head copy (movq %hA,%dst)
1260// and a tail copy (movq %dst,%hA) plus per-step dst shuffling. G11 fuses the
1261// WHOLE chain onto the home register: each chain binop emits `op src1,%hA`
1262// IN PLACE (op0 never materialized -- it IS hA), the head load and the tail
1263// store emit NOTHING. `x = x*A + C` -> imulq+addq straight on %hx; `i = i+1`
1264// -> one `addq $1,%hi`. SOUNDNESS: the scan requires (a) head load of a
1265// G2-homed 8-byte alloca, result single-use consumed at op0 of an
1266// ADD/SUB/MUL/AND/OR/XOR whose result is again single-use at the next step's
1267// op0, ... terminating in `store A, final`; (b) NO other access to A (load
1268// OR store) inside the window -- hA holds INTERMEDIATE values mid-chain, so
1269// any other reader would see garbage; (c) no call-class op inside; (d) all
1270// same-block. Interleaved instructions that don't touch A are fine (they
1271// write rax/rcx/their own homes, never hA -- homes are dedicated).
1272const X86_CHAIN_ENABLE: i64 = 1
1273// NEGATIVE CONTROL: 1 = ignore the mid-window load-of-A abort -> a chain
1274// containing a second read of A fuses anyway -> that read sees the MUTATED
1275// home -> nx_homefwd_adversary T4 answers WRONG -> battery RED. Ships at 0.
1276const X86_NEGCTL_CHAIN_IGNORE_READ: i64 = 0
1277// NEGATIVE CONTROL: 1 = drop the self-ref chain guard -> `z = z & (z-1)` fuses
1278// in place again (subq $1,%home; andq %home,%home) -> Kernighan popcount
1279// degrades to a decrement -> nx_chain_selfref_adversary goes RED. Kills the
1280// "the guard never fires, green is vacuous" liar. Ships at 0.
1281const X86_NEGCTL_CHAIN_SELFREF_OFF: i64 = 0
1282// (X86_NEGCTL_NO_BACKEDGE_EXT MOVED UP to sit beside its only reader -- it was declared here and
1283// read 827 lines earlier, so it silently resolved to 0 and could never fire. Do NOT move it back.)
1284
1285func x86_chain_op_ok(op: i64) -> i64 {
1286 if op == OP_ADD { return 1 }
1287 if op == OP_SUB { return 1 }
1288 if op == OP_MUL { return 1 }
1289 if op == OP_AND { return 1 }
1290 if op == OP_OR { return 1 }
1291 if op == OP_XOR { return 1 }
1292 return 0
1293}
1294
1295// Commutative subset: the chain value may sit at op1 (const-first canonical
1296// forms like MUL(3,n)); `op src,dst` then computes dst OP src = src OP dst.
1297// SUB excluded (3-n != n-3).
1298// Marks: chain_home[v] = the home idx for IN-PLACE emission of chain binop
1299// results (-1 otherwise); the head load is killed via fwd_home[head]=hA (the
1300// existing G10 kill path); the tail store is suppressed in emit_store via
1301// chain_home[op1] == alloca_home[op0]. Runs AFTER x86_fwd_scan (which inits
1302// fwd_home) so the head-kill write survives.
1303func x86_chain_scan(f: *Function, alloca_off: *i64, alloca_home: *i64,
1304 intv: *X86Interval, fwd_home: *i64, chain_home: *i64,
1305 chain_swap: *i64) -> i64 {
1306 var vz: i64 = 0
1307 while vz < f.n_values { chain_home[vz] = 0 - 1; chain_swap[vz] = 0; vz = vz + 1 }
1308 if X86_CHAIN_ENABLE == 0 { return 0 }
1309 var bi: i64 = 0
1310 while bi < f.n_blocks {
1311 let b: *BasicBlock = x86_block_at(f, bi)
1312 var inst: *Instr = b.head
1313 while inst != (0 as *Instr) {
1314 if inst.op == OP_LOAD {
1315 let a: i64 = inst.op0
1316 if a >= 0 { if a < f.n_values { if alloca_home[a] >= 0 {
1317 let lt: *Type = inst.ty
1318 if lt != (0 as *Type) { if lt.size == 8 {
1319 let r: i64 = inst.result
1320 if r >= 0 { if r < f.n_values {
1321 let riv: *X86Interval = x86_intv_at(intv, r)
1322 // STAGE 5: a HOMED load result must never ALSO be forwarded or
1323 // chain-fused. Both paths make emit_load emit NOTHING, so the home
1324 // register would never be written and every consumer reading it
1325 // through the VL_REGISTER path would get garbage. Homing already
1326 // removes the reload these scans exist to avoid, so declining costs
1327 // nothing. Selection runs BEFORE both scans, so iv.reg is final here
1328 // and this is an exact test, not an assumption about ordering.
1329 if riv.use_count == 1 && riv.reg < 0 {
1330 // Walk the op0-thread to a store-back of A.
1331 var cur: i64 = r
1332 var steps: i64 = 0
1333 var J: *Instr = inst.next
1334 var verdict: i64 = 0 // 0=scan 1=fuse 2=no
1335 var term: *Instr = 0 as *Instr
1336 while verdict == 0 {
1337 if J == (0 as *Instr) { verdict = 2 }
1338 if verdict == 0 {
1339 if J.op == OP_LOAD { if J.op0 == a {
1340 if X86_NEGCTL_CHAIN_IGNORE_READ == 0 { verdict = 2 }
1341 } }
1342 }
1343 if verdict == 0 {
1344 if J.op == OP_STORE { if J.op0 == a {
1345 if J.op1 == cur {
1346 if steps >= 1 { verdict = 1; term = J }
1347 if steps < 1 { verdict = 2 }
1348 }
1349 if J.op1 != cur { verdict = 2 }
1350 } }
1351 }
1352 if verdict == 0 {
1353 if x86_is_call_class(J.op) == 1 { verdict = 2 }
1354 }
1355 if verdict == 0 {
1356 // Does J consume cur anywhere?
1357 let nv: i64 = x86_n_value_operands(J)
1358 var kk: i64 = 0
1359 var found: i64 = 0
1360 while kk < nv {
1361 if x86_operand_k(J, kk) == cur { found = 1 }
1362 kk = kk + 1
1363 }
1364 if found == 1 {
1365 var ok: i64 = 0
1366 if x86_chain_op_ok(J.op) == 1 {
1367 // straight: chain value at op0
1368 if J.op0 == cur { if J.op1 != cur { ok = 1 } }
1369 // commuted: chain value at op1
1370 // of a COMMUTATIVE op (const-
1371 // first canonical MUL(3,n) etc.)
1372 if ok == 0 {
1373 if x86_chain_op_commutative(J.op) == 1 {
1374 if J.op1 == cur { if J.op0 != cur { ok = 1 } }
1375 }
1376 }
1377 if ok == 1 {
1378 let civ: *X86Interval = x86_intv_at(intv, cur)
1379 if civ.use_count != 1 { ok = 0 }
1380 let jr: i64 = J.result
1381 if jr < 0 { ok = 0 }
1382 if jr >= f.n_values { ok = 0 }
1383 // SELF-REF GUARD (fixes z = z & (z-1) miscompile):
1384 // the SRC operand (the non-chain operand) must NOT read
1385 // the alloca `a` being chained. The chain mutates a's home
1386 // IN PLACE, so any src that resolves to a's value (the head
1387 // load r, OR any other LOAD of a) reads the MUTATED home,
1388 // not the original z -- `z&(z-1)`, `(z-1)&z`, `z^(z+1)` all
1389 // route a second read of z into a step's src. Legit chains
1390 // (s += arr[i]) load a DIFFERENT alloca, so are unaffected.
1391 if X86_NEGCTL_CHAIN_SELFREF_OFF == 0 {
1392 var chsrc: i64 = J.op1
1393 if J.op0 != cur { chsrc = J.op0 }
1394 if chsrc == r { ok = 0 }
1395 if chsrc >= 0 { if chsrc < f.n_values {
1396 let sv: *Value = x86_val_at(f, chsrc)
1397 if sv.kind == VK_INSTR {
1398 let si: *Instr = sv.instr
1399 if si != (0 as *Instr) {
1400 if si.op == OP_LOAD { if si.op0 == a { ok = 0 } }
1401 }
1402 }
1403 } }
1404 }
1405 }
1406 }
1407 if ok == 1 { cur = J.result; steps = steps + 1 }
1408 if ok == 0 { verdict = 2 }
1409 }
1410 }
1411 if verdict == 0 { J = J.next }
1412 }
1413 if verdict == 1 {
1414 // Final value must be single-use (the store).
1415 let fiv: *X86Interval = x86_intv_at(intv, cur)
1416 if fiv.use_count == 1 {
1417 let hA: i64 = alloca_home[a]
1418 fwd_home[r] = hA // kill the head load
1419 // Mark every chain binop for in-place emit.
1420 var C2: *Instr = inst.next
1421 var prev: i64 = r
1422 var marking: i64 = 1
1423 while marking == 1 {
1424 if C2 == (0 as *Instr) { marking = 0 }
1425 if marking == 1 {
1426 if C2 == term { marking = 0 }
1427 }
1428 if marking == 1 {
1429 if x86_chain_op_ok(C2.op) == 1 {
1430 var mk: i64 = 0
1431 var sw: i64 = 0
1432 if C2.op0 == prev { if C2.op1 != prev { mk = 1 } }
1433 if mk == 0 {
1434 if x86_chain_op_commutative(C2.op) == 1 {
1435 if C2.op1 == prev { if C2.op0 != prev { mk = 1; sw = 1 } }
1436 }
1437 }
1438 if mk == 1 {
1439 chain_home[C2.result] = hA
1440 chain_swap[C2.result] = sw
1441 prev = C2.result
1442 }
1443 }
1444 C2 = C2.next
1445 }
1446 }
1447 }
1448 }
1449 }
1450 } }
1451 } }
1452 } } }
1453 }
1454 inst = inst.next
1455 }
1456 bi = bi + 1
1457 }
1458 return 0
1459}
1460
1461// Is value id `u` a VK_CONST_INT equal to one of up to 4 given values?
1462func x86_fwd_const_in(f: *Function, u: i64, a: i64, b: i64, c2: i64, d: i64) -> i64 {
1463 if u < 0 { return 0 }
1464 if u >= f.n_values { return 0 }
1465 let v: *Value = x86_val_at(f, u)
1466 if v.kind != VK_CONST_INT { return 0 }
1467 let x: i64 = v.const_int
1468 if x == a { return 1 }
1469 if x == b { return 1 }
1470 if x == c2 { return 1 }
1471 if x == d { return 1 }
1472 return 0
1473}
1474
1475// Is value id `u` produced by an instruction that a SIB fold could consume
1476// (SHL by 0..3 / MUL by 1,2,4,8)? Used to keep forwarded values out of any
1477// shape the G8 SIB probe might fold (folds emit DISPLACED, at the load/store
1478// site, possibly past a store-to-the-alloca -- unsound for forwarding).
1479func x86_fwd_is_sibish(f: *Function, u: i64) -> i64 {
1480 if u < 0 { return 0 }
1481 if u >= f.n_values { return 0 }
1482 let v: *Value = x86_val_at(f, u)
1483 if v.kind != VK_INSTR { return 0 }
1484 let inst: *Instr = v.instr
1485 if inst == (0 as *Instr) { return 0 }
1486 if inst.op == OP_SHL {
1487 if x86_fwd_const_in(f, inst.op1, 0, 1, 2, 3) == 1 { return 1 }
1488 }
1489 if inst.op == OP_MUL {
1490 if x86_fwd_const_in(f, inst.op1, 1, 2, 4, 8) == 1 { return 1 }
1491 if x86_fwd_const_in(f, inst.op0, 1, 2, 4, 8) == 1 { return 1 }
1492 }
1493 return 0
1494}
1495
1496// AUDITED consumer positions: (op, k) pairs whose emission materializes the
1497// operand via load_value_v (verified in nx_x86_64_ctx.nx: binop op0 -> dst,
1498// binop op1 -> rcx/direct, cmp op0 -> rax + op1 -> rcx/direct, STORE op1 on
1499// all four paths, RETURN op0). Everything else (GEP/LOAD/STORE addresses,
1500// calls, syscalls, branches, unops, SIMD) is NOT forwarded. SIB exclusions:
1501// - (SHL,0) with shift 0..3 and (MUL,*) by 1/2/4/8: the instr itself can be
1502// folded into a SIB address -> displaced emission -> skip.
1503// - (ADD,k) whose OTHER operand is such a SHL/MUL: LOAD(ADD(ptr,SHL(i,3)))
1504// folds the ADD too -> skip. (ADD with a non-sib MUL, e.g. k*192, is fine.)
1505func x86_fwd_consumer_ok(f: *Function, J: *Instr, k: i64) -> i64 {
1506 let op: i64 = J.op
1507 if op == OP_STORE {
1508 if k == 1 { return 1 }
1509 return 0
1510 }
1511 if op == OP_RETURN {
1512 if k == 0 { return 1 }
1513 return 0
1514 }
1515 var binop: i64 = 0
1516 if op == OP_ADD { binop = 1 }
1517 if op == OP_SUB { binop = 1 }
1518 if op == OP_MUL { binop = 1 }
1519 if op == OP_AND { binop = 1 }
1520 if op == OP_OR { binop = 1 }
1521 if op == OP_XOR { binop = 1 }
1522 if op == OP_SHL { binop = 1 }
1523 if op == OP_SHR_S { binop = 1 }
1524 if op == OP_SHR_U { binop = 1 }
1525 if op == OP_DIV_S { binop = 1 }
1526 if op == OP_DIV_U { binop = 1 }
1527 if op == OP_REM_S { binop = 1 }
1528 if op == OP_REM_U { binop = 1 }
1529 var cmp: i64 = 0
1530 if op == OP_EQ { cmp = 1 }
1531 if op == OP_NE { cmp = 1 }
1532 if op == OP_LT_S { cmp = 1 }
1533 if op == OP_LE_S { cmp = 1 }
1534 if op == OP_GT_S { cmp = 1 }
1535 if op == OP_GE_S { cmp = 1 }
1536 if binop == 0 { if cmp == 0 { return 0 } }
1537 if k > 1 { return 0 }
1538 // SIB exclusion 1: the consumer itself is a sib-foldable SHL/MUL.
1539 if op == OP_SHL {
1540 if x86_fwd_const_in(f, J.op1, 0, 1, 2, 3) == 1 { return 0 }
1541 }
1542 if op == OP_MUL {
1543 if x86_fwd_const_in(f, J.op1, 1, 2, 4, 8) == 1 { return 0 }
1544 if x86_fwd_const_in(f, J.op0, 1, 2, 4, 8) == 1 { return 0 }
1545 }
1546 // SIB exclusion 2: an ADD whose OTHER operand is a sib-ish SHL/MUL.
1547 if op == OP_ADD {
1548 var other: i64 = J.op1
1549 if k == 1 { other = J.op0 }
1550 if x86_fwd_is_sibish(f, other) == 1 { return 0 }
1551 }
1552 return 1
1553}
1554
1555// LN7 switch for the block rule (declared ABOVE its readers: this file has already
1556// measured that a const read before its declaration silently resolves to 0).
1557// 0 = the 2026-07-15 single-use rule only (the pre-LN7 allocator, bit for bit);
1558// 1 = block rule admitted. Ships at 1.
1559const X86_LN7_BLOCK_FWD_ENABLE: i64 = 1
1560
1561// LN7 (2026-08-23, lang rung "backend consumes its register allocation", watch symbol
1562// x86_use_regalloc in nx_x86_64_ctx.nx): the audited operand POSITIONS alone -- the
1563// (op, k) whitelist without the SIB-shape exclusions. x86_fwd_consumer_ok layers the
1564// exclusions on top for the single-use rule; the block rule below needs only this.
1565func x86_fwd_pos_audited(op: i64, k: i64) -> i64 {
1566 if op == OP_STORE {
1567 if k == 1 { return 1 }
1568 return 0
1569 }
1570 if op == OP_RETURN {
1571 if k == 0 { return 1 }
1572 return 0
1573 }
1574 var binop: i64 = 0
1575 if op == OP_ADD { binop = 1 }
1576 if op == OP_SUB { binop = 1 }
1577 if op == OP_MUL { binop = 1 }
1578 if op == OP_AND { binop = 1 }
1579 if op == OP_OR { binop = 1 }
1580 if op == OP_XOR { binop = 1 }
1581 if op == OP_SHL { binop = 1 }
1582 if op == OP_SHR_S { binop = 1 }
1583 if op == OP_SHR_U { binop = 1 }
1584 if op == OP_DIV_S { binop = 1 }
1585 if op == OP_DIV_U { binop = 1 }
1586 if op == OP_REM_S { binop = 1 }
1587 if op == OP_REM_U { binop = 1 }
1588 var cmp: i64 = 0
1589 if op == OP_EQ { cmp = 1 }
1590 if op == OP_NE { cmp = 1 }
1591 if op == OP_LT_S { cmp = 1 }
1592 if op == OP_LE_S { cmp = 1 }
1593 if op == OP_GT_S { cmp = 1 }
1594 if op == OP_GE_S { cmp = 1 }
1595 if binop == 0 { if cmp == 0 { return 0 } }
1596 if k > 1 { return 0 }
1597 return 1
1598}
1599
1600// One instruction of the LN7 clean-path walk (x86_fwd_probe). Returns 0 = path
1601// killed here (a store to the alloca a, or a call-class op), -1 = a use of r at an
1602// UNAUDITED position (refuse the load), 1 = clean and no use of r, 2 = clean with
1603// one audited use, 3 = clean with two audited uses (r at op0 and op1, e.g. r + r).
1604func x86_fwd_step(f: *Function, K: *Instr, a: i64, r: i64) -> i64 {
1605 if K.op == OP_STORE { if K.op0 == a {
1606 if X86_NEGCTL_FWD_IGNORE_STORE == 0 { return 0 }
1607 } }
1608 if x86_is_call_class(K.op) == 1 { return 0 }
1609 let nv2: i64 = x86_n_value_operands(K)
1610 var kk2: i64 = 0
1611 var uses: i64 = 0
1612 while kk2 < nv2 {
1613 if x86_operand_k(K, kk2) == r {
1614 if x86_fwd_pos_audited(K.op, kk2) == 0 { return 0 - 1 }
1615 uses = uses + 1
1616 }
1617 kk2 = kk2 + 1
1618 }
1619 return 1 + uses
1620}
1621
1622// Push successors of B not yet visited (visited = scratch[2nb..3nb), stack = scratch[3nb..4nb)); the
1623// REACHK walk of x86_fwd_probe uses this. Returns the new stack depth. b0 is pre-marked visited (cut).
1624func x86_fwd_push_succs2(f: *Function, B: *BasicBlock, scratch: *i64, sp_in: i64, nb: i64) -> i64 {
1625 var sp: i64 = sp_in
1626 let t: *Instr = B.tail
1627 if t == (0 as *Instr) { return sp }
1628 var t0: i64 = 0 - 1
1629 var t1: i64 = 0 - 1
1630 if t.op == OP_BR { t0 = t.op0 }
1631 if t.op == OP_BR_COND { t0 = t.op1; t1 = t.op2 }
1632 var ti: i64 = 0
1633 while ti < 2 {
1634 var tid: i64 = t0
1635 if ti == 1 { tid = t1 }
1636 if tid >= 0 { if tid < nb {
1637 if scratch[2 * nb + tid] == 0 {
1638 scratch[2 * nb + tid] = 1
1639 scratch[3 * nb + sp] = tid
1640 sp = sp + 1
1641 }
1642 } }
1643 ti = ti + 1
1644 }
1645 return sp
1646}
1647
1648// LN7 probe: would this LOAD's result be home-forwarded IF its source alloca is
1649// homed? Returns the source alloca id, or -1. Deliberately independent of
1650// alloca_home so it can run BEFORE selection (x86_fwd_cand_scan) as well as after
1651// (x86_fwd_scan): the same predicate decides candidacy and forwarding, so the two
1652// cannot disagree. b0 = the load's block id; scratch = 2*n_blocks i64 of workspace.
1653// Two rules, tried in order:
1654// SINGLE-USE (the 2026-07-15 G10 rule, unchanged): one consumer, in-block, at an
1655// audited position that is not a SIB-foldable shape, with no store-to-the-
1656// alloca and no call-class op between the load and that consumer.
1657// CFG (LN7): every use of the result (use_count of them) is reached from the load
1658// along a CLEAN path, at an audited POSITION (SIB shapes admitted): walk the
1659// rest of the load's block, then depth-first over successors (terminator
1660// targets), scanning each block from its head; a store to the alloca or a
1661// call-class op KILLS the path there (uses past it are not counted, successors
1662// past it are not followed). SSA dominance puts every use downstream of the
1663// load, so a use never counted lies on a killed path and the load is refused;
1664// counted == use_count guarantees none hides in an unvisited block. The load's
1665// own block is terminal when re-entered through a back edge: the load
1666// re-executes there before any later use can, so the question restarts.
1667// SOUNDNESS: the home register is dedicated and changes only on a store to the
1668// alloca (a G11 in-place chain always ends in one), so on a clean path every
1669// read of the home -- including a SIB fold's read DISPLACED to the consuming
1670// load/store site, the hazard the single-use rule's exclusions exist for --
1671// sees the loaded value. A use at an unaudited position refuses the whole load,
1672// and the elide tripwire in x86_regalloc_function turns any unaudited slot read
1673// into a link failure rather than a silent stale read.
1674// The witness this rung was opened on (nx_probe_bchk_asm): a bounds-checked a[i]
1675// loads i and s BEFORE the check's branches and uses them two blocks later (the
1676// compares, the SIB index, the add), so every such load was homed into a scratch
1677// register via a movq copy per iteration. The CFG rule forwards all three and the
1678// selector no longer spends home registers on them.
1679func x86_fwd_probe(f: *Function, inst: *Instr, alloca_off: *i64, intv: *X86Interval,
1680 b0: i64, scratch: *i64) -> i64 {
1681 if inst.op != OP_LOAD { return 0 - 1 }
1682 let a: i64 = inst.op0
1683 if a < 0 { return 0 - 1 }
1684 if a >= f.n_values { return 0 - 1 }
1685 if alloca_off[a] < 0 { return 0 - 1 }
1686 let lt: *Type = inst.ty
1687 if lt == (0 as *Type) { return 0 - 1 }
1688 if lt.size != 8 { return 0 - 1 }
1689 let r: i64 = inst.result
1690 if r < 0 { return 0 - 1 }
1691 if r >= f.n_values { return 0 - 1 }
1692 let riv: *X86Interval = x86_intv_at(intv, r)
1693 if riv.use_count < 1 { return 0 - 1 }
1694 // ---- SINGLE-USE rule (unchanged G10 walk) ----
1695 if riv.use_count == 1 {
1696 var J: *Instr = inst.next
1697 var verdict: i64 = 0 // 0=scan 1=fwd 2=no
1698 while verdict == 0 {
1699 if J == (0 as *Instr) { verdict = 2 }
1700 if verdict == 0 {
1701 if J.op == OP_STORE { if J.op0 == a {
1702 if X86_NEGCTL_FWD_IGNORE_STORE == 0 { verdict = 2 }
1703 } }
1704 }
1705 if verdict == 0 {
1706 if x86_is_call_class(J.op) == 1 { verdict = 2 }
1707 }
1708 if verdict == 0 {
1709 let nv: i64 = x86_n_value_operands(J)
1710 var kk: i64 = 0
1711 var found: i64 = 0
1712 var okpos: i64 = 1
1713 while kk < nv {
1714 if x86_operand_k(J, kk) == r {
1715 found = 1
1716 if x86_fwd_consumer_ok(f, J, kk) == 0 { okpos = 0 }
1717 }
1718 kk = kk + 1
1719 }
1720 if found == 1 {
1721 if okpos == 1 { verdict = 1 }
1722 if okpos == 0 { verdict = 2 }
1723 }
1724 }
1725 if verdict == 0 { J = J.next }
1726 }
1727 if verdict == 1 { return a }
1728 }
1729 // ---- CFG rule (LN7), SOUND availability ----
1730 // The value loaded from alloca `a` is available at a use iff NO store to `a` (and no call-class
1731 // op, which may clobber through aliasing) lies on any path from THIS load to that use. The load
1732 // re-executes on every entry to its own block, so a store that reaches a use only by passing back
1733 // through the load's block does NOT make the use stale (the classic loop-carried counter). The
1734 // sound, cheap test for that: CUT the load's block out of the CFG, then if any store/call block can
1735 // still reach any use block, some path delivers a stale value -- refuse. This is what the
1736 // 2026-07-15 single-use rule got for free from its in-block/single-consumer constraints; dropping
1737 // those without this check is a MERGE-POINT MISCOMPILE (measured 2026-08-23: it corrupted the
1738 // compiler's own symbol table on self-host -- `sys_mmap not defined` in g2).
1739 if X86_LN7_BLOCK_FWD_ENABLE == 0 { return 0 - 1 }
1740 if scratch == (0 as *i64) { return 0 - 1 }
1741 if b0 < 0 { return 0 - 1 }
1742 if b0 >= f.n_blocks { return 0 - 1 }
1743 let nb: i64 = f.n_blocks
1744 // scratch layout: kill[0..nb) isuse[nb..2nb) visited[2nb..3nb) stack[3nb..4nb)
1745 var zi: i64 = 0
1746 while zi < nb {
1747 scratch[zi] = 0
1748 scratch[nb + zi] = 0
1749 scratch[2 * nb + zi] = 0
1750 zi = zi + 1
1751 }
1752 // Pass: per block, mark kill (store-to-a or call) and audited use of r; refuse an UNAUDITED use.
1753 // Count audited uses so seen == use_count proves every use is understood (none in an unseen block).
1754 var seen: i64 = 0
1755 var refuse: i64 = 0
1756 var bx: i64 = 0
1757 while bx < nb {
1758 let bb: *BasicBlock = x86_block_at(f, bx)
1759 var I2: *Instr = bb.head
1760 while I2 != (0 as *Instr) {
1761 if I2.op == OP_STORE { if I2.op0 == a {
1762 if X86_NEGCTL_FWD_IGNORE_STORE == 0 { scratch[bx] = 1 }
1763 } }
1764 if x86_is_call_class(I2.op) == 1 { scratch[bx] = 1 }
1765 let nv2: i64 = x86_n_value_operands(I2)
1766 var kk2: i64 = 0
1767 while kk2 < nv2 {
1768 if x86_operand_k(I2, kk2) == r {
1769 if x86_fwd_pos_audited(I2.op, kk2) == 0 { refuse = 1 }
1770 scratch[nb + bx] = 1
1771 seen = seen + 1
1772 }
1773 kk2 = kk2 + 1
1774 }
1775 I2 = I2.next
1776 }
1777 bx = bx + 1
1778 }
1779 if refuse == 1 { return 0 - 1 }
1780 if seen != riv.use_count { return 0 - 1 }
1781 // Load-block special case: a store-to-a / call AFTER the load in b0 makes any LATER use in b0
1782 // stale (its value is not the loaded one). Scan b0 from load.next; a kill before any remaining
1783 // in-block use of r is fine (the loop store at the block's tail), a use at-or-after a kill refuses.
1784 var b0_kill_after_load: i64 = 0
1785 var K2: *Instr = inst.next
1786 var b0killed: i64 = 0
1787 while K2 != (0 as *Instr) {
1788 if b0killed == 0 {
1789 if K2.op == OP_STORE { if K2.op0 == a { if X86_NEGCTL_FWD_IGNORE_STORE == 0 { b0killed = 1 } } }
1790 if x86_is_call_class(K2.op) == 1 { b0killed = 1 }
1791 }
1792 if b0killed == 1 {
1793 let nv3: i64 = x86_n_value_operands(K2)
1794 var k3: i64 = 0
1795 while k3 < nv3 { if x86_operand_k(K2, k3) == r { return 0 - 1 } k3 = k3 + 1 }
1796 b0_kill_after_load = 1
1797 }
1798 K2 = K2.next
1799 }
1800 // REACHK: blocks reachable from any kill block (and from b0's successors if b0 exits killed),
1801 // WITHOUT re-entering b0. visited = scratch[2nb..3nb), stack = scratch[3nb..4nb).
1802 scratch[2 * nb + b0] = 1 // b0 is cut
1803 var sp: i64 = 0
1804 var kb: i64 = 0
1805 while kb < nb {
1806 if scratch[kb] == 1 { if kb != b0 { // seed every kill block (not the cut b0)
1807 if scratch[2 * nb + kb] == 0 {
1808 scratch[2 * nb + kb] = 1
1809 scratch[3 * nb + sp] = kb
1810 sp = sp + 1
1811 }
1812 } }
1813 kb = kb + 1
1814 }
1815 if b0_kill_after_load == 1 { sp = x86_fwd_push_succs2(f, x86_block_at(f, b0), scratch, sp, nb) }
1816 while sp > 0 {
1817 sp = sp - 1
1818 let cur: i64 = scratch[3 * nb + sp]
1819 sp = x86_fwd_push_succs2(f, x86_block_at(f, cur), scratch, sp, nb)
1820 }
1821 // Any use block reachable from a kill (without the load) => a stale value can arrive => refuse.
1822 var ub: i64 = 0
1823 while ub < nb {
1824 if ub != b0 { if scratch[nb + ub] == 1 { if scratch[2 * nb + ub] == 1 { return 0 - 1 } } }
1825 ub = ub + 1
1826 }
1827 return a
1828}
1829
1830// LN7 candidacy: fwd_cand[r] = source alloca id for every load that x86_fwd_probe
1831// would forward, else -1. Runs BEFORE select_all so a load that will be forwarded
1832// (zero instructions, reads the alloca's home in place) never competes for -- and
1833// never wins -- a home register of its own: pre-LN7 the selector homed these
1834// loads, STAGE 5 then refused to forward a homed result, and each one cost a
1835// `movq %alloca_home,%value_home` copy per execution PLUS a dedicated register
1836// withheld from the next-best candidate.
1837func x86_fwd_cand_scan(f: *Function, alloca_off: *i64, intv: *X86Interval, fwd_cand: *i64,
1838 scratch: *i64) -> i64 {
1839 var vz: i64 = 0
1840 while vz < f.n_values { fwd_cand[vz] = 0 - 1; vz = vz + 1 }
1841 if X86_FWD_ENABLE == 0 { return 0 }
1842 var bi: i64 = 0
1843 while bi < f.n_blocks {
1844 let b: *BasicBlock = x86_block_at(f, bi)
1845 var inst: *Instr = b.head
1846 while inst != (0 as *Instr) {
1847 if inst.op == OP_LOAD {
1848 let a: i64 = x86_fwd_probe(f, inst, alloca_off, intv, bi, scratch)
1849 if a >= 0 { fwd_cand[inst.result] = a }
1850 }
1851 inst = inst.next
1852 }
1853 bi = bi + 1
1854 }
1855 return 0
1856}
1857
1858// The scan. fwd_home[v] = the source alloca's home index for a forwarded
1859// load result, else -1. Runs after select_all (alloca_home final).
1860// LN7: the decision is x86_fwd_probe (shared with candidacy). A forwardable load
1861// whose result nevertheless holds a home (the residual the candidacy scan could
1862// not see -- it can only arise if the selector homed the load BEFORE its source
1863// alloca, which the wcost order makes impossible for a loaded alloca but is kept
1864// here as the belt) RELEASES that register (iv.reg = -1) and is forwarded; the
1865// caller recomputes used_cs_mask afterwards. Pre-LN7 this was STAGE 5's refusal
1866// ("a HOMED load result must never ALSO be forwarded"): both paths emit no load,
1867// so a value that stayed VL_REGISTER with nothing ever written to its register
1868// would read garbage -- releasing the home is exactly what makes the two
1869// compatible, because the value is then never read through the VL_REGISTER path.
1870func x86_fwd_scan(f: *Function, alloca_off: *i64, alloca_home: *i64,
1871 intv: *X86Interval, fwd_home: *i64, scratch: *i64) -> i64 {
1872 var vz: i64 = 0
1873 while vz < f.n_values { fwd_home[vz] = 0 - 1; vz = vz + 1 }
1874 if X86_FWD_ENABLE == 0 { return 0 }
1875 var bi: i64 = 0
1876 while bi < f.n_blocks {
1877 let b: *BasicBlock = x86_block_at(f, bi)
1878 var inst: *Instr = b.head
1879 while inst != (0 as *Instr) {
1880 var hidx: i64 = 0 - 1
1881 if inst.op == OP_LOAD {
1882 let a: i64 = x86_fwd_probe(f, inst, alloca_off, intv, bi, scratch)
1883 if a >= 0 { if alloca_home[a] >= 0 {
1884 let riv: *X86Interval = x86_intv_at(intv, inst.result)
1885 if riv.reg >= 0 { riv.reg = 0 - 1 } // LN7 release (see above)
1886 hidx = alloca_home[a]
1887 if X86_NEGCTL_FWD_WRONG_HOME == 1 {
1888 hidx = hidx + 1
1889 if hidx >= X86_HOME_CAP { hidx = 0 }
1890 }
1891 } }
1892 }
1893 if hidx >= 0 { fwd_home[inst.result] = hidx }
1894 inst = inst.next
1895 }
1896 bi = bi + 1
1897 }
1898 return 0
1899}
1900
1901// LN7: the callee-saved home mask, derived from the FINAL assignments (SSA homes
1902// with idx < X86_HOME_CAP plus alloca homes) rather than accumulated during
1903// selection -- so a register released by x86_fwd_scan is neither saved nor
1904// restored for nothing, and G5 may hand it to a constant.
1905func x86_recompute_cs_mask(f: *Function, intv: *X86Interval, alloca_off: *i64,
1906 alloca_home: *i64, used_cs_mask_out: *i64) -> i64 {
1907 var m: i64 = 0
1908 var v: i64 = 0
1909 while v < f.n_values {
1910 if alloca_off[v] >= 0 {
1911 if alloca_home[v] >= 0 { if alloca_home[v] < X86_HOME_CAP { m = m | (1 << alloca_home[v]) } }
1912 }
1913 if alloca_off[v] < 0 {
1914 let iv: *X86Interval = x86_intv_at(intv, v)
1915 if iv.reg >= 0 { if iv.reg < X86_HOME_CAP { m = m | (1 << iv.reg) } }
1916 }
1917 v = v + 1
1918 }
1919 *used_cs_mask_out = m
1920 return 0
1921}
1922
1923// ===== UNIFIED SOTA SELECTION (2026-07-15) ==========================
1924// Rank ALL homing candidates -- homeable SSA values (iv.reg) AND eligible
1925// allocas (alloca_home) -- TOGETHER by loop-weighted wcost, greedily giving each
1926// the best LEGAL register. Constraints: allocas home their whole-function
1927// storage so they MUST use callee-saved (survives the setup calls); a
1928// cross-call SSA value also needs callee-saved; a call-free SSA value prefers a
1929// caller-saved reg (rsi/rdi/r8/r9, no prologue save) to leave callee-saved for
1930// those that need them. Each homed value gets a DEDICATED register for its whole
1931// range (no two share) -> sound under SSA dominance. This replaces the old
1932// SSA-first-then-alloca two-pass scheme that let cold single-use SSA temps grab
1933// the callee-saved regs the hot loop-carried allocas needed.
1934// LN7: is v a G4-class temp -- single use, consumed by the IMMEDIATELY NEXT
1935// instruction at a position x86_g4_pos_ok serves from rax? Mirrors the producer,
1936// use-count and position tests of x86_g4_elide_scan, with the consumer's homing
1937// read from the live intervals (selection is in progress) instead of final locs.
1938// Such a value is carried in rax between producer and consumer at zero cost; a
1939// home register would be spent to add a move. Decided per pick, not once.
1940func x86_ln7_rax_served(f: *Function, intv: *X86Interval, alloca_off: *i64, v: i64) -> i64 {
1941 if X86_LN7_BLOCK_FWD_ENABLE == 0 { return 0 }
1942 if alloca_off[v] >= 0 { return 0 }
1943 let iv: *X86Interval = x86_intv_at(intv, v)
1944 if iv.use_count != 1 { return 0 }
1945 let val: *Value = x86_val_at(f, v)
1946 if val.kind != VK_INSTR { return 0 }
1947 let inst: *Instr = val.instr
1948 if inst == (0 as *Instr) { return 0 }
1949 if inst.ty == (0 as *Type) { return 0 }
1950 if inst.ty.kind == TY_VOID { return 0 }
1951 if x86_g4_producer_ok(inst.op) == 0 { return 0 }
1952 let nxt: *Instr = inst.next
1953 if nxt == (0 as *Instr) { return 0 }
1954 var jres_homed: i64 = 0
1955 let jr: i64 = nxt.result
1956 if jr >= 0 { if jr < f.n_values {
1957 let jiv: *X86Interval = x86_intv_at(intv, jr)
1958 if jiv.reg >= 0 { jres_homed = 1 }
1959 } }
1960 let nv: i64 = x86_n_value_operands(nxt)
1961 var k: i64 = 0
1962 while k < nv {
1963 if x86_operand_k(nxt, k) == v {
1964 if x86_g4_pos_ok(nxt.op, k, jres_homed) == 1 { return 1 }
1965 }
1966 k = k + 1
1967 }
1968 return 0
1969}
1970
1971func x86_select_all(f: *Function, intv: *X86Interval, alloca_off: *i64,
1972 any_call: *i64, elig: *i64, alloca_home: *i64,
1973 used_cs_mask_out: *i64, wcost: *i64, fwd_cand: *i64) -> i64 {
1974 *used_cs_mask_out = 0
1975 if X86_HOME_CAP_ENABLE == 0 { return 0 }
1976 let fn_clob: i64 = x86_fn_has_clobber_intrinsic(f)
1977 var caller_mask: i64 = 0
1978 var done: i64 = 0
1979 while done == 0 {
1980 // Current register availability.
1981 var free_callee: i64 = 0
1982 var cb: i64 = 0
1983 while cb < X86_HOME_CAP {
1984 if ((used_cs_mask_out[0] >> cb) & 1) == 0 { free_callee = free_callee + 1 }
1985 cb = cb + 1
1986 }
1987 var free_caller: i64 = 0
1988 if X86_CALLER_POOL_ENABLE == 1 { if fn_clob == 0 {
1989 var qb: i64 = 0
1990 while qb < X86_CALLER_CAP {
1991 if ((caller_mask >> qb) & 1) == 0 { free_caller = free_caller + 1 }
1992 qb = qb + 1
1993 }
1994 } }
1995 // Pick the highest-wcost PLACEABLE candidate.
1996 var best: i64 = 0 - 1
1997 var best_w: i64 = 0 - 1
1998 var best_alloca: i64 = 0
1999 var best_needs_callee: i64 = 0
2000 var v: i64 = 0
2001 while v < f.n_values {
2002 let iv: *X86Interval = x86_intv_at(intv, v)
2003 var is_cand: i64 = 0
2004 var is_alloca: i64 = 0
2005 if alloca_off[v] >= 0 {
2006 if elig[v] == 1 { if alloca_home[v] < 0 { is_cand = 1; is_alloca = 1 } }
2007 }
2008 if alloca_off[v] < 0 {
2009 if iv.reg < 0 { if x86_is_homeable(f, intv, alloca_off, any_call, v) == 1 { is_cand = 1 } }
2010 // LN7: a load that x86_fwd_scan WILL forward (its source alloca is
2011 // already homed -- allocas outrank their own loads by wcost, so the
2012 // alloca is decided first) costs zero instructions and needs no home.
2013 // Giving it one would spend a register to materialize a copy.
2014 if is_cand == 1 { if fwd_cand[v] >= 0 { if alloca_home[fwd_cand[v]] >= 0 { is_cand = 0 } } }
2015 // LN7: a single-use temp the NEXT instruction consumes from rax (the
2016 // G4 class: slot store elided, G1 forwards rax) is already free --
2017 // a home can only add the move the consumer then needs. Evaluated
2018 // with the consumer's CURRENT homing, exactly as x86_g4_elide_scan
2019 // will evaluate it on the final locs, so the two cannot disagree:
2020 // if the consumer's result is homed later, v is re-offered here.
2021 if is_cand == 1 { if x86_ln7_rax_served(f, intv, alloca_off, v) == 1 { is_cand = 0 } }
2022 // G13 (2026-07-16): BIG CONSTANTS compete for homes by wcost
2023 // like everything else -- a non-imm32 const re-materializes a
2024 // 10-byte movabsq at EVERY use (per-iteration in loops). The
2025 // prologue materializer + VL_REGISTER read path already exist
2026 // (G5); the old G5 selector only got LEFTOVER regs, which the
2027 // unified allocator never leaves. crosses_call gates caller-
2028 // saved exactly as for SSA values (read-only, but a clobbered
2029 // caller-saved home would still read garbage).
2030 if is_cand == 0 { if iv.reg < 0 { if iv.start >= 0 {
2031 let g13v: *Value = x86_val_at(f, v)
2032 if g13v.kind == VK_CONST_INT {
2033 if x86_g5_imm32_ok(g13v.const_int) == 0 { is_cand = 1 }
2034 }
2035 } } }
2036 }
2037 if is_cand == 1 {
2038 var nc: i64 = 0
2039 if is_alloca == 1 { nc = 1 }
2040 if is_alloca == 0 { if iv.crosses_call == 1 { if X86_NEGCTL_CALLER_IGNORE_CALL == 0 { nc = 1 } } }
2041 var placeable: i64 = 0
2042 if nc == 1 { if free_callee > 0 { placeable = 1 } }
2043 if nc == 0 {
2044 if free_callee > 0 { placeable = 1 }
2045 if free_caller > 0 { if wcost[v] >= X86_CALLER_MIN_WCOST { placeable = 1 } }
2046 // G13: call-free CONSTANTS take caller-saved at ANY wcost --
2047 // read-only, so a caller-saved home has zero move overhead
2048 // (no store-back ever; one prologue movabsq). MUST mirror
2049 // the chosen-branch exemption below or the pick loop hangs.
2050 if placeable == 0 { if free_caller > 0 {
2051 let g13p: *Value = x86_val_at(f, v)
2052 if g13p.kind == VK_CONST_INT { placeable = 1 }
2053 } }
2054 }
2055 if placeable == 1 { if wcost[v] > best_w {
2056 best = v; best_w = wcost[v]; best_alloca = is_alloca; best_needs_callee = nc
2057 } }
2058 }
2059 v = v + 1
2060 }
2061 if best < 0 { done = 1 }
2062 if best >= 0 { if best_w < X86_HOME_MIN_USES { done = 1 } }
2063 if done == 0 {
2064 var chosen: i64 = 0 - 1
2065 // Deep-loop call-free SSA prefers caller-saved (leave callee for those
2066 // needing it); shallow values (wcost < threshold) fall through to
2067 // callee-only, matching the baseline for tight scalar loops.
2068 // G13: constants are caller-eligible at ANY wcost (mirrors placeable).
2069 var cpref: i64 = 0
2070 if best_needs_callee == 0 { if free_caller > 0 {
2071 if best_w >= X86_CALLER_MIN_WCOST { cpref = 1 }
2072 if cpref == 0 {
2073 let g13b: *Value = x86_val_at(f, best)
2074 if g13b.kind == VK_CONST_INT { cpref = 1 }
2075 }
2076 } }
2077 if cpref == 1 {
2078 var qb2: i64 = 0
2079 while qb2 < X86_CALLER_CAP {
2080 if chosen < 0 { if ((caller_mask >> qb2) & 1) == 0 {
2081 chosen = X86_CALLER_BASE + qb2
2082 caller_mask = caller_mask | (1 << qb2)
2083 } }
2084 qb2 = qb2 + 1
2085 }
2086 }
2087 if chosen < 0 {
2088 var cb2: i64 = 0
2089 while cb2 < X86_HOME_CAP {
2090 if chosen < 0 { if ((used_cs_mask_out[0] >> cb2) & 1) == 0 {
2091 chosen = cb2
2092 used_cs_mask_out[0] = used_cs_mask_out[0] | (1 << cb2)
2093 } }
2094 cb2 = cb2 + 1
2095 }
2096 }
2097 if best_alloca == 1 { alloca_home[best] = chosen }
2098 if best_alloca == 0 { let biv: *X86Interval = x86_intv_at(intv, best); biv.reg = chosen }
2099 }
2100 }
2101 return 0
2102}
2103
2104// ----- allocator entry (STEP 2b + G2: SSA homes, then alloca homes) ----
2105// alloca_off (authoritative alloca map, FIX-10). alloca_home[v] receives the
2106// G2 home index (0..4) for a registerized alloca, or -1. elide[v]=1 marks
2107// G4 dead-store temps (see x86_g4_elide_scan).
2108func x86_regalloc_function(f: *Function, alloca_off: *i64,
2109 locs: *ValueLoc, used_cs_mask_out: *i64,
2110 alloca_home: *i64, elide: *i64,
2111 fwd_home: *i64, chain_home: *i64, chain_swap: *i64) -> i64 {
2112 let n: i64 = f.n_values
2113 let intv_raw: *u8 = sys_mmap(n * 64 + 16)
2114 let intv: *X86Interval = intv_raw as *X86Interval
2115 let calls_raw: *u8 = sys_mmap(f.n_instrs * 8 + 32)
2116 let calls: *i64 = calls_raw as *i64
2117 let nc_raw: *u8 = sys_mmap(16)
2118 let nc: *i64 = nc_raw as *i64
2119 *nc = 0
2120 let ac_raw: *u8 = sys_mmap(n * 8 + 16)
2121 let any_call: *i64 = ac_raw as *i64
2122 let bs_raw: *u8 = sys_mmap(f.n_blocks * 8 + 16)
2123 let bb_start: *i64 = bs_raw as *i64
2124 let be_raw: *u8 = sys_mmap(f.n_blocks * 8 + 16)
2125 let bb_end: *i64 = be_raw as *i64
2126
2127 x86_build_intervals(f, intv, calls, nc, any_call, bb_start, bb_end)
2128 // G13: a homed CONST is materialized in the PROLOGUE -- its effective live
2129 // range is [0, last use], NOT [first use, last use]. Stretch starts to 0 so
2130 // crosses_call counts SETUP calls too (a caller-saved const home clobbered
2131 // by a pre-loop syscall's arg setup = the sha256/lcg/fnv miscompile the
2132 // battery caught 2026-07-16; call-free functions still go caller-saved).
2133 var g13i: i64 = 0
2134 while g13i < n {
2135 let g13iv: *X86Interval = x86_intv_at(intv, g13i)
2136 if g13iv.start > 0 {
2137 let g13val: *Value = x86_val_at(f, g13i)
2138 if g13val.kind == VK_CONST_INT { g13iv.start = 0 }
2139 }
2140 g13i = g13i + 1
2141 }
2142 // STOP-SHIP fix: extend intervals across back-edges BEFORE the call scan,
2143 // so loop-internal calls are counted for values live across the edge.
2144 x86_extend_backedge_intervals(f, intv, bb_start, bb_end)
2145 x86_mark_crosses_call(intv, n, calls, *nc)
2146 // SOTA: loop-depth-weighted spill cost drives BOTH SSA and alloca selection.
2147 let dep_raw: *u8 = sys_mmap(f.n_blocks * 8 + 16)
2148 let depth: *i64 = dep_raw as *i64
2149 let wc_raw: *u8 = sys_mmap(n * 8 + 16)
2150 let wcost: *i64 = wc_raw as *i64
2151 x86_compute_loop_depth(f, depth)
2152 x86_compute_wcost(f, depth, wcost)
2153 // UNIFIED SOTA selection: SSA values AND allocas ranked TOGETHER by
2154 // loop-weighted wcost. ah_scan first (computes alloca eligibility `elig`),
2155 // then one pass gives each candidate the best legal register (allocas +
2156 // cross-call SSA -> callee-saved; call-free SSA prefers caller-saved).
2157 var ai: i64 = 0
2158 while ai < n { alloca_home[ai] = 0 - 1; ai = ai + 1 }
2159 let el_raw: *u8 = sys_mmap(n * 8 + 16)
2160 let elig: *i64 = el_raw as *i64
2161 let ct_raw: *u8 = sys_mmap(n * 8 + 16)
2162 let acnt: *i64 = ct_raw as *i64
2163 x86_ah_scan(f, alloca_off, elig, acnt)
2164 // LN7: forwardable loads are known BEFORE selection (the probe is independent of
2165 // alloca_home), so the selector can decline to home what forwarding makes free.
2166 let fc_raw: *u8 = sys_mmap(n * 8 + 16)
2167 let fwd_cand: *i64 = fc_raw as *i64
2168 let fs_raw: *u8 = sys_mmap(f.n_blocks * 32 + 32) // kill + isuse + visited + stack (4 x n_blocks)
2169 let fwd_scratch: *i64 = fs_raw as *i64
2170 x86_fwd_cand_scan(f, alloca_off, intv, fwd_cand, fwd_scratch)
2171 x86_select_all(f, intv, alloca_off, any_call, elig, alloca_home, used_cs_mask_out, wcost, fwd_cand)
2172 // G10: home-forwarding scan (needs the FINAL alloca_home + use counts).
2173 x86_fwd_scan(f, alloca_off, alloca_home, intv, fwd_home, fwd_scratch)
2174 // LN7: the scan may have released a home (residual case); the save/restore mask
2175 // and G5's free-register view must describe the FINAL assignments.
2176 x86_recompute_cs_mask(f, intv, alloca_off, alloca_home, used_cs_mask_out)
2177 // G11: chain fusion scan (runs AFTER fwd_scan -- it writes fwd_home[head]
2178 // for the chain-head kill and must not be wiped by fwd_scan's init).
2179 x86_chain_scan(f, alloca_off, alloca_home, intv, fwd_home, chain_home, chain_swap)
2180
2181 // Lower SSA intervals to ValueLocs: homed (iv.reg>=0) -> VL_REGISTER else spill.
2182 let lbase: i64 = locs as i64
2183 var k: i64 = 0
2184 while k < n {
2185 let iv: *X86Interval = x86_intv_at(intv, k)
2186 let l: *ValueLoc = (lbase + k * 16) as *ValueLoc
2187 if iv.reg >= 0 {
2188 l.kind = VL_REGISTER
2189 l.idx = iv.reg
2190 }
2191 if iv.reg < 0 {
2192 l.kind = VL_SPILLED
2193 l.idx = 0 - 1
2194 }
2195 k = k + 1
2196 }
2197
2198 // G5: big constants take whatever homes remain.
2199 x86_g5_select_const_homes(f, intv, locs, used_cs_mask_out)
2200
2201 // G4: dead single-use temp stores (needs the FINAL locs -- runs last).
2202 x86_g4_elide_scan(f, locs, alloca_off, intv, elide, chain_home, chain_swap, fwd_home)
2203 // G10 tripwire: a forwarded (killed) load's slot is NEVER written; flag it
2204 // elide so any unaudited slot read hits the loud .G4_elided_slot_load_bug
2205 // link failure instead of silently reading stale stack garbage. (The fwd
2206 // check in load_value_v/load_value runs BEFORE the elide tripwire, so the
2207 // one legitimate consumer is unaffected.)
2208 var tw: i64 = 0
2209 while tw < n {
2210 if fwd_home[tw] >= 0 { elide[tw] = 1 }
2211 // G11 tripwire: chain-internal values never materialize anywhere (the
2212 // next chain step operates on the home in place); an unaudited slot
2213 // read must fail loud, not read stale garbage.
2214 if chain_home[tw] >= 0 { elide[tw] = 1 }
2215 tw = tw + 1
2216 }
2217 return 0
2218}