lib/Transforms/Utils/LowerSwitch.cpp

   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
  17 namespace {
  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...
  33 FunctionPass *createLowerSwitchPass() {
  34   return new LowerSwitch();
  35 }
  36
  37 bool 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 //
  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...
  62
  63   // Unlink the switch instruction from it's block.
  64   CurBlock->getInstList().remove(SI);
  65
  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()));
  69     delete SI;
  70     return;
  71   }
  72
  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;
  77     if (i != e-2) {
  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());
  82     }
  83
  84     // Make the seteq instruction...
  85     Instruction *Comp = new SetCondInst(Instruction::SetEQ, Val,
  86                                         SI->getOperand(i), "switchcase");
  87     CurBlock->getInstList().push_back(Comp);
  88
  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);
  93
  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);
 101     }
 102
 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);
 111       }
 112     }
 113
 114     CurBlock = NextBlock;  // Move on to the next condition
 115   }
 116
 117   // We are now done with the switch instruction, delete it.
 118   delete SI;
 119 }