13 #include <llvm/Support/DebugLog.h>
23 #define DEBUG_TYPE "liveness-analysis"
33 os << (
isLive ?
"live" :
"not live");
43 const auto *otherLiveness =
reinterpret_cast<const Liveness *
>(&other);
82 LDBG() <<
"[visitOperation] Enter: "
86 LDBG() <<
"[visitOperation] Operation has memory effects or is "
87 "return-like, marking operands live";
88 for (
auto *operand : operands) {
89 LDBG() <<
" [visitOperation] Marking operand live: " << operand <<
" ("
90 << operand->isLive <<
")";
96 bool foundLiveResult =
false;
98 if (r->isLive && !foundLiveResult) {
99 LDBG() <<
"[visitOperation] Found live result, "
100 "meeting all operands with result: "
104 for (
Liveness *operand : operands) {
105 LDBG() <<
" [visitOperation] Meeting operand: " << operand
106 <<
" with result: " << r;
109 foundLiveResult =
true;
111 LDBG() <<
"[visitOperation] Adding dependency for result: " << r
112 <<
" after op: " << *op;
119 LDBG() <<
"Visiting branch operand: " << operand.
get()
120 <<
" in op: " << *operand.
getOwner();
125 assert((isa<RegionBranchOpInterface>(op) || isa<BranchOpInterface>(op) ||
126 isa<RegionBranchTerminatorOpInterface>(op)) &&
127 "expected the op to be `RegionBranchOpInterface`, "
128 "`BranchOpInterface` or `RegionBranchTerminatorOpInterface`");
138 bool mayLive =
false;
140 if (isa<RegionBranchOpInterface>(op)) {
152 LDBG() <<
"[visitBranchOperand] Non-forwarded branch "
153 "operand may be live due to live result: "
163 for (
Block &block : region)
164 blocks.push_back(&block);
167 }
else if (isa<BranchOpInterface>(op)) {
174 LDBG() <<
"[visitBranchOperand] Non-forwarded branch operand may "
175 "be live due to branch op interface";
178 assert(isa<RegionBranchOpInterface>(parentOp) &&
179 "expected parent op to implement `RegionBranchOpInterface`");
191 LDBG() <<
"[visitBranchOperand] Non-forwarded branch "
192 "operand may be live due to parent live result: "
203 for (
Block &block : region)
204 blocks.push_back(&block);
208 for (
Block *block : blocks) {
214 LDBG() <<
"Non-forwarded branch operand may be "
215 "live due to memory effect in block: "
224 LDBG() <<
"Marking branch operand live: " << operand.
get();
236 LDBG() <<
"Visiting operation for non-forwarded branch operand: " << *op;
243 if (!isa<RegionBranchTerminatorOpInterface>(op))
249 LDBG() <<
"Visiting parent operation for non-forwarded branch operand: "
251 (void)
visitOperation(parentOp, operandLiveness, parentResultsLiveness);
255 LDBG() <<
"Visiting call operand: " << operand.
get()
256 <<
" in op: " << *operand.
getOwner();
259 assert(isa<CallOpInterface>(operand.
getOwner()) &&
260 "expected the op to implement `CallOpInterface`");
269 LDBG() <<
"Marking call operand live: " << operand.
get();
274 LDBG() <<
"setToExitState for lattice: " << lattice;
276 LDBG() <<
"Lattice already live, nothing to do";
280 LDBG() <<
"Marking lattice live due to exit state";
290 LDBG() <<
"Constructing RunLivenessAnalysis for op: " << op->
getName();
295 LDBG() <<
"Initializing and running solver";
297 LDBG() <<
"RunLivenessAnalysis initialized for op: " << op->
getName()
298 <<
" check on unreachable code now:";
305 if (getLiveness(result.value()))
307 LDBG() <<
"Result: " << result.index() <<
" of "
308 << OpWithFlags(op, OpPrintingFlags().skipRegions())
309 <<
" has no liveness info (unreachable), mark dead";
310 solver.getOrCreateState<Liveness>(result.value());
313 for (auto &block : region) {
314 for (auto blockArg : llvm::enumerate(block.getArguments())) {
315 if (getLiveness(blockArg.value()))
317 LDBG() <<
"Block argument: " << blockArg.index() <<
" of "
318 << OpWithFlags(op, OpPrintingFlags().skipRegions())
319 <<
" has no liveness info, mark dead";
320 solver.getOrCreateState<Liveness>(blockArg.value());
328 return solver.lookupState<
Liveness>(val);
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)
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.
A wrapper class that allows for printing an operation with a set of flags, useful to act as a "stream...
Operation is the basic unit of execution within MLIR.
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
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),...
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.
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...
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
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)