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
invalidate(MachineFunction &,const PreservedAnalyses & PA,MachineFunctionAnalysisManager::Invalidator &)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
run(MachineFunction & MF,MachineFunctionAnalysisManager &)79 MachineDominatorTreeAnalysis::run(MachineFunction &MF,
80 MachineFunctionAnalysisManager &) {
81 return MachineDominatorTree(MF);
82 }
83
84 PreservedAnalyses
run(MachineFunction & MF,MachineFunctionAnalysisManager & MFAM)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
MachineDominatorTreeWrapperPass()97 MachineDominatorTreeWrapperPass::MachineDominatorTreeWrapperPass()
98 : MachineFunctionPass(ID) {
99 initializeMachineDominatorTreeWrapperPassPass(
100 *PassRegistry::getPassRegistry());
101 }
102
103 char &llvm::MachineDominatorsID = MachineDominatorTreeWrapperPass::ID;
104
runOnMachineFunction(MachineFunction & F)105 bool MachineDominatorTreeWrapperPass::runOnMachineFunction(MachineFunction &F) {
106 DT = MachineDominatorTree(F);
107 return false;
108 }
109
releaseMemory()110 void MachineDominatorTreeWrapperPass::releaseMemory() { DT.reset(); }
111
verifyAnalysis() const112 void MachineDominatorTreeWrapperPass::verifyAnalysis() const {
113 if (VerifyMachineDomInfo && DT)
114 if (!DT->verify(MachineDominatorTree::VerificationLevel::Basic))
115 report_fatal_error("MachineDominatorTree verification failed!");
116 }
117
print(raw_ostream & OS,const Module *) const118 void MachineDominatorTreeWrapperPass::print(raw_ostream &OS,
119 const Module *) const {
120 if (DT)
121 DT->print(OS);
122 }
123