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, std::enable_if_t<lattice_has_meet<VT>::value>>
144 ValueT newValue = ValueT::meet(value, rhs);
145 assert(ValueT::meet(newValue, value) == newValue &&
146 "expected `meet` to be monotonic");
147 assert(ValueT::meet(newValue, rhs) == newValue &&
148 "expected `meet` to be monotonic");
151 if (newValue == value)
158 template <
typename VT>
164 void print(raw_ostream &os)
const override { value.print(os); }
205 CallOpInterface call,
246 void visitBlock(
Block *block);
252 void visitRegionSuccessors(
ProgramPoint point, RegionBranchOpInterface branch,
265 template <
typename StateT>
269 std::is_base_of<AbstractSparseLattice, StateT>::value,
270 "analysis state class expected to subclass AbstractSparseLattice");
298 unsigned firstIndex) {
307 return getOrCreate<StateT>(value);
313 return static_cast<const StateT *
>(
329 void visitOperationImpl(
334 {
reinterpret_cast<const StateT *
const *
>(operandLattices.begin()),
335 operandLattices.size()},
336 {
reinterpret_cast<StateT *
const *
>(resultLattices.begin()),
337 resultLattices.size()});
339 void visitExternalCallImpl(
340 CallOpInterface call,
341 ArrayRef<const AbstractSparseLattice *> argumentLattices,
342 ArrayRef<AbstractSparseLattice *> resultLattices)
override {
345 {
reinterpret_cast<const StateT *
const *
>(argumentLattices.begin()),
346 argumentLattices.size()},
347 {
reinterpret_cast<StateT *
const *
>(resultLattices.begin()),
348 resultLattices.size()});
350 void visitNonControlFlowArgumentsImpl(
351 Operation *op,
const RegionSuccessor &successor,
352 ArrayRef<AbstractSparseLattice *> argLattices,
353 unsigned firstIndex)
override {
356 {
reinterpret_cast<StateT *
const *
>(argLattices.begin()),
428 void visitBlock(
Block *block);
431 void visitRegionSuccessors(RegionBranchOpInterface branch,
438 void visitRegionSuccessorsFromTerminator(
439 RegionBranchTerminatorOpInterface terminator,
440 RegionBranchOpInterface branch);
465 template <
typename StateT>
484 (void)argumentLattices;
485 (void)resultLattices;
486 for (
OpOperand &operand : call->getOpOperands()) {
494 return getOrCreate<StateT>(value);
511 void visitOperationImpl(
516 {
reinterpret_cast<StateT *
const *
>(operandLattices.begin()),
517 operandLattices.size()},
518 {
reinterpret_cast<const StateT *
const *
>(resultLattices.begin()),
519 resultLattices.size()});
522 void visitExternalCallImpl(
523 CallOpInterface call, ArrayRef<AbstractSparseLattice *> operandLattices,
524 ArrayRef<const AbstractSparseLattice *> resultLattices)
override {
527 {
reinterpret_cast<StateT *
const *
>(operandLattices.begin()),
528 operandLattices.size()},
529 {
reinterpret_cast<const StateT *
const *
>(resultLattices.begin()),
530 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.
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.
decltype(std::declval< T >().meet()) has_meet
Trait to check if T provides a meet method.
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.
ChangeResult meet(const VT &rhs)
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.
This class represents an efficient way to signal success or failure.
Fundamental IR components are supported as first-class program points.