LowerSwitch.cpp revision bf9eaddfb0642e49bc2f3835765a9782ff48c76e
114383485ac546e369b11797b42bc20831b6db57bChris Lattner//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 914383485ac546e369b11797b42bc20831b6db57bChris Lattner// 1014383485ac546e369b11797b42bc20831b6db57bChris Lattner// The LowerSwitch transformation rewrites switch statements with a sequence of 1114383485ac546e369b11797b42bc20831b6db57bChris Lattner// branches, which allows targets to get away with not implementing the switch 1214383485ac546e369b11797b42bc20831b6db57bChris Lattner// statement until it is convenient. 1314383485ac546e369b11797b42bc20831b6db57bChris Lattner// 1414383485ac546e369b11797b42bc20831b6db57bChris Lattner//===----------------------------------------------------------------------===// 1514383485ac546e369b11797b42bc20831b6db57bChris Lattner 1614383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Transforms/Scalar.h" 17ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner#include "llvm/Constants.h" 1814383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Function.h" 1914383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/iTerminators.h" 2014383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/iOperators.h" 2114383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/iPHINode.h" 2214383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Pass.h" 23ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner#include "Support/Debug.h" 2414383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "Support/Statistic.h" 25d7456026629fc1760a45e6e955e9834246493147Chris Lattnerusing namespace llvm; 26d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2714383485ac546e369b11797b42bc20831b6db57bChris Lattnernamespace { 2814383485ac546e369b11797b42bc20831b6db57bChris Lattner Statistic<> NumLowered("lowerswitch", "Number of SwitchInst's replaced"); 2914383485ac546e369b11797b42bc20831b6db57bChris Lattner 3014383485ac546e369b11797b42bc20831b6db57bChris Lattner /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch 3114383485ac546e369b11797b42bc20831b6db57bChris Lattner /// instructions. Note that this cannot be a BasicBlock pass because it 3214383485ac546e369b11797b42bc20831b6db57bChris Lattner /// modifies the CFG! 33ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner class LowerSwitch : public FunctionPass { 34ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner public: 3514383485ac546e369b11797b42bc20831b6db57bChris Lattner bool runOnFunction(Function &F); 36ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner typedef std::pair<Constant*, BasicBlock*> Case; 37ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner typedef std::vector<Case>::iterator CaseItr; 38ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner private: 3914383485ac546e369b11797b42bc20831b6db57bChris Lattner void processSwitchInst(SwitchInst *SI); 40ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 41ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* switchConvert(CaseItr Begin, CaseItr End, Value* Val, 42ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* OrigBlock, BasicBlock* Default); 43ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* newLeafBlock(Case& Leaf, Value* Val, 44ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* OrigBlock, BasicBlock* Default); 45ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner }; 46ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 47ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner /// The comparison function for sorting the switch case values in the vector. 48ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner struct CaseCmp { 49ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner bool operator () (const LowerSwitch::Case& C1, 50ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner const LowerSwitch::Case& C2) { 51ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner if (const ConstantUInt* U1 = dyn_cast<const ConstantUInt>(C1.first)) 52ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return U1->getValue() < cast<const ConstantUInt>(C2.first)->getValue(); 53ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 54ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner const ConstantSInt* S1 = dyn_cast<const ConstantSInt>(C1.first); 55ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return S1->getValue() < cast<const ConstantSInt>(C2.first)->getValue(); 56ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner } 5714383485ac546e369b11797b42bc20831b6db57bChris Lattner }; 5814383485ac546e369b11797b42bc20831b6db57bChris Lattner 5914383485ac546e369b11797b42bc20831b6db57bChris Lattner RegisterOpt<LowerSwitch> 6014383485ac546e369b11797b42bc20831b6db57bChris Lattner X("lowerswitch", "Lower SwitchInst's to branches"); 6114383485ac546e369b11797b42bc20831b6db57bChris Lattner} 6214383485ac546e369b11797b42bc20831b6db57bChris Lattner 6314383485ac546e369b11797b42bc20831b6db57bChris Lattner// createLowerSwitchPass - Interface to this file... 64d7456026629fc1760a45e6e955e9834246493147Chris LattnerFunctionPass *llvm::createLowerSwitchPass() { 6514383485ac546e369b11797b42bc20831b6db57bChris Lattner return new LowerSwitch(); 6614383485ac546e369b11797b42bc20831b6db57bChris Lattner} 6714383485ac546e369b11797b42bc20831b6db57bChris Lattner 6814383485ac546e369b11797b42bc20831b6db57bChris Lattnerbool LowerSwitch::runOnFunction(Function &F) { 6914383485ac546e369b11797b42bc20831b6db57bChris Lattner bool Changed = false; 7014383485ac546e369b11797b42bc20831b6db57bChris Lattner 7114383485ac546e369b11797b42bc20831b6db57bChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 7214383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 7314383485ac546e369b11797b42bc20831b6db57bChris Lattner 7414383485ac546e369b11797b42bc20831b6db57bChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 7514383485ac546e369b11797b42bc20831b6db57bChris Lattner Changed = true; 7614383485ac546e369b11797b42bc20831b6db57bChris Lattner processSwitchInst(SI); 7714383485ac546e369b11797b42bc20831b6db57bChris Lattner } 7814383485ac546e369b11797b42bc20831b6db57bChris Lattner } 7914383485ac546e369b11797b42bc20831b6db57bChris Lattner 8014383485ac546e369b11797b42bc20831b6db57bChris Lattner return Changed; 8114383485ac546e369b11797b42bc20831b6db57bChris Lattner} 8214383485ac546e369b11797b42bc20831b6db57bChris Lattner 83ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// operator<< - Used for debugging purposes. 84ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// 85d7456026629fc1760a45e6e955e9834246493147Chris Lattnerstd::ostream& operator<<(std::ostream &O, 86d7456026629fc1760a45e6e955e9834246493147Chris Lattner const std::vector<LowerSwitch::Case> &C) { 87ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner O << "["; 88ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 89d7456026629fc1760a45e6e955e9834246493147Chris Lattner for (std::vector<LowerSwitch::Case>::const_iterator B = C.begin(), 90d7456026629fc1760a45e6e955e9834246493147Chris Lattner E = C.end(); B != E; ) { 91ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner O << *B->first; 92ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner if (++B != E) O << ", "; 93ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner } 94ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 95ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return O << "]"; 96ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 97ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 98ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// switchConvert - Convert the switch statement into a binary lookup of 99ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// the case values. The function recursively builds this tree. 100ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// 101ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris LattnerBasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, 102ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Value* Val, BasicBlock* OrigBlock, 103ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Default) 104ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner{ 105ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner unsigned Size = End - Begin; 106ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 107ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner if (Size == 1) 108ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return newLeafBlock(*Begin, Val, OrigBlock, Default); 109ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 110ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner unsigned Mid = Size / 2; 111ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner std::vector<Case> LHS(Begin, Begin + Mid); 112ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner DEBUG(std::cerr << "LHS: " << LHS << "\n"); 113ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner std::vector<Case> RHS(Begin + Mid, End); 114ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner DEBUG(std::cerr << "RHS: " << RHS << "\n"); 115ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 116ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Case& Pivot = *(Begin + Mid); 117ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner DEBUG(std::cerr << "Pivot ==> " 118940ff563f716c528e242caa9af06dd02407b41d0Chris Lattner << (int64_t)cast<ConstantInt>(Pivot.first)->getRawValue() 119940ff563f716c528e242caa9af06dd02407b41d0Chris Lattner << "\n"); 120ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 121ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val, 122ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner OrigBlock, Default); 123ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val, 124ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner OrigBlock, Default); 125ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 126ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Create a new node that checks if the value is < pivot. Go to the 127ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // left branch if it is and right branch if not. 128ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Function* F = OrigBlock->getParent(); 129ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* NewNode = new BasicBlock("NodeBlock"); 130ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner F->getBasicBlockList().insert(OrigBlock->getNext(), NewNode); 131ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 132ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner SetCondInst* Comp = new SetCondInst(Instruction::SetLT, Val, Pivot.first, 133ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner "Pivot"); 134ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner NewNode->getInstList().push_back(Comp); 135f8485c643412dbff46fe87ea2867445169a5c28eChris Lattner new BranchInst(LBranch, RBranch, Comp, NewNode); 136ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return NewNode; 137ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 138ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 139ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// newLeafBlock - Create a new leaf block for the binary lookup tree. It 140ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// checks if the switch's value == the case's value. If not, then it 141ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// jumps to the default branch. At this point in the tree, the value 142ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// can't be another valid case value, so the jump to the "default" branch 143ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// is warranted. 144ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// 145ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris LattnerBasicBlock* LowerSwitch::newLeafBlock(Case& Leaf, Value* Val, 146ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* OrigBlock, 147ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Default) 148ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner{ 149ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Function* F = OrigBlock->getParent(); 150ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* NewLeaf = new BasicBlock("LeafBlock"); 151ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner F->getBasicBlockList().insert(OrigBlock->getNext(), NewLeaf); 152ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 153ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Make the seteq instruction... 154ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner SetCondInst* Comp = new SetCondInst(Instruction::SetEQ, Val, 155ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Leaf.first, "SwitchLeaf"); 156ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner NewLeaf->getInstList().push_back(Comp); 157ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 158ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Make the conditional branch... 159ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Succ = Leaf.second; 160f8485c643412dbff46fe87ea2867445169a5c28eChris Lattner new BranchInst(Succ, Default, Comp, NewLeaf); 161ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 162ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // If there were any PHI nodes in this successor, rewrite one entry 163ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // from OrigBlock to come from NewLeaf. 164ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner for (BasicBlock::iterator I = Succ->begin(); 165ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner PHINode* PN = dyn_cast<PHINode>(I); ++I) { 166ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 167ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 168ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 169ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner } 170ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 171ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return NewLeaf; 172ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 173ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 17414383485ac546e369b11797b42bc20831b6db57bChris Lattner// processSwitchInst - Replace the specified switch instruction with a sequence 175ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// of chained if-then insts in a balanced binary search. 17614383485ac546e369b11797b42bc20831b6db57bChris Lattner// 17714383485ac546e369b11797b42bc20831b6db57bChris Lattnervoid LowerSwitch::processSwitchInst(SwitchInst *SI) { 17814383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *CurBlock = SI->getParent(); 17914383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *OrigBlock = CurBlock; 18014383485ac546e369b11797b42bc20831b6db57bChris Lattner Function *F = CurBlock->getParent(); 18114383485ac546e369b11797b42bc20831b6db57bChris Lattner Value *Val = SI->getOperand(0); // The value we are switching on... 182ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Default = SI->getDefaultDest(); 18314383485ac546e369b11797b42bc20831b6db57bChris Lattner 18444bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner // If there is only the default destination, don't bother with the code below. 18544bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner if (SI->getNumOperands() == 2) { 186108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner new BranchInst(SI->getDefaultDest(), CurBlock); 187bf9eaddfb0642e49bc2f3835765a9782ff48c76eChris Lattner CurBlock->getInstList().erase(SI); 18844bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner return; 18944bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner } 19044bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner 191ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Create a new, empty default block so that the new hierarchy of 192ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // if-then statements go to this and the PHI nodes are happy. 193ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* NewDefault = new BasicBlock("NewDefault"); 194ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner F->getBasicBlockList().insert(Default, NewDefault); 19514383485ac546e369b11797b42bc20831b6db57bChris Lattner 196108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner new BranchInst(Default, NewDefault); 19720af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner 198ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // If there is an entry in any PHI nodes for the default edge, make sure 199ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // to update them as well. 200ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner for (BasicBlock::iterator I = Default->begin(); 201ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) { 202ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 203ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 204ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 20514383485ac546e369b11797b42bc20831b6db57bChris Lattner } 20614383485ac546e369b11797b42bc20831b6db57bChris Lattner 207ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner std::vector<Case> Cases; 208ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 209ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Expand comparisons for all of the non-default cases... 210ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner for (unsigned i = 1; i < SI->getNumSuccessors(); ++i) 211ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Cases.push_back(Case(SI->getSuccessorValue(i), SI->getSuccessor(i))); 212ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 213ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner std::sort(Cases.begin(), Cases.end(), CaseCmp()); 214ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner DEBUG(std::cerr << "Cases: " << Cases << "\n"); 215ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val, 216ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner OrigBlock, NewDefault); 217ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 218ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Branch to our shiny new if-then stuff... 219108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner new BranchInst(SwitchBlock, OrigBlock); 220ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 22114383485ac546e369b11797b42bc20831b6db57bChris Lattner // We are now done with the switch instruction, delete it. 222bf9eaddfb0642e49bc2f3835765a9782ff48c76eChris Lattner CurBlock->getInstList().erase(SI); 22314383485ac546e369b11797b42bc20831b6db57bChris Lattner} 224