LLVM  15.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  int64_t 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 < B.High; });
70  return I != Ranges.end() && I->Low <= 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(
120  BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB,
121  const unsigned NumMergedCases = std::numeric_limits<unsigned>::max()) {
122  for (auto &I : SuccBB->phis()) {
123  PHINode *PN = cast<PHINode>(&I);
124 
125  // Only update the first occurrence if NewBB exists.
126  unsigned Idx = 0, E = PN->getNumIncomingValues();
127  unsigned LocalNumMergedCases = NumMergedCases;
128  for (; Idx != E && NewBB; ++Idx) {
129  if (PN->getIncomingBlock(Idx) == OrigBB) {
130  PN->setIncomingBlock(Idx, NewBB);
131  break;
132  }
133  }
134 
135  // Skip the updated incoming block so that it will not be removed.
136  if (NewBB)
137  ++Idx;
138 
139  // Remove additional occurrences coming from condensed cases and keep the
140  // number of incoming values equal to the number of branches to SuccBB.
141  SmallVector<unsigned, 8> Indices;
142  for (; LocalNumMergedCases > 0 && Idx < E; ++Idx)
143  if (PN->getIncomingBlock(Idx) == OrigBB) {
144  Indices.push_back(Idx);
145  LocalNumMergedCases--;
146  }
147  // Remove incoming values in the reverse order to prevent invalidating
148  // *successive* index.
149  for (unsigned III : llvm::reverse(Indices))
150  PN->removeIncomingValue(III);
151  }
152 }
153 
154 /// Create a new leaf block for the binary lookup tree. It checks if the
155 /// switch's value == the case's value. If not, then it jumps to the default
156 /// branch. At this point in the tree, the value can't be another valid case
157 /// value, so the jump to the "default" branch is warranted.
158 BasicBlock *NewLeafBlock(CaseRange &Leaf, Value *Val, ConstantInt *LowerBound,
159  ConstantInt *UpperBound, BasicBlock *OrigBlock,
160  BasicBlock *Default) {
161  Function *F = OrigBlock->getParent();
162  BasicBlock *NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock");
163  F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewLeaf);
164 
165  // Emit comparison
166  ICmpInst *Comp = nullptr;
167  if (Leaf.Low == Leaf.High) {
168  // Make the seteq instruction...
169  Comp =
170  new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, Leaf.Low, "SwitchLeaf");
171  } else {
172  // Make range comparison
173  if (Leaf.Low == LowerBound) {
174  // Val >= Min && Val <= Hi --> Val <= Hi
175  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High,
176  "SwitchLeaf");
177  } else if (Leaf.High == UpperBound) {
178  // Val <= Max && Val >= Lo --> Val >= Lo
179  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SGE, Val, Leaf.Low,
180  "SwitchLeaf");
181  } else if (Leaf.Low->isZero()) {
182  // Val >= 0 && Val <= Hi --> Val <=u Hi
183  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High,
184  "SwitchLeaf");
185  } else {
186  // Emit V-Lo <=u Hi-Lo
187  Constant *NegLo = ConstantExpr::getNeg(Leaf.Low);
189  Val, NegLo, Val->getName() + ".off", NewLeaf);
190  Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High);
191  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound,
192  "SwitchLeaf");
193  }
194  }
195 
196  // Make the conditional branch...
197  BasicBlock *Succ = Leaf.BB;
198  BranchInst::Create(Succ, Default, Comp, NewLeaf);
199 
200  // Update the PHI incoming value/block for the default.
201  for (auto &I : Default->phis()) {
202  PHINode *PN = cast<PHINode>(&I);
203  auto *V = PN->getIncomingValueForBlock(OrigBlock);
204  PN->addIncoming(V, NewLeaf);
205  }
206 
207  // If there were any PHI nodes in this successor, rewrite one entry
208  // from OrigBlock to come from NewLeaf.
209  for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
210  PHINode *PN = cast<PHINode>(I);
211  // Remove all but one incoming entries from the cluster
212  uint64_t Range = Leaf.High->getSExtValue() - Leaf.Low->getSExtValue();
213  for (uint64_t j = 0; j < Range; ++j) {
214  PN->removeIncomingValue(OrigBlock);
215  }
216 
217  int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
218  assert(BlockIdx != -1 && "Switch didn't go to this successor??");
219  PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf);
220  }
221 
222  return NewLeaf;
223 }
224 
225 /// Convert the switch statement into a binary lookup of the case values.
226 /// The function recursively builds this tree. LowerBound and UpperBound are
227 /// used to keep track of the bounds for Val that have already been checked by
228 /// a block emitted by one of the previous calls to switchConvert in the call
229 /// stack.
230 BasicBlock *SwitchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,
231  ConstantInt *UpperBound, Value *Val,
232  BasicBlock *Predecessor, BasicBlock *OrigBlock,
233  BasicBlock *Default,
234  const std::vector<IntRange> &UnreachableRanges) {
235  assert(LowerBound && UpperBound && "Bounds must be initialized");
236  unsigned Size = End - Begin;
237 
238  if (Size == 1) {
239  // Check if the Case Range is perfectly squeezed in between
240  // already checked Upper and Lower bounds. If it is then we can avoid
241  // emitting the code that checks if the value actually falls in the range
242  // because the bounds already tell us so.
243  if (Begin->Low == LowerBound && Begin->High == UpperBound) {
244  unsigned NumMergedCases = 0;
245  NumMergedCases = UpperBound->getSExtValue() - LowerBound->getSExtValue();
246  FixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);
247  return Begin->BB;
248  }
249  return NewLeafBlock(*Begin, Val, LowerBound, UpperBound, OrigBlock,
250  Default);
251  }
252 
253  unsigned Mid = Size / 2;
254  std::vector<CaseRange> LHS(Begin, Begin + Mid);
255  LLVM_DEBUG(dbgs() << "LHS: " << LHS << "\n");
256  std::vector<CaseRange> RHS(Begin + Mid, End);
257  LLVM_DEBUG(dbgs() << "RHS: " << RHS << "\n");
258 
259  CaseRange &Pivot = *(Begin + Mid);
260  LLVM_DEBUG(dbgs() << "Pivot ==> [" << Pivot.Low->getValue() << ", "
261  << Pivot.High->getValue() << "]\n");
262 
263  // NewLowerBound here should never be the integer minimal value.
264  // This is because it is computed from a case range that is never
265  // the smallest, so there is always a case range that has at least
266  // a smaller value.
267  ConstantInt *NewLowerBound = Pivot.Low;
268 
269  // Because NewLowerBound is never the smallest representable integer
270  // it is safe here to subtract one.
271  ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(),
272  NewLowerBound->getValue() - 1);
273 
274  if (!UnreachableRanges.empty()) {
275  // Check if the gap between LHS's highest and NewLowerBound is unreachable.
276  int64_t GapLow = LHS.back().High->getSExtValue() + 1;
277  int64_t GapHigh = NewLowerBound->getSExtValue() - 1;
278  IntRange Gap = { GapLow, GapHigh };
279  if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges))
280  NewUpperBound = LHS.back().High;
281  }
282 
283  LLVM_DEBUG(dbgs() << "LHS Bounds ==> [" << LowerBound->getSExtValue() << ", "
284  << NewUpperBound->getSExtValue() << "]\n"
285  << "RHS Bounds ==> [" << NewLowerBound->getSExtValue()
286  << ", " << UpperBound->getSExtValue() << "]\n");
287 
288  // Create a new node that checks if the value is < pivot. Go to the
289  // left branch if it is and right branch if not.
290  Function* F = OrigBlock->getParent();
291  BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock");
292 
294  Val, Pivot.Low, "Pivot");
295 
296  BasicBlock *LBranch =
297  SwitchConvert(LHS.begin(), LHS.end(), LowerBound, NewUpperBound, Val,
298  NewNode, OrigBlock, Default, UnreachableRanges);
299  BasicBlock *RBranch =
300  SwitchConvert(RHS.begin(), RHS.end(), NewLowerBound, UpperBound, Val,
301  NewNode, OrigBlock, Default, UnreachableRanges);
302 
303  F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewNode);
304  NewNode->getInstList().push_back(Comp);
305 
306  BranchInst::Create(LBranch, RBranch, Comp, NewNode);
307  return NewNode;
308 }
309 
310 /// Transform simple list of \p SI's cases into list of CaseRange's \p Cases.
311 /// \post \p Cases wouldn't contain references to \p SI's default BB.
312 /// \returns Number of \p SI's cases that do not reference \p SI's default BB.
313 unsigned Clusterify(CaseVector &Cases, SwitchInst *SI) {
314  unsigned NumSimpleCases = 0;
315 
316  // Start with "simple" cases
317  for (auto Case : SI->cases()) {
318  if (Case.getCaseSuccessor() == SI->getDefaultDest())
319  continue;
320  Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),
321  Case.getCaseSuccessor()));
322  ++NumSimpleCases;
323  }
324 
325  llvm::sort(Cases, CaseCmp());
326 
327  // Merge case into clusters
328  if (Cases.size() >= 2) {
329  CaseItr I = Cases.begin();
330  for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {
331  int64_t nextValue = J->Low->getSExtValue();
332  int64_t currentValue = I->High->getSExtValue();
333  BasicBlock* nextBB = J->BB;
334  BasicBlock* currentBB = I->BB;
335 
336  // If the two neighboring cases go to the same destination, merge them
337  // into a single case.
338  assert(nextValue > currentValue && "Cases should be strictly ascending");
339  if ((nextValue == currentValue + 1) && (currentBB == nextBB)) {
340  I->High = J->High;
341  // FIXME: Combine branch weights.
342  } else if (++I != J) {
343  *I = *J;
344  }
345  }
346  Cases.erase(std::next(I), Cases.end());
347  }
348 
349  return NumSimpleCases;
350 }
351 
352 /// Replace the specified switch instruction with a sequence of chained if-then
353 /// insts in a balanced binary search.
354 void ProcessSwitchInst(SwitchInst *SI,
355  SmallPtrSetImpl<BasicBlock *> &DeleteList,
356  AssumptionCache *AC, LazyValueInfo *LVI) {
357  BasicBlock *OrigBlock = SI->getParent();
358  Function *F = OrigBlock->getParent();
359  Value *Val = SI->getCondition(); // The value we are switching on...
360  BasicBlock* Default = SI->getDefaultDest();
361 
362  // Don't handle unreachable blocks. If there are successors with phis, this
363  // would leave them behind with missing predecessors.
364  if ((OrigBlock != &F->getEntryBlock() && pred_empty(OrigBlock)) ||
365  OrigBlock->getSinglePredecessor() == OrigBlock) {
366  DeleteList.insert(OrigBlock);
367  return;
368  }
369 
370  // Prepare cases vector.
371  CaseVector Cases;
372  const unsigned NumSimpleCases = Clusterify(Cases, SI);
373  LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size()
374  << ". Total non-default cases: " << NumSimpleCases
375  << "\nCase clusters: " << Cases << "\n");
376 
377  // If there is only the default destination, just branch.
378  if (Cases.empty()) {
379  BranchInst::Create(Default, OrigBlock);
380  // Remove all the references from Default's PHIs to OrigBlock, but one.
381  FixPhis(Default, OrigBlock, OrigBlock);
382  SI->eraseFromParent();
383  return;
384  }
385 
386  ConstantInt *LowerBound = nullptr;
387  ConstantInt *UpperBound = nullptr;
388  bool DefaultIsUnreachableFromSwitch = false;
389 
390  if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) {
391  // Make the bounds tightly fitted around the case value range, because we
392  // know that the value passed to the switch must be exactly one of the case
393  // values.
394  LowerBound = Cases.front().Low;
395  UpperBound = Cases.back().High;
396  DefaultIsUnreachableFromSwitch = true;
397  } else {
398  // Constraining the range of the value being switched over helps eliminating
399  // unreachable BBs and minimizing the number of `add` instructions
400  // newLeafBlock ends up emitting. Running CorrelatedValuePropagation after
401  // LowerSwitch isn't as good, and also much more expensive in terms of
402  // compile time for the following reasons:
403  // 1. it processes many kinds of instructions, not just switches;
404  // 2. even if limited to icmp instructions only, it will have to process
405  // roughly C icmp's per switch, where C is the number of cases in the
406  // switch, while LowerSwitch only needs to call LVI once per switch.
407  const DataLayout &DL = F->getParent()->getDataLayout();
408  KnownBits Known = computeKnownBits(Val, DL, /*Depth=*/0, AC, SI);
409  // TODO Shouldn't this create a signed range?
410  ConstantRange KnownBitsRange =
411  ConstantRange::fromKnownBits(Known, /*IsSigned=*/false);
412  const ConstantRange LVIRange = LVI->getConstantRange(Val, SI);
413  ConstantRange ValRange = KnownBitsRange.intersectWith(LVIRange);
414  // We delegate removal of unreachable non-default cases to other passes. In
415  // the unlikely event that some of them survived, we just conservatively
416  // maintain the invariant that all the cases lie between the bounds. This
417  // may, however, still render the default case effectively unreachable.
418  APInt Low = Cases.front().Low->getValue();
419  APInt High = Cases.back().High->getValue();
420  APInt Min = APIntOps::smin(ValRange.getSignedMin(), Low);
421  APInt Max = APIntOps::smax(ValRange.getSignedMax(), High);
422 
423  LowerBound = ConstantInt::get(SI->getContext(), Min);
424  UpperBound = ConstantInt::get(SI->getContext(), Max);
425  DefaultIsUnreachableFromSwitch = (Min + (NumSimpleCases - 1) == Max);
426  }
427 
428  std::vector<IntRange> UnreachableRanges;
429 
430  if (DefaultIsUnreachableFromSwitch) {
432  unsigned MaxPop = 0;
433  BasicBlock *PopSucc = nullptr;
434 
435  IntRange R = {std::numeric_limits<int64_t>::min(),
437  UnreachableRanges.push_back(R);
438  for (const auto &I : Cases) {
439  int64_t Low = I.Low->getSExtValue();
440  int64_t High = I.High->getSExtValue();
441 
442  IntRange &LastRange = UnreachableRanges.back();
443  if (LastRange.Low == Low) {
444  // There is nothing left of the previous range.
445  UnreachableRanges.pop_back();
446  } else {
447  // Terminate the previous range.
448  assert(Low > LastRange.Low);
449  LastRange.High = Low - 1;
450  }
452  IntRange R = { High + 1, std::numeric_limits<int64_t>::max() };
453  UnreachableRanges.push_back(R);
454  }
455 
456  // Count popularity.
457  int64_t N = High - Low + 1;
458  unsigned &Pop = Popularity[I.BB];
459  if ((Pop += N) > MaxPop) {
460  MaxPop = Pop;
461  PopSucc = I.BB;
462  }
463  }
464 #ifndef NDEBUG
465  /* UnreachableRanges should be sorted and the ranges non-adjacent. */
466  for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end();
467  I != E; ++I) {
468  assert(I->Low <= I->High);
469  auto Next = I + 1;
470  if (Next != E) {
471  assert(Next->Low > I->High);
472  }
473  }
474 #endif
475 
476  // As the default block in the switch is unreachable, update the PHI nodes
477  // (remove all of the references to the default block) to reflect this.
478  const unsigned NumDefaultEdges = SI->getNumCases() + 1 - NumSimpleCases;
479  for (unsigned I = 0; I < NumDefaultEdges; ++I)
480  Default->removePredecessor(OrigBlock);
481 
482  // Use the most popular block as the new default, reducing the number of
483  // cases.
484  assert(MaxPop > 0 && PopSucc);
485  Default = PopSucc;
486  llvm::erase_if(Cases,
487  [PopSucc](const CaseRange &R) { return R.BB == PopSucc; });
488 
489  // If there are no cases left, just branch.
490  if (Cases.empty()) {
491  BranchInst::Create(Default, OrigBlock);
492  SI->eraseFromParent();
493  // As all the cases have been replaced with a single branch, only keep
494  // one entry in the PHI nodes.
495  for (unsigned I = 0 ; I < (MaxPop - 1) ; ++I)
496  PopSucc->removePredecessor(OrigBlock);
497  return;
498  }
499 
500  // If the condition was a PHI node with the switch block as a predecessor
501  // removing predecessors may have caused the condition to be erased.
502  // Getting the condition value again here protects against that.
503  Val = SI->getCondition();
504  }
505 
506  BasicBlock *SwitchBlock =
507  SwitchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
508  OrigBlock, OrigBlock, Default, UnreachableRanges);
509 
510  // We have added incoming values for newly-created predecessors in
511  // NewLeafBlock(). The only meaningful work we offload to FixPhis() is to
512  // remove the incoming values from OrigBlock. There might be a special case
513  // that SwitchBlock is the same as Default, under which the PHIs in Default
514  // are fixed inside SwitchConvert().
515  if (SwitchBlock != Default)
516  FixPhis(Default, OrigBlock, nullptr);
517 
518  // Branch to our shiny new if-then stuff...
519  BranchInst::Create(SwitchBlock, OrigBlock);
520 
521  // We are now done with the switch instruction, delete it.
522  BasicBlock *OldDefault = SI->getDefaultDest();
523  OrigBlock->getInstList().erase(SI);
524 
525  // If the Default block has no more predecessors just add it to DeleteList.
526  if (pred_empty(OldDefault))
527  DeleteList.insert(OldDefault);
528 }
529 
530 bool LowerSwitch(Function &F, LazyValueInfo *LVI, AssumptionCache *AC) {
531  bool Changed = false;
532  SmallPtrSet<BasicBlock *, 8> DeleteList;
533 
534  // We use make_early_inc_range here so that we don't traverse new blocks.
535  for (BasicBlock &Cur : llvm::make_early_inc_range(F)) {
536  // If the block is a dead Default block that will be deleted later, don't
537  // waste time processing it.
538  if (DeleteList.count(&Cur))
539  continue;
540 
541  if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur.getTerminator())) {
542  Changed = true;
543  ProcessSwitchInst(SI, DeleteList, AC, LVI);
544  }
545  }
546 
547  for (BasicBlock *BB : DeleteList) {
548  LVI->eraseBlock(BB);
550  }
551 
552  return Changed;
553 }
554 
555 /// Replace all SwitchInst instructions with chained branch instructions.
556 class LowerSwitchLegacyPass : public FunctionPass {
557 public:
558  // Pass identification, replacement for typeid
559  static char ID;
560 
561  LowerSwitchLegacyPass() : FunctionPass(ID) {
563  }
564 
565  bool runOnFunction(Function &F) override;
566 
567  void getAnalysisUsage(AnalysisUsage &AU) const override {
569  }
570 };
571 
572 } // end anonymous namespace
573 
575 
576 // Publicly exposed interface to pass...
578 
579 INITIALIZE_PASS_BEGIN(LowerSwitchLegacyPass, "lowerswitch",
580  "Lower SwitchInst's to branches", false, false)
583 INITIALIZE_PASS_END(LowerSwitchLegacyPass, "lowerswitch",
585 
586 // createLowerSwitchPass - Interface to this file...
588  return new LowerSwitchLegacyPass();
589 }
590 
592  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
593  auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>();
594  AssumptionCache *AC = ACT ? &ACT->getAssumptionCache(F) : nullptr;
595  return LowerSwitch(F, LVI, AC);
596 }
597 
602  return LowerSwitch(F, LVI, AC) ? PreservedAnalyses::none()
604 }
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:138
llvm::LowerSwitchPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LowerSwitch.cpp:598
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:740
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
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:104
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:780
llvm::initializeLowerSwitchLegacyPassPass
void initializeLowerSwitchLegacyPassPass(PassRegistry &)
llvm::Function
Definition: Function.h:60
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:1736
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:133
High
uint64_t High
Definition: NVVMIntrRange.cpp:61
llvm::LazyValueAnalysis
Analysis to compute lazy value information.
Definition: LazyValueInfo.h:134
llvm::SmallVector< unsigned, 8 >
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:1807
llvm::PHINode::removeIncomingValue
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Definition: Instructions.cpp:113
ValueTracking.h
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
DenseMap.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
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:749
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
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:261
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:240
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:79
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:31
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:745
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
InstrTypes.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
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:2836
llvm::Instruction
Definition: Instruction.h:42
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:355
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
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:928
SmallPtrSet.h
Utils.h
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2743
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:58
CFG.h
llvm::createLowerSwitchPass
FunctionPass * createLowerSwitchPass()
Definition: LowerSwitch.cpp:587
BasicBlock.h
llvm::APInt::slt
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1080
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:239
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:1173
uint64_t
llvm::ConstantRange::getSignedMin
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:443
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:1610
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:2786
llvm::LazyValueInfoWrapperPass
Wrapper around LazyValueInfo.
Definition: LazyValueInfo.h:145
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:2801
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3142
llvm::DenseMap< BasicBlock *, unsigned >
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:618
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:2829
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:222
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
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:584
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:748
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:2127
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:97
Compiler.h
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
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::ConstantInt::getSExtValue
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:148
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::LowerSwitchID
char & LowerSwitchID
Definition: LowerSwitch.cpp:577
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
j
return j(j<< 16)
llvm::ConstantRange::getSignedMax
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:437
llvm::KnownBits
Definition: KnownBits.h:23
llvm::ConstantExpr::getNeg
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2704
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:2723
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:799
Casting.h
Function.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1562
PassManager.h
llvm::TargetStackID::Default
@ Default
Definition: TargetFrameLowering.h:28
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:747
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:364
lowerswitch
lowerswitch
Definition: LowerSwitch.cpp:583
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:523
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:58
N
#define N
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2767
llvm::PHINode
Definition: Instructions.h:2651
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:318
llvm::DeleteDeadBlock
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
Definition: BasicBlockUtils.cpp:94
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:231
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3230
raw_ostream.h
llvm::LazyValueInfo::eraseBlock
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
Definition: LazyValueInfo.cpp:1876
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:2132
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
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38