llvm/lib/CodeGen/MachinePostDominators.cpp

   1 //===- MachinePostDominators.cpp -Machine Post 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 // post dominators on machine functions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/MachinePostDominators.h"
  15 #include "llvm/InitializePasses.h"
  16 #include "llvm/Support/GenericDomTreeConstruction.h"
  17
  18 using namespace llvm;
  19
  20 namespace llvm {
  21 template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTreeBase
  22
  23 namespace DomTreeBuilder {
  24
  25 template void Calculate<MBBPostDomTree>(MBBPostDomTree &DT);
  26 template void InsertEdge<MBBPostDomTree>(MBBPostDomTree &DT,
  27                                          MachineBasicBlock *From,
  28                                          MachineBasicBlock *To);
  29 template void DeleteEdge<MBBPostDomTree>(MBBPostDomTree &DT,
  30                                          MachineBasicBlock *From,
  31                                          MachineBasicBlock *To);
  32 template void ApplyUpdates<MBBPostDomTree>(MBBPostDomTree &DT,
  33                                            MBBPostDomTreeGraphDiff &,
  34                                            MBBPostDomTreeGraphDiff *);
  35 template bool Verify<MBBPostDomTree>(const MBBPostDomTree &DT,
  36                                      MBBPostDomTree::VerificationLevel VL);
  37
  38 } // namespace DomTreeBuilder
  39 extern bool VerifyMachineDomInfo;
  40 } // namespace llvm
  41
  42 AnalysisKey MachinePostDominatorTreeAnalysis::Key;
  43
  44 MachinePostDominatorTreeAnalysis::Result
  45 MachinePostDominatorTreeAnalysis::run(MachineFunction &MF,
  46                                       MachineFunctionAnalysisManager &) {
  47   return MachinePostDominatorTree(MF);
  48 }
  49
  50 PreservedAnalyses
  51 MachinePostDominatorTreePrinterPass::run(MachineFunction &MF,
  52                                          MachineFunctionAnalysisManager &MFAM) {
  53   OS << "MachinePostDominatorTree for machine function: " << MF.getName()
  54      << '\n';
  55   MFAM.getResult<MachinePostDominatorTreeAnalysis>(MF).print(OS);
  56   return PreservedAnalyses::all();
  57 }
  58
  59 char MachinePostDominatorTreeWrapperPass::ID = 0;
  60
  61 //declare initializeMachinePostDominatorTreePass
  62 INITIALIZE_PASS(MachinePostDominatorTreeWrapperPass, "machinepostdomtree",
  63                 "MachinePostDominator Tree Construction", true, true)
  64
  65 MachinePostDominatorTreeWrapperPass::MachinePostDominatorTreeWrapperPass()
  66     : MachineFunctionPass(ID), PDT() {
  67   initializeMachinePostDominatorTreeWrapperPassPass(
  68       *PassRegistry::getPassRegistry());
  69 }
  70
  71 bool MachinePostDominatorTreeWrapperPass::runOnMachineFunction(
  72     MachineFunction &F) {
  73   PDT = MachinePostDominatorTree();
  74   PDT->recalculate(F);
  75   return false;
  76 }
  77
  78 void MachinePostDominatorTreeWrapperPass::getAnalysisUsage(
  79     AnalysisUsage &AU) const {
  80   AU.setPreservesAll();
  81   MachineFunctionPass::getAnalysisUsage(AU);
  82 }
  83
  84 bool MachinePostDominatorTree::invalidate(
  85     MachineFunction &, const PreservedAnalyses &PA,
  86     MachineFunctionAnalysisManager::Invalidator &) {
  87   // Check whether the analysis, all analyses on machine functions, or the
  88   // machine function's CFG have been preserved.
  89   auto PAC = PA.getChecker<MachinePostDominatorTreeAnalysis>();
  90   return !PAC.preserved() &&
  91          !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&
  92          !PAC.preservedSet<CFGAnalyses>();
  93 }
  94
  95 MachineBasicBlock *MachinePostDominatorTree::findNearestCommonDominator(
  96     ArrayRef<MachineBasicBlock *> Blocks) const {
  97   assert(!Blocks.empty());
  98
  99   MachineBasicBlock *NCD = Blocks.front();
 100   for (MachineBasicBlock *BB : Blocks.drop_front()) {
 101     NCD = Base::findNearestCommonDominator(NCD, BB);
 102
 103     // Stop when the root is reached.
 104     if (isVirtualRoot(getNode(NCD)))
 105       return nullptr;
 106   }
 107
 108   return NCD;
 109 }
 110
 111 void MachinePostDominatorTreeWrapperPass::verifyAnalysis() const {
 112   if (VerifyMachineDomInfo && PDT &&
 113       !PDT->verify(MachinePostDominatorTree::VerificationLevel::Basic))
 114     report_fatal_error("MachinePostDominatorTree verification failed!");
 115 }
 116
 117 void MachinePostDominatorTreeWrapperPass::print(llvm::raw_ostream &OS,
 118                                                 const Module *M) const {
 119   PDT->print(OS);
 120 }