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 <llvm/Support/Debug.h>
14#include <mlir/Analysis/DataFlow/SparseAnalysis.h>
15#include <mlir/Analysis/DataFlow/Utils.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
23#define DEBUG_TYPE "liveness-analysis"
24#define DBGS() (llvm::dbgs() << '[' << DEBUG_TYPE << "] ")
25#define LDBG(X) LLVM_DEBUG(DBGS() << X << "\n")
26
27using namespace mlir;
28using namespace mlir::dataflow;
29
30//===----------------------------------------------------------------------===//
31// Liveness
32//===----------------------------------------------------------------------===//
33
34void Liveness::print(raw_ostream &os) const {
35 os << (isLive ? "live" : "not live");
36}
37
38ChangeResult Liveness::markLive() {
39 bool wasLive = isLive;
40 isLive = true;
41 return wasLive ? ChangeResult::NoChange : ChangeResult::Change;
42}
43
44ChangeResult Liveness::meet(const AbstractSparseLattice &other) {
45 const auto *otherLiveness = reinterpret_cast<const Liveness *>(&other);
46 return otherLiveness->isLive ? markLive() : ChangeResult::NoChange;
47}
48
49//===----------------------------------------------------------------------===//
50// LivenessAnalysis
51//===----------------------------------------------------------------------===//
52
53/// For every value, liveness analysis determines whether or not it is "live".
54///
55/// A value is considered "live" iff it:
56/// (1) has memory effects OR
57/// (2) is returned by a public function OR
58/// (3) is used to compute a value of type (1) or (2) OR
59/// (4) is returned by a return-like op whose parent isn't a callable
60/// nor a RegionBranchOpInterface (e.g.: linalg.yield, gpu.yield,...)
61/// These ops have their own semantics, so we conservatively mark the
62/// the yield value as live.
63/// It is also to be noted that a value could be of multiple types (1/2/3) at
64/// the same time.
65///
66/// A value "has memory effects" iff it:
67/// (1.a) is an operand of an op with memory effects OR
68/// (1.b) is a non-forwarded branch operand and its branch op could take the
69/// control to a block that has an op with memory effects OR
70/// (1.c) is a non-forwarded branch operand and its branch op could result
71/// in different live result OR
72/// (1.d) is a non-forwarded call operand.
73///
74/// A value `A` is said to be "used to compute" value `B` iff `B` cannot be
75/// computed in the absence of `A`. Thus, in this implementation, we say that
76/// value `A` is used to compute value `B` iff:
77/// (3.a) `B` is a result of an op with operand `A` OR
78/// (3.b) `A` is used to compute some value `C` and `C` is used to compute
79/// `B`.
80
81LogicalResult
82LivenessAnalysis::visitOperation(Operation *op, ArrayRef<Liveness *> operands,
83 ArrayRef<const Liveness *> results) {
84 LLVM_DEBUG(DBGS() << "[visitOperation] Enter: ";
85 op->print(llvm::dbgs(), OpPrintingFlags().skipRegions());
86 llvm::dbgs() << "\n");
87 // This marks values of type (1.a) and (4) liveness as "live".
88 if (!isMemoryEffectFree(op) || op->hasTrait<OpTrait::ReturnLike>()) {
89 LDBG("[visitOperation] Operation has memory effects or is "
90 "return-like, marking operands live");
91 for (auto *operand : operands) {
92 LDBG(" [visitOperation] Marking operand live: "
93 << operand << " (" << operand->isLive << ")");
94 propagateIfChanged(state: operand, changed: operand->markLive());
95 }
96 }
97
98 // This marks values of type (3) liveness as "live".
99 bool foundLiveResult = false;
100 for (const Liveness *r : results) {
101 if (r->isLive && !foundLiveResult) {
102 LDBG("[visitOperation] Found live result, "
103 "meeting all operands with result: "
104 << r);
105 // It is assumed that each operand is used to compute each result of an
106 // op. Thus, if at least one result is live, each operand is live.
107 for (Liveness *operand : operands) {
108 LDBG(" [visitOperation] Meeting operand: " << operand
109 << " with result: " << r);
110 meet(lhs: operand, rhs: *r);
111 }
112 foundLiveResult = true;
113 }
114 LDBG("[visitOperation] Adding dependency for result: " << r << " after op: "
115 << *op);
116 addDependency(state: const_cast<Liveness *>(r), point: getProgramPointAfter(op));
117 }
118 return success();
119}
120
121void LivenessAnalysis::visitBranchOperand(OpOperand &operand) {
122 LDBG("Visiting branch operand: " << operand.get()
123 << " in op: " << *operand.getOwner());
124 // We know (at the moment) and assume (for the future) that `operand` is a
125 // non-forwarded branch operand of a `RegionBranchOpInterface`,
126 // `BranchOpInterface`, `RegionBranchTerminatorOpInterface` or return-like op.
127 Operation *op = operand.getOwner();
128 assert((isa<RegionBranchOpInterface>(op) || isa<BranchOpInterface>(op) ||
129 isa<RegionBranchTerminatorOpInterface>(op)) &&
130 "expected the op to be `RegionBranchOpInterface`, "
131 "`BranchOpInterface` or `RegionBranchTerminatorOpInterface`");
132
133 // The lattices of the non-forwarded branch operands don't get updated like
134 // the forwarded branch operands or the non-branch operands. Thus they need
135 // to be handled separately. This is where we handle them.
136
137 // This marks values of type (1.b/1.c) liveness as "live". A non-forwarded
138 // branch operand will be live if a block where its op could take the control
139 // has an op with memory effects or could result in different results.
140 // Populating such blocks in `blocks`.
141 bool mayLive = false;
142 SmallVector<Block *, 4> blocks;
143 if (isa<RegionBranchOpInterface>(Val: op)) {
144 if (op->getNumResults() != 0) {
145 // This mark value of type 1.c liveness as may live, because the region
146 // branch operation has a return value, and the non-forwarded operand can
147 // determine the region to jump to, it can thereby control the result of
148 // the region branch operation.
149 // Therefore, if the result value is live, we conservatively consider the
150 // non-forwarded operand of the region branch operation with result may
151 // live and record all result.
152 for (Value result : op->getResults()) {
153 if (getLatticeElement(value: result)->isLive) {
154 mayLive = true;
155 LDBG("[visitBranchOperand] Non-forwarded branch "
156 "operand may be live due to live result: "
157 << result);
158 break;
159 }
160 }
161 } else {
162 // When the op is a `RegionBranchOpInterface`, like an `scf.for` or an
163 // `scf.index_switch` op, its branch operand controls the flow into this
164 // op's regions.
165 for (Region &region : op->getRegions()) {
166 for (Block &block : region)
167 blocks.push_back(Elt: &block);
168 }
169 }
170 } else if (isa<BranchOpInterface>(Val: op)) {
171 // We cannot track all successor blocks of the branch operation(More
172 // specifically, it's the successor's successor). Additionally, different
173 // blocks might also lead to the different block argument described in 1.c.
174 // Therefore, we conservatively consider the non-forwarded operand of the
175 // branch operation may live.
176 mayLive = true;
177 LDBG("[visitBranchOperand] Non-forwarded branch operand may "
178 "be live due to branch op interface");
179 } else {
180 Operation *parentOp = op->getParentOp();
181 assert(isa<RegionBranchOpInterface>(parentOp) &&
182 "expected parent op to implement `RegionBranchOpInterface`");
183 if (parentOp->getNumResults() != 0) {
184 // This mark value of type 1.c liveness as may live, because the region
185 // branch operation has a return value, and the non-forwarded operand can
186 // determine the region to jump to, it can thereby control the result of
187 // the region branch operation.
188 // Therefore, if the result value is live, we conservatively consider the
189 // non-forwarded operand of the region branch operation with result may
190 // live and record all result.
191 for (Value result : parentOp->getResults()) {
192 if (getLatticeElement(value: result)->isLive) {
193 mayLive = true;
194 LDBG("[visitBranchOperand] Non-forwarded branch "
195 "operand may be live due to parent live result: "
196 << result);
197 break;
198 }
199 }
200 } else {
201 // When the op is a `RegionBranchTerminatorOpInterface`, like an
202 // `scf.condition` op or return-like, like an `scf.yield` op, its branch
203 // operand controls the flow into this op's parent's (which is a
204 // `RegionBranchOpInterface`'s) regions.
205 for (Region &region : parentOp->getRegions()) {
206 for (Block &block : region)
207 blocks.push_back(Elt: &block);
208 }
209 }
210 }
211 for (Block *block : blocks) {
212 if (mayLive)
213 break;
214 for (Operation &nestedOp : *block) {
215 if (!isMemoryEffectFree(op: &nestedOp)) {
216 mayLive = true;
217 LDBG("Non-forwarded branch operand may be "
218 "live due to memory effect in block: "
219 << block);
220 break;
221 }
222 }
223 }
224
225 if (mayLive) {
226 Liveness *operandLiveness = getLatticeElement(value: operand.get());
227 LDBG("Marking branch operand live: " << operand.get());
228 propagateIfChanged(state: operandLiveness, changed: operandLiveness->markLive());
229 }
230
231 // Now that we have checked for memory-effecting ops in the blocks of concern,
232 // we will simply visit the op with this non-forwarded operand to potentially
233 // mark it "live" due to type (1.a/3) liveness.
234 SmallVector<Liveness *, 4> operandLiveness;
235 operandLiveness.push_back(Elt: getLatticeElement(value: operand.get()));
236 SmallVector<const Liveness *, 4> resultsLiveness;
237 for (const Value result : op->getResults())
238 resultsLiveness.push_back(Elt: getLatticeElement(value: result));
239 LDBG("Visiting operation for non-forwarded branch operand: " << *op);
240 (void)visitOperation(op, operands: operandLiveness, results: resultsLiveness);
241
242 // We also visit the parent op with the parent's results and this operand if
243 // `op` is a `RegionBranchTerminatorOpInterface` because its non-forwarded
244 // operand depends on not only its memory effects/results but also on those of
245 // its parent's.
246 if (!isa<RegionBranchTerminatorOpInterface>(Val: op))
247 return;
248 Operation *parentOp = op->getParentOp();
249 SmallVector<const Liveness *, 4> parentResultsLiveness;
250 for (const Value parentResult : parentOp->getResults())
251 parentResultsLiveness.push_back(Elt: getLatticeElement(value: parentResult));
252 LDBG("Visiting parent operation for non-forwarded branch operand: "
253 << *parentOp);
254 (void)visitOperation(op: parentOp, operands: operandLiveness, results: parentResultsLiveness);
255}
256
257void LivenessAnalysis::visitCallOperand(OpOperand &operand) {
258 LDBG("Visiting call operand: " << operand.get()
259 << " in op: " << *operand.getOwner());
260 // We know (at the moment) and assume (for the future) that `operand` is a
261 // non-forwarded call operand of an op implementing `CallOpInterface`.
262 assert(isa<CallOpInterface>(operand.getOwner()) &&
263 "expected the op to implement `CallOpInterface`");
264
265 // The lattices of the non-forwarded call operands don't get updated like the
266 // forwarded call operands or the non-call operands. Thus they need to be
267 // handled separately. This is where we handle them.
268
269 // This marks values of type (1.c) liveness as "live". A non-forwarded
270 // call operand is live.
271 Liveness *operandLiveness = getLatticeElement(value: operand.get());
272 LDBG("Marking call operand live: " << operand.get());
273 propagateIfChanged(state: operandLiveness, changed: operandLiveness->markLive());
274}
275
276void LivenessAnalysis::setToExitState(Liveness *lattice) {
277 LDBG("setToExitState for lattice: " << lattice);
278 if (lattice->isLive) {
279 LDBG("Lattice already live, nothing to do");
280 return;
281 }
282 // This marks values of type (2) liveness as "live".
283 LDBG("Marking lattice live due to exit state");
284 (void)lattice->markLive();
285 propagateIfChanged(state: lattice, changed: ChangeResult::Change);
286}
287
288//===----------------------------------------------------------------------===//
289// RunLivenessAnalysis
290//===----------------------------------------------------------------------===//
291
292RunLivenessAnalysis::RunLivenessAnalysis(Operation *op) {
293 LDBG("Constructing RunLivenessAnalysis for op: " << op->getName());
294 SymbolTableCollection symbolTable;
295
296 loadBaselineAnalyses(solver);
297 solver.load<LivenessAnalysis>(args&: symbolTable);
298 LLVM_DEBUG({ llvm::dbgs() << "Initializing and running solver\n"; });
299 (void)solver.initializeAndRun(top: op);
300 LLVM_DEBUG({
301 llvm::dbgs() << "RunLivenessAnalysis initialized for op: " << op->getName()
302 << " check on unreachable code now:"
303 << "\n";
304 });
305 // The framework doesn't visit operations in dead blocks, so we need to
306 // explicitly mark them as dead.
307 op->walk(callback: [&](Operation *op) {
308 if (op->getNumResults() == 0)
309 return;
310 for (auto result : llvm::enumerate(First: op->getResults())) {
311 if (getLiveness(val: result.value()))
312 continue;
313 LLVM_DEBUG({
314 llvm::dbgs() << "Result: " << result.index() << " of "
315 << OpWithFlags(op, OpPrintingFlags().skipRegions())
316 << " has no liveness info (unreachable), mark dead"
317 << "\n";
318 });
319 solver.getOrCreateState<Liveness>(anchor: result.value());
320 }
321 for (auto &region : op->getRegions()) {
322 for (auto &block : region) {
323 for (auto blockArg : llvm::enumerate(First: block.getArguments())) {
324 if (getLiveness(val: blockArg.value()))
325 continue;
326 LLVM_DEBUG({
327 llvm::dbgs() << "Block argument: " << blockArg.index() << " of "
328 << OpWithFlags(op, OpPrintingFlags().skipRegions())
329 << " has no liveness info, mark dead"
330 << "\n";
331 });
332 solver.getOrCreateState<Liveness>(anchor: blockArg.value());
333 }
334 }
335 }
336 });
337}
338
339const Liveness *RunLivenessAnalysis::getLiveness(Value val) {
340 return solver.lookupState<Liveness>(anchor: val);
341}
342

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