nx_regalloc_linscan.nx source

1// nx_regalloc_linscan.nx -- linear-scan register allocation, bits-up + PROVABLE. 2// 3// This is the keystone lever the ONGOING race vs C keeps pointing at: Nishi's 4// stack/memory-resident codegen loads every operand and stores every result (the 5// ~2x speed + ~6x code-density tax the race measured). Register allocation keeps 6// live values in registers; only SPILLS touch memory. Built STANDALONE + proven 7// first (NOT hand-patched into the protected self-hosting compiler -- a prior 8// "g1 regalloc" attempt silently miscompiled high-pressure functions; we prove 9// soundness here, then the loop absorbs it into codegen under governance). 10// 11// Algorithm: Poletto & Sarkar, "Linear Scan Register Allocation," ACM TOPLAS 1999 12// (the alternative is Chaitin graph-coloring, SIGPLAN 1982; linear scan is faster 13// and good enough -- the right fit for a spore that re-derives its stack on deploy). 14// 15// Model IR: a straight-line block of n instructions; instruction i DEFINES virtual 16// register i and USES up to two prior vregs (u0[i], u1[i]; -1 = none). The live 17// interval of vreg v is [v (its def), last_use[v]]. Linear scan allocates nreg 18// physical registers across the intervals, spilling the farthest-future interval 19// when it runs out (the standard heuristic). 20 21import "nx_syscalls.nx" 22 23const RA_SPILL: i64 = 0 - 1 24 25// last_use[v] = the latest instruction that reads v (>= v's own def point). 26func ra_compute_last_use(n: i64, u0: *i64, u1: *i64, last_use: *i64) -> i64 { 27 var i: i64 = 0 28 while i < n { last_use[i] = i; i = i + 1 } 29 i = 0 30 while i < n { 31 if u0[i] >= 0 { if i > last_use[u0[i]] { last_use[u0[i]] = i } } 32 if u1[i] >= 0 { if i > last_use[u1[i]] { last_use[u1[i]] = i } } 33 i = i + 1 34 } 35 return 0 36} 37 38// Linear scan: fills alloc[v] with a physical reg 0..nreg-1, or RA_SPILL. Returns 39// the spill count. active set kept as parallel (vreg,end) arrays (no sort needed -- 40// we scan; correctness does not depend on order, only the spill pick does). 41func ra_linscan(n: i64, nreg: i64, last_use: *i64, alloc: *i64) -> i64 { 42 let reg_busy: *i64 = sys_mmap(8 * nreg) 43 let act_v: *i64 = sys_mmap(8 * (n + 1)) 44 let act_e: *i64 = sys_mmap(8 * (n + 1)) 45 var act_n: i64 = 0 46 var spills: i64 = 0 47 var i: i64 = 0 48 while i < n { 49 // expire intervals whose end < i (their registers become free) 50 var k: i64 = 0 51 var w: i64 = 0 52 while k < act_n { 53 if act_e[k] < i { 54 reg_busy[alloc[act_v[k]]] = 0 55 } else { 56 act_v[w] = act_v[k]; act_e[w] = act_e[k]; w = w + 1 57 } 58 k = k + 1 59 } 60 act_n = w 61 // find a free physical register 62 var r: i64 = 0 - 1 63 var j: i64 = 0 64 while j < nreg { if reg_busy[j] == 0 { r = j; j = nreg } else { j = j + 1 } } 65 if r >= 0 { 66 alloc[i] = r 67 reg_busy[r] = 1 68 act_v[act_n] = i; act_e[act_n] = last_use[i]; act_n = act_n + 1 69 } else { 70 // no free reg: spill the active interval with the farthest end 71 var mx: i64 = 0 - 1 72 var mxi: i64 = 0 - 1 73 var t: i64 = 0 74 while t < act_n { 75 if act_e[t] > mx { mx = act_e[t]; mxi = t } 76 t = t + 1 77 } 78 if mx > last_use[i] { 79 let sv: i64 = act_v[mxi] // steal its register 80 alloc[i] = alloc[sv] 81 alloc[sv] = RA_SPILL 82 act_v[mxi] = i; act_e[mxi] = last_use[i] 83 } else { 84 alloc[i] = RA_SPILL // spill the new one instead 85 } 86 spills = spills + 1 87 } 88 i = i + 1 89 } 90 return spills 91} 92 93// INDEPENDENT soundness check (the proof): at EVERY program point, every pair of 94// simultaneously-live, non-spilled vregs must occupy DISTINCT physical registers. 95// This is the invariant the prior g1 attempt violated. Returns 0 if valid, else 96// 0-(p+1) for the first colliding point p. 97func ra_validate(n: i64, last_use: *i64, alloc: *i64, nreg: i64) -> i64 { 98 let seen: *i64 = sys_mmap(8 * nreg) 99 var p: i64 = 0 100 while p < n { 101 var j: i64 = 0 102 while j < nreg { seen[j] = 0; j = j + 1 } 103 var v: i64 = 0 104 while v <= p { 105 if last_use[v] >= p { // v live at p 106 let r: i64 = alloc[v] 107 if r >= 0 { 108 if seen[r] == 1 { return 0 - (p + 1) } // COLLISION 109 seen[r] = 1 110 } 111 } 112 v = v + 1 113 } 114 p = p + 1 115 } 116 return 0 117} 118 119// stack/memory-resident baseline: load each operand + store each result. 120func ra_baseline_mem(n: i64, u0: *i64, u1: *i64) -> i64 { 121 var m: i64 = 0 122 var i: i64 = 0 123 while i < n { 124 if u0[i] >= 0 { m = m + 1 } 125 if u1[i] >= 0 { m = m + 1 } 126 m = m + 1 127 i = i + 1 128 } 129 return m 130} 131 132// register-allocated traffic: only SPILLED operands load, only SPILLED results store. 133func ra_regalloc_mem(n: i64, u0: *i64, u1: *i64, alloc: *i64) -> i64 { 134 var m: i64 = 0 135 var i: i64 = 0 136 while i < n { 137 if u0[i] >= 0 { if alloc[u0[i]] == RA_SPILL { m = m + 1 } } 138 if u1[i] >= 0 { if alloc[u1[i]] == RA_SPILL { m = m + 1 } } 139 if alloc[i] == RA_SPILL { m = m + 1 } 140 i = i + 1 141 } 142 return m 143}