MLIR  22.0.0git
LivenessAnalysis.cpp
Go to the documentation of this file.
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>
12 
13 #include <llvm/Support/DebugLog.h>
17 #include <mlir/IR/Operation.h>
18 #include <mlir/IR/Value.h>
21 #include <mlir/Support/LLVM.h>
22 
23 #define DEBUG_TYPE "liveness-analysis"
24 
25 using namespace mlir;
26 using namespace mlir::dataflow;
27 
28 //===----------------------------------------------------------------------===//
29 // Liveness
30 //===----------------------------------------------------------------------===//
31 
32 void Liveness::print(raw_ostream &os) const {
33  os << (isLive ? "live" : "not live");
34 }
35 
37  bool wasLive = isLive;
38  isLive = true;
40 }
41 
43  const auto *otherLiveness = reinterpret_cast<const Liveness *>(&other);
44  return otherLiveness->isLive ? markLive() : ChangeResult::NoChange;
45 }
46 
47 //===----------------------------------------------------------------------===//
48 // LivenessAnalysis
49 //===----------------------------------------------------------------------===//
50 
51 /// For every value, liveness analysis determines whether or not it is "live".
52 ///
53 /// A value is considered "live" iff it:
54 /// (1) has memory effects OR
55 /// (2) is returned by a public function OR
56 /// (3) is used to compute a value of type (1) or (2) OR
57 /// (4) is returned by a return-like op whose parent isn't a callable
58 /// nor a RegionBranchOpInterface (e.g.: linalg.yield, gpu.yield,...)
59 /// These ops have their own semantics, so we conservatively mark the
60 /// the yield value as live.
61 /// It is also to be noted that a value could be of multiple types (1/2/3) at
62 /// the same time.
63 ///
64 /// A value "has memory effects" iff it:
65 /// (1.a) is an operand of an op with memory effects OR
66 /// (1.b) is a non-forwarded branch operand and its branch op could take the
67 /// control to a block that has an op with memory effects OR
68 /// (1.c) is a non-forwarded branch operand and its branch op could result
69 /// in different live result OR
70 /// (1.d) is a non-forwarded call operand.
71 ///
72 /// A value `A` is said to be "used to compute" value `B` iff `B` cannot be
73 /// computed in the absence of `A`. Thus, in this implementation, we say that
74 /// value `A` is used to compute value `B` iff:
75 /// (3.a) `B` is a result of an op with operand `A` OR
76 /// (3.b) `A` is used to compute some value `C` and `C` is used to compute
77 /// `B`.
78 
79 LogicalResult
82  LDBG() << "[visitOperation] Enter: "
83  << OpWithFlags(op, OpPrintingFlags().skipRegions());
84  // This marks values of type (1.a) and (4) liveness as "live".
85  if (!isMemoryEffectFree(op) || op->hasTrait<OpTrait::ReturnLike>()) {
86  LDBG() << "[visitOperation] Operation has memory effects or is "
87  "return-like, marking operands live";
88  for (auto *operand : operands) {
89  LDBG() << " [visitOperation] Marking operand live: " << operand << " ("
90  << operand->isLive << ")";
91  propagateIfChanged(operand, operand->markLive());
92  }
93  }
94 
95  // This marks values of type (3) liveness as "live".
96  bool foundLiveResult = false;
97  for (const Liveness *r : results) {
98  if (r->isLive && !foundLiveResult) {
99  LDBG() << "[visitOperation] Found live result, "
100  "meeting all operands with result: "
101  << r;
102  // It is assumed that each operand is used to compute each result of an
103  // op. Thus, if at least one result is live, each operand is live.
104  for (Liveness *operand : operands) {
105  LDBG() << " [visitOperation] Meeting operand: " << operand
106  << " with result: " << r;
107  meet(operand, *r);
108  }
109  foundLiveResult = true;
110  }
111  LDBG() << "[visitOperation] Adding dependency for result: " << r
112  << " after op: " << *op;
113  addDependency(const_cast<Liveness *>(r), getProgramPointAfter(op));
114  }
115  return success();
116 }
117 
119  LDBG() << "Visiting branch operand: " << operand.get()
120  << " in op: " << *operand.getOwner();
121  // We know (at the moment) and assume (for the future) that `operand` is a
122  // non-forwarded branch operand of a `RegionBranchOpInterface`,
123  // `BranchOpInterface`, `RegionBranchTerminatorOpInterface` or return-like op.
124  Operation *op = operand.getOwner();
125  assert((isa<RegionBranchOpInterface>(op) || isa<BranchOpInterface>(op) ||
126  isa<RegionBranchTerminatorOpInterface>(op)) &&
127  "expected the op to be `RegionBranchOpInterface`, "
128  "`BranchOpInterface` or `RegionBranchTerminatorOpInterface`");
129 
130  // The lattices of the non-forwarded branch operands don't get updated like
131  // the forwarded branch operands or the non-branch operands. Thus they need
132  // to be handled separately. This is where we handle them.
133 
134  // This marks values of type (1.b/1.c) liveness as "live". A non-forwarded
135  // branch operand will be live if a block where its op could take the control
136  // has an op with memory effects or could result in different results.
137  // Populating such blocks in `blocks`.
138  bool mayLive = false;
140  if (isa<RegionBranchOpInterface>(op)) {
141  if (op->getNumResults() != 0) {
142  // This mark value of type 1.c liveness as may live, because the region
143  // branch operation has a return value, and the non-forwarded operand can
144  // determine the region to jump to, it can thereby control the result of
145  // the region branch operation.
146  // Therefore, if the result value is live, we conservatively consider the
147  // non-forwarded operand of the region branch operation with result may
148  // live and record all result.
149  for (Value result : op->getResults()) {
150  if (getLatticeElement(result)->isLive) {
151  mayLive = true;
152  LDBG() << "[visitBranchOperand] Non-forwarded branch "
153  "operand may be live due to live result: "
154  << result;
155  break;
156  }
157  }
158  } else {
159  // When the op is a `RegionBranchOpInterface`, like an `scf.for` or an
160  // `scf.index_switch` op, its branch operand controls the flow into this
161  // op's regions.
162  for (Region &region : op->getRegions()) {
163  for (Block &block : region)
164  blocks.push_back(&block);
165  }
166  }
167  } else if (isa<BranchOpInterface>(op)) {
168  // We cannot track all successor blocks of the branch operation(More
169  // specifically, it's the successor's successor). Additionally, different
170  // blocks might also lead to the different block argument described in 1.c.
171  // Therefore, we conservatively consider the non-forwarded operand of the
172  // branch operation may live.
173  mayLive = true;
174  LDBG() << "[visitBranchOperand] Non-forwarded branch operand may "
175  "be live due to branch op interface";
176  } else {
177  Operation *parentOp = op->getParentOp();
178  assert(isa<RegionBranchOpInterface>(parentOp) &&
179  "expected parent op to implement `RegionBranchOpInterface`");
180  if (parentOp->getNumResults() != 0) {
181  // This mark value of type 1.c liveness as may live, because the region
182  // branch operation has a return value, and the non-forwarded operand can
183  // determine the region to jump to, it can thereby control the result of
184  // the region branch operation.
185  // Therefore, if the result value is live, we conservatively consider the
186  // non-forwarded operand of the region branch operation with result may
187  // live and record all result.
188  for (Value result : parentOp->getResults()) {
189  if (getLatticeElement(result)->isLive) {
190  mayLive = true;
191  LDBG() << "[visitBranchOperand] Non-forwarded branch "
192  "operand may be live due to parent live result: "
193  << result;
194  break;
195  }
196  }
197  } else {
198  // When the op is a `RegionBranchTerminatorOpInterface`, like an
199  // `scf.condition` op or return-like, like an `scf.yield` op, its branch
200  // operand controls the flow into this op's parent's (which is a
201  // `RegionBranchOpInterface`'s) regions.
202  for (Region &region : parentOp->getRegions()) {
203  for (Block &block : region)
204  blocks.push_back(&block);
205  }
206  }
207  }
208  for (Block *block : blocks) {
209  if (mayLive)
210  break;
211  for (Operation &nestedOp : *block) {
212  if (!isMemoryEffectFree(&nestedOp)) {
213  mayLive = true;
214  LDBG() << "Non-forwarded branch operand may be "
215  "live due to memory effect in block: "
216  << block;
217  break;
218  }
219  }
220  }
221 
222  if (mayLive) {
223  Liveness *operandLiveness = getLatticeElement(operand.get());
224  LDBG() << "Marking branch operand live: " << operand.get();
225  propagateIfChanged(operandLiveness, operandLiveness->markLive());
226  }
227 
228  // Now that we have checked for memory-effecting ops in the blocks of concern,
229  // we will simply visit the op with this non-forwarded operand to potentially
230  // mark it "live" due to type (1.a/3) liveness.
231  SmallVector<Liveness *, 4> operandLiveness;
232  operandLiveness.push_back(getLatticeElement(operand.get()));
233  SmallVector<const Liveness *, 4> resultsLiveness;
234  for (const Value result : op->getResults())
235  resultsLiveness.push_back(getLatticeElement(result));
236  LDBG() << "Visiting operation for non-forwarded branch operand: " << *op;
237  (void)visitOperation(op, operandLiveness, resultsLiveness);
238 
239  // We also visit the parent op with the parent's results and this operand if
240  // `op` is a `RegionBranchTerminatorOpInterface` because its non-forwarded
241  // operand depends on not only its memory effects/results but also on those of
242  // its parent's.
243  if (!isa<RegionBranchTerminatorOpInterface>(op))
244  return;
245  Operation *parentOp = op->getParentOp();
246  SmallVector<const Liveness *, 4> parentResultsLiveness;
247  for (const Value parentResult : parentOp->getResults())
248  parentResultsLiveness.push_back(getLatticeElement(parentResult));
249  LDBG() << "Visiting parent operation for non-forwarded branch operand: "
250  << *parentOp;
251  (void)visitOperation(parentOp, operandLiveness, parentResultsLiveness);
252 }
253 
255  LDBG() << "Visiting call operand: " << operand.get()
256  << " in op: " << *operand.getOwner();
257  // We know (at the moment) and assume (for the future) that `operand` is a
258  // non-forwarded call operand of an op implementing `CallOpInterface`.
259  assert(isa<CallOpInterface>(operand.getOwner()) &&
260  "expected the op to implement `CallOpInterface`");
261 
262  // The lattices of the non-forwarded call operands don't get updated like the
263  // forwarded call operands or the non-call operands. Thus they need to be
264  // handled separately. This is where we handle them.
265 
266  // This marks values of type (1.c) liveness as "live". A non-forwarded
267  // call operand is live.
268  Liveness *operandLiveness = getLatticeElement(operand.get());
269  LDBG() << "Marking call operand live: " << operand.get();
270  propagateIfChanged(operandLiveness, operandLiveness->markLive());
271 }
272 
274  LDBG() << "setToExitState for lattice: " << lattice;
275  if (lattice->isLive) {
276  LDBG() << "Lattice already live, nothing to do";
277  return;
278  }
279  // This marks values of type (2) liveness as "live".
280  LDBG() << "Marking lattice live due to exit state";
281  (void)lattice->markLive();
283 }
284 
285 //===----------------------------------------------------------------------===//
286 // RunLivenessAnalysis
287 //===----------------------------------------------------------------------===//
288 
290  LDBG() << "Constructing RunLivenessAnalysis for op: " << op->getName();
291  SymbolTableCollection symbolTable;
292 
293  loadBaselineAnalyses(solver);
294  solver.load<LivenessAnalysis>(symbolTable);
295  LDBG() << "Initializing and running solver";
296  (void)solver.initializeAndRun(op);
297  LDBG() << "RunLivenessAnalysis initialized for op: " << op->getName()
298  << " check on unreachable code now:";
299  // The framework doesn't visit operations in dead blocks, so we need to
300  // explicitly mark them as dead.
301  op->walk([&](Operation *op) {
302  if (op->getNumResults() == 0)
303  return;
304  for (auto result : llvm::enumerate(op->getResults())) {
305  if (getLiveness(result.value()))
306  continue;
307  LDBG() << "Result: " << result.index() << " of "
308  << OpWithFlags(op, OpPrintingFlags().skipRegions())
309  << " has no liveness info (unreachable), mark dead";
310  solver.getOrCreateState<Liveness>(result.value());
311  }
312  for (auto &region : op->getRegions()) {
313  for (auto &block : region) {
314  for (auto blockArg : llvm::enumerate(block.getArguments())) {
315  if (getLiveness(blockArg.value()))
316  continue;
317  LDBG() << "Block argument: " << blockArg.index() << " of "
318  << OpWithFlags(op, OpPrintingFlags().skipRegions())
319  << " has no liveness info, mark dead";
320  solver.getOrCreateState<Liveness>(blockArg.value());
321  }
322  }
323  }
324  });
325 }
326 
327 const Liveness *RunLivenessAnalysis::getLiveness(Value val) {
328  return solver.lookupState<Liveness>(val);
329 }
Block represents an ordered list of Operations.
Definition: Block.h:33
void addDependency(AnalysisState *state, ProgramPoint *point)
Create a dependency between the given analysis state and lattice anchor on this analysis.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
ProgramPoint * getProgramPointAfter(Operation *op)
AnalysisT * load(Args &&...args)
Load an analysis into the solver. Return the analysis instance.
LogicalResult initializeAndRun(Operation *top)
Initialize the children analyses starting from the provided top-level operation and run the analysis ...
IRValueT get() const
Return the current value being used by this operand.
Definition: UseDefLists.h:160
This class represents an operand of an operation.
Definition: Value.h:257
Set of flags used to control the behavior of the various IR print methods (e.g.
A wrapper class that allows for printing an operation with a set of flags, useful to act as a "stream...
Definition: Operation.h:1111
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:749
std::enable_if_t< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT > walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one),...
Definition: Operation.h:797
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:234
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:677
OperationName getName()
The name of an operation is the key identifier for it.
Definition: Operation.h:119
result_range getResults()
Definition: Operation.h:415
unsigned getNumResults()
Return the number of results held by this operation.
Definition: Operation.h:404
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
This class represents a collection of SymbolTables.
Definition: SymbolTable.h:283
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
void meet(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs)
Join the lattice element and propagate and update if it changed.
This class represents an abstract lattice.
An analysis that, by going backwards along the dataflow graph, annotates each value with a boolean st...
void setToExitState(Liveness *lattice) override
Set the given lattice element(s) at control flow exit point(s).
void visitBranchOperand(OpOperand &operand) override
void visitCallOperand(OpOperand &operand) override
LogicalResult visitOperation(Operation *op, ArrayRef< Liveness * > operands, ArrayRef< const Liveness * > results) override
For every value, liveness analysis determines whether or not it is "live".
Liveness * getLatticeElement(Value value) override
Get the lattice element for a value.
Operation * getOwner() const
Return the owner of this operand.
Definition: UseDefLists.h:38
void loadBaselineAnalyses(DataFlowSolver &solver)
Populates a DataFlowSolver with analyses that are required to ensure user-defined analyses are run pr...
Definition: Utils.h:29
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:344
Include the generated interface declarations.
ChangeResult
A result type used to indicate if a change happened.
bool isMemoryEffectFree(Operation *op)
Returns true if the given operation is free of memory effects.
This trait indicates that a terminator operation is "return-like".
This lattice represents, for a given value, whether or not it is "live".
void print(raw_ostream &os) const override
Print the contents of the analysis state.
ChangeResult meet(const AbstractSparseLattice &other) override
Meet (intersect) the information in this lattice with 'rhs'.