LowerSwitch.cpp revision 288943
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 16193323Sed#include "llvm/Transforms/Scalar.h" 17249423Sdim#include "llvm/ADT/STLExtras.h" 18288943Sdim#include "llvm/IR/CFG.h" 19249423Sdim#include "llvm/IR/Constants.h" 20249423Sdim#include "llvm/IR/Function.h" 21249423Sdim#include "llvm/IR/Instructions.h" 22249423Sdim#include "llvm/IR/LLVMContext.h" 23193323Sed#include "llvm/Pass.h" 24198892Srdivacky#include "llvm/Support/Compiler.h" 25193323Sed#include "llvm/Support/Debug.h" 26193323Sed#include "llvm/Support/raw_ostream.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 52193323Sed /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch 53212904Sdim /// instructions. 54198892Srdivacky class LowerSwitch : public FunctionPass { 55193323Sed public: 56193323Sed static char ID; // Pass identification, replacement for typeid 57218893Sdim LowerSwitch() : FunctionPass(ID) { 58218893Sdim initializeLowerSwitchPass(*PassRegistry::getPassRegistry()); 59218893Sdim } 60193323Sed 61276479Sdim bool runOnFunction(Function &F) override; 62276479Sdim 63276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 64193323Sed // This is a cluster of orthogonal Transforms 65193323Sed AU.addPreserved<UnifyFunctionExitNodes>(); 66193323Sed AU.addPreservedID(LowerInvokePassID); 67193323Sed } 68193323Sed 69193323Sed struct CaseRange { 70288943Sdim ConstantInt* Low; 71288943Sdim ConstantInt* High; 72193323Sed BasicBlock* BB; 73193323Sed 74288943Sdim CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb) 75288943Sdim : Low(low), High(high), BB(bb) {} 76193323Sed }; 77193323Sed 78276479Sdim typedef std::vector<CaseRange> CaseVector; 79193323Sed typedef std::vector<CaseRange>::iterator CaseItr; 80193323Sed private: 81193323Sed void processSwitchInst(SwitchInst *SI); 82193323Sed 83276479Sdim BasicBlock *switchConvert(CaseItr Begin, CaseItr End, 84276479Sdim ConstantInt *LowerBound, ConstantInt *UpperBound, 85276479Sdim Value *Val, BasicBlock *Predecessor, 86288943Sdim BasicBlock *OrigBlock, BasicBlock *Default, 87288943Sdim const std::vector<IntRange> &UnreachableRanges); 88276479Sdim BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, BasicBlock *OrigBlock, 89276479Sdim BasicBlock *Default); 90276479Sdim unsigned Clusterify(CaseVector &Cases, SwitchInst *SI); 91193323Sed }; 92261991Sdim 93261991Sdim /// The comparison function for sorting the switch case values in the vector. 94261991Sdim /// WARNING: Case ranges should be disjoint! 95261991Sdim struct CaseCmp { 96261991Sdim bool operator () (const LowerSwitch::CaseRange& C1, 97261991Sdim const LowerSwitch::CaseRange& C2) { 98261991Sdim 99261991Sdim const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 100261991Sdim const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 101261991Sdim return CI1->getValue().slt(CI2->getValue()); 102261991Sdim } 103261991Sdim }; 104193323Sed} 105193323Sed 106193323Sedchar LowerSwitch::ID = 0; 107212904SdimINITIALIZE_PASS(LowerSwitch, "lowerswitch", 108218893Sdim "Lower SwitchInst's to branches", false, false) 109193323Sed 110221345Sdim// Publicly exposed interface to pass... 111212904Sdimchar &llvm::LowerSwitchID = LowerSwitch::ID; 112193323Sed// createLowerSwitchPass - Interface to this file... 113193323SedFunctionPass *llvm::createLowerSwitchPass() { 114193323Sed return new LowerSwitch(); 115193323Sed} 116193323Sed 117193323Sedbool LowerSwitch::runOnFunction(Function &F) { 118193323Sed bool Changed = false; 119193323Sed 120193323Sed for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 121193323Sed BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 122193323Sed 123193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 124193323Sed Changed = true; 125193323Sed processSwitchInst(SI); 126193323Sed } 127193323Sed } 128193323Sed 129193323Sed return Changed; 130193323Sed} 131193323Sed 132193323Sed// operator<< - Used for debugging purposes. 133193323Sed// 134198090Srdivackystatic raw_ostream& operator<<(raw_ostream &O, 135218893Sdim const LowerSwitch::CaseVector &C) 136218893Sdim LLVM_ATTRIBUTE_USED; 137198090Srdivackystatic raw_ostream& operator<<(raw_ostream &O, 138198090Srdivacky const LowerSwitch::CaseVector &C) { 139193323Sed O << "["; 140193323Sed 141193323Sed for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 142193323Sed E = C.end(); B != E; ) { 143193323Sed O << *B->Low << " -" << *B->High; 144193323Sed if (++B != E) O << ", "; 145193323Sed } 146193323Sed 147193323Sed return O << "]"; 148193323Sed} 149193323Sed 150280031Sdim// \brief Update the first occurrence of the "switch statement" BB in the PHI 151280031Sdim// node with the "new" BB. The other occurrences will: 152280031Sdim// 153280031Sdim// 1) Be updated by subsequent calls to this function. Switch statements may 154280031Sdim// have more than one outcoming edge into the same BB if they all have the same 155280031Sdim// value. When the switch statement is converted these incoming edges are now 156280031Sdim// coming from multiple BBs. 157280031Sdim// 2) Removed if subsequent incoming values now share the same case, i.e., 158280031Sdim// multiple outcome edges are condensed into one. This is necessary to keep the 159280031Sdim// number of phi values equal to the number of branches to SuccBB. 160280031Sdimstatic void fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB, 161280031Sdim unsigned NumMergedCases) { 162280031Sdim for (BasicBlock::iterator I = SuccBB->begin(), IE = SuccBB->getFirstNonPHI(); 163280031Sdim I != IE; ++I) { 164276479Sdim PHINode *PN = cast<PHINode>(I); 165276479Sdim 166280031Sdim // Only update the first occurence. 167280031Sdim unsigned Idx = 0, E = PN->getNumIncomingValues(); 168280031Sdim unsigned LocalNumMergedCases = NumMergedCases; 169280031Sdim for (; Idx != E; ++Idx) { 170280031Sdim if (PN->getIncomingBlock(Idx) == OrigBB) { 171280031Sdim PN->setIncomingBlock(Idx, NewBB); 172280031Sdim break; 173280031Sdim } 174276479Sdim } 175280031Sdim 176280031Sdim // Remove additional occurences coming from condensed cases and keep the 177280031Sdim // number of incoming values equal to the number of branches to SuccBB. 178288943Sdim SmallVector<unsigned, 8> Indices; 179280031Sdim for (++Idx; LocalNumMergedCases > 0 && Idx < E; ++Idx) 180280031Sdim if (PN->getIncomingBlock(Idx) == OrigBB) { 181288943Sdim Indices.push_back(Idx); 182280031Sdim LocalNumMergedCases--; 183280031Sdim } 184288943Sdim // Remove incoming values in the reverse order to prevent invalidating 185288943Sdim // *successive* index. 186288943Sdim for (auto III = Indices.rbegin(), IIE = Indices.rend(); III != IIE; ++III) 187288943Sdim PN->removeIncomingValue(*III); 188276479Sdim } 189276479Sdim} 190276479Sdim 191193323Sed// switchConvert - Convert the switch statement into a binary lookup of 192193323Sed// the case values. The function recursively builds this tree. 193276479Sdim// LowerBound and UpperBound are used to keep track of the bounds for Val 194276479Sdim// that have already been checked by a block emitted by one of the previous 195276479Sdim// calls to switchConvert in the call stack. 196288943SdimBasicBlock * 197288943SdimLowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound, 198288943Sdim ConstantInt *UpperBound, Value *Val, 199288943Sdim BasicBlock *Predecessor, BasicBlock *OrigBlock, 200288943Sdim BasicBlock *Default, 201288943Sdim const std::vector<IntRange> &UnreachableRanges) { 202193323Sed unsigned Size = End - Begin; 203193323Sed 204276479Sdim if (Size == 1) { 205276479Sdim // Check if the Case Range is perfectly squeezed in between 206276479Sdim // already checked Upper and Lower bounds. If it is then we can avoid 207276479Sdim // emitting the code that checks if the value actually falls in the range 208276479Sdim // because the bounds already tell us so. 209276479Sdim if (Begin->Low == LowerBound && Begin->High == UpperBound) { 210280031Sdim unsigned NumMergedCases = 0; 211280031Sdim if (LowerBound && UpperBound) 212280031Sdim NumMergedCases = 213280031Sdim UpperBound->getSExtValue() - LowerBound->getSExtValue(); 214280031Sdim fixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases); 215276479Sdim return Begin->BB; 216276479Sdim } 217193323Sed return newLeafBlock(*Begin, Val, OrigBlock, Default); 218276479Sdim } 219193323Sed 220193323Sed unsigned Mid = Size / 2; 221193323Sed std::vector<CaseRange> LHS(Begin, Begin + Mid); 222202375Srdivacky DEBUG(dbgs() << "LHS: " << LHS << "\n"); 223193323Sed std::vector<CaseRange> RHS(Begin + Mid, End); 224202375Srdivacky DEBUG(dbgs() << "RHS: " << RHS << "\n"); 225193323Sed 226276479Sdim CaseRange &Pivot = *(Begin + Mid); 227276479Sdim DEBUG(dbgs() << "Pivot ==> " 228288943Sdim << Pivot.Low->getValue() 229288943Sdim << " -" << Pivot.High->getValue() << "\n"); 230193323Sed 231276479Sdim // NewLowerBound here should never be the integer minimal value. 232276479Sdim // This is because it is computed from a case range that is never 233276479Sdim // the smallest, so there is always a case range that has at least 234276479Sdim // a smaller value. 235288943Sdim ConstantInt *NewLowerBound = Pivot.Low; 236193323Sed 237288943Sdim // Because NewLowerBound is never the smallest representable integer 238288943Sdim // it is safe here to subtract one. 239288943Sdim ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(), 240288943Sdim NewLowerBound->getValue() - 1); 241288943Sdim 242288943Sdim if (!UnreachableRanges.empty()) { 243288943Sdim // Check if the gap between LHS's highest and NewLowerBound is unreachable. 244288943Sdim int64_t GapLow = LHS.back().High->getSExtValue() + 1; 245288943Sdim int64_t GapHigh = NewLowerBound->getSExtValue() - 1; 246288943Sdim IntRange Gap = { GapLow, GapHigh }; 247288943Sdim if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges)) 248288943Sdim NewUpperBound = LHS.back().High; 249276479Sdim } 250276479Sdim 251276479Sdim DEBUG(dbgs() << "LHS Bounds ==> "; 252276479Sdim if (LowerBound) { 253288943Sdim dbgs() << LowerBound->getSExtValue(); 254276479Sdim } else { 255276479Sdim dbgs() << "NONE"; 256276479Sdim } 257276479Sdim dbgs() << " - " << NewUpperBound->getSExtValue() << "\n"; 258276479Sdim dbgs() << "RHS Bounds ==> "; 259276479Sdim dbgs() << NewLowerBound->getSExtValue() << " - "; 260276479Sdim if (UpperBound) { 261288943Sdim dbgs() << UpperBound->getSExtValue() << "\n"; 262276479Sdim } else { 263276479Sdim dbgs() << "NONE\n"; 264276479Sdim }); 265276479Sdim 266193323Sed // Create a new node that checks if the value is < pivot. Go to the 267193323Sed // left branch if it is and right branch if not. 268193323Sed Function* F = OrigBlock->getParent(); 269198090Srdivacky BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock"); 270193323Sed 271261991Sdim ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, 272198090Srdivacky Val, Pivot.Low, "Pivot"); 273276479Sdim 274276479Sdim BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound, 275276479Sdim NewUpperBound, Val, NewNode, OrigBlock, 276288943Sdim Default, UnreachableRanges); 277276479Sdim BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound, 278276479Sdim UpperBound, Val, NewNode, OrigBlock, 279288943Sdim Default, UnreachableRanges); 280276479Sdim 281276479Sdim Function::iterator FI = OrigBlock; 282276479Sdim F->getBasicBlockList().insert(++FI, NewNode); 283193323Sed NewNode->getInstList().push_back(Comp); 284276479Sdim 285193323Sed BranchInst::Create(LBranch, RBranch, Comp, NewNode); 286193323Sed return NewNode; 287193323Sed} 288193323Sed 289193323Sed// newLeafBlock - Create a new leaf block for the binary lookup tree. It 290193323Sed// checks if the switch's value == the case's value. If not, then it 291193323Sed// jumps to the default branch. At this point in the tree, the value 292193323Sed// can't be another valid case value, so the jump to the "default" branch 293193323Sed// is warranted. 294193323Sed// 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"); 301193323Sed Function::iterator FI = OrigBlock; 302193323Sed F->getBasicBlockList().insert(++FI, NewLeaf); 303193323Sed 304193323Sed // Emit comparison 305276479Sdim ICmpInst* Comp = nullptr; 306193323Sed if (Leaf.Low == Leaf.High) { 307193323Sed // Make the seteq instruction... 308198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, 309198090Srdivacky Leaf.Low, "SwitchLeaf"); 310193323Sed } else { 311193323Sed // Make range comparison 312288943Sdim if (Leaf.Low->isMinValue(true /*isSigned*/)) { 313193323Sed // Val >= Min && Val <= Hi --> Val <= Hi 314198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, 315198090Srdivacky "SwitchLeaf"); 316288943Sdim } else if (Leaf.Low->isZero()) { 317193323Sed // Val >= 0 && Val <= Hi --> Val <=u Hi 318198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, 319198090Srdivacky "SwitchLeaf"); 320193323Sed } else { 321193323Sed // Emit V-Lo <=u Hi-Lo 322193323Sed Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); 323193323Sed Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 324193323Sed Val->getName()+".off", 325193323Sed NewLeaf); 326193323Sed Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); 327198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, 328198090Srdivacky "SwitchLeaf"); 329193323Sed } 330193323Sed } 331193323Sed 332193323Sed // Make the conditional branch... 333193323Sed BasicBlock* Succ = Leaf.BB; 334193323Sed BranchInst::Create(Succ, Default, Comp, NewLeaf); 335193323Sed 336193323Sed // If there were any PHI nodes in this successor, rewrite one entry 337193323Sed // from OrigBlock to come from NewLeaf. 338193323Sed for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 339193323Sed PHINode* PN = cast<PHINode>(I); 340193323Sed // Remove all but one incoming entries from the cluster 341288943Sdim uint64_t Range = Leaf.High->getSExtValue() - 342288943Sdim Leaf.Low->getSExtValue(); 343193323Sed for (uint64_t j = 0; j < Range; ++j) { 344193323Sed PN->removeIncomingValue(OrigBlock); 345193323Sed } 346193323Sed 347193323Sed int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 348193323Sed assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 349193323Sed PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 350193323Sed } 351193323Sed 352193323Sed return NewLeaf; 353193323Sed} 354193323Sed 355193323Sed// Clusterify - Transform simple list of Cases into list of CaseRange's 356193323Sedunsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 357261991Sdim unsigned numCmps = 0; 358193323Sed 359193323Sed // Start with "simple" cases 360261991Sdim for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) 361261991Sdim Cases.push_back(CaseRange(i.getCaseValue(), i.getCaseValue(), 362261991Sdim i.getCaseSuccessor())); 363234353Sdim 364261991Sdim std::sort(Cases.begin(), Cases.end(), CaseCmp()); 365261991Sdim 366261991Sdim // Merge case into clusters 367288943Sdim if (Cases.size() >= 2) { 368288943Sdim CaseItr I = Cases.begin(); 369288943Sdim for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) { 370288943Sdim int64_t nextValue = J->Low->getSExtValue(); 371288943Sdim int64_t currentValue = I->High->getSExtValue(); 372261991Sdim BasicBlock* nextBB = J->BB; 373261991Sdim BasicBlock* currentBB = I->BB; 374261991Sdim 375261991Sdim // If the two neighboring cases go to the same destination, merge them 376261991Sdim // into a single case. 377288943Sdim assert(nextValue > currentValue && "Cases should be strictly ascending"); 378288943Sdim if ((nextValue == currentValue + 1) && (currentBB == nextBB)) { 379261991Sdim I->High = J->High; 380288943Sdim // FIXME: Combine branch weights. 381288943Sdim } else if (++I != J) { 382288943Sdim *I = *J; 383261991Sdim } 384261991Sdim } 385288943Sdim Cases.erase(std::next(I), Cases.end()); 386288943Sdim } 387261991Sdim 388261991Sdim for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 389261991Sdim if (I->Low != I->High) 390193323Sed // A range counts double, since it requires two compares. 391193323Sed ++numCmps; 392193323Sed } 393193323Sed 394261991Sdim return numCmps; 395193323Sed} 396193323Sed 397193323Sed// processSwitchInst - Replace the specified switch instruction with a sequence 398193323Sed// of chained if-then insts in a balanced binary search. 399193323Sed// 400193323Sedvoid LowerSwitch::processSwitchInst(SwitchInst *SI) { 401193323Sed BasicBlock *CurBlock = SI->getParent(); 402193323Sed BasicBlock *OrigBlock = CurBlock; 403193323Sed Function *F = CurBlock->getParent(); 404226633Sdim Value *Val = SI->getCondition(); // The value we are switching on... 405193323Sed BasicBlock* Default = SI->getDefaultDest(); 406193323Sed 407288943Sdim // If there is only the default destination, just branch. 408234353Sdim if (!SI->getNumCases()) { 409288943Sdim BranchInst::Create(Default, CurBlock); 410288943Sdim SI->eraseFromParent(); 411193323Sed return; 412193323Sed } 413193323Sed 414288943Sdim // Prepare cases vector. 415288943Sdim CaseVector Cases; 416288943Sdim unsigned numCmps = Clusterify(Cases, SI); 417288943Sdim DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() 418288943Sdim << ". Total compares: " << numCmps << "\n"); 419288943Sdim DEBUG(dbgs() << "Cases: " << Cases << "\n"); 420288943Sdim (void)numCmps; 421288943Sdim 422288943Sdim ConstantInt *LowerBound = nullptr; 423288943Sdim ConstantInt *UpperBound = nullptr; 424288943Sdim std::vector<IntRange> UnreachableRanges; 425288943Sdim 426288943Sdim if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) { 427288943Sdim // Make the bounds tightly fitted around the case value range, becase we 428288943Sdim // know that the value passed to the switch must be exactly one of the case 429288943Sdim // values. 430288943Sdim assert(!Cases.empty()); 431288943Sdim LowerBound = Cases.front().Low; 432288943Sdim UpperBound = Cases.back().High; 433288943Sdim 434288943Sdim DenseMap<BasicBlock *, unsigned> Popularity; 435288943Sdim unsigned MaxPop = 0; 436288943Sdim BasicBlock *PopSucc = nullptr; 437288943Sdim 438288943Sdim IntRange R = { INT64_MIN, INT64_MAX }; 439288943Sdim UnreachableRanges.push_back(R); 440288943Sdim for (const auto &I : Cases) { 441288943Sdim int64_t Low = I.Low->getSExtValue(); 442288943Sdim int64_t High = I.High->getSExtValue(); 443288943Sdim 444288943Sdim IntRange &LastRange = UnreachableRanges.back(); 445288943Sdim if (LastRange.Low == Low) { 446288943Sdim // There is nothing left of the previous range. 447288943Sdim UnreachableRanges.pop_back(); 448288943Sdim } else { 449288943Sdim // Terminate the previous range. 450288943Sdim assert(Low > LastRange.Low); 451288943Sdim LastRange.High = Low - 1; 452288943Sdim } 453288943Sdim if (High != INT64_MAX) { 454288943Sdim IntRange R = { High + 1, INT64_MAX }; 455288943Sdim UnreachableRanges.push_back(R); 456288943Sdim } 457288943Sdim 458288943Sdim // Count popularity. 459288943Sdim int64_t N = High - Low + 1; 460288943Sdim unsigned &Pop = Popularity[I.BB]; 461288943Sdim if ((Pop += N) > MaxPop) { 462288943Sdim MaxPop = Pop; 463288943Sdim PopSucc = I.BB; 464288943Sdim } 465288943Sdim } 466288943Sdim#ifndef NDEBUG 467288943Sdim /* UnreachableRanges should be sorted and the ranges non-adjacent. */ 468288943Sdim for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end(); 469288943Sdim I != E; ++I) { 470288943Sdim assert(I->Low <= I->High); 471288943Sdim auto Next = I + 1; 472288943Sdim if (Next != E) { 473288943Sdim assert(Next->Low > I->High); 474288943Sdim } 475288943Sdim } 476288943Sdim#endif 477288943Sdim 478288943Sdim // Use the most popular block as the new default, reducing the number of 479288943Sdim // cases. 480288943Sdim assert(MaxPop > 0 && PopSucc); 481288943Sdim Default = PopSucc; 482288943Sdim Cases.erase(std::remove_if( 483288943Sdim Cases.begin(), Cases.end(), 484288943Sdim [PopSucc](const CaseRange &R) { return R.BB == PopSucc; }), 485288943Sdim Cases.end()); 486288943Sdim 487288943Sdim // If there are no cases left, just branch. 488288943Sdim if (Cases.empty()) { 489288943Sdim BranchInst::Create(Default, CurBlock); 490288943Sdim SI->eraseFromParent(); 491288943Sdim return; 492288943Sdim } 493288943Sdim } 494288943Sdim 495193323Sed // Create a new, empty default block so that the new hierarchy of 496193323Sed // if-then statements go to this and the PHI nodes are happy. 497288943Sdim BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); 498288943Sdim F->getBasicBlockList().insert(Default, NewDefault); 499288943Sdim BranchInst::Create(Default, NewDefault); 500193323Sed 501193323Sed // If there is an entry in any PHI nodes for the default edge, make sure 502193323Sed // to update them as well. 503193323Sed for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 504193323Sed PHINode *PN = cast<PHINode>(I); 505193323Sed int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 506193323Sed assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 507193323Sed PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 508193323Sed } 509193323Sed 510276479Sdim BasicBlock *SwitchBlock = 511276479Sdim switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val, 512288943Sdim OrigBlock, OrigBlock, NewDefault, UnreachableRanges); 513276479Sdim 514193323Sed // Branch to our shiny new if-then stuff... 515193323Sed BranchInst::Create(SwitchBlock, OrigBlock); 516193323Sed 517193323Sed // We are now done with the switch instruction, delete it. 518288943Sdim BasicBlock *OldDefault = SI->getDefaultDest(); 519193323Sed CurBlock->getInstList().erase(SI); 520276479Sdim 521288943Sdim // If the Default block has no more predecessors just remove it. 522288943Sdim if (pred_begin(OldDefault) == pred_end(OldDefault)) 523288943Sdim DeleteDeadBlock(OldDefault); 524193323Sed} 525