nx_eqsat.nx
buildroot/runtime/nx_eqsat.nx
about
nx_eqsat.nx -- equality-saturation framework (egg/SpEC family).
Foundation for the superoptimization arc per ZERO_TO_ADVANCED.md M2:
"the system is the FASTEST possible at every layer". Equality
saturation is the 2026-research-grade approach -- developed by
Willsey/Tate/Bornholt (egg, 2021) + Tate et al (Equality Saturation
for Compiler Optimization, 2009), proven on Souper/Cranelift et al
production compilers.
Why equality saturation vs traditional peephole:
Peephole: apply one rewrite, commit. If the rewrite was bad you
lose; if a better cascade existed but required first
un-doing a rewrite, you never find it. Phase-ordering
tyranny.
EqSat: keep ALL equivalent expressions in an e-graph. Apply
all rewrites breadth-first to saturation. Extract the
lowest-cost representative. Provably optimal under the
rule set + cost model.
For RV64IM: lets the compiler find non-obvious wins like
(add x x) -> (shl x 1) (when shl is faster)
(shl (shl x a) b) -> (shl x (add a b)) (kill dependent chain)
(mul x 2^k) -> (shl x k) (strength reduction)
(and x (not (and ~a y))) -> ... (DeMorgan reroute)
AND once silicon-feedback (rv64im_min_hot_report.nx) identifies hot
patterns, those become silicon-aware rewrites:
(popcount-naive-loop) -> (intrinsic popcount) when silicon has it
(gemm-inner-product) -> (vec mac fused) when SIMD lands
Status: SEED. 2026-05-26. V1: e-class union-find + rule registry +
bounded saturation loop + greedy extractor. ~50 baseline rewrites
for RV64IM; extends per silicon-feedback findings.
dependencies 3 imports · 10 importers
imports: nx_syscalls.nxnx_sketch_hash_map.nxnx_nxgate_sim.nx
imported by: nx_apex_gcc_bench.nxnx_eqsat_congruence_bench.nxnx_eqsat_congruence_test.nxnx_eqsat_constfold_bench.nxnx_eqsat_dsl_bench.nxnx_eqsat_membership_proof.nxnx_eqsat_race_bench.nxnx_eqsat_test.nxnx_eqsat_vs_gcc_battery_test.nxnx_superopt.nx
structs
| 90 | struct NxENode |
| 105 | struct NxEClass |
| 190 | struct NxDslRule |
| 215 | struct NxEGraph |
| 2102 | struct NxEmitNode |
consts
| 38 | const NX_MAGIC_1024: i64 = 1024 |
| 39 | const NX_MAGIC_1000000000: i64 = 1000000000 |
| 46 | const NX_EQ_OP_CONST: i64 = 0 // 0 children; payload = i64 value |
| 47 | const NX_EQ_OP_VAR: i64 = 1 // 0 children; payload = variable id |
| 48 | const NX_EQ_OP_ADD: i64 = 2 // 2 children |
| 49 | const NX_EQ_OP_SUB: i64 = 3 // 2 children |
| 50 | const NX_EQ_OP_MUL: i64 = 4 // 2 children |
| 51 | const NX_EQ_OP_DIV: i64 = 5 // 2 children |
| 52 | const NX_EQ_OP_REM: i64 = 6 // 2 children |
| 53 | const NX_EQ_OP_AND: i64 = 7 // 2 children |
| 54 | const NX_EQ_OP_OR: i64 = 8 // 2 children |
| 55 | const NX_EQ_OP_XOR: i64 = 9 // 2 children |
| 56 | const NX_EQ_OP_NOT: i64 = 10 // 1 child |
| 57 | const NX_EQ_OP_SHL: i64 = 11 // 2 children |
| 58 | const NX_EQ_OP_SHR: i64 = 12 // 2 children (logical) |
| 59 | const NX_EQ_OP_SAR: i64 = 13 // 2 children (arithmetic) |
| 60 | const NX_EQ_OP_NEG: i64 = 14 // 1 child |
| 61 | const NX_EQ_OP_EQ: i64 = 15 // 2 children |
| 62 | const NX_EQ_OP_LT: i64 = 16 // 2 children (signed) |
| 63 | const NX_EQ_OP_LTU: i64 = 17 // 2 children (unsigned) |
| 64 | const NX_EQ_OP_SELECT: i64 = 18 // 3 children (mux) |
| 65 | const NX_EQ_OP_POPCNT: i64 = 19 // 1 child (Zbb-equivalent) |
| 66 | const NX_EQ_OP_N: i64 = 20 |
| 133 | const NX_CF_NONE: i64 = 0 - 0x7FFFFFFFFFFFFFFF - 1 |
| 158 | const DSL_VAR:i64 = 0 |
| 159 | const DSL_CONST:i64 = 1 |
| 160 | const DSL_SAME_AS_A:i64 = 2 |
| 162 | const RHS_BIND_A:i64 = 0 |
| 163 | const RHS_BIND_B:i64 = 1 |
| 164 | const RHS_CONST:i64 = 2 |
| 165 | const RHS_SHL_A_BY_CONST:i64 = 3 |
| 166 | const RHS_SHL_A_BY_LOG2B:i64 = 4 |
| 172 | const RHS_SHL_A_BY_IADDED_J:i64 = 5 |
| 174 | const SC_NONE:i64 = 0 |
| 175 | const SC_POW2_B_KLTW:i64 = 1 |
| 182 | const SC_SHIFT_MERGE_IJW:i64 = 2 |
| 184 | const CNT_EVERY:i64 = 0 // count every match (the 6 V1 rules' behavior) |
| 185 | const CNT_REAL_MERGE:i64 = 1 // count only real find!=find merges (mul_pow2) |
| 309 | const NX_EQSAT_OK: i64 = 0 |
| 310 | const NX_EQSAT_BAD_OP: i64 = 1 |
| 311 | const NX_EQSAT_BAD_ARITY: i64 = 2 |
| 312 | const NX_EQSAT_OVERFLOW: i64 = 3 |
| 313 | const NX_EQSAT_SATURATED: i64 = 4 |
| 314 | const NX_EQSAT_STEP_BUDGET: i64 = 5 |
| 325 | const NX_EQSAT_RULE_NONE: i64 = 0 |
| 326 | const NX_EQSAT_RULE_ADD_ZERO: i64 = 1 |
| 327 | const NX_EQSAT_RULE_SUB_SELF: i64 = 2 |
| 328 | const NX_EQSAT_RULE_ADD_SELF: i64 = 3 |
| 329 | const NX_EQSAT_RULE_AND_SELF: i64 = 4 |
| 330 | const NX_EQSAT_RULE_OR_ZERO: i64 = 5 |
| 331 | const NX_EQSAT_RULE_MUL_ONE: i64 = 6 |
| 332 | const NX_EQSAT_RULE_MUL_POW2: i64 = 7 |
| 340 | const NX_EQSAT_RULE_CONGRUENCE: i64 = 8 |
| 347 | const NX_EQSAT_RULE_XOR_SELF: i64 = 9 |
| 361 | const NX_EQSAT_RULE_CONSTFOLD: i64 = 10 |
| 372 | const NX_EQSAT_RULE_SHIFT_MERGE: i64 = 11 |
| 373 | const NX_EQSAT_RULE_N: i64 = 12 |
| 1361 | const NX_EQSAT_W: i64 = 64 |
functions
| 68 | func nx_eqsat_op_is_valid(op: i64) -> i64 called by 1: nx_eqsat_add |
| 74 | func nx_eqsat_arity_for(op: i64) -> i64 |
| 377 | func nx_eqsat_init(g: *NxEGraph, |
| 437 | func nx_eqsat_enable_prov(g: *NxEGraph, buf: *i64, cap: i64) -> i64 |
| 451 | func nx_eqsat_log_rule(g: *NxEGraph, rule_id: i64) -> i64 called by 1: nx_eqsat_union_cited |
| 476 | func nx_eqsat_enable_meet(g: *NxEGraph, hc: *HashMap, |
| 518 | func nx_eqsat_enable_dsl(g: *NxEGraph, table: *NxDslRule, n: i64, cap: i64) -> i64 |
| 537 | func nx_eqsat_enable_constfold(g: *NxEGraph) -> i64 |
| 570 | func nx_cf_make_const_node(g: *NxEGraph, value: i64) -> i64 |
| 593 | func nx_cf_intern_const(g: *NxEGraph, value: i64) -> i64 |
| 631 | func nx_eqsat_builtin_dsl_table(table: *NxDslRule) -> i64 |
| 679 | func nx_eqsat_dsl_set_row(table: *NxDslRule, i: i64, rule_id: i64, lhs_op: i64, |
| 698 | func nx_eqsat_mix(h: i64) -> i64 |
| 707 | func nx_eqsat_fingerprint(op: i64, payload: i64, kc0: i64, kc1: i64, kc2: i64) -> i64 |
| 721 | func nx_eqsat_node_matches(g: *NxEGraph, nidx: i64, op: i64, payload: i64, |
| 737 | func nx_eqsat_add_parent(g: *NxEGraph, nidx: i64, child_cls: i64) -> i64 called by 1: nx_eqsat_add |
| 751 | func nx_eqsat_push_dirty(g: *NxEGraph, cls: i64) -> i64 called by 1: nx_eqsat_union_cited |
| 761 | func nx_eqsat_new_class(g: *NxEGraph, node_idx: i64, initial_cost: i64) -> i64 |
| 783 | func nx_eqsat_find(g: *NxEGraph, id: i64) -> i64 |
| 799 | func nx_eqsat_union_cited(g: *NxEGraph, a: i64, b: i64, rule_id: i64) -> i64 |
| 851 | func nx_eqsat_union(g: *NxEGraph, a: i64, b: i64) -> i64 |
| 867 | func nx_eqsat_op_cost(op: i64) -> i64 |
| 880 | func nx_eqsat_class_cost(g: *NxEGraph, class_id: i64) -> i64 |
| 918 | func nx_eqsat_op_to_gate_kind(op: i64) -> i64 |
| 938 | func nx_eqsat_class_const(g: *NxEGraph, cls: i64, out_v: *i64) -> i64 |
| 954 | func nx_eqsat_class_cf(g: *NxEGraph, cls: i64, out_v: *i64) -> i64 calls 1: nx_eqsat_find |
| 971 | func nx_eqsat_try_constfold(g: *NxEGraph, new_cls: i64, op: i64, |
| 1013 | func nx_eqsat_fold_value(g: *NxEGraph, op: i64, kc0: i64, kc1: i64, kc2: i64, out_v: *i64) -> i64 |
| 1031 | func nx_eqsat_add(g: *NxEGraph, op: i64, k0: i64, k1: i64, k2: i64, payload: i64) -> i64 |
| 1204 | func nx_eqsat_add_const(g: *NxEGraph, value: i64) -> i64 |
| 1207 | func nx_eqsat_add_var(g: *NxEGraph, var_id: i64) -> i64 |
| 1210 | func nx_eqsat_add_binary(g: *NxEGraph, op: i64, a: i64, b: i64) -> i64 |
| 1213 | func nx_eqsat_add_unary(g: *NxEGraph, op: i64, a: i64) -> i64 |
| 1224 | func nx_eqsat_apply_rule_add_zero(g: *NxEGraph) -> i64 |
| 1252 | func nx_eqsat_apply_rule_sub_self(g: *NxEGraph) -> i64 |
| 1271 | func nx_eqsat_apply_rule_add_self(g: *NxEGraph) -> i64 called by 1: nx_eqsat_saturate calls 4: nx_eqsat_findnx_eqsat_add_constnx_eqsat_add_binarynx_eqsat_union_cited |
| 1291 | func nx_eqsat_apply_rule_and_self(g: *NxEGraph) -> i64 |
| 1309 | func nx_eqsat_apply_rule_or_zero(g: *NxEGraph) -> i64 |
| 1337 | func nx_eqsat_apply_rule_mul_one(g: *NxEGraph) -> i64 |
| 1363 | func nx_eqsat_apply_rule_mul_pow2(g: *NxEGraph) -> i64 called by 1: nx_eqsat_saturate calls 4: nx_eqsat_findnx_eqsat_add_constnx_eqsat_add_binarynx_eqsat_union_cited |
| 1420 | func nx_eqsat_match_node_inline(g: *NxEGraph, nidx: i64) -> i64 called by 1: nx_eqsat_match_node calls 4: nx_eqsat_findnx_eqsat_union_citednx_eqsat_add_constnx_eqsat_add_binary |
| 1554 | func nx_eqsat_dsl_log2_pow2(c: i64) -> i64 |
| 1570 | func nx_eqsat_dsl_class_is_const(g: *NxEGraph, cls: i64, want: i64) -> i64 |
| 1582 | func nx_eqsat_dsl_const_val(g: *NxEGraph, cls: i64, out_v: *i64) -> i64 called by 1: nx_eqsat_dsl_shift_merge |
| 1605 | func nx_eqsat_dsl_shift_merge(g: *NxEGraph, table: *NxDslRule, ri: i64, |
| 1641 | func nx_eqsat_dsl_instantiate_rhs(g: *NxEGraph, table: *NxDslRule, ri: i64, bindA: i64, shamt: i64) -> i64 |
| 1662 | func nx_eqsat_apply_dsl_rule(g: *NxEGraph, table: *NxDslRule, ri: i64) -> i64 |
| 1748 | func nx_eqsat_apply_dsl_table(g: *NxEGraph) -> i64 |
| 1764 | func nx_eqsat_match_node_dsl(g: *NxEGraph, nidx: i64) -> i64 |
| 1833 | func nx_eqsat_match_node(g: *NxEGraph, nidx: i64) -> i64 |
| 1856 | func nx_eqsat_rebuild(g: *NxEGraph) -> i64 |
| 1923 | func nx_eqsat_saturate(g: *NxEGraph, max_iters: i64) -> i64 |
| 2017 | func nx_eqsat_extract_best_node(g: *NxEGraph, class_id: i64) -> i64 |
| 2036 | func nx_eqsat_recompute_best(g: *NxEGraph) -> i64 called by 11: _report_one_iter_one_iter_one_iter_parity_one_iter+5 calls 3: nx_eqsat_findnx_eqsat_arity_fornx_eqsat_op_cost |
| 2086 | func nx_eqsat_best_cost(g: *NxEGraph, class_id: i64) -> i64 |
| 2110 | func nx_eqsat_emit(g: *NxEGraph, class_id: i64, out: *NxEmitNode, cap: i64, count: *i64) -> i64 called by 7: _reportnx_eqsat_emitmain_reportopt_onemain+1 calls 3: nx_eqsat_findnx_eqsat_arity_fornx_eqsat_emit |