LLVM
15.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 override |
Create the root node of the graph. More... | |
DDGNode & | createFineGrainedNode (Instruction &I) final override |
Create an atomic node in the graph given a single instruction. More... | |
DDGNode & | createPiBlock (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... | |
DDGEdge & | createDefUseEdge (DDGNode &Src, DDGNode &Tgt) final override |
DDGEdge & | createMemoryEdge (DDGNode &Src, DDGNode &Tgt) final override |
DDGEdge & | createRootedEdge (DDGNode &Src, DDGNode &Tgt) final override |
const NodeListType & | getNodesInPiBlock (const DDGNode &N) final override |
bool | areNodesMergeable (const DDGNode &Src, const DDGNode &Tgt) const final override |
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. More... | |
void | mergeNodes (DDGNode &Src, DDGNode &Tgt) final override |
bool | shouldSimplify () const final override |
bool | shouldCreatePiBlocks () const final override |
![]() | |
AbstractDependenceGraphBuilder (DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs) | |
virtual | ~AbstractDependenceGraphBuilder ()=default |
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 | |
![]() | |
using | ClassesType = EquivalenceClasses< BasicBlock * > |
using | NodeListType = SmallVector< NodeType *, 4 > |
![]() | |
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 > |
![]() | |
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 NodeListType & | getNodesInPiBlock (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... | |
![]() | |
DataDependenceGraph & | Graph |
Reference to the graph that gets built by a concrete implementation of this builder. More... | |
DependenceInfo & | DI |
Dependence information used to create memory dependence edges in the graph. More... | |
const BasicBlockListType & | BBList |
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... | |
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.
|
inlinefinaloverridevirtual |
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.
|
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 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.
|
inlinefinaloverridevirtual |
Create the root node of the graph.
Implements llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >.
Definition at line 351 of file DDG.h.
References llvm::DataDependenceGraph::addNode(), assert(), llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph, and RN.
|
inlinefinaloverride |
Definition at line 279 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().
|
finaloverride |
Definition at line 301 of file DDG.cpp.
References CreatePiBlocks.
|
finaloverride |
Definition at line 299 of file DDG.cpp.
References SimplifyDDG.