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> 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 * 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> 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
