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

#include "llvm/Analysis/DependenceGraphBuilder.h"

Inheritance diagram for llvm::AbstractDependenceGraphBuilder< GraphType >:

Public Types
using	ClassesType = EquivalenceClasses< BasicBlock * >

using	NodeListType = SmallVector< NodeType *, 4 >

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.

Detailed Description

template<class GraphType>
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 31 of file DependenceGraphBuilder.h.

Member Typedef Documentation

◆ BasicBlockListType

template<class GraphType >

using llvm::AbstractDependenceGraphBuilder< GraphType >::BasicBlockListType = SmallVectorImpl<BasicBlock *>

protected

Definition at line 33 of file DependenceGraphBuilder.h.

◆ ClassesType

template<class GraphType >

using llvm::AbstractDependenceGraphBuilder< GraphType >::ClassesType = EquivalenceClasses<BasicBlock *>

Definition at line 40 of file DependenceGraphBuilder.h.

◆ InstToNodeMap

template<class GraphType >

using llvm::AbstractDependenceGraphBuilder< GraphType >::InstToNodeMap = DenseMap<Instruction *, NodeType *>

protected

Map types to map instructions to nodes used when populating the graph.

Definition at line 171 of file DependenceGraphBuilder.h.

◆ InstToOrdinalMap

template<class GraphType >

using llvm::AbstractDependenceGraphBuilder< GraphType >::InstToOrdinalMap = DenseMap<Instruction *, size_t>

protected

Map Types to map instruction/nodes to an ordinal number.

Definition at line 174 of file DependenceGraphBuilder.h.

◆ NodeListType

template<class GraphType >

using llvm::AbstractDependenceGraphBuilder< GraphType >::NodeListType = SmallVector<NodeType *, 4>

Definition at line 41 of file DependenceGraphBuilder.h.

◆ NodeToOrdinalMap

template<class GraphType >

using llvm::AbstractDependenceGraphBuilder< GraphType >::NodeToOrdinalMap = DenseMap<NodeType *, size_t>

protected

Definition at line 175 of file DependenceGraphBuilder.h.

Constructor & Destructor Documentation

◆ AbstractDependenceGraphBuilder()

template<class GraphType >

llvm::AbstractDependenceGraphBuilder< GraphType >::AbstractDependenceGraphBuilder	(	GraphType &	G,
		DependenceInfo &	D,
		const BasicBlockListType &	BBs
	)

inline

Definition at line 43 of file DependenceGraphBuilder.h.

◆ ~AbstractDependenceGraphBuilder()

template<class GraphType >

virtual llvm::AbstractDependenceGraphBuilder< GraphType >::~AbstractDependenceGraphBuilder ( )

virtualdefault

Member Function Documentation

◆ areNodesMergeable()

template<class GraphType >

virtual bool llvm::AbstractDependenceGraphBuilder< GraphType >::areNodesMergeable	(	const NodeType &	A,
		const NodeType &	B
	)		const

protectedpure virtual

Return true if it's safe to merge the two nodes.

◆ 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 I.

Referenced by llvm::AbstractDependenceGraphBuilder< GraphType >::populate().

◆ createAndConnectRootNode()

template<class G >

void AbstractDependenceGraphBuilder::createAndConnectRootNode

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

Definition at line 64 of file DependenceGraphBuilder.cpp.

Referenced by llvm::AbstractDependenceGraphBuilder< GraphType >::populate().

◆ createDefUseEdge()

template<class GraphType >

virtual EdgeType & llvm::AbstractDependenceGraphBuilder< GraphType >::createDefUseEdge	(	NodeType &	Src,
		NodeType &	Tgt
	)

protectedpure virtual

Create a def-use edge going from Src to Tgt.

◆ createDefUseEdges()

template<class G >

void AbstractDependenceGraphBuilder::createDefUseEdges

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

Definition at line 228 of file DependenceGraphBuilder.cpp.

