mlir/docs/Canonicalization.md

   1 # Operation Canonicalization in MLIR
   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
  48 *   Move constant operands to commutative binary operators to the right side -
  49     e.g. "(addi 4, x)" to "(addi x, 4)".
  50
  51 ## Builtin Ops Canonicalizations
  52
  53 These transformations are applied to builtin ops:
  54
  55 *   `constant` ops are uniqued and hoisted into the entry block of the first
  56     parent region that is isolated from above, e.g. the entry block of a
  57     function.
  58 *   (TODO) Merge `affine.apply` operations that directly feed each other.
  59
  60 ## Standard Ops Canonicalizations
  61
  62 *   Shape folding of `alloc` operations to turn dynamic dimensions into static
  63     ones.
  64 *   Folding `memref_cast` operations into users where possible.