MLIR  21.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 #include <utility>
14 
15 using namespace mlir;
16 
17 //===----------------------------------------------------------------------===//
18 // SideEffect Interfaces
19 //===----------------------------------------------------------------------===//
20 
21 /// Include the definitions of the side effect interfaces.
22 #include "mlir/Interfaces/SideEffectInterfaces.cpp.inc"
23 
24 //===----------------------------------------------------------------------===//
25 // MemoryEffects
26 //===----------------------------------------------------------------------===//
27 
29  return isa<Allocate, Free, Read, Write>(effect);
30 }
31 
32 //===----------------------------------------------------------------------===//
33 // SideEffect Utilities
34 //===----------------------------------------------------------------------===//
35 
37  return op->use_empty() && wouldOpBeTriviallyDead(op);
38 }
39 
40 /// Internal implementation of `mlir::wouldOpBeTriviallyDead` that also
41 /// considers terminator operations as dead if they have no side effects. This
42 /// allows for marking region operations as trivially dead without always being
43 /// conservative of terminators.
44 static bool wouldOpBeTriviallyDeadImpl(Operation *rootOp) {
45  // The set of operation intervals (end-exclusive) to consider when checking
46  // for side effects.
48  std::make_pair(Block::iterator(rootOp), ++Block::iterator(rootOp))};
49  while (!effectingOps.empty()) {
50  Block::iterator &it = effectingOps.back().first;
51  Block::iterator end = effectingOps.back().second;
52  if (it == end) {
53  effectingOps.pop_back();
54  continue;
55  }
56  mlir::Operation *op = &*(it++);
57 
58  // If the operation has recursive effects, push all of the nested operations
59  // on to the stack to consider.
60  bool hasRecursiveEffects =
62  if (hasRecursiveEffects) {
63  for (Region &region : op->getRegions()) {
64  for (auto &block : region) {
65  effectingOps.push_back(std::make_pair(block.begin(), block.end()));
66  }
67  }
68  }
69 
70  // If the op has memory effects, try to characterize them to see if the op
71  // is trivially dead here.
72  if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
73  // Check to see if this op either has no effects, or only allocates/reads
74  // memory.
76  effectInterface.getEffects(effects);
77 
78  // Gather all results of this op that are allocated.
79  SmallPtrSet<Value, 4> allocResults;
80  for (const MemoryEffects::EffectInstance &it : effects)
81  if (isa<MemoryEffects::Allocate>(it.getEffect()) && it.getValue() &&
82  it.getValue().getDefiningOp() == op)
83  allocResults.insert(it.getValue());
84 
85  if (!llvm::all_of(effects, [&allocResults](
87  // We can drop effects if the value is an allocation and is a result
88  // of the operation.
89  if (allocResults.contains(it.getValue()))
90  return true;
91  // Otherwise, the effect must be a read.
92  return isa<MemoryEffects::Read>(it.getEffect());
93  })) {
94  return false;
95  }
96  continue;
97  }
98  // Otherwise, if the op only has recursive side effects we can treat the
99  // operation itself as having no effects. We will visit its children next.
100  if (hasRecursiveEffects)
101  continue;
102 
103  // If there were no effect interfaces, we treat this op as conservatively
104  // having effects.
105  return false;
106  }
107 
108  // If we get here, none of the operations had effects that prevented marking
109  // 'op' as dead.
110  return true;
111 }
112 
113 template <typename EffectTy>
115  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
116  if (!memOp)
117  return false;
119  memOp.getEffects(effects);
120  bool hasSingleEffectOnVal = false;
121  // Iterate through `effects` and check if an effect of type `EffectTy` and
122  // only of that type is present.
123  for (auto &effect : effects) {
124  hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());
125  if (!hasSingleEffectOnVal)
126  return false;
127  }
128  return hasSingleEffectOnVal;
129 }
130 template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *);
131 template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *);
132 template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *);
133 template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *);
134 
135 template <typename EffectTy>
137  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
138  if (!memOp)
139  return false;
141  memOp.getEffects(effects);
142  bool hasSingleEffectOnVal = false;
143  // Iterate through `effects` and check if an effect of type `EffectTy` and
144  // only of that type is present.
145  for (auto &effect : effects) {
146  if (effect.getValue() != value)
147  continue;
148  hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());
149  if (!hasSingleEffectOnVal)
150  return false;
151  }
152  return hasSingleEffectOnVal;
153 }
154 
155 template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *,
156  Value value);
157 template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *,
158  Value value);
159 template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *,
160  Value value);
161 template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *,
162  Value value);
163 
164 template <typename ValueTy, typename EffectTy>
165 bool mlir::hasSingleEffect(Operation *op, ValueTy value) {
166  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
167  if (!memOp)
168  return false;
170  memOp.getEffects(effects);
171  bool hasSingleEffectOnVal = false;
172  // Iterate through `effects` and check if an effect of type `EffectTy` and
173  // only of that type is present on value.
174  for (auto &effect : effects) {
175  if (effect.getEffectValue<ValueTy>() != value)
176  continue;
177  hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());
178  if (!hasSingleEffectOnVal)
179  return false;
180  }
181  return hasSingleEffectOnVal;
182 }
183 
184 template bool
185 mlir::hasSingleEffect<OpOperand *, MemoryEffects::Allocate>(Operation *,
186  OpOperand *);
187 template bool
188 mlir::hasSingleEffect<OpOperand *, MemoryEffects::Free>(Operation *,
189  OpOperand *);
190 template bool
191 mlir::hasSingleEffect<OpOperand *, MemoryEffects::Read>(Operation *,
192  OpOperand *);
193 template bool
194 mlir::hasSingleEffect<OpOperand *, MemoryEffects::Write>(Operation *,
195  OpOperand *);
196 template bool
197 mlir::hasSingleEffect<OpResult, MemoryEffects::Allocate>(Operation *, OpResult);
198 template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Free>(Operation *,
199  OpResult);
200 template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Read>(Operation *,
201  OpResult);
202 template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Write>(Operation *,
203  OpResult);
204 template bool
205 mlir::hasSingleEffect<BlockArgument, MemoryEffects::Allocate>(Operation *,
206  BlockArgument);
207 template bool
208 mlir::hasSingleEffect<BlockArgument, MemoryEffects::Free>(Operation *,
209  BlockArgument);
210 template bool
211 mlir::hasSingleEffect<BlockArgument, MemoryEffects::Read>(Operation *,
212  BlockArgument);
213 template bool
214 mlir::hasSingleEffect<BlockArgument, MemoryEffects::Write>(Operation *,
215  BlockArgument);
216 
217 template <typename... EffectTys>
219  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
220  if (!memOp)
221  return false;
223  memOp.getEffects(effects);
224  return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
225  return isa<EffectTys...>(effect.getEffect());
226  });
227 }
228 template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *);
229 template bool mlir::hasEffect<MemoryEffects::Free>(Operation *);
230 template bool mlir::hasEffect<MemoryEffects::Read>(Operation *);
231 template bool mlir::hasEffect<MemoryEffects::Write>(Operation *);
232 template bool
233 mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *);
234 
235 template <typename... EffectTys>
236 bool mlir::hasEffect(Operation *op, Value value) {
237  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
238  if (!memOp)
239  return false;
241  memOp.getEffects(effects);
242  return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
243  if (effect.getValue() != value)
244  return false;
245  return isa<EffectTys...>(effect.getEffect());
246  });
247 }
248 template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *,
249  Value value);
250 template bool mlir::hasEffect<MemoryEffects::Free>(Operation *, Value value);
251 template bool mlir::hasEffect<MemoryEffects::Read>(Operation *, Value value);
252 template bool mlir::hasEffect<MemoryEffects::Write>(Operation *, Value value);
253 template bool
254 mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *,
255  Value value);
256 
257 template <typename ValueTy, typename... EffectTys>
258 bool mlir::hasEffect(Operation *op, ValueTy value) {
259  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
260  if (!memOp)
261  return false;
263  memOp.getEffects(effects);
264  return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
265  if (effect.getEffectValue<ValueTy>() != value)
266  return false;
267  return isa<EffectTys...>(effect.getEffect());
268  });
269 }
270 template bool
271 mlir::hasEffect<OpOperand *, MemoryEffects::Allocate>(Operation *, OpOperand *);
272 template bool mlir::hasEffect<OpOperand *, MemoryEffects::Free>(Operation *,
273  OpOperand *);
274 template bool mlir::hasEffect<OpOperand *, MemoryEffects::Read>(Operation *,
275  OpOperand *);
276 template bool mlir::hasEffect<OpOperand *, MemoryEffects::Write>(Operation *,
277  OpOperand *);
278 template bool
279 mlir::hasEffect<OpOperand *, MemoryEffects::Write, MemoryEffects::Free>(
280  Operation *, OpOperand *);
281 
282 template bool mlir::hasEffect<OpResult, MemoryEffects::Allocate>(Operation *,
283  OpResult);
284 template bool mlir::hasEffect<OpResult, MemoryEffects::Free>(Operation *,
285  OpResult);
286 template bool mlir::hasEffect<OpResult, MemoryEffects::Read>(Operation *,
287  OpResult);
288 template bool mlir::hasEffect<OpResult, MemoryEffects::Write>(Operation *,
289  OpResult);
290 template bool
291 mlir::hasEffect<OpResult, MemoryEffects::Write, MemoryEffects::Free>(
292  Operation *, OpResult);
293 
294 template bool
295 mlir::hasEffect<BlockArgument, MemoryEffects::Allocate>(Operation *,
296  BlockArgument);
297 template bool
298 mlir::hasEffect<BlockArgument, MemoryEffects::Free>(Operation *, BlockArgument);
299 template bool
300 mlir::hasEffect<BlockArgument, MemoryEffects::Read>(Operation *, BlockArgument);
301 template bool
302 mlir::hasEffect<BlockArgument, MemoryEffects::Write>(Operation *,
303  BlockArgument);
304 template bool
305 mlir::hasEffect<BlockArgument, MemoryEffects::Write, MemoryEffects::Free>(
307 
310  return false;
311  if (isa<SymbolOpInterface>(op))
312  return false;
313  return wouldOpBeTriviallyDeadImpl(op);
314 }
315 
317  if (auto memInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
318  if (!memInterface.hasNoEffect())
319  return false;
320  // If the op does not have recursive side effects, then it is memory effect
321  // free.
323  return true;
324  } else if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>()) {
325  // Otherwise, if the op does not implement the memory effect interface and
326  // it does not have recursive side effects, then it cannot be known that the
327  // op is moveable.
328  return false;
329  }
330 
331  // Recurse into the regions and ensure that all nested ops are memory effect
332  // free.
333  for (Region &region : op->getRegions())
334  for (Operation &op : region.getOps())
335  if (!isMemoryEffectFree(&op))
336  return false;
337  return true;
338 }
339 
340 // the returned vector may contain duplicate effects
341 std::optional<llvm::SmallVector<MemoryEffects::EffectInstance>>
344  SmallVector<Operation *> effectingOps(1, rootOp);
345  while (!effectingOps.empty()) {
346  Operation *op = effectingOps.pop_back_val();
347 
348  // If the operation has recursive effects, push all of the nested
349  // operations on to the stack to consider.
350  bool hasRecursiveEffects =
352  if (hasRecursiveEffects) {
353  for (Region &region : op->getRegions()) {
354  for (Block &block : region) {
355  for (Operation &nestedOp : block) {
356  effectingOps.push_back(&nestedOp);
357  }
358  }
359  }
360  }
361 
362  if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
363  effectInterface.getEffects(effects);
364  } else if (!hasRecursiveEffects) {
365  // the operation does not have recursive memory effects or implement
366  // the memory effect op interface. Its effects are unknown.
367  return std::nullopt;
368  }
369  }
370  return effects;
371 }
372 
374  auto conditionallySpeculatable = dyn_cast<ConditionallySpeculatable>(op);
375  if (!conditionallySpeculatable)
376  return false;
377 
378  switch (conditionallySpeculatable.getSpeculatability()) {
380  for (Region &region : op->getRegions()) {
381  for (Operation &op : region.getOps())
382  if (!isSpeculatable(&op))
383  return false;
384  }
385  return true;
386 
388  return true;
389 
391  return false;
392  }
393 
394  llvm_unreachable("Unhandled enum in mlir::isSpeculatable!");
395 }
396 
397 /// The implementation of this function replicates the `def Pure : TraitList`
398 /// in `SideEffectInterfaces.td` and has to be kept in sync manually.
400  return isSpeculatable(op) && isMemoryEffectFree(op);
401 }
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:33
OpListType::iterator iterator
Definition: Block.h:140
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:768
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:853
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:750
bool mightHaveTrait()
Returns true if the operation might have the provided trait.
Definition: Operation.h:758
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:677
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.