‘ematch’ Dialect

A dialect for e-matching and equality saturation.

The ematch dialect provides operations used to express e-matching and equality saturation over the e-graphs built with the equivalence dialect.

Operations

ematch.are_equivalent (ematch::AreEquivalentOp)

Check whether two values are in the same equivalence class.

Syntax:

operation ::= `ematch.are_equivalent` $lhs `,` $rhs attr-dict `->` $trueDest `,` $falseDest

The ematch.are_equivalent operation checks whether two !pdl.values belong to the same e-class. Unlike pdl_interp.are_equal, it looks through the leader chain of nested graph scopes: two equivalence.class results are equivalent if they share the same canonical leader. Values that are not equivalence.class results are only equivalent to themselves. It behaves like a pdl_interp predicate: on success control branches to the true destination, otherwise to the false destination.

This operation is lowered to a pdl_interp.apply_constraint.

Example:

ematch.are_equivalent %a, %b -> ^success, ^failure

Traits: Terminator

Operands:

Operand	Description
lhs	PDL handle for an mlir::Value
rhs	PDL handle for an mlir::Value

Successors:

Successor	Description
trueDest	any successor
falseDest	any successor

ematch.dedup (ematch::DedupOp)

Deduplicate an operation against the hashcons.

Syntax:

operation ::= `ematch.dedup` $input_op attr-dict

Check if the operation already exists in the hashcons.

If so, remove the new one and return the existing one.

Interfaces: InferTypeOpInterface

Operands:

Operand	Description
input_op	PDL handle to an mlir::Operation *

Results:

Result	Description
result_op	PDL handle to an mlir::Operation *

ematch.equivalent (ematch::EquivalentOp)

Test that two values are in the same equivalence class.

Syntax:

operation ::= `ematch.equivalent` $lhs `,` $rhs attr-dict

The ematch.equivalent operation is the match dialect counterpart of ematch.are_equivalent: a test inside a match.matcher that succeeds if the two !pdl.values belong to the same e-class, and otherwise fails the enclosing scope like the other match tests (e.g. match.equal).

It is produced by ematchify and lowered to a match.apply_native_constraint by convert-ematch-to-match.

Example:

ematch.equivalent %a, %b

Operands:

Operand	Description
lhs	PDL handle for an mlir::Value
rhs	PDL handle for an mlir::Value

ematch.get_class_representative (ematch::GetClassRepresentativeOp)

Get one of the values in the equivalence class of a value.

Syntax:

operation ::= `ematch.get_class_representative` $value attr-dict

Get one of the values in the equivalence class of v.

Interfaces: InferTypeOpInterface

Operands:

Operand	Description
value	PDL handle for an mlir::Value

Results:

Result	Description
result	PDL handle for an mlir::Value

ematch.get_class_result (ematch::GetClassResultOp)

Get the equivalence.class result for the class of a value.

Syntax:

operation ::= `ematch.get_class_result` $value attr-dict

Get the equivalence.class result corresponding to the equivalence class of v.

Interfaces: InferTypeOpInterface

Operands:

Operand	Description
value	PDL handle for an mlir::Value

Results:

Result	Description
result	PDL handle for an mlir::Value

ematch.get_class_results (ematch::GetClassResultsOp)

Get equivalence.class results for a range of values.

Syntax:

operation ::= `ematch.get_class_results` $values attr-dict

Get the equivalence.class results corresponding to the equivalence classes of a range of values.

Interfaces: InferTypeOpInterface

Operands:

Operand	Description
values	range of PDL handle for an mlir::Value values

Results:

Result	Description
result	range of PDL handle for an mlir::Value values

ematch.get_class_vals (ematch::GetClassValsOp)

Get all values in the equivalence class of a value.

Syntax:

operation ::= `ematch.get_class_vals` $value attr-dict

Take a value and return all values in its equivalence class.

If the value is an equivalence.class result, return the operands of the class, otherwise return a range containing the value itself.

Interfaces: InferTypeOpInterface

Operands:

Operand	Description
value	PDL handle for an mlir::Value

Results:

Result	Description
result	range of PDL handle for an mlir::Value values

ematch.is_arg (ematch::IsArgOp)

Constrain a matched value to a specific block argument.

Syntax:

operation ::= `ematch.is_arg` $value `,` $index attr-dict `->` $trueDest `,` $falseDest

The ematch.is_arg operation constrains a !pdl.value captured during matching to be (equivalent to) the block argument at a given index of the function containing the e-graph. It behaves like a pdl_interp predicate: on success control branches to the true destination, otherwise to the false destination.

It is intended to be used inside pdl_interp matchers handed to the equivalence-graph-contains pass, so that a pattern’s operands can be pinned to concrete block arguments (fully grounding the pattern) instead of matching arbitrary values.

This operation is lowered to a pdl_interp.apply_constraint invoking a constraint registered by the equivalence-graph-contains pass.

Example:

// Require %v to be in the e-class of block argument 0.
ematch.is_arg %v, 0 -> ^success, ^failure

Traits: Terminator

Attributes:

Attribute	MLIR Type	Description
index	::mlir::IntegerAttr	32-bit signless integer attribute

Operands:

Operand	Description
value	PDL handle for an mlir::Value

Successors:

Successor	Description
trueDest	any successor
falseDest	any successor

ematch.union (ematch::UnionOp)

Merge values or operations into equivalence class(es).

Syntax:

operation ::= `ematch.union` $lhs `:` type($lhs) `,` $rhs `:` type($rhs) attr-dict

Merge two values, an operation and a value range, or two value ranges into equivalence class(es).

Supported operand type combinations:

