mlir/docs/Rationale/SideEffectsAndSpeculation.md

   1 # Side Effects & Speculation
   2
   3 This document outlines how MLIR models side effects and how speculation works in
   4 MLIR.
   5
   6 This rationale only applies to operations used in
   7 [CFG regions](../LangRef.md/#control-flow-and-ssacfg-regions). Side effect
   8 modeling in [graph regions](../LangRef.md/#graph-regions) is TBD.
   9
  10 [TOC]
  11
  12 ## Overview
  13
  14 Many MLIR operations don't exhibit any behavior other than consuming and
  15 producing SSA values. These operations can be reordered with other operations as
  16 long as they obey SSA dominance requirements and can be eliminated or even
  17 introduced (e.g. for
  18 [rematerialization](https://en.wikipedia.org/wiki/Rematerialization)) as needed.
  19
  20 However, a subset of MLIR operations have implicit behavior than isn't reflected
  21 in their SSA data-flow semantics. These operations need special handing, and
  22 cannot be reordered, eliminated or introduced without additional analysis.
  23
  24 This doc introduces a categorization of these operations and shows how these
  25 operations are modeled in MLIR.
  26
  27 ## Categorization
  28
  29 Operations with implicit behaviors can be broadly categorized as follows:
  30
  31 1. Operations with memory effects. These operations read from and write to some
  32    mutable system resource, e.g. the heap, the stack, HW registers, the console.
  33    They may also interact with the heap in other ways, like by allocating and
  34    freeing memory. E.g. standard memory reads and writes, `printf` (which can be
  35    modeled as "writing" to the console and reading from the input buffers).
  36 1. Operations with undefined behavior. These operations are not defined on
  37    certain inputs or in some situations -- we do not specify what happens when
  38    such illegal inputs are passed, and instead say that behavior is undefined
  39    and can assume it does not happen. In practice, in such cases these ops may
  40    do anything from producing garbage results to crashing the program or
  41    corrupting memory. E.g. integer division which has UB when dividing by zero,
  42    loading from a pointer that has been freed.
  43 1. Operations that don't terminate. E.g. an `scf.while` where the condition is
  44    always true.
  45 1. Operations with non-local control flow. These operations may pop their
  46    current frame of execution and return directly to an older frame. E.g.
  47    `longjmp`, operations that throw exceptions.
  48
  49 Finally, a given operation may have a combination of the above implicit
  50 behaviors. The combination of implicit behaviors during the execution of the
  51 operation may be ordered. We use 'stage' to label the order of implicit
  52 behaviors during the execution of 'op'. Implicit behaviors with a lower stage
  53 number happen earlier than those with a higher stage number.
  54
  55 ## Modeling
  56
  57 Modeling these behaviors has to walk a fine line -- we need to empower more
  58 complicated passes to reason about the nuances of such behaviors while
  59 simultaneously not overburdening simple passes that only need a coarse grained
  60 "can this op be freely moved" query.
  61
  62 MLIR has two op interfaces to represent these implicit behaviors:
  63
  64 1. The
  65    [`MemoryEffectsOpInterface` op interface](https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/SideEffectInterfaces.td#L26)
  66    is used to track memory effects.
  67 1. The
  68    [`ConditionallySpeculatable` op interface](https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/SideEffectInterfaces.td#L105)
  69    is used to track undefined behavior and infinite loops.
  70
  71 Both of these are op interfaces which means operations can dynamically
  72 introspect themselves (e.g. by checking input types or attributes) to infer what
  73 memory effects they have and whether they are speculatable.
  74
  75 We don't have proper modeling yet to fully capture non-local control flow
  76 semantics.
  77
  78 When adding a new op, ask:
  79
  80 1. Does it read from or write to the heap or stack? It should probably implement
  81    `MemoryEffectsOpInterface`.
  82 1. Are these side effects ordered? The op should probably set the stage of
  83    side effects to make analyses more accurate.
  84 1. Do these side effects act on every single value of a resource? It probably
  85    should set the FullEffect on effect.
  86 1. Does it have side effects that must be preserved, like a volatile store or a
  87    syscall? It should probably implement `MemoryEffectsOpInterface` and model
  88    the effect as a read from or write to an abstract `Resource`. Please start an
  89    RFC if your operation has a novel side effect that cannot be adequately
  90    captured by `MemoryEffectsOpInterface`.
  91 1. Is it well defined in all inputs or does it assume certain runtime
  92    restrictions on its inputs, e.g. the pointer operand must point to valid
  93    memory? It should probably implement `ConditionallySpeculatable`.
  94 1. Can it infinitely loop on certain inputs? It should probably implement
  95    `ConditionallySpeculatable`.
  96 1. Does it have non-local control flow (e.g. `longjmp`)? We don't have proper
  97    modeling for these yet, patches welcome!
  98 1. Is your operation free of side effects and can be freely hoisted, introduced
  99    and eliminated? It should probably be marked `Pure`. (TODO: revisit this name
 100    since it has overloaded meanings in C++.)
 101
 102 ## Examples
 103
 104 This section describes a few very simple examples that help understand how to
 105 add side effect correctly.
 106
 107 ### SIMD compute operation
 108
 109 Consider a SIMD backend dialect with a "simd.abs" operation which reads all
 110 values from the source memref, calculates their absolute values, and writes them
 111 to the target memref:
 112
 113 ```mlir
 114   func.func @abs(%source : memref<10xf32>, %target : memref<10xf32>) {
 115     simd.abs(%source, %target) : memref<10xf32> to memref<10xf32>
 116     return
 117   }
 118 ```
 119
 120 The abs operation reads each individual value from the source resource and then
 121 writes these values to each corresponding value in the target resource.
 122 Therefore, we need to specify a read side effect for the source and a write side
 123 effect for the target. The read side effect occurs before the write side effect,
 124 so we need to mark the read stage as earlier than the write stage. Additionally,
 125 we need to indicate that these side effects apply to each individual value in
 126 the resource.
 127
 128 A typical approach is as follows:
 129 ``` mlir
 130   def AbsOp : SIMD_Op<"abs", [...] {
 131     ...
 132
 133     let arguments = (ins Arg<AnyRankedOrUnrankedMemRef, "the source memref",
 134                              [MemReadAt<0, FullEffect>]>:$source,
 135                          Arg<AnyRankedOrUnrankedMemRef, "the target memref",
 136                              [MemWriteAt<1, FullEffect>]>:$target);
 137
 138     ...
 139   }
 140 ```
 141
 142 In the above example, we attach the side effect `[MemReadAt<0, FullEffect>]` to
 143 the source, indicating that the abs operation reads each individual value from
 144 the source during stage 0. Likewise, we attach the side effect
 145 `[MemWriteAt<1, FullEffect>]` to the target, indicating that the abs operation
 146 writes to each individual value within the target during stage 1 (after reading
 147 from the source).
 148
 149 ### Load like operation
 150
 151 Memref.load is a typical load like operation:
 152 ```mlir
 153   func.func @foo(%input : memref<10xf32>, %index : index) -> f32 {
 154     %result = memref.load  %input[index] : memref<10xf32>
 155     return %result : f32
 156   }
 157 ```
 158
 159 The load like operation reads a single value from the input memref and returns
 160 it. Therefore, we need to specify a partial read side effect for the input
 161 memref, indicating that not every single value is used.
 162
 163 A typical approach is as follows:
 164 ``` mlir
 165   def LoadOp : MemRef_Op<"load", [...] {
 166     ...
 167
 168     let arguments = (ins Arg<AnyMemRef, "the reference to load from",
 169                              [MemReadAt<0, PartialEffect>]>:$memref,
 170                          Variadic<Index>:$indices,
 171                          DefaultValuedOptionalAttr<BoolAttr, "false">:$nontemporal);
 172
 173     ...
 174   }
 175 ```
 176
 177 In the above example, we attach the side effect `[MemReadAt<0, PartialEffect>]` to
 178 the source, indicating that the load operation reads parts of values from the
 179 memref during stage 0. Since side effects typically occur at stage 0 and are
 180 partial by default, we can abbreviate it as `[MemRead]`.