1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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
|