[mlir] Add a conversion pass between PDL and the PDL Interpreter Dialect

Authored by rriddle on Oct 26 2020, 5:23 PM.


[mlir] Add a conversion pass between PDL and the PDL Interpreter Dialect

The conversion between PDL and the interpreter is split into several different parts.

  • The Matcher:

The matching section of all incoming pdl.pattern operations is converted into a predicate tree and merged. Each pattern is first converted into an ordered list of predicates starting from the root operation. A predicate is composed of three distinct parts:

  • Position
    • A position refers to a specific location on the input DAG, i.e. an existing MLIR entity being matched. These can be attributes, operands, operations, results, and types. Each position also defines a relation to its parent. For example, the operand [0] -> 1 has a parent operation position [0] (the root).
  • Question
    • A question refers to a query on a specific positional value. For example, an operation name question checks the name of an operation position.
  • Answer
    • An answer is the expected result of a question. For example, when matching an operation with the name "foo.op". The question would be an operation name question, with an expected answer of "foo.op".

After the predicate lists have been created and ordered(based on occurrence of common predicates and other factors), they are formed into a tree of nodes that represent the branching flow of a pattern match. This structure allows for efficient construction and merging of the input patterns. There are currently only 4 simple nodes in the tree:

  • ExitNode: Represents the termination of a match
  • SuccessNode: Represents a successful match of a specific pattern
  • BoolNode/SwitchNode: Branch to a specific child node based on the expected answer to a predicate question.

Once the matcher tree has been generated, this tree is walked to generate the corresponding interpreter operations.

  • The Rewriter:

The rewriter portion of a pattern is generated in a very straightforward manor, similarly to lowerings in other dialects. Each PDL operation that may exist within a rewrite has a mapping into the interpreter dialect. The code for the rewriter is generated within a FuncOp, that is invoked by the interpreter on a successful pattern match. Referenced values defined in the matcher become inputs the generated rewriter function.

An example lowering is shown below:

// The following high level PDL pattern:
pdl.pattern : benefit(1) {
  %resultType = pdl.type
  %inputOperand = pdl.input
  %root, %results = pdl.operation "foo.op"(%inputOperand) -> %resultType
  pdl.rewrite %root {
    pdl.replace %root with (%inputOperand)

// is lowered to the following:
module {
  // The matcher function takes the root operation as an input.
  func @matcher(%arg0: !pdl.operation) {
    pdl_interp.check_operation_name of %arg0 is "foo.op" -> ^bb2, ^bb1
    pdl_interp.check_operand_count of %arg0 is 1 -> ^bb3, ^bb1
    pdl_interp.check_result_count of %arg0 is 1 -> ^bb4, ^bb1
    %0 = pdl_interp.get_operand 0 of %arg0
    pdl_interp.is_not_null %0 : !pdl.value -> ^bb5, ^bb1
    %1 = pdl_interp.get_result 0 of %arg0
    pdl_interp.is_not_null %1 : !pdl.value -> ^bb6, ^bb1
    // This operation corresponds to a successful pattern match.
    pdl_interp.record_match @rewriters::@rewriter(%0, %arg0 : !pdl.value, !pdl.operation) : benefit(1), loc([%arg0]), root("foo.op") -> ^bb1
  module @rewriters {
    // The inputs to the rewriter from the matcher are passed as arguments.
    func @rewriter(%arg0: !pdl.value, %arg1: !pdl.operation) {
      pdl_interp.replace %arg1 with(%arg0)

Differential Revision: https://reviews.llvm.org/D84580