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 | |
22 | using namespace llvm; |
23 | |
24 | namespace llvm { |
25 | // Always verify dominfo if expensive checking is enabled. |
26 | #ifdef EXPENSIVE_CHECKS |
27 | bool VerifyMachineDomInfo = true; |
28 | #else |
29 | bool VerifyMachineDomInfo = false; |
30 | #endif |
31 | } // namespace llvm |
32 | |
33 | static cl::opt<bool, true> VerifyMachineDomInfoX( |
34 | "verify-machine-dom-info" , cl::location(L&: VerifyMachineDomInfo), cl::Hidden, |
35 | cl::desc("Verify machine dominator info (time consuming)" )); |
36 | |
37 | namespace llvm { |
38 | template class DomTreeNodeBase<MachineBasicBlock>; |
39 | template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase |
40 | } |
41 | |
42 | char MachineDominatorTree::ID = 0; |
43 | |
44 | INITIALIZE_PASS(MachineDominatorTree, "machinedomtree" , |
45 | "MachineDominator Tree Construction" , true, true) |
46 | |
47 | char &llvm::MachineDominatorsID = MachineDominatorTree::ID; |
48 | |
49 | void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const { |
50 | AU.setPreservesAll(); |
51 | MachineFunctionPass::getAnalysisUsage(AU); |
52 | } |
53 | |
54 | bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) { |
55 | calculate(F); |
56 | return false; |
57 | } |
58 | |
59 | void MachineDominatorTree::calculate(MachineFunction &F) { |
60 | CriticalEdgesToSplit.clear(); |
61 | NewBBs.clear(); |
62 | DT.reset(p: new DomTreeBase<MachineBasicBlock>()); |
63 | DT->recalculate(Func&: F); |
64 | } |
65 | |
66 | MachineDominatorTree::MachineDominatorTree() |
67 | : MachineFunctionPass(ID) { |
68 | initializeMachineDominatorTreePass(Registry&: *PassRegistry::getPassRegistry()); |
69 | } |
70 | |
71 | void MachineDominatorTree::releaseMemory() { |
72 | CriticalEdgesToSplit.clear(); |
73 | DT.reset(p: nullptr); |
74 | } |
75 | |
76 | void MachineDominatorTree::verifyAnalysis() const { |
77 | if (DT && VerifyMachineDomInfo) |
78 | if (!DT->verify(VL: MachineDomTree::VerificationLevel::Basic)) { |
79 | errs() << "MachineDominatorTree verification failed\n" ; |
80 | abort(); |
81 | } |
82 | } |
83 | |
84 | void MachineDominatorTree::print(raw_ostream &OS, const Module*) const { |
85 | if (DT) |
86 | DT->print(O&: OS); |
87 | } |
88 | |
89 | void MachineDominatorTree::applySplitCriticalEdges() const { |
90 | // Bail out early if there is nothing to do. |
91 | if (CriticalEdgesToSplit.empty()) |
92 | return; |
93 | |
94 | // For each element in CriticalEdgesToSplit, remember whether or not element |
95 | // is the new immediate domminator of its successor. The mapping is done by |
96 | // index, i.e., the information for the ith element of CriticalEdgesToSplit is |
97 | // the ith element of IsNewIDom. |
98 | SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true); |
99 | size_t Idx = 0; |
100 | |
101 | // Collect all the dominance properties info, before invalidating |
102 | // the underlying DT. |
103 | for (CriticalEdge &Edge : CriticalEdgesToSplit) { |
104 | // Update dominator information. |
105 | MachineBasicBlock *Succ = Edge.ToBB; |
106 | MachineDomTreeNode *SuccDTNode = DT->getNode(BB: Succ); |
107 | |
108 | for (MachineBasicBlock *PredBB : Succ->predecessors()) { |
109 | if (PredBB == Edge.NewBB) |
110 | continue; |
111 | // If we are in this situation: |
112 | // FromBB1 FromBB2 |
113 | // + + |
114 | // + + + + |
115 | // + + + + |
116 | // ... Split1 Split2 ... |
117 | // + + |
118 | // + + |
119 | // + |
120 | // Succ |
121 | // Instead of checking the domiance property with Split2, we check it with |
122 | // FromBB2 since Split2 is still unknown of the underlying DT structure. |
123 | if (NewBBs.count(Ptr: PredBB)) { |
124 | assert(PredBB->pred_size() == 1 && "A basic block resulting from a " |
125 | "critical edge split has more " |
126 | "than one predecessor!" ); |
127 | PredBB = *PredBB->pred_begin(); |
128 | } |
129 | if (!DT->dominates(A: SuccDTNode, B: DT->getNode(BB: PredBB))) { |
130 | IsNewIDom[Idx] = false; |
131 | break; |
132 | } |
133 | } |
134 | ++Idx; |
135 | } |
136 | |
137 | // Now, update DT with the collected dominance properties info. |
138 | Idx = 0; |
139 | for (CriticalEdge &Edge : CriticalEdgesToSplit) { |
140 | // We know FromBB dominates NewBB. |
141 | MachineDomTreeNode *NewDTNode = DT->addNewBlock(BB: Edge.NewBB, DomBB: Edge.FromBB); |
142 | |
143 | // If all the other predecessors of "Succ" are dominated by "Succ" itself |
144 | // then the new block is the new immediate dominator of "Succ". Otherwise, |
145 | // the new block doesn't dominate anything. |
146 | if (IsNewIDom[Idx]) |
147 | DT->changeImmediateDominator(N: DT->getNode(BB: Edge.ToBB), NewIDom: NewDTNode); |
148 | ++Idx; |
149 | } |
150 | NewBBs.clear(); |
151 | CriticalEdgesToSplit.clear(); |
152 | } |
153 | |