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