LLVM  11.0.0git
Public Member Functions | List of all members
llvm::DDGBuilder Class Reference

Concrete implementation of a pure data dependence graph builder. More...

#include "llvm/Analysis/DDG.h"

Inheritance diagram for llvm::DDGBuilder:
Inheritance graph
[legend]
Collaboration diagram for llvm::DDGBuilder:
Collaboration graph
[legend]

Public Member Functions

 DDGBuilder (DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs)
 
DDGNodecreateRootNode () final override
 Create the root node of the graph. More...
 
DDGNodecreateFineGrainedNode (Instruction &I) final override
 Create an atomic node in the graph given a single instruction. More...
 
DDGNodecreatePiBlock (const NodeListType &L) final override
 Create a pi-block node in the graph representing a group of nodes in an SCC of the graph. More...
 
DDGEdgecreateDefUseEdge (DDGNode &Src, DDGNode &Tgt) final override
 
DDGEdgecreateMemoryEdge (DDGNode &Src, DDGNode &Tgt) final override
 
DDGEdgecreateRootedEdge (DDGNode &Src, DDGNode &Tgt) final override
 
const NodeListTypegetNodesInPiBlock (const DDGNode &N) final override
 
bool areNodesMergeable (const DDGNode &Src, const DDGNode &Tgt) const final override
 Return true if the two nodes and are both simple nodes and the consecutive instructions after merging belong to the same basic block. More...
 
void mergeNodes (DDGNode &Src, DDGNode &Tgt) final override
 
bool shouldSimplify () const final override
 Return true if graph simplification step is requested, and false otherwise. More...
 
bool shouldCreatePiBlocks () const final override
 Return true if creation of pi-blocks are supported and desired, and false otherwise. More...
 
- Public Member Functions inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
 AbstractDependenceGraphBuilder (DataDependenceGraph &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...
 

Additional Inherited Members

- Public Types inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
using ClassesType = EquivalenceClasses< BasicBlock *>
 
using NodeListType = SmallVector< NodeType *, 4 >
 
- Protected Types inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
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 inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
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 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 inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
DataDependenceGraphGraph
 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

Concrete implementation of a pure data dependence graph builder.

This class provides custom implementation for the pure-virtual functions used in the generic dependence graph build algorithm.

For information about time complexity of the build algorithm see the comments near the declaration of AbstractDependenceGraphBuilder.

Definition at line 350 of file DDG.h.

Constructor & Destructor Documentation

◆ DDGBuilder()

llvm::DDGBuilder::DDGBuilder ( DataDependenceGraph G,
DependenceInfo D,
const BasicBlockListType BBs 
)
inline

Definition at line 352 of file DDG.h.

Member Function Documentation

◆ areNodesMergeable()

bool DDGBuilder::areNodesMergeable ( const DDGNode Src,
const DDGNode Tgt 
) const
finaloverride

Return true if the two nodes and are both simple nodes and the consecutive instructions after merging belong to the same basic block.

Definition at line 269 of file DDG.cpp.

References llvm::dyn_cast(), llvm::SimpleDDGNode::getLastInstruction(), llvm::Instruction::getParent(), and llvm::BasicBlock::getParent().

◆ createDefUseEdge()

DDGEdge& llvm::DDGBuilder::createDefUseEdge ( DDGNode Src,
DDGNode Tgt 
)
inlinefinaloverride

Definition at line 373 of file DDG.h.

References assert(), E, and llvm::DDGEdge::RegisterDefUse.

◆ createFineGrainedNode()

DDGNode& llvm::DDGBuilder::createFineGrainedNode ( Instruction I)
inlinefinaloverridevirtual

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

Implements llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.

Definition at line 361 of file DDG.h.

References assert(), and I.

◆ createMemoryEdge()

DDGEdge& llvm::DDGBuilder::createMemoryEdge ( DDGNode Src,
DDGNode Tgt 
)
inlinefinaloverride

Definition at line 379 of file DDG.h.

References assert(), E, and llvm::DDGEdge::MemoryDependence.

◆ createPiBlock()

DDGNode& llvm::DDGBuilder::createPiBlock ( const NodeListType L)
inlinefinaloverridevirtual

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

Implements llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.

Definition at line 367 of file DDG.h.

References assert().

◆ createRootedEdge()

DDGEdge& llvm::DDGBuilder::createRootedEdge ( DDGNode Src,
DDGNode Tgt 
)
inlinefinaloverride

Definition at line 385 of file DDG.h.

References assert(), E, and llvm::DDGEdge::Rooted.

◆ createRootNode()

DDGNode& llvm::DDGBuilder::createRootNode ( )
inlinefinaloverridevirtual

Create the root node of the graph.

Implements llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.

Definition at line 355 of file DDG.h.

References assert(), and llvm::NVPTX::PTXCvtMode::RN.

◆ getNodesInPiBlock()

const NodeListType& llvm::DDGBuilder::getNodesInPiBlock ( const DDGNode N)
inlinefinaloverride

Definition at line 393 of file DDG.h.

References assert(), llvm::dyn_cast(), E, G, N, and llvm::operator<<().

◆ mergeNodes()

void DDGBuilder::mergeNodes ( DDGNode Src,
DDGNode Tgt 
)
finaloverride

◆ shouldCreatePiBlocks()

bool DDGBuilder::shouldCreatePiBlocks ( ) const
finaloverridevirtual

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

Reimplemented from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.

Definition at line 304 of file DDG.cpp.

References CreatePiBlocks.

◆ shouldSimplify()

bool DDGBuilder::shouldSimplify ( ) const
finaloverridevirtual

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

Reimplemented from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.

Definition at line 302 of file DDG.cpp.

References SimplifyDDG.


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