Concrete implementation of a pure data dependence graph builder. More...

#include "llvm/Analysis/DDG.h"

Inheritance diagram for llvm::DDGBuilder:

Public Member Functions
	DDGBuilder (DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs)

DDGNode &	createRootNode () final
	Create the root node of the graph.

DDGNode &	createFineGrainedNode (Instruction &I) final
	Create an atomic node in the graph given a single instruction.

DDGNode &	createPiBlock (const NodeListType &L) final
	Create a pi-block node in the graph representing a group of nodes in an SCC of the graph.

DDGEdge &	createDefUseEdge (DDGNode &Src, DDGNode &Tgt) final

DDGEdge &	createMemoryEdge (DDGNode &Src, DDGNode &Tgt) final

DDGEdge &	createRootedEdge (DDGNode &Src, DDGNode &Tgt) final

const NodeListType &	getNodesInPiBlock (const DDGNode &N) final

bool	areNodesMergeable (const DDGNode &Src, const DDGNode &Tgt) const final
	Return true if the two nodes \pSrc and \pTgt are both simple nodes and the consecutive instructions after merging belong to the same basic block.

void	mergeNodes (DDGNode &Src, DDGNode &Tgt) final

bool	shouldSimplify () const final
	Return true if graph simplification step is requested, and false otherwise.

bool	shouldCreatePiBlocks () const final
	Return true if creation of pi-blocks are supported and desired, and false otherwise.

Public Member Functions inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
	AbstractDependenceGraphBuilder (DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs)

virtual	~AbstractDependenceGraphBuilder ()=default

void	populate ()
	The main entry to the graph construction algorithm.

void	computeInstructionOrdinals ()
	Compute ordinal numbers for each instruction and store them in a map for future look up.

void	createFineGrainedNodes ()
	Create fine grained nodes.

void	createDefUseEdges ()
	Analyze the def-use chains and create edges from the nodes containing definitions to the nodes containing the uses.

void	createMemoryDependencyEdges ()
	Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create edges between them.

void	createAndConnectRootNode ()
	Create a root node and add edges such that each node in the graph is reachable from the root.

void	createPiBlocks ()
	Apply graph abstraction to groups of nodes that belong to a strongly connected component of the graph to create larger compound nodes called pi-blocks.

void	simplify ()
	Go through all the nodes in the graph and collapse any two nodes 'a' and 'b' if all of the following are true:

void	sortNodesTopologically ()
	Topologically sort the graph nodes.

Additional Inherited Members
Public Types inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
using	ClassesType = EquivalenceClasses< BasicBlock * >

using	NodeListType = SmallVector< NodeType *, 4 >

Protected Types inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
using	BasicBlockListType = SmallVectorImpl< BasicBlock * >

using	InstToNodeMap = DenseMap< Instruction , NodeType >
	Map types to map instructions to nodes used when populating the graph.

using	InstToOrdinalMap = DenseMap< Instruction *, size_t >
	Map Types to map instruction/nodes to an ordinal number.

using	NodeToOrdinalMap = DenseMap< NodeType *, size_t >

Protected Member Functions inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
virtual NodeType &	createRootNode ()=0
	Create the root node of the graph.

virtual NodeType &	createFineGrainedNode (Instruction &I)=0
	Create an atomic node in the graph given a single instruction.

virtual NodeType &	createPiBlock (const NodeListType &L)=0
	Create a pi-block node in the graph representing a group of nodes in an SCC of the graph.

virtual EdgeType &	createDefUseEdge (NodeType &Src, NodeType &Tgt)=0
	Create a def-use edge going from `Src` to `Tgt`.

virtual EdgeType &	createMemoryEdge (NodeType &Src, NodeType &Tgt)=0
	Create a memory dependence edge going from `Src` to `Tgt`.

virtual EdgeType &	createRootedEdge (NodeType &Src, NodeType &Tgt)=0
	Create a rooted edge going from `Src` to `Tgt` .

virtual const NodeListType &	getNodesInPiBlock (const NodeType &N)=0
	Given a pi-block node, return a vector of all the nodes contained within it.

virtual void	destroyEdge (EdgeType &E)
	Deallocate memory of edge `E`.

virtual void	destroyNode (NodeType &N)
	Deallocate memory of node `N`.

virtual bool	shouldCreatePiBlocks () const
	Return true if creation of pi-blocks are supported and desired, and false otherwise.

virtual bool	shouldSimplify () const
	Return true if graph simplification step is requested, and false otherwise.

virtual bool	areNodesMergeable (const NodeType &A, const NodeType &B) const=0
	Return true if it's safe to merge the two nodes.

virtual void	mergeNodes (NodeType &A, NodeType &B)=0
	Append the content of node `B` into node `A` and remove `B` and the edge between `A` and `B` from the graph.

size_t	getOrdinal (Instruction &I)
	Given an instruction `I` return its associated ordinal number.

size_t	getOrdinal (NodeType &N)
	Given a node `N` return its associated ordinal number.

Protected Attributes inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
DataDependenceGraph &	Graph
	Reference to the graph that gets built by a concrete implementation of this builder.

DependenceInfo &	DI
	Dependence information used to create memory dependence edges in the graph.

const BasicBlockListType &	BBList
	The list of basic blocks to consider when building the graph.

