MLIR  20.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.
116  for (auto &effect : effects) {
117  hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());
118  if (!hasSingleEffectOnVal)
119  return false;
120  }
121  return hasSingleEffectOnVal;
122 }
123 template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *);
124 template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *);
125 template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *);
126 template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *);
127 
128 template <typename EffectTy>
130  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
131  if (!memOp)
132  return false;
134  memOp.getEffects(effects);
135  bool hasSingleEffectOnVal = false;
136  // Iterate through `effects` and check if an effect of type `EffectTy` and
137  // only of that type is present.
138  for (auto &effect : effects) {
139  if (effect.getValue() != value)
140  continue;
141  hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());
142  if (!hasSingleEffectOnVal)
143  return false;
144  }
145  return hasSingleEffectOnVal;
146 }
147 
148 template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *,
149  Value value);
150 template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *,
151  Value value);
152 template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *,
153  Value value);
154 template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *,
155  Value value);
156 
157 template <typename ValueTy, typename EffectTy>
158 bool mlir::hasSingleEffect(Operation *op, ValueTy value) {
159  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
160  if (!memOp)
161  return false;
163  memOp.getEffects(effects);
164  bool hasSingleEffectOnVal = false;
165  // Iterate through `effects` and check if an effect of type `EffectTy` and
166  // only of that type is present on value.
167  for (auto &effect : effects) {
168  if (effect.getEffectValue<ValueTy>() != value)
169  continue;
170  hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());
171  if (!hasSingleEffectOnVal)
172  return false;
173  }
174  return hasSingleEffectOnVal;
175 }
176 
177 template bool
178 mlir::hasSingleEffect<OpOperand *, MemoryEffects::Allocate>(Operation *,
179  OpOperand *);
180 template bool
181 mlir::hasSingleEffect<OpOperand *, MemoryEffects::Free>(Operation *,
182  OpOperand *);
183 template bool
184 mlir::hasSingleEffect<OpOperand *, MemoryEffects::Read>(Operation *,
185  OpOperand *);
186 template bool
187 mlir::hasSingleEffect<OpOperand *, MemoryEffects::Write>(Operation *,
188  OpOperand *);
189 template bool
190 mlir::hasSingleEffect<OpResult, MemoryEffects::Allocate>(Operation *, OpResult);
191 template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Free>(Operation *,
192  OpResult);
193 template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Read>(Operation *,
194  OpResult);
195 template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Write>(Operation *,
196  OpResult);
197 template bool
198 mlir::hasSingleEffect<BlockArgument, MemoryEffects::Allocate>(Operation *,
199  BlockArgument);
200 template bool
201 mlir::hasSingleEffect<BlockArgument, MemoryEffects::Free>(Operation *,
202  BlockArgument);
203 template bool
204 mlir::hasSingleEffect<BlockArgument, MemoryEffects::Read>(Operation *,
205  BlockArgument);
206 template bool
207 mlir::hasSingleEffect<BlockArgument, MemoryEffects::Write>(Operation *,
208  BlockArgument);
209 
210 template <typename... EffectTys>
212  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
213  if (!memOp)
214  return false;
216  memOp.getEffects(effects);
217  return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
218  return isa<EffectTys...>(effect.getEffect());
219  });
220 }
221 template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *);
222 template bool mlir::hasEffect<MemoryEffects::Free>(Operation *);
223 template bool mlir::hasEffect<MemoryEffects::Read>(Operation *);
224 template bool mlir::hasEffect<MemoryEffects::Write>(Operation *);
225 template bool
226 mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *);
227 
228 template <typename... EffectTys>
229 bool mlir::hasEffect(Operation *op, Value value) {
230  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
231  if (!memOp)
232  return false;
234  memOp.getEffects(effects);
235  return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
236  if (effect.getValue() != value)
237  return false;
238  return isa<EffectTys...>(effect.getEffect());
239  });
240 }
241 template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *,
242  Value value);
243 template bool mlir::hasEffect<MemoryEffects::Free>(Operation *, Value value);
244 template bool mlir::hasEffect<MemoryEffects::Read>(Operation *, Value value);
245 template bool mlir::hasEffect<MemoryEffects::Write>(Operation *, Value value);
246 template bool
247 mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *,
248  Value value);
249 
250 template <typename ValueTy, typename... EffectTys>
251 bool mlir::hasEffect(Operation *op, ValueTy value) {
252  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
253  if (!memOp)
254  return false;
256  memOp.getEffects(effects);
257  return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
258  if (effect.getEffectValue<ValueTy>() != value)
259  return false;
260  return isa<EffectTys...>(effect.getEffect());
261  });
262 }
263 template bool
264 mlir::hasEffect<OpOperand *, MemoryEffects::Allocate>(Operation *, OpOperand *);
265 template bool mlir::hasEffect<OpOperand *, MemoryEffects::Free>(Operation *,
266  OpOperand *);
267 template bool mlir::hasEffect<OpOperand *, MemoryEffects::Read>(Operation *,
268  OpOperand *);
269 template bool mlir::hasEffect<OpOperand *, MemoryEffects::Write>(Operation *,
270  OpOperand *);
271 template bool
272 mlir::hasEffect<OpOperand *, MemoryEffects::Write, MemoryEffects::Free>(
273  Operation *, OpOperand *);
274 
275 template bool mlir::hasEffect<OpResult, MemoryEffects::Allocate>(Operation *,
276  OpResult);
277 template bool mlir::hasEffect<OpResult, MemoryEffects::Free>(Operation *,
278  OpResult);
279 template bool mlir::hasEffect<OpResult, MemoryEffects::Read>(Operation *,
280  OpResult);
281 template bool mlir::hasEffect<OpResult, MemoryEffects::Write>(Operation *,
282  OpResult);
283 template bool
284 mlir::hasEffect<OpResult, MemoryEffects::Write, MemoryEffects::Free>(
285  Operation *, OpResult);
286 
287 template bool
288 mlir::hasEffect<BlockArgument, MemoryEffects::Allocate>(Operation *,
289  BlockArgument);
290 template bool
291 mlir::hasEffect<BlockArgument, MemoryEffects::Free>(Operation *, BlockArgument);
292 template bool
293 mlir::hasEffect<BlockArgument, MemoryEffects::Read>(Operation *, BlockArgument);
294 template bool
295 mlir::hasEffect<BlockArgument, MemoryEffects::Write>(Operation *,
296  BlockArgument);
297 template bool
298 mlir::hasEffect<BlockArgument, MemoryEffects::Write, MemoryEffects::Free>(
300 
303  return false;
304  if (isa<SymbolOpInterface>(op))
305  return false;
306  return wouldOpBeTriviallyDeadImpl(op);
307 }
308 
310  if (auto memInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
311  if (!memInterface.hasNoEffect())
312  return false;
313  // If the op does not have recursive side effects, then it is memory effect
314  // free.
316  return true;
317  } else if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>()) {
318  // Otherwise, if the op does not implement the memory effect interface and
319  // it does not have recursive side effects, then it cannot be known that the
320  // op is moveable.
321  return false;
322  }
323 
324  // Recurse into the regions and ensure that all nested ops are memory effect
325  // free.
326  for (Region &region : op->getRegions())
327  for (Operation &op : region.getOps())
328  if (!isMemoryEffectFree(&op))
329  return false;
330  return true;
331 }
332 
333 // the returned vector may contain duplicate effects
334 std::optional<llvm::SmallVector<MemoryEffects::EffectInstance>>
337  SmallVector<Operation *> effectingOps(1, rootOp);
338  while (!effectingOps.empty()) {
339  Operation *op = effectingOps.pop_back_val();
340 
341  // If the operation has recursive effects, push all of the nested
342  // operations on to the stack to consider.
343  bool hasRecursiveEffects =
345  if (hasRecursiveEffects) {
346  for (Region &region : op->getRegions()) {
347  for (Block &block : region) {
348  for (Operation &nestedOp : block) {
349  effectingOps.push_back(&nestedOp);
350  }
351  }
352  }
353  }
354 
355  if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
356  effectInterface.getEffects(effects);
357  } else if (!hasRecursiveEffects) {
358  // the operation does not have recursive memory effects or implement
359  // the memory effect op interface. Its effects are unknown.
360  return std::nullopt;
361  }
362  }
363  return effects;
364 }
365 
367  auto conditionallySpeculatable = dyn_cast<ConditionallySpeculatable>(op);
368  if (!conditionallySpeculatable)
369  return false;
370 
371  switch (conditionallySpeculatable.getSpeculatability()) {
373  for (Region &region : op->getRegions()) {
374  for (Operation &op : region.getOps())
375  if (!isSpeculatable(&op))
376  return false;
377  }
378  return true;
379 
381  return true;
382 
384  return false;
385  }
386 
387  llvm_unreachable("Unhandled enum in mlir::isSpeculatable!");
388 }
389 
390 /// The implementation of this function replicates the `def Pure : TraitList`
391 /// in `SideEffectInterfaces.td` and has to be kept in sync manually.
393  return isSpeculatable(op) && isMemoryEffectFree(op);
394 }
static bool wouldOpBeTriviallyDeadImpl(Operation *rootOp)
Internal implementation of mlir::wouldOpBeTriviallyDead that also considers terminator operations as ...
This class represents an argument of a Block.
Definition: Value.h:319
Block represents an ordered list of Operations.
Definition: Block.h:31
This class represents an operand of an operation.
Definition: Value.h:267
This is a value defined by a result of an operation.
Definition: Value.h:457
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:764
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.
T getEffectValue() const
Returns the OpOperand effect is applied on, or nullptr if there isn't a known value being effected.
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 hasSingleEffect(Operation *op)
Returns true if op has only an effect of type EffectTy.
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 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.
bool hasEffect(Operation *op)
Returns true if op has an effect of type EffectTy.
static bool classof(const SideEffects::Effect *effect)
Include the definitions of the side effect interfaces.