MLIR  17.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 "llvm/ADT/SmallPtrSet.h"
12 
13 using namespace mlir;
14 
15 //===----------------------------------------------------------------------===//
16 // SideEffect Interfaces
17 //===----------------------------------------------------------------------===//
18 
19 /// Include the definitions of the side effect interfaces.
20 #include "mlir/Interfaces/SideEffectInterfaces.cpp.inc"
21 
22 //===----------------------------------------------------------------------===//
23 // MemoryEffects
24 //===----------------------------------------------------------------------===//
25 
27  return isa<Allocate, Free, Read, Write>(effect);
28 }
29 
30 //===----------------------------------------------------------------------===//
31 // SideEffect Utilities
32 //===----------------------------------------------------------------------===//
33 
35  return op->use_empty() && wouldOpBeTriviallyDead(op);
36 }
37 
38 /// Internal implementation of `mlir::wouldOpBeTriviallyDead` that also
39 /// considers terminator operations as dead if they have no side effects. This
40 /// allows for marking region operations as trivially dead without always being
41 /// conservative of terminators.
42 static bool wouldOpBeTriviallyDeadImpl(Operation *rootOp) {
43  // The set of operations to consider when checking for side effects.
44  SmallVector<Operation *, 1> effectingOps(1, rootOp);
45  while (!effectingOps.empty()) {
46  Operation *op = effectingOps.pop_back_val();
47 
48  // If the operation has recursive effects, push all of the nested operations
49  // on to the stack to consider.
50  bool hasRecursiveEffects =
52  if (hasRecursiveEffects) {
53  for (Region &region : op->getRegions()) {
54  for (auto &block : region) {
55  for (auto &nestedOp : block)
56  effectingOps.push_back(&nestedOp);
57  }
58  }
59  }
60 
61  // If the op has memory effects, try to characterize them to see if the op
62  // is trivially dead here.
63  if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
64  // Check to see if this op either has no effects, or only allocates/reads
65  // memory.
67  effectInterface.getEffects(effects);
68 
69  // Gather all results of this op that are allocated.
70  SmallPtrSet<Value, 4> allocResults;
71  for (const MemoryEffects::EffectInstance &it : effects)
72  if (isa<MemoryEffects::Allocate>(it.getEffect()) && it.getValue() &&
73  it.getValue().getDefiningOp() == op)
74  allocResults.insert(it.getValue());
75 
76  if (!llvm::all_of(effects, [&allocResults](
78  // We can drop effects if the value is an allocation and is a result
79  // of the operation.
80  if (allocResults.contains(it.getValue()))
81  return true;
82  // Otherwise, the effect must be a read.
83  return isa<MemoryEffects::Read>(it.getEffect());
84  })) {
85  return false;
86  }
87  continue;
88 
89  // Otherwise, if the op has recursive side effects we can treat the
90  // operation itself as having no effects.
91  }
92  if (hasRecursiveEffects)
93  continue;
94 
95  // If there were no effect interfaces, we treat this op as conservatively
96  // having effects.
97  return false;
98  }
99 
100  // If we get here, none of the operations had effects that prevented marking
101  // 'op' as dead.
102  return true;
103 }
104 
105 template <typename EffectTy>
107  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
108  if (!memOp)
109  return false;
111  memOp.getEffects(effects);
112  bool hasSingleEffectOnVal = false;
113  // Iterate through `effects` and check if an effect of type `EffectTy` and
114  // only of that type is present. A `value` to check the effect on may or may
115  // not have been provided.
116  for (auto &effect : effects) {
117  if (value && effect.getValue() != value)
118  continue;
119  hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());
120  if (!hasSingleEffectOnVal)
121  return false;
122  }
123  return hasSingleEffectOnVal;
124 }
125 
126 template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *,
127  Value);
128 template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *, Value);
129 template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *, Value);
130 template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *, Value);
131 
132 template <typename... EffectTys>
133 bool mlir::hasEffect(Operation *op, Value value) {
134  auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
135  if (!memOp)
136  return false;
138  memOp.getEffects(effects);
139  return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
140  if (value && effect.getValue() != value)
141  return false;
142  return isa<EffectTys...>(effect.getEffect());
143  });
144 }
145 template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *, Value);
146 template bool mlir::hasEffect<MemoryEffects::Free>(Operation *, Value);
147 template bool mlir::hasEffect<MemoryEffects::Read>(Operation *, Value);
148 template bool mlir::hasEffect<MemoryEffects::Write>(Operation *, Value);
149 template bool
150 mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *, Value);
151 
154  return false;
155  return wouldOpBeTriviallyDeadImpl(op);
156 }
157 
159  if (auto memInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
160  if (!memInterface.hasNoEffect())
161  return false;
162  // If the op does not have recursive side effects, then it is memory effect
163  // free.
165  return true;
166  } else if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>()) {
167  // Otherwise, if the op does not implement the memory effect interface and
168  // it does not have recursive side effects, then it cannot be known that the
169  // op is moveable.
170  return false;
171  }
172 
173  // Recurse into the regions and ensure that all nested ops are memory effect
174  // free.
175  for (Region &region : op->getRegions())
176  for (Operation &op : region.getOps())
177  if (!isMemoryEffectFree(&op))
178  return false;
179  return true;
180 }
181 
183  auto conditionallySpeculatable = dyn_cast<ConditionallySpeculatable>(op);
184  if (!conditionallySpeculatable)
185  return false;
186 
187  switch (conditionallySpeculatable.getSpeculatability()) {
189  for (Region &region : op->getRegions()) {
190  for (Operation &op : region.getOps())
191  if (!isSpeculatable(&op))
192  return false;
193  }
194  return true;
195 
197  return true;
198 
200  return false;
201  }
202 
203  llvm_unreachable("Unhandled enum in mlir::isSpeculatable!");
204 }
205 
206 /// The implementation of this function replicates the `def Pure : TraitList`
207 /// in `SideEffectInterfaces.td` and has to be kept in sync manually.
209  return isSpeculatable(op) && isMemoryEffectFree(op);
210 }
static bool wouldOpBeTriviallyDeadImpl(Operation *rootOp)
Internal implementation of mlir::wouldOpBeTriviallyDead that also considers terminator operations as ...
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:701
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:75
bool use_empty()
Returns true if this operation has no uses.
Definition: Operation.h:675
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:574
bool mightHaveTrait()
Returns true if the operation might have the provided trait.
Definition: Operation.h:582
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:522
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:93
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.
static bool classof(const SideEffects::Effect *effect)
Include the definitions of the side effect interfaces.