llvm::AbstractDependenceGraphBuilder

Synopsis

Declared in <llvm/Analysis/DependenceGraphBuilder.h>

template<class GraphType>
class AbstractDependenceGraphBuilder;

Description

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.

Type Aliases

Name	Description
`ClassesType`	Equivalence classes of basic blocks.
`NodeListType`	Small vector of graph node pointers.

Member Functions

Name	Description
`AbstractDependenceGraphBuilder` [constructor]	Construct a builder for graph `G` using dependence info `D` and blocks `BBs.`
`~AbstractDependenceGraphBuilder` [destructor] [virtual]	Destroy this dependence graph builder.
`computeInstructionOrdinals`	Compute ordinal numbers for each instruction and store them in a map.
`createAndConnectRootNode`	Create a root node and add edges such that each node in the graph is reachable from the root.
`createDefUseEdges`	Analyze the def-use chains and create edges from the nodes containing definitions to the nodes containing the uses.
`createFineGrainedNodes`	Create fine grained nodes. These are typically atomic nodes that consist of a single instruction.
`createMemoryDependencyEdges`	Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create edges between them.
`createPiBlocks`	Create pi-block nodes from strongly connected components.
`populate`	The main entry to the graph construction algorithm.
`simplify`	Collapse adjacent def-use pairs in the same basic block.
`sortNodesTopologically`	Topologically sort the graph nodes.

Protected Type Aliases

Name	Description
`BasicBlockListType`	List of basic blocks considered when building the graph.
`InstToNodeMap`	Map types to map instructions to nodes used when populating the graph.
`InstToOrdinalMap`	Map Types to map instruction/nodes to an ordinal number.
`NodeToOrdinalMap`	Map from graph nodes to ordinal numbers.

Protected Member Functions

Name	Description
`areNodesMergeable` [virtual]	Return true if it's safe to merge the two nodes.
`createDefUseEdge` [virtual]	Create a def-use edge going from `Src` to `Tgt.`
`createFineGrainedNode` [virtual]	Create an atomic node in the graph given a single instruction.
`createMemoryEdge` [virtual]	Create a memory dependence edge going from `Src` to `Tgt.`
`createPiBlock` [virtual]	Create a pi-block node in the graph representing a group of nodes in an SCC of the graph.
`createRootNode` [virtual]	Create the root node of the graph.
`createRootedEdge` [virtual]	Create a rooted edge going from `Src` to `Tgt.`
`destroyEdge` [virtual]	Deallocate memory of edge `E.`
`destroyNode` [virtual]	Deallocate memory of node `N.`
`getNodesInPiBlock` [virtual]	Given a pi-block node, return a vector of all the nodes contained within it.
`getOrdinal`	`getOrdinal` overloads
`mergeNodes` [virtual]	Append the content of node `B` into node `A` and remove `B` and the edge between `A` and `B` from the graph.
`shouldCreatePiBlocks` [virtual]	Return true if creation of pi-blocks are supported and desired, and false otherwise.
`shouldSimplify` [virtual]	Return true if graph simplification step is requested, and false otherwise.

Protected Data Members

Name	Description
`BBList`	The list of basic blocks to consider when building the graph.
`DI`	Dependence information used to create memory dependence edges in the graph.
`Graph`	Reference to the graph that gets built by a concrete implementation of this builder.
`IMap`	A mapping from instructions to the corresponding nodes in the graph.
`InstOrdinalMap`	A mapping from each instruction to an ordinal number. This map is used to populate the `NodeOrdinalMap.`
`NodeOrdinalMap`	A mapping from nodes to an ordinal number. This map is used to sort nodes in a pi-block based on program order.

Derived Classes

Name	Description
`DDGBuilder`	Builder that constructs a pure data dependence graph.