References llvm::dbgs(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, and N.

Referenced by llvm::AbstractDependenceGraphBuilder< GraphType >::populate().

◆ createFineGrainedNode()

template<class GraphType >

virtual NodeType & llvm::AbstractDependenceGraphBuilder< GraphType >::createFineGrainedNode ( Instruction & I )

protectedpure virtual

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

Implemented in llvm::DDGBuilder.

◆ createFineGrainedNodes()

template<class G >

void AbstractDependenceGraphBuilder::createFineGrainedNodes

Create fine grained nodes.

These are typically atomic nodes that consist of a single instruction.

Definition at line 51 of file DependenceGraphBuilder.cpp.

References assert(), and I.

Referenced by llvm::AbstractDependenceGraphBuilder< GraphType >::populate().

◆ 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 278 of file DependenceGraphBuilder.cpp.

References D, llvm::SmallVectorBase< Size_T >::empty(), llvm::Dependence::DVEntry::EQ, llvm::Dependence::DVEntry::GT, I, and llvm::Dependence::DVEntry::LT.

Referenced by llvm::AbstractDependenceGraphBuilder< GraphType >::populate().

◆ createMemoryEdge()

template<class GraphType >

virtual EdgeType & llvm::AbstractDependenceGraphBuilder< GraphType >::createMemoryEdge	(	NodeType &	Src,
		NodeType &	Tgt
	)

protectedpure virtual

Create a memory dependence edge going from Src to Tgt.

◆ createPiBlock()

template<class GraphType >

virtual NodeType & llvm::AbstractDependenceGraphBuilder< GraphType >::createPiBlock ( const NodeListType & L )

protectedpure virtual

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.

References llvm::dbgs(), and LLVM_DEBUG.

Referenced by llvm::AbstractDependenceGraphBuilder< GraphType >::populate().

◆ createRootedEdge()

template<class GraphType >

virtual EdgeType & llvm::AbstractDependenceGraphBuilder< GraphType >::createRootedEdge	(	NodeType &	Src,
		NodeType &	Tgt
	)

protectedpure virtual

Create a rooted edge going from Src to Tgt .

◆ createRootNode()

template<class GraphType >

virtual NodeType & llvm::AbstractDependenceGraphBuilder< GraphType >::createRootNode ( )

protectedpure virtual

Create the root node of the graph.

Implemented in llvm::DDGBuilder.

◆ destroyEdge()

template<class GraphType >

virtual void llvm::AbstractDependenceGraphBuilder< GraphType >::destroyEdge ( EdgeType & E )

inlineprotectedvirtual

Deallocate memory of edge E.

Definition at line 136 of file DependenceGraphBuilder.h.

References E.

◆ destroyNode()

template<class GraphType >

virtual void llvm::AbstractDependenceGraphBuilder< GraphType >::destroyNode ( NodeType & N )

inlineprotectedvirtual

Deallocate memory of node N.

Definition at line 139 of file DependenceGraphBuilder.h.

References N.

◆ getNodesInPiBlock()

template<class GraphType >

virtual const NodeListType & llvm::AbstractDependenceGraphBuilder< GraphType >::getNodesInPiBlock ( const NodeType & N )

protectedpure virtual

Given a pi-block node, return a vector of all the nodes contained within it.

◆ getOrdinal() [1/2]

template<class GraphType >

size_t llvm::AbstractDependenceGraphBuilder< GraphType >::getOrdinal ( Instruction & I )

inlineprotected

Given an instruction I return its associated ordinal number.

Definition at line 158 of file DependenceGraphBuilder.h.

References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), I, and llvm::AbstractDependenceGraphBuilder< GraphType >::InstOrdinalMap.

◆ getOrdinal() [2/2]

template<class GraphType >

size_t llvm::AbstractDependenceGraphBuilder< GraphType >::getOrdinal ( NodeType & N )

inlineprotected

Given a node N return its associated ordinal number.

Definition at line 165 of file DependenceGraphBuilder.h.

References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), N, and llvm::AbstractDependenceGraphBuilder< GraphType >::NodeOrdinalMap.

◆ mergeNodes()

template<class GraphType >

virtual void llvm::AbstractDependenceGraphBuilder< GraphType >::mergeNodes	(	NodeType &	A,
		NodeType &	B
	)

protectedpure virtual

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

◆ populate()

template<class GraphType >

void llvm::AbstractDependenceGraphBuilder< GraphType >::populate ( )

inline

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 59 of file DependenceGraphBuilder.h.

◆ shouldCreatePiBlocks()

template<class GraphType >

virtual bool llvm::AbstractDependenceGraphBuilder< GraphType >::shouldCreatePiBlocks ( ) const

inlineprotectedvirtual

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

Reimplemented in llvm::DDGBuilder.

Definition at line 143 of file DependenceGraphBuilder.h.

◆ shouldSimplify()

template<class GraphType >

virtual bool llvm::AbstractDependenceGraphBuilder< GraphType >::shouldSimplify ( ) const

