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 <utility>
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>(Val: effect);
29}
30
31//===----------------------------------------------------------------------===//
32// SideEffect Utilities
33//===----------------------------------------------------------------------===//
34
35bool mlir::isOpTriviallyDead(Operation *op) {
36 return op->use_empty() && wouldOpBeTriviallyDead(op);
37}
38
39/// Return true if the op's own memory effects do not prevent erasure. Allowed
40/// effects are reads and effects on results allocated by the op itself.
41///
42/// If the op only has recursive effects, treat the op itself as having no
43/// effects. Without a memory effect interface or recursive effects, return
44/// false to conservatively assume live effects.
45///
46/// The caller must also check nested effects when `hasRecursiveEffects` is
47/// true. This function does not check uses or restrictions on erasing
48/// terminators and symbols.
49static bool hasOnlyRemovableEffects(Operation *op, bool hasRecursiveEffects) {
50 if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(Val: op)) {
51 SmallVector<MemoryEffects::EffectInstance, 1> effects;
52 effectInterface.getEffects(effects);
53
54 // Gather all results of this op that are allocated.
55 SmallPtrSet<Value, 4> allocResults;
56 for (const MemoryEffects::EffectInstance &effect : effects)
57 if (isa<MemoryEffects::Allocate>(Val: effect.getEffect()) &&
58 effect.getValue() && effect.getValue().getDefiningOp() == op)
59 allocResults.insert(Ptr: effect.getValue());
60 return llvm::all_of(Range&: effects,
61 P: [&](const MemoryEffects::EffectInstance &effect) {
62 // We can drop effects on values allocated by this
63 // operation and returned as results. Otherwise, the
64 // effect must be a read.
65 return allocResults.contains(Ptr: effect.getValue()) ||
66 isa<MemoryEffects::Read>(Val: effect.getEffect());
67 });
68 }
69 return hasRecursiveEffects;
70}
71
72/// Internal implementation of `mlir::wouldOpBeTriviallyDead` that also
73/// considers terminator operations as dead if they have no side effects. This
74/// allows for marking region operations as trivially dead without always being
75/// conservative of terminators.
76static bool wouldOpBeTriviallyDeadImpl(
77 Operation *root,
78 DenseMap<Operation *, DeadnessCache::State> *cache = nullptr) {
79 using State = DeadnessCache::State;
80 // Repeated queries on nested operations would otherwise scan the same
81 // subtrees. Cache each subtree after checking its effects, and skip cached
82 // subtrees on later queries. An explicit worklist also bounds C++ stack use
83 // for deeply nested IR. Uncached queries do not look up or record summaries.
84 struct WorkItem {
85 // Keep the unvisited range so a block can resume after a nested operation
86 // without adding every sibling to the worklist.
87 Block::iterator current;
88 Block::iterator end;
89 Operation *complete = nullptr;
90 };
91 SmallVector<WorkItem, 1> worklist = {
92 {.current: Block::iterator(root), .end: ++Block::iterator(root)}};
93 while (!worklist.empty()) {
94 WorkItem &item = worklist.back();
95 if (item.current == item.end) {
96 if (cache && item.complete)
97 (*cache)[item.complete] = State::Dead;
98 worklist.pop_back();
99 continue;
100 }
101 Operation *op = &*item.current++;
102 bool cachedAlive = false;
103 if (cache) {
104 auto cached = cache->find(Val: op);
105 if (cached != cache->end()) {
106 if (cached->second == State::Dead)
107 continue;
108 cachedAlive = true;
109 }
110 }
111 bool recursive = op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();
112 if (cachedAlive || !hasOnlyRemovableEffects(op, hasRecursiveEffects: recursive)) {
113 // One live effect keeps every ancestor up to the root live. The
114 // remaining subtrees cannot change the answer.
115 if (cache) {
116 for (Operation *ancestor = op;; ancestor = ancestor->getParentOp()) {
117 (*cache)[ancestor] = State::Alive;
118 if (ancestor == root)
119 break;
120 }
121 }
122 return false;
123 }
124 if (!recursive) {
125 if (cache)
126 (*cache)[op] = State::Dead;
127 continue;
128 }
129 // The first pushed block is processed last. Record the parent's summary
130 // only when that block is complete and all other blocks have been checked.
131 Operation *complete = cache ? op : nullptr;
132 for (Region &region : op->getRegions()) {
133 for (Block &block : region) {
134 worklist.push_back(Elt: {.current: block.begin(), .end: block.end(), .complete: complete});
135 complete = nullptr;
136 }
137 }
138 if (complete)
139 (*cache)[complete] = State::Dead;
140 }
141 return true;
142}
143
144bool DeadnessCache::isOpTriviallyDead(Operation *root) {
145 // Cache only effects. Uses can change without a change to the defining op.
146 // Nested operations may have internal uses or be terminators even when the
147 // whole root can be erased, so these checks apply only to the root.
148 if (!root->use_empty() || root->mightHaveTrait<OpTrait::IsTerminator>() ||
149 isa<SymbolOpInterface>(Val: root))
150 return false;
151
152 auto cachedRoot = cache.find(Val: root);
153 if (cachedRoot != cache.end())
154 return cachedRoot->second == State::Dead;
155
156 return wouldOpBeTriviallyDeadImpl(root, cache: &cache);
157}
158
159void DeadnessCache::invalidate(Operation *op) {
160 op->walk(callback: [&](Operation *nested) { cache.erase(Val: nested); });
161 invalidateAncestors(op);
162}
163
164void DeadnessCache::invalidateAncestors(Operation *op) {
165 // An ancestor may report nested effects through its own effect interface,
166 // without querying the intermediate cache entries. A missing entry cannot
167 // stop invalidation of its ancestors.
168 for (Operation *parent = op; parent; parent = parent->getParentOp())
169 cache.erase(Val: parent);
170}
171
172template <typename EffectTy>
173bool mlir::hasSingleEffect(Operation *op) {
174 auto memOp = dyn_cast<MemoryEffectOpInterface>(Val: op);
175 if (!memOp)
176 return false;
177 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
178 memOp.getEffects(effects);
179 bool hasSingleEffectOnVal = false;
180 // Iterate through `effects` and check if an effect of type `EffectTy` and
181 // only of that type is present.
182 for (auto &effect : effects) {
183 hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());
184 if (!hasSingleEffectOnVal)
185 return false;
186 }
187 return hasSingleEffectOnVal;
188}
189template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *);
190template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *);
191template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *);
192template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *);
193
194template <typename EffectTy>
195bool mlir::hasSingleEffect(Operation *op, Value value) {
196 auto memOp = dyn_cast<MemoryEffectOpInterface>(Val: op);
197 if (!memOp)
198 return false;
199 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
200 memOp.getEffects(effects);
201 bool hasSingleEffectOnVal = false;
202 // Iterate through `effects` and check if an effect of type `EffectTy` and
203 // only of that type is present.
204 for (auto &effect : effects) {
205 if (effect.getValue() != value)
206 continue;
207 hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());
208 if (!hasSingleEffectOnVal)
209 return false;
210 }
211 return hasSingleEffectOnVal;
212}
213
214template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *,
215 Value value);
216template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *,
217 Value value);
218template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *,
219 Value value);
220template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *,
221 Value value);
222
223template <typename ValueTy, typename EffectTy>
224bool mlir::hasSingleEffect(Operation *op, ValueTy value) {
225 auto memOp = dyn_cast<MemoryEffectOpInterface>(Val: op);
226 if (!memOp)
227 return false;
228 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
229 memOp.getEffects(effects);
230 bool hasSingleEffectOnVal = false;
231 // Iterate through `effects` and check if an effect of type `EffectTy` and
232 // only of that type is present on value.
233 for (auto &effect : effects) {
234 if (effect.getEffectValue<ValueTy>() != value)
235 continue;
236 hasSingleEffectOnVal = isa<EffectTy>(effect.getEffect());
237 if (!hasSingleEffectOnVal)
238 return false;
239 }
240 return hasSingleEffectOnVal;
241}
242
243template bool
244mlir::hasSingleEffect<OpOperand *, MemoryEffects::Allocate>(Operation *,
245 OpOperand *);
246template bool
247mlir::hasSingleEffect<OpOperand *, MemoryEffects::Free>(Operation *,
248 OpOperand *);
249template bool
250mlir::hasSingleEffect<OpOperand *, MemoryEffects::Read>(Operation *,
251 OpOperand *);
252template bool
253mlir::hasSingleEffect<OpOperand *, MemoryEffects::Write>(Operation *,
254 OpOperand *);
255template bool
256mlir::hasSingleEffect<OpResult, MemoryEffects::Allocate>(Operation *, OpResult);
257template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Free>(Operation *,
258 OpResult);
259template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Read>(Operation *,
260 OpResult);
261template bool mlir::hasSingleEffect<OpResult, MemoryEffects::Write>(Operation *,
262 OpResult);
263template bool
264mlir::hasSingleEffect<BlockArgument, MemoryEffects::Allocate>(Operation *,
265 BlockArgument);
266template bool
267mlir::hasSingleEffect<BlockArgument, MemoryEffects::Free>(Operation *,
268 BlockArgument);
269template bool
270mlir::hasSingleEffect<BlockArgument, MemoryEffects::Read>(Operation *,
271 BlockArgument);
272template bool
273mlir::hasSingleEffect<BlockArgument, MemoryEffects::Write>(Operation *,
274 BlockArgument);
275
276template <typename... EffectTys>
277bool mlir::hasEffect(Operation *op) {
278 auto memOp = dyn_cast<MemoryEffectOpInterface>(Val: op);
279 if (!memOp)
280 return false;
281 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
282 memOp.getEffects(effects);
283 return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
284 return isa<EffectTys...>(effect.getEffect());
285 });
286}
287template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *);
288template bool mlir::hasEffect<MemoryEffects::Free>(Operation *);
289template bool mlir::hasEffect<MemoryEffects::Read>(Operation *);
290template bool mlir::hasEffect<MemoryEffects::Write>(Operation *);
291template bool
292mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *);
293
294template <typename... EffectTys>
295bool mlir::hasEffect(Operation *op, Value value) {
296 auto memOp = dyn_cast<MemoryEffectOpInterface>(Val: op);
297 if (!memOp)
298 return false;
299 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
300 memOp.getEffects(effects);
301 return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
302 if (effect.getValue() != value)
303 return false;
304 return isa<EffectTys...>(effect.getEffect());
305 });
306}
307template bool mlir::hasEffect<MemoryEffects::Allocate>(Operation *,
308 Value value);
309template bool mlir::hasEffect<MemoryEffects::Free>(Operation *, Value value);
310template bool mlir::hasEffect<MemoryEffects::Read>(Operation *, Value value);
311template bool mlir::hasEffect<MemoryEffects::Write>(Operation *, Value value);
312template bool
313mlir::hasEffect<MemoryEffects::Write, MemoryEffects::Free>(Operation *,
314 Value value);
315
316template <typename ValueTy, typename... EffectTys>
317bool mlir::hasEffect(Operation *op, ValueTy value) {
318 auto memOp = dyn_cast<MemoryEffectOpInterface>(Val: op);
319 if (!memOp)
320 return false;
321 SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
322 memOp.getEffects(effects);
323 return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &effect) {
324 if (effect.getEffectValue<ValueTy>() != value)
325 return false;
326 return isa<EffectTys...>(effect.getEffect());
327 });
328}
329template bool
330mlir::hasEffect<OpOperand *, MemoryEffects::Allocate>(Operation *, OpOperand *);
331template bool mlir::hasEffect<OpOperand *, MemoryEffects::Free>(Operation *,
332 OpOperand *);
333template bool mlir::hasEffect<OpOperand *, MemoryEffects::Read>(Operation *,
334 OpOperand *);
335template bool mlir::hasEffect<OpOperand *, MemoryEffects::Write>(Operation *,
336 OpOperand *);
337template bool
338mlir::hasEffect<OpOperand *, MemoryEffects::Write, MemoryEffects::Free>(
339 Operation *, OpOperand *);
340
341template bool mlir::hasEffect<OpResult, MemoryEffects::Allocate>(Operation *,
342 OpResult);
343template bool mlir::hasEffect<OpResult, MemoryEffects::Free>(Operation *,
344 OpResult);
345template bool mlir::hasEffect<OpResult, MemoryEffects::Read>(Operation *,
346 OpResult);
347template bool mlir::hasEffect<OpResult, MemoryEffects::Write>(Operation *,
348 OpResult);
349template bool
350mlir::hasEffect<OpResult, MemoryEffects::Write, MemoryEffects::Free>(
351 Operation *, OpResult);
352
353template bool
354mlir::hasEffect<BlockArgument, MemoryEffects::Allocate>(Operation *,
355 BlockArgument);
356template bool
357mlir::hasEffect<BlockArgument, MemoryEffects::Free>(Operation *, BlockArgument);
358template bool
359mlir::hasEffect<BlockArgument, MemoryEffects::Read>(Operation *, BlockArgument);
360template bool
361mlir::hasEffect<BlockArgument, MemoryEffects::Write>(Operation *,
362 BlockArgument);
363template bool
364mlir::hasEffect<BlockArgument, MemoryEffects::Write, MemoryEffects::Free>(
365 Operation *, BlockArgument);
366
367bool mlir::hasUnknownEffects(Operation *op) {
368 return !isa<MemoryEffectOpInterface>(Val: op) &&
369 !op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();
370}
371
372bool mlir::wouldOpBeTriviallyDead(Operation *op) {
373 if (op->mightHaveTrait<OpTrait::IsTerminator>())
374 return false;
375 if (isa<SymbolOpInterface>(Val: op))
376 return false;
377 return wouldOpBeTriviallyDeadImpl(root: op);
378}
379
380bool mlir::isMemoryEffectFree(Operation *op) {
381 if (auto memInterface = dyn_cast<MemoryEffectOpInterface>(Val: op)) {
382 if (!memInterface.hasNoEffect())
383 return false;
384 // If the op does not have recursive side effects, then it is memory effect
385 // free.
386 if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>())
387 return true;
388 } else if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>()) {
389 // Otherwise, if the op does not implement the memory effect interface and
390 // it does not have recursive side effects, then it cannot be known that the
391 // op is moveable.
392 return false;
393 }
394
395 // Recurse into the regions and ensure that all nested ops are memory effect
396 // free.
397 for (Region &region : op->getRegions())
398 for (Operation &op : region.getOps())
399 if (!isMemoryEffectFree(op: &op))
400 return false;
401 return true;
402}
403
404// the returned vector may contain duplicate effects
405std::optional<llvm::SmallVector<MemoryEffects::EffectInstance>>
406mlir::getEffectsRecursively(Operation *rootOp) {
407 SmallVector<MemoryEffects::EffectInstance> effects;
408 SmallVector<Operation *> effectingOps(1, rootOp);
409 while (!effectingOps.empty()) {
410 Operation *op = effectingOps.pop_back_val();
411
412 // If the operation has recursive effects, push all of the nested
413 // operations on to the stack to consider.
414 bool hasRecursiveEffects =
415 op->hasTrait<OpTrait::HasRecursiveMemoryEffects>();
416 if (hasRecursiveEffects) {
417 for (Region &region : op->getRegions()) {
418 for (Block &block : region) {
419 for (Operation &nestedOp : block) {
420 effectingOps.push_back(Elt: &nestedOp);
421 }
422 }
423 }
424 }
425
426 if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(Val: op)) {
427 effectInterface.getEffects(effects);
428 } else if (!hasRecursiveEffects) {
429 // the operation does not have recursive memory effects or implement
430 // the memory effect op interface. Its effects are unknown.
431 return std::nullopt;
432 }
433 }
434 return effects;
435}
436
437bool mlir::isSpeculatable(Operation *op) {
438 auto conditionallySpeculatable = dyn_cast<ConditionallySpeculatable>(Val: op);
439 if (!conditionallySpeculatable)
440 return false;
441
442 switch (conditionallySpeculatable.getSpeculatability()) {
443 case Speculation::RecursivelySpeculatable:
444 for (Region &region : op->getRegions()) {
445 for (Operation &op : region.getOps())
446 if (!isSpeculatable(op: &op))
447 return false;
448 }
449 return true;
450
451 case Speculation::Speculatable:
452 return true;
453
454 case Speculation::NotSpeculatable:
455 return false;
456 }
457
458 llvm_unreachable("Unhandled enum in mlir::isSpeculatable!");
459}
460
461/// The implementation of this function replicates the `def Pure : TraitList`
462/// in `SideEffectInterfaces.td` and has to be kept in sync manually.
463bool mlir::isPure(Operation *op) {
464 return isSpeculatable(op) && isMemoryEffectFree(op);
465}
466