summaryrefslogtreecommitdiff
path: root/include/llvm/Analysis/DependenceGraphBuilder.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/Analysis/DependenceGraphBuilder.h')
-rw-r--r--include/llvm/Analysis/DependenceGraphBuilder.h119
1 files changed, 119 insertions, 0 deletions
diff --git a/include/llvm/Analysis/DependenceGraphBuilder.h b/include/llvm/Analysis/DependenceGraphBuilder.h
new file mode 100644
index 000000000000..5f4bdb47043b
--- /dev/null
+++ b/include/llvm/Analysis/DependenceGraphBuilder.h
@@ -0,0 +1,119 @@
+//===- 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_DEPENDENCE_GRAPH_BUILDER_H
+#define LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
+
+#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 {
+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() {}
+
+ /// 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() {
+ createFineGrainedNodes();
+ createDefUseEdges();
+ createMemoryDependencyEdges();
+ createAndConnectRootNode();
+ }
+
+ /// 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();
+
+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 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
+
+#endif // LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H