MLIR 24.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
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
23using namespace mlir;
24
25namespace {
26/// Builds and holds block information during the construction phase.
27struct 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 defValues.insert_range(op->getResults());
72 useValues.insert_range(op->getOperands());
73 for (Region &region : op->getRegions())
74 for (Block &child : region.getBlocks())
75 defValues.insert_range(child.getArguments());
76 });
77 llvm::set_subtract(useValues, defValues);
78 }
79
80 /// Updates live-in information of the current block. To do so it uses the
81 /// default liveness-computation formula: newIn = use union out \ def. The
82 /// methods returns true, if the set has changed (newIn != in), false
83 /// otherwise.
84 bool updateLiveIn() {
85 ValueSetT newIn = useValues;
86 llvm::set_union(newIn, outValues);
87 llvm::set_subtract(newIn, defValues);
88
89 // It is sufficient to check the set sizes (instead of their contents) since
90 // the live-in set can only grow monotonically during all update operations.
91 if (newIn.size() == inValues.size())
92 return false;
93
94 inValues = std::move(newIn);
95 return true;
96 }
97
98 /// Updates live-out information of the current block. It iterates over all
99 /// successors and unifies their live-in values with the current live-out
100 /// values.
101 void updateLiveOut(const DenseMap<Block *, BlockInfoBuilder> &builders) {
102 for (Block *succ : block->getSuccessors()) {
103 const BlockInfoBuilder &builder = builders.find(succ)->second;
104 llvm::set_union(outValues, builder.inValues);
105 }
106 }
107
108 /// The current block.
109 Block *block{nullptr};
110
111 /// The set of all live in values.
112 ValueSetT inValues;
113
114 /// The set of all live out values.
115 ValueSetT outValues;
116
117 /// The set of all defined values.
118 ValueSetT defValues;
119
120 /// The set of all used values.
121 ValueSetT useValues;
122};
123} // namespace
124
125/// Builds the internal liveness block mapping.
126static void buildBlockMapping(Operation *operation,
128 SetVector<Block *> toProcess;
129
130 operation->walk<WalkOrder::PreOrder>([&](Block *block) {
131 BlockInfoBuilder &builder =
132 builders.try_emplace(block, block).first->second;
133
134 if (builder.updateLiveIn())
135 toProcess.insert(block->pred_begin(), block->pred_end());
136 });
137
138 // Propagate the in and out-value sets (fixpoint iteration).
139 while (!toProcess.empty()) {
140 Block *current = toProcess.pop_back_val();
141 BlockInfoBuilder &builder = builders[current];
142
143 // Update the current out values.
144 builder.updateLiveOut(builders);
145
146 // Compute (potentially) updated live in values.
147 if (builder.updateLiveIn())
148 toProcess.insert(current->pred_begin(), current->pred_end());
149 }
150}
151
152//===----------------------------------------------------------------------===//
153// Liveness
154//===----------------------------------------------------------------------===//
155
156/// Creates a new Liveness analysis that computes liveness information for all
157/// associated regions.
158Liveness::Liveness(Operation *op) : operation(op) { build(); }
159
160/// Initializes the internal mappings.
161void Liveness::build() {
162 // Build internal block mapping.
164 buildBlockMapping(operation, builders);
165
166 // Store internal block data.
167 for (auto &entry : builders) {
168 BlockInfoBuilder &builder = entry.second;
169 LivenessBlockInfo &info = blockMapping[entry.first];
170
171 info.block = builder.block;
172 info.inValues = std::move(builder.inValues);
173 info.outValues = std::move(builder.outValues);
174 }
175}
176
177/// Gets liveness info (if any) for the given value.
181 SmallVector<Block *, 8> toProcess;
182
183 // Start with the defining block
184 Block *currentBlock;
185 if (Operation *defOp = value.getDefiningOp())
186 currentBlock = defOp->getBlock();
187 else
188 currentBlock = cast<BlockArgument>(value).getOwner();
189 toProcess.push_back(currentBlock);
190 visited.insert(currentBlock);
191
192 // Start with all associated blocks
193 for (OpOperand &use : value.getUses()) {
194 Block *useBlock = use.getOwner()->getBlock();
195 if (visited.insert(useBlock).second)
196 toProcess.push_back(useBlock);
197 }
198
199 while (!toProcess.empty()) {
200 // Get block and block liveness information.
201 Block *block = toProcess.pop_back_val();
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`.
241bool 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#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
258void Liveness::dump() const { print(llvm::errs()); }
259#endif
260
261/// Dumps the liveness information to the given stream.
263 os << "// ---- Liveness -----\n";
264
265 // Builds unique block/value mappings for testing purposes.
269 operation->walk<WalkOrder::PreOrder>([&](Block *block) {
270 blockIds.insert({block, blockIds.size()});
271 for (BlockArgument argument : block->getArguments())
272 valueIds.insert({argument, valueIds.size()});
273 for (Operation &operation : *block) {
274 operationIds.insert({&operation, operationIds.size()});
275 for (Value result : operation.getResults())
276 valueIds.insert({result, valueIds.size()});
277 }
278 });
279
280 // Local printing helpers
281 auto printValueRef = [&](Value value) {
282 if (value.getDefiningOp())
283 os << "val_" << valueIds[value];
284 else {
285 auto blockArg = cast<BlockArgument>(value);
286 os << "arg" << blockArg.getArgNumber() << "@"
287 << blockIds[blockArg.getOwner()];
288 }
289 os << " ";
290 };
291
292 auto printValueRefs = [&](const ValueSetT &values) {
293 std::vector<Value> orderedValues(values.begin(), values.end());
294 llvm::sort(orderedValues, [&](Value left, Value right) {
295 return valueIds[left] < valueIds[right];
296 });
297 for (Value value : orderedValues)
298 printValueRef(value);
299 };
300
301 // Dump information about in and out values.
302 operation->walk<WalkOrder::PreOrder>([&](Block *block) {
303 os << "// - Block: " << blockIds[block] << "\n";
304 const auto *liveness = getLiveness(block);
305 os << "// --- LiveIn: ";
306 printValueRefs(liveness->inValues);
307 os << "\n// --- LiveOut: ";
308 printValueRefs(liveness->outValues);
309 os << "\n";
310
311 // Print liveness intervals.
312 os << "// --- BeginLivenessIntervals";
313 for (Operation &op : *block) {
314 if (op.getNumResults() < 1)
315 continue;
316 os << "\n";
317 for (Value result : op.getResults()) {
318 os << "// ";
319 printValueRef(result);
320 os << ":";
321 auto liveOperations = resolveLiveness(result);
322 llvm::sort(liveOperations, [&](Operation *left, Operation *right) {
323 return operationIds[left] < operationIds[right];
324 });
325 for (Operation *operation : liveOperations) {
326 os << "\n// ";
327 operation->print(os);
328 }
329 }
330 }
331 os << "\n// --- EndLivenessIntervals\n";
332
333 // Print currently live values.
334 os << "// --- BeginCurrentlyLive\n";
335 for (Operation &op : *block) {
336 auto currentlyLive = liveness->currentlyLiveValues(&op);
337 if (currentlyLive.empty())
338 continue;
339 os << "// ";
340 op.print(os);
341 os << " [";
342 printValueRefs(currentlyLive);
343 os << "\b]\n";
344 }
345 os << "// --- EndCurrentlyLive\n";
346 });
347 os << "// -------------------\n";
348}
349
350//===----------------------------------------------------------------------===//
351// LivenessBlockInfo
352//===----------------------------------------------------------------------===//
353
354/// Returns true if the given value is in the live-in set.
356 return inValues.count(value);
357}
358
359/// Returns true if the given value is in the live-out set.
361 return outValues.count(value);
362}
363
364/// Gets the start operation for the given value (must be referenced in this
365/// block).
367 Operation *definingOp = value.getDefiningOp();
368 // The given value is either live-in or is defined
369 // in the scope of this block.
370 if (isLiveIn(value) || !definingOp)
371 return &block->front();
372 return definingOp;
373}
374
375/// Gets the end operation for the given value using the start operation
376/// provided (must be referenced in this block).
378 Operation *startOperation) const {
379 // The given value is either dying in this block or live-out.
380 if (isLiveOut(value))
381 return &block->back();
382
383 // Resolve the last operation (must exist by definition).
384 Operation *endOperation = startOperation;
385 for (Operation *useOp : value.getUsers()) {
386 // Find the associated operation in the current block (if any).
387 useOp = block->findAncestorOpInBlock(*useOp);
388 // Check whether the use is in our block and after the current end
389 // operation.
390 if (useOp && endOperation->isBeforeInBlock(useOp))
391 endOperation = useOp;
392 }
393 return endOperation;
394}
395
396/// Return the values that are currently live as of the given operation.
399 ValueSetT liveSet;
400
401 // Given a value, check which ops are within its live range. For each of
402 // those ops, add the value to the set of live values as-of that op.
403 auto addValueToCurrentlyLiveSets = [&](Value value) {
404 // Determine the live range of this value inside this block.
405 Operation *startOfLiveRange = value.getDefiningOp();
406 Operation *endOfLiveRange = nullptr;
407 // If it's a live in or a block argument, then the start is the beginning
408 // of the block.
409 if (isLiveIn(value) || isa<BlockArgument>(value))
410 startOfLiveRange = &block->front();
411 else
412 startOfLiveRange = block->findAncestorOpInBlock(*startOfLiveRange);
413
414 // If it's a live out, then the end is the back of the block.
415 if (isLiveOut(value))
416 endOfLiveRange = &block->back();
417
418 // We must have at least a startOfLiveRange at this point. Given this, we
419 // can use the existing getEndOperation to find the end of the live range.
420 if (startOfLiveRange && !endOfLiveRange)
421 endOfLiveRange = getEndOperation(value, startOfLiveRange);
422
423 assert(endOfLiveRange && "Must have endOfLiveRange at this point!");
424 // If this op is within the live range, insert the value into the set.
425 if (!(op->isBeforeInBlock(startOfLiveRange) ||
426 endOfLiveRange->isBeforeInBlock(op)))
427 liveSet.insert(value);
428 };
429
430 // Handle block arguments if any.
431 for (Value arg : block->getArguments())
432 addValueToCurrentlyLiveSets(arg);
433
434 // Handle live-ins. Between the live ins and all the op results that gives us
435 // every value in the block.
436 for (Value in : inValues)
437 addValueToCurrentlyLiveSets(in);
438
439 // Now walk the block and handle all values used in the block and values
440 // defined by the block.
441 for (Operation &walkOp :
442 llvm::make_range(block->begin(), ++op->getIterator()))
443 for (auto result : walkOp.getResults())
444 addValueToCurrentlyLiveSets(result);
445
446 return liveSet;
447}
for(Operation *op :ops)
static void buildBlockMapping(Operation *operation, DenseMap< Block *, BlockInfoBuilder > &builders)
Builds the internal liveness block mapping.
Definition Liveness.cpp:126
This class represents an argument of a Block.
Definition Value.h:308
Block represents an ordered list of Operations.
Definition Block.h:34
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
Definition Block.cpp:27
pred_iterator pred_begin()
Definition Block.h:246
SuccessorRange getSuccessors()
Definition Block.h:280
pred_iterator pred_end()
Definition Block.h:249
This class represents liveness information on block level.
Definition Liveness.h:101
Liveness::ValueSetT ValueSetT
A typedef declaration of a value set.
Definition Liveness.h:104
bool isLiveIn(Value value) const
Returns true if the given value is in the live-in set.
Definition Liveness.cpp:355
Operation * getStartOperation(Value value) const
Gets the start operation for the given value.
Definition Liveness.cpp:366
const ValueSetT & out() const
Returns all values that are live at the end of the block (unordered).
Definition Liveness.h:116
ValueSetT currentlyLiveValues(Operation *op) const
Get the set of values that are currently live (if any) for the current op.
Definition Liveness.cpp:398
bool isLiveOut(Value value) const
Returns true if the given value is in the live-out set.
Definition Liveness.cpp:360
const ValueSetT & in() const
Returns all values that are live at the beginning of the block (unordered).
Definition Liveness.h:112
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:377
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:158
OperationListT resolveLiveness(Value value) const
Gets liveness info (if any) for the given value.
Definition Liveness.cpp:178
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:262
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
LLVM_DUMP_METHOD void dump() const
Dumps the liveness information in a human readable format.
Definition Liveness.cpp:258
This class represents an operand of an operation.
Definition Value.h:256
Operation is the basic unit of execution within MLIR.
Definition Operation.h:87
bool isBeforeInBlock(Operation *other)
Given an operation 'other' that is within the same parent block, return whether the current operation...
void print(raw_ostream &os, const OpPrintingFlags &flags={})
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition Operation.h:731
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition Operation.h:405
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:851
result_range getResults()
Definition Operation.h:442
unsigned getNumResults()
Return the number of results held by this operation.
Definition Operation.h:431
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:188
user_range getUsers() const
Definition Value.h:218
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition Value.cpp:18
Include the generated interface declarations.
llvm::SetVector< T, Vector, Set, N > SetVector
Definition LLVM.h:128
llvm::DenseMap< KeyT, ValueT, KeyInfoT, BucketT > DenseMap
Definition LLVM.h:123