X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FDominators.cpp;h=4a6c5e80250b15c318ef7b2e29ca3cb44134172f;hb=d13db2c59cc94162d6cf0a04187d408bfef6d4a7;hp=6f1de466043df8937445f2bd03d5ab537a970b7d;hpb=687e03b2fa6b08fcd59c4f2f0c4aababdd91a71a;p=oota-llvm.git diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 6f1de466043..4a6c5e80250 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -17,28 +17,27 @@ #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/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 @@ -49,37 +48,89 @@ static std::ostream &operator<<(std::ostream &o, // //===----------------------------------------------------------------------===// -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; } +void DominatorTree::verifyAnalysis() const { + if (!VerifyDomInfo) return; + + Function &F = *getRoot()->getParent(); + + DominatorTree OtherDT; + OtherDT.getBase().recalculate(F); + assert(!compare(OtherDT) && "Invalid DominatorTree info!"); +} + +void DominatorTree::print(raw_ostream &OS, const Module *) const { + DT->print(OS); +} + +// 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; +} + + + //===----------------------------------------------------------------------===// // DominanceFrontier Implementation //===----------------------------------------------------------------------===// char DominanceFrontier::ID = 0; -static RegisterPass -G("domfrontier", "Dominance Frontier Construction", true, 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!"); BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); - std::vector PredBlocks; + SmallVector PredBlocks; for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); PI != PE; ++PI) - PredBlocks.push_back(*PI); + PredBlocks.push_back(*PI); if (PredBlocks.empty()) // If NewBB does not have any predecessors then it is a entry block. @@ -97,11 +148,11 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) { } // 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]); + 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. @@ -153,17 +204,14 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) { // 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(), + for (SmallVectorImpl::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. @@ -181,7 +229,8 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) { if (ShouldRemove) removeFromFrontier(DFI, NewBBSucc); - addToFrontier(DFI, NewBB); + if (BlockDominatesAny && (&*FI == NewBB || !DT.dominates(FI, NewBB))) + addToFrontier(DFI, NewBB); } } @@ -272,18 +321,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()); }