InstToNodeMap	IMap
	A mapping from instructions to the corresponding nodes in the graph.

InstToOrdinalMap	InstOrdinalMap
	A mapping from each instruction to an ordinal number.

NodeToOrdinalMap	NodeOrdinalMap
	A mapping from nodes to an ordinal number.

Detailed Description

Concrete implementation of a pure data dependence graph builder.

This class provides custom implementation for the pure-virtual functions used in the generic dependence graph build algorithm.

For information about time complexity of the build algorithm see the comments near the declaration of AbstractDependenceGraphBuilder.

Definition at line 346 of file DDG.h.

Constructor & Destructor Documentation

◆ DDGBuilder()

llvm::DDGBuilder::DDGBuilder	(	DataDependenceGraph &	G,
		DependenceInfo &	D,
		const BasicBlockListType &	BBs
	)

inline

Definition at line 348 of file DDG.h.

Member Function Documentation

◆ areNodesMergeable()

bool DDGBuilder::areNodesMergeable	(	const DDGNode &	Src,
		const DDGNode &	Tgt
	)		const

final

Return true if the two nodes \pSrc and \pTgt are both simple nodes and the consecutive instructions after merging belong to the same basic block.

Definition at line 265 of file DDG.cpp.

◆ createDefUseEdge()

DDGEdge & llvm::DDGBuilder::createDefUseEdge	(	DDGNode &	Src,
		DDGNode &	Tgt
	)

inlinefinal

Definition at line 369 of file DDG.h.

References assert(), llvm::DirectedGraph< NodeType, EdgeType >::connect(), E, llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph, and llvm::DDGEdge::RegisterDefUse.

◆ createFineGrainedNode()

DDGNode & llvm::DDGBuilder::createFineGrainedNode ( Instruction & I )

inlinefinalvirtual

Create an atomic node in the graph given a single instruction.

Implements llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.

Definition at line 357 of file DDG.h.

References llvm::DataDependenceGraph::addNode(), assert(), llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph, and I.

◆ createMemoryEdge()

DDGEdge & llvm::DDGBuilder::createMemoryEdge	(	DDGNode &	Src,
		DDGNode &	Tgt
	)

inlinefinal

Definition at line 375 of file DDG.h.

References assert(), llvm::DirectedGraph< NodeType, EdgeType >::connect(), E, llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph, and llvm::DDGEdge::MemoryDependence.

◆ createPiBlock()

DDGNode & llvm::DDGBuilder::createPiBlock ( const NodeListType & L )

inlinefinalvirtual

Create a pi-block node in the graph representing a group of nodes in an SCC of the graph.

Implements llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.

Definition at line 363 of file DDG.h.

References llvm::DataDependenceGraph::addNode(), assert(), and llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph.

◆ createRootedEdge()

DDGEdge & llvm::DDGBuilder::createRootedEdge	(	DDGNode &	Src,
		DDGNode &	Tgt
	)

inlinefinal

Definition at line 381 of file DDG.h.

References assert(), llvm::DirectedGraph< NodeType, EdgeType >::connect(), E, llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph, and llvm::DDGEdge::Rooted.

◆ createRootNode()

DDGNode & llvm::DDGBuilder::createRootNode ( )

inlinefinalvirtual

Create the root node of the graph.

Implements llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.

Definition at line 351 of file DDG.h.

References llvm::DataDependenceGraph::addNode(), assert(), and llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph.

◆ getNodesInPiBlock()

const NodeListType & llvm::DDGBuilder::getNodesInPiBlock ( const DDGNode & N )

inlinefinal

Definition at line 389 of file DDG.h.

References assert(), and N.

◆ mergeNodes()

void DDGBuilder::mergeNodes	(	DDGNode &	Src,
		DDGNode &	Tgt
	)

final

Definition at line 278 of file DDG.cpp.

References A, assert(), B, llvm::DirectedGraph< NodeType, EdgeType >::connect(), llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::destroyEdge(), llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::destroyNode(), llvm::DGEdge< NodeType, EdgeType >::getTargetNode(), llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph, and llvm::DirectedGraph< NodeType, EdgeType >::removeNode().

◆ shouldCreatePiBlocks()

bool DDGBuilder::shouldCreatePiBlocks ( ) const

finalvirtual

Return true if creation of pi-blocks are supported and desired, and false otherwise.

Reimplemented from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.

Definition at line 300 of file DDG.cpp.

References CreatePiBlocks.

◆ shouldSimplify()

bool DDGBuilder::shouldSimplify ( ) const

finalvirtual

Return true if graph simplification step is requested, and false otherwise.

Reimplemented from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.

Definition at line 298 of file DDG.cpp.

References SimplifyDDG.

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

include/llvm/Analysis/DDG.h
lib/Analysis/DDG.cpp

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ DDGBuilder()

Member Function Documentation

◆ areNodesMergeable()

◆ createDefUseEdge()

◆ createFineGrainedNode()

◆ createMemoryEdge()

◆ createPiBlock()

◆ createRootedEdge()

◆ createRootNode()

◆ getNodesInPiBlock()

◆ mergeNodes()

◆ shouldCreatePiBlocks()

◆ shouldSimplify()