1249259Sdim//===- Dominators.cpp - Dominator Calculation -----------------------------===// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim// This file implements simple dominator construction algorithms for finding 11249259Sdim// forward dominators. Postdominators are available in libanalysis, but are not 12249259Sdim// included in libvmcore, because it's not needed. Forward dominators are 13249259Sdim// needed to support the Verifier pass. 14249259Sdim// 15249259Sdim//===----------------------------------------------------------------------===// 16249259Sdim 17249259Sdim#include "llvm/Analysis/Dominators.h" 18249259Sdim#include "llvm/ADT/DepthFirstIterator.h" 19249259Sdim#include "llvm/ADT/SmallPtrSet.h" 20249259Sdim#include "llvm/ADT/SmallVector.h" 21249259Sdim#include "llvm/Analysis/DominatorInternals.h" 22249259Sdim#include "llvm/Assembly/Writer.h" 23249259Sdim#include "llvm/IR/Instructions.h" 24249259Sdim#include "llvm/Support/CFG.h" 25249259Sdim#include "llvm/Support/CommandLine.h" 26249259Sdim#include "llvm/Support/Compiler.h" 27249259Sdim#include "llvm/Support/Debug.h" 28249259Sdim#include "llvm/Support/raw_ostream.h" 29249259Sdim#include <algorithm> 30249259Sdimusing namespace llvm; 31249259Sdim 32249259Sdim// Always verify dominfo if expensive checking is enabled. 33249259Sdim#ifdef XDEBUG 34249259Sdimstatic bool VerifyDomInfo = true; 35249259Sdim#else 36249259Sdimstatic bool VerifyDomInfo = false; 37249259Sdim#endif 38249259Sdimstatic cl::opt<bool,true> 39249259SdimVerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), 40249259Sdim cl::desc("Verify dominator info (time consuming)")); 41249259Sdim 42249259Sdimbool BasicBlockEdge::isSingleEdge() const { 43249259Sdim const TerminatorInst *TI = Start->getTerminator(); 44249259Sdim unsigned NumEdgesToEnd = 0; 45249259Sdim for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) { 46249259Sdim if (TI->getSuccessor(i) == End) 47249259Sdim ++NumEdgesToEnd; 48249259Sdim if (NumEdgesToEnd >= 2) 49249259Sdim return false; 50249259Sdim } 51249259Sdim assert(NumEdgesToEnd == 1); 52249259Sdim return true; 53249259Sdim} 54249259Sdim 55249259Sdim//===----------------------------------------------------------------------===// 56249259Sdim// DominatorTree Implementation 57249259Sdim//===----------------------------------------------------------------------===// 58249259Sdim// 59249259Sdim// Provide public access to DominatorTree information. Implementation details 60249259Sdim// can be found in DominatorInternals.h. 61249259Sdim// 62249259Sdim//===----------------------------------------------------------------------===// 63249259Sdim 64249259SdimTEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase<BasicBlock>); 65249259SdimTEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase<BasicBlock>); 66249259Sdim 67249259Sdimchar DominatorTree::ID = 0; 68249259SdimINITIALIZE_PASS(DominatorTree, "domtree", 69249259Sdim "Dominator Tree Construction", true, true) 70249259Sdim 71249259Sdimbool DominatorTree::runOnFunction(Function &F) { 72249259Sdim DT->recalculate(F); 73249259Sdim return false; 74249259Sdim} 75249259Sdim 76249259Sdimvoid DominatorTree::verifyAnalysis() const { 77249259Sdim if (!VerifyDomInfo) return; 78249259Sdim 79249259Sdim Function &F = *getRoot()->getParent(); 80249259Sdim 81249259Sdim DominatorTree OtherDT; 82249259Sdim OtherDT.getBase().recalculate(F); 83249259Sdim if (compare(OtherDT)) { 84249259Sdim errs() << "DominatorTree is not up to date!\nComputed:\n"; 85249259Sdim print(errs()); 86249259Sdim errs() << "\nActual:\n"; 87249259Sdim OtherDT.print(errs()); 88249259Sdim abort(); 89249259Sdim } 90249259Sdim} 91249259Sdim 92249259Sdimvoid DominatorTree::print(raw_ostream &OS, const Module *) const { 93249259Sdim DT->print(OS); 94249259Sdim} 95249259Sdim 96249259Sdim// dominates - Return true if Def dominates a use in User. This performs 97249259Sdim// the special checks necessary if Def and User are in the same basic block. 98249259Sdim// Note that Def doesn't dominate a use in Def itself! 99249259Sdimbool DominatorTree::dominates(const Instruction *Def, 100249259Sdim const Instruction *User) const { 101249259Sdim const BasicBlock *UseBB = User->getParent(); 102249259Sdim const BasicBlock *DefBB = Def->getParent(); 103249259Sdim 104249259Sdim // Any unreachable use is dominated, even if Def == User. 105249259Sdim if (!isReachableFromEntry(UseBB)) 106249259Sdim return true; 107249259Sdim 108249259Sdim // Unreachable definitions don't dominate anything. 109249259Sdim if (!isReachableFromEntry(DefBB)) 110249259Sdim return false; 111249259Sdim 112249259Sdim // An instruction doesn't dominate a use in itself. 113249259Sdim if (Def == User) 114249259Sdim return false; 115249259Sdim 116249259Sdim // The value defined by an invoke dominates an instruction only if 117249259Sdim // it dominates every instruction in UseBB. 118249259Sdim // A PHI is dominated only if the instruction dominates every possible use 119249259Sdim // in the UseBB. 120249259Sdim if (isa<InvokeInst>(Def) || isa<PHINode>(User)) 121249259Sdim return dominates(Def, UseBB); 122249259Sdim 123249259Sdim if (DefBB != UseBB) 124249259Sdim return dominates(DefBB, UseBB); 125249259Sdim 126249259Sdim // Loop through the basic block until we find Def or User. 127249259Sdim BasicBlock::const_iterator I = DefBB->begin(); 128249259Sdim for (; &*I != Def && &*I != User; ++I) 129249259Sdim /*empty*/; 130249259Sdim 131249259Sdim return &*I == Def; 132249259Sdim} 133249259Sdim 134249259Sdim// true if Def would dominate a use in any instruction in UseBB. 135249259Sdim// note that dominates(Def, Def->getParent()) is false. 136249259Sdimbool DominatorTree::dominates(const Instruction *Def, 137249259Sdim const BasicBlock *UseBB) const { 138249259Sdim const BasicBlock *DefBB = Def->getParent(); 139249259Sdim 140249259Sdim // Any unreachable use is dominated, even if DefBB == UseBB. 141249259Sdim if (!isReachableFromEntry(UseBB)) 142249259Sdim return true; 143249259Sdim 144249259Sdim // Unreachable definitions don't dominate anything. 145249259Sdim if (!isReachableFromEntry(DefBB)) 146249259Sdim return false; 147249259Sdim 148249259Sdim if (DefBB == UseBB) 149249259Sdim return false; 150249259Sdim 151249259Sdim const InvokeInst *II = dyn_cast<InvokeInst>(Def); 152249259Sdim if (!II) 153249259Sdim return dominates(DefBB, UseBB); 154249259Sdim 155249259Sdim // Invoke results are only usable in the normal destination, not in the 156249259Sdim // exceptional destination. 157249259Sdim BasicBlock *NormalDest = II->getNormalDest(); 158249259Sdim BasicBlockEdge E(DefBB, NormalDest); 159249259Sdim return dominates(E, UseBB); 160249259Sdim} 161249259Sdim 162249259Sdimbool DominatorTree::dominates(const BasicBlockEdge &BBE, 163249259Sdim const BasicBlock *UseBB) const { 164249259Sdim // Assert that we have a single edge. We could handle them by simply 165249259Sdim // returning false, but since isSingleEdge is linear on the number of 166249259Sdim // edges, the callers can normally handle them more efficiently. 167249259Sdim assert(BBE.isSingleEdge()); 168249259Sdim 169249259Sdim // If the BB the edge ends in doesn't dominate the use BB, then the 170249259Sdim // edge also doesn't. 171249259Sdim const BasicBlock *Start = BBE.getStart(); 172249259Sdim const BasicBlock *End = BBE.getEnd(); 173249259Sdim if (!dominates(End, UseBB)) 174249259Sdim return false; 175249259Sdim 176249259Sdim // Simple case: if the end BB has a single predecessor, the fact that it 177249259Sdim // dominates the use block implies that the edge also does. 178249259Sdim if (End->getSinglePredecessor()) 179249259Sdim return true; 180249259Sdim 181249259Sdim // The normal edge from the invoke is critical. Conceptually, what we would 182249259Sdim // like to do is split it and check if the new block dominates the use. 183249259Sdim // With X being the new block, the graph would look like: 184249259Sdim // 185249259Sdim // DefBB 186249259Sdim // /\ . . 187249259Sdim // / \ . . 188249259Sdim // / \ . . 189249259Sdim // / \ | | 190249259Sdim // A X B C 191249259Sdim // | \ | / 192249259Sdim // . \|/ 193249259Sdim // . NormalDest 194249259Sdim // . 195249259Sdim // 196249259Sdim // Given the definition of dominance, NormalDest is dominated by X iff X 197249259Sdim // dominates all of NormalDest's predecessors (X, B, C in the example). X 198249259Sdim // trivially dominates itself, so we only have to find if it dominates the 199249259Sdim // other predecessors. Since the only way out of X is via NormalDest, X can 200249259Sdim // only properly dominate a node if NormalDest dominates that node too. 201249259Sdim for (const_pred_iterator PI = pred_begin(End), E = pred_end(End); 202249259Sdim PI != E; ++PI) { 203249259Sdim const BasicBlock *BB = *PI; 204249259Sdim if (BB == Start) 205249259Sdim continue; 206249259Sdim 207249259Sdim if (!dominates(End, BB)) 208249259Sdim return false; 209249259Sdim } 210249259Sdim return true; 211249259Sdim} 212249259Sdim 213249259Sdimbool DominatorTree::dominates(const BasicBlockEdge &BBE, 214249259Sdim const Use &U) const { 215249259Sdim // Assert that we have a single edge. We could handle them by simply 216249259Sdim // returning false, but since isSingleEdge is linear on the number of 217249259Sdim // edges, the callers can normally handle them more efficiently. 218249259Sdim assert(BBE.isSingleEdge()); 219249259Sdim 220249259Sdim Instruction *UserInst = cast<Instruction>(U.getUser()); 221249259Sdim // A PHI in the end of the edge is dominated by it. 222249259Sdim PHINode *PN = dyn_cast<PHINode>(UserInst); 223249259Sdim if (PN && PN->getParent() == BBE.getEnd() && 224249259Sdim PN->getIncomingBlock(U) == BBE.getStart()) 225249259Sdim return true; 226249259Sdim 227249259Sdim // Otherwise use the edge-dominates-block query, which 228249259Sdim // handles the crazy critical edge cases properly. 229249259Sdim const BasicBlock *UseBB; 230249259Sdim if (PN) 231249259Sdim UseBB = PN->getIncomingBlock(U); 232249259Sdim else 233249259Sdim UseBB = UserInst->getParent(); 234249259Sdim return dominates(BBE, UseBB); 235249259Sdim} 236249259Sdim 237249259Sdimbool DominatorTree::dominates(const Instruction *Def, 238249259Sdim const Use &U) const { 239249259Sdim Instruction *UserInst = cast<Instruction>(U.getUser()); 240249259Sdim const BasicBlock *DefBB = Def->getParent(); 241249259Sdim 242249259Sdim // Determine the block in which the use happens. PHI nodes use 243249259Sdim // their operands on edges; simulate this by thinking of the use 244249259Sdim // happening at the end of the predecessor block. 245249259Sdim const BasicBlock *UseBB; 246249259Sdim if (PHINode *PN = dyn_cast<PHINode>(UserInst)) 247249259Sdim UseBB = PN->getIncomingBlock(U); 248249259Sdim else 249249259Sdim UseBB = UserInst->getParent(); 250249259Sdim 251249259Sdim // Any unreachable use is dominated, even if Def == User. 252249259Sdim if (!isReachableFromEntry(UseBB)) 253249259Sdim return true; 254249259Sdim 255249259Sdim // Unreachable definitions don't dominate anything. 256249259Sdim if (!isReachableFromEntry(DefBB)) 257249259Sdim return false; 258249259Sdim 259249259Sdim // Invoke instructions define their return values on the edges 260249259Sdim // to their normal successors, so we have to handle them specially. 261249259Sdim // Among other things, this means they don't dominate anything in 262249259Sdim // their own block, except possibly a phi, so we don't need to 263249259Sdim // walk the block in any case. 264249259Sdim if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) { 265249259Sdim BasicBlock *NormalDest = II->getNormalDest(); 266249259Sdim BasicBlockEdge E(DefBB, NormalDest); 267249259Sdim return dominates(E, U); 268249259Sdim } 269249259Sdim 270249259Sdim // If the def and use are in different blocks, do a simple CFG dominator 271249259Sdim // tree query. 272249259Sdim if (DefBB != UseBB) 273249259Sdim return dominates(DefBB, UseBB); 274249259Sdim 275249259Sdim // Ok, def and use are in the same block. If the def is an invoke, it 276249259Sdim // doesn't dominate anything in the block. If it's a PHI, it dominates 277249259Sdim // everything in the block. 278249259Sdim if (isa<PHINode>(UserInst)) 279249259Sdim return true; 280249259Sdim 281249259Sdim // Otherwise, just loop through the basic block until we find Def or User. 282249259Sdim BasicBlock::const_iterator I = DefBB->begin(); 283249259Sdim for (; &*I != Def && &*I != UserInst; ++I) 284249259Sdim /*empty*/; 285249259Sdim 286249259Sdim return &*I != UserInst; 287249259Sdim} 288249259Sdim 289249259Sdimbool DominatorTree::isReachableFromEntry(const Use &U) const { 290249259Sdim Instruction *I = dyn_cast<Instruction>(U.getUser()); 291249259Sdim 292249259Sdim // ConstantExprs aren't really reachable from the entry block, but they 293249259Sdim // don't need to be treated like unreachable code either. 294249259Sdim if (!I) return true; 295249259Sdim 296249259Sdim // PHI nodes use their operands on their incoming edges. 297249259Sdim if (PHINode *PN = dyn_cast<PHINode>(I)) 298249259Sdim return isReachableFromEntry(PN->getIncomingBlock(U)); 299249259Sdim 300249259Sdim // Everything else uses their operands in their own block. 301249259Sdim return isReachableFromEntry(I->getParent()); 302249259Sdim} 303