1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LowerSwitch transformation rewrites switch instructions with a sequence 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// of branches, which allows targets to get away with not implementing the 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// switch instruction until it is convenient. 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Scalar.h" 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Constants.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Function.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Instructions.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/LLVMContext.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Pass.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/STLExtras.h" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Compiler.h" 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Debug.h" 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/raw_ostream.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <algorithm> 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// instructions. 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class LowerSwitch : public FunctionPass { 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; // Pass identification, replacement for typeid 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LowerSwitch() : FunctionPass(ID) { 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeLowerSwitchPass(*PassRegistry::getPassRegistry()); 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual bool runOnFunction(Function &F); 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This is a cluster of orthogonal Transforms 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreserved<UnifyFunctionExitNodes>(); 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreserved("mem2reg"); 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addPreservedID(LowerInvokePassID); 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct CaseRange { 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Constant* Low; 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Constant* High; 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* BB; 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CaseRange(Constant *low = 0, Constant *high = 0, BasicBlock *bb = 0) : 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Low(low), High(high), BB(bb) { } 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::vector<CaseRange> CaseVector; 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::vector<CaseRange>::iterator CaseItr; 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void processSwitchInst(SwitchInst *SI); 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* switchConvert(CaseItr Begin, CaseItr End, Value* Val, 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* OrigBlock, BasicBlock* Default); 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* newLeafBlock(CaseRange& Leaf, Value* Val, 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* OrigBlock, BasicBlock* Default); 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Clusterify(CaseVector& Cases, SwitchInst *SI); 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// The comparison function for sorting the switch case values in the vector. 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// WARNING: Case ranges should be disjoint! 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct CaseCmp { 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator () (const LowerSwitch::CaseRange& C1, 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const LowerSwitch::CaseRange& C2) { 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return CI1->getValue().slt(CI2->getValue()); 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanchar LowerSwitch::ID = 0; 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS(LowerSwitch, "lowerswitch", 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Lower SwitchInst's to branches", false, false) 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Publicly exposed interface to pass... 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanchar &llvm::LowerSwitchID = LowerSwitch::ID; 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// createLowerSwitchPass - Interface to this file... 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanFunctionPass *llvm::createLowerSwitchPass() { 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return new LowerSwitch(); 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool LowerSwitch::runOnFunction(Function &F) { 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Changed = false; 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman processSwitchInst(SI); 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Changed; 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// operator<< - Used for debugging purposes. 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic raw_ostream& operator<<(raw_ostream &O, 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const LowerSwitch::CaseVector &C) 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LLVM_ATTRIBUTE_USED; 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic raw_ostream& operator<<(raw_ostream &O, 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const LowerSwitch::CaseVector &C) { 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman O << "["; 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = C.end(); B != E; ) { 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman O << *B->Low << " -" << *B->High; 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (++B != E) O << ", "; 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return O << "]"; 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// switchConvert - Convert the switch statement into a binary lookup of 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// the case values. The function recursively builds this tree. 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanBasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value* Val, BasicBlock* OrigBlock, 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* Default) 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman{ 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Size = End - Begin; 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Size == 1) 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return newLeafBlock(*Begin, Val, OrigBlock, Default); 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Mid = Size / 2; 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<CaseRange> LHS(Begin, Begin + Mid); 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "LHS: " << LHS << "\n"); 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<CaseRange> RHS(Begin + Mid, End); 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "RHS: " << RHS << "\n"); 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CaseRange& Pivot = *(Begin + Mid); 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Pivot ==> " 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << cast<ConstantInt>(Pivot.Low)->getValue() << " -" 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << cast<ConstantInt>(Pivot.High)->getValue() << "\n"); 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val, 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OrigBlock, Default); 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val, 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OrigBlock, Default); 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create a new node that checks if the value is < pivot. Go to the 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // left branch if it is and right branch if not. 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function* F = OrigBlock->getParent(); 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock"); 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function::iterator FI = OrigBlock; 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman F->getBasicBlockList().insert(++FI, NewNode); 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Val, Pivot.Low, "Pivot"); 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewNode->getInstList().push_back(Comp); 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchInst::Create(LBranch, RBranch, Comp, NewNode); 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NewNode; 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// newLeafBlock - Create a new leaf block for the binary lookup tree. It 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// checks if the switch's value == the case's value. If not, then it 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// jumps to the default branch. At this point in the tree, the value 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// can't be another valid case value, so the jump to the "default" branch 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// is warranted. 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanBasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* OrigBlock, 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* Default) 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman{ 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function* F = OrigBlock->getParent(); 18019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock"); 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function::iterator FI = OrigBlock; 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman F->getBasicBlockList().insert(++FI, NewLeaf); 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Emit comparison 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ICmpInst* Comp = NULL; 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Leaf.Low == Leaf.High) { 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Make the seteq instruction... 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, 18919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Leaf.Low, "SwitchLeaf"); 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Make range comparison 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (cast<ConstantInt>(Leaf.Low)->isMinValue(true /*isSigned*/)) { 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Val >= Min && Val <= Hi --> Val <= Hi 19419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, 19519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "SwitchLeaf"); 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (cast<ConstantInt>(Leaf.Low)->isZero()) { 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Val >= 0 && Val <= Hi --> Val <=u Hi 19819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, 19919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "SwitchLeaf"); 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Emit V-Lo <=u Hi-Lo 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 20419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Val->getName()+".off", 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewLeaf); 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); 20719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, 20819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "SwitchLeaf"); 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Make the conditional branch... 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* Succ = Leaf.BB; 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchInst::Create(Succ, Default, Comp, NewLeaf); 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If there were any PHI nodes in this successor, rewrite one entry 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // from OrigBlock to come from NewLeaf. 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode* PN = cast<PHINode>(I); 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove all but one incoming entries from the cluster 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman uint64_t Range = cast<ConstantInt>(Leaf.High)->getSExtValue() - 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cast<ConstantInt>(Leaf.Low)->getSExtValue(); 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (uint64_t j = 0; j < Range; ++j) { 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->removeIncomingValue(OrigBlock); 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return NewLeaf; 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Clusterify - Transform simple list of Cases into list of CaseRange's 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanunsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned numCmps = 0; 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Start with "simple" cases 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 1; i < SI->getNumSuccessors(); ++i) 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Cases.push_back(CaseRange(SI->getSuccessorValue(i), 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SI->getSuccessorValue(i), 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SI->getSuccessor(i))); 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::sort(Cases.begin(), Cases.end(), CaseCmp()); 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Merge case into clusters 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Cases.size()>=2) 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (CaseItr I=Cases.begin(), J=llvm::next(Cases.begin()); J!=Cases.end(); ) { 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue(); 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue(); 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* nextBB = J->BB; 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* currentBB = I->BB; 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the two neighboring cases go to the same destination, merge them 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // into a single case. 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((nextValue-currentValue==1) && (currentBB == nextBB)) { 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->High = J->High; 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman J = Cases.erase(J); 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I = J++; 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->Low != I->High) 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // A range counts double, since it requires two compares. 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++numCmps; 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return numCmps; 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// processSwitchInst - Replace the specified switch instruction with a sequence 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// of chained if-then insts in a balanced binary search. 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LowerSwitch::processSwitchInst(SwitchInst *SI) { 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *CurBlock = SI->getParent(); 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *OrigBlock = CurBlock; 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function *F = CurBlock->getParent(); 28019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *Val = SI->getCondition(); // The value we are switching on... 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* Default = SI->getDefaultDest(); 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If there is only the default destination, don't bother with the code below. 28419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SI->getNumCases() == 1) { 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchInst::Create(SI->getDefaultDest(), CurBlock); 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurBlock->getInstList().erase(SI); 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create a new, empty default block so that the new hierarchy of 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // if-then statements go to this and the PHI nodes are happy. 29219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock* NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman F->getBasicBlockList().insert(Default, NewDefault); 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchInst::Create(Default, NewDefault); 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If there is an entry in any PHI nodes for the default edge, make sure 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to update them as well. 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *PN = cast<PHINode>(I); 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Prepare cases vector. 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CaseVector Cases; 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned numCmps = Clusterify(Cases, SI); 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << ". Total compares: " << numCmps << "\n"); 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Cases: " << Cases << "\n"); 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (void)numCmps; 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val, 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OrigBlock, NewDefault); 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Branch to our shiny new if-then stuff... 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BranchInst::Create(SwitchBlock, OrigBlock); 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We are now done with the switch instruction, delete it. 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurBlock->getInstList().erase(SI); 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 324