lib/CodeGen/MachineDominators.cpp

   1 //===- MachineDominators.cpp - Machine Dominator Calculation --------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements simple dominator construction algorithms for finding
  10 // forward dominators on machine functions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/MachineDominators.h"
  15 #include "llvm/ADT/SmallBitVector.h"
  16 #include "llvm/CodeGen/Passes.h"
  17 #include "llvm/Support/CommandLine.h"
  18
  19 using namespace llvm;
  20
  21 // Always verify dominfo if expensive checking is enabled.
  22 #ifdef EXPENSIVE_CHECKS
  23 static bool VerifyMachineDomInfo = true;
  24 #else
  25 static bool VerifyMachineDomInfo = false;
  26 #endif
  27 static cl::opt<bool, true> VerifyMachineDomInfoX(
  28     "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
  29     cl::desc("Verify machine dominator info (time consuming)"));
  30
  31 namespace llvm {
  32 template class DomTreeNodeBase<MachineBasicBlock>;
  33 template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
  34 }
  35
  36 char MachineDominatorTree::ID = 0;
  37
  38 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
  39                 "MachineDominator Tree Construction", true, true)
  40
  41 char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
  42
  43 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
  44   AU.setPreservesAll();
  45   MachineFunctionPass::getAnalysisUsage(AU);
  46 }
  47
  48 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
  49   CriticalEdgesToSplit.clear();
  50   NewBBs.clear();
  51   DT.reset(new DomTreeBase<MachineBasicBlock>());
  52   DT->recalculate(F);
  53   return false;
  54 }
  55
  56 MachineDominatorTree::MachineDominatorTree()
  57     : MachineFunctionPass(ID) {
  58   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
  59 }
  60
  61 void MachineDominatorTree::releaseMemory() {
  62   CriticalEdgesToSplit.clear();
  63   DT.reset(nullptr);
  64 }
  65
  66 void MachineDominatorTree::verifyAnalysis() const {
  67   if (DT && VerifyMachineDomInfo) {
  68     MachineFunction &F = *getRoot()->getParent();
  69
  70     DomTreeBase<MachineBasicBlock> OtherDT;
  71     OtherDT.recalculate(F);
  72     if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() ||
  73         DT->compare(OtherDT)) {
  74       errs() << "MachineDominatorTree for function " << F.getName()
  75             << " is not up to date!\nComputed:\n";
  76       DT->print(errs());
  77       errs() << "\nActual:\n";
  78       OtherDT.print(errs());
  79       abort();
  80     }
  81   }
  82 }
  83
  84 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
  85   if (DT)
  86     DT->print(OS);
  87 }
  88
  89 void MachineDominatorTree::applySplitCriticalEdges() const {
  90   // Bail out early if there is nothing to do.
  91   if (CriticalEdgesToSplit.empty())
  92     return;
  93
  94   // For each element in CriticalEdgesToSplit, remember whether or not element
  95   // is the new immediate domminator of its successor. The mapping is done by
  96   // index, i.e., the information for the ith element of CriticalEdgesToSplit is
  97   // the ith element of IsNewIDom.
  98   SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
  99   size_t Idx = 0;
 100
 101   // Collect all the dominance properties info, before invalidating
 102   // the underlying DT.
 103   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
 104     // Update dominator information.
 105     MachineBasicBlock *Succ = Edge.ToBB;
 106     MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
 107
 108     for (MachineBasicBlock *PredBB : Succ->predecessors()) {
 109       if (PredBB == Edge.NewBB)
 110         continue;
 111       // If we are in this situation:
 112       // FromBB1        FromBB2
 113       //    +              +
 114       //   + +            + +
 115       //  +   +          +   +
 116       // ...  Split1  Split2 ...
 117       //           +   +
 118       //            + +
 119       //             +
 120       //            Succ
 121       // Instead of checking the domiance property with Split2, we check it with
 122       // FromBB2 since Split2 is still unknown of the underlying DT structure.
 123       if (NewBBs.count(PredBB)) {
 124         assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
 125                                            "critical edge split has more "
 126                                            "than one predecessor!");
 127         PredBB = *PredBB->pred_begin();
 128       }
 129       if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
 130         IsNewIDom[Idx] = false;
 131         break;
 132       }
 133     }
 134     ++Idx;
 135   }
 136
 137   // Now, update DT with the collected dominance properties info.
 138   Idx = 0;
 139   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
 140     // We know FromBB dominates NewBB.
 141     MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
 142
 143     // If all the other predecessors of "Succ" are dominated by "Succ" itself
 144     // then the new block is the new immediate dominator of "Succ". Otherwise,
 145     // the new block doesn't dominate anything.
 146     if (IsNewIDom[Idx])
 147       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
 148     ++Idx;
 149   }
 150   NewBBs.clear();
 151   CriticalEdgesToSplit.clear();
 152 }