Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SwitchLoweringUtils.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- SwitchLoweringUtils.cpp - Switch Lowering --------------------------===//
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
// This file contains switch inst lowering optimizations and utilities for
10
// codegen, so that it can be used for both SelectionDAG and GlobalISel.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/CodeGen/MachineJumpTableInfo.h"
15
#include "llvm/CodeGen/SwitchLoweringUtils.h"
16
17
using namespace llvm;
18
using namespace SwitchCG;
19
20
uint64_t SwitchCG::getJumpTableRange(const CaseClusterVector &Clusters,
21
29.2k
                                     unsigned First, unsigned Last) {
22
29.2k
  assert(Last >= First);
23
29.2k
  const APInt &LowCase = Clusters[First].Low->getValue();
24
29.2k
  const APInt &HighCase = Clusters[Last].High->getValue();
25
29.2k
  assert(LowCase.getBitWidth() == HighCase.getBitWidth());
26
29.2k
27
29.2k
  // FIXME: A range of consecutive cases has 100% density, but only requires one
28
29.2k
  // comparison to lower. We should discriminate against such consecutive ranges
29
29.2k
  // in jump tables.
30
29.2k
  return (HighCase - LowCase).getLimitedValue((UINT64_MAX - 1) / 100) + 1;
31
29.2k
}
32
33
uint64_t
34
SwitchCG::getJumpTableNumCases(const SmallVectorImpl<unsigned> &TotalCases,
35
29.2k
                               unsigned First, unsigned Last) {
36
29.2k
  assert(Last >= First);
37
29.2k
  assert(TotalCases[Last] >= TotalCases[First]);
38
29.2k
  uint64_t NumCases =
39
29.2k
      TotalCases[Last] - (First == 0 ? 
09.31k
:
TotalCases[First - 1]19.9k
);
40
29.2k
  return NumCases;
41
29.2k
}
42
43
void SwitchCG::SwitchLowering::findJumpTables(CaseClusterVector &Clusters,
44
                                              const SwitchInst *SI,
45
22.6k
                                              MachineBasicBlock *DefaultMBB) {
46
#ifndef NDEBUG
47
  // Clusters must be non-empty, sorted, and only contain Range clusters.
48
  assert(!Clusters.empty());
49
  for (CaseCluster &C : Clusters)
50
    assert(C.Kind == CC_Range);
51
  for (unsigned i = 1, e = Clusters.size(); i < e; ++i)
52
    assert(Clusters[i - 1].High->getValue().slt(Clusters[i].Low->getValue()));
53
#endif
54
55
22.6k
  assert(TLI && "TLI not set!");
56
22.6k
  if (!TLI->areJTsAllowed(SI->getParent()->getParent()))
57
16
    return;
58
22.6k
59
22.6k
  const unsigned MinJumpTableEntries = TLI->getMinimumJumpTableEntries();
60
22.6k
  const unsigned SmallNumberOfEntries = MinJumpTableEntries / 2;
61
22.6k
62
22.6k
  // Bail if not enough cases.
63
22.6k
  const int64_t N = Clusters.size();
64
22.6k
  if (N < 2 || 
N < MinJumpTableEntries22.2k
)
65
17.5k
    return;
66
5.07k
67
5.07k
  // Accumulated number of cases in each cluster and those prior to it.
68
5.07k
  SmallVector<unsigned, 8> TotalCases(N);
69
37.2k
  for (unsigned i = 0; i < N; 
++i32.1k
) {
70
32.1k
    const APInt &Hi = Clusters[i].High->getValue();
71
32.1k
    const APInt &Lo = Clusters[i].Low->getValue();
72
32.1k
    TotalCases[i] = (Hi - Lo).getLimitedValue() + 1;
73
32.1k
    if (i != 0)
74
27.0k
      TotalCases[i] += TotalCases[i - 1];
75
32.1k
  }
76
5.07k
77
5.07k
  uint64_t Range = getJumpTableRange(Clusters,0, N - 1);
78
5.07k
  uint64_t NumCases = getJumpTableNumCases(TotalCases, 0, N - 1);
79
5.07k
  assert(NumCases < UINT64_MAX / 100);
80
5.07k
  assert(Range >= NumCases);
81
5.07k
82
5.07k
  // Cheap case: the whole range may be suitable for jump table.
83
5.07k
  if (TLI->isSuitableForJumpTable(SI, NumCases, Range)) {
84
4.57k
    CaseCluster JTCluster;
85
4.57k
    if (buildJumpTable(Clusters, 0, N - 1, SI, DefaultMBB, JTCluster)) {
86
4.34k
      Clusters[0] = JTCluster;
87
4.34k
      Clusters.resize(1);
88
4.34k
      return;
89
4.34k
    }
90
734
  }
91
734
92
734
  // The algorithm below is not suitable for -O0.
93
734
  if (TM->getOptLevel() == CodeGenOpt::None)
94
20
    return;
95
714
96
714
  // Split Clusters into minimum number of dense partitions. The algorithm uses
97
714
  // the same idea as Kannan & Proebsting "Correction to 'Producing Good Code
98
714
  // for the Case Statement'" (1994), but builds the MinPartitions array in
99
714
  // reverse order to make it easier to reconstruct the partitions in ascending
100
714
  // order. In the choice between two optimal partitionings, it picks the one
101
714
  // which yields more jump tables.
102
714
103
714
  // MinPartitions[i] is the minimum nbr of partitions of Clusters[i..N-1].
104
714
  SmallVector<unsigned, 8> MinPartitions(N);
105
714
  // LastElement[i] is the last element of the partition starting at i.
106
714
  SmallVector<unsigned, 8> LastElement(N);
107
714
  // PartitionsScore[i] is used to break ties when choosing between two
108
714
  // partitionings resulting in the same number of partitions.
109
714
  SmallVector<unsigned, 8> PartitionsScore(N);
110
714
  // For PartitionsScore, a small number of comparisons is considered as good as
111
714
  // a jump table and a single comparison is considered better than a jump
112
714
  // table.
113
714
  enum PartitionScores : unsigned {
114
714
    NoTable = 0,
115
714
    Table = 1,
116
714
    FewCases = 1,
117
714
    SingleCase = 2
118
714
  };
119
714
120
714
  // Base case: There is only one way to partition Clusters[N-1].
121
714
  MinPartitions[N - 1] = 1;
122
714
  LastElement[N - 1] = N - 1;
123
714
  PartitionsScore[N - 1] = PartitionScores::SingleCase;
124
714
125
714
  // Note: loop indexes are signed to avoid underflow.
126
4.94k
  for (int64_t i = N - 2; i >= 0; 
i--4.23k
) {
127
4.23k
    // Find optimal partitioning of Clusters[i..N-1].
128
4.23k
    // Baseline: Put Clusters[i] into a partition on its own.
129
4.23k
    MinPartitions[i] = MinPartitions[i + 1] + 1;
130
4.23k
    LastElement[i] = i;
131
4.23k
    PartitionsScore[i] = PartitionsScore[i + 1] + PartitionScores::SingleCase;
132
4.23k
133
4.23k
    // Search for a solution that results in fewer partitions.
134
28.4k
    for (int64_t j = N - 1; j > i; 
j--24.2k
) {
135
24.2k
      // Try building a partition from Clusters[i..j].
136
24.2k
      Range = getJumpTableRange(Clusters, i, j);
137
24.2k
      NumCases = getJumpTableNumCases(TotalCases, i, j);
138
24.2k
      assert(NumCases < UINT64_MAX / 100);
139
24.2k
      assert(Range >= NumCases);
140
24.2k
141
24.2k
      if (TLI->isSuitableForJumpTable(SI, NumCases, Range)) {
142
13.2k
        unsigned NumPartitions = 1 + (j == N - 1 ? 
01.75k
:
MinPartitions[j + 1]11.5k
);
143
13.2k
        unsigned Score = j == N - 1 ? 
01.75k
:
PartitionsScore[j + 1]11.5k
;
144
13.2k
        int64_t NumEntries = j - i + 1;
145
13.2k
146
13.2k
        if (NumEntries == 1)
147
0
          Score += PartitionScores::SingleCase;
148
13.2k
        else if (NumEntries <= SmallNumberOfEntries)
149
3.06k
          Score += PartitionScores::FewCases;
150
10.1k
        else if (NumEntries >= MinJumpTableEntries)
151
8.07k
          Score += PartitionScores::Table;
152
13.2k
153
13.2k
        // If this leads to fewer partitions, or to the same number of
154
13.2k
        // partitions with better score, it is a better partitioning.
155
13.2k
        if (NumPartitions < MinPartitions[i] ||
156
13.2k
            
(10.2k
NumPartitions == MinPartitions[i]10.2k
&&
Score > PartitionsScore[i]399
)) {
157
2.99k
          MinPartitions[i] = NumPartitions;
158
2.99k
          LastElement[i] = j;
159
2.99k
          PartitionsScore[i] = Score;
160
2.99k
        }
161
13.2k
      }
162
24.2k
    }
163
4.23k
  }
164
714
165
714
  // Iterate over the partitions, replacing some with jump tables in-place.
166
714
  unsigned DstIndex = 0;
167
2.48k
  for (unsigned First = 0, Last; First < N; 
First = Last + 11.77k
) {
168
1.77k
    Last = LastElement[First];
169
1.77k
    assert(Last >= First);
170
1.77k
    assert(DstIndex <= First);
171
1.77k
    unsigned NumClusters = Last - First + 1;
172
1.77k
173
1.77k
    CaseCluster JTCluster;
174
1.77k
    if (NumClusters >= MinJumpTableEntries &&
175
1.77k
        
buildJumpTable(Clusters, First, Last, SI, DefaultMBB, JTCluster)453
) {
176
196
      Clusters[DstIndex++] = JTCluster;
177
1.57k
    } else {
178
4.79k
      for (unsigned I = First; I <= Last; 
++I3.21k
)
179
3.21k
        std::memmove(&Clusters[DstIndex++], &Clusters[I], sizeof(Clusters[I]));
180
1.57k
    }
181
1.77k
  }
182
714
  Clusters.resize(DstIndex);
183
714
}
184
185
bool SwitchCG::SwitchLowering::buildJumpTable(const CaseClusterVector &Clusters,
186
                                              unsigned First, unsigned Last,
187
                                              const SwitchInst *SI,
188
                                              MachineBasicBlock *DefaultMBB,
189
5.02k
                                              CaseCluster &JTCluster) {
190
5.02k
  assert(First <= Last);
191
5.02k
192
5.02k
  auto Prob = BranchProbability::getZero();
193
5.02k
  unsigned NumCmps = 0;
194
5.02k
  std::vector<MachineBasicBlock*> Table;
195
5.02k
  DenseMap<MachineBasicBlock*, BranchProbability> JTProbs;
196
5.02k
197
5.02k
  // Initialize probabilities in JTProbs.
198
36.3k
  for (unsigned I = First; I <= Last; 
++I31.3k
)
199
31.3k
    JTProbs[Clusters[I].MBB] = BranchProbability::getZero();
200
5.02k
201
36.3k
  for (unsigned I = First; I <= Last; 
++I31.3k
) {
202
31.3k
    assert(Clusters[I].Kind == CC_Range);
203
31.3k
    Prob += Clusters[I].Prob;
204
31.3k
    const APInt &Low = Clusters[I].Low->getValue();
205
31.3k
    const APInt &High = Clusters[I].High->getValue();
206
31.3k
    NumCmps += (Low == High) ? 
129.6k
:
21.74k
;
207
31.3k
    if (I != First) {
208
26.3k
      // Fill the gap between this and the previous cluster.
209
26.3k
      const APInt &PreviousHigh = Clusters[I - 1].High->getValue();
210
26.3k
      assert(PreviousHigh.slt(Low));
211
26.3k
      uint64_t Gap = (Low - PreviousHigh).getLimitedValue() - 1;
212
68.8k
      for (uint64_t J = 0; J < Gap; 
J++42.5k
)
213
42.5k
        Table.push_back(DefaultMBB);
214
26.3k
    }
215
31.3k
    uint64_t ClusterSize = (High - Low).getLimitedValue() + 1;
216
66.7k
    for (uint64_t J = 0; J < ClusterSize; 
++J35.3k
)
217
35.3k
      Table.push_back(Clusters[I].MBB);
218
31.3k
    JTProbs[Clusters[I].MBB] += Clusters[I].Prob;
219
31.3k
  }
220
5.02k
221
5.02k
  unsigned NumDests = JTProbs.size();
222
5.02k
  if (TLI->isSuitableForBitTests(NumDests, NumCmps,
223
5.02k
                                 Clusters[First].Low->getValue(),
224
5.02k
                                 Clusters[Last].High->getValue(), *DL)) {
225
487
    // Clusters[First..Last] should be lowered as bit tests instead.
226
487
    return false;
227
487
  }
228
4.53k
229
4.53k
  // Create the MBB that will load from and jump through the table.
230
4.53k
  // Note: We create it here, but it's not inserted into the function yet.
231
4.53k
  MachineFunction *CurMF = FuncInfo.MF;
232
4.53k
  MachineBasicBlock *JumpTableMBB =
233
4.53k
      CurMF->CreateMachineBasicBlock(SI->getParent());
234
4.53k
235
4.53k
  // Add successors. Note: use table order for determinism.
236
4.53k
  SmallPtrSet<MachineBasicBlock *, 8> Done;
237
59.3k
  for (MachineBasicBlock *Succ : Table) {
238
59.3k
    if (Done.count(Succ))
239
31.6k
      continue;
240
27.7k
    addSuccessorWithProb(JumpTableMBB, Succ, JTProbs[Succ]);
241
27.7k
    Done.insert(Succ);
242
27.7k
  }
243
4.53k
  JumpTableMBB->normalizeSuccProbs();
244
4.53k
245
4.53k
  unsigned JTI = CurMF->getOrCreateJumpTableInfo(TLI->getJumpTableEncoding())
246
4.53k
                     ->createJumpTableIndex(Table);
247
4.53k
248
4.53k
  // Set up the jump table info.
249
4.53k
  JumpTable JT(-1U, JTI, JumpTableMBB, nullptr);
250
4.53k
  JumpTableHeader JTH(Clusters[First].Low->getValue(),
251
4.53k
                      Clusters[Last].High->getValue(), SI->getCondition(),
252
4.53k
                      nullptr, false);
253
4.53k
  JTCases.emplace_back(std::move(JTH), std::move(JT));
254
4.53k
255
4.53k
  JTCluster = CaseCluster::jumpTable(Clusters[First].Low, Clusters[Last].High,
256
4.53k
                                     JTCases.size() - 1, Prob);
257
4.53k
  return true;
258
4.53k
}
259
260
void SwitchCG::SwitchLowering::findBitTestClusters(CaseClusterVector &Clusters,
261
7.70k
                                                   const SwitchInst *SI) {
262
7.70k
  // Partition Clusters into as few subsets as possible, where each subset has a
263
7.70k
  // range that fits in a machine word and has <= 3 unique destinations.
264
7.70k
265
#ifndef NDEBUG
266
  // Clusters must be sorted and contain Range or JumpTable clusters.
267
  assert(!Clusters.empty());
268
  assert(Clusters[0].Kind == CC_Range || Clusters[0].Kind == CC_JumpTable);
269
  for (const CaseCluster &C : Clusters)
270
    assert(C.Kind == CC_Range || C.Kind == CC_JumpTable);
271
  for (unsigned i = 1; i < Clusters.size(); ++i)
272
    assert(Clusters[i-1].High->getValue().slt(Clusters[i].Low->getValue()));
273
#endif
274
275
7.70k
  // The algorithm below is not suitable for -O0.
276
7.70k
  if (TM->getOptLevel() == CodeGenOpt::None)
277
43
    return;
278
7.66k
279
7.66k
  // If target does not have legal shift left, do not emit bit tests at all.
280
7.66k
  EVT PTy = TLI->getPointerTy(*DL);
281
7.66k
  if (!TLI->isOperationLegal(ISD::SHL, PTy))
282
2
    return;
283
7.65k
284
7.65k
  int BitWidth = PTy.getSizeInBits();
285
7.65k
  const int64_t N = Clusters.size();
286
7.65k
287
7.65k
  // MinPartitions[i] is the minimum nbr of partitions of Clusters[i..N-1].
288
7.65k
  SmallVector<unsigned, 8> MinPartitions(N);
289
7.65k
  // LastElement[i] is the last element of the partition starting at i.
290
7.65k
  SmallVector<unsigned, 8> LastElement(N);
291
7.65k
292
7.65k
  // FIXME: This might not be the best algorithm for finding bit test clusters.
293
7.65k
294
7.65k
  // Base case: There is only one way to partition Clusters[N-1].
295
7.65k
  MinPartitions[N - 1] = 1;
296
7.65k
  LastElement[N - 1] = N - 1;
297
7.65k
298
7.65k
  // Note: loop indexes are signed to avoid underflow.
299
14.1k
  for (int64_t i = N - 2; i >= 0; 
--i6.49k
) {
300
6.49k
    // Find optimal partitioning of Clusters[i..N-1].
301
6.49k
    // Baseline: Put Clusters[i] into a partition on its own.
302
6.49k
    MinPartitions[i] = MinPartitions[i + 1] + 1;
303
6.49k
    LastElement[i] = i;
304
6.49k
305
6.49k
    // Search for a solution that results in fewer partitions.
306
6.49k
    // Note: the search is limited by BitWidth, reducing time complexity.
307
16.1k
    for (int64_t j = std::min(N - 1, i + BitWidth - 1); j > i; 
--j9.66k
) {
308
9.74k
      // Try building a partition from Clusters[i..j].
309
9.74k
310
9.74k
      // Check the range.
311
9.74k
      if (!TLI->rangeFitsInWord(Clusters[i].Low->getValue(),
312
9.74k
                                Clusters[j].High->getValue(), *DL))
313
1.95k
        continue;
314
7.79k
315
7.79k
      // Check nbr of destinations and cluster types.
316
7.79k
      // FIXME: This works, but doesn't seem very efficient.
317
7.79k
      bool RangesOnly = true;
318
7.79k
      BitVector Dests(FuncInfo.MF->getNumBlockIDs());
319
26.8k
      for (int64_t k = i; k <= j; 
k++19.0k
) {
320
19.0k
        if (Clusters[k].Kind != CC_Range) {
321
32
          RangesOnly = false;
322
32
          break;
323
32
        }
324
19.0k
        Dests.set(Clusters[k].MBB->getNumber());
325
19.0k
      }
326
7.79k
      if (!RangesOnly || 
Dests.count() > 37.76k
)
327
84
        break;
328
7.71k
329
7.71k
      // Check if it's a better partition.
330
7.71k
      unsigned NumPartitions = 1 + (j == N - 1 ? 
05.73k
:
MinPartitions[j + 1]1.98k
);
331
7.71k
      if (NumPartitions < MinPartitions[i]) {
332
5.84k
        // Found a better partition.
333
5.84k
        MinPartitions[i] = NumPartitions;
334
5.84k
        LastElement[i] = j;
335
5.84k
      }
336
7.71k
    }
337
6.49k
  }
338
7.65k
339
7.65k
  // Iterate over the partitions, replacing with bit-test clusters in-place.
340
7.65k
  unsigned DstIndex = 0;
341
15.9k
  for (unsigned First = 0, Last; First < N; 
First = Last + 18.30k
) {
342
8.30k
    Last = LastElement[First];
343
8.30k
    assert(First <= Last);
344
8.30k
    assert(DstIndex <= First);
345
8.30k
346
8.30k
    CaseCluster BitTestCluster;
347
8.30k
    if (buildBitTests(Clusters, First, Last, SI, BitTestCluster)) {
348
286
      Clusters[DstIndex++] = BitTestCluster;
349
8.02k
    } else {
350
8.02k
      size_t NumClusters = Last - First + 1;
351
8.02k
      std::memmove(&Clusters[DstIndex], &Clusters[First],
352
8.02k
                   sizeof(Clusters[0]) * NumClusters);
353
8.02k
      DstIndex += NumClusters;
354
8.02k
    }
355
8.30k
  }
356
7.65k
  Clusters.resize(DstIndex);
357
7.65k
}
358
359
bool SwitchCG::SwitchLowering::buildBitTests(CaseClusterVector &Clusters,
360
                                             unsigned First, unsigned Last,
361
                                             const SwitchInst *SI,
362
8.30k
                                             CaseCluster &BTCluster) {
363
8.30k
  assert(First <= Last);
364
8.30k
  if (First == Last)
365
3.44k
    return false;
366
4.86k
367
4.86k
  BitVector Dests(FuncInfo.MF->getNumBlockIDs());
368
4.86k
  unsigned NumCmps = 0;
369
15.5k
  for (int64_t I = First; I <= Last; 
++I10.7k
) {
370
10.7k
    assert(Clusters[I].Kind == CC_Range);
371
10.7k
    Dests.set(Clusters[I].MBB->getNumber());
372
10.7k
    NumCmps += (Clusters[I].Low == Clusters[I].High) ? 
110.3k
:
2348
;
373
10.7k
  }
374
4.86k
  unsigned NumDests = Dests.count();
375
4.86k
376
4.86k
  APInt Low = Clusters[First].Low->getValue();
377
4.86k
  APInt High = Clusters[Last].High->getValue();
378
4.86k
  assert(Low.slt(High));
379
4.86k
380
4.86k
  if (!TLI->isSuitableForBitTests(NumDests, NumCmps, Low, High, *DL))
381
4.57k
    return false;
382
286
383
286
  APInt LowBound;
384
286
  APInt CmpRange;
385
286
386
286
  const int BitWidth = TLI->getPointerTy(*DL).getSizeInBits();
387
286
  assert(TLI->rangeFitsInWord(Low, High, *DL) &&
388
286
         "Case range must fit in bit mask!");
389
286
390
286
  // Check if the clusters cover a contiguous range such that no value in the
391
286
  // range will jump to the default statement.
392
286
  bool ContiguousRange = true;
393
419
  for (int64_t I = First + 1; I <= Last; 
++I133
) {
394
382
    if (Clusters[I].Low->getValue() != Clusters[I - 1].High->getValue() + 1) {
395
249
      ContiguousRange = false;
396
249
      break;
397
249
    }
398
382
  }
399
286
400
286
  if (Low.isStrictlyPositive() && 
High.slt(BitWidth)100
) {
401
52
    // Optimize the case where all the case values fit in a word without having
402
52
    // to subtract minValue. In this case, we can optimize away the subtraction.
403
52
    LowBound = APInt::getNullValue(Low.getBitWidth());
404
52
    CmpRange = High;
405
52
    ContiguousRange = false;
406
234
  } else {
407
234
    LowBound = Low;
408
234
    CmpRange = High - Low;
409
234
  }
410
286
411
286
  CaseBitsVector CBV;
412
286
  auto TotalProb = BranchProbability::getZero();
413
1.50k
  for (unsigned i = First; i <= Last; 
++i1.21k
) {
414
1.21k
    // Find the CaseBits for this destination.
415
1.21k
    unsigned j;
416
1.67k
    for (j = 0; j < CBV.size(); 
++j460
)
417
1.23k
      if (CBV[j].BB == Clusters[i].MBB)
418
772
        break;
419
1.21k
    if (j == CBV.size())
420
447
      CBV.push_back(
421
447
          CaseBits(0, Clusters[i].MBB, 0, BranchProbability::getZero()));
422
1.21k
    CaseBits *CB = &CBV[j];
423
1.21k
424
1.21k
    // Update Mask, Bits and ExtraProb.
425
1.21k
    uint64_t Lo = (Clusters[i].Low->getValue() - LowBound).getZExtValue();
426
1.21k
    uint64_t Hi = (Clusters[i].High->getValue() - LowBound).getZExtValue();
427
1.21k
    assert(Hi >= Lo && Hi < 64 && "Invalid bit case!");
428
1.21k
    CB->Mask |= (-1ULL >> (63 - (Hi - Lo))) << Lo;
429
1.21k
    CB->Bits += Hi - Lo + 1;
430
1.21k
    CB->ExtraProb += Clusters[i].Prob;
431
1.21k
    TotalProb += Clusters[i].Prob;
432
1.21k
  }
433
286
434
286
  BitTestInfo BTI;
435
286
  llvm::sort(CBV, [](const CaseBits &a, const CaseBits &b) {
436
196
    // Sort by probability first, number of bits second, bit mask third.
437
196
    if (a.ExtraProb != b.ExtraProb)
438
155
      return a.ExtraProb > b.ExtraProb;
439
41
    if (a.Bits != b.Bits)
440
0
      return a.Bits > b.Bits;
441
41
    return a.Mask < b.Mask;
442
41
  });
443
286
444
447
  for (auto &CB : CBV) {
445
447
    MachineBasicBlock *BitTestBB =
446
447
        FuncInfo.MF->CreateMachineBasicBlock(SI->getParent());
447
447
    BTI.push_back(BitTestCase(CB.Mask, BitTestBB, CB.BB, CB.ExtraProb));
448
447
  }
449
286
  BitTestCases.emplace_back(std::move(LowBound), std::move(CmpRange),
450
286
                            SI->getCondition(), -1U, MVT::Other, false,
451
286
                            ContiguousRange, nullptr, nullptr, std::move(BTI),
452
286
                            TotalProb);
453
286
454
286
  BTCluster = CaseCluster::bitTests(Clusters[First].Low, Clusters[Last].High,
455
286
                                    BitTestCases.size() - 1, TotalProb);
456
286
  return true;
457
286
}
458
459
22.6k
void SwitchCG::sortAndRangeify(CaseClusterVector &Clusters) {
460
#ifndef NDEBUG
461
  for (const CaseCluster &CC : Clusters)
462
    assert(CC.Low == CC.High && "Input clusters must be single-case");
463
#endif
464
465
113k
  llvm::sort(Clusters, [](const CaseCluster &a, const CaseCluster &b) {
466
113k
    return a.Low->getValue().slt(b.Low->getValue());
467
113k
  });
468
22.6k
469
22.6k
  // Merge adjacent clusters with the same destination.
470
22.6k
  const unsigned N = Clusters.size();
471
22.6k
  unsigned DstIndex = 0;
472
97.5k
  for (unsigned SrcIndex = 0; SrcIndex < N; 
++SrcIndex74.8k
) {
473
74.8k
    CaseCluster &CC = Clusters[SrcIndex];
474
74.8k
    const ConstantInt *CaseVal = CC.Low;
475
74.8k
    MachineBasicBlock *Succ = CC.MBB;
476
74.8k
477
74.8k
    if (DstIndex != 0 && 
Clusters[DstIndex - 1].MBB == Succ52.1k
&&
478
74.8k
        
(CaseVal->getValue() - Clusters[DstIndex - 1].High->getValue()) == 113.9k
) {
479
4.85k
      // If this case has the same successor and is a neighbour, merge it into
480
4.85k
      // the previous cluster.
481
4.85k
      Clusters[DstIndex - 1].High = CaseVal;
482
4.85k
      Clusters[DstIndex - 1].Prob += CC.Prob;
483
70.0k
    } else {
484
70.0k
      std::memmove(&Clusters[DstIndex++], &Clusters[SrcIndex],
485
70.0k
                   sizeof(Clusters[SrcIndex]));
486
70.0k
    }
487
74.8k
  }
488
22.6k
  Clusters.resize(DstIndex);
489
22.6k
}