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