/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/MachineDominators.cpp
Line | Count | Source (jump to first uncovered line) |
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), |
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 | | |
44 | 204k | void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const { |
45 | 204k | AU.setPreservesAll(); |
46 | 204k | MachineFunctionPass::getAnalysisUsage(AU); |
47 | 204k | } |
48 | | |
49 | 3.66M | bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) { |
50 | 3.66M | CriticalEdgesToSplit.clear(); |
51 | 3.66M | NewBBs.clear(); |
52 | 3.66M | DT.reset(new DomTreeBase<MachineBasicBlock>()); |
53 | 3.66M | DT->recalculate(F); |
54 | 3.66M | return false; |
55 | 3.66M | } |
56 | | |
57 | | MachineDominatorTree::MachineDominatorTree() |
58 | 207k | : MachineFunctionPass(ID) { |
59 | 207k | initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); |
60 | 207k | } |
61 | | |
62 | 3.66M | void MachineDominatorTree::releaseMemory() { |
63 | 3.66M | CriticalEdgesToSplit.clear(); |
64 | 3.66M | DT.reset(nullptr); |
65 | 3.66M | } |
66 | | |
67 | 0 | void MachineDominatorTree::verifyAnalysis() const { |
68 | 0 | if (DT && 0 VerifyMachineDomInfo0 ) |
69 | 0 | verifyDomTree(); |
70 | 0 | } |
71 | | |
72 | 0 | void MachineDominatorTree::print(raw_ostream &OS, const Module*) const { |
73 | 0 | if (DT) |
74 | 0 | DT->print(OS); |
75 | 0 | } |
76 | | |
77 | 40.4M | void MachineDominatorTree::applySplitCriticalEdges() const { |
78 | 40.4M | // Bail out early if there is nothing to do. |
79 | 40.4M | if (CriticalEdgesToSplit.empty()) |
80 | 40.3M | return; |
81 | 146k | |
82 | 146k | // For each element in CriticalEdgesToSplit, remember whether or not element |
83 | 146k | // is the new immediate domminator of its successor. The mapping is done by |
84 | 146k | // index, i.e., the information for the ith element of CriticalEdgesToSplit is |
85 | 146k | // the ith element of IsNewIDom. |
86 | 146k | SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true); |
87 | 146k | size_t Idx = 0; |
88 | 146k | |
89 | 146k | // Collect all the dominance properties info, before invalidating |
90 | 146k | // the underlying DT. |
91 | 467k | for (CriticalEdge &Edge : CriticalEdgesToSplit) { |
92 | 467k | // Update dominator information. |
93 | 467k | MachineBasicBlock *Succ = Edge.ToBB; |
94 | 467k | MachineDomTreeNode *SuccDTNode = DT->getNode(Succ); |
95 | 467k | |
96 | 511k | for (MachineBasicBlock *PredBB : Succ->predecessors()) { |
97 | 511k | if (PredBB == Edge.NewBB) |
98 | 36.5k | continue; |
99 | 474k | // If we are in this situation: |
100 | 474k | // FromBB1 FromBB2 |
101 | 474k | // + + |
102 | 474k | // + + + + |
103 | 474k | // + + + + |
104 | 474k | // ... Split1 Split2 ... |
105 | 474k | // + + |
106 | 474k | // + + |
107 | 474k | // + |
108 | 474k | // Succ |
109 | 474k | // Instead of checking the domiance property with Split2, we check it with |
110 | 474k | // FromBB2 since Split2 is still unknown of the underlying DT structure. |
111 | 474k | if (474k NewBBs.count(PredBB)474k ) { |
112 | 36.9k | assert(PredBB->pred_size() == 1 && "A basic block resulting from a " |
113 | 36.9k | "critical edge split has more " |
114 | 36.9k | "than one predecessor!"); |
115 | 36.9k | PredBB = *PredBB->pred_begin(); |
116 | 36.9k | } |
117 | 474k | if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))474k ) { |
118 | 443k | IsNewIDom[Idx] = false; |
119 | 443k | break; |
120 | 443k | } |
121 | 467k | } |
122 | 467k | ++Idx; |
123 | 467k | } |
124 | 146k | |
125 | 146k | // Now, update DT with the collected dominance properties info. |
126 | 146k | Idx = 0; |
127 | 467k | for (CriticalEdge &Edge : CriticalEdgesToSplit) { |
128 | 467k | // We know FromBB dominates NewBB. |
129 | 467k | MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB); |
130 | 467k | |
131 | 467k | // If all the other predecessors of "Succ" are dominated by "Succ" itself |
132 | 467k | // then the new block is the new immediate dominator of "Succ". Otherwise, |
133 | 467k | // the new block doesn't dominate anything. |
134 | 467k | if (IsNewIDom[Idx]) |
135 | 23.9k | DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode); |
136 | 467k | ++Idx; |
137 | 467k | } |
138 | 40.4M | NewBBs.clear(); |
139 | 40.4M | CriticalEdgesToSplit.clear(); |
140 | 40.4M | } |
141 | | |
142 | 0 | void MachineDominatorTree::verifyDomTree() const { |
143 | 0 | if (!DT) |
144 | 0 | return; |
145 | 0 | MachineFunction &F = *getRoot()->getParent(); |
146 | 0 |
|
147 | 0 | DomTreeBase<MachineBasicBlock> OtherDT; |
148 | 0 | OtherDT.recalculate(F); |
149 | 0 | if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() || |
150 | 0 | DT->compare(OtherDT)0 ) { |
151 | 0 | errs() << "MachineDominatorTree is not up to date!\nComputed:\n"; |
152 | 0 | DT->print(errs()); |
153 | 0 | errs() << "\nActual:\n"; |
154 | 0 | OtherDT.print(errs()); |
155 | 0 | abort(); |
156 | 0 | } |
157 | 0 | } |