1# Operation Canonicalization
2
3Canonicalization is an important part of compiler IR design: it makes it easier
4to implement reliable compiler transformations and to reason about what is
5better or worse in the code, and it forces interesting discussions about the
6goals of a particular level of IR. Dan Gohman wrote
7[an article](https://sunfishcode.github.io/blog/2018/10/22/Canonicalization.html)
8exploring these issues; it is worth reading if you're not familiar with these
9concepts.
10
11Most compilers have canonicalization passes, and sometimes they have many
12different ones (e.g. instcombine, dag combine, etc in LLVM). Because MLIR is a
13multi-level IR, we can provide a single canonicalization infrastructure and
14reuse it across many different IRs that it represents. This document describes
15the general approach, global canonicalizations performed, and provides sections
16to capture IR-specific rules for reference.
17
18## General Design
19
20MLIR has a single canonicalization pass, which iteratively applies
21canonicalization transformations in a greedy way until the IR converges. These
22transformations are defined by the operations themselves, which allows each
23dialect to define its own set of operations and canonicalizations together.
24
25Some 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
41These 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
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 `DialectFoldInterface`.
55
56## Defining Canonicalizations
57
58Two mechanisms are available with which to define canonicalizations;
59general `RewritePattern`s and the `fold` method.
60
61### Canonicalizing with `RewritePattern`s
62
63This 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
66infrastructure allows for expressing many different types of canonicalizations.
67These transformations may be as simple as replacing a multiplication with a
68shift, or even replacing a conditional branch with an unconditional one.
69
70In [ODS](OpDefinitions.md), an operation can set the `hasCanonicalizer` bit or
71the `hasCanonicalizeMethod` bit to generate a declaration for the
72`getCanonicalizationPatterns` method:
73
74```tablegen
75def MyOp : ... {
76  // I want to define a fully general set of patterns for this op.
77  let hasCanonicalizer = 1;
78}
79
80def OtherOp : ... {
81  // A single "matchAndRewrite" style RewritePattern implemented as a method
82  // is good enough for me.
83  let hasCanonicalizeMethod = 1;
84}
85```
86
87Canonicalization patterns can then be provided in the source file:
88
89```c++
90void MyOp::getCanonicalizationPatterns(RewritePatternSet &patterns,
91                                       MLIRContext *context) {
92  patterns.add<...>(...);
93}
94
95LogicalResult OtherOp::canonicalize(OtherOp op, PatternRewriter &rewriter) {
96  // patterns and rewrites go here.
97  return failure();
98}
99```
100
101See the [quickstart guide](Tutorials/QuickstartRewrites.md) for information on
102defining operation rewrites.
103
104### Canonicalizing with the `fold` method
105
106The `fold` mechanism is an intentionally limited, but powerful mechanism that
107allows for applying canonicalizations in many places throughout the compiler.
108For example, outside of the canonicalizer pass, `fold` is used within the
109[dialect conversion infrastructure](DialectConversion.md) as a legalization
110mechanism, and can be invoked directly anywhere with an `OpBuilder` via
111`OpBuilder::createOrFold`.
112
113`fold` has the restriction that no new operations may be created, and only the
114root operation may be replaced (but not erased). It allows for updating an
115operation in-place, or returning a set of pre-existing values (or attributes) to
116replace the operation with. This ensures that the `fold` method is a truly
117"local" transformation, and can be invoked without the need for a pattern
118rewriter.
119
120In [ODS](OpDefinitions.md), an operation can set the `hasFolder` bit to generate
121a declaration for the `fold` method. This method takes on a different form,
122depending on the structure of the operation.
123
124```tablegen
125def MyOp : ... {
126  let hasFolder = 1;
127}
128```
129
130If the operation has a single result the following will be generated:
131
132```c++
133/// Implementations of this hook can only perform the following changes to the
134/// operation:
135///
136///  1. They can leave the operation alone and without changing the IR, and
137///     return nullptr.
138///  2. They can mutate the operation in place, without changing anything else
139///     in the IR. In this case, return the operation itself.
140///  3. They can return an existing value or attribute that can be used instead
141///     of the operation. The caller will remove the operation and use that
142///     result instead.
143///
144OpFoldResult MyOp::fold(ArrayRef<Attribute> operands) {
145  ...
146}
147```
148
149Otherwise, the following is generated:
150
151```c++
152/// Implementations of this hook can only perform the following changes to the
153/// operation:
154///
155///  1. They can leave the operation alone and without changing the IR, and
156///     return failure.
157///  2. They can mutate the operation in place, without changing anything else
158///     in the IR. In this case, return success.
159///  3. They can return a list of existing values or attribute that can be used
160///     instead of the operation. In this case, fill in the results list and
161///     return success. The results list must correspond 1-1 with the results of
162///     the operation, partial folding is not supported. The caller will remove
163///     the operation and use those results instead.
164///
165/// Note that this mechanism cannot be used to remove 0-result operations.
166LogicalResult MyOp::fold(ArrayRef<Attribute> operands,
167                         SmallVectorImpl<OpFoldResult> &results) {
168  ...
169}
170```
171
172In the above, for each method an `ArrayRef<Attribute>` is provided that
173corresponds to the constant attribute value of each of the operands. These
174operands are those that implement the `ConstantLike` trait. If any of the
175operands are non-constant, a null `Attribute` value is provided instead. For
176example, if MyOp provides three operands [`a`, `b`, `c`], but only `b` is
177constant then `operands` will be of the form [Attribute(), b-value,
178Attribute()].
179
180Also above, is the use of `OpFoldResult`. This class represents the possible
181result of folding an operation result: either an SSA `Value`, or an
182`Attribute`(for a constant result). If an SSA `Value` is provided, it *must*
183correspond to an existing value. The `fold` methods are not permitted to
184generate new `Value`s. There are no specific restrictions on the form of the
185`Attribute` value returned, but it is important to ensure that the `Attribute`
186representation of a specific `Type` is consistent.
187
188When the `fold` hook on an operation is not successful, the dialect can
189provide a fallback by implementing the `DialectFoldInterface` and overriding
190the fold hook.
191
192#### Generating Constants from Attributes
193
194When a `fold` method returns an `Attribute` as the result, it signifies that
195this result is "constant". The `Attribute` is the constant representation of the
196value. Users of the `fold` method, such as the canonicalizer pass, will take
197these `Attribute`s and materialize constant operations in the IR to represent
198them. To enable this materialization, the dialect of the operation must
199implement the `materializeConstant` hook. This hook takes in an `Attribute`
200value, generally returned by `fold`, and produces a "constant-like" operation
201that materializes that value.
202
203In [ODS](DefiningDialects.md), a dialect can set the `hasConstantMaterializer` bit
204to generate a declaration for the `materializeConstant` method.
205
206```tablegen
207def MyDialect : ... {
208  let hasConstantMaterializer = 1;
209}
210```
211
212Constants can then be materialized in the source file:
213
214```c++
215/// Hook to materialize a single constant operation from a given attribute value
216/// with the desired resultant type. This method should use the provided builder
217/// to create the operation without changing the insertion position. The
218/// generated operation is expected to be constant-like. On success, this hook
219/// should return the value generated to represent the constant value.
220/// Otherwise, it should return nullptr on failure.
221Operation *MyDialect::materializeConstant(OpBuilder &builder, Attribute value,
222                                          Type type, Location loc) {
223  ...
224}
225```
226