LLVM  17.0.0git
LowerSwitch.cpp
Go to the documentation of this file.
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 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallVector.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"
39 #include "llvm/Transforms/Utils.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 {
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.
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);
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) {
436  APInt MaxPop(UnsignedZero);
437  BasicBlock *PopSucc = nullptr;
438 
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);
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) {
570  }
571 
572  bool runOnFunction(Function &F) override;
573 
574  void getAnalysisUsage(AnalysisUsage &AU) const override {
576  }
577 };
578 
579 } // end anonymous namespace
580 
582 
583 // Publicly exposed interface to pass...
585 
586 INITIALIZE_PASS_BEGIN(LowerSwitchLegacyPass, "lowerswitch",
587  "Lower SwitchInst's to branches", false, false)
590 INITIALIZE_PASS_END(LowerSwitchLegacyPass, "lowerswitch",
592 
593 // createLowerSwitchPass - Interface to this file...
595  return new LowerSwitchLegacyPass();
596 }
597 
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 
609  return LowerSwitch(F, LVI, AC) ? PreservedAnalyses::none()
611 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
AssumptionCache.h
LLVM_ATTRIBUTE_USED
#define LLVM_ATTRIBUTE_USED
Definition: Compiler.h:139
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:316
llvm::LowerSwitchPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LowerSwitch.cpp:605
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:739
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:114
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:824
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
llvm::initializeLowerSwitchLegacyPassPass
void initializeLowerSwitchLegacyPassPass(PassRegistry &)
llvm::Function
Definition: Function.h:59
llvm::lower_bound
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1923
Pass.h
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:132
High
uint64_t High
Definition: NVVMIntrRange.cpp:61
llvm::LazyValueAnalysis
Analysis to compute lazy value information.
Definition: LazyValueInfo.h:138
llvm::SmallVector< unsigned, 8 >
llvm::Instruction::insertInto
SymbolTableList< Instruction >::iterator insertInto(BasicBlock *ParentBB, SymbolTableList< Instruction >::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Definition: Instruction.cpp:98
llvm::APInt::getMaxValue
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:186
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1998
llvm::PHINode::removeIncomingValue
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Definition: Instructions.cpp:124
ValueTracking.h
IT
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
to
Should compile to
Definition: README.txt:449
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
llvm::APInt::getSignedMaxValue
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
DenseMap.h
llvm::APInt::ugt
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1160
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:748
LazyValueInfo.h
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:284
STLExtras.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:275
KnownBits.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
bb
< i1 > br i1 label label bb bb
Definition: README.txt:978
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LowerSwitchLegacyPass, "lowerswitch", "Lower SwitchInst's to branches", false, false) INITIALIZE_PASS_END(LowerSwitchLegacyPass
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::CmpInst::ICMP_ULE
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:744
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
InstrTypes.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:314
SI
@ SI
Definition: SIInstrInfo.cpp:7993
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
LowerSwitch.h
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2889
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction
Definition: Instruction.h:41
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:372
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
llvm::ThreadPriority::Low
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:887
SmallPtrSet.h
Utils.h
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2790
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
CFG.h
llvm::createLowerSwitchPass
FunctionPass * createLowerSwitchPass()
Definition: LowerSwitch.cpp:594
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1683
BasicBlock.h
llvm::APInt::slt
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1108
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:274
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1197
llvm::ConstantRange::getSignedMin
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:440
llvm::LazyValueInfo::getConstantRange
ConstantRange getConstantRange(Value *V, Instruction *CxtI, bool UndefAllowed=true)
Return the ConstantRange constraint that is known to hold for the specified value at the specified in...
Definition: LazyValueInfo.cpp:1637
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2833
llvm::LazyValueInfoWrapperPass
Wrapper around LazyValueInfo.
Definition: LazyValueInfo.h:149
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
s
multiplies can be turned into SHL s
Definition: README.txt:370
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2854
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3195
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:721
llvm::PHINode::getBasicBlockIndex
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Definition: Instructions.h:2882
llvm::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Definition: ValueTracking.cpp:186
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::APInt::sge
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
Definition: APInt.h:1215
llvm::LazyValueInfo
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:31
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
branches
Lower SwitchInst s to branches
Definition: LowerSwitch.cpp:591
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:747
llvm::APIntOps::smin
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2175
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::logicalview::LVAttributeKind::Range
@ Range
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:105
Compiler.h
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
ConstantRange.h
llvm::pred_empty
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::LowerSwitchID
char & LowerSwitchID
Definition: LowerSwitch.cpp:584
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
j
return j(j<< 16)
llvm::ConstantRange::getSignedMax
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:434
llvm::KnownBits
Definition: KnownBits.h:23
llvm::ConstantExpr::getNeg
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2644
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::ConstantExpr::getAdd
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2657
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
Casting.h
Function.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
PassManager.h
llvm::TargetStackID::Default
@ Default
Definition: TargetFrameLowering.h:28
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:746
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:186
llvm::APInt::getSignedMinValue
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
lowerswitch
lowerswitch
Definition: LowerSwitch.cpp:590
Instructions.h
llvm::ConstantRange::intersectWith
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
Definition: ConstantRange.cpp:520
llvm::pdb::DbgHeaderType::Max
@ Max
SmallVector.h
llvm::ConstantRange::fromKnownBits
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
Definition: ConstantRange.cpp:59
N
#define N
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2814
llvm::PHINode
Definition: Instructions.h:2708
llvm::logicalview::LVWarningKind::Ranges
@ Ranges
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:341
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:484
llvm::APInt::sgt
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1179
llvm::DeleteDeadBlock
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
Definition: BasicBlockUtils.cpp:95
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
CreateAdd
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:241
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3283
raw_ostream.h
llvm::LazyValueInfo::eraseBlock
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
Definition: LazyValueInfo.cpp:1963
BasicBlockUtils.h
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::APIntOps::smax
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2180
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365