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).
55/// It is also to be noted that a value could be of multiple types (1/2/3) at
56/// the same time.
57///
58/// A value "has memory effects" iff it:
59/// (1.a) is an operand of an op with memory effects OR
60/// (1.b) is a non-forwarded branch operand and its branch op could take the
61/// control to a block that has an op with memory effects OR
62/// (1.c) is a non-forwarded call operand.
63///
64/// A value `A` is said to be "used to compute" value `B` iff `B` cannot be
65/// computed in the absence of `A`. Thus, in this implementation, we say that
66/// value `A` is used to compute value `B` iff:
67/// (3.a) `B` is a result of an op with operand `A` OR
68/// (3.b) `A` is used to compute some value `C` and `C` is used to compute
69/// `B`.
70
71void LivenessAnalysis::visitOperation(Operation *op,
72 ArrayRef<Liveness *> operands,
73 ArrayRef<const Liveness *> results) {
74 // This marks values of type (1.a) liveness as "live".
75 if (!isMemoryEffectFree(op)) {
76 for (auto *operand : operands)
77 propagateIfChanged(operand, operand->markLive());
78 }
79
80 // This marks values of type (3) liveness as "live".
81 bool foundLiveResult = false;
82 for (const Liveness *r : results) {
83 if (r->isLive && !foundLiveResult) {
84 // It is assumed that each operand is used to compute each result of an
85 // op. Thus, if at least one result is live, each operand is live.
86 for (Liveness *operand : operands)
87 meet(operand, *r);
88 foundLiveResult = true;
89 }
90 addDependency(const_cast<Liveness *>(r), op);
91 }
92}
93
94void LivenessAnalysis::visitBranchOperand(OpOperand &operand) {
95 // We know (at the moment) and assume (for the future) that `operand` is a
96 // non-forwarded branch operand of a `RegionBranchOpInterface`,
97 // `BranchOpInterface`, `RegionBranchTerminatorOpInterface` or return-like op.
98 Operation *op = operand.getOwner();
99 assert((isa<RegionBranchOpInterface>(op) || isa<BranchOpInterface>(op) ||
100 isa<RegionBranchTerminatorOpInterface>(op)) &&
101 "expected the op to be `RegionBranchOpInterface`, "
102 "`BranchOpInterface` or `RegionBranchTerminatorOpInterface`");
103
104 // The lattices of the non-forwarded branch operands don't get updated like
105 // the forwarded branch operands or the non-branch operands. Thus they need
106 // to be handled separately. This is where we handle them.
107
108 // This marks values of type (1.b) liveness as "live". A non-forwarded
109 // branch operand will be live if a block where its op could take the control
110 // has an op with memory effects.
111 // Populating such blocks in `blocks`.
112 SmallVector<Block *, 4> blocks;
113 if (isa<RegionBranchOpInterface>(Val: op)) {
114 // When the op is a `RegionBranchOpInterface`, like an `scf.for` or an
115 // `scf.index_switch` op, its branch operand controls the flow into this
116 // op's regions.
117 for (Region &region : op->getRegions()) {
118 for (Block &block : region)
119 blocks.push_back(Elt: &block);
120 }
121 } else if (isa<BranchOpInterface>(Val: op)) {
122 // When the op is a `BranchOpInterface`, like a `cf.cond_br` or a
123 // `cf.switch` op, its branch operand controls the flow into this op's
124 // successors.
125 blocks = op->getSuccessors();
126 } else {
127 // When the op is a `RegionBranchTerminatorOpInterface`, like an
128 // `scf.condition` op or return-like, like an `scf.yield` op, its branch
129 // operand controls the flow into this op's parent's (which is a
130 // `RegionBranchOpInterface`'s) regions.
131 Operation *parentOp = op->getParentOp();
132 assert(isa<RegionBranchOpInterface>(parentOp) &&
133 "expected parent op to implement `RegionBranchOpInterface`");
134 for (Region &region : parentOp->getRegions()) {
135 for (Block &block : region)
136 blocks.push_back(Elt: &block);
137 }
138 }
139 bool foundMemoryEffectingOp = false;
140 for (Block *block : blocks) {
141 if (foundMemoryEffectingOp)
142 break;
143 for (Operation &nestedOp : *block) {
144 if (!isMemoryEffectFree(op: &nestedOp)) {
145 Liveness *operandLiveness = getLatticeElement(operand.get());
146 propagateIfChanged(operandLiveness, operandLiveness->markLive());
147 foundMemoryEffectingOp = true;
148 break;
149 }
150 }
151 }
152
153 // Now that we have checked for memory-effecting ops in the blocks of concern,
154 // we will simply visit the op with this non-forwarded operand to potentially
155 // mark it "live" due to type (1.a/3) liveness.
156 SmallVector<Liveness *, 4> operandLiveness;
157 operandLiveness.push_back(Elt: getLatticeElement(operand.get()));
158 SmallVector<const Liveness *, 4> resultsLiveness;
159 for (const Value result : op->getResults())
160 resultsLiveness.push_back(Elt: getLatticeElement(result));
161 visitOperation(op, operands: operandLiveness, results: resultsLiveness);
162
163 // We also visit the parent op with the parent's results and this operand if
164 // `op` is a `RegionBranchTerminatorOpInterface` because its non-forwarded
165 // operand depends on not only its memory effects/results but also on those of
166 // its parent's.
167 if (!isa<RegionBranchTerminatorOpInterface>(Val: op))
168 return;
169 Operation *parentOp = op->getParentOp();
170 SmallVector<const Liveness *, 4> parentResultsLiveness;
171 for (const Value parentResult : parentOp->getResults())
172 parentResultsLiveness.push_back(Elt: getLatticeElement(parentResult));
173 visitOperation(op: parentOp, operands: operandLiveness, results: parentResultsLiveness);
174}
175
176void LivenessAnalysis::visitCallOperand(OpOperand &operand) {
177 // We know (at the moment) and assume (for the future) that `operand` is a
178 // non-forwarded call operand of an op implementing `CallOpInterface`.
179 assert(isa<CallOpInterface>(operand.getOwner()) &&
180 "expected the op to implement `CallOpInterface`");
181
182 // The lattices of the non-forwarded call operands don't get updated like the
183 // forwarded call operands or the non-call operands. Thus they need to be
184 // handled separately. This is where we handle them.
185
186 // This marks values of type (1.c) liveness as "live". A non-forwarded
187 // call operand is live.
188 Liveness *operandLiveness = getLatticeElement(operand.get());
189 propagateIfChanged(operandLiveness, operandLiveness->markLive());
190}
191
192void LivenessAnalysis::setToExitState(Liveness *lattice) {
193 // This marks values of type (2) liveness as "live".
194 (void)lattice->markLive();
195}
196
197//===----------------------------------------------------------------------===//
198// RunLivenessAnalysis
199//===----------------------------------------------------------------------===//
200
201RunLivenessAnalysis::RunLivenessAnalysis(Operation *op) {
202 SymbolTableCollection symbolTable;
203
204 solver.load<DeadCodeAnalysis>();
205 solver.load<SparseConstantPropagation>();
206 solver.load<LivenessAnalysis>(args&: symbolTable);
207 (void)solver.initializeAndRun(top: op);
208}
209
210const Liveness *RunLivenessAnalysis::getLiveness(Value val) {
211 return solver.lookupState<Liveness>(point: val);
212}
213

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