LLVM  14.0.0git
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 >:
[legend]
Collaboration diagram for llvm::AbstractDependenceGraphBuilder< GraphType >:
[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.

## ◆ BasicBlockListType

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

Definition at line 33 of file DependenceGraphBuilder.h.

## ◆ ClassesType

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

Definition at line 40 of file DependenceGraphBuilder.h.

## ◆ InstToNodeMap

template<class GraphType >
 using llvm::AbstractDependenceGraphBuilder< GraphType >::InstToNodeMap = DenseMap
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
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

Definition at line 41 of file DependenceGraphBuilder.h.

## ◆ NodeToOrdinalMap

template<class GraphType >
 using llvm::AbstractDependenceGraphBuilder< GraphType >::NodeToOrdinalMap = DenseMap
protected

Definition at line 176 of file DependenceGraphBuilder.h.

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

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

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

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

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

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

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

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

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

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

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

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.

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

## ◆ sortNodesTopologically()

template<class G >
 void AbstractDependenceGraphBuilder::sortNodesTopologically

Topologically sort the graph nodes.

Definition at line 481 of file DependenceGraphBuilder.cpp.

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

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

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