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