The general data-flow analysis solver. More...

#include "mlir/Analysis/DataFlowFramework.h"

Public Types
using	WorkItem = std::pair< ProgramPoint , DataFlowAnalysis >
	A work item on the solver queue is a program point, child analysis pair. More...

Public Member Functions
	DataFlowSolver (const DataFlowConfig &config=DataFlowConfig())

template<typename AnalysisT , typename... Args>
AnalysisT *	load (Args &&...args)
	Load an analysis into the solver. Return the analysis instance. More...

LogicalResult	initializeAndRun (Operation *top)
	Initialize the children analyses starting from the provided top-level operation and run the analysis until fixpoint. More...

template<typename StateT , typename AnchorT >
const StateT *	lookupState (AnchorT anchor) const
	Lookup an analysis state for the given lattice anchor. More...

template<typename AnchorT >
void	eraseState (AnchorT anchor)
	Erase any analysis state associated with the given lattice anchor. More...

void	eraseAllStates ()
	Erase all analysis states. More...

template<typename AnchorT , typename... Args>
AnchorT *	getLatticeAnchor (Args &&...args)
	Get a uniqued lattice anchor instance. More...

ProgramPoint *	getProgramPointBefore (Operation *op)
	Get a uniqued program point instance. More...

ProgramPoint *	getProgramPointBefore (Block *block)

ProgramPoint *	getProgramPointAfter (Operation *op)

ProgramPoint *	getProgramPointAfter (Block *block)

void	enqueue (WorkItem item)
	Push a work item onto the worklist. More...

template<typename StateT , typename AnchorT >
StateT *	getOrCreateState (AnchorT anchor)
	Get the state associated with the given lattice anchor. More...

template<typename StateT >
LatticeAnchor	getLeaderAnchorOrSelf (LatticeAnchor latticeAnchor) const
	Get leader lattice anchor in equivalence lattice anchor group, return input lattice anchor if input not found in equivalece lattice anchor group. More...

template<typename StateT , typename AnchorT >
void	unionLatticeAnchors (AnchorT anchor, AnchorT other)
	Union input anchors under the given state. More...

template<typename StateT >
bool	isEquivalent (LatticeAnchor lhs, LatticeAnchor rhs) const
	Return given lattice is equivalent on given state. More...

void	propagateIfChanged (AnalysisState *state, ChangeResult changed)
	Propagate an update to an analysis state if it changed by pushing dependent work items to the back of the queue. More...

const DataFlowConfig &	getConfig () const
	Get the configuration of the solver. More...

Friends
class	DataFlowAnalysis
	Allow the base child analysis class to access the internals of the solver. More...

Detailed Description

The general data-flow analysis solver.

This class is responsible for orchestrating child data-flow analyses, running the fixed-point iteration algorithm, managing analysis state and lattice anchor memory, and tracking dependencies between analyses, lattice anchor, and analysis states.

Steps to run a data-flow analysis:

Load and initialize children analyses. Children analyses are instantiated in the solver and initialized, building their dependency relations.
Configure and run the analysis. The solver invokes the children analyses according to their dependency relations until a fixed point is reached.
Query analysis state results from the solver.

Steps to re-run a data-flow analysis when IR changes:

Erase all analysis states as they are no longer valid.
Re-run the analysis using initializeAndRun.

TODO: Optimize the internal implementation of the solver.

Definition at line 325 of file DataFlowFramework.h.

Member Typedef Documentation

◆ WorkItem

using mlir::DataFlowSolver::WorkItem = std::pair<ProgramPoint *, DataFlowAnalysis *>

A work item on the solver queue is a program point, child analysis pair.

Each item is processed by invoking the child analysis at the program point.

Definition at line 426 of file DataFlowFramework.h.

Constructor & Destructor Documentation

◆ DataFlowSolver()

mlir::DataFlowSolver::DataFlowSolver ( const DataFlowConfig & config = DataFlowConfig() )

inlineexplicit

Definition at line 327 of file DataFlowFramework.h.

References mlir::StorageUniquer::registerParametricStorageType().

Member Function Documentation

◆ enqueue()

void mlir::DataFlowSolver::enqueue ( WorkItem item )

inline

Push a work item onto the worklist.

Definition at line 428 of file DataFlowFramework.h.

Referenced by mlir::AnalysisState::onUpdate(), mlir::dataflow::Executable::onUpdate(), and mlir::dataflow::AbstractSparseLattice::onUpdate().

◆ eraseAllStates()

void mlir::DataFlowSolver::eraseAllStates ( )

inline

Erase all analysis states.

Definition at line 382 of file DataFlowFramework.h.

◆ eraseState()

template<typename AnchorT >

void mlir::DataFlowSolver::eraseState ( AnchorT anchor )

inline

Erase any analysis state associated with the given lattice anchor.

Definition at line 357 of file DataFlowFramework.h.

Referenced by mlir::dataflow::maybeReplaceWithConstant().

◆ getConfig()

const DataFlowConfig& mlir::DataFlowSolver::getConfig ( ) const

inline

Get the configuration of the solver.

Definition at line 456 of file DataFlowFramework.h.

Referenced by mlir::DataFlowAnalysis::getSolverConfig().

◆ getLatticeAnchor()

template<typename AnchorT , typename... Args>

AnchorT* mlir::DataFlowSolver::getLatticeAnchor ( Args &&... args )

inline

Get a uniqued lattice anchor instance.

If one is not present, it is created with the provided arguments.

Definition at line 390 of file DataFlowFramework.h.

References mlir::get().

Referenced by mlir::DataFlowAnalysis::getLatticeAnchor().

◆ getLeaderAnchorOrSelf()

template<typename StateT >

LatticeAnchor mlir::DataFlowSolver::getLeaderAnchorOrSelf ( LatticeAnchor latticeAnchor ) const

