blob: 5f4bdb47043b571110b7d3930f56aa10e1fe36a3 [file] [log] [blame]
//===- llvm/Analysis/DependenceGraphBuilder.h -------------------*- C++ -*-===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// This file defines a builder interface that can be used to populate dependence
// graphs such as DDG and PDG.
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Instructions.h"
namespace llvm {
/// 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.
template <class GraphType> class AbstractDependenceGraphBuilder {
using BasicBlockListType = SmallVectorImpl<BasicBlock *>;
using NodeType = typename GraphType::NodeType;
using EdgeType = typename GraphType::EdgeType;
using ClassesType = EquivalenceClasses<BasicBlock *>;
using NodeListType = SmallVector<NodeType *, 4>;
AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D,
const BasicBlockListType &BBs)
: Graph(G), DI(D), BBList(BBs) {}
virtual ~AbstractDependenceGraphBuilder() {}
/// 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.
/// 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).
void populate() {
/// Create fine grained nodes. These are typically atomic nodes that
/// consist of a single instruction.
void createFineGrainedNodes();
/// Analyze the def-use chains and create edges from the nodes containing
/// definitions to the nodes containing the uses.
void createDefUseEdges();
/// Analyze data dependencies that exist between memory loads or stores,
/// in the graph nodes and create edges between them.
void createMemoryDependencyEdges();
/// Create a root node and add edges such that each node in the graph is
/// reachable from the root.
void createAndConnectRootNode();
/// Create the root node of the graph.
virtual NodeType &createRootNode() = 0;
/// Create an atomic node in the graph given a single instruction.
virtual NodeType &createFineGrainedNode(Instruction &I) = 0;
/// Create a def-use edge going from \p Src to \p Tgt.
virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0;
/// Create a memory dependence edge going from \p Src to \p Tgt.
virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0;
/// Create a rooted edge going from \p Src to \p Tgt .
virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0;
/// Deallocate memory of edge \p E.
virtual void destroyEdge(EdgeType &E) { delete &E; }
/// Deallocate memory of node \p N.
virtual void destroyNode(NodeType &N) { delete &N; }
/// Map types to map instructions to nodes used when populating the graph.
using InstToNodeMap = DenseMap<Instruction *, NodeType *>;
/// Reference to the graph that gets built by a concrete implementation of
/// this builder.
GraphType &Graph;
/// Dependence information used to create memory dependence edges in the
/// graph.
DependenceInfo &DI;
/// The list of basic blocks to consider when building the graph.
const BasicBlockListType &BBList;
/// A mapping from instructions to the corresponding nodes in the graph.
InstToNodeMap IMap;
} // namespace llvm