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