LLVM 20.0.0git
|
Concrete implementation of a pure data dependence graph builder. More...
#include "llvm/Analysis/DDG.h"
Public Member Functions | |
DDGBuilder (DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs) | |
DDGNode & | createRootNode () final |
Create the root node of the graph. | |
DDGNode & | createFineGrainedNode (Instruction &I) final |
Create an atomic node in the graph given a single instruction. | |
DDGNode & | createPiBlock (const NodeListType &L) final |
Create a pi-block node in the graph representing a group of nodes in an SCC of the graph. | |
DDGEdge & | createDefUseEdge (DDGNode &Src, DDGNode &Tgt) final |
DDGEdge & | createMemoryEdge (DDGNode &Src, DDGNode &Tgt) final |
DDGEdge & | createRootedEdge (DDGNode &Src, DDGNode &Tgt) final |
const NodeListType & | getNodesInPiBlock (const DDGNode &N) final |
bool | areNodesMergeable (const DDGNode &Src, const DDGNode &Tgt) const final |
Return true if the two nodes \pSrc and \pTgt are both simple nodes and the consecutive instructions after merging belong to the same basic block. | |
void | mergeNodes (DDGNode &Src, DDGNode &Tgt) final |
bool | shouldSimplify () const final |
Return true if graph simplification step is requested, and false otherwise. | |
bool | shouldCreatePiBlocks () const final |
Return true if creation of pi-blocks are supported and desired, and false otherwise. | |
Public Member Functions inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph > | |
AbstractDependenceGraphBuilder (DataDependenceGraph &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. | |
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. | |
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 inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph > | |
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 inherited from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph > | |
DataDependenceGraph & | 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. | |
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.
|
inline |
Definition at line 369 of file DDG.h.
References assert(), llvm::DirectedGraph< NodeType, EdgeType >::connect(), E, llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph, and llvm::DDGEdge::RegisterDefUse.
|
inlinefinalvirtual |
Create an atomic node in the graph given a single instruction.
Implements llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.
Definition at line 357 of file DDG.h.
References llvm::DataDependenceGraph::addNode(), assert(), llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph, and I.
Definition at line 375 of file DDG.h.
References assert(), llvm::DirectedGraph< NodeType, EdgeType >::connect(), E, llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph, and llvm::DDGEdge::MemoryDependence.
|
inlinefinalvirtual |
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 363 of file DDG.h.
References llvm::DataDependenceGraph::addNode(), assert(), and llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph.
Definition at line 381 of file DDG.h.
References assert(), llvm::DirectedGraph< NodeType, EdgeType >::connect(), E, llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph, and llvm::DDGEdge::Rooted.
|
inlinefinalvirtual |
Create the root node of the graph.
Implements llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.
Definition at line 351 of file DDG.h.
References llvm::DataDependenceGraph::addNode(), assert(), and llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph.
|
inlinefinal |
Definition at line 278 of file DDG.cpp.
References A, assert(), B, llvm::DirectedGraph< NodeType, EdgeType >::connect(), llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::destroyEdge(), llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::destroyNode(), llvm::DGEdge< NodeType, EdgeType >::getTargetNode(), llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph, and llvm::DirectedGraph< NodeType, EdgeType >::removeNode().
|
finalvirtual |
Return true if creation of pi-blocks are supported and desired, and false otherwise.
Reimplemented from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.
Definition at line 300 of file DDG.cpp.
References CreatePiBlocks.
|
finalvirtual |
Return true if graph simplification step is requested, and false otherwise.
Reimplemented from llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.
Definition at line 298 of file DDG.cpp.
References SimplifyDDG.