Base class for dense backward dataflow analyses. More...

#include "mlir/Analysis/DataFlow/DenseAnalysis.h"

Inheritance diagram for mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis:

Public Member Functions
	AbstractDenseBackwardDataFlowAnalysis (DataFlowSolver &solver, SymbolTableCollection &symbolTable)
	Construct the analysis in the given solver.
LogicalResult	initialize (Operation *top) override
	Initialize the analysis by visiting every program point whose execution may modify the program state; that is, every operation and block.
virtual void	initializeEquivalentLatticeAnchor (Operation *top) override
	Initialize lattice anchor equivalence class from the provided top-level operation.
LogicalResult	visit (ProgramPoint *point) override
	Visit a program point that modifies the state of the program.
Public Member Functions inherited from mlir::DataFlowAnalysis
virtual	~DataFlowAnalysis ()
	DataFlowAnalysis (DataFlowSolver &solver)
	Create an analysis with a reference to the parent solver.

Protected Member Functions
virtual LogicalResult	visitOperationImpl (Operation op, const AbstractDenseLattice &after, AbstractDenseLattice before)=0
	Propagate the dense lattice after the execution of an operation to the lattice before its execution.
virtual AbstractDenseLattice *	getLattice (LatticeAnchor anchor)=0
	Get the dense lattice before the execution of the lattice anchor.
virtual const AbstractDenseLattice *	getLatticeFor (ProgramPoint *dependent, LatticeAnchor anchor)=0
	Get the dense lattice on the given lattice anchor and add dependent as its dependency.
virtual void	setToExitState (AbstractDenseLattice *lattice)=0
	Set the dense lattice before at the control flow exit point and propagate the update if it changed.
void	meet (AbstractDenseLattice *lhs, const AbstractDenseLattice &rhs)
	Meet a lattice with another lattice and propagate an update if it changed.
virtual LogicalResult	processOperation (Operation *op)
	Visit an operation.
virtual void	buildOperationEquivalentLatticeAnchor (Operation *op)
	Visit an operation.
virtual void	visitBlockTransfer (Block block, ProgramPoint point, Block successor, const AbstractDenseLattice &after, AbstractDenseLattice before)
	Visit a block and propagate the dense lattice backward along the control flow edge from successor to block.
virtual void	visitRegionBranchControlFlowTransfer (RegionBranchOpInterface branch, RegionBranchPoint regionFrom, RegionSuccessor regionTo, const AbstractDenseLattice &after, AbstractDenseLattice *before)
	Propagate the dense lattice backwards along the control flow edge from regionFrom to regionTo regions of the branch operation.
virtual void	visitCallControlFlowTransfer (CallOpInterface call, CallControlFlowAction action, const AbstractDenseLattice &after, AbstractDenseLattice *before)
	Propagate the dense lattice backwards along the call control flow edge, which can be either entering or exiting the callee.
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.
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.

Detailed Description

Base class for dense backward dataflow analyses.

Such analyses attach a lattice to program point and implement a transfer function from the lattice after the operation to the lattice before it, thus propagating backward.

Visit a program point in dense backward data-flow analysis will invoke the transfer function of the operation following the program point iterator. Visit a program point at the end of block will visit the block itself.

Definition at line 357 of file DenseAnalysis.h.

Constructor & Destructor Documentation

◆ AbstractDenseBackwardDataFlowAnalysis()

mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::AbstractDenseBackwardDataFlowAnalysis	(	DataFlowSolver &	solver,
		SymbolTableCollection &	symbolTable )

inline

Construct the analysis in the given solver.

Takes a symbol table collection that is used to cache symbol resolution in interprocedural part of the analysis. The symbol table need not be prefilled.

Definition at line 362 of file DenseAnalysis.h.

References mlir::DataFlowAnalysis::DataFlowAnalysis(), and mlir::DataFlowAnalysis::DataFlowSolver.

Member Function Documentation

◆ buildOperationEquivalentLatticeAnchor()

virtual void mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::buildOperationEquivalentLatticeAnchor ( Operation * op )

inlineprotectedvirtual

Visit an operation.

If this analysis can confirm that lattice content of lattice anchors around operation are necessarily identical, join them into the same equivalent class.

Definition at line 424 of file DenseAnalysis.h.

Referenced by initializeEquivalentLatticeAnchor().

◆ getLattice()

virtual AbstractDenseLattice * mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::getLattice ( LatticeAnchor anchor )

protectedpure virtual

Get the dense lattice before the execution of the lattice anchor.

That is, before the execution of the given operation or after the execution of the block.

Implemented in mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >.

Referenced by processOperation().

◆ getLatticeFor()

virtual const AbstractDenseLattice * mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::getLatticeFor	(	ProgramPoint *	dependent,
		LatticeAnchor	anchor )

protectedpure virtual

Get the dense lattice on the given lattice anchor and add dependent as its dependency.

That is, every time the lattice after anchor is updated, the dependent program point must be visited, and the newly triggered visit might update the lattice before dependent.

Implemented in mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >.

Referenced by processOperation().

◆ initialize()

LogicalResult AbstractDenseBackwardDataFlowAnalysis::initialize ( Operation * top )

overridevirtual

Initialize the analysis by visiting every program point whose execution may modify the program state; that is, every operation and block.

Implements mlir::DataFlowAnalysis.

Definition at line 377 of file DenseAnalysis.cpp.

References mlir::Block::getOperations(), mlir::Operation::getRegions(), initialize(), processOperation(), and success().

Referenced by initialize().

◆ initializeEquivalentLatticeAnchor()

void AbstractDenseBackwardDataFlowAnalysis::initializeEquivalentLatticeAnchor ( Operation * top )

overridevirtual

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 from mlir::DataFlowAnalysis.

