Lines Matching full:pattern
1 # Pattern Rewriting : Generic DAG-to-DAG Rewriting
5 This document details the design and API of the pattern rewriting infrastructure
16 The pattern rewriting framework can largely be decomposed into two parts:
17 Pattern Definition and Pattern Application.
27 This is the expected benefit of applying a given pattern. This benefit is static
28 upon construction of the pattern, but may be computed dynamically at pattern
31 performing pattern fusion and compiling patterns into an efficient state
35 almost all cases: you can simply instantiate the same pattern one time for each
40 The name of the root operation that this pattern matches against. If specified,
61 /// This overload constructs a pattern that only matches operations with the
65 /// This overload constructs a pattern that matches any operation type.
72 // The `match` method returns `success()` if the pattern is a match, failure
94 Within the `match` section of a pattern, the following constraints apply:
98 Within the `rewrite` section of a pattern, the following constraints apply:
102 possible mutations that may take place within a pattern. For example, this
111 Recursion is an important topic in the context of pattern rewrites, as a pattern
112 may often be applicable to its own result. For example, imagine a pattern that
114 peelable iterations, this pattern may apply multiple times during the
115 application process. By looking at the implementation of this pattern, the bound
117 within the loop, but from the perspective of the pattern driver this recursion
118 is potentially dangerous. Often times the recursive application of a pattern
121 this, the pattern rewriting infrastructure conservatively assumes that no
123 detected. A pattern that is known to have proper support for handling recursion
125 pattern. This will signal to the pattern driver that recursive application of
126 this pattern may happen, and the pattern is equipped to safely handle it.
132 pattern; and a set of debug labels (via `addDebugLabels`), which correspond to
134 by various utilities to aid in the debugging of pattern rewrites, e.g. in debug
135 logs, to provide pattern filtering, etc. A simple code example is shown below:
160 Several pieces of pattern state require explicit initialization by the pattern,
161 for example setting `setHasBoundedRewriteRecursion` if a pattern safely handles
162 recursive application. This pattern state can be initialized either in the
163 constructor of the pattern or via the utility `initialize` hook. Using the
164 `initialize` hook removes the need to redefine pattern constructors just to
165 inject additional pattern state initialization. An example is shown below:
173 /// Initialize the pattern.
175 /// Signal that this pattern safely handles recursive application.
186 `RewritePattern::create<T>` utility method. This method ensures that the pattern
189 ## Pattern Rewriter
191 A `PatternRewriter` is a special class that allows for a pattern to communicate
192 with the driver of pattern application. As noted above, *all* IR mutations,
194 class. This is required because the underlying pattern driver may have state
208 as to why a pattern failed to match. How this message is displayed back to the
209 user is determined by the specific pattern driver.
220 within a pattern. An in-place update transaction is started with
232 ## Pattern Application
246 within the pattern rewriters, a driver must provide a `PatternRewriter` instance
251 * Pattern Application and Cost Model
254 well as pattern cost model, but the final application is performed via a
257 cost model. This cost model computes a final benefit for a given pattern, using
271 /// Populate the pattern list.
292 applicator.applyCostModel([](const Pattern &pattern) {
297 return pattern.getBenefit();
300 // Try to match and apply a pattern.
305 // ... A pattern was successfully applied.
309 ## Common Pattern Drivers
311 MLIR provides several common pattern drivers that serve a variety of different
319 conversion target, via a set of pattern-based operation rewriting patterns. This
323 ### Walk Pattern Rewrite Driver
326 that locally have the most benefit. The benefit of a pattern is decided solely
327 by the benefit specified on the pattern, and the relative order of the pattern
328 within the pattern list (when two patterns have the same local benefit).
335 supported for the currently matched op and its descendant. If your pattern
336 set requires these, consider using the Greedy Pattern Rewrite Driver instead,
347 You can debug the Walk Pattern Rewrite Driver by passing the
351 ### Greedy Pattern Rewrite Driver
354 patterns that locally have the most benefit (same as the Walk Pattern Rewrite
375 match larger patterns with ambiguous pattern sets.
399 To debug the execution of the greedy pattern rewrite driver,
401 LLVM's debug logging infrastructure solely for the greedy pattern rewriter. The
402 output is formatted as a tree structure, mirroring the structure of the pattern
414 * Pattern SimplifyConstCondBranchPred : 'cf.cond_br -> ()' {
415 } -> failure : pattern failed to match
417 * Pattern SimplifyCondBranchIdenticalSuccessors : 'cf.cond_br -> ()' {
420 } -> success : pattern applied successfully
421 } -> success : pattern matched
427 pattern (`SimplifyCondBranchIdenticalSuccessors`) is applied that matches the
432 ### Pattern Filtering
436 to the pattern driver for application. Filtering behavior is specified by
439 debug names or labels for patterns that are disabled during pattern application,
442 pattern application, patterns that do not satisfy this constraint are filtered
474 // Inherit the common pattern rewrite options from `RewritePassUtils`.
482 behavior of rewrite pattern application.
484 ##### Pattern Filtering
486 Two common pattern filtering options are exposed, `disable-patterns` and
488 `enabledPatterns` lists described in the [Pattern Filtering](#pattern-filtering)