Get leader lattice anchor in equivalence lattice anchor group, return input lattice anchor if input not found in equivalece lattice anchor group.

Definition at line 717 of file DataFlowFramework.h.

◆ getOrCreateState()

template<typename StateT , typename AnchorT >

StateT * mlir::DataFlowSolver::getOrCreateState ( AnchorT anchor )

Get the state associated with the given lattice anchor.

If it does not exist, create an uninitialized state.

Definition at line 732 of file DataFlowFramework.h.

Referenced by copyIntegerRange(), mlir::DataFlowAnalysis::getOrCreate(), and mlir::dataflow::IntegerValueRangeLattice::onUpdate().

◆ getProgramPointAfter() [1/2]

ProgramPoint* mlir::DataFlowSolver::getProgramPointAfter ( Block * block )

inline

Definition at line 418 of file DataFlowFramework.h.

References mlir::Block::end(), and mlir::StorageUniquer::get().

◆ getProgramPointAfter() [2/2]

ProgramPoint* mlir::DataFlowSolver::getProgramPointAfter ( Operation * op )

inline

Definition at line 409 of file DataFlowFramework.h.

References mlir::StorageUniquer::get(), and mlir::Operation::getBlock().

Referenced by mlir::DataFlowAnalysis::getProgramPointAfter(), mlir::dataflow::Executable::onUpdate(), and mlir::dataflow::AbstractSparseLattice::onUpdate().

◆ getProgramPointBefore() [1/2]

ProgramPoint* mlir::DataFlowSolver::getProgramPointBefore ( Block * block )

inline

Definition at line 404 of file DataFlowFramework.h.

References mlir::Block::begin(), and mlir::StorageUniquer::get().

◆ getProgramPointBefore() [2/2]

ProgramPoint* mlir::DataFlowSolver::getProgramPointBefore ( Operation * op )

inline

Get a uniqued program point instance.

Definition at line 395 of file DataFlowFramework.h.

References mlir::StorageUniquer::get(), and mlir::Operation::getBlock().

Referenced by mlir::DataFlowAnalysis::getProgramPointBefore(), and mlir::dataflow::Executable::onUpdate().

◆ initializeAndRun()

LogicalResult DataFlowSolver::initializeAndRun ( Operation * top )

Initialize the children analyses starting from the provided top-level operation and run the analysis until fixpoint.

Definition at line 107 of file DataFlowFramework.cpp.

References DATAFLOW_DEBUG.

Referenced by mlir::dataflow::RunLivenessAnalysis::RunLivenessAnalysis().

◆ isEquivalent()

template<typename StateT >

bool mlir::DataFlowSolver::isEquivalent	(	LatticeAnchor	lhs,
		LatticeAnchor	rhs
	)		const

Return given lattice is equivalent on given state.

Definition at line 748 of file DataFlowFramework.h.

◆ load()

template<typename AnalysisT , typename... Args>

AnalysisT * mlir::DataFlowSolver::load ( Args &&... args )

Load an analysis into the solver. Return the analysis instance.

Definition at line 707 of file DataFlowFramework.h.

Referenced by mlir::dataflow::RunLivenessAnalysis::RunLivenessAnalysis().

◆ lookupState()

template<typename StateT , typename AnchorT >

const StateT* mlir::DataFlowSolver::lookupState ( AnchorT anchor ) const

inline

Lookup an analysis state for the given lattice anchor.

Returns null if one does not exist.

Definition at line 343 of file DataFlowFramework.h.

Referenced by copyIntegerRange(), mlir::dataflow::RunLivenessAnalysis::getLiveness(), getMaybeConstantValue(), mlir::dataflow::maybeReplaceWithConstant(), replaceWithConstant(), and mlir::dataflow::staticallyNonNegative().

◆ propagateIfChanged()

void DataFlowSolver::propagateIfChanged	(	AnalysisState *	state,
		ChangeResult	changed
	)

Propagate an update to an analysis state if it changed by pushing dependent work items to the back of the queue.

This should only be used when DataFlowSolver is running. Otherwise, the solver won't process the work items.

Definition at line 141 of file DataFlowFramework.cpp.

Referenced by mlir::dataflow::IntegerValueRangeLattice::onUpdate().

◆ unionLatticeAnchors()

template<typename StateT , typename AnchorT >

void mlir::DataFlowSolver::unionLatticeAnchors	(	AnchorT	anchor,
		AnchorT	other
	)

Union input anchors under the given state.

Definition at line 760 of file DataFlowFramework.h.

Referenced by mlir::DataFlowAnalysis::unionLatticeAnchors().

Friends And Related Function Documentation

◆ DataFlowAnalysis

friend class DataFlowAnalysis

friend

Allow the base child analysis class to access the internals of the solver.

Definition at line 489 of file DataFlowFramework.h.

The documentation for this class was generated from the following files:

include/mlir/Analysis/DataFlowFramework.h
lib/Analysis/DataFlowFramework.cpp

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ WorkItem

Constructor & Destructor Documentation

◆ DataFlowSolver()

Member Function Documentation

◆ enqueue()

◆ eraseAllStates()

◆ eraseState()

◆ getConfig()

◆ getLatticeAnchor()

◆ getLeaderAnchorOrSelf()

◆ getOrCreateState()

◆ getProgramPointAfter() [1/2]

◆ getProgramPointAfter() [2/2]

◆ getProgramPointBefore() [1/2]

◆ getProgramPointBefore() [2/2]

◆ initializeAndRun()

◆ isEquivalent()

◆ load()

◆ lookupState()

◆ propagateIfChanged()

◆ unionLatticeAnchors()

Friends And Related Function Documentation

◆ DataFlowAnalysis