code wiki / _hdl_build / nx_superopt_strength_test.nx
nx_superopt_strength_test.nx source
↩ module page · 74 lines · 3444 B
1// nx_superopt_strength_test.nx -- watch the GENERATOR author optimizations itself.
2// For a set of constants it has NEVER been told how to lower, the search discovers
3// the cheapest verified `x*C` rewrite, prints it, and proves it 1:1. I did not
4// write any of these lowerings -- the search did. Known answer: every authored plan
5// is verified == x*C, and every reducible constant beats the multiply. exit 0.
6
7import "nx_superopt_strength.nx"
8
9func sot_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 sot_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}
18
19// describe the authored plan as human-readable code.
20func sot_show(out: *i64) -> i64 {
21 let kind: i64 = out[0]
22 if kind == SO_PLAN_MUL { sot_puts("x*C (multiply -- no cheaper form found)" as *u8); return 0 }
23 if kind == SO_PLAN_SHL { sot_puts("x<<" as *u8); sot_num(out[1]); return 0 }
24 sot_puts("(x<<" as *u8); sot_num(out[1]); sot_puts(")" as *u8)
25 if out[2] == SO_ADD { sot_puts(" + " as *u8) } else { sot_puts(" - " as *u8) }
26 sot_puts("(x<<" as *u8); sot_num(out[3]); sot_puts(")" as *u8)
27 return 0
28}
29
30func main() -> i64 {
31 sot_puts("=== GENERATOR authors strength-reductions by SEARCH (not hand-written) ===\n" as *u8)
32 let consts: *i64 = sys_mmap(8 * 16) as *i64
33 var n: i64 = 0
34 consts[n] = 8; n = n + 1
35 consts[n] = 9; n = n + 1
36 consts[n] = 7; n = n + 1
37 consts[n] = 6; n = n + 1
38 consts[n] = 5; n = n + 1
39 consts[n] = 1024; n = n + 1
40 consts[n] = 15; n = n + 1
41 consts[n] = 31; n = n + 1
42 consts[n] = 6364136223846793005; n = n + 1 // the LCG prime -- no reduction; falls back to mul
43
44 let out: *i64 = sys_mmap(32) as *i64
45 var bad_verify: i64 = 0
46 var reducible_won: i64 = 0
47 var reducible_total: i64 = 0
48 var i: i64 = 0
49 while i < n {
50 let C: i64 = consts[i]
51 let cost: i64 = so_best(C, out)
52 sot_puts(" x*" as *u8); sot_num(C); sot_puts(" -> " as *u8); sot_show(out)
53 sot_puts(" [cost " as *u8); sot_num(cost); sot_puts(" vs mul " as *u8); sot_num(SO_MUL_COST); sot_puts("]\n" as *u8)
54 // the authored plan MUST be 1:1 with x*C
55 if so_verify(out[0], out[1], out[2], out[3], C) != 1 { bad_verify = bad_verify + 1 }
56 // small constants are reducible; the LCG prime is not
57 if C < 4096 {
58 reducible_total = reducible_total + 1
59 if cost < SO_MUL_COST { reducible_won = reducible_won + 1 }
60 }
61 i = i + 1
62 }
63
64 sot_puts("----------------------------------------------------------------\n" as *u8)
65 sot_puts(" the SEARCH authored each lowering + proved it 1:1; I wrote no rule.\n" as *u8)
66 sot_puts(" reducible constants beaten-by-shifts: " as *u8); sot_num(reducible_won)
67 sot_puts(" / " as *u8); sot_num(reducible_total); sot_puts("\n" as *u8)
68
69 // GATE: every authored plan is correct, and every reducible constant won.
70 if bad_verify != 0 { sys_exit(1); return 1 }
71 if reducible_won != reducible_total { sys_exit(2); return 2 }
72 sys_exit(0)
73 return 0
74}