• (value, value): merge two values

• (operation, range): merge operation results with values

• (range, range): merge two value ranges

Operands:

Operand	Description
lhs	PDL handle for an mlir::Value or PDL handle to an mlir::Operation * or range of PDL handle for an mlir::Value values
rhs	PDL handle for an mlir::Value or range of PDL handle for an mlir::Value values

Passes

-convert-ematch-to-match

Lower the ematch operations in match matchers and rewriters to native calls.

Lowers the ematch operations that ematchify puts in match.matcher and match.rewriter ops: ematch.equivalent becomes a match.apply_native_constraint named are_equivalent, and the others (get_class_*, union, dedup) become match.apply_native_rewrite ops with the same name. They lower further to the pdl_interp calls whose implementations ematch-saturate registers.

This runs after match-combine-matchers, which would otherwise keep the are_equivalent constraints behind every predicate that preceded them in their pattern.

-convert-ematch-to-pdl-interp

Convert ematch operations to pdl_interp apply_rewrite operations.

This pass converts operations in the ematch dialect into a pdl_interp.apply_rewrite operations. Note that this transformation also happens in ematch-saturate by default.

-ematch-apply-pdl-interp

Apply pdl_interp patterns to the IR module using the greedy pattern rewrite driver.

A debugging pass that applies pdl_interp patterns to the IR module using MLIR’s greedy pattern rewrite driver, similar to TestPDLByteCode in MLIR. pdl patterns are lowered to pdl_interp through the match dialect first (without e-matching): convert-pdl-to-match, match-combine-matchers, convert-match-to-pdl-interp.

-ematch-convert-pdl-to-pdl-interp

Lower PDL patterns to e-matching pdl_interp.

Lowers the pdl.pattern ops in the module to a pdl_interp matcher and rewriters that match and rewrite over e-classes, as consumed by ematch-saturate. This runs convert-pdl-to-match, ematchify, match-combine-matchers{defer-loops}, convert-ematch-to-match and convert-match-to-pdl-interp. Before the ematch operations are lowered, the e-class helpers are moved right before their first use, but not into a loop, so that they are not computed when an earlier check fails.

If the module has a @patterns submodule, that submodule is lowered instead.

-ematch-saturate

Run equality saturation on the program with the provided patterns.

This pass applies pattern rewriting to operations in the ematch dialect.

The patterns are either e-matching pdl_interp or pdl patterns. The latter are lowered with ematch-convert-pdl-to-pdl-interp first.

Options

-max-iters     : Maximum number of iterations before equality saturation times out.
-max-nodes     : Maximum number of nodes in the e-graph (0 = unlimited).
-patterns-file : Path to an MLIR file containing the patterns module. When set, the input module is treated as the IR module directly.
-eager-rewrite : When true, matching and rewriting are interleaved (eager). When false, all matches are collected first, then applied.

-ematch-saturate-benchmark

Run equality saturation N times for benchmarking/profiling.

This pass runs the ematch-saturate pass N times, cloning the IR module each time to ensure fresh input. Useful for profiling and benchmarking. Like ematch-saturate, it accepts pdl patterns too.

Options

-num-runs  : Number of times to run equality saturation.
-max-iters : Maximum number of iterations before equality saturation times out.
-max-nodes : Maximum number of nodes in the e-graph (0 = unlimited).

-ematchify

Make match-dialect patterns match and rewrite over e-classes.

Rewrites the match.matcher and match.rewriter ops produced by convert-pdl-to-match so that they operate on the e-classes of an e-graph instead of on concrete values and operations.

In the matchers, using the ematch operations:

• A matched result (match.get_result(s) unwrapped by match.is_not_null) is mapped to its e-class result with ematch.get_class_result(s).

• match.get_defining_op %v is tried for every member of the e-class of %v: it moves, together with the rest of its block, into a match.foreach over ematch.get_class_vals %v. The defining op of a value range is still taken from the range itself.

• match.equal on values becomes ematch.equivalent.

• A matched operand passed to match.success is replaced by its ematch.get_class_representative, and an e-class result by the value it was computed from.

In the rewriters:

• Value (range) arguments, pdl.result(s) of created ops are mapped to their e-class result(s) with ematch.get_class_result(s).

• Created operations, including operations returned by native rewrites, are deduplicated against the hash-cons with ematch.dedup.

• match.replace becomes an ematch.union of the replaced operation with its replacement values, and match.erase is dropped.

The pass expects one matcher per pattern, i.e. it runs before match-combine-matchers. That pass should run with defer-loops, so that the e-class loops end up nested under the checks that do not need them. Afterwards, convert-ematch-to-match lowers the ematch operations for convert-match-to-pdl-interp.

-equivalence-graph-contains

Report which patterns are contained in the e-graph rooted at the yielded value.

Given a pdl_interp patterns module (via the patterns-file option or nested @patterns/@ir submodules) and an input module containing equivalence.graph operations, this pass reports, for each pattern, whether it matches the e-graph with its root equivalent to a value returned by an equivalence.yield.

Rather than running equality saturation, the pass replaces every pdl_interp.record_match in the matcher with a custom pdl_interp.apply_constraint that records the match together with its operands. The matcher is then run once over the e-graph. Patterns may use ematch.is_arg to pin operands to concrete block arguments, fully grounding the query. For each pattern the pass prints whether some recorded match has its root in the e-class of a yielded value.

Like ematch-saturate, it accepts pdl patterns too (which cannot use ematch.is_arg).

Options

-patterns-file : Path to an MLIR file containing the pdl_interp patterns module. When set, the input module is treated as the IR module directly.