Home | History | Annotate | Download | only in CodeGen 
      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 static cl::opt<bool, true> VerifyMachineDomInfoX(
     29     "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
     30     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 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
     40                 "MachineDominator Tree Construction", true, true)
     41 
     42 char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
     43 
     44 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
     45   AU.setPreservesAll();
     46   MachineFunctionPass::getAnalysisUsage(AU);
     47 }
     48 
     49 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
     50   CriticalEdgesToSplit.clear();
     51   NewBBs.clear();
     52   DT.reset(new DomTreeBase<MachineBasicBlock>());
     53   DT->recalculate(F);
     54   return false;
     55 }
     56 
     57 MachineDominatorTree::MachineDominatorTree()
     58     : MachineFunctionPass(ID) {
     59   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
     60 }
     61 
     62 void MachineDominatorTree::releaseMemory() {
     63   CriticalEdgesToSplit.clear();
     64   DT.reset(nullptr);
     65 }
     66 
     67 void MachineDominatorTree::verifyAnalysis() const {
     68   if (DT && VerifyMachineDomInfo) {
     69     MachineFunction &F = *getRoot()->getParent();
     70 
     71     DomTreeBase<MachineBasicBlock> OtherDT;
     72     OtherDT.recalculate(F);
     73     if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() ||
     74         DT->compare(OtherDT)) {
     75       errs() << "MachineDominatorTree for function " << F.getName()
     76             << " is not up to date!\nComputed:\n";
     77       DT->print(errs());
     78       errs() << "\nActual:\n";
     79       OtherDT.print(errs());
     80       abort();
     81     }
     82   }
     83 }
     84 
     85 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
     86   if (DT)
     87     DT->print(OS);
     88 }
     89 
     90 void MachineDominatorTree::applySplitCriticalEdges() const {
     91   // Bail out early if there is nothing to do.
     92   if (CriticalEdgesToSplit.empty())
     93     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   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   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
    105     // Update dominator information.
    106     MachineBasicBlock *Succ = Edge.ToBB;
    107     MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
    108 
    109     for (MachineBasicBlock *PredBB : Succ->predecessors()) {
    110       if (PredBB == Edge.NewBB)
    111         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       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         PredBB = *PredBB->pred_begin();
    129       }
    130       if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
    131         IsNewIDom[Idx] = false;
    132         break;
    133       }
    134     }
    135     ++Idx;
    136   }
    137 
    138   // Now, update DT with the collected dominance properties info.
    139   Idx = 0;
    140   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
    141     // We know FromBB dominates NewBB.
    142     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     if (IsNewIDom[Idx])
    148       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
    149     ++Idx;
    150   }
    151   NewBBs.clear();
    152   CriticalEdgesToSplit.clear();
    153 }
    154