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