15 #ifndef MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H
16 #define MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H
22 #include "llvm/ADT/SmallPtrSet.h"
62 useDefSubscribers.insert(analysis);
84 template <
typename ValueT>
117 ValueT newValue = ValueT::join(value, rhs);
118 assert(ValueT::join(newValue, value) == newValue &&
119 "expected `join` to be monotonic");
120 assert(ValueT::join(newValue, rhs) == newValue &&
121 "expected `join` to be monotonic");
124 if (newValue == value)
134 template <
typename T,
typename... Args>
136 template <
typename T>
142 template <
typename VT,
143 std::enable_if_t<lattice_has_meet<VT>::value> * =
nullptr>
145 ValueT newValue = ValueT::meet(value, rhs);
146 assert(ValueT::meet(newValue, value) == newValue &&
147 "expected `meet` to be monotonic");
148 assert(ValueT::meet(newValue, rhs) == newValue &&
149 "expected `meet` to be monotonic");
152 if (newValue == value)
159 template <
typename VT,
160 std::enable_if_t<!lattice_has_meet<VT>::value> * =
nullptr>
166 void print(raw_ostream &os)
const override { value.print(os); }
207 CallOpInterface call,
236 LogicalResult initializeRecursively(
Operation *op);
248 void visitBlock(
Block *block);
254 void visitRegionSuccessors(
ProgramPoint point, RegionBranchOpInterface branch,
267 template <
typename StateT>
271 std::is_base_of<AbstractSparseLattice, StateT>::value,
272 "analysis state class expected to subclass AbstractSparseLattice");
300 unsigned firstIndex) {
309 return getOrCreate<StateT>(value);
315 return static_cast<const StateT *
>(
331 void visitOperationImpl(
336 {
reinterpret_cast<const StateT *
const *
>(operandLattices.begin()),
337 operandLattices.size()},
338 {
reinterpret_cast<StateT *
const *
>(resultLattices.begin()),
339 resultLattices.size()});
341 void visitExternalCallImpl(
342 CallOpInterface call,
343 ArrayRef<const AbstractSparseLattice *> argumentLattices,
344 ArrayRef<AbstractSparseLattice *> resultLattices)
override {
347 {
reinterpret_cast<const StateT *
const *
>(argumentLattices.begin()),
348 argumentLattices.size()},
349 {
reinterpret_cast<StateT *
const *
>(resultLattices.begin()),
350 resultLattices.size()});
352 void visitNonControlFlowArgumentsImpl(
353 Operation *op,
const RegionSuccessor &successor,
354 ArrayRef<AbstractSparseLattice *> argLattices,
355 unsigned firstIndex)
override {
358 {
reinterpret_cast<StateT *
const *
>(argLattices.begin()),
422 LogicalResult initializeRecursively(
Operation *op);
430 void visitBlock(
Block *block);
433 void visitRegionSuccessors(RegionBranchOpInterface branch,
440 void visitRegionSuccessorsFromTerminator(
441 RegionBranchTerminatorOpInterface terminator,
442 RegionBranchOpInterface branch);
467 template <
typename StateT>
486 (void)argumentLattices;
487 (void)resultLattices;
488 for (
OpOperand &operand : call->getOpOperands()) {
496 return getOrCreate<StateT>(value);
513 void visitOperationImpl(
518 {
reinterpret_cast<StateT *
const *
>(operandLattices.begin()),
519 operandLattices.size()},
520 {
reinterpret_cast<const StateT *
const *
>(resultLattices.begin()),
521 resultLattices.size()});
524 void visitExternalCallImpl(
525 CallOpInterface call, ArrayRef<AbstractSparseLattice *> operandLattices,
526 ArrayRef<const AbstractSparseLattice *> resultLattices)
override {
529 {
reinterpret_cast<StateT *
const *
>(operandLattices.begin()),
530 operandLattices.size()},
531 {
reinterpret_cast<const StateT *
const *
>(resultLattices.begin()),
532 resultLattices.size()});
Base class for generic analysis states.
ProgramPoint getPoint() const
Returns the program point this state is located at.
ProgramPoint point
The program point to which the state belongs.
Block represents an ordered list of Operations.
Base class for all data-flow analyses.
The general data-flow analysis solver.
This class represents an operand of an operation.
Operation is the basic unit of execution within MLIR.
This class represents a point being branched from in the methods of the RegionBranchOpInterface.
This class represents a successor of a region.
ValueRange getSuccessorInputs() const
Return the inputs to the successor that are remapped by the exit values of the current region.
This class represents a collection of SymbolTables.
This class provides an abstraction over the different types of ranges over Values.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Base class for sparse backward data-flow analyses.
virtual void setToExitState(AbstractSparseLattice *lattice)=0
Set the given lattice element(s) at control flow exit point(s).
SmallVector< AbstractSparseLattice * > getLatticeElements(ValueRange values)
Get the lattice elements for a range of values.
AbstractSparseBackwardDataFlowAnalysis(DataFlowSolver &solver, SymbolTableCollection &symbolTable)
virtual void visitBranchOperand(OpOperand &operand)=0
virtual void visitOperationImpl(Operation *op, ArrayRef< AbstractSparseLattice * > operandLattices, ArrayRef< const AbstractSparseLattice * > resultLattices)=0
The operation transfer function.
virtual void visitCallOperand(OpOperand &operand)=0
LogicalResult visit(ProgramPoint point) override
Visit a program point.
void meet(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs)
Join the lattice element and propagate and update if it changed.
virtual void visitExternalCallImpl(CallOpInterface call, ArrayRef< AbstractSparseLattice * > operandLattices, ArrayRef< const AbstractSparseLattice * > resultLattices)=0
The transfer function for calls to external functions.
virtual AbstractSparseLattice * getLatticeElement(Value value)=0
Get the lattice element for a value.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting the operation and everything nested under it.
void setAllToExitStates(ArrayRef< AbstractSparseLattice * > lattices)
Set the given lattice element(s) at control flow exit point(s).
Base class for sparse forward data-flow analyses.
LogicalResult visit(ProgramPoint point) override
Visit a program point.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting every owner of an SSA value: all operations and blocks.
virtual void visitOperationImpl(Operation *op, ArrayRef< const AbstractSparseLattice * > operandLattices, ArrayRef< AbstractSparseLattice * > resultLattices)=0
The operation transfer function.
virtual AbstractSparseLattice * getLatticeElement(Value value)=0
Get the lattice element of a value.
virtual void visitExternalCallImpl(CallOpInterface call, ArrayRef< const AbstractSparseLattice * > argumentLattices, ArrayRef< AbstractSparseLattice * > resultLattices)=0
The transfer function for calls to external functions.
AbstractSparseForwardDataFlowAnalysis(DataFlowSolver &solver)
void setAllToEntryStates(ArrayRef< AbstractSparseLattice * > lattices)
virtual void setToEntryState(AbstractSparseLattice *lattice)=0
Set the given lattice element(s) at control flow entry point(s).
virtual void visitNonControlFlowArgumentsImpl(Operation *op, const RegionSuccessor &successor, ArrayRef< AbstractSparseLattice * > argLattices, unsigned firstIndex)=0
Given an operation with region control-flow, the lattices of the operands, and a region successor,...
const AbstractSparseLattice * getLatticeElementFor(ProgramPoint point, Value value)
Get a read-only lattice element for a value and add it as a dependency to a program point.
void join(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs)
Join the lattice element and propagate and update if it changed.
This class represents an abstract lattice.
void onUpdate(DataFlowSolver *solver) const override
When the lattice gets updated, propagate an update to users of the value using its use-def chain to s...
virtual ChangeResult join(const AbstractSparseLattice &rhs)
Join the information contained in 'rhs' into this lattice.
Value getPoint() const
Return the program point this lattice is located at.
virtual ChangeResult meet(const AbstractSparseLattice &rhs)
Meet (intersect) the information in this lattice with 'rhs'.
void useDefSubscribe(DataFlowAnalysis *analysis)
Subscribe an analysis to updates of the lattice.
AbstractSparseLattice(Value value)
Lattices can only be created for values.
This class represents a lattice holding a specific value of type ValueT.
ChangeResult join(const ValueT &rhs)
Join the information contained in the 'rhs' value into this lattice.
void print(raw_ostream &os) const override
Print the lattice element.
ChangeResult meet(const VT &rhs)
Meet (intersect) the information contained in the 'rhs' value with this lattice.
decltype(&T::meet) has_meet
Trait to check if T provides a meet method.
const ValueT & getValue() const
ValueT & getValue()
Return the value held by this lattice.
llvm::is_detected< has_meet, T > lattice_has_meet
ChangeResult join(const AbstractSparseLattice &rhs) override
Join the information contained in the 'rhs' lattice into this lattice.
ChangeResult meet(const AbstractSparseLattice &rhs) override
Meet (intersect) the information contained in the 'rhs' lattice with this lattice.
Value getPoint() const
Return the program point this lattice is located at.
A sparse (backward) data-flow analysis for propagating SSA value lattices backwards across the IR by ...
StateT * getLatticeElement(Value value) override
Get the lattice element for a value.
void setAllToExitStates(ArrayRef< StateT * > lattices)
virtual void visitExternalCall(CallOpInterface call, ArrayRef< StateT * > argumentLattices, ArrayRef< const StateT * > resultLattices)
Visit a call to an external function.
void setToExitState(AbstractSparseLattice *lattice) override
Set the given lattice element(s) at control flow exit point(s).
SparseBackwardDataFlowAnalysis(DataFlowSolver &solver, SymbolTableCollection &symbolTable)
virtual void visitOperation(Operation *op, ArrayRef< StateT * > operands, ArrayRef< const StateT * > results)=0
Visit an operation with the lattices of its results.
virtual void setToExitState(StateT *lattice)=0
Set the given lattice element(s) at control flow exit point(s).
A sparse forward data-flow analysis for propagating SSA value lattices across the IR by implementing ...
const StateT * getLatticeElementFor(ProgramPoint point, Value value)
Get the lattice element for a value and create a dependency on the provided program point.
virtual void visitExternalCall(CallOpInterface call, ArrayRef< const StateT * > argumentLattices, ArrayRef< StateT * > resultLattices)
Visit a call operation to an externally defined function given the lattices of its arguments.
StateT * getLatticeElement(Value value) override
Get the lattice element for a value.
virtual void setToEntryState(StateT *lattice)=0
Set the given lattice element(s) at control flow entry point(s).
void setAllToEntryStates(ArrayRef< StateT * > lattices)
virtual void visitNonControlFlowArguments(Operation *op, const RegionSuccessor &successor, ArrayRef< StateT * > argLattices, unsigned firstIndex)
Given an operation with possible region control-flow, the lattices of the operands,...
virtual void visitOperation(Operation *op, ArrayRef< const StateT * > operands, ArrayRef< StateT * > results)=0
Visit an operation with the lattices of its operands.
SparseForwardDataFlowAnalysis(DataFlowSolver &solver)
Include the generated interface declarations.
ChangeResult
A result type used to indicate if a change happened.
Fundamental IR components are supported as first-class program points.