lib/IR/Dominators.cpp

   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/IR/Dominators.h"
  18 #include "llvm/ADT/DepthFirstIterator.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/Config/llvm-config.h"
  21 #include "llvm/IR/CFG.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/Instructions.h"
  24 #include "llvm/IR/PassManager.h"
  25 #include "llvm/Support/CommandLine.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/GenericDomTreeConstruction.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include <algorithm>
  30 using namespace llvm;
  31
  32 bool llvm::VerifyDomInfo = false;
  33 static cl::opt<bool, true>
  34     VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden,
  35                    cl::desc("Verify dominator info (time consuming)"));
  36
  37 #ifdef EXPENSIVE_CHECKS
  38 static constexpr bool ExpensiveChecksEnabled = true;
  39 #else
  40 static constexpr bool ExpensiveChecksEnabled = false;
  41 #endif
  42
  43 bool BasicBlockEdge::isSingleEdge() const {
  44   const TerminatorInst *TI = Start->getTerminator();
  45   unsigned NumEdgesToEnd = 0;
  46   for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
  47     if (TI->getSuccessor(i) == End)
  48       ++NumEdgesToEnd;
  49     if (NumEdgesToEnd >= 2)
  50       return false;
  51   }
  52   assert(NumEdgesToEnd == 1);
  53   return true;
  54 }
  55
  56 //===----------------------------------------------------------------------===//
  57 //  DominatorTree Implementation
  58 //===----------------------------------------------------------------------===//
  59 //
  60 // Provide public access to DominatorTree information.  Implementation details
  61 // can be found in Dominators.h, GenericDomTree.h, and
  62 // GenericDomTreeConstruction.h.
  63 //
  64 //===----------------------------------------------------------------------===//
  65
  66 template class llvm::DomTreeNodeBase<BasicBlock>;
  67 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
  68 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
  69
  70 template struct llvm::DomTreeBuilder::Update<BasicBlock *>;
  71
  72 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
  73     DomTreeBuilder::BBDomTree &DT);
  74 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
  75     DomTreeBuilder::BBPostDomTree &DT);
  76
  77 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
  78     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
  79 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
  80     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
  81
  82 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
  83     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
  84 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
  85     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
  86
  87 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
  88     DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates);
  89 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
  90     DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
  91
  92 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
  93     const DomTreeBuilder::BBDomTree &DT,
  94     DomTreeBuilder::BBDomTree::VerificationLevel VL);
  95 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
  96     const DomTreeBuilder::BBPostDomTree &DT,
  97     DomTreeBuilder::BBPostDomTree::VerificationLevel VL);
  98
  99 bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
 100                                FunctionAnalysisManager::Invalidator &) {
 101   // Check whether the analysis, all analyses on functions, or the function's
 102   // CFG have been preserved.
 103   auto PAC = PA.getChecker<DominatorTreeAnalysis>();
 104   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
 105            PAC.preservedSet<CFGAnalyses>());
 106 }
 107
 108 // dominates - Return true if Def dominates a use in User. This performs
 109 // the special checks necessary if Def and User are in the same basic block.
 110 // Note that Def doesn't dominate a use in Def itself!
 111 bool DominatorTree::dominates(const Instruction *Def,
 112                               const Instruction *User) const {
 113   const BasicBlock *UseBB = User->getParent();
 114   const BasicBlock *DefBB = Def->getParent();
 115
 116   // Any unreachable use is dominated, even if Def == User.
 117   if (!isReachableFromEntry(UseBB))
 118     return true;
 119
 120   // Unreachable definitions don't dominate anything.
 121   if (!isReachableFromEntry(DefBB))
 122     return false;
 123
 124   // An instruction doesn't dominate a use in itself.
 125   if (Def == User)
 126     return false;
 127
 128   // The value defined by an invoke dominates an instruction only if it
 129   // dominates every instruction in UseBB.
 130   // A PHI is dominated only if the instruction dominates every possible use in
 131   // the UseBB.
 132   if (isa<InvokeInst>(Def) || isa<PHINode>(User))
 133     return dominates(Def, UseBB);
 134
 135   if (DefBB != UseBB)
 136     return dominates(DefBB, UseBB);
 137
 138   // Loop through the basic block until we find Def or User.
 139   BasicBlock::const_iterator I = DefBB->begin();
 140   for (; &*I != Def && &*I != User; ++I)
 141     /*empty*/;
 142
 143   return &*I == Def;
 144 }
 145
 146 // true if Def would dominate a use in any instruction in UseBB.
 147 // note that dominates(Def, Def->getParent()) is false.
 148 bool DominatorTree::dominates(const Instruction *Def,
 149                               const BasicBlock *UseBB) const {
 150   const BasicBlock *DefBB = Def->getParent();
 151
 152   // Any unreachable use is dominated, even if DefBB == UseBB.
 153   if (!isReachableFromEntry(UseBB))
 154     return true;
 155
 156   // Unreachable definitions don't dominate anything.
 157   if (!isReachableFromEntry(DefBB))
 158     return false;
 159
 160   if (DefBB == UseBB)
 161     return false;
 162
 163   // Invoke results are only usable in the normal destination, not in the
 164   // exceptional destination.
 165   if (const auto *II = dyn_cast<InvokeInst>(Def)) {
 166     BasicBlock *NormalDest = II->getNormalDest();
 167     BasicBlockEdge E(DefBB, NormalDest);
 168     return dominates(E, UseBB);
 169   }
 170
 171   return dominates(DefBB, UseBB);
 172 }
 173
 174 bool DominatorTree::dominates(const BasicBlockEdge &BBE,
 175                               const BasicBlock *UseBB) const {
 176   // If the BB the edge ends in doesn't dominate the use BB, then the
 177   // edge also doesn't.
 178   const BasicBlock *Start = BBE.getStart();
 179   const BasicBlock *End = BBE.getEnd();
 180   if (!dominates(End, UseBB))
 181     return false;
 182
 183   // Simple case: if the end BB has a single predecessor, the fact that it
 184   // dominates the use block implies that the edge also does.
 185   if (End->getSinglePredecessor())
 186     return true;
 187
 188   // The normal edge from the invoke is critical. Conceptually, what we would
 189   // like to do is split it and check if the new block dominates the use.
 190   // With X being the new block, the graph would look like:
 191   //
 192   //        DefBB
 193   //          /\      .  .
 194   //         /  \     .  .
 195   //        /    \    .  .
 196   //       /      \   |  |
 197   //      A        X  B  C
 198   //      |         \ | /
 199   //      .          \|/
 200   //      .      NormalDest
 201   //      .
 202   //
 203   // Given the definition of dominance, NormalDest is dominated by X iff X
 204   // dominates all of NormalDest's predecessors (X, B, C in the example). X
 205   // trivially dominates itself, so we only have to find if it dominates the
 206   // other predecessors. Since the only way out of X is via NormalDest, X can
 207   // only properly dominate a node if NormalDest dominates that node too.
 208   int IsDuplicateEdge = 0;
 209   for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
 210        PI != E; ++PI) {
 211     const BasicBlock *BB = *PI;
 212     if (BB == Start) {
 213       // If there are multiple edges between Start and End, by definition they
 214       // can't dominate anything.
 215       if (IsDuplicateEdge++)
 216         return false;
 217       continue;
 218     }
 219
 220     if (!dominates(End, BB))
 221       return false;
 222   }
 223   return true;
 224 }
 225
 226 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
 227   Instruction *UserInst = cast<Instruction>(U.getUser());
 228   // A PHI in the end of the edge is dominated by it.
 229   PHINode *PN = dyn_cast<PHINode>(UserInst);
 230   if (PN && PN->getParent() == BBE.getEnd() &&
 231       PN->getIncomingBlock(U) == BBE.getStart())
 232     return true;
 233
 234   // Otherwise use the edge-dominates-block query, which
 235   // handles the crazy critical edge cases properly.
 236   const BasicBlock *UseBB;
 237   if (PN)
 238     UseBB = PN->getIncomingBlock(U);
 239   else
 240     UseBB = UserInst->getParent();
 241   return dominates(BBE, UseBB);
 242 }
 243
 244 bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
 245   Instruction *UserInst = cast<Instruction>(U.getUser());
 246   const BasicBlock *DefBB = Def->getParent();
 247
 248   // Determine the block in which the use happens. PHI nodes use
 249   // their operands on edges; simulate this by thinking of the use
 250   // happening at the end of the predecessor block.
 251   const BasicBlock *UseBB;
 252   if (PHINode *PN = dyn_cast<PHINode>(UserInst))
 253     UseBB = PN->getIncomingBlock(U);
 254   else
 255     UseBB = UserInst->getParent();
 256
 257   // Any unreachable use is dominated, even if Def == User.
 258   if (!isReachableFromEntry(UseBB))
 259     return true;
 260
 261   // Unreachable definitions don't dominate anything.
 262   if (!isReachableFromEntry(DefBB))
 263     return false;
 264
 265   // Invoke instructions define their return values on the edges to their normal
 266   // successors, so we have to handle them specially.
 267   // Among other things, this means they don't dominate anything in
 268   // their own block, except possibly a phi, so we don't need to
 269   // walk the block in any case.
 270   if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
 271     BasicBlock *NormalDest = II->getNormalDest();
 272     BasicBlockEdge E(DefBB, NormalDest);
 273     return dominates(E, U);
 274   }
 275
 276   // If the def and use are in different blocks, do a simple CFG dominator
 277   // tree query.
 278   if (DefBB != UseBB)
 279     return dominates(DefBB, UseBB);
 280
 281   // Ok, def and use are in the same block. If the def is an invoke, it
 282   // doesn't dominate anything in the block. If it's a PHI, it dominates
 283   // everything in the block.
 284   if (isa<PHINode>(UserInst))
 285     return true;
 286
 287   // Otherwise, just loop through the basic block until we find Def or User.
 288   BasicBlock::const_iterator I = DefBB->begin();
 289   for (; &*I != Def && &*I != UserInst; ++I)
 290     /*empty*/;
 291
 292   return &*I != UserInst;
 293 }
 294
 295 bool DominatorTree::isReachableFromEntry(const Use &U) const {
 296   Instruction *I = dyn_cast<Instruction>(U.getUser());
 297
 298   // ConstantExprs aren't really reachable from the entry block, but they
 299   // don't need to be treated like unreachable code either.
 300   if (!I) return true;
 301
 302   // PHI nodes use their operands on their incoming edges.
 303   if (PHINode *PN = dyn_cast<PHINode>(I))
 304     return isReachableFromEntry(PN->getIncomingBlock(U));
 305
 306   // Everything else uses their operands in their own block.
 307   return isReachableFromEntry(I->getParent());
 308 }
 309
 310 //===----------------------------------------------------------------------===//
 311 //  DominatorTreeAnalysis and related pass implementations
 312 //===----------------------------------------------------------------------===//
 313 //
 314 // This implements the DominatorTreeAnalysis which is used with the new pass
 315 // manager. It also implements some methods from utility passes.
 316 //
 317 //===----------------------------------------------------------------------===//
 318
 319 DominatorTree DominatorTreeAnalysis::run(Function &F,
 320                                          FunctionAnalysisManager &) {
 321   DominatorTree DT;
 322   DT.recalculate(F);
 323   return DT;
 324 }
 325
 326 AnalysisKey DominatorTreeAnalysis::Key;
 327
 328 DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
 329
 330 PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
 331                                                 FunctionAnalysisManager &AM) {
 332   OS << "DominatorTree for function: " << F.getName() << "\n";
 333   AM.getResult<DominatorTreeAnalysis>(F).print(OS);
 334
 335   return PreservedAnalyses::all();
 336 }
 337
 338 PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
 339                                                  FunctionAnalysisManager &AM) {
 340   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 341   assert(DT.verify());
 342   (void)DT;
 343   return PreservedAnalyses::all();
 344 }
 345
 346 //===----------------------------------------------------------------------===//
 347 //  DominatorTreeWrapperPass Implementation
 348 //===----------------------------------------------------------------------===//
 349 //
 350 // The implementation details of the wrapper pass that holds a DominatorTree
 351 // suitable for use with the legacy pass manager.
 352 //
 353 //===----------------------------------------------------------------------===//
 354
 355 char DominatorTreeWrapperPass::ID = 0;
 356 INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
 357                 "Dominator Tree Construction", true, true)
 358
 359 bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
 360   DT.recalculate(F);
 361   return false;
 362 }
 363
 364 void DominatorTreeWrapperPass::verifyAnalysis() const {
 365   if (VerifyDomInfo)
 366     assert(DT.verify(DominatorTree::VerificationLevel::Full));
 367   else if (ExpensiveChecksEnabled)
 368     assert(DT.verify(DominatorTree::VerificationLevel::Basic));
 369 }
 370
 371 void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
 372   DT.print(OS);
 373 }
 374
 375 //===----------------------------------------------------------------------===//
 376 //  DeferredDominance Implementation
 377 //===----------------------------------------------------------------------===//
 378 //
 379 // The implementation details of the DeferredDominance class which allows
 380 // one to queue updates to a DominatorTree.
 381 //
 382 //===----------------------------------------------------------------------===//
 383
 384 /// Queues multiple updates and discards duplicates.
 385 void DeferredDominance::applyUpdates(
 386     ArrayRef<DominatorTree::UpdateType> Updates) {
 387   SmallVector<DominatorTree::UpdateType, 8> Seen;
 388   for (auto U : Updates)
 389     // Avoid duplicates to applyUpdate() to save on analysis.
 390     if (std::none_of(Seen.begin(), Seen.end(),
 391                      [U](DominatorTree::UpdateType S) { return S == U; })) {
 392       Seen.push_back(U);
 393       applyUpdate(U.getKind(), U.getFrom(), U.getTo());
 394     }
 395 }
 396
 397 /// Helper method for a single edge insertion. It's almost always better
 398 /// to batch updates and call applyUpdates to quickly remove duplicate edges.
 399 /// This is best used when there is only a single insertion needed to update
 400 /// Dominators.
 401 void DeferredDominance::insertEdge(BasicBlock *From, BasicBlock *To) {
 402   applyUpdate(DominatorTree::Insert, From, To);
 403 }
 404
 405 /// Helper method for a single edge deletion. It's almost always better
 406 /// to batch updates and call applyUpdates to quickly remove duplicate edges.
 407 /// This is best used when there is only a single deletion needed to update
 408 /// Dominators.
 409 void DeferredDominance::deleteEdge(BasicBlock *From, BasicBlock *To) {
 410   applyUpdate(DominatorTree::Delete, From, To);
 411 }
 412
 413 /// Delays the deletion of a basic block until a flush() event.
 414 void DeferredDominance::deleteBB(BasicBlock *DelBB) {
 415   assert(DelBB && "Invalid push_back of nullptr DelBB.");
 416   assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
 417   // DelBB is unreachable and all its instructions are dead.
 418   while (!DelBB->empty()) {
 419     Instruction &I = DelBB->back();
 420     // Replace used instructions with an arbitrary value (undef).
 421     if (!I.use_empty())
 422       I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
 423     DelBB->getInstList().pop_back();
 424   }
 425   // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
 426   // Child of Function F it must contain valid IR.
 427   new UnreachableInst(DelBB->getContext(), DelBB);
 428   DeletedBBs.insert(DelBB);
 429 }
 430
 431 /// Returns true if DelBB is awaiting deletion at a flush() event.
 432 bool DeferredDominance::pendingDeletedBB(BasicBlock *DelBB) {
 433   if (DeletedBBs.empty())
 434     return false;
 435   return DeletedBBs.count(DelBB) != 0;
 436 }
 437
 438 /// Returns true if pending DT updates are queued for a flush() event.
 439 bool DeferredDominance::pending() { return !PendUpdates.empty(); }
 440
 441 /// Flushes all pending updates and block deletions. Returns a
 442 /// correct DominatorTree reference to be used by the caller for analysis.
 443 DominatorTree &DeferredDominance::flush() {
 444   // Updates to DT must happen before blocks are deleted below. Otherwise the
 445   // DT traversal will encounter badref blocks and assert.
 446   if (!PendUpdates.empty()) {
 447     DT.applyUpdates(PendUpdates);
 448     PendUpdates.clear();
 449   }
 450   flushDelBB();
 451   return DT;
 452 }
 453
 454 /// Drops all internal state and forces a (slow) recalculation of the
 455 /// DominatorTree based on the current state of the LLVM IR in F. This should
 456 /// only be used in corner cases such as the Entry block of F being deleted.
 457 void DeferredDominance::recalculate(Function &F) {
 458   // flushDelBB must be flushed before the recalculation. The state of the IR
 459   // must be consistent before the DT traversal algorithm determines the
 460   // actual DT.
 461   if (flushDelBB() || !PendUpdates.empty()) {
 462     DT.recalculate(F);
 463     PendUpdates.clear();
 464   }
 465 }
 466
 467 /// Debug method to help view the state of pending updates.
 468 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 469 LLVM_DUMP_METHOD void DeferredDominance::dump() const {
 470   raw_ostream &OS = llvm::dbgs();
 471   OS << "PendUpdates:\n";
 472   int I = 0;
 473   for (auto U : PendUpdates) {
 474     OS << "  " << I << " : ";
 475     ++I;
 476     if (U.getKind() == DominatorTree::Insert)
 477       OS << "Insert, ";
 478     else
 479       OS << "Delete, ";
 480     BasicBlock *From = U.getFrom();
 481     if (From) {
 482       auto S = From->getName();
 483       if (!From->hasName())
 484         S = "(no name)";
 485       OS << S << "(" << From << "), ";
 486     } else {
 487       OS << "(badref), ";
 488     }
 489     BasicBlock *To = U.getTo();
 490     if (To) {
 491       auto S = To->getName();
 492       if (!To->hasName())
 493         S = "(no_name)";
 494       OS << S << "(" << To << ")\n";
 495     } else {
 496       OS << "(badref)\n";
 497     }
 498   }
 499   OS << "DeletedBBs:\n";
 500   I = 0;
 501   for (auto BB : DeletedBBs) {
 502     OS << "  " << I << " : ";
 503     ++I;
 504     if (BB->hasName())
 505       OS << BB->getName() << "(";
 506     else
 507       OS << "(no_name)(";
 508     OS << BB << ")\n";
 509   }
 510 }
 511 #endif
 512
 513 /// Apply an update (Kind, From, To) to the internal queued updates. The
 514 /// update is only added when determined to be necessary. Checks for
 515 /// self-domination, unnecessary updates, duplicate requests, and balanced
 516 /// pairs of requests are all performed. Returns true if the update is
 517 /// queued and false if it is discarded.
 518 bool DeferredDominance::applyUpdate(DominatorTree::UpdateKind Kind,
 519                                     BasicBlock *From, BasicBlock *To) {
 520   if (From == To)
 521     return false; // Cannot dominate self; discard update.
 522
 523   // Discard updates by inspecting the current state of successors of From.
 524   // Since applyUpdate() must be called *after* the Terminator of From is
 525   // altered we can determine if the update is unnecessary.
 526   bool HasEdge = std::any_of(succ_begin(From), succ_end(From),
 527                              [To](BasicBlock *B) { return B == To; });
 528   if (Kind == DominatorTree::Insert && !HasEdge)
 529     return false; // Unnecessary Insert: edge does not exist in IR.
 530   if (Kind == DominatorTree::Delete && HasEdge)
 531     return false; // Unnecessary Delete: edge still exists in IR.
 532
 533   // Analyze pending updates to determine if the update is unnecessary.
 534   DominatorTree::UpdateType Update = {Kind, From, To};
 535   DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
 536                                           ? DominatorTree::Insert
 537                                           : DominatorTree::Delete,
 538                                       From, To};
 539   for (auto I = PendUpdates.begin(), E = PendUpdates.end(); I != E; ++I) {
 540     if (Update == *I)
 541       return false; // Discard duplicate updates.
 542     if (Invert == *I) {
 543       // Update and Invert are both valid (equivalent to a no-op). Remove
 544       // Invert from PendUpdates and discard the Update.
 545       PendUpdates.erase(I);
 546       return false;
 547     }
 548   }
 549   PendUpdates.push_back(Update); // Save the valid update.
 550   return true;
 551 }
 552
 553 /// Performs all pending basic block deletions. We have to defer the deletion
 554 /// of these blocks until after the DominatorTree updates are applied. The
 555 /// internal workings of the DominatorTree code expect every update's From
 556 /// and To blocks to exist and to be a member of the same Function.
 557 bool DeferredDominance::flushDelBB() {
 558   if (DeletedBBs.empty())
 559     return false;
 560   for (auto *BB : DeletedBBs)
 561     BB->eraseFromParent();
 562   DeletedBBs.clear();
 563   return true;
 564 }