LLVM  11.0.0git
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 computeInstructionOrdinals ()
 Compute ordinal numbers for each instruction and store them in a map for future look up. 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...
 
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. More...
 
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: More...
 
void sortNodesTopologically ()
 Topologically sort the graph nodes. 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...
 
using InstToOrdinalMap = DenseMap< Instruction *, size_t >
 Map Types to map instruction/nodes to an ordinal number. More...
 
using NodeToOrdinalMap = DenseMap< NodeType *, size_t >
 

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 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. 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 const NodeListTypegetNodesInPiBlock (const NodeType &N)=0
 Given a pi-block node, return a vector of all the nodes contained within it. More...
 
virtual void destroyEdge (EdgeType &E)
 Deallocate memory of edge E. More...
 
virtual void destroyNode (NodeType &N)
 Deallocate memory of node N. More...
 
virtual bool shouldCreatePiBlocks () const
 Return true if creation of pi-blocks are supported and desired, and false otherwise. More...
 
virtual bool shouldSimplify () const
 Return true if graph simplification step is requested, and false otherwise. More...
 
virtual bool areNodesMergeable (const NodeType &A, const NodeType &B) const =0
 Return true if it's safe to merge the two nodes. More...
 
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. More...
 
size_t getOrdinal (Instruction &I)
 Given an instruction I return its associated ordinal number. More...
 
size_t getOrdinal (NodeType &N)
 Given a node N return its associated ordinal number. 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...
 
InstToOrdinalMap InstOrdinalMap
 A mapping from each instruction to an ordinal number. More...
 
NodeToOrdinalMap NodeOrdinalMap
 A mapping from nodes to an ordinal number. 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 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 172 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 175 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 176 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 ( )
inlinevirtual

Definition at line 46 of file DependenceGraphBuilder.h.

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.

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

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

Referenced by llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::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 63 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 228 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 50 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 278 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().

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

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

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

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

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

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

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

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

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

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

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

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

◆ sortNodesTopologically()

template<class G >
void AbstractDependenceGraphBuilder::sortNodesTopologically ( )

Topologically sort the graph nodes.

Definition at line 482 of file DependenceGraphBuilder.cpp.

Referenced by llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::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 187 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 184 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 180 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 190 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 194 of file DependenceGraphBuilder.h.

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

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


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