class AbstractDependenceGraphBuilder

Declaration

template <class GraphType>
class AbstractDependenceGraphBuilder { /* full declaration omitted */ };

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.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:31

Templates

GraphType

Member Variables

protected GraphType& Graph
Reference to the graph that gets built by a concrete implementation of this builder.
protected llvm::DependenceInfo& DI
Dependence information used to create memory dependence edges in the graph.
protected const llvm::AbstractDependenceGraphBuilder:: BasicBlockListType& BBList
The list of basic blocks to consider when building the graph.
protected llvm::AbstractDependenceGraphBuilder:: InstToNodeMap IMap
A mapping from instructions to the corresponding nodes in the graph.
protected llvm::AbstractDependenceGraphBuilder:: InstToOrdinalMap InstOrdinalMap
A mapping from each instruction to an ordinal number. This map is used to populate the \p NodeOrdinalMap.
protected llvm::AbstractDependenceGraphBuilder:: NodeToOrdinalMap NodeOrdinalMap
A mapping from nodes to an ordinal number. This map is used to sort nodes in a pi-block based on program order.

Method Overview

Methods

AbstractDependenceGraphBuilder<GraphType>(
    GraphType& G,
    llvm::DependenceInfo& D,
    const llvm::AbstractDependenceGraphBuilder::
        BasicBlockListType& BBs)

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:43

Parameters

GraphType& G
llvm::DependenceInfo& D
const llvm::AbstractDependenceGraphBuilder:: BasicBlockListType& BBs

virtual bool areNodesMergeable(
    const llvm::AbstractDependenceGraphBuilder::
        NodeType& A,
    const llvm::AbstractDependenceGraphBuilder::
        NodeType& B) const

Description

Return true if it's safe to merge the two nodes.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:150

Parameters

const llvm::AbstractDependenceGraphBuilder:: NodeType& A
const llvm::AbstractDependenceGraphBuilder:: NodeType& B

void computeInstructionOrdinals()

Description

Compute ordinal numbers for each instruction and store them in a map for future look up. These ordinals are used to compute node ordinals which are in turn used to order nodes that are part of a cycle. Instruction ordinals are assigned based on lexical program order.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:74

void createAndConnectRootNode()

Description

Create a root node and add edges such that each node in the graph is reachable from the root.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:90

virtual llvm::AbstractDependenceGraphBuilder::
    EdgeType&
    createDefUseEdge(
        llvm::AbstractDependenceGraphBuilder::
            NodeType& Src,
        llvm::AbstractDependenceGraphBuilder::
            NodeType& Tgt)

Description

Create a def-use edge going from \p Src to \p Tgt.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:123

Parameters

llvm::AbstractDependenceGraphBuilder::NodeType& Src
llvm::AbstractDependenceGraphBuilder::NodeType& Tgt

void createDefUseEdges()

Description

Analyze the def-use chains and create edges from the nodes containing definitions to the nodes containing the uses.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:82

virtual llvm::AbstractDependenceGraphBuilder::
    NodeType&
    createFineGrainedNode(llvm::Instruction& I)

Description

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

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:116

Parameters

llvm::Instruction& I

void createFineGrainedNodes()

Description

Create fine grained nodes. These are typically atomic nodes that consist of a single instruction.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:78

void createMemoryDependencyEdges()

Description

Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create edges between them.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:86

virtual llvm::AbstractDependenceGraphBuilder::
    EdgeType&
    createMemoryEdge(
        llvm::AbstractDependenceGraphBuilder::
            NodeType& Src,
        llvm::AbstractDependenceGraphBuilder::
            NodeType& Tgt)

Description

Create a memory dependence edge going from \p Src to \p Tgt.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:126

Parameters

llvm::AbstractDependenceGraphBuilder::NodeType& Src
llvm::AbstractDependenceGraphBuilder::NodeType& Tgt

virtual llvm::AbstractDependenceGraphBuilder::
    NodeType&
    createPiBlock(
        const llvm::
            AbstractDependenceGraphBuilder::
                NodeListType& L)

