MLIR 23.0.0git
Public Member Functions | Protected Member Functions | Friends | List of all members
mlir::DataFlowAnalysis Class Referenceabstract

Base class for all data-flow analyses. More...

#include "mlir/Analysis/DataFlowFramework.h"

Inheritance diagram for mlir::DataFlowAnalysis:

Public Member Functions

virtual ~DataFlowAnalysis ()
 DataFlowAnalysis (DataFlowSolver &solver)
 Create an analysis with a reference to the parent solver.
virtual LogicalResult initialize (Operation *top)=0
 Initialize the analysis from the provided top-level operation by building an initial dependency graph between all lattice anchors of interest.
virtual LogicalResult visit (ProgramPoint *point)=0
 Visit the given program point.
virtual void initializeEquivalentLatticeAnchor (Operation *top)
 Initialize lattice anchor equivalence class from the provided top-level operation.
TypeID getTypeID () const
 Return the TypeID of the concrete analysis class.

Protected Member Functions

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.
template<typename AnchorT>
void registerAnchorKind ()
 Register a custom lattice anchor class.
template<typename AnchorT, typename... Args>
AnchorT * getLatticeAnchor (Args &&...args)
 Get or create a custom lattice anchor.
template<typename StateT, typename AnchorT>
void unionLatticeAnchors (AnchorT anchor, AnchorT other)
 Union input anchors under the given state.
template<typename StateT, typename AnchorT>
StateT * getOrCreate (AnchorT anchor)
 Get the analysis state associated with the lattice anchor.
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.
ProgramPoint * getProgramPointBefore (Operation *op)
 Get a uniqued program point instance.
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.

Friends

class DataFlowSolver
 Allow the data-flow solver to access the internals of this class.

Detailed Description

Base class for all data-flow analyses.

A child analysis is expected to build an initial dependency graph (and optionally provide an initial state) when initialized and define transfer functions when visiting program points.

Subclasses defined in anonymous namespaces must provide an explicit TypeID via MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID in their class body. This is required because DataFlowSolver::load resolves the analysis TypeID at load time, and the implicit TypeID fallback is not supported for classes in anonymous namespaces.

In classical data-flow analysis, the dependency graph is fixed and analyses define explicit transfer functions between input states and output states. In this framework, however, the dependency graph can change during the analysis, and transfer functions are opaque such that the solver doesn't know what states calling visit on an analysis will be updated. This allows multiple analyses to plug in and provide values for the same state.

Generally, when an analysis queries an uninitialized state, it is expected to "bail out", i.e., not provide any updates. When the value is initialized, the solver will re-invoke the analysis. If the solver exhausts its worklist, however, and there are still uninitialized states, the solver "nudges" the analyses by default-initializing those states.

Definition at line 603 of file DataFlowFramework.h.

Constructor & Destructor Documentation

◆ ~DataFlowAnalysis()

DataFlowAnalysis::~DataFlowAnalysis ( )
virtualdefault

References DataFlowSolver.

◆ DataFlowAnalysis()

DataFlowAnalysis::DataFlowAnalysis ( DataFlowSolver & solver)
explicit

Create an analysis with a reference to the parent solver.

Definition at line 179 of file DataFlowFramework.cpp.

References DataFlowSolver.

Referenced by mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::AbstractDenseBackwardDataFlowAnalysis(), mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis::AbstractSparseBackwardDataFlowAnalysis(), mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::AbstractSparseForwardDataFlowAnalysis(), and mlir::dataflow::DeadCodeAnalysis::DeadCodeAnalysis().

Member Function Documentation

◆ addDependency()

void DataFlowAnalysis::addDependency ( AnalysisState * state,
ProgramPoint * point )
protected

Create a dependency between the given analysis state and lattice anchor on this analysis.

Definition at line 181 of file DataFlowFramework.cpp.

References mlir::AnalysisState::addDependency().

Referenced by mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::getLatticeElementFor(), getOrCreateFor(), and mlir::dataflow::LivenessAnalysis::visitOperation().

◆ getLatticeAnchor()

template<typename AnchorT, typename... Args>
AnchorT * mlir::DataFlowAnalysis::getLatticeAnchor ( Args &&... args)
inlineprotected

Get or create a custom lattice anchor.

Definition at line 669 of file DataFlowFramework.h.

◆ getOrCreate()

template<typename StateT, typename AnchorT>
StateT * mlir::DataFlowAnalysis::getOrCreate ( AnchorT anchor)
inlineprotected

Get the analysis state associated with the lattice anchor.

The returned state is expected to be "write-only", and any updates need to be propagated by propagateIfChanged.

Definition at line 683 of file DataFlowFramework.h.

