LLVM  10.0.0svn
Public Types | Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | List of all members
llvm::AbstractDependenceGraphBuilder< GraphType > Class Template Referenceabstract

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 >:
Inheritance graph
[legend]
Collaboration diagram for llvm::AbstractDependenceGraphBuilder< GraphType >:
Collaboration graph
[legend]

Public Types

using ClassesType = EquivalenceClasses< BasicBlock * >
 
using NodeListType = SmallVector< NodeType *, 4 >
 

Public Member Functions

 AbstractDependenceGraphBuilder (GraphType &G, DependenceInfo &D, const BasicBlockListType &BBs)
 
virtual ~AbstractDependenceGraphBuilder ()
 
void populate ()
 The main entry to the graph construction algorithm. More...
 
void createFineGrainedNodes ()
 Create fine grained nodes. More...
 
void createDefUseEdges ()
 Analyze the def-use chains and create edges from the nodes containing definitions to the nodes containing the uses. More...
 
void createMemoryDependencyEdges ()
 Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create edges between them. More...
 
void createAndConnectRootNode ()
 Create a root node and add edges such that each node in the graph is reachable from the root. More...
 

Protected Types

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

Protected Member Functions

virtual NodeType & createRootNode ()=0
 Create the root node of the graph. More...
 
virtual NodeType & createFineGrainedNode (Instruction &I)=0
 Create an atomic node in the graph given a single instruction. More...
 
virtual EdgeType & createDefUseEdge (NodeType &Src, NodeType &Tgt)=0
 Create a def-use edge going from Src to Tgt. More...
 
virtual EdgeType & createMemoryEdge (NodeType &Src, NodeType &Tgt)=0
 Create a memory dependence edge going from Src to Tgt. More...
 
virtual EdgeType & createRootedEdge (NodeType &Src, NodeType &Tgt)=0
 Create a rooted edge going from Src to Tgt . More...
 
virtual void destroyEdge (EdgeType &E)
 Deallocate memory of edge E. More...
 
virtual void destroyNode (NodeType &N)
 Deallocate memory of node N. More...
 

Protected Attributes

GraphType & Graph
 Reference to the graph that gets built by a concrete implementation of this builder. More...
 
DependenceInfoDI
 Dependence information used to create memory dependence edges in the graph. More...
 
const BasicBlockListTypeBBList
 The list of basic blocks to consider when building the graph. More...
 
InstToNodeMap IMap
 A mapping from instructions to the corresponding nodes in the graph. More...
 

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

Member Typedef Documentation

◆ BasicBlockListType

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

Definition at line 30 of file DependenceGraphBuilder.h.

◆ ClassesType

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

Definition at line 37 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 100 of file DependenceGraphBuilder.h.

◆ NodeListType

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

Definition at line 38 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 40 of file DependenceGraphBuilder.h.

◆ ~AbstractDependenceGraphBuilder()

template<class GraphType>
virtual llvm::AbstractDependenceGraphBuilder< GraphType >::~AbstractDependenceGraphBuilder ( )
inlinevirtual

Definition at line 43 of file DependenceGraphBuilder.h.

Member Function Documentation

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

Referenced by llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::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.

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

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

Referenced by llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::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.

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

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

Referenced by llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::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 127 of file DependenceGraphBuilder.cpp.

Referenced by llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::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.

Referenced by llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::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 .

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

◆ createRootNode()

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

Create the root node of the graph.

Implemented in llvm::DDGBuilder.

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

◆ destroyEdge()

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

Deallocate memory of edge E.

Definition at line 94 of file DependenceGraphBuilder.h.

◆ destroyNode()

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

Deallocate memory of node N.

Definition at line 97 of file DependenceGraphBuilder.h.

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

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

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 111 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 108 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 104 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 114 of file DependenceGraphBuilder.h.


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