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 using namespace mlir;
12 
13 //===----------------------------------------------------------------------===//
14 // SideEffect Interfaces
15 //===----------------------------------------------------------------------===//
16 
17 /// Include the definitions of the side effect interfaces.
18 #include "mlir/Interfaces/SideEffectInterfaces.cpp.inc"
19 
20 //===----------------------------------------------------------------------===//
21 // MemoryEffects
22 //===----------------------------------------------------------------------===//
23 
24 bool MemoryEffects::Effect::classof(const SideEffects::Effect *effect) {
25   return isa<Allocate, Free, Read, Write>(effect);
26 }
27 
28 //===----------------------------------------------------------------------===//
29 // SideEffect Utilities
30 //===----------------------------------------------------------------------===//
31 
32 bool mlir::isOpTriviallyDead(Operation *op) {
33   return op->use_empty() && wouldOpBeTriviallyDead(op);
34 }
35 
36 /// Internal implementation of `mlir::wouldOpBeTriviallyDead` that also
37 /// considers terminator operations as dead if they have no side effects. This
38 /// allows for marking region operations as trivially dead without always being
39 /// conservative of terminators.
40 static bool wouldOpBeTriviallyDeadImpl(Operation *rootOp) {
41   // The set of operations to consider when checking for side effects.
42   SmallVector<Operation *, 1> effectingOps(1, rootOp);
43   while (!effectingOps.empty()) {
44     Operation *op = effectingOps.pop_back_val();
45 
46     // If the operation has recursive effects, push all of the nested operations
47     // on to the stack to consider.
48     bool hasRecursiveEffects = op->hasTrait<OpTrait::HasRecursiveSideEffects>();
49     if (hasRecursiveEffects) {
50       for (Region &region : op->getRegions()) {
51         for (auto &block : region) {
52           for (auto &nestedOp : block)
53             effectingOps.push_back(&nestedOp);
54         }
55       }
56     }
57 
58     // If the op has memory effects, try to characterize them to see if the op
59     // is trivially dead here.
60     if (auto effectInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
61       // Check to see if this op either has no effects, or only allocates/reads
62       // memory.
63       SmallVector<MemoryEffects::EffectInstance, 1> effects;
64       effectInterface.getEffects(effects);
65       if (!llvm::all_of(effects, [op](const MemoryEffects::EffectInstance &it) {
66             // We can drop allocations if the value is a result of the
67             // operation.
68             if (isa<MemoryEffects::Allocate>(it.getEffect()))
69               return it.getValue() && it.getValue().getDefiningOp() == op;
70             // Otherwise, the effect must be a read.
71             return isa<MemoryEffects::Read>(it.getEffect());
72           })) {
73         return false;
74       }
75       continue;
76 
77       // Otherwise, if the op has recursive side effects we can treat the
78       // operation itself as having no effects.
79     }
80     if (hasRecursiveEffects)
81       continue;
82 
83     // If there were no effect interfaces, we treat this op as conservatively
84     // having effects.
85     return false;
86   }
87 
88   // If we get here, none of the operations had effects that prevented marking
89   // 'op' as dead.
90   return true;
91 }
92 
93 template <typename EffectTy>
94 bool mlir::hasSingleEffect(Operation *op, Value value) {
95   auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
96   if (!memOp)
97     return false;
98   SmallVector<SideEffects::EffectInstance<MemoryEffects::Effect>, 4> effects;
99   memOp.getEffects(effects);
100   bool doesOpOnlyHaveSingleEffectOnVal = false;
101   // Iterate through `effects` and check if and only if effect of type
102   // `EffectTy` is present.
103   for (auto &effect : effects) {
104     if (effect.getValue() == value && isa<EffectTy>(effect.getEffect()))
105       doesOpOnlyHaveSingleEffectOnVal = true;
106     if (effect.getValue() == value && !isa<EffectTy>(effect.getEffect())) {
107       doesOpOnlyHaveSingleEffectOnVal = false;
108       break;
109     }
110   }
111   return doesOpOnlyHaveSingleEffectOnVal;
112 }
113 
114 template bool mlir::hasSingleEffect<MemoryEffects::Allocate>(Operation *,
115                                                              Value);
116 template bool mlir::hasSingleEffect<MemoryEffects::Free>(Operation *, Value);
117 template bool mlir::hasSingleEffect<MemoryEffects::Write>(Operation *, Value);
118 template bool mlir::hasSingleEffect<MemoryEffects::Read>(Operation *, Value);
119 
120 bool mlir::wouldOpBeTriviallyDead(Operation *op) {
121   if (op->mightHaveTrait<OpTrait::IsTerminator>())
122     return false;
123   return wouldOpBeTriviallyDeadImpl(op);
124 }
125