From 3dc6776b338f81e2d47daa42cc12c9f91053043d Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Sun, 15 Apr 2007 08:47:27 +0000 Subject: [PATCH] Remove ImmediateDominator analysis. The same information can be obtained from DomTree. A lot of code for constructing ImmediateDominator is now folded into DomTree construction. This is part of the ongoing work for PR217. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36063 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/Dominators.h | 155 ++++--------------- include/llvm/Analysis/PostDominators.h | 46 ++---- include/llvm/LinkAllPasses.h | 1 - lib/Analysis/PostDominators.cpp | 89 +++++------ lib/Transforms/Scalar/LoopStrengthReduce.cpp | 1 - lib/Transforms/Utils/BreakCriticalEdges.cpp | 24 --- lib/Transforms/Utils/LoopSimplify.cpp | 26 ---- lib/VMCore/Dominators.cpp | 134 ++++++---------- 8 files changed, 132 insertions(+), 344 deletions(-) diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 6826b942548..c948a5fc7e8 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -8,13 +8,11 @@ //===----------------------------------------------------------------------===// // // This file defines the following classes: -// 1. ImmediateDominators: Calculates and holds a mapping between BasicBlocks -// and their immediate dominator. -// 2. DominatorTree: Represent the ImmediateDominator as an explicit tree +// 1. DominatorTree: Represent the ImmediateDominator as an explicit tree // structure. -// 3. ETForest: Efficient data structure for dominance comparisons and +// 2. ETForest: Efficient data structure for dominance comparisons and // nearest-common-ancestor queries. -// 4. DominanceFrontier: Calculate and hold the dominance frontier for a +// 3. DominanceFrontier: Calculate and hold the dominance frontier for a // function. // // These data structures are listed in increasing order of complexity. It @@ -58,135 +56,37 @@ public: bool isPostDominator() const { return IsPostDominators; } }; - //===----------------------------------------------------------------------===// -/// ImmediateDominators - Calculate the immediate dominator for each node in a -/// function. +/// DominatorTree - Calculate the immediate dominator tree for a function. /// -class ImmediateDominatorsBase : public DominatorBase { +class DominatorTreeBase : public DominatorBase { +public: + class Node; protected: - struct InfoRec { + std::map Nodes; + void reset(); + typedef std::map NodeMapType; + + Node *RootNode; + + struct InfoRec { unsigned Semi; unsigned Size; BasicBlock *Label, *Parent, *Child, *Ancestor; - + std::vector Bucket; - + InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){} }; - + std::map IDoms; // Vertex - Map the DFS number to the BasicBlock* std::vector Vertex; - + // Info - Collection of information used during the computation of idoms. std::map Info; -public: - ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {} - - virtual void releaseMemory() { IDoms.clear(); } - // Accessor interface: - typedef std::map IDomMapType; - typedef IDomMapType::const_iterator const_iterator; - inline const_iterator begin() const { return IDoms.begin(); } - inline const_iterator end() const { return IDoms.end(); } - inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);} - - /// operator[] - Return the idom for the specified basic block. The start - /// node returns null, because it does not have an immediate dominator. - /// - inline BasicBlock *operator[](BasicBlock *BB) const { - return get(BB); - } - - /// dominates - Return true if A dominates B. - /// - bool dominates(BasicBlock *A, BasicBlock *B) const; - - /// properlyDominates - Return true if A dominates B and A != B. - /// - bool properlyDominates(BasicBlock *A, BasicBlock *B) const { - return A != B || properlyDominates(A, B); - } - - /// get() - Synonym for operator[]. - /// - inline BasicBlock *get(BasicBlock *BB) const { - std::map::const_iterator I = IDoms.find(BB); - return I != IDoms.end() ? I->second : 0; - } - - //===--------------------------------------------------------------------===// - // API to update Immediate(Post)Dominators information based on modifications - // to the CFG... - - /// addNewBlock - Add a new block to the CFG, with the specified immediate - /// dominator. - /// - void addNewBlock(BasicBlock *BB, BasicBlock *IDom) { - assert(get(BB) == 0 && "BasicBlock already in idom info!"); - IDoms[BB] = IDom; - } - - /// setImmediateDominator - Update the immediate dominator information to - /// change the current immediate dominator for the specified block to another - /// block. This method requires that BB already have an IDom, otherwise just - /// use addNewBlock. - /// - void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) { - assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!"); - IDoms[BB] = NewIDom; - } - - /// print - Convert to human readable form - /// - virtual void print(std::ostream &OS, const Module* = 0) const; - void print(std::ostream *OS, const Module* M = 0) const { - if (OS) print(*OS, M); - } -}; - -//===------------------------------------- -/// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase -/// that is used to compute a normal immediate dominator set. -/// -class ImmediateDominators : public ImmediateDominatorsBase { -public: - ImmediateDominators() : ImmediateDominatorsBase(false) {} - - BasicBlock *getRoot() const { - assert(Roots.size() == 1 && "Should always have entry node!"); - return Roots[0]; - } - - virtual bool runOnFunction(Function &F); - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - } - -private: - unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N); - void Compress(BasicBlock *V, InfoRec &VInfo); - BasicBlock *Eval(BasicBlock *v); - void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); -}; - - -//===----------------------------------------------------------------------===// -/// DominatorTree - Calculate the immediate dominator tree for a function. -/// -class DominatorTreeBase : public DominatorBase { -public: - class Node; -protected: - std::map Nodes; - void reset(); - typedef std::map NodeMapType; - - Node *RootNode; public: class Node { friend class DominatorTree; @@ -313,21 +213,22 @@ public: return Roots[0]; } - virtual bool runOnFunction(Function &F) { - reset(); // Reset from the last time we were run... - ImmediateDominators &ID = getAnalysis(); - Roots = ID.getRoots(); - calculate(ID); - return false; - } + virtual bool runOnFunction(Function &F); virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - AU.addRequired(); } private: - void calculate(const ImmediateDominators &ID); + void calculate(Function& F); Node *getNodeForBlock(BasicBlock *BB); + unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, 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 { + std::map::const_iterator I = IDoms.find(BB); + return I != IDoms.end() ? I->second : 0; + } }; //===------------------------------------- diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h index aea901374ed..4997f93d09e 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -18,26 +18,6 @@ namespace llvm { -//===------------------------------------- -/// ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase -/// that is used to compute a normal immediate dominator set. -/// -struct ImmediatePostDominators : public ImmediateDominatorsBase { - ImmediatePostDominators() : ImmediateDominatorsBase(false) {} - - virtual bool runOnFunction(Function &F); - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - } - -private: - unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N); - void Compress(BasicBlock *V, InfoRec &VInfo); - BasicBlock *Eval(BasicBlock *v); - void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); -}; - /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to /// compute the a post-dominator tree. /// @@ -46,19 +26,25 @@ struct PostDominatorTree : public DominatorTreeBase { virtual bool runOnFunction(Function &F) { reset(); // Reset from the last time we were run... - ImmediatePostDominators &IPD = getAnalysis(); - Roots = IPD.getRoots(); - calculate(IPD); + calculate(F); return false; } virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - AU.addRequired(); } private: - void calculate(const ImmediatePostDominators &IPD); + void calculate(Function &F); Node *getNodeForBlock(BasicBlock *BB); + unsigned DFSPass(BasicBlock *V, InfoRec &VInfo,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 { + std::map::const_iterator I = IDoms.find(BB); + return I != IDoms.end() ? I->second : 0; + } }; @@ -69,18 +55,18 @@ struct PostETForest : public ETForestBase { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - AU.addRequired(); + AU.addRequired(); } virtual bool runOnFunction(Function &F) { reset(); // Reset from the last time we were run... - ImmediatePostDominators &ID = getAnalysis(); - Roots = ID.getRoots(); - calculate(ID); + PostDominatorTree &DT = getAnalysis(); + Roots = DT.getRoots(); + calculate(DT); return false; } - void calculate(const ImmediatePostDominators &ID); + void calculate(const PostDominatorTree &DT); ETNode *getNodeForBlock(BasicBlock *BB); }; diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index 7481c820251..f13104b6922 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -113,7 +113,6 @@ namespace { (void) llvm::createCodeGenPreparePass(); (void)new llvm::IntervalPartition(); - (void)new llvm::ImmediateDominators(); (void)new llvm::FindUsedTypes(); (void)new llvm::ScalarEvolution(); ((llvm::Function*)0)->viewCFGOnly(); diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp index 24399405fc9..7351ed7a6ab 100644 --- a/lib/Analysis/PostDominators.cpp +++ b/lib/Analysis/PostDominators.cpp @@ -19,13 +19,13 @@ using namespace llvm; //===----------------------------------------------------------------------===// -// ImmediatePostDominators Implementation +// PostDominatorTree Implementation //===----------------------------------------------------------------------===// -static RegisterPass -D("postidom", "Immediate Post-Dominators Construction", true); +static RegisterPass +F("postdomtree", "Post-Dominator Tree Construction", true); -unsigned ImmediatePostDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, +unsigned PostDominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N) { std::vector > workStack; std::set visited; @@ -73,7 +73,7 @@ unsigned ImmediatePostDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, return N; } -void ImmediatePostDominators::Compress(BasicBlock *V, InfoRec &VInfo) { +void PostDominatorTree::Compress(BasicBlock *V, InfoRec &VInfo) { BasicBlock *VAncestor = VInfo.Ancestor; InfoRec &VAInfo = Info[VAncestor]; if (VAInfo.Ancestor == 0) @@ -89,7 +89,7 @@ void ImmediatePostDominators::Compress(BasicBlock *V, InfoRec &VInfo) { VInfo.Ancestor = VAInfo.Ancestor; } -BasicBlock *ImmediatePostDominators::Eval(BasicBlock *V) { +BasicBlock *PostDominatorTree::Eval(BasicBlock *V) { InfoRec &VInfo = Info[V]; // Higher-complexity but faster implementation @@ -99,16 +99,13 @@ BasicBlock *ImmediatePostDominators::Eval(BasicBlock *V) { return VInfo.Label; } -void ImmediatePostDominators::Link(BasicBlock *V, BasicBlock *W, +void PostDominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo) { // Higher-complexity but faster implementation WInfo.Ancestor = V; } -bool ImmediatePostDominators::runOnFunction(Function &F) { - IDoms.clear(); // Reset from the last time we were run... - Roots.clear(); - +void PostDominatorTree::calculate(Function &F) { // Step #0: Scan the function looking for the root nodes of the post-dominance // relationships. These blocks, which have no successors, end with return and // unwind instructions. @@ -159,35 +156,6 @@ bool ImmediatePostDominators::runOnFunction(Function &F) { WIDom = IDoms[WIDom]; } - // Free temporary memory used to construct idom's - Info.clear(); - std::vector().swap(Vertex); - - return false; -} - -//===----------------------------------------------------------------------===// -// PostDominatorTree Implementation -//===----------------------------------------------------------------------===// - -static RegisterPass -F("postdomtree", "Post-Dominator Tree Construction", true); - -DominatorTreeBase::Node *PostDominatorTree::getNodeForBlock(BasicBlock *BB) { - Node *&BBNode = Nodes[BB]; - if (BBNode) return BBNode; - - // Haven't calculated this node yet? Get or calculate the node for the - // immediate postdominator. - BasicBlock *IPDom = getAnalysis()[BB]; - Node *IPDomNode = getNodeForBlock(IPDom); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - return BBNode = IPDomNode->addChild(new Node(BB, IPDomNode)); -} - -void PostDominatorTree::calculate(const ImmediatePostDominators &IPD) { if (Roots.empty()) return; // Add a node for the root. This node might be the actual root, if there is @@ -196,10 +164,9 @@ void PostDominatorTree::calculate(const ImmediatePostDominators &IPD) { BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0; Nodes[Root] = RootNode = new Node(Root, 0); - Function *F = Roots[0]->getParent(); // Loop over all of the reachable blocks in the function... - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) - if (BasicBlock *ImmPostDom = IPD.get(I)) { // Reachable block. + for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) + if (BasicBlock *ImmPostDom = getIDom(I)) { // Reachable block. Node *&BBNode = Nodes[I]; if (!BBNode) { // Haven't calculated this node yet? // Get or calculate the node for the immediate dominator @@ -210,6 +177,26 @@ void PostDominatorTree::calculate(const ImmediatePostDominators &IPD) { BBNode = IPDomNode->addChild(new Node(I, IPDomNode)); } } + + // Free temporary memory used to construct idom's + IDoms.clear(); + Info.clear(); + std::vector().swap(Vertex); +} + + +DominatorTreeBase::Node *PostDominatorTree::getNodeForBlock(BasicBlock *BB) { + Node *&BBNode = Nodes[BB]; + if (BBNode) return BBNode; + + // Haven't calculated this node yet? Get or calculate the node for the + // immediate postdominator. + BasicBlock *IPDom = getIDom(BB); + Node *IPDomNode = getNodeForBlock(IPDom); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + return BBNode = IPDomNode->addChild(new Node(BB, IPDomNode)); } //===----------------------------------------------------------------------===// @@ -225,13 +212,15 @@ ETNode *PostETForest::getNodeForBlock(BasicBlock *BB) { // Haven't calculated this node yet? Get or calculate the node for the // immediate dominator. - BasicBlock *IDom = getAnalysis()[BB]; + PostDominatorTree::Node *node = getAnalysis().getNode(BB); // If we are unreachable, we may not have an immediate dominator. - if (!IDom) + if (!node) + return 0; + else if (!node->getIDom()) return BBNode = new ETNode(BB); else { - ETNode *IDomNode = getNodeForBlock(IDom); + ETNode *IDomNode = getNodeForBlock(node->getIDom()->getBlock()); // Add a new tree node for this BasicBlock, and link it as a child of // IDomNode @@ -241,7 +230,7 @@ ETNode *PostETForest::getNodeForBlock(BasicBlock *BB) { } } -void PostETForest::calculate(const ImmediatePostDominators &ID) { +void PostETForest::calculate(const PostDominatorTree &DT) { for (unsigned i = 0, e = Roots.size(); i != e; ++i) Nodes[Roots[i]] = new ETNode(Roots[i]); // Add a node for the root @@ -253,9 +242,9 @@ void PostETForest::calculate(const ImmediatePostDominators &ID) { ETNode *&BBNode = Nodes[BB]; if (!BBNode) { ETNode *IDomNode = NULL; - - if (ID.get(BB)) - IDomNode = getNodeForBlock(ID.get(BB)); + PostDominatorTree::Node *node = DT.getNode(BB); + if (node && node->getIDom()) + IDomNode = getNodeForBlock(node->getIDom()->getBlock()); // Add a new ETNode for this BasicBlock, and set it's parent // to it's immediate dominator. diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 332ddfa488e..38cfd91fe1b 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -154,7 +154,6 @@ namespace { AU.addPreservedID(LoopSimplifyID); AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp index 2f91e575908..2cf2ecd3e96 100644 --- a/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -38,7 +38,6 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved(); - AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -196,29 +195,6 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P, if (NewBBDominatesDestBB) EF->setImmediateDominator(DestBB, NewBB); } - - // Should we update ImmediateDominator information? - if (ImmediateDominators *ID = P->getAnalysisToUpdate()) { - // Only do this if TIBB is reachable. - if (ID->get(TIBB) || &TIBB->getParent()->getEntryBlock() == TIBB) { - // TIBB is the new immediate dominator for NewBB. - ID->addNewBlock(NewBB, TIBB); - - // If NewBBDominatesDestBB hasn't been computed yet, do so with ID. - if (!OtherPreds.empty()) { - while (!OtherPreds.empty() && NewBBDominatesDestBB) { - NewBBDominatesDestBB = ID->dominates(DestBB, OtherPreds.back()); - OtherPreds.pop_back(); - } - OtherPreds.clear(); - } - - // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it - // doesn't dominate anything. - if (NewBBDominatesDestBB) - ID->setImmediateDominator(DestBB, NewBB); - } - } // Should we update DominatorTree information? if (DominatorTree *DT = P->getAnalysisToUpdate()) { diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index 75991688b10..7d34b95cba5 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -68,7 +68,6 @@ namespace { AU.addRequired(); AU.addPreserved(); - AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -749,31 +748,6 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, } BasicBlock *NewBBIDom = 0; - - // Update immediate dominator information if we have it. - if (ImmediateDominators *ID = getAnalysisToUpdate()) { - unsigned i = 0; - for (i = 0; i < PredBlocks.size(); ++i) - if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i])) { - NewBBIDom = PredBlocks[i]; - break; - } - assert(i != PredBlocks.size() && "No reachable preds?"); - for (i = i + 1; i < PredBlocks.size(); ++i) { - if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i])) - NewBBIDom = ETF.nearestCommonDominator(NewBBIDom, PredBlocks[i]); - } - assert(NewBBIDom && "No immediate dominator found??"); - - // Set the immediate dominator now... - ID->addNewBlock(NewBB, NewBBIDom); - - // If NewBB strictly dominates other blocks, we need to update their idom's - // now. The only block that need adjustment is the NewBBSucc block, whose - // idom should currently be set to PredBlocks[0]. - if (NewBBDominatesNewBBSucc) - ID->setImmediateDominator(NewBBSucc, NewBB); - } // Update DominatorTree information if it is active. if (DominatorTree *DT = getAnalysisToUpdate()) { diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 0959b07b47a..9685ed9efae 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -24,11 +24,24 @@ #include using namespace llvm; +namespace llvm { +static std::ostream &operator<<(std::ostream &o, + const std::set &BBs) { + for (std::set::const_iterator I = BBs.begin(), E = BBs.end(); + I != E; ++I) + if (*I) + WriteAsOperand(o, *I, false); + else + o << " <>"; + return o; +} +} + //===----------------------------------------------------------------------===// -// ImmediateDominators Implementation +// DominatorTree Implementation //===----------------------------------------------------------------------===// // -// Immediate Dominators construction - This pass constructs immediate dominator +// DominatorTree construction - This pass constructs immediate dominator // information for a flow-graph based on the algorithm described in this // document: // @@ -45,10 +58,10 @@ using namespace llvm; // //===----------------------------------------------------------------------===// -static RegisterPass -C("idom", "Immediate Dominators Construction", true); +static RegisterPass +E("domtree", "Dominator Tree Construction", true); -unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, +unsigned DominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo, 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 @@ -110,7 +123,7 @@ unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, return N; } -void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) { +void DominatorTree::Compress(BasicBlock *V, InfoRec &VInfo) { BasicBlock *VAncestor = VInfo.Ancestor; InfoRec &VAInfo = Info[VAncestor]; if (VAInfo.Ancestor == 0) @@ -126,7 +139,7 @@ void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) { VInfo.Ancestor = VAInfo.Ancestor; } -BasicBlock *ImmediateDominators::Eval(BasicBlock *V) { +BasicBlock *DominatorTree::Eval(BasicBlock *V) { InfoRec &VInfo = Info[V]; #if !BALANCE_IDOM_TREE // Higher-complexity but faster implementation @@ -149,7 +162,7 @@ BasicBlock *ImmediateDominators::Eval(BasicBlock *V) { #endif } -void ImmediateDominators::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){ +void DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){ #if !BALANCE_IDOM_TREE // Higher-complexity but faster implementation WInfo.Ancestor = V; @@ -196,13 +209,10 @@ void ImmediateDominators::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){ #endif } - - -bool ImmediateDominators::runOnFunction(Function &F) { - IDoms.clear(); // Reset from the last time we were run... - BasicBlock *Root = &F.getEntryBlock(); - Roots.clear(); - Roots.push_back(Root); +void DominatorTree::calculate(Function& F) { + BasicBlock* Root = Roots[0]; + + Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root... Vertex.push_back(0); @@ -247,65 +257,34 @@ bool ImmediateDominators::runOnFunction(Function &F) { 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. + Node *&BBNode = Nodes[I]; + if (!BBNode) { // Haven't calculated this node yet? + // Get or calculate the node for the immediate dominator + Node *IDomNode = getNodeForBlock(ImmDom); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + BBNode = IDomNode->addChild(new Node(I, IDomNode)); + } + } + // Free temporary memory used to construct idom's Info.clear(); + IDoms.clear(); std::vector().swap(Vertex); - - return false; } -/// dominates - Return true if A dominates B. -/// -bool ImmediateDominatorsBase::dominates(BasicBlock *A, BasicBlock *B) const { - assert(A && B && "Null pointers?"); - - // Walk up the dominator tree from B to determine if A dom B. - while (A != B && B) - B = get(B); - return A == B; -} - -void ImmediateDominatorsBase::print(std::ostream &o, const Module* ) const { - Function *F = getRoots()[0]->getParent(); - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { - o << " Immediate Dominator For Basic Block:"; - WriteAsOperand(o, I, false); - o << " is:"; - if (BasicBlock *ID = get(I)) - WriteAsOperand(o, ID, false); - else - o << " <>"; - o << "\n"; - } - o << "\n"; -} - -namespace llvm { -static std::ostream &operator<<(std::ostream &o, - const std::set &BBs) { - for (std::set::const_iterator I = BBs.begin(), E = BBs.end(); - I != E; ++I) - if (*I) - WriteAsOperand(o, *I, false); - else - o << " <>"; - return o; -} -} - -//===----------------------------------------------------------------------===// -// DominatorTree Implementation -//===----------------------------------------------------------------------===// - -static RegisterPass -E("domtree", "Dominator Tree Construction", true); - // DominatorTreeBase::reset - Free all of the tree node memory. // void DominatorTreeBase::reset() { for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) delete I->second; Nodes.clear(); + IDoms.clear(); + Roots.clear(); RootNode = 0; } @@ -331,7 +310,7 @@ DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) { // Haven't calculated this node yet? Get or calculate the node for the // immediate dominator. - BasicBlock *IDom = getAnalysis()[BB]; + BasicBlock *IDom = getIDom(BB); Node *IDomNode = getNodeForBlock(IDom); // Add a new tree node for this BasicBlock, and link it as a child of @@ -339,27 +318,6 @@ DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) { return BBNode = IDomNode->addChild(new Node(BB, IDomNode)); } -void DominatorTree::calculate(const ImmediateDominators &ID) { - assert(Roots.size() == 1 && "DominatorTree should have 1 root block!"); - BasicBlock *Root = Roots[0]; - Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root... - - Function *F = Root->getParent(); - // 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 = ID.get(I)) { // Reachable block. - Node *&BBNode = Nodes[I]; - if (!BBNode) { // Haven't calculated this node yet? - // Get or calculate the node for the immediate dominator - Node *IDomNode = getNodeForBlock(ImmDom); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - BBNode = IDomNode->addChild(new Node(I, IDomNode)); - } - } -} - static std::ostream &operator<<(std::ostream &o, const DominatorTreeBase::Node *Node) { if (Node->getBlock()) @@ -383,6 +341,12 @@ void DominatorTreeBase::print(std::ostream &o, const Module* ) const { PrintDomTree(getRootNode(), o, 1); } +bool DominatorTree::runOnFunction(Function &F) { + reset(); // Reset from the last time we were run... + Roots.push_back(&F.getEntryBlock()); + calculate(F); + return false; +} //===----------------------------------------------------------------------===// // DominanceFrontier Implementation -- 2.34.1