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/Debug.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 #define DBGS() (llvm::dbgs() << '[' << DEBUG_TYPE << "] ")
25 #define LDBG(X) LLVM_DEBUG(DBGS() << X << "\n")
26 
27 using namespace mlir;
28 using namespace mlir::dataflow;
29 
30 //===----------------------------------------------------------------------===//
31 // Liveness
32 //===----------------------------------------------------------------------===//
33 
34 void Liveness::print(raw_ostream &os) const {
35  os << (isLive ? "live" : "not live");
36 }
37 
39  bool wasLive = isLive;
40  isLive = true;
42 }
43 
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 
81 LogicalResult
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(operand, 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(operand, *r);
111  }
112  foundLiveResult = true;
113  }
114  LDBG("[visitOperation] Adding dependency for result: " << r << " after op: "
115  << *op);
116  addDependency(const_cast<Liveness *>(r), getProgramPointAfter(op));
117  }
118  return success();
119 }
120 
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;
143  if (isa<RegionBranchOpInterface>(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(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(&block);
168  }
169  }
170  } else if (isa<BranchOpInterface>(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(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(&block);
208  }
209  }
210  }
211  for (Block *block : blocks) {
212  if (mayLive)
213  break;
214  for (Operation &nestedOp : *block) {
215  if (!isMemoryEffectFree(&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(operand.get());
227  LDBG("Marking branch operand live: " << operand.get());
228  propagateIfChanged(operandLiveness, 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(getLatticeElement(operand.get()));
236  SmallVector<const Liveness *, 4> resultsLiveness;
237  for (const Value result : op->getResults())
238  resultsLiveness.push_back(getLatticeElement(result));
239  LDBG("Visiting operation for non-forwarded branch operand: " << *op);
240  (void)visitOperation(op, operandLiveness, 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>(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(getLatticeElement(parentResult));
252  LDBG("Visiting parent operation for non-forwarded branch operand: "
253  << *parentOp);
254  (void)visitOperation(parentOp, operandLiveness, parentResultsLiveness);
255 }
256 
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(operand.get());
272  LDBG("Marking call operand live: " << operand.get());
273  propagateIfChanged(operandLiveness, operandLiveness->markLive());
274 }
275 
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();
286 }
287 
288 //===----------------------------------------------------------------------===//
289 // RunLivenessAnalysis
290 //===----------------------------------------------------------------------===//
291 
293  LDBG("Constructing RunLivenessAnalysis for op: " << op->getName());
294  SymbolTableCollection symbolTable;
295 
296  loadBaselineAnalyses(solver);
297  solver.load<LivenessAnalysis>(symbolTable);
298  LDBG("Initializing and running solver");
299  (void)solver.initializeAndRun(op);
300  LDBG("Dumping liveness state for op");
301 }
302 
304  return solver.lookupState<Liveness>(val);
305 }
#define DBGS()
#define LDBG(X)
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)
const StateT * lookupState(AnchorT anchor) const
Lookup an analysis state for the given lattice anchor.
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.
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
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
void print(raw_ostream &os, const OpPrintingFlags &flags={})
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
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'.
const Liveness * getLiveness(Value val)