nx_regalloc_calls.nx source

1// nx_regalloc_calls.nx -- the G1 register allocator's KEYSTONE capability: correct 2// handling of values LIVE ACROSS A CALL. This is the exact bug the bootstrap compiler 3// has (project-knowngood-compiler-regpressure-miscompile): a value held live across a 4// call is left in a CALLER-SAVED register and clobbered by the call, so a later read 5// gets garbage and a comparison flips. The base linear scan (nx_regalloc_linscan) models 6// live intervals but knows nothing about calls or the caller/callee-saved ABI split -- 7// so it can place a live-across-call value in a caller-saved register. That is the gap. 8// 9// This closes it and PROVES it three ways: 10// (1) ra_linscan_calls -- a vreg that spans a call may take only a CALLEE-saved reg, 11// else it SPILLS (a spilled value is in memory and survives any call). 12// (2) ra_validate_calls -- STATIC proof: no live-across-call vreg sits in a caller-saved reg. 13// (3) rc_interp_alloc -- EXECUTION model where a call POISONS caller-saved registers, 14// so a wrong allocation actually computes a wrong answer (the bug, reproduced). 15// The differential (call-unaware diverges / call-aware matches the reference) is the proof. 16// 17// x86-64 SysV ABI: caller-saved = rax,rcx,rdx,rsi,rdi,r8-r11 (clobbered by a call); 18// callee-saved = rbx,rbp,r12-r15 (survive a call). We model regs [0,ncaller) caller-saved, 19// [ncaller,nreg) callee-saved. license_tier: ORIGINAL 20 21import "nx_regalloc_interp.nx" // chains nx_regalloc_linscan + nx_syscalls; ri_get, ri_op_eval, RA_SPILL 22 23const ROP_CALL: i64 = 8 24const RC_POISON: i64 = 0 - 999999 // value a clobbered caller-saved register holds 25 26// does vreg v span a call? -- is there a call instruction c with v < c < ... and v still 27// used after c (last_use[v] > c)? such a v is live in a register across the call. 28func rc_spans_call(v: i64, last_use: *i64, is_call: *i64, n: i64) -> i64 { 29 var c: i64 = v + 1 30 while c < n { 31 if is_call[c] == 1 { if last_use[v] > c { return 1 } } 32 c = c + 1 33 } 34 return 0 35} 36 37// CALL-AWARE linear scan. caller-saved = [0,ncaller); callee-saved = [ncaller,nreg). 38// A vreg that spans a call may only take a callee-saved register; if none is free it 39// SPILLS (always call-safe). Non-spanning vregs prefer any free register. 40func ra_linscan_calls(n: i64, nreg: i64, ncaller: i64, last_use: *i64, is_call: *i64, alloc: *i64) -> i64 { 41 let reg_busy: *i64 = sys_mmap(8 * nreg) 42 let act_v: *i64 = sys_mmap(8 * (n + 1)) 43 let act_e: *i64 = sys_mmap(8 * (n + 1)) 44 var act_n: i64 = 0 45 var spills: i64 = 0 46 var i: i64 = 0 47 while i < n { 48 var k: i64 = 0 49 var w: i64 = 0 50 while k < act_n { 51 if act_e[k] < i { reg_busy[alloc[act_v[k]]] = 0 } 52 else { act_v[w] = act_v[k]; act_e[w] = act_e[k]; w = w + 1 } 53 k = k + 1 54 } 55 act_n = w 56 let spans: i64 = rc_spans_call(i, last_use, is_call, n) 57 var r: i64 = 0 - 1 58 if spans == 1 { 59 var j: i64 = ncaller 60 while j < nreg { if reg_busy[j] == 0 { r = j; j = nreg } else { j = j + 1 } } 61 } else { 62 var j: i64 = 0 63 while j < nreg { if reg_busy[j] == 0 { r = j; j = nreg } else { j = j + 1 } } 64 } 65 if r >= 0 { 66 alloc[i] = r; reg_busy[r] = 1 67 act_v[act_n] = i; act_e[act_n] = last_use[i]; act_n = act_n + 1 68 } else { 69 alloc[i] = RA_SPILL // spill -- in memory, survives any call 70 spills = spills + 1 71 } 72 i = i + 1 73 } 74 return spills 75} 76 77// STATIC soundness for calls: every vreg that spans a call must be SPILLED or callee-saved. 78// Returns 0 if valid, else 0-(v+1) for the first vreg in a caller-saved reg across a call. 79func ra_validate_calls(n: i64, last_use: *i64, is_call: *i64, alloc: *i64, ncaller: i64) -> i64 { 80 var v: i64 = 0 81 while v < n { 82 if rc_spans_call(v, last_use, is_call, n) == 1 { 83 let a: i64 = alloc[v] 84 if a >= 0 { if a < ncaller { return 0 - (v + 1) } } 85 } 86 v = v + 1 87 } 88 return 0 89} 90 91// REFERENCE interpreter with calls: one slot per vreg, a call yields its return value 92// (imm). No register reuse, so nothing can clobber -- always correct. 93func rc_interp_ref(n: i64, op: *i64, u0: *i64, u1: *i64, imm: *i64, is_call: *i64, 94 inputs: *i64, loa: i64, lob: i64, loc: i64) -> i64 { 95 let val: *i64 = sys_mmap(8 * n) 96 var i: i64 = 0 97 while i < n { 98 if is_call[i] == 1 { val[i] = imm[i] } 99 else { 100 if op[i] == ROP_INPUT { val[i] = inputs[imm[i]] } 101 else { 102 var a: i64 = 0 103 var b: i64 = 0 104 if u0[i] >= 0 { a = val[u0[i]] } 105 if u1[i] >= 0 { b = val[u1[i]] } 106 val[i] = ri_op_eval(op[i], a, b, imm[i]) 107 } 108 } 109 i = i + 1 110 } 111 return val[loa] * 31 + val[lob] * 7 + val[loc] 112} 113 114// ALLOCATED interpreter with calls: executing a CALL POISONS every caller-saved register. 115// A vreg that was left live in a caller-saved register across the call is now poison, so 116// the result diverges from the reference -- the miscompile, made observable. 117func rc_interp_alloc(n: i64, nreg: i64, ncaller: i64, op: *i64, u0: *i64, u1: *i64, imm: *i64, 118 is_call: *i64, alloc: *i64, inputs: *i64, loa: i64, lob: i64, loc: i64) -> i64 { 119 let regf: *i64 = sys_mmap(8 * nreg) 120 let spill: *i64 = sys_mmap(8 * n) 121 var i: i64 = 0 122 while i < n { 123 if is_call[i] == 1 { 124 var c: i64 = 0 125 while c < ncaller { regf[c] = RC_POISON; c = c + 1 } // the call clobbers caller-saved 126 if alloc[i] >= 0 { regf[alloc[i]] = imm[i] } else { spill[i] = imm[i] } 127 } else { 128 var v: i64 = 0 129 if op[i] == ROP_INPUT { v = inputs[imm[i]] } 130 else { 131 var a: i64 = 0 132 var b: i64 = 0 133 if u0[i] >= 0 { a = ri_get(u0[i], alloc, regf, spill) } 134 if u1[i] >= 0 { b = ri_get(u1[i], alloc, regf, spill) } 135 v = ri_op_eval(op[i], a, b, imm[i]) 136 } 137 if alloc[i] >= 0 { regf[alloc[i]] = v } else { spill[i] = v } 138 } 139 i = i + 1 140 } 141 return ri_get(loa, alloc, regf, spill) * 31 + ri_get(lob, alloc, regf, spill) * 7 + ri_get(loc, alloc, regf, spill) 142}