nx_regalloc.nx source
↩ module page · 1112 lines · 42982 B
1// regalloc.nx -- linear-scan register allocator, in NishiLang.
2//
3// Port of regalloc.c. Poletto-Sarkar 1999 with back-edge extension
4// (so values live across a loop keep their register). Separate
5// pools for caller-clobbered temps (t0..t3) and callee-saved
6// registers (s0..s11). Values that cross a call go to s-regs; the
7// emitted function saves only the s-regs it touched.
8//
9// Produces a ValueLoc table: one entry per Value, either
10// { kind = REGISTER, idx = reg_index } or
11// { kind = SPILLED, idx = sp-relative byte offset }.
12//
13// Shared struct layout with ir.nx: same Value/Instr/BasicBlock/
14// Function shapes. Redeclared here for scope; future module-import
15// eliminates the duplication.
16
17// ---- syscalls ----
18
19// ---- IR shapes (must match ir.nx / opt.nx) ----
20
21// nx_safety_envelope: (schema: nishi-library/seeds/safety-critical-standards.toml)
22// intended_use: "Linear-scan register allocator (Poletto-Sarkar
23// 1999) -- GPR + FPR passes with spillAtInterval
24// eviction. Output ValueLoc table consumed by
25// nx_riscv codegen."
26// sil_target: SIL2 (allocator correctness affects every
27// compiled program)
28// asil_target: QM
29// dal_target: DAL B
30// iec_62304_class: NONE
31// evidence: [no_floating_point, bounded_intervals,
32// spill_furthest_active_class_agnostic,
33// rematerialisation_for_VAL_CONST,
34// Poletto_Sarkar_1999_algorithm_match,
35// smoke_GPR_eviction_proven,
36// smoke_FPR_eviction_proven]
37// hazard_register: [bug-tape-F14-codegen-register-collision,
38// bug-tape-loop-carried-interval-clobber,
39// bug-tape-F16-self-compile-via-this-file,
40// bug-tape-alloca-not-rematerialised]
41// residual_risk: "VAL_ALLOCA is NOT rematerialisable (gap
42// documented at lines 612-617 + bench/
43// ir_diff_corpus/regression_alloca_remat_
44// param_step_loop.nx). Allocas get t-reg
45// homes that intermediate compare/binop
46// instructions can clobber across loop
47// iterations -> SIGSEGV. Fix is queued;
48// gauntlet has the behavioural oracle."
49// verdict: NOT_YET_EVALUATED
50
51import "nx_syscalls.nx"
52import "nx_types.nx"
53import "nx_ir.nx"
54const FREG_MAGIC_1024: i64 = 1024
55const FREG_MAGIC_4096: i64 = 4096
56// ---- per-value live interval ----
57//
58// [start, end] both inclusive. reg = -1 means spilled. slot = -1
59// means not yet spilled. crosses_call = 1 forces s-reg preference.
60
61struct Interval {
62 v: i64,
63 start: i64,
64 end: i64,
65 reg: i64,
66 slot: i64,
67 crosses_call: i64,
68}
69
70// ---- final per-value location ----
71//
72// Consumed by riscv.nx codegen. kind=0 register, kind=1 spilled.
73
74// ---- register pool ----
75//
76// Integer (GPR) pool:
77// 0..3 t0..t3 (caller-clobbered; 4 regs)
78// 4..15 s0..s11 (callee-saved; 12 regs)
79//
80// Float (FPR) pool -- RV64F / RV64D:
81// 100..107 ft0..ft7 (caller-clobbered)
82// 108..111 ft8..ft11 (caller-clobbered)
83// 200..211 fs0..fs11 (callee-saved)
84//
85// Offset 100 / 200 lets us store GPR and FPR indices in the
86// same `reg` field without conflict. is_float_reg() tests the
87// tag; is_callee_saved() distinguishes within each bank.
88//
89// For v0.0.1, f-reg pool is DECLARED but the allocator logic
90// stays GPR-only -- F-extension lowering in runtime/riscv.nx
91// wires this pool in when OP_FADD et al. land. See IR type +
92// opcode reservations in types.nx (TY_F32/F64, OP_F*).
93
94const FREG_BASE_T: i64 = 100 // ft0 = 100
95const FREG_BASE_S: i64 = 200 // fs0 = 200
96const NUM_FT: i64 = 12 // ft0..ft11
97const NUM_FS: i64 = 12 // fs0..fs11
98
99// RVV vector register pool. 32 v-regs (v0..v31). Indices 300..331
100// share the same `reg` field as GPR/FPR homes without collision
101// because scalar pools are strictly < 300. Scratches v0/v1 reserved
102// for codegen-emitted vsetvli+broadcast sequences and mask ops (v0
103// is ISA-mandated mask register); the allocator pool excludes both.
104//
105// v0.0.1: the allocator does NOT yet assign v-reg homes. The pool
106// scheme is reserved here so downstream code can use is_vec_reg()
107// + reg_name() dispatching once the third linear-scan pass lands.
108const VREG_BASE: i64 = 300 // v0 = 300
109const NUM_V: i64 = 32 // v0..v31
110const VREG_SCRATCH_0: i64 = 300 // v0 (ISA mask reg)
111const VREG_SCRATCH_1: i64 = 301 // v1 (spill scratch)
112
113func is_vec_reg(r: i64) -> i64 {
114 if r >= VREG_BASE { return 1 }
115 return 0
116}
117
118func num_vregs() -> i64 { return NUM_V - 2 } // minus v0/v1 scratches
119
120func is_float_reg(r: i64) -> i64 {
121 if r >= FREG_BASE_T { return 1 }
122 return 0
123}
124
125func is_callee_saved(r: i64) -> i64 {
126 // GPR callee-saved range.
127 if r >= 4 { if r < FREG_BASE_T { return 1 } }
128 // FPR callee-saved range (fs0..fs11).
129 if r >= FREG_BASE_S { return 1 }
130 return 0
131}
132
133func num_regs() -> i64 { return 16 }
134func num_fregs() -> i64 { return NUM_FT + NUM_FS }
135
136// Scratch f-reg indices reserved by riscv.nx codegen (rv_emit_fbinop,
137// fmaterialise, emit_sp_flw/fsw). Allocator MUST exclude these from
138// the FPR pool -- otherwise a value assigned to ft4 would be corrupted
139// when rv_emit_fbinop materialises op0 into ft4. Mirrors the GPR
140// convention where t4/t5/t6 aren't in the regalloc pool either
141// (indices 4-15 map to s0..s11; the GPR allocator simply never
142// produces t4/t5/t6).
143const FREG_SCRATCH_4: i64 = 104 // ft4
144const FREG_SCRATCH_5: i64 = 105 // ft5
145const FREG_SCRATCH_6: i64 = 106 // ft6
146
147// Is Value `v` a floating-point value? Used to partition the ids
148// list between the GPR and FPR linear-scan passes. Returns 0 when
149// the Value has no type (e.g. raw param placeholder) so the caller
150// treats it as GPR.
151func is_float_value(f: *Function, v: i64) -> i64 {
152 if v >= f.n_values { return 0 }
153 let base: i64 = f.values as i64
154 let val: *Value = (base + v * 48) as *Value
155 if val.ty == (0 as *Type) { return 0 }
156 let k: i64 = val.ty.kind
157 if k == TY_F32 { return 1 }
158 if k == TY_F64 { return 1 }
159 return 0
160}
161
162// ---- helpers: pool access ----
163
164func intv_at(buf: *Interval, id: i64) -> *Interval {
165 let base: i64 = buf as i64
166 return (base + id * 48) as *Interval
167}
168
169// ---- interval construction ----
170//
171// Walk instructions in block order (flat concat; proper liveness
172// comes via dom-based back-edge extension). For each instruction
173// at index `idx`:
174// * Defs: extend intv.start for the result Value to idx
175// * Uses: extend intv.end for each operand Value to idx
176
177func build_intervals(f: *Function,
178 intv: *Interval,
179 calls: *i64, n_calls_ptr: *i64,
180 bb_start: *i64, bb_end: *i64) -> i64 {
181 // Initialise every interval to "unused".
182 var v: i64 = 0
183 while v < f.n_values {
184 let iv: *Interval = intv_at(intv, v)
185 iv.v = v
186 iv.start = -1
187 iv.end = -1
188 iv.reg = -1
189 iv.slot = -1
190 iv.crosses_call = 0
191 v = v + 1
192 }
193 // Parameters are live from index 0.
194 v = 0
195 while v < f.n_values {
196 let vv: *Value = val_at(f, v)
197 if vv.kind == 1 {
198 let iv: *Interval = intv_at(intv, v)
199 iv.start = 0
200 iv.end = 0
201 }
202 v = v + 1
203 }
204
205 var idx: i64 = 1
206 var bi: i64 = 0
207 var n_calls: i64 = 0
208 while bi < f.n_blocks {
209 let b: *BasicBlock = block_at(f, bi)
210 bb_start[bi] = idx
211 var inst: *Instr = b.head
212 while inst != (0 as *Instr) {
213 // Def: the instruction's result.
214 if inst.ty != (0 as *Type) {
215 if inst.ty.kind != 0 {
216 let rv: *Interval = intv_at(intv, inst.result)
217 if rv.start < 0 { rv.start = idx }
218 if rv.end < idx { rv.end = idx }
219 }
220 }
221 // Uses: up to 4 operands. BR operand is a block id,
222 // not a Value; skip it.
223 //
224 // (Extending to op4..op7 was attempted 2026-05-19 but
225 // caused a regression in simpler programs. The change
226 // shifted regalloc decisions for SIMPLE main()s in a
227 // way that broke the bootstrap. Leaving at op0..op3 for
228 // now until we can do the extension WITHOUT side-effects
229 // on already-working cases. See task #10 / nx_codegen_diff.
230 // Cardinal 3: rewrite from scratch if 2nd fix fails.
231 // Better: port C's compute_liveness in full instead of
232 // patching build_intervals.)
233 if inst.op != 31 {
234 let n: i64 = inst.n_operands
235 if n >= 1 {
236 let u: *Interval = intv_at(intv, inst.op0)
237 if u.start < 0 { u.start = idx }
238 if u.end < idx { u.end = idx }
239 }
240 if n >= 2 {
241 let u: *Interval = intv_at(intv, inst.op1)
242 if u.start < 0 { u.start = idx }
243 if u.end < idx { u.end = idx }
244 }
245 if n >= 3 {
246 let u: *Interval = intv_at(intv, inst.op2)
247 if u.start < 0 { u.start = idx }
248 if u.end < idx { u.end = idx }
249 }
250 if n >= 4 {
251 let u: *Interval = intv_at(intv, inst.op3)
252 if u.start < 0 { u.start = idx }
253 if u.end < idx { u.end = idx }
254 }
255 }
256 // Track CALL sites so we can mark crosses-call ranges. BOTH direct
257 // (OP_CALL=33) AND indirect (OP_CALL_INDIRECT=144) calls clobber the
258 // caller-saved regs, so an interval live across EITHER must land in a
259 // callee-saved s-reg. Missing 144 meant a fn-ptr call in a loop
260 // clobbered the live accumulator/index/base -> the dispatch table
261 // returned 206 not 50 (caught by the array-of-fn-ptr oracle).
262 if inst.op == 33 {
263 calls[n_calls] = idx
264 n_calls = n_calls + 1
265 }
266 if inst.op == 144 {
267 calls[n_calls] = idx
268 n_calls = n_calls + 1
269 }
270 idx = idx + 1
271 inst = inst.next
272 }
273 bb_end[bi] = idx - 1
274 bi = bi + 1
275 }
276 // ★BUG 8: loop-carried interval extension (see cardinal note in regalloc_function). Extend to the back-edge
277 // every interval that overlaps a loop and ends inside it, so a value used across the back-edge stays live.
278 var le_changed: i64 = 1
279 var le_rounds: i64 = 0
280 while le_changed != 0 {
281 le_changed = 0
282 le_rounds = le_rounds + 1
283 var le_go: i64 = 1
284 if le_rounds > 64 { le_go = 0 }
285 if le_go == 1 {
286 var lb: i64 = 0
287 while lb < f.n_blocks {
288 let bbx: *BasicBlock = block_at(f, lb)
289 var se: i64 = 0
290 while se < 2 {
291 var succ: *BasicBlock = 0 as *BasicBlock
292 if se == 0 { if bbx.n_succs >= 1 { succ = bbx.succ0 } }
293 if se == 1 { if bbx.n_succs >= 2 { succ = bbx.succ1 } }
294 if succ != (0 as *BasicBlock) {
295 let sid: i64 = succ.id
296 if sid <= lb {
297 let loop_start: i64 = bb_start[sid]
298 let loop_end: i64 = bb_end[lb]
299 var vv2: i64 = 0
300 while vv2 < f.n_values {
301 let iv2: *Interval = intv_at(intv, vv2)
302 if iv2.start >= 0 {
303 if iv2.start <= loop_end {
304 if iv2.end >= loop_start {
305 if iv2.end < loop_end {
306 iv2.end = loop_end
307 le_changed = 1
308 }
309 }
310 }
311 }
312 vv2 = vv2 + 1
313 }
314 }
315 }
316 se = se + 1
317 }
318 lb = lb + 1
319 }
320 }
321 }
322 *n_calls_ptr = n_calls
323 return idx
324}
325
326// ---- compute_liveness (port of regalloc.c:302-432) ---------------
327//
328// Standard backward-dataflow liveness analysis. build_intervals
329// alone only tracks the LITERAL define-to-last-use range, which
330// misses values that flow through intermediate BBs (especially
331// across back-edges in loops). compute_liveness extends each
332// interval to cover EVERY BB where the value is live, so linear-
333// scan correctly preserves the register/slot across the full range.
334//
335// Closes M0a-gate2 root cause: NX regalloc systematically under-
336// spilled relative to C, because build_intervals' per-instruction
337// tracking missed cross-BB liveness extensions.
338//
339// Bit-set storage: i64 words, 64 values per word.
340
341func cl_bit_get(bs: *i64, v: i64) -> i64 {
342 let w: i64 = v >> 6
343 let b: i64 = v & 63
344 return (bs[w] >> b) & 1
345}
346
347func cl_bit_set(bs: *i64, v: i64) -> i64 {
348 let w: i64 = v >> 6
349 let b: i64 = v & 63
350 bs[w] = bs[w] | (1 << b)
351 return 0
352}
353
354// Words needed for n values, ceiling-rounded.
355func cl_words(n: i64) -> i64 {
356 return (n + 63) >> 6
357}
358
359func compute_liveness(f: *Function, intv: *Interval,
360 bb_start: *i64, bb_end: *i64) -> i64 {
361 if f.n_blocks == 0 { return 0 }
362 let n: i64 = f.n_values
363 let nb: i64 = f.n_blocks
364 if n == 0 { return 0 }
365
366 let words: i64 = cl_words(n)
367 let bytes_per_set: i64 = words * 8
368
369 // Per-BB bitsets: use_, def_, live_in, live_out.
370 let use_buf: *u8 = sys_mmap(bytes_per_set * nb + 16)
371 let def_buf: *u8 = sys_mmap(bytes_per_set * nb + 16)
372 let in_buf: *u8 = sys_mmap(bytes_per_set * nb + 16)
373 let out_buf: *u8 = sys_mmap(bytes_per_set * nb + 16)
374 let ni_buf: *u8 = sys_mmap(bytes_per_set + 16)
375 let no_buf: *u8 = sys_mmap(bytes_per_set + 16)
376
377 let use_: *i64 = use_buf as *i64
378 let def_: *i64 = def_buf as *i64
379 let live_in: *i64 = in_buf as *i64
380 let live_out:*i64 = out_buf as *i64
381 let ni: *i64 = ni_buf as *i64
382 let no: *i64 = no_buf as *i64
383
384 // Build use[b] and def[b] sets per BB. use[b][v]=1 iff v is
385 // used in b before any def in b. def[b][v]=1 iff v is defined
386 // anywhere in b.
387 var b: i64 = 0
388 while b < nb {
389 let bb: *BasicBlock = block_at(f, b)
390 let u: *i64 = ((use_ as i64) + b * bytes_per_set) as *i64
391 let d: *i64 = ((def_ as i64) + b * bytes_per_set) as *i64
392 var inst: *Instr = bb.head
393 while inst != (0 as *Instr) {
394 // Uses: walk all 8 inline operand slots. Unlike the
395 // per-instruction interval extension in build_intervals
396 // (which broke when op4..op7 were added there), here we
397 // only ADD to the use[] set, which then flows through
398 // proper backward dataflow. No per-instruction
399 // interval semantics to corrupt.
400 // OP_BR (31) operand is a block id, not a Value; skip.
401 if inst.op != 31 {
402 let nops: i64 = inst.n_operands
403 if nops >= 1 {
404 let v: i64 = inst.op0
405 if v < n {
406 if cl_bit_get(d, v) == 0 { cl_bit_set(u, v) }
407 }
408 }
409 if nops >= 2 {
410 let v: i64 = inst.op1
411 if v < n {
412 if cl_bit_get(d, v) == 0 { cl_bit_set(u, v) }
413 }
414 }
415 if nops >= 3 {
416 let v: i64 = inst.op2
417 if v < n {
418 if cl_bit_get(d, v) == 0 { cl_bit_set(u, v) }
419 }
420 }
421 if nops >= 4 {
422 let v: i64 = inst.op3
423 if v < n {
424 if cl_bit_get(d, v) == 0 { cl_bit_set(u, v) }
425 }
426 }
427 if nops >= 5 {
428 let v: i64 = inst.op4
429 if v < n {
430 if cl_bit_get(d, v) == 0 { cl_bit_set(u, v) }
431 }
432 }
433 if nops >= 6 {
434 let v: i64 = inst.op5
435 if v < n {
436 if cl_bit_get(d, v) == 0 { cl_bit_set(u, v) }
437 }
438 }
439 if nops >= 7 {
440 let v: i64 = inst.op6
441 if v < n {
442 if cl_bit_get(d, v) == 0 { cl_bit_set(u, v) }
443 }
444 }
445 if nops >= 8 {
446 let v: i64 = inst.op7
447 if v < n {
448 if cl_bit_get(d, v) == 0 { cl_bit_set(u, v) }
449 }
450 }
451 }
452 // Def: instruction's result (if non-void).
453 if inst.ty != (0 as *Type) {
454 if inst.ty.kind != 0 {
455 let r: i64 = inst.result
456 if r < n { cl_bit_set(d, r) }
457 }
458 }
459 inst = inst.next
460 }
461 b = b + 1
462 }
463
464 // Iterate to fixed point. Backward dataflow: live_out[b] is
465 // the union of live_in[s] over successors s; live_in[b] is
466 // use[b] union (live_out[b] & ~def[b]). ~def computed as XOR
467 // identity: a & ~d == a ^ (a & d).
468 var changed: i64 = 1
469 var rounds: i64 = 0
470 while changed != 0 {
471 if rounds >= FREG_MAGIC_1024 { changed = 0; break }
472 rounds = rounds + 1
473 changed = 0
474 var bi: i64 = nb - 1
475 while bi >= 0 {
476 let bb: *BasicBlock = block_at(f, bi)
477 let u: *i64 = ((use_ as i64) + bi * bytes_per_set) as *i64
478 let d: *i64 = ((def_ as i64) + bi * bytes_per_set) as *i64
479 let li: *i64 = ((live_in as i64) + bi * bytes_per_set) as *i64
480 let lo: *i64 = ((live_out as i64) + bi * bytes_per_set) as *i64
481
482 // new_out = union of successors' live_in.
483 var w: i64 = 0
484 while w < words {
485 no[w] = 0
486 w = w + 1
487 }
488 if bb.n_succs >= 1 {
489 if bb.succ0 != (0 as *BasicBlock) {
490 let sid: i64 = bb.succ0.id
491 if sid < nb {
492 let sin: *i64 = ((live_in as i64) + sid * bytes_per_set) as *i64
493 w = 0
494 while w < words {
495 no[w] = no[w] | sin[w]
496 w = w + 1
497 }
498 }
499 }
500 }
501 if bb.n_succs >= 2 {
502 if bb.succ1 != (0 as *BasicBlock) {
503 let sid: i64 = bb.succ1.id
504 if sid < nb {
505 let sin: *i64 = ((live_in as i64) + sid * bytes_per_set) as *i64
506 w = 0
507 while w < words {
508 no[w] = no[w] | sin[w]
509 w = w + 1
510 }
511 }
512 }
513 }
514
515 // new_in = use ∪ (new_out & ~def). Express ~def via
516 // XOR: x & ~y = x ^ (x & y).
517 w = 0
518 while w < words {
519 let masked: i64 = no[w] & d[w]
520 let not_def_part: i64 = no[w] ^ masked
521 ni[w] = u[w] | not_def_part
522 w = w + 1
523 }
524
525 // Detect change vs current live_in / live_out.
526 w = 0
527 while w < words {
528 if ni[w] != li[w] { changed = 1 }
529 if no[w] != lo[w] { changed = 1 }
530 w = w + 1
531 }
532 // Commit.
533 w = 0
534 while w < words {
535 li[w] = ni[w]
536 lo[w] = no[w]
537 w = w + 1
538 }
539 bi = bi - 1
540 }
541 }
542
543 // Apply liveness to intervals: extend [start, end] to cover
544 // every BB where the value is live (in OR out OR defined OR used).
545 // Apply liveness to intervals. C2 FIX (was O(n_values * n_blocks) -> blew up on giant functions): iterate
546 // BLOCKS -> live-set WORDS (skip zero words) -> SET BITS only, extending each live value's interval. Same
547 // RESULT (min start / max end is order-independent) so codegen is byte-identical; cost is the live-incidence
548 // count, near-linear for sparse liveness instead of quadratic.
549 var b2: i64 = 0
550 while b2 < nb {
551 let bs_in: *i64 = ((live_in as i64) + b2 * bytes_per_set) as *i64
552 let bs_out: *i64 = ((live_out as i64) + b2 * bytes_per_set) as *i64
553 let bs_use: *i64 = ((use_ as i64) + b2 * bytes_per_set) as *i64
554 let bs_def: *i64 = ((def_ as i64) + b2 * bytes_per_set) as *i64
555 let bstart: i64 = bb_start[b2]
556 let bend: i64 = bb_end[b2]
557 var w: i64 = 0
558 while w < words {
559 let combined: i64 = bs_in[w] | bs_out[w] | bs_use[w] | bs_def[w]
560 if combined != 0 {
561 var bit: i64 = 0
562 while bit < 64 {
563 if ((combined >> bit) & 1) == 1 {
564 let v: i64 = w * 64 + bit
565 if v < n {
566 let iv: *Interval = intv_at(intv, v)
567 if iv.start >= 0 {
568 if bstart < iv.start { iv.start = bstart }
569 if bend > iv.end { iv.end = bend }
570 }
571 }
572 }
573 bit = bit + 1
574 }
575 }
576 w = w + 1
577 }
578 b2 = b2 + 1
579 }
580 return 0
581}
582
583// Mark each interval's crosses_call flag: any call index strictly
584// between start and end (inclusive end) means the value needs to
585// survive a call.
586
587func mark_crosses_call(intv: *Interval, n_values: i64,
588 calls: *i64, n_calls: i64) -> i64 {
589 var v: i64 = 0
590 while v < n_values {
591 let iv: *Interval = intv_at(intv, v)
592 if iv.start >= 0 {
593 var k: i64 = 0
594 while k < n_calls {
595 let ci: i64 = calls[k]
596 if ci > iv.start {
597 if ci <= iv.end {
598 iv.crosses_call = 1
599 }
600 }
601 k = k + 1
602 }
603 }
604 v = v + 1
605 }
606 return 0
607}
608
609// ---- linear-scan core ----
610//
611// Simplified but correct: for each interval in start order, pop
612// free register (preferring t-pool for non-crossing, s-pool for
613// crossing), insert into actives sorted by end. On exhaustion,
614// spill the interval whose end is furthest.
615
616// Pop a register from the free pool that matches the preferred
617// class. Returns the register index, or -1 on empty. `free_regs`
618// is an array of size n_free; we compact by swap-with-last.
619
620func pop_free(free_regs: *i64, n_free_ptr: *i64,
621 want_cs: i64, fallback: i64) -> i64 {
622 var j: i64 = *n_free_ptr - 1
623 while j >= 0 {
624 let r: i64 = free_regs[j]
625 let cs: i64 = is_callee_saved(r)
626 if cs == want_cs {
627 free_regs[j] = free_regs[*n_free_ptr - 1]
628 *n_free_ptr = *n_free_ptr - 1
629 return r
630 }
631 j = j - 1
632 }
633 if fallback == 0 { return -1 }
634 j = *n_free_ptr - 1
635 while j >= 0 {
636 let r: i64 = free_regs[j]
637 let cs: i64 = is_callee_saved(r)
638 if cs != want_cs {
639 free_regs[j] = free_regs[*n_free_ptr - 1]
640 *n_free_ptr = *n_free_ptr - 1
641 return r
642 }
643 j = j - 1
644 }
645 return -1
646}
647
648// Expire any actives whose interval has ended before `cur_start`.
649// Returns freed registers to the free pool. `active` array is kept
650// dense (no holes).
651
652func expire(active: *i64, n_active_ptr: *i64,
653 intv: *Interval, cur_start: i64,
654 free_regs: *i64, n_free_ptr: *i64) -> i64 {
655 var w: i64 = 0
656 var j: i64 = 0
657 while j < *n_active_ptr {
658 let iv_id: i64 = active[j]
659 let iv: *Interval = intv_at(intv, iv_id)
660 if iv.end < cur_start {
661 if iv.reg >= 0 {
662 free_regs[*n_free_ptr] = iv.reg
663 *n_free_ptr = *n_free_ptr + 1
664 }
665 }
666 if iv.end >= cur_start {
667 active[w] = iv_id
668 w = w + 1
669 }
670 j = j + 1
671 }
672 *n_active_ptr = w
673 return 0
674}
675
676// Insertion-sort-style insert into active[] keyed on end ascending.
677
678func active_insert(active: *i64, n_active_ptr: *i64,
679 intv: *Interval, id: i64) -> i64 {
680 let iv: *Interval = intv_at(intv, id)
681 var k: i64 = *n_active_ptr
682 while k > 0 {
683 let prev_id: i64 = active[k - 1]
684 let prev_iv: *Interval = intv_at(intv, prev_id)
685 if prev_iv.end <= iv.end { break }
686 active[k] = active[k - 1]
687 k = k - 1
688 }
689 active[k] = id
690 *n_active_ptr = *n_active_ptr + 1
691 return 0
692}
693
694// Spill-at-interval: when the free pool is empty (or has no register
695// of the desired class), look at the active interval with the
696// furthest end of the matching class. If its end > new.end, evict
697// it: return its register so the new interval can land in it, and
698// mark the evicted one as spilled. This is the canonical Poletto-
699// Sarkar 1999 spillAtInterval policy. Without it, spills go in
700// arrival order which produces worse code on register-pressured
701// functions (the textbook minimal example: 17 live ints across 16
702// GPRs spills the 17th value, but if that value is hot and an
703// already-active value has a longer remaining lifetime, evicting
704// the longer-lived one is strictly better).
705//
706// Class-agnostic: works for both the GPR pass (t/s split at idx 4)
707// and the FPR pass (ft/fs split at FREG_BASE_S). is_callee_saved()
708// already handles both pools, so a single helper serves both
709// linear_scan and linear_scan_fpr.
710//
711// `want_cs` matches the request the caller made of pop_free:
712// 1 -> evict from the callee-saved pool (s-regs / fs-regs)
713// 0 -> evict from the caller-clobbered pool (t-regs / ft-regs)
714//
715// Active[] is kept sorted by end ascending, so the candidate with
716// the latest end lives at the back -- we walk backward looking for
717// the first one matching want_cs.
718//
719// Returns the now-free register index >= 0 on successful eviction;
720// returns -1 if no profitable eviction (caller must spill the new
721// interval instead).
722
723func spill_furthest_active(active: *i64, n_active_ptr: *i64,
724 intv: *Interval,
725 want_cs: i64, new_end: i64,
726 next_slot_ptr: *i64) -> i64 {
727 var j: i64 = *n_active_ptr - 1
728 while j >= 0 {
729 let cand_id: i64 = active[j]
730 let cand: *Interval = intv_at(intv, cand_id)
731 let cand_cs: i64 = is_callee_saved(cand.reg)
732 if cand_cs == want_cs {
733 if cand.end > new_end {
734 let freed: i64 = cand.reg
735 cand.reg = -1
736 cand.slot = *next_slot_ptr
737 *next_slot_ptr = *next_slot_ptr + 8
738 var k: i64 = j
739 while k < *n_active_ptr - 1 {
740 active[k] = active[k + 1]
741 k = k + 1
742 }
743 *n_active_ptr = *n_active_ptr - 1
744 return freed
745 }
746 return -1
747 }
748 j = j - 1
749 }
750 return -1
751}
752
753// Main linear-scan. `sorted_ids[0..n_sorted)` holds interval ids
754// in ascending start order. Writes final reg / slot into each
755// interval. Returns the total stack_bytes used for spills.
756
757func linear_scan(intv: *Interval,
758 sorted_ids: *i64, n_sorted: i64,
759 used_cs_mask: *i64) -> i64 {
760 let free_regs: *u8 = sys_mmap(num_regs() * 8 + 8)
761 let free_arr: *i64 = free_regs as *i64
762 var n_free: i64 = num_regs()
763 var r: i64 = 0
764 while r < num_regs() {
765 free_arr[r] = r
766 r = r + 1
767 }
768
769 let active_raw: *u8 = sys_mmap(n_sorted * 8 + 16)
770 let active: *i64 = active_raw as *i64
771 var n_active: i64 = 0
772
773 var next_slot: i64 = 0
774 *used_cs_mask = 0
775
776 var i: i64 = 0
777 while i < n_sorted {
778 let id: i64 = sorted_ids[i]
779 let iv: *Interval = intv_at(intv, id)
780
781 expire(active, &n_active, intv, iv.start, free_arr, &n_free)
782
783 var picked: i64 = pop_free(free_arr, &n_free, iv.crosses_call, 1)
784 if picked < 0 {
785 picked = spill_furthest_active(active, &n_active, intv,
786 iv.crosses_call, iv.end,
787 &next_slot)
788 }
789 if picked < 0 {
790 iv.reg = -1
791 iv.slot = next_slot
792 next_slot = next_slot + 8
793 i = i + 1
794 continue
795 }
796 if iv.crosses_call {
797 if picked < 4 {
798 let from_evict: i64 = spill_furthest_active(active, &n_active,
799 intv, 1, iv.end,
800 &next_slot)
801 if from_evict < 0 {
802 free_arr[n_free] = picked
803 n_free = n_free + 1
804 iv.reg = -1
805 iv.slot = next_slot
806 next_slot = next_slot + 8
807 i = i + 1
808 continue
809 }
810 free_arr[n_free] = picked
811 n_free = n_free + 1
812 picked = from_evict
813 }
814 }
815 iv.reg = picked
816 iv.slot = -1
817 if picked >= 4 {
818 *used_cs_mask = *used_cs_mask | (1 << picked)
819 }
820 active_insert(active, &n_active, intv, id)
821 i = i + 1
822 }
823 return next_slot
824}
825
826// ---- FPR linear scan ----------------------------------------------
827//
828// Float-register allocator. Mirrors linear_scan but draws from the
829// F-extension register pool (indices 100-111, 200-211) minus ft4/
830// ft5/ft6 scratches. Spill slots continue numbering from
831// `spill_slot_start` so the single contiguous stack frame holds both
832// GPR and FPR spills.
833//
834// crosses_call interpretation:
835// * 0 -> prefer ft* (caller-clobbered) so spills stay cheap
836// * 1 -> require fs* (callee-saved); we spill rather than land in
837// ft* because the call would clobber it
838//
839// used_cs_mask_fpr bit k (0..11) = fs<k> was assigned. Reused by the
840// emitter's prologue/epilogue to save/restore fs-regs that the
841// function touches. (Prologue/epilogue wiring for f-reg saves comes
842// with the first real end-to-end f-code generation.)
843
844func linear_scan_fpr(intv: *Interval,
845 sorted_ids: *i64, n_sorted: i64,
846 used_cs_mask_fpr: *i64,
847 spill_slot_start: i64) -> i64 {
848 // Build free pool: ft0..ft11 minus ft4/ft5/ft6, plus fs0..fs11.
849 let free_regs: *u8 = sys_mmap((NUM_FT + NUM_FS) * 8 + 64)
850 let free_arr: *i64 = free_regs as *i64
851 var n_free: i64 = 0
852 var r: i64 = FREG_BASE_T
853 while r < FREG_BASE_T + NUM_FT {
854 if r != FREG_SCRATCH_4 {
855 if r != FREG_SCRATCH_5 {
856 if r != FREG_SCRATCH_6 {
857 free_arr[n_free] = r
858 n_free = n_free + 1
859 }
860 }
861 }
862 r = r + 1
863 }
864 r = FREG_BASE_S
865 while r < FREG_BASE_S + NUM_FS {
866 free_arr[n_free] = r
867 n_free = n_free + 1
868 r = r + 1
869 }
870
871 let active_raw: *u8 = sys_mmap(n_sorted * 8 + 16)
872 let active: *i64 = active_raw as *i64
873 var n_active: i64 = 0
874
875 var next_slot: i64 = spill_slot_start
876 *used_cs_mask_fpr = 0
877
878 var i: i64 = 0
879 while i < n_sorted {
880 let id: i64 = sorted_ids[i]
881 let iv: *Interval = intv_at(intv, id)
882
883 expire(active, &n_active, intv, iv.start, free_arr, &n_free)
884
885 var picked: i64 = pop_free(free_arr, &n_free, iv.crosses_call, 1)
886 if picked < 0 {
887 picked = spill_furthest_active(active, &n_active, intv,
888 iv.crosses_call, iv.end,
889 &next_slot)
890 }
891 if picked < 0 {
892 iv.reg = -1
893 iv.slot = next_slot
894 next_slot = next_slot + 8
895 i = i + 1
896 continue
897 }
898 if iv.crosses_call {
899 if picked < FREG_BASE_S {
900 let from_evict: i64 = spill_furthest_active(active, &n_active,
901 intv, 1, iv.end,
902 &next_slot)
903 if from_evict < 0 {
904 free_arr[n_free] = picked
905 n_free = n_free + 1
906 iv.reg = -1
907 iv.slot = next_slot
908 next_slot = next_slot + 8
909 i = i + 1
910 continue
911 }
912 free_arr[n_free] = picked
913 n_free = n_free + 1
914 picked = from_evict
915 }
916 }
917 iv.reg = picked
918 iv.slot = -1
919 if picked >= FREG_BASE_S {
920 let bit: i64 = picked - FREG_BASE_S
921 *used_cs_mask_fpr = *used_cs_mask_fpr | (1 << bit)
922 }
923 active_insert(active, &n_active, intv, id)
924 i = i + 1
925 }
926 return next_slot
927}
928
929// Helper: simple insertion sort of ids by interval start.
930// Stable-enough for our small functions; not optimized.
931
932func sort_by_start(ids: *i64, n: i64, intv: *Interval) -> i64 {
933 var i: i64 = 1
934 while i < n {
935 let key: i64 = ids[i]
936 let key_iv: *Interval = intv_at(intv, key)
937 let key_start: i64 = key_iv.start
938 var j: i64 = i - 1
939 while j >= 0 {
940 let prev_id: i64 = ids[j]
941 let prev_iv: *Interval = intv_at(intv, prev_id)
942 if prev_iv.start <= key_start { break }
943 ids[j + 1] = ids[j]
944 j = j - 1
945 }
946 ids[j + 1] = key
947 i = i + 1
948 }
949 return 0
950}
951
952// ---- rematerialisation predicate ----
953//
954// True iff Value v is rematerialisable -- codegen recomputes the
955// value at every use site instead of consulting a register/spill
956// home. These intervals MUST NOT compete for registers in
957// linear-scan: keeping them in the candidate set wastes register
958// slots that would never be consulted by the codegen anyway.
959//
960// Mirrors is_rematerialisable in nxc2/regalloc.c (commit 728c073).
961//
962// Scope (matches what runtime/riscv.nx materialise() recomputes
963// inline today, no signature change required):
964// - VAL_CONST -> emit `li reg, N`
965//
966// OP_ALLOCA addresses ARE rematerialisable in principle (the C side
967// recomputes via `addi reg, sp, off` from alloca_off[]), but the
968// NishiLang materialise() doesn't yet receive alloca_off as an
969// argument. Adding it requires a signature change touching every
970// emitter. Deferred to a follow-up commit; for now allocas keep
971// their VL_REGISTER/VL_SPILLED home.
972
973func is_rematerialisable(f: *Function, v: i64) -> i64 {
974 if v >= f.n_values { return 0 }
975 let base: i64 = f.values as i64
976 let val: *Value = (base + v * 48) as *Value
977 if val.kind == VAL_CONST { return 1 }
978 return 0
979}
980
981// ---- public entry ----
982//
983// Allocate intervals + sorted list + locs. Runs the whole pipeline
984// and fills `locs`. Caller supplies `locs` array of size n_values.
985
986func regalloc_function(f: *Function, locs: *ValueLoc,
987 used_cs_mask: *i64, used_cs_mask_fpr: *i64,
988 stack_bytes_out: *i64) -> i64 {
989 let intv_raw: *u8 = sys_mmap(f.n_values * 48 + 16)
990 let intv: *Interval = intv_raw as *Interval
991
992 let calls_raw: *u8 = sys_mmap(FREG_MAGIC_4096)
993 let calls: *i64 = calls_raw as *i64
994
995 let bb_start_raw: *u8 = sys_mmap(f.n_blocks * 8 + 16)
996 let bb_start: *i64 = bb_start_raw as *i64
997 let bb_end_raw: *u8 = sys_mmap(f.n_blocks * 8 + 16)
998 let bb_end: *i64 = bb_end_raw as *i64
999
1000 let nc_raw: *u8 = sys_mmap(16)
1001 let nc_ptr: *i64 = nc_raw as *i64
1002 *nc_ptr = 0
1003 build_intervals(f, intv, calls, nc_ptr, bb_start, bb_end)
1004 // compute_liveness was tried 2026-05-19 — fixed probe_m0b but
1005 // regressed probe_irfn/probe_irbuild/probe_callchain (over-extends
1006 // intervals, causing different regalloc → miscompiled IR-construction
1007 // code). Disabled for now; build_intervals' per-instruction
1008 // tracking covers most cases. Future: refine compute_liveness OR
1009 // pair it with an extended Interval struct that has cross_block flag.
1010 // ✅2026-07-14 BUG 8 FIXED (two coupled defects; compute_liveness stays disabled -- it has its own
1011 // large-CFG regression). build_intervals' [first,last] in block-index order mis-handled LOOPS: a loop-carried
1012 // value (w) whose use sits mid-loop-body looked dead for the rest of the block while it was live across the
1013 // back-edge, so a value defined later in the block (acc's reload) reused its register (both got t2 -> wrong
1014 // SHA-256 digest, sha256corrupt.nx 153 not 174). FIX 1 = a LOOP-CARRIED interval extension appended to
1015 // build_intervals (extend to the back-edge any interval that overlaps a loop and ends inside it). That
1016 // extension then EXPOSED the pre-existing FIX 2 = emit_function called compute_alloca_offsets with
1017 // spill_bytes=0, so alloca #0 and spill slot #0 both sat at sp+0 -> a spill overwrote the first local
1018 // (TRIPLE-NESTED 4 not 24); now emit_function recovers real spill_bytes and bases allocas above it. Both
1019 // validated: sha256corrupt 174, TRIPLE-NESTED 182a, full 34-oracle GREEN, compute+print SHA-256 kernel prints
1020 // the NIST digest byte-identical sim==QEMU.
1021 // compute_liveness(f, intv, bb_start, bb_end)
1022 mark_crosses_call(intv, f.n_values, calls, *nc_ptr)
1023
1024 // Collect ids with valid intervals into two dense sorted arrays:
1025 // one for GPR values, one for FPR values. Rematerialisable values
1026 // (constants, alloca addresses, etc.) are skipped in both: codegen
1027 // recomputes them inline at every use. See is_rematerialisable.
1028 //
1029 // Partitioning by type lets each pass draw from its own pool
1030 // without cross-contamination. The two passes share the single
1031 // contiguous stack frame by continuing spill-slot numbering.
1032 let gpr_ids_raw: *u8 = sys_mmap(f.n_values * 8 + 16)
1033 let gpr_ids: *i64 = gpr_ids_raw as *i64
1034 let fpr_ids_raw: *u8 = sys_mmap(f.n_values * 8 + 16)
1035 let fpr_ids: *i64 = fpr_ids_raw as *i64
1036 var n_gpr: i64 = 0
1037 var n_fpr: i64 = 0
1038 var v: i64 = 0
1039 while v < f.n_values {
1040 let iv: *Interval = intv_at(intv, v)
1041 if iv.start >= 0 {
1042 if is_rematerialisable(f, v) == 0 {
1043 if is_float_value(f, v) == 1 {
1044 fpr_ids[n_fpr] = v
1045 n_fpr = n_fpr + 1
1046 }
1047 if is_float_value(f, v) == 0 {
1048 gpr_ids[n_gpr] = v
1049 n_gpr = n_gpr + 1
1050 }
1051 }
1052 }
1053 v = v + 1
1054 }
1055 sort_by_start(gpr_ids, n_gpr, intv)
1056 sort_by_start(fpr_ids, n_fpr, intv)
1057
1058 // GPR pass. Returns total bytes consumed by integer spills.
1059 let gpr_spill: i64 = linear_scan(intv, gpr_ids, n_gpr, used_cs_mask)
1060
1061 // FPR pass, continuing the spill numbering. The fpr cs mask
1062 // now flows back to the caller via used_cs_mask_fpr so
1063 // emit_function can save/restore fs0..fs11 in the prologue/
1064 // epilogue.
1065 let total_spill: i64 = linear_scan_fpr(intv, fpr_ids, n_fpr,
1066 used_cs_mask_fpr, gpr_spill)
1067 *stack_bytes_out = total_spill
1068
1069 // Lower intervals to ValueLocs. Rematerialisable values get
1070 // VL_REMAT (kind=2); codegen's materialise() recomputes them
1071 // inline without consulting the loc.
1072 let lbase: i64 = locs as i64
1073 var k: i64 = 0
1074 while k < f.n_values {
1075 let iv: *Interval = intv_at(intv, k)
1076 let l: *ValueLoc = (lbase + k * 16) as *ValueLoc
1077 if iv.start < 0 {
1078 l.kind = VL_SPILLED
1079 l.idx = -1
1080 }
1081 if iv.start >= 0 {
1082 if is_rematerialisable(f, k) == 1 {
1083 l.kind = VL_REMAT
1084 l.idx = 0
1085 }
1086 if is_rematerialisable(f, k) == 0 {
1087 if iv.reg >= 0 {
1088 l.kind = VL_REGISTER
1089 l.idx = iv.reg
1090 }
1091 if iv.reg < 0 {
1092 l.kind = VL_SPILLED
1093 l.idx = iv.slot
1094 }
1095 }
1096 }
1097 k = k + 1
1098 }
1099
1100 return 0
1101}
1102
1103// ===== self-test ===================================================
1104//
1105// Build a tiny straight-line function: %0 = const 10, %1 = const 20,
1106// %2 = add %0 %1. Verify that regalloc produces reasonable
1107// intervals and register assignments. Specifically:
1108// * All three values get register homes (no spills for 3 values
1109// when we have 16 registers).
1110// * The intervals have start > 0 and end >= start.
1111
1112// Library only; self-test lives in regalloc_test.nx.