LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineDominators.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 39 56 69.6 %
Date: 2018-06-17 00:07:59 Functions: 9 11 81.8 %
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      101169 : static cl::opt<bool, true> VerifyMachineDomInfoX(
      29      202338 :     "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
      30      303507 :     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     3360236 : INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
      40             :                 "MachineDominator Tree Construction", true, true)
      41             : 
      42             : char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
      43             : 
      44      109158 : void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
      45             :   AU.setPreservesAll();
      46      109158 :   MachineFunctionPass::getAnalysisUsage(AU);
      47      109158 : }
      48             : 
      49     1115610 : bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
      50             :   CriticalEdgesToSplit.clear();
      51     1115610 :   NewBBs.clear();
      52     1115610 :   DT.reset(new DomTreeBase<MachineBasicBlock>());
      53             :   DT->recalculate(F);
      54     1115610 :   return false;
      55             : }
      56             : 
      57      287181 : MachineDominatorTree::MachineDominatorTree()
      58      287181 :     : MachineFunctionPass(ID) {
      59      287181 :   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
      60      287181 : }
      61             : 
      62     1110863 : void MachineDominatorTree::releaseMemory() {
      63             :   CriticalEdgesToSplit.clear();
      64             :   DT.reset(nullptr);
      65     1110863 : }
      66             : 
      67           0 : void MachineDominatorTree::verifyAnalysis() const {
      68           0 :   if (DT && VerifyMachineDomInfo) {
      69           0 :     MachineFunction &F = *getRoot()->getParent();
      70             : 
      71           0 :     DomTreeBase<MachineBasicBlock> OtherDT;
      72             :     OtherDT.recalculate(F);
      73           0 :     if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() ||
      74           0 :         DT->compare(OtherDT)) {
      75           0 :       errs() << "MachineDominatorTree for function " << F.getName()
      76           0 :             << " is not up to date!\nComputed:\n";
      77           0 :       DT->print(errs());
      78           0 :       errs() << "\nActual:\n";
      79           0 :       OtherDT.print(errs());
      80           0 :       abort();
      81             :     }
      82             :   }
      83           0 : }
      84             : 
      85           0 : void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
      86           0 :   if (DT)
      87           0 :     DT->print(OS);
      88           0 : }
      89             : 
      90     2590073 : void MachineDominatorTree::applySplitCriticalEdges() const {
      91             :   // Bail out early if there is nothing to do.
      92     2590073 :   if (CriticalEdgesToSplit.empty())
      93     2587173 :     return;
      94             : 
      95             :   // For each element in CriticalEdgesToSplit, remember whether or not element
      96             :   // is the new immediate domminator of its successor. The mapping is done by
      97             :   // index, i.e., the information for the ith element of CriticalEdgesToSplit is
      98             :   // the ith element of IsNewIDom.
      99        5800 :   SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
     100             :   size_t Idx = 0;
     101             : 
     102             :   // Collect all the dominance properties info, before invalidating
     103             :   // the underlying DT.
     104       14388 :   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
     105             :     // Update dominator information.
     106        5744 :     MachineBasicBlock *Succ = Edge.ToBB;
     107             :     MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
     108             : 
     109        6357 :     for (MachineBasicBlock *PredBB : Succ->predecessors()) {
     110        6128 :       if (PredBB == Edge.NewBB)
     111         343 :         continue;
     112             :       // If we are in this situation:
     113             :       // FromBB1        FromBB2
     114             :       //    +              +
     115             :       //   + +            + +
     116             :       //  +   +          +   +
     117             :       // ...  Split1  Split2 ...
     118             :       //           +   +
     119             :       //            + +
     120             :       //             +
     121             :       //            Succ
     122             :       // Instead of checking the domiance property with Split2, we check it with
     123             :       // FromBB2 since Split2 is still unknown of the underlying DT structure.
     124        5785 :       if (NewBBs.count(PredBB)) {
     125             :         assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
     126             :                                            "critical edge split has more "
     127             :                                            "than one predecessor!");
     128         281 :         PredBB = *PredBB->pred_begin();
     129             :       }
     130        5785 :       if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
     131        5515 :         IsNewIDom[Idx] = false;
     132        5515 :         break;
     133             :       }
     134             :     }
     135        5744 :     ++Idx;
     136             :   }
     137             : 
     138             :   // Now, update DT with the collected dominance properties info.
     139             :   Idx = 0;
     140       14388 :   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
     141             :     // We know FromBB dominates NewBB.
     142        5744 :     MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
     143             : 
     144             :     // If all the other predecessors of "Succ" are dominated by "Succ" itself
     145             :     // then the new block is the new immediate dominator of "Succ". Otherwise,
     146             :     // the new block doesn't dominate anything.
     147       11488 :     if (IsNewIDom[Idx])
     148         229 :       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
     149        5744 :     ++Idx;
     150             :   }
     151        2900 :   NewBBs.clear();
     152             :   CriticalEdgesToSplit.clear();
     153      303507 : }

Generated by: LCOV version 1.13