code wiki / (root) / nx_eqsat_test.nx

nx_eqsat_test.nx

buildroot/runtime/nx_eqsat_test.nx

4997 B90 linesdepth 7pulls 9 transitivereach 0 importersview sourcekind gate/prooftopic eqsat
docsdependenciesstructsconstsfunctions

about

nx_eqsat_test.nx -- proof-of-life + correctness GATE for the equality- saturation engine (the GENERATOR organ of the Sovereign Invention Engine). Case 1 -- EXTRACTOR correctness. (add (mul x x) 0): add_zero unions it with (mul x x); the add-class stays canonical (shallow cost 1 < mul's 3) with best_node = the add node, so the V1 CACHED extractor returns (add (mul x x) 0) [cost 4] -- a wasted +0. The REAL bottom-up extractor (nx_eqsat_recompute_best) returns (mul x x) [cost 3]. Known: before_op=ADD(2), cached_op=ADD(2) [the bug], real_op=MUL(4), real_cost=3. Case 2 -- a REAL optimization WIN. (mul x 8): the strength-reduction rule (mul x 2^k)->(shl x k) fires, and the real extractor picks (shl x 3) [cost 1] over (mul x 8) [cost 3] -- a genuine 3->1 win. The idempotent rule lets saturation CONVERGE (NX_EQSAT_SATURATED). Known: red_op=SHL(11), red_cost=1. Full known answer (FAIL LOUD): "2 2 4 3 11 1 ".

dependencies 1 imports · 0 importers

nx_eqsat.nx nx_eqsat_test.nx

imports: nx_eqsat.nx

imported by: nobody (leaf or entry point)

call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown

main nx_eqsat_init nx_eqsat_add_var nx_eqsat_add nx_eqsat_op_is_valid nx_eqsat_arity_for nx_cf_intern_const nx_eqsat_add_const nx_eqsat_add ↻ nx_eqsat_mix nx_cf_make_const_node nx_eqsat_new_class nx_eqsat_find nx_eqsat_find ↻ nx_eqsat_fold_value nx_eqsat_op_to_gate_kind nx_gsim_kind_supported nx_eqsat_arity_for ↻ nx_eqsat_find ↻ nx_gsim_eval_cell nx_eqsat_op_cost nx_eqsat_new_class ↻ nx_eqsat_union_cited nx_eqsat_find ↻ nx_eqsat_log_rule nx_eqsat_push_dirty nx_eqsat_fingerprint nx_eqsat_mix ↻ nx_hmap_has nx_hmap_probe_find nx_hmap_hash nx_hmap_entry_at nx_hmap_get nx_hmap_probe_find ↻ nx_hmap_entry_at ↻ nx_eqsat_node_matches nx_eqsat_arity_for ↻ nx_eqsat_find ↻ nx_hmap_put nx_hmap_probe_insert

structs

none

consts

none

functions

21func _emit_num(v: i64) -> i64
called by 1: main
29func _nl() -> i64 { let z: *u8 = sys_mmap(2); z[0] = 10; sys_write(1, z, 1); return 0 }
called by 1: main
31func main() -> i64