X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FDominators.cpp;h=77b2403d87dd1873538d3337593f27ad5eefed21;hb=3756e70af69096a82b367ee9667e7720ca2201e4;hp=08b845ef9d6b44ae98ca91ead5982289022561d5;hpb=0f4158790916352a52f105dbfb638c9a0db00321;p=oota-llvm.git diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 08b845ef9d6..77b2403d87d 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -39,6 +39,19 @@ 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 //===----------------------------------------------------------------------===// @@ -80,27 +93,210 @@ 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)) +// 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(); + + // Any unreachable use is dominated, even if Def == User. + if (!isReachableFromEntry(UseBB)) + return true; + + // Unreachable definitions don't dominate anything. + if (!isReachableFromEntry(DefBB)) + return false; + + // An instruction doesn't dominate a use in itself. + if (Def == User) + return false; + + // 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); + + if (DefBB != UseBB) + return dominates(DefBB, UseBB); + + // Loop through the basic block until we find Def or User. + BasicBlock::const_iterator I = DefBB->begin(); + for (; &*I != Def && &*I != User; ++I) + /*empty*/; + + return &*I == Def; +} + +// 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(); + + // Any unreachable use is dominated, even if DefBB == UseBB. + if (!isReachableFromEntry(UseBB)) + return true; + + // Unreachable definitions don't dominate anything. + if (!isReachableFromEntry(DefBB)) + return false; + + if (DefBB == UseBB) + return false; + + const InvokeInst *II = dyn_cast(Def); + if (!II) + return dominates(DefBB, UseBB); + + // 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); +} + +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; + + // 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; + + // 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; + + if (!dominates(End, BB)) + return false; + } + return true; +} + +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); +} + +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 + UseBB = UserInst->getParent(); + + // Any unreachable use is dominated, even if Def == User. + if (!isReachableFromEntry(UseBB)) + return true; + + // Unreachable definitions don't dominate anything. + if (!isReachableFromEntry(DefBB)) 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) + + // 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); + } + + // If the def and use are in different blocks, do a simple CFG dominator + // tree query. + if (DefBB != UseBB) + return dominates(DefBB, UseBB); + + // 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; + + // 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*/; - - return &*I == A; + + return &*I != UserInst; +} + +bool DominatorTree::isReachableFromEntry(const Use &U) const { + Instruction *I = dyn_cast(U.getUser()); + + // 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; + + // PHI nodes use their operands on their incoming edges. + if (PHINode *PN = dyn_cast(I)) + return isReachableFromEntry(PN->getIncomingBlock(U)); + + // Everything else uses their operands in their own block. + return isReachableFromEntry(I->getParent()); }