diff options
author | Owen Anderson <resistor@mac.com> | 2007-04-15 08:47:27 +0000 |
---|---|---|
committer | Owen Anderson <resistor@mac.com> | 2007-04-15 08:47:27 +0000 |
commit | 3dc6776b338f81e2d47daa42cc12c9f91053043d (patch) | |
tree | 810e120395e315d2c0e11e0da643422ab5e72f4b /lib | |
parent | 2aabd0722d68ee53af9ad7140d1c0b853b6fe421 (diff) | |
download | external_llvm-3dc6776b338f81e2d47daa42cc12c9f91053043d.zip external_llvm-3dc6776b338f81e2d47daa42cc12c9f91053043d.tar.gz external_llvm-3dc6776b338f81e2d47daa42cc12c9f91053043d.tar.bz2 |
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
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Analysis/PostDominators.cpp | 89 | ||||
-rw-r--r-- | lib/Transforms/Scalar/LoopStrengthReduce.cpp | 1 | ||||
-rw-r--r-- | lib/Transforms/Utils/BreakCriticalEdges.cpp | 24 | ||||
-rw-r--r-- | lib/Transforms/Utils/LoopSimplify.cpp | 26 | ||||
-rw-r--r-- | lib/VMCore/Dominators.cpp | 134 |
5 files changed, 88 insertions, 186 deletions
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp index 2439940..7351ed7 100644 --- a/lib/Analysis/PostDominators.cpp +++ b/lib/Analysis/PostDominators.cpp @@ -19,13 +19,13 @@ using namespace llvm; //===----------------------------------------------------------------------===// -// ImmediatePostDominators Implementation +// PostDominatorTree Implementation //===----------------------------------------------------------------------===// -static RegisterPass<ImmediatePostDominators> -D("postidom", "Immediate Post-Dominators Construction", true); +static RegisterPass<PostDominatorTree> +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<std::pair<BasicBlock *, InfoRec *> > workStack; std::set<BasicBlock *> 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<BasicBlock*>().swap(Vertex); - - return false; -} - -//===----------------------------------------------------------------------===// -// PostDominatorTree Implementation -//===----------------------------------------------------------------------===// - -static RegisterPass<PostDominatorTree> -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<ImmediatePostDominators>()[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<BasicBlock*>().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<ImmediatePostDominators>()[BB]; + PostDominatorTree::Node *node = getAnalysis<PostDominatorTree>().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 332ddfa..38cfd91 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -154,7 +154,6 @@ namespace { AU.addPreservedID(LoopSimplifyID); AU.addPreserved<LoopInfo>(); AU.addPreserved<ETForest>(); - AU.addPreserved<ImmediateDominators>(); AU.addPreserved<DominanceFrontier>(); AU.addPreserved<DominatorTree>(); diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp index 2f91e57..2cf2ecd 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<ETForest>(); - AU.addPreserved<ImmediateDominators>(); AU.addPreserved<DominatorTree>(); AU.addPreserved<DominanceFrontier>(); AU.addPreserved<LoopInfo>(); @@ -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<ImmediateDominators>()) { - // 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<DominatorTree>()) { diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index 7599168..7d34b95 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -68,7 +68,6 @@ namespace { AU.addRequired<ETForest>(); AU.addPreserved<LoopInfo>(); - AU.addPreserved<ImmediateDominators>(); AU.addPreserved<ETForest>(); AU.addPreserved<DominatorTree>(); AU.addPreserved<DominanceFrontier>(); @@ -749,31 +748,6 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, } BasicBlock *NewBBIDom = 0; - - // Update immediate dominator information if we have it. - if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { - 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<DominatorTree>()) { diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 0959b07..9685ed9 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -24,11 +24,24 @@ #include <algorithm> using namespace llvm; +namespace llvm { +static std::ostream &operator<<(std::ostream &o, + const std::set<BasicBlock*> &BBs) { + for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); + I != E; ++I) + if (*I) + WriteAsOperand(o, *I, false); + else + o << " <<exit node>>"; + 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<ImmediateDominators> -C("idom", "Immediate Dominators Construction", true); +static RegisterPass<DominatorTree> +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<BasicBlock*>().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 << " <<exit node>>"; - o << "\n"; - } - o << "\n"; -} - -namespace llvm { -static std::ostream &operator<<(std::ostream &o, - const std::set<BasicBlock*> &BBs) { - for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); - I != E; ++I) - if (*I) - WriteAsOperand(o, *I, false); - else - o << " <<exit node>>"; - return o; -} -} - -//===----------------------------------------------------------------------===// -// DominatorTree Implementation -//===----------------------------------------------------------------------===// - -static RegisterPass<DominatorTree> -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<ImmediateDominators>()[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 |