LowerSwitch.cpp revision 296417
1132744Skan//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// 290285Sobrien// 3169706Skan// The LLVM Compiler Infrastructure 418334Speter// 5132744Skan// This file is distributed under the University of Illinois Open Source 618334Speter// License. See LICENSE.TXT for details. 7132744Skan// 818334Speter//===----------------------------------------------------------------------===// 918334Speter// 1018334Speter// The LowerSwitch transformation rewrites switch instructions with a sequence 1118334Speter// of branches, which allows targets to get away with not implementing the 12132744Skan// switch instruction until it is convenient. 1318334Speter// 1418334Speter//===----------------------------------------------------------------------===// 1518334Speter 1618334Speter#include "llvm/Transforms/Scalar.h" 1718334Speter#include "llvm/ADT/STLExtras.h" 18132744Skan#include "llvm/IR/CFG.h" 19169706Skan#include "llvm/IR/Constants.h" 20169706Skan#include "llvm/IR/Function.h" 2118334Speter#include "llvm/IR/Instructions.h" 2218334Speter#include "llvm/IR/LLVMContext.h" 2318334Speter#include "llvm/Pass.h" 2418334Speter#include "llvm/Support/Compiler.h" 2518334Speter#include "llvm/Support/Debug.h" 2618334Speter#include "llvm/Support/raw_ostream.h" 2718334Speter#include "llvm/Transforms/Utils/BasicBlockUtils.h" 2818334Speter#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 2918334Speter#include <algorithm> 3018334Speterusing namespace llvm; 3118334Speter 3218334Speter#define DEBUG_TYPE "lower-switch" 3390285Sobrien 3490285Sobriennamespace { 3590285Sobrien struct IntRange { 3618334Speter int64_t Low, High; 3750654Sobrien }; 3850654Sobrien // Return true iff R is covered by Ranges. 3950654Sobrien static bool IsInRanges(const IntRange &R, 4090285Sobrien const std::vector<IntRange> &Ranges) { 4190285Sobrien // Note: Ranges must be sorted, non-overlapping and non-adjacent. 4290285Sobrien 4390285Sobrien // Find the first range whose High field is >= R.High, 44169706Skan // then check if the Low field is <= R.Low. If so, we 45132744Skan // have a Range that covers R. 4690285Sobrien auto I = std::lower_bound( 47169706Skan Ranges.begin(), Ranges.end(), R, 48132744Skan [](const IntRange &A, const IntRange &B) { return A.High < B.High; }); 4990285Sobrien return I != Ranges.end() && I->Low <= R.Low; 5090285Sobrien } 5190285Sobrien 5290285Sobrien /// Replace all SwitchInst instructions with chained branch instructions. 5390285Sobrien class LowerSwitch : public FunctionPass { 5490285Sobrien public: 5590285Sobrien static char ID; // Pass identification, replacement for typeid 5690285Sobrien LowerSwitch() : FunctionPass(ID) { 5790285Sobrien initializeLowerSwitchPass(*PassRegistry::getPassRegistry()); 5890285Sobrien } 5990285Sobrien 6090285Sobrien bool runOnFunction(Function &F) override; 6190285Sobrien 6290285Sobrien void getAnalysisUsage(AnalysisUsage &AU) const override { 6390285Sobrien // This is a cluster of orthogonal Transforms 6490285Sobrien AU.addPreserved<UnifyFunctionExitNodes>(); 6590285Sobrien AU.addPreservedID(LowerInvokePassID); 6690285Sobrien } 6790285Sobrien 6890285Sobrien struct CaseRange { 6990285Sobrien ConstantInt* Low; 7090285Sobrien ConstantInt* High; 7190285Sobrien BasicBlock* BB; 7290285Sobrien 7390285Sobrien CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb) 7490285Sobrien : Low(low), High(high), BB(bb) {} 7590285Sobrien }; 7690285Sobrien 7790285Sobrien typedef std::vector<CaseRange> CaseVector; 7890285Sobrien typedef std::vector<CaseRange>::iterator CaseItr; 7990285Sobrien private: 80132744Skan void processSwitchInst(SwitchInst *SI, SmallPtrSetImpl<BasicBlock*> &DeleteList); 81117407Skan 82117407Skan BasicBlock *switchConvert(CaseItr Begin, CaseItr End, 83117407Skan ConstantInt *LowerBound, ConstantInt *UpperBound, 84117407Skan Value *Val, BasicBlock *Predecessor, 85117407Skan BasicBlock *OrigBlock, BasicBlock *Default, 86117407Skan const std::vector<IntRange> &UnreachableRanges); 8750654Sobrien BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, BasicBlock *OrigBlock, 8850654Sobrien BasicBlock *Default); 8990285Sobrien unsigned Clusterify(CaseVector &Cases, SwitchInst *SI); 9050654Sobrien }; 9118334Speter 9218334Speter /// The comparison function for sorting the switch case values in the vector. 9318334Speter /// WARNING: Case ranges should be disjoint! 9490285Sobrien struct CaseCmp { 9518334Speter bool operator () (const LowerSwitch::CaseRange& C1, 96169706Skan const LowerSwitch::CaseRange& C2) { 9718334Speter 98169706Skan const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 99169706Skan const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 100169706Skan return CI1->getValue().slt(CI2->getValue()); 101169706Skan } 102132744Skan }; 10318334Speter} 104169706Skan 105117407Skanchar LowerSwitch::ID = 0; 106117407SkanINITIALIZE_PASS(LowerSwitch, "lowerswitch", 107117407Skan "Lower SwitchInst's to branches", false, false) 108117407Skan 109169706Skan// Publicly exposed interface to pass... 110117407Skanchar &llvm::LowerSwitchID = LowerSwitch::ID; 111117407Skan// createLowerSwitchPass - Interface to this file... 112117407SkanFunctionPass *llvm::createLowerSwitchPass() { 113117407Skan return new LowerSwitch(); 114117407Skan} 115117407Skan 116169706Skanbool LowerSwitch::runOnFunction(Function &F) { 117169706Skan bool Changed = false; 118117407Skan SmallPtrSet<BasicBlock*, 8> DeleteList; 11990285Sobrien 12090285Sobrien for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 12190285Sobrien BasicBlock *Cur = &*I++; // Advance over block so we don't traverse new blocks 12290285Sobrien 12390285Sobrien // If the block is a dead Default block that will be deleted later, don't 124117407Skan // waste time processing it. 12518334Speter if (DeleteList.count(Cur)) 126169706Skan continue; 127169706Skan 12852295Sobrien if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 129132744Skan Changed = true; 130132744Skan processSwitchInst(SI, DeleteList); 131132744Skan } 132132744Skan } 133219374Smm 134132744Skan for (BasicBlock* BB: DeleteList) { 135132744Skan DeleteDeadBlock(BB); 136132744Skan } 137132744Skan 138132744Skan return Changed; 139169706Skan} 140219374Smm 141169706Skan/// Used for debugging purposes. 142169706Skanstatic raw_ostream& operator<<(raw_ostream &O, 143169706Skan const LowerSwitch::CaseVector &C) 144132744Skan LLVM_ATTRIBUTE_USED; 145132744Skanstatic raw_ostream& operator<<(raw_ostream &O, 14652295Sobrien const LowerSwitch::CaseVector &C) { 14752295Sobrien O << "["; 14890285Sobrien 14990285Sobrien for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 150169706Skan E = C.end(); B != E; ) { 151169706Skan O << *B->Low << " -" << *B->High; 15290285Sobrien if (++B != E) O << ", "; 153117407Skan } 15490285Sobrien 15590285Sobrien return O << "]"; 15690285Sobrien} 15790285Sobrien 15890285Sobrien/// \brief Update the first occurrence of the "switch statement" BB in the PHI 15990285Sobrien/// node with the "new" BB. The other occurrences will: 160117407Skan/// 161169706Skan/// 1) Be updated by subsequent calls to this function. Switch statements may 162132744Skan/// have more than one outcoming edge into the same BB if they all have the same 163169706Skan/// value. When the switch statement is converted these incoming edges are now 164169706Skan/// coming from multiple BBs. 165169706Skan/// 2) Removed if subsequent incoming values now share the same case, i.e., 166237021Spfg/// multiple outcome edges are condensed into one. This is necessary to keep the 167169706Skan/// number of phi values equal to the number of branches to SuccBB. 168169706Skanstatic void fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB, 169169706Skan unsigned NumMergedCases) { 170237021Spfg for (BasicBlock::iterator I = SuccBB->begin(), 17152295Sobrien IE = SuccBB->getFirstNonPHI()->getIterator(); 172132744Skan I != IE; ++I) { 173132744Skan PHINode *PN = cast<PHINode>(I); 174132744Skan 175132744Skan // Only update the first occurrence. 176132744Skan unsigned Idx = 0, E = PN->getNumIncomingValues(); 17790285Sobrien unsigned LocalNumMergedCases = NumMergedCases; 17890285Sobrien for (; Idx != E; ++Idx) { 17990285Sobrien if (PN->getIncomingBlock(Idx) == OrigBB) { 180169706Skan PN->setIncomingBlock(Idx, NewBB); 181132744Skan break; 182132744Skan } 183132744Skan } 184132744Skan 185132744Skan // Remove additional occurrences coming from condensed cases and keep the 186132744Skan // number of incoming values equal to the number of branches to SuccBB. 187169706Skan SmallVector<unsigned, 8> Indices; 188169706Skan for (++Idx; LocalNumMergedCases > 0 && Idx < E; ++Idx) 189169706Skan if (PN->getIncomingBlock(Idx) == OrigBB) { 190132744Skan Indices.push_back(Idx); 191132744Skan LocalNumMergedCases--; 192132744Skan } 193132744Skan // Remove incoming values in the reverse order to prevent invalidating 194132744Skan // *successive* index. 195132744Skan for (auto III = Indices.rbegin(), IIE = Indices.rend(); III != IIE; ++III) 196132744Skan PN->removeIncomingValue(*III); 197132744Skan } 198132744Skan} 199132744Skan 200132744Skan/// Convert the switch statement into a binary lookup of the case values. 201132744Skan/// The function recursively builds this tree. LowerBound and UpperBound are 202132744Skan/// used to keep track of the bounds for Val that have already been checked by 203132744Skan/// a block emitted by one of the previous calls to switchConvert in the call 204132744Skan/// stack. 205132744SkanBasicBlock * 206132744SkanLowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound, 207132744Skan ConstantInt *UpperBound, Value *Val, 208132744Skan BasicBlock *Predecessor, BasicBlock *OrigBlock, 209132744Skan BasicBlock *Default, 210169706Skan const std::vector<IntRange> &UnreachableRanges) { 211132744Skan unsigned Size = End - Begin; 212132744Skan 213132744Skan if (Size == 1) { 214132744Skan // Check if the Case Range is perfectly squeezed in between 215132744Skan // already checked Upper and Lower bounds. If it is then we can avoid 21690285Sobrien // emitting the code that checks if the value actually falls in the range 217132744Skan // because the bounds already tell us so. 218132744Skan if (Begin->Low == LowerBound && Begin->High == UpperBound) { 219132744Skan unsigned NumMergedCases = 0; 220132744Skan if (LowerBound && UpperBound) 221169706Skan NumMergedCases = 222169706Skan UpperBound->getSExtValue() - LowerBound->getSExtValue(); 223169706Skan fixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases); 224169706Skan return Begin->BB; 225169706Skan } 22652295Sobrien return newLeafBlock(*Begin, Val, OrigBlock, Default); 22790285Sobrien } 22890285Sobrien 22990285Sobrien unsigned Mid = Size / 2; 23090285Sobrien std::vector<CaseRange> LHS(Begin, Begin + Mid); 23190285Sobrien DEBUG(dbgs() << "LHS: " << LHS << "\n"); 23290285Sobrien std::vector<CaseRange> RHS(Begin + Mid, End); 233117407Skan DEBUG(dbgs() << "RHS: " << RHS << "\n"); 234169706Skan 235169706Skan CaseRange &Pivot = *(Begin + Mid); 236117407Skan DEBUG(dbgs() << "Pivot ==> " 237117407Skan << Pivot.Low->getValue() 238169706Skan << " -" << Pivot.High->getValue() << "\n"); 239169706Skan 240237021Spfg // NewLowerBound here should never be the integer minimal value. 241169706Skan // This is because it is computed from a case range that is never 24296294Sobrien // the smallest, so there is always a case range that has at least 243117407Skan // a smaller value. 244117407Skan ConstantInt *NewLowerBound = Pivot.Low; 24590285Sobrien 246132744Skan // Because NewLowerBound is never the smallest representable integer 247132744Skan // it is safe here to subtract one. 248132744Skan ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(), 24990285Sobrien NewLowerBound->getValue() - 1); 250117407Skan 251117407Skan if (!UnreachableRanges.empty()) { 252117407Skan // Check if the gap between LHS's highest and NewLowerBound is unreachable. 253117407Skan int64_t GapLow = LHS.back().High->getSExtValue() + 1; 25450654Sobrien int64_t GapHigh = NewLowerBound->getSExtValue() - 1; 255117407Skan IntRange Gap = { GapLow, GapHigh }; 256117407Skan if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges)) 257117407Skan NewUpperBound = LHS.back().High; 258117407Skan } 25950654Sobrien 260146908Skan DEBUG(dbgs() << "LHS Bounds ==> "; 261146908Skan if (LowerBound) { 262146908Skan dbgs() << LowerBound->getSExtValue(); 263146908Skan } else { 26418334Speter dbgs() << "NONE"; 26518334Speter } 26618334Speter dbgs() << " - " << NewUpperBound->getSExtValue() << "\n"; 26718334Speter dbgs() << "RHS Bounds ==> "; 26818334Speter dbgs() << NewLowerBound->getSExtValue() << " - "; 26918334Speter if (UpperBound) { 27018334Speter dbgs() << UpperBound->getSExtValue() << "\n"; 27118334Speter } else { 27218334Speter dbgs() << "NONE\n"; 27318334Speter }); 27418334Speter 27550654Sobrien // Create a new node that checks if the value is < pivot. Go to the 27690285Sobrien // left branch if it is and right branch if not. 27790285Sobrien Function* F = OrigBlock->getParent(); 27850654Sobrien BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock"); 279169706Skan 280169706Skan ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, 281169706Skan Val, Pivot.Low, "Pivot"); 282169706Skan 283169706Skan BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound, 284169706Skan NewUpperBound, Val, NewNode, OrigBlock, 285169706Skan Default, UnreachableRanges); 286169706Skan BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound, 287169706Skan UpperBound, Val, NewNode, OrigBlock, 288169706Skan Default, UnreachableRanges); 289169706Skan 290169706Skan F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewNode); 291169706Skan NewNode->getInstList().push_back(Comp); 292169706Skan 293132744Skan BranchInst::Create(LBranch, RBranch, Comp, NewNode); 294132744Skan return NewNode; 295169706Skan} 296169706Skan 297132744Skan/// Create a new leaf block for the binary lookup tree. It checks if the 29850654Sobrien/// switch's value == the case's value. If not, then it jumps to the default 29950654Sobrien/// branch. At this point in the tree, the value can't be another valid case 30050654Sobrien/// value, so the jump to the "default" branch is warranted. 301169706SkanBasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, 302132744Skan BasicBlock* OrigBlock, 303132744Skan BasicBlock* Default) 304132744Skan{ 305132744Skan Function* F = OrigBlock->getParent(); 306132744Skan BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock"); 307132744Skan F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewLeaf); 308132744Skan 309132744Skan // Emit comparison 310132744Skan ICmpInst* Comp = nullptr; 311132744Skan if (Leaf.Low == Leaf.High) { 312132744Skan // Make the seteq instruction... 313132744Skan Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, 31490285Sobrien Leaf.Low, "SwitchLeaf"); 31590285Sobrien } else { 31690285Sobrien // Make range comparison 31790285Sobrien if (Leaf.Low->isMinValue(true /*isSigned*/)) { 318169706Skan // Val >= Min && Val <= Hi --> Val <= Hi 319169706Skan Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, 320169706Skan "SwitchLeaf"); 321169706Skan } else if (Leaf.Low->isZero()) { 322169706Skan // Val >= 0 && Val <= Hi --> Val <=u Hi 323169706Skan Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, 324169706Skan "SwitchLeaf"); 325169706Skan } else { 32650654Sobrien // Emit V-Lo <=u Hi-Lo 327169706Skan Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); 32818334Speter Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 329117407Skan Val->getName()+".off", 330117407Skan NewLeaf); 331117407Skan Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); 332117407Skan Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, 333117407Skan "SwitchLeaf"); 334132744Skan } 335117407Skan } 336132744Skan 337117407Skan // Make the conditional branch... 338117407Skan BasicBlock* Succ = Leaf.BB; 339117407Skan BranchInst::Create(Succ, Default, Comp, NewLeaf); 340117407Skan 341132744Skan // If there were any PHI nodes in this successor, rewrite one entry 342132744Skan // from OrigBlock to come from NewLeaf. 343132744Skan for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 344117407Skan PHINode* PN = cast<PHINode>(I); 345117407Skan // Remove all but one incoming entries from the cluster 346117407Skan uint64_t Range = Leaf.High->getSExtValue() - 347117407Skan Leaf.Low->getSExtValue(); 348117407Skan for (uint64_t j = 0; j < Range; ++j) { 349117407Skan PN->removeIncomingValue(OrigBlock); 350117407Skan } 351117407Skan 352117407Skan int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 353117407Skan assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 354132744Skan PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 355132744Skan } 356117407Skan 357117407Skan return NewLeaf; 358117407Skan} 359117407Skan 360117407Skan/// Transform simple list of Cases into list of CaseRange's. 361117407Skanunsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 362117407Skan unsigned numCmps = 0; 363117407Skan 364132744Skan // Start with "simple" cases 365117407Skan for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) 366117407Skan Cases.push_back(CaseRange(i.getCaseValue(), i.getCaseValue(), 367117407Skan i.getCaseSuccessor())); 368117407Skan 369117407Skan std::sort(Cases.begin(), Cases.end(), CaseCmp()); 370117407Skan 371132744Skan // Merge case into clusters 372117407Skan if (Cases.size() >= 2) { 373117407Skan CaseItr I = Cases.begin(); 374117407Skan for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) { 375117407Skan int64_t nextValue = J->Low->getSExtValue(); 376117407Skan int64_t currentValue = I->High->getSExtValue(); 377117407Skan BasicBlock* nextBB = J->BB; 378117407Skan BasicBlock* currentBB = I->BB; 379117407Skan 380117407Skan // If the two neighboring cases go to the same destination, merge them 381219374Smm // into a single case. 382219374Smm assert(nextValue > currentValue && "Cases should be strictly ascending"); 383219374Smm if ((nextValue == currentValue + 1) && (currentBB == nextBB)) { 384219374Smm I->High = J->High; 385117407Skan // FIXME: Combine branch weights. 386117407Skan } else if (++I != J) { 387117407Skan *I = *J; 388132744Skan } 389117407Skan } 390132744Skan Cases.erase(std::next(I), Cases.end()); 391117407Skan } 392117407Skan 393117407Skan for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 394117407Skan if (I->Low != I->High) 395117407Skan // A range counts double, since it requires two compares. 396148163Sobrien ++numCmps; 397148163Sobrien } 398117407Skan 399117407Skan return numCmps; 400132744Skan} 401132744Skan 402117407Skan/// Replace the specified switch instruction with a sequence of chained if-then 403117407Skan/// insts in a balanced binary search. 404169706Skanvoid LowerSwitch::processSwitchInst(SwitchInst *SI, 405169706Skan SmallPtrSetImpl<BasicBlock*> &DeleteList) { 406219374Smm BasicBlock *CurBlock = SI->getParent(); 407219374Smm BasicBlock *OrigBlock = CurBlock; 408117407Skan Function *F = CurBlock->getParent(); 409117407Skan Value *Val = SI->getCondition(); // The value we are switching on... 410117407Skan BasicBlock* Default = SI->getDefaultDest(); 411117407Skan 412117407Skan // If there is only the default destination, just branch. 413117407Skan if (!SI->getNumCases()) { 414117407Skan BranchInst::Create(Default, CurBlock); 415117407Skan SI->eraseFromParent(); 416117407Skan return; 417117407Skan } 418117407Skan 419132744Skan // Prepare cases vector. 420169706Skan CaseVector Cases; 421219639Smm unsigned numCmps = Clusterify(Cases, SI); 422219639Smm DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() 423117407Skan << ". Total compares: " << numCmps << "\n"); 424117407Skan DEBUG(dbgs() << "Cases: " << Cases << "\n"); 425117407Skan (void)numCmps; 426117407Skan 427117407Skan ConstantInt *LowerBound = nullptr; 428117407Skan ConstantInt *UpperBound = nullptr; 429117407Skan std::vector<IntRange> UnreachableRanges; 430117407Skan 431117407Skan if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) { 432117407Skan // Make the bounds tightly fitted around the case value range, because we 433117407Skan // know that the value passed to the switch must be exactly one of the case 434117407Skan // values. 435117407Skan assert(!Cases.empty()); 436117407Skan LowerBound = Cases.front().Low; 437117407Skan UpperBound = Cases.back().High; 438117407Skan 439117407Skan DenseMap<BasicBlock *, unsigned> Popularity; 440117407Skan unsigned MaxPop = 0; 441117407Skan BasicBlock *PopSucc = nullptr; 442117407Skan 443117407Skan IntRange R = { INT64_MIN, INT64_MAX }; 444117407Skan UnreachableRanges.push_back(R); 445117407Skan for (const auto &I : Cases) { 446117407Skan int64_t Low = I.Low->getSExtValue(); 447117407Skan int64_t High = I.High->getSExtValue(); 448117407Skan 449117407Skan IntRange &LastRange = UnreachableRanges.back(); 450219374Smm if (LastRange.Low == Low) { 451219374Smm // There is nothing left of the previous range. 452219374Smm UnreachableRanges.pop_back(); 453219374Smm } else { 454219374Smm // Terminate the previous range. 455117407Skan assert(Low > LastRange.Low); 456117407Skan LastRange.High = Low - 1; 457117407Skan } 458117407Skan if (High != INT64_MAX) { 459117407Skan IntRange R = { High + 1, INT64_MAX }; 460117407Skan UnreachableRanges.push_back(R); 461117407Skan } 462117407Skan 463117407Skan // Count popularity. 464117407Skan int64_t N = High - Low + 1; 465117407Skan unsigned &Pop = Popularity[I.BB]; 466117407Skan if ((Pop += N) > MaxPop) { 467117407Skan MaxPop = Pop; 468117407Skan PopSucc = I.BB; 469148163Sobrien } 470148163Sobrien } 471117407Skan#ifndef NDEBUG 472117407Skan /* UnreachableRanges should be sorted and the ranges non-adjacent. */ 473132744Skan for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end(); 474132744Skan I != E; ++I) { 475132744Skan assert(I->Low <= I->High); 476132744Skan auto Next = I + 1; 477132744Skan if (Next != E) { 478117407Skan assert(Next->Low > I->High); 479117407Skan } 480117407Skan } 481117407Skan#endif 482117407Skan 483169706Skan // Use the most popular block as the new default, reducing the number of 484169706Skan // cases. 485169706Skan assert(MaxPop > 0 && PopSucc); 486169706Skan Default = PopSucc; 487169706Skan Cases.erase(std::remove_if( 488219374Smm Cases.begin(), Cases.end(), 489219374Smm [PopSucc](const CaseRange &R) { return R.BB == PopSucc; }), 490219374Smm Cases.end()); 491219374Smm 492219374Smm // If there are no cases left, just branch. 493117407Skan if (Cases.empty()) { 494117407Skan BranchInst::Create(Default, CurBlock); 495117407Skan SI->eraseFromParent(); 49690285Sobrien return; 49790285Sobrien } 49890285Sobrien } 49990285Sobrien 50090285Sobrien // Create a new, empty default block so that the new hierarchy of 50190285Sobrien // if-then statements go to this and the PHI nodes are happy. 50290285Sobrien BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); 50390285Sobrien F->getBasicBlockList().insert(Default->getIterator(), NewDefault); 504219374Smm BranchInst::Create(Default, NewDefault); 505219374Smm 506219374Smm // If there is an entry in any PHI nodes for the default edge, make sure 507219374Smm // to update them as well. 508219374Smm for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 509219374Smm PHINode *PN = cast<PHINode>(I); 510219374Smm int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 511219374Smm assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 512219374Smm PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 513219374Smm } 514219374Smm 515219374Smm BasicBlock *SwitchBlock = 51650654Sobrien switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val, 51790285Sobrien OrigBlock, OrigBlock, NewDefault, UnreachableRanges); 51890285Sobrien 519219374Smm // Branch to our shiny new if-then stuff... 520132744Skan BranchInst::Create(SwitchBlock, OrigBlock); 521169706Skan 522237021Spfg // We are now done with the switch instruction, delete it. 52350654Sobrien BasicBlock *OldDefault = SI->getDefaultDest(); 52450654Sobrien CurBlock->getInstList().erase(SI); 52590285Sobrien 52650654Sobrien // If the Default block has no more predecessors just add it to DeleteList. 52750654Sobrien if (pred_begin(OldDefault) == pred_end(OldDefault)) 52850654Sobrien DeleteList.insert(OldDefault); 52950654Sobrien} 53050654Sobrien