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/CodeGen/Passes.h"
  17 #include "llvm/ADT/SmallBitVector.h"
  18
  19 using namespace llvm;
  20
  21 namespace llvm {
  22 template class DomTreeNodeBase<MachineBasicBlock>;
  23 template class DominatorTreeBase<MachineBasicBlock>;
  24 }
  25
  26 char MachineDominatorTree::ID = 0;
  27
  28 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
  29                 "MachineDominator Tree Construction", true, true)
  30
  31 char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
  32
  33 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
  34   AU.setPreservesAll();
  35   MachineFunctionPass::getAnalysisUsage(AU);
  36 }
  37
  38 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
  39   CriticalEdgesToSplit.clear();
  40   NewBBs.clear();
  41   DT->recalculate(F);
  42
  43   return false;
  44 }
  45
  46 MachineDominatorTree::MachineDominatorTree()
  47     : MachineFunctionPass(ID) {
  48   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
  49   DT = new DominatorTreeBase<MachineBasicBlock>(false);
  50 }
  51
  52 MachineDominatorTree::~MachineDominatorTree() {
  53   delete DT;
  54 }
  55
  56 void MachineDominatorTree::releaseMemory() {
  57   DT->releaseMemory();
  58 }
  59
  60 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
  61   DT->print(OS);
  62 }
  63
  64 void MachineDominatorTree::applySplitCriticalEdges() const {
  65   // Bail out early if there is nothing to do.
  66   if (CriticalEdgesToSplit.empty())
  67     return;
  68
  69   // For each element in CriticalEdgesToSplit, remember whether or not element
  70   // is the new immediate domminator of its successor. The mapping is done by
  71   // index, i.e., the information for the ith element of CriticalEdgesToSplit is
  72   // the ith element of IsNewIDom.
  73   SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
  74   size_t Idx = 0;
  75
  76   // Collect all the dominance properties info, before invalidating
  77   // the underlying DT.
  78   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
  79     // Update dominator information.
  80     MachineBasicBlock *Succ = Edge.ToBB;
  81     MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
  82
  83     for (MachineBasicBlock *PredBB : Succ->predecessors()) {
  84       if (PredBB == Edge.NewBB)
  85         continue;
  86       // If we are in this situation:
  87       // FromBB1        FromBB2
  88       //    +              +
  89       //   + +            + +
  90       //  +   +          +   +
  91       // ...  Split1  Split2 ...
  92       //           +   +
  93       //            + +
  94       //             +
  95       //            Succ
  96       // Instead of checking the domiance property with Split2, we check it with
  97       // FromBB2 since Split2 is still unknown of the underlying DT structure.
  98       if (NewBBs.count(PredBB)) {
  99         assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
 100                                            "critical edge split has more "
 101                                            "than one predecessor!");
 102         PredBB = *PredBB->pred_begin();
 103       }
 104       if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
 105         IsNewIDom[Idx] = false;
 106         break;
 107       }
 108     }
 109     ++Idx;
 110   }
 111
 112   // Now, update DT with the collected dominance properties info.
 113   Idx = 0;
 114   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
 115     // We know FromBB dominates NewBB.
 116     MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
 117
 118     // If all the other predecessors of "Succ" are dominated by "Succ" itself
 119     // then the new block is the new immediate dominator of "Succ". Otherwise,
 120     // the new block doesn't dominate anything.
 121     if (IsNewIDom[Idx])
 122       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
 123     ++Idx;
 124   }
 125   NewBBs.clear();
 126   CriticalEdgesToSplit.clear();
 127 }