Description

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

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:120

Parameters

const llvm::AbstractDependenceGraphBuilder:: NodeListType& L

void createPiBlocks()

Description

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. The purpose of this abstraction is to isolate sets of program elements that need to stay together during codegen and turn the dependence graph into an acyclic graph.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:97

virtual llvm::AbstractDependenceGraphBuilder::
    NodeType&
    createRootNode()

Description

Create the root node of the graph.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:113

virtual llvm::AbstractDependenceGraphBuilder::
    EdgeType&
    createRootedEdge(
        llvm::AbstractDependenceGraphBuilder::
            NodeType& Src,
        llvm::AbstractDependenceGraphBuilder::
            NodeType& Tgt)

Description

Create a rooted edge going from \p Src to \p Tgt .

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:129

Parameters

llvm::AbstractDependenceGraphBuilder::NodeType& Src
llvm::AbstractDependenceGraphBuilder::NodeType& Tgt

virtual void destroyEdge(
    llvm::AbstractDependenceGraphBuilder::
        EdgeType& E)

Description

Deallocate memory of edge \p E.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:136

Parameters

llvm::AbstractDependenceGraphBuilder::EdgeType& E

virtual void destroyNode(
    llvm::AbstractDependenceGraphBuilder::
        NodeType& N)

Description

Deallocate memory of node \p N.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:139

Parameters

llvm::AbstractDependenceGraphBuilder::NodeType& N

virtual const llvm::
    AbstractDependenceGraphBuilder::NodeListType&
    getNodesInPiBlock(
        const llvm::
            AbstractDependenceGraphBuilder::
                NodeType& N)

Description

Given a pi-block node, return a vector of all the nodes contained within it.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:133

Parameters

const llvm::AbstractDependenceGraphBuilder:: NodeType& N

size_t getOrdinal(
    llvm::AbstractDependenceGraphBuilder::
        NodeType& N)

Description

Given a node \p N return its associated ordinal number.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:165

Parameters

llvm::AbstractDependenceGraphBuilder::NodeType& N

size_t getOrdinal(llvm::Instruction& I)

Description

Given an instruction \p I return its associated ordinal number.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:158

Parameters

llvm::Instruction& I

virtual void mergeNodes(
    llvm::AbstractDependenceGraphBuilder::
        NodeType& A,
    llvm::AbstractDependenceGraphBuilder::
        NodeType& B)

Description

Append the content of node \p B into node \p A and remove \p B and the edge between \p A and \p B from the graph.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:155

Parameters

llvm::AbstractDependenceGraphBuilder::NodeType& A
llvm::AbstractDependenceGraphBuilder::NodeType& B

void populate()

Description

The main entry to the graph construction algorithm. It starts by creating nodes in increasing order of granularity and then adds def-use and memory edges. As one of the final stages, it also creates pi-block nodes to facilitate codegen in transformations that use dependence graphs. The algorithmic complexity of this implementation is O(V^2 * I^2), where V is the number of vertecies (nodes) and I is the number of instructions in each node. The total number of instructions, N, is equal to V * I, therefore the worst-case time complexity is O(N^2). The average time complexity is O((N^2)/2).

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:59

virtual bool shouldCreatePiBlocks() const

Description

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

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:143

virtual bool shouldSimplify() const

Description

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

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:147

void simplify()

Description

Go through all the nodes in the graph and collapse any two nodes 'a' and 'b' if all of the following are true: - the only edge from 'a' is a def-use edge to 'b' and - the only edge to 'b' is a def-use edge from 'a' and - there is no cyclic edge from 'b' to 'a' and - all instructions in 'a' and 'b' belong to the same basic block and - both 'a' and 'b' are simple (single or multi instruction) nodes.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:106

void sortNodesTopologically()

Description

Topologically sort the graph nodes.

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:109

virtual ~AbstractDependenceGraphBuilder<
    GraphType>()

Declared at: llvm/include/llvm/Analysis/DependenceGraphBuilder.h:46