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