X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FDominators.cpp;h=f3dad824461dd9e7ded770765fd37899a386cb80;hb=b08ba8824e0e8bf1d4a68594c5efb65bf640ecc1;hp=1f172145c3b1ff6518a5b5f2f56ca6844d763c07;hpb=850c9178dc5bc8a49fc41c7cf606bfdd7cd1de3a;p=oota-llvm.git diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 1f172145c3b..f3dad824461 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -17,6 +17,7 @@ #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" @@ -24,9 +25,20 @@ #include "llvm/Analysis/DominatorInternals.h" #include "llvm/Instructions.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Support/CommandLine.h" #include using namespace llvm; +// 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 //===----------------------------------------------------------------------===// @@ -36,18 +48,28 @@ using namespace llvm; // //===----------------------------------------------------------------------===// -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); } @@ -84,42 +106,40 @@ bool DominatorTree::dominates(const Instruction *A, const Instruction *B) const{ //===----------------------------------------------------------------------===// 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!"); + assert(NewBB->getTerminator()->getNumSuccessors() == 1 && + "NewBB should have a single successor!"); BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); - SmallVector 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. @@ -128,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 @@ -154,50 +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 (SmallVectorImpl::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 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) - removeFromFrontier(DFI, NewBBSucc); - if (BlockDominatesAny && (&*FI == NewBB || !DT.dominates(FI, NewBB))) + + // 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); } } @@ -290,7 +333,7 @@ DominanceFrontier::calculate(const DominatorTree &DT, void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const { for (const_iterator I = begin(), E = end(); I != E; ++I) { - OS << " DomFrontier for BB"; + OS << " DomFrontier for BB "; if (I->first) WriteAsOperand(OS, I->first, false); else @@ -300,12 +343,18 @@ void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const { const std::set &BBs = I->second; for (std::set::const_iterator I = BBs.begin(), E = BBs.end(); - I != E; ++I) + I != E; ++I) { + OS << ' '; if (*I) WriteAsOperand(OS, *I, false); else - OS << " <>"; + OS << "<>"; + } OS << "\n"; } } +void DominanceFrontierBase::dump() const { + print(dbgs()); +} +