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;
59`getCanonicalizationPatterns` and `fold`.
60
61### Canonicalizing with `getCanonicalizationPatterns`
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 to
71generate a declaration for the `getCanonicalizationPatterns` method.
72
73```tablegen
74def MyOp : ... {
75  let hasCanonicalizer = 1;
76}
77```
78
79Canonicalization patterns can then be provided in the source file:
80
81```c++
82void MyOp::getCanonicalizationPatterns(OwningRewritePatternList &patterns,
83                                       MLIRContext *context) {
84  patterns.insert<...>(...);
85}
86```
87
88See the [quickstart guide](Tutorials/QuickstartRewrites.md) for information on
89defining operation rewrites.
90
91### Canonicalizing with `fold`
92
93The `fold` mechanism is an intentionally limited, but powerful mechanism that
94allows for applying canonicalizations in many places throughout the compiler.
95For example, outside of the canonicalizer pass, `fold` is used within the
96[dialect conversion infrastructure](#DialectConversion.md) as a legalization
97mechanism, 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
101root operation may be replaced. It allows for updating an operation in-place, or
102returning a set of pre-existing values (or attributes) to replace the operation
103with. This ensures that the `fold` method is a truly "local" transformation, and
104can be invoked without the need for a pattern rewriter.
105
106In [ODS](OpDefinitions.md), an operation can set the `hasFolder` bit to generate
107a declaration for the `fold` method. This method takes on a different form,
108depending on the structure of the operation.
109
110```tablegen
111def MyOp : ... {
112  let hasFolder = 1;
113}
114```
115
116If the operation has a single result the following will be generated:
117
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///
130OpFoldResult MyOp::fold(ArrayRef<Attribute> operands) {
131  ...
132}
133```
134
135Otherwise, 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///
151LogicalResult MyOp::fold(ArrayRef<Attribute> operands,
152                         SmallVectorImpl<OpFoldResult> &results) {
153  ...
154}
155```
156
157In the above, for each method an `ArrayRef<Attribute>` is provided that
158corresponds to the constant attribute value of each of the operands. These
159operands are those that implement the `ConstantLike` trait. If any of the
160operands are non-constant, a null `Attribute` value is provided instead. For
161example, if MyOp provides three operands [`a`, `b`, `c`], but only `b` is
162constant then `operands` will be of the form [Attribute(), b-value,
163Attribute()].
164
165Also above, is the use of `OpFoldResult`. This class represents the possible
166result 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*
168correspond to an existing value. The `fold` methods are not permitted to
169generate 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`
171representation of a specific `Type` is consistent.
172
173When the `fold` hook on an operation is not successful, the dialect can
174provide a fallback by implementing the `DialectFoldInterface` and overriding
175the fold hook.
176
177#### Generating Constants from Attributes
178
179When a `fold` method returns an `Attribute` as the result, it signifies that
180this result is "constant". The `Attribute` is the constant representation of the
181value. Users of the `fold` method, such as the canonicalizer pass, will take
182these `Attribute`s and materialize constant operations in the IR to represent
183them. To enable this materialization, the dialect of the operation must
184implement the `materializeConstant` hook. This hook takes in an `Attribute`
185value, generally returned by `fold`, and produces a "constant-like" operation
186that materializes that value.
187
188In [ODS](OpDefinitions.md), a dialect can set the `hasConstantMaterializer` bit
189to generate a declaration for the `materializeConstant` method.
190
191```tablegen
192def MyDialect_Dialect : ... {
193  let hasConstantMaterializer = 1;
194}
195```
196
197Constants can then be materialized in the source file:
198
199```c++
200/// Hook to materialize a single constant operation from a given attribute value
201/// with the desired resultant type. This method should use the provided builder
202/// to create the operation without changing the insertion position. The
203/// generated operation is expected to be constant-like. On success, this hook
204/// should return the value generated to represent the constant value.
205/// Otherwise, it should return nullptr on failure.
206Operation *MyDialect::materializeConstant(OpBuilder &builder, Attribute value,
207                                          Type type, Location loc) {
208  ...
209}
210```
211