[mlir][SideEffects] Mark the CFG only terminator operations as NoSideEffect

[rriddle]

Summary

These terminator operations don't really have any side effects, and this allows for more accurate side-effect analysis for region operations. For example, currently we can't detect like a loop.for or affine.for are dead because the affine.terminator is "side effecting".

Note: Marking as NoSideEffect doesn't mean that these operations can be opaquely erased.

Depends On D75886

[mehdi_amini]

The plan is to get rid of NoSideEffect right? Are you just taking a temporary detour here?

[rriddle]

In D75888#1913757, @mehdi_amini wrote:

The plan is to get rid of NoSideEffect right? Are you just taking a temporary detour here?

Essentially yes. I'm building up the necessary infra for replacing Operation::hasNoSideEffect with something more powerful. Setting that up will make it much easier to transition things.

[herhut]

For the dialects I am involved with this looks reasonable.

mlir/lib/Transforms/CSE.cpp

127

This might still simplify terminator operations that we do not identify as those. Is the idea that those still have to remain side-effecting? Or will this be fixed in a future iteration with more detailed modelling?

[rriddle]

mlir/lib/Transforms/CSE.cpp

127

CSE/DCE doesn't modify the CFG(terminators) generally, so this check will remain the same regardless of effect modeling.

mlir/examples/toy/Ch2/include/toy/Ops.td

def ReshapeOp : Toy_Op<"reshape"> {
   // We expect that the reshape operation returns a statically shaped tensor.
   let results = (outs StaticShapeTensorOf<[F64]>);
 
   let assemblyFormat = [{
     `(` $input `:` type($input) `)` attr-dict `to` type(results)
   }];
 }
 
