]>
Commit | Line | Data |
---|---|---|
1a4d82fc | 1 | //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==// |
223e47cc LB |
2 | // |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
1a4d82fc JJ |
9 | /// \file |
10 | /// | |
11 | /// Generic dominator tree construction - This file provides routines to | |
12 | /// construct immediate dominator information for a flow-graph based on the | |
13 | /// algorithm described in this document: | |
14 | /// | |
15 | /// A Fast Algorithm for Finding Dominators in a Flowgraph | |
16 | /// T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. | |
17 | /// | |
18 | /// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns | |
19 | /// out that the theoretically slower O(n*log(n)) implementation is actually | |
20 | /// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs. | |
21 | /// | |
22 | //===----------------------------------------------------------------------===// | |
223e47cc | 23 | |
223e47cc | 24 | |
1a4d82fc JJ |
25 | #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H |
26 | #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H | |
223e47cc | 27 | |
1a4d82fc JJ |
28 | #include "llvm/ADT/SmallPtrSet.h" |
29 | #include "llvm/Support/GenericDomTree.h" | |
223e47cc LB |
30 | |
31 | namespace llvm { | |
32 | ||
33 | template<class GraphT> | |
34 | unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, | |
35 | typename GraphT::NodeType* V, unsigned N) { | |
36 | // This is more understandable as a recursive algorithm, but we can't use the | |
37 | // recursive algorithm due to stack depth issues. Keep it here for | |
38 | // documentation purposes. | |
39 | #if 0 | |
40 | InfoRec &VInfo = DT.Info[DT.Roots[i]]; | |
41 | VInfo.DFSNum = VInfo.Semi = ++N; | |
42 | VInfo.Label = V; | |
43 | ||
44 | Vertex.push_back(V); // Vertex[n] = V; | |
45 | ||
46 | for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { | |
47 | InfoRec &SuccVInfo = DT.Info[*SI]; | |
48 | if (SuccVInfo.Semi == 0) { | |
49 | SuccVInfo.Parent = V; | |
50 | N = DTDFSPass(DT, *SI, N); | |
51 | } | |
52 | } | |
53 | #else | |
54 | bool IsChildOfArtificialExit = (N != 0); | |
55 | ||
56 | SmallVector<std::pair<typename GraphT::NodeType*, | |
57 | typename GraphT::ChildIteratorType>, 32> Worklist; | |
58 | Worklist.push_back(std::make_pair(V, GraphT::child_begin(V))); | |
59 | while (!Worklist.empty()) { | |
60 | typename GraphT::NodeType* BB = Worklist.back().first; | |
61 | typename GraphT::ChildIteratorType NextSucc = Worklist.back().second; | |
62 | ||
63 | typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo = | |
64 | DT.Info[BB]; | |
65 | ||
66 | // First time we visited this BB? | |
67 | if (NextSucc == GraphT::child_begin(BB)) { | |
68 | BBInfo.DFSNum = BBInfo.Semi = ++N; | |
69 | BBInfo.Label = BB; | |
70 | ||
71 | DT.Vertex.push_back(BB); // Vertex[n] = V; | |
72 | ||
73 | if (IsChildOfArtificialExit) | |
74 | BBInfo.Parent = 1; | |
75 | ||
76 | IsChildOfArtificialExit = false; | |
77 | } | |
78 | ||
79 | // store the DFS number of the current BB - the reference to BBInfo might | |
80 | // get invalidated when processing the successors. | |
81 | unsigned BBDFSNum = BBInfo.DFSNum; | |
82 | ||
83 | // If we are done with this block, remove it from the worklist. | |
84 | if (NextSucc == GraphT::child_end(BB)) { | |
85 | Worklist.pop_back(); | |
86 | continue; | |
87 | } | |
88 | ||
89 | // Increment the successor number for the next time we get to it. | |
90 | ++Worklist.back().second; | |
91 | ||
92 | // Visit the successor next, if it isn't already visited. | |
93 | typename GraphT::NodeType* Succ = *NextSucc; | |
94 | ||
95 | typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &SuccVInfo = | |
96 | DT.Info[Succ]; | |
97 | if (SuccVInfo.Semi == 0) { | |
98 | SuccVInfo.Parent = BBDFSNum; | |
99 | Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ))); | |
100 | } | |
101 | } | |
102 | #endif | |
103 | return N; | |
104 | } | |
105 | ||
106 | template<class GraphT> | |
107 | typename GraphT::NodeType* | |
108 | Eval(DominatorTreeBase<typename GraphT::NodeType>& DT, | |
109 | typename GraphT::NodeType *VIn, unsigned LastLinked) { | |
110 | typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInInfo = | |
111 | DT.Info[VIn]; | |
112 | if (VInInfo.DFSNum < LastLinked) | |
113 | return VIn; | |
114 | ||
115 | SmallVector<typename GraphT::NodeType*, 32> Work; | |
116 | SmallPtrSet<typename GraphT::NodeType*, 32> Visited; | |
117 | ||
118 | if (VInInfo.Parent >= LastLinked) | |
119 | Work.push_back(VIn); | |
120 | ||
121 | while (!Work.empty()) { | |
122 | typename GraphT::NodeType* V = Work.back(); | |
123 | typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo = | |
124 | DT.Info[V]; | |
125 | typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Parent]; | |
126 | ||
127 | // Process Ancestor first | |
85aaf69f | 128 | if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) { |
223e47cc LB |
129 | Work.push_back(VAncestor); |
130 | continue; | |
131 | } | |
132 | Work.pop_back(); | |
133 | ||
134 | // Update VInfo based on Ancestor info | |
135 | if (VInfo.Parent < LastLinked) | |
136 | continue; | |
137 | ||
138 | typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo = | |
139 | DT.Info[VAncestor]; | |
140 | typename GraphT::NodeType* VAncestorLabel = VAInfo.Label; | |
141 | typename GraphT::NodeType* VLabel = VInfo.Label; | |
142 | if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi) | |
143 | VInfo.Label = VAncestorLabel; | |
144 | VInfo.Parent = VAInfo.Parent; | |
145 | } | |
146 | ||
147 | return VInInfo.Label; | |
148 | } | |
149 | ||
150 | template<class FuncT, class NodeT> | |
151 | void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT, | |
152 | FuncT& F) { | |
153 | typedef GraphTraits<NodeT> GraphT; | |
154 | ||
155 | unsigned N = 0; | |
156 | bool MultipleRoots = (DT.Roots.size() > 1); | |
157 | if (MultipleRoots) { | |
158 | typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo = | |
1a4d82fc | 159 | DT.Info[nullptr]; |
223e47cc | 160 | BBInfo.DFSNum = BBInfo.Semi = ++N; |
1a4d82fc | 161 | BBInfo.Label = nullptr; |
223e47cc | 162 | |
1a4d82fc | 163 | DT.Vertex.push_back(nullptr); // Vertex[n] = V; |
223e47cc LB |
164 | } |
165 | ||
166 | // Step #1: Number blocks in depth-first order and initialize variables used | |
167 | // in later stages of the algorithm. | |
168 | for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size()); | |
169 | i != e; ++i) | |
170 | N = DFSPass<GraphT>(DT, DT.Roots[i], N); | |
171 | ||
172 | // it might be that some blocks did not get a DFS number (e.g., blocks of | |
173 | // infinite loops). In these cases an artificial exit node is required. | |
174 | MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F)); | |
175 | ||
176 | // When naively implemented, the Lengauer-Tarjan algorithm requires a separate | |
177 | // bucket for each vertex. However, this is unnecessary, because each vertex | |
178 | // is only placed into a single bucket (that of its semidominator), and each | |
179 | // vertex's bucket is processed before it is added to any bucket itself. | |
180 | // | |
181 | // Instead of using a bucket per vertex, we use a single array Buckets that | |
182 | // has two purposes. Before the vertex V with preorder number i is processed, | |
183 | // Buckets[i] stores the index of the first element in V's bucket. After V's | |
184 | // bucket is processed, Buckets[i] stores the index of the next element in the | |
185 | // bucket containing V, if any. | |
186 | SmallVector<unsigned, 32> Buckets; | |
187 | Buckets.resize(N + 1); | |
188 | for (unsigned i = 1; i <= N; ++i) | |
189 | Buckets[i] = i; | |
190 | ||
191 | for (unsigned i = N; i >= 2; --i) { | |
192 | typename GraphT::NodeType* W = DT.Vertex[i]; | |
193 | typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo = | |
194 | DT.Info[W]; | |
195 | ||
196 | // Step #2: Implicitly define the immediate dominator of vertices | |
197 | for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) { | |
198 | typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; | |
199 | typename GraphT::NodeType* U = Eval<GraphT>(DT, V, i + 1); | |
200 | DT.IDoms[V] = DT.Info[U].Semi < i ? U : W; | |
201 | } | |
202 | ||
203 | // Step #3: Calculate the semidominators of all vertices | |
204 | ||
205 | // initialize the semi dominator to point to the parent node | |
206 | WInfo.Semi = WInfo.Parent; | |
207 | typedef GraphTraits<Inverse<NodeT> > InvTraits; | |
208 | for (typename InvTraits::ChildIteratorType CI = | |
209 | InvTraits::child_begin(W), | |
210 | E = InvTraits::child_end(W); CI != E; ++CI) { | |
211 | typename InvTraits::NodeType *N = *CI; | |
212 | if (DT.Info.count(N)) { // Only if this predecessor is reachable! | |
213 | unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi; | |
214 | if (SemiU < WInfo.Semi) | |
215 | WInfo.Semi = SemiU; | |
216 | } | |
217 | } | |
218 | ||
219 | // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is | |
220 | // necessarily parent(V). In this case, set idom(V) here and avoid placing | |
221 | // V into a bucket. | |
222 | if (WInfo.Semi == WInfo.Parent) { | |
223 | DT.IDoms[W] = DT.Vertex[WInfo.Parent]; | |
224 | } else { | |
225 | Buckets[i] = Buckets[WInfo.Semi]; | |
226 | Buckets[WInfo.Semi] = i; | |
227 | } | |
228 | } | |
229 | ||
230 | if (N >= 1) { | |
231 | typename GraphT::NodeType* Root = DT.Vertex[1]; | |
232 | for (unsigned j = 1; Buckets[j] != 1; j = Buckets[j]) { | |
233 | typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; | |
234 | DT.IDoms[V] = Root; | |
235 | } | |
236 | } | |
237 | ||
238 | // Step #4: Explicitly define the immediate dominator of each vertex | |
239 | for (unsigned i = 2; i <= N; ++i) { | |
240 | typename GraphT::NodeType* W = DT.Vertex[i]; | |
241 | typename GraphT::NodeType*& WIDom = DT.IDoms[W]; | |
242 | if (WIDom != DT.Vertex[DT.Info[W].Semi]) | |
243 | WIDom = DT.IDoms[WIDom]; | |
244 | } | |
245 | ||
246 | if (DT.Roots.empty()) return; | |
247 | ||
248 | // Add a node for the root. This node might be the actual root, if there is | |
249 | // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0) | |
250 | // which postdominates all real exits if there are multiple exit blocks, or | |
251 | // an infinite loop. | |
1a4d82fc | 252 | typename GraphT::NodeType* Root = !MultipleRoots ? DT.Roots[0] : nullptr; |
223e47cc LB |
253 | |
254 | DT.DomTreeNodes[Root] = DT.RootNode = | |
1a4d82fc | 255 | new DomTreeNodeBase<typename GraphT::NodeType>(Root, nullptr); |
223e47cc LB |
256 | |
257 | // Loop over all of the reachable blocks in the function... | |
258 | for (unsigned i = 2; i <= N; ++i) { | |
259 | typename GraphT::NodeType* W = DT.Vertex[i]; | |
260 | ||
261 | DomTreeNodeBase<typename GraphT::NodeType> *BBNode = DT.DomTreeNodes[W]; | |
262 | if (BBNode) continue; // Haven't calculated this node yet? | |
263 | ||
264 | typename GraphT::NodeType* ImmDom = DT.getIDom(W); | |
265 | ||
1a4d82fc | 266 | assert(ImmDom || DT.DomTreeNodes[nullptr]); |
223e47cc LB |
267 | |
268 | // Get or calculate the node for the immediate dominator | |
269 | DomTreeNodeBase<typename GraphT::NodeType> *IDomNode = | |
270 | DT.getNodeForBlock(ImmDom); | |
271 | ||
272 | // Add a new tree node for this BasicBlock, and link it as a child of | |
273 | // IDomNode | |
274 | DomTreeNodeBase<typename GraphT::NodeType> *C = | |
275 | new DomTreeNodeBase<typename GraphT::NodeType>(W, IDomNode); | |
276 | DT.DomTreeNodes[W] = IDomNode->addChild(C); | |
277 | } | |
278 | ||
279 | // Free temporary memory used to construct idom's | |
280 | DT.IDoms.clear(); | |
281 | DT.Info.clear(); | |
282 | std::vector<typename GraphT::NodeType*>().swap(DT.Vertex); | |
283 | ||
284 | DT.updateDFSNumbers(); | |
285 | } | |
286 | ||
287 | } | |
288 | ||
289 | #endif |