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