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 DominatorTreeBase<MachineBasicBlock, true>; // PostDomTreeBase
22
23 namespace DomTreeBuilder {
24
25 template void Calculate<MBBPostDomTree>(MBBPostDomTree &DT);
26 template void InsertEdge<MBBPostDomTree>(MBBPostDomTree &DT,
27 MachineBasicBlock *From,
28 MachineBasicBlock *To);
29 template void DeleteEdge<MBBPostDomTree>(MBBPostDomTree &DT,
30 MachineBasicBlock *From,
31 MachineBasicBlock *To);
32 template void ApplyUpdates<MBBPostDomTree>(MBBPostDomTree &DT,
33 MBBPostDomTreeGraphDiff &,
34 MBBPostDomTreeGraphDiff *);
35 template bool Verify<MBBPostDomTree>(const MBBPostDomTree &DT,
36 MBBPostDomTree::VerificationLevel VL);
37
38 } // namespace DomTreeBuilder
39 extern bool VerifyMachineDomInfo;
40 } // namespace llvm
41
42 AnalysisKey MachinePostDominatorTreeAnalysis::Key;
43
44 MachinePostDominatorTreeAnalysis::Result
run(MachineFunction & MF,MachineFunctionAnalysisManager &)45 MachinePostDominatorTreeAnalysis::run(MachineFunction &MF,
46 MachineFunctionAnalysisManager &) {
47 return MachinePostDominatorTree(MF);
48 }
49
50 PreservedAnalyses
run(MachineFunction & MF,MachineFunctionAnalysisManager & MFAM)51 MachinePostDominatorTreePrinterPass::run(MachineFunction &MF,
52 MachineFunctionAnalysisManager &MFAM) {
53 OS << "MachinePostDominatorTree for machine function: " << MF.getName()
54 << '\n';
55 MFAM.getResult<MachinePostDominatorTreeAnalysis>(MF).print(OS);
56 return PreservedAnalyses::all();
57 }
58
59 char MachinePostDominatorTreeWrapperPass::ID = 0;
60
61 //declare initializeMachinePostDominatorTreePass
62 INITIALIZE_PASS(MachinePostDominatorTreeWrapperPass, "machinepostdomtree",
63 "MachinePostDominator Tree Construction", true, true)
64
MachinePostDominatorTreeWrapperPass()65 MachinePostDominatorTreeWrapperPass::MachinePostDominatorTreeWrapperPass()
66 : MachineFunctionPass(ID), PDT() {
67 initializeMachinePostDominatorTreeWrapperPassPass(
68 *PassRegistry::getPassRegistry());
69 }
70
runOnMachineFunction(MachineFunction & F)71 bool MachinePostDominatorTreeWrapperPass::runOnMachineFunction(
72 MachineFunction &F) {
73 PDT = MachinePostDominatorTree();
74 PDT->recalculate(F);
75 return false;
76 }
77
getAnalysisUsage(AnalysisUsage & AU) const78 void MachinePostDominatorTreeWrapperPass::getAnalysisUsage(
79 AnalysisUsage &AU) const {
80 AU.setPreservesAll();
81 MachineFunctionPass::getAnalysisUsage(AU);
82 }
83
invalidate(MachineFunction &,const PreservedAnalyses & PA,MachineFunctionAnalysisManager::Invalidator &)84 bool MachinePostDominatorTree::invalidate(
85 MachineFunction &, const PreservedAnalyses &PA,
86 MachineFunctionAnalysisManager::Invalidator &) {
87 // Check whether the analysis, all analyses on machine functions, or the
88 // machine function's CFG have been preserved.
89 auto PAC = PA.getChecker<MachinePostDominatorTreeAnalysis>();
90 return !PAC.preserved() &&
91 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&
92 !PAC.preservedSet<CFGAnalyses>();
93 }
94
findNearestCommonDominator(ArrayRef<MachineBasicBlock * > Blocks) const95 MachineBasicBlock *MachinePostDominatorTree::findNearestCommonDominator(
96 ArrayRef<MachineBasicBlock *> Blocks) const {
97 assert(!Blocks.empty());
98
99 MachineBasicBlock *NCD = Blocks.front();
100 for (MachineBasicBlock *BB : Blocks.drop_front()) {
101 NCD = Base::findNearestCommonDominator(NCD, BB);
102
103 // Stop when the root is reached.
104 if (isVirtualRoot(getNode(NCD)))
105 return nullptr;
106 }
107
108 return NCD;
109 }
110
verifyAnalysis() const111 void MachinePostDominatorTreeWrapperPass::verifyAnalysis() const {
112 if (VerifyMachineDomInfo && PDT &&
113 !PDT->verify(MachinePostDominatorTree::VerificationLevel::Basic))
114 report_fatal_error("MachinePostDominatorTree verification failed!");
115 }
116
print(llvm::raw_ostream & OS,const Module * M) const117 void MachinePostDominatorTreeWrapperPass::print(llvm::raw_ostream &OS,
118 const Module *M) const {
119 PDT->print(OS);
120 }
121