Introduce a ConditionallySpeculatable op interface
authorSanjoy Das <sanjoy.das@getcruise.com>
Thu, 6 Oct 2022 22:57:25 +0000 (15:57 -0700)
committerSanjoy Das <sanjoy.das@getcruise.com>
Wed, 12 Oct 2022 17:56:12 +0000 (10:56 -0700)
commit86771d0b65ee13242f89b8dfdf3c66f738eae4e5
tree084d8960661774b1ec302c7f4585696147b42a00
parent2eaf6f973cacd7f24691b72a9c6a3ee2a3d1a60b
Introduce a ConditionallySpeculatable op interface

This patch takes the first step towards a more principled modeling of undefined behavior in MLIR as discussed in the following discourse threads:

 1. https://discourse.llvm.org/t/semantics-modeling-undefined-behavior-and-side-effects/4812
 2. https://discourse.llvm.org/t/rfc-mark-tensor-dim-and-memref-dim-as-side-effecting/65729

This patch in particular does the following:

 1. Introduces a ConditionallySpeculatable OpInterface that dynamically determines whether an Operation can be speculated.
 2. Re-defines `NoSideEffect` to allow undefined behavior, making it necessary but not sufficient for speculation.  Also renames it to `NoMemoryEffect`.
 3. Makes LICM respect the above semantics.
 4. Changes all ops tagged with `NoSideEffect` today to additionally implement ConditionallySpeculatable and mark themselves as always speculatable.  This combined trait is named `Pure`.  This makes this change NFC.

For out of tree dialects:

 1. Replace `NoSideEffect` with `Pure` if the operation does not have any memory effects, undefined behavior or infinite loops.
 2. Replace `NoSideEffect` with `NoSideEffect` otherwise.

The next steps in this process are (I'm proposing to do these in upcoming patches):

 1. Update operations like `tensor.dim`, `memref.dim`, `scf.for`, `affine.for` to implement a correct hook for `ConditionallySpeculatable`.  I'm also happy to update ops in other dialects if the respective dialect owners would like to and can give me some pointers.
 2. Update other passes that speculate operations to consult `ConditionallySpeculatable` in addition to `NoMemoryEffect`.  I could not find any other than LICM on a quick skim, but I could have missed some.
 3. Add some documentation / FAQs detailing the differences between side effects, undefined behavior, speculatabilty.

Reviewed By: rriddle, mehdi_amini

Differential Revision: https://reviews.llvm.org/D135505
84 files changed:
mlir/docs/OpDefinitions.md
mlir/docs/Tutorials/QuickstartRewrites.md
mlir/docs/Tutorials/Toy/Ch-3.md
mlir/docs/Tutorials/Toy/Ch-4.md
mlir/examples/standalone/include/Standalone/StandaloneOps.td
mlir/examples/toy/Ch2/include/toy/Ops.td
mlir/examples/toy/Ch3/include/toy/Ops.td
mlir/examples/toy/Ch4/include/toy/Ops.td
mlir/examples/toy/Ch5/include/toy/Ops.td
mlir/examples/toy/Ch6/include/toy/Ops.td
mlir/examples/toy/Ch7/include/toy/Ops.td
mlir/include/mlir/Dialect/AMDGPU/AMDGPU.td
mlir/include/mlir/Dialect/AMX/AMX.td
mlir/include/mlir/Dialect/Affine/IR/AffineOps.td
mlir/include/mlir/Dialect/Arith/IR/ArithOps.td
mlir/include/mlir/Dialect/ArmNeon/ArmNeon.td
mlir/include/mlir/Dialect/ArmSVE/ArmSVE.td
mlir/include/mlir/Dialect/Async/IR/AsyncOps.td
mlir/include/mlir/Dialect/Bufferization/IR/BufferizationOps.td
mlir/include/mlir/Dialect/Complex/IR/ComplexOps.td
mlir/include/mlir/Dialect/ControlFlow/IR/ControlFlowOps.td
mlir/include/mlir/Dialect/EmitC/IR/EmitC.td
mlir/include/mlir/Dialect/Func/IR/FuncOps.td
mlir/include/mlir/Dialect/GPU/IR/GPUOps.td
mlir/include/mlir/Dialect/LLVMIR/LLVMIntrinsicOps.td
mlir/include/mlir/Dialect/LLVMIR/LLVMOpBase.td
mlir/include/mlir/Dialect/LLVMIR/LLVMOps.td
mlir/include/mlir/Dialect/LLVMIR/NVVMOps.td
mlir/include/mlir/Dialect/LLVMIR/ROCDLOps.td
mlir/include/mlir/Dialect/Linalg/IR/LinalgOps.td
mlir/include/mlir/Dialect/MLProgram/IR/MLProgramOps.td
mlir/include/mlir/Dialect/Math/IR/MathOps.td
mlir/include/mlir/Dialect/MemRef/IR/MemRefOps.td
mlir/include/mlir/Dialect/NVGPU/IR/NVGPU.td
mlir/include/mlir/Dialect/OpenMP/OpenMPOps.td
mlir/include/mlir/Dialect/PDL/IR/PDLOps.td
mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td
mlir/include/mlir/Dialect/Quant/QuantOps.td
mlir/include/mlir/Dialect/SCF/IR/SCFOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVArithmeticOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVBitOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVCLOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVCastOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVCompositeOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVControlFlowOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVCooperativeMatrixOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVGLOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVGroupOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVImageOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVJointMatrixOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVLogicalOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVMatrixOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVMemoryOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVMiscOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVNonUniformOps.td
mlir/include/mlir/Dialect/SPIRV/IR/SPIRVStructureOps.td
mlir/include/mlir/Dialect/Shape/IR/ShapeOps.td
mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorOps.td
mlir/include/mlir/Dialect/Tensor/IR/TensorOps.td
mlir/include/mlir/Dialect/Tosa/IR/TosaOps.td
mlir/include/mlir/Dialect/Tosa/IR/TosaUtilOps.td
mlir/include/mlir/Dialect/Transform/IR/TransformOps.td
mlir/include/mlir/Dialect/Vector/IR/VectorOps.td
mlir/include/mlir/Dialect/X86Vector/X86Vector.td
mlir/include/mlir/IR/BuiltinOps.td
mlir/include/mlir/Interfaces/SideEffectInterfaceBase.td
mlir/include/mlir/Interfaces/SideEffectInterfaces.h
mlir/include/mlir/Interfaces/SideEffectInterfaces.td
mlir/include/mlir/Transforms/SideEffectUtils.h
mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp
mlir/lib/Dialect/Affine/Utils/Utils.cpp
mlir/lib/Dialect/MemRef/IR/MemRefOps.cpp
mlir/lib/Dialect/Vector/Transforms/VectorDistribute.cpp
mlir/lib/Dialect/Vector/Transforms/VectorTransferOpTransforms.cpp
mlir/lib/Interfaces/SideEffectInterfaces.cpp
mlir/lib/Transforms/ControlFlowSink.cpp
mlir/lib/Transforms/Utils/LoopInvariantCodeMotionUtils.cpp
mlir/lib/Transforms/Utils/SideEffectUtils.cpp
mlir/test/Transforms/loop-invariant-code-motion.mlir
mlir/test/lib/Dialect/Test/TestOps.td
mlir/test/lib/Dialect/Transform/TestTransformDialectExtension.td
mlir/test/mlir-tblgen/gen-dialect-doc.td
mlir/test/mlir-tblgen/llvm-intrinsics.td
mlir/tools/mlir-tblgen/LLVMIRIntrinsicGen.cpp