//===- llvm/Analysis/DependenceGraphBuilder.h -------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt 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.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H
#define LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/SmallVector.h"
namespace llvm {
class BasicBlock;
class DependenceInfo;
class Instruction;
/// 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 {
protected:
using BasicBlockListType = SmallVectorImpl<BasicBlock *>;
private:
using NodeType = typename GraphType::NodeType;
using EdgeType = typename GraphType::EdgeType;
public:
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() = default;
/// 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).
void populate() {
computeInstructionOrdinals();
createFineGrainedNodes();
createDefUseEdges();
createMemoryDependencyEdges();
simplify();
createAndConnectRootNode();
createPiBlocks();
sortNodesTopologically();
}
/// 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.
void computeInstructionOrdinals();
/// 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();
/// 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.
void createPiBlocks();
/// 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.
void simplify();
/// Topologically sort the graph nodes.
void sortNodesTopologically();
protected:
/// 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 pi-block node in the graph representing a group of nodes in an
/// SCC of the graph.
virtual NodeType &createPiBlock(const NodeListType &L) = 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;
/// Given a pi-block node, return a vector of all the nodes contained within
/// it.
virtual const NodeListType &getNodesInPiBlock(const NodeType &N) = 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; }
/// Return true if creation of pi-blocks are supported and desired,
/// and false otherwise.
virtual bool shouldCreatePiBlocks() const { return true; }
/// Return true if graph simplification step is requested, and false
/// otherwise.
virtual bool shouldSimplify() const { return true; }
/// Return true if it's safe to merge the two nodes.
virtual bool areNodesMergeable(const NodeType &A,
const NodeType &B) const = 0;
/// 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.
virtual void mergeNodes(NodeType &A, NodeType &B) = 0;
/// Given an instruction \p I return its associated ordinal number.
size_t getOrdinal(Instruction &I) {
assert(InstOrdinalMap.find(&I) != InstOrdinalMap.end() &&
"No ordinal computed for this instruction.");
return InstOrdinalMap[&I];
}
/// Given a node \p N return its associated ordinal number.
size_t getOrdinal(NodeType &N) {
assert(NodeOrdinalMap.find(&N) != NodeOrdinalMap.end() &&
"No ordinal computed for this node.");
return NodeOrdinalMap[&N];
}
/// Map types to map instructions to nodes used when populating the graph.
using InstToNodeMap = DenseMap<Instruction *, NodeType *>;
/// Map Types to map instruction/nodes to an ordinal number.
using InstToOrdinalMap = DenseMap<Instruction *, size_t>;
using NodeToOrdinalMap = DenseMap<NodeType *, size_t>;
/// 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;
/// A mapping from each instruction to an ordinal number. This map is used to
/// populate the \p NodeOrdinalMap.
InstToOrdinalMap InstOrdinalMap;
/// A mapping from nodes to an ordinal number. This map is used to sort nodes
/// in a pi-block based on program order.
NodeToOrdinalMap NodeOrdinalMap;
};
} // namespace llvm
#endif // LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H