MLIR  19.0.0git
SideEffectInterfaces.cpp
Go to the documentation of this file.
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 
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 
28  return isa<Allocate, Free, Read, Write>(effect);
29 }
30 
31 //===----------------------------------------------------------------------===//
32 // SideEffect Utilities
33 //===----------------------------------------------------------------------===//
34 
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 =
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.
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](
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>
108  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
109  if (!memOp)
110  return false;
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;
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 
155  return false;
156  if (isa<SymbolOpInterface>(op))
157  return false;
158  return wouldOpBeTriviallyDeadImpl(op);
159 }
160 
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.
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>>
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 =
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 
219  auto conditionallySpeculatable = dyn_cast<ConditionallySpeculatable>(op);
220  if (!conditionallySpeculatable)
221  return false;
222 
223  switch (conditionallySpeculatable.getSpeculatability()) {
225  for (Region &region : op->getRegions()) {
226  for (Operation &op : region.getOps())
227  if (!isSpeculatable(&op))
228  return false;
229  }
230  return true;
231 
233  return true;
234 
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.
245  return isSpeculatable(op) && isMemoryEffectFree(op);
246 }
static bool wouldOpBeTriviallyDeadImpl(Operation *rootOp)
Internal implementation of mlir::wouldOpBeTriviallyDead that also considers terminator operations as ...
Block represents an ordered list of Operations.
Definition: Block.h:30
This trait indicates that the memory effects of an operation includes the effects of operations neste...
This class provides the API for ops that are known to be terminators.
Definition: OpDefinition.h:762
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
bool use_empty()
Returns true if this operation has no uses.
Definition: Operation.h:848
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:745
bool mightHaveTrait()
Returns true if the operation might have the provided trait.
Definition: Operation.h:753
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:672
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
This class represents a specific instance of an effect.
EffectT * getEffect() const
Return the effect being applied.
Value getValue() const
Return the value the effect is applied on, or nullptr if there isn't a known value being affected.
This class represents a base class for a specific effect type.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
constexpr auto RecursivelySpeculatable
constexpr auto Speculatable
constexpr auto NotSpeculatable
Include the generated interface declarations.
bool hasEffect(Operation *op, Value value=nullptr)
Returns true if op has an effect of type EffectTy on value.
bool isPure(Operation *op)
Returns true if the given operation is pure, i.e., is speculatable that does not touch memory.
bool isMemoryEffectFree(Operation *op)
Returns true if the given operation is free of memory effects.
bool wouldOpBeTriviallyDead(Operation *op)
Return true if the given operation would be dead if unused, and has no side effects on memory that wo...
bool hasSingleEffect(Operation *op, Value value=nullptr)
Returns true if op has only an effect of type EffectTy (and of no other type) on value.
bool isSpeculatable(Operation *op)
Returns true if the given operation is speculatable, i.e.
bool isOpTriviallyDead(Operation *op)
Return true if the given operation is unused, and has no side effects on memory that prevent erasing.
std::optional< llvm::SmallVector< MemoryEffects::EffectInstance > > getEffectsRecursively(Operation *rootOp)
Returns the side effects of an operation.
static bool classof(const SideEffects::Effect *effect)
Include the definitions of the side effect interfaces.