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"
27struct BlockInfoBuilder {
31 BlockInfoBuilder() =
default;
34 BlockInfoBuilder(
Block *block) : block(block) {
35 auto gatherOutValues = [&](Value value) {
40 for (Operation *useOp : value.getUsers()) {
41 Block *ownerBlock = useOp->getBlock();
45 assert(ownerBlock &&
"Use leaves the current parent region");
46 if (ownerBlock != block) {
47 outValues.insert(value);
54 for (BlockArgument argument : block->getArguments()) {
56 defValues.insert(argument);
59 gatherOutValues(argument);
63 for (Operation &operation : *block)
64 for (Value
result : operation.getResults())
70 block->walk([&](Operation *op) {
74 for (
Block &child : region.getBlocks())
75 defValues.insert_range(child.getArguments());
77 llvm::set_subtract(useValues, defValues);
85 ValueSetT newIn = useValues;
86 llvm::set_union(newIn, outValues);
87 llvm::set_subtract(newIn, defValues);
91 if (newIn.size() == inValues.size())
94 inValues = std::move(newIn);
102 for (
Block *succ : block->getSuccessors()) {
103 const BlockInfoBuilder &builder = builders.find(succ)->second;
104 llvm::set_union(outValues, builder.inValues);
109 Block *block{
nullptr};
131 BlockInfoBuilder &builder =
132 builders.try_emplace(block, block).first->second;
134 if (builder.updateLiveIn())
135 toProcess.insert(block->pred_begin(), block->pred_end());
139 while (!toProcess.empty()) {
140 Block *current = toProcess.pop_back_val();
141 BlockInfoBuilder &builder = builders[current];
144 builder.updateLiveOut(builders);
147 if (builder.updateLiveIn())
161void Liveness::build() {
167 for (
auto &entry : builders) {
168 BlockInfoBuilder &builder = entry.second;
171 info.block = builder.block;
172 info.inValues = std::move(builder.inValues);
173 info.outValues = std::move(builder.outValues);
186 currentBlock = defOp->getBlock();
188 currentBlock = cast<BlockArgument>(value).getOwner();
189 toProcess.push_back(currentBlock);
190 visited.insert(currentBlock);
194 Block *useBlock = use.getOwner()->getBlock();
195 if (visited.insert(useBlock).second)
196 toProcess.push_back(useBlock);
199 while (!toProcess.empty()) {
201 Block *block = toProcess.pop_back_val();
209 while (start != end) {
210 start = start->getNextNode();
216 visited.insert(successor).second)
217 toProcess.push_back(successor);
226 auto it = blockMapping.find(block);
227 return it == blockMapping.end() ?
nullptr : &it->second;
242 Block *block = operation->getBlock();
253 return endOperation == operation || endOperation->
isBeforeInBlock(operation);
257#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
263 os <<
"// ---- Liveness -----\n";
270 blockIds.insert({block, blockIds.size()});
272 valueIds.insert({argument, valueIds.size()});
274 operationIds.insert({&operation, operationIds.size()});
276 valueIds.insert({
result, valueIds.size()});
281 auto printValueRef = [&](
Value value) {
282 if (value.getDefiningOp())
283 os <<
"val_" << valueIds[value];
285 auto blockArg = cast<BlockArgument>(value);
286 os <<
"arg" << blockArg.getArgNumber() <<
"@"
287 << blockIds[blockArg.getOwner()];
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];
297 for (
Value value : orderedValues)
298 printValueRef(value);
303 os <<
"// - Block: " << blockIds[block] <<
"\n";
305 os <<
"// --- LiveIn: ";
306 printValueRefs(liveness->inValues);
307 os <<
"\n// --- LiveOut: ";
308 printValueRefs(liveness->outValues);
312 os <<
"// --- BeginLivenessIntervals";
323 return operationIds[left] < operationIds[right];
325 for (
Operation *operation : liveOperations) {
327 operation->print(os);
331 os <<
"\n// --- EndLivenessIntervals\n";
334 os <<
"// --- BeginCurrentlyLive\n";
336 auto currentlyLive = liveness->currentlyLiveValues(&op);
337 if (currentlyLive.empty())
342 printValueRefs(currentlyLive);
345 os <<
"// --- EndCurrentlyLive\n";
347 os <<
"// -------------------\n";
356 return inValues.count(value);
361 return outValues.count(value);
371 return &block->front();
381 return &block->back();
384 Operation *endOperation = startOperation;
387 useOp = block->findAncestorOpInBlock(*useOp);
391 endOperation = useOp;
403 auto addValueToCurrentlyLiveSets = [&](
Value value) {
405 Operation *startOfLiveRange = value.getDefiningOp();
409 if (
isLiveIn(value) || isa<BlockArgument>(value))
410 startOfLiveRange = &block->front();
412 startOfLiveRange = block->findAncestorOpInBlock(*startOfLiveRange);
416 endOfLiveRange = &block->back();
420 if (startOfLiveRange && !endOfLiveRange)
423 assert(endOfLiveRange &&
"Must have endOfLiveRange at this point!");
427 liveSet.insert(value);
431 for (
Value arg : block->getArguments())
432 addValueToCurrentlyLiveSets(arg);
437 addValueToCurrentlyLiveSets(
in);
442 llvm::make_range(block->begin(), ++op->getIterator()))
443 for (
auto result : walkOp.getResults())
444 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.
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()
This class represents liveness information on block level.
Liveness::ValueSetT ValueSetT
A typedef declaration of a value set.
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 & out() const
Returns all values that are live at the end 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 & in() const
Returns all values that are live at the beginning 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
LLVM_DUMP_METHOD 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...
void print(raw_ostream &os, const OpPrintingFlags &flags={})
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
operand_range getOperands()
Returns an iterator on the underlying Value's.
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),...
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.
Include the generated interface declarations.
llvm::SetVector< T, Vector, Set, N > SetVector
llvm::DenseMap< KeyT, ValueT, KeyInfoT, BucketT > DenseMap