llvm/lib/Transforms/Utils/LowerSwitch.cpp

   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, true); j.slt(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->getParent()->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 }