code wiki / _hdl_build / nx_mulchain.nx
nx_mulchain.nx
buildroot/runtime/_hdl_build/nx_mulchain.nx
about
nx_mulchain.nx -- a FASTER, deeper superoptimizer for multiply-by-constant: search the
MULTIPLIER space (addition/subtraction/shift chains) instead of evaluating raw programs
on many inputs. Every slot holds a multiplier k (meaning k*x); ops grow the set:
ADD(k1,k2)=k1+k2, SUB(k1,k2)=k1-k2, SHL(k,s)=k<<s. Iterative deepening over op-count
returns the SHORTEST chain to C (provably minimal op count). Magnitude pruning (|k| <=
4|C|) keeps it fast and lets it reach constants the raw-op search timed out on -- the
team escalating its OWN search to close its OWN gaps. Output is the emitter's slot form
(0=x, op t writes slot t+3), so se_emit_full emits it directly. license_tier: ORIGINAL
Refs: Bernstein "Multiplication by integer constants" 1986; Lefevre, INRIA RR-4192 2001;
addition-chain / shift-add literature. Op constants reuse SO_ADD/SO_SUB/SO_SHL.
dependencies 1 imports · 12 importers
diagram shows first 10 each side; +0 more imports, +2 more importers in the complete lists below.
imports: nx_superopt_opt.nx
imported by: nx_autoopt_library_test.nxnx_autorace_test.nxnx_builder.nxnx_cost_race_test.nxnx_horizontal_test.nxnx_layer_campaign.nxnx_levels_test.nxnx_mulchain_deep.nxnx_mulchain_deep_probe.nxnx_mulchain_test.nxnx_selfix.nxnx_team_tick.nx
structs
| none |
consts
| none |
functions
| 15 | func mc_abs(v: i64) -> i64 { if v < 0 { return 0 - v } return v } |
| 18 | func mc_avslot(k: i64) -> i64 { if k == 0 { return 0 } return k + 2 } |
| 21 | func mc_enum(op: *i64, a: *i64, b: *i64, t: i64, L: i64, sv: *i64, C: i64, bound: i64, maxsh: i64) -> i64 |
| 98 | func mulchain_find(C: i64, maxL: i64, op: *i64, a: *i64, b: *i64) -> i64 |
| 112 | func mc_eval(op: *i64, a: *i64, b: *i64, L: i64, x: i64) -> i64 |
| 133 | func mulchain_verified(c: i64, maxL: i64, op: *i64, a: *i64, b: *i64) -> i64 |