llvm-project

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

47
using namespace llvm;
48

49
#define DEBUG_TYPE "lower-switch"
50

51
namespace {
52

53
struct IntRange {
54
  APInt Low, High;
55
};
56

57
} // end anonymous namespace
58

59
namespace {
60
// Return true iff R is covered by Ranges.
61
bool 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
      Ranges, R, [](IntRange A, IntRange B) { return A.High.slt(B.High); });
69
  return I != Ranges.end() && I->Low.sle(R.Low);
70
}
71

72
struct 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

81
using CaseVector = std::vector<CaseRange>;
82
using 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!
86
struct CaseCmp {
87
  bool operator()(const CaseRange &C1, const CaseRange &C2) {
88
    const ConstantInt *CI1 = cast<const ConstantInt>(C1.Low);
89
    const ConstantInt *CI2 = cast<const ConstantInt>(C2.High);
90
    return CI1->getValue().slt(CI2->getValue());
91
  }
92
};
93

94
/// Used for debugging purposes.
95
LLVM_ATTRIBUTE_USED
96
raw_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.
118
void FixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB,
119
             const APInt &NumMergedCases) {
120
  for (auto &I : SuccBB->phis()) {
121
    PHINode *PN = cast<PHINode>(&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(Idx) == OrigBB) {
128
        PN->setIncomingBlock(Idx, 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(0) && Idx < E; ++Idx)
141
      if (PN->getIncomingBlock(Idx) == OrigBB) {
142
        Indices.push_back(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(Indices))
148
      PN->removeIncomingValue(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.
156
BasicBlock *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(Val->getContext(), "LeafBlock");
161
  F->insert(++OrigBlock->getIterator(), 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(Leaf.Low);
186
      Instruction *Add = BinaryOperator::CreateAdd(
187
          Val, NegLo, Val->getName() + ".off", NewLeaf);
188
      Constant *UpperBound = ConstantExpr::getAdd(NegLo, 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(Succ, Default, Comp, NewLeaf);
197

198
  // Update the PHI incoming value/block for the default.
199
  for (auto &I : Default->phis()) {
200
    PHINode *PN = cast<PHINode>(&I);
201
    auto *V = PN->getIncomingValueForBlock(OrigBlock);
202
    PN->addIncoming(V, 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>(I); ++I) {
208
    PHINode *PN = cast<PHINode>(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(Range); ++j) {
212
      PN->removeIncomingValue(OrigBlock);
213
    }
214

215
    int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
216
    assert(BlockIdx != -1 && "Switch didn't go to this successor??");
217
    PN->setIncomingBlock((unsigned)BlockIdx, 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.
228
BasicBlock *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(Begin->BB, OrigBlock, Predecessor, NumMergedCases);
244
      return Begin->BB;
245
    }
246
    return NewLeafBlock(*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(NewLowerBound->getContext(),
269
                                                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 = {GapLow, GapHigh};
276
    if (GapHigh.sge(GapLow) && IsInRanges(Gap, 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(Val->getContext(), "NodeBlock");
289

290
  ICmpInst *Comp = new ICmpInst(ICmpInst::ICMP_SLT, Val, Pivot.Low, "Pivot");
291

292
  BasicBlock *LBranch =
293
      SwitchConvert(LHS.begin(), LHS.end(), LowerBound, NewUpperBound, Val,
294
                    NewNode, OrigBlock, Default, UnreachableRanges);
295
  BasicBlock *RBranch =
296
      SwitchConvert(RHS.begin(), RHS.end(), NewLowerBound, UpperBound, Val,
297
                    NewNode, OrigBlock, Default, UnreachableRanges);
298

299
  F->insert(++OrigBlock->getIterator(), NewNode);
300
  Comp->insertInto(NewNode, NewNode->end());
301

302
  BranchInst::Create(LBranch, RBranch, Comp, 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.
309
unsigned 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(CaseRange(Case.getCaseValue(), Case.getCaseValue(),
317
                              Case.getCaseSuccessor()));
318
    ++NumSimpleCases;
319
  }
320

321
  llvm::sort(Cases, CaseCmp());
322

323
  // Merge case into clusters
324
  if (Cases.size() >= 2) {
325
    CaseItr I = Cases.begin();
326
    for (CaseItr J = std::next(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(std::next(I), 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.
351
void 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(OrigBlock)) ||
362
      OrigBlock->getSinglePredecessor() == OrigBlock) {
363
    DeleteList.insert(OrigBlock);
364
    return;
365
  }
366

367
  // Prepare cases vector.
368
  CaseVector Cases;
369
  const unsigned NumSimpleCases = Clusterify(Cases, SI);
370
  IntegerType *IT = cast<IntegerType>(SI->getCondition()->getType());
371
  const unsigned BitWidth = IT->getBitWidth();
372
  // Explictly use higher precision to prevent unsigned overflow where
373
  // `UnsignedMax - 0 + 1 == 0`
374
  APInt UnsignedZero(BitWidth + 1, 0);
375
  APInt UnsignedMax = APInt::getMaxValue(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(Default, OrigBlock);
383
    // Remove all the references from Default's PHIs to OrigBlock, but one.
384
    FixPhis(Default, OrigBlock, OrigBlock, 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>(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(Val, DL, /*Depth=*/0, AC, 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(Val, SI, /*UndefAllowed*/ false);
417
    ConstantRange ValRange = KnownBitsRange.intersectWith(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(ValRange.getSignedMin(), Low);
425
    APInt Max = APIntOps::smax(ValRange.getSignedMax(), High);
426

427
    LowerBound = ConstantInt::get(SI->getContext(), Min);
428
    UpperBound = ConstantInt::get(SI->getContext(), 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(BitWidth);
440
    APInt SignedMin = APInt::getSignedMinValue(BitWidth);
441
    IntRange R = {SignedMin, SignedMax};
442
    UnreachableRanges.push_back(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(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(SignedMax)) {
457
        IntRange R = {High + 1, SignedMax};
458
        UnreachableRanges.push_back(R);
459
      }
460

461
      // Count popularity.
462
      assert(High.sge(Low) && "Popularity shouldn't be negative.");
463
      APInt N = High.sext(BitWidth + 1) - Low.sext(BitWidth + 1) + 1;
464
      // Explict insert to make sure the bitwidth of APInts match
465
      APInt &Pop = Popularity.insert({I.BB, APInt(UnsignedZero)}).first->second;
466
      if ((Pop += N).ugt(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(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(Cases,
493
                   [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(Default, 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(MaxPop - 1); ++I)
503
          PopSucc->removePredecessor(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(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
515
                    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(Default, OrigBlock, nullptr, UnsignedMax);
524

525
  // Branch to our shiny new if-then stuff...
526
  BranchInst::Create(SwitchBlock, 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(OldDefault))
534
    DeleteList.insert(OldDefault);
535
}
536

537
bool 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(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(&Cur))
546
      continue;
547

548
    if (SwitchInst *SI = dyn_cast<SwitchInst>(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.
563
class LowerSwitchLegacyPass : public FunctionPass {
564
public:
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

581
char LowerSwitchLegacyPass::ID = 0;
582

583
// Publicly exposed interface to pass...
584
char &llvm::LowerSwitchID = LowerSwitchLegacyPass::ID;
585

586
INITIALIZE_PASS_BEGIN(LowerSwitchLegacyPass, "lowerswitch",
587
                      "Lower SwitchInst's to branches", false, false)
588
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
589
INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
590
INITIALIZE_PASS_END(LowerSwitchLegacyPass, "lowerswitch",
591
                    "Lower SwitchInst's to branches", false, false)
592

593
// createLowerSwitchPass - Interface to this file...
594
FunctionPass *llvm::createLowerSwitchPass() {
595
  return new LowerSwitchLegacyPass();
596
}
597

598
bool 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

605
PreservedAnalyses LowerSwitchPass::run(Function &F,
606
                                       FunctionAnalysisManager &AM) {
607
  LazyValueInfo *LVI = &AM.getResult<LazyValueAnalysis>(F);
608
  AssumptionCache *AC = AM.getCachedResult<AssumptionAnalysis>(F);
609
  return LowerSwitch(F, LVI, AC) ? PreservedAnalyses::none()
610
                                 : PreservedAnalyses::all();
611
}
612