Referenced by mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >::getLattice(), mlir::dataflow::DenseForwardDataFlowAnalysis< LatticeT >::getLattice(), mlir::dataflow::SparseBackwardDataFlowAnalysis< StateT >::getLatticeElement(), mlir::dataflow::SparseForwardDataFlowAnalysis< StateT >::getLatticeElement(), getOrCreateFor(), mlir::dataflow::DeadCodeAnalysis::initialize(), and mlir::dataflow::DeadCodeAnalysis::visit().

◆ getOrCreateFor()

template<typename StateT, typename AnchorT>
const StateT * mlir::DataFlowAnalysis::getOrCreateFor ( ProgramPoint * dependent,
AnchorT anchor )
inlineprotected

Get a read-only analysis state for the given point and create a dependency on dependent.

If the return state is updated elsewhere, this analysis is re-invoked on the dependent.

Definition at line 691 of file DataFlowFramework.h.

References addDependency(), and getOrCreate().

Referenced by mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >::getLatticeFor(), mlir::dataflow::DenseForwardDataFlowAnalysis< LatticeT >::getLatticeFor(), mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::processOperation(), mlir::dataflow::AbstractDenseForwardDataFlowAnalysis::processOperation(), mlir::dataflow::DeadCodeAnalysis::visit(), mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis::visitCallableOperation(), mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::visitCallableOperation(), mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::visitCallOperation(), mlir::dataflow::StridedMetadataRangeAnalysis::visitOperation(), and mlir::dataflow::AbstractDenseForwardDataFlowAnalysis::visitRegionBranchOperation().

◆ getProgramPointAfter() [1/2]

ProgramPoint * mlir::DataFlowAnalysis::getProgramPointAfter ( Block * block)
inlineprotected

Definition at line 712 of file DataFlowFramework.h.

◆ getProgramPointAfter() [2/2]

ProgramPoint * mlir::DataFlowAnalysis::getProgramPointAfter ( Operation * op)
inlineprotected

Definition at line 708 of file DataFlowFramework.h.

Referenced by mlir::dataflow::DeadCodeAnalysis::initialize(), mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::processOperation(), mlir::dataflow::AbstractDenseForwardDataFlowAnalysis::processOperation(), mlir::dataflow::DeadCodeAnalysis::visit(), mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis::visitCallableOperation(), mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::visitCallableOperation(), mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::visitCallOperation(), mlir::dataflow::LivenessAnalysis::visitOperation(), mlir::dataflow::StridedMetadataRangeAnalysis::visitOperation(), and mlir::dataflow::AbstractDenseForwardDataFlowAnalysis::visitRegionBranchOperation().

◆ getProgramPointBefore() [1/2]

ProgramPoint * mlir::DataFlowAnalysis::getProgramPointBefore ( Block * block)
inlineprotected

Definition at line 704 of file DataFlowFramework.h.

◆ getProgramPointBefore() [2/2]

ProgramPoint * mlir::DataFlowAnalysis::getProgramPointBefore ( Operation * op)
inlineprotected

Get a uniqued program point instance.

Definition at line 700 of file DataFlowFramework.h.

Referenced by mlir::dataflow::DeadCodeAnalysis::initialize(), mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::processOperation(), mlir::dataflow::AbstractDenseForwardDataFlowAnalysis::processOperation(), mlir::dataflow::DeadCodeAnalysis::visit(), mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::visitCallableOperation(), mlir::dataflow::IntegerRangeAnalysis::visitNonControlFlowArguments(), and mlir::dataflow::AbstractDenseForwardDataFlowAnalysis::visitRegionBranchOperation().

◆ getSolverConfig()

const DataFlowConfig & mlir::DataFlowAnalysis::getSolverConfig ( ) const
inlineprotected

Return the configuration of the solver used for this analysis.

Definition at line 717 of file DataFlowFramework.h.

Referenced by mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::visitCallableOperation(), and mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::visitCallOperation().

◆ getTypeID()

TypeID mlir::DataFlowAnalysis::getTypeID ( ) const
inline

Return the TypeID of the concrete analysis class.

Valid only after DataFlowSolver::load<AnalysisT> has returned; must not be called from the analysis constructor body because the TypeID is set by load after construction.

Definition at line 651 of file DataFlowFramework.h.

◆ initialize()

virtual LogicalResult mlir::DataFlowAnalysis::initialize ( Operation * top)
pure virtual

Initialize the analysis from the provided top-level operation by building an initial dependency graph between all lattice anchors of interest.

This can be implemented by calling visit on all program points of interest below the top-level operation.

An analysis can optionally provide initial values to certain analysis states to influence the evolution of the analysis.

Implemented in mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis, mlir::dataflow::AbstractDenseForwardDataFlowAnalysis, mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis, mlir::dataflow::AbstractSparseForwardDataFlowAnalysis, and mlir::dataflow::DeadCodeAnalysis.

◆ initializeEquivalentLatticeAnchor()

