nx_regalloc_race_kernel_test.nx source

1// nx_regalloc_race_kernel_test.nx -- point the proven allocator at the EXACT hot 2// loop we lose ~1.9x to C on (nx_race_kernel), to quantify the lever concretely. 3// 4// The race kernel's loop body, as a straight-line IR (each line defines one vreg): 5// c_in, acc_in, i_in live-ins (already in registers) 6// t0 = c_in * K (3) 7// c1 = t0 + A (4) 8// t1 = c1 >> 31 (5) 9// c2 = c1 ^ t1 (6) <- next iteration's c (live-out) 10// t2 = c2 & 65535 (7) 11// acc1 = acc_in + t2 (8) <- next iteration's acc (live-out) 12// i1 = i_in + 1 (9) <- next iteration's i (live-out) 13// cmp = i1 < K (10) 14// 15// Pressure stays low (~4-5 live), so on x86-64's ~8+ usable GP registers the WHOLE 16// body fits in registers: ZERO memory traffic. The stack-resident codegen instead 17// loads each operand + stores each result every iteration -- run 20,000,000 times, 18// that is the ~1.9x. This shows the allocator turns the hot loop memory-free, the 19// direct path to closing the gap. 20// 21// Known answer: 0 spills (fits in registers) AND regalloc memory traffic = 0 AND 22// the stack baseline is large -> exit 0. 23 24import "nx_regalloc_linscan.nx" 25 26func rk_puts(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 } 27func rk_emit(name: *u8, v: i64) -> i64 { 28 rk_puts(name) 29 let b: *u8 = sys_mmap(28); var m: i64 = v; if m < 0 { m = 0 - m } 30 let t: *u8 = sys_mmap(28); var k: i64 = 0 31 if m == 0 { t[0] = 48; k = 1 } 32 while m > 0 { t[k] = 48 + (m % 10); m = m / 10; k = k + 1 } 33 var i: i64 = 0; while i < k { b[i] = t[k - 1 - i]; i = i + 1 } 34 b[k] = 10; sys_write(1, b, k + 1); return 0 35} 36 37const RKB_N: i64 = 11 38const RKB_NREG: i64 = 8 // x86-64 has ~14 GP regs; 8 is conservative 39const RKB_ITERS: i64 = 20000000 // the race kernel's iteration count 40 41func main() -> i64 { 42 rk_puts("=== register allocation applied to the race kernel's hot loop ===\n" as *u8) 43 let u0: *i64 = sys_mmap(8 * RKB_N) 44 let u1: *i64 = sys_mmap(8 * RKB_N) 45 // live-ins (no operands) 46 u0[0] = 0 - 1; u1[0] = 0 - 1 // c_in 47 u0[1] = 0 - 1; u1[1] = 0 - 1 // acc_in 48 u0[2] = 0 - 1; u1[2] = 0 - 1 // i_in 49 u0[3] = 0; u1[3] = 0 - 1 // t0 = c_in * K 50 u0[4] = 3; u1[4] = 0 - 1 // c1 = t0 + A 51 u0[5] = 4; u1[5] = 0 - 1 // t1 = c1 >> 31 52 u0[6] = 4; u1[6] = 5 // c2 = c1 ^ t1 53 u0[7] = 6; u1[7] = 0 - 1 // t2 = c2 & M 54 u0[8] = 1; u1[8] = 7 // acc1 = acc_in + t2 55 u0[9] = 2; u1[9] = 0 - 1 // i1 = i_in + 1 56 u0[10] = 9; u1[10] = 0 - 1 // cmp = i1 < K 57 58 let last_use: *i64 = sys_mmap(8 * RKB_N) 59 let alloc: *i64 = sys_mmap(8 * RKB_N) 60 ra_compute_last_use(RKB_N, u0, u1, last_use) 61 let spills: i64 = ra_linscan(RKB_N, RKB_NREG, last_use, alloc) 62 let valid: i64 = ra_validate(RKB_N, last_use, alloc, RKB_NREG) 63 let base: i64 = ra_baseline_mem(RKB_N, u0, u1) 64 let ra: i64 = ra_regalloc_mem(RKB_N, u0, u1, alloc) 65 66 rk_emit(" instructions in body : " as *u8, RKB_N) 67 rk_emit(" spills (0 = fits in regs) : " as *u8, spills) 68 rk_emit(" sound (0 = valid) : " as *u8, valid) 69 rk_emit(" stack mem ops / iteration : " as *u8, base) 70 rk_emit(" regalloc mem ops / iteration : " as *u8, ra) 71 rk_emit(" stack mem ops over the run : " as *u8, base * RKB_ITERS) 72 rk_emit(" regalloc mem ops over the run: " as *u8, ra * RKB_ITERS) 73 rk_puts(" -> the hot loop becomes MEMORY-FREE; that erased traffic is the ~1.9x.\n" as *u8) 74 75 // GATE: the body fits in registers (0 spills), allocation is sound, it is 76 // memory-free, and the stack baseline it replaces is real (large). 77 if valid != 0 { sys_exit(1); return 1 } 78 if spills != 0 { sys_exit(2); return 2 } // low-pressure body must fit 79 if ra != 0 { sys_exit(3); return 3 } // memory-free under regalloc 80 if base < 10 { sys_exit(4); return 4 } // the stack tax it removes is real 81 sys_exit(0) 82 return 0 83}