610 lines · cpp
1//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// The LowerSwitch transformation rewrites switch instructions with a sequence10// of branches, which allows targets to get away with not implementing the11// switch instruction until it is convenient.12//13//===----------------------------------------------------------------------===//14 15#include "llvm/Transforms/Utils/LowerSwitch.h"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/Analysis/AssumptionCache.h"21#include "llvm/Analysis/LazyValueInfo.h"22#include "llvm/Analysis/ValueTracking.h"23#include "llvm/IR/BasicBlock.h"24#include "llvm/IR/CFG.h"25#include "llvm/IR/ConstantRange.h"26#include "llvm/IR/Constants.h"27#include "llvm/IR/Function.h"28#include "llvm/IR/InstrTypes.h"29#include "llvm/IR/Instructions.h"30#include "llvm/IR/PassManager.h"31#include "llvm/IR/Value.h"32#include "llvm/InitializePasses.h"33#include "llvm/Pass.h"34#include "llvm/Support/Casting.h"35#include "llvm/Support/Compiler.h"36#include "llvm/Support/Debug.h"37#include "llvm/Support/KnownBits.h"38#include "llvm/Support/raw_ostream.h"39#include "llvm/Transforms/Utils.h"40#include "llvm/Transforms/Utils/BasicBlockUtils.h"41#include <cassert>42#include <iterator>43#include <vector>44 45using namespace llvm;46 47#define DEBUG_TYPE "lower-switch"48 49namespace {50 51struct IntRange {52 APInt Low, High;53};54 55} // end anonymous namespace56 57namespace {58// Return true iff R is covered by Ranges.59bool IsInRanges(const IntRange &R, const std::vector<IntRange> &Ranges) {60 // Note: Ranges must be sorted, non-overlapping and non-adjacent.61 62 // Find the first range whose High field is >= R.High,63 // then check if the Low field is <= R.Low. If so, we64 // have a Range that covers R.65 auto I = llvm::lower_bound(66 Ranges, R, [](IntRange A, IntRange B) { return A.High.slt(B.High); });67 return I != Ranges.end() && I->Low.sle(R.Low);68}69 70struct CaseRange {71 ConstantInt *Low;72 ConstantInt *High;73 BasicBlock *BB;74 75 CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb)76 : Low(low), High(high), BB(bb) {}77};78 79using CaseVector = std::vector<CaseRange>;80using CaseItr = std::vector<CaseRange>::iterator;81 82/// The comparison function for sorting the switch case values in the vector.83/// WARNING: Case ranges should be disjoint!84struct CaseCmp {85 bool operator()(const CaseRange &C1, const CaseRange &C2) {86 const ConstantInt *CI1 = cast<const ConstantInt>(C1.Low);87 const ConstantInt *CI2 = cast<const ConstantInt>(C2.High);88 return CI1->getValue().slt(CI2->getValue());89 }90};91 92/// Used for debugging purposes.93LLVM_ATTRIBUTE_USED94raw_ostream &operator<<(raw_ostream &O, const CaseVector &C) {95 O << "[";96 97 for (CaseVector::const_iterator B = C.begin(), E = C.end(); B != E;) {98 O << "[" << B->Low->getValue() << ", " << B->High->getValue() << "]";99 if (++B != E)100 O << ", ";101 }102 103 return O << "]";104}105 106/// Update the first occurrence of the "switch statement" BB in the PHI107/// node with the "new" BB. The other occurrences will:108///109/// 1) Be updated by subsequent calls to this function. Switch statements may110/// have more than one outcoming edge into the same BB if they all have the same111/// value. When the switch statement is converted these incoming edges are now112/// coming from multiple BBs.113/// 2) Removed if subsequent incoming values now share the same case, i.e.,114/// multiple outcome edges are condensed into one. This is necessary to keep the115/// number of phi values equal to the number of branches to SuccBB.116void FixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB,117 const APInt &NumMergedCases) {118 for (auto &I : SuccBB->phis()) {119 PHINode *PN = cast<PHINode>(&I);120 121 // Only update the first occurrence if NewBB exists.122 unsigned Idx = 0, E = PN->getNumIncomingValues();123 APInt LocalNumMergedCases = NumMergedCases;124 for (; Idx != E && NewBB; ++Idx) {125 if (PN->getIncomingBlock(Idx) == OrigBB) {126 PN->setIncomingBlock(Idx, NewBB);127 break;128 }129 }130 131 // Skip the updated incoming block so that it will not be removed.132 if (NewBB)133 ++Idx;134 135 // Remove additional occurrences coming from condensed cases and keep the136 // number of incoming values equal to the number of branches to SuccBB.137 SmallVector<unsigned, 8> Indices;138 for (; LocalNumMergedCases.ugt(0) && Idx < E; ++Idx)139 if (PN->getIncomingBlock(Idx) == OrigBB) {140 Indices.push_back(Idx);141 LocalNumMergedCases -= 1;142 }143 // Remove incoming values in the reverse order to prevent invalidating144 // *successive* index.145 for (unsigned III : llvm::reverse(Indices))146 PN->removeIncomingValue(III);147 }148}149 150/// Create a new leaf block for the binary lookup tree. It checks if the151/// switch's value == the case's value. If not, then it jumps to the default152/// branch. At this point in the tree, the value can't be another valid case153/// value, so the jump to the "default" branch is warranted.154BasicBlock *NewLeafBlock(CaseRange &Leaf, Value *Val, ConstantInt *LowerBound,155 ConstantInt *UpperBound, BasicBlock *OrigBlock,156 BasicBlock *Default) {157 Function *F = OrigBlock->getParent();158 BasicBlock *NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock");159 F->insert(++OrigBlock->getIterator(), NewLeaf);160 161 // Emit comparison162 ICmpInst *Comp = nullptr;163 if (Leaf.Low == Leaf.High) {164 // Make the seteq instruction...165 Comp =166 new ICmpInst(NewLeaf, ICmpInst::ICMP_EQ, Val, Leaf.Low, "SwitchLeaf");167 } else {168 // Make range comparison169 if (Leaf.Low == LowerBound) {170 // Val >= Min && Val <= Hi --> Val <= Hi171 Comp = new ICmpInst(NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High,172 "SwitchLeaf");173 } else if (Leaf.High == UpperBound) {174 // Val <= Max && Val >= Lo --> Val >= Lo175 Comp = new ICmpInst(NewLeaf, ICmpInst::ICMP_SGE, Val, Leaf.Low,176 "SwitchLeaf");177 } else if (Leaf.Low->isZero()) {178 // Val >= 0 && Val <= Hi --> Val <=u Hi179 Comp = new ICmpInst(NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High,180 "SwitchLeaf");181 } else {182 // Emit V-Lo <=u Hi-Lo183 Constant *NegLo = ConstantExpr::getNeg(Leaf.Low);184 Instruction *Add = BinaryOperator::CreateAdd(185 Val, NegLo, Val->getName() + ".off", NewLeaf);186 Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High);187 Comp = new ICmpInst(NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound,188 "SwitchLeaf");189 }190 }191 192 // Make the conditional branch...193 BasicBlock *Succ = Leaf.BB;194 BranchInst::Create(Succ, Default, Comp, NewLeaf);195 196 // Update the PHI incoming value/block for the default.197 for (auto &I : Default->phis()) {198 PHINode *PN = cast<PHINode>(&I);199 auto *V = PN->getIncomingValueForBlock(OrigBlock);200 PN->addIncoming(V, NewLeaf);201 }202 203 // If there were any PHI nodes in this successor, rewrite one entry204 // from OrigBlock to come from NewLeaf.205 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {206 PHINode *PN = cast<PHINode>(I);207 // Remove all but one incoming entries from the cluster208 APInt Range = Leaf.High->getValue() - Leaf.Low->getValue();209 for (APInt j(Range.getBitWidth(), 0, false); j.ult(Range); ++j) {210 PN->removeIncomingValue(OrigBlock);211 }212 213 int BlockIdx = PN->getBasicBlockIndex(OrigBlock);214 assert(BlockIdx != -1 && "Switch didn't go to this successor??");215 PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf);216 }217 218 return NewLeaf;219}220 221/// Convert the switch statement into a binary lookup of the case values.222/// The function recursively builds this tree. LowerBound and UpperBound are223/// used to keep track of the bounds for Val that have already been checked by224/// a block emitted by one of the previous calls to switchConvert in the call225/// stack.226BasicBlock *SwitchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,227 ConstantInt *UpperBound, Value *Val,228 BasicBlock *Predecessor, BasicBlock *OrigBlock,229 BasicBlock *Default,230 const std::vector<IntRange> &UnreachableRanges) {231 assert(LowerBound && UpperBound && "Bounds must be initialized");232 unsigned Size = End - Begin;233 234 if (Size == 1) {235 // Check if the Case Range is perfectly squeezed in between236 // already checked Upper and Lower bounds. If it is then we can avoid237 // emitting the code that checks if the value actually falls in the range238 // because the bounds already tell us so.239 if (Begin->Low == LowerBound && Begin->High == UpperBound) {240 APInt NumMergedCases = UpperBound->getValue() - LowerBound->getValue();241 FixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);242 return Begin->BB;243 }244 return NewLeafBlock(*Begin, Val, LowerBound, UpperBound, OrigBlock,245 Default);246 }247 248 unsigned Mid = Size / 2;249 std::vector<CaseRange> LHS(Begin, Begin + Mid);250 LLVM_DEBUG(dbgs() << "LHS: " << LHS << "\n");251 std::vector<CaseRange> RHS(Begin + Mid, End);252 LLVM_DEBUG(dbgs() << "RHS: " << RHS << "\n");253 254 CaseRange &Pivot = *(Begin + Mid);255 LLVM_DEBUG(dbgs() << "Pivot ==> [" << Pivot.Low->getValue() << ", "256 << Pivot.High->getValue() << "]\n");257 258 // NewLowerBound here should never be the integer minimal value.259 // This is because it is computed from a case range that is never260 // the smallest, so there is always a case range that has at least261 // a smaller value.262 ConstantInt *NewLowerBound = Pivot.Low;263 264 // Because NewLowerBound is never the smallest representable integer265 // it is safe here to subtract one.266 ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(),267 NewLowerBound->getValue() - 1);268 269 if (!UnreachableRanges.empty()) {270 // Check if the gap between LHS's highest and NewLowerBound is unreachable.271 APInt GapLow = LHS.back().High->getValue() + 1;272 APInt GapHigh = NewLowerBound->getValue() - 1;273 IntRange Gap = {GapLow, GapHigh};274 if (GapHigh.sge(GapLow) && IsInRanges(Gap, UnreachableRanges))275 NewUpperBound = LHS.back().High;276 }277 278 LLVM_DEBUG(dbgs() << "LHS Bounds ==> [" << LowerBound->getValue() << ", "279 << NewUpperBound->getValue() << "]\n"280 << "RHS Bounds ==> [" << NewLowerBound->getValue() << ", "281 << UpperBound->getValue() << "]\n");282 283 // Create a new node that checks if the value is < pivot. Go to the284 // left branch if it is and right branch if not.285 Function *F = OrigBlock->getParent();286 BasicBlock *NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock");287 288 ICmpInst *Comp = new ICmpInst(ICmpInst::ICMP_SLT, Val, Pivot.Low, "Pivot");289 290 BasicBlock *LBranch =291 SwitchConvert(LHS.begin(), LHS.end(), LowerBound, NewUpperBound, Val,292 NewNode, OrigBlock, Default, UnreachableRanges);293 BasicBlock *RBranch =294 SwitchConvert(RHS.begin(), RHS.end(), NewLowerBound, UpperBound, Val,295 NewNode, OrigBlock, Default, UnreachableRanges);296 297 F->insert(++OrigBlock->getIterator(), NewNode);298 Comp->insertInto(NewNode, NewNode->end());299 300 BranchInst::Create(LBranch, RBranch, Comp, NewNode);301 return NewNode;302}303 304/// Transform simple list of \p SI's cases into list of CaseRange's \p Cases.305/// \post \p Cases wouldn't contain references to \p SI's default BB.306/// \returns Number of \p SI's cases that do not reference \p SI's default BB.307unsigned Clusterify(CaseVector &Cases, SwitchInst *SI) {308 unsigned NumSimpleCases = 0;309 310 // Start with "simple" cases311 for (auto Case : SI->cases()) {312 if (Case.getCaseSuccessor() == SI->getDefaultDest())313 continue;314 Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),315 Case.getCaseSuccessor()));316 ++NumSimpleCases;317 }318 319 llvm::sort(Cases, CaseCmp());320 321 // Merge case into clusters322 if (Cases.size() >= 2) {323 CaseItr I = Cases.begin();324 for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {325 const APInt &nextValue = J->Low->getValue();326 const APInt ¤tValue = I->High->getValue();327 BasicBlock *nextBB = J->BB;328 BasicBlock *currentBB = I->BB;329 330 // If the two neighboring cases go to the same destination, merge them331 // into a single case.332 assert(nextValue.sgt(currentValue) &&333 "Cases should be strictly ascending");334 if ((nextValue == currentValue + 1) && (currentBB == nextBB)) {335 I->High = J->High;336 // FIXME: Combine branch weights.337 } else if (++I != J) {338 *I = *J;339 }340 }341 Cases.erase(std::next(I), Cases.end());342 }343 344 return NumSimpleCases;345}346 347/// Replace the specified switch instruction with a sequence of chained if-then348/// insts in a balanced binary search.349void ProcessSwitchInst(SwitchInst *SI,350 SmallPtrSetImpl<BasicBlock *> &DeleteList,351 AssumptionCache *AC, LazyValueInfo *LVI) {352 BasicBlock *OrigBlock = SI->getParent();353 Function *F = OrigBlock->getParent();354 Value *Val = SI->getCondition(); // The value we are switching on...355 BasicBlock *Default = SI->getDefaultDest();356 357 // Don't handle unreachable blocks. If there are successors with phis, this358 // would leave them behind with missing predecessors.359 if ((OrigBlock != &F->getEntryBlock() && pred_empty(OrigBlock)) ||360 OrigBlock->getSinglePredecessor() == OrigBlock) {361 DeleteList.insert(OrigBlock);362 return;363 }364 365 // Prepare cases vector.366 CaseVector Cases;367 const unsigned NumSimpleCases = Clusterify(Cases, SI);368 IntegerType *IT = cast<IntegerType>(SI->getCondition()->getType());369 const unsigned BitWidth = IT->getBitWidth();370 // Explicitly use higher precision to prevent unsigned overflow where371 // `UnsignedMax - 0 + 1 == 0`372 APInt UnsignedZero(BitWidth + 1, 0);373 APInt UnsignedMax = APInt::getMaxValue(BitWidth);374 LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size()375 << ". Total non-default cases: " << NumSimpleCases376 << "\nCase clusters: " << Cases << "\n");377 378 // If there is only the default destination, just branch.379 if (Cases.empty()) {380 BranchInst::Create(Default, OrigBlock);381 // Remove all the references from Default's PHIs to OrigBlock, but one.382 FixPhis(Default, OrigBlock, OrigBlock, UnsignedMax);383 SI->eraseFromParent();384 return;385 }386 387 ConstantInt *LowerBound = nullptr;388 ConstantInt *UpperBound = nullptr;389 bool DefaultIsUnreachableFromSwitch = false;390 391 if (SI->defaultDestUnreachable()) {392 // Make the bounds tightly fitted around the case value range, because we393 // know that the value passed to the switch must be exactly one of the case394 // values.395 LowerBound = Cases.front().Low;396 UpperBound = Cases.back().High;397 DefaultIsUnreachableFromSwitch = true;398 } else {399 // Constraining the range of the value being switched over helps eliminating400 // unreachable BBs and minimizing the number of `add` instructions401 // newLeafBlock ends up emitting. Running CorrelatedValuePropagation after402 // LowerSwitch isn't as good, and also much more expensive in terms of403 // compile time for the following reasons:404 // 1. it processes many kinds of instructions, not just switches;405 // 2. even if limited to icmp instructions only, it will have to process406 // roughly C icmp's per switch, where C is the number of cases in the407 // switch, while LowerSwitch only needs to call LVI once per switch.408 const DataLayout &DL = F->getDataLayout();409 KnownBits Known = computeKnownBits(Val, DL, AC, SI);410 // TODO Shouldn't this create a signed range?411 ConstantRange KnownBitsRange =412 ConstantRange::fromKnownBits(Known, /*IsSigned=*/false);413 const ConstantRange LVIRange =414 LVI->getConstantRange(Val, SI, /*UndefAllowed*/ false);415 ConstantRange ValRange = KnownBitsRange.intersectWith(LVIRange);416 // We delegate removal of unreachable non-default cases to other passes. In417 // the unlikely event that some of them survived, we just conservatively418 // maintain the invariant that all the cases lie between the bounds. This419 // may, however, still render the default case effectively unreachable.420 const APInt &Low = Cases.front().Low->getValue();421 const APInt &High = Cases.back().High->getValue();422 APInt Min = APIntOps::smin(ValRange.getSignedMin(), Low);423 APInt Max = APIntOps::smax(ValRange.getSignedMax(), High);424 425 LowerBound = ConstantInt::get(SI->getContext(), Min);426 UpperBound = ConstantInt::get(SI->getContext(), Max);427 DefaultIsUnreachableFromSwitch = (Min + (NumSimpleCases - 1) == Max);428 }429 430 std::vector<IntRange> UnreachableRanges;431 432 if (DefaultIsUnreachableFromSwitch) {433 DenseMap<BasicBlock *, APInt> Popularity;434 APInt MaxPop(UnsignedZero);435 BasicBlock *PopSucc = nullptr;436 437 APInt SignedMax = APInt::getSignedMaxValue(BitWidth);438 APInt SignedMin = APInt::getSignedMinValue(BitWidth);439 IntRange R = {SignedMin, SignedMax};440 UnreachableRanges.push_back(R);441 for (const auto &I : Cases) {442 const APInt &Low = I.Low->getValue();443 const APInt &High = I.High->getValue();444 445 IntRange &LastRange = UnreachableRanges.back();446 if (LastRange.Low.eq(Low)) {447 // There is nothing left of the previous range.448 UnreachableRanges.pop_back();449 } else {450 // Terminate the previous range.451 assert(Low.sgt(LastRange.Low));452 LastRange.High = Low - 1;453 }454 if (High.ne(SignedMax)) {455 IntRange R = {High + 1, SignedMax};456 UnreachableRanges.push_back(R);457 }458 459 // Count popularity.460 assert(High.sge(Low) && "Popularity shouldn't be negative.");461 APInt N = High.sext(BitWidth + 1) - Low.sext(BitWidth + 1) + 1;462 // Explict insert to make sure the bitwidth of APInts match463 APInt &Pop = Popularity.insert({I.BB, APInt(UnsignedZero)}).first->second;464 if ((Pop += N).ugt(MaxPop)) {465 MaxPop = Pop;466 PopSucc = I.BB;467 }468 }469#ifndef NDEBUG470 /* UnreachableRanges should be sorted and the ranges non-adjacent. */471 for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end();472 I != E; ++I) {473 assert(I->Low.sle(I->High));474 auto Next = I + 1;475 if (Next != E) {476 assert(Next->Low.sgt(I->High));477 }478 }479#endif480 481 // As the default block in the switch is unreachable, update the PHI nodes482 // (remove all of the references to the default block) to reflect this.483 const unsigned NumDefaultEdges = SI->getNumCases() + 1 - NumSimpleCases;484 for (unsigned I = 0; I < NumDefaultEdges; ++I)485 Default->removePredecessor(OrigBlock);486 487 // Use the most popular block as the new default, reducing the number of488 // cases.489 Default = PopSucc;490 llvm::erase_if(Cases,491 [PopSucc](const CaseRange &R) { return R.BB == PopSucc; });492 493 // If there are no cases left, just branch.494 if (Cases.empty()) {495 BranchInst::Create(Default, OrigBlock);496 SI->eraseFromParent();497 // As all the cases have been replaced with a single branch, only keep498 // one entry in the PHI nodes.499 if (!MaxPop.isZero())500 for (APInt I(UnsignedZero); I.ult(MaxPop - 1); ++I)501 PopSucc->removePredecessor(OrigBlock);502 return;503 }504 505 // If the condition was a PHI node with the switch block as a predecessor506 // removing predecessors may have caused the condition to be erased.507 // Getting the condition value again here protects against that.508 Val = SI->getCondition();509 }510 511 BasicBlock *SwitchBlock =512 SwitchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,513 OrigBlock, OrigBlock, Default, UnreachableRanges);514 515 // We have added incoming values for newly-created predecessors in516 // NewLeafBlock(). The only meaningful work we offload to FixPhis() is to517 // remove the incoming values from OrigBlock. There might be a special case518 // that SwitchBlock is the same as Default, under which the PHIs in Default519 // are fixed inside SwitchConvert().520 if (SwitchBlock != Default)521 FixPhis(Default, OrigBlock, nullptr, UnsignedMax);522 523 // Branch to our shiny new if-then stuff...524 BranchInst::Create(SwitchBlock, OrigBlock);525 526 // We are now done with the switch instruction, delete it.527 BasicBlock *OldDefault = SI->getDefaultDest();528 SI->eraseFromParent();529 530 // If the Default block has no more predecessors just add it to DeleteList.531 if (pred_empty(OldDefault))532 DeleteList.insert(OldDefault);533}534 535bool LowerSwitch(Function &F, LazyValueInfo *LVI, AssumptionCache *AC) {536 bool Changed = false;537 SmallPtrSet<BasicBlock *, 8> DeleteList;538 539 // We use make_early_inc_range here so that we don't traverse new blocks.540 for (BasicBlock &Cur : llvm::make_early_inc_range(F)) {541 // If the block is a dead Default block that will be deleted later, don't542 // waste time processing it.543 if (DeleteList.count(&Cur))544 continue;545 546 if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur.getTerminator())) {547 Changed = true;548 ProcessSwitchInst(SI, DeleteList, AC, LVI);549 }550 }551 552 for (BasicBlock *BB : DeleteList) {553 LVI->eraseBlock(BB);554 DeleteDeadBlock(BB);555 }556 557 return Changed;558}559 560/// Replace all SwitchInst instructions with chained branch instructions.561class LowerSwitchLegacyPass : public FunctionPass {562public:563 // Pass identification, replacement for typeid564 static char ID;565 566 LowerSwitchLegacyPass() : FunctionPass(ID) {567 initializeLowerSwitchLegacyPassPass(*PassRegistry::getPassRegistry());568 }569 570 bool runOnFunction(Function &F) override;571 572 void getAnalysisUsage(AnalysisUsage &AU) const override {573 AU.addRequired<LazyValueInfoWrapperPass>();574 }575};576 577} // end anonymous namespace578 579char LowerSwitchLegacyPass::ID = 0;580 581// Publicly exposed interface to pass...582char &llvm::LowerSwitchID = LowerSwitchLegacyPass::ID;583 584INITIALIZE_PASS_BEGIN(LowerSwitchLegacyPass, "lowerswitch",585 "Lower SwitchInst's to branches", false, false)586INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)587INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)588INITIALIZE_PASS_END(LowerSwitchLegacyPass, "lowerswitch",589 "Lower SwitchInst's to branches", false, false)590 591// createLowerSwitchPass - Interface to this file...592FunctionPass *llvm::createLowerSwitchPass() {593 return new LowerSwitchLegacyPass();594}595 596bool LowerSwitchLegacyPass::runOnFunction(Function &F) {597 LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();598 auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>();599 AssumptionCache *AC = ACT ? &ACT->getAssumptionCache(F) : nullptr;600 return LowerSwitch(F, LVI, AC);601}602 603PreservedAnalyses LowerSwitchPass::run(Function &F,604 FunctionAnalysisManager &AM) {605 LazyValueInfo *LVI = &AM.getResult<LazyValueAnalysis>(F);606 AssumptionCache *AC = AM.getCachedResult<AssumptionAnalysis>(F);607 return LowerSwitch(F, LVI, AC) ? PreservedAnalyses::none()608 : PreservedAnalyses::all();609}610