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