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