LowerSwitch.cpp revision 0aa32d5d0ff6cd65b6cff957858a79e2d2a614bd
114383485ac546e369b11797b42bc20831b6db57bChris Lattner//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 914383485ac546e369b11797b42bc20831b6db57bChris Lattner// 10c86b67742a3298c0a5a715b57a64f11107b8a3f2Gordon Henriksen// The LowerSwitch transformation rewrites switch instructions with a sequence 11c86b67742a3298c0a5a715b57a64f11107b8a3f2Gordon Henriksen// of branches, which allows targets to get away with not implementing the 12c86b67742a3298c0a5a715b57a64f11107b8a3f2Gordon Henriksen// switch instruction until it is convenient. 1314383485ac546e369b11797b42bc20831b6db57bChris Lattner// 1414383485ac546e369b11797b42bc20831b6db57bChris Lattner//===----------------------------------------------------------------------===// 1514383485ac546e369b11797b42bc20831b6db57bChris Lattner 1614383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Transforms/Scalar.h" 178d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 18ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner#include "llvm/Constants.h" 1914383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Function.h" 20d8e1eea678833cc2b15e4ea69a5a403ba9c3b013Misha Brukman#include "llvm/Instructions.h" 210a205a459884ec745df1c529396dd921f029dafdOwen Anderson#include "llvm/LLVMContext.h" 2214383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Pass.h" 23b61f2f061feefd79623fadd21eee4f195b0b8e56Dan Gohman#include "llvm/ADT/STLExtras.h" 24a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 25f5a86f45e75ec744c203270ffa03659eb0a220c1Nick Lewycky#include "llvm/Support/Debug.h" 26944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner#include "llvm/Support/raw_ostream.h" 2720aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 28d7456026629fc1760a45e6e955e9834246493147Chris Lattnerusing namespace llvm; 29d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3014383485ac546e369b11797b42bc20831b6db57bChris Lattnernamespace { 3114383485ac546e369b11797b42bc20831b6db57bChris Lattner /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch 32473fc96889ff8d0862a8fea16c4a5b9252e2d44dChris Lattner /// instructions. 336726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class LowerSwitch : public FunctionPass { 34ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner public: 35ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 36081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson LowerSwitch() : FunctionPass(ID) { 37081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLowerSwitchPass(*PassRegistry::getPassRegistry()); 38081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 39794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 408d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner virtual bool runOnFunction(Function &F); 41ed96fe8c79b36a38bd9280438656ee539276fb41Chris Lattner 428d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 43bed2946a96ecb15b0b636fa74cb26ce61b1c648eAnton Korobeynikov // This is a cluster of orthogonal Transforms 448d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner AU.addPreserved<UnifyFunctionExitNodes>(); 4560493c3f4ff9b20f43a3abc605bc64642de75b59Dan Gohman AU.addPreserved("mem2reg"); 46ed96fe8c79b36a38bd9280438656ee539276fb41Chris Lattner AU.addPreservedID(LowerInvokePassID); 478d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner } 48e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 49e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov struct CaseRange { 50e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Constant* Low; 51e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Constant* High; 52e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov BasicBlock* BB; 53e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 54473fc96889ff8d0862a8fea16c4a5b9252e2d44dChris Lattner CaseRange(Constant *low = 0, Constant *high = 0, BasicBlock *bb = 0) : 55c4558fde76bdb17bff28375fe20ee02e027095b8Jeff Cohen Low(low), High(high), BB(bb) { } 56e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov }; 57e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 58e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov typedef std::vector<CaseRange> CaseVector; 59e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov typedef std::vector<CaseRange>::iterator CaseItr; 60ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner private: 6114383485ac546e369b11797b42bc20831b6db57bChris Lattner void processSwitchInst(SwitchInst *SI); 62ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 63ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* switchConvert(CaseItr Begin, CaseItr End, Value* Val, 64ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* OrigBlock, BasicBlock* Default); 65e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov BasicBlock* newLeafBlock(CaseRange& Leaf, Value* Val, 66ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* OrigBlock, BasicBlock* Default); 67e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov unsigned Clusterify(CaseVector& Cases, SwitchInst *SI); 68ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner }; 6914383485ac546e369b11797b42bc20831b6db57bChris Lattner} 7014383485ac546e369b11797b42bc20831b6db57bChris Lattner 71844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LowerSwitch::ID = 0; 7202dd53e1c5b941ca5f60fca1b95ebcaf9ccd1dfcOwen AndersonINITIALIZE_PASS(LowerSwitch, "lowerswitch", 73ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Lower SwitchInst's to branches", false, false) 74844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 757a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// Publicly exposed interface to pass... 7690c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::LowerSwitchID = LowerSwitch::ID; 7714383485ac546e369b11797b42bc20831b6db57bChris Lattner// createLowerSwitchPass - Interface to this file... 78d7456026629fc1760a45e6e955e9834246493147Chris LattnerFunctionPass *llvm::createLowerSwitchPass() { 7914383485ac546e369b11797b42bc20831b6db57bChris Lattner return new LowerSwitch(); 8014383485ac546e369b11797b42bc20831b6db57bChris Lattner} 8114383485ac546e369b11797b42bc20831b6db57bChris Lattner 8214383485ac546e369b11797b42bc20831b6db57bChris Lattnerbool LowerSwitch::runOnFunction(Function &F) { 8314383485ac546e369b11797b42bc20831b6db57bChris Lattner bool Changed = false; 8414383485ac546e369b11797b42bc20831b6db57bChris Lattner 8514383485ac546e369b11797b42bc20831b6db57bChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 8614383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 8714383485ac546e369b11797b42bc20831b6db57bChris Lattner 8814383485ac546e369b11797b42bc20831b6db57bChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 8914383485ac546e369b11797b42bc20831b6db57bChris Lattner Changed = true; 9014383485ac546e369b11797b42bc20831b6db57bChris Lattner processSwitchInst(SI); 9114383485ac546e369b11797b42bc20831b6db57bChris Lattner } 9214383485ac546e369b11797b42bc20831b6db57bChris Lattner } 9314383485ac546e369b11797b42bc20831b6db57bChris Lattner 9414383485ac546e369b11797b42bc20831b6db57bChris Lattner return Changed; 9514383485ac546e369b11797b42bc20831b6db57bChris Lattner} 9614383485ac546e369b11797b42bc20831b6db57bChris Lattner 97ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// operator<< - Used for debugging purposes. 98ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// 991cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarstatic raw_ostream& operator<<(raw_ostream &O, 100100c267249d1d03c4f96eede9877a4f9f54f2247Chandler Carruth const LowerSwitch::CaseVector &C) 101100c267249d1d03c4f96eede9877a4f9f54f2247Chandler Carruth LLVM_ATTRIBUTE_USED; 10266ad89cebaecd7d88d9e723170c2b55fadd76b71Mike Stumpstatic raw_ostream& operator<<(raw_ostream &O, 1031cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar const LowerSwitch::CaseVector &C) { 104ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner O << "["; 105ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 106e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 107d7456026629fc1760a45e6e955e9834246493147Chris Lattner E = C.end(); B != E; ) { 108e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov O << *B->Low << " -" << *B->High; 109ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner if (++B != E) O << ", "; 110ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner } 111ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 112ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return O << "]"; 113ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 114e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 115ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// switchConvert - Convert the switch statement into a binary lookup of 116ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// the case values. The function recursively builds this tree. 117ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// 118ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris LattnerBasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, 119ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Value* Val, BasicBlock* OrigBlock, 120ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Default) 121ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner{ 122ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner unsigned Size = End - Begin; 123ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 124ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner if (Size == 1) 125ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return newLeafBlock(*Begin, Val, OrigBlock, Default); 126ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 127ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner unsigned Mid = Size / 2; 128e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov std::vector<CaseRange> LHS(Begin, Begin + Mid); 1290f4c988a27d5723d723b7c8e7c4ca9fc6777f20dDavid Greene DEBUG(dbgs() << "LHS: " << LHS << "\n"); 130e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov std::vector<CaseRange> RHS(Begin + Mid, End); 1310f4c988a27d5723d723b7c8e7c4ca9fc6777f20dDavid Greene DEBUG(dbgs() << "RHS: " << RHS << "\n"); 132ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 133e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov CaseRange& Pivot = *(Begin + Mid); 1340f4c988a27d5723d723b7c8e7c4ca9fc6777f20dDavid Greene DEBUG(dbgs() << "Pivot ==> " 135944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner << cast<ConstantInt>(Pivot.Low)->getValue() << " -" 136f871ccb853a2ccbe8675c912330c041b318be8cdDan Gohman << cast<ConstantInt>(Pivot.High)->getValue() << "\n"); 137ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 138ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val, 139ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner OrigBlock, Default); 140ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val, 141ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner OrigBlock, Default); 142ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 143ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Create a new node that checks if the value is < pivot. Go to the 144ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // left branch if it is and right branch if not. 145ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Function* F = OrigBlock->getParent(); 1461d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock"); 147261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner Function::iterator FI = OrigBlock; 148261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner F->getBasicBlockList().insert(++FI, NewNode); 149ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 150e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_ULT, 151333c40096561218bc3597cf153c0a3895274414cOwen Anderson Val, Pivot.Low, "Pivot"); 152ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner NewNode->getInstList().push_back(Comp); 153051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(LBranch, RBranch, Comp, NewNode); 154ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return NewNode; 155ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 156ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 157ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// newLeafBlock - Create a new leaf block for the binary lookup tree. It 158ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// checks if the switch's value == the case's value. If not, then it 159ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// jumps to the default branch. At this point in the tree, the value 160ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// can't be another valid case value, so the jump to the "default" branch 161ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// is warranted. 162ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// 163e2ff29c17c1a7c121e22789cf1654d923467b472Anton KorobeynikovBasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, 164ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* OrigBlock, 165ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Default) 166ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner{ 167ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Function* F = OrigBlock->getParent(); 1681d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock"); 169261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner Function::iterator FI = OrigBlock; 170261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner F->getBasicBlockList().insert(++FI, NewLeaf); 171ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 172e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Emit comparison 173e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov ICmpInst* Comp = NULL; 174e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov if (Leaf.Low == Leaf.High) { 175e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Make the seteq instruction... 176333c40096561218bc3597cf153c0a3895274414cOwen Anderson Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, 177333c40096561218bc3597cf153c0a3895274414cOwen Anderson Leaf.Low, "SwitchLeaf"); 178e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } else { 179e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Make range comparison 180e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov if (cast<ConstantInt>(Leaf.Low)->isMinValue(true /*isSigned*/)) { 181e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Val >= Min && Val <= Hi --> Val <= Hi 182333c40096561218bc3597cf153c0a3895274414cOwen Anderson Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, 183333c40096561218bc3597cf153c0a3895274414cOwen Anderson "SwitchLeaf"); 184e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } else if (cast<ConstantInt>(Leaf.Low)->isZero()) { 185e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Val >= 0 && Val <= Hi --> Val <=u Hi 186333c40096561218bc3597cf153c0a3895274414cOwen Anderson Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, 187333c40096561218bc3597cf153c0a3895274414cOwen Anderson "SwitchLeaf"); 188e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } else { 189e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Emit V-Lo <=u Hi-Lo 190baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); 1917cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 192e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Val->getName()+".off", 193e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov NewLeaf); 194baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); 195333c40096561218bc3597cf153c0a3895274414cOwen Anderson Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, 196333c40096561218bc3597cf153c0a3895274414cOwen Anderson "SwitchLeaf"); 197e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 198e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 199ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 200ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Make the conditional branch... 201e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov BasicBlock* Succ = Leaf.BB; 202051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(Succ, Default, Comp, NewLeaf); 203ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 204ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // If there were any PHI nodes in this successor, rewrite one entry 205ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // from OrigBlock to come from NewLeaf. 2062da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 2072da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode* PN = cast<PHINode>(I); 208e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Remove all but one incoming entries from the cluster 209e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov uint64_t Range = cast<ConstantInt>(Leaf.High)->getSExtValue() - 210e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov cast<ConstantInt>(Leaf.Low)->getSExtValue(); 211e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov for (uint64_t j = 0; j < Range; ++j) { 212e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov PN->removeIncomingValue(OrigBlock); 213e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 214e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 215ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 216ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 217ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 218ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner } 219ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 220ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return NewLeaf; 221ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 222ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 223e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov// Clusterify - Transform simple list of Cases into list of CaseRange's 224e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikovunsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 225e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy 2260aa32d5d0ff6cd65b6cff957858a79e2d2a614bdStepan Dyatkovskiy IntegersSubsetToBB TheClusterifier; 227e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 228e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Start with "simple" cases 229e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 230e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy i != e; ++i) { 231e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy BasicBlock *SuccBB = i.getCaseSuccessor(); 2320aa32d5d0ff6cd65b6cff957858a79e2d2a614bdStepan Dyatkovskiy IntegersSubset CaseRanges = i.getCaseValueEx(); 2330aa32d5d0ff6cd65b6cff957858a79e2d2a614bdStepan Dyatkovskiy TheClusterifier.add(CaseRanges, SuccBB); 234e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy } 235c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy 236e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy TheClusterifier.optimize(); 237e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy 238e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy size_t numCmps = 0; 2390aa32d5d0ff6cd65b6cff957858a79e2d2a614bdStepan Dyatkovskiy for (IntegersSubsetToBB::RangeIterator i = TheClusterifier.begin(), 240e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy e = TheClusterifier.end(); i != e; ++i, ++numCmps) { 2410aa32d5d0ff6cd65b6cff957858a79e2d2a614bdStepan Dyatkovskiy IntegersSubsetToBB::Cluster &C = *i; 242484fc93eff0295b1aa52b9a64d22346580e4b0e2Stepan Dyatkovskiy 243484fc93eff0295b1aa52b9a64d22346580e4b0e2Stepan Dyatkovskiy // FIXME: Currently work with ConstantInt based numbers. 244484fc93eff0295b1aa52b9a64d22346580e4b0e2Stepan Dyatkovskiy // Changing it to APInt based is a pretty heavy for this commit. 245484fc93eff0295b1aa52b9a64d22346580e4b0e2Stepan Dyatkovskiy Cases.push_back(CaseRange(C.first.Low.toConstantInt(), 246484fc93eff0295b1aa52b9a64d22346580e4b0e2Stepan Dyatkovskiy C.first.High.toConstantInt(), C.second)); 247e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy if (C.first.Low != C.first.High) 248e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // A range counts double, since it requires two compares. 249e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov ++numCmps; 250e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 251e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 252e98a88957ea0c16ec49ff33bff564604255c024fStepan Dyatkovskiy return numCmps; 253e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov} 254e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 25514383485ac546e369b11797b42bc20831b6db57bChris Lattner// processSwitchInst - Replace the specified switch instruction with a sequence 256ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// of chained if-then insts in a balanced binary search. 25714383485ac546e369b11797b42bc20831b6db57bChris Lattner// 25814383485ac546e369b11797b42bc20831b6db57bChris Lattnervoid LowerSwitch::processSwitchInst(SwitchInst *SI) { 25914383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *CurBlock = SI->getParent(); 26014383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *OrigBlock = CurBlock; 26114383485ac546e369b11797b42bc20831b6db57bChris Lattner Function *F = CurBlock->getParent(); 262bb5a7442e362776621112dc9453e546a55878e79Eli Friedman Value *Val = SI->getCondition(); // The value we are switching on... 263ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Default = SI->getDefaultDest(); 26414383485ac546e369b11797b42bc20831b6db57bChris Lattner 26544bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner // If there is only the default destination, don't bother with the code below. 26624473120a253a05f3601cd3373403b47e6d03d41Stepan Dyatkovskiy if (!SI->getNumCases()) { 267051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(SI->getDefaultDest(), CurBlock); 268bf9eaddfb0642e49bc2f3835765a9782ff48c76eChris Lattner CurBlock->getInstList().erase(SI); 26944bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner return; 27044bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner } 27144bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner 272ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Create a new, empty default block so that the new hierarchy of 273ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // if-then statements go to this and the PHI nodes are happy. 2741d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock* NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); 275ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner F->getBasicBlockList().insert(Default, NewDefault); 27614383485ac546e369b11797b42bc20831b6db57bChris Lattner 277051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(Default, NewDefault); 27820af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner 279ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // If there is an entry in any PHI nodes for the default edge, make sure 280ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // to update them as well. 2812da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 2822da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 283ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 284ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 285ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 28614383485ac546e369b11797b42bc20831b6db57bChris Lattner } 28714383485ac546e369b11797b42bc20831b6db57bChris Lattner 288e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Prepare cases vector. 289e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov CaseVector Cases; 290e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov unsigned numCmps = Clusterify(Cases, SI); 291ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 2920f4c988a27d5723d723b7c8e7c4ca9fc6777f20dDavid Greene DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() 2936c1980b3357207c4d756255bc5e32323eac278dcDan Gohman << ". Total compares: " << numCmps << "\n"); 2940f4c988a27d5723d723b7c8e7c4ca9fc6777f20dDavid Greene DEBUG(dbgs() << "Cases: " << Cases << "\n"); 29502efa786d40fabae6dbbb3de5ab057359701e337Mike Stump (void)numCmps; 296e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 297ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val, 298ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner OrigBlock, NewDefault); 299ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 300ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Branch to our shiny new if-then stuff... 301051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(SwitchBlock, OrigBlock); 302ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 30314383485ac546e369b11797b42bc20831b6db57bChris Lattner // We are now done with the switch instruction, delete it. 304bf9eaddfb0642e49bc2f3835765a9782ff48c76eChris Lattner CurBlock->getInstList().erase(SI); 30514383485ac546e369b11797b42bc20831b6db57bChris Lattner} 306