X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FDominators.cpp;h=f3dad824461dd9e7ded770765fd37899a386cb80;hb=b08ba8824e0e8bf1d4a68594c5efb65bf640ecc1;hp=57cf670286836385ea46fb55501a2eb3fc31de81;hpb=471ab54df756f2f48c9146ad897672662c3f25f9;p=oota-llvm.git diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 57cf6702868..f3dad824461 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group 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. // //===----------------------------------------------------------------------===// // @@ -16,29 +16,28 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Support/CFG.h" -#include "llvm/Assembly/Writer.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SetOperations.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/DominatorInternals.h" #include "llvm/Instructions.h" -#include "llvm/Support/Streams.h" -#include "DominatorCalculation.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/CommandLine.h" #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; -} -} +// Always verify dominfo if expensive checking is enabled. +#ifdef XDEBUG +static bool VerifyDomInfo = true; +#else +static bool VerifyDomInfo = false; +#endif +static cl::opt +VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), + cl::desc("Verify dominator info (time consuming)")); //===----------------------------------------------------------------------===// // DominatorTree Implementation @@ -49,359 +48,98 @@ static std::ostream &operator<<(std::ostream &o, // //===----------------------------------------------------------------------===// -char DominatorTree::ID = 0; -static RegisterPass -E("domtree", "Dominator Tree Construction", true); - -// NewBB is split and now it has one successor. Update dominator tree to -// reflect this change. -void DominatorTree::splitBlock(BasicBlock *NewBB) { - assert(NewBB->getTerminator()->getNumSuccessors() == 1 - && "NewBB should have a single successor!"); - BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); - - std::vector PredBlocks; - for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); - PI != PE; ++PI) - PredBlocks.push_back(*PI); - - assert(!PredBlocks.empty() && "No predblocks??"); - - // The newly inserted basic block will dominate existing basic blocks iff the - // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate - // the non-pred blocks, then they all must be the same block! - // - bool NewBBDominatesNewBBSucc = true; - { - BasicBlock *OnePred = PredBlocks[0]; - unsigned i = 1, e = PredBlocks.size(); - for (i = 1; !isReachableFromEntry(OnePred); ++i) { - assert(i != e && "Didn't find reachable pred?"); - OnePred = PredBlocks[i]; - } - - for (; i != e; ++i) - if (PredBlocks[i] != OnePred && isReachableFromEntry(OnePred)) { - NewBBDominatesNewBBSucc = false; - break; - } +TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase); +TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase); - if (NewBBDominatesNewBBSucc) - for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); - PI != E; ++PI) - if (*PI != NewBB && !dominates(NewBBSucc, *PI)) { - NewBBDominatesNewBBSucc = false; - break; - } - } - - // The other scenario where the new block can dominate its successors are when - // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc - // already. - if (!NewBBDominatesNewBBSucc) { - NewBBDominatesNewBBSucc = true; - for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); - PI != E; ++PI) - if (*PI != NewBB && !dominates(NewBBSucc, *PI)) { - NewBBDominatesNewBBSucc = false; - break; - } - } +char DominatorTree::ID = 0; +INITIALIZE_PASS(DominatorTree, "domtree", + "Dominator Tree Construction", true, true); - // Find NewBB's immediate dominator and create new dominator tree node for - // NewBB. - BasicBlock *NewBBIDom = 0; - unsigned i = 0; - for (i = 0; i < PredBlocks.size(); ++i) - if (isReachableFromEntry(PredBlocks[i])) { - NewBBIDom = PredBlocks[i]; - break; - } - assert(i != PredBlocks.size() && "No reachable preds?"); - for (i = i + 1; i < PredBlocks.size(); ++i) { - if (isReachableFromEntry(PredBlocks[i])) - NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); - } - assert(NewBBIDom && "No immediate dominator found??"); - - // Create the new dominator tree node... and set the idom of NewBB. - DomTreeNode *NewBBNode = addNewBlock(NewBB, NewBBIDom); - - // If NewBB strictly dominates other blocks, then it is now the immediate - // dominator of NewBBSucc. Update the dominator tree as appropriate. - if (NewBBDominatesNewBBSucc) { - DomTreeNode *NewBBSuccNode = getNode(NewBBSucc); - changeImmediateDominator(NewBBSuccNode, NewBBNode); - } +bool DominatorTree::runOnFunction(Function &F) { + DT->recalculate(F); + return false; } -void DominatorTreeBase::updateDFSNumbers() { - unsigned DFSNum = 0; +void DominatorTree::verifyAnalysis() const { + if (!VerifyDomInfo) return; - SmallVector, 32> WorkStack; - - for (unsigned i = 0, e = Roots.size(); i != e; ++i) { - DomTreeNode *ThisRoot = getNode(Roots[i]); - WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); - ThisRoot->DFSNumIn = DFSNum++; - - while (!WorkStack.empty()) { - DomTreeNode *Node = WorkStack.back().first; - DomTreeNode::iterator ChildIt = WorkStack.back().second; - - // If we visited all of the children of this node, "recurse" back up the - // stack setting the DFOutNum. - if (ChildIt == Node->end()) { - Node->DFSNumOut = DFSNum++; - WorkStack.pop_back(); - } else { - // Otherwise, recursively visit this child. - DomTreeNode *Child = *ChildIt; - ++WorkStack.back().second; - - WorkStack.push_back(std::make_pair(Child, Child->begin())); - Child->DFSNumIn = DFSNum++; - } - } - } - - SlowQueries = 0; - DFSInfoValid = true; + Function &F = *getRoot()->getParent(); + + DominatorTree OtherDT; + OtherDT.getBase().recalculate(F); + assert(!compare(OtherDT) && "Invalid DominatorTree info!"); } -/// isReachableFromEntry - Return true if A is dominated by the entry -/// block of the function containing it. -const bool DominatorTreeBase::isReachableFromEntry(BasicBlock* A) { - assert (!isPostDominator() - && "This is not implemented for post dominators"); - return dominates(&A->getParent()->getEntryBlock(), A); +void DominatorTree::print(raw_ostream &OS, const Module *) const { + DT->print(OS); } -// dominates - Return true if A dominates B. THis performs the +// dominates - Return true if A dominates a use in B. This performs the // special checks necessary if A and B are in the same basic block. -bool DominatorTreeBase::dominates(Instruction *A, Instruction *B) { - BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); +bool DominatorTree::dominates(const Instruction *A, const Instruction *B) const{ + const BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); + + // If A is an invoke instruction, its value is only available in this normal + // successor block. + if (const InvokeInst *II = dyn_cast(A)) + BBA = II->getNormalDest(); + if (BBA != BBB) return dominates(BBA, BBB); // It is not possible to determine dominance between two PHI nodes // based on their ordering. if (isa(A) && isa(B)) return false; - - // Loop through the basic block until we find A or B. - BasicBlock::iterator I = BBA->begin(); - for (; &*I != A && &*I != B; ++I) /*empty*/; - - if(!IsPostDominators) { - // A dominates B if it is found first in the basic block. - return &*I == A; - } else { - // A post-dominates B if B is found first in the basic block. - return &*I == B; - } -} - -// DominatorTreeBase::reset - Free all of the tree node memory. -// -void DominatorTreeBase::reset() { - for (DomTreeNodeMapType::iterator I = DomTreeNodes.begin(), - E = DomTreeNodes.end(); I != E; ++I) - delete I->second; - DomTreeNodes.clear(); - IDoms.clear(); - Roots.clear(); - Vertex.clear(); - 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, - BasicBlock *B) { - - assert (!isPostDominator() - && "This is not implemented for post dominators"); - assert (A->getParent() == B->getParent() - && "Two blocks are not in same function"); - - // If either A or B is a entry block then it is nearest common dominator. - BasicBlock &Entry = A->getParent()->getEntryBlock(); - if (A == &Entry || B == &Entry) - return &Entry; - - // If B dominates A then B is nearest common dominator. - if (dominates(B, A)) - return B; - - // If A dominates B then A is nearest common dominator. - if (dominates(A, B)) - return A; - - DomTreeNode *NodeA = getNode(A); - DomTreeNode *NodeB = getNode(B); - - // Collect NodeA dominators set. - SmallPtrSet NodeADoms; - NodeADoms.insert(NodeA); - DomTreeNode *IDomA = NodeA->getIDom(); - while (IDomA) { - NodeADoms.insert(IDomA); - IDomA = IDomA->getIDom(); - } - - // Walk NodeB immediate dominators chain and find common dominator node. - DomTreeNode *IDomB = NodeB->getIDom(); - while(IDomB) { - if (NodeADoms.count(IDomB) != 0) - return IDomB->getBlock(); - - IDomB = IDomB->getIDom(); - } - - return NULL; -} - -void DomTreeNode::setIDom(DomTreeNode *NewIDom) { - assert(IDom && "No immediate dominator?"); - if (IDom != NewIDom) { - std::vector::iterator I = - std::find(IDom->Children.begin(), IDom->Children.end(), this); - assert(I != IDom->Children.end() && - "Not in immediate dominator children set!"); - // I am no longer your child... - IDom->Children.erase(I); - - // Switch to new dominator - IDom = NewIDom; - IDom->Children.push_back(this); - } -} - -static std::ostream &operator<<(std::ostream &o, const DomTreeNode *Node) { - if (Node->getBlock()) - WriteAsOperand(o, Node->getBlock(), false); - else - o << " <>"; - - o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; - return o << "\n"; -} - -static void PrintDomTree(const DomTreeNode *N, std::ostream &o, - unsigned Lev) { - o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N; - for (DomTreeNode::const_iterator I = N->begin(), E = N->end(); - I != E; ++I) - PrintDomTree(*I, o, Lev+1); -} - -/// eraseNode - Removes a node from the domiantor tree. Block must not -/// domiante any other blocks. Removes node from its immediate dominator's -/// children list. Deletes dominator node associated with basic block BB. -void DominatorTreeBase::eraseNode(BasicBlock *BB) { - DomTreeNode *Node = getNode(BB); - assert (Node && "Removing node that isn't in dominator tree."); - assert (Node->getChildren().empty() && "Node is not a leaf node."); - - // Remove node from immediate dominator's children list. - DomTreeNode *IDom = Node->getIDom(); - if (IDom) { - std::vector::iterator I = - std::find(IDom->Children.begin(), IDom->Children.end(), Node); - assert(I != IDom->Children.end() && - "Not in immediate dominator children set!"); - // I am no longer your child... - IDom->Children.erase(I); - } - - DomTreeNodes.erase(BB); - delete Node; -} - -void DominatorTreeBase::print(std::ostream &o, const Module* ) const { - o << "=============================--------------------------------\n"; - o << "Inorder Dominator Tree: "; - if (DFSInfoValid) - o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; - o << "\n"; + // Loop through the basic block until we find A or B. + BasicBlock::const_iterator I = BBA->begin(); + for (; &*I != A && &*I != B; ++I) + /*empty*/; - PrintDomTree(getRootNode(), o, 1); + return &*I == A; } -void DominatorTreeBase::dump() { - print(llvm::cerr); -} -bool DominatorTree::runOnFunction(Function &F) { - reset(); // Reset from the last time we were run... - - // Initialize roots - Roots.push_back(&F.getEntryBlock()); - IDoms[&F.getEntryBlock()] = 0; - DomTreeNodes[&F.getEntryBlock()] = 0; - Vertex.push_back(0); - - DTcalculate(*this, F); - return false; -} //===----------------------------------------------------------------------===// // DominanceFrontier Implementation //===----------------------------------------------------------------------===// char DominanceFrontier::ID = 0; -static RegisterPass -G("domfrontier", "Dominance Frontier Construction", true); +INITIALIZE_PASS(DominanceFrontier, "domfrontier", + "Dominance Frontier Construction", true, true); + +void DominanceFrontier::verifyAnalysis() const { + if (!VerifyDomInfo) return; + + DominatorTree &DT = getAnalysis(); + + DominanceFrontier OtherDF; + const std::vector &DTRoots = DT.getRoots(); + OtherDF.calculate(DT, DT.getNode(DTRoots[0])); + assert(!compare(OtherDF) && "Invalid DominanceFrontier info!"); +} -// NewBB is split and now it has one successor. Update dominace frontier to +// NewBB is split and now it has one successor. Update dominance frontier to // reflect this change. void DominanceFrontier::splitBlock(BasicBlock *NewBB) { - assert(NewBB->getTerminator()->getNumSuccessors() == 1 - && "NewBB should have a single successor!"); + assert(NewBB->getTerminator()->getNumSuccessors() == 1 && + "NewBB should have a single successor!"); BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); - std::vector PredBlocks; - for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); - PI != PE; ++PI) - PredBlocks.push_back(*PI); - - if (PredBlocks.empty()) - // If NewBB does not have any predecessors then it is a entry block. - // In this case, NewBB and its successor NewBBSucc dominates all - // other blocks. - return; - // NewBBSucc inherits original NewBB frontier. DominanceFrontier::iterator NewBBI = find(NewBB); - if (NewBBI != end()) { - DominanceFrontier::DomSetType NewBBSet = NewBBI->second; - DominanceFrontier::DomSetType NewBBSuccSet; - NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end()); - addBasicBlock(NewBBSucc, NewBBSuccSet); - } + if (NewBBI != end()) + addBasicBlock(NewBBSucc, NewBBI->second); // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the - // DF(PredBlocks[0]) without the stuff that the new block does not dominate + // DF(NewBBSucc) without the stuff that the new block does not dominate // a predecessor of. DominatorTree &DT = getAnalysis(); - if (DT.dominates(NewBB, NewBBSucc)) { - DominanceFrontier::iterator DFI = find(PredBlocks[0]); + DomTreeNode *NewBBNode = DT.getNode(NewBB); + DomTreeNode *NewBBSuccNode = DT.getNode(NewBBSucc); + if (DT.dominates(NewBBNode, NewBBSuccNode)) { + DominanceFrontier::iterator DFI = find(NewBBSucc); if (DFI != end()) { DominanceFrontier::DomSetType Set = DFI->second; // Filter out stuff in Set that we do not dominate a predecessor of. @@ -410,8 +148,10 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) { bool DominatesPred = false; for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); PI != E; ++PI) - if (DT.dominates(NewBB, *PI)) + if (DT.dominates(NewBBNode, DT.getNode(*PI))) { DominatesPred = true; + break; + } if (!DominatesPred) Set.erase(SetI++); else @@ -419,8 +159,11 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) { } if (NewBBI != end()) { - DominanceFrontier::DomSetType NewBBSet = NewBBI->second; - NewBBSet.insert(Set.begin(), Set.end()); + for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), + E = Set.end(); SetI != E; ++SetI) { + BasicBlock *SB = *SetI; + addToFrontier(NewBBI, SB); + } } else addBasicBlock(NewBB, Set); } @@ -433,52 +176,71 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) { NewDFSet.insert(NewBBSucc); addBasicBlock(NewBB, NewDFSet); } - - // Now we must loop over all of the dominance frontiers in the function, - // replacing occurrences of NewBBSucc with NewBB in some cases. All - // blocks that dominate a block in PredBlocks and contained NewBBSucc in - // their dominance frontier must be updated to contain NewBB instead. - // - for (Function::iterator FI = NewBB->getParent()->begin(), - FE = NewBB->getParent()->end(); FI != FE; ++FI) { - DominanceFrontier::iterator DFI = find(FI); - if (DFI == end()) continue; // unreachable block. - - // Only consider nodes that have NewBBSucc in their dominator frontier. - if (!DFI->second.count(NewBBSucc)) continue; - - // Verify whether this block dominates a block in predblocks. If not, do - // not update it. - bool BlockDominatesAny = false; - for (std::vector::const_iterator BI = PredBlocks.begin(), - BE = PredBlocks.end(); BI != BE; ++BI) { - if (DT.dominates(FI, *BI)) { - BlockDominatesAny = true; + + // Now update dominance frontiers which either used to contain NewBBSucc + // or which now need to include NewBB. + + // Collect the set of blocks which dominate a predecessor of NewBB or + // NewSuccBB and which don't dominate both. This is an initial + // approximation of the blocks whose dominance frontiers will need updates. + SmallVector AllPredDoms; + + // Compute the block which dominates both NewBBSucc and NewBB. This is + // the immediate dominator of NewBBSucc unless NewBB dominates NewBBSucc. + // The code below which climbs dominator trees will stop at this point, + // because from this point up, dominance frontiers are unaffected. + DomTreeNode *DominatesBoth = 0; + if (NewBBSuccNode) { + DominatesBoth = NewBBSuccNode->getIDom(); + if (DominatesBoth == NewBBNode) + DominatesBoth = NewBBNode->getIDom(); + } + + // Collect the set of all blocks which dominate a predecessor of NewBB. + SmallPtrSet NewBBPredDoms; + for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); PI != E; ++PI) + for (DomTreeNode *DTN = DT.getNode(*PI); DTN; DTN = DTN->getIDom()) { + if (DTN == DominatesBoth) break; - } + if (!NewBBPredDoms.insert(DTN)) + break; + AllPredDoms.push_back(DTN); } - - if (!BlockDominatesAny) - continue; - - // If NewBBSucc should not stay in our dominator frontier, remove it. - // We remove it unless there is a predecessor of NewBBSucc that we - // dominate, but we don't strictly dominate NewBBSucc. - bool ShouldRemove = true; - if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) { - // Okay, we know that PredDom does not strictly dominate NewBBSucc. - // Check to see if it dominates any predecessors of NewBBSucc. - for (pred_iterator PI = pred_begin(NewBBSucc), - E = pred_end(NewBBSucc); PI != E; ++PI) - if (DT.dominates(FI, *PI)) { - ShouldRemove = false; - break; - } + + // Collect the set of all blocks which dominate a predecessor of NewSuccBB. + SmallPtrSet NewBBSuccPredDoms; + for (pred_iterator PI = pred_begin(NewBBSucc), + E = pred_end(NewBBSucc); PI != E; ++PI) + for (DomTreeNode *DTN = DT.getNode(*PI); DTN; DTN = DTN->getIDom()) { + if (DTN == DominatesBoth) + break; + if (!NewBBSuccPredDoms.insert(DTN)) + break; + if (!NewBBPredDoms.count(DTN)) + AllPredDoms.push_back(DTN); } - - if (ShouldRemove) + + // Visit all relevant dominance frontiers and make any needed updates. + for (SmallVectorImpl::const_iterator I = AllPredDoms.begin(), + E = AllPredDoms.end(); I != E; ++I) { + DomTreeNode *DTN = *I; + iterator DFI = find((*I)->getBlock()); + + // Only consider nodes that have NewBBSucc in their dominator frontier. + if (DFI == end() || !DFI->second.count(NewBBSucc)) continue; + + // If the block dominates a predecessor of NewBB but does not properly + // dominate NewBB itself, add NewBB to its dominance frontier. + if (NewBBPredDoms.count(DTN) && + !DT.properlyDominates(DTN, NewBBNode)) + addToFrontier(DFI, NewBB); + + // If the block does not dominate a predecessor of NewBBSucc or + // properly dominates NewBBSucc itself, remove NewBBSucc from its + // dominance frontier. + if (!NewBBSuccPredDoms.count(DTN) || + DT.properlyDominates(DTN, NewBBSuccNode)) removeFromFrontier(DFI, NewBBSucc); - addToFrontier(DFI, NewBB); } } @@ -569,17 +331,30 @@ DominanceFrontier::calculate(const DominatorTree &DT, return *Result; } -void DominanceFrontierBase::print(std::ostream &o, const Module* ) const { +void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const { for (const_iterator I = begin(), E = end(); I != E; ++I) { - o << " DomFrontier for BB"; + OS << " DomFrontier for BB "; if (I->first) - WriteAsOperand(o, I->first, false); + WriteAsOperand(OS, I->first, false); else - o << " <>"; - o << " is:\t" << I->second << "\n"; + OS << " <>"; + OS << " is:\t"; + + const std::set &BBs = I->second; + + for (std::set::const_iterator I = BBs.begin(), E = BBs.end(); + I != E; ++I) { + OS << ' '; + if (*I) + WriteAsOperand(OS, *I, false); + else + OS << "<>"; + } + OS << "\n"; } } -void DominanceFrontierBase::dump() { - print (llvm::cerr); +void DominanceFrontierBase::dump() const { + print(dbgs()); } +