-def ReturnOp : Toy_Op<"return", [Terminator, HasParent<"FuncOp">]> {
+def ReturnOp : Toy_Op<"return", [NoSideEffect, HasParent<"FuncOp">,
+                                 Terminator]> {
   let summary = "return operation";
   let description = [{
     The "return" operation represents a return operation within a function.
     The operation takes an optional tensor operand and produces no results.
     The operand type must match the signature of the function that contains
     the operation. For example:
 
     ```mlir

mlir/examples/toy/Ch3/include/toy/Ops.td

def ReshapeOp : Toy_Op<"reshape", [NoSideEffect]> {
   let assemblyFormat = [{
     `(` $input `:` type($input) `)` attr-dict `to` type(results)
   }];
 
   // Enable registering canonicalization patterns with this operation.
   let hasCanonicalizer = 1;
 }
 
-def ReturnOp : Toy_Op<"return", [Terminator, HasParent<"FuncOp">]> {
+def ReturnOp : Toy_Op<"return", [NoSideEffect, HasParent<"FuncOp">,
+                                 Terminator]> {
   let summary = "return operation";
   let description = [{
     The "return" operation represents a return operation within a function.
     The operation takes an optional tensor operand and produces no results.
     The operand type must match the signature of the function that contains
     the operation. For example:
 
     ```mlir

mlir/examples/toy/Ch4/include/toy/Ops.td

def ReshapeOp : Toy_Op<"reshape", [NoSideEffect]> {
   let assemblyFormat = [{
     `(` $input `:` type($input) `)` attr-dict `to` type(results)
   }];
 
   // Enable registering canonicalization patterns with this operation.
   let hasCanonicalizer = 1;
 }
 
-def ReturnOp : Toy_Op<"return", [Terminator, HasParent<"FuncOp">]> {
+def ReturnOp : Toy_Op<"return", [NoSideEffect, HasParent<"FuncOp">,
+                                 Terminator]> {
   let summary = "return operation";
   let description = [{
     The "return" operation represents a return operation within a function.
     The operation takes an optional tensor operand and produces no results.
     The operand type must match the signature of the function that contains
     the operation. For example:
 
     ```mlir

mlir/examples/toy/Ch5/include/toy/Ops.td

def ReshapeOp : Toy_Op<"reshape", [NoSideEffect]> {
   let assemblyFormat = [{
     `(` $input `:` type($input) `)` attr-dict `to` type(results)
   }];
 
   // Enable registering canonicalization patterns with this operation.
   let hasCanonicalizer = 1;
 }
 
-def ReturnOp : Toy_Op<"return", [Terminator, HasParent<"FuncOp">]> {
+def ReturnOp : Toy_Op<"return", [NoSideEffect, HasParent<"FuncOp">,
+                                 Terminator]> {
   let summary = "return operation";
   let description = [{
     The "return" operation represents a return operation within a function.
     The operation takes an optional tensor operand and produces no results.
     The operand type must match the signature of the function that contains
     the operation. For example:
 
     ```mlir

mlir/examples/toy/Ch6/include/toy/Ops.td

def ReshapeOp : Toy_Op<"reshape", [NoSideEffect]> {
 
   // Enable registering canonicalization patterns with this operation.
   let hasCanonicalizer = 1;
 
   // We expect that the reshape operation returns a statically shaped tensor.
   let results = (outs StaticShapeTensorOf<[F64]>);
 }
 
-def ReturnOp : Toy_Op<"return", [Terminator, HasParent<"FuncOp">]> {
+def ReturnOp : Toy_Op<"return", [NoSideEffect, HasParent<"FuncOp">,
+                                 Terminator]> {
   let summary = "return operation";
   let description = [{
     The "return" operation represents a return operation within a function.
     The operation takes an optional tensor operand and produces no results.
     The operand type must match the signature of the function that contains
     the operation. For example:
 
     ```mlir

mlir/examples/toy/Ch7/include/toy/Ops.td

def ReshapeOp : Toy_Op<"reshape", [NoSideEffect]> {
 
   // Enable registering canonicalization patterns with this operation.
   let hasCanonicalizer = 1;
 
   // We expect that the reshape operation returns a statically shaped tensor.
   let results = (outs StaticShapeTensorOf<[F64]>);
 }
 
-def ReturnOp : Toy_Op<"return", [Terminator, HasParent<"FuncOp">]> {
+def ReturnOp : Toy_Op<"return", [NoSideEffect, HasParent<"FuncOp">,
+                                 Terminator]> {
   let summary = "return operation";
   let description = [{
     The "return" operation represents a return operation within a function.
     The operation takes an optional operand and produces no results.
     The operand type must match the signature of the function that contains
     the operation. For example:
 
     ```mlir

mlir/include/mlir/Dialect/AffineOps/AffineOps.td

let extraClassDeclaration = [{
     static StringRef getIsDataCacheAttrName() { return "isDataCache"; }
   }];
 
   let hasCanonicalizer = 1;
   let hasFolder = 1;
 }
 
 def AffineTerminatorOp :
-    Affine_Op<"terminator", [Terminator]> {
+    Affine_Op<"terminator", [NoSideEffect, Terminator]> {
   let summary = "affine terminator operation";
   let description = [{
     Affine terminator is a special terminator operation for blocks inside affine
     loops and branches. It unconditionally transmits the control flow to the
     successor of the operation enclosing the region.
 
     This operation does _not_ have a custom syntax. However, affine control
     operations omit the terminator in their custom syntax for brevity.

mlir/include/mlir/Dialect/GPU/GPUOps.td

let extraClassDeclaration = [{
     static constexpr unsigned kNumConfigRegionAttributes = 12;
   }];
 
   let parser = [{ return parseLaunchOp(parser, result); }];
   let printer = [{ printLaunchOp(p, *this); }];
   let verifier = [{ return ::verify(*this); }];
 }
 
-def GPU_ReturnOp : GPU_Op<"return", [HasParent<"GPUFuncOp">, Terminator]>,
+def GPU_ReturnOp : GPU_Op<"return", [HasParent<"GPUFuncOp">, NoSideEffect,
+                                     Terminator]>,
     Arguments<(ins Variadic<AnyType>:$operands)>, Results<(outs)> {
   let summary = "Terminator for GPU functions.";
   let description = [{
     A terminator operation for regions that appear in the body of  `gpu.func`
     functions. The operands to the `gpu.return` are the result values returned
     by an incovation of the `gpu.func`.
   }];
 
   let builders = [OpBuilder<"Builder *builder, OperationState &result", " // empty">];
 
   let parser = [{ return parseReturnOp(parser, result); }];
   let printer = [{ p << getOperationName(); }];
   let verifier = [{ return ::verify(*this); }];
 }
 
-def GPU_TerminatorOp : GPU_Op<"terminator", [HasParent<"LaunchOp">, Terminator]>,
+def GPU_TerminatorOp : GPU_Op<"terminator", [HasParent<"LaunchOp">,
+                                             NoSideEffect, Terminator]>,
     Arguments<(ins)>, Results<(outs)> {
   let summary = "Terminator for GPU launch regions.";
   let description = [{
     A terminator operation for regions that appear in the body of `gpu.launch`
     operation.  These regions are not expected to return any value so the
     terminator takes no operands.
   }];
 
   let parser = [{ return success(); }];
   let printer = [{ p << getOperationName(); }];
 }
 
-def GPU_YieldOp : GPU_Op<"yield", [Terminator]>,
+def GPU_YieldOp : GPU_Op<"yield", [NoSideEffect, Terminator]>,
     Arguments<(ins Variadic<AnyType>:$values)> {
   let summary = "GPU yield operation";
   let description = [{
     "gpu.yield" is a special terminator operation for blocks inside regions
     in gpu ops. It returns values to the immediately enclosing gpu op.
 
     Example:
 

mlir/include/mlir/Dialect/LLVMIR/LLVMOps.td

 def LLVM_FreezeOp : LLVM_OneResultOp<"freeze", [SameOperandsAndResultType]>,
                     Arguments<(ins LLVM_Type:$val)> {
   let assemblyFormat = "$val attr-dict `:` type($val)";
   string llvmBuilder = "builder.CreateFreeze($val);";
 }
 
 // Terminators.
 def LLVM_BrOp : LLVM_TerminatorOp<"br",
-    [DeclareOpInterfaceMethods<BranchOpInterface>]> {
+    [DeclareOpInterfaceMethods<BranchOpInterface>, NoSideEffect]> {
   let arguments = (ins Variadic<LLVM_Type>:$destOperands);
   let successors = (successor AnySuccessor:$dest);
   let assemblyFormat = [{
     $dest (`(` $destOperands^ `:` type($destOperands) `)`)? attr-dict
   }];
   let builders = [LLVM_TerminatorPassthroughOpBuilder];
 }
 def LLVM_CondBrOp : LLVM_TerminatorOp<"cond_br",
-    [AttrSizedOperandSegments, DeclareOpInterfaceMethods<BranchOpInterface>]> {
+    [AttrSizedOperandSegments, DeclareOpInterfaceMethods<BranchOpInterface>,
+     NoSideEffect]> {
   let arguments = (ins LLVMI1:$condition,
                    Variadic<LLVM_Type>:$trueDestOperands,
                    Variadic<LLVM_Type>:$falseDestOperands);
   let successors = (successor AnySuccessor:$trueDest, AnySuccessor:$falseDest);
   let assemblyFormat = [{
     $condition `,`
     $trueDest (`(` $trueDestOperands^ `:` type($trueDestOperands) `)`)? `,`
     $falseDest (`(` $falseDestOperands^ `:` type($falseDestOperands) `)`)?
     attr-dict
   }];
 
   let builders = [OpBuilder<
     "Builder *builder, OperationState &result, Value condition,"
     "Block *trueDest, ValueRange trueOperands,"
     "Block *falseDest, ValueRange falseOperands", [{
       build(builder, result, condition, trueOperands, falseOperands, trueDest,
             falseDest);
   }]>, OpBuilder<
     "Builder *builder, OperationState &result, Value condition,"
     "Block *trueDest, Block *falseDest, ValueRange falseOperands = {}", [{
       build(builder, result, condition, trueDest, ValueRange(), falseDest,
             falseOperands);
   }]>, LLVM_TerminatorPassthroughOpBuilder];
 }
-def LLVM_ReturnOp : LLVM_TerminatorOp<"return", []>,
+def LLVM_ReturnOp : LLVM_TerminatorOp<"return", [NoSideEffect]>,
                     Arguments<(ins Variadic<LLVM_Type>:$args)> {
   string llvmBuilder = [{
     if ($_numOperands != 0)
       builder.CreateRet($args[0]);
     else
       builder.CreateRetVoid();
   }];
 

mlir/include/mlir/Dialect/Linalg/IR/LinalgOps.td

def Linalg_TransposeOp : Linalg_Op<"transpose", [NoSideEffect]>,
   let extraClassDeclaration = [{
     static StringRef getPermutationAttrName() { return "permutation"; }
     ShapedType getShapedType() { return view().getType().cast<ShapedType>(); }
   }];
 
   let hasFolder = 1;
 }
 
-def Linalg_YieldOp : Linalg_Op<"yield", [NativeOpTrait<"IsTerminator">]>,
+def Linalg_YieldOp : Linalg_Op<"yield", [NoSideEffect, Terminator]>,
     Arguments<(ins Variadic<AnyType>:$values)> {
   let summary = "Linalg yield operation";
   let description = [{
     `linalg.yield` is a special terminator operation for blocks inside regions
     in `linalg` generic ops. It returns values to the immediately enclosing
     `linalg` generic op.
 
     Example:
 
     ```mlir
        linalg.yield %f0, %f1 : f32, f32
     ```
   }];
 }
 
 #endif // LINALG_OPS

mlir/include/mlir/Dialect/LoopOps/LoopOps.td

OpBuilder<"Builder *builder, OperationState &result, "
               "Value operand">
   ];
 
   let arguments = (ins AnyType:$operand);
   let regions = (region SizedRegion<1>:$reductionOperator);
 }
 
 def ReduceReturnOp :
-    Loop_Op<"reduce.return", [HasParent<"ReduceOp">, Terminator]> {
+    Loop_Op<"reduce.return", [HasParent<"ReduceOp">, NoSideEffect,
+                              Terminator]> {
   let summary = "terminator for reduce operation";
   let description = [{
     "loop.reduce.return" is a special terminator operation for the block inside
     "loop.reduce". It terminates the region. It should have the same type as
     the operand of "loop.reduce". Example for the custom format:
 
     ```mlir
       loop.reduce.return %res : f32
     ```
   }];
 
   let arguments = (ins AnyType:$result);
   let assemblyFormat = "$result attr-dict `:` type($result)";
 }
 
-def YieldOp : Loop_Op<"yield", [Terminator]> {
+def YieldOp : Loop_Op<"yield", [NoSideEffect, Terminator]> {
   let summary = "loop yield and termination operation";
   let description = [{
     "loop.yield" yields an SSA value from a loop dialect op region and
     terminates the regions. The semantics of how the values are yielded
     is defined by the parent operation.
     If "loop.yield" has any operands, the operands must match the parent
     operation's results.
     If the parent operation defines no values, then the "loop.yield" may be

mlir/include/mlir/Dialect/SPIRV/SPIRVControlFlowOps.td

 
 include "mlir/Dialect/SPIRV/SPIRVBase.td"
 include "mlir/Interfaces/CallInterfaces.td"
 include "mlir/Interfaces/ControlFlowInterfaces.td"
 
 // -----
 
 def SPV_BranchOp : SPV_Op<"Branch", [
-    DeclareOpInterfaceMethods<BranchOpInterface>, InFunctionScope,
+    DeclareOpInterfaceMethods<BranchOpInterface>, InFunctionScope, NoSideEffect,
     Terminator]> {
   let summary = "Unconditional branch to target block.";
 
   let description = [{
     This instruction must be the last instruction in a block.
 
     ### Custom assembly form
 
let assemblyFormat = [{
     $target (`(` $targetOperands^ `:` type($targetOperands) `)`)? attr-dict
   }];
 }
 
 // -----
 
 def SPV_BranchConditionalOp : SPV_Op<"BranchConditional", [
     AttrSizedOperandSegments, DeclareOpInterfaceMethods<BranchOpInterface>,
-    InFunctionScope, Terminator]> {
+    InFunctionScope, NoSideEffect, Terminator]> {
   let summary = [{
     If Condition is true, branch to true block, otherwise branch to false
     block.
   }];
 
   let description = [{
     Condition must be a Boolean type scalar.
 
def SPV_LoopOp : SPV_Op<"loop", [InFunctionScope]> {
 
   let hasOpcode = 0;
 
   let autogenSerialization = 0;
 }
 
 // -----
 
-def SPV_MergeOp : SPV_Op<"_merge", [Terminator]> {
+def SPV_MergeOp : SPV_Op<"_merge", [NoSideEffect, Terminator]> {
   let summary = "A special terminator for merging a structured selection/loop.";
 
   let description = [{
     We use `spv.selection`/`spv.loop` for modelling structured selection/loop.
     This op is a terminator used inside their regions to mean jumping to the
     merge point, which is the next op following the `spv.selection` or
     `spv.loop` op. This op does not have a corresponding instruction in the
     SPIR-V binary format; it's solely for structural purpose.
   }];
 
   let arguments = (ins);
 
   let results = (outs);
 
   let assemblyFormat = "attr-dict";
 
   let hasOpcode = 0;
 
   let autogenSerialization = 0;
 }
 
 // -----
 
-def SPV_ReturnOp : SPV_Op<"Return", [InFunctionScope, Terminator]> {
+def SPV_ReturnOp : SPV_Op<"Return", [InFunctionScope, NoSideEffect,
+                                     Terminator]> {
   let summary = "Return with no value from a function with void return type.";
 
   let description = [{
     This instruction must be the last instruction in a block.
 
     ### Custom assembly form
 
     ```
def SPV_UnreachableOp : SPV_Op<"Unreachable", [InFunctionScope, Terminator]> {
 
   let results = (outs);
 
   let assemblyFormat = "attr-dict";
 }
 
 // -----
 
-def SPV_ReturnValueOp : SPV_Op<"ReturnValue", [InFunctionScope, Terminator]> {
+def SPV_ReturnValueOp : SPV_Op<"ReturnValue", [InFunctionScope, NoSideEffect,
+                                               Terminator]> {
   let summary = "Return a value from a function.";
 
   let description = [{
     Value is the value returned, by copy, and must match the Return Type
     operand of the OpTypeFunction type of the OpFunction body this return
     instruction is in.
 
     This instruction must be the last instruction in a block.

mlir/include/mlir/Dialect/StandardOps/IR/Ops.td

def AtomicRMWOp : Std_Op<"atomic_rmw", [
   }];
 }
 
 //===----------------------------------------------------------------------===//
 // BranchOp
 //===----------------------------------------------------------------------===//
 
 def BranchOp : Std_Op<"br",
-    [DeclareOpInterfaceMethods<BranchOpInterface>, Terminator]> {
+    [DeclareOpInterfaceMethods<BranchOpInterface>, NoSideEffect, Terminator]> {
   let summary = "branch operation";
   let description = [{
     The "br" operation represents a branch operation in a function.
     The operation takes variable number of operands and produces no results.
     The operand number and types for each successor must match the arguments of
     the block successor. For example:
 
       ^bb2:

 }
 
 //===----------------------------------------------------------------------===//
 // CondBranchOp
 //===----------------------------------------------------------------------===//
 
 def CondBranchOp : Std_Op<"cond_br",
     [AttrSizedOperandSegments, DeclareOpInterfaceMethods<BranchOpInterface>,
-     Terminator]> {
+     NoSideEffect, Terminator]> {
   let summary = "conditional branch operation";
   let description = [{
     The "cond_br" operation represents a conditional branch operation in a
     function. The operation takes variable number of operands and produces
     no results. The operand number and types for each successor must match the
     arguments of the block successor. For example:
 
       ^bb0:

 def RemFOp : FloatArithmeticOp<"remf"> {
   let summary = "floating point division remainder operation";
 }
 
 //===----------------------------------------------------------------------===//
 // ReturnOp
 //===----------------------------------------------------------------------===//
 
-def ReturnOp : Std_Op<"return", [Terminator, HasParent<"FuncOp">]> {
+def ReturnOp : Std_Op<"return", [NoSideEffect, HasParent<"FuncOp">,
+                                 Terminator]> {
   let summary = "return operation";
   let description = [{
     The "return" operation represents a return operation within a function.
     The operation takes variable number of operands and produces no results.
     The operand number and types must match the signature of the function
     that contains the operation. For example:
 
       func @foo() : (i32, f8) {

mlir/lib/Transforms/CSE.cpp

private:
   /// Statistics for CSE.
   Statistic numCSE{this, "num-cse'd", "Number of operations CSE'd"};
   Statistic numDCE{this, "num-dce'd", "Number of operations trivially DCE'd"};
 };
 } // end anonymous namespace
 
 /// Attempt to eliminate a redundant operation.
 LogicalResult CSE::simplifyOperation(ScopedMapTy &knownValues, Operation *op) {
+  // Don't simplify terminator operations.
+  if (op->isKnownTerminator())
+    return failure();
+
   // Don't simplify operations with nested blocks. We don't currently model
   // equality comparisons correctly among other things. It is also unclear
   // whether we would want to CSE such operations.
   if (op->getNumRegions() != 0)
     return failure();
 
   // TODO(riverriddle) We currently only eliminate non side-effecting
   // operations.

mlir/lib/Transforms/Utils/GreedyPatternRewriteDriver.cpp

while (!worklist.empty()) {
 
       // Nulls get added to the worklist when operations are removed, ignore
       // them.
       if (op == nullptr)
         continue;
 
       // If the operation has no side effects, and no users, then it is
       // trivially dead - remove it.
-      if (op->hasNoSideEffect() && op->use_empty()) {
+      if (op->isKnownNonTerminator() && op->hasNoSideEffect() &&
+          op->use_empty()) {
         // Be careful to update bookkeeping.
         notifyOperationRemoved(op);
         op->erase();
         continue;
       }
 
       // Collects all the operands and result uses of the given `op` into work
       // list. Also remove `op` and nested ops from worklist.

mlir/lib/Transforms/Utils/LoopUtils.cpp

 // Return failure when any op fails to hoist.
 static LogicalResult hoistOpsBetween(loop::ForOp outer, loop::ForOp inner) {
   SetVector<Operation *> forwardSlice;
   getForwardSlice(outer.getOperation(), &forwardSlice, [&inner](Operation *op) {
     return op != inner.getOperation();
   });
   LogicalResult status = success();
   SmallVector<Operation *, 8> toHoist;
-  for (auto &op : outer.getBody()->getOperations()) {
+  for (auto &op : outer.getBody()->without_terminator()) {
     // Stop when encountering the inner loop.
     if (&op == inner.getOperation())
       break;
     // Skip over non-hoistable ops.
     if (forwardSlice.count(&op) > 0) {
       status = failure();
       continue;
     }