Definition at line 359 of file DenseAnalysis.cpp.

References buildOperationEquivalentLatticeAnchor(), and mlir::Operation::walk().

◆ meet()

void mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::meet	(	AbstractDenseLattice *	lhs,
		const AbstractDenseLattice &	rhs )

inlineprotected

Meet a lattice with another lattice and propagate an update if it changed.

Definition at line 412 of file DenseAnalysis.h.

References lhs, mlir::DataFlowAnalysis::propagateIfChanged(), and rhs.

Referenced by visitBlockTransfer(), visitCallControlFlowTransfer(), and visitRegionBranchControlFlowTransfer().

◆ processOperation()

LogicalResult AbstractDenseBackwardDataFlowAnalysis::processOperation ( Operation * op )

protectedvirtual

Visit an operation.

Dispatches to specialized methods for call or region control-flow operations. Otherwise, this function invokes the operation transfer function.

Definition at line 489 of file DenseAnalysis.cpp.

References mlir::Operation::getBlock(), getLattice(), getLatticeFor(), mlir::DataFlowAnalysis::getOrCreateFor(), mlir::DataFlowAnalysis::getProgramPointAfter(), mlir::DataFlowAnalysis::getProgramPointBefore(), mlir::RegionBranchPoint::parent(), success(), and visitOperationImpl().

Referenced by initialize(), and visit().

◆ setToExitState()

virtual void mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::setToExitState ( AbstractDenseLattice * lattice )

protectedpure virtual

Set the dense lattice before at the control flow exit point and propagate the update if it changed.

Implemented in mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >.

Referenced by visitCallControlFlowTransfer().

◆ visit()

LogicalResult AbstractDenseBackwardDataFlowAnalysis::visit ( ProgramPoint * point )

overridevirtual

Visit a program point that modifies the state of the program.

The state is propagated along control flow directions for branch-, region- and call-based control flow using the respective interfaces. For other operations, the state is propagated using the transfer function (visitOperation).

Note: the transfer function is currently not invoked before operations with region or call interface, but is invoked before block terminators.

Implements mlir::DataFlowAnalysis.

Definition at line 408 of file DenseAnalysis.cpp.

References mlir::ProgramPoint::getBlock(), mlir::ProgramPoint::getNextOp(), mlir::ProgramPoint::isBlockEnd(), processOperation(), and success().

◆ visitBlockTransfer()

virtual void mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::visitBlockTransfer	(	Block *	block,
		ProgramPoint *	point,
		Block *	successor,
		const AbstractDenseLattice &	after,
		AbstractDenseLattice *	before )

inlineprotectedvirtual

Visit a block and propagate the dense lattice backward along the control flow edge from successor to block.

point corresponds to the program point after block. The default implementation merges in the state from the successor's first operation or the block itself when empty.

Reimplemented in mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >.

Definition at line 430 of file DenseAnalysis.h.

References meet().

Referenced by mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >::visitBlockTransfer().

◆ visitCallControlFlowTransfer()

virtual void mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::visitCallControlFlowTransfer	(	CallOpInterface	call,
		CallControlFlowAction	action,
		const AbstractDenseLattice &	after,
		AbstractDenseLattice *	before )

inlineprotectedvirtual

Propagate the dense lattice backwards along the call control flow edge, which can be either entering or exiting the callee.

Default implementation for enter and exit callee action just meets the states, meaning that operations implementing CallOpInterface don't have any effect on the lattice that isn't already expressed by the interface itself. Default implementation for external callee action additional sets the result to the exit (fixpoint) state.

Reimplemented in mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >.

Definition at line 458 of file DenseAnalysis.h.

References mlir::dataflow::ExternalCallee, meet(), and setToExitState().

Referenced by mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >::visitCallControlFlowTransfer().

◆ visitOperationImpl()

virtual LogicalResult mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::visitOperationImpl	(	Operation *	op,
		const AbstractDenseLattice &	after,
		AbstractDenseLattice *	before )

protectedpure virtual

Propagate the dense lattice after the execution of an operation to the lattice before its execution.

Implemented in mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >.

Referenced by processOperation().

◆ visitRegionBranchControlFlowTransfer()

virtual void mlir::dataflow::AbstractDenseBackwardDataFlowAnalysis::visitRegionBranchControlFlowTransfer	(	RegionBranchOpInterface	branch,
		RegionBranchPoint	regionFrom,
		RegionSuccessor	regionTo,
		const AbstractDenseLattice &	after,
		AbstractDenseLattice *	before )

inlineprotectedvirtual

Propagate the dense lattice backwards along the control flow edge from regionFrom to regionTo regions of the branch operation.

nullopt values correspond to control flow branches originating at or targeting the branch operation itself. Default implementation just meets the states, meaning that operations implementing RegionBranchOpInterface don't have any effect on the lattice that isn't already expressed by the interface itself.

Reimplemented in mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >.

Definition at line 444 of file DenseAnalysis.h.

References meet().

Referenced by mlir::dataflow::DenseBackwardDataFlowAnalysis< LatticeT >::visitRegionBranchControlFlowTransfer().

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

include/mlir/Analysis/DataFlow/DenseAnalysis.h
lib/Analysis/DataFlow/DenseAnalysis.cpp

Public Member Functions

Protected Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ AbstractDenseBackwardDataFlowAnalysis()

Member Function Documentation

◆ buildOperationEquivalentLatticeAnchor()

◆ getLattice()

◆ getLatticeFor()

◆ initialize()

◆ initializeEquivalentLatticeAnchor()

◆ meet()

◆ processOperation()

◆ setToExitState()

◆ visit()

◆ visitBlockTransfer()

◆ visitCallControlFlowTransfer()

◆ visitOperationImpl()

◆ visitRegionBranchControlFlowTransfer()