LowerSwitch.cpp revision 19df3876e6dce016ec4c5ab28320a246ab285001 
1//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===//
2//
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.
6//
7//===----------------------------------------------------------------------===//
8
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"
16
17namespace {
18  Statistic<> NumLowered("lowerswitch", "Number of SwitchInst's replaced");
19
20  /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch
21  /// instructions.  Note that this cannot be a BasicBlock pass because it
22  /// modifies the CFG!
23  struct LowerSwitch : public FunctionPass {
24    bool runOnFunction(Function &F);
25    void processSwitchInst(SwitchInst *SI);
26  };
27
28  RegisterOpt<LowerSwitch>
29  X("lowerswitch", "Lower SwitchInst's to branches");
30}
31
32// createLowerSwitchPass - Interface to this file...
33FunctionPass *createLowerSwitchPass() {
34  return new LowerSwitch();
35}
36
37bool LowerSwitch::runOnFunction(Function &F) {
38  bool Changed = false;
39
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
42
43    if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) {
44      Changed = true;
45      processSwitchInst(SI);
46    }
47  }
48
49  return Changed;
50}
51
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
56//
57void 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...
62
63  // Unlink the switch instruction from it's block.
64  CurBlock->getInstList().remove(SI);
65
66  // Expand comparisons for all of the non-default cases...
67  for (unsigned i = 2, e = SI->getNumOperands(); i != e; i += 2) {
68    // Insert a new basic block after the current one...
69    BasicBlock *NextBlock;
70    if (i != e-2) {
71      NextBlock = new BasicBlock("switchblock");
72      F->getBasicBlockList().insert(CurBlock->getNext(), NextBlock);
73    } else {   // Last case, if it's not the value, go to default block.
74      NextBlock = cast<BasicBlock>(SI->getDefaultDest());
75    }
76
77    // Make the seteq instruction...
78    Instruction *Comp = new SetCondInst(Instruction::SetEQ, Val,
79                                        SI->getOperand(i), "switchcase");
80    CurBlock->getInstList().push_back(Comp);
81
82    // Make the conditional branch...
83    BasicBlock *Succ = cast<BasicBlock>(SI->getOperand(i+1));
84    Instruction *Br = new BranchInst(Succ, NextBlock, Comp);
85    CurBlock->getInstList().push_back(Br);
86
87    // If there were any PHI nodes in this successor, rewrite one entry from
88    // OrigBlock to come from CurBlock.
89    for (BasicBlock::iterator I = Succ->begin();
90         PHINode *PN = dyn_cast<PHINode>(I); ++I) {
91      int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
92      assert(BlockIdx != -1 && "Switch didn't go to this successor??");
93      PN->setIncomingBlock((unsigned)BlockIdx, CurBlock);
94    }
95
96    if (i == e-2) {  // Is this looking at the default destination?
97      // If there is an entry in any PHI nodes for the default edge, make sure
98      // to update them as well.
99      for (BasicBlock::iterator I = NextBlock->begin();
100           PHINode *PN = dyn_cast<PHINode>(I); ++I) {
101        int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
102        assert(BlockIdx != -1 && "Switch didn't go to this successor??");
103        PN->setIncomingBlock((unsigned)BlockIdx, CurBlock);
104      }
105    }
106
107    CurBlock = NextBlock;  // Move on to the next condition
108  }
109
110  // We are now done with the switch instruction, delete it.
111  delete SI;
112}
113