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 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 }