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 25 #ifndef LLVM_SUPPORT_GENERIC_DOM_TREE_CONSTRUCTION_H 26 #define LLVM_SUPPORT_GENERIC_DOM_TREE_CONSTRUCTION_H 27 28 #include "llvm/ADT/SmallPtrSet.h" 29 #include "llvm/Support/GenericDomTree.h" 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 128 if (Visited.insert(VAncestor) && VInfo.Parent >= LastLinked) { 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 = 159 DT.Info[nullptr]; 160 BBInfo.DFSNum = BBInfo.Semi = ++N; 161 BBInfo.Label = nullptr; 162 163 DT.Vertex.push_back(nullptr); // Vertex[n] = V; 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. 252 typename GraphT::NodeType* Root = !MultipleRoots ? DT.Roots[0] : nullptr; 253 254 DT.DomTreeNodes[Root] = DT.RootNode = 255 new DomTreeNodeBase<typename GraphT::NodeType>(Root, nullptr); 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 266 assert(ImmDom || DT.DomTreeNodes[nullptr]); 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 290
