code wiki / _hdl_build / nx_superopt_emit.nx
nx_superopt_emit.nx source
↩ module page · 216 lines · 12324 B
1// nx_superopt_emit.nx -- emit COMPETITIVE x86-64 machine code for a superoptimized
2// program (the slot/op/a/b form from nx_superopt_opt). This is the team building UP from
3// machine code: SYNTHESIZE the optimal op sequence, then EMIT it as tight assembly to
4// race gcc -O2. Tightness comes from the same register-allocation insight proved in
5// nx_regalloc_calls: keep the running result in one register (reuse a dead operand's
6// register in place), and use `lea` to fuse a shift/add with its move so each op is ~1
7// instruction -- exactly how gcc's strength reduction emits. Input x in %rdi, result in
8// %rax. license_tier: ORIGINAL
9//
10// op/a/b: op[t] in {ADD,SUB,MUL,SHL,SAR,XOR,AND,OR}; a[t],b[t] are slot indices
11// (0=x, 1=const0, 2=const1, t+3=result of op t); for shifts b[t] is the shift amount.
12
13import "nx_superopt_opt.nx" // SO_* op constants, so_eval, so_is_shift (chains in syscalls)
14
15// our physical register ids: 0..5 = the allocatable pool; 7 = %rdi (x, source).
16func se_rn(buf: *u8, oi: i64, id: i64) -> i64 {
17 if id == 0 { buf[oi]=37 as u8; buf[oi+1]=114 as u8; buf[oi+2]=97 as u8; buf[oi+3]=120 as u8; return oi + 4 } // %rax
18 if id == 1 { buf[oi]=37 as u8; buf[oi+1]=114 as u8; buf[oi+2]=99 as u8; buf[oi+3]=120 as u8; return oi + 4 } // %rcx
19 if id == 2 { buf[oi]=37 as u8; buf[oi+1]=114 as u8; buf[oi+2]=100 as u8; buf[oi+3]=120 as u8; return oi + 4 } // %rdx
20 if id == 3 { buf[oi]=37 as u8; buf[oi+1]=114 as u8; buf[oi+2]=115 as u8; buf[oi+3]=105 as u8; return oi + 4 } // %rsi
21 if id == 4 { buf[oi]=37 as u8; buf[oi+1]=114 as u8; buf[oi+2]=56 as u8; return oi + 3 } // %r8
22 if id == 5 { buf[oi]=37 as u8; buf[oi+1]=114 as u8; buf[oi+2]=57 as u8; return oi + 3 } // %r9
23 buf[oi]=37 as u8; buf[oi+1]=114 as u8; buf[oi+2]=100 as u8; buf[oi+3]=105 as u8; return oi + 4 // %rdi
24}
25
26func se_str(buf: *u8, oi: i64, s: *u8) -> i64 { var j: i64 = 0; while s[j] != (0 as u8) { buf[oi] = s[j]; oi = oi + 1; j = j + 1 } return oi }
27func se_num(buf: *u8, oi: i64, v: i64) -> i64 {
28 var m: i64 = v; if m < 0 { buf[oi] = 45 as u8; oi = oi + 1; m = 0 - m }
29 let t: *u8 = sys_mmap(28); var k: i64 = 0
30 if m == 0 { t[0] = 48; k = 1 }
31 while m > 0 { t[k] = 48 + (m % 10); m = m / 10; k = k + 1 }
32 var i: i64 = 0; while i < k { buf[oi] = t[k - 1 - i]; oi = oi + 1; i = i + 1 }
33 return oi
34}
35
36func se_opmn(o: i64) -> *u8 {
37 if o == SO_ADD { return "addq " as *u8 }
38 if o == SO_SUB { return "subq " as *u8 }
39 if o == SO_MUL { return "imulq " as *u8 }
40 if o == SO_XOR { return "xorq " as *u8 }
41 if o == SO_AND { return "andq " as *u8 }
42 if o == SO_OR { return "orq " as *u8 }
43 return "?? " as *u8
44}
45
46// emit one operand (a slot) as text: a register, or an immediate ($0 / $1).
47func se_slot(buf: *u8, oi: i64, slot: i64, sreg: *i64) -> i64 {
48 if slot == 1 { return se_str(buf, oi, "$0" as *u8) }
49 if slot == 2 { return se_str(buf, oi, "$1" as *u8) }
50 return se_rn(buf, oi, sreg[slot])
51}
52func se_slot_isreg(slot: i64) -> i64 { if slot == 1 { return 0 } if slot == 2 { return 0 } return 1 }
53
54// EMIT the synthesized function body (label-less ops + ret) into buf. icnt[0] gets the
55// instruction count (excluding ret) -- the team's number for the race vs gcc -O2.
56func se_emit_synth(op: *i64, a: *i64, b: *i64, L: i64, buf: *u8, oi: i64, icnt: *i64) -> i64 {
57 // last read + use-count of each slot (to free / reuse registers and to fuse safely)
58 let nsl: i64 = L + 3
59 let lu: *i64 = sys_mmap(8 * (nsl + 1)) as *i64
60 let uc: *i64 = sys_mmap(8 * (nsl + 1)) as *i64
61 var i: i64 = 0
62 while i < nsl { lu[i] = 0 - 1; uc[i] = 0; i = i + 1 }
63 var t: i64 = 0
64 while t < L {
65 if a[t] > lu[a[t]] { lu[a[t]] = t }
66 uc[a[t]] = uc[a[t]] + 1
67 if so_is_shift(op[t]) == 0 { if b[t] > lu[b[t]] { lu[b[t]] = t } uc[b[t]] = uc[b[t]] + 1 }
68 t = t + 1
69 }
70 // PEEPHOLE pre-pass: an ADD whose operand was produced by SHL(x,k) or ADD(x,x) and is
71 // used ONLY here fuses into ONE x86 lea(base, index, scale) -- gcc's strength reduction.
72 // Restricted to index == x (slot 0, always live in %rdi) so liveness stays trivially sound.
73 let skip: *i64 = sys_mmap(8 * (L + 1)) as *i64
74 let fuse: *i64 = sys_mmap(8 * (L + 1)) as *i64
75 let fbase: *i64 = sys_mmap(8 * (L + 1)) as *i64
76 let fidx: *i64 = sys_mmap(8 * (L + 1)) as *i64
77 let fscale: *i64 = sys_mmap(8 * (L + 1)) as *i64
78 t = 0
79 while t < L { skip[t] = 0; fuse[t] = 0; t = t + 1 }
80 t = 0
81 while t < L {
82 if op[t] == SO_ADD {
83 let sa: i64 = a[t]
84 let sb: i64 = b[t]
85 var done: i64 = 0
86 var which: i64 = sb // try the second operand as the scaled part
87 var base: i64 = sa
88 var pass: i64 = 0
89 while pass < 2 {
90 if done == 0 { if which >= 3 { if uc[which] == 1 { if skip[which - 3] == 0 {
91 let p: i64 = which - 3
92 var sc: i64 = 0
93 if op[p] == SO_SHL { if b[p] >= 1 { if b[p] <= 3 { sc = 1 << b[p] } } }
94 if op[p] == SO_ADD { if a[p] == b[p] { sc = 2 } }
95 if sc > 0 { if a[p] == 0 { // index src must be x (slot 0)
96 fuse[t] = 1; fbase[t] = base; fidx[t] = a[p]; fscale[t] = sc; skip[p] = 1; done = 1
97 } }
98 } } } }
99 which = sa; base = sb; pass = pass + 1 // then try the first operand
100 }
101 }
102 t = t + 1
103 }
104 let sreg: *i64 = sys_mmap(8 * (nsl + 1)) as *i64
105 sreg[0] = 7 // x -> %rdi
106 // free pool popped from the TOP (psz-1); order it so %rax(0) pops FIRST -> chains land
107 // in %rax and need no final move, matching how gcc keeps the result in %rax.
108 let pool: *i64 = sys_mmap(8 * 8) as *i64
109 pool[0]=5; pool[1]=4; pool[2]=3; pool[3]=2; pool[4]=1; pool[5]=0
110 var psz: i64 = 6
111 var ic: i64 = 0
112 t = 0
113 while t < L {
114 if skip[t] == 1 {
115 sreg[t + 3] = 0 - 9 // folded producer -- never materialized
116 } else { if fuse[t] == 1 {
117 let bReg: i64 = sreg[fbase[t]]
118 let iReg: i64 = sreg[fidx[t]]
119 var fdst: i64 = 0 - 1
120 if lu[fbase[t]] == t { if bReg != 7 { fdst = bReg } }
121 if fdst < 0 { fdst = pool[psz - 1]; psz = psz - 1 }
122 oi = se_str(buf, oi, " leaq (" as *u8); oi = se_rn(buf, oi, bReg); oi = se_str(buf, oi, "," as *u8); oi = se_rn(buf, oi, iReg); oi = se_str(buf, oi, "," as *u8); oi = se_num(buf, oi, fscale[t]); oi = se_str(buf, oi, "), " as *u8); oi = se_rn(buf, oi, fdst); oi = se_str(buf, oi, "\n" as *u8)
123 ic = ic + 1
124 sreg[t + 3] = fdst
125 if lu[fbase[t]] == t { if bReg != 7 { if bReg != fdst { pool[psz] = bReg; psz = psz + 1 } } }
126 } else {
127 let o: i64 = op[t]
128 let sa: i64 = a[t]
129 let aReg: i64 = sreg[sa] // operand A register (sa is x or computed)
130 // pick dst: reuse A's reg if A dies here and A is a pool reg (not %rdi); else pop pool
131 var dst: i64 = 0 - 1
132 if lu[sa] == t { if aReg != 7 { dst = aReg } }
133 if dst < 0 { dst = pool[psz - 1]; psz = psz - 1 }
134 var emitted: i64 = 0
135
136 if so_is_shift(o) == 1 {
137 let amt: i64 = b[t]
138 if o == SO_SHL { if amt >= 1 { if amt <= 3 { if se_slot_isreg(sa) == 1 {
139 oi = se_str(buf, oi, " leaq 0(," as *u8); oi = se_rn(buf, oi, aReg)
140 oi = se_str(buf, oi, "," as *u8); oi = se_num(buf, oi, 1 << amt)
141 oi = se_str(buf, oi, "), " as *u8); oi = se_rn(buf, oi, dst); oi = se_str(buf, oi, "\n" as *u8)
142 ic = ic + 1; emitted = 1
143 } } } }
144 if emitted == 0 {
145 if dst != aReg { oi = se_str(buf, oi, " movq " as *u8); oi = se_slot(buf, oi, sa, sreg); oi = se_str(buf, oi, ", " as *u8); oi = se_rn(buf, oi, dst); oi = se_str(buf, oi, "\n" as *u8); ic = ic + 1 }
146 if o == SO_SHL { oi = se_str(buf, oi, " shlq $" as *u8) } else { oi = se_str(buf, oi, " sarq $" as *u8) }
147 oi = se_num(buf, oi, amt); oi = se_str(buf, oi, ", " as *u8); oi = se_rn(buf, oi, dst); oi = se_str(buf, oi, "\n" as *u8); ic = ic + 1
148 }
149 } else {
150 let sb: i64 = b[t]
151 let bReg: i64 = sreg[sb]
152 // explicit fused lea op from the search: base + index*scale, one instruction
153 var lsc: i64 = 0
154 if o == SO_LEA2 { lsc = 2 }
155 if o == SO_LEA4 { lsc = 4 }
156 if o == SO_LEA8 { lsc = 8 }
157 if lsc > 0 {
158 oi = se_str(buf, oi, " leaq (" as *u8); oi = se_rn(buf, oi, aReg); oi = se_str(buf, oi, "," as *u8); oi = se_rn(buf, oi, bReg); oi = se_str(buf, oi, "," as *u8); oi = se_num(buf, oi, lsc); oi = se_str(buf, oi, "), " as *u8); oi = se_rn(buf, oi, dst); oi = se_str(buf, oi, "\n" as *u8)
159 ic = ic + 1; emitted = 1
160 }
161 if o == SO_ADD { if se_slot_isreg(sa) == 1 { if se_slot_isreg(sb) == 1 { if dst != aReg { if dst != bReg {
162 oi = se_str(buf, oi, " leaq (" as *u8); oi = se_rn(buf, oi, aReg); oi = se_str(buf, oi, "," as *u8); oi = se_rn(buf, oi, bReg)
163 oi = se_str(buf, oi, "), " as *u8); oi = se_rn(buf, oi, dst); oi = se_str(buf, oi, "\n" as *u8)
164 ic = ic + 1; emitted = 1
165 } } } } }
166 if emitted == 0 {
167 if dst != aReg { oi = se_str(buf, oi, " movq " as *u8); oi = se_slot(buf, oi, sa, sreg); oi = se_str(buf, oi, ", " as *u8); oi = se_rn(buf, oi, dst); oi = se_str(buf, oi, "\n" as *u8); ic = ic + 1 }
168 oi = se_str(buf, oi, " " as *u8); oi = se_str(buf, oi, se_opmn(o)); oi = se_slot(buf, oi, sb, sreg); oi = se_str(buf, oi, ", " as *u8); oi = se_rn(buf, oi, dst); oi = se_str(buf, oi, "\n" as *u8); ic = ic + 1
169 }
170 }
171 sreg[t + 3] = dst
172 // free A's register back to the pool if it died here and wasn't reused as dst
173 if lu[sa] == t { if aReg != 7 { if aReg != dst { pool[psz] = aReg; psz = psz + 1 } } }
174 } }
175 t = t + 1
176 }
177 // ensure result (slot L+2) ends in %rax
178 let rres: i64 = sreg[L + 2]
179 if rres != 0 { oi = se_str(buf, oi, " movq " as *u8); oi = se_rn(buf, oi, rres); oi = se_str(buf, oi, ", %rax\n" as *u8); ic = ic + 1 }
180 oi = se_str(buf, oi, " ret\n" as *u8)
181 icnt[0] = ic
182 return oi
183}
184
185// EMIT a complete program whose synth is a single imul-by-constant (the strategy the team
186// diagnosed it lacked). 1 instruction, ~3-cycle latency -- the right choice (by cost) for
187// constants whose shift-add chain is long or unreachable. icnt[0] = 1.
188func se_emit_imul_full(c: i64, inputs: *i64, nin: i64, buf: *u8, icnt: *i64) -> i64 {
189 var oi: i64 = 0
190 oi = se_str(buf, oi, " .att_syntax prefix\n .text\n .globl _start\n_start:\n xorq %rbx, %rbx\n" as *u8)
191 var i: i64 = 0
192 while i < nin {
193 oi = se_str(buf, oi, " movabsq $" as *u8); oi = se_num(buf, oi, inputs[i]); oi = se_str(buf, oi, ", %rdi\n call synth\n addq %rax, %rbx\n" as *u8)
194 i = i + 1
195 }
196 oi = se_str(buf, oi, " movq %rbx, %rdi\n andq $255, %rdi\n movabsq $60, %rax\n syscall\nsynth:\n imulq $" as *u8)
197 oi = se_num(buf, oi, c); oi = se_str(buf, oi, ", %rdi, %rax\n ret\n" as *u8)
198 icnt[0] = 1
199 return oi
200}
201
202// EMIT a complete runnable program: a _start driver that sums synth(in_i) over the test
203// inputs into %rbx (callee-saved, survives the calls) and exits with the low byte, plus
204// the synth function. The test compares that byte to its own checksum -> 1:1 emit proof.
205func se_emit_full(op: *i64, a: *i64, b: *i64, L: i64, inputs: *i64, nin: i64, buf: *u8, icnt: *i64) -> i64 {
206 var oi: i64 = 0
207 oi = se_str(buf, oi, " .att_syntax prefix\n .text\n .globl _start\n_start:\n xorq %rbx, %rbx\n" as *u8)
208 var i: i64 = 0
209 while i < nin {
210 oi = se_str(buf, oi, " movabsq $" as *u8); oi = se_num(buf, oi, inputs[i]); oi = se_str(buf, oi, ", %rdi\n call synth\n addq %rax, %rbx\n" as *u8)
211 i = i + 1
212 }
213 oi = se_str(buf, oi, " movq %rbx, %rdi\n andq $255, %rdi\n movabsq $60, %rax\n syscall\nsynth:\n" as *u8)
214 oi = se_emit_synth(op, a, b, L, buf, oi, icnt)
215 return oi
216}