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#include <utility>
14
15using 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
28bool MemoryEffects::Effect::classof(const SideEffects::Effect *effect) {
29 return isa<Allocate, Free, Read, Write>(effect);
30}
31
32//===----------------------------------------------------------------------===//
33// SideEffect Utilities
34//===----------------------------------------------------------------------===//
35
36bool mlir::isOpTriviallyDead(Operation *op) {
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.
44static bool wouldOpBeTriviallyDeadImpl(Operation *rootOp) {
45 // The set of operation intervals (end-exclusive) to consider when checking
46 // for side effects.
47 SmallVector<std::pair<Block::iterator, Block::iterator>, 1> effectingOps = {
48 std::make_pair(x: Block::iterator(rootOp), y&: ++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 =
61 op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();
62 if (hasRecursiveEffects) {
63 for (Region &region : op->getRegions()) {
64 for (auto &block : region) {
65 effectingOps.push_back(Elt: std::make_pair(x: block.begin(), y: 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.
75 SmallVector<MemoryEffects::EffectInstance, 1> effects;
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>(Val: it.getEffect()) && it.getValue() &&
82 it.getValue().getDefiningOp() == op)
83 allocResults.insert(Ptr: it.getValue());
84
85 if (!llvm::all_of(Range&: effects, P: [&allocResults](
86 const MemoryEffects::EffectInstance &it) {
87 // We can drop effects if the value is an allocation and is a result
88 // of the operation.
89 if (allocResults.contains(Ptr: it.getValue()))
90 return true;
91 // Otherwise, the effect must be a read.
92 return isa<MemoryEffects::Read>(Val: 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
113template <typename EffectTy>
114bool mlir::hasSingleEffect(Operation *op) {
115 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
116 if (!memOp)
117 return false;
118 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
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}
130template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *);
131template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *);
132template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *);
133template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *);
134
135template <typename EffectTy>
136bool mlir::hasSingleEffect(Operation *op, Value value) {
137 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
138 if (!memOp)
139 return false;
140 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
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
155template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *,
156 Value value);
157template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *,
158 Value value);
159template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *,
160 Value value);
161template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *,
162 Value value);
163
164template <typename ValueTy, typename EffectTy>
165bool mlir::hasSingleEffect(Operation *op, ValueTy value) {
166 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
167 if (!memOp)
168 return false;
169 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
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
184template bool
185mlir::hasSingleEffect<OpOperand *, MemoryEffects::Allocate>(Operation *,
186 OpOperand *);
187template bool
188mlir::hasSingleEffect<OpOperand *, MemoryEffects::Free>(Operation *,
189 OpOperand *);
190template bool
191mlir::hasSingleEffect<OpOperand *, MemoryEffects::Read>(Operation *,
192 OpOperand *);
193template bool
194mlir::hasSingleEffect<OpOperand *, MemoryEffects::Write>(Operation *,
195 OpOperand *);
196template bool
197mlir::hasSingleEffect<OpResult, MemoryEffects::Allocate>(Operation *, OpResult);
198template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Free>(Operation *,
199 OpResult);
200template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Read>(Operation *,
201 OpResult);
202template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Write>(Operation *,
203 OpResult);
204template bool
205mlir::hasSingleEffect<BlockArgument, MemoryEffects::Allocate>(Operation *,
206 BlockArgument);
207template bool
208mlir::hasSingleEffect<BlockArgument, MemoryEffects::Free>(Operation *,
209 BlockArgument);
210template bool
211mlir::hasSingleEffect<BlockArgument, MemoryEffects::Read>(Operation *,
212 BlockArgument);
213template bool
214mlir::hasSingleEffect<BlockArgument, MemoryEffects::Write>(Operation *,
215 BlockArgument);
216
217template <typename... EffectTys>
218bool mlir::hasEffect(Operation *op) {
219 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
220 if (!memOp)
221 return false;
222 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
223 memOp.getEffects(effects);
224 return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
225 return isa<EffectTys...>(effect.getEffect());
226 });
227}
228template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *);
229template bool mlir::hasEffect<MemoryEffects::Free>(Operation *);
230template bool mlir::hasEffect<MemoryEffects::Read>(Operation *);
231template bool mlir::hasEffect<MemoryEffects::Write>(Operation *);
232template bool
233mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *);
234
235template <typename... EffectTys>
236bool mlir::hasEffect(Operation *op, Value value) {
237 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
238 if (!memOp)
239 return false;
240 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
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}
248template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *,
249 Value value);
250template bool mlir::hasEffect<MemoryEffects::Free>(Operation *, Value value);
251template bool mlir::hasEffect<MemoryEffects::Read>(Operation *, Value value);
252template bool mlir::hasEffect<MemoryEffects::Write>(Operation *, Value value);
253template bool
254mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *,
255 Value value);
256
257template <typename ValueTy, typename... EffectTys>
258bool mlir::hasEffect(Operation *op, ValueTy value) {
259 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
260 if (!memOp)
261 return false;
262 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
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}
270template bool
271mlir::hasEffect<OpOperand *, MemoryEffects::Allocate>(Operation *, OpOperand *);
272template bool mlir::hasEffect<OpOperand *, MemoryEffects::Free>(Operation *,
273 OpOperand *);
274template bool mlir::hasEffect<OpOperand *, MemoryEffects::Read>(Operation *,
275 OpOperand *);
276template bool mlir::hasEffect<OpOperand *, MemoryEffects::Write>(Operation *,
277 OpOperand *);
278template bool
279mlir::hasEffect<OpOperand *, MemoryEffects::Write, MemoryEffects::Free>(
280 Operation *, OpOperand *);
281
282template bool mlir::hasEffect<OpResult, MemoryEffects::Allocate>(Operation *,
283 OpResult);
284template bool mlir::hasEffect<OpResult, MemoryEffects::Free>(Operation *,
285 OpResult);
286template bool mlir::hasEffect<OpResult, MemoryEffects::Read>(Operation *,
287 OpResult);
288template bool mlir::hasEffect<OpResult, MemoryEffects::Write>(Operation *,
289 OpResult);
290template bool
291mlir::hasEffect<OpResult, MemoryEffects::Write, MemoryEffects::Free>(
292 Operation *, OpResult);
293
294template bool
295mlir::hasEffect<BlockArgument, MemoryEffects::Allocate>(Operation *,
296 BlockArgument);
297template bool
298mlir::hasEffect<BlockArgument, MemoryEffects::Free>(Operation *, BlockArgument);
299template bool
300mlir::hasEffect<BlockArgument, MemoryEffects::Read>(Operation *, BlockArgument);
301template bool
302mlir::hasEffect<BlockArgument, MemoryEffects::Write>(Operation *,
303 BlockArgument);
304template bool
305mlir::hasEffect<BlockArgument, MemoryEffects::Write, MemoryEffects::Free>(
306 Operation *, BlockArgument);
307
308bool mlir::wouldOpBeTriviallyDead(Operation *op) {
309 if (op->mightHaveTrait<OpTrait::IsTerminator>())
310 return false;
311 if (isa<SymbolOpInterface>(op))
312 return false;
313 return wouldOpBeTriviallyDeadImpl(rootOp: op);
314}
315
316bool mlir::isMemoryEffectFree(Operation *op) {
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.
322 if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>())
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: &op))
336 return false;
337 return true;
338}
339
340// the returned vector may contain duplicate effects
341std::optional<llvm::SmallVector<MemoryEffects::EffectInstance>>
342mlir::getEffectsRecursively(Operation *rootOp) {
343 SmallVector<MemoryEffects::EffectInstance> effects;
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 =
351 op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();
352 if (hasRecursiveEffects) {
353 for (Region &region : op->getRegions()) {
354 for (Block &block : region) {
355 for (Operation &nestedOp : block) {
356 effectingOps.push_back(Elt: &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
373bool mlir::isSpeculatable(Operation *op) {
374 auto conditionallySpeculatable = dyn_cast<ConditionallySpeculatable>(op);
375 if (!conditionallySpeculatable)
376 return false;
377
378 switch (conditionallySpeculatable.getSpeculatability()) {
379 case Speculation::RecursivelySpeculatable:
380 for (Region &region : op->getRegions()) {
381 for (Operation &op : region.getOps())
382 if (!isSpeculatable(op: &op))
383 return false;
384 }
385 return true;
386
387 case Speculation::Speculatable:
388 return true;
389
390 case Speculation::NotSpeculatable:
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.
399bool mlir::isPure(Operation *op) {
400 return isSpeculatable(op) && isMemoryEffectFree(op);
401}
402

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