llvm/lib/IR/Dominators.cpp

   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/GenericDomTreeConstruction.h"
  29 #include "llvm/Support/raw_ostream.h"
  30
  31 #include <cassert>
  32
  33 namespace llvm {
  34 class Argument;
  35 class Constant;
  36 class Value;
  37 } // namespace llvm
  38 using namespace llvm;
  39
  40 bool llvm::VerifyDomInfo = false;
  41 static cl::opt<bool, true>
  42     VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden,
  43                    cl::desc("Verify dominator info (time consuming)"));
  44
  45 #ifdef EXPENSIVE_CHECKS
  46 static constexpr bool ExpensiveChecksEnabled = true;
  47 #else
  48 static constexpr bool ExpensiveChecksEnabled = false;
  49 #endif
  50
  51 bool BasicBlockEdge::isSingleEdge() const {
  52   unsigned NumEdgesToEnd = 0;
  53   for (const BasicBlock *Succ : successors(Start)) {
  54     if (Succ == 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   return dominates(DefBB, UseBB);
 198 }
 199
 200 bool DominatorTree::dominates(const BasicBlockEdge &BBE,
 201                               const BasicBlock *UseBB) const {
 202   // If the BB the edge ends in doesn't dominate the use BB, then the
 203   // edge also doesn't.
 204   const BasicBlock *Start = BBE.getStart();
 205   const BasicBlock *End = BBE.getEnd();
 206   if (!dominates(End, UseBB))
 207     return false;
 208
 209   // Simple case: if the end BB has a single predecessor, the fact that it
 210   // dominates the use block implies that the edge also does.
 211   if (End->getSinglePredecessor())
 212     return true;
 213
 214   // The normal edge from the invoke is critical. Conceptually, what we would
 215   // like to do is split it and check if the new block dominates the use.
 216   // With X being the new block, the graph would look like:
 217   //
 218   //        DefBB
 219   //          /\      .  .
 220   //         /  \     .  .
 221   //        /    \    .  .
 222   //       /      \   |  |
 223   //      A        X  B  C
 224   //      |         \ | /
 225   //      .          \|/
 226   //      .      NormalDest
 227   //      .
 228   //
 229   // Given the definition of dominance, NormalDest is dominated by X iff X
 230   // dominates all of NormalDest's predecessors (X, B, C in the example). X
 231   // trivially dominates itself, so we only have to find if it dominates the
 232   // other predecessors. Since the only way out of X is via NormalDest, X can
 233   // only properly dominate a node if NormalDest dominates that node too.
 234   int IsDuplicateEdge = 0;
 235   for (const BasicBlock *BB : predecessors(End)) {
 236     if (BB == Start) {
 237       // If there are multiple edges between Start and End, by definition they
 238       // can't dominate anything.
 239       if (IsDuplicateEdge++)
 240         return false;
 241       continue;
 242     }
 243
 244     if (!dominates(End, BB))
 245       return false;
 246   }
 247   return true;
 248 }
 249
 250 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
 251   Instruction *UserInst = cast<Instruction>(U.getUser());
 252   // A PHI in the end of the edge is dominated by it.
 253   PHINode *PN = dyn_cast<PHINode>(UserInst);
 254   if (PN && PN->getParent() == BBE.getEnd() &&
 255       PN->getIncomingBlock(U) == BBE.getStart())
 256     return true;
 257
 258   // Otherwise use the edge-dominates-block query, which
 259   // handles the crazy critical edge cases properly.
 260   const BasicBlock *UseBB;
 261   if (PN)
 262     UseBB = PN->getIncomingBlock(U);
 263   else
 264     UseBB = UserInst->getParent();
 265   return dominates(BBE, UseBB);
 266 }
 267
 268 bool DominatorTree::dominates(const Value *DefV, const Use &U) const {
 269   const Instruction *Def = dyn_cast<Instruction>(DefV);
 270   if (!Def) {
 271     assert((isa<Argument>(DefV) || isa<Constant>(DefV)) &&
 272            "Should be called with an instruction, argument or constant");
 273     return true; // Arguments and constants dominate everything.
 274   }
 275
 276   Instruction *UserInst = cast<Instruction>(U.getUser());
 277   const BasicBlock *DefBB = Def->getParent();
 278
 279   // Determine the block in which the use happens. PHI nodes use
 280   // their operands on edges; simulate this by thinking of the use
 281   // happening at the end of the predecessor block.
 282   const BasicBlock *UseBB;
 283   if (PHINode *PN = dyn_cast<PHINode>(UserInst))
 284     UseBB = PN->getIncomingBlock(U);
 285   else
 286     UseBB = UserInst->getParent();
 287
 288   // Any unreachable use is dominated, even if Def == User.
 289   if (!isReachableFromEntry(UseBB))
 290     return true;
 291
 292   // Unreachable definitions don't dominate anything.
 293   if (!isReachableFromEntry(DefBB))
 294     return false;
 295
 296   // Invoke instructions define their return values on the edges to their normal
 297   // successors, so we have to handle them specially.
 298   // Among other things, this means they don't dominate anything in
 299   // their own block, except possibly a phi, so we don't need to
 300   // walk the block in any case.
 301   if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
 302     BasicBlock *NormalDest = II->getNormalDest();
 303     BasicBlockEdge E(DefBB, NormalDest);
 304     return dominates(E, U);
 305   }
 306
 307   // If the def and use are in different blocks, do a simple CFG dominator
 308   // tree query.
 309   if (DefBB != UseBB)
 310     return dominates(DefBB, UseBB);
 311
 312   // Ok, def and use are in the same block. If the def is an invoke, it
 313   // doesn't dominate anything in the block. If it's a PHI, it dominates
 314   // everything in the block.
 315   if (isa<PHINode>(UserInst))
 316     return true;
 317
 318   return Def->comesBefore(UserInst);
 319 }
 320
 321 bool DominatorTree::isReachableFromEntry(const Use &U) const {
 322   Instruction *I = dyn_cast<Instruction>(U.getUser());
 323
 324   // ConstantExprs aren't really reachable from the entry block, but they
 325   // don't need to be treated like unreachable code either.
 326   if (!I) return true;
 327
 328   // PHI nodes use their operands on their incoming edges.
 329   if (PHINode *PN = dyn_cast<PHINode>(I))
 330     return isReachableFromEntry(PN->getIncomingBlock(U));
 331
 332   // Everything else uses their operands in their own block.
 333   return isReachableFromEntry(I->getParent());
 334 }
 335
 336 // Edge BBE1 dominates edge BBE2 if they match or BBE1 dominates start of BBE2.
 337 bool DominatorTree::dominates(const BasicBlockEdge &BBE1,
 338                               const BasicBlockEdge &BBE2) const {
 339   if (BBE1.getStart() == BBE2.getStart() && BBE1.getEnd() == BBE2.getEnd())
 340     return true;
 341   return dominates(BBE1, BBE2.getStart());
 342 }
 343
 344 Instruction *DominatorTree::findNearestCommonDominator(Instruction *I1,
 345                                                        Instruction *I2) const {
 346   BasicBlock *BB1 = I1->getParent();
 347   BasicBlock *BB2 = I2->getParent();
 348   if (BB1 == BB2)
 349     return I1->comesBefore(I2) ? I1 : I2;
 350   if (!isReachableFromEntry(BB2))
 351     return I1;
 352   if (!isReachableFromEntry(BB1))
 353     return I2;
 354   BasicBlock *DomBB = findNearestCommonDominator(BB1, BB2);
 355   if (BB1 == DomBB)
 356     return I1;
 357   if (BB2 == DomBB)
 358     return I2;
 359   return DomBB->getTerminator();
 360 }
 361
 362 //===----------------------------------------------------------------------===//
 363 //  DominatorTreeAnalysis and related pass implementations
 364 //===----------------------------------------------------------------------===//
 365 //
 366 // This implements the DominatorTreeAnalysis which is used with the new pass
 367 // manager. It also implements some methods from utility passes.
 368 //
 369 //===----------------------------------------------------------------------===//
 370
 371 DominatorTree DominatorTreeAnalysis::run(Function &F,
 372                                          FunctionAnalysisManager &) {
 373   DominatorTree DT;
 374   DT.recalculate(F);
 375   return DT;
 376 }
 377
 378 AnalysisKey DominatorTreeAnalysis::Key;
 379
 380 DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
 381
 382 PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
 383                                                 FunctionAnalysisManager &AM) {
 384   OS << "DominatorTree for function: " << F.getName() << "\n";
 385   AM.getResult<DominatorTreeAnalysis>(F).print(OS);
 386
 387   return PreservedAnalyses::all();
 388 }
 389
 390 PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
 391                                                  FunctionAnalysisManager &AM) {
 392   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 393   assert(DT.verify());
 394   (void)DT;
 395   return PreservedAnalyses::all();
 396 }
 397
 398 //===----------------------------------------------------------------------===//
 399 //  DominatorTreeWrapperPass Implementation
 400 //===----------------------------------------------------------------------===//
 401 //
 402 // The implementation details of the wrapper pass that holds a DominatorTree
 403 // suitable for use with the legacy pass manager.
 404 //
 405 //===----------------------------------------------------------------------===//
 406
 407 char DominatorTreeWrapperPass::ID = 0;
 408
 409 DominatorTreeWrapperPass::DominatorTreeWrapperPass() : FunctionPass(ID) {
 410   initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
 411 }
 412
 413 INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
 414                 "Dominator Tree Construction", true, true)
 415
 416 bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
 417   DT.recalculate(F);
 418   return false;
 419 }
 420
 421 void DominatorTreeWrapperPass::verifyAnalysis() const {
 422   if (VerifyDomInfo)
 423     assert(DT.verify(DominatorTree::VerificationLevel::Full));
 424   else if (ExpensiveChecksEnabled)
 425     assert(DT.verify(DominatorTree::VerificationLevel::Basic));
 426 }
 427
 428 void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
 429   DT.print(OS);
 430 }