X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDominatorInternals.h;h=c0f95cbd9b9b698a33adbc196526e3877e6d549b;hb=b09c146b116359616f6cbd4c8b3328607e00ff42;hp=cca0d502b69c393a036b81e35e14cca5154f41b3;hpb=d68a07650cdb2e18f18f362ba533459aa10e01b6;p=oota-llvm.git diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h index cca0d502b69..c0f95cbd9b9 100644 --- a/include/llvm/Analysis/DominatorInternals.h +++ b/include/llvm/Analysis/DominatorInternals.h @@ -10,8 +10,8 @@ #ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H #define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H -#include "llvm/Analysis/Dominators.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/Dominators.h" //===----------------------------------------------------------------------===// // @@ -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. // //===----------------------------------------------------------------------===// @@ -46,9 +42,6 @@ unsigned DFSPass(DominatorTreeBase& DT, 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,10 +51,10 @@ unsigned DFSPass(DominatorTreeBase& DT, } } #else - bool IsChilOfArtificialExit = (N != 0); + bool IsChildOfArtificialExit = (N != 0); - std::vector > Worklist; + SmallVector, 32> Worklist; Worklist.push_back(std::make_pair(V, GraphT::child_begin(V))); while (!Worklist.empty()) { typename GraphT::NodeType* BB = Worklist.back().first; @@ -76,14 +69,11 @@ unsigned DFSPass(DominatorTreeBase& DT, 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 (IsChilOfArtificialExit) + if (IsChildOfArtificialExit) BBInfo.Parent = 1; - IsChilOfArtificialExit = false; + IsChildOfArtificialExit = false; } // store the DFS number of the current BB - the reference to BBInfo might @@ -114,117 +104,47 @@ 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 DominatorTreeBase::InfoRec &VInVAInfo = - DT.Info[DT.Vertex[DT.Info[VIn].Ancestor]]; - 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 = DT.Vertex[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; - } -} - -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, - unsigned DFSNumV, typename GraphT::NodeType* W, - typename DominatorTreeBase::InfoRec &WInfo) { -#if !BALANCE_IDOM_TREE - // Higher-complexity but faster implementation - WInfo.Ancestor = DFSNumV; -#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]; - } + VInfo.Parent = VAInfo.Parent; } - 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 @@ -241,9 +161,6 @@ void Calculate(DominatorTreeBase::NodeType>& DT, BBInfo.Label = NULL; DT.Vertex.push_back(NULL); // Vertex[n] = V; - //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0 - //BBInfo[V].Child = 0; // Child[v] = 0 - BBInfo.Size = 1; // Size[v] = 1 } // Step #1: Number blocks in depth-first order and initialize variables used @@ -254,51 +171,67 @@ void Calculate(DominatorTreeBase::NodeType>& DT, // 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 != F.size()); + 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 - bool HasChildOutsideDFS = false; + // 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; - 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; + 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; } - else { - // if the child has no DFS number it is not post-dominated by any exit, - // and so is the current block. - HasChildOutsideDFS = true; - } } - // if some child has no DFS number it is not post-dominated by any exit, - // and so is the current block. - if (DT.isPostDominator() && HasChildOutsideDFS) - WInfo.Semi = 0; - - DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W); - - typename GraphT::NodeType* WParent = DT.Vertex[WInfo.Parent]; - Link(DT, WInfo.Parent, 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; } } @@ -347,15 +280,8 @@ void Calculate(DominatorTreeBase::NodeType>& DT, 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(); } }