LowerSwitch.cpp revision f871ccb853a2ccbe8675c912330c041b318be8cd
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" 2114383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Pass.h" 22b61f2f061feefd79623fadd21eee4f195b0b8e56Dan Gohman#include "llvm/ADT/STLExtras.h" 23551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 24a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 25944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner#include "llvm/Support/raw_ostream.h" 2620aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 27d7456026629fc1760a45e6e955e9834246493147Chris Lattnerusing namespace llvm; 28d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2914383485ac546e369b11797b42bc20831b6db57bChris Lattnernamespace { 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! 33f4b546110c7b9f0c24be26cfe1eccdd570ee9feeChris Lattner class VISIBILITY_HIDDEN LowerSwitch : public FunctionPass { 34ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner public: 35ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 36ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman LowerSwitch() : FunctionPass(&ID) {} 37794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 388d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner virtual bool runOnFunction(Function &F); 39ed96fe8c79b36a38bd9280438656ee539276fb41Chris Lattner 408d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 41bed2946a96ecb15b0b636fa74cb26ce61b1c648eAnton Korobeynikov // This is a cluster of orthogonal Transforms 428d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner AU.addPreserved<UnifyFunctionExitNodes>(); 438d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner AU.addPreservedID(PromoteMemoryToRegisterID); 44ed96fe8c79b36a38bd9280438656ee539276fb41Chris Lattner AU.addPreservedID(LowerInvokePassID); 45ed96fe8c79b36a38bd9280438656ee539276fb41Chris Lattner AU.addPreservedID(LowerAllocationsID); 468d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner } 47e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 48e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov struct CaseRange { 49e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Constant* Low; 50e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Constant* High; 51e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov BasicBlock* BB; 52e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 53c4558fde76bdb17bff28375fe20ee02e027095b8Jeff Cohen CaseRange() : Low(0), High(0), BB(0) { } 54c4558fde76bdb17bff28375fe20ee02e027095b8Jeff Cohen CaseRange(Constant* low, Constant* high, BasicBlock* bb) : 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 }; 69ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 70ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner /// The comparison function for sorting the switch case values in the vector. 71e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov /// WARNING: Case ranges should be disjoint! 72ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner struct CaseCmp { 73e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov bool operator () (const LowerSwitch::CaseRange& C1, 74e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov const LowerSwitch::CaseRange& C2) { 75ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 76e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 77e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 78e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov return CI1->getValue().slt(CI2->getValue()); 79ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner } 8014383485ac546e369b11797b42bc20831b6db57bChris Lattner }; 8114383485ac546e369b11797b42bc20831b6db57bChris Lattner} 8214383485ac546e369b11797b42bc20831b6db57bChris Lattner 83844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LowerSwitch::ID = 0; 84844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LowerSwitch> 85844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("lowerswitch", "Lower SwitchInst's to branches"); 86844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 87b3674e475389b72939bf90965790d63e9fa24b95Chris Lattner// Publically exposed interface to pass... 886ddba2b933645d308428201e942abe1274fa5085Dan Gohmanconst PassInfo *const llvm::LowerSwitchID = &X; 8914383485ac546e369b11797b42bc20831b6db57bChris Lattner// createLowerSwitchPass - Interface to this file... 90d7456026629fc1760a45e6e955e9834246493147Chris LattnerFunctionPass *llvm::createLowerSwitchPass() { 9114383485ac546e369b11797b42bc20831b6db57bChris Lattner return new LowerSwitch(); 9214383485ac546e369b11797b42bc20831b6db57bChris Lattner} 9314383485ac546e369b11797b42bc20831b6db57bChris Lattner 9414383485ac546e369b11797b42bc20831b6db57bChris Lattnerbool LowerSwitch::runOnFunction(Function &F) { 9514383485ac546e369b11797b42bc20831b6db57bChris Lattner bool Changed = false; 9614383485ac546e369b11797b42bc20831b6db57bChris Lattner 9714383485ac546e369b11797b42bc20831b6db57bChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 9814383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 9914383485ac546e369b11797b42bc20831b6db57bChris Lattner 10014383485ac546e369b11797b42bc20831b6db57bChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 10114383485ac546e369b11797b42bc20831b6db57bChris Lattner Changed = true; 10214383485ac546e369b11797b42bc20831b6db57bChris Lattner processSwitchInst(SI); 10314383485ac546e369b11797b42bc20831b6db57bChris Lattner } 10414383485ac546e369b11797b42bc20831b6db57bChris Lattner } 10514383485ac546e369b11797b42bc20831b6db57bChris Lattner 10614383485ac546e369b11797b42bc20831b6db57bChris Lattner return Changed; 10714383485ac546e369b11797b42bc20831b6db57bChris Lattner} 10814383485ac546e369b11797b42bc20831b6db57bChris Lattner 109ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// operator<< - Used for debugging purposes. 110ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// 111e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikovstatic std::ostream& operator<<(std::ostream &O, 112e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov const LowerSwitch::CaseVector &C) { 113ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner O << "["; 114ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 115e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 116d7456026629fc1760a45e6e955e9834246493147Chris Lattner E = C.end(); B != E; ) { 117e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov O << *B->Low << " -" << *B->High; 118ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner if (++B != E) O << ", "; 119ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner } 120ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 121ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return O << "]"; 122ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 123e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 124e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikovstatic OStream& operator<<(OStream &O, const LowerSwitch::CaseVector &C) { 1255c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling if (O.stream()) *O.stream() << C; 1265c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling return O; 1275c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling} 128ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 129ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// switchConvert - Convert the switch statement into a binary lookup of 130ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// the case values. The function recursively builds this tree. 131ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// 132ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris LattnerBasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, 133ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Value* Val, BasicBlock* OrigBlock, 134ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Default) 135ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner{ 136ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner unsigned Size = End - Begin; 137ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 138ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner if (Size == 1) 139ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return newLeafBlock(*Begin, Val, OrigBlock, Default); 140ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 141ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner unsigned Mid = Size / 2; 142e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov std::vector<CaseRange> LHS(Begin, Begin + Mid); 1430d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "LHS: " << LHS << "\n"; 144e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov std::vector<CaseRange> RHS(Begin + Mid, End); 1450d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "RHS: " << RHS << "\n"; 146ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 147e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov CaseRange& Pivot = *(Begin + Mid); 148944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner DEBUG(errs() << "Pivot ==> " 149944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner << cast<ConstantInt>(Pivot.Low)->getValue() << " -" 150f871ccb853a2ccbe8675c912330c041b318be8cdDan Gohman << cast<ConstantInt>(Pivot.High)->getValue() << "\n"); 151ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 152ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val, 153ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner OrigBlock, Default); 154ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val, 155ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner OrigBlock, Default); 156ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 157ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Create a new node that checks if the value is < pivot. Go to the 158ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // left branch if it is and right branch if not. 159ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Function* F = OrigBlock->getParent(); 160051a950000e21935165db56695e35bade668193bGabor Greif BasicBlock* NewNode = BasicBlock::Create("NodeBlock"); 161261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner Function::iterator FI = OrigBlock; 162261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner F->getBasicBlockList().insert(++FI, NewNode); 163ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 164e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, Val, Pivot.Low, "Pivot"); 165ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner NewNode->getInstList().push_back(Comp); 166051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(LBranch, RBranch, Comp, NewNode); 167ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return NewNode; 168ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 169ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 170ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// newLeafBlock - Create a new leaf block for the binary lookup tree. It 171ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// checks if the switch's value == the case's value. If not, then it 172ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// jumps to the default branch. At this point in the tree, the value 173ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// can't be another valid case value, so the jump to the "default" branch 174ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// is warranted. 175ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// 176e2ff29c17c1a7c121e22789cf1654d923467b472Anton KorobeynikovBasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, 177ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* OrigBlock, 178ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Default) 179ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner{ 180ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner Function* F = OrigBlock->getParent(); 181051a950000e21935165db56695e35bade668193bGabor Greif BasicBlock* NewLeaf = BasicBlock::Create("LeafBlock"); 182261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner Function::iterator FI = OrigBlock; 183261cdfbe5e6e11d56ca1c49a75f26fece3b139c8Chris Lattner F->getBasicBlockList().insert(++FI, NewLeaf); 184ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 185e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Emit comparison 186e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov ICmpInst* Comp = NULL; 187e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov if (Leaf.Low == Leaf.High) { 188e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Make the seteq instruction... 189e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Comp = new ICmpInst(ICmpInst::ICMP_EQ, Val, Leaf.Low, 190e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov "SwitchLeaf", NewLeaf); 191e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } else { 192e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Make range comparison 193e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov if (cast<ConstantInt>(Leaf.Low)->isMinValue(true /*isSigned*/)) { 194e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Val >= Min && Val <= Hi --> Val <= Hi 195e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Comp = new ICmpInst(ICmpInst::ICMP_SLE, Val, Leaf.High, 196e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov "SwitchLeaf", NewLeaf); 197e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } else if (cast<ConstantInt>(Leaf.Low)->isZero()) { 198e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Val >= 0 && Val <= Hi --> Val <=u Hi 199e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Comp = new ICmpInst(ICmpInst::ICMP_ULE, Val, Leaf.High, 200e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov "SwitchLeaf", NewLeaf); 201e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } else { 202e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Emit V-Lo <=u Hi-Lo 203e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); 2047cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 205e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Val->getName()+".off", 206e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov NewLeaf); 207e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); 208e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Comp = new ICmpInst(ICmpInst::ICMP_ULE, Add, UpperBound, 209e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov "SwitchLeaf", NewLeaf); 210e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 211e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 212ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 213ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Make the conditional branch... 214e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov BasicBlock* Succ = Leaf.BB; 215051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(Succ, Default, Comp, NewLeaf); 216ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 217ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // If there were any PHI nodes in this successor, rewrite one entry 218ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // from OrigBlock to come from NewLeaf. 2192da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 2202da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode* PN = cast<PHINode>(I); 221e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Remove all but one incoming entries from the cluster 222e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov uint64_t Range = cast<ConstantInt>(Leaf.High)->getSExtValue() - 223e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov cast<ConstantInt>(Leaf.Low)->getSExtValue(); 224e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov for (uint64_t j = 0; j < Range; ++j) { 225e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov PN->removeIncomingValue(OrigBlock); 226e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 227e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 228ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 229ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 230ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 231ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner } 232ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 233ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner return NewLeaf; 234ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner} 235ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 236e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov// Clusterify - Transform simple list of Cases into list of CaseRange's 237e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikovunsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 238e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov unsigned numCmps = 0; 239e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 240e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Start with "simple" cases 241e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov for (unsigned i = 1; i < SI->getNumSuccessors(); ++i) 242e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov Cases.push_back(CaseRange(SI->getSuccessorValue(i), 243e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov SI->getSuccessorValue(i), 244e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov SI->getSuccessor(i))); 245111c4f897eb9a42eac6aceea830b8e76058afd73Dan Gohman std::sort(Cases.begin(), Cases.end(), CaseCmp()); 246e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 247e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Merge case into clusters 248e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov if (Cases.size()>=2) 2499dfb11d32d302abfe8803d530138b38ddc567c60David Greene for (CaseItr I=Cases.begin(), J=next(Cases.begin()); J!=Cases.end(); ) { 250e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue(); 251e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue(); 252e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov BasicBlock* nextBB = J->BB; 253e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov BasicBlock* currentBB = I->BB; 254e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 255e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // If the two neighboring cases go to the same destination, merge them 256e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // into a single case. 257e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov if ((nextValue-currentValue==1) && (currentBB == nextBB)) { 258e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov I->High = J->High; 259e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov J = Cases.erase(J); 260e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } else { 261e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov I = J++; 262e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 263e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 264e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 265e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 266e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov if (I->Low != I->High) 267e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // A range counts double, since it requires two compares. 268e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov ++numCmps; 269e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov } 270e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 271e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov return numCmps; 272e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov} 273e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 27414383485ac546e369b11797b42bc20831b6db57bChris Lattner// processSwitchInst - Replace the specified switch instruction with a sequence 275ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner// of chained if-then insts in a balanced binary search. 27614383485ac546e369b11797b42bc20831b6db57bChris Lattner// 27714383485ac546e369b11797b42bc20831b6db57bChris Lattnervoid LowerSwitch::processSwitchInst(SwitchInst *SI) { 27814383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *CurBlock = SI->getParent(); 27914383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *OrigBlock = CurBlock; 28014383485ac546e369b11797b42bc20831b6db57bChris Lattner Function *F = CurBlock->getParent(); 28114383485ac546e369b11797b42bc20831b6db57bChris Lattner Value *Val = SI->getOperand(0); // The value we are switching on... 282ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* Default = SI->getDefaultDest(); 28314383485ac546e369b11797b42bc20831b6db57bChris Lattner 28444bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner // If there is only the default destination, don't bother with the code below. 28544bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner if (SI->getNumOperands() == 2) { 286051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(SI->getDefaultDest(), CurBlock); 287bf9eaddfb0642e49bc2f3835765a9782ff48c76eChris Lattner CurBlock->getInstList().erase(SI); 28844bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner return; 28944bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner } 29044bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner 291ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Create a new, empty default block so that the new hierarchy of 292ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // if-then statements go to this and the PHI nodes are happy. 293051a950000e21935165db56695e35bade668193bGabor Greif BasicBlock* NewDefault = BasicBlock::Create("NewDefault"); 294ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner F->getBasicBlockList().insert(Default, NewDefault); 29514383485ac546e369b11797b42bc20831b6db57bChris Lattner 296051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(Default, NewDefault); 29720af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner 298ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // If there is an entry in any PHI nodes for the default edge, make sure 299ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // to update them as well. 3002da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 3012da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 302ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 303ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 304ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 30514383485ac546e369b11797b42bc20831b6db57bChris Lattner } 30614383485ac546e369b11797b42bc20831b6db57bChris Lattner 307e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov // Prepare cases vector. 308e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov CaseVector Cases; 309e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov unsigned numCmps = Clusterify(Cases, SI); 310ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 311e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov DOUT << "Clusterify finished. Total clusters: " << Cases.size() 312e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov << ". Total compares: " << numCmps << "\n"; 3130d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "Cases: " << Cases << "\n"; 314e2ff29c17c1a7c121e22789cf1654d923467b472Anton Korobeynikov 315ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val, 316ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner OrigBlock, NewDefault); 317ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 318ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner // Branch to our shiny new if-then stuff... 319051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(SwitchBlock, OrigBlock); 320ebbc1a5aa0c37ab29d14ae56c176b3bfd25658cbChris Lattner 32114383485ac546e369b11797b42bc20831b6db57bChris Lattner // We are now done with the switch instruction, delete it. 322bf9eaddfb0642e49bc2f3835765a9782ff48c76eChris Lattner CurBlock->getInstList().erase(SI); 32314383485ac546e369b11797b42bc20831b6db57bChris Lattner} 324