1 //===- Dominators.cpp - Dominator Calculation -----------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements simple dominator construction algorithms for finding 11 // forward dominators. Postdominators are available in libanalysis, but are not 12 // included in libvmcore, because it's not needed. Forward dominators are 13 // needed to support the Verifier pass. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "llvm/Analysis/Dominators.h" 18 #include "llvm/Support/CFG.h" 19 #include "llvm/Support/Compiler.h" 20 #include "llvm/Support/Debug.h" 21 #include "llvm/ADT/DepthFirstIterator.h" 22 #include "llvm/ADT/SmallPtrSet.h" 23 #include "llvm/ADT/SmallVector.h" 24 #include "llvm/Analysis/DominatorInternals.h" 25 #include "llvm/Assembly/Writer.h" 26 #include "llvm/Instructions.h" 27 #include "llvm/Support/raw_ostream.h" 28 #include "llvm/Support/CommandLine.h" 29 #include <algorithm> 30 using namespace llvm; 31 32 // Always verify dominfo if expensive checking is enabled. 33 #ifdef XDEBUG 34 static bool VerifyDomInfo = true; 35 #else 36 static bool VerifyDomInfo = false; 37 #endif 38 static cl::opt<bool,true> 39 VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), 40 cl::desc("Verify dominator info (time consuming)")); 41 42 //===----------------------------------------------------------------------===// 43 // DominatorTree Implementation 44 //===----------------------------------------------------------------------===// 45 // 46 // Provide public access to DominatorTree information. Implementation details 47 // can be found in DominatorInternals.h. 48 // 49 //===----------------------------------------------------------------------===// 50 51 TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase<BasicBlock>); 52 TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase<BasicBlock>); 53 54 char DominatorTree::ID = 0; 55 INITIALIZE_PASS(DominatorTree, "domtree", 56 "Dominator Tree Construction", true, true) 57 58 bool DominatorTree::runOnFunction(Function &F) { 59 DT->recalculate(F); 60 return false; 61 } 62 63 void DominatorTree::verifyAnalysis() const { 64 if (!VerifyDomInfo) return; 65 66 Function &F = *getRoot()->getParent(); 67 68 DominatorTree OtherDT; 69 OtherDT.getBase().recalculate(F); 70 if (compare(OtherDT)) { 71 errs() << "DominatorTree is not up to date!\nComputed:\n"; 72 print(errs()); 73 errs() << "\nActual:\n"; 74 OtherDT.print(errs()); 75 abort(); 76 } 77 } 78 79 void DominatorTree::print(raw_ostream &OS, const Module *) const { 80 DT->print(OS); 81 } 82 83 // dominates - Return true if A dominates a use in B. This performs the 84 // special checks necessary if A and B are in the same basic block. 85 bool DominatorTree::dominates(const Instruction *A, const Instruction *B) const{ 86 const BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 87 88 // If A is an invoke instruction, its value is only available in this normal 89 // successor block. 90 if (const InvokeInst *II = dyn_cast<InvokeInst>(A)) 91 BBA = II->getNormalDest(); 92 93 if (BBA != BBB) return dominates(BBA, BBB); 94 95 // It is not possible to determine dominance between two PHI nodes 96 // based on their ordering. 97 if (isa<PHINode>(A) && isa<PHINode>(B)) 98 return false; 99 100 // Loop through the basic block until we find A or B. 101 BasicBlock::const_iterator I = BBA->begin(); 102 for (; &*I != A && &*I != B; ++I) 103 /*empty*/; 104 105 return &*I == A; 106 } 107
