LCOV - code coverage report
Current view: top level - lib/IR - Dominators.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 80 82 97.6 %
Date: 2018-10-20 13:21:21 Functions: 16 17 94.1 %
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             :     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      303484 : bool BasicBlockEdge::isSingleEdge() const {
      44      303484 :   const Instruction *TI = Start->getTerminator();
      45             :   unsigned NumEdgesToEnd = 0;
      46      910446 :   for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
      47      606968 :     if (TI->getSuccessor(i) == End)
      48      303490 :       ++NumEdgesToEnd;
      49      606968 :     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 class llvm::cfg::Update<BasicBlock *>;
      71             : 
      72             : template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
      73             :     DomTreeBuilder::BBDomTree &DT);
      74             : template void
      75             : llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>(
      76             :     DomTreeBuilder::BBDomTree &DT, BBUpdates U);
      77             : 
      78             : template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
      79             :     DomTreeBuilder::BBPostDomTree &DT);
      80             : // No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises.
      81             : 
      82             : template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
      83             :     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
      84             : template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
      85             :     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
      86             : 
      87             : template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
      88             :     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
      89             : template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
      90             :     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
      91             : 
      92             : template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
      93             :     DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates);
      94             : template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
      95             :     DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
      96             : 
      97             : template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
      98             :     const DomTreeBuilder::BBDomTree &DT,
      99             :     DomTreeBuilder::BBDomTree::VerificationLevel VL);
     100             : template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
     101             :     const DomTreeBuilder::BBPostDomTree &DT,
     102             :     DomTreeBuilder::BBPostDomTree::VerificationLevel VL);
     103             : 
     104        2249 : bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
     105             :                                FunctionAnalysisManager::Invalidator &) {
     106             :   // Check whether the analysis, all analyses on functions, or the function's
     107             :   // CFG have been preserved.
     108             :   auto PAC = PA.getChecker<DominatorTreeAnalysis>();
     109        3695 :   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
     110        1446 :            PAC.preservedSet<CFGAnalyses>());
     111             : }
     112             : 
     113             : // dominates - Return true if Def dominates a use in User. This performs
     114             : // the special checks necessary if Def and User are in the same basic block.
     115             : // Note that Def doesn't dominate a use in Def itself!
     116      956908 : bool DominatorTree::dominates(const Instruction *Def,
     117             :                               const Instruction *User) const {
     118      956908 :   const BasicBlock *UseBB = User->getParent();
     119      956908 :   const BasicBlock *DefBB = Def->getParent();
     120             : 
     121             :   // Any unreachable use is dominated, even if Def == User.
     122      956908 :   if (!isReachableFromEntry(UseBB))
     123             :     return true;
     124             : 
     125             :   // Unreachable definitions don't dominate anything.
     126      956902 :   if (!isReachableFromEntry(DefBB))
     127             :     return false;
     128             : 
     129             :   // An instruction doesn't dominate a use in itself.
     130      956896 :   if (Def == User)
     131             :     return false;
     132             : 
     133             :   // The value defined by an invoke dominates an instruction only if it
     134             :   // dominates every instruction in UseBB.
     135             :   // A PHI is dominated only if the instruction dominates every possible use in
     136             :   // the UseBB.
     137      945910 :   if (isa<InvokeInst>(Def) || isa<PHINode>(User))
     138      479582 :     return dominates(Def, UseBB);
     139             : 
     140      466328 :   if (DefBB != UseBB)
     141      428269 :     return dominates(DefBB, UseBB);
     142             : 
     143             :   // Loop through the basic block until we find Def or User.
     144             :   BasicBlock::const_iterator I = DefBB->begin();
     145    11199071 :   for (; &*I != Def && &*I != User; ++I)
     146             :     /*empty*/;
     147             : 
     148       38059 :   return &*I == Def;
     149             : }
     150             : 
     151             : // true if Def would dominate a use in any instruction in UseBB.
     152             : // note that dominates(Def, Def->getParent()) is false.
     153      513721 : bool DominatorTree::dominates(const Instruction *Def,
     154             :                               const BasicBlock *UseBB) const {
     155      513721 :   const BasicBlock *DefBB = Def->getParent();
     156             : 
     157             :   // Any unreachable use is dominated, even if DefBB == UseBB.
     158      513721 :   if (!isReachableFromEntry(UseBB))
     159             :     return true;
     160             : 
     161             :   // Unreachable definitions don't dominate anything.
     162      513718 :   if (!isReachableFromEntry(DefBB))
     163             :     return false;
     164             : 
     165      513716 :   if (DefBB == UseBB)
     166             :     return false;
     167             : 
     168             :   // Invoke results are only usable in the normal destination, not in the
     169             :   // exceptional destination.
     170             :   if (const auto *II = dyn_cast<InvokeInst>(Def)) {
     171             :     BasicBlock *NormalDest = II->getNormalDest();
     172             :     BasicBlockEdge E(DefBB, NormalDest);
     173      420571 :     return dominates(E, UseBB);
     174             :   }
     175             : 
     176       65041 :   return dominates(DefBB, UseBB);
     177             : }
     178             : 
     179     1007357 : bool DominatorTree::dominates(const BasicBlockEdge &BBE,
     180             :                               const BasicBlock *UseBB) const {
     181             :   // If the BB the edge ends in doesn't dominate the use BB, then the
     182             :   // edge also doesn't.
     183     1007357 :   const BasicBlock *Start = BBE.getStart();
     184     1007357 :   const BasicBlock *End = BBE.getEnd();
     185     1007357 :   if (!dominates(End, UseBB))
     186             :     return false;
     187             : 
     188             :   // Simple case: if the end BB has a single predecessor, the fact that it
     189             :   // dominates the use block implies that the edge also does.
     190       90139 :   if (End->getSinglePredecessor())
     191             :     return true;
     192             : 
     193             :   // The normal edge from the invoke is critical. Conceptually, what we would
     194             :   // like to do is split it and check if the new block dominates the use.
     195             :   // With X being the new block, the graph would look like:
     196             :   //
     197             :   //        DefBB
     198             :   //          /\      .  .
     199             :   //         /  \     .  .
     200             :   //        /    \    .  .
     201             :   //       /      \   |  |
     202             :   //      A        X  B  C
     203             :   //      |         \ | /
     204             :   //      .          \|/
     205             :   //      .      NormalDest
     206             :   //      .
     207             :   //
     208             :   // Given the definition of dominance, NormalDest is dominated by X iff X
     209             :   // dominates all of NormalDest's predecessors (X, B, C in the example). X
     210             :   // trivially dominates itself, so we only have to find if it dominates the
     211             :   // other predecessors. Since the only way out of X is via NormalDest, X can
     212             :   // only properly dominate a node if NormalDest dominates that node too.
     213             :   int IsDuplicateEdge = 0;
     214       16480 :   for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
     215       24833 :        PI != E; ++PI) {
     216             :     const BasicBlock *BB = *PI;
     217       24748 :     if (BB == Start) {
     218             :       // If there are multiple edges between Start and End, by definition they
     219             :       // can't dominate anything.
     220        8190 :       if (IsDuplicateEdge++)
     221       16395 :         return false;
     222             :       continue;
     223             :     }
     224             : 
     225       16558 :     if (!dominates(End, BB))
     226             :       return false;
     227             :   }
     228          85 :   return true;
     229             : }
     230             : 
     231      302229 : bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
     232      302229 :   Instruction *UserInst = cast<Instruction>(U.getUser());
     233             :   // A PHI in the end of the edge is dominated by it.
     234             :   PHINode *PN = dyn_cast<PHINode>(UserInst);
     235       30461 :   if (PN && PN->getParent() == BBE.getEnd() &&
     236        7146 :       PN->getIncomingBlock(U) == BBE.getStart())
     237             :     return true;
     238             : 
     239             :   // Otherwise use the edge-dominates-block query, which
     240             :   // handles the crazy critical edge cases properly.
     241             :   const BasicBlock *UseBB;
     242      296913 :   if (PN)
     243             :     UseBB = PN->getIncomingBlock(U);
     244             :   else
     245      271768 :     UseBB = UserInst->getParent();
     246      296913 :   return dominates(BBE, UseBB);
     247             : }
     248             : 
     249      534497 : bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
     250      534497 :   Instruction *UserInst = cast<Instruction>(U.getUser());
     251      534497 :   const BasicBlock *DefBB = Def->getParent();
     252             : 
     253             :   // Determine the block in which the use happens. PHI nodes use
     254             :   // their operands on edges; simulate this by thinking of the use
     255             :   // happening at the end of the predecessor block.
     256             :   const BasicBlock *UseBB;
     257             :   if (PHINode *PN = dyn_cast<PHINode>(UserInst))
     258             :     UseBB = PN->getIncomingBlock(U);
     259             :   else
     260      426283 :     UseBB = UserInst->getParent();
     261             : 
     262             :   // Any unreachable use is dominated, even if Def == User.
     263      534497 :   if (!isReachableFromEntry(UseBB))
     264             :     return true;
     265             : 
     266             :   // Unreachable definitions don't dominate anything.
     267      533373 :   if (!isReachableFromEntry(DefBB))
     268             :     return false;
     269             : 
     270             :   // Invoke instructions define their return values on the edges to their normal
     271             :   // successors, so we have to handle them specially.
     272             :   // Among other things, this means they don't dominate anything in
     273             :   // their own block, except possibly a phi, so we don't need to
     274             :   // walk the block in any case.
     275             :   if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
     276             :     BasicBlock *NormalDest = II->getNormalDest();
     277             :     BasicBlockEdge E(DefBB, NormalDest);
     278        1254 :     return dominates(E, U);
     279             :   }
     280             : 
     281             :   // If the def and use are in different blocks, do a simple CFG dominator
     282             :   // tree query.
     283      532119 :   if (DefBB != UseBB)
     284      438230 :     return dominates(DefBB, UseBB);
     285             : 
     286             :   // Ok, def and use are in the same block. If the def is an invoke, it
     287             :   // doesn't dominate anything in the block. If it's a PHI, it dominates
     288             :   // everything in the block.
     289       93889 :   if (isa<PHINode>(UserInst))
     290             :     return true;
     291             : 
     292             :   // Otherwise, just loop through the basic block until we find Def or User.
     293             :   BasicBlock::const_iterator I = DefBB->begin();
     294         371 :   for (; &*I != Def && &*I != UserInst; ++I)
     295             :     /*empty*/;
     296             : 
     297         142 :   return &*I != UserInst;
     298             : }
     299             : 
     300         124 : bool DominatorTree::isReachableFromEntry(const Use &U) const {
     301         124 :   Instruction *I = dyn_cast<Instruction>(U.getUser());
     302             : 
     303             :   // ConstantExprs aren't really reachable from the entry block, but they
     304             :   // don't need to be treated like unreachable code either.
     305             :   if (!I) return true;
     306             : 
     307             :   // PHI nodes use their operands on their incoming edges.
     308             :   if (PHINode *PN = dyn_cast<PHINode>(I))
     309          16 :     return isReachableFromEntry(PN->getIncomingBlock(U));
     310             : 
     311             :   // Everything else uses their operands in their own block.
     312         116 :   return isReachableFromEntry(I->getParent());
     313             : }
     314             : 
     315             : //===----------------------------------------------------------------------===//
     316             : //  DominatorTreeAnalysis and related pass implementations
     317             : //===----------------------------------------------------------------------===//
     318             : //
     319             : // This implements the DominatorTreeAnalysis which is used with the new pass
     320             : // manager. It also implements some methods from utility passes.
     321             : //
     322             : //===----------------------------------------------------------------------===//
     323             : 
     324        2907 : DominatorTree DominatorTreeAnalysis::run(Function &F,
     325             :                                          FunctionAnalysisManager &) {
     326             :   DominatorTree DT;
     327        2907 :   DT.recalculate(F);
     328        2907 :   return DT;
     329             : }
     330             : 
     331             : AnalysisKey DominatorTreeAnalysis::Key;
     332             : 
     333           2 : DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
     334             : 
     335           3 : PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
     336             :                                                 FunctionAnalysisManager &AM) {
     337           3 :   OS << "DominatorTree for function: " << F.getName() << "\n";
     338           3 :   AM.getResult<DominatorTreeAnalysis>(F).print(OS);
     339             : 
     340           3 :   return PreservedAnalyses::all();
     341             : }
     342             : 
     343          28 : PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
     344             :                                                  FunctionAnalysisManager &AM) {
     345             :   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
     346             :   assert(DT.verify());
     347             :   (void)DT;
     348          28 :   return PreservedAnalyses::all();
     349             : }
     350             : 
     351             : //===----------------------------------------------------------------------===//
     352             : //  DominatorTreeWrapperPass Implementation
     353             : //===----------------------------------------------------------------------===//
     354             : //
     355             : // The implementation details of the wrapper pass that holds a DominatorTree
     356             : // suitable for use with the legacy pass manager.
     357             : //
     358             : //===----------------------------------------------------------------------===//
     359             : 
     360             : char DominatorTreeWrapperPass::ID = 0;
     361     3394754 : INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
     362             :                 "Dominator Tree Construction", true, true)
     363             : 
     364     2123158 : bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
     365     2123158 :   DT.recalculate(F);
     366     2123158 :   return false;
     367             : }
     368             : 
     369           0 : void DominatorTreeWrapperPass::verifyAnalysis() const {
     370             :   if (VerifyDomInfo)
     371             :     assert(DT.verify(DominatorTree::VerificationLevel::Full));
     372             :   else if (ExpensiveChecksEnabled)
     373             :     assert(DT.verify(DominatorTree::VerificationLevel::Basic));
     374           0 : }
     375             : 
     376           6 : void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
     377           6 :   DT.print(OS);
     378           6 : }
     379             : 

Generated by: LCOV version 1.13