MLIR  14.0.0git
Liveness.cpp
Go to the documentation of this file.
1 //===- Liveness.cpp - Liveness analysis for MLIR --------------------------===//
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 // Implementation of the liveness analysis.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "mlir/Analysis/Liveness.h"
14 #include "mlir/IR/Block.h"
15 #include "mlir/IR/Operation.h"
16 #include "mlir/IR/Region.h"
17 #include "mlir/IR/Value.h"
18 #include "llvm/ADT/SetOperations.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/Support/raw_ostream.h"
21 
22 using namespace mlir;
23 
24 namespace {
25 /// Builds and holds block information during the construction phase.
26 struct BlockInfoBuilder {
27  using ValueSetT = Liveness::ValueSetT;
28 
29  /// Constructs an empty block builder.
30  BlockInfoBuilder() = default;
31 
32  /// Fills the block builder with initial liveness information.
33  BlockInfoBuilder(Block *block) : block(block) {
34  auto gatherOutValues = [&](Value value) {
35  // Check whether this value will be in the outValues set (its uses escape
36  // this block). Due to the SSA properties of the program, the uses must
37  // occur after the definition. Therefore, we do not have to check
38  // additional conditions to detect an escaping value.
39  for (Operation *useOp : value.getUsers()) {
40  Block *ownerBlock = useOp->getBlock();
41  // Find an owner block in the current region. Note that a value does not
42  // escape this block if it is used in a nested region.
43  ownerBlock = block->getParent()->findAncestorBlockInRegion(*ownerBlock);
44  assert(ownerBlock && "Use leaves the current parent region");
45  if (ownerBlock != block) {
46  outValues.insert(value);
47  break;
48  }
49  }
50  };
51 
52  // Mark all block arguments (phis) as defined.
53  for (BlockArgument argument : block->getArguments()) {
54  // Insert value into the set of defined values.
55  defValues.insert(argument);
56 
57  // Gather all out values of all arguments in the current block.
58  gatherOutValues(argument);
59  }
60 
61  // Gather out values of all operations in the current block.
62  for (Operation &operation : *block)
63  for (Value result : operation.getResults())
64  gatherOutValues(result);
65 
66  // Mark all nested operation results as defined, and nested operation
67  // operands as used. All defined value will be removed from the used set
68  // at the end.
69  block->walk([&](Operation *op) {
70  for (Value result : op->getResults())
71  defValues.insert(result);
72  for (Value operand : op->getOperands())
73  useValues.insert(operand);
74  });
75  llvm::set_subtract(useValues, defValues);
76  }
77 
78  /// Updates live-in information of the current block. To do so it uses the
79  /// default liveness-computation formula: newIn = use union out \ def. The
80  /// methods returns true, if the set has changed (newIn != in), false
81  /// otherwise.
82  bool updateLiveIn() {
83  ValueSetT newIn = useValues;
84  llvm::set_union(newIn, outValues);
85  llvm::set_subtract(newIn, defValues);
86 
87  // It is sufficient to check the set sizes (instead of their contents) since
88  // the live-in set can only grow monotonically during all update operations.
89  if (newIn.size() == inValues.size())
90  return false;
91 
92  inValues = std::move(newIn);
93  return true;
94  }
95 
96  /// Updates live-out information of the current block. It iterates over all
97  /// successors and unifies their live-in values with the current live-out
98  /// values.
99  void updateLiveOut(const DenseMap<Block *, BlockInfoBuilder> &builders) {
100  for (Block *succ : block->getSuccessors()) {
101  const BlockInfoBuilder &builder = builders.find(succ)->second;
102  llvm::set_union(outValues, builder.inValues);
103  }
104  }
105 
106  /// The current block.
107  Block *block{nullptr};
108 
109  /// The set of all live in values.
110  ValueSetT inValues;
111 
112  /// The set of all live out values.
113  ValueSetT outValues;
114 
115  /// The set of all defined values.
116  ValueSetT defValues;
117 
118  /// The set of all used values.
119  ValueSetT useValues;
120 };
121 } // namespace
122 
123 /// Builds the internal liveness block mapping.
124 static void buildBlockMapping(Operation *operation,
126  SetVector<Block *> toProcess;
127 
128  operation->walk<WalkOrder::PreOrder>([&](Block *block) {
129  BlockInfoBuilder &builder =
130  builders.try_emplace(block, block).first->second;
131 
132  if (builder.updateLiveIn())
133  toProcess.insert(block->pred_begin(), block->pred_end());
134  });
135 
136  // Propagate the in and out-value sets (fixpoint iteration).
137  while (!toProcess.empty()) {
138  Block *current = toProcess.pop_back_val();
139  BlockInfoBuilder &builder = builders[current];
140 
141  // Update the current out values.
142  builder.updateLiveOut(builders);
143 
144  // Compute (potentially) updated live in values.
145  if (builder.updateLiveIn())
146  toProcess.insert(current->pred_begin(), current->pred_end());
147  }
148 }
149 
150 //===----------------------------------------------------------------------===//
151 // Liveness
152 //===----------------------------------------------------------------------===//
153 
154 /// Creates a new Liveness analysis that computes liveness information for all
155 /// associated regions.
156 Liveness::Liveness(Operation *op) : operation(op) { build(); }
157 
158 /// Initializes the internal mappings.
159 void Liveness::build() {
160  // Build internal block mapping.
162  buildBlockMapping(operation, builders);
163 
164  // Store internal block data.
165  for (auto &entry : builders) {
166  BlockInfoBuilder &builder = entry.second;
167  LivenessBlockInfo &info = blockMapping[entry.first];
168 
169  info.block = builder.block;
170  info.inValues = std::move(builder.inValues);
171  info.outValues = std::move(builder.outValues);
172  }
173 }
174 
175 /// Gets liveness info (if any) for the given value.
177  OperationListT result;
178  SmallPtrSet<Block *, 32> visited;
179  SmallVector<Block *, 8> toProcess;
180 
181  // Start with the defining block
182  Block *currentBlock;
183  if (Operation *defOp = value.getDefiningOp())
184  currentBlock = defOp->getBlock();
185  else
186  currentBlock = value.cast<BlockArgument>().getOwner();
187  toProcess.push_back(currentBlock);
188  visited.insert(currentBlock);
189 
190  // Start with all associated blocks
191  for (OpOperand &use : value.getUses()) {
192  Block *useBlock = use.getOwner()->getBlock();
193  if (visited.insert(useBlock).second)
194  toProcess.push_back(useBlock);
195  }
196 
197  while (!toProcess.empty()) {
198  // Get block and block liveness information.
199  Block *block = toProcess.back();
200  toProcess.pop_back();
201  const LivenessBlockInfo *blockInfo = getLiveness(block);
202 
203  // Note that start and end will be in the same block.
204  Operation *start = blockInfo->getStartOperation(value);
205  Operation *end = blockInfo->getEndOperation(value, start);
206 
207  result.push_back(start);
208  while (start != end) {
209  start = start->getNextNode();
210  result.push_back(start);
211  }
212 
213  for (Block *successor : block->getSuccessors()) {
214  if (getLiveness(successor)->isLiveIn(value) &&
215  visited.insert(successor).second)
216  toProcess.push_back(successor);
217  }
218  }
219 
220  return result;
221 }
222 
223 /// Gets liveness info (if any) for the block.
225  auto it = blockMapping.find(block);
226  return it == blockMapping.end() ? nullptr : &it->second;
227 }
228 
229 /// Returns a reference to a set containing live-in values.
231  return getLiveness(block)->in();
232 }
233 
234 /// Returns a reference to a set containing live-out values.
236  return getLiveness(block)->out();
237 }
238 
239 /// Returns true if `value` is not live after `operation`.
240 bool Liveness::isDeadAfter(Value value, Operation *operation) const {
241  Block *block = operation->getBlock();
242  const LivenessBlockInfo *blockInfo = getLiveness(block);
243 
244  // The given value escapes the associated block.
245  if (blockInfo->isLiveOut(value))
246  return false;
247 
248  Operation *endOperation = blockInfo->getEndOperation(value, operation);
249  // If the operation is a real user of `value` the first check is sufficient.
250  // If not, we will have to test whether the end operation is executed before
251  // the given operation in the block.
252  return endOperation == operation || endOperation->isBeforeInBlock(operation);
253 }
254 
255 /// Dumps the liveness information in a human readable format.
256 void Liveness::dump() const { print(llvm::errs()); }
257 
258 /// Dumps the liveness information to the given stream.
259 void Liveness::print(raw_ostream &os) const {
260  os << "// ---- Liveness -----\n";
261 
262  // Builds unique block/value mappings for testing purposes.
263  DenseMap<Block *, size_t> blockIds;
264  DenseMap<Operation *, size_t> operationIds;
265  DenseMap<Value, size_t> valueIds;
266  operation->walk<WalkOrder::PreOrder>([&](Block *block) {
267  blockIds.insert({block, blockIds.size()});
268  for (BlockArgument argument : block->getArguments())
269  valueIds.insert({argument, valueIds.size()});
270  for (Operation &operation : *block) {
271  operationIds.insert({&operation, operationIds.size()});
272  for (Value result : operation.getResults())
273  valueIds.insert({result, valueIds.size()});
274  }
275  });
276 
277  // Local printing helpers
278  auto printValueRef = [&](Value value) {
279  if (value.getDefiningOp())
280  os << "val_" << valueIds[value];
281  else {
282  auto blockArg = value.cast<BlockArgument>();
283  os << "arg" << blockArg.getArgNumber() << "@"
284  << blockIds[blockArg.getOwner()];
285  }
286  os << " ";
287  };
288 
289  auto printValueRefs = [&](const ValueSetT &values) {
290  std::vector<Value> orderedValues(values.begin(), values.end());
291  std::sort(orderedValues.begin(), orderedValues.end(),
292  [&](Value left, Value right) {
293  return valueIds[left] < valueIds[right];
294  });
295  for (Value value : orderedValues)
296  printValueRef(value);
297  };
298 
299  // Dump information about in and out values.
300  operation->walk<WalkOrder::PreOrder>([&](Block *block) {
301  os << "// - Block: " << blockIds[block] << "\n";
302  const auto *liveness = getLiveness(block);
303  os << "// --- LiveIn: ";
304  printValueRefs(liveness->inValues);
305  os << "\n// --- LiveOut: ";
306  printValueRefs(liveness->outValues);
307  os << "\n";
308 
309  // Print liveness intervals.
310  os << "// --- BeginLiveness";
311  for (Operation &op : *block) {
312  if (op.getNumResults() < 1)
313  continue;
314  os << "\n";
315  for (Value result : op.getResults()) {
316  os << "// ";
317  printValueRef(result);
318  os << ":";
319  auto liveOperations = resolveLiveness(result);
320  std::sort(liveOperations.begin(), liveOperations.end(),
321  [&](Operation *left, Operation *right) {
322  return operationIds[left] < operationIds[right];
323  });
324  for (Operation *operation : liveOperations) {
325  os << "\n// ";
326  operation->print(os);
327  }
328  }
329  }
330  os << "\n// --- EndLiveness\n";
331  });
332  os << "// -------------------\n";
333 }
334 
335 //===----------------------------------------------------------------------===//
336 // LivenessBlockInfo
337 //===----------------------------------------------------------------------===//
338 
339 /// Returns true if the given value is in the live-in set.
341  return inValues.count(value);
342 }
343 
344 /// Returns true if the given value is in the live-out set.
346  return outValues.count(value);
347 }
348 
349 /// Gets the start operation for the given value (must be referenced in this
350 /// block).
352  Operation *definingOp = value.getDefiningOp();
353  // The given value is either live-in or is defined
354  // in the scope of this block.
355  if (isLiveIn(value) || !definingOp)
356  return &block->front();
357  return definingOp;
358 }
359 
360 /// Gets the end operation for the given value using the start operation
361 /// provided (must be referenced in this block).
363  Operation *startOperation) const {
364  // The given value is either dying in this block or live-out.
365  if (isLiveOut(value))
366  return &block->back();
367 
368  // Resolve the last operation (must exist by definition).
369  Operation *endOperation = startOperation;
370  for (Operation *useOp : value.getUsers()) {
371  // Find the associated operation in the current block (if any).
372  useOp = block->findAncestorOpInBlock(*useOp);
373  // Check whether the use is in our block and after the current end
374  // operation.
375  if (useOp && endOperation->isBeforeInBlock(useOp))
376  endOperation = useOp;
377  }
378  return endOperation;
379 }
Include the generated interface declarations.
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:28
operand_range getOperands()
Returns an iterator on the underlying Value&#39;s.
Definition: Operation.h:247
Block represents an ordered list of Operations.
Definition: Block.h:29
pred_iterator pred_end()
Definition: Block.h:224
This class represents liveness information on block level.
Definition: Liveness.h:99
Operation * getStartOperation(Value value) const
Gets the start operation for the given value.
Definition: Liveness.cpp:351
bool isBeforeInBlock(Operation *other)
Given an operation &#39;other&#39; that is within the same parent block, return whether the current operation...
Definition: Operation.cpp:271
void print(raw_ostream &os) const
Dumps the liveness information to the given stream.
Definition: Liveness.cpp:259
unsigned getArgNumber() const
Returns the number of this argument.
Definition: Value.h:310
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:96
bool isLiveOut(Value value) const
Returns true if the given value is in the live-out set.
Definition: Liveness.cpp:345
const ValueSetT & out() const
Returns all values that are live at the end of the block (unordered).
Definition: Liveness.h:114
user_range getUsers() const
Definition: Value.h:212
Region * getParent() const
Provide a &#39;getParent&#39; method for ilist_node_with_parent methods.
Definition: Block.cpp:26
static constexpr const bool value
std::enable_if< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT >::type walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one)...
Definition: Operation.h:515
bool isDeadAfter(Value value, Operation *operation) const
Returns true if value is not live after operation.
Definition: Liveness.cpp:240
const ValueSetT & getLiveOut(Block *block) const
Returns a reference to a set containing live-out values (unordered).
Definition: Liveness.cpp:235
BlockArgListType getArguments()
Definition: Block.h:76
This class represents an argument of a Block.
Definition: Value.h:298
const LivenessBlockInfo * getLiveness(Block *block) const
Gets liveness info (if any) for the block.
Definition: Liveness.cpp:224
void print(raw_ostream &os, const OpPrintingFlags &flags=llvm::None)
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:84
Block * findAncestorBlockInRegion(Block &block)
Returns &#39;block&#39; if &#39;block&#39; lies in this region, or otherwise finds the ancestor of &#39;block&#39; that lies ...
Definition: Region.cpp:121
Operation * getEndOperation(Value value, Operation *startOperation) const
Gets the end operation for the given value using the start operation provided (must be referenced in ...
Definition: Liveness.cpp:362
void dump() const
Dumps the liveness information in a human readable format.
Definition: Liveness.cpp:256
std::vector< Operation * > OperationListT
Definition: Liveness.h:49
bool isLiveIn(Value value) const
Returns true if the given value is in the live-in set.
Definition: Liveness.cpp:340
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
This class represents an operand of an operation.
Definition: Value.h:249
U cast() const
Definition: Value.h:107
OperationListT resolveLiveness(Value value) const
Gets liveness info (if any) for the given value.
Definition: Liveness.cpp:176
unsigned getNumResults()
Return the number of results held by this operation.
Definition: Operation.h:273
static void buildBlockMapping(Operation *operation, DenseMap< Block *, BlockInfoBuilder > &builders)
Builds the internal liveness block mapping.
Definition: Liveness.cpp:124
SuccessorRange getSuccessors()
Definition: Block.h:255
const ValueSetT & in() const
Returns all values that are live at the beginning of the block (unordered).
Definition: Liveness.h:110
result_range getResults()
Definition: Operation.h:284
Liveness(Operation *op)
Creates a new Liveness analysis that computes liveness information for all associated regions...
Definition: Liveness.cpp:156
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
Definition: Value.h:196
const ValueSetT & getLiveIn(Block *block) const
Returns a reference to a set containing live-in values (unordered).
Definition: Liveness.cpp:230
SmallPtrSet< Value, 16 > ValueSetT
Definition: Liveness.h:51
pred_iterator pred_begin()
Definition: Block.h:221