LLVM  9.0.0svn
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 
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/CFG.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/Function.h"
23 #include "llvm/IR/InstrTypes.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/Value.h"
26 #include "llvm/Pass.h"
27 #include "llvm/Support/Casting.h"
28 #include "llvm/Support/Compiler.h"
29 #include "llvm/Support/Debug.h"
31 #include "llvm/Transforms/Utils.h"
33 #include <algorithm>
34 #include <cassert>
35 #include <cstdint>
36 #include <iterator>
37 #include <limits>
38 #include <vector>
39 
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "lower-switch"
43 
44 namespace {
45 
46  struct IntRange {
47  int64_t Low, High;
48  };
49 
50 } // end anonymous namespace
51 
52 // Return true iff R is covered by Ranges.
53 static bool IsInRanges(const IntRange &R,
54  const std::vector<IntRange> &Ranges) {
55  // Note: Ranges must be sorted, non-overlapping and non-adjacent.
56 
57  // Find the first range whose High field is >= R.High,
58  // then check if the Low field is <= R.Low. If so, we
59  // have a Range that covers R.
60  auto I = std::lower_bound(
61  Ranges.begin(), Ranges.end(), R,
62  [](const IntRange &A, const IntRange &B) { return A.High < B.High; });
63  return I != Ranges.end() && I->Low <= R.Low;
64 }
65 
66 namespace {
67 
68  /// Replace all SwitchInst instructions with chained branch instructions.
69  class LowerSwitch : public FunctionPass {
70  public:
71  // Pass identification, replacement for typeid
72  static char ID;
73 
74  LowerSwitch() : FunctionPass(ID) {
76  }
77 
78  bool runOnFunction(Function &F) override;
79 
80  struct CaseRange {
81  ConstantInt* Low;
83  BasicBlock* BB;
84 
85  CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb)
86  : Low(low), High(high), BB(bb) {}
87  };
88 
89  using CaseVector = std::vector<CaseRange>;
90  using CaseItr = std::vector<CaseRange>::iterator;
91 
92  private:
93  void processSwitchInst(SwitchInst *SI, SmallPtrSetImpl<BasicBlock*> &DeleteList);
94 
95  BasicBlock *switchConvert(CaseItr Begin, CaseItr End,
96  ConstantInt *LowerBound, ConstantInt *UpperBound,
97  Value *Val, BasicBlock *Predecessor,
98  BasicBlock *OrigBlock, BasicBlock *Default,
99  const std::vector<IntRange> &UnreachableRanges);
100  BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, BasicBlock *OrigBlock,
101  BasicBlock *Default);
102  unsigned Clusterify(CaseVector &Cases, SwitchInst *SI);
103  };
104 
105  /// The comparison function for sorting the switch case values in the vector.
106  /// WARNING: Case ranges should be disjoint!
107  struct CaseCmp {
108  bool operator()(const LowerSwitch::CaseRange& C1,
109  const LowerSwitch::CaseRange& C2) {
110  const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low);
111  const ConstantInt* CI2 = cast<const ConstantInt>(C2.High);
112  return CI1->getValue().slt(CI2->getValue());
113  }
114  };
115 
116 } // end anonymous namespace
117 
118 char LowerSwitch::ID = 0;
119 
120 // Publicly exposed interface to pass...
122 
123 INITIALIZE_PASS(LowerSwitch, "lowerswitch",
124  "Lower SwitchInst's to branches", false, false)
125 
126 // createLowerSwitchPass - Interface to this file...
128  return new LowerSwitch();
129 }
130 
132  bool Changed = false;
133  SmallPtrSet<BasicBlock*, 8> DeleteList;
134 
135  for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
136  BasicBlock *Cur = &*I++; // Advance over block so we don't traverse new blocks
137 
138  // If the block is a dead Default block that will be deleted later, don't
139  // waste time processing it.
140  if (DeleteList.count(Cur))
141  continue;
142 
143  if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) {
144  Changed = true;
145  processSwitchInst(SI, DeleteList);
146  }
147  }
148 
149  for (BasicBlock* BB: DeleteList) {
150  DeleteDeadBlock(BB);
151  }
152 
153  return Changed;
154 }
155 
156 /// Used for debugging purposes.
159  const LowerSwitch::CaseVector &C) {
160  O << "[";
161 
162  for (LowerSwitch::CaseVector::const_iterator B = C.begin(),
163  E = C.end(); B != E; ) {
164  O << *B->Low << " -" << *B->High;
165  if (++B != E) O << ", ";
166  }
167 
168  return O << "]";
169 }
170 
171 /// Update the first occurrence of the "switch statement" BB in the PHI
172 /// node with the "new" BB. The other occurrences will:
173 ///
174 /// 1) Be updated by subsequent calls to this function. Switch statements may
175 /// have more than one outcoming edge into the same BB if they all have the same
176 /// value. When the switch statement is converted these incoming edges are now
177 /// coming from multiple BBs.
178 /// 2) Removed if subsequent incoming values now share the same case, i.e.,
179 /// multiple outcome edges are condensed into one. This is necessary to keep the
180 /// number of phi values equal to the number of branches to SuccBB.
181 static void fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB,
182  unsigned NumMergedCases) {
183  for (BasicBlock::iterator I = SuccBB->begin(),
184  IE = SuccBB->getFirstNonPHI()->getIterator();
185  I != IE; ++I) {
186  PHINode *PN = cast<PHINode>(I);
187 
188  // Only update the first occurrence.
189  unsigned Idx = 0, E = PN->getNumIncomingValues();
190  unsigned LocalNumMergedCases = NumMergedCases;
191  for (; Idx != E; ++Idx) {
192  if (PN->getIncomingBlock(Idx) == OrigBB) {
193  PN->setIncomingBlock(Idx, NewBB);
194  break;
195  }
196  }
197 
198  // Remove additional occurrences coming from condensed cases and keep the
199  // number of incoming values equal to the number of branches to SuccBB.
200  SmallVector<unsigned, 8> Indices;
201  for (++Idx; LocalNumMergedCases > 0 && Idx < E; ++Idx)
202  if (PN->getIncomingBlock(Idx) == OrigBB) {
203  Indices.push_back(Idx);
204  LocalNumMergedCases--;
205  }
206  // Remove incoming values in the reverse order to prevent invalidating
207  // *successive* index.
208  for (unsigned III : llvm::reverse(Indices))
209  PN->removeIncomingValue(III);
210  }
211 }
212 
213 /// Convert the switch statement into a binary lookup of the case values.
214 /// The function recursively builds this tree. LowerBound and UpperBound are
215 /// used to keep track of the bounds for Val that have already been checked by
216 /// a block emitted by one of the previous calls to switchConvert in the call
217 /// stack.
218 BasicBlock *
219 LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,
220  ConstantInt *UpperBound, Value *Val,
221  BasicBlock *Predecessor, BasicBlock *OrigBlock,
223  const std::vector<IntRange> &UnreachableRanges) {
224  unsigned Size = End - Begin;
225 
226  if (Size == 1) {
227  // Check if the Case Range is perfectly squeezed in between
228  // already checked Upper and Lower bounds. If it is then we can avoid
229  // emitting the code that checks if the value actually falls in the range
230  // because the bounds already tell us so.
231  if (Begin->Low == LowerBound && Begin->High == UpperBound) {
232  unsigned NumMergedCases = 0;
233  if (LowerBound && UpperBound)
234  NumMergedCases =
235  UpperBound->getSExtValue() - LowerBound->getSExtValue();
236  fixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);
237  return Begin->BB;
238  }
239  return newLeafBlock(*Begin, Val, OrigBlock, Default);
240  }
241 
242  unsigned Mid = Size / 2;
243  std::vector<CaseRange> LHS(Begin, Begin + Mid);
244  LLVM_DEBUG(dbgs() << "LHS: " << LHS << "\n");
245  std::vector<CaseRange> RHS(Begin + Mid, End);
246  LLVM_DEBUG(dbgs() << "RHS: " << RHS << "\n");
247 
248  CaseRange &Pivot = *(Begin + Mid);
249  LLVM_DEBUG(dbgs() << "Pivot ==> " << Pivot.Low->getValue() << " -"
250  << Pivot.High->getValue() << "\n");
251 
252  // NewLowerBound here should never be the integer minimal value.
253  // This is because it is computed from a case range that is never
254  // the smallest, so there is always a case range that has at least
255  // a smaller value.
256  ConstantInt *NewLowerBound = Pivot.Low;
257 
258  // Because NewLowerBound is never the smallest representable integer
259  // it is safe here to subtract one.
260  ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(),
261  NewLowerBound->getValue() - 1);
262 
263  if (!UnreachableRanges.empty()) {
264  // Check if the gap between LHS's highest and NewLowerBound is unreachable.
265  int64_t GapLow = LHS.back().High->getSExtValue() + 1;
266  int64_t GapHigh = NewLowerBound->getSExtValue() - 1;
267  IntRange Gap = { GapLow, GapHigh };
268  if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges))
269  NewUpperBound = LHS.back().High;
270  }
271 
272  LLVM_DEBUG(dbgs() << "LHS Bounds ==> "; if (LowerBound) {
273  dbgs() << LowerBound->getSExtValue();
274  } else { dbgs() << "NONE"; } dbgs() << " - "
275  << NewUpperBound->getSExtValue() << "\n";
276  dbgs() << "RHS Bounds ==> ";
277  dbgs() << NewLowerBound->getSExtValue() << " - "; if (UpperBound) {
278  dbgs() << UpperBound->getSExtValue() << "\n";
279  } else { dbgs() << "NONE\n"; });
280 
281  // Create a new node that checks if the value is < pivot. Go to the
282  // left branch if it is and right branch if not.
283  Function* F = OrigBlock->getParent();
284  BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock");
285 
287  Val, Pivot.Low, "Pivot");
288 
289  BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound,
290  NewUpperBound, Val, NewNode, OrigBlock,
291  Default, UnreachableRanges);
292  BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound,
293  UpperBound, Val, NewNode, OrigBlock,
294  Default, UnreachableRanges);
295 
296  F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewNode);
297  NewNode->getInstList().push_back(Comp);
298 
299  BranchInst::Create(LBranch, RBranch, Comp, NewNode);
300  return NewNode;
301 }
302 
303 /// Create a new leaf block for the binary lookup tree. It checks if the
304 /// switch's value == the case's value. If not, then it jumps to the default
305 /// branch. At this point in the tree, the value can't be another valid case
306 /// value, so the jump to the "default" branch is warranted.
307 BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val,
308  BasicBlock* OrigBlock,
309  BasicBlock* Default) {
310  Function* F = OrigBlock->getParent();
311  BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock");
312  F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewLeaf);
313 
314  // Emit comparison
315  ICmpInst* Comp = nullptr;
316  if (Leaf.Low == Leaf.High) {
317  // Make the seteq instruction...
318  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val,
319  Leaf.Low, "SwitchLeaf");
320  } else {
321  // Make range comparison
322  if (Leaf.Low->isMinValue(true /*isSigned*/)) {
323  // Val >= Min && Val <= Hi --> Val <= Hi
324  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High,
325  "SwitchLeaf");
326  } else if (Leaf.Low->isZero()) {
327  // Val >= 0 && Val <= Hi --> Val <=u Hi
328  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High,
329  "SwitchLeaf");
330  } else {
331  // Emit V-Lo <=u Hi-Lo
332  Constant* NegLo = ConstantExpr::getNeg(Leaf.Low);
334  Val->getName()+".off",
335  NewLeaf);
336  Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High);
337  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound,
338  "SwitchLeaf");
339  }
340  }
341 
342  // Make the conditional branch...
343  BasicBlock* Succ = Leaf.BB;
344  BranchInst::Create(Succ, Default, Comp, NewLeaf);
345 
346  // If there were any PHI nodes in this successor, rewrite one entry
347  // from OrigBlock to come from NewLeaf.
348  for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
349  PHINode* PN = cast<PHINode>(I);
350  // Remove all but one incoming entries from the cluster
351  uint64_t Range = Leaf.High->getSExtValue() -
352  Leaf.Low->getSExtValue();
353  for (uint64_t j = 0; j < Range; ++j) {
354  PN->removeIncomingValue(OrigBlock);
355  }
356 
357  int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
358  assert(BlockIdx != -1 && "Switch didn't go to this successor??");
359  PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf);
360  }
361 
362  return NewLeaf;
363 }
364 
365 /// Transform simple list of Cases into list of CaseRange's.
366 unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) {
367  unsigned numCmps = 0;
368 
369  // Start with "simple" cases
370  for (auto Case : SI->cases())
371  Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),
372  Case.getCaseSuccessor()));
373 
374  llvm::sort(Cases, CaseCmp());
375 
376  // Merge case into clusters
377  if (Cases.size() >= 2) {
378  CaseItr I = Cases.begin();
379  for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {
380  int64_t nextValue = J->Low->getSExtValue();
381  int64_t currentValue = I->High->getSExtValue();
382  BasicBlock* nextBB = J->BB;
383  BasicBlock* currentBB = I->BB;
384 
385  // If the two neighboring cases go to the same destination, merge them
386  // into a single case.
387  assert(nextValue > currentValue && "Cases should be strictly ascending");
388  if ((nextValue == currentValue + 1) && (currentBB == nextBB)) {
389  I->High = J->High;
390  // FIXME: Combine branch weights.
391  } else if (++I != J) {
392  *I = *J;
393  }
394  }
395  Cases.erase(std::next(I), Cases.end());
396  }
397 
398  for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) {
399  if (I->Low != I->High)
400  // A range counts double, since it requires two compares.
401  ++numCmps;
402  }
403 
404  return numCmps;
405 }
406 
407 /// Replace the specified switch instruction with a sequence of chained if-then
408 /// insts in a balanced binary search.
409 void LowerSwitch::processSwitchInst(SwitchInst *SI,
410  SmallPtrSetImpl<BasicBlock*> &DeleteList) {
411  BasicBlock *CurBlock = SI->getParent();
412  BasicBlock *OrigBlock = CurBlock;
413  Function *F = CurBlock->getParent();
414  Value *Val = SI->getCondition(); // The value we are switching on...
415  BasicBlock* Default = SI->getDefaultDest();
416 
417  // Don't handle unreachable blocks. If there are successors with phis, this
418  // would leave them behind with missing predecessors.
419  if ((CurBlock != &F->getEntryBlock() && pred_empty(CurBlock)) ||
420  CurBlock->getSinglePredecessor() == CurBlock) {
421  DeleteList.insert(CurBlock);
422  return;
423  }
424 
425  // If there is only the default destination, just branch.
426  if (!SI->getNumCases()) {
427  BranchInst::Create(Default, CurBlock);
428  SI->eraseFromParent();
429  return;
430  }
431 
432  // Prepare cases vector.
433  CaseVector Cases;
434  unsigned numCmps = Clusterify(Cases, SI);
435  LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size()
436  << ". Total compares: " << numCmps << "\n");
437  LLVM_DEBUG(dbgs() << "Cases: " << Cases << "\n");
438  (void)numCmps;
439 
440  ConstantInt *LowerBound = nullptr;
441  ConstantInt *UpperBound = nullptr;
442  std::vector<IntRange> UnreachableRanges;
443 
444  if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) {
445  // Make the bounds tightly fitted around the case value range, because we
446  // know that the value passed to the switch must be exactly one of the case
447  // values.
448  assert(!Cases.empty());
449  LowerBound = Cases.front().Low;
450  UpperBound = Cases.back().High;
451 
453  unsigned MaxPop = 0;
454  BasicBlock *PopSucc = nullptr;
455 
456  IntRange R = {std::numeric_limits<int64_t>::min(),
458  UnreachableRanges.push_back(R);
459  for (const auto &I : Cases) {
460  int64_t Low = I.Low->getSExtValue();
461  int64_t High = I.High->getSExtValue();
462 
463  IntRange &LastRange = UnreachableRanges.back();
464  if (LastRange.Low == Low) {
465  // There is nothing left of the previous range.
466  UnreachableRanges.pop_back();
467  } else {
468  // Terminate the previous range.
469  assert(Low > LastRange.Low);
470  LastRange.High = Low - 1;
471  }
472  if (High != std::numeric_limits<int64_t>::max()) {
473  IntRange R = { High + 1, std::numeric_limits<int64_t>::max() };
474  UnreachableRanges.push_back(R);
475  }
476 
477  // Count popularity.
478  int64_t N = High - Low + 1;
479  unsigned &Pop = Popularity[I.BB];
480  if ((Pop += N) > MaxPop) {
481  MaxPop = Pop;
482  PopSucc = I.BB;
483  }
484  }
485 #ifndef NDEBUG
486  /* UnreachableRanges should be sorted and the ranges non-adjacent. */
487  for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end();
488  I != E; ++I) {
489  assert(I->Low <= I->High);
490  auto Next = I + 1;
491  if (Next != E) {
492  assert(Next->Low > I->High);
493  }
494  }
495 #endif
496 
497  // As the default block in the switch is unreachable, update the PHI nodes
498  // (remove the entry to the default block) to reflect this.
499  Default->removePredecessor(OrigBlock);
500 
501  // Use the most popular block as the new default, reducing the number of
502  // cases.
503  assert(MaxPop > 0 && PopSucc);
504  Default = PopSucc;
505  Cases.erase(
507  Cases, [PopSucc](const CaseRange &R) { return R.BB == PopSucc; }),
508  Cases.end());
509 
510  // If there are no cases left, just branch.
511  if (Cases.empty()) {
512  BranchInst::Create(Default, CurBlock);
513  SI->eraseFromParent();
514  // As all the cases have been replaced with a single branch, only keep
515  // one entry in the PHI nodes.
516  for (unsigned I = 0 ; I < (MaxPop - 1) ; ++I)
517  PopSucc->removePredecessor(OrigBlock);
518  return;
519  }
520  }
521 
522  unsigned NrOfDefaults = (SI->getDefaultDest() == Default) ? 1 : 0;
523  for (const auto &Case : SI->cases())
524  if (Case.getCaseSuccessor() == Default)
525  NrOfDefaults++;
526 
527  // Create a new, empty default block so that the new hierarchy of
528  // if-then statements go to this and the PHI nodes are happy.
529  BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault");
530  F->getBasicBlockList().insert(Default->getIterator(), NewDefault);
531  BranchInst::Create(Default, NewDefault);
532 
533  BasicBlock *SwitchBlock =
534  switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
535  OrigBlock, OrigBlock, NewDefault, UnreachableRanges);
536 
537  // If there are entries in any PHI nodes for the default edge, make sure
538  // to update them as well.
539  fixPhis(Default, OrigBlock, NewDefault, NrOfDefaults);
540 
541  // Branch to our shiny new if-then stuff...
542  BranchInst::Create(SwitchBlock, OrigBlock);
543 
544  // We are now done with the switch instruction, delete it.
545  BasicBlock *OldDefault = SI->getDefaultDest();
546  CurBlock->getInstList().erase(SI);
547 
548  // If the Default block has no more predecessors just add it to DeleteList.
549  if (pred_begin(OldDefault) == pred_end(OldDefault))
550  DeleteList.insert(OldDefault);
551 }
uint64_t CallInst * C
unsigned getNumCases() const
Return the number of &#39;cases&#39; in this switch instruction, excluding the default case.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
iterator_range< CaseIt > cases()
Iteration adapter for range-for loops.
iterator erase(iterator where)
Definition: ilist.h:265
This class represents lattice values for constants.
Definition: AllocatorList.h:23
FunctionPass * createLowerSwitchPass()
iterator end()
Definition: Function.h:657
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Notify the BasicBlock that the predecessor Pred is no longer able to reach it.
Definition: BasicBlock.cpp:301
void push_back(const T &Elt)
Definition: SmallVector.h:211
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1203
Value * getCondition() const
unsigned less or equal
Definition: InstrTypes.h:672
static bool IsInRanges(const IntRange &R, const std::vector< IntRange > &Ranges)
Definition: LowerSwitch.cpp:53
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:705
F(f)
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
uint64_t High
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2237
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:266
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:137
auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1281
iterator begin()
Definition: Function.h:655
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
const BasicBlock & getEntryBlock() const
Definition: Function.h:639
static bool runOnFunction(Function &F, bool PostInlining)
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:189
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
INITIALIZE_PASS(LowerSwitch, "lowerswitch", "Lower SwitchInst's to branches", false, false) FunctionPass *llvm
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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:370
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:112
BasicBlock * getDefaultDest() const
static void fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB, unsigned NumMergedCases)
Update the first occurrence of the "switch statement" BB in the PHI node with the "new" BB...
This instruction compares its operands according to the predicate given to the constructor.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:99
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
self_iterator getIterator()
Definition: ilist_node.h:81
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:116
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1225
char & LowerSwitchID
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1115
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:333
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
void setIncomingBlock(unsigned i, BasicBlock *BB)
signed less than
Definition: InstrTypes.h:675
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:621
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
signed less or equal
Definition: InstrTypes.h:676
void push_back(pointer val)
Definition: ilist.h:311
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2218
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iterator insert(iterator where, pointer New)
Definition: ilist.h:226
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:632
uint32_t Size
Definition: Profile.cpp:46
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
Multiway switch.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
void initializeLowerSwitchPass(PassRegistry &)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
const Instruction * getFirstNonPHIOrDbg() const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic...
Definition: BasicBlock.cpp:196
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:156
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const BasicBlock * getParent() const
Definition: Instruction.h:66
#define LLVM_ATTRIBUTE_USED
Definition: Compiler.h:119