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:28

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:40

Parameters

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

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:70

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:86

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:110

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:78

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:103

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:74

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:82

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:113

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:107

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:93

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

Description

Create the root node of the graph.

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

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:116

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:123

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:126

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:120

Parameters

const 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:133

Parameters

llvm::Instruction& I

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:140

Parameters

llvm::AbstractDependenceGraphBuilder::NodeType& N

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:56

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:130

void sortNodesTopologically()

Description

Topologically sort the graph nodes.

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

virtual ~AbstractDependenceGraphBuilder<
    GraphType>()

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