1 //===- Dominators.cpp - Dominator Calculation -----------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements simple dominator construction algorithms for finding 10 // forward dominators. Postdominators are available in libanalysis, but are not 11 // included in libvmcore, because it's not needed. Forward dominators are 12 // needed to support the Verifier pass. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/IR/Dominators.h" 17 #include "llvm/ADT/StringRef.h" 18 #include "llvm/Config/llvm-config.h" 19 #include "llvm/IR/CFG.h" 20 #include "llvm/IR/Function.h" 21 #include "llvm/IR/Instruction.h" 22 #include "llvm/IR/Instructions.h" 23 #include "llvm/IR/PassManager.h" 24 #include "llvm/InitializePasses.h" 25 #include "llvm/PassRegistry.h" 26 #include "llvm/Support/Casting.h" 27 #include "llvm/Support/CommandLine.h" 28 #include "llvm/Support/raw_ostream.h" 29 30 #include <cassert> 31 32 namespace llvm { 33 class Argument; 34 class Constant; 35 class Value; 36 } // namespace llvm 37 using namespace llvm; 38 39 bool llvm::VerifyDomInfo = false; 40 static cl::opt<bool, true> 41 VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden, 42 cl::desc("Verify dominator info (time consuming)")); 43 44 #ifdef EXPENSIVE_CHECKS 45 static constexpr bool ExpensiveChecksEnabled = true; 46 #else 47 static constexpr bool ExpensiveChecksEnabled = false; 48 #endif 49 50 bool BasicBlockEdge::isSingleEdge() const { 51 const Instruction *TI = Start->getTerminator(); 52 unsigned NumEdgesToEnd = 0; 53 for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) { 54 if (TI->getSuccessor(i) == End) 55 ++NumEdgesToEnd; 56 if (NumEdgesToEnd >= 2) 57 return false; 58 } 59 assert(NumEdgesToEnd == 1); 60 return true; 61 } 62 63 //===----------------------------------------------------------------------===// 64 // DominatorTree Implementation 65 //===----------------------------------------------------------------------===// 66 // 67 // Provide public access to DominatorTree information. Implementation details 68 // can be found in Dominators.h, GenericDomTree.h, and 69 // GenericDomTreeConstruction.h. 70 // 71 //===----------------------------------------------------------------------===// 72 73 template class llvm::DomTreeNodeBase<BasicBlock>; 74 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase 75 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase 76 77 template class llvm::cfg::Update<BasicBlock *>; 78 79 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>( 80 DomTreeBuilder::BBDomTree &DT); 81 template void 82 llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>( 83 DomTreeBuilder::BBDomTree &DT, BBUpdates U); 84 85 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>( 86 DomTreeBuilder::BBPostDomTree &DT); 87 // No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises. 88 89 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>( 90 DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To); 91 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>( 92 DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); 93 94 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>( 95 DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To); 96 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>( 97 DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); 98 99 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>( 100 DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBDomTreeGraphDiff &, 101 DomTreeBuilder::BBDomTreeGraphDiff *); 102 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>( 103 DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBPostDomTreeGraphDiff &, 104 DomTreeBuilder::BBPostDomTreeGraphDiff *); 105 106 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>( 107 const DomTreeBuilder::BBDomTree &DT, 108 DomTreeBuilder::BBDomTree::VerificationLevel VL); 109 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>( 110 const DomTreeBuilder::BBPostDomTree &DT, 111 DomTreeBuilder::BBPostDomTree::VerificationLevel VL); 112 113 bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA, 114 FunctionAnalysisManager::Invalidator &) { 115 // Check whether the analysis, all analyses on functions, or the function's 116 // CFG have been preserved. 117 auto PAC = PA.getChecker<DominatorTreeAnalysis>(); 118 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() || 119 PAC.preservedSet<CFGAnalyses>()); 120 } 121 122 bool DominatorTree::dominates(const BasicBlock *BB, const Use &U) const { 123 Instruction *UserInst = cast<Instruction>(U.getUser()); 124 if (auto *PN = dyn_cast<PHINode>(UserInst)) 125 // A phi use using a value from a block is dominated by the end of that 126 // block. Note that the phi's parent block may not be. 127 return dominates(BB, PN->getIncomingBlock(U)); 128 else 129 return properlyDominates(BB, UserInst->getParent()); 130 } 131 132 // dominates - Return true if Def dominates a use in User. This performs 133 // the special checks necessary if Def and User are in the same basic block. 134 // Note that Def doesn't dominate a use in Def itself! 135 bool DominatorTree::dominates(const Value *DefV, 136 const Instruction *User) const { 137 const Instruction *Def = dyn_cast<Instruction>(DefV); 138 if (!Def) { 139 assert((isa<Argument>(DefV) || isa<Constant>(DefV)) && 140 "Should be called with an instruction, argument or constant"); 141 return true; // Arguments and constants dominate everything. 142 } 143 144 const BasicBlock *UseBB = User->getParent(); 145 const BasicBlock *DefBB = Def->getParent(); 146 147 // Any unreachable use is dominated, even if Def == User. 148 if (!isReachableFromEntry(UseBB)) 149 return true; 150 151 // Unreachable definitions don't dominate anything. 152 if (!isReachableFromEntry(DefBB)) 153 return false; 154 155 // An instruction doesn't dominate a use in itself. 156 if (Def == User) 157 return false; 158 159 // The value defined by an invoke dominates an instruction only if it 160 // dominates every instruction in UseBB. 161 // A PHI is dominated only if the instruction dominates every possible use in 162 // the UseBB. 163 if (isa<InvokeInst>(Def) || isa<CallBrInst>(Def) || isa<PHINode>(User)) 164 return dominates(Def, UseBB); 165 166 if (DefBB != UseBB) 167 return dominates(DefBB, UseBB); 168 169 return Def->comesBefore(User); 170 } 171 172 // true if Def would dominate a use in any instruction in UseBB. 173 // note that dominates(Def, Def->getParent()) is false. 174 bool DominatorTree::dominates(const Instruction *Def, 175 const BasicBlock *UseBB) const { 176 const BasicBlock *DefBB = Def->getParent(); 177 178 // Any unreachable use is dominated, even if DefBB == UseBB. 179 if (!isReachableFromEntry(UseBB)) 180 return true; 181 182 // Unreachable definitions don't dominate anything. 183 if (!isReachableFromEntry(DefBB)) 184 return false; 185 186 if (DefBB == UseBB) 187 return false; 188 189 // Invoke results are only usable in the normal destination, not in the 190 // exceptional destination. 191 if (const auto *II = dyn_cast<InvokeInst>(Def)) { 192 BasicBlock *NormalDest = II->getNormalDest(); 193 BasicBlockEdge E(DefBB, NormalDest); 194 return dominates(E, UseBB); 195 } 196 197 // Callbr results are similarly only usable in the default destination. 198 if (const auto *CBI = dyn_cast<CallBrInst>(Def)) { 199 BasicBlock *NormalDest = CBI->getDefaultDest(); 200 BasicBlockEdge E(DefBB, NormalDest); 201 return dominates(E, UseBB); 202 } 203 204 return dominates(DefBB, UseBB); 205 } 206 207 bool DominatorTree::dominates(const BasicBlockEdge &BBE, 208 const BasicBlock *UseBB) const { 209 // If the BB the edge ends in doesn't dominate the use BB, then the 210 // edge also doesn't. 211 const BasicBlock *Start = BBE.getStart(); 212 const BasicBlock *End = BBE.getEnd(); 213 if (!dominates(End, UseBB)) 214 return false; 215 216 // Simple case: if the end BB has a single predecessor, the fact that it 217 // dominates the use block implies that the edge also does. 218 if (End->getSinglePredecessor()) 219 return true; 220 221 // The normal edge from the invoke is critical. Conceptually, what we would 222 // like to do is split it and check if the new block dominates the use. 223 // With X being the new block, the graph would look like: 224 // 225 // DefBB 226 // /\ . . 227 // / \ . . 228 // / \ . . 229 // / \ | | 230 // A X B C 231 // | \ | / 232 // . \|/ 233 // . NormalDest 234 // . 235 // 236 // Given the definition of dominance, NormalDest is dominated by X iff X 237 // dominates all of NormalDest's predecessors (X, B, C in the example). X 238 // trivially dominates itself, so we only have to find if it dominates the 239 // other predecessors. Since the only way out of X is via NormalDest, X can 240 // only properly dominate a node if NormalDest dominates that node too. 241 int IsDuplicateEdge = 0; 242 for (const BasicBlock *BB : predecessors(End)) { 243 if (BB == Start) { 244 // If there are multiple edges between Start and End, by definition they 245 // can't dominate anything. 246 if (IsDuplicateEdge++) 247 return false; 248 continue; 249 } 250 251 if (!dominates(End, BB)) 252 return false; 253 } 254 return true; 255 } 256 257 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const { 258 Instruction *UserInst = cast<Instruction>(U.getUser()); 259 // A PHI in the end of the edge is dominated by it. 260 PHINode *PN = dyn_cast<PHINode>(UserInst); 261 if (PN && PN->getParent() == BBE.getEnd() && 262 PN->getIncomingBlock(U) == BBE.getStart()) 263 return true; 264 265 // Otherwise use the edge-dominates-block query, which 266 // handles the crazy critical edge cases properly. 267 const BasicBlock *UseBB; 268 if (PN) 269 UseBB = PN->getIncomingBlock(U); 270 else 271 UseBB = UserInst->getParent(); 272 return dominates(BBE, UseBB); 273 } 274 275 bool DominatorTree::dominates(const Value *DefV, const Use &U) const { 276 const Instruction *Def = dyn_cast<Instruction>(DefV); 277 if (!Def) { 278 assert((isa<Argument>(DefV) || isa<Constant>(DefV)) && 279 "Should be called with an instruction, argument or constant"); 280 return true; // Arguments and constants dominate everything. 281 } 282 283 Instruction *UserInst = cast<Instruction>(U.getUser()); 284 const BasicBlock *DefBB = Def->getParent(); 285 286 // Determine the block in which the use happens. PHI nodes use 287 // their operands on edges; simulate this by thinking of the use 288 // happening at the end of the predecessor block. 289 const BasicBlock *UseBB; 290 if (PHINode *PN = dyn_cast<PHINode>(UserInst)) 291 UseBB = PN->getIncomingBlock(U); 292 else 293 UseBB = UserInst->getParent(); 294 295 // Any unreachable use is dominated, even if Def == User. 296 if (!isReachableFromEntry(UseBB)) 297 return true; 298 299 // Unreachable definitions don't dominate anything. 300 if (!isReachableFromEntry(DefBB)) 301 return false; 302 303 // Invoke instructions define their return values on the edges to their normal 304 // successors, so we have to handle them specially. 305 // Among other things, this means they don't dominate anything in 306 // their own block, except possibly a phi, so we don't need to 307 // walk the block in any case. 308 if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) { 309 BasicBlock *NormalDest = II->getNormalDest(); 310 BasicBlockEdge E(DefBB, NormalDest); 311 return dominates(E, U); 312 } 313 314 // Callbr results are similarly only usable in the default destination. 315 if (const auto *CBI = dyn_cast<CallBrInst>(Def)) { 316 BasicBlock *NormalDest = CBI->getDefaultDest(); 317 BasicBlockEdge E(DefBB, NormalDest); 318 return dominates(E, U); 319 } 320 321 // If the def and use are in different blocks, do a simple CFG dominator 322 // tree query. 323 if (DefBB != UseBB) 324 return dominates(DefBB, UseBB); 325 326 // Ok, def and use are in the same block. If the def is an invoke, it 327 // doesn't dominate anything in the block. If it's a PHI, it dominates 328 // everything in the block. 329 if (isa<PHINode>(UserInst)) 330 return true; 331 332 return Def->comesBefore(UserInst); 333 } 334 335 bool DominatorTree::isReachableFromEntry(const Use &U) const { 336 Instruction *I = dyn_cast<Instruction>(U.getUser()); 337 338 // ConstantExprs aren't really reachable from the entry block, but they 339 // don't need to be treated like unreachable code either. 340 if (!I) return true; 341 342 // PHI nodes use their operands on their incoming edges. 343 if (PHINode *PN = dyn_cast<PHINode>(I)) 344 return isReachableFromEntry(PN->getIncomingBlock(U)); 345 346 // Everything else uses their operands in their own block. 347 return isReachableFromEntry(I->getParent()); 348 } 349 350 // Edge BBE1 dominates edge BBE2 if they match or BBE1 dominates start of BBE2. 351 bool DominatorTree::dominates(const BasicBlockEdge &BBE1, 352 const BasicBlockEdge &BBE2) const { 353 if (BBE1.getStart() == BBE2.getStart() && BBE1.getEnd() == BBE2.getEnd()) 354 return true; 355 return dominates(BBE1, BBE2.getStart()); 356 } 357 358 //===----------------------------------------------------------------------===// 359 // DominatorTreeAnalysis and related pass implementations 360 //===----------------------------------------------------------------------===// 361 // 362 // This implements the DominatorTreeAnalysis which is used with the new pass 363 // manager. It also implements some methods from utility passes. 364 // 365 //===----------------------------------------------------------------------===// 366 367 DominatorTree DominatorTreeAnalysis::run(Function &F, 368 FunctionAnalysisManager &) { 369 DominatorTree DT; 370 DT.recalculate(F); 371 return DT; 372 } 373 374 AnalysisKey DominatorTreeAnalysis::Key; 375 376 DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {} 377 378 PreservedAnalyses DominatorTreePrinterPass::run(Function &F, 379 FunctionAnalysisManager &AM) { 380 OS << "DominatorTree for function: " << F.getName() << "\n"; 381 AM.getResult<DominatorTreeAnalysis>(F).print(OS); 382 383 return PreservedAnalyses::all(); 384 } 385 386 PreservedAnalyses DominatorTreeVerifierPass::run(Function &F, 387 FunctionAnalysisManager &AM) { 388 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 389 assert(DT.verify()); 390 (void)DT; 391 return PreservedAnalyses::all(); 392 } 393 394 //===----------------------------------------------------------------------===// 395 // DominatorTreeWrapperPass Implementation 396 //===----------------------------------------------------------------------===// 397 // 398 // The implementation details of the wrapper pass that holds a DominatorTree 399 // suitable for use with the legacy pass manager. 400 // 401 //===----------------------------------------------------------------------===// 402 403 char DominatorTreeWrapperPass::ID = 0; 404 405 DominatorTreeWrapperPass::DominatorTreeWrapperPass() : FunctionPass(ID) { 406 initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry()); 407 } 408 409 INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree", 410 "Dominator Tree Construction", true, true) 411 412 bool DominatorTreeWrapperPass::runOnFunction(Function &F) { 413 DT.recalculate(F); 414 return false; 415 } 416 417 void DominatorTreeWrapperPass::verifyAnalysis() const { 418 if (VerifyDomInfo) 419 assert(DT.verify(DominatorTree::VerificationLevel::Full)); 420 else if (ExpensiveChecksEnabled) 421 assert(DT.verify(DominatorTree::VerificationLevel::Basic)); 422 } 423 424 void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const { 425 DT.print(OS); 426 } 427