# About SideEffect & Speculation

MLIRのOperationsには暗黙的振舞いを持つものがたくさん存在し、これらは最適化パスの実行有無に影響を与える。Operatorを定義する際にはこの暗黙的振る舞い、つまりSideEffectの有無を指定する必要があり、SideEffectがあるかないかによって最適化の実行有無が決定される（e.g. [Rematerialization](https://en.wikipedia.org/wiki/Rematerialization)）。

この暗黙的振舞いは大きく4つに分類される:

1. **Operations with Memory Effects**
These operations read from and write to some mutable system resource, e.g. the heap, the stack, HW registers, the console. They may also interact with the heap in other ways, like by allocating and freeing memory.
**E.g.** standard memory reads and writes, printf (which can be modeled as “writing” to the console and reading from the input buffers).
1. **Operations with undefined behavior.**
These operations are not defined on certain inputs or in some situations – we do not specify what happens when such illegal inputs are passed, and instead say that behavior is undefined and can assume it does not happen. In practice, in such cases these ops may do anything from producing garbage results to crashing the program or corrupting memory.
**E.g.** integer division which has UB when dividing by zero, loading from a pointer that has been freed.
1. **Operations that don’t terminate.**
**E.g.** an scf.while where the condition is always true.
1. **Operations with non-local control flow.**
These operations may pop their current frame of execution and return directly to an older frame.
**E.g.** longjmp, operations that throw exceptions.

> from https://mlir.llvm.org/docs/Rationale/SideEffectsAndSpeculation/#categorization

まとめると、1.Memory Effect/2.未定義動作/3.無限ループ等のTerminateのない命令/4.Long jumpする命令の4つが暗黙的振舞いとして扱われている。これらの4を除く暗黙的振舞いをOperationsが持つかどうかを判断するためのInterfaceとして、`SideEffectInterface`があり、このInterfaceは大きく`SideMemoryEffect`と`Speculation`の二つの性質を持つ。そして、それぞれのInterfaceとして、`MemoryEffectsOpInterface`と`ConditionallySpeculatable`がある:

- **MemoryEffectsOpInterface**: MemoryEffectをtrackingするためのIF
- **ConditionallySpeculatable**: 未定義動作と無限ループをtrackingするためのIF

## SideMemoryEffect
`SideMemoryEffect`は任意の確保したメモリ領域のリソースに対する作用の有無を表すものであり、

1. [MemAlloc](https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/SideEffectInterfaces.td#L48-L53)
2. [MemFree](https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/SideEffectInterfaces.td#L55-L60)
3. [MemRead](https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/SideEffectInterfaces.td#L62-L67)
4. [MemWrite](https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/SideEffectInterfaces.td#L69-L74)

の4つのEffectsを指定することができる。それぞれ指定したResourceに対するMemory操作を表すものである。SideEffectを持つ持たないをOpの定義で表すためのTraitは以下の通り:

// Op has no effect on memory but may have undefined behavior.
def NoMemoryEffect : MemoryEffects<[]>;

// Op has recursively computed side effects.
def RecursiveMemoryEffects : NativeOpTrait<"HasRecursiveMemoryEffects">;

`NoMemoryEffect`はMemoryEffectsに空リストを渡しているだけのTraitであり、これはSideMemoryEffectがないということを表している。

### e.g. MemoryEffects trait

def GPU_SetDefaultDeviceOp : GPU_Op<"set_default_device",
                                    [MemoryEffects<[MemWrite]>]>,
                                    Arguments<(ins I32:$devIndex)> {
  let summary = "Set default GPU for operations after this by index";
  let description = [{
    Operation that sets the current default GPU, using a zero-based index
    into the set of GPUs on the system. The default GPU setting may be
    thread-local.
  }];
  let assemblyFormat = "attr-dict $devIndex";
}

## Speculation
Speculationは投機実行の可否を表すためのものであり、未定義動作および無限ループ等がないことを要求する。`Speculatability`の有無は`ConditionallySpeculatable` Interfaceの`getSpeculatability`関数を実装することによって判定することができる。この`getSpeculatability`は以下の`Speculatability`のEnumを返すことでSpeculationが可能かどうかを見る。

/// This enum is returned from the `getSpeculatability` method in the
/// `ConditionallySpeculatable` op interface.
enum class Speculatability {
  /// The Operation in question cannot be speculatively executed.  This could be
  /// because it may invoke undefined behavior or have other side effects.
  NotSpeculatable,

  // The Operation in question can be speculatively executed.  It does not have
  // any side effects or undefined behavior.
  Speculatable,

  // The Operation in question can be speculatively executed if all the
  // operations in all attached regions can also be speculatively executed.
  RecursivelySpeculatable,
};

Opを定義する際にそのOpがSpeculationが可能かどうかをマークするためのTraitとしては、`AlwaysSpeculatable`/`RecursivelySpeculatable`をOpのtraitに指定する。

// Marks an Operation as always speculatable.
def AlwaysSpeculatable : TraitList<[
    ConditionallySpeculatable, AlwaysSpeculatableImplTrait]>;

// Marks an Operation as speculatable only if all the operations in all attached
// regions are also speculatable.
def RecursivelySpeculatable : TraitList<[
    ConditionallySpeculatable, RecursivelySpeculatableImplTrait]>;

## Pure
`SideMemoryEffect`がなく、常に`Speculatable`なOpを示す場合は、Traitに`Pure`を指定する。

// Always speculatable operation that does not touch memory.  These operations
// are always legal to hoist or sink.
def Pure : TraitList<[AlwaysSpeculatable, NoMemoryEffect]>;

##

---
## Version
- commit: [dfdfd306cfaf54fbc43e2d5eb36489dac3eb9976](https://github.com/llvm/llvm-project/tree/dfdfd306cfaf54fbc43e2d5eb36489dac3eb9976)

## Reference
- [llvm-project/mlir/include/mlir/Interfaces/SideEffectInterfaces.h](https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/SideEffectInterfaces.h)
- [llvm-project/mlir/include/mlir/Interfaces/SideEffectInterfaces.td](https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/SideEffectInterfaces.td)
- [llvm-project/mlir/include/mlir/Interfaces/SideEffectInterfaceBase.td](https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/SideEffectInterfaceBase.td)