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/DebugLog.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
25using namespace mlir;
26using namespace mlir::dataflow;
27
28//===----------------------------------------------------------------------===//
29// Liveness
30//===----------------------------------------------------------------------===//
31
32void Liveness::print(raw_ostream &os) const {
33 os << (isLive ? "live" : "not live");
34}
35
36ChangeResult Liveness::markLive() {
37 bool wasLive = isLive;
38 isLive = true;
39 return wasLive ? ChangeResult::NoChange : ChangeResult::Change;
40}
41
42ChangeResult Liveness::meet(const AbstractSparseLattice &other) {
43 const auto *otherLiveness = reinterpret_cast<const Liveness *>(&other);
44 return otherLiveness->isLive ? markLive() : ChangeResult::NoChange;
45}
46
47//===----------------------------------------------------------------------===//
48// LivenessAnalysis
49//===----------------------------------------------------------------------===//
50
51LogicalResult LivenessAnalysis::initialize(Operation *top) {
52 // Users outside the analysis root are not visited. Mark all root results live
53 // so that this missing information does not make their producers dead. For a
54 // region branch root, this keeps the yielded values and their producers live.
55 for (Value result : top->getResults())
56 setToExitState(getLatticeElement(value: result));
57 return SparseBackwardDataFlowAnalysis<Liveness>::initialize(top);
58}
59
60/// For every value, liveness analysis determines whether or not it is "live".
61///
62/// A value is considered "live" iff it:
63/// (1) has memory effects OR
64/// (2) is returned by a public function OR
65/// (3) is used to compute a value of type (1) or (2) OR
66/// (4) is returned by a return-like op whose parent isn't a callable
67/// nor a RegionBranchOpInterface (e.g.: linalg.yield, gpu.yield,...)
68/// These ops have their own semantics, so we conservatively mark the
69/// the yield value as live.
70/// It is also to be noted that a value could be of multiple types (1/2/3) at
71/// the same time.
72///
73/// A value "has memory effects" iff it:
74/// (1.a) is an operand of an op with memory effects OR
75/// (1.b) is a non-forwarded branch operand and its branch op could take the
76/// control to a block that has an op with memory effects OR
77/// (1.c) is a non-forwarded branch operand and its branch op could result
78/// in different live result OR
79/// (1.d) is a non-forwarded call operand.
80///
81/// A value `A` is said to be "used to compute" value `B` iff `B` cannot be
82/// computed in the absence of `A`. Thus, in this implementation, we say that
83/// value `A` is used to compute value `B` iff:
84/// (3.a) `B` is a result of an op with operand `A` OR
85/// (3.b) `A` is used to compute some value `C` and `C` is used to compute
86/// `B`.
87
88LogicalResult
89LivenessAnalysis::visitOperation(Operation *op, ArrayRef<Liveness *> operands,
90 ArrayRef<const Liveness *> results) {
91 LDBG() << "[visitOperation] Enter: "
92 << OpWithFlags(op, OpPrintingFlags().skipRegions());
93 // This marks values of type (1.a) and (4) liveness as "live".
94 if (!wouldOpBeTriviallyDead(op)) {
95 LDBG() << "[visitOperation] Operation has memory effects or is "
96 "return-like, marking operands live";
97 for (auto *operand : operands) {
98 LDBG() << " [visitOperation] Marking operand live: " << operand << " ("
99 << operand->isLive << ")";
100 propagateIfChanged(state: operand, changed: operand->markLive());
101 }
102 }
103
104 // This marks values of type (3) liveness as "live".
105 bool foundLiveResult = false;
106 for (const Liveness *r : results) {
107 if (r->isLive && !foundLiveResult) {
108 LDBG() << "[visitOperation] Found live result, "
109 "meeting all operands with result: "
110 << r;
111 // It is assumed that each operand is used to compute each result of an
112 // op. Thus, if at least one result is live, each operand is live.
113 for (Liveness *operand : operands) {
114 LDBG() << " [visitOperation] Meeting operand: " << operand
115 << " with result: " << r;
116 meet(lhs: operand, rhs: *r);
117 }
118 foundLiveResult = true;
119 }
120 LDBG() << "[visitOperation] Adding dependency for result: " << r
121 << " after op: " << OpWithFlags(op, OpPrintingFlags().skipRegions());
122 addDependency(state: const_cast<Liveness *>(r), point: getProgramPointAfter(op));
123 }
124 return success();
125}
126
127void LivenessAnalysis::visitBranchOperand(OpOperand &operand) {
128 Operation *op = operand.getOwner();
129 LDBG() << "Visiting branch operand: " << operand.get()
130 << " in op: " << OpWithFlags(op, OpPrintingFlags().skipRegions());
131 // We know (at the moment) and assume (for the future) that `operand` is a
132 // non-forwarded branch operand of a `RegionBranchOpInterface`,
133 // `BranchOpInterface`, `RegionBranchTerminatorOpInterface` or return-like op.
134 assert((isa<RegionBranchOpInterface>(op) || isa<BranchOpInterface>(op) ||
135 isa<RegionBranchTerminatorOpInterface>(op)) &&
136 "expected the op to be `RegionBranchOpInterface`, "
137 "`BranchOpInterface` or `RegionBranchTerminatorOpInterface`");
138
139 // The lattices of the non-forwarded branch operands don't get updated like
140 // the forwarded branch operands or the non-branch operands. Thus they need
141 // to be handled separately. This is where we handle them.
142
143 // 1. BranchOpInterface: We cannot track all successor blocks. Therefore, we
144 // conservatively consider the non-forwarded operand of the branch operation
145 // live. We can just call visitOperation, which treats any terminator as live.
146 // 2. RegionBranchOpInterface: We can simply visit it as a normal operation
147 // with this operand. The operand is live if the results of the op are used,
148 // or if it has any recursive memory side effects (which visitOperation will
149 // check).
150 // 3. RegionBranchOpTerminatorInterface, the operand is live if the
151 // surrounding RegionBranchOp is live, so we call visitOperation on the
152 // surrounding op, but with the operand that we are looking at.
153 auto *visitOp =
154 isa<RegionBranchTerminatorOpInterface>(Val: op) ? op->getParentOp() : op;
155 Liveness *operandLiveness[] = {getLatticeElement(value: operand.get())};
156 SmallVector<const Liveness *, 4> resultsLiveness;
157 for (const Value result : visitOp->getResults())
158 resultsLiveness.push_back(Elt: getLatticeElement(value: result));
159 LDBG() << "Visiting operation for non-forwarded branch operand: "
160 << OpWithFlags(visitOp, OpPrintingFlags().skipRegions());
161 (void)visitOperation(op: visitOp, operands: operandLiveness, results: resultsLiveness);
162}
163
164void LivenessAnalysis::visitCallOperand(OpOperand &operand) {
165 LDBG() << "Visiting call operand: " << operand.get()
166 << " in op: " << *operand.getOwner();
167 // We know (at the moment) and assume (for the future) that `operand` is a
168 // non-forwarded call operand of an op implementing `CallOpInterface`.
169 assert(isa<CallOpInterface>(operand.getOwner()) &&
170 "expected the op to implement `CallOpInterface`");
171
172 // The lattices of the non-forwarded call operands don't get updated like the
173 // forwarded call operands or the non-call operands. Thus they need to be
174 // handled separately. This is where we handle them.
175
176 // This marks values of type (1.c) liveness as "live". A non-forwarded
177 // call operand is live.
178 Liveness *operandLiveness = getLatticeElement(value: operand.get());
179 LDBG() << "Marking call operand live: " << operand.get();
180 propagateIfChanged(state: operandLiveness, changed: operandLiveness->markLive());
181}
182
183void LivenessAnalysis::visitNonControlFlowArguments(
184 RegionSuccessor &successor, ArrayRef<BlockArgument> arguments) {
185 assert(successor.isRegion() && "expected a region successor");
186 Operation *parentOp = successor.getSuccessor()->getParentOp();
187 LDBG() << "visitNonControlFlowArguments visit the region: #"
188 << successor.getSuccessor()->getRegionNumber() << " of "
189 << OpWithFlags(parentOp, OpPrintingFlags().skipRegions());
190 auto valuesToLattices = [&](Value value) { return getLatticeElement(value); };
191 SmallVector<Liveness *> argumentLattices =
192 llvm::map_to_vector(C&: arguments, F&: valuesToLattices);
193 SmallVector<Liveness *> parentResultLattices =
194 llvm::map_to_vector(C: parentOp->getResults(), F&: valuesToLattices);
195
196 for (Liveness *resultLattice : parentResultLattices) {
197 if (resultLattice->isLive) {
198 for (Liveness *argumentLattice : argumentLattices) {
199 LDBG() << "make lattice: " << argumentLattice << " live";
200 propagateIfChanged(state: argumentLattice, changed: argumentLattice->markLive());
201 }
202 return;
203 }
204 }
205 (void)visitOperation(op: parentOp, operands: argumentLattices, results: parentResultLattices);
206}
207
208void LivenessAnalysis::setToExitState(Liveness *lattice) {
209 LDBG() << "setToExitState for lattice: " << lattice;
210 if (lattice->isLive) {
211 LDBG() << "Lattice already live, nothing to do";
212 return;
213 }
214 // This marks values of type (2) liveness as "live".
215 LDBG() << "Marking lattice live due to exit state";
216 (void)lattice->markLive();
217 propagateIfChanged(state: lattice, changed: ChangeResult::Change);
218}
219
220//===----------------------------------------------------------------------===//
221// RunLivenessAnalysis
222//===----------------------------------------------------------------------===//
223
224RunLivenessAnalysis::RunLivenessAnalysis(Operation *op) {
225 LDBG() << "Constructing RunLivenessAnalysis for op: " << op->getName();
226 SymbolTableCollection symbolTable;
227
228 loadBaselineAnalyses(solver);
229 solver.load<LivenessAnalysis>(args&: symbolTable);
230 LDBG() << "Initializing and running solver";
231 (void)solver.initializeAndRun(top: op);
232 LDBG() << "RunLivenessAnalysis initialized for op: " << op->getName()
233 << " check on unreachable code now:";
234 // The framework doesn't visit operations in dead blocks, so we need to
235 // explicitly mark them as dead.
236 op->walk(callback: [&](Operation *op) {
237 for (auto result : llvm::enumerate(First: op->getResults())) {
238 if (getLiveness(val: result.value()))
239 continue;
240 LDBG() << "Result: " << result.index() << " of "
241 << OpWithFlags(op, OpPrintingFlags().skipRegions())
242 << " has no liveness info (unreachable), mark dead";
243 solver.getOrCreateState<Liveness>(anchor: result.value());
244 }
245 for (auto &region : op->getRegions()) {
246 for (auto &block : region) {
247 for (auto blockArg : llvm::enumerate(First: block.getArguments())) {
248 if (getLiveness(val: blockArg.value()))
249 continue;
250 LDBG() << "Block argument: " << blockArg.index() << " of "
251 << OpWithFlags(op, OpPrintingFlags().skipRegions())
252 << " has no liveness info, mark dead";
253 solver.getOrCreateState<Liveness>(anchor: blockArg.value());
254 }
255 }
256 }
257 });
258}
259
260const Liveness *RunLivenessAnalysis::getLiveness(Value val) {
261 return solver.lookupState<Liveness>(anchor: val);
262}
263