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/Support/CommandLine.h"
19#include "llvm/Support/Compiler.h"
20#include "llvm/Support/ErrorHandling.h"
21#include "llvm/Support/GenericDomTreeConstruction.h"
22
23using namespace llvm;
24
25namespace llvm {
26// Always verify dominfo if expensive checking is enabled.
27#ifdef EXPENSIVE_CHECKS
28bool VerifyMachineDomInfo = true;
29#else
30bool VerifyMachineDomInfo = false;
31#endif
32} // namespace llvm
33
34static cl::opt<bool, true> VerifyMachineDomInfoX(
35 "verify-machine-dom-info", cl::location(L&: VerifyMachineDomInfo), cl::Hidden,
36 cl::desc("Verify machine dominator info (time consuming)"));
37
38namespace llvm {
39template class LLVM_EXPORT_TEMPLATE DomTreeNodeBase<MachineBasicBlock>;
40template class LLVM_EXPORT_TEMPLATE
41 DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
42
43namespace DomTreeBuilder {
44template LLVM_EXPORT_TEMPLATE void Calculate<MBBDomTree>(MBBDomTree &DT);
45template LLVM_EXPORT_TEMPLATE void
46CalculateWithUpdates<MBBDomTree>(MBBDomTree &DT, MBBUpdates U);
47
48template LLVM_EXPORT_TEMPLATE void
49InsertEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From,
50 MachineBasicBlock *To);
51
52template LLVM_EXPORT_TEMPLATE void
53DeleteEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From,
54 MachineBasicBlock *To);
55
56template LLVM_EXPORT_TEMPLATE void
57ApplyUpdates<MBBDomTree>(MBBDomTree &DT, MBBDomTreeGraphDiff &,
58 MBBDomTreeGraphDiff *);
59
60template LLVM_EXPORT_TEMPLATE bool
61Verify<MBBDomTree>(const MBBDomTree &DT, MBBDomTree::VerificationLevel VL);
62} // namespace DomTreeBuilder
63}
64
65bool 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
76AnalysisKey MachineDominatorTreeAnalysis::Key;
77
78MachineDominatorTreeAnalysis::Result
79MachineDominatorTreeAnalysis::run(MachineFunction &MF,
80 MachineFunctionAnalysisManager &) {
81 return MachineDominatorTree(MF);
82}
83
84PreservedAnalyses
85MachineDominatorTreePrinterPass::run(MachineFunction &MF,
86 MachineFunctionAnalysisManager &MFAM) {
87 OS << "MachineDominatorTree for machine function: " << MF.getName() << '\n';
88 MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF).print(O&: OS);
89 return PreservedAnalyses::all();
90}
91
92PreservedAnalyses
93MachineDominatorTreeVerifierPass::run(MachineFunction &MF,
94 MachineFunctionAnalysisManager &MFAM) {
95 auto &DT = MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
96 if (!DT.verify())
97 reportFatalInternalError(
98 reason: "verify<machine-dom-tree> detected an invalid dominator tree");
99 return PreservedAnalyses::all();
100}
101
102char MachineDominatorTreeWrapperPass::ID = 0;
103
104INITIALIZE_PASS(MachineDominatorTreeWrapperPass, "machinedomtree",
105 "MachineDominator Tree Construction", true, true)
106
107MachineDominatorTreeWrapperPass::MachineDominatorTreeWrapperPass()
108 : MachineFunctionPass(ID) {}
109
110char &llvm::MachineDominatorsID = MachineDominatorTreeWrapperPass::ID;
111
112bool MachineDominatorTreeWrapperPass::runOnMachineFunction(MachineFunction &F) {
113 if (F.empty()) {
114 assert(F.getProperties().hasFailedISel() &&
115 "Machine function should not be empty unless ISel failed.");
116 return false;
117 }
118
119 DT = MachineDominatorTree(F);
120 return false;
121}
122
123void MachineDominatorTreeWrapperPass::releaseMemory() { DT.reset(); }
124
125void MachineDominatorTreeWrapperPass::verifyAnalysis() const {
126 if (VerifyMachineDomInfo && DT)
127 if (!DT->verify(VL: MachineDominatorTree::VerificationLevel::Basic))
128 report_fatal_error(reason: "MachineDominatorTree verification failed!");
129}
130
131void MachineDominatorTreeWrapperPass::print(raw_ostream &OS,
132 const Module *) const {
133 if (DT)
134 DT->print(O&: OS);
135}
136