LCOV - code coverage report
Current view: top level - lib/IR - Dominators.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 133 136 97.8 %
Date: 2018-06-17 00:07:59 Functions: 28 29 96.6 %
Legend: Lines: hit not hit

          Line data    Source code
       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      303579 :     VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden,
      35      303579 :                    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      161909 : bool BasicBlockEdge::isSingleEdge() const {
      44      161909 :   const TerminatorInst *TI = Start->getTerminator();
      45             :   unsigned NumEdgesToEnd = 0;
      46      485721 :   for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
      47      323818 :     if (TI->getSuccessor(i) == End)
      48      161915 :       ++NumEdgesToEnd;
      49      323818 :     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        1997 : 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        3341 :   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
     105        3341 :            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      655713 : bool DominatorTree::dominates(const Instruction *Def,
     112             :                               const Instruction *User) const {
     113      655713 :   const BasicBlock *UseBB = User->getParent();
     114      655713 :   const BasicBlock *DefBB = Def->getParent();
     115             : 
     116             :   // Any unreachable use is dominated, even if Def == User.
     117      655713 :   if (!isReachableFromEntry(UseBB))
     118             :     return true;
     119             : 
     120             :   // Unreachable definitions don't dominate anything.
     121      655409 :   if (!isReachableFromEntry(DefBB))
     122             :     return false;
     123             : 
     124             :   // An instruction doesn't dominate a use in itself.
     125      655403 :   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     1205923 :   if (isa<InvokeInst>(Def) || isa<PHINode>(User))
     133      125295 :     return dominates(Def, UseBB);
     134             : 
     135      522735 :   if (DefBB != UseBB)
     136      492093 :     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    11099230 :   for (; &*I != Def && &*I != User; ++I)
     141             :     /*empty*/;
     142             : 
     143       30642 :   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      152596 : bool DominatorTree::dominates(const Instruction *Def,
     149             :                               const BasicBlock *UseBB) const {
     150      152596 :   const BasicBlock *DefBB = Def->getParent();
     151             : 
     152             :   // Any unreachable use is dominated, even if DefBB == UseBB.
     153      152596 :   if (!isReachableFromEntry(UseBB))
     154             :     return true;
     155             : 
     156             :   // Unreachable definitions don't dominate anything.
     157      152593 :   if (!isReachableFromEntry(DefBB))
     158             :     return false;
     159             : 
     160      152591 :   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       90022 :     return dominates(E, UseBB);
     169             :   }
     170             : 
     171       39717 :   return dominates(DefBB, UseBB);
     172             : }
     173             : 
     174      646612 : 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      646612 :   const BasicBlock *Start = BBE.getStart();
     179      646612 :   const BasicBlock *End = BBE.getEnd();
     180      646612 :   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       29854 :   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       10794 :   for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
     210       13938 :        PI != E; ++PI) {
     211             :     const BasicBlock *BB = *PI;
     212       16914 :     if (BB == Start) {
     213             :       // If there are multiple edges between Start and End, by definition they
     214             :       // can't dominate anything.
     215        3062 :       if (IsDuplicateEdge++)
     216       10710 :         return false;
     217        3060 :       continue;
     218             :     }
     219             : 
     220       10792 :     if (!dominates(End, BB))
     221             :       return false;
     222             :   }
     223          84 :   return true;
     224             : }
     225             : 
     226      407091 : bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
     227      407091 :   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       20050 :   if (PN && PN->getParent() == BBE.getEnd() &&
     231        3850 :       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      404099 :   if (PN)
     238             :     UseBB = PN->getIncomingBlock(U);
     239             :   else
     240      390891 :     UseBB = UserInst->getParent();
     241      404099 :   return dominates(BBE, UseBB);
     242             : }
     243             : 
     244      493840 : bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
     245      493840 :   Instruction *UserInst = cast<Instruction>(U.getUser());
     246      493840 :   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      393750 :     UseBB = UserInst->getParent();
     256             : 
     257             :   // Any unreachable use is dominated, even if Def == User.
     258      493840 :   if (!isReachableFromEntry(UseBB))
     259             :     return true;
     260             : 
     261             :   // Unreachable definitions don't dominate anything.
     262      492763 :   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        1195 :     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      491568 :   if (DefBB != UseBB)
     279      404858 :     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       86710 :   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         366 :   for (; &*I != Def && &*I != UserInst; ++I)
     290             :     /*empty*/;
     291             : 
     292         138 :   return &*I != UserInst;
     293             : }
     294             : 
     295         124 : bool DominatorTree::isReachableFromEntry(const Use &U) const {
     296         124 :   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          16 :     return isReachableFromEntry(PN->getIncomingBlock(U));
     305             : 
     306             :   // Everything else uses their operands in their own block.
     307         116 :   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        2636 : DominatorTree DominatorTreeAnalysis::run(Function &F,
     320             :                                          FunctionAnalysisManager &) {
     321             :   DominatorTree DT;
     322        2636 :   DT.recalculate(F);
     323        2636 :   return DT;
     324             : }
     325             : 
     326             : AnalysisKey DominatorTreeAnalysis::Key;
     327             : 
     328           2 : DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
     329             : 
     330           3 : PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
     331             :                                                 FunctionAnalysisManager &AM) {
     332           3 :   OS << "DominatorTree for function: " << F.getName() << "\n";
     333           3 :   AM.getResult<DominatorTreeAnalysis>(F).print(OS);
     334             : 
     335           3 :   return PreservedAnalyses::all();
     336             : }
     337             : 
     338          28 : PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
     339             :                                                  FunctionAnalysisManager &AM) {
     340             :   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
     341             :   assert(DT.verify());
     342             :   (void)DT;
     343          28 :   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     6117062 : INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
     357             :                 "Dominator Tree Construction", true, true)
     358             : 
     359     1652974 : bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
     360     1652974 :   DT.recalculate(F);
     361     1652974 :   return false;
     362             : }
     363             : 
     364           0 : 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           0 : }
     370             : 
     371           6 : void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
     372           6 :   DT.print(OS);
     373           6 : }
     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       24588 : void DeferredDominance::applyUpdates(
     386             :     ArrayRef<DominatorTree::UpdateType> Updates) {
     387             :   SmallVector<DominatorTree::UpdateType, 8> Seen;
     388      203700 :   for (auto U : Updates)
     389             :     // Avoid duplicates to applyUpdate() to save on analysis.
     390      179112 :     if (std::none_of(Seen.begin(), Seen.end(),
     391             :                      [U](DominatorTree::UpdateType S) { return S == U; })) {
     392       89497 :       Seen.push_back(U);
     393       89497 :       applyUpdate(U.getKind(), U.getFrom(), U.getTo());
     394             :     }
     395       24588 : }
     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           3 : void DeferredDominance::insertEdge(BasicBlock *From, BasicBlock *To) {
     402           3 :   applyUpdate(DominatorTree::Insert, From, To);
     403           3 : }
     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        2153 : void DeferredDominance::deleteEdge(BasicBlock *From, BasicBlock *To) {
     410        2153 :   applyUpdate(DominatorTree::Delete, From, To);
     411        2153 : }
     412             : 
     413             : /// Delays the deletion of a basic block until a flush() event.
     414       22560 : 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       30564 :   while (!DelBB->empty()) {
     419             :     Instruction &I = DelBB->back();
     420             :     // Replace used instructions with an arbitrary value (undef).
     421        4002 :     if (!I.use_empty())
     422           0 :       I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
     423        4002 :     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       45120 :   new UnreachableInst(DelBB->getContext(), DelBB);
     428       22560 :   DeletedBBs.insert(DelBB);
     429       22560 : }
     430             : 
     431             : /// Returns true if DelBB is awaiting deletion at a flush() event.
     432     1083216 : bool DeferredDominance::pendingDeletedBB(BasicBlock *DelBB) {
     433     1083216 :   if (DeletedBBs.empty())
     434             :     return false;
     435      645466 :   return DeletedBBs.count(DelBB) != 0;
     436             : }
     437             : 
     438             : /// Returns true if pending DT updates are queued for a flush() event.
     439      182039 : 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      146509 : 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      146509 :   if (!PendUpdates.empty()) {
     447        6695 :     DT.applyUpdates(PendUpdates);
     448             :     PendUpdates.clear();
     449             :   }
     450      146509 :   flushDelBB();
     451      146509 :   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         833 : 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         833 :   if (flushDelBB() || !PendUpdates.empty()) {
     462         833 :     DT.recalculate(F);
     463             :     PendUpdates.clear();
     464             :   }
     465         833 : }
     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       91653 : bool DeferredDominance::applyUpdate(DominatorTree::UpdateKind Kind,
     519             :                                     BasicBlock *From, BasicBlock *To) {
     520       91653 :   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       91628 :   bool HasEdge = std::any_of(succ_begin(From), succ_end(From),
     527       91628 :                              [To](BasicBlock *B) { return B == To; });
     528       91628 :   if (Kind == DominatorTree::Insert && !HasEdge)
     529             :     return false; // Unnecessary Insert: edge does not exist in IR.
     530       91625 :   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       91593 :                                       From, To};
     539     7608637 :   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        4707 :       return false;
     547             :     }
     548             :   }
     549       86886 :   PendUpdates.push_back(Update); // Save the valid update.
     550       86886 :   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      147342 : bool DeferredDominance::flushDelBB() {
     558      147342 :   if (DeletedBBs.empty())
     559             :     return false;
     560        6899 :   for (auto *BB : DeletedBBs)
     561       22560 :     BB->eraseFromParent();
     562        6899 :   DeletedBBs.clear();
     563        6899 :   return true;
     564      303579 : }

Generated by: LCOV version 1.13