code wiki / _hdl_build / nx_superopt_machinecode_test.nx
nx_superopt_machinecode_test.nx source
↩ module page · 149 lines · 7041 B
1// nx_superopt_machinecode_test.nx -- the team builds MACHINE CODE UP, MULTI-ARCH,
2// by itself. The algebra (x*C -> (x<<a) +/- (x<<b)) is authored ONCE by search; the
3// per-target ENCODERS lower it to real RV64 AND AArch64 machine-code words, and
4// each is PROVEN by EXECUTION on its own sovereign emulator (no qemu, no JIT, no
5// hand-written stream). This is emit-to-TARGET, not bake-one-binary -- the same
6// invention lands on whatever silicon the spore/seed reaches. I wrote the search +
7// the two encoders; the team produced the bytes and the emulators ran them.
8//
9// Both emulators return the exit register (a0/x0) as an 8-bit status, so each plan
10// is checked exhaustively over the inputs where x*C < 256 -- enough to convict a
11// wrong instruction stream. Encodings per the RISC-V + ARMv8-A manuals. Known
12// answer: every authored program, on BOTH arches, computes x*C -> exit 0.
13
14import "nx_emu_rv64.nx"
15import "nx_emu_arm64.nx"
16
17// ---- the GENERATOR: search the cheapest (x<<a) op (x<<b) == x*C (op 0=add,1=sub) ----
18func mc_eval(a: i64, op: i64, b: i64, x: i64) -> i64 {
19 if op == 0 { return (x << a) + (x << b) }
20 return (x << a) - (x << b)
21}
22func mc_verify_alg(a: i64, op: i64, b: i64, C: i64) -> i64 {
23 var s: i64 = 19088743
24 var t: i64 = 0
25 while t < 24 { s = s * 6364136223846793005 + 1442695040888963407; let x: i64 = s
26 if mc_eval(a, op, b, x) != x * C { return 0 } t = t + 1 }
27 return 1
28}
29func mc_best(C: i64, out: *i64) -> i64 {
30 var a: i64 = 0
31 while a < 12 {
32 var b: i64 = 0
33 while b < 12 {
34 var op: i64 = 0
35 while op < 2 {
36 if mc_verify_alg(a, op, b, C) == 1 {
37 let cost: i64 = 1 + a + b + b
38 if out[3] < 0 { out[0]=a; out[1]=op; out[2]=b; out[3]=cost }
39 else { if cost < out[3] { out[0]=a; out[1]=op; out[2]=b; out[3]=cost } }
40 }
41 op = op + 1
42 }
43 b = b + 1
44 }
45 a = a + 1
46 }
47 if out[3] < 0 { return 0 }
48 return 1
49}
50
51func mc_put_w(code: *u8, o: i64, w: i64) -> i64 {
52 code[o] = w & 0xff; code[o+1] = (w >> 8) & 0xff; code[o+2] = (w >> 16) & 0xff; code[o+3] = (w >> 24) & 0xff
53 return o + 4
54}
55
56// ---- RV64 encoders (regs: zero=0 t0=5 t1=6 a0=10 a1=11 a7=17) ----
57func rv_addi(rd: i64, rs1: i64, imm: i64) -> i64 { return ((imm & 0xfff) << 20) | (rs1 << 15) | (rd << 7) | 0x13 }
58func rv_slli(rd: i64, rs1: i64, sh: i64) -> i64 { return ((sh & 0x3f) << 20) | (rs1 << 15) | (1 << 12) | (rd << 7) | 0x13 }
59func rv_add(rd: i64, rs1: i64, rs2: i64) -> i64 { return (rs2 << 20) | (rs1 << 15) | (rd << 7) | 0x33 }
60func rv_sub(rd: i64, rs1: i64, rs2: i64) -> i64 { return (0x20 << 25) | (rs2 << 20) | (rs1 << 15) | (rd << 7) | 0x33 }
61func mc_run_rv(x: i64, a: i64, op: i64, b: i64) -> i64 {
62 let code: *u8 = sys_mmap(64)
63 var o: i64 = 0
64 o = mc_put_w(code, o, rv_addi(11, 0, x)) // li a1, x
65 o = mc_put_w(code, o, rv_slli(5, 11, a)) // slli t0, a1, a
66 o = mc_put_w(code, o, rv_slli(6, 11, b)) // slli t1, a1, b
67 if op == 0 { o = mc_put_w(code, o, rv_add(10, 5, 6)) } else { o = mc_put_w(code, o, rv_sub(10, 5, 6)) }
68 o = mc_put_w(code, o, rv_addi(17, 0, 93)) // li a7, 93
69 o = mc_put_w(code, o, 0x00000073) // ecall
70 return emu_rv64_run(code, o)
71}
72
73// ---- AArch64 encoders (regs: x0 result, x1 input, x8 nr, x9 temp, xzr=31) ----
74func a64_movz(rd: i64, imm16: i64) -> i64 { return 0xD2800000 | ((imm16 & 0xffff) << 5) | rd }
75func a64_add_sh(rd: i64, rn: i64, rm: i64, sh: i64) -> i64 { return 0x8B000000 | (rm << 16) | ((sh & 0x3f) << 10) | (rn << 5) | rd }
76func a64_sub_sh(rd: i64, rn: i64, rm: i64, sh: i64) -> i64 { return 0xCB000000 | (rm << 16) | ((sh & 0x3f) << 10) | (rn << 5) | rd }
77func mc_run_a64(x: i64, a: i64, op: i64, b: i64) -> i64 {
78 let code: *u8 = sys_mmap(64)
79 var o: i64 = 0
80 o = mc_put_w(code, o, a64_movz(1, x)) // movz x1, #x
81 o = mc_put_w(code, o, a64_add_sh(9, 31, 1, a)) // add x9, xzr, x1, lsl #a -> x<<a
82 if op == 0 { o = mc_put_w(code, o, a64_add_sh(0, 9, 1, b)) } else { o = mc_put_w(code, o, a64_sub_sh(0, 9, 1, b)) }
83 o = mc_put_w(code, o, a64_movz(8, 93)) // movz x8, #93
84 o = mc_put_w(code, o, 0xD4000001) // svc #0
85 return emu_arm64_run(code, o)
86}
87
88func mc_puts(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
89func mc_num(v: i64) -> i64 {
90 let b: *u8 = sys_mmap(28); var m: i64 = v; if m < 0 { m = 0 - m }
91 let t: *u8 = sys_mmap(28); var k: i64 = 0
92 if m == 0 { t[0] = 48; k = 1 }
93 while m > 0 { t[k] = 48 + (m % 10); m = m / 10; k = k + 1 }
94 var i: i64 = 0; while i < k { b[i] = t[k - 1 - i]; i = i + 1 }
95 sys_write(1, b, k); return 0
96}
97
98// verify the authored plan's machine code on one arch over all valid x. 1=ok.
99func mc_check(arch: i64, C: i64, a: i64, op: i64, b: i64) -> i64 {
100 let maxx: i64 = 255 / C
101 var x: i64 = 0
102 while x <= maxx {
103 var r: i64 = 0
104 if arch == 0 { r = mc_run_rv(x, a, op, b) } else { r = mc_run_a64(x, a, op, b) }
105 if r != x * C { return 0 }
106 x = x + 1
107 }
108 return 1
109}
110
111func main() -> i64 {
112 mc_puts("=== TEAM authors MACHINE CODE by search, MULTI-ARCH, proven on emulators ===\n" as *u8)
113 let consts: *i64 = sys_mmap(8 * 8) as *i64
114 var n: i64 = 0
115 consts[n] = 7; n = n + 1
116 consts[n] = 9; n = n + 1
117 consts[n] = 5; n = n + 1
118 consts[n] = 15; n = n + 1
119 let out: *i64 = sys_mmap(32) as *i64
120 var rv_ok: i64 = 0
121 var a64_ok: i64 = 0
122 var i: i64 = 0
123 while i < n {
124 let C: i64 = consts[i]
125 out[3] = 0 - 1
126 if mc_best(C, out) == 1 {
127 let a: i64 = out[0]; let op: i64 = out[1]; let b: i64 = out[2]
128 mc_puts(" x*" as *u8); mc_num(C); mc_puts(" -> (x<<" as *u8); mc_num(a)
129 if op == 0 { mc_puts(")+(x<<" as *u8) } else { mc_puts(")-(x<<" as *u8) }
130 mc_num(b); mc_puts(") " as *u8)
131 let rok: i64 = mc_check(0, C, a, op, b)
132 let aok: i64 = mc_check(1, C, a, op, b)
133 if rok == 1 { rv_ok = rv_ok + 1; mc_puts("RV64:exec-ok " as *u8) } else { mc_puts("RV64:FAIL " as *u8) }
134 if aok == 1 { a64_ok = a64_ok + 1; mc_puts("ARM64:exec-ok\n" as *u8) } else { mc_puts("ARM64:FAIL\n" as *u8) }
135 }
136 i = i + 1
137 }
138
139 mc_puts("----------------------------------------------------------------\n" as *u8)
140 mc_puts(" authored + emulator-PROVEN RV64 " as *u8); mc_num(rv_ok); mc_puts("/" as *u8); mc_num(n)
141 mc_puts(" ARM64 " as *u8); mc_num(a64_ok); mc_puts("/" as *u8); mc_num(n); mc_puts("\n" as *u8)
142 mc_puts(" one authored algebra -> two real ISAs -> proven by execution. emit-to-target.\n" as *u8)
143
144 // GATE: every authored plan verified by EXECUTION on BOTH arches.
145 if rv_ok != n { sys_exit(1); return 1 }
146 if a64_ok != n { sys_exit(2); return 2 }
147 sys_exit(0)
148 return 0
149}