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