LowerSwitch.cpp revision 249423
1193323Sed//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// The LowerSwitch transformation rewrites switch instructions with a sequence 11193323Sed// of branches, which allows targets to get away with not implementing the 12193323Sed// switch instruction until it is convenient. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16193323Sed#include "llvm/Transforms/Scalar.h" 17249423Sdim#include "llvm/ADT/STLExtras.h" 18249423Sdim#include "llvm/IR/Constants.h" 19249423Sdim#include "llvm/IR/Function.h" 20249423Sdim#include "llvm/IR/Instructions.h" 21249423Sdim#include "llvm/IR/LLVMContext.h" 22193323Sed#include "llvm/Pass.h" 23198892Srdivacky#include "llvm/Support/Compiler.h" 24193323Sed#include "llvm/Support/Debug.h" 25193323Sed#include "llvm/Support/raw_ostream.h" 26249423Sdim#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 27193323Sed#include <algorithm> 28193323Sedusing namespace llvm; 29193323Sed 30193323Sednamespace { 31193323Sed /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch 32212904Sdim /// instructions. 33198892Srdivacky class LowerSwitch : public FunctionPass { 34193323Sed public: 35193323Sed static char ID; // Pass identification, replacement for typeid 36218893Sdim LowerSwitch() : FunctionPass(ID) { 37218893Sdim initializeLowerSwitchPass(*PassRegistry::getPassRegistry()); 38218893Sdim } 39193323Sed 40193323Sed virtual bool runOnFunction(Function &F); 41193323Sed 42193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 43193323Sed // This is a cluster of orthogonal Transforms 44193323Sed AU.addPreserved<UnifyFunctionExitNodes>(); 45212904Sdim AU.addPreserved("mem2reg"); 46193323Sed AU.addPreservedID(LowerInvokePassID); 47193323Sed } 48193323Sed 49193323Sed struct CaseRange { 50193323Sed Constant* Low; 51193323Sed Constant* High; 52193323Sed BasicBlock* BB; 53193323Sed 54212904Sdim CaseRange(Constant *low = 0, Constant *high = 0, BasicBlock *bb = 0) : 55193323Sed Low(low), High(high), BB(bb) { } 56193323Sed }; 57193323Sed 58193323Sed typedef std::vector<CaseRange> CaseVector; 59193323Sed typedef std::vector<CaseRange>::iterator CaseItr; 60193323Sed private: 61193323Sed void processSwitchInst(SwitchInst *SI); 62193323Sed 63193323Sed BasicBlock* switchConvert(CaseItr Begin, CaseItr End, Value* Val, 64193323Sed BasicBlock* OrigBlock, BasicBlock* Default); 65193323Sed BasicBlock* newLeafBlock(CaseRange& Leaf, Value* Val, 66193323Sed BasicBlock* OrigBlock, BasicBlock* Default); 67193323Sed unsigned Clusterify(CaseVector& Cases, SwitchInst *SI); 68193323Sed }; 69193323Sed} 70193323Sed 71193323Sedchar LowerSwitch::ID = 0; 72212904SdimINITIALIZE_PASS(LowerSwitch, "lowerswitch", 73218893Sdim "Lower SwitchInst's to branches", false, false) 74193323Sed 75221345Sdim// Publicly exposed interface to pass... 76212904Sdimchar &llvm::LowerSwitchID = LowerSwitch::ID; 77193323Sed// createLowerSwitchPass - Interface to this file... 78193323SedFunctionPass *llvm::createLowerSwitchPass() { 79193323Sed return new LowerSwitch(); 80193323Sed} 81193323Sed 82193323Sedbool LowerSwitch::runOnFunction(Function &F) { 83193323Sed bool Changed = false; 84193323Sed 85193323Sed for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 86193323Sed BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 87193323Sed 88193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 89193323Sed Changed = true; 90193323Sed processSwitchInst(SI); 91193323Sed } 92193323Sed } 93193323Sed 94193323Sed return Changed; 95193323Sed} 96193323Sed 97193323Sed// operator<< - Used for debugging purposes. 98193323Sed// 99198090Srdivackystatic raw_ostream& operator<<(raw_ostream &O, 100218893Sdim const LowerSwitch::CaseVector &C) 101218893Sdim LLVM_ATTRIBUTE_USED; 102198090Srdivackystatic raw_ostream& operator<<(raw_ostream &O, 103198090Srdivacky const LowerSwitch::CaseVector &C) { 104193323Sed O << "["; 105193323Sed 106193323Sed for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 107193323Sed E = C.end(); B != E; ) { 108193323Sed O << *B->Low << " -" << *B->High; 109193323Sed if (++B != E) O << ", "; 110193323Sed } 111193323Sed 112193323Sed return O << "]"; 113193323Sed} 114193323Sed 115193323Sed// switchConvert - Convert the switch statement into a binary lookup of 116193323Sed// the case values. The function recursively builds this tree. 117193323Sed// 118193323SedBasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, 119193323Sed Value* Val, BasicBlock* OrigBlock, 120193323Sed BasicBlock* Default) 121193323Sed{ 122193323Sed unsigned Size = End - Begin; 123193323Sed 124193323Sed if (Size == 1) 125193323Sed return newLeafBlock(*Begin, Val, OrigBlock, Default); 126193323Sed 127193323Sed unsigned Mid = Size / 2; 128193323Sed std::vector<CaseRange> LHS(Begin, Begin + Mid); 129202375Srdivacky DEBUG(dbgs() << "LHS: " << LHS << "\n"); 130193323Sed std::vector<CaseRange> RHS(Begin + Mid, End); 131202375Srdivacky DEBUG(dbgs() << "RHS: " << RHS << "\n"); 132193323Sed 133193323Sed CaseRange& Pivot = *(Begin + Mid); 134202375Srdivacky DEBUG(dbgs() << "Pivot ==> " 135193323Sed << cast<ConstantInt>(Pivot.Low)->getValue() << " -" 136193323Sed << cast<ConstantInt>(Pivot.High)->getValue() << "\n"); 137193323Sed 138193323Sed BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val, 139193323Sed OrigBlock, Default); 140193323Sed BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val, 141193323Sed OrigBlock, Default); 142193323Sed 143193323Sed // Create a new node that checks if the value is < pivot. Go to the 144193323Sed // left branch if it is and right branch if not. 145193323Sed Function* F = OrigBlock->getParent(); 146198090Srdivacky BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock"); 147193323Sed Function::iterator FI = OrigBlock; 148193323Sed F->getBasicBlockList().insert(++FI, NewNode); 149193323Sed 150239462Sdim ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_ULT, 151198090Srdivacky Val, Pivot.Low, "Pivot"); 152193323Sed NewNode->getInstList().push_back(Comp); 153193323Sed BranchInst::Create(LBranch, RBranch, Comp, NewNode); 154193323Sed return NewNode; 155193323Sed} 156193323Sed 157193323Sed// newLeafBlock - Create a new leaf block for the binary lookup tree. It 158193323Sed// checks if the switch's value == the case's value. If not, then it 159193323Sed// jumps to the default branch. At this point in the tree, the value 160193323Sed// can't be another valid case value, so the jump to the "default" branch 161193323Sed// is warranted. 162193323Sed// 163193323SedBasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, 164193323Sed BasicBlock* OrigBlock, 165193323Sed BasicBlock* Default) 166193323Sed{ 167193323Sed Function* F = OrigBlock->getParent(); 168198090Srdivacky BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock"); 169193323Sed Function::iterator FI = OrigBlock; 170193323Sed F->getBasicBlockList().insert(++FI, NewLeaf); 171193323Sed 172193323Sed // Emit comparison 173193323Sed ICmpInst* Comp = NULL; 174193323Sed if (Leaf.Low == Leaf.High) { 175193323Sed // Make the seteq instruction... 176198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, 177198090Srdivacky Leaf.Low, "SwitchLeaf"); 178193323Sed } else { 179193323Sed // Make range comparison 180193323Sed if (cast<ConstantInt>(Leaf.Low)->isMinValue(true /*isSigned*/)) { 181193323Sed // Val >= Min && Val <= Hi --> Val <= Hi 182198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, 183198090Srdivacky "SwitchLeaf"); 184193323Sed } else if (cast<ConstantInt>(Leaf.Low)->isZero()) { 185193323Sed // Val >= 0 && Val <= Hi --> Val <=u Hi 186198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, 187198090Srdivacky "SwitchLeaf"); 188193323Sed } else { 189193323Sed // Emit V-Lo <=u Hi-Lo 190193323Sed Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); 191193323Sed Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 192193323Sed Val->getName()+".off", 193193323Sed NewLeaf); 194193323Sed Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); 195198090Srdivacky Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, 196198090Srdivacky "SwitchLeaf"); 197193323Sed } 198193323Sed } 199193323Sed 200193323Sed // Make the conditional branch... 201193323Sed BasicBlock* Succ = Leaf.BB; 202193323Sed BranchInst::Create(Succ, Default, Comp, NewLeaf); 203193323Sed 204193323Sed // If there were any PHI nodes in this successor, rewrite one entry 205193323Sed // from OrigBlock to come from NewLeaf. 206193323Sed for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 207193323Sed PHINode* PN = cast<PHINode>(I); 208193323Sed // Remove all but one incoming entries from the cluster 209193323Sed uint64_t Range = cast<ConstantInt>(Leaf.High)->getSExtValue() - 210193323Sed cast<ConstantInt>(Leaf.Low)->getSExtValue(); 211193323Sed for (uint64_t j = 0; j < Range; ++j) { 212193323Sed PN->removeIncomingValue(OrigBlock); 213193323Sed } 214193323Sed 215193323Sed int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 216193323Sed assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 217193323Sed PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 218193323Sed } 219193323Sed 220193323Sed return NewLeaf; 221193323Sed} 222193323Sed 223193323Sed// Clusterify - Transform simple list of Cases into list of CaseRange's 224193323Sedunsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 225193323Sed 226239462Sdim IntegersSubsetToBB TheClusterifier; 227239462Sdim 228193323Sed // Start with "simple" cases 229239462Sdim for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 230239462Sdim i != e; ++i) { 231239462Sdim BasicBlock *SuccBB = i.getCaseSuccessor(); 232239462Sdim IntegersSubset CaseRanges = i.getCaseValueEx(); 233239462Sdim TheClusterifier.add(CaseRanges, SuccBB); 234239462Sdim } 235234353Sdim 236239462Sdim TheClusterifier.optimize(); 237239462Sdim 238239462Sdim size_t numCmps = 0; 239239462Sdim for (IntegersSubsetToBB::RangeIterator i = TheClusterifier.begin(), 240239462Sdim e = TheClusterifier.end(); i != e; ++i, ++numCmps) { 241239462Sdim IntegersSubsetToBB::Cluster &C = *i; 242239462Sdim 243239462Sdim // FIXME: Currently work with ConstantInt based numbers. 244239462Sdim // Changing it to APInt based is a pretty heavy for this commit. 245239462Sdim Cases.push_back(CaseRange(C.first.getLow().toConstantInt(), 246239462Sdim C.first.getHigh().toConstantInt(), C.second)); 247239462Sdim if (C.first.isSingleNumber()) 248193323Sed // A range counts double, since it requires two compares. 249193323Sed ++numCmps; 250193323Sed } 251193323Sed 252239462Sdim return numCmps; 253193323Sed} 254193323Sed 255193323Sed// processSwitchInst - Replace the specified switch instruction with a sequence 256193323Sed// of chained if-then insts in a balanced binary search. 257193323Sed// 258193323Sedvoid LowerSwitch::processSwitchInst(SwitchInst *SI) { 259193323Sed BasicBlock *CurBlock = SI->getParent(); 260193323Sed BasicBlock *OrigBlock = CurBlock; 261193323Sed Function *F = CurBlock->getParent(); 262226633Sdim Value *Val = SI->getCondition(); // The value we are switching on... 263193323Sed BasicBlock* Default = SI->getDefaultDest(); 264193323Sed 265193323Sed // If there is only the default destination, don't bother with the code below. 266234353Sdim if (!SI->getNumCases()) { 267193323Sed BranchInst::Create(SI->getDefaultDest(), CurBlock); 268193323Sed CurBlock->getInstList().erase(SI); 269193323Sed return; 270193323Sed } 271193323Sed 272193323Sed // Create a new, empty default block so that the new hierarchy of 273193323Sed // if-then statements go to this and the PHI nodes are happy. 274198090Srdivacky BasicBlock* NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); 275193323Sed F->getBasicBlockList().insert(Default, NewDefault); 276193323Sed 277193323Sed BranchInst::Create(Default, NewDefault); 278193323Sed 279193323Sed // If there is an entry in any PHI nodes for the default edge, make sure 280193323Sed // to update them as well. 281193323Sed for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 282193323Sed PHINode *PN = cast<PHINode>(I); 283193323Sed int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 284193323Sed assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 285193323Sed PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 286193323Sed } 287193323Sed 288193323Sed // Prepare cases vector. 289193323Sed CaseVector Cases; 290193323Sed unsigned numCmps = Clusterify(Cases, SI); 291193323Sed 292202375Srdivacky DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() 293198090Srdivacky << ". Total compares: " << numCmps << "\n"); 294202375Srdivacky DEBUG(dbgs() << "Cases: " << Cases << "\n"); 295198090Srdivacky (void)numCmps; 296193323Sed 297193323Sed BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val, 298193323Sed OrigBlock, NewDefault); 299193323Sed 300193323Sed // Branch to our shiny new if-then stuff... 301193323Sed BranchInst::Create(SwitchBlock, OrigBlock); 302193323Sed 303193323Sed // We are now done with the switch instruction, delete it. 304193323Sed CurBlock->getInstList().erase(SI); 305193323Sed} 306