nx_boolhunt.nx source

1// nx_boolhunt.nx -- the team HUNTS its own search space: it enumerates EVERY 3-input boolean 2// function (all 256 truth tables), finds each one's provably-minimal circuit, and races the 3// compiler on each -- discovering, ITSELF, the functions where its exhaustive search beats 4// the compiler's heuristics (and the ones where it's behind, which name the ops it should 5// next author). No human picks the functions; the team sweeps the whole space. The team 6// generates the C for each truth table (sum-of-products) so the compiler can compile it. 7// license_tier: ORIGINAL 8 9import "nx_boolsynth.nx" // bl_find (minimal boolean circuit) 10import "nx_gcc_race.nx" // gr_race_cv / gr_newest_gcc / gr_exists (race + count) 11import "nx_engineer_crash.nx" // eng_link + eng_run (verify the team's emit by execution) 12const K_MAGIC_4096: i64 = 4096 13const K_MAGIC_8192: i64 = 8192 14 15func bh_emit(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 } 16 17// generate the sum-of-products C function for a truth table into <path>: 18// long f(long a,long b,long c){ return (lit&lit&lit) | ... ; } 19// where the columns are a=0xAA, b=0xCC, c=0xF0 (so bit p of tt is the minterm (a_p,b_p,c_p)). 20func bool_gen_c(tt: i64, path: *u8) -> i64 { 21 let buf: *u8 = sys_mmap(K_MAGIC_4096) 22 var oi: i64 = bh_emit(buf, 0, "long f(long a,long b,long c){return " as *u8) 23 if (tt & 255) == 0 { oi = bh_emit(buf, oi, "0" as *u8) } 24 else { 25 var first: i64 = 1 26 var p: i64 = 0 27 while p < 8 { 28 if ((tt >> p) & 1) == 1 { 29 if first == 0 { oi = bh_emit(buf, oi, "|" as *u8) } 30 first = 0 31 oi = bh_emit(buf, oi, "(" as *u8) 32 if ((170 >> p) & 1) == 1 { oi = bh_emit(buf, oi, "a" as *u8) } else { oi = bh_emit(buf, oi, "(~a)" as *u8) } 33 oi = bh_emit(buf, oi, "&" as *u8) 34 if ((204 >> p) & 1) == 1 { oi = bh_emit(buf, oi, "b" as *u8) } else { oi = bh_emit(buf, oi, "(~b)" as *u8) } 35 oi = bh_emit(buf, oi, "&" as *u8) 36 if ((240 >> p) & 1) == 1 { oi = bh_emit(buf, oi, "c" as *u8) } else { oi = bh_emit(buf, oi, "(~c)" as *u8) } 37 oi = bh_emit(buf, oi, ")" as *u8) 38 } 39 p = p + 1 40 } 41 } 42 oi = bh_emit(buf, oi, ";}\n" as *u8) 43 let fd: i64 = sys_openat_wr(path, 0x1a4) 44 if fd < 0 { return 0 - 1 } 45 sys_write(fd, buf, oi); sys_close(fd) 46 return 0 47} 48 49// ---- boolean machine-code EMITTER (3-input a=rdi,b=rsi,c=rdx -> result rax) so the team's 50// size is its REAL emitted instruction count, an HONEST race vs the compiler's insn count. ---- 51func bse_rn(buf: *u8, oi: i64, id: i64) -> i64 { 52 if id == 0 { return bh_emit(buf, oi, "%rax" as *u8) } 53 if id == 1 { return bh_emit(buf, oi, "%rcx" as *u8) } 54 if id == 2 { return bh_emit(buf, oi, "%rdx" as *u8) } 55 if id == 6 { return bh_emit(buf, oi, "%rsi" as *u8) } 56 if id == 7 { return bh_emit(buf, oi, "%rdi" as *u8) } 57 if id == 8 { return bh_emit(buf, oi, "%r8" as *u8) } 58 if id == 9 { return bh_emit(buf, oi, "%r9" as *u8) } 59 if id == 10 { return bh_emit(buf, oi, "%r10" as *u8) } 60 return bh_emit(buf, oi, "%r11" as *u8) 61} 62func bse_opmn(o: i64) -> *u8 { 63 if o == BL_AND { return " andq " as *u8 } 64 if o == BL_OR { return " orq " as *u8 } 65 return " xorq " as *u8 66} 67// emit synth body; icnt[0]=instruction count (ex ret). slots: 0->rdi 1->rsi 2->rdx, op t->slot t+3. 68func bse_emit_synth(op: *i64, a: *i64, b: *i64, L: i64, buf: *u8, oi: i64, icnt: *i64) -> i64 { 69 let nsl: i64 = L + 3 70 let lu: *i64 = sys_mmap(8 * (nsl + 1)) as *i64 71 var i: i64 = 0 72 while i < nsl { lu[i] = 0 - 1; i = i + 1 } 73 var t: i64 = 0 74 while t < L { if a[t] > lu[a[t]] { lu[a[t]] = t } if bl_is_unary(op[t]) == 0 { if b[t] > lu[b[t]] { lu[b[t]] = t } } t = t + 1 } 75 let sreg: *i64 = sys_mmap(8 * (nsl + 1)) as *i64 76 sreg[0] = 7; sreg[1] = 6; sreg[2] = 2 77 let pool: *i64 = sys_mmap(8 * 8) as *i64 78 pool[0]=11; pool[1]=10; pool[2]=9; pool[3]=8; pool[4]=1; pool[5]=0 79 var psz: i64 = 6 80 var ic: i64 = 0 81 t = 0 82 while t < L { 83 let o: i64 = op[t] 84 let sa: i64 = a[t] 85 let aReg: i64 = sreg[sa] 86 var dst: i64 = 0 - 1 87 if lu[sa] == t { if sa >= 3 { dst = aReg } } // reuse a dead computed operand 88 if dst < 0 { dst = pool[psz - 1]; psz = psz - 1 } 89 if bl_is_unary(o) == 1 { 90 if dst != aReg { oi = bh_emit(buf, oi, " movq " as *u8); oi = bse_rn(buf, oi, aReg); oi = bh_emit(buf, oi, ", " as *u8); oi = bse_rn(buf, oi, dst); oi = bh_emit(buf, oi, "\n" as *u8); ic = ic + 1 } 91 oi = bh_emit(buf, oi, " notq " as *u8); oi = bse_rn(buf, oi, dst); oi = bh_emit(buf, oi, "\n" as *u8); ic = ic + 1 92 } else { 93 let sb: i64 = b[t] 94 let bReg: i64 = sreg[sb] 95 if dst == aReg { oi = bh_emit(buf, oi, bse_opmn(o)); oi = bse_rn(buf, oi, bReg); oi = bh_emit(buf, oi, ", " as *u8); oi = bse_rn(buf, oi, dst); oi = bh_emit(buf, oi, "\n" as *u8); ic = ic + 1 } 96 else { if dst == bReg { oi = bh_emit(buf, oi, bse_opmn(o)); oi = bse_rn(buf, oi, aReg); oi = bh_emit(buf, oi, ", " as *u8); oi = bse_rn(buf, oi, dst); oi = bh_emit(buf, oi, "\n" as *u8); ic = ic + 1 } 97 else { oi = bh_emit(buf, oi, " movq " as *u8); oi = bse_rn(buf, oi, aReg); oi = bh_emit(buf, oi, ", " as *u8); oi = bse_rn(buf, oi, dst); oi = bh_emit(buf, oi, "\n" as *u8); ic = ic + 1 98 oi = bh_emit(buf, oi, bse_opmn(o)); oi = bse_rn(buf, oi, bReg); oi = bh_emit(buf, oi, ", " as *u8); oi = bse_rn(buf, oi, dst); oi = bh_emit(buf, oi, "\n" as *u8); ic = ic + 1 } } 99 } 100 sreg[t + 3] = dst 101 if lu[sa] == t { if sa >= 3 { if aReg != dst { pool[psz] = aReg; psz = psz + 1 } } } 102 t = t + 1 103 } 104 let rr: i64 = sreg[L + 2] 105 if rr != 0 { oi = bh_emit(buf, oi, " movq " as *u8); oi = bse_rn(buf, oi, rr); oi = bh_emit(buf, oi, ", %rax\n" as *u8); ic = ic + 1 } 106 oi = bh_emit(buf, oi, " ret\n" as *u8) 107 icnt[0] = ic 108 return oi 109} 110// full program: driver sets rdi=0xAA,rsi=0xCC,rdx=0xF0 (the truth-table columns), calls synth, 111// exits with (result & 255) -- which IS the truth table, so a run verifies correctness exhaustively. 112func bse_emit_full(op: *i64, a: *i64, b: *i64, L: i64, buf: *u8, icnt: *i64) -> i64 { 113 var oi: i64 = bh_emit(buf, 0, " .att_syntax prefix\n .text\n .globl _start\n_start:\n movabsq $170, %rdi\n movabsq $204, %rsi\n movabsq $240, %rdx\n call synth\n andq $255, %rax\n movq %rax, %rdi\n movabsq $60, %rax\n syscall\nsynth:\n" as *u8) 114 oi = bse_emit_synth(op, a, b, L, buf, oi, icnt) 115 return oi 116} 117 118// race one truth table HONESTLY: emit the team's circuit, run it (verify == tt), count its 119// instructions, vs best compiler insns. res[0]=team_insns 1=best_comp 2=verdict 3=verified 120func bool_hunt_one(tt: i64, gccpath: *u8, res: *i64) -> i64 { 121 let op: *i64 = sys_mmap(8 * 12) as *i64 122 let a: *i64 = sys_mmap(8 * 12) as *i64 123 let b: *i64 = sys_mmap(8 * 12) as *i64 124 let buf: *u8 = sys_mmap(K_MAGIC_8192) 125 let icnt: *i64 = sys_mmap(8) as *i64 126 let L: i64 = bl_find(tt, op, a, b, 6) 127 res[3] = 0 128 if L <= 0 { res[0] = 1; res[1] = 1; res[2] = 0; if L == 0 { res[3] = 1 } return 0 } // trivial (input/const) 129 let blen: i64 = bse_emit_full(op, a, b, L, buf, icnt) 130 let fd: i64 = sys_openat_wr("/tmp/bht.s" as *u8, 0x1a4) 131 if fd >= 0 { sys_write(fd, buf, blen); sys_close(fd) } 132 res[0] = icnt[0] 133 if eng_link("/tmp/bht.s" as *u8, "/tmp/bht.elf" as *u8) == 0 { if eng_run("/tmp/bht.elf" as *u8, 0 as *u8) == (tt & 255) { res[3] = 1 } } 134 bool_gen_c(tt, "/tmp/bh.c" as *u8) 135 var best: i64 = gr_race_cv(gccpath, "/tmp/bh.c" as *u8, "/tmp/bh.o" as *u8, "/tmp/bh.txt" as *u8, "f" as *u8) 136 if gr_exists("/usr/bin/clang" as *u8) == 1 { 137 let cc: i64 = gr_race_cv("/usr/bin/clang" as *u8, "/tmp/bh.c" as *u8, "/tmp/bh2.o" as *u8, "/tmp/bh2.txt" as *u8, "f" as *u8) 138 if cc > 0 { if cc < best { best = cc } } 139 } 140 res[1] = best 141 res[2] = 0 142 if best > 0 { if res[0] < best { res[2] = 1 } if res[0] > best { res[2] = 0 - 1 } } 143 return 0 144}