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