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