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 Def dominates a use in User. This performs 84 // the special checks necessary if Def and User are in the same basic block. 85 // Note that Def doesn't dominate a use in Def itself! 86 bool DominatorTree::dominates(const Instruction *Def, 87 const Instruction *User) const { 88 const BasicBlock *UseBB = User->getParent(); 89 const BasicBlock *DefBB = Def->getParent(); 90 91 // Any unreachable use is dominated, even if Def == User. 92 if (!isReachableFromEntry(UseBB)) 93 return true; 94 95 // Unreachable definitions don't dominate anything. 96 if (!isReachableFromEntry(DefBB)) 97 return false; 98 99 // An instruction doesn't dominate a use in itself. 100 if (Def == User) 101 return false; 102 103 // The value defined by an invoke dominates an instruction only if 104 // it dominates every instruction in UseBB. 105 // A PHI is dominated only if the instruction dominates every possible use 106 // in the UseBB. 107 if (isa<InvokeInst>(Def) || isa<PHINode>(User)) 108 return dominates(Def, UseBB); 109 110 if (DefBB != UseBB) 111 return dominates(DefBB, UseBB); 112 113 // Loop through the basic block until we find Def or User. 114 BasicBlock::const_iterator I = DefBB->begin(); 115 for (; &*I != Def && &*I != User; ++I) 116 /*empty*/; 117 118 return &*I == Def; 119 } 120 121 // true if Def would dominate a use in any instruction in UseBB. 122 // note that dominates(Def, Def->getParent()) is false. 123 bool DominatorTree::dominates(const Instruction *Def, 124 const BasicBlock *UseBB) const { 125 const BasicBlock *DefBB = Def->getParent(); 126 127 // Any unreachable use is dominated, even if DefBB == UseBB. 128 if (!isReachableFromEntry(UseBB)) 129 return true; 130 131 // Unreachable definitions don't dominate anything. 132 if (!isReachableFromEntry(DefBB)) 133 return false; 134 135 if (DefBB == UseBB) 136 return false; 137 138 const InvokeInst *II = dyn_cast<InvokeInst>(Def); 139 if (!II) 140 return dominates(DefBB, UseBB); 141 142 // Invoke results are only usable in the normal destination, not in the 143 // exceptional destination. 144 BasicBlock *NormalDest = II->getNormalDest(); 145 if (!dominates(NormalDest, UseBB)) 146 return false; 147 148 // Simple case: if the normal destination has a single predecessor, the 149 // fact that it dominates the use block implies that we also do. 150 if (NormalDest->getSinglePredecessor()) 151 return true; 152 153 // The normal edge from the invoke is critical. Conceptually, what we would 154 // like to do is split it and check if the new block dominates the use. 155 // With X being the new block, the graph would look like: 156 // 157 // DefBB 158 // /\ . . 159 // / \ . . 160 // / \ . . 161 // / \ | | 162 // A X B C 163 // | \ | / 164 // . \|/ 165 // . NormalDest 166 // . 167 // 168 // Given the definition of dominance, NormalDest is dominated by X iff X 169 // dominates all of NormalDest's predecessors (X, B, C in the example). X 170 // trivially dominates itself, so we only have to find if it dominates the 171 // other predecessors. Since the only way out of X is via NormalDest, X can 172 // only properly dominate a node if NormalDest dominates that node too. 173 for (pred_iterator PI = pred_begin(NormalDest), 174 E = pred_end(NormalDest); PI != E; ++PI) { 175 const BasicBlock *BB = *PI; 176 if (BB == DefBB) 177 continue; 178 179 if (!DT->isReachableFromEntry(BB)) 180 continue; 181 182 if (!dominates(NormalDest, BB)) 183 return false; 184 } 185 return true; 186 } 187 188 bool DominatorTree::dominates(const Instruction *Def, 189 const Use &U) const { 190 Instruction *UserInst = dyn_cast<Instruction>(U.getUser()); 191 192 // Instructions do not dominate non-instructions. 193 if (!UserInst) 194 return false; 195 196 const BasicBlock *DefBB = Def->getParent(); 197 198 // Determine the block in which the use happens. PHI nodes use 199 // their operands on edges; simulate this by thinking of the use 200 // happening at the end of the predecessor block. 201 const BasicBlock *UseBB; 202 if (PHINode *PN = dyn_cast<PHINode>(UserInst)) 203 UseBB = PN->getIncomingBlock(U); 204 else 205 UseBB = UserInst->getParent(); 206 207 // Any unreachable use is dominated, even if Def == User. 208 if (!isReachableFromEntry(UseBB)) 209 return true; 210 211 // Unreachable definitions don't dominate anything. 212 if (!isReachableFromEntry(DefBB)) 213 return false; 214 215 // Invoke instructions define their return values on the edges 216 // to their normal successors, so we have to handle them specially. 217 // Among other things, this means they don't dominate anything in 218 // their own block, except possibly a phi, so we don't need to 219 // walk the block in any case. 220 if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) { 221 // A PHI in the normal successor using the invoke's return value is 222 // dominated by the invoke's return value. 223 if (isa<PHINode>(UserInst) && 224 UserInst->getParent() == II->getNormalDest() && 225 cast<PHINode>(UserInst)->getIncomingBlock(U) == DefBB) 226 return true; 227 228 // Otherwise use the instruction-dominates-block query, which 229 // handles the crazy case of an invoke with a critical edge 230 // properly. 231 return dominates(Def, UseBB); 232 } 233 234 // If the def and use are in different blocks, do a simple CFG dominator 235 // tree query. 236 if (DefBB != UseBB) 237 return dominates(DefBB, UseBB); 238 239 // Ok, def and use are in the same block. If the def is an invoke, it 240 // doesn't dominate anything in the block. If it's a PHI, it dominates 241 // everything in the block. 242 if (isa<PHINode>(UserInst)) 243 return true; 244 245 // Otherwise, just loop through the basic block until we find Def or User. 246 BasicBlock::const_iterator I = DefBB->begin(); 247 for (; &*I != Def && &*I != UserInst; ++I) 248 /*empty*/; 249 250 return &*I != UserInst; 251 } 252 253 bool DominatorTree::isReachableFromEntry(const Use &U) const { 254 Instruction *I = dyn_cast<Instruction>(U.getUser()); 255 256 // ConstantExprs aren't really reachable from the entry block, but they 257 // don't need to be treated like unreachable code either. 258 if (!I) return true; 259 260 // PHI nodes use their operands on their incoming edges. 261 if (PHINode *PN = dyn_cast<PHINode>(I)) 262 return isReachableFromEntry(PN->getIncomingBlock(U)); 263 264 // Everything else uses their operands in their own block. 265 return isReachableFromEntry(I->getParent()); 266 } 267
