1193323Sed//=== llvm/Analysis/DominatorInternals.h - Dominator Calculation -*- C++ -*-==// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed 10193323Sed#ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H 11193323Sed#define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H 12193323Sed 13249423Sdim#include "llvm/ADT/SmallPtrSet.h" 14193323Sed#include "llvm/Analysis/Dominators.h" 15193323Sed 16193323Sed//===----------------------------------------------------------------------===// 17193323Sed// 18193323Sed// DominatorTree construction - This pass constructs immediate dominator 19193323Sed// information for a flow-graph based on the algorithm described in this 20193323Sed// document: 21193323Sed// 22193323Sed// A Fast Algorithm for Finding Dominators in a Flowgraph 23193323Sed// T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. 24193323Sed// 25218893Sdim// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns 26218893Sdim// out that the theoretically slower O(n*log(n)) implementation is actually 27218893Sdim// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs. 28193323Sed// 29193323Sed//===----------------------------------------------------------------------===// 30193323Sed 31193323Sednamespace llvm { 32193323Sed 33193323Sedtemplate<class GraphT> 34193323Sedunsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, 35193323Sed typename GraphT::NodeType* V, unsigned N) { 36193323Sed // This is more understandable as a recursive algorithm, but we can't use the 37193323Sed // recursive algorithm due to stack depth issues. Keep it here for 38193323Sed // documentation purposes. 39193323Sed#if 0 40193323Sed InfoRec &VInfo = DT.Info[DT.Roots[i]]; 41193323Sed VInfo.DFSNum = VInfo.Semi = ++N; 42193323Sed VInfo.Label = V; 43193323Sed 44193323Sed Vertex.push_back(V); // Vertex[n] = V; 45193323Sed 46193323Sed for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { 47193323Sed InfoRec &SuccVInfo = DT.Info[*SI]; 48193323Sed if (SuccVInfo.Semi == 0) { 49193323Sed SuccVInfo.Parent = V; 50193323Sed N = DTDFSPass(DT, *SI, N); 51193323Sed } 52193323Sed } 53193323Sed#else 54218893Sdim bool IsChildOfArtificialExit = (N != 0); 55193323Sed 56218893Sdim SmallVector<std::pair<typename GraphT::NodeType*, 57218893Sdim typename GraphT::ChildIteratorType>, 32> Worklist; 58193323Sed Worklist.push_back(std::make_pair(V, GraphT::child_begin(V))); 59193323Sed while (!Worklist.empty()) { 60193323Sed typename GraphT::NodeType* BB = Worklist.back().first; 61193323Sed typename GraphT::ChildIteratorType NextSucc = Worklist.back().second; 62193323Sed 63193323Sed typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo = 64193323Sed DT.Info[BB]; 65193323Sed 66193323Sed // First time we visited this BB? 67193323Sed if (NextSucc == GraphT::child_begin(BB)) { 68193323Sed BBInfo.DFSNum = BBInfo.Semi = ++N; 69193323Sed BBInfo.Label = BB; 70193323Sed 71193323Sed DT.Vertex.push_back(BB); // Vertex[n] = V; 72193323Sed 73218893Sdim if (IsChildOfArtificialExit) 74193323Sed BBInfo.Parent = 1; 75193323Sed 76218893Sdim IsChildOfArtificialExit = false; 77193323Sed } 78193323Sed 79193323Sed // store the DFS number of the current BB - the reference to BBInfo might 80193323Sed // get invalidated when processing the successors. 81193323Sed unsigned BBDFSNum = BBInfo.DFSNum; 82193323Sed 83193323Sed // If we are done with this block, remove it from the worklist. 84193323Sed if (NextSucc == GraphT::child_end(BB)) { 85193323Sed Worklist.pop_back(); 86193323Sed continue; 87193323Sed } 88193323Sed 89193323Sed // Increment the successor number for the next time we get to it. 90193323Sed ++Worklist.back().second; 91193323Sed 92193323Sed // Visit the successor next, if it isn't already visited. 93193323Sed typename GraphT::NodeType* Succ = *NextSucc; 94193323Sed 95193323Sed typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &SuccVInfo = 96193323Sed DT.Info[Succ]; 97193323Sed if (SuccVInfo.Semi == 0) { 98193323Sed SuccVInfo.Parent = BBDFSNum; 99193323Sed Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ))); 100193323Sed } 101193323Sed } 102193323Sed#endif 103193323Sed return N; 104193323Sed} 105193323Sed 106193323Sedtemplate<class GraphT> 107218893Sdimtypename GraphT::NodeType* 108218893SdimEval(DominatorTreeBase<typename GraphT::NodeType>& DT, 109218893Sdim typename GraphT::NodeType *VIn, unsigned LastLinked) { 110218893Sdim typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInInfo = 111218893Sdim DT.Info[VIn]; 112218893Sdim if (VInInfo.DFSNum < LastLinked) 113218893Sdim return VIn; 114218893Sdim 115218893Sdim SmallVector<typename GraphT::NodeType*, 32> Work; 116193323Sed SmallPtrSet<typename GraphT::NodeType*, 32> Visited; 117193323Sed 118218893Sdim if (VInInfo.Parent >= LastLinked) 119193323Sed Work.push_back(VIn); 120193323Sed 121193323Sed while (!Work.empty()) { 122193323Sed typename GraphT::NodeType* V = Work.back(); 123193323Sed typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo = 124193323Sed DT.Info[V]; 125218893Sdim typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Parent]; 126193323Sed 127193323Sed // Process Ancestor first 128218893Sdim if (Visited.insert(VAncestor) && VInfo.Parent >= LastLinked) { 129193323Sed Work.push_back(VAncestor); 130193323Sed continue; 131193323Sed } 132193323Sed Work.pop_back(); 133193323Sed 134193323Sed // Update VInfo based on Ancestor info 135218893Sdim if (VInfo.Parent < LastLinked) 136193323Sed continue; 137218893Sdim 138218893Sdim typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo = 139218893Sdim DT.Info[VAncestor]; 140193323Sed typename GraphT::NodeType* VAncestorLabel = VAInfo.Label; 141193323Sed typename GraphT::NodeType* VLabel = VInfo.Label; 142193323Sed if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi) 143193323Sed VInfo.Label = VAncestorLabel; 144218893Sdim VInfo.Parent = VAInfo.Parent; 145193323Sed } 146193323Sed 147218893Sdim return VInInfo.Label; 148193323Sed} 149193323Sed 150193323Sedtemplate<class FuncT, class NodeT> 151193323Sedvoid Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT, 152193323Sed FuncT& F) { 153193323Sed typedef GraphTraits<NodeT> GraphT; 154193323Sed 155193323Sed unsigned N = 0; 156193323Sed bool MultipleRoots = (DT.Roots.size() > 1); 157193323Sed if (MultipleRoots) { 158193323Sed typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo = 159193323Sed DT.Info[NULL]; 160193323Sed BBInfo.DFSNum = BBInfo.Semi = ++N; 161193323Sed BBInfo.Label = NULL; 162193323Sed 163193323Sed DT.Vertex.push_back(NULL); // Vertex[n] = V; 164193323Sed } 165193323Sed 166193323Sed // Step #1: Number blocks in depth-first order and initialize variables used 167193323Sed // in later stages of the algorithm. 168193323Sed for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size()); 169193323Sed i != e; ++i) 170193323Sed N = DFSPass<GraphT>(DT, DT.Roots[i], N); 171193323Sed 172193323Sed // it might be that some blocks did not get a DFS number (e.g., blocks of 173193323Sed // infinite loops). In these cases an artificial exit node is required. 174234353Sdim MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F)); 175193323Sed 176218893Sdim // When naively implemented, the Lengauer-Tarjan algorithm requires a separate 177218893Sdim // bucket for each vertex. However, this is unnecessary, because each vertex 178218893Sdim // is only placed into a single bucket (that of its semidominator), and each 179218893Sdim // vertex's bucket is processed before it is added to any bucket itself. 180218893Sdim // 181218893Sdim // Instead of using a bucket per vertex, we use a single array Buckets that 182218893Sdim // has two purposes. Before the vertex V with preorder number i is processed, 183218893Sdim // Buckets[i] stores the index of the first element in V's bucket. After V's 184218893Sdim // bucket is processed, Buckets[i] stores the index of the next element in the 185218893Sdim // bucket containing V, if any. 186218893Sdim SmallVector<unsigned, 32> Buckets; 187218893Sdim Buckets.resize(N + 1); 188218893Sdim for (unsigned i = 1; i <= N; ++i) 189218893Sdim Buckets[i] = i; 190218893Sdim 191193323Sed for (unsigned i = N; i >= 2; --i) { 192193323Sed typename GraphT::NodeType* W = DT.Vertex[i]; 193193323Sed typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo = 194193323Sed DT.Info[W]; 195193323Sed 196218893Sdim // Step #2: Implicitly define the immediate dominator of vertices 197218893Sdim for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) { 198218893Sdim typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; 199218893Sdim typename GraphT::NodeType* U = Eval<GraphT>(DT, V, i + 1); 200218893Sdim DT.IDoms[V] = DT.Info[U].Semi < i ? U : W; 201218893Sdim } 202193323Sed 203218893Sdim // Step #3: Calculate the semidominators of all vertices 204218893Sdim 205193323Sed // initialize the semi dominator to point to the parent node 206193323Sed WInfo.Semi = WInfo.Parent; 207210299Sed typedef GraphTraits<Inverse<NodeT> > InvTraits; 208210299Sed for (typename InvTraits::ChildIteratorType CI = 209210299Sed InvTraits::child_begin(W), 210210299Sed E = InvTraits::child_end(W); CI != E; ++CI) { 211210299Sed typename InvTraits::NodeType *N = *CI; 212210299Sed if (DT.Info.count(N)) { // Only if this predecessor is reachable! 213218893Sdim unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi; 214193323Sed if (SemiU < WInfo.Semi) 215193323Sed WInfo.Semi = SemiU; 216193323Sed } 217210299Sed } 218193323Sed 219218893Sdim // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is 220218893Sdim // necessarily parent(V). In this case, set idom(V) here and avoid placing 221218893Sdim // V into a bucket. 222218893Sdim if (WInfo.Semi == WInfo.Parent) { 223218893Sdim DT.IDoms[W] = DT.Vertex[WInfo.Parent]; 224218893Sdim } else { 225218893Sdim Buckets[i] = Buckets[WInfo.Semi]; 226218893Sdim Buckets[WInfo.Semi] = i; 227218893Sdim } 228218893Sdim } 229193323Sed 230218893Sdim if (N >= 1) { 231218893Sdim typename GraphT::NodeType* Root = DT.Vertex[1]; 232218893Sdim for (unsigned j = 1; Buckets[j] != 1; j = Buckets[j]) { 233218893Sdim typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; 234218893Sdim DT.IDoms[V] = Root; 235193323Sed } 236193323Sed } 237193323Sed 238193323Sed // Step #4: Explicitly define the immediate dominator of each vertex 239193323Sed for (unsigned i = 2; i <= N; ++i) { 240193323Sed typename GraphT::NodeType* W = DT.Vertex[i]; 241193323Sed typename GraphT::NodeType*& WIDom = DT.IDoms[W]; 242193323Sed if (WIDom != DT.Vertex[DT.Info[W].Semi]) 243193323Sed WIDom = DT.IDoms[WIDom]; 244193323Sed } 245193323Sed 246193323Sed if (DT.Roots.empty()) return; 247193323Sed 248193323Sed // Add a node for the root. This node might be the actual root, if there is 249193323Sed // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0) 250193323Sed // which postdominates all real exits if there are multiple exit blocks, or 251193323Sed // an infinite loop. 252193323Sed typename GraphT::NodeType* Root = !MultipleRoots ? DT.Roots[0] : 0; 253193323Sed 254193323Sed DT.DomTreeNodes[Root] = DT.RootNode = 255193323Sed new DomTreeNodeBase<typename GraphT::NodeType>(Root, 0); 256193323Sed 257193323Sed // Loop over all of the reachable blocks in the function... 258193323Sed for (unsigned i = 2; i <= N; ++i) { 259193323Sed typename GraphT::NodeType* W = DT.Vertex[i]; 260193323Sed 261193323Sed DomTreeNodeBase<typename GraphT::NodeType> *BBNode = DT.DomTreeNodes[W]; 262193323Sed if (BBNode) continue; // Haven't calculated this node yet? 263193323Sed 264193323Sed typename GraphT::NodeType* ImmDom = DT.getIDom(W); 265193323Sed 266193323Sed assert(ImmDom || DT.DomTreeNodes[NULL]); 267193323Sed 268193323Sed // Get or calculate the node for the immediate dominator 269193323Sed DomTreeNodeBase<typename GraphT::NodeType> *IDomNode = 270193323Sed DT.getNodeForBlock(ImmDom); 271193323Sed 272193323Sed // Add a new tree node for this BasicBlock, and link it as a child of 273193323Sed // IDomNode 274193323Sed DomTreeNodeBase<typename GraphT::NodeType> *C = 275193323Sed new DomTreeNodeBase<typename GraphT::NodeType>(W, IDomNode); 276193323Sed DT.DomTreeNodes[W] = IDomNode->addChild(C); 277193323Sed } 278193323Sed 279193323Sed // Free temporary memory used to construct idom's 280193323Sed DT.IDoms.clear(); 281193323Sed DT.Info.clear(); 282193323Sed std::vector<typename GraphT::NodeType*>().swap(DT.Vertex); 283193323Sed 284202375Srdivacky DT.updateDFSNumbers(); 285193323Sed} 286193323Sed 287193323Sed} 288193323Sed 289193323Sed#endif 290