13 #include <llvm/Support/Debug.h>
23 #define DEBUG_TYPE "liveness-analysis"
24 #define DBGS() (llvm::dbgs() << '[' << DEBUG_TYPE << "] ")
25 #define LDBG(X) LLVM_DEBUG(DBGS() << X << "\n")
35 os << (
isLive ?
"live" :
"not live");
45 const auto *otherLiveness =
reinterpret_cast<const Liveness *
>(&other);
84 LLVM_DEBUG(
DBGS() <<
"[visitOperation] Enter: ";
86 llvm::dbgs() <<
"\n");
89 LDBG(
"[visitOperation] Operation has memory effects or is "
90 "return-like, marking operands live");
91 for (
auto *operand : operands) {
92 LDBG(
" [visitOperation] Marking operand live: "
93 << operand <<
" (" << operand->isLive <<
")");
99 bool foundLiveResult =
false;
101 if (r->isLive && !foundLiveResult) {
102 LDBG(
"[visitOperation] Found live result, "
103 "meeting all operands with result: "
107 for (
Liveness *operand : operands) {
108 LDBG(
" [visitOperation] Meeting operand: " << operand
109 <<
" with result: " << r);
112 foundLiveResult =
true;
114 LDBG(
"[visitOperation] Adding dependency for result: " << r <<
" after op: "
122 LDBG(
"Visiting branch operand: " << operand.
get()
123 <<
" in op: " << *operand.
getOwner());
128 assert((isa<RegionBranchOpInterface>(op) || isa<BranchOpInterface>(op) ||
129 isa<RegionBranchTerminatorOpInterface>(op)) &&
130 "expected the op to be `RegionBranchOpInterface`, "
131 "`BranchOpInterface` or `RegionBranchTerminatorOpInterface`");
141 bool mayLive =
false;
143 if (isa<RegionBranchOpInterface>(op)) {
155 LDBG(
"[visitBranchOperand] Non-forwarded branch "
156 "operand may be live due to live result: "
166 for (
Block &block : region)
167 blocks.push_back(&block);
170 }
else if (isa<BranchOpInterface>(op)) {
177 LDBG(
"[visitBranchOperand] Non-forwarded branch operand may "
178 "be live due to branch op interface");
181 assert(isa<RegionBranchOpInterface>(parentOp) &&
182 "expected parent op to implement `RegionBranchOpInterface`");
194 LDBG(
"[visitBranchOperand] Non-forwarded branch "
195 "operand may be live due to parent live result: "
206 for (
Block &block : region)
207 blocks.push_back(&block);
211 for (
Block *block : blocks) {
217 LDBG(
"Non-forwarded branch operand may be "
218 "live due to memory effect in block: "
227 LDBG(
"Marking branch operand live: " << operand.
get());
239 LDBG(
"Visiting operation for non-forwarded branch operand: " << *op);
246 if (!isa<RegionBranchTerminatorOpInterface>(op))
252 LDBG(
"Visiting parent operation for non-forwarded branch operand: "
254 (void)
visitOperation(parentOp, operandLiveness, parentResultsLiveness);
258 LDBG(
"Visiting call operand: " << operand.
get()
259 <<
" in op: " << *operand.
getOwner());
262 assert(isa<CallOpInterface>(operand.
getOwner()) &&
263 "expected the op to implement `CallOpInterface`");
272 LDBG(
"Marking call operand live: " << operand.
get());
277 LDBG(
"setToExitState for lattice: " << lattice);
279 LDBG(
"Lattice already live, nothing to do");
283 LDBG(
"Marking lattice live due to exit state");
293 LDBG(
"Constructing RunLivenessAnalysis for op: " << op->
getName());
298 LDBG(
"Initializing and running solver");
300 LDBG(
"Dumping liveness state for op");
Block represents an ordered list of Operations.
void addDependency(AnalysisState *state, ProgramPoint *point)
Create a dependency between the given analysis state and lattice anchor on this analysis.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
ProgramPoint * getProgramPointAfter(Operation *op)
const StateT * lookupState(AnchorT anchor) const
Lookup an analysis state for the given lattice anchor.
AnalysisT * load(Args &&...args)
Load an analysis into the solver. Return the analysis instance.
LogicalResult initializeAndRun(Operation *top)
Initialize the children analyses starting from the provided top-level operation and run the analysis ...
IRValueT get() const
Return the current value being used by this operand.
This class represents an operand of an operation.
Set of flags used to control the behavior of the various IR print methods (e.g.
Operation is the basic unit of execution within MLIR.
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
OperationName getName()
The name of an operation is the key identifier for it.
void print(raw_ostream &os, const OpPrintingFlags &flags={})
result_range getResults()
unsigned getNumResults()
Return the number of results held by this operation.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
This class represents a collection of SymbolTables.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
void meet(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs)
Join the lattice element and propagate and update if it changed.
This class represents an abstract lattice.
An analysis that, by going backwards along the dataflow graph, annotates each value with a boolean st...
void setToExitState(Liveness *lattice) override
Set the given lattice element(s) at control flow exit point(s).
void visitBranchOperand(OpOperand &operand) override
void visitCallOperand(OpOperand &operand) override
LogicalResult visitOperation(Operation *op, ArrayRef< Liveness * > operands, ArrayRef< const Liveness * > results) override
For every value, liveness analysis determines whether or not it is "live".
Liveness * getLatticeElement(Value value) override
Get the lattice element for a value.
Operation * getOwner() const
Return the owner of this operand.
void loadBaselineAnalyses(DataFlowSolver &solver)
Populates a DataFlowSolver with analyses that are required to ensure user-defined analyses are run pr...
Include the generated interface declarations.
ChangeResult
A result type used to indicate if a change happened.
bool isMemoryEffectFree(Operation *op)
Returns true if the given operation is free of memory effects.
This trait indicates that a terminator operation is "return-like".
This lattice represents, for a given value, whether or not it is "live".
void print(raw_ostream &os) const override
Print the contents of the analysis state.
ChangeResult meet(const AbstractSparseLattice &other) override
Meet (intersect) the information in this lattice with 'rhs'.
RunLivenessAnalysis(Operation *op)
const Liveness * getLiveness(Value val)