LowerSwitch.cpp revision 02efa786d40fabae6dbbb3de5ab057359701e337
1//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// The LowerSwitch transformation rewrites switch instructions with a sequence 11// of branches, which allows targets to get away with not implementing the 12// switch instruction until it is convenient. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/Transforms/Scalar.h" 17#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 18#include "llvm/Constants.h" 19#include "llvm/Function.h" 20#include "llvm/Instructions.h" 21#include "llvm/LLVMContext.h" 22#include "llvm/Pass.h" 23#include "llvm/ADT/STLExtras.h" 24#include "llvm/Support/Debug.h" 25#include "llvm/Support/Compiler.h" 26#include "llvm/Support/raw_ostream.h" 27#include <algorithm> 28using namespace llvm; 29 30namespace { 31 /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch 32 /// instructions. Note that this cannot be a BasicBlock pass because it 33 /// modifies the CFG! 34 class VISIBILITY_HIDDEN LowerSwitch : public FunctionPass { 35 public: 36 static char ID; // Pass identification, replacement for typeid 37 LowerSwitch() : FunctionPass(&ID) {} 38 39 virtual bool runOnFunction(Function &F); 40 41 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 42 // This is a cluster of orthogonal Transforms 43 AU.addPreserved<UnifyFunctionExitNodes>(); 44 AU.addPreservedID(PromoteMemoryToRegisterID); 45 AU.addPreservedID(LowerInvokePassID); 46 AU.addPreservedID(LowerAllocationsID); 47 } 48 49 struct CaseRange { 50 Constant* Low; 51 Constant* High; 52 BasicBlock* BB; 53 54 CaseRange() : Low(0), High(0), BB(0) { } 55 CaseRange(Constant* low, Constant* high, BasicBlock* bb) : 56 Low(low), High(high), BB(bb) { } 57 }; 58 59 typedef std::vector<CaseRange> CaseVector; 60 typedef std::vector<CaseRange>::iterator CaseItr; 61 private: 62 void processSwitchInst(SwitchInst *SI); 63 64 BasicBlock* switchConvert(CaseItr Begin, CaseItr End, Value* Val, 65 BasicBlock* OrigBlock, BasicBlock* Default); 66 BasicBlock* newLeafBlock(CaseRange& Leaf, Value* Val, 67 BasicBlock* OrigBlock, BasicBlock* Default); 68 unsigned Clusterify(CaseVector& Cases, SwitchInst *SI); 69 }; 70 71 /// The comparison function for sorting the switch case values in the vector. 72 /// WARNING: Case ranges should be disjoint! 73 struct CaseCmp { 74 bool operator () (const LowerSwitch::CaseRange& C1, 75 const LowerSwitch::CaseRange& C2) { 76 77 const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 78 const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 79 return CI1->getValue().slt(CI2->getValue()); 80 } 81 }; 82} 83 84char LowerSwitch::ID = 0; 85static RegisterPass<LowerSwitch> 86X("lowerswitch", "Lower SwitchInst's to branches"); 87 88// Publically exposed interface to pass... 89const PassInfo *const llvm::LowerSwitchID = &X; 90// createLowerSwitchPass - Interface to this file... 91FunctionPass *llvm::createLowerSwitchPass() { 92 return new LowerSwitch(); 93} 94 95bool LowerSwitch::runOnFunction(Function &F) { 96 bool Changed = false; 97 98 for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 99 BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 100 101 if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 102 Changed = true; 103 processSwitchInst(SI); 104 } 105 } 106 107 return Changed; 108} 109 110// operator<< - Used for debugging purposes. 111// 112static raw_ostream& operator<<(raw_ostream &O, 113 const LowerSwitch::CaseVector &C) { 114 O << "["; 115 116 for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 117 E = C.end(); B != E; ) { 118 O << *B->Low << " -" << *B->High; 119 if (++B != E) O << ", "; 120 } 121 122 return O << "]"; 123} 124 125// switchConvert - Convert the switch statement into a binary lookup of 126// the case values. The function recursively builds this tree. 127// 128BasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, 129 Value* Val, BasicBlock* OrigBlock, 130 BasicBlock* Default) 131{ 132 unsigned Size = End - Begin; 133 134 if (Size == 1) 135 return newLeafBlock(*Begin, Val, OrigBlock, Default); 136 137 unsigned Mid = Size / 2; 138 std::vector<CaseRange> LHS(Begin, Begin + Mid); 139 DEBUG(errs() << "LHS: " << LHS << "\n"); 140 std::vector<CaseRange> RHS(Begin + Mid, End); 141 DEBUG(errs() << "RHS: " << RHS << "\n"); 142 143 CaseRange& Pivot = *(Begin + Mid); 144 DEBUG(errs() << "Pivot ==> " 145 << cast<ConstantInt>(Pivot.Low)->getValue() << " -" 146 << cast<ConstantInt>(Pivot.High)->getValue() << "\n"); 147 148 BasicBlock* LBranch = switchConvert(LHS.begin(), LHS.end(), Val, 149 OrigBlock, Default); 150 BasicBlock* RBranch = switchConvert(RHS.begin(), RHS.end(), Val, 151 OrigBlock, Default); 152 153 // Create a new node that checks if the value is < pivot. Go to the 154 // left branch if it is and right branch if not. 155 Function* F = OrigBlock->getParent(); 156 BasicBlock* NewNode = BasicBlock::Create("NodeBlock"); 157 Function::iterator FI = OrigBlock; 158 F->getBasicBlockList().insert(++FI, NewNode); 159 160 ICmpInst* Comp = new ICmpInst(Default->getContext(), ICmpInst::ICMP_SLT, 161 Val, Pivot.Low, "Pivot"); 162 NewNode->getInstList().push_back(Comp); 163 BranchInst::Create(LBranch, RBranch, Comp, NewNode); 164 return NewNode; 165} 166 167// newLeafBlock - Create a new leaf block for the binary lookup tree. It 168// checks if the switch's value == the case's value. If not, then it 169// jumps to the default branch. At this point in the tree, the value 170// can't be another valid case value, so the jump to the "default" branch 171// is warranted. 172// 173BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, 174 BasicBlock* OrigBlock, 175 BasicBlock* Default) 176{ 177 Function* F = OrigBlock->getParent(); 178 LLVMContext &Context = F->getContext(); 179 BasicBlock* NewLeaf = BasicBlock::Create("LeafBlock"); 180 Function::iterator FI = OrigBlock; 181 F->getBasicBlockList().insert(++FI, NewLeaf); 182 183 // Emit comparison 184 ICmpInst* Comp = NULL; 185 if (Leaf.Low == Leaf.High) { 186 // Make the seteq instruction... 187 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, 188 Leaf.Low, "SwitchLeaf"); 189 } else { 190 // Make range comparison 191 if (cast<ConstantInt>(Leaf.Low)->isMinValue(true /*isSigned*/)) { 192 // Val >= Min && Val <= Hi --> Val <= Hi 193 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, 194 "SwitchLeaf"); 195 } else if (cast<ConstantInt>(Leaf.Low)->isZero()) { 196 // Val >= 0 && Val <= Hi --> Val <=u Hi 197 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, 198 "SwitchLeaf"); 199 } else { 200 // Emit V-Lo <=u Hi-Lo 201 Constant* NegLo = Context.getConstantExprNeg(Leaf.Low); 202 Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 203 Val->getName()+".off", 204 NewLeaf); 205 Constant *UpperBound = Context.getConstantExprAdd(NegLo, Leaf.High); 206 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, 207 "SwitchLeaf"); 208 } 209 } 210 211 // Make the conditional branch... 212 BasicBlock* Succ = Leaf.BB; 213 BranchInst::Create(Succ, Default, Comp, NewLeaf); 214 215 // If there were any PHI nodes in this successor, rewrite one entry 216 // from OrigBlock to come from NewLeaf. 217 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 218 PHINode* PN = cast<PHINode>(I); 219 // Remove all but one incoming entries from the cluster 220 uint64_t Range = cast<ConstantInt>(Leaf.High)->getSExtValue() - 221 cast<ConstantInt>(Leaf.Low)->getSExtValue(); 222 for (uint64_t j = 0; j < Range; ++j) { 223 PN->removeIncomingValue(OrigBlock); 224 } 225 226 int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 227 assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 228 PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 229 } 230 231 return NewLeaf; 232} 233 234// Clusterify - Transform simple list of Cases into list of CaseRange's 235unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 236 unsigned numCmps = 0; 237 238 // Start with "simple" cases 239 for (unsigned i = 1; i < SI->getNumSuccessors(); ++i) 240 Cases.push_back(CaseRange(SI->getSuccessorValue(i), 241 SI->getSuccessorValue(i), 242 SI->getSuccessor(i))); 243 std::sort(Cases.begin(), Cases.end(), CaseCmp()); 244 245 // Merge case into clusters 246 if (Cases.size()>=2) 247 for (CaseItr I=Cases.begin(), J=next(Cases.begin()); J!=Cases.end(); ) { 248 int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue(); 249 int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue(); 250 BasicBlock* nextBB = J->BB; 251 BasicBlock* currentBB = I->BB; 252 253 // If the two neighboring cases go to the same destination, merge them 254 // into a single case. 255 if ((nextValue-currentValue==1) && (currentBB == nextBB)) { 256 I->High = J->High; 257 J = Cases.erase(J); 258 } else { 259 I = J++; 260 } 261 } 262 263 for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 264 if (I->Low != I->High) 265 // A range counts double, since it requires two compares. 266 ++numCmps; 267 } 268 269 return numCmps; 270} 271 272// processSwitchInst - Replace the specified switch instruction with a sequence 273// of chained if-then insts in a balanced binary search. 274// 275void LowerSwitch::processSwitchInst(SwitchInst *SI) { 276 BasicBlock *CurBlock = SI->getParent(); 277 BasicBlock *OrigBlock = CurBlock; 278 Function *F = CurBlock->getParent(); 279 Value *Val = SI->getOperand(0); // The value we are switching on... 280 BasicBlock* Default = SI->getDefaultDest(); 281 282 // If there is only the default destination, don't bother with the code below. 283 if (SI->getNumOperands() == 2) { 284 BranchInst::Create(SI->getDefaultDest(), CurBlock); 285 CurBlock->getInstList().erase(SI); 286 return; 287 } 288 289 // Create a new, empty default block so that the new hierarchy of 290 // if-then statements go to this and the PHI nodes are happy. 291 BasicBlock* NewDefault = BasicBlock::Create("NewDefault"); 292 F->getBasicBlockList().insert(Default, NewDefault); 293 294 BranchInst::Create(Default, NewDefault); 295 296 // If there is an entry in any PHI nodes for the default edge, make sure 297 // to update them as well. 298 for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 299 PHINode *PN = cast<PHINode>(I); 300 int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 301 assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 302 PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 303 } 304 305 // Prepare cases vector. 306 CaseVector Cases; 307 unsigned numCmps = Clusterify(Cases, SI); 308 309 DEBUG(errs() << "Clusterify finished. Total clusters: " << Cases.size() 310 << ". Total compares: " << numCmps << "\n"); 311 DEBUG(errs() << "Cases: " << Cases << "\n"); 312 (void)numCmps; 313 314 BasicBlock* SwitchBlock = switchConvert(Cases.begin(), Cases.end(), Val, 315 OrigBlock, NewDefault); 316 317 // Branch to our shiny new if-then stuff... 318 BranchInst::Create(SwitchBlock, OrigBlock); 319 320 // We are now done with the switch instruction, delete it. 321 CurBlock->getInstList().erase(SI); 322} 323