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
9#include "mlir/Interfaces/SideEffectInterfaces.h"
10
11#include "mlir/IR/SymbolTable.h"
12#include "llvm/ADT/SmallPtrSet.h"
13
14using 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
27bool MemoryEffects::Effect::classof(const SideEffects::Effect *effect) {
28 return isa<Allocate, Free, Read, Write>(effect);
29}
30
31//===----------------------------------------------------------------------===//
32// SideEffect Utilities
33//===----------------------------------------------------------------------===//
34
35bool mlir::isOpTriviallyDead(Operation *op) {
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.
43static 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 =
52 op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();
53 if (hasRecursiveEffects) {
54 for (Region &region : op->getRegions()) {
55 for (auto &block : region) {
56 for (auto &nestedOp : block)
57 effectingOps.push_back(Elt: &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.
67 SmallVector<MemoryEffects::EffectInstance, 1> effects;
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>(Val: it.getEffect()) && it.getValue() &&
74 it.getValue().getDefiningOp() == op)
75 allocResults.insert(Ptr: it.getValue());
76
77 if (!llvm::all_of(Range&: effects, P: [&allocResults](
78 const MemoryEffects::EffectInstance &it) {
79 // We can drop effects if the value is an allocation and is a result
80 // of the operation.
81 if (allocResults.contains(Ptr: it.getValue()))
82 return true;
83 // Otherwise, the effect must be a read.
84 return isa<MemoryEffects::Read>(Val: 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
106template <typename EffectTy>
107bool mlir::hasSingleEffect(Operation *op, Value value) {
108 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
109 if (!memOp)
110 return false;
111 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
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
127template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *,
128 Value);
129template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *, Value);
130template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *, Value);
131template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *, Value);
132
133template <typename... EffectTys>
134bool mlir::hasEffect(Operation *op, Value value) {
135 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
136 if (!memOp)
137 return false;
138 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
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}
146template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *, Value);
147template bool mlir::hasEffect<MemoryEffects::Free>(Operation *, Value);
148template bool mlir::hasEffect<MemoryEffects::Read>(Operation *, Value);
149template bool mlir::hasEffect<MemoryEffects::Write>(Operation *, Value);
150template bool
151mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *, Value);
152
153bool mlir::wouldOpBeTriviallyDead(Operation *op) {
154 if (op->mightHaveTrait<OpTrait::IsTerminator>())
155 return false;
156 if (isa<SymbolOpInterface>(op))
157 return false;
158 return wouldOpBeTriviallyDeadImpl(rootOp: op);
159}
160
161bool mlir::isMemoryEffectFree(Operation *op) {
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.
167 if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>())
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: &op))
181 return false;
182 return true;
183}
184
185// the returned vector may contain duplicate effects
186std::optional<llvm::SmallVector<MemoryEffects::EffectInstance>>
187mlir::getEffectsRecursively(Operation *rootOp) {
188 SmallVector<MemoryEffects::EffectInstance> effects;
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 =
196 op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();
197 if (hasRecursiveEffects) {
198 for (Region &region : op->getRegions()) {
199 for (Block &block : region) {
200 for (Operation &nestedOp : block) {
201 effectingOps.push_back(Elt: &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
218bool mlir::isSpeculatable(Operation *op) {
219 auto conditionallySpeculatable = dyn_cast<ConditionallySpeculatable>(op);
220 if (!conditionallySpeculatable)
221 return false;
222
223 switch (conditionallySpeculatable.getSpeculatability()) {
224 case Speculation::RecursivelySpeculatable:
225 for (Region &region : op->getRegions()) {
226 for (Operation &op : region.getOps())
227 if (!isSpeculatable(op: &op))
228 return false;
229 }
230 return true;
231
232 case Speculation::Speculatable:
233 return true;
234
235 case Speculation::NotSpeculatable:
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.
244bool mlir::isPure(Operation *op) {
245 return isSpeculatable(op) && isMemoryEffectFree(op);
246}
247

source code of mlir/lib/Interfaces/SideEffectInterfaces.cpp