inlineprotectedvirtual

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

Reimplemented in llvm::DDGBuilder.

Definition at line 147 of file DependenceGraphBuilder.h.

◆ simplify()

template<class G >

void AbstractDependenceGraphBuilder::simplify

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

the only edge from 'a' is a def-use edge to 'b' and
the only edge to 'b' is a def-use edge from 'a' and
there is no cyclic edge from 'b' to 'a' and
all instructions in 'a' and 'b' belong to the same basic block and
both 'a' and 'b' are simple (single or multi instruction) nodes.

Definition at line 378 of file DependenceGraphBuilder.cpp.

References assert(), llvm::SmallPtrSetImpl< PtrType >::begin(), llvm::dbgs(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::SmallPtrSetImpl< PtrType >::end(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, N, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::size(), and llvm::SmallPtrSetImplBase::size().

Referenced by llvm::AbstractDependenceGraphBuilder< GraphType >::populate().

◆ sortNodesTopologically()

template<class G >

void AbstractDependenceGraphBuilder::sortNodesTopologically

Topologically sort the graph nodes.

Definition at line 482 of file DependenceGraphBuilder.cpp.

References llvm::append_range(), assert(), N, llvm::post_order(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::reverse().

Referenced by llvm::AbstractDependenceGraphBuilder< GraphType >::populate().

Member Data Documentation

◆ BBList

template<class GraphType >

const BasicBlockListType& llvm::AbstractDependenceGraphBuilder< GraphType >::BBList

protected

The list of basic blocks to consider when building the graph.

Definition at line 186 of file DependenceGraphBuilder.h.

◆ DI

template<class GraphType >

DependenceInfo& llvm::AbstractDependenceGraphBuilder< GraphType >::DI

protected

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

Definition at line 183 of file DependenceGraphBuilder.h.

◆ Graph

template<class GraphType >

GraphType& llvm::AbstractDependenceGraphBuilder< GraphType >::Graph

protected

Reference to the graph that gets built by a concrete implementation of this builder.

Definition at line 179 of file DependenceGraphBuilder.h.

◆ IMap

template<class GraphType >

InstToNodeMap llvm::AbstractDependenceGraphBuilder< GraphType >::IMap

protected

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

Definition at line 189 of file DependenceGraphBuilder.h.

◆ InstOrdinalMap

template<class GraphType >

InstToOrdinalMap llvm::AbstractDependenceGraphBuilder< GraphType >::InstOrdinalMap

protected

A mapping from each instruction to an ordinal number.

This map is used to populate the NodeOrdinalMap.

Definition at line 193 of file DependenceGraphBuilder.h.

Referenced by llvm::AbstractDependenceGraphBuilder< GraphType >::getOrdinal().

◆ NodeOrdinalMap

template<class GraphType >

NodeToOrdinalMap llvm::AbstractDependenceGraphBuilder< GraphType >::NodeOrdinalMap

protected

A mapping from nodes to an ordinal number.

This map is used to sort nodes in a pi-block based on program order.

Definition at line 197 of file DependenceGraphBuilder.h.

Referenced by llvm::AbstractDependenceGraphBuilder< GraphType >::getOrdinal().

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

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

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ BasicBlockListType

◆ ClassesType

◆ InstToNodeMap

◆ InstToOrdinalMap

◆ NodeListType

◆ NodeToOrdinalMap

Constructor & Destructor Documentation

◆ AbstractDependenceGraphBuilder()

◆ ~AbstractDependenceGraphBuilder()

Member Function Documentation

◆ areNodesMergeable()

◆ computeInstructionOrdinals()

◆ createAndConnectRootNode()

◆ createDefUseEdge()

◆ createDefUseEdges()

◆ createFineGrainedNode()

◆ createFineGrainedNodes()

◆ createMemoryDependencyEdges()

◆ createMemoryEdge()

◆ createPiBlock()

◆ createPiBlocks()

◆ createRootedEdge()

◆ createRootNode()

◆ destroyEdge()

◆ destroyNode()

◆ getNodesInPiBlock()

◆ getOrdinal() [1/2]

◆ getOrdinal() [2/2]

◆ mergeNodes()

◆ populate()

◆ shouldCreatePiBlocks()

◆ shouldSimplify()

◆ simplify()

◆ sortNodesTopologically()

Member Data Documentation

◆ BBList

◆ DI

◆ Graph

◆ IMap

◆ InstOrdinalMap

◆ NodeOrdinalMap