LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineDominators.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 39 60 65.0 %
Date: 2018-02-23 15:42:53 Functions: 9 12 75.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- MachineDominators.cpp - Machine 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 on machine functions.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #include "llvm/CodeGen/MachineDominators.h"
      16             : #include "llvm/ADT/SmallBitVector.h"
      17             : #include "llvm/CodeGen/Passes.h"
      18             : #include "llvm/Support/CommandLine.h"
      19             : 
      20             : using namespace llvm;
      21             : 
      22             : // Always verify dominfo if expensive checking is enabled.
      23             : #ifdef EXPENSIVE_CHECKS
      24             : static bool VerifyMachineDomInfo = true;
      25             : #else
      26             : static bool VerifyMachineDomInfo = false;
      27             : #endif
      28       81686 : static cl::opt<bool, true> VerifyMachineDomInfoX(
      29      163372 :     "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
      30      245058 :     cl::desc("Verify machine dominator info (time consuming)"));
      31             : 
      32             : namespace llvm {
      33             : template class DomTreeNodeBase<MachineBasicBlock>;
      34             : template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
      35             : }
      36             : 
      37             : char MachineDominatorTree::ID = 0;
      38             : 
      39     2469301 : INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
      40             :                 "MachineDominator Tree Construction", true, true)
      41             : 
      42             : char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
      43             : 
      44      123396 : void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
      45             :   AU.setPreservesAll();
      46      123396 :   MachineFunctionPass::getAnalysisUsage(AU);
      47      123396 : }
      48             : 
      49     1166954 : bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
      50             :   CriticalEdgesToSplit.clear();
      51     1166954 :   NewBBs.clear();
      52     1166954 :   DT.reset(new DomTreeBase<MachineBasicBlock>());
      53             :   DT->recalculate(F);
      54     1166954 :   return false;
      55             : }
      56             : 
      57      126836 : MachineDominatorTree::MachineDominatorTree()
      58      126836 :     : MachineFunctionPass(ID) {
      59      126836 :   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
      60      126836 : }
      61             : 
      62     1163717 : void MachineDominatorTree::releaseMemory() {
      63             :   CriticalEdgesToSplit.clear();
      64             :   DT.reset(nullptr);
      65     1163717 : }
      66             : 
      67           0 : void MachineDominatorTree::verifyAnalysis() const {
      68           0 :   if (DT && VerifyMachineDomInfo)
      69           0 :     verifyDomTree();
      70           0 : }
      71             : 
      72           0 : void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
      73           0 :   if (DT)
      74           0 :     DT->print(OS);
      75           0 : }
      76             : 
      77     2342857 : void MachineDominatorTree::applySplitCriticalEdges() const {
      78             :   // Bail out early if there is nothing to do.
      79     2342857 :   if (CriticalEdgesToSplit.empty())
      80     2340246 :     return;
      81             : 
      82             :   // For each element in CriticalEdgesToSplit, remember whether or not element
      83             :   // is the new immediate domminator of its successor. The mapping is done by
      84             :   // index, i.e., the information for the ith element of CriticalEdgesToSplit is
      85             :   // the ith element of IsNewIDom.
      86        5222 :   SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
      87             :   size_t Idx = 0;
      88             : 
      89             :   // Collect all the dominance properties info, before invalidating
      90             :   // the underlying DT.
      91       13523 :   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
      92             :     // Update dominator information.
      93        5456 :     MachineBasicBlock *Succ = Edge.ToBB;
      94             :     MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
      95             : 
      96        6015 :     for (MachineBasicBlock *PredBB : Succ->predecessors()) {
      97        5809 :       if (PredBB == Edge.NewBB)
      98         312 :         continue;
      99             :       // If we are in this situation:
     100             :       // FromBB1        FromBB2
     101             :       //    +              +
     102             :       //   + +            + +
     103             :       //  +   +          +   +
     104             :       // ...  Split1  Split2 ...
     105             :       //           +   +
     106             :       //            + +
     107             :       //             +
     108             :       //            Succ
     109             :       // Instead of checking the domiance property with Split2, we check it with
     110             :       // FromBB2 since Split2 is still unknown of the underlying DT structure.
     111        5497 :       if (NewBBs.count(PredBB)) {
     112             :         assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
     113             :                                            "critical edge split has more "
     114             :                                            "than one predecessor!");
     115         265 :         PredBB = *PredBB->pred_begin();
     116             :       }
     117        5497 :       if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
     118        5250 :         IsNewIDom[Idx] = false;
     119        5250 :         break;
     120             :       }
     121             :     }
     122        5456 :     ++Idx;
     123             :   }
     124             : 
     125             :   // Now, update DT with the collected dominance properties info.
     126             :   Idx = 0;
     127       13523 :   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
     128             :     // We know FromBB dominates NewBB.
     129        5456 :     MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
     130             : 
     131             :     // If all the other predecessors of "Succ" are dominated by "Succ" itself
     132             :     // then the new block is the new immediate dominator of "Succ". Otherwise,
     133             :     // the new block doesn't dominate anything.
     134       10912 :     if (IsNewIDom[Idx])
     135         206 :       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
     136        5456 :     ++Idx;
     137             :   }
     138        2611 :   NewBBs.clear();
     139             :   CriticalEdgesToSplit.clear();
     140             : }
     141             : 
     142           0 : void MachineDominatorTree::verifyDomTree() const {
     143           0 :   if (!DT)
     144           0 :     return;
     145           0 :   MachineFunction &F = *getRoot()->getParent();
     146             : 
     147           0 :   DomTreeBase<MachineBasicBlock> OtherDT;
     148             :   OtherDT.recalculate(F);
     149           0 :   if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() ||
     150           0 :       DT->compare(OtherDT)) {
     151           0 :     errs() << "MachineDominatorTree for function " << F.getName()
     152           0 :            << " is not up to date!\nComputed:\n";
     153           0 :     DT->print(errs());
     154           0 :     errs() << "\nActual:\n";
     155           0 :     OtherDT.print(errs());
     156           0 :     abort();
     157             :   }
     158      245058 : }

Generated by: LCOV version 1.13