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