LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

LowerSwitch.cpp

Go to the documentation of this file.
00001 //===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // The LowerSwitch transformation rewrites switch statements with a sequence of
00011 // branches, which allows targets to get away with not implementing the switch
00012 // statement until it is convenient.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Transforms/Scalar.h"
00017 #include "llvm/Constants.h"
00018 #include "llvm/Function.h"
00019 #include "llvm/Instructions.h"
00020 #include "llvm/Pass.h"
00021 #include "llvm/Support/Debug.h"
00022 #include "llvm/ADT/Statistic.h"
00023 #include <algorithm>
00024 using namespace llvm;
00025 
00026 namespace {
00027   Statistic<> NumLowered("lowerswitch", "Number of SwitchInst's replaced");
00028 
00029   /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch
00030   /// instructions.  Note that this cannot be a BasicBlock pass because it
00031   /// modifies the CFG!
00032   class LowerSwitch : public FunctionPass {
00033   public:
00034     bool runOnFunction(Function &F);
00035     typedef std::pair<Constant*, BasicBlock*> Case;
00036     typedef std::vector<Case>::iterator       CaseItr;
00037   private:
00038     void processSwitchInst(SwitchInst *SI);
00039 
00040     BasicBlock* switchConvert(CaseItr Begin, CaseItr End, Value* Val,
00041                               BasicBlock* OrigBlock, BasicBlock* Default);
00042     BasicBlock* newLeafBlock(Case& Leaf, Value* Val,
00043                              BasicBlock* OrigBlock, BasicBlock* Default);
00044   };
00045 
00046   /// The comparison function for sorting the switch case values in the vector.
00047   struct CaseCmp {
00048     bool operator () (const LowerSwitch::Case& C1,
00049                       const LowerSwitch::Case& C2) {
00050       if (const ConstantUInt* U1 = dyn_cast<const ConstantUInt>(C1.first))
00051         return U1->getValue() < cast<const ConstantUInt>(C2.first)->getValue();
00052 
00053       const ConstantSInt* S1 = dyn_cast<const ConstantSInt>(C1.first);
00054       return S1->getValue() < cast<const ConstantSInt>(C2.first)->getValue();
00055     }
00056   };
00057 
00058   RegisterOpt<LowerSwitch>
00059   X("lowerswitch", "Lower SwitchInst's to branches");
00060 }
00061 
00062 // createLowerSwitchPass - Interface to this file...
00063 FunctionPass *llvm::createLowerSwitchPass() {
00064   return new LowerSwitch();
00065 }
00066 
00067 bool LowerSwitch::runOnFunction(Function &F) {
00068   bool Changed = false;
00069 
00070   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
00071     BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks
00072 
00073     if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) {
00074       Changed = true;
00075       processSwitchInst(SI);
00076     }
00077   }
00078 
00079   return Changed;
00080 }
00081 
00082 // operator<< - Used for debugging purposes.
00083 //
00084 std::ostream& operator<<(std::ostream &O,
00085                          const std::vector<LowerSwitch::Case> &C) {
00086   O << "[";
00087 
00088   for (std::vector<LowerSwitch::Case>::const_iterator B = C.begin(),
00089          E = C.end(); B != E; ) {
00090     O << *B->first;
00091     if (++B != E) O << ", ";
00092   }
00093 
00094   return O << "]";
00095 }
00096 
00097 // switchConvert - Convert the switch statement into a binary lookup of
00098 // the case values. The function recursively builds this tree.
00099 //
00100 BasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End,
00101                                        Value* Val, BasicBlock* OrigBlock,
00102                                        BasicBlock* Default)
00103 {
00104   unsigned Size = End - Begin;
00105 
00106   if (Size == 1)
00107     return newLeafBlock(*Begin, Val, OrigBlock, Default);
00108 
00109   unsigned Mid = Size / 2;
00110   std::vector<Case> LHS(Begin, Begin + Mid);
00111   DEBUG(std::cerr << "LHS: " << LHS << "\n");
00112   std::vector<Case> RHS(Begin + Mid, End);
00113   DEBUG(std::cerr << "RHS: " << RHS << "\n");
00114 
00115   Case& Pivot = *(Begin + Mid);
00116   DEBUG(std::cerr << "Pivot ==> "
00117                   << (int64_t)cast<ConstantInt>(Pivot.first)->getRawValue()
00118                   << "\n");
00119 
00120   BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val,
00121                                       OrigBlock, Default);
00122   BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val,
00123                                       OrigBlock, Default);
00124 
00125   // Create a new node that checks if the value is < pivot. Go to the
00126   // left branch if it is and right branch if not.
00127   Function* F = OrigBlock->getParent();
00128   BasicBlock* NewNode = new BasicBlock("NodeBlock");
00129   F->getBasicBlockList().insert(OrigBlock->getNext(), NewNode);
00130 
00131   SetCondInst* Comp = new SetCondInst(Instruction::SetLT, Val, Pivot.first,
00132                                       "Pivot");
00133   NewNode->getInstList().push_back(Comp);
00134   new BranchInst(LBranch, RBranch, Comp, NewNode);
00135   return NewNode;
00136 }
00137 
00138 // newLeafBlock - Create a new leaf block for the binary lookup tree. It
00139 // checks if the switch's value == the case's value. If not, then it
00140 // jumps to the default branch. At this point in the tree, the value
00141 // can't be another valid case value, so the jump to the "default" branch
00142 // is warranted.
00143 //
00144 BasicBlock* LowerSwitch::newLeafBlock(Case& Leaf, Value* Val,
00145                                       BasicBlock* OrigBlock,
00146                                       BasicBlock* Default)
00147 {
00148   Function* F = OrigBlock->getParent();
00149   BasicBlock* NewLeaf = new BasicBlock("LeafBlock");
00150   F->getBasicBlockList().insert(OrigBlock->getNext(), NewLeaf);
00151 
00152   // Make the seteq instruction...
00153   SetCondInst* Comp = new SetCondInst(Instruction::SetEQ, Val,
00154                                       Leaf.first, "SwitchLeaf");
00155   NewLeaf->getInstList().push_back(Comp);
00156 
00157   // Make the conditional branch...
00158   BasicBlock* Succ = Leaf.second;
00159   new BranchInst(Succ, Default, Comp, NewLeaf);
00160 
00161   // If there were any PHI nodes in this successor, rewrite one entry
00162   // from OrigBlock to come from NewLeaf.
00163   for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
00164     PHINode* PN = cast<PHINode>(I);
00165     int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
00166     assert(BlockIdx != -1 && "Switch didn't go to this successor??");
00167     PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf);
00168   }
00169 
00170   return NewLeaf;
00171 }
00172 
00173 // processSwitchInst - Replace the specified switch instruction with a sequence
00174 // of chained if-then insts in a balanced binary search.
00175 //
00176 void LowerSwitch::processSwitchInst(SwitchInst *SI) {
00177   BasicBlock *CurBlock = SI->getParent();
00178   BasicBlock *OrigBlock = CurBlock;
00179   Function *F = CurBlock->getParent();
00180   Value *Val = SI->getOperand(0);  // The value we are switching on...
00181   BasicBlock* Default = SI->getDefaultDest();
00182 
00183   // If there is only the default destination, don't bother with the code below.
00184   if (SI->getNumOperands() == 2) {
00185     new BranchInst(SI->getDefaultDest(), CurBlock);
00186     CurBlock->getInstList().erase(SI);
00187     return;
00188   }
00189 
00190   // Create a new, empty default block so that the new hierarchy of
00191   // if-then statements go to this and the PHI nodes are happy.
00192   BasicBlock* NewDefault = new BasicBlock("NewDefault");
00193   F->getBasicBlockList().insert(Default, NewDefault);
00194 
00195   new BranchInst(Default, NewDefault);
00196 
00197   // If there is an entry in any PHI nodes for the default edge, make sure
00198   // to update them as well.
00199   for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) {
00200     PHINode *PN = cast<PHINode>(I);
00201     int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
00202     assert(BlockIdx != -1 && "Switch didn't go to this successor??");
00203     PN->setIncomingBlock((unsigned)BlockIdx, NewDefault);
00204   }
00205 
00206   std::vector<Case> Cases;
00207 
00208   // Expand comparisons for all of the non-default cases...
00209   for (unsigned i = 1; i < SI->getNumSuccessors(); ++i)
00210     Cases.push_back(Case(SI->getSuccessorValue(i), SI->getSuccessor(i)));
00211 
00212   std::sort(Cases.begin(), Cases.end(), CaseCmp());
00213   DEBUG(std::cerr << "Cases: " << Cases << "\n");
00214   BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val,
00215                                           OrigBlock, NewDefault);
00216 
00217   // Branch to our shiny new if-then stuff...
00218   new BranchInst(SwitchBlock, OrigBlock);
00219 
00220   // We are now done with the switch instruction, delete it.
00221   CurBlock->getInstList().erase(SI);
00222 }