LowerSwitch.cpp revision 344779
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/Utils.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. 158LLVM_ATTRIBUTE_USED 159static raw_ostream &operator<<(raw_ostream &O, 160 const LowerSwitch::CaseVector &C) { 161 O << "["; 162 163 for (LowerSwitch::CaseVector::const_iterator B = C.begin(), 164 E = C.end(); B != E; ) { 165 O << *B->Low << " -" << *B->High; 166 if (++B != E) O << ", "; 167 } 168 169 return O << "]"; 170} 171 172/// Update the first occurrence of the "switch statement" BB in the PHI 173/// node with the "new" BB. The other occurrences will: 174/// 175/// 1) Be updated by subsequent calls to this function. Switch statements may 176/// have more than one outcoming edge into the same BB if they all have the same 177/// value. When the switch statement is converted these incoming edges are now 178/// coming from multiple BBs. 179/// 2) Removed if subsequent incoming values now share the same case, i.e., 180/// multiple outcome edges are condensed into one. This is necessary to keep the 181/// number of phi values equal to the number of branches to SuccBB. 182static void fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB, 183 unsigned NumMergedCases) { 184 for (BasicBlock::iterator I = SuccBB->begin(), 185 IE = SuccBB->getFirstNonPHI()->getIterator(); 186 I != IE; ++I) { 187 PHINode *PN = cast<PHINode>(I); 188 189 // Only update the first occurrence. 190 unsigned Idx = 0, E = PN->getNumIncomingValues(); 191 unsigned LocalNumMergedCases = NumMergedCases; 192 for (; Idx != E; ++Idx) { 193 if (PN->getIncomingBlock(Idx) == OrigBB) { 194 PN->setIncomingBlock(Idx, NewBB); 195 break; 196 } 197 } 198 199 // Remove additional occurrences coming from condensed cases and keep the 200 // number of incoming values equal to the number of branches to SuccBB. 201 SmallVector<unsigned, 8> Indices; 202 for (++Idx; LocalNumMergedCases > 0 && Idx < E; ++Idx) 203 if (PN->getIncomingBlock(Idx) == OrigBB) { 204 Indices.push_back(Idx); 205 LocalNumMergedCases--; 206 } 207 // Remove incoming values in the reverse order to prevent invalidating 208 // *successive* index. 209 for (unsigned III : llvm::reverse(Indices)) 210 PN->removeIncomingValue(III); 211 } 212} 213 214/// Convert the switch statement into a binary lookup of the case values. 215/// The function recursively builds this tree. LowerBound and UpperBound are 216/// used to keep track of the bounds for Val that have already been checked by 217/// a block emitted by one of the previous calls to switchConvert in the call 218/// stack. 219BasicBlock * 220LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound, 221 ConstantInt *UpperBound, Value *Val, 222 BasicBlock *Predecessor, BasicBlock *OrigBlock, 223 BasicBlock *Default, 224 const std::vector<IntRange> &UnreachableRanges) { 225 unsigned Size = End - Begin; 226 227 if (Size == 1) { 228 // Check if the Case Range is perfectly squeezed in between 229 // already checked Upper and Lower bounds. If it is then we can avoid 230 // emitting the code that checks if the value actually falls in the range 231 // because the bounds already tell us so. 232 if (Begin->Low == LowerBound && Begin->High == UpperBound) { 233 unsigned NumMergedCases = 0; 234 if (LowerBound && UpperBound) 235 NumMergedCases = 236 UpperBound->getSExtValue() - LowerBound->getSExtValue(); 237 fixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases); 238 return Begin->BB; 239 } 240 return newLeafBlock(*Begin, Val, OrigBlock, Default); 241 } 242 243 unsigned Mid = Size / 2; 244 std::vector<CaseRange> LHS(Begin, Begin + Mid); 245 LLVM_DEBUG(dbgs() << "LHS: " << LHS << "\n"); 246 std::vector<CaseRange> RHS(Begin + Mid, End); 247 LLVM_DEBUG(dbgs() << "RHS: " << RHS << "\n"); 248 249 CaseRange &Pivot = *(Begin + Mid); 250 LLVM_DEBUG(dbgs() << "Pivot ==> " << Pivot.Low->getValue() << " -" 251 << Pivot.High->getValue() << "\n"); 252 253 // NewLowerBound here should never be the integer minimal value. 254 // This is because it is computed from a case range that is never 255 // the smallest, so there is always a case range that has at least 256 // a smaller value. 257 ConstantInt *NewLowerBound = Pivot.Low; 258 259 // Because NewLowerBound is never the smallest representable integer 260 // it is safe here to subtract one. 261 ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(), 262 NewLowerBound->getValue() - 1); 263 264 if (!UnreachableRanges.empty()) { 265 // Check if the gap between LHS's highest and NewLowerBound is unreachable. 266 int64_t GapLow = LHS.back().High->getSExtValue() + 1; 267 int64_t GapHigh = NewLowerBound->getSExtValue() - 1; 268 IntRange Gap = { GapLow, GapHigh }; 269 if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges)) 270 NewUpperBound = LHS.back().High; 271 } 272 273 LLVM_DEBUG(dbgs() << "LHS Bounds ==> "; if (LowerBound) { 274 dbgs() << LowerBound->getSExtValue(); 275 } else { dbgs() << "NONE"; } dbgs() << " - " 276 << NewUpperBound->getSExtValue() << "\n"; 277 dbgs() << "RHS Bounds ==> "; 278 dbgs() << NewLowerBound->getSExtValue() << " - "; if (UpperBound) { 279 dbgs() << UpperBound->getSExtValue() << "\n"; 280 } else { dbgs() << "NONE\n"; }); 281 282 // Create a new node that checks if the value is < pivot. Go to the 283 // left branch if it is and right branch if not. 284 Function* F = OrigBlock->getParent(); 285 BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock"); 286 287 ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, 288 Val, Pivot.Low, "Pivot"); 289 290 BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound, 291 NewUpperBound, Val, NewNode, OrigBlock, 292 Default, UnreachableRanges); 293 BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound, 294 UpperBound, Val, NewNode, OrigBlock, 295 Default, UnreachableRanges); 296 297 F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewNode); 298 NewNode->getInstList().push_back(Comp); 299 300 BranchInst::Create(LBranch, RBranch, Comp, NewNode); 301 return NewNode; 302} 303 304/// Create a new leaf block for the binary lookup tree. It checks if the 305/// switch's value == the case's value. If not, then it jumps to the default 306/// branch. At this point in the tree, the value can't be another valid case 307/// value, so the jump to the "default" branch is warranted. 308BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, 309 BasicBlock* OrigBlock, 310 BasicBlock* Default) { 311 Function* F = OrigBlock->getParent(); 312 BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock"); 313 F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewLeaf); 314 315 // Emit comparison 316 ICmpInst* Comp = nullptr; 317 if (Leaf.Low == Leaf.High) { 318 // Make the seteq instruction... 319 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, 320 Leaf.Low, "SwitchLeaf"); 321 } else { 322 // Make range comparison 323 if (Leaf.Low->isMinValue(true /*isSigned*/)) { 324 // Val >= Min && Val <= Hi --> Val <= Hi 325 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High, 326 "SwitchLeaf"); 327 } else if (Leaf.Low->isZero()) { 328 // Val >= 0 && Val <= Hi --> Val <=u Hi 329 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High, 330 "SwitchLeaf"); 331 } else { 332 // Emit V-Lo <=u Hi-Lo 333 Constant* NegLo = ConstantExpr::getNeg(Leaf.Low); 334 Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo, 335 Val->getName()+".off", 336 NewLeaf); 337 Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High); 338 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound, 339 "SwitchLeaf"); 340 } 341 } 342 343 // Make the conditional branch... 344 BasicBlock* Succ = Leaf.BB; 345 BranchInst::Create(Succ, Default, Comp, NewLeaf); 346 347 // If there were any PHI nodes in this successor, rewrite one entry 348 // from OrigBlock to come from NewLeaf. 349 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 350 PHINode* PN = cast<PHINode>(I); 351 // Remove all but one incoming entries from the cluster 352 uint64_t Range = Leaf.High->getSExtValue() - 353 Leaf.Low->getSExtValue(); 354 for (uint64_t j = 0; j < Range; ++j) { 355 PN->removeIncomingValue(OrigBlock); 356 } 357 358 int BlockIdx = PN->getBasicBlockIndex(OrigBlock); 359 assert(BlockIdx != -1 && "Switch didn't go to this successor??"); 360 PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf); 361 } 362 363 return NewLeaf; 364} 365 366/// Transform simple list of Cases into list of CaseRange's. 367unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { 368 unsigned numCmps = 0; 369 370 // Start with "simple" cases 371 for (auto Case : SI->cases()) 372 Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(), 373 Case.getCaseSuccessor())); 374 375 llvm::sort(Cases, CaseCmp()); 376 377 // Merge case into clusters 378 if (Cases.size() >= 2) { 379 CaseItr I = Cases.begin(); 380 for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) { 381 int64_t nextValue = J->Low->getSExtValue(); 382 int64_t currentValue = I->High->getSExtValue(); 383 BasicBlock* nextBB = J->BB; 384 BasicBlock* currentBB = I->BB; 385 386 // If the two neighboring cases go to the same destination, merge them 387 // into a single case. 388 assert(nextValue > currentValue && "Cases should be strictly ascending"); 389 if ((nextValue == currentValue + 1) && (currentBB == nextBB)) { 390 I->High = J->High; 391 // FIXME: Combine branch weights. 392 } else if (++I != J) { 393 *I = *J; 394 } 395 } 396 Cases.erase(std::next(I), Cases.end()); 397 } 398 399 for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 400 if (I->Low != I->High) 401 // A range counts double, since it requires two compares. 402 ++numCmps; 403 } 404 405 return numCmps; 406} 407 408/// Replace the specified switch instruction with a sequence of chained if-then 409/// insts in a balanced binary search. 410void LowerSwitch::processSwitchInst(SwitchInst *SI, 411 SmallPtrSetImpl<BasicBlock*> &DeleteList) { 412 BasicBlock *CurBlock = SI->getParent(); 413 BasicBlock *OrigBlock = CurBlock; 414 Function *F = CurBlock->getParent(); 415 Value *Val = SI->getCondition(); // The value we are switching on... 416 BasicBlock* Default = SI->getDefaultDest(); 417 418 // Don't handle unreachable blocks. If there are successors with phis, this 419 // would leave them behind with missing predecessors. 420 if ((CurBlock != &F->getEntryBlock() && pred_empty(CurBlock)) || 421 CurBlock->getSinglePredecessor() == CurBlock) { 422 DeleteList.insert(CurBlock); 423 return; 424 } 425 426 // If there is only the default destination, just branch. 427 if (!SI->getNumCases()) { 428 BranchInst::Create(Default, CurBlock); 429 SI->eraseFromParent(); 430 return; 431 } 432 433 // Prepare cases vector. 434 CaseVector Cases; 435 unsigned numCmps = Clusterify(Cases, SI); 436 LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() 437 << ". Total compares: " << numCmps << "\n"); 438 LLVM_DEBUG(dbgs() << "Cases: " << Cases << "\n"); 439 (void)numCmps; 440 441 ConstantInt *LowerBound = nullptr; 442 ConstantInt *UpperBound = nullptr; 443 std::vector<IntRange> UnreachableRanges; 444 445 if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) { 446 // Make the bounds tightly fitted around the case value range, because we 447 // know that the value passed to the switch must be exactly one of the case 448 // values. 449 assert(!Cases.empty()); 450 LowerBound = Cases.front().Low; 451 UpperBound = Cases.back().High; 452 453 DenseMap<BasicBlock *, unsigned> Popularity; 454 unsigned MaxPop = 0; 455 BasicBlock *PopSucc = nullptr; 456 457 IntRange R = {std::numeric_limits<int64_t>::min(), 458 std::numeric_limits<int64_t>::max()}; 459 UnreachableRanges.push_back(R); 460 for (const auto &I : Cases) { 461 int64_t Low = I.Low->getSExtValue(); 462 int64_t High = I.High->getSExtValue(); 463 464 IntRange &LastRange = UnreachableRanges.back(); 465 if (LastRange.Low == Low) { 466 // There is nothing left of the previous range. 467 UnreachableRanges.pop_back(); 468 } else { 469 // Terminate the previous range. 470 assert(Low > LastRange.Low); 471 LastRange.High = Low - 1; 472 } 473 if (High != std::numeric_limits<int64_t>::max()) { 474 IntRange R = { High + 1, std::numeric_limits<int64_t>::max() }; 475 UnreachableRanges.push_back(R); 476 } 477 478 // Count popularity. 479 int64_t N = High - Low + 1; 480 unsigned &Pop = Popularity[I.BB]; 481 if ((Pop += N) > MaxPop) { 482 MaxPop = Pop; 483 PopSucc = I.BB; 484 } 485 } 486#ifndef NDEBUG 487 /* UnreachableRanges should be sorted and the ranges non-adjacent. */ 488 for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end(); 489 I != E; ++I) { 490 assert(I->Low <= I->High); 491 auto Next = I + 1; 492 if (Next != E) { 493 assert(Next->Low > I->High); 494 } 495 } 496#endif 497 498 // As the default block in the switch is unreachable, update the PHI nodes 499 // (remove the entry to the default block) to reflect this. 500 Default->removePredecessor(OrigBlock); 501 502 // Use the most popular block as the new default, reducing the number of 503 // cases. 504 assert(MaxPop > 0 && PopSucc); 505 Default = PopSucc; 506 Cases.erase( 507 llvm::remove_if( 508 Cases, [PopSucc](const CaseRange &R) { return R.BB == PopSucc; }), 509 Cases.end()); 510 511 // If there are no cases left, just branch. 512 if (Cases.empty()) { 513 BranchInst::Create(Default, CurBlock); 514 SI->eraseFromParent(); 515 // As all the cases have been replaced with a single branch, only keep 516 // one entry in the PHI nodes. 517 for (unsigned I = 0 ; I < (MaxPop - 1) ; ++I) 518 PopSucc->removePredecessor(OrigBlock); 519 return; 520 } 521 } 522 523 unsigned NrOfDefaults = (SI->getDefaultDest() == Default) ? 1 : 0; 524 for (const auto &Case : SI->cases()) 525 if (Case.getCaseSuccessor() == Default) 526 NrOfDefaults++; 527 528 // Create a new, empty default block so that the new hierarchy of 529 // if-then statements go to this and the PHI nodes are happy. 530 BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault"); 531 F->getBasicBlockList().insert(Default->getIterator(), NewDefault); 532 BranchInst::Create(Default, NewDefault); 533 534 BasicBlock *SwitchBlock = 535 switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val, 536 OrigBlock, OrigBlock, NewDefault, UnreachableRanges); 537 538 // If there are entries in any PHI nodes for the default edge, make sure 539 // to update them as well. 540 fixPhis(Default, OrigBlock, NewDefault, NrOfDefaults); 541 542 // Branch to our shiny new if-then stuff... 543 BranchInst::Create(SwitchBlock, OrigBlock); 544 545 // We are now done with the switch instruction, delete it. 546 BasicBlock *OldDefault = SI->getDefaultDest(); 547 CurBlock->getInstList().erase(SI); 548 549 // If the Default block has no more predecessors just add it to DeleteList. 550 if (pred_begin(OldDefault) == pred_end(OldDefault)) 551 DeleteList.insert(OldDefault); 552} 553