Go to the documentation of this file.
14 #ifndef LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H
15 #define LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H
37 using EdgeType =
typename GraphType::EdgeType;
151 const NodeType &
B)
const = 0;
155 virtual void mergeNodes(NodeType &A, NodeType &
B) = 0;
160 "No ordinal computed for this instruction.");
167 "No ordinal computed for this node.");
203 #endif // LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H
This is an optimization pass for GlobalISel generic memory operations.
void createDefUseEdges()
Analyze the def-use chains and create edges from the nodes containing definitions to the nodes contai...
void populate()
The main entry to the graph construction algorithm.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
size_t getOrdinal(Instruction &I)
Given an instruction I return its associated ordinal number.
void createPiBlocks()
Apply graph abstraction to groups of nodes that belong to a strongly connected component of the graph...
virtual void destroyNode(NodeType &N)
Deallocate memory of node N.
AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D, const BasicBlockListType &BBs)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
NodeToOrdinalMap NodeOrdinalMap
A mapping from nodes to an ordinal number.
const BasicBlockListType & BBList
The list of basic blocks to consider when building the graph.
virtual const NodeListType & getNodesInPiBlock(const NodeType &N)=0
Given a pi-block node, return a vector of all the nodes contained within it.
DependenceInfo & DI
Dependence information used to create memory dependence edges in the graph.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
void createAndConnectRootNode()
Create a root node and add edges such that each node in the graph is reachable from the root.
This abstract builder class defines a set of high-level steps for creating DDG-like graphs.
virtual EdgeType & createRootedEdge(NodeType &Src, NodeType &Tgt)=0
Create a rooted edge going from Src to Tgt .
size_t getOrdinal(NodeType &N)
Given a node N return its associated ordinal number.
void createMemoryDependencyEdges()
Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create ed...
virtual NodeType & createFineGrainedNode(Instruction &I)=0
Create an atomic node in the graph given a single instruction.
DependenceInfo - This class is the main dependence-analysis driver.
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 ~AbstractDependenceGraphBuilder()=default
void computeInstructionOrdinals()
Compute ordinal numbers for each instruction and store them in a map for future look up.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
virtual bool shouldCreatePiBlocks() const
Return true if creation of pi-blocks are supported and desired, and false otherwise.
iterator find(const_arg_type_t< KeyT > Val)
SmallVector< NodeType *, 4 > NodeListType
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
virtual EdgeType & createMemoryEdge(NodeType &Src, NodeType &Tgt)=0
Create a memory dependence edge going from Src to Tgt.
@ BasicBlock
Various leaf nodes.
virtual EdgeType & createDefUseEdge(NodeType &Src, NodeType &Tgt)=0
Create a def-use edge going from Src to Tgt.
virtual bool areNodesMergeable(const NodeType &A, const NodeType &B) const =0
Return true if it's safe to merge the two nodes.
void simplify()
Go through all the nodes in the graph and collapse any two nodes 'a' and 'b' if all of the following ...
InstToOrdinalMap InstOrdinalMap
A mapping from each instruction to an ordinal number.
virtual NodeType & createRootNode()=0
Create the root node of the graph.
virtual void destroyEdge(EdgeType &E)
Deallocate memory of edge E.
void sortNodesTopologically()
Topologically sort the graph nodes.
void createFineGrainedNodes()
Create fine grained nodes.
InstToNodeMap IMap
A mapping from instructions to the corresponding nodes in the graph.
virtual bool shouldSimplify() const
Return true if graph simplification step is requested, and false otherwise.
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.
GraphType & Graph
Reference to the graph that gets built by a concrete implementation of this builder.