Dominators.cpp revision 280031
1303233Sdim//===- Dominators.cpp - Dominator Calculation -----------------------------===// 2303233Sdim// 3353358Sdim// The LLVM Compiler Infrastructure 4353358Sdim// 5353358Sdim// This file is distributed under the University of Illinois Open Source 6303233Sdim// License. See LICENSE.TXT for details. 7303233Sdim// 8303233Sdim//===----------------------------------------------------------------------===// 9303233Sdim// 10303233Sdim// This file implements simple dominator construction algorithms for finding 11303233Sdim// forward dominators. Postdominators are available in libanalysis, but are not 12303233Sdim// included in libvmcore, because it's not needed. Forward dominators are 13303233Sdim// needed to support the Verifier pass. 14314564Sdim// 15303233Sdim//===----------------------------------------------------------------------===// 16303233Sdim 17303233Sdim#include "llvm/IR/Dominators.h" 18303233Sdim#include "llvm/ADT/DepthFirstIterator.h" 19303233Sdim#include "llvm/ADT/SmallPtrSet.h" 20303233Sdim#include "llvm/ADT/SmallVector.h" 21303233Sdim#include "llvm/IR/CFG.h" 22303233Sdim#include "llvm/IR/Instructions.h" 23303233Sdim#include "llvm/IR/PassManager.h" 24303233Sdim#include "llvm/Support/CommandLine.h" 25303233Sdim#include "llvm/Support/Compiler.h" 26303233Sdim#include "llvm/Support/Debug.h" 27303233Sdim#include "llvm/Support/GenericDomTreeConstruction.h" 28303233Sdim#include "llvm/Support/raw_ostream.h" 29303233Sdim#include <algorithm> 30303233Sdimusing namespace llvm; 31303233Sdim 32303233Sdim// Always verify dominfo if expensive checking is enabled. 33303233Sdim#ifdef XDEBUG 34303233Sdimstatic bool VerifyDomInfo = true; 35303233Sdim#else 36303233Sdimstatic bool VerifyDomInfo = false; 37303233Sdim#endif 38303233Sdimstatic cl::opt<bool,true> 39303233SdimVerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), 40303233Sdim cl::desc("Verify dominator info (time consuming)")); 41303233Sdim 42303233Sdimbool BasicBlockEdge::isSingleEdge() const { 43303233Sdim const TerminatorInst *TI = Start->getTerminator(); 44303233Sdim unsigned NumEdgesToEnd = 0; 45303233Sdim for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) { 46303233Sdim if (TI->getSuccessor(i) == End) 47303233Sdim ++NumEdgesToEnd; 48303233Sdim if (NumEdgesToEnd >= 2) 49303233Sdim return false; 50303233Sdim } 51303233Sdim assert(NumEdgesToEnd == 1); 52303233Sdim return true; 53303233Sdim} 54303233Sdim 55303233Sdim//===----------------------------------------------------------------------===// 56303233Sdim// DominatorTree Implementation 57303233Sdim//===----------------------------------------------------------------------===// 58303233Sdim// 59303233Sdim// Provide public access to DominatorTree information. Implementation details 60303233Sdim// can be found in Dominators.h, GenericDomTree.h, and 61303233Sdim// GenericDomTreeConstruction.h. 62303233Sdim// 63303233Sdim//===----------------------------------------------------------------------===// 64303233Sdim 65303233SdimTEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase<BasicBlock>); 66303233SdimTEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase<BasicBlock>); 67303233Sdim 68303233Sdim#define LLVM_COMMA , 69303233SdimTEMPLATE_INSTANTIATION(void llvm::Calculate<Function LLVM_COMMA BasicBlock *>( 70303233Sdim DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA 71303233Sdim Function &F)); 72303233SdimTEMPLATE_INSTANTIATION( 73303233Sdim void llvm::Calculate<Function LLVM_COMMA Inverse<BasicBlock *> >( 74303233Sdim DominatorTreeBase<GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT 75303233Sdim LLVM_COMMA Function &F)); 76303233Sdim#undef LLVM_COMMA 77303233Sdim 78303233Sdim// dominates - Return true if Def dominates a use in User. This performs 79303233Sdim// the special checks necessary if Def and User are in the same basic block. 80303233Sdim// Note that Def doesn't dominate a use in Def itself! 81303233Sdimbool DominatorTree::dominates(const Instruction *Def, 82303233Sdim const Instruction *User) const { 83303233Sdim const BasicBlock *UseBB = User->getParent(); 84303233Sdim const BasicBlock *DefBB = Def->getParent(); 85303233Sdim 86303233Sdim // Any unreachable use is dominated, even if Def == User. 87303233Sdim if (!isReachableFromEntry(UseBB)) 88303233Sdim return true; 89303233Sdim 90303233Sdim // Unreachable definitions don't dominate anything. 91303233Sdim if (!isReachableFromEntry(DefBB)) 92303233Sdim return false; 93303233Sdim 94303233Sdim // An instruction doesn't dominate a use in itself. 95303233Sdim if (Def == User) 96303233Sdim return false; 97303233Sdim 98303233Sdim // The value defined by an invoke dominates an instruction only if 99303233Sdim // it dominates every instruction in UseBB. 100303233Sdim // A PHI is dominated only if the instruction dominates every possible use 101303233Sdim // in the UseBB. 102303233Sdim if (isa<InvokeInst>(Def) || isa<PHINode>(User)) 103303233Sdim return dominates(Def, UseBB); 104303233Sdim 105303233Sdim if (DefBB != UseBB) 106303233Sdim return dominates(DefBB, UseBB); 107303233Sdim 108303233Sdim // Loop through the basic block until we find Def or User. 109303233Sdim BasicBlock::const_iterator I = DefBB->begin(); 110303233Sdim for (; &*I != Def && &*I != User; ++I) 111303233Sdim /*empty*/; 112303233Sdim 113303233Sdim return &*I == Def; 114303233Sdim} 115303233Sdim 116303233Sdim// true if Def would dominate a use in any instruction in UseBB. 117303233Sdim// note that dominates(Def, Def->getParent()) is false. 118303233Sdimbool DominatorTree::dominates(const Instruction *Def, 119303233Sdim const BasicBlock *UseBB) const { 120303233Sdim const BasicBlock *DefBB = Def->getParent(); 121303233Sdim 122303233Sdim // Any unreachable use is dominated, even if DefBB == UseBB. 123303233Sdim if (!isReachableFromEntry(UseBB)) 124303233Sdim return true; 125303233Sdim 126303233Sdim // Unreachable definitions don't dominate anything. 127303233Sdim if (!isReachableFromEntry(DefBB)) 128303233Sdim return false; 129303233Sdim 130303233Sdim if (DefBB == UseBB) 131303233Sdim return false; 132303233Sdim 133303233Sdim const InvokeInst *II = dyn_cast<InvokeInst>(Def); 134303233Sdim if (!II) 135303233Sdim return dominates(DefBB, UseBB); 136303233Sdim 137303233Sdim // Invoke results are only usable in the normal destination, not in the 138303233Sdim // exceptional destination. 139303233Sdim BasicBlock *NormalDest = II->getNormalDest(); 140303233Sdim BasicBlockEdge E(DefBB, NormalDest); 141303233Sdim return dominates(E, UseBB); 142303233Sdim} 143303233Sdim 144303233Sdimbool DominatorTree::dominates(const BasicBlockEdge &BBE, 145303233Sdim const BasicBlock *UseBB) const { 146303233Sdim // Assert that we have a single edge. We could handle them by simply 147303233Sdim // returning false, but since isSingleEdge is linear on the number of 148303233Sdim // edges, the callers can normally handle them more efficiently. 149303233Sdim assert(BBE.isSingleEdge()); 150303233Sdim 151303233Sdim // If the BB the edge ends in doesn't dominate the use BB, then the 152303233Sdim // edge also doesn't. 153303233Sdim const BasicBlock *Start = BBE.getStart(); 154303233Sdim const BasicBlock *End = BBE.getEnd(); 155303233Sdim if (!dominates(End, UseBB)) 156303233Sdim return false; 157303233Sdim 158303233Sdim // Simple case: if the end BB has a single predecessor, the fact that it 159303233Sdim // dominates the use block implies that the edge also does. 160303233Sdim if (End->getSinglePredecessor()) 161303233Sdim return true; 162303233Sdim 163303233Sdim // The normal edge from the invoke is critical. Conceptually, what we would 164303233Sdim // like to do is split it and check if the new block dominates the use. 165303233Sdim // With X being the new block, the graph would look like: 166303233Sdim // 167303233Sdim // DefBB 168303233Sdim // /\ . . 169303233Sdim // / \ . . 170303233Sdim // / \ . . 171303233Sdim // / \ | | 172303233Sdim // A X B C 173303233Sdim // | \ | / 174303233Sdim // . \|/ 175303233Sdim // . NormalDest 176303233Sdim // . 177303233Sdim // 178303233Sdim // Given the definition of dominance, NormalDest is dominated by X iff X 179303233Sdim // dominates all of NormalDest's predecessors (X, B, C in the example). X 180303233Sdim // trivially dominates itself, so we only have to find if it dominates the 181303233Sdim // other predecessors. Since the only way out of X is via NormalDest, X can 182303233Sdim // only properly dominate a node if NormalDest dominates that node too. 183303233Sdim for (const_pred_iterator PI = pred_begin(End), E = pred_end(End); 184303233Sdim PI != E; ++PI) { 185303233Sdim const BasicBlock *BB = *PI; 186303233Sdim if (BB == Start) 187303233Sdim continue; 188303233Sdim 189303233Sdim if (!dominates(End, BB)) 190303233Sdim return false; 191303233Sdim } 192303233Sdim return true; 193303233Sdim} 194303233Sdim 195303233Sdimbool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const { 196303233Sdim // Assert that we have a single edge. We could handle them by simply 197303233Sdim // returning false, but since isSingleEdge is linear on the number of 198303233Sdim // edges, the callers can normally handle them more efficiently. 199303233Sdim assert(BBE.isSingleEdge()); 200303233Sdim 201303233Sdim Instruction *UserInst = cast<Instruction>(U.getUser()); 202303233Sdim // A PHI in the end of the edge is dominated by it. 203303233Sdim PHINode *PN = dyn_cast<PHINode>(UserInst); 204303233Sdim if (PN && PN->getParent() == BBE.getEnd() && 205303233Sdim PN->getIncomingBlock(U) == BBE.getStart()) 206303233Sdim return true; 207303233Sdim 208303233Sdim // Otherwise use the edge-dominates-block query, which 209303233Sdim // handles the crazy critical edge cases properly. 210303233Sdim const BasicBlock *UseBB; 211303233Sdim if (PN) 212303233Sdim UseBB = PN->getIncomingBlock(U); 213303233Sdim else 214303233Sdim UseBB = UserInst->getParent(); 215303233Sdim return dominates(BBE, UseBB); 216303233Sdim} 217303233Sdim 218303233Sdimbool DominatorTree::dominates(const Instruction *Def, const Use &U) const { 219303233Sdim Instruction *UserInst = cast<Instruction>(U.getUser()); 220303233Sdim const BasicBlock *DefBB = Def->getParent(); 221303233Sdim 222303233Sdim // Determine the block in which the use happens. PHI nodes use 223303233Sdim // their operands on edges; simulate this by thinking of the use 224303233Sdim // happening at the end of the predecessor block. 225303233Sdim const BasicBlock *UseBB; 226303233Sdim if (PHINode *PN = dyn_cast<PHINode>(UserInst)) 227303233Sdim UseBB = PN->getIncomingBlock(U); 228303233Sdim else 229303233Sdim UseBB = UserInst->getParent(); 230303233Sdim 231303233Sdim // Any unreachable use is dominated, even if Def == User. 232303233Sdim if (!isReachableFromEntry(UseBB)) 233303233Sdim return true; 234303233Sdim 235303233Sdim // Unreachable definitions don't dominate anything. 236303233Sdim if (!isReachableFromEntry(DefBB)) 237303233Sdim return false; 238303233Sdim 239303233Sdim // Invoke instructions define their return values on the edges 240303233Sdim // to their normal successors, so we have to handle them specially. 241303233Sdim // Among other things, this means they don't dominate anything in 242303233Sdim // their own block, except possibly a phi, so we don't need to 243303233Sdim // walk the block in any case. 244303233Sdim if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) { 245303233Sdim BasicBlock *NormalDest = II->getNormalDest(); 246303233Sdim BasicBlockEdge E(DefBB, NormalDest); 247303233Sdim return dominates(E, U); 248303233Sdim } 249303233Sdim 250303233Sdim // If the def and use are in different blocks, do a simple CFG dominator 251303233Sdim // tree query. 252303233Sdim if (DefBB != UseBB) 253303233Sdim return dominates(DefBB, UseBB); 254303233Sdim 255303233Sdim // Ok, def and use are in the same block. If the def is an invoke, it 256303233Sdim // doesn't dominate anything in the block. If it's a PHI, it dominates 257303233Sdim // everything in the block. 258303233Sdim if (isa<PHINode>(UserInst)) 259303233Sdim return true; 260303233Sdim 261303233Sdim // Otherwise, just loop through the basic block until we find Def or User. 262303233Sdim BasicBlock::const_iterator I = DefBB->begin(); 263303233Sdim for (; &*I != Def && &*I != UserInst; ++I) 264303233Sdim /*empty*/; 265303233Sdim 266303233Sdim return &*I != UserInst; 267303233Sdim} 268303233Sdim 269303233Sdimbool DominatorTree::isReachableFromEntry(const Use &U) const { 270303233Sdim Instruction *I = dyn_cast<Instruction>(U.getUser()); 271303233Sdim 272303233Sdim // ConstantExprs aren't really reachable from the entry block, but they 273303233Sdim // don't need to be treated like unreachable code either. 274303233Sdim if (!I) return true; 275303233Sdim 276303233Sdim // PHI nodes use their operands on their incoming edges. 277303233Sdim if (PHINode *PN = dyn_cast<PHINode>(I)) 278303233Sdim return isReachableFromEntry(PN->getIncomingBlock(U)); 279303233Sdim 280303233Sdim // Everything else uses their operands in their own block. 281303233Sdim return isReachableFromEntry(I->getParent()); 282303233Sdim} 283303233Sdim 284void DominatorTree::verifyDomTree() const { 285 if (!VerifyDomInfo) 286 return; 287 288 Function &F = *getRoot()->getParent(); 289 290 DominatorTree OtherDT; 291 OtherDT.recalculate(F); 292 if (compare(OtherDT)) { 293 errs() << "DominatorTree is not up to date!\nComputed:\n"; 294 print(errs()); 295 errs() << "\nActual:\n"; 296 OtherDT.print(errs()); 297 abort(); 298 } 299} 300 301//===----------------------------------------------------------------------===// 302// DominatorTreeAnalysis and related pass implementations 303//===----------------------------------------------------------------------===// 304// 305// This implements the DominatorTreeAnalysis which is used with the new pass 306// manager. It also implements some methods from utility passes. 307// 308//===----------------------------------------------------------------------===// 309 310DominatorTree DominatorTreeAnalysis::run(Function &F) { 311 DominatorTree DT; 312 DT.recalculate(F); 313 return DT; 314} 315 316char DominatorTreeAnalysis::PassID; 317 318DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {} 319 320PreservedAnalyses DominatorTreePrinterPass::run(Function &F, 321 FunctionAnalysisManager *AM) { 322 OS << "DominatorTree for function: " << F.getName() << "\n"; 323 AM->getResult<DominatorTreeAnalysis>(F).print(OS); 324 325 return PreservedAnalyses::all(); 326} 327 328PreservedAnalyses DominatorTreeVerifierPass::run(Function &F, 329 FunctionAnalysisManager *AM) { 330 AM->getResult<DominatorTreeAnalysis>(F).verifyDomTree(); 331 332 return PreservedAnalyses::all(); 333} 334 335//===----------------------------------------------------------------------===// 336// DominatorTreeWrapperPass Implementation 337//===----------------------------------------------------------------------===// 338// 339// The implementation details of the wrapper pass that holds a DominatorTree 340// suitable for use with the legacy pass manager. 341// 342//===----------------------------------------------------------------------===// 343 344char DominatorTreeWrapperPass::ID = 0; 345INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree", 346 "Dominator Tree Construction", true, true) 347 348bool DominatorTreeWrapperPass::runOnFunction(Function &F) { 349 DT.recalculate(F); 350 return false; 351} 352 353void DominatorTreeWrapperPass::verifyAnalysis() const { DT.verifyDomTree(); } 354 355void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const { 356 DT.print(OS); 357} 358 359