1//===- MachineDominators.cpp - Machine 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// forward dominators on machine functions.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/CodeGen/MachineDominators.h"
15#include "llvm/ADT/SmallBitVector.h"
16#include "llvm/CodeGen/Passes.h"
17#include "llvm/InitializePasses.h"
18#include "llvm/Pass.h"
19#include "llvm/PassRegistry.h"
20#include "llvm/Support/CommandLine.h"
21#include "llvm/Support/GenericDomTreeConstruction.h"
22
23using namespace llvm;
24
25namespace llvm {
26// Always verify dominfo if expensive checking is enabled.
27#ifdef EXPENSIVE_CHECKS
28bool VerifyMachineDomInfo = true;
29#else
30bool VerifyMachineDomInfo = false;
31#endif
32} // namespace llvm
33
34static cl::opt<bool, true> VerifyMachineDomInfoX(
35 "verify-machine-dom-info", cl::location(L&: VerifyMachineDomInfo), cl::Hidden,
36 cl::desc("Verify machine dominator info (time consuming)"));
37
38namespace llvm {
39template class DomTreeNodeBase<MachineBasicBlock>;
40template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
41
42namespace DomTreeBuilder {
43template void Calculate<MBBDomTree>(MBBDomTree &DT);
44template void CalculateWithUpdates<MBBDomTree>(MBBDomTree &DT, MBBUpdates U);
45
46template void InsertEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From,
47 MachineBasicBlock *To);
48
49template void DeleteEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From,
50 MachineBasicBlock *To);
51
52template void ApplyUpdates<MBBDomTree>(MBBDomTree &DT, MBBDomTreeGraphDiff &,
53 MBBDomTreeGraphDiff *);
54
55template bool Verify<MBBDomTree>(const MBBDomTree &DT,
56 MBBDomTree::VerificationLevel VL);
57} // namespace DomTreeBuilder
58}
59
60bool MachineDominatorTree::invalidate(
61 MachineFunction &, const PreservedAnalyses &PA,
62 MachineFunctionAnalysisManager::Invalidator &) {
63 // Check whether the analysis, all analyses on machine functions, or the
64 // machine function's CFG have been preserved.
65 auto PAC = PA.getChecker<MachineDominatorTreeAnalysis>();
66 return !PAC.preserved() &&
67 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&
68 !PAC.preservedSet<CFGAnalyses>();
69}
70
71AnalysisKey MachineDominatorTreeAnalysis::Key;
72
73MachineDominatorTreeAnalysis::Result
74MachineDominatorTreeAnalysis::run(MachineFunction &MF,
75 MachineFunctionAnalysisManager &) {
76 return MachineDominatorTree(MF);
77}
78
79PreservedAnalyses
80MachineDominatorTreePrinterPass::run(MachineFunction &MF,
81 MachineFunctionAnalysisManager &MFAM) {
82 OS << "MachineDominatorTree for machine function: " << MF.getName() << '\n';
83 MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF).print(O&: OS);
84 return PreservedAnalyses::all();
85}
86
87char MachineDominatorTreeWrapperPass::ID = 0;
88
89INITIALIZE_PASS(MachineDominatorTreeWrapperPass, "machinedomtree",
90 "MachineDominator Tree Construction", true, true)
91
92MachineDominatorTreeWrapperPass::MachineDominatorTreeWrapperPass()
93 : MachineFunctionPass(ID) {
94 initializeMachineDominatorTreeWrapperPassPass(
95 Registry&: *PassRegistry::getPassRegistry());
96}
97
98void MachineDominatorTree::calculate(MachineFunction &F) {
99 CriticalEdgesToSplit.clear();
100 NewBBs.clear();
101 recalculate(Func&: F);
102}
103
104char &llvm::MachineDominatorsID = MachineDominatorTreeWrapperPass::ID;
105
106bool MachineDominatorTreeWrapperPass::runOnMachineFunction(MachineFunction &F) {
107 DT = MachineDominatorTree(F);
108 return false;
109}
110
111void MachineDominatorTreeWrapperPass::releaseMemory() { DT.reset(); }
112
113void MachineDominatorTreeWrapperPass::verifyAnalysis() const {
114 if (VerifyMachineDomInfo && DT)
115 if (!DT->verify(VL: MachineDominatorTree::VerificationLevel::Basic))
116 report_fatal_error(reason: "MachineDominatorTree verification failed!");
117}
118
119void MachineDominatorTreeWrapperPass::print(raw_ostream &OS,
120 const Module *) const {
121 if (DT)
122 DT->print(O&: OS);
123}
124
125void MachineDominatorTree::applySplitCriticalEdges() const {
126 // Bail out early if there is nothing to do.
127 if (CriticalEdgesToSplit.empty())
128 return;
129
130 // For each element in CriticalEdgesToSplit, remember whether or not element
131 // is the new immediate domminator of its successor. The mapping is done by
132 // index, i.e., the information for the ith element of CriticalEdgesToSplit is
133 // the ith element of IsNewIDom.
134 SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
135 size_t Idx = 0;
136
137 // Collect all the dominance properties info, before invalidating
138 // the underlying DT.
139 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
140 // Update dominator information.
141 MachineBasicBlock *Succ = Edge.ToBB;
142 MachineDomTreeNode *SuccDTNode = Base::getNode(BB: Succ);
143
144 for (MachineBasicBlock *PredBB : Succ->predecessors()) {
145 if (PredBB == Edge.NewBB)
146 continue;
147 // If we are in this situation:
148 // FromBB1 FromBB2
149 // + +
150 // + + + +
151 // + + + +
152 // ... Split1 Split2 ...
153 // + +
154 // + +
155 // +
156 // Succ
157 // Instead of checking the domiance property with Split2, we check it with
158 // FromBB2 since Split2 is still unknown of the underlying DT structure.
159 if (NewBBs.count(Ptr: PredBB)) {
160 assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
161 "critical edge split has more "
162 "than one predecessor!");
163 PredBB = *PredBB->pred_begin();
164 }
165 if (!Base::dominates(A: SuccDTNode, B: Base::getNode(BB: PredBB))) {
166 IsNewIDom[Idx] = false;
167 break;
168 }
169 }
170 ++Idx;
171 }
172
173 // Now, update DT with the collected dominance properties info.
174 Idx = 0;
175 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
176 // We know FromBB dominates NewBB.
177 MachineDomTreeNode *NewDTNode =
178 const_cast<MachineDominatorTree *>(this)->Base::addNewBlock(
179 BB: Edge.NewBB, DomBB: Edge.FromBB);
180
181 // If all the other predecessors of "Succ" are dominated by "Succ" itself
182 // then the new block is the new immediate dominator of "Succ". Otherwise,
183 // the new block doesn't dominate anything.
184 if (IsNewIDom[Idx])
185 const_cast<MachineDominatorTree *>(this)->Base::changeImmediateDominator(
186 N: Base::getNode(BB: Edge.ToBB), NewIDom: NewDTNode);
187 ++Idx;
188 }
189 NewBBs.clear();
190 CriticalEdgesToSplit.clear();
191}
192