LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineDominators.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 48 69 69.6 %
Date: 2017-09-14 15:23:50 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       72306 : static cl::opt<bool, true> VerifyMachineDomInfoX(
      29      144612 :     "verify-machine-dom-info", cl::location(VerifyMachineDomInfo),
      30      289224 :     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     2566039 : INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
      40             :                 "MachineDominator Tree Construction", true, true)
      41             : 
      42             : char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
      43             : 
      44      108978 : void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
      45      108978 :   AU.setPreservesAll();
      46      108978 :   MachineFunctionPass::getAnalysisUsage(AU);
      47      108978 : }
      48             : 
      49      967535 : bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
      50     1935070 :   CriticalEdgesToSplit.clear();
      51      967535 :   NewBBs.clear();
      52     2902605 :   DT.reset(new DomTreeBase<MachineBasicBlock>());
      53     2902605 :   DT->recalculate(F);
      54      967535 :   return false;
      55             : }
      56             : 
      57      111399 : MachineDominatorTree::MachineDominatorTree()
      58      445596 :     : MachineFunctionPass(ID) {
      59      111399 :   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
      60      111399 : }
      61             : 
      62      965305 : void MachineDominatorTree::releaseMemory() {
      63     1930610 :   CriticalEdgesToSplit.clear();
      64     1930610 :   DT.reset(nullptr);
      65      965305 : }
      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     2032612 : void MachineDominatorTree::applySplitCriticalEdges() const {
      78             :   // Bail out early if there is nothing to do.
      79     2032612 :   if (CriticalEdgesToSplit.empty())
      80     2030144 :     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        7404 :   SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
      87        2468 :   size_t Idx = 0;
      88             : 
      89             :   // Collect all the dominance properties info, before invalidating
      90             :   // the underlying DT.
      91       12381 :   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
      92             :     // Update dominator information.
      93        4977 :     MachineBasicBlock *Succ = Edge.ToBB;
      94       14931 :     MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
      95             : 
      96       10481 :     for (MachineBasicBlock *PredBB : Succ->predecessors()) {
      97        5304 :       if (PredBB == Edge.NewBB)
      98         286 :         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        5018 :       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         201 :         PredBB = *PredBB->pred_begin();
     116             :       }
     117       20072 :       if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
     118        9554 :         IsNewIDom[Idx] = false;
     119        4777 :         break;
     120             :       }
     121             :     }
     122        4977 :     ++Idx;
     123             :   }
     124             : 
     125             :   // Now, update DT with the collected dominance properties info.
     126        2468 :   Idx = 0;
     127       12381 :   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
     128             :     // We know FromBB dominates NewBB.
     129        9954 :     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       14931 :     if (IsNewIDom[Idx])
     135         800 :       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
     136        4977 :     ++Idx;
     137             :   }
     138        2468 :   NewBBs.clear();
     139        4936 :   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           0 :   OtherDT.recalculate(F);
     149           0 :   if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() ||
     150           0 :       DT->compare(OtherDT)) {
     151           0 :     errs() << "MachineDominatorTree is not up to date!\nComputed:\n";
     152           0 :     DT->print(errs());
     153           0 :     errs() << "\nActual:\n";
     154           0 :     OtherDT.print(errs());
     155           0 :     abort();
     156             :   }
     157      216918 : }

Generated by: LCOV version 1.13