LowerSwitch.cpp revision 44bb541c011bcae84759ed194ec7cb4139775fcb
114383485ac546e369b11797b42bc20831b6db57bChris Lattner//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// 214383485ac546e369b11797b42bc20831b6db57bChris Lattner// 314383485ac546e369b11797b42bc20831b6db57bChris Lattner// The LowerSwitch transformation rewrites switch statements with a sequence of 414383485ac546e369b11797b42bc20831b6db57bChris Lattner// branches, which allows targets to get away with not implementing the switch 514383485ac546e369b11797b42bc20831b6db57bChris Lattner// statement until it is convenient. 614383485ac546e369b11797b42bc20831b6db57bChris Lattner// 714383485ac546e369b11797b42bc20831b6db57bChris Lattner//===----------------------------------------------------------------------===// 814383485ac546e369b11797b42bc20831b6db57bChris Lattner 914383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Transforms/Scalar.h" 1014383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Function.h" 1114383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/iTerminators.h" 1214383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/iOperators.h" 1314383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/iPHINode.h" 1414383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "llvm/Pass.h" 1514383485ac546e369b11797b42bc20831b6db57bChris Lattner#include "Support/Statistic.h" 1614383485ac546e369b11797b42bc20831b6db57bChris Lattner 1714383485ac546e369b11797b42bc20831b6db57bChris Lattnernamespace { 1814383485ac546e369b11797b42bc20831b6db57bChris Lattner Statistic<> NumLowered("lowerswitch", "Number of SwitchInst's replaced"); 1914383485ac546e369b11797b42bc20831b6db57bChris Lattner 2014383485ac546e369b11797b42bc20831b6db57bChris Lattner /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch 2114383485ac546e369b11797b42bc20831b6db57bChris Lattner /// instructions. Note that this cannot be a BasicBlock pass because it 2214383485ac546e369b11797b42bc20831b6db57bChris Lattner /// modifies the CFG! 2314383485ac546e369b11797b42bc20831b6db57bChris Lattner struct LowerSwitch : public FunctionPass { 2414383485ac546e369b11797b42bc20831b6db57bChris Lattner bool runOnFunction(Function &F); 2514383485ac546e369b11797b42bc20831b6db57bChris Lattner void processSwitchInst(SwitchInst *SI); 2614383485ac546e369b11797b42bc20831b6db57bChris Lattner }; 2714383485ac546e369b11797b42bc20831b6db57bChris Lattner 2814383485ac546e369b11797b42bc20831b6db57bChris Lattner RegisterOpt<LowerSwitch> 2914383485ac546e369b11797b42bc20831b6db57bChris Lattner X("lowerswitch", "Lower SwitchInst's to branches"); 3014383485ac546e369b11797b42bc20831b6db57bChris Lattner} 3114383485ac546e369b11797b42bc20831b6db57bChris Lattner 3214383485ac546e369b11797b42bc20831b6db57bChris Lattner// createLowerSwitchPass - Interface to this file... 3319df3876e6dce016ec4c5ab28320a246ab285001Brian GaekeFunctionPass *createLowerSwitchPass() { 3414383485ac546e369b11797b42bc20831b6db57bChris Lattner return new LowerSwitch(); 3514383485ac546e369b11797b42bc20831b6db57bChris Lattner} 3614383485ac546e369b11797b42bc20831b6db57bChris Lattner 3714383485ac546e369b11797b42bc20831b6db57bChris Lattnerbool LowerSwitch::runOnFunction(Function &F) { 3814383485ac546e369b11797b42bc20831b6db57bChris Lattner bool Changed = false; 3914383485ac546e369b11797b42bc20831b6db57bChris Lattner 4014383485ac546e369b11797b42bc20831b6db57bChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 4114383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 4214383485ac546e369b11797b42bc20831b6db57bChris Lattner 4314383485ac546e369b11797b42bc20831b6db57bChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 4414383485ac546e369b11797b42bc20831b6db57bChris Lattner Changed = true; 4514383485ac546e369b11797b42bc20831b6db57bChris Lattner processSwitchInst(SI); 4614383485ac546e369b11797b42bc20831b6db57bChris Lattner } 4714383485ac546e369b11797b42bc20831b6db57bChris Lattner } 4814383485ac546e369b11797b42bc20831b6db57bChris Lattner 4914383485ac546e369b11797b42bc20831b6db57bChris Lattner return Changed; 5014383485ac546e369b11797b42bc20831b6db57bChris Lattner} 5114383485ac546e369b11797b42bc20831b6db57bChris Lattner 5214383485ac546e369b11797b42bc20831b6db57bChris Lattner// processSwitchInst - Replace the specified switch instruction with a sequence 5314383485ac546e369b11797b42bc20831b6db57bChris Lattner// of chained basic blocks. Right now we just insert an incredibly stupid 5414383485ac546e369b11797b42bc20831b6db57bChris Lattner// linear sequence of branches. It would be better to do a balanced binary 5514383485ac546e369b11797b42bc20831b6db57bChris Lattner// search eventually. FIXME 5614383485ac546e369b11797b42bc20831b6db57bChris Lattner// 5714383485ac546e369b11797b42bc20831b6db57bChris Lattnervoid LowerSwitch::processSwitchInst(SwitchInst *SI) { 5814383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *CurBlock = SI->getParent(); 5914383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *OrigBlock = CurBlock; 6014383485ac546e369b11797b42bc20831b6db57bChris Lattner Function *F = CurBlock->getParent(); 6114383485ac546e369b11797b42bc20831b6db57bChris Lattner Value *Val = SI->getOperand(0); // The value we are switching on... 6214383485ac546e369b11797b42bc20831b6db57bChris Lattner 6314383485ac546e369b11797b42bc20831b6db57bChris Lattner // Unlink the switch instruction from it's block. 6414383485ac546e369b11797b42bc20831b6db57bChris Lattner CurBlock->getInstList().remove(SI); 6514383485ac546e369b11797b42bc20831b6db57bChris Lattner 6644bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner // If there is only the default destination, don't bother with the code below. 6744bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner if (SI->getNumOperands() == 2) { 6844bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner CurBlock->getInstList().push_back(new BranchInst(SI->getDefaultDest())); 6944bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner delete SI; 7044bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner return; 7144bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner } 7244bb541c011bcae84759ed194ec7cb4139775fcbChris Lattner 7314383485ac546e369b11797b42bc20831b6db57bChris Lattner // Expand comparisons for all of the non-default cases... 7414383485ac546e369b11797b42bc20831b6db57bChris Lattner for (unsigned i = 2, e = SI->getNumOperands(); i != e; i += 2) { 7514383485ac546e369b11797b42bc20831b6db57bChris Lattner // Insert a new basic block after the current one... 7614383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *NextBlock; 7714383485ac546e369b11797b42bc20831b6db57bChris Lattner if (i != e-2) { 7814383485ac546e369b11797b42bc20831b6db57bChris Lattner NextBlock = new BasicBlock("switchblock"); 7914383485ac546e369b11797b42bc20831b6db57bChris Lattner F->getBasicBlockList().insert(CurBlock->getNext(), NextBlock); 8014383485ac546e369b11797b42bc20831b6db57bChris Lattner } else { // Last case, if it's not the value, go to default block. 8114383485ac546e369b11797b42bc20831b6db57bChris Lattner NextBlock = cast<BasicBlock>(SI->getDefaultDest()); 8214383485ac546e369b11797b42bc20831b6db57bChris Lattner } 8314383485ac546e369b11797b42bc20831b6db57bChris Lattner 8414383485ac546e369b11797b42bc20831b6db57bChris Lattner // Make the seteq instruction... 8514383485ac546e369b11797b42bc20831b6db57bChris Lattner Instruction *Comp = new SetCondInst(Instruction::SetEQ, Val, 8614383485ac546e369b11797b42bc20831b6db57bChris Lattner SI->getOperand(i), "switchcase"); 8714383485ac546e369b11797b42bc20831b6db57bChris Lattner CurBlock->getInstList().push_back(Comp); 8814383485ac546e369b11797b42bc20831b6db57bChris Lattner 8914383485ac546e369b11797b42bc20831b6db57bChris Lattner // Make the conditional branch... 9014383485ac546e369b11797b42bc20831b6db57bChris Lattner BasicBlock *Succ = cast<BasicBlock>(SI->getOperand(i+1)); 9114383485ac546e369b11797b42bc20831b6db57bChris Lattner Instruction *Br = new BranchInst(Succ, NextBlock, Comp); 9214383485ac546e369b11797b42bc20831b6db57bChris Lattner CurBlock->getInstList().push_back(Br); 9314383485ac546e369b11797b42bc20831b6db57bChris Lattner 9420af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner // If there were any PHI nodes in this successor, rewrite one entry from 9514383485ac546e369b11797b42bc20831b6db57bChris Lattner // OrigBlock to come from CurBlock. 9614383485ac546e369b11797b42bc20831b6db57bChris Lattner for (BasicBlock::iterator I = Succ->begin(); 9714383485ac546e369b11797b42bc20831b6db57bChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) { 9814383485ac546e369b11797b42bc20831b6db57bChris Lattner int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 9914383485ac546e369b11797b42bc20831b6db57bChris Lattner assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 10014383485ac546e369b11797b42bc20831b6db57bChris Lattner PN->setIncomingBlock((unsigned)BlockIdx, CurBlock); 10114383485ac546e369b11797b42bc20831b6db57bChris Lattner } 10214383485ac546e369b11797b42bc20831b6db57bChris Lattner 10320af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner if (i == e-2) { // Is this looking at the default destination? 10420af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner // If there is an entry in any PHI nodes for the default edge, make sure 10520af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner // to update them as well. 10620af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner for (BasicBlock::iterator I = NextBlock->begin(); 10720af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) { 10820af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 10920af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 11020af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner PN->setIncomingBlock((unsigned)BlockIdx, CurBlock); 11120af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner } 11220af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner } 11320af3222da5dea65246ecd9f64a53ea3e3cc1b8aChris Lattner 11414383485ac546e369b11797b42bc20831b6db57bChris Lattner CurBlock = NextBlock; // Move on to the next condition 11514383485ac546e369b11797b42bc20831b6db57bChris Lattner } 11614383485ac546e369b11797b42bc20831b6db57bChris Lattner 11714383485ac546e369b11797b42bc20831b6db57bChris Lattner // We are now done with the switch instruction, delete it. 11814383485ac546e369b11797b42bc20831b6db57bChris Lattner delete SI; 11914383485ac546e369b11797b42bc20831b6db57bChris Lattner} 120