|
173
|
1 # Operation Canonicalization
|
|
150
|
2
|
|
|
3 Canonicalization is an important part of compiler IR design: it makes it easier
|
|
|
4 to implement reliable compiler transformations and to reason about what is
|
|
|
5 better or worse in the code, and it forces interesting discussions about the
|
|
|
6 goals of a particular level of IR. Dan Gohman wrote
|
|
|
7 [an article](https://sunfishcode.github.io/blog/2018/10/22/Canonicalization.html)
|
|
|
8 exploring these issues; it is worth reading if you're not familiar with these
|
|
|
9 concepts.
|
|
|
10
|
|
|
11 Most compilers have canonicalization passes, and sometimes they have many
|
|
|
12 different ones (e.g. instcombine, dag combine, etc in LLVM). Because MLIR is a
|
|
|
13 multi-level IR, we can provide a single canonicalization infrastructure and
|
|
|
14 reuse it across many different IRs that it represents. This document describes
|
|
|
15 the general approach, global canonicalizations performed, and provides sections
|
|
|
16 to capture IR-specific rules for reference.
|
|
|
17
|
|
|
18 ## General Design
|
|
|
19
|
|
|
20 MLIR has a single canonicalization pass, which iteratively applies
|
|
|
21 canonicalization transformations in a greedy way until the IR converges. These
|
|
|
22 transformations are defined by the operations themselves, which allows each
|
|
|
23 dialect to define its own set of operations and canonicalizations together.
|
|
|
24
|
|
|
25 Some important things to think about w.r.t. canonicalization patterns:
|
|
|
26
|
|
|
27 * Repeated applications of patterns should converge. Unstable or cyclic
|
|
|
28 rewrites will cause infinite loops in the canonicalizer.
|
|
|
29
|
|
|
30 * It is generally better to canonicalize towards operations that have fewer
|
|
|
31 uses of a value when the operands are duplicated, because some patterns only
|
|
|
32 match when a value has a single user. For example, it is generally good to
|
|
|
33 canonicalize "x + x" into "x * 2", because this reduces the number of uses
|
|
|
34 of x by one.
|
|
|
35
|
|
|
36 * It is always good to eliminate operations entirely when possible, e.g. by
|
|
|
37 folding known identities (like "x + 0 = x").
|
|
|
38
|
|
|
39 ## Globally Applied Rules
|
|
|
40
|
|
|
41 These transformations are applied to all levels of IR:
|
|
|
42
|
|
|
43 * Elimination of operations that have no side effects and have no uses.
|
|
|
44
|
|
|
45 * Constant folding - e.g. "(addi 1, 2)" to "3". Constant folding hooks are
|
|
|
46 specified by operations.
|
|
|
47
|
|
173
|
48 * Move constant operands to commutative operators to the right side - e.g.
|
|
|
49 "(addi 4, x)" to "(addi x, 4)".
|
|
|
50
|
|
|
51 * `constant-like` operations are uniqued and hoisted into the entry block of
|
|
|
52 the first parent barrier region. This is a region that is either isolated
|
|
|
53 from above, e.g. the entry block of a function, or one marked as a barrier
|
|
|
54 via the `shouldMaterializeInto` method on the `OpFolderDialectInterface`.
|
|
|
55
|
|
|
56 ## Defining Canonicalizations
|
|
|
57
|
|
|
58 Two mechanisms are available with which to define canonicalizations;
|
|
|
59 `getCanonicalizationPatterns` and `fold`.
|
|
|
60
|
|
|
61 ### Canonicalizing with `getCanonicalizationPatterns`
|
|
|
62
|
|
|
63 This mechanism allows for providing canonicalizations as a set of
|
|
|
64 `RewritePattern`s, either imperatively defined in C++ or declaratively as
|
|
|
65 [Declarative Rewrite Rules](DeclarativeRewrites.md). The pattern rewrite
|
|
|
66 infrastructure allows for expressing many different types of canonicalizations.
|
|
|
67 These transformations may be as simple as replacing a multiplication with a
|
|
|
68 shift, or even replacing a conditional branch with an unconditional one.
|
|
|
69
|
|
|
70 In [ODS](OpDefinitions.md), an operation can set the `hasCanonicalizer` bit to
|
|
|
71 generate a declaration for the `getCanonicalizationPatterns` method.
|
|
|
72
|
|
|
73 ```tablegen
|
|
|
74 def MyOp : ... {
|
|
|
75 let hasCanonicalizer = 1;
|
|
|
76 }
|
|
|
77 ```
|
|
|
78
|
|
|
79 Canonicalization patterns can then be provided in the source file:
|
|
150
|
80
|
|
173
|
81 ```c++
|
|
|
82 void MyOp::getCanonicalizationPatterns(OwningRewritePatternList &patterns,
|
|
|
83 MLIRContext *context) {
|
|
|
84 patterns.insert<...>(...);
|
|
|
85 }
|
|
|
86 ```
|
|
|
87
|
|
|
88 See the [quickstart guide](Tutorials/QuickstartRewrites.md) for information on
|
|
|
89 defining operation rewrites.
|
|
|
90
|
|
|
91 ### Canonicalizing with `fold`
|
|
150
|
92
|
|
173
|
93 The `fold` mechanism is an intentionally limited, but powerful mechanism that
|
|
|
94 allows for applying canonicalizations in many places throughout the compiler.
|
|
|
95 For example, outside of the canonicalizer pass, `fold` is used within the
|
|
|
96 [dialect conversion infrastructure](#DialectConversion.md) as a legalization
|
|
|
97 mechanism, and can be invoked directly anywhere with an `OpBuilder` via
|
|
|
98 `OpBuilder::createOrFold`.
|
|
|
99
|
|
|
100 `fold` has the restriction that no new operations may be created, and only the
|
|
|
101 root operation may be replaced. It allows for updating an operation in-place, or
|
|
|
102 returning a set of pre-existing values (or attributes) to replace the operation
|
|
|
103 with. This ensures that the `fold` method is a truly "local" transformation, and
|
|
|
104 can be invoked without the need for a pattern rewriter.
|
|
|
105
|
|
|
106 In [ODS](OpDefinitions.md), an operation can set the `hasFolder` bit to generate
|
|
|
107 a declaration for the `fold` method. This method takes on a different form,
|
|
|
108 depending on the structure of the operation.
|
|
|
109
|
|
|
110 ```tablegen
|
|
|
111 def MyOp : ... {
|
|
|
112 let hasFolder = 1;
|
|
|
113 }
|
|
|
114 ```
|
|
|
115
|
|
|
116 If the operation has a single result the following will be generated:
|
|
150
|
117
|
|
173
|
118 ```c++
|
|
|
119 /// Implementations of this hook can only perform the following changes to the
|
|
|
120 /// operation:
|
|
|
121 ///
|
|
|
122 /// 1. They can leave the operation alone and without changing the IR, and
|
|
|
123 /// return nullptr.
|
|
|
124 /// 2. They can mutate the operation in place, without changing anything else
|
|
|
125 /// in the IR. In this case, return the operation itself.
|
|
|
126 /// 3. They can return an existing value or attribute that can be used instead
|
|
|
127 /// of the operation. The caller will remove the operation and use that
|
|
|
128 /// result instead.
|
|
|
129 ///
|
|
|
130 OpFoldResult MyOp::fold(ArrayRef<Attribute> operands) {
|
|
|
131 ...
|
|
|
132 }
|
|
|
133 ```
|
|
|
134
|
|
|
135 Otherwise, the following is generated:
|
|
|
136
|
|
|
137 ```c++
|
|
|
138 /// Implementations of this hook can only perform the following changes to the
|
|
|
139 /// operation:
|
|
|
140 ///
|
|
|
141 /// 1. They can leave the operation alone and without changing the IR, and
|
|
|
142 /// return failure.
|
|
|
143 /// 2. They can mutate the operation in place, without changing anything else
|
|
|
144 /// in the IR. In this case, return success.
|
|
|
145 /// 3. They can return a list of existing values or attribute that can be used
|
|
|
146 /// instead of the operation. In this case, fill in the results list and
|
|
|
147 /// return success. The results list must correspond 1-1 with the results of
|
|
|
148 /// the operation, partial folding is not supported. The caller will remove
|
|
|
149 /// the operation and use those results instead.
|
|
|
150 ///
|
|
|
151 LogicalResult MyOp::fold(ArrayRef<Attribute> operands,
|
|
|
152 SmallVectorImpl<OpFoldResult> &results) {
|
|
|
153 ...
|
|
|
154 }
|
|
|
155 ```
|
|
150
|
156
|
|
173
|
157 In the above, for each method an `ArrayRef<Attribute>` is provided that
|
|
|
158 corresponds to the constant attribute value of each of the operands. These
|
|
|
159 operands are those that implement the `ConstantLike` trait. If any of the
|
|
|
160 operands are non-constant, a null `Attribute` value is provided instead. For
|
|
|
161 example, if MyOp provides three operands [`a`, `b`, `c`], but only `b` is
|
|
|
162 constant then `operands` will be of the form [Attribute(), b-value,
|
|
|
163 Attribute()].
|
|
|
164
|
|
|
165 Also above, is the use of `OpFoldResult`. This class represents the possible
|
|
|
166 result of folding an operation result: either an SSA `Value`, or an
|
|
|
167 `Attribute`(for a constant result). If an SSA `Value` is provided, it *must*
|
|
|
168 correspond to an existing value. The `fold` methods are not permitted to
|
|
|
169 generate new `Value`s. There are no specific restrictions on the form of the
|
|
|
170 `Attribute` value returned, but it is important to ensure that the `Attribute`
|
|
|
171 representation of a specific `Type` is consistent.
|
|
|
172
|
|
|
173 #### Generating Constants from Attributes
|
|
150
|
174
|
|
173
|
175 When a `fold` method returns an `Attribute` as the result, it signifies that
|
|
|
176 this result is "constant". The `Attribute` is the constant representation of the
|
|
|
177 value. Users of the `fold` method, such as the canonicalizer pass, will take
|
|
|
178 these `Attribute`s and materialize constant operations in the IR to represent
|
|
|
179 them. To enable this materialization, the dialect of the operation must
|
|
|
180 implement the `materializeConstant` hook. This hook takes in an `Attribute`
|
|
|
181 value, generally returned by `fold`, and produces a "constant-like" operation
|
|
|
182 that materializes that value.
|
|
|
183
|
|
|
184 In [ODS](OpDefinitions.md), a dialect can set the `hasConstantMaterializer` bit
|
|
|
185 to generate a declaration for the `materializeConstant` method.
|
|
|
186
|
|
|
187 ```tablegen
|
|
|
188 def MyDialect_Dialect : ... {
|
|
|
189 let hasConstantMaterializer = 1;
|
|
|
190 }
|
|
|
191 ```
|
|
|
192
|
|
|
193 Constants can then be materialized in the source file:
|
|
|
194
|
|
|
195 ```c++
|
|
|
196 /// Hook to materialize a single constant operation from a given attribute value
|
|
|
197 /// with the desired resultant type. This method should use the provided builder
|
|
|
198 /// to create the operation without changing the insertion position. The
|
|
|
199 /// generated operation is expected to be constant-like. On success, this hook
|
|
|
200 /// should return the value generated to represent the constant value.
|
|
|
201 /// Otherwise, it should return nullptr on failure.
|
|
|
202 Operation *MyDialect::materializeConstant(OpBuilder &builder, Attribute value,
|
|
|
203 Type type, Location loc) {
|
|
|
204 ...
|
|
|
205 }
|
|
|
206 ```
|
