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"
27 struct BlockInfoBuilder {
31 BlockInfoBuilder() =
default;
34 BlockInfoBuilder(
Block *block) : block(block) {
35 auto gatherOutValues = [&](
Value value) {
41 Block *ownerBlock = useOp->getBlock();
45 assert(ownerBlock &&
"Use leaves the current parent region");
46 if (ownerBlock != block) {
47 outValues.insert(value);
56 defValues.insert(argument);
59 gatherOutValues(argument);
64 for (
Value result : operation.getResults())
65 gatherOutValues(result);
72 defValues.insert(result);
74 useValues.insert(operand);
76 llvm::set_subtract(useValues, defValues);
84 ValueSetT newIn = useValues;
85 llvm::set_union(newIn, outValues);
86 llvm::set_subtract(newIn, defValues);
90 if (newIn.size() == inValues.size())
93 inValues = std::move(newIn);
102 const BlockInfoBuilder &builder = builders.find(succ)->second;
103 llvm::set_union(outValues, builder.inValues);
108 Block *block{
nullptr};
130 BlockInfoBuilder &builder =
131 builders.try_emplace(block, block).first->second;
133 if (builder.updateLiveIn())
134 toProcess.insert(block->pred_begin(), block->pred_end());
138 while (!toProcess.empty()) {
139 Block *current = toProcess.pop_back_val();
140 BlockInfoBuilder &builder = builders[current];
143 builder.updateLiveOut(builders);
146 if (builder.updateLiveIn())
160 void Liveness::build() {
166 for (
auto &entry : builders) {
167 BlockInfoBuilder &builder = entry.second;
170 info.block = builder.block;
171 info.inValues = std::move(builder.inValues);
172 info.outValues = std::move(builder.outValues);
185 currentBlock = defOp->getBlock();
188 toProcess.push_back(currentBlock);
189 visited.insert(currentBlock);
193 Block *useBlock = use.getOwner()->getBlock();
194 if (visited.insert(useBlock).second)
195 toProcess.push_back(useBlock);
198 while (!toProcess.empty()) {
200 Block *block = toProcess.back();
201 toProcess.pop_back();
208 result.push_back(start);
209 while (start != end) {
210 start = start->getNextNode();
211 result.push_back(start);
216 visited.insert(successor).second)
217 toProcess.push_back(successor);
226 auto it = blockMapping.find(block);
227 return it == blockMapping.end() ? nullptr : &it->second;
253 return endOperation == operation || endOperation->
isBeforeInBlock(operation);
261 os <<
"// ---- Liveness -----\n";
268 blockIds.insert({block, blockIds.size()});
270 valueIds.insert({argument, valueIds.size()});
272 operationIds.insert({&operation, operationIds.size()});
274 valueIds.insert({result, valueIds.size()});
279 auto printValueRef = [&](
Value value) {
280 if (value.getDefiningOp())
281 os <<
"val_" << valueIds[value];
285 << blockIds[blockArg.getOwner()];
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];
295 for (
Value value : orderedValues)
296 printValueRef(value);
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);
310 os <<
"// --- BeginLivenessIntervals";
317 printValueRef(result);
319 auto liveOperations = resolveLiveness(result);
321 return operationIds[left] < operationIds[right];
323 for (
Operation *operation : liveOperations) {
325 operation->print(os);
329 os <<
"\n// --- EndLivenessIntervals\n";
332 os <<
"// --- BeginCurrentlyLive\n";
334 auto currentlyLive = liveness->currentlyLiveValues(&op);
335 if (currentlyLive.empty())
340 printValueRefs(currentlyLive);
343 os <<
"// --- EndCurrentlyLive\n";
345 os <<
"// -------------------\n";
353 bool LivenessBlockInfo::isLiveIn(
Value value)
const {
354 return inValues.count(value);
359 return outValues.count(value);
369 return &block->front();
379 return &block->back();
382 Operation *endOperation = startOperation;
385 useOp = block->findAncestorOpInBlock(*useOp);
389 endOperation = useOp;
401 auto addValueToCurrentlyLiveSets = [&](
Value value) {
403 Operation *startOfLiveRange = value.getDefiningOp();
408 startOfLiveRange = &block->front();
410 startOfLiveRange = block->findAncestorOpInBlock(*startOfLiveRange);
414 endOfLiveRange = &block->back();
418 if (startOfLiveRange && !endOfLiveRange)
421 assert(endOfLiveRange &&
"Must have endOfLiveRange at this point!");
425 liveSet.insert(value);
429 for (
Value arg : block->getArguments())
430 addValueToCurrentlyLiveSets(arg);
435 addValueToCurrentlyLiveSets(
in);
440 llvm::make_range(block->begin(), ++op->getIterator()))
441 for (
auto result : walkOp.getResults())
442 addValueToCurrentlyLiveSets(result);
static void buildBlockMapping(Operation *operation, DenseMap< Block *, BlockInfoBuilder > &builders)
Builds the internal liveness block mapping.
This class represents an argument of a Block.
unsigned getArgNumber() const
Returns the number of this argument.
Block represents an ordered list of Operations.
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
pred_iterator pred_begin()
SuccessorRange getSuccessors()
BlockArgListType getArguments()
This class represents liveness information on block level.
bool isLiveIn(Value value) const
Returns true if the given value is in the live-in set.
Operation * getStartOperation(Value value) const
Gets the start operation for the given value.
const ValueSetT & in() const
Returns all values that are live at the beginning of the block (unordered).
ValueSetT currentlyLiveValues(Operation *op) const
Get the set of values that are currently live (if any) for the current op.
bool isLiveOut(Value value) const
Returns true if the given value is in the live-out set.
const ValueSetT & out() const
Returns all values that are live at the end of the block (unordered).
Operation * getEndOperation(Value value, Operation *startOperation) const
Gets the end operation for the given value using the start operation provided (must be referenced in ...
bool isDeadAfter(Value value, Operation *operation) const
Returns true if value is not live after operation.
Liveness(Operation *op)
Creates a new Liveness analysis that computes liveness information for all associated regions.
OperationListT resolveLiveness(Value value) const
Gets liveness info (if any) for the given value.
const LivenessBlockInfo * getLiveness(Block *block) const
Gets liveness info (if any) for the block.
SmallPtrSet< Value, 16 > ValueSetT
void print(raw_ostream &os) const
Dumps the liveness information to the given stream.
const ValueSetT & getLiveOut(Block *block) const
Returns a reference to a set containing live-out values (unordered).
const ValueSetT & getLiveIn(Block *block) const
Returns a reference to a set containing live-in values (unordered).
std::vector< Operation * > OperationListT
void dump() const
Dumps the liveness information in a human readable format.
This class represents an operand of an operation.
Operation is the basic unit of execution within MLIR.
bool isBeforeInBlock(Operation *other)
Given an operation 'other' that is within the same parent block, return whether the current operation...
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),...
void print(raw_ostream &os, const OpPrintingFlags &flags=std::nullopt)
Block * getBlock()
Returns the operation block that contains this operation.
operand_range getOperands()
Returns an iterator on the underlying Value's.
user_range getUsers()
Returns a range of all users.
result_range getResults()
unsigned getNumResults()
Return the number of results held by this operation.
Block * findAncestorBlockInRegion(Block &block)
Returns 'block' if 'block' lies in this region, or otherwise finds the ancestor of 'block' that lies ...
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
user_range getUsers() const
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
This header declares functions that assit transformations in the MemRef dialect.