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