lib/CodeGen/MachineDominators.cpp

   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),
  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     verifyDomTree();
  70 }
  71
  72 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
  73   if (DT)
  74     DT->print(OS);
  75 }
  76
  77 void MachineDominatorTree::applySplitCriticalEdges() const {
  78   // Bail out early if there is nothing to do.
  79   if (CriticalEdgesToSplit.empty())
  80     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   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   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
  92     // Update dominator information.
  93     MachineBasicBlock *Succ = Edge.ToBB;
  94     MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
  95
  96     for (MachineBasicBlock *PredBB : Succ->predecessors()) {
  97       if (PredBB == Edge.NewBB)
  98         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       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         PredBB = *PredBB->pred_begin();
 116       }
 117       if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
 118         IsNewIDom[Idx] = false;
 119         break;
 120       }
 121     }
 122     ++Idx;
 123   }
 124
 125   // Now, update DT with the collected dominance properties info.
 126   Idx = 0;
 127   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
 128     // We know FromBB dominates NewBB.
 129     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     if (IsNewIDom[Idx])
 135       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
 136     ++Idx;
 137   }
 138   NewBBs.clear();
 139   CriticalEdgesToSplit.clear();
 140 }
 141
 142 void MachineDominatorTree::verifyDomTree() const {
 143   if (!DT)
 144     return;
 145   MachineFunction &F = *getRoot()->getParent();
 146
 147   DomTreeBase<MachineBasicBlock> OtherDT;
 148   OtherDT.recalculate(F);
 149   if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() ||
 150       DT->compare(OtherDT)) {
 151     errs() << "MachineDominatorTree is not up to date!\nComputed:\n";
 152     DT->print(errs());
 153     errs() << "\nActual:\n";
 154     OtherDT.print(errs());
 155     abort();
 156   }
 157 }