Owen, Could you please add doxygen style comments for the new functions you are adding/moving? Its useful to have comments before the function describing what it does.
Thanks, Tanya On Sep 23, 2007, at 2:31 PM, Owen Anderson wrote: > Author: resistor > Date: Sun Sep 23 16:31:44 2007 > New Revision: 42248 > > URL: http://llvm.org/viewvc/llvm-project?rev=42248&view=rev > Log: > Factor the dominator tree calculation details out into > DominatorCalculation.h. This > change is not useful in and of itself, but it lays the groundwork > for combining > the dominator and postdominator implementations. > > Also, factor a few methods that are common to DominatorTree and > PostDominatorTree > into DominatorTreeBase. Again, this will make merging the two > calculation methods > simpler in the future. > > Added: > llvm/trunk/lib/VMCore/DominatorCalculation.h > Modified: > llvm/trunk/include/llvm/Analysis/Dominators.h > llvm/trunk/include/llvm/Analysis/PostDominators.h > llvm/trunk/lib/VMCore/Dominators.cpp > > Modified: llvm/trunk/include/llvm/Analysis/Dominators.h > URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/ > Analysis/Dominators.h?rev=42248&r1=42247&r2=42248&view=diff > > ====================================================================== > ======== > --- llvm/trunk/include/llvm/Analysis/Dominators.h (original) > +++ llvm/trunk/include/llvm/Analysis/Dominators.h Sun Sep 23 > 16:31:44 2007 > @@ -129,6 +129,7 @@ > > // Info - Collection of information used during the computation > of idoms. > DenseMap<BasicBlock*, InfoRec> Info; > + unsigned DFSPass(BasicBlock *V, unsigned N); > > public: > DominatorTreeBase(intptr_t ID, bool isPostDom) > @@ -278,6 +279,13 @@ > /// updateDFSNumbers - Assign In and Out numbers to the nodes > while walking > /// dominator tree in dfs order. > void updateDFSNumbers(); > + > + DomTreeNode *getNodeForBlock(BasicBlock *BB); > + > + inline BasicBlock *getIDom(BasicBlock *BB) const { > + DenseMap<BasicBlock*, BasicBlock*>::const_iterator I = > IDoms.find(BB); > + return I != IDoms.end() ? I->second : 0; > + } > }; > > //===------------------------------------- > @@ -304,17 +312,13 @@ > /// BB is split and now it has one successor. Update dominator > tree to > /// reflect this change. > void splitBlock(BasicBlock *BB); > + > private: > - void calculate(Function& F); > - DomTreeNode *getNodeForBlock(BasicBlock *BB); > - unsigned DFSPass(BasicBlock *V, unsigned N); > - void Compress(BasicBlock *V); > - BasicBlock *Eval(BasicBlock *v); > - void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); > - inline BasicBlock *getIDom(BasicBlock *BB) const { > - DenseMap<BasicBlock*, BasicBlock*>::const_iterator I = > IDoms.find(BB); > - return I != IDoms.end() ? I->second : 0; > - } > + friend void DTcalculate(DominatorTree& DT, Function& F); > + friend void DTCompress(DominatorTree& DT, BasicBlock *VIn); > + friend BasicBlock *DTEval(DominatorTree& DT, BasicBlock *v); > + friend void DTLink(DominatorTree& DT, BasicBlock *V, > + BasicBlock *W, InfoRec &WInfo); > }; > > //===------------------------------------- > > Modified: llvm/trunk/include/llvm/Analysis/PostDominators.h > URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/ > Analysis/PostDominators.h?rev=42248&r1=42247&r2=42248&view=diff > > ====================================================================== > ======== > --- llvm/trunk/include/llvm/Analysis/PostDominators.h (original) > +++ llvm/trunk/include/llvm/Analysis/PostDominators.h Sun Sep 23 > 16:31:44 2007 > @@ -38,16 +38,10 @@ > } > private: > void calculate(Function &F); > - DomTreeNode *getNodeForBlock(BasicBlock *BB); > unsigned DFSPass(BasicBlock *V, unsigned N); > void Compress(BasicBlock *V, InfoRec &VInfo); > BasicBlock *Eval(BasicBlock *V); > void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); > - > - inline BasicBlock *getIDom(BasicBlock *BB) const { > - DenseMap<BasicBlock*, BasicBlock*>::const_iterator I = > IDoms.find(BB); > - return I != IDoms.end() ? I->second : 0; > - } > }; > > > > Added: llvm/trunk/lib/VMCore/DominatorCalculation.h > URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/VMCore/ > DominatorCalculation.h?rev=42248&view=auto > > ====================================================================== > ======== > --- llvm/trunk/lib/VMCore/DominatorCalculation.h (added) > +++ llvm/trunk/lib/VMCore/DominatorCalculation.h Sun Sep 23 > 16:31:44 2007 > @@ -0,0 +1,213 @@ > +//==- llvm/VMCore/DominatorCalculation.h - Dominator Calculation - > *- C++ -*-==// > +// > +// 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. > +// > +// > ===------------------------------------------------------------------- > ---===// > + > +#ifndef LLVM_VMCORE_DOMINATOR_CALCULATION_H > +#define LLVM_VMCORE_DOMINATOR_CALCULATION_H > + > +#include "llvm/Analysis/Dominators.h" > + > +// > ===------------------------------------------------------------------- > ---===// > +// > +// DominatorTree construction - This pass constructs immediate > dominator > +// information for a flow-graph based on the algorithm described > in this > +// document: > +// > +// 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 > +// > +// > ===------------------------------------------------------------------- > ---===// > + > +namespace llvm { > + > +void DTCompress(DominatorTree& DT, BasicBlock *VIn) { > + > + std::vector<BasicBlock *> Work; > + SmallPtrSet<BasicBlock *, 32> Visited; > + BasicBlock *VInAncestor = DT.Info[VIn].Ancestor; > + DominatorTree::InfoRec &VInVAInfo = DT.Info[VInAncestor]; > + > + if (VInVAInfo.Ancestor != 0) > + Work.push_back(VIn); > + > + while (!Work.empty()) { > + BasicBlock *V = Work.back(); > + DominatorTree::InfoRec &VInfo = DT.Info[V]; > + BasicBlock *VAncestor = VInfo.Ancestor; > + DominatorTree::InfoRec &VAInfo = DT.Info[VAncestor]; > + > + // Process Ancestor first > + if (Visited.insert(VAncestor) && > + VAInfo.Ancestor != 0) { > + Work.push_back(VAncestor); > + continue; > + } > + Work.pop_back(); > + > + // Update VInfo based on Ancestor info > + if (VAInfo.Ancestor == 0) > + continue; > + BasicBlock *VAncestorLabel = VAInfo.Label; > + BasicBlock *VLabel = VInfo.Label; > + if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi) > + VInfo.Label = VAncestorLabel; > + VInfo.Ancestor = VAInfo.Ancestor; > + } > +} > + > +BasicBlock *DTEval(DominatorTree& DT, BasicBlock *V) { > + DominatorTree::InfoRec &VInfo = DT.Info[V]; > +#if !BALANCE_IDOM_TREE > + // Higher-complexity but faster implementation > + if (VInfo.Ancestor == 0) > + return V; > + DTCompress(DT, V); > + return VInfo.Label; > +#else > + // Lower-complexity but slower implementation > + if (VInfo.Ancestor == 0) > + return VInfo.Label; > + DTCompress(DT, V); > + BasicBlock *VLabel = VInfo.Label; > + > + BasicBlock *VAncestorLabel = DT.Info[VInfo.Ancestor].Label; > + if (DT.Info[VAncestorLabel].Semi >= DT.Info[VLabel].Semi) > + return VLabel; > + else > + return VAncestorLabel; > +#endif > +} > + > +void DTLink(DominatorTree& DT, BasicBlock *V, BasicBlock *W, > + DominatorTree::InfoRec &WInfo) { > +#if !BALANCE_IDOM_TREE > + // Higher-complexity but faster implementation > + WInfo.Ancestor = V; > +#else > + // Lower-complexity but slower implementation > + BasicBlock *WLabel = WInfo.Label; > + unsigned WLabelSemi = Info[WLabel].Semi; > + BasicBlock *S = W; > + InfoRec *SInfo = &Info[S]; > + > + BasicBlock *SChild = SInfo->Child; > + InfoRec *SChildInfo = &Info[SChild]; > + > + while (WLabelSemi < Info[SChildInfo->Label].Semi) { > + BasicBlock *SChildChild = SChildInfo->Child; > + if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) { > + SChildInfo->Ancestor = S; > + SInfo->Child = SChild = SChildChild; > + SChildInfo = &Info[SChild]; > + } else { > + SChildInfo->Size = SInfo->Size; > + S = SInfo->Ancestor = SChild; > + SInfo = SChildInfo; > + SChild = SChildChild; > + SChildInfo = &Info[SChild]; > + } > + } > + > + InfoRec &VInfo = 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 = &Info[S]; > + SInfo->Ancestor = V; > + S = SInfo->Child; > + } > +#endif > +} > + > +void DTcalculate(DominatorTree& DT, Function &F) { > + BasicBlock* Root = DT.Roots[0]; > + > + // Add a node for the root... > + DT.DomTreeNodes[Root] = DT.RootNode = new DomTreeNode(Root, 0); > + > + DT.Vertex.push_back(0); > + > + // Step #1: Number blocks in depth-first order and initialize > variables used > + // in later stages of the algorithm. > + unsigned N = DT.DFSPass(Root, 0); > + > + for (unsigned i = N; i >= 2; --i) { > + BasicBlock *W = DT.Vertex[i]; > + DominatorTree::InfoRec &WInfo = DT.Info[W]; > + > + // Step #2: Calculate the semidominators of all vertices > + for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != > E; ++PI) > + if (DT.Info.count(*PI)) { // Only if this predecessor is > reachable! > + unsigned SemiU = DT.Info[DTEval(DT, *PI)].Semi; > + if (SemiU < WInfo.Semi) > + WInfo.Semi = SemiU; > + } > + > + DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W); > + > + BasicBlock *WParent = WInfo.Parent; > + DTLink(DT, WParent, W, WInfo); > + > + // Step #3: Implicitly define the immediate dominator of vertices > + std::vector<BasicBlock*> &WParentBucket = DT.Info > [WParent].Bucket; > + while (!WParentBucket.empty()) { > + BasicBlock *V = WParentBucket.back(); > + WParentBucket.pop_back(); > + BasicBlock *U = DTEval(DT, V); > + DT.IDoms[V] = DT.Info[U].Semi < DT.Info[V].Semi ? U : WParent; > + } > + } > + > + // Step #4: Explicitly define the immediate dominator of each > vertex > + for (unsigned i = 2; i <= N; ++i) { > + BasicBlock *W = DT.Vertex[i]; > + BasicBlock *&WIDom = DT.IDoms[W]; > + if (WIDom != DT.Vertex[DT.Info[W].Semi]) > + WIDom = DT.IDoms[WIDom]; > + } > + > + // Loop over all of the reachable blocks in the function... > + for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) > + if (BasicBlock *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); > + } > + > + // Free temporary memory used to construct idom's > + DT.Info.clear(); > + DT.IDoms.clear(); > + std::vector<BasicBlock*>().swap(DT.Vertex); > + > + DT.updateDFSNumbers(); > +} > + > +} > +#endif > \ No newline at end of file > > Modified: llvm/trunk/lib/VMCore/Dominators.cpp > URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/VMCore/ > Dominators.cpp?rev=42248&r1=42247&r2=42248&view=diff > > ====================================================================== > ======== > --- llvm/trunk/lib/VMCore/Dominators.cpp (original) > +++ llvm/trunk/lib/VMCore/Dominators.cpp Sun Sep 23 16:31:44 2007 > @@ -23,6 +23,7 @@ > #include "llvm/ADT/SmallVector.h" > #include "llvm/Instructions.h" > #include "llvm/Support/Streams.h" > +#include "DominatorCalculation.h" > #include <algorithm> > using namespace llvm; > > @@ -43,20 +44,8 @@ > // DominatorTree Implementation > // > ===------------------------------------------------------------------- > ---===// > // > -// DominatorTree construction - This pass constructs immediate > dominator > -// information for a flow-graph based on the algorithm described > in this > -// document: > -// > -// 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 > +// Provide public access to DominatorTree information. > Implementation details > +// can be found in DominatorCalculation.h. > // > // > ===------------------------------------------------------------------- > ---===// > > @@ -64,6 +53,68 @@ > static RegisterPass<DominatorTree> > E("domtree", "Dominator Tree Construction", true); > > +unsigned DominatorTreeBase::DFSPass(BasicBlock *V, unsigned N) { > + // This is more understandable as a recursive algorithm, but we > can't use the > + // recursive algorithm due to stack depth issues. Keep it here for > + // documentation purposes. > +#if 0 > + InfoRec &VInfo = Info[Roots[i]]; > + 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 = Info[*SI]; > + if (SuccVInfo.Semi == 0) { > + SuccVInfo.Parent = V; > + N = DFSPass(*SI, N); > + } > + } > +#else > + std::vector<std::pair<BasicBlock*, unsigned> > Worklist; > + Worklist.push_back(std::make_pair(V, 0U)); > + while (!Worklist.empty()) { > + BasicBlock *BB = Worklist.back().first; > + unsigned NextSucc = Worklist.back().second; > + > + // First time we visited this BB? > + if (NextSucc == 0) { > + InfoRec &BBInfo = Info[BB]; > + BBInfo.Semi = ++N; > + BBInfo.Label = BB; > + > + 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 we are done with this block, remove it from the worklist. > + if (NextSucc == BB->getTerminator()->getNumSuccessors()) { > + Worklist.pop_back(); > + continue; > + } > + > + // Otherwise, increment the successor number for the next time > we get to it. > + ++Worklist.back().second; > + > + // Visit the successor next, if it isn't already visited. > + BasicBlock *Succ = BB->getTerminator()->getSuccessor(NextSucc); > + > + InfoRec &SuccVInfo = Info[Succ]; > + if (SuccVInfo.Semi == 0) { > + SuccVInfo.Parent = BB; > + Worklist.push_back(std::make_pair(Succ, 0U)); > + } > + } > +#endif > + return N; > +} > + > // NewBB is split and now it has one successor. Update dominator > tree to > // reflect this change. > void DominatorTree::splitBlock(BasicBlock *NewBB) { > @@ -146,243 +197,6 @@ > } > } > > -unsigned DominatorTree::DFSPass(BasicBlock *V, unsigned N) { > - // This is more understandable as a recursive algorithm, but we > can't use the > - // recursive algorithm due to stack depth issues. Keep it here for > - // documentation purposes. > -#if 0 > - InfoRec &VInfo = Info[Roots[i]]; > - 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 = Info[*SI]; > - if (SuccVInfo.Semi == 0) { > - SuccVInfo.Parent = V; > - N = DFSPass(*SI, N); > - } > - } > -#else > - std::vector<std::pair<BasicBlock*, unsigned> > Worklist; > - Worklist.push_back(std::make_pair(V, 0U)); > - while (!Worklist.empty()) { > - BasicBlock *BB = Worklist.back().first; > - unsigned NextSucc = Worklist.back().second; > - > - // First time we visited this BB? > - if (NextSucc == 0) { > - InfoRec &BBInfo = Info[BB]; > - BBInfo.Semi = ++N; > - BBInfo.Label = BB; > - > - 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 we are done with this block, remove it from the worklist. > - if (NextSucc == BB->getTerminator()->getNumSuccessors()) { > - Worklist.pop_back(); > - continue; > - } > - > - // Otherwise, increment the successor number for the next time > we get to it. > - ++Worklist.back().second; > - > - // Visit the successor next, if it isn't already visited. > - BasicBlock *Succ = BB->getTerminator()->getSuccessor(NextSucc); > - > - InfoRec &SuccVInfo = Info[Succ]; > - if (SuccVInfo.Semi == 0) { > - SuccVInfo.Parent = BB; > - Worklist.push_back(std::make_pair(Succ, 0U)); > - } > - } > -#endif > - return N; > -} > - > -void DominatorTree::Compress(BasicBlock *VIn) { > - > - std::vector<BasicBlock *> Work; > - SmallPtrSet<BasicBlock *, 32> Visited; > - BasicBlock *VInAncestor = Info[VIn].Ancestor; > - InfoRec &VInVAInfo = Info[VInAncestor]; > - > - if (VInVAInfo.Ancestor != 0) > - Work.push_back(VIn); > - > - while (!Work.empty()) { > - BasicBlock *V = Work.back(); > - InfoRec &VInfo = Info[V]; > - BasicBlock *VAncestor = VInfo.Ancestor; > - InfoRec &VAInfo = Info[VAncestor]; > - > - // Process Ancestor first > - if (Visited.insert(VAncestor) && > - VAInfo.Ancestor != 0) { > - Work.push_back(VAncestor); > - continue; > - } > - Work.pop_back(); > - > - // Update VInfo based on Ancestor info > - if (VAInfo.Ancestor == 0) > - continue; > - BasicBlock *VAncestorLabel = VAInfo.Label; > - BasicBlock *VLabel = VInfo.Label; > - if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) > - VInfo.Label = VAncestorLabel; > - VInfo.Ancestor = VAInfo.Ancestor; > - } > -} > - > -BasicBlock *DominatorTree::Eval(BasicBlock *V) { > - InfoRec &VInfo = Info[V]; > -#if !BALANCE_IDOM_TREE > - // Higher-complexity but faster implementation > - if (VInfo.Ancestor == 0) > - return V; > - Compress(V); > - return VInfo.Label; > -#else > - // Lower-complexity but slower implementation > - if (VInfo.Ancestor == 0) > - return VInfo.Label; > - Compress(V); > - BasicBlock *VLabel = VInfo.Label; > - > - BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label; > - if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi) > - return VLabel; > - else > - return VAncestorLabel; > -#endif > -} > - > -void DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec > &WInfo){ > -#if !BALANCE_IDOM_TREE > - // Higher-complexity but faster implementation > - WInfo.Ancestor = V; > -#else > - // Lower-complexity but slower implementation > - BasicBlock *WLabel = WInfo.Label; > - unsigned WLabelSemi = Info[WLabel].Semi; > - BasicBlock *S = W; > - InfoRec *SInfo = &Info[S]; > - > - BasicBlock *SChild = SInfo->Child; > - InfoRec *SChildInfo = &Info[SChild]; > - > - while (WLabelSemi < Info[SChildInfo->Label].Semi) { > - BasicBlock *SChildChild = SChildInfo->Child; > - if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) { > - SChildInfo->Ancestor = S; > - SInfo->Child = SChild = SChildChild; > - SChildInfo = &Info[SChild]; > - } else { > - SChildInfo->Size = SInfo->Size; > - S = SInfo->Ancestor = SChild; > - SInfo = SChildInfo; > - SChild = SChildChild; > - SChildInfo = &Info[SChild]; > - } > - } > - > - InfoRec &VInfo = 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 = &Info[S]; > - SInfo->Ancestor = V; > - S = SInfo->Child; > - } > -#endif > -} > - > -void DominatorTree::calculate(Function &F) { > - BasicBlock* Root = Roots[0]; > - > - // Add a node for the root... > - DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0); > - > - Vertex.push_back(0); > - > - // Step #1: Number blocks in depth-first order and initialize > variables used > - // in later stages of the algorithm. > - unsigned N = DFSPass(Root, 0); > - > - for (unsigned i = N; i >= 2; --i) { > - BasicBlock *W = Vertex[i]; > - InfoRec &WInfo = Info[W]; > - > - // Step #2: Calculate the semidominators of all vertices > - for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != > E; ++PI) > - if (Info.count(*PI)) { // Only if this predecessor is > reachable! > - unsigned SemiU = Info[Eval(*PI)].Semi; > - if (SemiU < WInfo.Semi) > - WInfo.Semi = SemiU; > - } > - > - Info[Vertex[WInfo.Semi]].Bucket.push_back(W); > - > - BasicBlock *WParent = WInfo.Parent; > - Link(WParent, W, WInfo); > - > - // Step #3: Implicitly define the immediate dominator of vertices > - std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket; > - while (!WParentBucket.empty()) { > - BasicBlock *V = WParentBucket.back(); > - WParentBucket.pop_back(); > - BasicBlock *U = Eval(V); > - IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent; > - } > - } > - > - // Step #4: Explicitly define the immediate dominator of each > vertex > - for (unsigned i = 2; i <= N; ++i) { > - BasicBlock *W = Vertex[i]; > - BasicBlock *&WIDom = IDoms[W]; > - if (WIDom != Vertex[Info[W].Semi]) > - WIDom = IDoms[WIDom]; > - } > - > - // Loop over all of the reachable blocks in the function... > - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) > - if (BasicBlock *ImmDom = getIDom(I)) { // Reachable block. > - DomTreeNode *BBNode = DomTreeNodes[I]; > - if (BBNode) continue; // Haven't calculated this node yet? > - > - // Get or calculate the node for the immediate dominator > - DomTreeNode *IDomNode = getNodeForBlock(ImmDom); > - > - // Add a new tree node for this BasicBlock, and link it as a > child of > - // IDomNode > - DomTreeNode *C = new DomTreeNode(I, IDomNode); > - DomTreeNodes[I] = IDomNode->addChild(C); > - } > - > - // Free temporary memory used to construct idom's > - Info.clear(); > - IDoms.clear(); > - std::vector<BasicBlock*>().swap(Vertex); > - > - updateDFSNumbers(); > -} > - > void DominatorTreeBase::updateDFSNumbers() { > unsigned DFSNum = 0; > > @@ -462,6 +276,21 @@ > RootNode = 0; > } > > +DomTreeNode *DominatorTreeBase::getNodeForBlock(BasicBlock *BB) { > + if (DomTreeNode *BBNode = DomTreeNodes[BB]) > + return BBNode; > + > + // Haven't calculated this node yet? Get or calculate the node > for the > + // immediate dominator. > + BasicBlock *IDom = getIDom(BB); > + DomTreeNode *IDomNode = getNodeForBlock(IDom); > + > + // Add a new tree node for this BasicBlock, and link it as a > child of > + // IDomNode > + DomTreeNode *C = new DomTreeNode(BB, IDomNode); > + return DomTreeNodes[BB] = IDomNode->addChild(C); > +} > + > /// findNearestCommonDominator - Find nearest common dominator > basic block > /// for basic block A and B. If there is no such block then return > NULL. > BasicBlock *DominatorTreeBase::findNearestCommonDominator > (BasicBlock *A, > @@ -525,21 +354,6 @@ > } > } > > -DomTreeNode *DominatorTree::getNodeForBlock(BasicBlock *BB) { > - if (DomTreeNode *BBNode = DomTreeNodes[BB]) > - return BBNode; > - > - // Haven't calculated this node yet? Get or calculate the node > for the > - // immediate dominator. > - BasicBlock *IDom = getIDom(BB); > - DomTreeNode *IDomNode = getNodeForBlock(IDom); > - > - // Add a new tree node for this BasicBlock, and link it as a > child of > - // IDomNode > - DomTreeNode *C = new DomTreeNode(BB, IDomNode); > - return DomTreeNodes[BB] = IDomNode->addChild(C); > -} > - > static std::ostream &operator<<(std::ostream &o, const DomTreeNode > *Node) { > if (Node->getBlock()) > WriteAsOperand(o, Node->getBlock(), false); > @@ -599,7 +413,7 @@ > bool DominatorTree::runOnFunction(Function &F) { > reset(); // Reset from the last time we were run... > Roots.push_back(&F.getEntryBlock()); > - calculate(F); > + DTcalculate(*this, F); > return false; > } > > > > _______________________________________________ > llvm-commits mailing list > llvm-commits@cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits