‘equivalence’ Dialect

A dialect for representing e-graphs as MLIR operations.

The equivalence dialect represents e-graphs: equivalence.graph holds an unordered region of operations, and equivalence.class groups values that are known to be equivalent.

Operations

equivalence.class (equivalence::ClassOp)

An e-class representing a set of equivalent values

Syntax:

operation ::= `equivalence.class` $inputs (`leader` $leader^)? (` ` `(` `min_cost_index` `=` $min_cost_index^ `)` )? attr-dict `:` type($result)

An e-class operation representing a set of equivalent values. Optionally carries a leader operand for lazy union-find: when present, leader points to the canonical representative e-class.

Traits: AlwaysSpeculatableImplTrait, AttrSizedOperandSegments, SameOperandsAndResultType

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Attributes:

Attribute	MLIR Type	Description
min_cost_index	::mlir::IntegerAttr	64-bit signless integer attribute

Operands:

Operand	Description
inputs	variadic of any non-token type
leader	any non-token type

Results:

Result	Description
result	any non-token type

equivalence.graph (equivalence::GraphOp)

A graph region operation

Syntax:

operation ::= `equivalence.graph` ( `->` `(` type($outputs)^ `)` )? $body attr-dict

The equivalence.graph operation contains a single-block region in which equivalence classes and other operations are defined. Importantly, operations in the region are unordered, value uses can come before their definitions.

Traits: RecursivelySpeculatableImplTrait, SingleBlockImplicitTerminator<YieldOp>, SingleBlock

Interfaces: ConditionallySpeculatable, LoopLikeOpInterface, RegionKindInterface

Results:

Result	Description
outputs	variadic of any non-token type

equivalence.yield (equivalence::YieldOp)

Yield values from a graph region

Syntax:

operation ::= `equivalence.yield` attr-dict ($values^ `:` type($values))?

The equivalence.yield operation yields values from a equivalence.graph region. It serves as the terminator for the graph block.

Traits: AlwaysSpeculatableImplTrait, HasParent<GraphOp>, ReturnLike, Terminator

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface), RegionBranchTerminatorOpInterface

Effects: MemoryEffects::Effect{}

Operands:

Operand	Description
values	variadic of any non-token type

Attributes

CostAttr

An attribute representing the cost of an operation

Syntax:

#equivalence.cost<
  int64_t   # value
>

This attribute stores the cost of an operation for use in cost-based extraction algorithms. A value of -1 indicates no cost is available.

Parameters:

Parameter	C++ type	Description
value	int64_t

Passes

-equivalence-extract

Extracts selected nodes from equivalence classes.

After greedy selection has set min_cost_index on ClassOps, this pass extracts the selected operand from each e-class: replaces the ClassOp result with the chosen operand, erases the ClassOp and all non-selected candidate operations, and removes the cost attribute from the selected op. ClassOps with no uses are erased entirely along with their operand ops. ClassOps without a min_cost_index are left untouched.

Options

-remove-graphs : Remove the GraphOp wrapper if all e-classes have been extracted

-equivalence-graph-size

Prints the size of each equivalence graph in the module.

Walks each equivalence.graph in the module and prints the number of e-classes and e-nodes it contains. This is the same metric reported during equality saturation debug output.

-equivalence-insert-graph

Replaces a function body with a equivalence.graph operation.

-equivalence-restore-invariants

Restores the equivalence-class normal form to a fixpoint.

Applies the equivalence.class canonicalization patterns until no further rewrites apply, re-establishing the class normal form:

• a class result is never used as an operand of another class (nested classes are merged), and

• a class’s operands are used only by that class (external uses are rerouted through the class result).

• class operands are deduplicated

Unlike the general --canonicalize pass, this runs the greedy driver with no iteration or rewrite limit, so it reaches a genuine fixpoint. Folding and constant CSE are disabled: those optimizing rewrites (e.g. collapsing a single-element class to its operand) are not part of the normal form and would destroy e-graph structure that downstream consumers depend on.

-equivalence-select-constants

Selects constant operands in equivalence classes.

Walks each e-class (ClassOp) in the graph and inspects its operands. For classes that contain an operand produced by a constant operation, selects that operand. Classes that already carry a min_cost_index, or that contain no constant operand, are left untouched.

-equivalence-select-greedy

Performs greedy cost-based extraction for equivalence classes.

Implements greedy cost-based extraction for equivalence classes using bottom-up fixed-point iteration. For each e-class, finds the minimum cost node and sets the min_cost_index attribute on ClassOp operations.

Options

-cost-file      : Path to JSON file containing operation costs
-default-cost   : Default cost for operations not in cost file (-1 means none)
-attribute-name : Name of the attribute representing the local cost of operations

-equivalence-select-ilp

Selects e-nodes via an ILP formulation solved with HiGHS.

Selects one e-node per e-class by solving an integer linear program (ILP), then records the choice as a min_cost_index attribute on each ClassOp (the same form the greedy selector produces, so equivalence-extract consumes it unchanged).

The model is the exact acyclic-extraction ILP: a binary selection variable per e-node, a binary activation variable per e-class, level variables that forbid cyclic selections, and an objective that minimises the summed cost of the selected e-nodes (shared sub-terms counted once). Roots (the values yielded by the graph) are forced active. E-nodes carrying an equivalence.pruned marker, or whose cost is unresolvable, are excluded from consideration. When warm-starting is enabled the greedy heuristic supplies an initial feasible solution to seed the solver.

The ILP is solved with the HiGHS solver (https://highs.dev). This pass is only available when tamagoyaki is configured with -DTAMAGOYAKI_ENABLE_HIGHS=ON (the default). When HiGHS support is disabled at build time the pass is still registered but fails with a diagnostic when run.

Options

-default-cost   : Default local cost for e-nodes without a cost attribute (-1 means the e-node is unresolvable and is pruned)
-attribute-name : Name of the attribute holding the local cost of an operation
-warm-start     : Seed the solver with the greedy heuristic solution as a warm start