[mlir] Update the documentation on Canonicalization

[rriddle]

Summary

This updates the canonicalization documentation, and properly documents the different ways of canonicalizing operations.

[mehdi_amini]

mlir/docs/Canonicalization.md

53

This is controlled per dialect I believe, it can be more restrictive than "the first parent region that is isolated from above"

100

"no new operations" may be created: so I can't fold a dynamic slice(..., const) into a static slice that would take the constant value as an attribute, even though I'm just replacing the root operation?

168

The fold methods are not permitted to generate new Values.

Is this checked by the way?

[rriddle]

Resolve comments

mlir/docs/Canonicalization.md

100

Correct. The fold method isn't allowed to create anything, somewhat evident given that no builder is provided.

168

Not at the moment.

mlir/docs/Canonicalization.md

-# Operation Canonicalization in MLIR
+# Operation Canonicalization
 
 Canonicalization is an important part of compiler IR design: it makes it easier
 to implement reliable compiler transformations and to reason about what is
 better or worse in the code, and it forces interesting discussions about the
 goals of a particular level of IR. Dan Gohman wrote
 [an article](https://sunfishcode.github.io/blog/2018/10/22/Canonicalization.html)
 exploring these issues; it is worth reading if you're not familiar with these
 concepts.

 
 These transformations are applied to all levels of IR:
 
 *   Elimination of operations that have no side effects and have no uses.
 
 *   Constant folding - e.g. "(addi 1, 2)" to "3". Constant folding hooks are
     specified by operations.
 
-*   Move constant operands to commutative binary operators to the right side -
-    e.g. "(addi 4, x)" to "(addi x, 4)".
+*   Move constant operands to commutative operators to the right side - e.g.
+    "(addi 4, x)" to "(addi x, 4)".
 
-## Builtin Ops Canonicalizations
-
-These transformations are applied to builtin ops:
-
-*   `constant` ops are uniqued and hoisted into the entry block of the first
-    parent region that is isolated from above, e.g. the entry block of a
-    function.
-*   (TODO) Merge `affine.apply` operations that directly feed each other.
-
-## Standard Ops Canonicalizations
-
-*   Shape folding of `alloc` operations to turn dynamic dimensions into static
-    ones.
-*   Folding `memref_cast` operations into users where possible.
+*   `constant-like` operations are uniqued and hoisted into the entry block of
+    the first parent barrier region. This is a region that is either isolated
+    from above, e.g. the entry block of a function, or one marked as a barrier
+    via the `shouldMaterializeInto` method on the `OpFolderDialectInterface`.
+
+## Defining Canonicalizations
+
+Two mechanisms are available with which to define canonicalizations;
+`getCanonicalizationPatterns` and `fold`.
+
+### Canonicalizing with `getCanonicalizationPatterns`
+
+This mechanism allows for providing canonicalizations as a set of
+`RewritePattern`s, either imperatively defined in C++ or declaratively as
+[Declarative Rewrite Rules](DeclarativeRewrites.md). The pattern rewrite
+infrastructure allows for expressing many different types of canonicalizations.
+These transformations may be as simple as replacing a multiplication with a
+shift, or even replacing a conditional branch with an unconditional one.
+
+In [ODS](OpDefinitions.md), an operation can set the `hasCanonicalizer` bit to
+generate a declaration for the `getCanonicalizationPatterns` method.
+
+```tablegen
+def MyOp : ... {
+  let hasCanonicalizer = 1;
+}
+```
+
+Canonicalization patterns can then be provided in the source file:
+
+```c++
+void MyOp::getCanonicalizationPatterns(OwningRewritePatternList &patterns,
+                                       MLIRContext *context) {
+  patterns.insert<...>(...);
+}
+```
+
+See the [quickstart guide](QuickstartRewrites.md) for information on defining
+operation rewrites.
+
+### Canonicalizing with `fold`
+
+The `fold` mechanism is an intentionally limited, but powerful mechanism that
+allows for applying canonicalizations in many places throughout the compiler.
+For example, outside of the canonicalizer pass, `fold` is used within the
+[dialect conversion infrastructure](#DialectConversion.md) as a legalization
+mechanism, and can be invoked directly anywhere with an `OpBuilder` via
+`OpBuilder::createOrFold`.
+
+`fold` has the restriction that no new operations may be created, and only the
+root operation may be replaced. It allows for updating an operation in-place, or
+returning a set of pre-existing values (or attributes) to replace the operation
+with. This ensures that the `fold` method is a truly "local" transformation, and
+can be invoked without the need for a pattern rewriter.
+
+In [ODS](OpDefinitions.md), an operation can set the `hasFolder` bit to generate
+a declaration for the `fold` method. This method takes on a different form,
+depending on the structure of the operation.
+
+```tablegen
+def MyOp : ... {
+  let hasFolder = 1;
+}
+```
+
+If the operation has a single result the following will be generated:
+
+```c++
+/// Implementations of this hook can only perform the following changes to the
+/// operation:
+///
+///  1. They can leave the operation alone and without changing the IR, and
+///     return nullptr.
+///  2. They can mutate the operation in place, without changing anything else
+///     in the IR. In this case, return the operation itself.
+///  3. They can return an existing value or attribute that can be used instead
+///     of the operation. The caller will remove the operation and use that
+///     result instead.
+///
+OpFoldResult MyOp::fold(ArrayRef<Attribute> operands) {
+  ...
+}
+```
+
+Otherwise, the following is generated:
+
+```c++
+/// Implementations of this hook can only perform the following changes to the
+/// operation:
+///
+///  1. They can leave the operation alone and without changing the IR, and
+///     return failure.
+///  2. They can mutate the operation in place, without changing anything else
+///     in the IR. In this case, return success.
+///  3. They can return a list of existing values or attribute that can be used
+///     instead of the operation. In this case, fill in the results list and
+///     return success. The results list must correspond 1-1 with the results of
+///     the operation, partial folding is not supported. The caller will remove
+///     the operation and use those results instead.
+///
+LogicalResult MyOp::fold(ArrayRef<Attribute> operands,
+                         SmallVectorImpl<OpFoldResult> &results) {
+  ...
+}
+```
+
+In the above, for each method an `ArrayRef<Attribute>` is provided that
+corresponds to the constant attribute value of each of the operands. These
+operands are those that implement the `ConstantLike` trait. If any of the
+operands are non-constant, a null `Attribute` value is provided instead. For
+example, if MyOp provides three operands [`a`, `b`, `c`], but only `b` is
+constant then `operands` will be of the form [Attribute(), b-value,
+Attribute()].
+
+Also above, is the use of `OpFoldResult`. This class represents the possible
+result of folding an operation result: either an SSA `Value`, or an
+`Attribute`(for a constant result). If an SSA `Value` is provided, it *must*
+correspond to an existing value. The `fold` methods are not permitted to
+generate new `Value`s. There are no specific restrictions on the form of the
+`Attribute` value returned, but it is important to ensure that the `Attribute`
+representation of a specific `Type` is consistent.
+
+#### Generating Constants from Attributes
+
+When a `fold` method returns an `Attribute` as the result, it signifies that
+this result is "constant". The `Attribute` is the constant representation of the
+value. Users of the `fold` method, such as the canonicalizer pass, will take
+these `Attribute`s and materialize constant operations in the IR to represent
+them. To enable this materialization, the dialect of the operation must
+implement the `materializeConstant` hook. This hook takes in an `Attribute`
+value, generally returned by `fold`, and produces a "constant-like" operation
+that materializes that value.
+
+In [ODS](OpDefinitions.md), a dialect can set the `hasConstantMaterializer` bit
+to generate a declaration for the `materializeConstant` method.
+
+```tablegen
+def MyDialect_Dialect : ... {
+  let hasConstantMaterializer = 1;
+}
+```
+
+Constants can then be materialized in the source file:
+
+```c++
+/// Hook to materialize a single constant operation from a given attribute value
+/// with the desired resultant type. This method should use the provided builder
+/// to create the operation without changing the insertion position. The
+/// generated operation is expected to be constant-like. On success, this hook
+/// should return the value generated to represent the constant value.
+/// Otherwise, it should return nullptr on failure.
+Operation *MyDialect::materializeConstant(OpBuilder &builder, Attribute value,
+                                          Type type, Location loc) {
+  ...
+}
+```