An analysis that, by going backwards along the dataflow graph, annotates each value with a boolean storing true iff it is "live". More...
#include "mlir/Analysis/DataFlow/LivenessAnalysis.h"
Inheritance diagram for mlir::dataflow::LivenessAnalysis:Public Member Functions | |
| LogicalResult | visitOperation (Operation *op, ArrayRef< Liveness * > operands, ArrayRef< const Liveness * > results) override |
| For every value, liveness analysis determines whether or not it is "live". More... | |
| void | visitBranchOperand (OpOperand &operand) override |
| void | visitCallOperand (OpOperand &operand) override |
| void | setToExitState (Liveness *lattice) override |
| Set the given lattice element(s) at control flow exit point(s). More... | |
| SparseBackwardDataFlowAnalysis (DataFlowSolver &solver, SymbolTableCollection &symbolTable) | |
| Public Member Functions inherited from mlir::dataflow::SparseBackwardDataFlowAnalysis< Liveness > | |
| SparseBackwardDataFlowAnalysis (DataFlowSolver &solver, SymbolTableCollection &symbolTable) | |
| virtual void | visitExternalCall (CallOpInterface call, ArrayRef< Liveness * > argumentLattices, ArrayRef< const Liveness * > resultLattices) |
| Visit a call to an external function. More... | |
| Public Member Functions inherited from mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis | |
| LogicalResult | initialize (Operation *top) override |
| Initialize the analysis by visiting the operation and everything nested under it. More... | |
| LogicalResult | visit (ProgramPoint *point) override |
| Visit a program point. More... | |
| Public Member Functions inherited from mlir::DataFlowAnalysis | |
| virtual | ~DataFlowAnalysis () |
| DataFlowAnalysis (DataFlowSolver &solver) | |
| Create an analysis with a reference to the parent solver. More... | |
| virtual void | initializeEquivalentLatticeAnchor (Operation *top) |
| Initialize lattice anchor equivalence class from the provided top-level operation. More... | |
Additional Inherited Members | |
| Protected Member Functions inherited from mlir::dataflow::SparseBackwardDataFlowAnalysis< Liveness > | |
| Liveness * | getLatticeElement (Value value) override |
| Get the lattice element for a value. More... | |
| void | setToExitState (AbstractSparseLattice *lattice) override |
| Set the given lattice element(s) at control flow exit point(s) and propagate the update if it chaned. More... | |
| void | setAllToExitStates (ArrayRef< Liveness * > lattices) |
| Protected Member Functions inherited from mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis | |
| AbstractSparseBackwardDataFlowAnalysis (DataFlowSolver &solver, SymbolTableCollection &symbolTable) | |
| void | setAllToExitStates (ArrayRef< AbstractSparseLattice * > lattices) |
| Set the given lattice element(s) at control flow exit point(s) and propagate the update if it chaned. More... | |
| SmallVector< AbstractSparseLattice * > | getLatticeElements (ValueRange values) |
| Get the lattice elements for a range of values. More... | |
| void | meet (AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs) |
| Join the lattice element and propagate and update if it changed. More... | |
| virtual LogicalResult | visitCallableOperation (Operation *op, CallableOpInterface callable, ArrayRef< AbstractSparseLattice * > operandLattices) |
| Visits a callable operation. More... | |
| Protected Member Functions inherited from mlir::DataFlowAnalysis | |
| void | addDependency (AnalysisState *state, ProgramPoint *point) |
| Create a dependency between the given analysis state and lattice anchor on this analysis. More... | |
| void | propagateIfChanged (AnalysisState *state, ChangeResult changed) |
| Propagate an update to a state if it changed. More... | |
| template<typename AnchorT > | |
| void | registerAnchorKind () |
| Register a custom lattice anchor class. More... | |
| template<typename AnchorT , typename... Args> | |
| AnchorT * | getLatticeAnchor (Args &&...args) |
| Get or create a custom lattice anchor. More... | |
| template<typename StateT , typename AnchorT > | |
| void | unionLatticeAnchors (AnchorT anchor, AnchorT other) |
| Union input anchors under the given state. More... | |
| template<typename StateT , typename AnchorT > | |
| StateT * | getOrCreate (AnchorT anchor) |
| Get the analysis state associated with the lattice anchor. More... | |
| template<typename StateT , typename AnchorT > | |
| const StateT * | getOrCreateFor (ProgramPoint *dependent, AnchorT anchor) |
Get a read-only analysis state for the given point and create a dependency on dependent. More... | |
| ProgramPoint * | getProgramPointBefore (Operation *op) |
| Get a uniqued program point instance. More... | |
| ProgramPoint * | getProgramPointBefore (Block *block) |
| ProgramPoint * | getProgramPointAfter (Operation *op) |
| ProgramPoint * | getProgramPointAfter (Block *block) |
| const DataFlowConfig & | getSolverConfig () const |
| Return the configuration of the solver used for this analysis. More... | |
Detailed Description
An analysis that, by going backwards along the dataflow graph, annotates each value with a boolean storing true iff it is "live".
Definition at line 78 of file LivenessAnalysis.h.
Member Function Documentation
◆ setToExitState()
|
overridevirtual |
Set the given lattice element(s) at control flow exit point(s).
Implements mlir::dataflow::SparseBackwardDataFlowAnalysis< Liveness >.
Definition at line 306 of file LivenessAnalysis.cpp.
References mlir::Change, mlir::dataflow::Liveness::isLive, mlir::dataflow::Liveness::markLive(), and mlir::DataFlowAnalysis::propagateIfChanged().
◆ SparseBackwardDataFlowAnalysis()
|
inlineexplicit |
Definition at line 526 of file SparseAnalysis.h.
◆ visitBranchOperand()
|
overridevirtual |
Implements mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis.
Definition at line 118 of file LivenessAnalysis.cpp.
References mlir::detail::enumerate(), mlir::IROperand< DerivedT, IRValueT >::get(), mlir::dataflow::SparseBackwardDataFlowAnalysis< Liveness >::getLatticeElement(), mlir::Operation::getNumResults(), mlir::detail::IROperandBase::getOwner(), mlir::Operation::getParentOp(), mlir::Operation::getRegions(), mlir::Operation::getResults(), mlir::isMemoryEffectFree(), mlir::dataflow::Liveness::markLive(), mlir::DataFlowAnalysis::propagateIfChanged(), and visitOperation().
◆ visitCallOperand()
|
overridevirtual |
Implements mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis.
Definition at line 287 of file LivenessAnalysis.cpp.
References mlir::IROperand< DerivedT, IRValueT >::get(), mlir::dataflow::SparseBackwardDataFlowAnalysis< Liveness >::getLatticeElement(), mlir::detail::IROperandBase::getOwner(), mlir::dataflow::Liveness::markLive(), and mlir::DataFlowAnalysis::propagateIfChanged().
◆ visitOperation()
|
overridevirtual |
For every value, liveness analysis determines whether or not it is "live".
A value is considered "live" iff it: (1) has memory effects OR (2) is returned by a public function OR (3) is used to compute a value of type (1) or (2) OR (4) is returned by a return-like op whose parent isn't a callable nor a RegionBranchOpInterface (e.g.: linalg.yield, gpu.yield,...) These ops have their own semantics, so we conservatively mark the the yield value as live. It is also to be noted that a value could be of multiple types (1/2/3) at the same time.
A value "has memory effects" iff it: (1.a) is an operand of an op with memory effects OR (1.b) is a non-forwarded branch operand and its branch op could take the control to a block that has an op with memory effects OR (1.c) is a non-forwarded branch operand and its branch op could result in different live result OR (1.d) is a non-forwarded call operand.
A value A is said to be "used to compute" value B iff B cannot be computed in the absence of A. Thus, in this implementation, we say that value A is used to compute value B iff: (3.a) B is a result of an op with operand A OR (3.b) A is used to compute some value C and C is used to compute B.
Implements mlir::dataflow::SparseBackwardDataFlowAnalysis< Liveness >.
Definition at line 80 of file LivenessAnalysis.cpp.
References mlir::DataFlowAnalysis::addDependency(), mlir::DataFlowAnalysis::getProgramPointAfter(), mlir::Operation::hasTrait(), mlir::isMemoryEffectFree(), mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis::meet(), and mlir::DataFlowAnalysis::propagateIfChanged().
Referenced by visitBranchOperand().
The documentation for this class was generated from the following files:
- include/mlir/Analysis/DataFlow/LivenessAnalysis.h
- lib/Analysis/DataFlow/LivenessAnalysis.cpp
