1 //===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===//
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 // The LowerSwitch transformation rewrites switch instructions with a sequence
10 // of branches, which allows targets to get away with not implementing the
11 // switch instruction until it is convenient.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/Analysis/AssumptionCache.h"
20 #include "llvm/Analysis/LazyValueInfo.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/ConstantRange.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/Function.h"
27 #include "llvm/IR/InstrTypes.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/Value.h"
30 #include "llvm/InitializePasses.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Support/Casting.h"
33 #include "llvm/Support/Compiler.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/KnownBits.h"
36 #include "llvm/Support/raw_ostream.h"
37 #include "llvm/Transforms/Utils.h"
38 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
39 #include <algorithm>
40 #include <cassert>
41 #include <cstdint>
42 #include <iterator>
43 #include <limits>
44 #include <vector>
45
46 using namespace llvm;
47
48 #define DEBUG_TYPE "lower-switch"
49
50 namespace {
51
52 struct IntRange {
53 int64_t Low, High;
54 };
55
56 } // end anonymous namespace
57
58 // Return true iff R is covered by Ranges.
IsInRanges(const IntRange & R,const std::vector<IntRange> & Ranges)59 static bool IsInRanges(const IntRange &R,
60 const std::vector<IntRange> &Ranges) {
61 // Note: Ranges must be sorted, non-overlapping and non-adjacent.
62
63 // Find the first range whose High field is >= R.High,
64 // then check if the Low field is <= R.Low. If so, we
65 // have a Range that covers R.
66 auto I = llvm::lower_bound(
67 Ranges, R, [](IntRange A, IntRange B) { return A.High < B.High; });
68 return I != Ranges.end() && I->Low <= R.Low;
69 }
70
71 namespace {
72
73 /// Replace all SwitchInst instructions with chained branch instructions.
74 class LowerSwitch : public FunctionPass {
75 public:
76 // Pass identification, replacement for typeid
77 static char ID;
78
LowerSwitch()79 LowerSwitch() : FunctionPass(ID) {
80 initializeLowerSwitchPass(*PassRegistry::getPassRegistry());
81 }
82
83 bool runOnFunction(Function &F) override;
84
getAnalysisUsage(AnalysisUsage & AU) const85 void getAnalysisUsage(AnalysisUsage &AU) const override {
86 AU.addRequired<LazyValueInfoWrapperPass>();
87 }
88
89 struct CaseRange {
90 ConstantInt* Low;
91 ConstantInt* High;
92 BasicBlock* BB;
93
CaseRange__anonbf4418110311::LowerSwitch::CaseRange94 CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb)
95 : Low(low), High(high), BB(bb) {}
96 };
97
98 using CaseVector = std::vector<CaseRange>;
99 using CaseItr = std::vector<CaseRange>::iterator;
100
101 private:
102 void processSwitchInst(SwitchInst *SI,
103 SmallPtrSetImpl<BasicBlock *> &DeleteList,
104 AssumptionCache *AC, LazyValueInfo *LVI);
105
106 BasicBlock *switchConvert(CaseItr Begin, CaseItr End,
107 ConstantInt *LowerBound, ConstantInt *UpperBound,
108 Value *Val, BasicBlock *Predecessor,
109 BasicBlock *OrigBlock, BasicBlock *Default,
110 const std::vector<IntRange> &UnreachableRanges);
111 BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val,
112 ConstantInt *LowerBound, ConstantInt *UpperBound,
113 BasicBlock *OrigBlock, BasicBlock *Default);
114 unsigned Clusterify(CaseVector &Cases, SwitchInst *SI);
115 };
116
117 /// The comparison function for sorting the switch case values in the vector.
118 /// WARNING: Case ranges should be disjoint!
119 struct CaseCmp {
operator ()__anonbf4418110311::CaseCmp120 bool operator()(const LowerSwitch::CaseRange& C1,
121 const LowerSwitch::CaseRange& C2) {
122 const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low);
123 const ConstantInt* CI2 = cast<const ConstantInt>(C2.High);
124 return CI1->getValue().slt(CI2->getValue());
125 }
126 };
127
128 } // end anonymous namespace
129
130 char LowerSwitch::ID = 0;
131
132 // Publicly exposed interface to pass...
133 char &llvm::LowerSwitchID = LowerSwitch::ID;
134
135 INITIALIZE_PASS_BEGIN(LowerSwitch, "lowerswitch",
136 "Lower SwitchInst's to branches", false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)137 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
138 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
139 INITIALIZE_PASS_END(LowerSwitch, "lowerswitch",
140 "Lower SwitchInst's to branches", false, false)
141
142 // createLowerSwitchPass - Interface to this file...
143 FunctionPass *llvm::createLowerSwitchPass() {
144 return new LowerSwitch();
145 }
146
runOnFunction(Function & F)147 bool LowerSwitch::runOnFunction(Function &F) {
148 LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
149 auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>();
150 AssumptionCache *AC = ACT ? &ACT->getAssumptionCache(F) : nullptr;
151
152 bool Changed = false;
153 SmallPtrSet<BasicBlock*, 8> DeleteList;
154
155 for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
156 BasicBlock *Cur = &*I++; // Advance over block so we don't traverse new blocks
157
158 // If the block is a dead Default block that will be deleted later, don't
159 // waste time processing it.
160 if (DeleteList.count(Cur))
161 continue;
162
163 if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) {
164 Changed = true;
165 processSwitchInst(SI, DeleteList, AC, LVI);
166 }
167 }
168
169 for (BasicBlock* BB: DeleteList) {
170 LVI->eraseBlock(BB);
171 DeleteDeadBlock(BB);
172 }
173
174 return Changed;
175 }
176
177 /// Used for debugging purposes.
178 LLVM_ATTRIBUTE_USED
operator <<(raw_ostream & O,const LowerSwitch::CaseVector & C)179 static raw_ostream &operator<<(raw_ostream &O,
180 const LowerSwitch::CaseVector &C) {
181 O << "[";
182
183 for (LowerSwitch::CaseVector::const_iterator B = C.begin(), E = C.end();
184 B != E;) {
185 O << "[" << B->Low->getValue() << ", " << B->High->getValue() << "]";
186 if (++B != E)
187 O << ", ";
188 }
189
190 return O << "]";
191 }
192
193 /// Update the first occurrence of the "switch statement" BB in the PHI
194 /// node with the "new" BB. The other occurrences will:
195 ///
196 /// 1) Be updated by subsequent calls to this function. Switch statements may
197 /// have more than one outcoming edge into the same BB if they all have the same
198 /// value. When the switch statement is converted these incoming edges are now
199 /// coming from multiple BBs.
200 /// 2) Removed if subsequent incoming values now share the same case, i.e.,
201 /// multiple outcome edges are condensed into one. This is necessary to keep the
202 /// number of phi values equal to the number of branches to SuccBB.
203 static void
fixPhis(BasicBlock * SuccBB,BasicBlock * OrigBB,BasicBlock * NewBB,const unsigned NumMergedCases=std::numeric_limits<unsigned>::max ())204 fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB,
205 const unsigned NumMergedCases = std::numeric_limits<unsigned>::max()) {
206 for (BasicBlock::iterator I = SuccBB->begin(),
207 IE = SuccBB->getFirstNonPHI()->getIterator();
208 I != IE; ++I) {
209 PHINode *PN = cast<PHINode>(I);
210
211 // Only update the first occurrence.
212 unsigned Idx = 0, E = PN->getNumIncomingValues();
213 unsigned LocalNumMergedCases = NumMergedCases;
214 for (; Idx != E; ++Idx) {
215 if (PN->getIncomingBlock(Idx) == OrigBB) {
216 PN->setIncomingBlock(Idx, NewBB);
217 break;
218 }
219 }
220
221 // Remove additional occurrences coming from condensed cases and keep the
222 // number of incoming values equal to the number of branches to SuccBB.
223 SmallVector<unsigned, 8> Indices;
224 for (++Idx; LocalNumMergedCases > 0 && Idx < E; ++Idx)
225 if (PN->getIncomingBlock(Idx) == OrigBB) {
226 Indices.push_back(Idx);
227 LocalNumMergedCases--;
228 }
229 // Remove incoming values in the reverse order to prevent invalidating
230 // *successive* index.
231 for (unsigned III : llvm::reverse(Indices))
232 PN->removeIncomingValue(III);
233 }
234 }
235
236 /// Convert the switch statement into a binary lookup of the case values.
237 /// The function recursively builds this tree. LowerBound and UpperBound are
238 /// used to keep track of the bounds for Val that have already been checked by
239 /// a block emitted by one of the previous calls to switchConvert in the call
240 /// stack.
241 BasicBlock *
switchConvert(CaseItr Begin,CaseItr End,ConstantInt * LowerBound,ConstantInt * UpperBound,Value * Val,BasicBlock * Predecessor,BasicBlock * OrigBlock,BasicBlock * Default,const std::vector<IntRange> & UnreachableRanges)242 LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,
243 ConstantInt *UpperBound, Value *Val,
244 BasicBlock *Predecessor, BasicBlock *OrigBlock,
245 BasicBlock *Default,
246 const std::vector<IntRange> &UnreachableRanges) {
247 assert(LowerBound && UpperBound && "Bounds must be initialized");
248 unsigned Size = End - Begin;
249
250 if (Size == 1) {
251 // Check if the Case Range is perfectly squeezed in between
252 // already checked Upper and Lower bounds. If it is then we can avoid
253 // emitting the code that checks if the value actually falls in the range
254 // because the bounds already tell us so.
255 if (Begin->Low == LowerBound && Begin->High == UpperBound) {
256 unsigned NumMergedCases = 0;
257 NumMergedCases = UpperBound->getSExtValue() - LowerBound->getSExtValue();
258 fixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);
259 return Begin->BB;
260 }
261 return newLeafBlock(*Begin, Val, LowerBound, UpperBound, OrigBlock,
262 Default);
263 }
264
265 unsigned Mid = Size / 2;
266 std::vector<CaseRange> LHS(Begin, Begin + Mid);
267 LLVM_DEBUG(dbgs() << "LHS: " << LHS << "\n");
268 std::vector<CaseRange> RHS(Begin + Mid, End);
269 LLVM_DEBUG(dbgs() << "RHS: " << RHS << "\n");
270
271 CaseRange &Pivot = *(Begin + Mid);
272 LLVM_DEBUG(dbgs() << "Pivot ==> [" << Pivot.Low->getValue() << ", "
273 << Pivot.High->getValue() << "]\n");
274
275 // NewLowerBound here should never be the integer minimal value.
276 // This is because it is computed from a case range that is never
277 // the smallest, so there is always a case range that has at least
278 // a smaller value.
279 ConstantInt *NewLowerBound = Pivot.Low;
280
281 // Because NewLowerBound is never the smallest representable integer
282 // it is safe here to subtract one.
283 ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(),
284 NewLowerBound->getValue() - 1);
285
286 if (!UnreachableRanges.empty()) {
287 // Check if the gap between LHS's highest and NewLowerBound is unreachable.
288 int64_t GapLow = LHS.back().High->getSExtValue() + 1;
289 int64_t GapHigh = NewLowerBound->getSExtValue() - 1;
290 IntRange Gap = { GapLow, GapHigh };
291 if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges))
292 NewUpperBound = LHS.back().High;
293 }
294
295 LLVM_DEBUG(dbgs() << "LHS Bounds ==> [" << LowerBound->getSExtValue() << ", "
296 << NewUpperBound->getSExtValue() << "]\n"
297 << "RHS Bounds ==> [" << NewLowerBound->getSExtValue()
298 << ", " << UpperBound->getSExtValue() << "]\n");
299
300 // Create a new node that checks if the value is < pivot. Go to the
301 // left branch if it is and right branch if not.
302 Function* F = OrigBlock->getParent();
303 BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock");
304
305 ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT,
306 Val, Pivot.Low, "Pivot");
307
308 BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound,
309 NewUpperBound, Val, NewNode, OrigBlock,
310 Default, UnreachableRanges);
311 BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound,
312 UpperBound, Val, NewNode, OrigBlock,
313 Default, UnreachableRanges);
314
315 F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewNode);
316 NewNode->getInstList().push_back(Comp);
317
318 BranchInst::Create(LBranch, RBranch, Comp, NewNode);
319 return NewNode;
320 }
321
322 /// Create a new leaf block for the binary lookup tree. It checks if the
323 /// switch's value == the case's value. If not, then it jumps to the default
324 /// branch. At this point in the tree, the value can't be another valid case
325 /// value, so the jump to the "default" branch is warranted.
newLeafBlock(CaseRange & Leaf,Value * Val,ConstantInt * LowerBound,ConstantInt * UpperBound,BasicBlock * OrigBlock,BasicBlock * Default)326 BasicBlock *LowerSwitch::newLeafBlock(CaseRange &Leaf, Value *Val,
327 ConstantInt *LowerBound,
328 ConstantInt *UpperBound,
329 BasicBlock *OrigBlock,
330 BasicBlock *Default) {
331 Function* F = OrigBlock->getParent();
332 BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock");
333 F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewLeaf);
334
335 // Emit comparison
336 ICmpInst* Comp = nullptr;
337 if (Leaf.Low == Leaf.High) {
338 // Make the seteq instruction...
339 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val,
340 Leaf.Low, "SwitchLeaf");
341 } else {
342 // Make range comparison
343 if (Leaf.Low == LowerBound) {
344 // Val >= Min && Val <= Hi --> Val <= Hi
345 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High,
346 "SwitchLeaf");
347 } else if (Leaf.High == UpperBound) {
348 // Val <= Max && Val >= Lo --> Val >= Lo
349 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SGE, Val, Leaf.Low,
350 "SwitchLeaf");
351 } else if (Leaf.Low->isZero()) {
352 // Val >= 0 && Val <= Hi --> Val <=u Hi
353 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High,
354 "SwitchLeaf");
355 } else {
356 // Emit V-Lo <=u Hi-Lo
357 Constant* NegLo = ConstantExpr::getNeg(Leaf.Low);
358 Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo,
359 Val->getName()+".off",
360 NewLeaf);
361 Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High);
362 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound,
363 "SwitchLeaf");
364 }
365 }
366
367 // Make the conditional branch...
368 BasicBlock* Succ = Leaf.BB;
369 BranchInst::Create(Succ, Default, Comp, NewLeaf);
370
371 // If there were any PHI nodes in this successor, rewrite one entry
372 // from OrigBlock to come from NewLeaf.
373 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
374 PHINode* PN = cast<PHINode>(I);
375 // Remove all but one incoming entries from the cluster
376 uint64_t Range = Leaf.High->getSExtValue() -
377 Leaf.Low->getSExtValue();
378 for (uint64_t j = 0; j < Range; ++j) {
379 PN->removeIncomingValue(OrigBlock);
380 }
381
382 int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
383 assert(BlockIdx != -1 && "Switch didn't go to this successor??");
384 PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf);
385 }
386
387 return NewLeaf;
388 }
389
390 /// Transform simple list of \p SI's cases into list of CaseRange's \p Cases.
391 /// \post \p Cases wouldn't contain references to \p SI's default BB.
392 /// \returns Number of \p SI's cases that do not reference \p SI's default BB.
Clusterify(CaseVector & Cases,SwitchInst * SI)393 unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) {
394 unsigned NumSimpleCases = 0;
395
396 // Start with "simple" cases
397 for (auto Case : SI->cases()) {
398 if (Case.getCaseSuccessor() == SI->getDefaultDest())
399 continue;
400 Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),
401 Case.getCaseSuccessor()));
402 ++NumSimpleCases;
403 }
404
405 llvm::sort(Cases, CaseCmp());
406
407 // Merge case into clusters
408 if (Cases.size() >= 2) {
409 CaseItr I = Cases.begin();
410 for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {
411 int64_t nextValue = J->Low->getSExtValue();
412 int64_t currentValue = I->High->getSExtValue();
413 BasicBlock* nextBB = J->BB;
414 BasicBlock* currentBB = I->BB;
415
416 // If the two neighboring cases go to the same destination, merge them
417 // into a single case.
418 assert(nextValue > currentValue && "Cases should be strictly ascending");
419 if ((nextValue == currentValue + 1) && (currentBB == nextBB)) {
420 I->High = J->High;
421 // FIXME: Combine branch weights.
422 } else if (++I != J) {
423 *I = *J;
424 }
425 }
426 Cases.erase(std::next(I), Cases.end());
427 }
428
429 return NumSimpleCases;
430 }
431
432 /// Replace the specified switch instruction with a sequence of chained if-then
433 /// insts in a balanced binary search.
processSwitchInst(SwitchInst * SI,SmallPtrSetImpl<BasicBlock * > & DeleteList,AssumptionCache * AC,LazyValueInfo * LVI)434 void LowerSwitch::processSwitchInst(SwitchInst *SI,
435 SmallPtrSetImpl<BasicBlock *> &DeleteList,
436 AssumptionCache *AC, LazyValueInfo *LVI) {
437 BasicBlock *OrigBlock = SI->getParent();
438 Function *F = OrigBlock->getParent();
439 Value *Val = SI->getCondition(); // The value we are switching on...
440 BasicBlock* Default = SI->getDefaultDest();
441
442 // Don't handle unreachable blocks. If there are successors with phis, this
443 // would leave them behind with missing predecessors.
444 if ((OrigBlock != &F->getEntryBlock() && pred_empty(OrigBlock)) ||
445 OrigBlock->getSinglePredecessor() == OrigBlock) {
446 DeleteList.insert(OrigBlock);
447 return;
448 }
449
450 // Prepare cases vector.
451 CaseVector Cases;
452 const unsigned NumSimpleCases = Clusterify(Cases, SI);
453 LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size()
454 << ". Total non-default cases: " << NumSimpleCases
455 << "\nCase clusters: " << Cases << "\n");
456
457 // If there is only the default destination, just branch.
458 if (Cases.empty()) {
459 BranchInst::Create(Default, OrigBlock);
460 // Remove all the references from Default's PHIs to OrigBlock, but one.
461 fixPhis(Default, OrigBlock, OrigBlock);
462 SI->eraseFromParent();
463 return;
464 }
465
466 ConstantInt *LowerBound = nullptr;
467 ConstantInt *UpperBound = nullptr;
468 bool DefaultIsUnreachableFromSwitch = false;
469
470 if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) {
471 // Make the bounds tightly fitted around the case value range, because we
472 // know that the value passed to the switch must be exactly one of the case
473 // values.
474 LowerBound = Cases.front().Low;
475 UpperBound = Cases.back().High;
476 DefaultIsUnreachableFromSwitch = true;
477 } else {
478 // Constraining the range of the value being switched over helps eliminating
479 // unreachable BBs and minimizing the number of `add` instructions
480 // newLeafBlock ends up emitting. Running CorrelatedValuePropagation after
481 // LowerSwitch isn't as good, and also much more expensive in terms of
482 // compile time for the following reasons:
483 // 1. it processes many kinds of instructions, not just switches;
484 // 2. even if limited to icmp instructions only, it will have to process
485 // roughly C icmp's per switch, where C is the number of cases in the
486 // switch, while LowerSwitch only needs to call LVI once per switch.
487 const DataLayout &DL = F->getParent()->getDataLayout();
488 KnownBits Known = computeKnownBits(Val, DL, /*Depth=*/0, AC, SI);
489 // TODO Shouldn't this create a signed range?
490 ConstantRange KnownBitsRange =
491 ConstantRange::fromKnownBits(Known, /*IsSigned=*/false);
492 const ConstantRange LVIRange = LVI->getConstantRange(Val, OrigBlock, SI);
493 ConstantRange ValRange = KnownBitsRange.intersectWith(LVIRange);
494 // We delegate removal of unreachable non-default cases to other passes. In
495 // the unlikely event that some of them survived, we just conservatively
496 // maintain the invariant that all the cases lie between the bounds. This
497 // may, however, still render the default case effectively unreachable.
498 APInt Low = Cases.front().Low->getValue();
499 APInt High = Cases.back().High->getValue();
500 APInt Min = APIntOps::smin(ValRange.getSignedMin(), Low);
501 APInt Max = APIntOps::smax(ValRange.getSignedMax(), High);
502
503 LowerBound = ConstantInt::get(SI->getContext(), Min);
504 UpperBound = ConstantInt::get(SI->getContext(), Max);
505 DefaultIsUnreachableFromSwitch = (Min + (NumSimpleCases - 1) == Max);
506 }
507
508 std::vector<IntRange> UnreachableRanges;
509
510 if (DefaultIsUnreachableFromSwitch) {
511 DenseMap<BasicBlock *, unsigned> Popularity;
512 unsigned MaxPop = 0;
513 BasicBlock *PopSucc = nullptr;
514
515 IntRange R = {std::numeric_limits<int64_t>::min(),
516 std::numeric_limits<int64_t>::max()};
517 UnreachableRanges.push_back(R);
518 for (const auto &I : Cases) {
519 int64_t Low = I.Low->getSExtValue();
520 int64_t High = I.High->getSExtValue();
521
522 IntRange &LastRange = UnreachableRanges.back();
523 if (LastRange.Low == Low) {
524 // There is nothing left of the previous range.
525 UnreachableRanges.pop_back();
526 } else {
527 // Terminate the previous range.
528 assert(Low > LastRange.Low);
529 LastRange.High = Low - 1;
530 }
531 if (High != std::numeric_limits<int64_t>::max()) {
532 IntRange R = { High + 1, std::numeric_limits<int64_t>::max() };
533 UnreachableRanges.push_back(R);
534 }
535
536 // Count popularity.
537 int64_t N = High - Low + 1;
538 unsigned &Pop = Popularity[I.BB];
539 if ((Pop += N) > MaxPop) {
540 MaxPop = Pop;
541 PopSucc = I.BB;
542 }
543 }
544 #ifndef NDEBUG
545 /* UnreachableRanges should be sorted and the ranges non-adjacent. */
546 for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end();
547 I != E; ++I) {
548 assert(I->Low <= I->High);
549 auto Next = I + 1;
550 if (Next != E) {
551 assert(Next->Low > I->High);
552 }
553 }
554 #endif
555
556 // As the default block in the switch is unreachable, update the PHI nodes
557 // (remove all of the references to the default block) to reflect this.
558 const unsigned NumDefaultEdges = SI->getNumCases() + 1 - NumSimpleCases;
559 for (unsigned I = 0; I < NumDefaultEdges; ++I)
560 Default->removePredecessor(OrigBlock);
561
562 // Use the most popular block as the new default, reducing the number of
563 // cases.
564 assert(MaxPop > 0 && PopSucc);
565 Default = PopSucc;
566 Cases.erase(
567 llvm::remove_if(
568 Cases, [PopSucc](const CaseRange &R) { return R.BB == PopSucc; }),
569 Cases.end());
570
571 // If there are no cases left, just branch.
572 if (Cases.empty()) {
573 BranchInst::Create(Default, OrigBlock);
574 SI->eraseFromParent();
575 // As all the cases have been replaced with a single branch, only keep
576 // one entry in the PHI nodes.
577 for (unsigned I = 0 ; I < (MaxPop - 1) ; ++I)
578 PopSucc->removePredecessor(OrigBlock);
579 return;
580 }
581
582 // If the condition was a PHI node with the switch block as a predecessor
583 // removing predecessors may have caused the condition to be erased.
584 // Getting the condition value again here protects against that.
585 Val = SI->getCondition();
586 }
587
588 // Create a new, empty default block so that the new hierarchy of
589 // if-then statements go to this and the PHI nodes are happy.
590 BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault");
591 F->getBasicBlockList().insert(Default->getIterator(), NewDefault);
592 BranchInst::Create(Default, NewDefault);
593
594 BasicBlock *SwitchBlock =
595 switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
596 OrigBlock, OrigBlock, NewDefault, UnreachableRanges);
597
598 // If there are entries in any PHI nodes for the default edge, make sure
599 // to update them as well.
600 fixPhis(Default, OrigBlock, NewDefault);
601
602 // Branch to our shiny new if-then stuff...
603 BranchInst::Create(SwitchBlock, OrigBlock);
604
605 // We are now done with the switch instruction, delete it.
606 BasicBlock *OldDefault = SI->getDefaultDest();
607 OrigBlock->getInstList().erase(SI);
608
609 // If the Default block has no more predecessors just add it to DeleteList.
610 if (pred_begin(OldDefault) == pred_end(OldDefault))
611 DeleteList.insert(OldDefault);
612 }
613