1 //===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===//
3 // The LowerSwitch transformation rewrites switch statements with a sequence of
4 // branches, which allows targets to get away with not implementing the switch
5 // statement until it is convenient.
7 //===----------------------------------------------------------------------===//
9 #include "llvm/Transforms/Scalar.h"
10 #include "llvm/Function.h"
11 #include "llvm/iTerminators.h"
12 #include "llvm/iOperators.h"
13 #include "llvm/iPHINode.h"
14 #include "llvm/Pass.h"
15 #include "Support/Statistic.h"
18 Statistic<> NumLowered("lowerswitch", "Number of SwitchInst's replaced");
20 /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch
21 /// instructions. Note that this cannot be a BasicBlock pass because it
23 struct LowerSwitch : public FunctionPass {
24 bool runOnFunction(Function &F);
25 void processSwitchInst(SwitchInst *SI);
28 RegisterOpt<LowerSwitch>
29 X("lowerswitch", "Lower SwitchInst's to branches");
32 // createLowerSwitchPass - Interface to this file...
33 FunctionPass *createLowerSwitchPass() {
34 return new LowerSwitch();
37 bool LowerSwitch::runOnFunction(Function &F) {
40 for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
41 BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks
43 if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) {
45 processSwitchInst(SI);
52 // processSwitchInst - Replace the specified switch instruction with a sequence
53 // of chained basic blocks. Right now we just insert an incredibly stupid
54 // linear sequence of branches. It would be better to do a balanced binary
55 // search eventually. FIXME
57 void LowerSwitch::processSwitchInst(SwitchInst *SI) {
58 BasicBlock *CurBlock = SI->getParent();
59 BasicBlock *OrigBlock = CurBlock;
60 Function *F = CurBlock->getParent();
61 Value *Val = SI->getOperand(0); // The value we are switching on...
63 // Unlink the switch instruction from it's block.
64 CurBlock->getInstList().remove(SI);
66 // If there is only the default destination, don't bother with the code below.
67 if (SI->getNumOperands() == 2) {
68 CurBlock->getInstList().push_back(new BranchInst(SI->getDefaultDest()));
73 // Expand comparisons for all of the non-default cases...
74 for (unsigned i = 2, e = SI->getNumOperands(); i != e; i += 2) {
75 // Insert a new basic block after the current one...
76 BasicBlock *NextBlock;
78 NextBlock = new BasicBlock("switchblock");
79 F->getBasicBlockList().insert(CurBlock->getNext(), NextBlock);
80 } else { // Last case, if it's not the value, go to default block.
81 NextBlock = cast<BasicBlock>(SI->getDefaultDest());
84 // Make the seteq instruction...
85 Instruction *Comp = new SetCondInst(Instruction::SetEQ, Val,
86 SI->getOperand(i), "switchcase");
87 CurBlock->getInstList().push_back(Comp);
89 // Make the conditional branch...
90 BasicBlock *Succ = cast<BasicBlock>(SI->getOperand(i+1));
91 Instruction *Br = new BranchInst(Succ, NextBlock, Comp);
92 CurBlock->getInstList().push_back(Br);
94 // If there were any PHI nodes in this successor, rewrite one entry from
95 // OrigBlock to come from CurBlock.
96 for (BasicBlock::iterator I = Succ->begin();
97 PHINode *PN = dyn_cast<PHINode>(I); ++I) {
98 int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
99 assert(BlockIdx != -1 && "Switch didn't go to this successor??");
100 PN->setIncomingBlock((unsigned)BlockIdx, CurBlock);
103 if (i == e-2) { // Is this looking at the default destination?
104 // If there is an entry in any PHI nodes for the default edge, make sure
105 // to update them as well.
106 for (BasicBlock::iterator I = NextBlock->begin();
107 PHINode *PN = dyn_cast<PHINode>(I); ++I) {
108 int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
109 assert(BlockIdx != -1 && "Switch didn't go to this successor??");
110 PN->setIncomingBlock((unsigned)BlockIdx, CurBlock);
114 CurBlock = NextBlock; // Move on to the next condition
117 // We are now done with the switch instruction, delete it.