X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FDominators.cpp;h=77b2403d87dd1873538d3337593f27ad5eefed21;hb=28d1c60f89f7d224879bd84b89c3e280e6a7333b;hp=9b36e1de6371ab697785e4b18c17781f67b04eeb;hpb=0a5f83c22cc5d1fe24e57aadde9399fa90eb5c98;p=oota-llvm.git diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 9b36e1de637..77b2403d87d 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,806 +16,287 @@ #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/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)")); + +bool BasicBlockEdge::isSingleEdge() const { + const TerminatorInst *TI = Start->getTerminator(); + unsigned NumEdgesToEnd = 0; + for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) { + if (TI->getSuccessor(i) == End) + ++NumEdgesToEnd; + if (NumEdgesToEnd >= 2) + return false; + } + assert(NumEdgesToEnd == 1); + return true; } //===----------------------------------------------------------------------===// // DominatorTree Implementation //===----------------------------------------------------------------------===// // -// DominatorTree construction - This pass constructs immediate dominator -// information for a flow-graph based on the algorithm described in this -// document: -// -// A Fast Algorithm for Finding Dominators in a Flowgraph -// T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. -// -// This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and -// LINK, but it turns out that the theoretically slower O(n*log(n)) -// implementation is actually faster than the "efficient" algorithm (even for -// large CFGs) because the constant overheads are substantially smaller. The -// lower-complexity version can be enabled with the following #define: -// -#define BALANCE_IDOM_TREE 0 +// Provide public access to DominatorTree information. Implementation details +// can be found in DominatorInternals.h. // //===----------------------------------------------------------------------===// -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; - } - - 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; - } - } +TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase); +TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase); +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; } -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 - // documentation purposes. -#if 0 - VInfo.Semi = ++N; - VInfo.Label = V; - - Vertex.push_back(V); // Vertex[n] = V; - //Info[V].Ancestor = 0; // Ancestor[n] = 0 - //Info[V].Child = 0; // Child[v] = 0 - VInfo.Size = 1; // Size[v] = 1 - - for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { - InfoRec &SuccVInfo = Info[*SI]; - if (SuccVInfo.Semi == 0) { - SuccVInfo.Parent = V; - N = DFSPass(*SI, SuccVInfo, N); - } - } -#else - std::vector > Worklist; - Worklist.push_back(std::make_pair(V, 0U)); - while (!Worklist.empty()) { - BasicBlock *BB = Worklist.back().first; - unsigned NextSucc = Worklist.back().second; - - // First time we visited this BB? - if (NextSucc == 0) { - InfoRec &BBInfo = Info[BB]; - BBInfo.Semi = ++N; - BBInfo.Label = BB; - - Vertex.push_back(BB); // Vertex[n] = V; - //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0 - //BBInfo[V].Child = 0; // Child[v] = 0 - BBInfo.Size = 1; // Size[v] = 1 - } - - // If we are done with this block, remove it from the worklist. - if (NextSucc == BB->getTerminator()->getNumSuccessors()) { - Worklist.pop_back(); - continue; - } - - // Otherwise, increment the successor number for the next time we get to it. - ++Worklist.back().second; - - // Visit the successor next, if it isn't already visited. - BasicBlock *Succ = BB->getTerminator()->getSuccessor(NextSucc); - - InfoRec &SuccVInfo = Info[Succ]; - if (SuccVInfo.Semi == 0) { - SuccVInfo.Parent = BB; - Worklist.push_back(std::make_pair(Succ, 0U)); - } - } -#endif - return N; -} +void DominatorTree::verifyAnalysis() const { + if (!VerifyDomInfo) return; -void DominatorTree::Compress(BasicBlock *VIn) { - - std::vector Work; - std::set Visited; - BasicBlock *VInAncestor = Info[VIn].Ancestor; - InfoRec &VInVAInfo = Info[VInAncestor]; - - if (VInVAInfo.Ancestor != 0) - Work.push_back(VIn); - - while (!Work.empty()) { - BasicBlock *V = Work.back(); - InfoRec &VInfo = Info[V]; - BasicBlock *VAncestor = VInfo.Ancestor; - InfoRec &VAInfo = Info[VAncestor]; - - // Process Ancestor first - if (Visited.count(VAncestor) == 0 && VAInfo.Ancestor != 0) { - Work.push_back(VAncestor); - Visited.insert(VAncestor); - continue; - } - Work.pop_back(); + Function &F = *getRoot()->getParent(); - // Update VInfo based on Ancestor info - if (VAInfo.Ancestor == 0) - continue; - BasicBlock *VAncestorLabel = VAInfo.Label; - BasicBlock *VLabel = VInfo.Label; - if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) - VInfo.Label = VAncestorLabel; - VInfo.Ancestor = VAInfo.Ancestor; + 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(); } } -BasicBlock *DominatorTree::Eval(BasicBlock *V) { - InfoRec &VInfo = Info[V]; -#if !BALANCE_IDOM_TREE - // Higher-complexity but faster implementation - if (VInfo.Ancestor == 0) - return V; - Compress(V); - return VInfo.Label; -#else - // Lower-complexity but slower implementation - if (VInfo.Ancestor == 0) - return VInfo.Label; - Compress(V); - BasicBlock *VLabel = VInfo.Label; - - BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label; - if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi) - return VLabel; - else - return VAncestorLabel; -#endif +void DominatorTree::print(raw_ostream &OS, const Module *) const { + DT->print(OS); } -void DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){ -#if !BALANCE_IDOM_TREE - // Higher-complexity but faster implementation - WInfo.Ancestor = V; -#else - // Lower-complexity but slower implementation - BasicBlock *WLabel = WInfo.Label; - unsigned WLabelSemi = Info[WLabel].Semi; - BasicBlock *S = W; - InfoRec *SInfo = &Info[S]; - - BasicBlock *SChild = SInfo->Child; - InfoRec *SChildInfo = &Info[SChild]; - - while (WLabelSemi < Info[SChildInfo->Label].Semi) { - BasicBlock *SChildChild = SChildInfo->Child; - if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) { - SChildInfo->Ancestor = S; - SInfo->Child = SChild = SChildChild; - SChildInfo = &Info[SChild]; - } else { - SChildInfo->Size = SInfo->Size; - S = SInfo->Ancestor = SChild; - SInfo = SChildInfo; - SChild = SChildChild; - SChildInfo = &Info[SChild]; - } - } - - InfoRec &VInfo = Info[V]; - SInfo->Label = WLabel; - - assert(V != W && "The optimization here will not work in this case!"); - unsigned WSize = WInfo.Size; - unsigned VSize = (VInfo.Size += WSize); - - if (VSize < 2*WSize) - std::swap(S, VInfo.Child); +// dominates - Return true if Def dominates a use in User. This performs +// the special checks necessary if Def and User are in the same basic block. +// Note that Def doesn't dominate a use in Def itself! +bool DominatorTree::dominates(const Instruction *Def, + const Instruction *User) const { + const BasicBlock *UseBB = User->getParent(); + const BasicBlock *DefBB = Def->getParent(); - while (S) { - SInfo = &Info[S]; - SInfo->Ancestor = V; - S = SInfo->Child; - } -#endif -} - -void DominatorTree::calculate(Function& F) { - BasicBlock* Root = Roots[0]; - - // Add a node for the root... - DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0); - - Vertex.push_back(0); - - // Step #1: Number blocks in depth-first order and initialize variables used - // in later stages of the algorithm. - unsigned N = 0; - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - N = DFSPass(Roots[i], Info[Roots[i]], 0); - - for (unsigned i = N; i >= 2; --i) { - BasicBlock *W = Vertex[i]; - InfoRec &WInfo = Info[W]; - - // Step #2: Calculate the semidominators of all vertices - for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI) - if (Info.count(*PI)) { // Only if this predecessor is reachable! - unsigned SemiU = Info[Eval(*PI)].Semi; - if (SemiU < WInfo.Semi) - WInfo.Semi = SemiU; - } - - Info[Vertex[WInfo.Semi]].Bucket.push_back(W); - - BasicBlock *WParent = WInfo.Parent; - Link(WParent, W, WInfo); - - // Step #3: Implicitly define the immediate dominator of vertices - std::vector &WParentBucket = Info[WParent].Bucket; - while (!WParentBucket.empty()) { - BasicBlock *V = WParentBucket.back(); - WParentBucket.pop_back(); - BasicBlock *U = Eval(V); - IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent; - } - } + // Any unreachable use is dominated, even if Def == User. + if (!isReachableFromEntry(UseBB)) + return true; - // Step #4: Explicitly define the immediate dominator of each vertex - for (unsigned i = 2; i <= N; ++i) { - BasicBlock *W = Vertex[i]; - BasicBlock *&WIDom = IDoms[W]; - if (WIDom != Vertex[Info[W].Semi]) - WIDom = IDoms[WIDom]; - } + // Unreachable definitions don't dominate anything. + if (!isReachableFromEntry(DefBB)) + return false; - // 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. - DomTreeNode *BBNode = DomTreeNodes[I]; - if (BBNode) continue; // Haven't calculated this node yet? + // An instruction doesn't dominate a use in itself. + if (Def == User) + return false; - // Get or calculate the node for the immediate dominator - DomTreeNode *IDomNode = getNodeForBlock(ImmDom); + // The value defined by an invoke dominates an instruction only if + // it dominates every instruction in UseBB. + // A PHI is dominated only if the instruction dominates every possible use + // in the UseBB. + if (isa(Def) || isa(User)) + return dominates(Def, UseBB); - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - DomTreeNode *C = new DomTreeNode(I, IDomNode); - DomTreeNodes[I] = IDomNode->addChild(C); - } + if (DefBB != UseBB) + return dominates(DefBB, UseBB); - // Free temporary memory used to construct idom's - Info.clear(); - IDoms.clear(); - std::vector().swap(Vertex); + // Loop through the basic block until we find Def or User. + BasicBlock::const_iterator I = DefBB->begin(); + for (; &*I != Def && &*I != User; ++I) + /*empty*/; - updateDFSNumbers(); + return &*I == Def; } -void DominatorTreeBase::updateDFSNumbers() { - int dfsnum = 0; - // Iterate over all nodes in depth first order. - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - for (df_iterator I = df_begin(Roots[i]), - E = df_end(Roots[i]); I != E; ++I) { - BasicBlock *BB = *I; - DomTreeNode *BBNode = getNode(BB); - if (BBNode) { - if (!BBNode->getIDom()) - BBNode->assignDFSNumber(dfsnum); - } - } - SlowQueries = 0; - DFSInfoValid = true; -} +// true if Def would dominate a use in any instruction in UseBB. +// note that dominates(Def, Def->getParent()) is false. +bool DominatorTree::dominates(const Instruction *Def, + const BasicBlock *UseBB) const { + const BasicBlock *DefBB = Def->getParent(); -/// 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); -} + // Any unreachable use is dominated, even if DefBB == UseBB. + if (!isReachableFromEntry(UseBB)) + return true; -// dominates - Return true if A dominates 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(); - 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)) + // Unreachable definitions don't dominate anything. + if (!isReachableFromEntry(DefBB)) 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; -} + if (DefBB == UseBB) + return false; -/// 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(); - } + const InvokeInst *II = dyn_cast(Def); + if (!II) + return dominates(DefBB, UseBB); - // Walk NodeB immediate dominators chain and find common dominator node. - DomTreeNode *IDomB = NodeB->getIDom(); - while(IDomB) { - if (NodeADoms.count(IDomB) != 0) - return IDomB->getBlock(); + // Invoke results are only usable in the normal destination, not in the + // exceptional destination. + BasicBlock *NormalDest = II->getNormalDest(); + BasicBlockEdge E(DefBB, NormalDest); + return dominates(E, UseBB); +} - IDomB = IDomB->getIDom(); - } +bool DominatorTree::dominates(const BasicBlockEdge &BBE, + const BasicBlock *UseBB) const { + // Assert that we have a single edge. We could handle them by simply + // returning false, but since isSingleEdge is linear on the number of + // edges, the callers can normally handle them more efficiently. + assert(BBE.isSingleEdge()); + + // If the BB the edge ends in doesn't dominate the use BB, then the + // edge also doesn't. + const BasicBlock *Start = BBE.getStart(); + const BasicBlock *End = BBE.getEnd(); + if (!dominates(End, UseBB)) + return false; - return NULL; -} + // Simple case: if the end BB has a single predecessor, the fact that it + // dominates the use block implies that the edge also does. + if (End->getSinglePredecessor()) + return true; -/// assignDFSNumber - Assign In and Out numbers while walking dominator tree -/// in dfs order. -void DomTreeNode::assignDFSNumber(int num) { - std::vector workStack; - std::set visitedNodes; - - workStack.push_back(this); - visitedNodes.insert(this); - this->DFSNumIn = num++; - - while (!workStack.empty()) { - DomTreeNode *Node = workStack.back(); - - bool visitChild = false; - for (std::vector::iterator DI = Node->begin(), - E = Node->end(); DI != E && !visitChild; ++DI) { - DomTreeNode *Child = *DI; - if (visitedNodes.count(Child) == 0) { - visitChild = true; - Child->DFSNumIn = num++; - workStack.push_back(Child); - visitedNodes.insert(Child); - } - } - if (!visitChild) { - // If we reach here means all children are visited - Node->DFSNumOut = num++; - workStack.pop_back(); - } - } -} + // The normal edge from the invoke is critical. Conceptually, what we would + // like to do is split it and check if the new block dominates the use. + // With X being the new block, the graph would look like: + // + // DefBB + // /\ . . + // / \ . . + // / \ . . + // / \ | | + // A X B C + // | \ | / + // . \|/ + // . NormalDest + // . + // + // Given the definition of dominance, NormalDest is dominated by X iff X + // dominates all of NormalDest's predecessors (X, B, C in the example). X + // trivially dominates itself, so we only have to find if it dominates the + // other predecessors. Since the only way out of X is via NormalDest, X can + // only properly dominate a node if NormalDest dominates that node too. + for (const_pred_iterator PI = pred_begin(End), E = pred_end(End); + PI != E; ++PI) { + const BasicBlock *BB = *PI; + if (BB == Start) + continue; -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); + if (!dominates(End, BB)) + return false; } + return true; } -DomTreeNode *DominatorTree::getNodeForBlock(BasicBlock *BB) { - DomTreeNode *&BBNode = DomTreeNodes[BB]; - if (BBNode) 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); - DomTreeNodes[BB] = C; - return BBNode = IDomNode->addChild(C); +bool DominatorTree::dominates(const BasicBlockEdge &BBE, + const Use &U) const { + // Assert that we have a single edge. We could handle them by simply + // returning false, but since isSingleEdge is linear on the number of + // edges, the callers can normally handle them more efficiently. + assert(BBE.isSingleEdge()); + + Instruction *UserInst = cast(U.getUser()); + // A PHI in the end of the edge is dominated by it. + PHINode *PN = dyn_cast(UserInst); + if (PN && PN->getParent() == BBE.getEnd() && + PN->getIncomingBlock(U) == BBE.getStart()) + return true; + + // Otherwise use the edge-dominates-block query, which + // handles the crazy critical edge cases properly. + const BasicBlock *UseBB; + if (PN) + UseBB = PN->getIncomingBlock(U); + else + UseBB = UserInst->getParent(); + return dominates(BBE, UseBB); } -static std::ostream &operator<<(std::ostream &o, - const DomTreeNode *Node) { - if (Node->getBlock()) - WriteAsOperand(o, Node->getBlock(), false); +bool DominatorTree::dominates(const Instruction *Def, + const Use &U) const { + Instruction *UserInst = cast(U.getUser()); + const BasicBlock *DefBB = Def->getParent(); + + // Determine the block in which the use happens. PHI nodes use + // their operands on edges; simulate this by thinking of the use + // happening at the end of the predecessor block. + const BasicBlock *UseBB; + if (PHINode *PN = dyn_cast(UserInst)) + UseBB = PN->getIncomingBlock(U); else - o << " <>"; - return o << "\n"; -} + UseBB = UserInst->getParent(); -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); -} + // Any unreachable use is dominated, even if Def == User. + if (!isReachableFromEntry(UseBB)) + return true; -void DominatorTreeBase::print(std::ostream &o, const Module* ) const { - o << "=============================--------------------------------\n" - << "Inorder Dominator Tree:\n"; - PrintDomTree(getRootNode(), o, 1); -} + // Unreachable definitions don't dominate anything. + if (!isReachableFromEntry(DefBB)) + return false; -void DominatorTreeBase::dump() { - print (llvm::cerr); -} + // Invoke instructions define their return values on the edges + // to their normal successors, so we have to handle them specially. + // Among other things, this means they don't dominate anything in + // their own block, except possibly a phi, so we don't need to + // walk the block in any case. + if (const InvokeInst *II = dyn_cast(Def)) { + BasicBlock *NormalDest = II->getNormalDest(); + BasicBlockEdge E(DefBB, NormalDest); + return dominates(E, U); + } -bool DominatorTree::runOnFunction(Function &F) { - reset(); // Reset from the last time we were run... - Roots.push_back(&F.getEntryBlock()); - calculate(F); - return false; -} + // If the def and use are in different blocks, do a simple CFG dominator + // tree query. + if (DefBB != UseBB) + return dominates(DefBB, UseBB); -//===----------------------------------------------------------------------===// -// DominanceFrontier Implementation -//===----------------------------------------------------------------------===// + // Ok, def and use are in the same block. If the def is an invoke, it + // doesn't dominate anything in the block. If it's a PHI, it dominates + // everything in the block. + if (isa(UserInst)) + return true; -char DominanceFrontier::ID = 0; -static RegisterPass -G("domfrontier", "Dominance Frontier Construction", true); - -// 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); - - 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; - - DominatorTree &DT = getAnalysis(); - bool NewBBDominatesNewBBSucc = true; - if (!DT.dominates(NewBB, NewBBSucc)) - NewBBDominatesNewBBSucc = false; - - // NewBBSucc inherites 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); - } + // Otherwise, just loop through the basic block until we find Def or User. + BasicBlock::const_iterator I = DefBB->begin(); + for (; &*I != Def && &*I != UserInst; ++I) + /*empty*/; - // 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. - if (NewBBDominatesNewBBSucc) { - 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()) { - DominanceFrontier::DomSetType NewBBSet = NewBBI->second; - NewBBSet.insert(Set.begin(), Set.end()); - } 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 dominators of NewBBSucc - if (!DFI->second.count(NewBBSucc)) continue; - - 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) { - // 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); - - break; - } - } - } + return &*I != UserInst; } -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; - }; -} +bool DominatorTree::isReachableFromEntry(const Use &U) const { + Instruction *I = dyn_cast(U.getUser()); -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; -} + // ConstantExprs aren't really reachable from the entry block, but they + // don't need to be treated like unreachable code either. + if (!I) return true; -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"; - } -} + // PHI nodes use their operands on their incoming edges. + if (PHINode *PN = dyn_cast(I)) + return isReachableFromEntry(PN->getIncomingBlock(U)); -void DominanceFrontierBase::dump() { - print (llvm::cerr); + // Everything else uses their operands in their own block. + return isReachableFromEntry(I->getParent()); }