Coverage Report

Created: 2017-10-03 07:32

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