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