LLVM: llvm::AbstractDependenceGraphBuilder< GraphType > Class Template Reference (original) (raw)

This abstract builder class defines a set of high-level steps for creating DDG-like graphs. More...

#include "[llvm/Analysis/DependenceGraphBuilder.h](DependenceGraphBuilder%5F8h%5Fsource.html)"

Public Member Functions
	AbstractDependenceGraphBuilder (GraphType &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.

Protected Types
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
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
GraphType &	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.

template
class llvm::AbstractDependenceGraphBuilder< GraphType >

This abstract builder class defines a set of high-level steps for creating DDG-like graphs.

The client code is expected to inherit from this class and define concrete implementation for each of the pure virtual functions used in the high-level algorithm.

Definition at line 32 of file DependenceGraphBuilder.h.

◆ BasicBlockListType

template

◆ ClassesType

template

◆ InstToNodeMap

template

◆ InstToOrdinalMap

template

◆ NodeListType

template

◆ NodeToOrdinalMap

template

◆ ~AbstractDependenceGraphBuilder()

template

◆ areNodesMergeable()

template

◆ computeInstructionOrdinals()

template<class G>

void AbstractDependenceGraphBuilder::computeInstructionOrdinals	(	)

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

These ordinals are used to compute node ordinals which are in turn used to order nodes that are part of a cycle. Instruction ordinals are assigned based on lexical program order.

Definition at line 42 of file DependenceGraphBuilder.cpp.

References BBList, I, and InstOrdinalMap.

Referenced by populate().

◆ createAndConnectRootNode()

template<class G>

void AbstractDependenceGraphBuilder::createAndConnectRootNode	(	)

◆ createDefUseEdge()

template

◆ createDefUseEdges()

template<class G>

void AbstractDependenceGraphBuilder::createDefUseEdges	(	)

◆ createFineGrainedNode()

template

◆ createFineGrainedNodes()

template<class G>

void AbstractDependenceGraphBuilder::createFineGrainedNodes	(	)

◆ createMemoryDependencyEdges()

template<class G>

void AbstractDependenceGraphBuilder::createMemoryDependencyEdges	(	)

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

Definition at line 276 of file DependenceGraphBuilder.cpp.

References createMemoryEdge(), D(), DI, llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::Dependence::DVEntry::EQ, Graph, llvm::Dependence::DVEntry::GT, I, and llvm::Dependence::DVEntry::LT.

Referenced by populate().

◆ createMemoryEdge()

template

◆ createPiBlock()

template

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

Implemented in llvm::DDGBuilder.

◆ createPiBlocks()

template<class G>

void AbstractDependenceGraphBuilder::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.

The purpose of this abstraction is to isolate sets of program elements that need to stay together during codegen and turn the dependence graph into an acyclic graph.

Definition at line 91 of file DependenceGraphBuilder.cpp.

Referenced by populate().

◆ createRootedEdge()

template

◆ createRootNode()

template

◆ destroyEdge()

template

◆ destroyNode()

template

◆ getNodesInPiBlock()

template

◆ getOrdinal() [1/2]

template

◆ getOrdinal() [2/2]

template

◆ mergeNodes()

template

Append the content of node B into node A and remove B and the edge between A and B from the graph.

Implemented in llvm::DDGBuilder.

References A(), and B().

Referenced by simplify().

◆ populate()

template

The main entry to the graph construction algorithm.

It starts by creating nodes in increasing order of granularity and then adds def-use and memory edges. As one of the final stages, it also creates pi-block nodes to facilitate codegen in transformations that use dependence graphs.

The algorithmic complexity of this implementation is O(V^2 * I^2), where V is the number of vertecies (nodes) and I is the number of instructions in each node. The total number of instructions, N, is equal to V * I, therefore the worst-case time complexity is O(N^2). The average time complexity is O((N^2)/2).

Definition at line 60 of file DependenceGraphBuilder.h.

References computeInstructionOrdinals(), createAndConnectRootNode(), createDefUseEdges(), createFineGrainedNodes(), createMemoryDependencyEdges(), createPiBlocks(), simplify, and sortNodesTopologically().