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) {
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()});
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];
296 printValueRef(
value);
301 os <<
"// - Block: " << blockIds[block] <<
"\n";
303 os <<
"// --- LiveIn: ";
304 printValueRefs(liveness->inValues);
305 os <<
"\n// --- LiveOut: ";
306 printValueRefs(liveness->outValues);
310 os <<
"// --- BeginLivenessIntervals";
317 printValueRef(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";
354 return inValues.count(value);
359 return outValues.count(value);
368 if (isLiveIn(value) || !definingOp)
369 return &block->front();
378 if (isLiveOut(value))
379 return &block->back();
382 Operation *endOperation = startOperation;
385 useOp = block->findAncestorOpInBlock(*useOp);
389 endOperation = useOp;
401 auto addValueToCurrentlyLiveSets = [&](
Value value) {
408 startOfLiveRange = &block->front();
410 startOfLiveRange = block->findAncestorOpInBlock(*startOfLiveRange);
413 if (isLiveOut(
value))
414 endOfLiveRange = &block->back();
418 if (startOfLiveRange && !endOfLiveRange)
419 endOfLiveRange = getEndOperation(
value, startOfLiveRange);
421 assert(endOfLiveRange &&
"Must have endOfLiveRange at this point!");
425 liveSet.insert(
value);
429 for (
Value arg : block->getArguments())
430 addValueToCurrentlyLiveSets(arg);
434 for (
Value in : inValues)
435 addValueToCurrentlyLiveSets(in);
440 llvm::make_range(block->begin(), ++op->getIterator()))
441 for (
auto result : walkOp.getResults())
442 addValueToCurrentlyLiveSets(result);
Include the generated interface declarations.
Operation is a basic unit of execution within MLIR.
operand_range getOperands()
Returns an iterator on the underlying Value's.
Block represents an ordered list of Operations.
This class represents liveness information on block level.
Operation * getStartOperation(Value value) const
Gets the start operation for the given value.
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
Dumps the liveness information to the given stream.
unsigned getArgNumber() const
Returns the number of this argument.
Block * getBlock()
Returns the operation block that contains this operation.
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).
user_range getUsers() const
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
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)...
bool isDeadAfter(Value value, Operation *operation) const
Returns true if value is not live after operation.
ValueSetT currentlyLiveValues(Operation *op) const
Get the set of values that are currently live (if any) for the current op.
const ValueSetT & getLiveOut(Block *block) const
Returns a reference to a set containing live-out values (unordered).
BlockArgListType getArguments()
This class represents an argument of a Block.
const LivenessBlockInfo * getLiveness(Block *block) const
Gets liveness info (if any) for the block.
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...
Block * findAncestorBlockInRegion(Block &block)
Returns 'block' if 'block' lies in this region, or otherwise finds the ancestor of 'block' that lies ...
Operation * getEndOperation(Value value, Operation *startOperation) const
Gets the end operation for the given value using the start operation provided (must be referenced in ...
void dump() const
Dumps the liveness information in a human readable format.
std::vector< Operation * > OperationListT
bool isLiveIn(Value value) const
Returns true if the given value is in the live-in set.
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
This class represents an operand of an operation.
OperationListT resolveLiveness(Value value) const
Gets liveness info (if any) for the given value.
unsigned getNumResults()
Return the number of results held by this operation.
static void buildBlockMapping(Operation *operation, DenseMap< Block *, BlockInfoBuilder > &builders)
Builds the internal liveness block mapping.
SuccessorRange getSuccessors()
const ValueSetT & in() const
Returns all values that are live at the beginning of the block (unordered).
result_range getResults()
Liveness(Operation *op)
Creates a new Liveness analysis that computes liveness information for all associated regions...
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
const ValueSetT & getLiveIn(Block *block) const
Returns a reference to a set containing live-in values (unordered).
SmallPtrSet< Value, 16 > ValueSetT
pred_iterator pred_begin()