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 32namespace llvm { 33class Argument; 34class Constant; 35class Value; 36} // namespace llvm 37using namespace llvm; 38 39bool llvm::VerifyDomInfo = false; 40static 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 45static constexpr bool ExpensiveChecksEnabled = true; 46#else 47static constexpr bool ExpensiveChecksEnabled = false; 48#endif 49 50bool 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 73template class llvm::DomTreeNodeBase<BasicBlock>; 74template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase 75template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase 76 77template class llvm::cfg::Update<BasicBlock *>; 78 79template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>( 80 DomTreeBuilder::BBDomTree &DT); 81template void 82llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>( 83 DomTreeBuilder::BBDomTree &DT, BBUpdates U); 84 85template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>( 86 DomTreeBuilder::BBPostDomTree &DT); 87// No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises. 88 89template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>( 90 DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To); 91template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>( 92 DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); 93 94template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>( 95 DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To); 96template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>( 97 DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); 98 99template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>( 100 DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBDomTreeGraphDiff &, 101 DomTreeBuilder::BBDomTreeGraphDiff *); 102template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>( 103 DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBPostDomTreeGraphDiff &, 104 DomTreeBuilder::BBPostDomTreeGraphDiff *); 105 106template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>( 107 const DomTreeBuilder::BBDomTree &DT, 108 DomTreeBuilder::BBDomTree::VerificationLevel VL); 109template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>( 110 const DomTreeBuilder::BBPostDomTree &DT, 111 DomTreeBuilder::BBPostDomTree::VerificationLevel VL); 112 113bool 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 122bool 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! 135bool 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. 174bool 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 207bool 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 257bool 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 275bool 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 335bool 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. 351bool 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 358Instruction *DominatorTree::findNearestCommonDominator(Instruction *I1, 359 Instruction *I2) const { 360 BasicBlock *BB1 = I1->getParent(); 361 BasicBlock *BB2 = I2->getParent(); 362 if (BB1 == BB2) 363 return I1->comesBefore(I2) ? I1 : I2; 364 if (!isReachableFromEntry(BB2)) 365 return I1; 366 if (!isReachableFromEntry(BB1)) 367 return I2; 368 BasicBlock *DomBB = findNearestCommonDominator(BB1, BB2); 369 if (BB1 == DomBB) 370 return I1; 371 if (BB2 == DomBB) 372 return I2; 373 return DomBB->getTerminator(); 374} 375 376//===----------------------------------------------------------------------===// 377// DominatorTreeAnalysis and related pass implementations 378//===----------------------------------------------------------------------===// 379// 380// This implements the DominatorTreeAnalysis which is used with the new pass 381// manager. It also implements some methods from utility passes. 382// 383//===----------------------------------------------------------------------===// 384 385DominatorTree DominatorTreeAnalysis::run(Function &F, 386 FunctionAnalysisManager &) { 387 DominatorTree DT; 388 DT.recalculate(F); 389 return DT; 390} 391 392AnalysisKey DominatorTreeAnalysis::Key; 393 394DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {} 395 396PreservedAnalyses DominatorTreePrinterPass::run(Function &F, 397 FunctionAnalysisManager &AM) { 398 OS << "DominatorTree for function: " << F.getName() << "\n"; 399 AM.getResult<DominatorTreeAnalysis>(F).print(OS); 400 401 return PreservedAnalyses::all(); 402} 403 404PreservedAnalyses DominatorTreeVerifierPass::run(Function &F, 405 FunctionAnalysisManager &AM) { 406 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 407 assert(DT.verify()); 408 (void)DT; 409 return PreservedAnalyses::all(); 410} 411 412//===----------------------------------------------------------------------===// 413// DominatorTreeWrapperPass Implementation 414//===----------------------------------------------------------------------===// 415// 416// The implementation details of the wrapper pass that holds a DominatorTree 417// suitable for use with the legacy pass manager. 418// 419//===----------------------------------------------------------------------===// 420 421char DominatorTreeWrapperPass::ID = 0; 422 423DominatorTreeWrapperPass::DominatorTreeWrapperPass() : FunctionPass(ID) { 424 initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry()); 425} 426 427INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree", 428 "Dominator Tree Construction", true, true) 429 430bool DominatorTreeWrapperPass::runOnFunction(Function &F) { 431 DT.recalculate(F); 432 return false; 433} 434 435void DominatorTreeWrapperPass::verifyAnalysis() const { 436 if (VerifyDomInfo) 437 assert(DT.verify(DominatorTree::VerificationLevel::Full)); 438 else if (ExpensiveChecksEnabled) 439 assert(DT.verify(DominatorTree::VerificationLevel::Basic)); 440} 441 442void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const { 443 DT.print(OS); 444} 445