virtual void mlir::DataFlowAnalysis::initializeEquivalentLatticeAnchor ( Operation * top)
inlinevirtual

Initialize lattice anchor equivalence class from the provided top-level operation.

This function will union lattice anchor to same equivalent class if the analysis can determine the lattice content of lattice anchor is necessarily identical under the corrensponding lattice type.

Reimplemented in mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis, and mlir::dataflow::AbstractDenseForwardDataFlowAnalysis.

Definition at line 645 of file DataFlowFramework.h.

◆ propagateIfChanged()

void DataFlowAnalysis::propagateIfChanged ( AnalysisState * state,
ChangeResult changed )
protected

Propagate an update to a state if it changed.

Definition at line 186 of file DataFlowFramework.cpp.

Referenced by mlir::dataflow::DeadCodeAnalysis::initialize(), mlir::dataflow::AbstractDenseForwardDataFlowAnalysis::join(), mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::join(), mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::meet(), mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis::meet(), mlir::dataflow::IntegerRangeAnalysis::setToEntryState(), mlir::dataflow::SparseConstantPropagation::setToEntryState(), mlir::dataflow::StridedMetadataRangeAnalysis::setToEntryState(), mlir::dataflow::LivenessAnalysis::setToExitState(), mlir::dataflow::LivenessAnalysis::visitCallOperand(), mlir::dataflow::IntegerRangeAnalysis::visitNonControlFlowArguments(), mlir::dataflow::LivenessAnalysis::visitNonControlFlowArguments(), mlir::dataflow::IntegerRangeAnalysis::visitOperation(), mlir::dataflow::LivenessAnalysis::visitOperation(), mlir::dataflow::SparseConstantPropagation::visitOperation(), and mlir::dataflow::StridedMetadataRangeAnalysis::visitOperation().

◆ registerAnchorKind()

template<typename AnchorT>
void mlir::DataFlowAnalysis::registerAnchorKind ( )
inlineprotected

Register a custom lattice anchor class.

Definition at line 663 of file DataFlowFramework.h.

Referenced by mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis::AbstractSparseBackwardDataFlowAnalysis(), mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::AbstractSparseForwardDataFlowAnalysis(), and mlir::dataflow::DeadCodeAnalysis::DeadCodeAnalysis().

◆ unionLatticeAnchors()

template<typename StateT, typename AnchorT>
void mlir::DataFlowAnalysis::unionLatticeAnchors ( AnchorT anchor,
AnchorT other )
inlineprotected

Union input anchors under the given state.

Definition at line 675 of file DataFlowFramework.h.

◆ visit()

virtual LogicalResult mlir::DataFlowAnalysis::visit ( ProgramPoint * point)
pure virtual

Visit the given program point.

This function is invoked by the solver on this analysis with a given program point when a dependent analysis state is updated. The function is similar to a transfer function; it queries certain analysis states and sets other states.

The function is expected to create dependencies on queried states and propagate updates on changed states. A dependency can be created by calling addDependency between the input state and a program point, indicating that, if the state is updated, the solver should invoke solve on the program point. The dependent point does not have to be the same as the provided point. An update to a state is propagated by calling propagateIfChange on the state. If the state has changed, then all its dependents are placed on the worklist.

The dependency graph does not need to be static. Each invocation of visit can add new dependencies, but these dependencies will not be dynamically added to the worklist because the solver doesn't know what will provide a value for then.

Implemented in mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis, mlir::dataflow::AbstractDenseForwardDataFlowAnalysis, mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis, mlir::dataflow::AbstractSparseForwardDataFlowAnalysis, and mlir::dataflow::DeadCodeAnalysis.

◆ DataFlowSolver

friend class DataFlowSolver
friend

Allow the data-flow solver to access the internals of this class.

Definition at line 734 of file DataFlowFramework.h.

References DataFlowSolver.

Referenced by mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::AbstractDenseBackwardDataFlowAnalysis(), mlir::dataflow::AbstractSparseBackwardDataFlowAnalysis::AbstractSparseBackwardDataFlowAnalysis(), mlir::dataflow::AbstractSparseForwardDataFlowAnalysis::AbstractSparseForwardDataFlowAnalysis(), DataFlowAnalysis(), DataFlowSolver, mlir::dataflow::DeadCodeAnalysis::DeadCodeAnalysis(), mlir::dataflow::SparseBackwardDataFlowAnalysis< StateT >::SparseBackwardDataFlowAnalysis(), mlir::dataflow::SparseForwardDataFlowAnalysis< StateT >::SparseForwardDataFlowAnalysis(), mlir::dataflow::StridedMetadataRangeAnalysis::StridedMetadataRangeAnalysis(), and ~DataFlowAnalysis().

The documentation for this class was generated from the following files:
Generated on for MLIR by doxygen 1.14.0