1 | //===- llvm/Analysis/DependenceGraphBuilder.h -------------------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file defines a builder interface that can be used to populate dependence |
10 | // graphs such as DDG and PDG. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H |
15 | #define LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H |
16 | |
17 | #include "llvm/ADT/DenseMap.h" |
18 | #include "llvm/ADT/EquivalenceClasses.h" |
19 | #include "llvm/ADT/SmallVector.h" |
20 | |
21 | namespace llvm { |
22 | |
23 | class BasicBlock; |
24 | class DependenceInfo; |
25 | class Instruction; |
26 | |
27 | /// This abstract builder class defines a set of high-level steps for creating |
28 | /// DDG-like graphs. The client code is expected to inherit from this class and |
29 | /// define concrete implementation for each of the pure virtual functions used |
30 | /// in the high-level algorithm. |
31 | template <class GraphType> class AbstractDependenceGraphBuilder { |
32 | protected: |
33 | using BasicBlockListType = SmallVectorImpl<BasicBlock *>; |
34 | |
35 | private: |
36 | using NodeType = typename GraphType::NodeType; |
37 | using EdgeType = typename GraphType::EdgeType; |
38 | |
39 | public: |
40 | using ClassesType = EquivalenceClasses<BasicBlock *>; |
41 | using NodeListType = SmallVector<NodeType *, 4>; |
42 | |
43 | AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D, |
44 | const BasicBlockListType &BBs) |
45 | : Graph(G), DI(D), BBList(BBs) {} |
46 | virtual ~AbstractDependenceGraphBuilder() = default; |
47 | |
48 | /// The main entry to the graph construction algorithm. It starts by |
49 | /// creating nodes in increasing order of granularity and then |
50 | /// adds def-use and memory edges. As one of the final stages, it |
51 | /// also creates pi-block nodes to facilitate codegen in transformations |
52 | /// that use dependence graphs. |
53 | /// |
54 | /// The algorithmic complexity of this implementation is O(V^2 * I^2), where V |
55 | /// is the number of vertecies (nodes) and I is the number of instructions in |
56 | /// each node. The total number of instructions, N, is equal to V * I, |
57 | /// therefore the worst-case time complexity is O(N^2). The average time |
58 | /// complexity is O((N^2)/2). |
59 | void populate() { |
60 | computeInstructionOrdinals(); |
61 | createFineGrainedNodes(); |
62 | createDefUseEdges(); |
63 | createMemoryDependencyEdges(); |
64 | simplify(); |
65 | createAndConnectRootNode(); |
66 | createPiBlocks(); |
67 | sortNodesTopologically(); |
68 | } |
69 | |
70 | /// Compute ordinal numbers for each instruction and store them in a map for |
71 | /// future look up. These ordinals are used to compute node ordinals which are |
72 | /// in turn used to order nodes that are part of a cycle. |
73 | /// Instruction ordinals are assigned based on lexical program order. |
74 | void computeInstructionOrdinals(); |
75 | |
76 | /// Create fine grained nodes. These are typically atomic nodes that |
77 | /// consist of a single instruction. |
78 | void createFineGrainedNodes(); |
79 | |
80 | /// Analyze the def-use chains and create edges from the nodes containing |
81 | /// definitions to the nodes containing the uses. |
82 | void createDefUseEdges(); |
83 | |
84 | /// Analyze data dependencies that exist between memory loads or stores, |
85 | /// in the graph nodes and create edges between them. |
86 | void createMemoryDependencyEdges(); |
87 | |
88 | /// Create a root node and add edges such that each node in the graph is |
89 | /// reachable from the root. |
90 | void createAndConnectRootNode(); |
91 | |
92 | /// Apply graph abstraction to groups of nodes that belong to a strongly |
93 | /// connected component of the graph to create larger compound nodes |
94 | /// called pi-blocks. The purpose of this abstraction is to isolate sets of |
95 | /// program elements that need to stay together during codegen and turn |
96 | /// the dependence graph into an acyclic graph. |
97 | void createPiBlocks(); |
98 | |
99 | /// Go through all the nodes in the graph and collapse any two nodes |
100 | /// 'a' and 'b' if all of the following are true: |
101 | /// - the only edge from 'a' is a def-use edge to 'b' and |
102 | /// - the only edge to 'b' is a def-use edge from 'a' and |
103 | /// - there is no cyclic edge from 'b' to 'a' and |
104 | /// - all instructions in 'a' and 'b' belong to the same basic block and |
105 | /// - both 'a' and 'b' are simple (single or multi instruction) nodes. |
106 | void simplify(); |
107 | |
108 | /// Topologically sort the graph nodes. |
109 | void sortNodesTopologically(); |
110 | |
111 | protected: |
112 | /// Create the root node of the graph. |
113 | virtual NodeType &createRootNode() = 0; |
114 | |
115 | /// Create an atomic node in the graph given a single instruction. |
116 | virtual NodeType &createFineGrainedNode(Instruction &I) = 0; |
117 | |
118 | /// Create a pi-block node in the graph representing a group of nodes in an |
119 | /// SCC of the graph. |
120 | virtual NodeType &createPiBlock(const NodeListType &L) = 0; |
121 | |
122 | /// Create a def-use edge going from \p Src to \p Tgt. |
123 | virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0; |
124 | |
125 | /// Create a memory dependence edge going from \p Src to \p Tgt. |
126 | virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0; |
127 | |
128 | /// Create a rooted edge going from \p Src to \p Tgt . |
129 | virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0; |
130 | |
131 | /// Given a pi-block node, return a vector of all the nodes contained within |
132 | /// it. |
133 | virtual const NodeListType &getNodesInPiBlock(const NodeType &N) = 0; |
134 | |
135 | /// Deallocate memory of edge \p E. |
136 | virtual void destroyEdge(EdgeType &E) { delete &E; } |
137 | |
138 | /// Deallocate memory of node \p N. |
139 | virtual void destroyNode(NodeType &N) { delete &N; } |
140 | |
141 | /// Return true if creation of pi-blocks are supported and desired, |
142 | /// and false otherwise. |
143 | virtual bool shouldCreatePiBlocks() const { return true; } |
144 | |
145 | /// Return true if graph simplification step is requested, and false |
146 | /// otherwise. |
147 | virtual bool shouldSimplify() const { return true; } |
148 | |
149 | /// Return true if it's safe to merge the two nodes. |
150 | virtual bool areNodesMergeable(const NodeType &A, |
151 | const NodeType &B) const = 0; |
152 | |
153 | /// Append the content of node \p B into node \p A and remove \p B and |
154 | /// the edge between \p A and \p B from the graph. |
155 | virtual void mergeNodes(NodeType &A, NodeType &B) = 0; |
156 | |
157 | /// Given an instruction \p I return its associated ordinal number. |
158 | size_t getOrdinal(Instruction &I) { |
159 | assert(InstOrdinalMap.contains(&I) && |
160 | "No ordinal computed for this instruction." ); |
161 | return InstOrdinalMap[&I]; |
162 | } |
163 | |
164 | /// Given a node \p N return its associated ordinal number. |
165 | size_t getOrdinal(NodeType &N) { |
166 | assert(NodeOrdinalMap.contains(&N) && "No ordinal computed for this node." ); |
167 | return NodeOrdinalMap[&N]; |
168 | } |
169 | |
170 | /// Map types to map instructions to nodes used when populating the graph. |
171 | using InstToNodeMap = DenseMap<Instruction *, NodeType *>; |
172 | |
173 | /// Map Types to map instruction/nodes to an ordinal number. |
174 | using InstToOrdinalMap = DenseMap<Instruction *, size_t>; |
175 | using NodeToOrdinalMap = DenseMap<NodeType *, size_t>; |
176 | |
177 | /// Reference to the graph that gets built by a concrete implementation of |
178 | /// this builder. |
179 | GraphType &Graph; |
180 | |
181 | /// Dependence information used to create memory dependence edges in the |
182 | /// graph. |
183 | DependenceInfo &DI; |
184 | |
185 | /// The list of basic blocks to consider when building the graph. |
186 | const BasicBlockListType &BBList; |
187 | |
188 | /// A mapping from instructions to the corresponding nodes in the graph. |
189 | InstToNodeMap IMap; |
190 | |
191 | /// A mapping from each instruction to an ordinal number. This map is used to |
192 | /// populate the \p NodeOrdinalMap. |
193 | InstToOrdinalMap InstOrdinalMap; |
194 | |
195 | /// A mapping from nodes to an ordinal number. This map is used to sort nodes |
196 | /// in a pi-block based on program order. |
197 | NodeToOrdinalMap NodeOrdinalMap; |
198 | }; |
199 | |
200 | } // namespace llvm |
201 | |
202 | #endif // LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H |
203 | |