LLVM  7.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/Utils.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.
160  const LowerSwitch::CaseVector &C) {
161  O << "[";
162 
163  for (LowerSwitch::CaseVector::const_iterator B = C.begin(),
164  E = C.end(); B != E; ) {
165  O << *B->Low << " -" << *B->High;
166  if (++B != E) O << ", ";
167  }
168 
169  return O << "]";
170 }
171 
172 /// Update the first occurrence of the "switch statement" BB in the PHI
173 /// node with the "new" BB. The other occurrences will:
174 ///
175 /// 1) Be updated by subsequent calls to this function. Switch statements may
176 /// have more than one outcoming edge into the same BB if they all have the same
177 /// value. When the switch statement is converted these incoming edges are now
178 /// coming from multiple BBs.
179 /// 2) Removed if subsequent incoming values now share the same case, i.e.,
180 /// multiple outcome edges are condensed into one. This is necessary to keep the
181 /// number of phi values equal to the number of branches to SuccBB.
182 static void fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB,
183  unsigned NumMergedCases) {
184  for (BasicBlock::iterator I = SuccBB->begin(),
185  IE = SuccBB->getFirstNonPHI()->getIterator();
186  I != IE; ++I) {
187  PHINode *PN = cast<PHINode>(I);
188 
189  // Only update the first occurrence.
190  unsigned Idx = 0, E = PN->getNumIncomingValues();
191  unsigned LocalNumMergedCases = NumMergedCases;
192  for (; Idx != E; ++Idx) {
193  if (PN->getIncomingBlock(Idx) == OrigBB) {
194  PN->setIncomingBlock(Idx, NewBB);
195  break;
196  }
197  }
198 
199  // Remove additional occurrences coming from condensed cases and keep the
200  // number of incoming values equal to the number of branches to SuccBB.
201  SmallVector<unsigned, 8> Indices;
202  for (++Idx; LocalNumMergedCases > 0 && Idx < E; ++Idx)
203  if (PN->getIncomingBlock(Idx) == OrigBB) {
204  Indices.push_back(Idx);
205  LocalNumMergedCases--;
206  }
207  // Remove incoming values in the reverse order to prevent invalidating
208  // *successive* index.
209  for (unsigned III : llvm::reverse(Indices))
210  PN->removeIncomingValue(III);
211  }
212 }
213 
214 /// Convert the switch statement into a binary lookup of the case values.
215 /// The function recursively builds this tree. LowerBound and UpperBound are
216 /// used to keep track of the bounds for Val that have already been checked by
217 /// a block emitted by one of the previous calls to switchConvert in the call
218 /// stack.
219 BasicBlock *
220 LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,
221  ConstantInt *UpperBound, Value *Val,
222  BasicBlock *Predecessor, BasicBlock *OrigBlock,
224  const std::vector<IntRange> &UnreachableRanges) {
225  unsigned Size = End - Begin;
226 
227  if (Size == 1) {
228  // Check if the Case Range is perfectly squeezed in between
229  // already checked Upper and Lower bounds. If it is then we can avoid
230  // emitting the code that checks if the value actually falls in the range
231  // because the bounds already tell us so.
232  if (Begin->Low == LowerBound && Begin->High == UpperBound) {
233  unsigned NumMergedCases = 0;
234  if (LowerBound && UpperBound)
235  NumMergedCases =
236  UpperBound->getSExtValue() - LowerBound->getSExtValue();
237  fixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);
238  return Begin->BB;
239  }
240  return newLeafBlock(*Begin, Val, OrigBlock, Default);
241  }
242 
243  unsigned Mid = Size / 2;
244  std::vector<CaseRange> LHS(Begin, Begin + Mid);
245  LLVM_DEBUG(dbgs() << "LHS: " << LHS << "\n");
246  std::vector<CaseRange> RHS(Begin + Mid, End);
247  LLVM_DEBUG(dbgs() << "RHS: " << RHS << "\n");
248 
249  CaseRange &Pivot = *(Begin + Mid);
250  LLVM_DEBUG(dbgs() << "Pivot ==> " << Pivot.Low->getValue() << " -"
251  << Pivot.High->getValue() << "\n");
252 
253  // NewLowerBound here should never be the integer minimal value.
254  // This is because it is computed from a case range that is never
255  // the smallest, so there is always a case range that has at least
256  // a smaller value.
257  ConstantInt *NewLowerBound = Pivot.Low;
258 
259  // Because NewLowerBound is never the smallest representable integer
260  // it is safe here to subtract one.
261  ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(),
262  NewLowerBound->getValue() - 1);
263 
264  if (!UnreachableRanges.empty()) {
265  // Check if the gap between LHS's highest and NewLowerBound is unreachable.
266  int64_t GapLow = LHS.back().High->getSExtValue() + 1;
267  int64_t GapHigh = NewLowerBound->getSExtValue() - 1;
268  IntRange Gap = { GapLow, GapHigh };
269  if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges))
270  NewUpperBound = LHS.back().High;
271  }
272 
273  LLVM_DEBUG(dbgs() << "LHS Bounds ==> "; if (LowerBound) {
274  dbgs() << LowerBound->getSExtValue();
275  } else { dbgs() << "NONE"; } dbgs() << " - "
276  << NewUpperBound->getSExtValue() << "\n";
277  dbgs() << "RHS Bounds ==> ";
278  dbgs() << NewLowerBound->getSExtValue() << " - "; if (UpperBound) {
279  dbgs() << UpperBound->getSExtValue() << "\n";
280  } else { dbgs() << "NONE\n"; });
281 
282  // Create a new node that checks if the value is < pivot. Go to the
283  // left branch if it is and right branch if not.
284  Function* F = OrigBlock->getParent();
285  BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock");
286 
288  Val, Pivot.Low, "Pivot");
289 
290  BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound,
291  NewUpperBound, Val, NewNode, OrigBlock,
292  Default, UnreachableRanges);
293  BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound,
294  UpperBound, Val, NewNode, OrigBlock,
295  Default, UnreachableRanges);
296 
297  F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewNode);
298  NewNode->getInstList().push_back(Comp);
299 
300  BranchInst::Create(LBranch, RBranch, Comp, NewNode);
301  return NewNode;
302 }
303 
304 /// Create a new leaf block for the binary lookup tree. It checks if the
305 /// switch's value == the case's value. If not, then it jumps to the default
306 /// branch. At this point in the tree, the value can't be another valid case
307 /// value, so the jump to the "default" branch is warranted.
308 BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val,
309  BasicBlock* OrigBlock,
310  BasicBlock* Default) {
311  Function* F = OrigBlock->getParent();
312  BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock");
313  F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewLeaf);
314 
315  // Emit comparison
316  ICmpInst* Comp = nullptr;
317  if (Leaf.Low == Leaf.High) {
318  // Make the seteq instruction...
319  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val,
320  Leaf.Low, "SwitchLeaf");
321  } else {
322  // Make range comparison
323  if (Leaf.Low->isMinValue(true /*isSigned*/)) {
324  // Val >= Min && Val <= Hi --> Val <= Hi
325  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High,
326  "SwitchLeaf");
327  } else if (Leaf.Low->isZero()) {
328  // Val >= 0 && Val <= Hi --> Val <=u Hi
329  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High,
330  "SwitchLeaf");
331  } else {
332  // Emit V-Lo <=u Hi-Lo
333  Constant* NegLo = ConstantExpr::getNeg(Leaf.Low);
335  Val->getName()+".off",
336  NewLeaf);
337  Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High);
338  Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound,
339  "SwitchLeaf");
340  }
341  }
342 
343  // Make the conditional branch...
344  BasicBlock* Succ = Leaf.BB;
345  BranchInst::Create(Succ, Default, Comp, NewLeaf);
346 
347  // If there were any PHI nodes in this successor, rewrite one entry
348  // from OrigBlock to come from NewLeaf.
349  for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
350  PHINode* PN = cast<PHINode>(I);
351  // Remove all but one incoming entries from the cluster
352  uint64_t Range = Leaf.High->getSExtValue() -
353  Leaf.Low->getSExtValue();
354  for (uint64_t j = 0; j < Range; ++j) {
355  PN->removeIncomingValue(OrigBlock);
356  }
357 
358  int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
359  assert(BlockIdx != -1 && "Switch didn't go to this successor??");
360  PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf);
361  }
362 
363  return NewLeaf;
364 }
365 
366 /// Transform simple list of Cases into list of CaseRange's.
367 unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) {
368  unsigned numCmps = 0;
369 
370  // Start with "simple" cases
371  for (auto Case : SI->cases())
372  Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),
373  Case.getCaseSuccessor()));
374 
375  llvm::sort(Cases.begin(), Cases.end(), CaseCmp());
376 
377  // Merge case into clusters
378  if (Cases.size() >= 2) {
379  CaseItr I = Cases.begin();
380  for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {
381  int64_t nextValue = J->Low->getSExtValue();
382  int64_t currentValue = I->High->getSExtValue();
383  BasicBlock* nextBB = J->BB;
384  BasicBlock* currentBB = I->BB;
385 
386  // If the two neighboring cases go to the same destination, merge them
387  // into a single case.
388  assert(nextValue > currentValue && "Cases should be strictly ascending");
389  if ((nextValue == currentValue + 1) && (currentBB == nextBB)) {
390  I->High = J->High;
391  // FIXME: Combine branch weights.
392  } else if (++I != J) {
393  *I = *J;
394  }
395  }
396  Cases.erase(std::next(I), Cases.end());
397  }
398 
399  for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) {
400  if (I->Low != I->High)
401  // A range counts double, since it requires two compares.
402  ++numCmps;
403  }
404 
405  return numCmps;
406 }
407 
408 /// Replace the specified switch instruction with a sequence of chained if-then
409 /// insts in a balanced binary search.
410 void LowerSwitch::processSwitchInst(SwitchInst *SI,
411  SmallPtrSetImpl<BasicBlock*> &DeleteList) {
412  BasicBlock *CurBlock = SI->getParent();
413  BasicBlock *OrigBlock = CurBlock;
414  Function *F = CurBlock->getParent();
415  Value *Val = SI->getCondition(); // The value we are switching on...
416  BasicBlock* Default = SI->getDefaultDest();
417 
418  // Don't handle unreachable blocks. If there are successors with phis, this
419  // would leave them behind with missing predecessors.
420  if ((CurBlock != &F->getEntryBlock() && pred_empty(CurBlock)) ||
421  CurBlock->getSinglePredecessor() == CurBlock) {
422  DeleteList.insert(CurBlock);
423  return;
424  }
425 
426  // If there is only the default destination, just branch.
427  if (!SI->getNumCases()) {
428  BranchInst::Create(Default, CurBlock);
429  SI->eraseFromParent();
430  return;
431  }
432 
433  // Prepare cases vector.
434  CaseVector Cases;
435  unsigned numCmps = Clusterify(Cases, SI);
436  LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size()
437  << ". Total compares: " << numCmps << "\n");
438  LLVM_DEBUG(dbgs() << "Cases: " << Cases << "\n");
439  (void)numCmps;
440 
441  ConstantInt *LowerBound = nullptr;
442  ConstantInt *UpperBound = nullptr;
443  std::vector<IntRange> UnreachableRanges;
444 
445  if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) {
446  // Make the bounds tightly fitted around the case value range, because we
447  // know that the value passed to the switch must be exactly one of the case
448  // values.
449  assert(!Cases.empty());
450  LowerBound = Cases.front().Low;
451  UpperBound = Cases.back().High;
452 
454  unsigned MaxPop = 0;
455  BasicBlock *PopSucc = nullptr;
456 
457  IntRange R = {std::numeric_limits<int64_t>::min(),
459  UnreachableRanges.push_back(R);
460  for (const auto &I : Cases) {
461  int64_t Low = I.Low->getSExtValue();
462  int64_t High = I.High->getSExtValue();
463 
464  IntRange &LastRange = UnreachableRanges.back();
465  if (LastRange.Low == Low) {
466  // There is nothing left of the previous range.
467  UnreachableRanges.pop_back();
468  } else {
469  // Terminate the previous range.
470  assert(Low > LastRange.Low);
471  LastRange.High = Low - 1;
472  }
473  if (High != std::numeric_limits<int64_t>::max()) {
474  IntRange R = { High + 1, std::numeric_limits<int64_t>::max() };
475  UnreachableRanges.push_back(R);
476  }
477 
478  // Count popularity.
479  int64_t N = High - Low + 1;
480  unsigned &Pop = Popularity[I.BB];
481  if ((Pop += N) > MaxPop) {
482  MaxPop = Pop;
483  PopSucc = I.BB;
484  }
485  }
486 #ifndef NDEBUG
487  /* UnreachableRanges should be sorted and the ranges non-adjacent. */
488  for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end();
489  I != E; ++I) {
490  assert(I->Low <= I->High);
491  auto Next = I + 1;
492  if (Next != E) {
493  assert(Next->Low > I->High);
494  }
495  }
496 #endif
497 
498  // Use the most popular block as the new default, reducing the number of
499  // cases.
500  assert(MaxPop > 0 && PopSucc);
501  Default = PopSucc;
502  Cases.erase(
504  Cases, [PopSucc](const CaseRange &R) { return R.BB == PopSucc; }),
505  Cases.end());
506 
507  // If there are no cases left, just branch.
508  if (Cases.empty()) {
509  BranchInst::Create(Default, CurBlock);
510  SI->eraseFromParent();
511  return;
512  }
513  }
514 
515  unsigned NrOfDefaults = (SI->getDefaultDest() == Default) ? 1 : 0;
516  for (const auto &Case : SI->cases())
517  if (Case.getCaseSuccessor() == Default)
518  NrOfDefaults++;
519 
520  // Create a new, empty default block so that the new hierarchy of
521  // if-then statements go to this and the PHI nodes are happy.
522  BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault");
523  F->getBasicBlockList().insert(Default->getIterator(), NewDefault);
524  BranchInst::Create(Default, NewDefault);
525 
526  BasicBlock *SwitchBlock =
527  switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
528  OrigBlock, OrigBlock, NewDefault, UnreachableRanges);
529 
530  // If there are entries in any PHI nodes for the default edge, make sure
531  // to update them as well.
532  fixPhis(Default, OrigBlock, NewDefault, NrOfDefaults);
533 
534  // Branch to our shiny new if-then stuff...
535  BranchInst::Create(SwitchBlock, OrigBlock);
536 
537  // We are now done with the switch instruction, delete it.
538  BasicBlock *OldDefault = SI->getDefaultDest();
539  CurBlock->getInstList().erase(SI);
540 
541  // If the Default block has no more predecessors just add it to DeleteList.
542  if (pred_begin(OldDefault) == pred_end(OldDefault))
543  DeleteList.insert(OldDefault);
544 }
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 push_back(const T &Elt)
Definition: SmallVector.h:213
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:267
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
FunctionPass * createLowerSwitchPass()
iterator end()
Definition: Function.h:644
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1188
Value * getCondition() const
unsigned less or equal
Definition: InstrTypes.h:911
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:713
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:264
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2177
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:237
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:1004
iterator begin()
Definition: Function.h:642
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
const BasicBlock & getEntryBlock() const
Definition: Function.h:626
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:235
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:948
char & LowerSwitchID
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:859
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:329
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:914
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:611
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:133
signed less or equal
Definition: InstrTypes.h:915
void push_back(pointer val)
Definition: ilist.h:313
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2158
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
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:619
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2023
Multiway switch.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT=nullptr)
Delete the specified block, which must have no predecessors.
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:46
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: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:138
#define LLVM_DEBUG(X)
Definition: Debug.h:119
const BasicBlock * getParent() const
Definition: Instruction.h:67
#define LLVM_ATTRIBUTE_USED
Definition: Compiler.h:117