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