mlir/lib/Interfaces/SideEffectInterfaces.cpp

   1 //===- SideEffectInterfaces.cpp - SideEffects in MLIR ---------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "mlir/Interfaces/SideEffectInterfaces.h"
  10
  11 #include "mlir/IR/SymbolTable.h"
  12 #include "llvm/ADT/SmallPtrSet.h"
  13
  14 using namespace mlir;
  15
  16 //===----------------------------------------------------------------------===//
  17 // SideEffect Interfaces
  18 //===----------------------------------------------------------------------===//
  19
  20 /// Include the definitions of the side effect interfaces.
  21 #include "mlir/Interfaces/SideEffectInterfaces.cpp.inc"
  22
  23 //===----------------------------------------------------------------------===//
  24 // MemoryEffects
  25 //===----------------------------------------------------------------------===//
  26
  27 bool MemoryEffects::Effect::classof(const SideEffects::Effect *effect) {
  28   return isa<Allocate, Free, Read, Write>(effect);
  29 }
  30
  31 //===----------------------------------------------------------------------===//
  32 // SideEffect Utilities
  33 //===----------------------------------------------------------------------===//
  34
  35 bool mlir::isOpTriviallyDead(Operation *op) {
  36   return op->use_empty() && wouldOpBeTriviallyDead(op);
  37 }
  38
  39 /// Internal implementation of `mlir::wouldOpBeTriviallyDead` that also
  40 /// considers terminator operations as dead if they have no side effects. This
  41 /// allows for marking region operations as trivially dead without always being
  42 /// conservative of terminators.
  43 static bool wouldOpBeTriviallyDeadImpl(Operation *rootOp) {
  44   // The set of operations to consider when checking for side effects.
  45   SmallVector<Operation *, 1> effectingOps(1, rootOp);
  46   while (!effectingOps.empty()) {
  47     Operation *op = effectingOps.pop_back_val();
  48
  49     // If the operation has recursive effects, push all of the nested operations
  50     // on to the stack to consider.
  51     bool hasRecursiveEffects =
  52         op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();
  53     if (hasRecursiveEffects) {
  54       for (Region &region : op->getRegions()) {
  55         for (auto &block : region) {
  56           for (auto &nestedOp : block)
  57             effectingOps.push_back(&nestedOp);
  58         }
  59       }
  60     }
  61
  62     // If the op has memory effects, try to characterize them to see if the op
  63     // is trivially dead here.
  64     if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
  65       // Check to see if this op either has no effects, or only allocates/reads
  66       // memory.
  67       SmallVector<MemoryEffects::EffectInstance, 1> effects;
  68       effectInterface.getEffects(effects);
  69
  70       // Gather all results of this op that are allocated.
  71       SmallPtrSet<Value, 4> allocResults;
  72       for (const MemoryEffects::EffectInstance &it : effects)
  73         if (isa<MemoryEffects::Allocate>(it.getEffect()) && it.getValue() &&
  74             it.getValue().getDefiningOp() == op)
  75           allocResults.insert(it.getValue());
  76
  77       if (!llvm::all_of(effects, [&allocResults](
  78                                      const MemoryEffects::EffectInstance &it) {
  79             // We can drop effects if the value is an allocation and is a result
  80             // of the operation.
  81             if (allocResults.contains(it.getValue()))
  82               return true;
  83             // Otherwise, the effect must be a read.
  84             return isa<MemoryEffects::Read>(it.getEffect());
  85           })) {
  86         return false;
  87       }
  88       continue;
  89
  90       // Otherwise, if the op has recursive side effects we can treat the
  91       // operation itself as having no effects.
  92     }
  93     if (hasRecursiveEffects)
  94       continue;
  95
  96     // If there were no effect interfaces, we treat this op as conservatively
  97     // having effects.
  98     return false;
  99   }
 100
 101   // If we get here, none of the operations had effects that prevented marking
 102   // 'op' as dead.
 103   return true;
 104 }
 105
 106 template <typename EffectTy>
 107 bool mlir::hasSingleEffect(Operation *op, Value value) {
 108   auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
 109   if (!memOp)
 110     return false;
 111   SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
 112   memOp.getEffects(effects);
 113   bool hasSingleEffectOnVal = false;
 114   // Iterate through `effects` and check if an effect of type `EffectTy` and
 115   // only of that type is present. A `value` to check the effect on may or may
 116   // not have been provided.
 117   for (auto &effect : effects) {
 118     if (value && effect.getValue() != value)
 119       continue;
 120     hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());
 121     if (!hasSingleEffectOnVal)
 122       return false;
 123   }
 124   return hasSingleEffectOnVal;
 125 }
 126
 127 template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *,
 128                                                              Value);
 129 template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *, Value);
 130 template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *, Value);
 131 template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *, Value);
 132
 133 template <typename... EffectTys>
 134 bool mlir::hasEffect(Operation *op, Value value) {
 135   auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
 136   if (!memOp)
 137     return false;
 138   SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
 139   memOp.getEffects(effects);
 140   return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
 141     if (value && effect.getValue() != value)
 142       return false;
 143     return isa<EffectTys...>(effect.getEffect());
 144   });
 145 }
 146 template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *, Value);
 147 template bool mlir::hasEffect<MemoryEffects::Free>(Operation *, Value);
 148 template bool mlir::hasEffect<MemoryEffects::Read>(Operation *, Value);
 149 template bool mlir::hasEffect<MemoryEffects::Write>(Operation *, Value);
 150 template bool
 151 mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *, Value);
 152
 153 bool mlir::wouldOpBeTriviallyDead(Operation *op) {
 154   if (op->mightHaveTrait<OpTrait::IsTerminator>())
 155     return false;
 156   if (isa<SymbolOpInterface>(op))
 157     return false;
 158   return wouldOpBeTriviallyDeadImpl(op);
 159 }
 160
 161 bool mlir::isMemoryEffectFree(Operation *op) {
 162   if (auto memInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
 163     if (!memInterface.hasNoEffect())
 164       return false;
 165     // If the op does not have recursive side effects, then it is memory effect
 166     // free.
 167     if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>())
 168       return true;
 169   } else if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>()) {
 170     // Otherwise, if the op does not implement the memory effect interface and
 171     // it does not have recursive side effects, then it cannot be known that the
 172     // op is moveable.
 173     return false;
 174   }
 175
 176   // Recurse into the regions and ensure that all nested ops are memory effect
 177   // free.
 178   for (Region &region : op->getRegions())
 179     for (Operation &op : region.getOps())
 180       if (!isMemoryEffectFree(&op))
 181         return false;
 182   return true;
 183 }
 184
 185 // the returned vector may contain duplicate effects
 186 std::optional<llvm::SmallVector<MemoryEffects::EffectInstance>>
 187 mlir::getEffectsRecursively(Operation *rootOp) {
 188   SmallVector<MemoryEffects::EffectInstance> effects;
 189   SmallVector<Operation *> effectingOps(1, rootOp);
 190   while (!effectingOps.empty()) {
 191     Operation *op = effectingOps.pop_back_val();
 192
 193     // If the operation has recursive effects, push all of the nested
 194     // operations on to the stack to consider.
 195     bool hasRecursiveEffects =
 196         op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();
 197     if (hasRecursiveEffects) {
 198       for (Region &region : op->getRegions()) {
 199         for (Block &block : region) {
 200           for (Operation &nestedOp : block) {
 201             effectingOps.push_back(&nestedOp);
 202           }
 203         }
 204       }
 205     }
 206
 207     if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
 208       effectInterface.getEffects(effects);
 209     } else if (!hasRecursiveEffects) {
 210       // the operation does not have recursive memory effects or implement
 211       // the memory effect op interface. Its effects are unknown.
 212       return std::nullopt;
 213     }
 214   }
 215   return effects;
 216 }
 217
 218 bool mlir::isSpeculatable(Operation *op) {
 219   auto conditionallySpeculatable = dyn_cast<ConditionallySpeculatable>(op);
 220   if (!conditionallySpeculatable)
 221     return false;
 222
 223   switch (conditionallySpeculatable.getSpeculatability()) {
 224   case Speculation::RecursivelySpeculatable:
 225     for (Region &region : op->getRegions()) {
 226       for (Operation &op : region.getOps())
 227         if (!isSpeculatable(&op))
 228           return false;
 229     }
 230     return true;
 231
 232   case Speculation::Speculatable:
 233     return true;
 234
 235   case Speculation::NotSpeculatable:
 236     return false;
 237   }
 238
 239   llvm_unreachable("Unhandled enum in mlir::isSpeculatable!");
 240 }
 241
 242 /// The implementation of this function replicates the `def Pure : TraitList`
 243 /// in `SideEffectInterfaces.td` and has to be kept in sync manually.
 244 bool mlir::isPure(Operation *op) {
 245   return isSpeculatable(op) && isMemoryEffectFree(op);
 246 }