X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FDominators.cpp;h=08b845ef9d6b44ae98ca91ead5982289022561d5;hb=9d6070f161d89376c7c834950f518e25e34d7ce8;hp=5aa3f34e876e76c553ab5eee5bd37ea19b242dbe;hpb=ea705199af871a7541ac0114d62f1b83c40f0f1e;p=oota-llvm.git diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 5aa3f34e876..08b845ef9d6 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -17,272 +17,90 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Support/CFG.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/Assembly/Writer.h" #include "llvm/Instructions.h" -#include "llvm/Support/Streams.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 //===----------------------------------------------------------------------===// // // Provide public access to DominatorTree information. Implementation details -// can be found in DominatorCalculation.h. +// can be found in DominatorInternals.h. // //===----------------------------------------------------------------------===// -TEMPLATE_INSTANTIATION(class DomTreeNodeBase); -TEMPLATE_INSTANTIATION(class DominatorTreeBase); +TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase); +TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase); char DominatorTree::ID = 0; -static RegisterPass -E("domtree", "Dominator Tree Construction", true, true); +INITIALIZE_PASS(DominatorTree, "domtree", + "Dominator Tree Construction", true, true) bool DominatorTree::runOnFunction(Function &F) { DT->recalculate(F); return false; } -//===----------------------------------------------------------------------===// -// DominanceFrontier Implementation -//===----------------------------------------------------------------------===// - -char DominanceFrontier::ID = 0; -static RegisterPass -G("domfrontier", "Dominance Frontier Construction", false, true); +void DominatorTree::verifyAnalysis() const { + if (!VerifyDomInfo) return; -// NewBB is split and now it has one successor. Update dominace frontier to -// reflect this change. -void DominanceFrontier::splitBlock(BasicBlock *NewBB) { - assert(NewBB->getTerminator()->getNumSuccessors() == 1 - && "NewBB should have a single successor!"); - BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); + Function &F = *getRoot()->getParent(); - 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); + DominatorTree OtherDT; + OtherDT.getBase().recalculate(F); + if (compare(OtherDT)) { + errs() << "DominatorTree is not up to date!\nComputed:\n"; + print(errs()); + errs() << "\nActual:\n"; + OtherDT.print(errs()); + abort(); } - - // 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 - // a predecessor of. - DominatorTree &DT = getAnalysis(); - if (DT.dominates(NewBB, NewBBSucc)) { - DominanceFrontier::iterator DFI = find(PredBlocks[0]); - if (DFI != end()) { - DominanceFrontier::DomSetType Set = DFI->second; - // Filter out stuff in Set that we do not dominate a predecessor of. - for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), - E = Set.end(); SetI != E;) { - bool DominatesPred = false; - for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); - PI != E; ++PI) - if (DT.dominates(NewBB, *PI)) - DominatesPred = true; - if (!DominatesPred) - Set.erase(SetI++); - else - ++SetI; - } - - if (NewBBI != end()) { - for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), - E = Set.end(); SetI != E; ++SetI) { - BasicBlock *SB = *SetI; - addToFrontier(NewBBI, SB); - } - } else - addBasicBlock(NewBB, Set); - } - - } else { - // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate - // NewBBSucc, but it does dominate itself (and there is an edge (NewBB -> - // NewBBSucc)). NewBBSucc is the single successor of NewBB. - DominanceFrontier::DomSetType NewDFSet; - 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; - break; - } - } - - 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; - } - } - - if (ShouldRemove) - removeFromFrontier(DFI, NewBBSucc); - addToFrontier(DFI, NewBB); - } -} - -namespace { - class DFCalculateWorkObject { - public: - DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, - const DomTreeNode *N, - const DomTreeNode *PN) - : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} - BasicBlock *currentBB; - BasicBlock *parentBB; - const DomTreeNode *Node; - const DomTreeNode *parentNode; - }; -} - -const DominanceFrontier::DomSetType & -DominanceFrontier::calculate(const DominatorTree &DT, - const DomTreeNode *Node) { - BasicBlock *BB = Node->getBlock(); - DomSetType *Result = NULL; - - std::vector workList; - SmallPtrSet visited; - - workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL)); - do { - DFCalculateWorkObject *currentW = &workList.back(); - assert (currentW && "Missing work object."); - - BasicBlock *currentBB = currentW->currentBB; - BasicBlock *parentBB = currentW->parentBB; - const DomTreeNode *currentNode = currentW->Node; - const DomTreeNode *parentNode = currentW->parentNode; - assert (currentBB && "Invalid work object. Missing current Basic Block"); - assert (currentNode && "Invalid work object. Missing current Node"); - DomSetType &S = Frontiers[currentBB]; - - // Visit each block only once. - if (visited.count(currentBB) == 0) { - visited.insert(currentBB); - - // Loop over CFG successors to calculate DFlocal[currentNode] - for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); - SI != SE; ++SI) { - // Does Node immediately dominate this successor? - if (DT[*SI]->getIDom() != currentNode) - S.insert(*SI); - } - } - - // At this point, S is DFlocal. Now we union in DFup's of our children... - // Loop through and visit the nodes that Node immediately dominates (Node's - // children in the IDomTree) - bool visitChild = false; - for (DomTreeNode::const_iterator NI = currentNode->begin(), - NE = currentNode->end(); NI != NE; ++NI) { - DomTreeNode *IDominee = *NI; - BasicBlock *childBB = IDominee->getBlock(); - if (visited.count(childBB) == 0) { - workList.push_back(DFCalculateWorkObject(childBB, currentBB, - IDominee, currentNode)); - visitChild = true; - } - } - - // If all children are visited or there is any child then pop this block - // from the workList. - if (!visitChild) { - - if (!parentBB) { - Result = &S; - break; - } - - DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); - DomSetType &parentSet = Frontiers[parentBB]; - for (; CDFI != CDFE; ++CDFI) { - if (!DT.properlyDominates(parentNode, DT[*CDFI])) - parentSet.insert(*CDFI); - } - workList.pop_back(); - } - - } while (!workList.empty()); - - return *Result; } -void DominanceFrontierBase::print(std::ostream &o, const Module* ) const { - for (const_iterator I = begin(), E = end(); I != E; ++I) { - o << " DomFrontier for BB"; - if (I->first) - WriteAsOperand(o, I->first, false); - else - o << " <>"; - o << " is:\t" << I->second << "\n"; - } +void DominatorTree::print(raw_ostream &OS, const Module *) const { + DT->print(OS); } -void DominanceFrontierBase::dump() { - print (llvm::cerr); +// 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 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::const_iterator I = BBA->begin(); + for (; &*I != A && &*I != B; ++I) + /*empty*/; + + return &*I == A; }