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