READMEMilky2018/milkir/egraph does not have a README file
#EClassId
#EGraph
type EGraphThe main E-graph data structure
#EGraph::add
Add an e-node to the e-graph, returning its e-class id.
If an equivalent node already exists, returns the existing class id.
Rewriting happens later, in saturate_indexed.
#EGraph::add_binop
#EGraph::add_bitrev
Add a bit reverse node
#EGraph::add_bmask
Add a boolean mask node: 0 -> 0, nonzero -> -1
#EGraph::add_bnot
Add a bitwise NOT node: ~x
#EGraph::add_bswap
Add a byte swap node
#EGraph::add_clz
Add a count leading zeros node
#EGraph::add_ctz
Add a count trailing zeros node
#EGraph::add_eq
Add an equality comparison node
#EGraph::add_fabs
Add a float absolute value node
#EGraph::add_fadd
Add a float add node
#EGraph::add_fceil
Add a float ceiling node
#EGraph::add_fcmp
Add a float compare node
#EGraph::add_fconst
Add a float constant node (bits stored as UInt64)
#EGraph::add_fcopysign
Add a float copysign node
#EGraph::add_fcvt_to_sint
Add a float to signed int conversion node
#EGraph::add_fcvt_to_uint
Add a float to unsigned int conversion node
#EGraph::add_fdemote
Add a float demote (f64 -> f32) node
#EGraph::add_fdiv
Add a float divide node
#EGraph::add_ffloor
Add a float floor node
#EGraph::add_fmax
Add a float max node
#EGraph::add_fmin
Add a float min node
#EGraph::add_fmul
Add a float multiply node
#EGraph::add_fnearest
Add a float round to nearest node
#EGraph::add_fneg
Add a float negate node
#EGraph::add_fpromote
Add a float promote (f32 -> f64) node
#EGraph::add_fsqrt
Add a float square root node
#EGraph::add_fsub
Add a float subtract node
#EGraph::add_ftrunc
Add a float truncate node
#EGraph::add_icmp
Add an integer compare node with condition code
#EGraph::add_ireduce
Add an integer reduce (truncate) node with type info
#EGraph::add_ne
Add a not-equal comparison node
#EGraph::add_neg
Add a negation node: -x
#EGraph::add_popcnt
Add a population count node
#EGraph::add_rotl
#EGraph::add_rotr
#EGraph::add_sdiv
#EGraph::add_select
Add a select node: select(cond, a, b) = cond ? a : b
#EGraph::add_sextend
Add a signed extend node with type info
#EGraph::add_sint_to_fcvt
Add a signed int to float conversion node
#EGraph::add_splat
Add a vector splat node (broadcast scalar to all lanes)
#EGraph::add_srem
#EGraph::add_sshr
#EGraph::add_typed
Add an e-node with type information
bits: the bit width of the value (8, 16, 32, 64, 128)
#EGraph::add_udiv
#EGraph::add_uextend
Add an unsigned extend node with type info
#EGraph::add_uint_to_fcvt
Add an unsigned int to float conversion node
#EGraph::add_urem
#EGraph::add_ushr
#EGraph::add_vconst
Add a vector constant node
#EGraph::best_nodes
Best node per class root, computed once for the whole e-graph.
Elaboration needs every class's chosen node, not one class's, so it pays
for the shared fixpoint once instead of re-running extraction per value.
Classes with no finite extraction (every node cyclic) are absent.
#EGraph::const_conflict_count
Number of constant-cache conflict observations so far (diagnostic).
A nonzero value means some rule merged classes carrying different
constants — an unsound union whose constant is deliberately not
harvested.
#EGraph::equiv
Check if two e-class ids are equivalent
#EGraph::extract
Extract the best (lowest cost) expression from an e-class
Returns the total cost and the best e-node
Costs are computed with a bottom-up fixpoint over the whole e-graph
(egg-style relaxation) rather than a memoized DFS: a DFS that prices
re-entered classes as infinite while an ancestor is on the stack can
memoize that context-dependent infinity and poison later queries that
reach the class through a cycle-free route. The fixpoint has no
evaluation context, so every class settles to its true best cost.
#EGraph::find
Find the canonical EClassId for a given id
#EGraph::get_bits
Get the type (bit width) for an equivalence class
Returns None if no type information is available
#EGraph::get_const
Get cached constant value for an e-class (O(1) lookup)
#EGraph::get_fconst
Get cached float constant value for an e-class (O(1) lookup)
#EGraph::get_nodes
Get all nodes in an e-class
#EGraph::last_eclass_size_limit_hits
Number of classes skipped/truncated due to eclass size limit in the most
recent saturate / saturate_indexed* invocation.
#EGraph::last_matches_limit_hits
Number of classes/rule streams truncated by the rewrite matches limit in the
most recent saturate / saturate_indexed* invocation.
#EGraph::last_rebuild_repairs
Number of classes repaired by the most recent rebuild (diagnostic).
#EGraph::last_rule_applications
Number of successful rewrite rule applications in the most recent
saturate / saturate_indexed invocation.
#EGraph::merge
Merge two e-classes, returning the canonical id of the merged class
#EGraph::merge_changed
Merge two e-classes, reporting whether they were distinct beforehand.
Rewrite rules use this to answer "did I make progress?" directly, rather
than inferring it from which id merge returned. Keeping progress
explicit lets the union-find choose roots freely.
#EGraph::rebuild
Restore e-graph invariants after unions.
Repair is driven by a worklist of classes whose contents changed, not by
a walk of the whole graph: when a union moves a class, only the nodes
that reference it hold a stale child id, and parents names exactly the
classes holding those nodes. Repairing a class can expose new congruences,
whose merges enqueue more work, so the loop runs until the worklist
drains.
#EGraph::saturate_indexed
Apply rules using opcode index for efficiency
#EGraph::saturate_indexed_with_limits
fn EGraph::saturate_indexed_with_limits(self : EGraph, ruleset : IndexedRuleSet, max_iterations : Int, limits : SaturationLimits) -> IntApply rules using opcode index for efficiency with explicit rewrite caps.
#EGraph::set_type
Set the type (bit width) for an equivalence class.
A conflicting assignment poisons the class: it reports no width from
then on, so width-dependent rules skip it rather than rewriting with
whichever width happened to be recorded first.
#EGraph::subsume
Subsume: replace node in class a with node from class b
Unlike merge, this doesn't add the original node to the equivalence class.
Used to avoid infinite loops in associativity/commutativity rules.
Returns the canonical id of the result (same as b).
#EGraph::subsume_changed
Subsume a into b, reporting whether they were distinct beforehand.
#ENode
E-node: an expression node in the e-graph
Children are EClassIds, not direct node references
#EOpcode
pub(all) enum EOpcode {
Const(Int64)
Fconst(UInt64)
Add
Sub
Mul
Sdiv
Udiv
Srem
Urem
And
Or
Xor
Shl
Sshr
Ushr
Rotl
Rotr
Neg
Bnot
Clz
Ctz
Popcnt
Bswap
Bitrev
Icmp(Int)
Eq
Ne
Select
Bmask
Smin
Smax
Umin
Umax
Iabs
SpaceshipS
SpaceshipU
Ireduce(Int, Int)
Uextend(Int, Int)
Sextend(Int, Int)
Fadd
Fsub
Fmul
Fdiv
Fmin
Fmax
Fcopysign
Fneg
Fabs
Fsqrt
Fceil
Ffloor
Ftrunc
Fnearest
Fcmp(Int)
Fpromote
Fdemote
FcvtToSint
FcvtToUint
SintToFcvt
UintToFcvt
Splat
Vconst(Bytes)
Var(Int)
} derive(Compare, Eq, Hash, Debug)#EOpcodeTag
E-opcode tag for indexing (ignores parameters like Const value)
#SaturationLimits
Saturation bounds (Cranelift-style):
- matches_limit: max successful rewrites to keep per class per pass
- eclass_enode_limit: max eclass node budget before skipping further rewrites
#SaturationLimits::SaturationLimits
fn SaturationLimits::SaturationLimits(matches_limit : Int, eclass_enode_limit : Int) -> SaturationLimits#SaturationLimits::cranelift_default
#SaturationLimits::eclass_enode_limit
#SaturationLimits::matches_limit
#get_compact_ruleset
Get a compact ruleset for large functions where compile-time predictability
matters more than chasing deep algebraic rewrites.
#get_global_ruleset
Get the global indexed ruleset (singleton pattern for performance)
#legality_sensitive_rules
Rules that require frontend- or target-provided definedness facts.
These are intentionally not part of get_global_ruleset because generic
MilkIR does not yet model whether division/remainder operations are total,
trapping, or poison-producing. A frontend adapter may use this collection
only after proving the required non-zero and overflow preconditions.
Source Files
- egraph.mbt
- egraph_build.mbt
- egraph_class_facts.mbt
- egraph_extract.mbt
- egraph_saturate.mbt
- enode.mbt
- rules_algebraic.mbt
- rules_all.mbt
- rules_bitwise.mbt
- rules_canon.mbt
- rules_const.mbt
- rules_extends.mbt
- rules_float.mbt
- rules_icmp.mbt
- rules_identity.mbt
- rules_rebalance.mbt
- rules_rebalance_addsub.mbt
- rules_select.mbt
- rules_shift.mbt
- rules_skeleton.mbt
- rules_spaceship.mbt
- rules_strength.mbt
- rules_vector.mbt
- union_find.mbt
Reusable Cranelift-like SSA intermediate representation
compilerirssaoptimization
0.6.2
Apache-2.0
Updated 2 days ago
154 downloads