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. 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 79 LowerSwitch() : FunctionPass(ID) { 80 initializeLowerSwitchPass(*PassRegistry::getPassRegistry()); 81 } 82 83 bool runOnFunction(Function &F) override; 84 85 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 94 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 { 120 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) 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 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 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 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 * 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. 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. 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. 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