/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/Utils/LowerSwitch.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// |
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 | | // The LowerSwitch transformation rewrites switch instructions with a sequence |
11 | | // of branches, which allows targets to get away with not implementing the |
12 | | // switch instruction until it is convenient. |
13 | | // |
14 | | //===----------------------------------------------------------------------===// |
15 | | |
16 | | #include "llvm/ADT/STLExtras.h" |
17 | | #include "llvm/IR/CFG.h" |
18 | | #include "llvm/IR/Constants.h" |
19 | | #include "llvm/IR/Function.h" |
20 | | #include "llvm/IR/Instructions.h" |
21 | | #include "llvm/IR/LLVMContext.h" |
22 | | #include "llvm/Pass.h" |
23 | | #include "llvm/Support/Compiler.h" |
24 | | #include "llvm/Support/Debug.h" |
25 | | #include "llvm/Support/raw_ostream.h" |
26 | | #include "llvm/Transforms/Scalar.h" |
27 | | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
28 | | #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" |
29 | | #include <algorithm> |
30 | | using namespace llvm; |
31 | | |
32 | | #define DEBUG_TYPE "lower-switch" |
33 | | |
34 | | namespace { |
35 | | struct IntRange { |
36 | | int64_t Low, High; |
37 | | }; |
38 | | // Return true iff R is covered by Ranges. |
39 | | static bool IsInRanges(const IntRange &R, |
40 | 3 | const std::vector<IntRange> &Ranges) { |
41 | 3 | // Note: Ranges must be sorted, non-overlapping and non-adjacent. |
42 | 3 | |
43 | 3 | // Find the first range whose High field is >= R.High, |
44 | 3 | // then check if the Low field is <= R.Low. If so, we |
45 | 3 | // have a Range that covers R. |
46 | 3 | auto I = std::lower_bound( |
47 | 3 | Ranges.begin(), Ranges.end(), R, |
48 | 6 | [](const IntRange &A, const IntRange &B) { return A.High < B.High; }); |
49 | 3 | return I != Ranges.end() && I->Low <= R.Low; |
50 | 3 | } |
51 | | |
52 | | /// Replace all SwitchInst instructions with chained branch instructions. |
53 | | class LowerSwitch : public FunctionPass { |
54 | | public: |
55 | | static char ID; // Pass identification, replacement for typeid |
56 | 1.74k | LowerSwitch() : FunctionPass(ID) { |
57 | 1.74k | initializeLowerSwitchPass(*PassRegistry::getPassRegistry()); |
58 | 1.74k | } |
59 | | |
60 | | bool runOnFunction(Function &F) override; |
61 | | |
62 | | struct CaseRange { |
63 | | ConstantInt* Low; |
64 | | ConstantInt* High; |
65 | | BasicBlock* BB; |
66 | | |
67 | | CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb) |
68 | 102 | : Low(low), High(high), BB(bb) {} |
69 | | }; |
70 | | |
71 | | typedef std::vector<CaseRange> CaseVector; |
72 | | typedef std::vector<CaseRange>::iterator CaseItr; |
73 | | private: |
74 | | void processSwitchInst(SwitchInst *SI, SmallPtrSetImpl<BasicBlock*> &DeleteList); |
75 | | |
76 | | BasicBlock *switchConvert(CaseItr Begin, CaseItr End, |
77 | | ConstantInt *LowerBound, ConstantInt *UpperBound, |
78 | | Value *Val, BasicBlock *Predecessor, |
79 | | BasicBlock *OrigBlock, BasicBlock *Default, |
80 | | const std::vector<IntRange> &UnreachableRanges); |
81 | | BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, BasicBlock *OrigBlock, |
82 | | BasicBlock *Default); |
83 | | unsigned Clusterify(CaseVector &Cases, SwitchInst *SI); |
84 | | }; |
85 | | |
86 | | /// The comparison function for sorting the switch case values in the vector. |
87 | | /// WARNING: Case ranges should be disjoint! |
88 | | struct CaseCmp { |
89 | | bool operator () (const LowerSwitch::CaseRange& C1, |
90 | 93 | const LowerSwitch::CaseRange& C2) { |
91 | 93 | |
92 | 93 | const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); |
93 | 93 | const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); |
94 | 93 | return CI1->getValue().slt(CI2->getValue()); |
95 | 93 | } |
96 | | }; |
97 | | } |
98 | | |
99 | | char LowerSwitch::ID = 0; |
100 | | INITIALIZE_PASS(LowerSwitch, "lowerswitch", |
101 | | "Lower SwitchInst's to branches", false, false) |
102 | | |
103 | | // Publicly exposed interface to pass... |
104 | | char &llvm::LowerSwitchID = LowerSwitch::ID; |
105 | | // createLowerSwitchPass - Interface to this file... |
106 | 0 | FunctionPass *llvm::createLowerSwitchPass() { |
107 | 0 | return new LowerSwitch(); |
108 | 0 | } |
109 | | |
110 | 16.9k | bool LowerSwitch::runOnFunction(Function &F) { |
111 | 16.9k | bool Changed = false; |
112 | 16.9k | SmallPtrSet<BasicBlock*, 8> DeleteList; |
113 | 16.9k | |
114 | 36.2k | for (Function::iterator I = F.begin(), E = F.end(); I != E36.2k ; ) { |
115 | 19.2k | BasicBlock *Cur = &*I++; // Advance over block so we don't traverse new blocks |
116 | 19.2k | |
117 | 19.2k | // If the block is a dead Default block that will be deleted later, don't |
118 | 19.2k | // waste time processing it. |
119 | 19.2k | if (DeleteList.count(Cur)) |
120 | 4 | continue; |
121 | 19.2k | |
122 | 19.2k | if (SwitchInst *19.2k SI19.2k = dyn_cast<SwitchInst>(Cur->getTerminator())) { |
123 | 26 | Changed = true; |
124 | 26 | processSwitchInst(SI, DeleteList); |
125 | 26 | } |
126 | 19.2k | } |
127 | 16.9k | |
128 | 6 | for (BasicBlock* BB: DeleteList) { |
129 | 6 | DeleteDeadBlock(BB); |
130 | 6 | } |
131 | 16.9k | |
132 | 16.9k | return Changed; |
133 | 16.9k | } |
134 | | |
135 | | /// Used for debugging purposes. |
136 | | static raw_ostream& operator<<(raw_ostream &O, |
137 | | const LowerSwitch::CaseVector &C) |
138 | | LLVM_ATTRIBUTE_USED; |
139 | | static raw_ostream& operator<<(raw_ostream &O, |
140 | 0 | const LowerSwitch::CaseVector &C) { |
141 | 0 | O << "["; |
142 | 0 |
|
143 | 0 | for (LowerSwitch::CaseVector::const_iterator B = C.begin(), |
144 | 0 | E = C.end(); B != E0 ; ) { |
145 | 0 | O << *B->Low << " -" << *B->High; |
146 | 0 | if (++B != E0 ) O << ", "0 ; |
147 | 0 | } |
148 | 0 |
|
149 | 0 | return O << "]"; |
150 | 0 | } |
151 | | |
152 | | /// \brief Update the first occurrence of the "switch statement" BB in the PHI |
153 | | /// node with the "new" BB. The other occurrences will: |
154 | | /// |
155 | | /// 1) Be updated by subsequent calls to this function. Switch statements may |
156 | | /// have more than one outcoming edge into the same BB if they all have the same |
157 | | /// value. When the switch statement is converted these incoming edges are now |
158 | | /// coming from multiple BBs. |
159 | | /// 2) Removed if subsequent incoming values now share the same case, i.e., |
160 | | /// multiple outcome edges are condensed into one. This is necessary to keep the |
161 | | /// number of phi values equal to the number of branches to SuccBB. |
162 | | static void fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB, |
163 | 38 | unsigned NumMergedCases) { |
164 | 38 | for (BasicBlock::iterator I = SuccBB->begin(), |
165 | 38 | IE = SuccBB->getFirstNonPHI()->getIterator(); |
166 | 44 | I != IE44 ; ++I6 ) { |
167 | 6 | PHINode *PN = cast<PHINode>(I); |
168 | 6 | |
169 | 6 | // Only update the first occurrence. |
170 | 6 | unsigned Idx = 0, E = PN->getNumIncomingValues(); |
171 | 6 | unsigned LocalNumMergedCases = NumMergedCases; |
172 | 25 | for (; Idx != E25 ; ++Idx19 ) { |
173 | 25 | if (PN->getIncomingBlock(Idx) == OrigBB25 ) { |
174 | 6 | PN->setIncomingBlock(Idx, NewBB); |
175 | 6 | break; |
176 | 6 | } |
177 | 25 | } |
178 | 6 | |
179 | 6 | // Remove additional occurrences coming from condensed cases and keep the |
180 | 6 | // number of incoming values equal to the number of branches to SuccBB. |
181 | 6 | SmallVector<unsigned, 8> Indices; |
182 | 12 | for (++Idx; LocalNumMergedCases > 0 && 12 Idx < E6 ; ++Idx6 ) |
183 | 6 | if (6 PN->getIncomingBlock(Idx) == OrigBB6 ) { |
184 | 5 | Indices.push_back(Idx); |
185 | 5 | LocalNumMergedCases--; |
186 | 5 | } |
187 | 6 | // Remove incoming values in the reverse order to prevent invalidating |
188 | 6 | // *successive* index. |
189 | 6 | for (unsigned III : reverse(Indices)) |
190 | 5 | PN->removeIncomingValue(III); |
191 | 6 | } |
192 | 38 | } |
193 | | |
194 | | /// Convert the switch statement into a binary lookup of the case values. |
195 | | /// The function recursively builds this tree. LowerBound and UpperBound are |
196 | | /// used to keep track of the bounds for Val that have already been checked by |
197 | | /// a block emitted by one of the previous calls to switchConvert in the call |
198 | | /// stack. |
199 | | BasicBlock * |
200 | | LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound, |
201 | | ConstantInt *UpperBound, Value *Val, |
202 | | BasicBlock *Predecessor, BasicBlock *OrigBlock, |
203 | | BasicBlock *Default, |
204 | 129 | const std::vector<IntRange> &UnreachableRanges) { |
205 | 129 | unsigned Size = End - Begin; |
206 | 129 | |
207 | 129 | if (Size == 1129 ) { |
208 | 75 | // Check if the Case Range is perfectly squeezed in between |
209 | 75 | // already checked Upper and Lower bounds. If it is then we can avoid |
210 | 75 | // emitting the code that checks if the value actually falls in the range |
211 | 75 | // because the bounds already tell us so. |
212 | 75 | if (Begin->Low == LowerBound && 75 Begin->High == UpperBound57 ) { |
213 | 38 | unsigned NumMergedCases = 0; |
214 | 38 | if (LowerBound && 38 UpperBound38 ) |
215 | 38 | NumMergedCases = |
216 | 38 | UpperBound->getSExtValue() - LowerBound->getSExtValue(); |
217 | 38 | fixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases); |
218 | 38 | return Begin->BB; |
219 | 38 | } |
220 | 37 | return newLeafBlock(*Begin, Val, OrigBlock, Default); |
221 | 37 | } |
222 | 54 | |
223 | 54 | unsigned Mid = Size / 2; |
224 | 54 | std::vector<CaseRange> LHS(Begin, Begin + Mid); |
225 | 54 | DEBUG(dbgs() << "LHS: " << LHS << "\n"); |
226 | 54 | std::vector<CaseRange> RHS(Begin + Mid, End); |
227 | 54 | DEBUG(dbgs() << "RHS: " << RHS << "\n"); |
228 | 54 | |
229 | 54 | CaseRange &Pivot = *(Begin + Mid); |
230 | 54 | DEBUG(dbgs() << "Pivot ==> " |
231 | 54 | << Pivot.Low->getValue() |
232 | 54 | << " -" << Pivot.High->getValue() << "\n"); |
233 | 54 | |
234 | 54 | // NewLowerBound here should never be the integer minimal value. |
235 | 54 | // This is because it is computed from a case range that is never |
236 | 54 | // the smallest, so there is always a case range that has at least |
237 | 54 | // a smaller value. |
238 | 54 | ConstantInt *NewLowerBound = Pivot.Low; |
239 | 54 | |
240 | 54 | // Because NewLowerBound is never the smallest representable integer |
241 | 54 | // it is safe here to subtract one. |
242 | 54 | ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(), |
243 | 54 | NewLowerBound->getValue() - 1); |
244 | 54 | |
245 | 54 | if (!UnreachableRanges.empty()54 ) { |
246 | 4 | // Check if the gap between LHS's highest and NewLowerBound is unreachable. |
247 | 4 | int64_t GapLow = LHS.back().High->getSExtValue() + 1; |
248 | 4 | int64_t GapHigh = NewLowerBound->getSExtValue() - 1; |
249 | 4 | IntRange Gap = { GapLow, GapHigh }; |
250 | 4 | if (GapHigh >= GapLow && 4 IsInRanges(Gap, UnreachableRanges)3 ) |
251 | 2 | NewUpperBound = LHS.back().High; |
252 | 4 | } |
253 | 54 | |
254 | 54 | DEBUG(dbgs() << "LHS Bounds ==> "; |
255 | 129 | if (LowerBound) { |
256 | 129 | dbgs() << LowerBound->getSExtValue(); |
257 | 129 | } else { |
258 | 129 | dbgs() << "NONE"; |
259 | 129 | } |
260 | 129 | dbgs() << " - " << NewUpperBound->getSExtValue() << "\n"; |
261 | 129 | dbgs() << "RHS Bounds ==> "; |
262 | 129 | dbgs() << NewLowerBound->getSExtValue() << " - "; |
263 | 129 | if (UpperBound) { |
264 | 129 | dbgs() << UpperBound->getSExtValue() << "\n"; |
265 | 129 | } else { |
266 | 129 | dbgs() << "NONE\n"; |
267 | 129 | }); |
268 | 129 | |
269 | 129 | // Create a new node that checks if the value is < pivot. Go to the |
270 | 129 | // left branch if it is and right branch if not. |
271 | 129 | Function* F = OrigBlock->getParent(); |
272 | 129 | BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock"); |
273 | 129 | |
274 | 129 | ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, |
275 | 129 | Val, Pivot.Low, "Pivot"); |
276 | 129 | |
277 | 129 | BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound, |
278 | 129 | NewUpperBound, Val, NewNode, OrigBlock, |
279 | 129 | Default, UnreachableRanges); |
280 | 129 | BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound, |
281 | 129 | UpperBound, Val, NewNode, OrigBlock, |
282 | 129 | Default, UnreachableRanges); |
283 | 129 | |
284 | 129 | F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewNode); |
285 | 129 | NewNode->getInstList().push_back(Comp); |
286 | 129 | |
287 | 129 | BranchInst::Create(LBranch, RBranch, Comp, NewNode); |
288 | 129 | return NewNode; |
289 | 129 | } |
290 | | |
291 | | /// Create a new leaf block for the binary lookup tree. It checks if the |
292 | | /// switch's value == the case's value. If not, then it jumps to the default |
293 | | /// branch. At this point in the tree, the value can't be another valid case |
294 | | /// value, so the jump to the "default" branch is warranted. |
295 | | BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, |
296 | | BasicBlock* OrigBlock, |
297 | | BasicBlock* Default) |
298 | 37 | { |
299 | 37 | Function* F = OrigBlock->getParent(); |
300 | 37 | BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock"); |
301 | 37 | F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewLeaf); |
302 | 37 | |
303 | 37 | // Emit comparison |
304 | 37 | ICmpInst* Comp = nullptr; |
305 | 37 | if (Leaf.Low == Leaf.High37 ) { |
306 | 35 | // Make the seteq instruction... |
307 | 35 | Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, |
308 | 35 | Leaf.Low, "SwitchLeaf"); |
309 | 37 | } else { |
310 | 2 | // Make range comparison |
311 | 2 | if (Leaf.Low->isMinValue(true /*isSigned*/)2 ) { |
312 | 0 | // Val >= Min && Val <= Hi --> Val <= Hi |
313 | 0 | Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, |
314 | 0 | "SwitchLeaf"); |
315 | 2 | } else if (2 Leaf.Low->isZero()2 ) { |
316 | 0 | // Val >= 0 && Val <= Hi --> Val <=u Hi |
317 | 0 | Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, |
318 | 0 | "SwitchLeaf"); |
319 | 2 | } else { |
320 | 2 | // Emit V-Lo <=u Hi-Lo |
321 | 2 | Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); |
322 | 2 | Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, |
323 | 2 | Val->getName()+".off", |
324 | 2 | NewLeaf); |
325 | 2 | Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); |
326 | 2 | Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, |
327 | 2 | "SwitchLeaf"); |
328 | 2 | } |
329 | 2 | } |
330 | 37 | |
331 | 37 | // Make the conditional branch... |
332 | 37 | BasicBlock* Succ = Leaf.BB; |
333 | 37 | BranchInst::Create(Succ, Default, Comp, NewLeaf); |
334 | 37 | |
335 | 37 | // If there were any PHI nodes in this successor, rewrite one entry |
336 | 37 | // from OrigBlock to come from NewLeaf. |
337 | 43 | for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I)43 ; ++I6 ) { |
338 | 6 | PHINode* PN = cast<PHINode>(I); |
339 | 6 | // Remove all but one incoming entries from the cluster |
340 | 6 | uint64_t Range = Leaf.High->getSExtValue() - |
341 | 6 | Leaf.Low->getSExtValue(); |
342 | 6 | for (uint64_t j = 0; j < Range6 ; ++j0 ) { |
343 | 0 | PN->removeIncomingValue(OrigBlock); |
344 | 0 | } |
345 | 6 | |
346 | 6 | int BlockIdx = PN->getBasicBlockIndex(OrigBlock); |
347 | 6 | assert(BlockIdx != -1 && "Switch didn't go to this successor??"); |
348 | 6 | PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); |
349 | 6 | } |
350 | 37 | |
351 | 37 | return NewLeaf; |
352 | 37 | } |
353 | | |
354 | | /// Transform simple list of Cases into list of CaseRange's. |
355 | 22 | unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { |
356 | 22 | unsigned numCmps = 0; |
357 | 22 | |
358 | 22 | // Start with "simple" cases |
359 | 22 | for (auto Case : SI->cases()) |
360 | 102 | Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(), |
361 | 102 | Case.getCaseSuccessor())); |
362 | 22 | |
363 | 22 | std::sort(Cases.begin(), Cases.end(), CaseCmp()); |
364 | 22 | |
365 | 22 | // Merge case into clusters |
366 | 22 | if (Cases.size() >= 222 ) { |
367 | 20 | CaseItr I = Cases.begin(); |
368 | 100 | for (CaseItr J = std::next(I), E = Cases.end(); J != E100 ; ++J80 ) { |
369 | 80 | int64_t nextValue = J->Low->getSExtValue(); |
370 | 80 | int64_t currentValue = I->High->getSExtValue(); |
371 | 80 | BasicBlock* nextBB = J->BB; |
372 | 80 | BasicBlock* currentBB = I->BB; |
373 | 80 | |
374 | 80 | // If the two neighboring cases go to the same destination, merge them |
375 | 80 | // into a single case. |
376 | 80 | assert(nextValue > currentValue && "Cases should be strictly ascending"); |
377 | 80 | if ((nextValue == currentValue + 1) && 80 (currentBB == nextBB)64 ) { |
378 | 16 | I->High = J->High; |
379 | 16 | // FIXME: Combine branch weights. |
380 | 80 | } else if (64 ++I != J64 ) { |
381 | 19 | *I = *J; |
382 | 19 | } |
383 | 80 | } |
384 | 20 | Cases.erase(std::next(I), Cases.end()); |
385 | 20 | } |
386 | 22 | |
387 | 108 | for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E108 ; ++I, ++numCmps86 ) { |
388 | 86 | if (I->Low != I->High) |
389 | 86 | // A range counts double, since it requires two compares. |
390 | 5 | ++numCmps; |
391 | 86 | } |
392 | 22 | |
393 | 22 | return numCmps; |
394 | 22 | } |
395 | | |
396 | | /// Replace the specified switch instruction with a sequence of chained if-then |
397 | | /// insts in a balanced binary search. |
398 | | void LowerSwitch::processSwitchInst(SwitchInst *SI, |
399 | 26 | SmallPtrSetImpl<BasicBlock*> &DeleteList) { |
400 | 26 | BasicBlock *CurBlock = SI->getParent(); |
401 | 26 | BasicBlock *OrigBlock = CurBlock; |
402 | 26 | Function *F = CurBlock->getParent(); |
403 | 26 | Value *Val = SI->getCondition(); // The value we are switching on... |
404 | 26 | BasicBlock* Default = SI->getDefaultDest(); |
405 | 26 | |
406 | 26 | // Don't handle unreachable blocks. If there are successors with phis, this |
407 | 26 | // would leave them behind with missing predecessors. |
408 | 26 | if ((CurBlock != &F->getEntryBlock() && 26 pred_empty(CurBlock)8 ) || |
409 | 26 | CurBlock->getSinglePredecessor() == CurBlock25 ) { |
410 | 2 | DeleteList.insert(CurBlock); |
411 | 2 | return; |
412 | 2 | } |
413 | 24 | |
414 | 24 | // If there is only the default destination, just branch. |
415 | 24 | if (24 !SI->getNumCases()24 ) { |
416 | 2 | BranchInst::Create(Default, CurBlock); |
417 | 2 | SI->eraseFromParent(); |
418 | 2 | return; |
419 | 2 | } |
420 | 22 | |
421 | 22 | // Prepare cases vector. |
422 | 22 | CaseVector Cases; |
423 | 22 | unsigned numCmps = Clusterify(Cases, SI); |
424 | 22 | DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() |
425 | 22 | << ". Total compares: " << numCmps << "\n"); |
426 | 22 | DEBUG(dbgs() << "Cases: " << Cases << "\n"); |
427 | 22 | (void)numCmps; |
428 | 22 | |
429 | 22 | ConstantInt *LowerBound = nullptr; |
430 | 22 | ConstantInt *UpperBound = nullptr; |
431 | 22 | std::vector<IntRange> UnreachableRanges; |
432 | 22 | |
433 | 22 | if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())22 ) { |
434 | 5 | // Make the bounds tightly fitted around the case value range, because we |
435 | 5 | // know that the value passed to the switch must be exactly one of the case |
436 | 5 | // values. |
437 | 5 | assert(!Cases.empty()); |
438 | 5 | LowerBound = Cases.front().Low; |
439 | 5 | UpperBound = Cases.back().High; |
440 | 5 | |
441 | 5 | DenseMap<BasicBlock *, unsigned> Popularity; |
442 | 5 | unsigned MaxPop = 0; |
443 | 5 | BasicBlock *PopSucc = nullptr; |
444 | 5 | |
445 | 5 | IntRange R = { INT64_MIN, INT64_MAX }; |
446 | 5 | UnreachableRanges.push_back(R); |
447 | 19 | for (const auto &I : Cases) { |
448 | 19 | int64_t Low = I.Low->getSExtValue(); |
449 | 19 | int64_t High = I.High->getSExtValue(); |
450 | 19 | |
451 | 19 | IntRange &LastRange = UnreachableRanges.back(); |
452 | 19 | if (LastRange.Low == Low19 ) { |
453 | 6 | // There is nothing left of the previous range. |
454 | 6 | UnreachableRanges.pop_back(); |
455 | 19 | } else { |
456 | 13 | // Terminate the previous range. |
457 | 13 | assert(Low > LastRange.Low); |
458 | 13 | LastRange.High = Low - 1; |
459 | 13 | } |
460 | 19 | if (High != INT64_MAX19 ) { |
461 | 18 | IntRange R = { High + 1, INT64_MAX }; |
462 | 18 | UnreachableRanges.push_back(R); |
463 | 18 | } |
464 | 19 | |
465 | 19 | // Count popularity. |
466 | 19 | int64_t N = High - Low + 1; |
467 | 19 | unsigned &Pop = Popularity[I.BB]; |
468 | 19 | if ((Pop += N) > MaxPop19 ) { |
469 | 9 | MaxPop = Pop; |
470 | 9 | PopSucc = I.BB; |
471 | 9 | } |
472 | 19 | } |
473 | | #ifndef NDEBUG |
474 | | /* UnreachableRanges should be sorted and the ranges non-adjacent. */ |
475 | | for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end(); |
476 | | I != E; ++I) { |
477 | | assert(I->Low <= I->High); |
478 | | auto Next = I + 1; |
479 | | if (Next != E) { |
480 | | assert(Next->Low > I->High); |
481 | | } |
482 | | } |
483 | | #endif |
484 | | |
485 | 5 | // Use the most popular block as the new default, reducing the number of |
486 | 5 | // cases. |
487 | 5 | assert(MaxPop > 0 && PopSucc); |
488 | 5 | Default = PopSucc; |
489 | 5 | Cases.erase( |
490 | 5 | remove_if(Cases, |
491 | 19 | [PopSucc](const CaseRange &R) { return R.BB == PopSucc; }), |
492 | 5 | Cases.end()); |
493 | 5 | |
494 | 5 | // If there are no cases left, just branch. |
495 | 5 | if (Cases.empty()5 ) { |
496 | 1 | BranchInst::Create(Default, CurBlock); |
497 | 1 | SI->eraseFromParent(); |
498 | 1 | return; |
499 | 1 | } |
500 | 21 | } |
501 | 21 | |
502 | 21 | // Create a new, empty default block so that the new hierarchy of |
503 | 21 | // if-then statements go to this and the PHI nodes are happy. |
504 | 21 | BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); |
505 | 21 | F->getBasicBlockList().insert(Default->getIterator(), NewDefault); |
506 | 21 | BranchInst::Create(Default, NewDefault); |
507 | 21 | |
508 | 21 | // If there is an entry in any PHI nodes for the default edge, make sure |
509 | 21 | // to update them as well. |
510 | 24 | for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I)24 ; ++I3 ) { |
511 | 3 | PHINode *PN = cast<PHINode>(I); |
512 | 3 | int BlockIdx = PN->getBasicBlockIndex(OrigBlock); |
513 | 3 | assert(BlockIdx != -1 && "Switch didn't go to this successor??"); |
514 | 3 | PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); |
515 | 3 | } |
516 | 21 | |
517 | 21 | BasicBlock *SwitchBlock = |
518 | 21 | switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val, |
519 | 21 | OrigBlock, OrigBlock, NewDefault, UnreachableRanges); |
520 | 21 | |
521 | 21 | // Branch to our shiny new if-then stuff... |
522 | 21 | BranchInst::Create(SwitchBlock, OrigBlock); |
523 | 21 | |
524 | 21 | // We are now done with the switch instruction, delete it. |
525 | 21 | BasicBlock *OldDefault = SI->getDefaultDest(); |
526 | 21 | CurBlock->getInstList().erase(SI); |
527 | 21 | |
528 | 21 | // If the Default block has no more predecessors just add it to DeleteList. |
529 | 21 | if (pred_begin(OldDefault) == pred_end(OldDefault)) |
530 | 4 | DeleteList.insert(OldDefault); |
531 | 26 | } |