1//===- LivenessAnalysis.cpp - Liveness analysis ---------------------------===//
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/IR/SymbolTable.h"
10#include <cassert>
11#include <mlir/Analysis/DataFlow/LivenessAnalysis.h>
12
13#include <mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h>
14#include <mlir/Analysis/DataFlow/DeadCodeAnalysis.h>
15#include <mlir/Analysis/DataFlow/SparseAnalysis.h>
16#include <mlir/Analysis/DataFlowFramework.h>
17#include <mlir/IR/Operation.h>
18#include <mlir/IR/Value.h>
19#include <mlir/Interfaces/CallInterfaces.h>
20#include <mlir/Interfaces/SideEffectInterfaces.h>
21#include <mlir/Support/LLVM.h>
22
23using namespace mlir;
24using namespace mlir::dataflow;
25
26//===----------------------------------------------------------------------===//
27// Liveness
28//===----------------------------------------------------------------------===//
29
30void Liveness::print(raw_ostream &os) const {
31 os << (isLive ? "live" : "not live");
32}
33
34ChangeResult Liveness::markLive() {
35 bool wasLive = isLive;
36 isLive = true;
37 return wasLive ? ChangeResult::NoChange : ChangeResult::Change;
38}
39
40ChangeResult Liveness::meet(const AbstractSparseLattice &other) {
41 const auto *otherLiveness = reinterpret_cast<const Liveness *>(&other);
42 return otherLiveness->isLive ? markLive() : ChangeResult::NoChange;
43}
44
45//===----------------------------------------------------------------------===//
46// LivenessAnalysis
47//===----------------------------------------------------------------------===//
48
49/// For every value, liveness analysis determines whether or not it is "live".
50///
51/// A value is considered "live" iff it:
52/// (1) has memory effects OR
53/// (2) is returned by a public function OR
54/// (3) is used to compute a value of type (1) or (2) OR
55/// (4) is returned by a return-like op whose parent isn't a callable
56/// nor a RegionBranchOpInterface (e.g.: linalg.yield, gpu.yield,...)
57/// These ops have their own semantics, so we conservatively mark the
58/// the yield value as live.
59/// It is also to be noted that a value could be of multiple types (1/2/3) at
60/// the same time.
61///
62/// A value "has memory effects" iff it:
63/// (1.a) is an operand of an op with memory effects OR
64/// (1.b) is a non-forwarded branch operand and its branch op could take the
65/// control to a block that has an op with memory effects OR
66/// (1.c) is a non-forwarded branch operand and its branch op could result
67/// in different live result OR
68/// (1.d) is a non-forwarded call operand.
69///
70/// A value `A` is said to be "used to compute" value `B` iff `B` cannot be
71/// computed in the absence of `A`. Thus, in this implementation, we say that
72/// value `A` is used to compute value `B` iff:
73/// (3.a) `B` is a result of an op with operand `A` OR
74/// (3.b) `A` is used to compute some value `C` and `C` is used to compute
75/// `B`.
76
77LogicalResult
78LivenessAnalysis::visitOperation(Operation *op, ArrayRef<Liveness *> operands,
79 ArrayRef<const Liveness *> results) {
80 // This marks values of type (1.a) and (4) liveness as "live".
81 if (!isMemoryEffectFree(op) || op->hasTrait<OpTrait::ReturnLike>()) {
82 for (auto *operand : operands)
83 propagateIfChanged(state: operand, changed: operand->markLive());
84 }
85
86 // This marks values of type (3) liveness as "live".
87 bool foundLiveResult = false;
88 for (const Liveness *r : results) {
89 if (r->isLive && !foundLiveResult) {
90 // It is assumed that each operand is used to compute each result of an
91 // op. Thus, if at least one result is live, each operand is live.
92 for (Liveness *operand : operands)
93 meet(lhs: operand, rhs: *r);
94 foundLiveResult = true;
95 }
96 addDependency(state: const_cast<Liveness *>(r), point: getProgramPointAfter(op));
97 }
98 return success();
99}
100
101void LivenessAnalysis::visitBranchOperand(OpOperand &operand) {
102 // We know (at the moment) and assume (for the future) that `operand` is a
103 // non-forwarded branch operand of a `RegionBranchOpInterface`,
104 // `BranchOpInterface`, `RegionBranchTerminatorOpInterface` or return-like op.
105 Operation *op = operand.getOwner();
106 assert((isa<RegionBranchOpInterface>(op) || isa<BranchOpInterface>(op) ||
107 isa<RegionBranchTerminatorOpInterface>(op)) &&
108 "expected the op to be `RegionBranchOpInterface`, "
109 "`BranchOpInterface` or `RegionBranchTerminatorOpInterface`");
110
111 // The lattices of the non-forwarded branch operands don't get updated like
112 // the forwarded branch operands or the non-branch operands. Thus they need
113 // to be handled separately. This is where we handle them.
114
115 // This marks values of type (1.b/1.c) liveness as "live". A non-forwarded
116 // branch operand will be live if a block where its op could take the control
117 // has an op with memory effects or could result in different results.
118 // Populating such blocks in `blocks`.
119 bool mayLive = false;
120 SmallVector<Block *, 4> blocks;
121 if (isa<RegionBranchOpInterface>(Val: op)) {
122 if (op->getNumResults() != 0) {
123 // This mark value of type 1.c liveness as may live, because the region
124 // branch operation has a return value, and the non-forwarded operand can
125 // determine the region to jump to, it can thereby control the result of
126 // the region branch operation.
127 // Therefore, if the result value is live, we conservatively consider the
128 // non-forwarded operand of the region branch operation with result may
129 // live and record all result.
130 for (Value result : op->getResults()) {
131 if (getLatticeElement(value: result)->isLive) {
132 mayLive = true;
133 break;
134 }
135 }
136 } else {
137 // When the op is a `RegionBranchOpInterface`, like an `scf.for` or an
138 // `scf.index_switch` op, its branch operand controls the flow into this
139 // op's regions.
140 for (Region &region : op->getRegions()) {
141 for (Block &block : region)
142 blocks.push_back(Elt: &block);
143 }
144 }
145 } else if (isa<BranchOpInterface>(Val: op)) {
146 // We cannot track all successor blocks of the branch operation(More
147 // specifically, it's the successor's successor). Additionally, different
148 // blocks might also lead to the different block argument described in 1.c.
149 // Therefore, we conservatively consider the non-forwarded operand of the
150 // branch operation may live.
151 mayLive = true;
152 } else {
153 Operation *parentOp = op->getParentOp();
154 assert(isa<RegionBranchOpInterface>(parentOp) &&
155 "expected parent op to implement `RegionBranchOpInterface`");
156 if (parentOp->getNumResults() != 0) {
157 // This mark value of type 1.c liveness as may live, because the region
158 // branch operation has a return value, and the non-forwarded operand can
159 // determine the region to jump to, it can thereby control the result of
160 // the region branch operation.
161 // Therefore, if the result value is live, we conservatively consider the
162 // non-forwarded operand of the region branch operation with result may
163 // live and record all result.
164 for (Value result : parentOp->getResults()) {
165 if (getLatticeElement(value: result)->isLive) {
166 mayLive = true;
167 break;
168 }
169 }
170 } else {
171 // When the op is a `RegionBranchTerminatorOpInterface`, like an
172 // `scf.condition` op or return-like, like an `scf.yield` op, its branch
173 // operand controls the flow into this op's parent's (which is a
174 // `RegionBranchOpInterface`'s) regions.
175 for (Region &region : parentOp->getRegions()) {
176 for (Block &block : region)
177 blocks.push_back(Elt: &block);
178 }
179 }
180 }
181 for (Block *block : blocks) {
182 if (mayLive)
183 break;
184 for (Operation &nestedOp : *block) {
185 if (!isMemoryEffectFree(op: &nestedOp)) {
186 mayLive = true;
187 break;
188 }
189 }
190 }
191
192 if (mayLive) {
193 Liveness *operandLiveness = getLatticeElement(value: operand.get());
194 propagateIfChanged(state: operandLiveness, changed: operandLiveness->markLive());
195 }
196
197 // Now that we have checked for memory-effecting ops in the blocks of concern,
198 // we will simply visit the op with this non-forwarded operand to potentially
199 // mark it "live" due to type (1.a/3) liveness.
200 SmallVector<Liveness *, 4> operandLiveness;
201 operandLiveness.push_back(Elt: getLatticeElement(value: operand.get()));
202 SmallVector<const Liveness *, 4> resultsLiveness;
203 for (const Value result : op->getResults())
204 resultsLiveness.push_back(Elt: getLatticeElement(value: result));
205 (void)visitOperation(op, operands: operandLiveness, results: resultsLiveness);
206
207 // We also visit the parent op with the parent's results and this operand if
208 // `op` is a `RegionBranchTerminatorOpInterface` because its non-forwarded
209 // operand depends on not only its memory effects/results but also on those of
210 // its parent's.
211 if (!isa<RegionBranchTerminatorOpInterface>(Val: op))
212 return;
213 Operation *parentOp = op->getParentOp();
214 SmallVector<const Liveness *, 4> parentResultsLiveness;
215 for (const Value parentResult : parentOp->getResults())
216 parentResultsLiveness.push_back(Elt: getLatticeElement(value: parentResult));
217 (void)visitOperation(op: parentOp, operands: operandLiveness, results: parentResultsLiveness);
218}
219
220void LivenessAnalysis::visitCallOperand(OpOperand &operand) {
221 // We know (at the moment) and assume (for the future) that `operand` is a
222 // non-forwarded call operand of an op implementing `CallOpInterface`.
223 assert(isa<CallOpInterface>(operand.getOwner()) &&
224 "expected the op to implement `CallOpInterface`");
225
226 // The lattices of the non-forwarded call operands don't get updated like the
227 // forwarded call operands or the non-call operands. Thus they need to be
228 // handled separately. This is where we handle them.
229
230 // This marks values of type (1.c) liveness as "live". A non-forwarded
231 // call operand is live.
232 Liveness *operandLiveness = getLatticeElement(value: operand.get());
233 propagateIfChanged(state: operandLiveness, changed: operandLiveness->markLive());
234}
235
236void LivenessAnalysis::setToExitState(Liveness *lattice) {
237 if (lattice->isLive) {
238 return;
239 }
240 // This marks values of type (2) liveness as "live".
241 (void)lattice->markLive();
242 propagateIfChanged(state: lattice, changed: ChangeResult::Change);
243}
244
245//===----------------------------------------------------------------------===//
246// RunLivenessAnalysis
247//===----------------------------------------------------------------------===//
248
249RunLivenessAnalysis::RunLivenessAnalysis(Operation *op) {
250 SymbolTableCollection symbolTable;
251
252 solver.load<DeadCodeAnalysis>();
253 solver.load<SparseConstantPropagation>();
254 solver.load<LivenessAnalysis>(args&: symbolTable);
255 (void)solver.initializeAndRun(top: op);
256}
257
258const Liveness *RunLivenessAnalysis::getLiveness(Value val) {
259 return solver.lookupState<Liveness>(anchor: val);
260}
261

source code of mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp