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
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.consume_front();
100 for (MachineBasicBlock *BB : Blocks) {
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