LCOV - code coverage report
Current view: top level - lib/IR - Dominators.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 109 124 87.9 %
Date: 2017-09-14 15:23:50 Functions: 19 20 95.0 %
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/IR/CFG.h"
      21             : #include "llvm/IR/Instructions.h"
      22             : #include "llvm/IR/PassManager.h"
      23             : #include "llvm/Support/CommandLine.h"
      24             : #include "llvm/Support/Debug.h"
      25             : #include "llvm/Support/GenericDomTreeConstruction.h"
      26             : #include "llvm/Support/raw_ostream.h"
      27             : #include <algorithm>
      28             : using namespace llvm;
      29             : 
      30             : // Always verify dominfo if expensive checking is enabled.
      31             : #ifdef EXPENSIVE_CHECKS
      32             : bool llvm::VerifyDomInfo = true;
      33             : #else
      34             : bool llvm::VerifyDomInfo = false;
      35             : #endif
      36             : static cl::opt<bool,true>
      37      216990 : VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo),
      38      289320 :                cl::desc("Verify dominator info (time consuming)"));
      39             : 
      40      154784 : bool BasicBlockEdge::isSingleEdge() const {
      41      154784 :   const TerminatorInst *TI = Start->getTerminator();
      42      154784 :   unsigned NumEdgesToEnd = 0;
      43      464346 :   for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
      44      309568 :     if (TI->getSuccessor(i) == End)
      45      154790 :       ++NumEdgesToEnd;
      46      309568 :     if (NumEdgesToEnd >= 2)
      47             :       return false;
      48             :   }
      49             :   assert(NumEdgesToEnd == 1);
      50             :   return true;
      51             : }
      52             : 
      53             : //===----------------------------------------------------------------------===//
      54             : //  DominatorTree Implementation
      55             : //===----------------------------------------------------------------------===//
      56             : //
      57             : // Provide public access to DominatorTree information.  Implementation details
      58             : // can be found in Dominators.h, GenericDomTree.h, and
      59             : // GenericDomTreeConstruction.h.
      60             : //
      61             : //===----------------------------------------------------------------------===//
      62             : 
      63             : template class llvm::DomTreeNodeBase<BasicBlock>;
      64             : template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
      65             : template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
      66             : 
      67             : template struct llvm::DomTreeBuilder::Update<BasicBlock *>;
      68             : 
      69             : template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
      70             :     DomTreeBuilder::BBDomTree &DT);
      71             : template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
      72             :     DomTreeBuilder::BBPostDomTree &DT);
      73             : 
      74             : template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
      75             :     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
      76             : template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
      77             :     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
      78             : 
      79             : template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
      80             :     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
      81             : template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
      82             :     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
      83             : 
      84             : template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
      85             :     DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates);
      86             : template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
      87             :     DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
      88             : 
      89             : template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
      90             :     const DomTreeBuilder::BBDomTree &DT);
      91             : template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
      92             :     const DomTreeBuilder::BBPostDomTree &DT);
      93             : 
      94        1550 : bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
      95             :                                FunctionAnalysisManager::Invalidator &) {
      96             :   // Check whether the analysis, all analyses on functions, or the function's
      97             :   // CFG have been preserved.
      98        1550 :   auto PAC = PA.getChecker<DominatorTreeAnalysis>();
      99        2699 :   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
     100        2699 :            PAC.preservedSet<CFGAnalyses>());
     101             : }
     102             : 
     103             : // dominates - Return true if Def dominates a use in User. This performs
     104             : // the special checks necessary if Def and User are in the same basic block.
     105             : // Note that Def doesn't dominate a use in Def itself!
     106      555945 : bool DominatorTree::dominates(const Instruction *Def,
     107             :                               const Instruction *User) const {
     108      555945 :   const BasicBlock *UseBB = User->getParent();
     109      555945 :   const BasicBlock *DefBB = Def->getParent();
     110             : 
     111             :   // Any unreachable use is dominated, even if Def == User.
     112      555945 :   if (!isReachableFromEntry(UseBB))
     113             :     return true;
     114             : 
     115             :   // Unreachable definitions don't dominate anything.
     116      555787 :   if (!isReachableFromEntry(DefBB))
     117             :     return false;
     118             : 
     119             :   // An instruction doesn't dominate a use in itself.
     120      555782 :   if (Def == User)
     121             :     return false;
     122             : 
     123             :   // The value defined by an invoke dominates an instruction only if it
     124             :   // dominates every instruction in UseBB.
     125             :   // A PHI is dominated only if the instruction dominates every possible use in
     126             :   // the UseBB.
     127     1581603 :   if (isa<InvokeInst>(Def) || isa<PHINode>(User))
     128       95749 :     return dominates(Def, UseBB);
     129             : 
     130      453575 :   if (DefBB != UseBB)
     131      428825 :     return dominates(DefBB, UseBB);
     132             : 
     133             :   // Loop through the basic block until we find Def or User.
     134       24750 :   BasicBlock::const_iterator I = DefBB->begin();
     135    21968178 :   for (; &*I != Def && &*I != User; ++I)
     136             :     /*empty*/;
     137             : 
     138       24750 :   return &*I == Def;
     139             : }
     140             : 
     141             : // true if Def would dominate a use in any instruction in UseBB.
     142             : // note that dominates(Def, Def->getParent()) is false.
     143      109578 : bool DominatorTree::dominates(const Instruction *Def,
     144             :                               const BasicBlock *UseBB) const {
     145      109578 :   const BasicBlock *DefBB = Def->getParent();
     146             : 
     147             :   // Any unreachable use is dominated, even if DefBB == UseBB.
     148      109578 :   if (!isReachableFromEntry(UseBB))
     149             :     return true;
     150             : 
     151             :   // Unreachable definitions don't dominate anything.
     152      109575 :   if (!isReachableFromEntry(DefBB))
     153             :     return false;
     154             : 
     155      109575 :   if (DefBB == UseBB)
     156             :     return false;
     157             : 
     158             :   // Invoke results are only usable in the normal destination, not in the
     159             :   // exceptional destination.
     160       66137 :   if (const auto *II = dyn_cast<InvokeInst>(Def)) {
     161       66137 :     BasicBlock *NormalDest = II->getNormalDest();
     162       66137 :     BasicBlockEdge E(DefBB, NormalDest);
     163       66137 :     return dominates(E, UseBB);
     164             :   }
     165             : 
     166       22886 :   return dominates(DefBB, UseBB);
     167             : }
     168             : 
     169      587490 : bool DominatorTree::dominates(const BasicBlockEdge &BBE,
     170             :                               const BasicBlock *UseBB) const {
     171             :   // If the BB the edge ends in doesn't dominate the use BB, then the
     172             :   // edge also doesn't.
     173      587490 :   const BasicBlock *Start = BBE.getStart();
     174      587490 :   const BasicBlock *End = BBE.getEnd();
     175      587490 :   if (!dominates(End, UseBB))
     176             :     return false;
     177             : 
     178             :   // Simple case: if the end BB has a single predecessor, the fact that it
     179             :   // dominates the use block implies that the edge also does.
     180       24963 :   if (End->getSinglePredecessor())
     181             :     return true;
     182             : 
     183             :   // The normal edge from the invoke is critical. Conceptually, what we would
     184             :   // like to do is split it and check if the new block dominates the use.
     185             :   // With X being the new block, the graph would look like:
     186             :   //
     187             :   //        DefBB
     188             :   //          /\      .  .
     189             :   //         /  \     .  .
     190             :   //        /    \    .  .
     191             :   //       /      \   |  |
     192             :   //      A        X  B  C
     193             :   //      |         \ | /
     194             :   //      .          \|/
     195             :   //      .      NormalDest
     196             :   //      .
     197             :   //
     198             :   // Given the definition of dominance, NormalDest is dominated by X iff X
     199             :   // dominates all of NormalDest's predecessors (X, B, C in the example). X
     200             :   // trivially dominates itself, so we only have to find if it dominates the
     201             :   // other predecessors. Since the only way out of X is via NormalDest, X can
     202             :   // only properly dominate a node if NormalDest dominates that node too.
     203       10408 :   int IsDuplicateEdge = 0;
     204       20816 :   for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
     205       13602 :        PI != E; ++PI) {
     206       13528 :     const BasicBlock *BB = *PI;
     207       16648 :     if (BB == Start) {
     208             :       // If there are multiple edges between Start and End, by definition they
     209             :       // can't dominate anything.
     210        3122 :       if (IsDuplicateEdge++)
     211       10334 :         return false;
     212        3120 :       continue;
     213             :     }
     214             : 
     215       10406 :     if (!dominates(End, BB))
     216             :       return false;
     217             :   }
     218          74 :   return true;
     219             : }
     220             : 
     221      375797 : bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
     222      751594 :   Instruction *UserInst = cast<Instruction>(U.getUser());
     223             :   // A PHI in the end of the edge is dominated by it.
     224       11293 :   PHINode *PN = dyn_cast<PHINode>(UserInst);
     225       13704 :   if (PN && PN->getParent() == BBE.getEnd() &&
     226        2411 :       PN->getIncomingBlock(U) == BBE.getStart())
     227             :     return true;
     228             : 
     229             :   // Otherwise use the edge-dominates-block query, which
     230             :   // handles the crazy critical edge cases properly.
     231             :   const BasicBlock *UseBB;
     232      373778 :   if (PN)
     233        9274 :     UseBB = PN->getIncomingBlock(U);
     234             :   else
     235      364504 :     UseBB = UserInst->getParent();
     236      373778 :   return dominates(BBE, UseBB);
     237             : }
     238             : 
     239      267632 : bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
     240      535264 :   Instruction *UserInst = cast<Instruction>(U.getUser());
     241      267632 :   const BasicBlock *DefBB = Def->getParent();
     242             : 
     243             :   // Determine the block in which the use happens. PHI nodes use
     244             :   // their operands on edges; simulate this by thinking of the use
     245             :   // happening at the end of the predecessor block.
     246             :   const BasicBlock *UseBB;
     247      339865 :   if (PHINode *PN = dyn_cast<PHINode>(UserInst))
     248       72233 :     UseBB = PN->getIncomingBlock(U);
     249             :   else
     250      195399 :     UseBB = UserInst->getParent();
     251             : 
     252             :   // Any unreachable use is dominated, even if Def == User.
     253      267632 :   if (!isReachableFromEntry(UseBB))
     254             :     return true;
     255             : 
     256             :   // Unreachable definitions don't dominate anything.
     257      266772 :   if (!isReachableFromEntry(DefBB))
     258             :     return false;
     259             : 
     260             :   // Invoke instructions define their return values on the edges to their normal
     261             :   // successors, so we have to handle them specially.
     262             :   // Among other things, this means they don't dominate anything in
     263             :   // their own block, except possibly a phi, so we don't need to
     264             :   // walk the block in any case.
     265         833 :   if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
     266         833 :     BasicBlock *NormalDest = II->getNormalDest();
     267         833 :     BasicBlockEdge E(DefBB, NormalDest);
     268         833 :     return dominates(E, U);
     269             :   }
     270             : 
     271             :   // If the def and use are in different blocks, do a simple CFG dominator
     272             :   // tree query.
     273      265939 :   if (DefBB != UseBB)
     274      203878 :     return dominates(DefBB, UseBB);
     275             : 
     276             :   // Ok, def and use are in the same block. If the def is an invoke, it
     277             :   // doesn't dominate anything in the block. If it's a PHI, it dominates
     278             :   // everything in the block.
     279      124122 :   if (isa<PHINode>(UserInst))
     280             :     return true;
     281             : 
     282             :   // Otherwise, just loop through the basic block until we find Def or User.
     283         114 :   BasicBlock::const_iterator I = DefBB->begin();
     284         540 :   for (; &*I != Def && &*I != UserInst; ++I)
     285             :     /*empty*/;
     286             : 
     287         114 :   return &*I != UserInst;
     288             : }
     289             : 
     290         108 : bool DominatorTree::isReachableFromEntry(const Use &U) const {
     291         216 :   Instruction *I = dyn_cast<Instruction>(U.getUser());
     292             : 
     293             :   // ConstantExprs aren't really reachable from the entry block, but they
     294             :   // don't need to be treated like unreachable code either.
     295             :   if (!I) return true;
     296             : 
     297             :   // PHI nodes use their operands on their incoming edges.
     298         108 :   if (PHINode *PN = dyn_cast<PHINode>(I))
     299          12 :     return isReachableFromEntry(PN->getIncomingBlock(U));
     300             : 
     301             :   // Everything else uses their operands in their own block.
     302         102 :   return isReachableFromEntry(I->getParent());
     303             : }
     304             : 
     305          44 : void DominatorTree::verifyDomTree() const {
     306             :   // Perform the expensive checks only when VerifyDomInfo is set.
     307          45 :   if (VerifyDomInfo && !verify()) {
     308           0 :     errs() << "\n~~~~~~~~~~~\n\t\tDomTree verification failed!\n~~~~~~~~~~~\n";
     309           0 :     print(errs());
     310           0 :     abort();
     311             :   }
     312             : 
     313          88 :   Function &F = *getRoot()->getParent();
     314             : 
     315          88 :   DominatorTree OtherDT;
     316          44 :   OtherDT.recalculate(F);
     317          44 :   if (compare(OtherDT)) {
     318           0 :     errs() << "DominatorTree is not up to date!\nComputed:\n";
     319           0 :     print(errs());
     320           0 :     errs() << "\nActual:\n";
     321           0 :     OtherDT.print(errs());
     322           0 :     errs() << "\nCFG:\n";
     323           0 :     F.print(errs());
     324           0 :     errs().flush();
     325           0 :     abort();
     326             :   }
     327          44 : }
     328             : 
     329             : //===----------------------------------------------------------------------===//
     330             : //  DominatorTreeAnalysis and related pass implementations
     331             : //===----------------------------------------------------------------------===//
     332             : //
     333             : // This implements the DominatorTreeAnalysis which is used with the new pass
     334             : // manager. It also implements some methods from utility passes.
     335             : //
     336             : //===----------------------------------------------------------------------===//
     337             : 
     338        2056 : DominatorTree DominatorTreeAnalysis::run(Function &F,
     339             :                                          FunctionAnalysisManager &) {
     340        2056 :   DominatorTree DT;
     341        4112 :   DT.recalculate(F);
     342        2056 :   return DT;
     343             : }
     344             : 
     345             : AnalysisKey DominatorTreeAnalysis::Key;
     346             : 
     347           2 : DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
     348             : 
     349           3 : PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
     350             :                                                 FunctionAnalysisManager &AM) {
     351           3 :   OS << "DominatorTree for function: " << F.getName() << "\n";
     352           3 :   AM.getResult<DominatorTreeAnalysis>(F).print(OS);
     353             : 
     354           3 :   return PreservedAnalyses::all();
     355             : }
     356             : 
     357          28 : PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
     358             :                                                  FunctionAnalysisManager &AM) {
     359          28 :   AM.getResult<DominatorTreeAnalysis>(F).verifyDomTree();
     360             : 
     361          28 :   return PreservedAnalyses::all();
     362             : }
     363             : 
     364             : //===----------------------------------------------------------------------===//
     365             : //  DominatorTreeWrapperPass Implementation
     366             : //===----------------------------------------------------------------------===//
     367             : //
     368             : // The implementation details of the wrapper pass that holds a DominatorTree
     369             : // suitable for use with the legacy pass manager.
     370             : //
     371             : //===----------------------------------------------------------------------===//
     372             : 
     373             : char DominatorTreeWrapperPass::ID = 0;
     374     6808996 : INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
     375             :                 "Dominator Tree Construction", true, true)
     376             : 
     377     1252601 : bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
     378     2505202 :   DT.recalculate(F);
     379     1252601 :   return false;
     380             : }
     381             : 
     382           0 : void DominatorTreeWrapperPass::verifyAnalysis() const {
     383           0 :     if (VerifyDomInfo)
     384           0 :       DT.verifyDomTree();
     385           0 : }
     386             : 
     387           6 : void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
     388           6 :   DT.print(OS);
     389      216996 : }
     390             : 

Generated by: LCOV version 1.13