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
run(MachineFunction & MF,MachineFunctionAnalysisManager &)48 MachinePostDominatorTreeAnalysis::run(MachineFunction &MF,
49 MachineFunctionAnalysisManager &) {
50 return MachinePostDominatorTree(MF);
51 }
52
53 PreservedAnalyses
run(MachineFunction & MF,MachineFunctionAnalysisManager & MFAM)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
MachinePostDominatorTreeWrapperPass()68 MachinePostDominatorTreeWrapperPass::MachinePostDominatorTreeWrapperPass()
69 : MachineFunctionPass(ID), PDT() {
70 initializeMachinePostDominatorTreeWrapperPassPass(
71 *PassRegistry::getPassRegistry());
72 }
73
runOnMachineFunction(MachineFunction & F)74 bool MachinePostDominatorTreeWrapperPass::runOnMachineFunction(
75 MachineFunction &F) {
76 PDT = MachinePostDominatorTree();
77 PDT->recalculate(F);
78 return false;
79 }
80
getAnalysisUsage(AnalysisUsage & AU) const81 void MachinePostDominatorTreeWrapperPass::getAnalysisUsage(
82 AnalysisUsage &AU) const {
83 AU.setPreservesAll();
84 MachineFunctionPass::getAnalysisUsage(AU);
85 }
86
invalidate(MachineFunction &,const PreservedAnalyses & PA,MachineFunctionAnalysisManager::Invalidator &)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
findNearestCommonDominator(ArrayRef<MachineBasicBlock * > Blocks) const98 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
verifyAnalysis() const114 void MachinePostDominatorTreeWrapperPass::verifyAnalysis() const {
115 if (VerifyMachineDomInfo && PDT &&
116 !PDT->verify(MachinePostDominatorTree::VerificationLevel::Basic))
117 report_fatal_error("MachinePostDominatorTree verification failed!");
118 }
119
print(llvm::raw_ostream & OS,const Module * M) const120 void MachinePostDominatorTreeWrapperPass::print(llvm::raw_ostream &OS,
121 const Module *M) const {
122 PDT->print(OS);
123 }
124