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 } 121