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/CodeGen/Passes.h" 16 #include "llvm/InitializePasses.h" 17 #include "llvm/Pass.h" 18 #include "llvm/PassRegistry.h" 19 #include "llvm/Support/CommandLine.h" 20 #include "llvm/Support/Compiler.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 LLVM_EXPORT_TEMPLATE DomTreeNodeBase<MachineBasicBlock>; 40 template class LLVM_EXPORT_TEMPLATE 41 DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase 42 43 namespace DomTreeBuilder { 44 template LLVM_EXPORT_TEMPLATE void Calculate<MBBDomTree>(MBBDomTree &DT); 45 template LLVM_EXPORT_TEMPLATE void 46 CalculateWithUpdates<MBBDomTree>(MBBDomTree &DT, MBBUpdates U); 47 48 template LLVM_EXPORT_TEMPLATE void 49 InsertEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From, 50 MachineBasicBlock *To); 51 52 template LLVM_EXPORT_TEMPLATE void 53 DeleteEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From, 54 MachineBasicBlock *To); 55 56 template LLVM_EXPORT_TEMPLATE void 57 ApplyUpdates<MBBDomTree>(MBBDomTree &DT, MBBDomTreeGraphDiff &, 58 MBBDomTreeGraphDiff *); 59 60 template LLVM_EXPORT_TEMPLATE bool 61 Verify<MBBDomTree>(const MBBDomTree &DT, MBBDomTree::VerificationLevel VL); 62 } // namespace DomTreeBuilder 63 } 64 65 bool MachineDominatorTree::invalidate( 66 MachineFunction &, const PreservedAnalyses &PA, 67 MachineFunctionAnalysisManager::Invalidator &) { 68 // Check whether the analysis, all analyses on machine functions, or the 69 // machine function's CFG have been preserved. 70 auto PAC = PA.getChecker<MachineDominatorTreeAnalysis>(); 71 return !PAC.preserved() && 72 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() && 73 !PAC.preservedSet<CFGAnalyses>(); 74 } 75 76 AnalysisKey MachineDominatorTreeAnalysis::Key; 77 78 MachineDominatorTreeAnalysis::Result 79 MachineDominatorTreeAnalysis::run(MachineFunction &MF, 80 MachineFunctionAnalysisManager &) { 81 return MachineDominatorTree(MF); 82 } 83 84 PreservedAnalyses 85 MachineDominatorTreePrinterPass::run(MachineFunction &MF, 86 MachineFunctionAnalysisManager &MFAM) { 87 OS << "MachineDominatorTree for machine function: " << MF.getName() << '\n'; 88 MFAM.getResult<MachineDominatorTreeAnalysis>(MF).print(OS); 89 return PreservedAnalyses::all(); 90 } 91 92 char MachineDominatorTreeWrapperPass::ID = 0; 93 94 INITIALIZE_PASS(MachineDominatorTreeWrapperPass, "machinedomtree", 95 "MachineDominator Tree Construction", true, true) 96 97 MachineDominatorTreeWrapperPass::MachineDominatorTreeWrapperPass() 98 : MachineFunctionPass(ID) { 99 initializeMachineDominatorTreeWrapperPassPass( 100 *PassRegistry::getPassRegistry()); 101 } 102 103 char &llvm::MachineDominatorsID = MachineDominatorTreeWrapperPass::ID; 104 105 bool MachineDominatorTreeWrapperPass::runOnMachineFunction(MachineFunction &F) { 106 DT = MachineDominatorTree(F); 107 return false; 108 } 109 110 void MachineDominatorTreeWrapperPass::releaseMemory() { DT.reset(); } 111 112 void MachineDominatorTreeWrapperPass::verifyAnalysis() const { 113 if (VerifyMachineDomInfo && DT) 114 if (!DT->verify(MachineDominatorTree::VerificationLevel::Basic)) 115 report_fatal_error("MachineDominatorTree verification failed!"); 116 } 117 118 void MachineDominatorTreeWrapperPass::print(raw_ostream &OS, 119 const Module *) const { 120 if (DT) 121 DT->print(OS); 122 } 123