1# Pattern Rewriting : Generic DAG-to-DAG Rewriting 2 3[TOC] 4 5This document details the design and API of the pattern rewriting infrastructure 6present in MLIR, a general DAG-to-DAG transformation framework. This framework 7is widely used throughout MLIR for canonicalization, conversion, and general 8transformation. 9 10For an introduction to DAG-to-DAG transformation, and the rationale behind this 11framework please take a look at the 12[Generic DAG Rewriter Rationale](Rationale/RationaleGenericDAGRewriter.md). 13 14## Introduction 15 16The pattern rewriting framework can largely be decomposed into two parts: 17Pattern Definition and Pattern Application. 18 19## Defining Patterns 20 21Patterns are defined by inheriting from the `RewritePattern` class. This class 22represents the base class of all rewrite patterns within MLIR, and is comprised 23of the following components: 24 25### Benefit 26 27This is the expected benefit of applying a given pattern. This benefit is static 28upon construction of the pattern, but may be computed dynamically at pattern 29initialization time, e.g. allowing the benefit to be derived from domain 30specific information (like the target architecture). This limitation allows for 31performing pattern fusion and compiling patterns into an efficient state 32machine, and 33[Thier, Ertl, and Krall](https://dl.acm.org/citation.cfm?id=3179501) have shown 34that match predicates eliminate the need for dynamically computed costs in 35almost all cases: you can simply instantiate the same pattern one time for each 36possible cost and use the predicate to guard the match. 37 38### Root Operation Name (Optional) 39 40The name of the root operation that this pattern matches against. If specified, 41only operations with the given root name will be provided to the `match` and 42`rewrite` implementation. If not specified, any operation type may be provided. 43The root operation name should be provided whenever possible, because it 44simplifies the analysis of patterns when applying a cost model. To match any 45operation type, a special tag must be provided to make the intent explicit: 46`MatchAnyOpTypeTag`. 47 48### `match` and `rewrite` implementation 49 50This is the chunk of code that matches a given root `Operation` and performs a 51rewrite of the IR. A `RewritePattern` can specify this implementation either via 52separate `match` and `rewrite` methods, or via a combined `matchAndRewrite` 53method. When using the combined `matchAndRewrite` method, no IR mutation should 54take place before the match is deemed successful. The combined `matchAndRewrite` 55is useful when non-trivially recomputable information is required by the 56matching and rewriting phase. See below for examples: 57 58```c++ 59class MyPattern : public RewritePattern { 60public: 61 /// This overload constructs a pattern that only matches operations with the 62 /// root name of `MyOp`. 63 MyPattern(PatternBenefit benefit, MLIRContext *context) 64 : RewritePattern(MyOp::getOperationName(), benefit, context) {} 65 /// This overload constructs a pattern that matches any operation type. 66 MyPattern(PatternBenefit benefit) 67 : RewritePattern(benefit, MatchAnyOpTypeTag()) {} 68 69 /// In this section, the `match` and `rewrite` implementation is specified 70 /// using the separate hooks. 71 LogicalResult match(Operation *op) const override { 72 // The `match` method returns `success()` if the pattern is a match, failure 73 // otherwise. 74 // ... 75 } 76 void rewrite(Operation *op, PatternRewriter &rewriter) { 77 // The `rewrite` method performs mutations on the IR rooted at `op` using 78 // the provided rewriter. All mutations must go through the provided 79 // rewriter. 80 } 81 82 /// In this section, the `match` and `rewrite` implementation is specified 83 /// using a single hook. 84 LogicalResult matchAndRewrite(Operation *op, PatternRewriter &rewriter) { 85 // The `matchAndRewrite` method performs both the matching and the mutation. 86 // Note that the match must reach a successful point before IR mutation may 87 // take place. 88 } 89}; 90``` 91 92#### Restrictions 93 94Within the `match` section of a pattern, the following constraints apply: 95 96* No mutation of the IR is allowed. 97 98Within the `rewrite` section of a pattern, the following constraints apply: 99 100* All IR mutations, including creation, *must* be performed by the given 101 `PatternRewriter`. This class provides hooks for performing all of the 102 possible mutations that may take place within a pattern. For example, this 103 means that an operation should not be erased via its `erase` method. To 104 erase an operation, the appropriate `PatternRewriter` hook (in this case 105 `eraseOp`) should be used instead. 106* The root operation is required to either be: updated in-place, replaced, or 107 erased. 108 109### Pattern Rewriter 110 111A `PatternRewriter` is a special class that allows for a pattern to communicate 112with the driver of pattern application. As noted above, *all* IR mutations, 113including creations, are required to be performed via the `PatternRewriter` 114class. This is required because the underlying pattern driver may have state 115that would be invalidated when a mutation takes place. Examples of some of the 116more prevalent `PatternRewriter` API is shown below, please refer to the 117[class documentation](https://github.com/llvm/llvm-project/blob/master/mlir/include/mlir/IR/PatternMatch.h#L235) 118for a more up-to-date listing of the available API: 119 120* Erase an Operation : `eraseOp` 121 122This method erases an operation that either has no results, or whose results are 123all known to have no uses. 124 125* Notify why a `match` failed : `notifyMatchFailure` 126 127This method allows for providing a diagnostic message within a `matchAndRewrite` 128as to why a pattern failed to match. How this message is displayed back to the 129user is determined by the specific pattern driver. 130 131* Replace an Operation : `replaceOp`/`replaceOpWithNewOp` 132 133This method replaces an operation's results with a set of provided values, and 134erases the operation. 135 136* Update an Operation in-place : `(start|cancel|finalize)RootUpdate` 137 138This is a collection of methods that provide a transaction-like API for updating 139the attributes, location, operands, or successors of an operation in-place 140within a pattern. An in-place update transaction is started with 141`startRootUpdate`, and may either be canceled or finalized with 142`cancelRootUpdate` and `finalizeRootUpdate` respectively. A convenience wrapper, 143`updateRootInPlace`, is provided that wraps a `start` and `finalize` around a 144callback. 145 146* OpBuilder API 147 148The `PatternRewriter` inherits from the `OpBuilder` class, and thus provides all 149of the same functionality present within an `OpBuilder`. This includes operation 150creation, as well as many useful attribute and type construction methods. 151 152## Pattern Application 153 154After a set of patterns have been defined, they are collected and provided to a 155specific driver for application. A driver consists of several high levels parts: 156 157* Input `OwningRewritePatternList` 158 159The input patterns to a driver are provided in the form of an 160`OwningRewritePatternList`. This class provides a simplified API for building a 161list of patterns. 162 163* Driver-specific `PatternRewriter` 164 165To ensure that the driver state does not become invalidated by IR mutations 166within the pattern rewriters, a driver must provide a `PatternRewriter` instance 167with the necessary hooks overridden. If a driver does not need to hook into 168certain mutations, a default implementation is provided that will perform the 169mutation directly. 170 171* Pattern Application and Cost Model 172 173Each driver is responsible for defining its own operation visitation order as 174well as pattern cost model, but the final application is performed via a 175`PatternApplicator` class. This class takes as input the 176`OwningRewritePatternList` and transforms the patterns based upon a provided 177cost model. This cost model computes a final benefit for a given pattern, using 178whatever driver specific information necessary. After a cost model has been 179computed, the driver may begin to match patterns against operations using 180`PatternApplicator::matchAndRewrite`. 181 182An example is shown below: 183 184```c++ 185class MyPattern : public RewritePattern { 186public: 187 MyPattern(PatternBenefit benefit, MLIRContext *context) 188 : RewritePattern(MyOp::getOperationName(), benefit, context) {} 189}; 190 191/// Populate the pattern list. 192void collectMyPatterns(OwningRewritePatternList &patterns, MLIRContext *ctx) { 193 patterns.insert<MyPattern>(/*benefit=*/1, ctx); 194} 195 196/// Define a custom PatternRewriter for use by the driver. 197class MyPatternRewriter : public PatternRewriter { 198public: 199 MyPatternRewriter(MLIRContext *ctx) : PatternRewriter(ctx) {} 200 201 /// Override the necessary PatternRewriter hooks here. 202}; 203 204/// Apply the custom driver to `op`. 205void applyMyPatternDriver(Operation *op, 206 const OwningRewritePatternList &patterns) { 207 // Initialize the custom PatternRewriter. 208 MyPatternRewriter rewriter(op->getContext()); 209 210 // Create the applicator and apply our cost model. 211 PatternApplicator applicator(patterns); 212 applicator.applyCostModel([](const Pattern &pattern) { 213 // Apply a default cost model. 214 // Note: This is just for demonstration, if the default cost model is truly 215 // desired `applicator.applyDefaultCostModel()` should be used 216 // instead. 217 return pattern.getBenefit(); 218 }); 219 220 // Try to match and apply a pattern. 221 LogicalResult result = applicator.matchAndRewrite(op, rewriter); 222 if (failed(result)) { 223 // ... No patterns were applied. 224 } 225 // ... A pattern was successfully applied. 226} 227``` 228 229## Common Pattern Drivers 230 231MLIR provides several common pattern drivers that serve a variety of different 232use cases. 233 234### Dialect Conversion Driver 235 236This driver provides a framework in which to perform operation conversions 237between, and within dialects using a concept of "legality". This framework 238allows for transforming illegal operations to those supported by a provided 239conversion target, via a set of pattern-based operation rewriting patterns. This 240framework also provides support for type conversions. More information on this 241driver can be found [here](DialectConversion.md). 242 243### Greedy Pattern Rewrite Driver 244 245This driver performs a post order traversal over the provided operations and 246greedily applies the patterns that locally have the most benefit. The benefit of 247a pattern is decided solely by the benefit specified on the pattern, and the 248relative order of the pattern within the pattern list (when two patterns have 249the same local benefit). Patterns are iteratively applied to operations until a 250fixed point is reached, at which point the driver finishes. This driver may be 251used via the following: `applyPatternsAndFoldGreedily` and 252`applyOpPatternsAndFold`. The latter of which only applies patterns to the 253provided operation, and will not traverse the IR. 254 255Note: This driver is the one used by the [canonicalization](Canonicalization.md) 256[pass](Passes.md#-canonicalize-canonicalize-operations) in MLIR. 257