X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDominatorInternals.h;h=c0f95cbd9b9b698a33adbc196526e3877e6d549b;hb=b09c146b116359616f6cbd4c8b3328607e00ff42;hp=c3f81e66498bc758109ea7d4277637a571f0a8bb;hpb=4d6d5783d8f803a9ae1ad64b16643f7ddeacbc1b;p=oota-llvm.git diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h index c3f81e66498..c0f95cbd9b9 100644 --- a/include/llvm/Analysis/DominatorInternals.h +++ b/include/llvm/Analysis/DominatorInternals.h @@ -2,17 +2,17 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Owen Anderson and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H #define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H -#include "llvm/Analysis/Dominators.h" -#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/Dominators.h" + //===----------------------------------------------------------------------===// // // DominatorTree construction - This pass constructs immediate dominator @@ -22,13 +22,9 @@ // A Fast Algorithm for Finding Dominators in a Flowgraph // T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. // -// This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and -// LINK, but it turns out that the theoretically slower O(n*log(n)) -// implementation is actually faster than the "efficient" algorithm (even for -// large CFGs) because the constant overheads are substantially smaller. The -// lower-complexity version can be enabled with the following #define: -// -#define BALANCE_IDOM_TREE 0 +// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns +// out that the theoretically slower O(n*log(n)) implementation is actually +// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs. // //===----------------------------------------------------------------------===// @@ -42,13 +38,10 @@ unsigned DFSPass(DominatorTreeBase& DT, // documentation purposes. #if 0 InfoRec &VInfo = DT.Info[DT.Roots[i]]; - VInfo.Semi = ++N; + VInfo.DFSNum = VInfo.Semi = ++N; VInfo.Label = V; Vertex.push_back(V); // Vertex[n] = V; - //Info[V].Ancestor = 0; // Ancestor[n] = 0 - //Info[V].Child = 0; // Child[v] = 0 - VInfo.Size = 1; // Size[v] = 1 for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { InfoRec &SuccVInfo = DT.Info[*SI]; @@ -58,26 +51,35 @@ unsigned DFSPass(DominatorTreeBase& DT, } } #else - std::vector > Worklist; + bool IsChildOfArtificialExit = (N != 0); + + SmallVector, 32> Worklist; Worklist.push_back(std::make_pair(V, GraphT::child_begin(V))); while (!Worklist.empty()) { typename GraphT::NodeType* BB = Worklist.back().first; typename GraphT::ChildIteratorType NextSucc = Worklist.back().second; + typename DominatorTreeBase::InfoRec &BBInfo = + DT.Info[BB]; + // First time we visited this BB? if (NextSucc == GraphT::child_begin(BB)) { - typename DominatorTreeBase::InfoRec &BBInfo = - DT.Info[BB]; - BBInfo.Semi = ++N; + BBInfo.DFSNum = BBInfo.Semi = ++N; BBInfo.Label = BB; DT.Vertex.push_back(BB); // Vertex[n] = V; - //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0 - //BBInfo[V].Child = 0; // Child[v] = 0 - BBInfo.Size = 1; // Size[v] = 1 + + if (IsChildOfArtificialExit) + BBInfo.Parent = 1; + + IsChildOfArtificialExit = false; } - + + // store the DFS number of the current BB - the reference to BBInfo might + // get invalidated when processing the successors. + unsigned BBDFSNum = BBInfo.DFSNum; + // If we are done with this block, remove it from the worklist. if (NextSucc == GraphT::child_end(BB)) { Worklist.pop_back(); @@ -93,7 +95,7 @@ unsigned DFSPass(DominatorTreeBase& DT, typename DominatorTreeBase::InfoRec &SuccVInfo = DT.Info[Succ]; if (SuccVInfo.Semi == 0) { - SuccVInfo.Parent = BB; + SuccVInfo.Parent = BBDFSNum; Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ))); } } @@ -102,159 +104,134 @@ unsigned DFSPass(DominatorTreeBase& DT, } template -void Compress(DominatorTreeBase& DT, - typename GraphT::NodeType *VIn) { - std::vector Work; +typename GraphT::NodeType* +Eval(DominatorTreeBase& DT, + typename GraphT::NodeType *VIn, unsigned LastLinked) { + typename DominatorTreeBase::InfoRec &VInInfo = + DT.Info[VIn]; + if (VInInfo.DFSNum < LastLinked) + return VIn; + + SmallVector Work; SmallPtrSet Visited; - typename GraphT::NodeType* VInAncestor = DT.Info[VIn].Ancestor; - typename DominatorTreeBase::InfoRec &VInVAInfo = - DT.Info[VInAncestor]; - if (VInVAInfo.Ancestor != 0) + if (VInInfo.Parent >= LastLinked) Work.push_back(VIn); while (!Work.empty()) { typename GraphT::NodeType* V = Work.back(); typename DominatorTreeBase::InfoRec &VInfo = DT.Info[V]; - typename GraphT::NodeType* VAncestor = VInfo.Ancestor; - typename DominatorTreeBase::InfoRec &VAInfo = - DT.Info[VAncestor]; + typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Parent]; // Process Ancestor first - if (Visited.insert(VAncestor) && - VAInfo.Ancestor != 0) { + if (Visited.insert(VAncestor) && VInfo.Parent >= LastLinked) { Work.push_back(VAncestor); continue; } Work.pop_back(); // Update VInfo based on Ancestor info - if (VAInfo.Ancestor == 0) + if (VInfo.Parent < LastLinked) continue; + + typename DominatorTreeBase::InfoRec &VAInfo = + DT.Info[VAncestor]; typename GraphT::NodeType* VAncestorLabel = VAInfo.Label; typename GraphT::NodeType* VLabel = VInfo.Label; if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi) VInfo.Label = VAncestorLabel; - VInfo.Ancestor = VAInfo.Ancestor; + VInfo.Parent = VAInfo.Parent; } -} -template -typename GraphT::NodeType* Eval(DominatorTreeBase& DT, - typename GraphT::NodeType *V) { - typename DominatorTreeBase::InfoRec &VInfo = - DT.Info[V]; -#if !BALANCE_IDOM_TREE - // Higher-complexity but faster implementation - if (VInfo.Ancestor == 0) - return V; - Compress(DT, V); - return VInfo.Label; -#else - // Lower-complexity but slower implementation - if (VInfo.Ancestor == 0) - return VInfo.Label; - Compress(DT, V); - GraphT::NodeType* VLabel = VInfo.Label; - - GraphT::NodeType* VAncestorLabel = DT.Info[VInfo.Ancestor].Label; - if (DT.Info[VAncestorLabel].Semi >= DT.Info[VLabel].Semi) - return VLabel; - else - return VAncestorLabel; -#endif -} - -template -void Link(DominatorTreeBase& DT, - typename GraphT::NodeType* V, typename GraphT::NodeType* W, - typename DominatorTreeBase::InfoRec &WInfo) { -#if !BALANCE_IDOM_TREE - // Higher-complexity but faster implementation - WInfo.Ancestor = V; -#else - // Lower-complexity but slower implementation - GraphT::NodeType* WLabel = WInfo.Label; - unsigned WLabelSemi = DT.Info[WLabel].Semi; - GraphT::NodeType* S = W; - InfoRec *SInfo = &DT.Info[S]; - - GraphT::NodeType* SChild = SInfo->Child; - InfoRec *SChildInfo = &DT.Info[SChild]; - - while (WLabelSemi < DT.Info[SChildInfo->Label].Semi) { - GraphT::NodeType* SChildChild = SChildInfo->Child; - if (SInfo->Size+DT.Info[SChildChild].Size >= 2*SChildInfo->Size) { - SChildInfo->Ancestor = S; - SInfo->Child = SChild = SChildChild; - SChildInfo = &DT.Info[SChild]; - } else { - SChildInfo->Size = SInfo->Size; - S = SInfo->Ancestor = SChild; - SInfo = SChildInfo; - SChild = SChildChild; - SChildInfo = &DT.Info[SChild]; - } - } - - DominatorTreeBase::InfoRec &VInfo = DT.Info[V]; - SInfo->Label = WLabel; - - assert(V != W && "The optimization here will not work in this case!"); - unsigned WSize = WInfo.Size; - unsigned VSize = (VInfo.Size += WSize); - - if (VSize < 2*WSize) - std::swap(S, VInfo.Child); - - while (S) { - SInfo = &DT.Info[S]; - SInfo->Ancestor = V; - S = SInfo->Child; - } -#endif + return VInInfo.Label; } template void Calculate(DominatorTreeBase::NodeType>& DT, FuncT& F) { typedef GraphTraits GraphT; - + + unsigned N = 0; + bool MultipleRoots = (DT.Roots.size() > 1); + if (MultipleRoots) { + typename DominatorTreeBase::InfoRec &BBInfo = + DT.Info[NULL]; + BBInfo.DFSNum = BBInfo.Semi = ++N; + BBInfo.Label = NULL; + + DT.Vertex.push_back(NULL); // Vertex[n] = V; + } + // Step #1: Number blocks in depth-first order and initialize variables used // in later stages of the algorithm. - unsigned N = 0; - for (unsigned i = 0, e = DT.Roots.size(); i != e; ++i) + for (unsigned i = 0, e = static_cast(DT.Roots.size()); + i != e; ++i) N = DFSPass(DT, DT.Roots[i], N); + // it might be that some blocks did not get a DFS number (e.g., blocks of + // infinite loops). In these cases an artificial exit node is required. + MultipleRoots |= (DT.isPostDominator() && N != GraphTraits::size(&F)); + + // When naively implemented, the Lengauer-Tarjan algorithm requires a separate + // bucket for each vertex. However, this is unnecessary, because each vertex + // is only placed into a single bucket (that of its semidominator), and each + // vertex's bucket is processed before it is added to any bucket itself. + // + // Instead of using a bucket per vertex, we use a single array Buckets that + // has two purposes. Before the vertex V with preorder number i is processed, + // Buckets[i] stores the index of the first element in V's bucket. After V's + // bucket is processed, Buckets[i] stores the index of the next element in the + // bucket containing V, if any. + SmallVector Buckets; + Buckets.resize(N + 1); + for (unsigned i = 1; i <= N; ++i) + Buckets[i] = i; + for (unsigned i = N; i >= 2; --i) { typename GraphT::NodeType* W = DT.Vertex[i]; typename DominatorTreeBase::InfoRec &WInfo = DT.Info[W]; - // Step #2: Calculate the semidominators of all vertices - for (typename GraphTraits >::ChildIteratorType CI = - GraphTraits >::child_begin(W), - E = GraphTraits >::child_end(W); CI != E; ++CI) - if (DT.Info.count(*CI)) { // Only if this predecessor is reachable! - unsigned SemiU = DT.Info[Eval(DT, *CI)].Semi; + // Step #2: Implicitly define the immediate dominator of vertices + for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) { + typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; + typename GraphT::NodeType* U = Eval(DT, V, i + 1); + DT.IDoms[V] = DT.Info[U].Semi < i ? U : W; + } + + // Step #3: Calculate the semidominators of all vertices + + // initialize the semi dominator to point to the parent node + WInfo.Semi = WInfo.Parent; + typedef GraphTraits > InvTraits; + for (typename InvTraits::ChildIteratorType CI = + InvTraits::child_begin(W), + E = InvTraits::child_end(W); CI != E; ++CI) { + typename InvTraits::NodeType *N = *CI; + if (DT.Info.count(N)) { // Only if this predecessor is reachable! + unsigned SemiU = DT.Info[Eval(DT, N, i + 1)].Semi; if (SemiU < WInfo.Semi) WInfo.Semi = SemiU; } + } - DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W); - - typename GraphT::NodeType* WParent = WInfo.Parent; - Link(DT, WParent, W, WInfo); + // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is + // necessarily parent(V). In this case, set idom(V) here and avoid placing + // V into a bucket. + if (WInfo.Semi == WInfo.Parent) { + DT.IDoms[W] = DT.Vertex[WInfo.Parent]; + } else { + Buckets[i] = Buckets[WInfo.Semi]; + Buckets[WInfo.Semi] = i; + } + } - // Step #3: Implicitly define the immediate dominator of vertices - std::vector &WParentBucket = - DT.Info[WParent].Bucket; - while (!WParentBucket.empty()) { - typename GraphT::NodeType* V = WParentBucket.back(); - WParentBucket.pop_back(); - typename GraphT::NodeType* U = Eval(DT, V); - DT.IDoms[V] = DT.Info[U].Semi < DT.Info[V].Semi ? U : WParent; + if (N >= 1) { + typename GraphT::NodeType* Root = DT.Vertex[1]; + for (unsigned j = 1; Buckets[j] != 1; j = Buckets[j]) { + typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; + DT.IDoms[V] = Root; } } @@ -265,45 +242,46 @@ void Calculate(DominatorTreeBase::NodeType>& DT, if (WIDom != DT.Vertex[DT.Info[W].Semi]) WIDom = DT.IDoms[WIDom]; } - + if (DT.Roots.empty()) return; - + // Add a node for the root. This node might be the actual root, if there is // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0) - // which postdominates all real exits if there are multiple exit blocks. - typename GraphT::NodeType* Root = DT.Roots.size() == 1 ? DT.Roots[0] - : 0; - DT.DomTreeNodes[Root] = DT.RootNode = new DomTreeNode(Root, 0); - + // which postdominates all real exits if there are multiple exit blocks, or + // an infinite loop. + typename GraphT::NodeType* Root = !MultipleRoots ? DT.Roots[0] : 0; + + DT.DomTreeNodes[Root] = DT.RootNode = + new DomTreeNodeBase(Root, 0); + // Loop over all of the reachable blocks in the function... - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) - if (typename GraphT::NodeType* ImmDom = DT.getIDom(I)) { - // Reachable block. - DomTreeNode *BBNode = DT.DomTreeNodes[I]; - if (BBNode) continue; // Haven't calculated this node yet? - - // Get or calculate the node for the immediate dominator - DomTreeNode *IDomNode = DT.getNodeForBlock(ImmDom); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - DomTreeNode *C = new DomTreeNode(I, IDomNode); - DT.DomTreeNodes[I] = IDomNode->addChild(C); - } - + for (unsigned i = 2; i <= N; ++i) { + typename GraphT::NodeType* W = DT.Vertex[i]; + + DomTreeNodeBase *BBNode = DT.DomTreeNodes[W]; + if (BBNode) continue; // Haven't calculated this node yet? + + typename GraphT::NodeType* ImmDom = DT.getIDom(W); + + assert(ImmDom || DT.DomTreeNodes[NULL]); + + // Get or calculate the node for the immediate dominator + DomTreeNodeBase *IDomNode = + DT.getNodeForBlock(ImmDom); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + DomTreeNodeBase *C = + new DomTreeNodeBase(W, IDomNode); + DT.DomTreeNodes[W] = IDomNode->addChild(C); + } + // Free temporary memory used to construct idom's DT.IDoms.clear(); DT.Info.clear(); std::vector().swap(DT.Vertex); - - // FIXME: This does not work on PostDomTrees. It seems likely that this is - // due to an error in the algorithm for post-dominators. This really should - // be investigated and fixed at some point. - // DT.updateDFSNumbers(); - - // Start out with the DFS numbers being invalid. Let them be computed if - // demanded. - DT.DFSInfoValid = false; + + DT.updateDFSNumbers(); } }