nx_regalloc_linscan_test.nx source

1// nx_regalloc_linscan_test.nx -- prove the register allocator on two IRs: 2// A. LOW pressure (a dependency chain, <= 2 live at once): nreg=8 -> 0 spills, 3// memory traffic collapses (the stack tax eliminated). 4// B. HIGH pressure (a tree reduction with a long-lived value, 5 live at once): 5// nreg=3 -> MUST spill, and the allocation MUST STILL BE SOUND (no two live 6// non-spilled vregs share a register -- the exact property the prior g1 7// regalloc attempt violated). Memory traffic still far below the baseline. 8// 9// Known answer: both allocations VALID (independent checker), A has 0 spills, B has 10// spills > 0, and both reduce memory traffic vs the stack baseline. exit 0. 11 12import "nx_regalloc_linscan.nx" 13 14func ra_puts(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 } 15func ra_emit(name: *u8, v: i64) -> i64 { 16 ra_puts(name) 17 let b: *u8 = sys_mmap(28); var m: i64 = v; if m < 0 { m = 0 - m } 18 let t: *u8 = sys_mmap(28); var k: i64 = 0 19 if m == 0 { t[0] = 48; k = 1 } 20 while m > 0 { t[k] = 48 + (m % 10); m = m / 10; k = k + 1 } 21 var i: i64 = 0; while i < k { b[i] = t[k - 1 - i]; i = i + 1 } 22 b[k] = 10; sys_write(1, b, k + 1); return 0 23} 24 25// run one IR through the full pipeline; writes spills/valid/base/ra into out[0..3]. 26func ra_run(n: i64, nreg: i64, u0: *i64, u1: *i64, out: *i64) -> i64 { 27 let last_use: *i64 = sys_mmap(8 * n) 28 let alloc: *i64 = sys_mmap(8 * n) 29 ra_compute_last_use(n, u0, u1, last_use) 30 let spills: i64 = ra_linscan(n, nreg, last_use, alloc) 31 let valid: i64 = ra_validate(n, last_use, alloc, nreg) 32 out[0] = spills 33 out[1] = valid // 0 = sound 34 out[2] = ra_baseline_mem(n, u0, u1) 35 out[3] = ra_regalloc_mem(n, u0, u1, alloc) 36 return 0 37} 38 39func main() -> i64 { 40 ra_puts("=== linear-scan register allocation (Poletto & Sarkar 1999), proven ===\n" as *u8) 41 let outA: *i64 = sys_mmap(32) as *i64 42 let outB: *i64 = sys_mmap(32) as *i64 43 44 // --- Scenario A: dependency chain c0 -> c1 -> ... -> c15 (<=2 live) --- 45 let nA: i64 = 16 46 let aU0: *i64 = sys_mmap(8 * nA) 47 let aU1: *i64 = sys_mmap(8 * nA) 48 var i: i64 = 0 49 while i < nA { 50 if i == 0 { aU0[i] = 0 - 1 } else { aU0[i] = i - 1 } 51 aU1[i] = 0 - 1 52 i = i + 1 53 } 54 ra_run(nA, 8, aU0, aU1, outA) 55 ra_puts("[A] low pressure (chain, nreg=8)\n" as *u8) 56 ra_emit(" spills : " as *u8, outA[0]) 57 ra_emit(" sound (0=valid) : " as *u8, outA[1]) 58 ra_emit(" stack-baseline mem: " as *u8, outA[2]) 59 ra_emit(" regalloc mem : " as *u8, outA[3]) 60 61 // --- Scenario B: tree reduction with a long-lived v0 (5 live at point 4) --- 62 // v0..v3 = defs ; v4=v0+v1 ; v5=v2+v3 ; v6=v4+v5 ; v7=v6+v0 (v0 lives 0..7) 63 let nB: i64 = 8 64 let bU0: *i64 = sys_mmap(8 * nB) 65 let bU1: *i64 = sys_mmap(8 * nB) 66 bU0[0] = 0 - 1; bU1[0] = 0 - 1 67 bU0[1] = 0 - 1; bU1[1] = 0 - 1 68 bU0[2] = 0 - 1; bU1[2] = 0 - 1 69 bU0[3] = 0 - 1; bU1[3] = 0 - 1 70 bU0[4] = 0; bU1[4] = 1 71 bU0[5] = 2; bU1[5] = 3 72 bU0[6] = 4; bU1[6] = 5 73 bU0[7] = 6; bU1[7] = 0 74 ra_run(nB, 3, bU0, bU1, outB) 75 ra_puts("[B] high pressure (reduction, nreg=3)\n" as *u8) 76 ra_emit(" spills : " as *u8, outB[0]) 77 ra_emit(" sound (0=valid) : " as *u8, outB[1]) 78 ra_emit(" stack-baseline mem: " as *u8, outB[2]) 79 ra_emit(" regalloc mem : " as *u8, outB[3]) 80 81 ra_puts("----------------------------------------------------------------\n" as *u8) 82 ra_puts(" register allocation is SOUND under pressure (the g1 failure mode) AND\n" as *u8) 83 ra_puts(" cuts memory traffic = the lever to close the speed/density gap vs C.\n" as *u8) 84 85 // GATE: both sound; A spill-free; B actually spilled (pressure exercised); both 86 // strictly reduce memory traffic vs the stack baseline. 87 if outA[1] != 0 { sys_exit(1); return 1 } // A unsound 88 if outB[1] != 0 { sys_exit(2); return 2 } // B unsound (the prior bug) 89 if outA[0] != 0 { sys_exit(3); return 3 } // A should not spill 90 if outB[0] <= 0 { sys_exit(4); return 4 } // B must exercise spilling 91 if outA[3] >= outA[2] { sys_exit(5); return 5 } // A must reduce memory 92 if outB[3] >= outB[2] { sys_exit(6); return 6 } // B must reduce memory 93 sys_exit(0) 94 return 0 95}