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
18using namespace llvm;
19
20namespace llvm {
21template class LLVM_EXPORT_TEMPLATE
22 DominatorTreeBase<MachineBasicBlock, true>; // PostDomTreeBase
23
24namespace DomTreeBuilder {
25
26template LLVM_EXPORT_TEMPLATE void
27Calculate<MBBPostDomTree>(MBBPostDomTree &DT);
28template LLVM_EXPORT_TEMPLATE void
29InsertEdge<MBBPostDomTree>(MBBPostDomTree &DT, MachineBasicBlock *From,
30 MachineBasicBlock *To);
31template LLVM_EXPORT_TEMPLATE void
32DeleteEdge<MBBPostDomTree>(MBBPostDomTree &DT, MachineBasicBlock *From,
33 MachineBasicBlock *To);
34template LLVM_EXPORT_TEMPLATE void
35ApplyUpdates<MBBPostDomTree>(MBBPostDomTree &DT, MBBPostDomTreeGraphDiff &,
36 MBBPostDomTreeGraphDiff *);
37template LLVM_EXPORT_TEMPLATE bool
38Verify<MBBPostDomTree>(const MBBPostDomTree &DT,
39 MBBPostDomTree::VerificationLevel VL);
40
41} // namespace DomTreeBuilder
42extern bool VerifyMachineDomInfo;
43} // namespace llvm
44
45AnalysisKey MachinePostDominatorTreeAnalysis::Key;
46
47MachinePostDominatorTreeAnalysis::Result
48MachinePostDominatorTreeAnalysis::run(MachineFunction &MF,
49 MachineFunctionAnalysisManager &) {
50 return MachinePostDominatorTree(MF);
51}
52
53PreservedAnalyses
54MachinePostDominatorTreePrinterPass::run(MachineFunction &MF,
55 MachineFunctionAnalysisManager &MFAM) {
56 OS << "MachinePostDominatorTree for machine function: " << MF.getName()
57 << '\n';
58 MFAM.getResult<MachinePostDominatorTreeAnalysis>(IR&: MF).print(O&: OS);
59 return PreservedAnalyses::all();
60}
61
62char MachinePostDominatorTreeWrapperPass::ID = 0;
63
64//declare initializeMachinePostDominatorTreePass
65INITIALIZE_PASS(MachinePostDominatorTreeWrapperPass, "machinepostdomtree",
66 "MachinePostDominator Tree Construction", true, true)
67
68MachinePostDominatorTreeWrapperPass::MachinePostDominatorTreeWrapperPass()
69 : MachineFunctionPass(ID), PDT() {
70 initializeMachinePostDominatorTreeWrapperPassPass(
71 Registry&: *PassRegistry::getPassRegistry());
72}
73
74bool MachinePostDominatorTreeWrapperPass::runOnMachineFunction(
75 MachineFunction &F) {
76 PDT = MachinePostDominatorTree();
77 PDT->recalculate(Func&: F);
78 return false;
79}
80
81void MachinePostDominatorTreeWrapperPass::getAnalysisUsage(
82 AnalysisUsage &AU) const {
83 AU.setPreservesAll();
84 MachineFunctionPass::getAnalysisUsage(AU);
85}
86
87bool 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
98MachineBasicBlock *MachinePostDominatorTree::findNearestCommonDominator(
99 ArrayRef<MachineBasicBlock *> Blocks) const {
100 assert(!Blocks.empty());
101
102 MachineBasicBlock *NCD = Blocks.front();
103 for (MachineBasicBlock *BB : Blocks.drop_front()) {
104 NCD = Base::findNearestCommonDominator(A: NCD, B: BB);
105
106 // Stop when the root is reached.
107 if (isVirtualRoot(A: getNode(BB: NCD)))
108 return nullptr;
109 }
110
111 return NCD;
112}
113
114void MachinePostDominatorTreeWrapperPass::verifyAnalysis() const {
115 if (VerifyMachineDomInfo && PDT &&
116 !PDT->verify(VL: MachinePostDominatorTree::VerificationLevel::Basic))
117 report_fatal_error(reason: "MachinePostDominatorTree verification failed!");
118}
119
120void MachinePostDominatorTreeWrapperPass::print(llvm::raw_ostream &OS,
121 const Module *M) const {
122 PDT->print(O&: OS);
123}
124