1 //===- MachineDominators.cpp - Machine Dominator Calculation --------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements simple dominator construction algorithms for finding
11 // forward dominators on machine functions.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "llvm/CodeGen/MachineDominators.h"
16 #include "llvm/ADT/SmallBitVector.h"
17 #include "llvm/CodeGen/Passes.h"
18 #include "llvm/Support/CommandLine.h"
19
20 using namespace llvm;
21
22 // Always verify dominfo if expensive checking is enabled.
23 #ifdef EXPENSIVE_CHECKS
24 static bool VerifyMachineDomInfo = true;
25 #else
26 static bool VerifyMachineDomInfo = false;
27 #endif
28 static cl::opt<bool, true> VerifyMachineDomInfoX(
29 "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
30 cl::desc("Verify machine dominator info (time consuming)"));
31
32 namespace llvm {
33 template class DomTreeNodeBase<MachineBasicBlock>;
34 template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
35 }
36
37 char MachineDominatorTree::ID = 0;
38
39 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
40 "MachineDominator Tree Construction", true, true)
41
42 char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
43
getAnalysisUsage(AnalysisUsage & AU) const44 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
45 AU.setPreservesAll();
46 MachineFunctionPass::getAnalysisUsage(AU);
47 }
48
runOnMachineFunction(MachineFunction & F)49 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
50 CriticalEdgesToSplit.clear();
51 NewBBs.clear();
52 DT.reset(new DomTreeBase<MachineBasicBlock>());
53 DT->recalculate(F);
54 return false;
55 }
56
MachineDominatorTree()57 MachineDominatorTree::MachineDominatorTree()
58 : MachineFunctionPass(ID) {
59 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
60 }
61
releaseMemory()62 void MachineDominatorTree::releaseMemory() {
63 CriticalEdgesToSplit.clear();
64 DT.reset(nullptr);
65 }
66
verifyAnalysis() const67 void MachineDominatorTree::verifyAnalysis() const {
68 if (DT && VerifyMachineDomInfo) {
69 MachineFunction &F = *getRoot()->getParent();
70
71 DomTreeBase<MachineBasicBlock> OtherDT;
72 OtherDT.recalculate(F);
73 if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() ||
74 DT->compare(OtherDT)) {
75 errs() << "MachineDominatorTree for function " << F.getName()
76 << " is not up to date!\nComputed:\n";
77 DT->print(errs());
78 errs() << "\nActual:\n";
79 OtherDT.print(errs());
80 abort();
81 }
82 }
83 }
84
print(raw_ostream & OS,const Module *) const85 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
86 if (DT)
87 DT->print(OS);
88 }
89
applySplitCriticalEdges() const90 void MachineDominatorTree::applySplitCriticalEdges() const {
91 // Bail out early if there is nothing to do.
92 if (CriticalEdgesToSplit.empty())
93 return;
94
95 // For each element in CriticalEdgesToSplit, remember whether or not element
96 // is the new immediate domminator of its successor. The mapping is done by
97 // index, i.e., the information for the ith element of CriticalEdgesToSplit is
98 // the ith element of IsNewIDom.
99 SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
100 size_t Idx = 0;
101
102 // Collect all the dominance properties info, before invalidating
103 // the underlying DT.
104 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
105 // Update dominator information.
106 MachineBasicBlock *Succ = Edge.ToBB;
107 MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
108
109 for (MachineBasicBlock *PredBB : Succ->predecessors()) {
110 if (PredBB == Edge.NewBB)
111 continue;
112 // If we are in this situation:
113 // FromBB1 FromBB2
114 // + +
115 // + + + +
116 // + + + +
117 // ... Split1 Split2 ...
118 // + +
119 // + +
120 // +
121 // Succ
122 // Instead of checking the domiance property with Split2, we check it with
123 // FromBB2 since Split2 is still unknown of the underlying DT structure.
124 if (NewBBs.count(PredBB)) {
125 assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
126 "critical edge split has more "
127 "than one predecessor!");
128 PredBB = *PredBB->pred_begin();
129 }
130 if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
131 IsNewIDom[Idx] = false;
132 break;
133 }
134 }
135 ++Idx;
136 }
137
138 // Now, update DT with the collected dominance properties info.
139 Idx = 0;
140 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
141 // We know FromBB dominates NewBB.
142 MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
143
144 // If all the other predecessors of "Succ" are dominated by "Succ" itself
145 // then the new block is the new immediate dominator of "Succ". Otherwise,
146 // the new block doesn't dominate anything.
147 if (IsNewIDom[Idx])
148 DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
149 ++Idx;
150 }
151 NewBBs.clear();
152 CriticalEdgesToSplit.clear();
153 }
154