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/Pass.h"
  19 #include "llvm/PassRegistry.h"
  20 #include "llvm/Support/CommandLine.h"
  21 #include "llvm/Support/GenericDomTreeConstruction.h"
  22
  23 using namespace llvm;
  24
  25 namespace llvm {
  26 // Always verify dominfo if expensive checking is enabled.
  27 #ifdef EXPENSIVE_CHECKS
  28 bool VerifyMachineDomInfo = true;
  29 #else
  30 bool VerifyMachineDomInfo = false;
  31 #endif
  32 } // namespace llvm
  33
  34 static cl::opt<bool, true> VerifyMachineDomInfoX(
  35     "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
  36     cl::desc("Verify machine dominator info (time consuming)"));
  37
  38 namespace llvm {
  39 template class DomTreeNodeBase<MachineBasicBlock>;
  40 template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
  41
  42 namespace DomTreeBuilder {
  43 template void Calculate<MBBDomTree>(MBBDomTree &DT);
  44 template void CalculateWithUpdates<MBBDomTree>(MBBDomTree &DT, MBBUpdates U);
  45
  46 template void InsertEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From,
  47                                      MachineBasicBlock *To);
  48
  49 template void DeleteEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From,
  50                                      MachineBasicBlock *To);
  51
  52 template void ApplyUpdates<MBBDomTree>(MBBDomTree &DT, MBBDomTreeGraphDiff &,
  53                                        MBBDomTreeGraphDiff *);
  54
  55 template bool Verify<MBBDomTree>(const MBBDomTree &DT,
  56                                  MBBDomTree::VerificationLevel VL);
  57 } // namespace DomTreeBuilder
  58 }
  59
  60 bool MachineDominatorTree::invalidate(
  61     MachineFunction &, const PreservedAnalyses &PA,
  62     MachineFunctionAnalysisManager::Invalidator &) {
  63   // Check whether the analysis, all analyses on machine functions, or the
  64   // machine function's CFG have been preserved.
  65   auto PAC = PA.getChecker<MachineDominatorTreeAnalysis>();
  66   return !PAC.preserved() &&
  67          !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&
  68          !PAC.preservedSet<CFGAnalyses>();
  69 }
  70
  71 AnalysisKey MachineDominatorTreeAnalysis::Key;
  72
  73 MachineDominatorTreeAnalysis::Result
  74 MachineDominatorTreeAnalysis::run(MachineFunction &MF,
  75                                   MachineFunctionAnalysisManager &) {
  76   return MachineDominatorTree(MF);
  77 }
  78
  79 PreservedAnalyses
  80 MachineDominatorTreePrinterPass::run(MachineFunction &MF,
  81                                      MachineFunctionAnalysisManager &MFAM) {
  82   OS << "MachineDominatorTree for machine function: " << MF.getName() << '\n';
  83   MFAM.getResult<MachineDominatorTreeAnalysis>(MF).print(OS);
  84   return PreservedAnalyses::all();
  85 }
  86
  87 char MachineDominatorTreeWrapperPass::ID = 0;
  88
  89 INITIALIZE_PASS(MachineDominatorTreeWrapperPass, "machinedomtree",
  90                 "MachineDominator Tree Construction", true, true)
  91
  92 MachineDominatorTreeWrapperPass::MachineDominatorTreeWrapperPass()
  93     : MachineFunctionPass(ID) {
  94   initializeMachineDominatorTreeWrapperPassPass(
  95       *PassRegistry::getPassRegistry());
  96 }
  97
  98 void MachineDominatorTree::calculate(MachineFunction &F) {
  99   CriticalEdgesToSplit.clear();
 100   NewBBs.clear();
 101   recalculate(F);
 102 }
 103
 104 char &llvm::MachineDominatorsID = MachineDominatorTreeWrapperPass::ID;
 105
 106 bool MachineDominatorTreeWrapperPass::runOnMachineFunction(MachineFunction &F) {
 107   DT = MachineDominatorTree(F);
 108   return false;
 109 }
 110
 111 void MachineDominatorTreeWrapperPass::releaseMemory() { DT.reset(); }
 112
 113 void MachineDominatorTreeWrapperPass::verifyAnalysis() const {
 114   if (VerifyMachineDomInfo && DT)
 115     if (!DT->verify(MachineDominatorTree::VerificationLevel::Basic))
 116       report_fatal_error("MachineDominatorTree verification failed!");
 117 }
 118
 119 void MachineDominatorTreeWrapperPass::print(raw_ostream &OS,
 120                                             const Module *) const {
 121   if (DT)
 122     DT->print(OS);
 123 }
 124
 125 void MachineDominatorTree::applySplitCriticalEdges() const {
 126   // Bail out early if there is nothing to do.
 127   if (CriticalEdgesToSplit.empty())
 128     return;
 129
 130   // For each element in CriticalEdgesToSplit, remember whether or not element
 131   // is the new immediate domminator of its successor. The mapping is done by
 132   // index, i.e., the information for the ith element of CriticalEdgesToSplit is
 133   // the ith element of IsNewIDom.
 134   SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
 135   size_t Idx = 0;
 136
 137   // Collect all the dominance properties info, before invalidating
 138   // the underlying DT.
 139   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
 140     // Update dominator information.
 141     MachineBasicBlock *Succ = Edge.ToBB;
 142     MachineDomTreeNode *SuccDTNode = Base::getNode(Succ);
 143
 144     for (MachineBasicBlock *PredBB : Succ->predecessors()) {
 145       if (PredBB == Edge.NewBB)
 146         continue;
 147       // If we are in this situation:
 148       // FromBB1        FromBB2
 149       //    +              +
 150       //   + +            + +
 151       //  +   +          +   +
 152       // ...  Split1  Split2 ...
 153       //           +   +
 154       //            + +
 155       //             +
 156       //            Succ
 157       // Instead of checking the domiance property with Split2, we check it with
 158       // FromBB2 since Split2 is still unknown of the underlying DT structure.
 159       if (NewBBs.count(PredBB)) {
 160         assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
 161                                            "critical edge split has more "
 162                                            "than one predecessor!");
 163         PredBB = *PredBB->pred_begin();
 164       }
 165       if (!Base::dominates(SuccDTNode, Base::getNode(PredBB))) {
 166         IsNewIDom[Idx] = false;
 167         break;
 168       }
 169     }
 170     ++Idx;
 171   }
 172
 173   // Now, update DT with the collected dominance properties info.
 174   Idx = 0;
 175   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
 176     // We know FromBB dominates NewBB.
 177     MachineDomTreeNode *NewDTNode =
 178         const_cast<MachineDominatorTree *>(this)->Base::addNewBlock(
 179             Edge.NewBB, Edge.FromBB);
 180
 181     // If all the other predecessors of "Succ" are dominated by "Succ" itself
 182     // then the new block is the new immediate dominator of "Succ". Otherwise,
 183     // the new block doesn't dominate anything.
 184     if (IsNewIDom[Idx])
 185       const_cast<MachineDominatorTree *>(this)->Base::changeImmediateDominator(
 186           Base::getNode(Edge.ToBB), NewDTNode);
 187     ++Idx;
 188   }
 189   NewBBs.clear();
 190   CriticalEdgesToSplit.clear();
 191 }