Fix GCC build problem with 288f05f related to SmallVector. (#116958)
[llvm-project.git] / mlir / docs / PDLL.md
blobee1b615a2dcdee4506731b74130ca177f8c133ec
1 # PDLL - PDL Language
3 This document details the PDL Language (PDLL), a custom frontend language for
4 writing pattern rewrites targeting MLIR.
6 Note: This document assumes a familiarity with MLIR concepts; more specifically
7 the concepts detailed within the
8 [MLIR Pattern Rewriting](PatternRewriter.md) and
9 [Operation Definition Specification (ODS)](DefiningDialects/Operations.md)
10 documentation.
12 [TOC]
14 ## Introduction
16 Pattern matching is an extremely important component within MLIR, as it
17 encompasses many different facets of the compiler. From canonicalization, to
18 optimization, to conversion; every MLIR based compiler will heavily rely on the
19 pattern matching infrastructure in some capacity.
21 The PDL Language (PDLL) provides a declarative pattern language designed from
22 the ground up for representing MLIR pattern rewrites. PDLL is designed to
23 natively support writing matchers on all of MLIRs constructs via an intuitive
24 interface that may be used for both ahead-of-time (AOT) and just-in-time (JIT)
25 pattern compilation.
27 ## Rationale
29 This section provides details on various design decisions, their rationale, and
30 alternatives considered when designing PDLL. Given the nature of software
31 development, this section may include references to areas of the MLIR compiler
32 that no longer exist.
34 ### Why build a new language instead of improving TableGen DRR?
36 Note: This section assumes familiarity with
37 [TDRR](DeclarativeRewrites.md), please refer the
38 relevant documentation before continuing.
40 Tablegen DRR (TDRR), i.e.
41 [Table-driven Declarative Rewrite Rules](DeclarativeRewrites.md),
42 is a declarative DSL for defining MLIR pattern rewrites within the
43 [TableGen](https://llvm.org/docs/TableGen/index.html) language. This
44 infrastructure is currently the main way in which patterns may be defined
45 declaratively within MLIR. TDRR utilizes TableGen's `dag` support to enable
46 defining MLIR patterns that fit nicely within a DAG structure; in a similar way
47 in which tablegen has been used to defined patterns for LLVM's backend
48 infrastructure (SelectionDAG/Global Isel/etc.). Unfortunately however, the
49 TableGen language is not as amenable to the structure of MLIR patterns as it has
50 been for LLVM.
52 The issues with TDRR largely stem from the use of TableGen as the host language
53 for the DSL. These issues have risen from a mismatch in the structure of
54 TableGen compared to the structure of MLIR, and from TableGen having different
55 motivational goals than MLIR. A majority (or all depending on how stubborn you
56 are) of the issues that we've come across with TDRR have been addressable in
57 some form; the sticking point here is that the solutions to these problems have
58 often been more "creative" than we'd like. This is a problem, and why we decided
59 not to invest a larger effort into improving TDRR; users generally don't want
60 "creative" APIs, they want something that is intuitive to read/write.
62 To highlight some of these issues, below we will take a tour through some of the
63 problems that have arisen, and how we "fixed" them.
65 #### Multi-result operations
67 MLIR natively supports a variable number of operation results. For the DAG based
68 structure of TDRR, any form of multiple results (operations in this instance)
69 creates a problem. This is because the DAG wants a single root node, and does
70 not have nice facilities for indexing or naming the multiple results. Let's take
71 a look at a quick example to see how this manifests:
73 ```tablegen
74 // Suppose we have a three result operation, defined as seen below.
75 def ThreeResultOp : Op<"three_result_op"> {
76     let arguments = (ins ...);
78     let results = (outs
79       AnyTensor:$output1,
80       AnyTensor:$output2,
81       AnyTensor:$output3
82     );
85 // To bind the results of `ThreeResultOp` in a TDRR pattern, we bind all results
86 // to a single name and use a special naming convention: `__N`, where `N` is the
87 // N-th result.
88 def : Pattern<(ThreeResultOp:$results ...),
89               [(... $results__0), ..., (... $results__2), ...]>;
90 ```
92 In TDRR, we "solved" the problem of accessing multiple results, but this isn't a
93 very intuitive interface for users. Magical naming conventions obfuscate the
94 code and can easily introduce bugs and other errors. There are various things
95 that we could try to improve this situation, but there is a fundamental limit to
96 what we can do given the limits of the TableGen dag structure. In PDLL, however,
97 we have the freedom and flexibility to provide a proper interface into
98 operations, regardless of their structure:
100 ```pdll
101 // Import our definition of `ThreeResultOp`.
102 #include "ops.td"
104 Pattern {
105   ...
107   // In PDLL, we can directly reference the results of an operation variable.
108   // This provides a closer mental model to what the user expects.
109   let threeResultOp = op<my_dialect.three_result_op>;
110   let userOp = op<my_dialect.user_op>(threeResultOp.output1, ..., threeResultOp.output3);
112   ...
116 #### Constraints
118 In TDRR, the match dag defines the general structure of the input IR to match.
119 Any non-structural/non-type constraints on the input are generally relegated to
120 a list of constraints specified after the rewrite dag. For very simple patterns
121 this may suffice, but with larger patterns it becomes quite problematic as it
122 separates the constraint from the entity it constrains and negatively impacts
123 the readability of the pattern. As an example, let's look at a simple pattern
124 that adds additional constraints to its inputs:
126 ```tablegen
127 // Suppose we have a two result operation, defined as seen below.
128 def TwoResultOp : Op<"two_result_op"> {
129     let arguments = (ins ...);
131     let results = (outs
132       AnyTensor:$output1,
133       AnyTensor:$output2
134     );
137 // A simple constraint to check if a value is use_empty.
138 def HasNoUseOf: Constraint<CPred<"$_self.use_empty()">, "has no use">;
140 // Check if two values have a ShapedType with the same element type.
141 def HasSameElementType : Constraint<
142     CPred<"$0.getType().cast<ShapedType>().getElementType() == "
143           "$1.getType().cast<ShapedType>().getElementType()">,
144     "values have same element type">;
146 def : Pattern<(TwoResultOp:$results $input),
147               [(...), (...)],
148               [(HasNoUseOf:$results__1),
149                (HasSameElementType $results__0, $input)]>;
152 Above, when observing the constraints we need to search through the input dag
153 for the inputs (also keeping in mind the magic naming convention for multiple
154 results). For this simple pattern it may be just a few lines above, but complex
155 patterns often grow to 10s of lines long. In PDLL, these constraints can be
156 applied directly on or next to the entities they apply to:
158 ```pdll
159 // The same constraints that we defined above:
160 Constraint HasNoUseOf(value: Value) [{
161   return success(value.use_empty());
163 Constraint HasSameElementType(value1: Value, value2: Value) [{
164   return success(value1.getType().cast<ShapedType>().getElementType() ==
165                  value2.getType().cast<ShapedType>().getElementType());
168 Pattern {
169   // In PDLL, we can apply the constraint as early (or as late) as we want. This
170   // enables better structuring of the matcher code, and improves the
171   // readability/maintainability of the pattern.
172   let op = op<my_dialect.two_result_op>(input: Value);
173   HasNoUseOf(op.output2);
174   HasSameElementType(input, op.output2);
176   // ...
180 #### Replacing Multiple Operations
182 Often times a pattern will transform N number of input operations into N number
183 of result operations. In PDLL, replacing multiple operations is as simple as
184 adding two [`replace` statements](#replace-statement). In TDRR, the situation is
185 a bit more nuanced. Given the single root structure of the TableGen dag,
186 replacing a non-root operation is not nicely supported. It currently isn't
187 natively possible, and instead requires using multiple patterns. We could
188 potentially add another special rewrite directive, or extend `replaceWithValue`,
189 but this simply highlights how even a basic IR transformation is muddled by the
190 complexity of the host language.
192 ### Why not build a DSL in "X"?
194 Yes! Well yes and no. To understand why, we have to consider what types of users
195 we are trying to serve and what constraints we enforce upon them. The goal of
196 PDLL is to provide a default and effective pattern language for MLIR that all
197 users of MLIR can interact with immediately, regardless of their host
198 environment. This language is available with no extra dependencies and comes
199 "free" along with MLIR. If we were to use an existing host language to build our
200 new DSL, we would need to make compromises along with it depending on the
201 language. For some, there are questions of how to enforce matching environments
202 (python2 or python3?, which version?), performance considerations, integration,
203 etc. As an LLVM project, this could also mean enforcing a new language
204 dependency on the users of MLIR (many of which may not want/need such a
205 dependency otherwise). Another issue that comes along with any DSL that is
206 embeded in another language: mitigating the user impedance mismatch between what
207 the user expects from the host language and what our "backend" supports. For
208 example, the PDL IR abstraction only contains limited support for control flow.
209 If we were to build a DSL in python, we would need to ensure that complex
210 control flow is either handled completely or effectively errors out. Even with
211 ideal error handling, not having the expected features available creates user
212 frustration. In addition to the environment constraints, there is also the issue
213 of language tooling. With PDLL we intend to build a very robust and modern
214 toolset that is designed to cater the needs of pattern developers, including
215 code completion, signature help, and many more features that are specific to the
216 problem we are solving. Integrating custom language tooling into existing
217 languages can be difficult, and in some cases impossible (as our DSL would
218 merely be a small subset of the existing language).
220 These various points have led us to the initial conclusion that the most
221 effective tool we can provide for our users is a custom tool designed for the
222 problem at hand. With all of that being said, we understand that not all users
223 have the same constraints that we have placed upon ourselves. We absolutely
224 encourage and support the existence of various PDL frontends defined in
225 different languages. This is one of the original motivating factors around
226 building the PDL IR abstraction in the first place; to enable innovation and
227 flexibility for our users (and in turn their users). For some, such as those in
228 research and the Machine Learning space, they may already have a certain
229 language (such as Python) heavily integrated into their workflow. For these
230 users, a PDL DSL in their language may be ideal and we will remain committed to
231 supporting and endorsing that from an infrastructure point-of-view.
233 ## Language Specification
235 Note: PDLL is still under active development, and the designs discussed below
236 are not necessarily final and may be subject to change.
238 The design of PDLL is heavily influenced and centered around the
239 [PDL IR abstraction](https://mlir.llvm.org/docs/Dialects/PDLOps/), which in turn
240 is designed as an abstract model of the core MLIR structures. This leads to a
241 design and structure that feels very similar to if you were directly writing the
242 IR you want to match.
244 ### Includes
246 PDLL supports an `include` directive to import content defined within other
247 source files. There are two types of files that may be included: `.pdll` and
248 `.td` files.
250 #### `.pdll` includes
252 When including a `.pdll` file, the contents of that file are copied directly into
253 the current file being processed. This means that any patterns, constraints,
254 rewrites, etc., defined within that file are processed along with those within
255 the current file.
257 #### `.td` includes
259 When including a `.td` file, PDLL will automatically import any pertinent
260 [ODS](DefiningDialects/Operations.md) information within that file.
261 This includes any defined operations, constraints, interfaces, and more, making
262 them implicitly accessible within PDLL. This is important, as ODS information
263 allows for certain PDLL constructs, such as the
264 [`operation` expression](#operation), to become much more powerful.
266 ### Patterns
268 In any pattern descriptor language, pattern definition is at the core. In PDLL,
269 patterns start with `Pattern` optionally followed by a name and a set of pattern
270 metadata, and finally terminated by a pattern body. A few simple examples are
271 shown below:
273 ```pdll
274 // Here we have defined an anonymous pattern:
275 Pattern {
276   // Pattern bodies are separated into two components:
277   // * Match Section
278   //    - Describes the input IR.
279   let root = op<toy.reshape>(op<toy.reshape>(arg: Value));
281   // * Rewrite Section
282   //    - Describes how to transform the IR.
283   //    - Last statement starts the rewrite.
284   replace root with op<toy.reshape>(arg);
287 // Here we have defined a pattern named `ReshapeReshapeOptPattern` with a
288 // benefit of 10:
289 Pattern ReshapeReshapeOptPattern with benefit(10) {
290   replace op<toy.reshape>(op<toy.reshape>(arg: Value))
291     with op<toy.reshape>(arg);
295 After the definition of the pattern metadata, we specify the pattern body. The
296 structure of a pattern body is comprised of two main sections, the `match`
297 section and the `rewrite` section. The `match` section of a pattern describes
298 the expected input IR, whereas the `rewrite` section describes how to transform
299 that IR. This distinction is an important one to make, as PDLL handles certain
300 variables and expressions differently within the different sections. When
301 relevant in each of the sections below, we shall explicitly call out any
302 behavioral differences.
304 The general layout of the `match` and `rewrite` section is as follows: the
305 *last* statement of the pattern body is required to be a
306 [`operation rewrite statement`](#operation-rewrite-statements), and denotes the
307 `rewrite` section; every statement before denotes the `match` section.
309 #### Pattern metadata
311 Rewrite patterns in MLIR have a set of metadata that allow for controlling
312 certain behaviors, and providing information to the rewrite driver applying the
313 pattern. In PDLL, a pattern can provide a non-default value for this metadata
314 after the pattern name. Below, examples are shown for the different types of
315 metadata supported:
317 ##### Benefit
319 The benefit of a Pattern is an integer value that represents the "benefit" of
320 matching that pattern. It is used by pattern drivers to determine the relative
321 priorities of patterns during application; a pattern with a higher benefit is
322 generally applied before one with a lower benefit.
324 In PDLL, a pattern has a default benefit set to the number of input operations,
325 i.e. the number of distinct `Op` expressions/variables, in the match section. This
326 rule is driven by an observation that larger matches are more beneficial than smaller
327 ones, and if a smaller one is applied first the larger one may not apply anymore.
328 Patterns can override this behavior by specifying the benefit in the metadata section
329 of the pattern:
331 ```pdll
332 // Here we specify that this pattern has a benefit of `10`, overriding the
333 // default behavior.
334 Pattern with benefit(10) {
335   ...
339 ##### Bounded Rewrite Recursion
341 During pattern application, there are situations in which a pattern may be
342 applicable to the result of a previous application of that same pattern. If the
343 pattern does not properly handle this recusive application, the pattern driver
344 could become stuck in an infinite loop of application. To prevent this, patterns
345 by-default are assumed to not have proper recursive bounding and will not be
346 recursively applied. A pattern can signal that it does have proper handling for
347 recursion by specifying the `recusion` flag in the pattern metadata section:
349 ```pdll
350 // Here we signal that this pattern properly bounds recursive application.
351 Pattern with recusion {
352   ...
356 #### Single Line "Lambda" Body
358 Patterns generally define their body using a compound block of statements, as
359 shown below:
361 ```pdll
362 Pattern {
363   replace op<my_dialect.foo>(operands: ValueRange) with operands;
367 Patterns also support a lambda-like syntax for specifying simple single line
368 bodies. The lambda body of a Pattern expects a single
369 [operation rewrite statement](#operation-rewrite-statements):
371 ```pdll
372 Pattern => replace op<my_dialect.foo>(operands: ValueRange) with operands;
375 ### Variables
377 Variables in PDLL represent specific instances of IR entities, such as `Value`s,
378 `Operation`s, `Type`s, etc. Consider the simple pattern below:
380 ```pdll
381 Pattern {
382   let value: Value;
383   let root = op<mydialect.foo>(value);
385   replace root with value;
389 In this pattern we define two variables, `value` and `root`, using the `let`
390 statement. The `let` statement allows for defining variables and constraining
391 them. Every variable in PDLL is of a certain type, which defines the type of IR
392 entity the variable represents. The type of a variable may be determined via
393 either a constraint, or an initializer expression.
395 #### Variable "Binding"
397 In addition to having a type, variables must also be "bound", either via an initializer
398 expression or to a non-native constraint or rewrite use within the `match` section of the
399 pattern. "Binding" a variable contextually identifies that variable within either the
400 input (i.e. `match` section) or output (i.e. `rewrite` section) IR. In the `match` section,
401 this allows for building the match tree from the pattern's root operation, which must be
402 "bound" to the [operation rewrite statement](#operation-rewrite-statements) that denotes the
403 `rewrite` section of the pattern. All non-root variables within the `match`
404 section must be bound in some way to the "root" operation. To help illustrate
405 the concept, let's take a look at a quick example. Consider the `.mlir` snippet
406 below:
408 ```mlir
409 func.func @baz(%arg: i32) {
410   %result = my_dialect.foo %arg, %arg -> i32
414 Say that we want to write a pattern that matches `my_dialect.foo` and replaces
415 it with its unique input argument. A naive way to write this pattern in PDLL is
416 shown below:
418 ```pdll
419 Pattern {
420   // ** match section ** //
421   let arg: Value;
422   let root = op<my_dialect.foo>(arg, arg);
424   // ** rewrite section ** //
425   replace root with arg;
429 In the above pattern, the `arg` variable is "bound" to the first and second operands
430 of the `root` operation. Every use of `arg` is constrained to be the same `Value`, i.e.
431 the first and second operands of `root` will be constrained to refer to the same input
432 Value. The same is true for the `root` operation, it is bound to the "root" operation of the
433 pattern as it is used in input of the top-level [`replace` statement](#replace-statement)
434 of the `rewrite` section of the pattern. Writing this pattern using the C++ API, the concept
435 of "binding" becomes more clear:
437 ```c++
438 struct Pattern : public OpRewritePattern<my_dialect::FooOp> {
439   LogicalResult matchAndRewrite(my_dialect::FooOp root, PatternRewriter &rewriter) {
440     Value arg = root->getOperand(0);
441     if (arg != root->getOperand(1))
442       return failure();
444     rewriter.replaceOp(root, arg);
445     return success();
446   }
450 If a variable is not "bound" properly, PDLL won't be able to identify what value
451 it would correspond to in the IR. As a final example, let's consider a variable
452 that hasn't been bound:
454 ```pdll
455 Pattern {
456   // ** match section ** //
457   let arg: Value;
458   let root = op<my_dialect.foo>
460   // ** rewrite section ** //
461   replace root with arg;
465 If we were to write this exact pattern in C++, we would end up with:
467 ```c++
468 struct Pattern : public OpRewritePattern<my_dialect::FooOp> {
469   LogicalResult matchAndRewrite(my_dialect::FooOp root, PatternRewriter &rewriter) {
470     // `arg` was never bound, so we don't know what input Value it was meant to
471     // correspond to.
472     Value arg;
474     rewriter.replaceOp(root, arg);
475     return success();
476   }
480 #### Variable Constraints
482 ```pdll
483 // This statement defines a variable `value` that is constrained to be a `Value`.
484 let value: Value;
486 // This statement defines a variable `value` that is constrained to be a `Value`
487 // *and* constrained to have a single use.
488 let value: [Value, HasOneUse];
491 Any number of single entity constraints may be attached directly to a variable
492 upon declaration. Within the `matcher` section, these constraints may add
493 additional checks on the input IR. Within the `rewriter` section, constraints
494 are *only* used to define the type of the variable. There are a number of
495 builtin constraints that correlate to the core MLIR constructs: `Attr`, `Op`,
496 `Type`, `TypeRange`, `Value`, `ValueRange`. Along with these, users may define
497 custom constraints that are implemented within PDLL, or natively (i.e. outside
498 of PDLL). See the general [Constraints](#constraints) section for more detailed
499 information.
501 #### Inline Variable Definition
503 Along with the `let` statement, variables may also be defined inline by
504 specifying the constraint list along with the desired variable name in the first
505 place that the variable would be used. After definition, the variable is visible
506 from all points forward. See below for an example:
508 ```pdll
509 // `value` is used as an operand to the operation `root`:
510 let value: Value;
511 let root = op<my_dialect.foo>(value);
512 replace root with value;
514 // `value` could also be defined "inline":
515 let root = op<my_dialect.foo>(value: Value);
516 replace root with value;
519 Note that the point of definition of an inline variable is the point of reference,
520 meaning that an inline variable can be used immediately in the same parent
521 expression within which it was defined:
523 ```pdll
524 let root = op<my_dialect.foo>(value: Value, _: Value, value);
525 replace root with value;
528 ##### Wildcard Variable Definition
530 Often times when defining a variable inline, the variable isn't intended to be
531 used anywhere else in the pattern. For example, this may happen if you want to
532 attach constraints to a variable but have no other use for it. In these
533 situations, the "wildcard" variable can be used to remove the need to provide a
534 name, as "wildcard" variables are not visible outside of the point of
535 definition. An example is shown below:
537 ```pdll
538 Pattern {
539   let root = op<my_dialect.foo>(arg: Value, _: Value, _: [Value, I64Value], arg);
540   replace root with arg;
544 In the above example, the second operand isn't needed for the pattern but we
545 need to provide it to signal that a second operand does exist (we just don't
546 care what it is in this pattern).
548 ### Operation Expression
550 An operation expression in PDLL represents an MLIR operation. In the `match`
551 section of the pattern, this expression models one of the input operations to
552 the pattern. In the `rewrite` section of the pattern, this expression models one
553 of the operations to create. The general structure of the operation expression
554 is very similar to that of the "generic form" of textual MLIR assembly:
556 ```pdll
557 let root = op<my_dialect.foo>(operands: ValueRange) {attr = attr: Attr} -> (resultTypes: TypeRange);
560 Let's walk through each of the different components of the expression:
562 #### Operation name
564 The operation name signifies which type of MLIR Op this operation corresponds
565 to. In the `match` section of the pattern, the name may be elided. This would
566 cause this pattern to match *any* operation type that satifies the rest of the
567 constraints of the operation. In the `rewrite` section, the name is required.
569 ```pdll
570 // `root` corresponds to an instance of a `my_dialect.foo` operation.
571 let root = op<my_dialect.foo>;
573 // `root` could be an instance of any operation type.
574 let root = op<>;
577 #### Operands
579 The operands section corresponds to the operands of the operation. This section
580 of an operation expression may be elided, which within a `match` section means
581 that the operands are not constrained in any way. If elided within a `rewrite`
582 section, the operation is treated as having no operands. When present, the
583 operands of an operation expression are interpreted in the following ways:
585 1) A single instance of type `ValueRange`:
587 In this case, the single range is treated as all of the operands of the
588 operation:
590 ```pdll
591 // Define an instance with single range of operands.
592 let root = op<my_dialect.foo>(allOperands: ValueRange);
595 2) A variadic number of either `Value` or `ValueRange`:
597 In this case, the inputs are expected to correspond with the operand groups as
598 defined on the operation in ODS.
600 Given the following operation definition in ODS:
602 ```tablegen
603 def MyIndirectCallOp {
604   let arguments = (ins FunctionType:$call, Variadic<AnyType>:$args);
608 We can match the operands as so:
610 ```pdll
611 let root = op<my_dialect.indirect_call>(call: Value, args: ValueRange);
614 #### Results
616 The results section corresponds to the result types of the operation. This section
617 of an operation expression may be elided, which within a `match` section means
618 that the result types are not constrained in any way. If elided within a `rewrite`
619 section, the results of the operation are [inferred](#inferred-results). When present,
620 the result types of an operation expression are interpreted in the following ways:
622 1) A single instance of type `TypeRange`:
624 In this case, the single range is treated as all of the result types of the
625 operation:
627 ```pdll
628 // Define an instance with single range of types.
629 let root = op<my_dialect.foo> -> (allResultTypes: TypeRange);
632 2) A variadic number of either `Type` or `TypeRange`:
634 In this case, the inputs are expected to correspond with the result groups as
635 defined on the operation in ODS.
637 Given the following operation definition in ODS:
639 ```tablegen
640 def MyOp {
641   let results = (outs SomeType:$result, Variadic<SomeType>:$otherResults);
645 We can match the result types as so:
647 ```pdll
648 let root = op<my_dialect.op> -> (result: Type, otherResults: TypeRange);
651 #### Inferred Results
653 Within the `rewrite` section of a pattern, the result types of an
654 operation are inferred if they are elided or otherwise not
655 previously bound. The ["variable binding"](#variable-binding) section above
656 discusses the concept of "binding" in more detail. Below are various examples
657 that build upon this to help showcase how a result type may be "bound":
659 * Binding to a [constant](#type-expression):
661 ```pdll
662 op<my_dialect.op> -> (type<"i32">);
665 * Binding to types within the `match` section:
667 ```pdll
668 Pattern {
669   replace op<dialect.inputOp> -> (resultTypes: TypeRange)
670     with op<dialect.outputOp> -> (resultTypes);
674 * Binding to previously inferred types:
676 ```pdll
677 Pattern {
678   rewrite root: Op with {
679     // `resultTypes` here is *not* yet bound, and will be inferred when
680     // creating `dialect.op`. Any uses of `resultTypes` after this expression,
681     // will use the types inferred when creating this operation.
682     op<dialect.op> -> (resultTypes: TypeRange);
684     // `resultTypes` here is bound to the types inferred when creating `dialect.op`.
685     op<dialect.bar> -> (resultTypes);
686   };
690 * Binding to a [`Native Rewrite`](#native-rewriters) method result:
692 ```pdll
693 Rewrite BuildTypes() -> TypeRange;
695 Pattern {
696   rewrite root: Op with {
697     op<dialect.op> -> (BuildTypes());
698   };
702 Below are the set of contexts in which result type inferrence is supported:
704 ##### Inferred Results of Replacement Operation
706 Replacements have the invariant that the types of the replacement values must
707 match the result types of the input operation. This means that when replacing
708 one operation with another, the result types of the replacement operation may
709 be inferred from the result types of the operation being replaced. For example,
710 consider the following pattern:
712 ```pdll
713 Pattern => replace op<dialect.inputOp> with op<dialect.outputOp>;
716 This pattern could be written in a more explicit way as:
718 ```pdll
719 Pattern {
720   replace op<dialect.inputOp> -> (resultTypes: TypeRange)
721     with op<dialect.outputOp> -> (resultTypes);
725 ##### Inferred Results with InferTypeOpInterface
727 `InferTypeOpInterface` is an interface that enables operations to infer its result
728 types from its input attributes, operands, regions, etc. When the result types of
729 an operation cannot be inferred from any other context, this interface is invoked
730 to infer the result types of the operation.
732 #### Attributes
734 The attributes section of the operation expression corresponds to the attribute
735 dictionary of the operation. This section of an operation expression may be
736 elided, in which case the attributes are not constrained in any way. The
737 composition of this component maps exactly to how attribute dictionaries are
738 structured in the MLIR textual assembly format:
740 ```pdll
741 let root = op<my_dialect.foo> {attr1 = attrValue: Attr, attr2 = attrValue2: Attr};
744 Within the `{}` attribute entries are specified by an identifier or string name,
745 corresponding to the attribute name, followed by an assignment to the attribute
746 value. If the attribute value is elided, the value of the attribute is
747 implicitly defined as a
748 [`UnitAttr`](https://mlir.llvm.org/docs/Dialects/Builtin/#unitattr).
750 ```pdll
751 let unitConstant = op<my_dialect.constant> {value};
754 ##### Accessing Operation Results
756 In multi-operation patterns, the result of one operation often feeds as an input
757 into another. The result groups of an operation may be accessed by name or by
758 index via the `.` operator:
760 Note: Remember to import the definition of your operation via
761 [include](#`.td`_includes) to ensure it is visible to PDLL.
763 Given the following operation definition in ODS:
765 ```tablegen
766 def MyResultOp {
767   let results = (outs SomeType:$result);
769 def MyInputOp {
770   let arguments = (ins SomeType:$input, SomeType:$input);
774 We can write a pattern where `MyResultOp` feeds into `MyInputOp` as so:
776 ```pdll
777 // In this example, we use both `result`(the name) and `0`(the index) to refer to
778 // the first result group of `resultOp`.
779 // Note: If we elide the result types section within the match section, it means
780 //       they aren't constrained, not that the operation has no results.
781 let resultOp = op<my_dialect.result_op>;
782 let inputOp = op<my_dialect.input_op>(resultOp.result, resultOp.0);
785 Along with result name access, variables of `Op` type may implicitly convert to
786 `Value` or `ValueRange`. If these variables are registered (has ODS entry), they
787 are converted to `Value` when they are known to only have one result, otherwise
788 they will be converted to `ValueRange`:
790 ```pdll
791 // `resultOp` may also convert implicitly to a Value for use in `inputOp`:
792 let resultOp = op<my_dialect.result_op>;
793 let inputOp = op<my_dialect.input_op>(resultOp);
795 // We could also inline `resultOp` directly:
796 let inputOp = op<my_dialect.input_op>(op<my_dialect.result_op>);
799 #### Unregistered Operations
801 A variable of unregistered op is still available for numeric result indexing.
802 Given that we don't have knowledge of its result groups, numeric indexing
803 returns a Value corresponding to the individual result at the given index.
805 ```pdll
806 // Use the index `0` to refer to the first result value of the unregistered op.
807 let inputOp = op<my_dialect.input_op>(op<my_dialect.unregistered_op>.0);
810 ### Attribute Expression
812 An attribute expression represents a literal MLIR attribute. It allows for
813 statically specifying an MLIR attribute to use, by specifying the textual form
814 of that attribute.
816 ```pdll
817 let trueConstant = op<arith.constant> {value = attr<"true">};
819 let applyResult = op<affine.apply>(args: ValueRange) {map = attr<"affine_map<(d0, d1) -> (d1 - 3)>">}
822 ### Type Expression
824 A type expression represents a literal MLIR type. It allows for statically
825 specifying an MLIR type to use, by specifying the textual form of that type.
827 ```pdll
828 let i32Constant = op<arith.constant> -> (type<"i32">);
831 ### Tuples
833 PDLL provides native support for tuples, which are used to group multiple
834 elements into a single compound value. The values in a tuple can be of any type,
835 and do not need to be of the same type. There is also no limit to the number of
836 elements held by a tuple. The elements of a tuple can be accessed by index:
838 ```pdll
839 let tupleValue = (op<my_dialect.foo>, attr<"10 : i32">, type<"i32">);
841 let opValue = tupleValue.0;
842 let attrValue = tupleValue.1;
843 let typeValue = tupleValue.2;
846 You can also name the elements of a tuple and use those names to refer to the
847 values of the individual elements. An element name consists of an identifier
848 followed immediately by an equal (=).
850 ```pdll
851 let tupleValue = (
852   opValue = op<my_dialect.foo>,
853   attr<"10 : i32">,
854   typeValue = type<"i32">
857 let opValue = tupleValue.opValue;
858 let attrValue = tupleValue.1;
859 let typeValue = tupleValue.typeValue;
862 Tuples are used to represent multiple results from a
863 [constraint](#constraints-with-multiple-results) or
864 [rewrite](#rewrites-with-multiple-results).
866 ### Constraints
868 Constraints provide the ability to inject additional checks on the input IR
869 within the `match` section of a pattern. Constraints can be applied anywhere
870 within the `match` section, and depending on the type can either be applied via
871 the constraint list of a [variable](#variables) or via the call operator (e.g.
872 `MyConstraint(...)`). There are three main categories of constraints:
874 #### Core Constraints
876 PDLL defines a number of core constraints that constrain the type of the IR
877 entity. These constraints can only be applied via the
878 [constraint list](#variable-constraints) of a variable.
880 *   `Attr` (`<` type `>`)?
882 A single entity constraint that corresponds to an `mlir::Attribute`. This
883 constraint optionally takes a type component that constrains the result type of
884 the attribute.
886 ```pdll
887 // Define a simple variable using the `Attr` constraint.
888 let attr: Attr;
889 let constant = op<arith.constant> {value = attr};
891 // Define a simple variable using the `Attr` constraint, that has its type
892 // constrained as well.
893 let attrType: Type;
894 let attr: Attr<attrType>;
895 let constant = op<arith.constant> {value = attr};
898 *   `Op` (`<` op-name `>`)?
900 A single entity constraint that corresponds to an `mlir::Operation *`.
902 ```pdll
903 // Match only when the input is from another operation.
904 let inputOp: Op;
905 let root = op<my_dialect.foo>(inputOp);
907 // Match only when the input is from another `my_dialect.foo` operation.
908 let inputOp: Op<my_dialect.foo>;
909 let root = op<my_dialect.foo>(inputOp);
912 *   `Type`
914 A single entity constraint that corresponds to an `mlir::Type`.
916 ```pdll
917 // Define a simple variable using the `Type` constraint.
918 let resultType: Type;
919 let root = op<my_dialect.foo> -> (resultType);
922 *   `TypeRange`
924 A single entity constraint that corresponds to a `mlir::TypeRange`.
926 ```pdll
927 // Define a simple variable using the `TypeRange` constraint.
928 let resultTypes: TypeRange;
929 let root = op<my_dialect.foo> -> (resultTypes);
932 *   `Value` (`<` type-expr `>`)?
934 A single entity constraint that corresponds to an `mlir::Value`. This constraint
935 optionally takes a type component that constrains the result type of the value.
937 ```pdll
938 // Define a simple variable using the `Value` constraint.
939 let value: Value;
940 let root = op<my_dialect.foo>(value);
942 // Define a variable using the `Value` constraint, that has its type constrained
943 // to be same as the result type of the `root` op.
944 let valueType: Type;
945 let input: Value<valueType>;
946 let root = op<my_dialect.foo>(input) -> (valueType);
949 *   `ValueRange` (`<` type-expr `>`)?
951 A single entity constraint that corresponds to a `mlir::ValueRange`. This
952 constraint optionally takes a type component that constrains the result types of
953 the value range.
955 ```pdll
956 // Define a simple variable using the `ValueRange` constraint.
957 let inputs: ValueRange;
958 let root = op<my_dialect.foo>(inputs);
960 // Define a variable using the `ValueRange` constraint, that has its types
961 // constrained to be same as the result types of the `root` op.
962 let valueTypes: TypeRange;
963 let inputs: ValueRange<valueTypes>;
964 let root = op<my_dialect.foo>(inputs) -> (valueTypes);
967 #### Defining Constraints in PDLL
969 Aside from the core constraints, additional constraints can also be defined
970 within PDLL. This allows for building matcher fragments that can be composed
971 across many different patterns. A constraint in PDLL is defined similarly to a
972 function in traditional programming languages; it contains a name, a set of
973 input arguments, a set of result types, and a body. Results of a constraint are
974 returned via a `return` statement. A few examples are shown below:
976 ```pdll
977 /// A constraint that takes an input and constrains the use to an operation of
978 /// a given type.
979 Constraint UsedByFooOp(value: Value) {
980   op<my_dialect.foo>(value);
983 /// A constraint that returns a result of an existing operation.
984 Constraint ExtractResult(op: Op<my_dialect.foo>) -> Value {
985   return op.result;
988 Pattern {
989   let value = ExtractResult(op<my_dialect.foo>);
990   UsedByFooOp(value);
994 ##### Constraints with multiple results
996 Constraints can return multiple results by returning a tuple of values. When
997 returning multiple results, each result can also be assigned a name to use when
998 indexing that tuple element. Tuple elements can be referenced by their index
999 number, or by name if they were assigned one.
1001 ```pdll
1002 // A constraint that returns multiple results, with some of the results assigned
1003 // a more readable name.
1004 Constraint ExtractMultipleResults(op: Op<my_dialect.foo>) -> (Value, result1: Value) {
1005   return (op.result1, op.result2);
1008 Pattern {
1009   // Return a tuple of values.
1010   let result = ExtractMultipleResults(op: op<my_dialect.foo>);
1012   // Index the tuple elements by index, or by name.
1013   replace op<my_dialect.foo> with (result.0, result.1, result.result1);
1017 ##### Constraint result type inference
1019 In addition to explicitly specifying the results of the constraint via the
1020 constraint signature, PDLL defined constraints also support inferring the result
1021 type from the return statement. Result type inference is active whenever the
1022 constraint is defined with no result constraints:
1024 ```pdll
1025 // This constraint returns a derived operation.
1026 Constraint ReturnSelf(op: Op<my_dialect.foo>) {
1027   return op;
1029 // This constraint returns a tuple of two Values.
1030 Constraint ExtractMultipleResults(op: Op<my_dialect.foo>) {
1031   return (result1 = op.result1, result2 = op.result2);
1034 Pattern {
1035   let values = ExtractMultipleResults(op<my_dialect.foo>);
1036   replace op<my_dialect.foo> with (values.result1, values.result2);
1040 ##### Single Line "Lambda" Body
1042 Constraints generally define their body using a compound block of statements, as
1043 shown below:
1045 ```pdll
1046 Constraint ReturnSelf(op: Op<my_dialect.foo>) {
1047   return op;
1049 Constraint ExtractMultipleResults(op: Op<my_dialect.foo>) {
1050   return (result1 = op.result1, result2 = op.result2);
1054 Constraints also support a lambda-like syntax for specifying simple single line
1055 bodies. The lambda body of a Constraint expects a single expression, which is
1056 implicitly returned:
1058 ```pdll
1059 Constraint ReturnSelf(op: Op<my_dialect.foo>) => op;
1061 Constraint ExtractMultipleResults(op: Op<my_dialect.foo>)
1062   => (result1 = op.result1, result2 = op.result2);
1065 #### Native Constraints
1067 Constraints may also be defined outside of PDLL, and registered natively within
1068 the C++ API.
1070 ##### Importing existing Native Constraints
1072 Constraints defined externally can be imported into PDLL by specifying a
1073 constraint "declaration". This is similar to the PDLL form of defining a
1074 constraint but omits the body. Importing the declaration in this form allows for
1075 PDLL to statically know the expected input and output types.
1077 ```pdll
1078 // Import a single entity value native constraint that checks if the value has a
1079 // single use. This constraint must be registered by the consumer of the
1080 // compiled PDL.
1081 Constraint HasOneUse(value: Value);
1083 // Import a multi-entity type constraint that checks if two values have the same
1084 // element type.
1085 Constraint HasSameElementType(value1: Value, value2: Value);
1087 Pattern {
1088   // A single entity constraint can be applied via the variable argument list.
1089   let value: HasOneUse;
1091   // Otherwise, constraints can be applied via the call operator:
1092   let value: Value = ...;
1093   let value2: Value = ...;
1094   HasOneUse(value);
1095   HasSameElementType(value, value2);
1099 External constraints are those registered explicitly with the `RewritePatternSet` via
1100 the C++ PDL API. For example, the constraints above may be registered as:
1102 ```c++
1103 static LogicalResult hasOneUseImpl(PatternRewriter &rewriter, Value value) {
1104   return success(value.hasOneUse());
1106 static LogicalResult hasSameElementTypeImpl(PatternRewriter &rewriter,
1107                                             Value value1, Value Value2) {
1108   return success(value1.getType().cast<ShapedType>().getElementType() ==
1109                  value2.getType().cast<ShapedType>().getElementType());
1112 void registerNativeConstraints(RewritePatternSet &patterns) {
1113     patternList.getPDLPatterns().registerConstraintFunction(
1114         "HasOneUse", hasOneUseImpl);
1115     patternList.getPDLPatterns().registerConstraintFunction(
1116         "HasSameElementType", hasSameElementTypeImpl);
1120 ##### Defining Native Constraints in PDLL
1122 In addition to importing native constraints, PDLL also supports defining native
1123 constraints directly when compiling ahead-of-time (AOT) for C++. These
1124 constraints can be defined by specifying a string code block after the
1125 constraint declaration:
1127 ```pdll
1128 Constraint HasOneUse(value: Value) [{
1129   return success(value.hasOneUse());
1131 Constraint HasSameElementType(value1: Value, value2: Value) [{
1132   return success(value1.getType().cast<ShapedType>().getElementType() ==
1133                  value2.getType().cast<ShapedType>().getElementType());
1136 Pattern {
1137   // A single entity constraint can be applied via the variable argument list.
1138   let value: HasOneUse;
1140   // Otherwise, constraints can be applied via the call operator:
1141   let value: Value = ...;
1142   let value2: Value = ...;
1143   HasOneUse(value);
1144   HasSameElementType(value, value2);
1148 The arguments of the constraint are accessible within the code block via the
1149 same name. See the ["type translation"](#native-constraint-type-translations) below for
1150 detailed information on how PDLL types are converted to native types. In addition to the
1151 PDLL arguments, the code block may also access the current `PatternRewriter` using
1152 `rewriter`. The result type of the native constraint function is implicitly defined
1153 as a `::llvm::LogicalResult`.
1155 Taking the constraints defined above as an example, these function would roughly be
1156 translated into:
1158 ```c++
1159 LogicalResult HasOneUse(PatternRewriter &rewriter, Value value) {
1160   return success(value.hasOneUse());
1162 LogicalResult HasSameElementType(Value value1, Value value2) {
1163   return success(value1.getType().cast<ShapedType>().getElementType() ==
1164                  value2.getType().cast<ShapedType>().getElementType());
1168 TODO: Native constraints should also be allowed to return values in certain cases.
1170 ###### Native Constraint Type Translations
1172 The types of argument and result variables are generally mapped to the corresponding
1173 MLIR type of the [constraint](#constraints) used. Below is a detailed description
1174 of how the mapped type of a variable is determined for the various different types of
1175 constraints.
1177 * Attr, Op, Type, TypeRange, Value, ValueRange:
1179 These are all core constraints, and are mapped directly to the MLIR equivalent
1180 (that their names suggest), namely:
1182   * `Attr`       -> "::mlir::Attribute"
1183   * `Op`         -> "::mlir::Operation *"
1184   * `Type`       -> "::mlir::Type"
1185   * `TypeRange`  -> "::mlir::TypeRange"
1186   * `Value`      -> "::mlir::Value"
1187   * `ValueRange` -> "::mlir::ValueRange"
1189 * Op<dialect.name>
1191 A named operation constraint has a unique translation. If the ODS registration of the
1192 referenced operation has been included, the qualified C++ is used. If the ODS information
1193 is not available, this constraint maps to "::mlir::Operation *", similarly to the unnamed
1194 variant. For example, given the following:
1196 ```pdll
1197 // `my_ops.td` provides the ODS definition of the `my_dialect` operations, such as
1198 // `my_dialect.bar` used below.
1199 #include "my_ops.td"
1201 Constraint Cst(op: Op<my_dialect.bar>) [{
1202   return success(op ... );
1206 The native type used for `op` may be of the form `my_dialect::BarOp`, as opposed to the
1207 default `::mlir::Operation *`. Below is a sample translation of the above constraint:
1209 ```c++
1210 LogicalResult Cst(my_dialect::BarOp op) {
1211   return success(op ... );
1215 * Imported ODS Constraints
1217 Aside from the core constraints, certain constraints imported from ODS may use a unique
1218 native type. How to enable this unique type depends on the ODS constraint construct that
1219 was imported:
1221   * `Attr` constraints
1222     - Imported `Attr` constraints utilize the `storageType` field for native type translation.
1224   * `Type` constraints
1225     - Imported `Type` constraints utilize the `cppClassName` field for native type translation.
1227   * `AttrInterface`/`OpInterface`/`TypeInterface` constraints
1228     - Imported interfaces utilize the `cppInterfaceName` field for native type translation.
1230 #### Defining Constraints Inline
1232 In addition to global scope, PDLL Constraints and Native Constraints defined in
1233 PDLL may be specified *inline* at any level of nesting. This means that they may
1234 be defined in Patterns, other Constraints, Rewrites, etc:
1236 ```pdll
1237 Constraint GlobalConstraint() {
1238   Constraint LocalConstraint(value: Value) {
1239     ...
1240   };
1241   Constraint LocalNativeConstraint(value: Value) [{
1242     ...
1243   }];
1244   let someValue: [LocalConstraint, LocalNativeConstraint] = ...;
1248 Constraints that are defined inline may also elide the name when used directly:
1250 ```pdll
1251 Constraint GlobalConstraint(inputValue: Value) {
1252   Constraint(value: Value) { ... }(inputValue);
1253   Constraint(value: Value) [{ ... }](inputValue);
1257 When defined inline, PDLL constraints may reference any previously defined
1258 variable:
1260 ```pdll
1261 Constraint GlobalConstraint(op: Op<my_dialect.foo>) {
1262   Constraint LocalConstraint() {
1263     let results = op.results;
1264   };
1268 ### Rewriters
1270 Rewriters define the set of transformations to be performed within the `rewrite`
1271 section of a pattern, and, more specifically, how to transform the input IR
1272 after a successful pattern match. All PDLL rewrites must be defined within the
1273 `rewrite` section of the pattern. The `rewrite` section is denoted by the last
1274 statement within the body of the `Pattern`, which is required to be an
1275 [operation rewrite statement](#operation-rewrite-statements). There are two main
1276 categories of rewrites in PDLL: operation rewrite statements, and user defined
1277 rewrites.
1279 #### Operation Rewrite statements
1281 Operation rewrite statements are builtin PDLL statements that perform an IR
1282 transformation given a root operation. These statements are the only ones able
1283 to start the `rewrite` section of a pattern, as they allow for properly
1284 ["binding"](#variable-binding) the root operation of the pattern.
1286 ##### `erase` statement
1288 ```pdll
1289 // A pattern that erases all `my_dialect.foo` operations.
1290 Pattern => erase op<my_dialect.foo>;
1293 The `erase` statement erases a given operation.
1295 ##### `replace` statement
1297 ```pdll
1298 // A pattern that replaces the root operation with its input value.
1299 Pattern {
1300   let root = op<my_dialect.foo>(input: Value);
1301   replace root with input;
1304 // A pattern that replaces the root operation with multiple input values.
1305 Pattern {
1306   let root = op<my_dialect.foo>(input: Value, _: Value, input2: Value);
1307   replace root with (input, input2);
1310 // A pattern that replaces the root operation with another operation.
1311 // Note that when an operation is used as the replacement, we can infer its
1312 // result types from the input operation. In these cases, the result
1313 // types of replacement operation may be elided.
1314 Pattern {
1315   // Note: In this pattern we also inlined the `root` expression.
1316   replace op<my_dialect.foo> with op<my_dialect.bar>;
1320 The `replace` statement allows for replacing a given root operation with either
1321 another operation, or a set of input `Value` and `ValueRange` values. When an operation
1322 is used as the replacement, we allow infering the result types from the input operation.
1323 In these cases, the result types of replacement operation may be elided. Note that no
1324 other components aside from the result types will be inferred from the input operation
1325 during the replacement.
1327 ##### `rewrite` statement
1329 ```pdll
1330 // A simple pattern that replaces the root operation with its input value.
1331 Pattern {
1332   let root = op<my_dialect.foo>(input: Value);
1333   rewrite root with {
1334     ...
1336     replace root with input;
1337   };
1341 The `rewrite` statement allows for rewriting a given root operation with a block
1342 of nested rewriters. The root operation is not implicitly erased or replaced,
1343 and any transformations to it must be expressed within the nested rewrite block.
1344 The inner body may contain any number of other rewrite statements, variables, or
1345 expressions.
1347 #### Defining Rewriters in PDLL
1349 Additional rewrites can also be defined within PDLL, which allows for building
1350 rewrite fragments that can be composed across many different patterns. A
1351 rewriter in PDLL is defined similarly to a function in traditional programming
1352 languages; it contains a name, a set of input arguments, a set of result types,
1353 and a body. Results of a rewrite are returned via a `return` statement. A few
1354 examples are shown below:
1356 ```pdll
1357 // A rewrite that constructs and returns a new operation, given an input value.
1358 Rewrite BuildFooOp(value: Value) -> Op {
1359   return op<my_dialect.foo>(value);
1362 Pattern {
1363   // We invoke the rewrite in the same way as functions in traditional
1364   // languages.
1365   replace op<my_dialect.old_op>(input: Value) with BuildFooOp(input);
1369 ##### Rewrites with multiple results
1371 Rewrites can return multiple results by returning a tuple of values. When
1372 returning multiple results, each result can also be assigned a name to use when
1373 indexing that tuple element. Tuple elements can be referenced by their index
1374 number, or by name if they were assigned one.
1376 ```pdll
1377 // A rewrite that returns multiple results, with some of the results assigned
1378 // a more readable name.
1379 Rewrite CreateRewriteOps() -> (Op, result1: ValueRange) {
1380   return (op<my_dialect.bar>, op<my_dialect.foo>);
1383 Pattern {
1384   rewrite root: Op<my_dialect.foo> with {
1385     // Invoke the rewrite, which returns a tuple of values.
1386     let result = CreateRewriteOps();
1388     // Index the tuple elements by index, or by name.
1389     replace root with (result.0, result.1, result.result1);
1390   }
1394 ##### Rewrite result type inference
1396 In addition to explicitly specifying the results of the rewrite via the rewrite
1397 signature, PDLL defined rewrites also support inferring the result type from the
1398 return statement. Result type inference is active whenever the rewrite is
1399 defined with no result constraints:
1401 ```pdll
1402 // This rewrite returns a derived operation.
1403 Rewrite ReturnSelf(op: Op<my_dialect.foo>) => op;
1404 // This rewrite returns a tuple of two Values.
1405 Rewrite ExtractMultipleResults(op: Op<my_dialect.foo>) {
1406   return (result1 = op.result1, result2 = op.result2);
1409 Pattern {
1410   rewrite root: Op<my_dialect.foo> with {
1411     let values = ExtractMultipleResults(op<my_dialect.foo>);
1412     replace root with (values.result1, values.result2);
1413   }
1417 ##### Single Line "Lambda" Body
1419 Rewrites generally define their body using a compound block of statements, as
1420 shown below:
1422 ```pdll
1423 Rewrite ReturnSelf(op: Op<my_dialect.foo>) {
1424   return op;
1426 Rewrite EraseOp(op: Op) {
1427   erase op;
1431 Rewrites also support a lambda-like syntax for specifying simple single line
1432 bodies. The lambda body of a Rewrite expects a single expression, which is
1433 implicitly returned, or a single
1434 [operation rewrite statement](#operation-rewrite-statements):
1436 ```pdll
1437 Rewrite ReturnSelf(op: Op<my_dialect.foo>) => op;
1438 Rewrite EraseOp(op: Op) => erase op;
1441 #### Native Rewriters
1443 Rewriters may also be defined outside of PDLL, and registered natively within
1444 the C++ API.
1446 ##### Importing existing Native Rewrites
1448 Rewrites defined externally can be imported into PDLL by specifying a
1449 rewrite "declaration". This is similar to the PDLL form of defining a
1450 rewrite but omits the body. Importing the declaration in this form allows for
1451 PDLL to statically know the expected input and output types.
1453 ```pdll
1454 // Import a single input native rewrite that returns a new operation. This
1455 // rewrite must be registered by the consumer of the compiled PDL.
1456 Rewrite BuildOp(value: Value) -> Op;
1458 Pattern {
1459   replace op<my_dialect.old_op>(input: Value) with BuildOp(input);
1463 External rewrites are those registered explicitly with the `RewritePatternSet` via
1464 the C++ PDL API. For example, the rewrite above may be registered as:
1466 ```c++
1467 static Operation *buildOpImpl(PDLResultList &results, Value value) {
1468   // insert special rewrite logic here.
1469   Operation *resultOp = ...;
1470   return resultOp;
1473 void registerNativeRewrite(RewritePatternSet &patterns) {
1474   patterns.getPDLPatterns().registerRewriteFunction("BuildOp", buildOpImpl);
1478 ##### Defining Native Rewrites in PDLL
1480 In addition to importing native rewrites, PDLL also supports defining native
1481 rewrites directly when compiling ahead-of-time (AOT) for C++. These rewrites can
1482 be defined by specifying a string code block after the rewrite declaration:
1484 ```pdll
1485 Rewrite BuildOp(value: Value) -> (foo: Op<my_dialect.foo>, bar: Op<my_dialect.bar>) [{
1486   return {rewriter.create<my_dialect::FooOp>(value), rewriter.create<my_dialect::BarOp>()};
1489 Pattern {
1490   let root = op<my_dialect.foo>(input: Value);
1491   rewrite root with {
1492     // Invoke the native rewrite and use the results when replacing the root.
1493     let results = BuildOp(input);
1494     replace root with (results.foo, results.bar);
1495   }
1499 The arguments of the rewrite are accessible within the code block via the
1500 same name. See the ["type translation"](#native-rewrite-type-translations) below for
1501 detailed information on how PDLL types are converted to native types. In addition to the
1502 PDLL arguments, the code block may also access the current `PatternRewriter` using
1503 `rewriter`. See the ["result translation"](#native-rewrite-result-translation) section
1504 for detailed information on how the result type of the native function is determined.
1506 Taking the rewrite defined above as an example, this function would roughly be
1507 translated into:
1509 ```c++
1510 std::tuple<my_dialect::FooOp, my_dialect::BarOp> BuildOp(Value value) {
1511   return {rewriter.create<my_dialect::FooOp>(value), rewriter.create<my_dialect::BarOp>()};
1515 ###### Native Rewrite Type Translations
1517 The types of argument and result variables are generally mapped to the corresponding
1518 MLIR type of the [constraint](#constraints) used. The rules of native `Rewrite` type translation
1519 are identical to those of native `Constraint`s, please view the corresponding
1520 [native `Constraint` type translation](#native-constraint-type-translations) section for a
1521 detailed description of how the mapped type of a variable is determined.
1523 ###### Native Rewrite Result Translation
1525 The results of a native rewrite are directly translated to the results of the native function,
1526 using the type translation rules [described above](#native-rewrite-type-translations). The section
1527 below describes the various result translation scenarios:
1529 * Zero Result
1531 ```pdll
1532 Rewrite createOp() [{
1533   rewriter.create<my_dialect::FooOp>();
1537 In the case where a native `Rewrite` has no results, the native function returns `void`:
1539 ```c++
1540 void createOp(PatternRewriter &rewriter) {
1541   rewriter.create<my_dialect::FooOp>();
1545 * Single Result
1547 ```pdll
1548 Rewrite createOp() -> Op<my_dialect.foo> [{
1549   return rewriter.create<my_dialect::FooOp>();
1553 In the case where a native `Rewrite` has a single result, the native function returns the corresponding
1554 native type for that single result:
1556 ```c++
1557 my_dialect::FooOp createOp(PatternRewriter &rewriter) {
1558   return rewriter.create<my_dialect::FooOp>();
1562 * Multi Result
1564 ```pdll
1565 Rewrite complexRewrite(value: Value) -> (Op<my_dialect.foo>, FunctionOpInterface) [{
1566   ...
1570 In the case where a native `Rewrite` has multiple results, the native function returns a `std::tuple<...>`
1571 containing the corresponding native types for each of the results:
1573 ```c++
1574 std::tuple<my_dialect::FooOp, FunctionOpInterface>
1575 complexRewrite(PatternRewriter &rewriter, Value value) {
1576   ...
1580 #### Defining Rewrites Inline
1582 In addition to global scope, PDLL Rewrites and Native Rewrites defined in PDLL
1583 may be specified *inline* at any level of nesting. This means that they may be
1584 defined in Patterns, other Rewrites, etc:
1586 ```pdll
1587 Rewrite GlobalRewrite(inputValue: Value) {
1588   Rewrite localRewrite(value: Value) {
1589     ...
1590   };
1591   Rewrite localNativeRewrite(value: Value) [{
1592     ...
1593   }];
1594   localRewrite(inputValue);
1595   localNativeRewrite(inputValue);
1599 Rewrites that are defined inline may also elide the name when used directly:
1601 ```pdll
1602 Rewrite GlobalRewrite(inputValue: Value) {
1603   Rewrite(value: Value) { ... }(inputValue);
1604   Rewrite(value: Value) [{ ... }](inputValue);
1608 When defined inline, PDLL rewrites may reference any previously defined
1609 variable:
1611 ```pdll
1612 Rewrite GlobalRewrite(op: Op<my_dialect.foo>) {
1613   Rewrite localRewrite() {
1614     let results = op.results;
1615   };