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/CFG.h" 19 #include "llvm/IR/Constants.h" 20 #include "llvm/IR/Function.h" 21 #include "llvm/IR/Instructions.h" 22 #include "llvm/IR/LLVMContext.h" 23 #include "llvm/Pass.h" 24 #include "llvm/Support/Compiler.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/raw_ostream.h" 27 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 28 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 29 #include <algorithm> 30 using namespace llvm; 31 32 #define DEBUG_TYPE "lower-switch" 33 34 namespace { 35 struct IntRange { 36 int64_t Low, High; 37 }; 38 // Return true iff R is covered by Ranges. 39 static bool IsInRanges(const IntRange &R, 40 const std::vector<IntRange> &Ranges) { 41 // Note: Ranges must be sorted, non-overlapping and non-adjacent. 42 43 // Find the first range whose High field is >= R.High, 44 // then check if the Low field is <= R.Low. If so, we 45 // have a Range that covers R. 46 auto I = std::lower_bound( 47 Ranges.begin(), Ranges.end(), R, 48 [](const IntRange &A, const IntRange &B) { return A.High < B.High; }); 49 return I != Ranges.end() && I->Low <= R.Low; 50 } 51 52 /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch 53 /// instructions. 54 class LowerSwitch : public FunctionPass { 55 public: 56 static char ID; // Pass identification, replacement for typeid 57 LowerSwitch() : FunctionPass(ID) { 58 initializeLowerSwitchPass(*PassRegistry::getPassRegistry()); 59 } 60 61 bool runOnFunction(Function &F) override; 62 63 void getAnalysisUsage(AnalysisUsage &AU) const override { 64 // This is a cluster of orthogonal Transforms 65 AU.addPreserved<UnifyFunctionExitNodes>(); 66 AU.addPreservedID(LowerInvokePassID); 67 } 68 69 struct CaseRange { 70 ConstantInt* Low; 71 ConstantInt* High; 72 BasicBlock* BB; 73 74 CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb) 75 : Low(low), High(high), BB(bb) {} 76 }; 77 78 typedef std::vector<CaseRange> CaseVector; 79 typedef std::vector<CaseRange>::iterator CaseItr; 80 private: 81 void processSwitchInst(SwitchInst *SI); 82 83 BasicBlock *switchConvert(CaseItr Begin, CaseItr End, 84 ConstantInt *LowerBound, ConstantInt *UpperBound, 85 Value *Val, BasicBlock *Predecessor, 86 BasicBlock *OrigBlock, BasicBlock *Default, 87 const std::vector<IntRange> &UnreachableRanges); 88 BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, BasicBlock *OrigBlock, 89 BasicBlock *Default); 90 unsigned Clusterify(CaseVector &Cases, SwitchInst *SI); 91 }; 92 93 /// The comparison function for sorting the switch case values in the vector. 94 /// WARNING: Case ranges should be disjoint! 95 struct CaseCmp { 96 bool operator () (const LowerSwitch::CaseRange& C1, 97 const LowerSwitch::CaseRange& C2) { 98 99 const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 100 const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 101 return CI1->getValue().slt(CI2->getValue()); 102 } 103 }; 104 } 105 106 char LowerSwitch::ID = 0; 107 INITIALIZE_PASS(LowerSwitch, "lowerswitch", 108 "Lower SwitchInst's to branches", false, false) 109 110 // Publicly exposed interface to pass... 111 char &llvm::LowerSwitchID = LowerSwitch::ID; 112 // createLowerSwitchPass - Interface to this file... 113 FunctionPass *llvm::createLowerSwitchPass() { 114 return new LowerSwitch(); 115 } 116 117 bool LowerSwitch::runOnFunction(Function &F) { 118 bool Changed = false; 119 120 for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 121 BasicBlock *Cur = I++; // Advance over block so we don't traverse new blocks 122 123 if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) { 124 Changed = true; 125 processSwitchInst(SI); 126 } 127 } 128 129 return Changed; 130 } 131 132 // operator<< - Used for debugging purposes. 133 // 134 static raw_ostream& operator<<(raw_ostream &O, 135 const LowerSwitch::CaseVector &C) 136 LLVM_ATTRIBUTE_USED; 137 static raw_ostream& operator<<(raw_ostream &O, 138 const LowerSwitch::CaseVector &C) { 139 O << "["; 140 141 for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 142 E = C.end(); B != E; ) { 143 O << *B->Low << " -" << *B->High; 144 if (++B != E) O << ", "; 145 } 146 147 return O << "]"; 148 } 149 150 // \brief Update the first occurrence of the "switch statement" BB in the PHI 151 // node with the "new" BB. The other occurrences will: 152 // 153 // 1) Be updated by subsequent calls to this function. Switch statements may 154 // have more than one outcoming edge into the same BB if they all have the same 155 // value. When the switch statement is converted these incoming edges are now 156 // coming from multiple BBs. 157 // 2) Removed if subsequent incoming values now share the same case, i.e., 158 // multiple outcome edges are condensed into one. This is necessary to keep the 159 // number of phi values equal to the number of branches to SuccBB. 160 static void fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB, 161 unsigned NumMergedCases) { 162 for (BasicBlock::iterator I = SuccBB->begin(), IE = SuccBB->getFirstNonPHI(); 163 I != IE; ++I) { 164 PHINode *PN = cast<PHINode>(I); 165 166 // Only update the first occurence. 167 unsigned Idx = 0, E = PN->getNumIncomingValues(); 168 unsigned LocalNumMergedCases = NumMergedCases; 169 for (; Idx != E; ++Idx) { 170 if (PN->getIncomingBlock(Idx) == OrigBB) { 171 PN->setIncomingBlock(Idx, NewBB); 172 break; 173 } 174 } 175 176 // Remove additional occurences coming from condensed cases and keep the 177 // number of incoming values equal to the number of branches to SuccBB. 178 SmallVector<unsigned, 8> Indices; 179 for (++Idx; LocalNumMergedCases > 0 && Idx < E; ++Idx) 180 if (PN->getIncomingBlock(Idx) == OrigBB) { 181 Indices.push_back(Idx); 182 LocalNumMergedCases--; 183 } 184 // Remove incoming values in the reverse order to prevent invalidating 185 // *successive* index. 186 for (auto III = Indices.rbegin(), IIE = Indices.rend(); III != IIE; ++III) 187 PN->removeIncomingValue(*III); 188 } 189 } 190 191 // switchConvert - Convert the switch statement into a binary lookup of 192 // the case values. The function recursively builds this tree. 193 // LowerBound and UpperBound are used to keep track of the bounds for Val 194 // that have already been checked by a block emitted by one of the previous 195 // calls to switchConvert in the call stack. 196 BasicBlock * 197 LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound, 198 ConstantInt *UpperBound, Value *Val, 199 BasicBlock *Predecessor, BasicBlock *OrigBlock, 200 BasicBlock *Default, 201 const std::vector<IntRange> &UnreachableRanges) { 202 unsigned Size = End - Begin; 203 204 if (Size == 1) { 205 // Check if the Case Range is perfectly squeezed in between 206 // already checked Upper and Lower bounds. If it is then we can avoid 207 // emitting the code that checks if the value actually falls in the range 208 // because the bounds already tell us so. 209 if (Begin->Low == LowerBound && Begin->High == UpperBound) { 210 unsigned NumMergedCases = 0; 211 if (LowerBound && UpperBound) 212 NumMergedCases = 213 UpperBound->getSExtValue() - LowerBound->getSExtValue(); 214 fixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases); 215 return Begin->BB; 216 } 217 return newLeafBlock(*Begin, Val, OrigBlock, Default); 218 } 219 220 unsigned Mid = Size / 2; 221 std::vector<CaseRange> LHS(Begin, Begin + Mid); 222 DEBUG(dbgs() << "LHS: " << LHS << "\n"); 223 std::vector<CaseRange> RHS(Begin + Mid, End); 224 DEBUG(dbgs() << "RHS: " << RHS << "\n"); 225 226 CaseRange &Pivot = *(Begin + Mid); 227 DEBUG(dbgs() << "Pivot ==> " 228 << Pivot.Low->getValue() 229 << " -" << Pivot.High->getValue() << "\n"); 230 231 // NewLowerBound here should never be the integer minimal value. 232 // This is because it is computed from a case range that is never 233 // the smallest, so there is always a case range that has at least 234 // a smaller value. 235 ConstantInt *NewLowerBound = Pivot.Low; 236 237 // Because NewLowerBound is never the smallest representable integer 238 // it is safe here to subtract one. 239 ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(), 240 NewLowerBound->getValue() - 1); 241 242 if (!UnreachableRanges.empty()) { 243 // Check if the gap between LHS's highest and NewLowerBound is unreachable. 244 int64_t GapLow = LHS.back().High->getSExtValue() + 1; 245 int64_t GapHigh = NewLowerBound->getSExtValue() - 1; 246 IntRange Gap = { GapLow, GapHigh }; 247 if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges)) 248 NewUpperBound = LHS.back().High; 249 } 250 251 DEBUG(dbgs() << "LHS Bounds ==> "; 252 if (LowerBound) { 253 dbgs() << LowerBound->getSExtValue(); 254 } else { 255 dbgs() << "NONE"; 256 } 257 dbgs() << " - " << NewUpperBound->getSExtValue() << "\n"; 258 dbgs() << "RHS Bounds ==> "; 259 dbgs() << NewLowerBound->getSExtValue() << " - "; 260 if (UpperBound) { 261 dbgs() << UpperBound->getSExtValue() << "\n"; 262 } else { 263 dbgs() << "NONE\n"; 264 }); 265 266 // Create a new node that checks if the value is < pivot. Go to the 267 // left branch if it is and right branch if not. 268 Function* F = OrigBlock->getParent(); 269 BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock"); 270 271 ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, 272 Val, Pivot.Low, "Pivot"); 273 274 BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound, 275 NewUpperBound, Val, NewNode, OrigBlock, 276 Default, UnreachableRanges); 277 BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound, 278 UpperBound, Val, NewNode, OrigBlock, 279 Default, UnreachableRanges); 280 281 Function::iterator FI = OrigBlock; 282 F->getBasicBlockList().insert(++FI, NewNode); 283 NewNode->getInstList().push_back(Comp); 284 285 BranchInst::Create(LBranch, RBranch, Comp, NewNode); 286 return NewNode; 287 } 288 289 // newLeafBlock - Create a new leaf block for the binary lookup tree. It 290 // checks if the switch's value == the case's value. If not, then it 291 // jumps to the default branch. At this point in the tree, the value 292 // can't be another valid case value, so the jump to the "default" branch 293 // is warranted. 294 // 295 BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, 296 BasicBlock* OrigBlock, 297 BasicBlock* Default) 298 { 299 Function* F = OrigBlock->getParent(); 300 BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock"); 301 Function::iterator FI = OrigBlock; 302 F->getBasicBlockList().insert(++FI, NewLeaf); 303 304 // Emit comparison 305 ICmpInst* Comp = nullptr; 306 if (Leaf.Low == Leaf.High) { 307 // Make the seteq instruction... 308 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, 309 Leaf.Low, "SwitchLeaf"); 310 } else { 311 // Make range comparison 312 if (Leaf.Low->isMinValue(true /*isSigned*/)) { 313 // Val >= Min && Val <= Hi --> Val <= Hi 314 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, 315 "SwitchLeaf"); 316 } else if (Leaf.Low->isZero()) { 317 // Val >= 0 && Val <= Hi --> Val <=u Hi 318 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, 319 "SwitchLeaf"); 320 } else { 321 // Emit V-Lo <=u Hi-Lo 322 Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); 323 Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 324 Val->getName()+".off", 325 NewLeaf); 326 Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); 327 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, 328 "SwitchLeaf"); 329 } 330 } 331 332 // Make the conditional branch... 333 BasicBlock* Succ = Leaf.BB; 334 BranchInst::Create(Succ, Default, Comp, NewLeaf); 335 336 // If there were any PHI nodes in this successor, rewrite one entry 337 // from OrigBlock to come from NewLeaf. 338 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 339 PHINode* PN = cast<PHINode>(I); 340 // Remove all but one incoming entries from the cluster 341 uint64_t Range = Leaf.High->getSExtValue() - 342 Leaf.Low->getSExtValue(); 343 for (uint64_t j = 0; j < Range; ++j) { 344 PN->removeIncomingValue(OrigBlock); 345 } 346 347 int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 348 assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 349 PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 350 } 351 352 return NewLeaf; 353 } 354 355 // Clusterify - Transform simple list of Cases into list of CaseRange's 356 unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 357 unsigned numCmps = 0; 358 359 // Start with "simple" cases 360 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) 361 Cases.push_back(CaseRange(i.getCaseValue(), i.getCaseValue(), 362 i.getCaseSuccessor())); 363 364 std::sort(Cases.begin(), Cases.end(), CaseCmp()); 365 366 // Merge case into clusters 367 if (Cases.size()>=2) 368 for (CaseItr I = Cases.begin(), J = std::next(Cases.begin()); 369 J != Cases.end();) { 370 int64_t nextValue = J->Low->getSExtValue(); 371 int64_t currentValue = I->High->getSExtValue(); 372 BasicBlock* nextBB = J->BB; 373 BasicBlock* currentBB = I->BB; 374 375 // If the two neighboring cases go to the same destination, merge them 376 // into a single case. 377 if ((nextValue-currentValue==1) && (currentBB == nextBB)) { 378 I->High = J->High; 379 J = Cases.erase(J); 380 } else { 381 I = J++; 382 } 383 } 384 385 for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 386 if (I->Low != I->High) 387 // A range counts double, since it requires two compares. 388 ++numCmps; 389 } 390 391 return numCmps; 392 } 393 394 // processSwitchInst - Replace the specified switch instruction with a sequence 395 // of chained if-then insts in a balanced binary search. 396 // 397 void LowerSwitch::processSwitchInst(SwitchInst *SI) { 398 BasicBlock *CurBlock = SI->getParent(); 399 BasicBlock *OrigBlock = CurBlock; 400 Function *F = CurBlock->getParent(); 401 Value *Val = SI->getCondition(); // The value we are switching on... 402 BasicBlock* Default = SI->getDefaultDest(); 403 404 // If there is only the default destination, just branch. 405 if (!SI->getNumCases()) { 406 BranchInst::Create(Default, CurBlock); 407 SI->eraseFromParent(); 408 return; 409 } 410 411 // Prepare cases vector. 412 CaseVector Cases; 413 unsigned numCmps = Clusterify(Cases, SI); 414 DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() 415 << ". Total compares: " << numCmps << "\n"); 416 DEBUG(dbgs() << "Cases: " << Cases << "\n"); 417 (void)numCmps; 418 419 ConstantInt *LowerBound = nullptr; 420 ConstantInt *UpperBound = nullptr; 421 std::vector<IntRange> UnreachableRanges; 422 423 if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) { 424 // Make the bounds tightly fitted around the case value range, becase we 425 // know that the value passed to the switch must be exactly one of the case 426 // values. 427 assert(!Cases.empty()); 428 LowerBound = Cases.front().Low; 429 UpperBound = Cases.back().High; 430 431 DenseMap<BasicBlock *, unsigned> Popularity; 432 unsigned MaxPop = 0; 433 BasicBlock *PopSucc = nullptr; 434 435 IntRange R = { INT64_MIN, INT64_MAX }; 436 UnreachableRanges.push_back(R); 437 for (const auto &I : Cases) { 438 int64_t Low = I.Low->getSExtValue(); 439 int64_t High = I.High->getSExtValue(); 440 441 IntRange &LastRange = UnreachableRanges.back(); 442 if (LastRange.Low == Low) { 443 // There is nothing left of the previous range. 444 UnreachableRanges.pop_back(); 445 } else { 446 // Terminate the previous range. 447 assert(Low > LastRange.Low); 448 LastRange.High = Low - 1; 449 } 450 if (High != INT64_MAX) { 451 IntRange R = { High + 1, INT64_MAX }; 452 UnreachableRanges.push_back(R); 453 } 454 455 // Count popularity. 456 int64_t N = High - Low + 1; 457 unsigned &Pop = Popularity[I.BB]; 458 if ((Pop += N) > MaxPop) { 459 MaxPop = Pop; 460 PopSucc = I.BB; 461 } 462 } 463 #ifndef NDEBUG 464 /* UnreachableRanges should be sorted and the ranges non-adjacent. */ 465 for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end(); 466 I != E; ++I) { 467 assert(I->Low <= I->High); 468 auto Next = I + 1; 469 if (Next != E) { 470 assert(Next->Low > I->High); 471 } 472 } 473 #endif 474 475 // Use the most popular block as the new default, reducing the number of 476 // cases. 477 assert(MaxPop > 0 && PopSucc); 478 Default = PopSucc; 479 for (CaseItr I = Cases.begin(); I != Cases.end();) { 480 if (I->BB == PopSucc) 481 I = Cases.erase(I); 482 else 483 ++I; 484 } 485 486 // If there are no cases left, just branch. 487 if (Cases.empty()) { 488 BranchInst::Create(Default, CurBlock); 489 SI->eraseFromParent(); 490 return; 491 } 492 } 493 494 // Create a new, empty default block so that the new hierarchy of 495 // if-then statements go to this and the PHI nodes are happy. 496 BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); 497 F->getBasicBlockList().insert(Default, NewDefault); 498 BranchInst::Create(Default, NewDefault); 499 500 // If there is an entry in any PHI nodes for the default edge, make sure 501 // to update them as well. 502 for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) { 503 PHINode *PN = cast<PHINode>(I); 504 int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 505 assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 506 PN->setIncomingBlock((unsigned)BlockIdx, NewDefault); 507 } 508 509 BasicBlock *SwitchBlock = 510 switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val, 511 OrigBlock, OrigBlock, NewDefault, UnreachableRanges); 512 513 // Branch to our shiny new if-then stuff... 514 BranchInst::Create(SwitchBlock, OrigBlock); 515 516 // We are now done with the switch instruction, delete it. 517 BasicBlock *OldDefault = SI->getDefaultDest(); 518 CurBlock->getInstList().erase(SI); 519 520 // If the Default block has no more predecessors just remove it. 521 if (pred_begin(OldDefault) == pred_end(OldDefault)) 522 DeleteDeadBlock(OldDefault); 523 } 524