LLVM API Documentation
00001 //===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // The LowerSwitch transformation rewrites switch instructions with a sequence 00011 // of branches, which allows targets to get away with not implementing the 00012 // switch instruction until it is convenient. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #include "llvm/Transforms/Scalar.h" 00017 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 00018 #include "llvm/Constants.h" 00019 #include "llvm/Function.h" 00020 #include "llvm/Instructions.h" 00021 #include "llvm/LLVMContext.h" 00022 #include "llvm/Pass.h" 00023 #include "llvm/ADT/STLExtras.h" 00024 #include "llvm/Support/Debug.h" 00025 #include "llvm/Support/Compiler.h" 00026 #include "llvm/Support/raw_ostream.h" 00027 #include <algorithm> 00028 using namespace llvm; 00029 00030 namespace { 00031 /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch 00032 /// instructions. Note that this cannot be a BasicBlock pass because it 00033 /// modifies the CFG! 00034 class VISIBILITY_HIDDEN LowerSwitch : public FunctionPass { 00035 public: 00036 static char ID; // Pass identification, replacement for typeid 00037 LowerSwitch() : FunctionPass(&ID) {} 00038 00039 virtual bool runOnFunction(Function &F); 00040 00041 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00042 // This is a cluster of orthogonal Transforms 00043 AU.addPreserved<UnifyFunctionExitNodes>(); 00044 AU.addPreservedID(PromoteMemoryToRegisterID); 00045 AU.addPreservedID(LowerInvokePassID); 00046 AU.addPreservedID(LowerAllocationsID); 00047 } 00048 00049 struct CaseRange { 00050 Constant* Low; 00051 Constant* High; 00052 BasicBlock* BB; 00053 00054 CaseRange() : Low(0), High(0), BB(0) { } 00055 CaseRange(Constant* low, Constant* high, BasicBlock* bb) : 00056 Low(low), High(high), BB(bb) { } 00057 }; 00058 00059 typedef std::vector<CaseRange> CaseVector; 00060 typedef std::vector<CaseRange>::iterator CaseItr; 00061 private: 00062 void processSwitchInst(SwitchInst *SI); 00063 00064 BasicBlock* switchConvert(CaseItr Begin, CaseItr End, Value* Val, 00065 BasicBlock* OrigBlock, BasicBlock* Default); 00066 BasicBlock* newLeafBlock(CaseRange& Leaf, Value* Val, 00067 BasicBlock* OrigBlock, BasicBlock* Default); 00068 unsigned Clusterify(CaseVector& Cases, SwitchInst *SI); 00069 }; 00070 00071 /// The comparison function for sorting the switch case values in the vector. 00072 /// WARNING: Case ranges should be disjoint! 00073 struct CaseCmp { 00074 bool operator () (const LowerSwitch::CaseRange& C1, 00075 const LowerSwitch::CaseRange& C2) { 00076 00077 const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 00078 const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 00079 return CI1->getValue().slt(CI2->getValue()); 00080 } 00081 }; 00082 } 00083 00084 char LowerSwitch::ID = 0; 00085 static RegisterPass<LowerSwitch> 00086 X("lowerswitch", "Lower SwitchInst's to branches"); 00087 00088 // Publically exposed interface to pass... 00089 const PassInfo *const llvm::LowerSwitchID = &X; 00090 // createLowerSwitchPass - Interface to this file... 00091 FunctionPass *llvm::createLowerSwitchPass() { 00092 return new LowerSwitch(); 00093 } 00094 00095 bool LowerSwitch::runOnFunction(Function &F) { 00096 bool Changed = false; 00097 00098 for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 00099 BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 00100 00101 if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 00102 Changed = true; 00103 processSwitchInst(SI); 00104 } 00105 } 00106 00107 return Changed; 00108 } 00109 00110 // operator<< - Used for debugging purposes. 00111 // 00112 static raw_ostream& operator<<(raw_ostream &O, 00113 const LowerSwitch::CaseVector &C) ATTRIBUTE_USED; 00114 static raw_ostream& operator<<(raw_ostream &O, 00115 const LowerSwitch::CaseVector &C) { 00116 O << "["; 00117 00118 for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 00119 E = C.end(); B != E; ) { 00120 O << *B->Low << " -" << *B->High; 00121 if (++B != E) O << ", "; 00122 } 00123 00124 return O << "]"; 00125 } 00126 00127 // switchConvert - Convert the switch statement into a binary lookup of 00128 // the case values. The function recursively builds this tree. 00129 // 00130 BasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, 00131 Value* Val, BasicBlock* OrigBlock, 00132 BasicBlock* Default) 00133 { 00134 unsigned Size = End - Begin; 00135 00136 if (Size == 1) 00137 return newLeafBlock(*Begin, Val, OrigBlock, Default); 00138 00139 unsigned Mid = Size / 2; 00140 std::vector<CaseRange> LHS(Begin, Begin + Mid); 00141 DEBUG(errs() << "LHS: " << LHS << "\n"); 00142 std::vector<CaseRange> RHS(Begin + Mid, End); 00143 DEBUG(errs() << "RHS: " << RHS << "\n"); 00144 00145 CaseRange& Pivot = *(Begin + Mid); 00146 DEBUG(errs() << "Pivot ==> " 00147 << cast<ConstantInt>(Pivot.Low)->getValue() << " -" 00148 << cast<ConstantInt>(Pivot.High)->getValue() << "\n"); 00149 00150 BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val, 00151 OrigBlock, Default); 00152 BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val, 00153 OrigBlock, Default); 00154 00155 // Create a new node that checks if the value is < pivot. Go to the 00156 // left branch if it is and right branch if not. 00157 Function* F = OrigBlock->getParent(); 00158 BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock"); 00159 Function::iterator FI = OrigBlock; 00160 F->getBasicBlockList().insert(++FI, NewNode); 00161 00162 ICmpInst* Comp = new ICmpInst(Default->getContext(), ICmpInst::ICMP_SLT, 00163 Val, Pivot.Low, "Pivot"); 00164 NewNode->getInstList().push_back(Comp); 00165 BranchInst::Create(LBranch, RBranch, Comp, NewNode); 00166 return NewNode; 00167 } 00168 00169 // newLeafBlock - Create a new leaf block for the binary lookup tree. It 00170 // checks if the switch's value == the case's value. If not, then it 00171 // jumps to the default branch. At this point in the tree, the value 00172 // can't be another valid case value, so the jump to the "default" branch 00173 // is warranted. 00174 // 00175 BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, 00176 BasicBlock* OrigBlock, 00177 BasicBlock* Default) 00178 { 00179 Function* F = OrigBlock->getParent(); 00180 BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock"); 00181 Function::iterator FI = OrigBlock; 00182 F->getBasicBlockList().insert(++FI, NewLeaf); 00183 00184 // Emit comparison 00185 ICmpInst* Comp = NULL; 00186 if (Leaf.Low == Leaf.High) { 00187 // Make the seteq instruction... 00188 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, 00189 Leaf.Low, "SwitchLeaf"); 00190 } else { 00191 // Make range comparison 00192 if (cast<ConstantInt>(Leaf.Low)->isMinValue(true /*isSigned*/)) { 00193 // Val >= Min && Val <= Hi --> Val <= Hi 00194 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, 00195 "SwitchLeaf"); 00196 } else if (cast<ConstantInt>(Leaf.Low)->isZero()) { 00197 // Val >= 0 && Val <= Hi --> Val <=u Hi 00198 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, 00199 "SwitchLeaf"); 00200 } else { 00201 // Emit V-Lo <=u Hi-Lo 00202 Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); 00203 Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 00204 Val->getName()+".off", 00205 NewLeaf); 00206 Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); 00207 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, 00208 "SwitchLeaf"); 00209 } 00210 } 00211 00212 // Make the conditional branch... 00213 BasicBlock* Succ = Leaf.BB; 00214 BranchInst::Create(Succ, Default, Comp, NewLeaf); 00215 00216 // If there were any PHI nodes in this successor, rewrite one entry 00217 // from OrigBlock to come from NewLeaf. 00218 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 00219 PHINode* PN = cast<PHINode>(I); 00220 // Remove all but one incoming entries from the cluster 00221 uint64_t Range = cast<ConstantInt>(Leaf.High)->getSExtValue() - 00222 cast<ConstantInt>(Leaf.Low)->getSExtValue(); 00223 for (uint64_t j = 0; j < Range; ++j) { 00224 PN->removeIncomingValue(OrigBlock); 00225 } 00226 00227 int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 00228 assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 00229 PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 00230 } 00231 00232 return NewLeaf; 00233 } 00234 00235 // Clusterify - Transform simple list of Cases into list of CaseRange's 00236 unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 00237 unsigned numCmps = 0; 00238 00239 // Start with "simple" cases 00240 for (unsigned i = 1; i < SI->getNumSuccessors(); ++i) 00241 Cases.push_back(CaseRange(SI->getSuccessorValue(i), 00242 SI->getSuccessorValue(i), 00243 SI->getSuccessor(i))); 00244 std::sort(Cases.begin(), Cases.end(), CaseCmp()); 00245 00246 // Merge case into clusters 00247 if (Cases.size()>=2) 00248 for (CaseItr I=Cases.begin(), J=next(Cases.begin()); J!=Cases.end(); ) { 00249 int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue(); 00250 int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue(); 00251 BasicBlock* nextBB = J->BB; 00252 BasicBlock* currentBB = I->BB; 00253 00254 // If the two neighboring cases go to the same destination, merge them 00255 // into a single case. 00256 if ((nextValue-currentValue==1) && (currentBB == nextBB)) { 00257 I->High = J->High; 00258 J = Cases.erase(J); 00259 } else { 00260 I = J++; 00261 } 00262 } 00263 00264 for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 00265 if (I->Low != I->High) 00266 // A range counts double, since it requires two compares. 00267 ++numCmps; 00268 } 00269 00270 return numCmps; 00271 } 00272 00273 // processSwitchInst - Replace the specified switch instruction with a sequence 00274 // of chained if-then insts in a balanced binary search. 00275 // 00276 void LowerSwitch::processSwitchInst(SwitchInst *SI) { 00277 BasicBlock *CurBlock = SI->getParent(); 00278 BasicBlock *OrigBlock = CurBlock; 00279 Function *F = CurBlock->getParent(); 00280 Value *Val = SI->getOperand(0); // The value we are switching on... 00281 BasicBlock* Default = SI->getDefaultDest(); 00282 00283 // If there is only the default destination, don't bother with the code below. 00284 if (SI->getNumOperands() == 2) { 00285 BranchInst::Create(SI->getDefaultDest(), CurBlock); 00286 CurBlock->getInstList().erase(SI); 00287 return; 00288 } 00289 00290 // Create a new, empty default block so that the new hierarchy of 00291 // if-then statements go to this and the PHI nodes are happy. 00292 BasicBlock* NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); 00293 F->getBasicBlockList().insert(Default, NewDefault); 00294 00295 BranchInst::Create(Default, NewDefault); 00296 00297 // If there is an entry in any PHI nodes for the default edge, make sure 00298 // to update them as well. 00299 for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 00300 PHINode *PN = cast<PHINode>(I); 00301 int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 00302 assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 00303 PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 00304 } 00305 00306 // Prepare cases vector. 00307 CaseVector Cases; 00308 unsigned numCmps = Clusterify(Cases, SI); 00309 00310 DEBUG(errs() << "Clusterify finished. Total clusters: " << Cases.size() 00311 << ". Total compares: " << numCmps << "\n"); 00312 DEBUG(errs() << "Cases: " << Cases << "\n"); 00313 (void)numCmps; 00314 00315 BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val, 00316 OrigBlock, NewDefault); 00317 00318 // Branch to our shiny new if-then stuff... 00319 BranchInst::Create(SwitchBlock, OrigBlock); 00320 00321 // We are now done with the switch instruction, delete it. 00322 CurBlock->getInstList().erase(SI); 00323 }