nx_superopt_opt_test.nx source

1// nx_superopt_opt_test.nx -- the optimal superoptimizer finds the SHORTEST program 2// for a set of functions (constant-multiply + branchless bit-tricks), verified over 3// FULL-RANGE 64-bit inputs (negatives, sign bit). Reports the op count, which is the 4// number to put 1:1 against gcc -O2's instruction count in the honest board. 5// Known answer: every target's shortest program found + held-out verified -> exit 0. 6 7import "nx_superopt_opt.nx" 8 9func op_puts(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 } 10func op_num(v: i64) -> i64 { 11 let b: *u8 = sys_mmap(28); var m: i64 = v; if m < 0 { m = 0 - m; sys_write(1, "-" as *u8, 1) } 12 let t: *u8 = sys_mmap(28); var k: i64 = 0 13 if m == 0 { t[0] = 48; k = 1 } 14 while m > 0 { t[k] = 48 + (m % 10); m = m / 10; k = k + 1 } 15 var i: i64 = 0; while i < k { b[i] = t[k - 1 - i]; i = i + 1 } 16 sys_write(1, b, k); return 0 17} 18func op_opname(o: i64) -> *u8 { 19 if o == SO_ADD { return "add" as *u8 } if o == SO_SUB { return "sub" as *u8 } 20 if o == SO_MUL { return "mul" as *u8 } if o == SO_SHL { return "shl" as *u8 } 21 if o == SO_SAR { return "sar" as *u8 } if o == SO_XOR { return "xor" as *u8 } 22 if o == SO_AND { return "and" as *u8 } return "or" as *u8 23} 24func op_describe(op: *i64, a: *i64, b: *i64, L: i64) -> i64 { 25 var t: i64 = 0 26 while t < L { 27 op_puts(" " as *u8); op_puts(op_opname(op[t])); op_puts("(s" as *u8); op_num(a[t]); op_puts("," as *u8) 28 if so_is_shift(op[t]) == 1 { op_puts("#" as *u8); op_num(b[t]) } else { op_puts("s" as *u8); op_num(b[t]) } 29 op_puts(")" as *u8) 30 t = t + 1 31 } 32 return 0 33} 34 35func op_target(id: i64, x: i64) -> i64 { 36 if id == 0 { return x * 5 } 37 if id == 1 { if x < 0 { return 0 - x } return x } // abs 38 if id == 2 { return x & (x - 1) } // clear lowest set bit 39 if id == 3 { return x & (0 - x) } // isolate lowest set bit 40 if id == 4 { return x >> 63 } // sign mask (arithmetic) 41 return x * 2 42} 43func op_name(id: i64) -> *u8 { 44 if id == 0 { return "x*5 " as *u8 } 45 if id == 1 { return "abs(x) " as *u8 } 46 if id == 2 { return "x&(x-1) " as *u8 } 47 if id == 3 { return "x&(-x) " as *u8 } 48 if id == 4 { return "x>>63 " as *u8 } 49 return "x*2 " as *u8 50} 51 52func main() -> i64 { 53 op_puts("=== optimal superoptimizer: shortest program per function, full 64-bit ===\n" as *u8) 54 let ex_x: *i64 = sys_mmap(8 * 32) as *i64 55 let ex_y: *i64 = sys_mmap(8 * 32) as *i64 56 let ho: *i64 = sys_mmap(8 * 32) as *i64 57 let op: *i64 = sys_mmap(8 * 8) as *i64 58 let a: *i64 = sys_mmap(8 * 8) as *i64 59 let b: *i64 = sys_mmap(8 * 8) as *i64 60 61 // MANY diverse full-range inputs so an overfit program cannot survive: a few 62 // structured edges + ~200 pseudo-random 64-bit values (incl negatives). Held-out 63 // is an independent random set. (Still example-based, not a proof -- but a wrong 64 // program now has to fool ~200 random 64-bit inputs, which the sar-16 "abs" 65 // overfit does not.) 66 let xs: *i64 = sys_mmap(8 * 256) as *i64 67 var nx: i64 = 0 68 xs[nx]=0;nx=nx+1; xs[nx]=1;nx=nx+1; xs[nx]=0-1;nx=nx+1; xs[nx]=2;nx=nx+1; xs[nx]=0-2;nx=nx+1 69 xs[nx]=(1<<62);nx=nx+1; xs[nx]=0-(1<<62);nx=nx+1; xs[nx]=12345;nx=nx+1; xs[nx]=74565;nx=nx+1 70 var sx: i64 = 88172645463325252 71 while nx < 200 { sx = sx * 6364136223846793005 + 1442695040888963407; xs[nx] = sx; nx = nx + 1 } 72 let hs: *i64 = sys_mmap(8 * 256) as *i64 73 var nh: i64 = 0 74 var sh: i64 = 11400714819323198485 75 while nh < 200 { sh = sh * 6364136223846793005 + 1442695040888963407; hs[nh] = sh; nh = nh + 1 } 76 77 var found: i64 = 0 78 var verified: i64 = 0 79 let nt: i64 = 6 80 var id: i64 = 0 81 while id < nt { 82 var i: i64 = 0 83 while i < nx { ex_x[i] = xs[i]; ex_y[i] = op_target(id, xs[i]); i = i + 1 } 84 let L: i64 = so_find(ex_x, ex_y, nx, op, a, b, 3) 85 op_puts(" " as *u8); op_puts(op_name(id)) 86 if L == 0 { op_puts(" (none <=3)\n" as *u8) } 87 else { 88 found = found + 1 89 op_puts(" L=" as *u8); op_num(L); op_puts(" :" as *u8); op_describe(op, a, b, L) 90 var ok: i64 = 1 91 let sc: *i64 = sys_mmap(8 * 12) 92 var h: i64 = 0 93 while h < nh { if so_eval(op, a, b, L, hs[h], sc) != op_target(id, hs[h]) { ok = 0 } h = h + 1 } 94 if ok == 1 { verified = verified + 1; op_puts(" [held-out OK]\n" as *u8) } else { op_puts(" [HELD-OUT FAIL]\n" as *u8) } 95 } 96 id = id + 1 97 } 98 99 op_puts("----------------------------------------------------------------\n" as *u8) 100 op_puts(" optimal programs found " as *u8); op_num(found); op_puts("/" as *u8); op_num(nt) 101 op_puts(" held-out-verified " as *u8); op_num(verified); op_puts("/" as *u8); op_num(nt); op_puts("\n" as *u8) 102 op_puts(" op counts above go 1:1 vs gcc -O2 instruction counts (honest board).\n" as *u8) 103 104 if found != nt { sys_exit(1); return 1 } 105 if verified != nt { sys_exit(2); return 2 } 106 sys_exit(0) 107 return 0 108}