LowerSwitch.cpp revision 321369
1193323Sed//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// The LowerSwitch transformation rewrites switch instructions with a sequence 11193323Sed// of branches, which allows targets to get away with not implementing the 12193323Sed// switch instruction until it is convenient. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16249423Sdim#include "llvm/ADT/STLExtras.h" 17288943Sdim#include "llvm/IR/CFG.h" 18249423Sdim#include "llvm/IR/Constants.h" 19249423Sdim#include "llvm/IR/Function.h" 20249423Sdim#include "llvm/IR/Instructions.h" 21249423Sdim#include "llvm/IR/LLVMContext.h" 22193323Sed#include "llvm/Pass.h" 23198892Srdivacky#include "llvm/Support/Compiler.h" 24193323Sed#include "llvm/Support/Debug.h" 25193323Sed#include "llvm/Support/raw_ostream.h" 26321369Sdim#include "llvm/Transforms/Scalar.h" 27288943Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 28249423Sdim#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 29193323Sed#include <algorithm> 30193323Sedusing namespace llvm; 31193323Sed 32276479Sdim#define DEBUG_TYPE "lower-switch" 33276479Sdim 34193323Sednamespace { 35288943Sdim struct IntRange { 36288943Sdim int64_t Low, High; 37288943Sdim }; 38288943Sdim // Return true iff R is covered by Ranges. 39288943Sdim static bool IsInRanges(const IntRange &R, 40288943Sdim const std::vector<IntRange> &Ranges) { 41288943Sdim // Note: Ranges must be sorted, non-overlapping and non-adjacent. 42288943Sdim 43288943Sdim // Find the first range whose High field is >= R.High, 44288943Sdim // then check if the Low field is <= R.Low. If so, we 45288943Sdim // have a Range that covers R. 46288943Sdim auto I = std::lower_bound( 47288943Sdim Ranges.begin(), Ranges.end(), R, 48288943Sdim [](const IntRange &A, const IntRange &B) { return A.High < B.High; }); 49288943Sdim return I != Ranges.end() && I->Low <= R.Low; 50288943Sdim } 51288943Sdim 52296417Sdim /// Replace all SwitchInst instructions with chained branch instructions. 53198892Srdivacky class LowerSwitch : public FunctionPass { 54193323Sed public: 55193323Sed static char ID; // Pass identification, replacement for typeid 56218893Sdim LowerSwitch() : FunctionPass(ID) { 57218893Sdim initializeLowerSwitchPass(*PassRegistry::getPassRegistry()); 58218893Sdim } 59193323Sed 60276479Sdim bool runOnFunction(Function &F) override; 61276479Sdim 62193323Sed struct CaseRange { 63288943Sdim ConstantInt* Low; 64288943Sdim ConstantInt* High; 65193323Sed BasicBlock* BB; 66193323Sed 67288943Sdim CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb) 68288943Sdim : Low(low), High(high), BB(bb) {} 69193323Sed }; 70193323Sed 71276479Sdim typedef std::vector<CaseRange> CaseVector; 72193323Sed typedef std::vector<CaseRange>::iterator CaseItr; 73193323Sed private: 74296417Sdim void processSwitchInst(SwitchInst *SI, SmallPtrSetImpl<BasicBlock*> &DeleteList); 75193323Sed 76276479Sdim BasicBlock *switchConvert(CaseItr Begin, CaseItr End, 77276479Sdim ConstantInt *LowerBound, ConstantInt *UpperBound, 78276479Sdim Value *Val, BasicBlock *Predecessor, 79288943Sdim BasicBlock *OrigBlock, BasicBlock *Default, 80288943Sdim const std::vector<IntRange> &UnreachableRanges); 81276479Sdim BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, BasicBlock *OrigBlock, 82276479Sdim BasicBlock *Default); 83276479Sdim unsigned Clusterify(CaseVector &Cases, SwitchInst *SI); 84193323Sed }; 85261991Sdim 86261991Sdim /// The comparison function for sorting the switch case values in the vector. 87261991Sdim /// WARNING: Case ranges should be disjoint! 88261991Sdim struct CaseCmp { 89261991Sdim bool operator () (const LowerSwitch::CaseRange& C1, 90261991Sdim const LowerSwitch::CaseRange& C2) { 91261991Sdim 92261991Sdim const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 93261991Sdim const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 94261991Sdim return CI1->getValue().slt(CI2->getValue()); 95261991Sdim } 96261991Sdim }; 97193323Sed} 98193323Sed 99193323Sedchar LowerSwitch::ID = 0; 100212904SdimINITIALIZE_PASS(LowerSwitch, "lowerswitch", 101218893Sdim "Lower SwitchInst's to branches", false, false) 102193323Sed 103221345Sdim// Publicly exposed interface to pass... 104212904Sdimchar &llvm::LowerSwitchID = LowerSwitch::ID; 105193323Sed// createLowerSwitchPass - Interface to this file... 106193323SedFunctionPass *llvm::createLowerSwitchPass() { 107193323Sed return new LowerSwitch(); 108193323Sed} 109193323Sed 110193323Sedbool LowerSwitch::runOnFunction(Function &F) { 111193323Sed bool Changed = false; 112296417Sdim SmallPtrSet<BasicBlock*, 8> DeleteList; 113193323Sed 114193323Sed for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 115296417Sdim BasicBlock *Cur = &*I++; // Advance over block so we don't traverse new blocks 116193323Sed 117296417Sdim // If the block is a dead Default block that will be deleted later, don't 118296417Sdim // waste time processing it. 119296417Sdim if (DeleteList.count(Cur)) 120296417Sdim continue; 121296417Sdim 122193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 123193323Sed Changed = true; 124296417Sdim processSwitchInst(SI, DeleteList); 125193323Sed } 126193323Sed } 127193323Sed 128296417Sdim for (BasicBlock* BB: DeleteList) { 129296417Sdim DeleteDeadBlock(BB); 130296417Sdim } 131296417Sdim 132193323Sed return Changed; 133193323Sed} 134193323Sed 135296417Sdim/// Used for debugging purposes. 136198090Srdivackystatic raw_ostream& operator<<(raw_ostream &O, 137218893Sdim const LowerSwitch::CaseVector &C) 138218893Sdim LLVM_ATTRIBUTE_USED; 139198090Srdivackystatic raw_ostream& operator<<(raw_ostream &O, 140198090Srdivacky const LowerSwitch::CaseVector &C) { 141193323Sed O << "["; 142193323Sed 143193323Sed for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 144193323Sed E = C.end(); B != E; ) { 145193323Sed O << *B->Low << " -" << *B->High; 146193323Sed if (++B != E) O << ", "; 147193323Sed } 148193323Sed 149193323Sed return O << "]"; 150193323Sed} 151193323Sed 152296417Sdim/// \brief Update the first occurrence of the "switch statement" BB in the PHI 153296417Sdim/// node with the "new" BB. The other occurrences will: 154296417Sdim/// 155296417Sdim/// 1) Be updated by subsequent calls to this function. Switch statements may 156296417Sdim/// have more than one outcoming edge into the same BB if they all have the same 157296417Sdim/// value. When the switch statement is converted these incoming edges are now 158296417Sdim/// coming from multiple BBs. 159296417Sdim/// 2) Removed if subsequent incoming values now share the same case, i.e., 160296417Sdim/// multiple outcome edges are condensed into one. This is necessary to keep the 161296417Sdim/// number of phi values equal to the number of branches to SuccBB. 162280031Sdimstatic void fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB, 163280031Sdim unsigned NumMergedCases) { 164296417Sdim for (BasicBlock::iterator I = SuccBB->begin(), 165296417Sdim IE = SuccBB->getFirstNonPHI()->getIterator(); 166280031Sdim I != IE; ++I) { 167276479Sdim PHINode *PN = cast<PHINode>(I); 168276479Sdim 169296417Sdim // Only update the first occurrence. 170280031Sdim unsigned Idx = 0, E = PN->getNumIncomingValues(); 171280031Sdim unsigned LocalNumMergedCases = NumMergedCases; 172280031Sdim for (; Idx != E; ++Idx) { 173280031Sdim if (PN->getIncomingBlock(Idx) == OrigBB) { 174280031Sdim PN->setIncomingBlock(Idx, NewBB); 175280031Sdim break; 176280031Sdim } 177276479Sdim } 178280031Sdim 179296417Sdim // Remove additional occurrences coming from condensed cases and keep the 180280031Sdim // number of incoming values equal to the number of branches to SuccBB. 181288943Sdim SmallVector<unsigned, 8> Indices; 182280031Sdim for (++Idx; LocalNumMergedCases > 0 && Idx < E; ++Idx) 183280031Sdim if (PN->getIncomingBlock(Idx) == OrigBB) { 184288943Sdim Indices.push_back(Idx); 185280031Sdim LocalNumMergedCases--; 186280031Sdim } 187288943Sdim // Remove incoming values in the reverse order to prevent invalidating 188288943Sdim // *successive* index. 189309124Sdim for (unsigned III : reverse(Indices)) 190309124Sdim PN->removeIncomingValue(III); 191276479Sdim } 192276479Sdim} 193276479Sdim 194296417Sdim/// Convert the switch statement into a binary lookup of the case values. 195296417Sdim/// The function recursively builds this tree. LowerBound and UpperBound are 196296417Sdim/// used to keep track of the bounds for Val that have already been checked by 197296417Sdim/// a block emitted by one of the previous calls to switchConvert in the call 198296417Sdim/// stack. 199288943SdimBasicBlock * 200288943SdimLowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound, 201288943Sdim ConstantInt *UpperBound, Value *Val, 202288943Sdim BasicBlock *Predecessor, BasicBlock *OrigBlock, 203288943Sdim BasicBlock *Default, 204288943Sdim const std::vector<IntRange> &UnreachableRanges) { 205193323Sed unsigned Size = End - Begin; 206193323Sed 207276479Sdim if (Size == 1) { 208276479Sdim // Check if the Case Range is perfectly squeezed in between 209276479Sdim // already checked Upper and Lower bounds. If it is then we can avoid 210276479Sdim // emitting the code that checks if the value actually falls in the range 211276479Sdim // because the bounds already tell us so. 212276479Sdim if (Begin->Low == LowerBound && Begin->High == UpperBound) { 213280031Sdim unsigned NumMergedCases = 0; 214280031Sdim if (LowerBound && UpperBound) 215280031Sdim NumMergedCases = 216280031Sdim UpperBound->getSExtValue() - LowerBound->getSExtValue(); 217280031Sdim fixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases); 218276479Sdim return Begin->BB; 219276479Sdim } 220193323Sed return newLeafBlock(*Begin, Val, OrigBlock, Default); 221276479Sdim } 222193323Sed 223193323Sed unsigned Mid = Size / 2; 224193323Sed std::vector<CaseRange> LHS(Begin, Begin + Mid); 225202375Srdivacky DEBUG(dbgs() << "LHS: " << LHS << "\n"); 226193323Sed std::vector<CaseRange> RHS(Begin + Mid, End); 227202375Srdivacky DEBUG(dbgs() << "RHS: " << RHS << "\n"); 228193323Sed 229276479Sdim CaseRange &Pivot = *(Begin + Mid); 230276479Sdim DEBUG(dbgs() << "Pivot ==> " 231288943Sdim << Pivot.Low->getValue() 232288943Sdim << " -" << Pivot.High->getValue() << "\n"); 233193323Sed 234276479Sdim // NewLowerBound here should never be the integer minimal value. 235276479Sdim // This is because it is computed from a case range that is never 236276479Sdim // the smallest, so there is always a case range that has at least 237276479Sdim // a smaller value. 238288943Sdim ConstantInt *NewLowerBound = Pivot.Low; 239193323Sed 240288943Sdim // Because NewLowerBound is never the smallest representable integer 241288943Sdim // it is safe here to subtract one. 242288943Sdim ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(), 243288943Sdim NewLowerBound->getValue() - 1); 244288943Sdim 245288943Sdim if (!UnreachableRanges.empty()) { 246288943Sdim // Check if the gap between LHS's highest and NewLowerBound is unreachable. 247288943Sdim int64_t GapLow = LHS.back().High->getSExtValue() + 1; 248288943Sdim int64_t GapHigh = NewLowerBound->getSExtValue() - 1; 249288943Sdim IntRange Gap = { GapLow, GapHigh }; 250288943Sdim if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges)) 251288943Sdim NewUpperBound = LHS.back().High; 252276479Sdim } 253276479Sdim 254276479Sdim DEBUG(dbgs() << "LHS Bounds ==> "; 255276479Sdim if (LowerBound) { 256288943Sdim dbgs() << LowerBound->getSExtValue(); 257276479Sdim } else { 258276479Sdim dbgs() << "NONE"; 259276479Sdim } 260276479Sdim dbgs() << " - " << NewUpperBound->getSExtValue() << "\n"; 261276479Sdim dbgs() << "RHS Bounds ==> "; 262276479Sdim dbgs() << NewLowerBound->getSExtValue() << " - "; 263276479Sdim if (UpperBound) { 264288943Sdim dbgs() << UpperBound->getSExtValue() << "\n"; 265276479Sdim } else { 266276479Sdim dbgs() << "NONE\n"; 267276479Sdim }); 268276479Sdim 269193323Sed // Create a new node that checks if the value is < pivot. Go to the 270193323Sed // left branch if it is and right branch if not. 271193323Sed Function* F = OrigBlock->getParent(); 272198090Srdivacky BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock"); 273193323Sed 274261991Sdim ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, 275198090Srdivacky Val, Pivot.Low, "Pivot"); 276276479Sdim 277276479Sdim BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound, 278276479Sdim NewUpperBound, Val, NewNode, OrigBlock, 279288943Sdim Default, UnreachableRanges); 280276479Sdim BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound, 281276479Sdim UpperBound, Val, NewNode, OrigBlock, 282288943Sdim Default, UnreachableRanges); 283276479Sdim 284296417Sdim F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewNode); 285193323Sed NewNode->getInstList().push_back(Comp); 286276479Sdim 287193323Sed BranchInst::Create(LBranch, RBranch, Comp, NewNode); 288193323Sed return NewNode; 289193323Sed} 290193323Sed 291296417Sdim/// Create a new leaf block for the binary lookup tree. It checks if the 292296417Sdim/// switch's value == the case's value. If not, then it jumps to the default 293296417Sdim/// branch. At this point in the tree, the value can't be another valid case 294296417Sdim/// value, so the jump to the "default" branch is warranted. 295193323SedBasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, 296193323Sed BasicBlock* OrigBlock, 297193323Sed BasicBlock* Default) 298193323Sed{ 299193323Sed Function* F = OrigBlock->getParent(); 300198090Srdivacky BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock"); 301296417Sdim F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewLeaf); 302193323Sed 303193323Sed // Emit comparison 304276479Sdim ICmpInst* Comp = nullptr; 305193323Sed if (Leaf.Low == Leaf.High) { 306193323Sed // Make the seteq instruction... 307198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, 308198090Srdivacky Leaf.Low, "SwitchLeaf"); 309193323Sed } else { 310193323Sed // Make range comparison 311288943Sdim if (Leaf.Low->isMinValue(true /*isSigned*/)) { 312193323Sed // Val >= Min && Val <= Hi --> Val <= Hi 313198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, 314198090Srdivacky "SwitchLeaf"); 315288943Sdim } else if (Leaf.Low->isZero()) { 316193323Sed // Val >= 0 && Val <= Hi --> Val <=u Hi 317198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, 318198090Srdivacky "SwitchLeaf"); 319193323Sed } else { 320193323Sed // Emit V-Lo <=u Hi-Lo 321193323Sed Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); 322193323Sed Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 323193323Sed Val->getName()+".off", 324193323Sed NewLeaf); 325193323Sed Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); 326198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, 327198090Srdivacky "SwitchLeaf"); 328193323Sed } 329193323Sed } 330193323Sed 331193323Sed // Make the conditional branch... 332193323Sed BasicBlock* Succ = Leaf.BB; 333193323Sed BranchInst::Create(Succ, Default, Comp, NewLeaf); 334193323Sed 335193323Sed // If there were any PHI nodes in this successor, rewrite one entry 336193323Sed // from OrigBlock to come from NewLeaf. 337193323Sed for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 338193323Sed PHINode* PN = cast<PHINode>(I); 339193323Sed // Remove all but one incoming entries from the cluster 340288943Sdim uint64_t Range = Leaf.High->getSExtValue() - 341288943Sdim Leaf.Low->getSExtValue(); 342193323Sed for (uint64_t j = 0; j < Range; ++j) { 343193323Sed PN->removeIncomingValue(OrigBlock); 344193323Sed } 345193323Sed 346193323Sed int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 347193323Sed assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 348193323Sed PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 349193323Sed } 350193323Sed 351193323Sed return NewLeaf; 352193323Sed} 353193323Sed 354296417Sdim/// Transform simple list of Cases into list of CaseRange's. 355193323Sedunsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 356261991Sdim unsigned numCmps = 0; 357193323Sed 358193323Sed // Start with "simple" cases 359321369Sdim for (auto Case : SI->cases()) 360321369Sdim Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(), 361321369Sdim Case.getCaseSuccessor())); 362321369Sdim 363261991Sdim std::sort(Cases.begin(), Cases.end(), CaseCmp()); 364261991Sdim 365261991Sdim // Merge case into clusters 366288943Sdim if (Cases.size() >= 2) { 367288943Sdim CaseItr I = Cases.begin(); 368288943Sdim for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) { 369288943Sdim int64_t nextValue = J->Low->getSExtValue(); 370288943Sdim int64_t currentValue = I->High->getSExtValue(); 371261991Sdim BasicBlock* nextBB = J->BB; 372261991Sdim BasicBlock* currentBB = I->BB; 373261991Sdim 374261991Sdim // If the two neighboring cases go to the same destination, merge them 375261991Sdim // into a single case. 376288943Sdim assert(nextValue > currentValue && "Cases should be strictly ascending"); 377288943Sdim if ((nextValue == currentValue + 1) && (currentBB == nextBB)) { 378261991Sdim I->High = J->High; 379288943Sdim // FIXME: Combine branch weights. 380288943Sdim } else if (++I != J) { 381288943Sdim *I = *J; 382261991Sdim } 383261991Sdim } 384288943Sdim Cases.erase(std::next(I), Cases.end()); 385288943Sdim } 386261991Sdim 387261991Sdim for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 388261991Sdim if (I->Low != I->High) 389193323Sed // A range counts double, since it requires two compares. 390193323Sed ++numCmps; 391193323Sed } 392193323Sed 393261991Sdim return numCmps; 394193323Sed} 395193323Sed 396296417Sdim/// Replace the specified switch instruction with a sequence of chained if-then 397296417Sdim/// insts in a balanced binary search. 398296417Sdimvoid LowerSwitch::processSwitchInst(SwitchInst *SI, 399296417Sdim SmallPtrSetImpl<BasicBlock*> &DeleteList) { 400193323Sed BasicBlock *CurBlock = SI->getParent(); 401193323Sed BasicBlock *OrigBlock = CurBlock; 402193323Sed Function *F = CurBlock->getParent(); 403226633Sdim Value *Val = SI->getCondition(); // The value we are switching on... 404193323Sed BasicBlock* Default = SI->getDefaultDest(); 405193323Sed 406321369Sdim // Don't handle unreachable blocks. If there are successors with phis, this 407321369Sdim // would leave them behind with missing predecessors. 408321369Sdim if ((CurBlock != &F->getEntryBlock() && pred_empty(CurBlock)) || 409321369Sdim CurBlock->getSinglePredecessor() == CurBlock) { 410321369Sdim DeleteList.insert(CurBlock); 411321369Sdim return; 412321369Sdim } 413321369Sdim 414288943Sdim // If there is only the default destination, just branch. 415234353Sdim if (!SI->getNumCases()) { 416288943Sdim BranchInst::Create(Default, CurBlock); 417288943Sdim SI->eraseFromParent(); 418193323Sed return; 419193323Sed } 420193323Sed 421288943Sdim // Prepare cases vector. 422288943Sdim CaseVector Cases; 423288943Sdim unsigned numCmps = Clusterify(Cases, SI); 424288943Sdim DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() 425288943Sdim << ". Total compares: " << numCmps << "\n"); 426288943Sdim DEBUG(dbgs() << "Cases: " << Cases << "\n"); 427288943Sdim (void)numCmps; 428288943Sdim 429288943Sdim ConstantInt *LowerBound = nullptr; 430288943Sdim ConstantInt *UpperBound = nullptr; 431288943Sdim std::vector<IntRange> UnreachableRanges; 432288943Sdim 433288943Sdim if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) { 434296417Sdim // Make the bounds tightly fitted around the case value range, because we 435288943Sdim // know that the value passed to the switch must be exactly one of the case 436288943Sdim // values. 437288943Sdim assert(!Cases.empty()); 438288943Sdim LowerBound = Cases.front().Low; 439288943Sdim UpperBound = Cases.back().High; 440288943Sdim 441288943Sdim DenseMap<BasicBlock *, unsigned> Popularity; 442288943Sdim unsigned MaxPop = 0; 443288943Sdim BasicBlock *PopSucc = nullptr; 444288943Sdim 445288943Sdim IntRange R = { INT64_MIN, INT64_MAX }; 446288943Sdim UnreachableRanges.push_back(R); 447288943Sdim for (const auto &I : Cases) { 448288943Sdim int64_t Low = I.Low->getSExtValue(); 449288943Sdim int64_t High = I.High->getSExtValue(); 450288943Sdim 451288943Sdim IntRange &LastRange = UnreachableRanges.back(); 452288943Sdim if (LastRange.Low == Low) { 453288943Sdim // There is nothing left of the previous range. 454288943Sdim UnreachableRanges.pop_back(); 455288943Sdim } else { 456288943Sdim // Terminate the previous range. 457288943Sdim assert(Low > LastRange.Low); 458288943Sdim LastRange.High = Low - 1; 459288943Sdim } 460288943Sdim if (High != INT64_MAX) { 461288943Sdim IntRange R = { High + 1, INT64_MAX }; 462288943Sdim UnreachableRanges.push_back(R); 463288943Sdim } 464288943Sdim 465288943Sdim // Count popularity. 466288943Sdim int64_t N = High - Low + 1; 467288943Sdim unsigned &Pop = Popularity[I.BB]; 468288943Sdim if ((Pop += N) > MaxPop) { 469288943Sdim MaxPop = Pop; 470288943Sdim PopSucc = I.BB; 471288943Sdim } 472288943Sdim } 473288943Sdim#ifndef NDEBUG 474288943Sdim /* UnreachableRanges should be sorted and the ranges non-adjacent. */ 475288943Sdim for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end(); 476288943Sdim I != E; ++I) { 477288943Sdim assert(I->Low <= I->High); 478288943Sdim auto Next = I + 1; 479288943Sdim if (Next != E) { 480288943Sdim assert(Next->Low > I->High); 481288943Sdim } 482288943Sdim } 483288943Sdim#endif 484288943Sdim 485288943Sdim // Use the most popular block as the new default, reducing the number of 486288943Sdim // cases. 487288943Sdim assert(MaxPop > 0 && PopSucc); 488288943Sdim Default = PopSucc; 489314564Sdim Cases.erase( 490314564Sdim remove_if(Cases, 491314564Sdim [PopSucc](const CaseRange &R) { return R.BB == PopSucc; }), 492314564Sdim Cases.end()); 493288943Sdim 494288943Sdim // If there are no cases left, just branch. 495288943Sdim if (Cases.empty()) { 496288943Sdim BranchInst::Create(Default, CurBlock); 497288943Sdim SI->eraseFromParent(); 498288943Sdim return; 499288943Sdim } 500288943Sdim } 501288943Sdim 502193323Sed // Create a new, empty default block so that the new hierarchy of 503193323Sed // if-then statements go to this and the PHI nodes are happy. 504288943Sdim BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); 505296417Sdim F->getBasicBlockList().insert(Default->getIterator(), NewDefault); 506288943Sdim BranchInst::Create(Default, NewDefault); 507193323Sed 508193323Sed // If there is an entry in any PHI nodes for the default edge, make sure 509193323Sed // to update them as well. 510193323Sed for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 511193323Sed PHINode *PN = cast<PHINode>(I); 512193323Sed int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 513193323Sed assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 514193323Sed PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 515193323Sed } 516193323Sed 517276479Sdim BasicBlock *SwitchBlock = 518276479Sdim switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val, 519288943Sdim OrigBlock, OrigBlock, NewDefault, UnreachableRanges); 520276479Sdim 521193323Sed // Branch to our shiny new if-then stuff... 522193323Sed BranchInst::Create(SwitchBlock, OrigBlock); 523193323Sed 524193323Sed // We are now done with the switch instruction, delete it. 525288943Sdim BasicBlock *OldDefault = SI->getDefaultDest(); 526193323Sed CurBlock->getInstList().erase(SI); 527276479Sdim 528296417Sdim // If the Default block has no more predecessors just add it to DeleteList. 529288943Sdim if (pred_begin(OldDefault) == pred_end(OldDefault)) 530296417Sdim DeleteList.insert(OldDefault); 531193323Sed} 532