code wiki / _hdl_build / nx_superopt_opt.nx
nx_superopt_opt.nx
buildroot/runtime/_hdl_build/nx_superopt_opt.nx
about
nx_superopt_opt.nx -- a COST-OPTIMAL (exhaustive-shortest) superoptimizer over the
full integer/bit op set {add,sub,mul,shl,sar,xor,and,or}. Given a function as
input/output examples it returns the SHORTEST straight-line program that matches,
searching length 1 then 2 then 3 -- so the result is provably minimal within the
bound (the superoptimizer's defining property: optimality, which heuristic
compilers sacrifice). Verified over FULL-RANGE 64-bit inputs (sign bit + negatives),
not toy ranges. This is the engine for an honest 1:1 board vs gcc -O2.
Refs: Massalin, "Superoptimizer," AFIPS/ASPLOS 1987; Warren, Hacker's Delight 2e
(the branchless bit-tricks); GNU superopt. Slots: 0=x, 1=0, 2=1, then computed.
dependencies 1 imports · 3 importers
imports: nx_syscalls.nx
imported by: nx_mulchain.nxnx_superopt_emit.nxnx_superopt_opt_test.nx
structs
| none |
consts
| 14 | const SO_ADD: i64 = 0 |
| 15 | const SO_SUB: i64 = 1 |
| 16 | const SO_MUL: i64 = 2 |
| 17 | const SO_SHL: i64 = 3 |
| 18 | const SO_SAR: i64 = 4 |
| 19 | const SO_XOR: i64 = 5 |
| 20 | const SO_AND: i64 = 6 |
| 21 | const SO_OR: i64 = 7 |
| 24 | const SO_LEA2: i64 = 9 |
| 25 | const SO_LEA4: i64 = 10 |
| 26 | const SO_LEA8: i64 = 11 |
| 42 | const SO_NIMM: i64 = 9 |
functions
| 28 | func so_is_shift(o: i64) -> i64 { if o == SO_SHL { return 1 } if o == SO_SAR { return 1 } return 0 } |
| 31 | func so_imm(k: i64) -> i64 called by 1: so_enum |
| 46 | func so_eval(op: *i64, a: *i64, b: *i64, L: i64, x: i64, s: *i64) -> i64 |
| 67 | func so_matches(op: *i64, a: *i64, b: *i64, L: i64, ex_x: *i64, ex_y: *i64, nex: i64, s: *i64) -> i64 |
| 75 | func so_enum(op: *i64, a: *i64, b: *i64, t: i64, L: i64, nslot: i64, |
| 111 | func so_find(ex_x: *i64, ex_y: *i64, nex: i64, op: *i64, a: *i64, b: *i64, maxL: i64) -> i64 |