[SimplifyCFG] Range reduce switches

[jmolloy]

Summary

If a switch is sparse and all the cases (once sorted) are in arithmetic progression, we can extract the common factor out of the switch and create a dense switch. For example:

switch (i) {
case 5: ...
case 9: ...
case 13: ...
case 17: ...
}

can become:

if ( (i - 5) % 4 ) goto default;
switch ((i - 5) / 4) {
case 0: ...
case 1: ...
case 2: ...
case 3: ...
}

The division and remainder operations could be costly so we only do this if the factor is a power of two. Dense switches can be lowered significantly better than sparse switches and can even be transformed into lookup tables.

[sbaranga]

lib/Transforms/Utils/SimplifyCFG.cpp

4993 ↗

(On Diff #60524)

Could you also add a test for this case?

5009 ↗

(On Diff #60524)

If it doesn't have holes then the GCD that you are looking for should be Values[1].

[jmolloy]

Hi Silviu,

Thanks for the review!

James

lib/Transforms/Utils/SimplifyCFG.cpp

4993 ↗

(On Diff #60542)

This should be @test3

5009 ↗

(On Diff #60542)

Uhhhhh, yes. Yes it should. Thanks for spotting this!

I've rewritten the code entirely.

[sanjoy]

lib/Transforms/Utils/SimplifyCFG.cpp

4989 ↗

(On Diff #60542)

I'd prefer a getZExtValue or getSExtValue here. That way the code will assert if someone later accidentally removed the check on the bit width.

4992 ↗

(On Diff #60542)

How about {-2, 0, 2, 4}? That's sparse and can benefit from this pass, but here you'll conclude that it has no holes.

5006 ↗

(On Diff #60542)

Don't you need to check that V is divisible by Divisor here?

5007 ↗

(On Diff #60542)

Might be worth calling out the signedness of the division here explicitly. I'd mildly prefer bitwise ops instead of division.

5017 ↗

(On Diff #60542)

I'd be tempted to emit the bitwise ops here directly. That way you don't do extra work later and are less sensitive to pass ordering.

[sanjoy]

lib/Transforms/Utils/SimplifyCFG.cpp

4992 ↗

(On Diff #60542)

Bad example, I meant cases like {-3, -1, 1, 3}.

[eli.friedman]

Maybe it makes sense to perform this sort of transformation in SelectionDAGBuilder::visitSwitch instead? Most of the relevant logic is there.

This patch only handles situations where all the values form a linear series, but it seems important to also catch cases where *most* of the values form a linear series (for example, 97, 105, 109, 113, 117, 121).

I think your profitability model is a bit off: we never generate a jump table for less than four cases, so trying to improve the density of a nonexistent jump table seems like a bad idea. And for cases where the divisor is small, the tradeoff between extra jump table entries and an extra compare+branch isn't obvious.

[jmolloy]

Hi Sanjoy and Eli,

Thanks for your reviews. I agree with all of your comments. This new version has a real density function and will perform the optimization if the switch is not dense to begin with and would be made dense. The density function is adapted from SelectionDAGBuilder, and I'm not too happy on replicating the heuristic here but I couldn't think of a better way.

Similarly the hardcoded bailout for < 4 cases - ideally I'd use TargetLowering here which has a hook, but we only have TTI. It might be worth adding a hook, but perhaps it's not so urgent so I've added a FIXME.

Eli, the reason I'm doing this in SimplifyCFG is because it's an enabler for switch->lookup table lowering (which is also in SimplifyCFG).

The testing has also been improved to cover more negative and unsigned large values and wraparound cases.

Cheers,

James

[eli.friedman]

lib/Transforms/Utils/SimplifyCFG.cpp

5022 ↗

(On Diff #60817)

Nit: please make the implicit casting here explicit.

5031 ↗

(On Diff #60817)

If the GCD is some odd number N, you can multiply by the inverse of N and switch on that. Not sure if that's actually useful in practice.

5056 ↗

(On Diff #60817)

If we were doing this in SelectionDAG, we would be able to combine this branch with the jump table's bounds check: "ROTATE(X - Base, Shift) > Limit".

[sanjoy]

Haven't done a thorough review yet, but some minor nitpicky comments inline.

lib/Transforms/Utils/SimplifyCFG.cpp

5029 ↗

(On Diff #60817)

This gcd computation looks like extra work -- why not:

uint64_t PotentialGCD = Values[1];
if (!isPowerOf2(PotentialGCD)) return false;
if (!all_of(Values, [](uint64_t V) { return V & (PotentialGCD - 1) == 0; }) return false;

5072 ↗

(On Diff #60817)

This linear search (via replaceUsesOfWith) seems wasteful. Why not change getCaseValue to return a Use & and do C.getCaseValue().set(New) or something similar?

[jmolloy]

lib/Transforms/Utils/SimplifyCFG.cpp

5056 ↗

(On Diff #60817)

Hmm, you're close to convincing me. I'm loath to give up the lookup table optimization though.

How gross (/ acceptable) would it be to implement this in SelectionDAG and then also teach lookup table lowering in SimplifyCFG this trick too?

[eli.friedman]

lib/Transforms/Utils/SimplifyCFG.cpp

5029 ↗

(On Diff #60817)

That isn't equivalent for something like "0, 8, 12, 16, 20".

5056 ↗

(On Diff #60817)

It wouldn't be too terrible as long as the actual algorithm for finding a reducible switch is factored out into a utility, I think.

[sanjoy]

lib/Transforms/Utils/SimplifyCFG.cpp

5029 ↗

(On Diff #60817)

Yeah, you're right. I was still thinking in terms of the older "100% dense" scheme.

[jmolloy]

Hi Eli,

That rotate trick is, quite simply, brilliant.

New version uses SelectionDAG - I'll factor some of the machinery out at a later date when I implement this for lookup table formation too.

All comments should now be addressed.

Cheers,

James

[eli.friedman]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8332

Do we need to merge clusters in some cases, so we don't end up with adjacent clusters with the same destination? (This doesn't affect building a jump table, but it affects isDense.)

Hmm... actually, more generally, whether we transform a switch condition is to some extent independent of whether we form a jump table; for example, if we end up with one cluster here, you don't need a jump table at all. Maybe we can leave that for a followup, though.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

267

It's unintuitive to hide this in the constructor... it seems like a good idea to push the Shift == 0 special-case out.

[hans]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1971

I was going to comment that the code in the patch summary could use rotation instead, but it seems you're already on it :-)

8434

This code doesn't take into account that a range of cases could be transformed to become dense, so I'm not sure your patch will actually find any more jump table lowerings that don't cover the whole switch?

[hans]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8434

I guess what I was saying with this comment is that since you're not going to get the benefit of transforming parts of the switch, it there a point in doing this in the DAG instead of in the IR? I think the rotation trick should work in the IR too..

[eli.friedman]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8434

Err, I guess the rotation trick works in IR? You can let switch lowering do the compare+branch. Not sure what I was thinking before.

That said, we don't really want to do switch lowering in IR. I mean, in theory, we can lower switches in IR, but we want to do all of switch lowering at the same time. Otherwise, you end up with weird guessing games to predict what SelectionDAG will actually do.

[jmolloy]

Hi guys,

Thanks for the comments. I was away on vacation for 2 weeks which is why this has been sitting around.

Hans, if you're OK with it being done in DAG for the reasons mentioned, is this good to commit?

Cheers,

James

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8434

I agree with Eli here. It'd be nice to densify individual switch case ranges, and perhaps we could do that in the future?

The main advantage I got from moving from IR to SDAG for this is the heuristics don't need second-guessing, which was a major improvement. Doing this in IR would give one large advantage - it'd allow the switch table lookup lowering to work too. I intend to implement this directly in the switch table lookup lowering code though, which should be fairly simple.

[jmolloy]

Hi Hans, Sanjoy,

Ping! :) Are you now happy with this?

Cheers,

James

[jmolloy]

Ping!

[hans]

The code seems fine to me. I'm OK with this landing.

I still wonder if we shouldn't just do this in SimplifyCFG though. How big is the pay-off here? I've seen switches with e.g. a common factor of 10 in the cases, but are powers of 2 common enough to justify the complexity, especially if we start looking at densifying only parts of a switch?

I just imagine that doing this in SimplifyCFG instead would be so much simpler: we'd look for a common power-of-two factor and slap a rotate-right operation in front of the switch. This could potentially allow more lookup tables, jump tables, bit-test lowerings, new adjacent cases, who knows -- one could argue that densifying the switch is just general goodness, and if it doesn't pay off it's just an extra rotate which is cheap.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8389

This comment refers to the algorithm that finds dense partitions in Clusters, which is O(n^2). Now that there's more stuff happening below, maybe update it to "don't try any harder at -O0", or you could jsut move your code before it, since I don't think it would be a problem running it a -O0.

[jmolloy]

Hi Hans,

I do agree with you. I think that the major reason I moved from SimplifyCFG to SDAGBuilder was that, because we were inserting new CFG edges, we didn't want to do this unless we could be *sure* that a dense switch lowering was used.

However now we've used the rotate trick, the inserted code is so tiny that we don't have to be so conservative. So I think it's OK to replicate the density heuristic in SimplifyCFG and that's what I've done.

I hope this is now more acceptable to you? :)

Cheers,

James

[hans]

Thanks, I like this :-) Just some nits.

lib/Transforms/Utils/SimplifyCFG.cpp

5044 ↗

(On Diff #65900)

Aren't Values sorted (from line 5081), so this should be unnecessary?

5067 ↗

(On Diff #65900)

Maybe we should check DL.fitsInLegalInteger() instead of hard-coding 64 here.

Oh I see, 64 is because we use [u]int64_t below. It might still be a good idea to check fitsInLegalInteger() so we're not creating a non-legal rotate operation.

5088 ↗

(On Diff #65900)

why isn't Base int64_t already? Also, could the subtraction overflow?

5106 ↗

(On Diff #65900)

Any bijective transformation of the case values will work. The problem is just deciding when they're profitable, I suppose. But I'm all for more creative switch lowerings :-)

[jmolloy]

Thanks Hans!

New version - hopefully this one should be ready to go?

Cheers,

James

lib/Transforms/Utils/SimplifyCFG.cpp

5088 ↗

(On Diff #65900)

I don't think overflow is possible. The subtraction moves values towards zero; the only way I can consider it overflowing is if the difference between the smallest value and the largest value is INT64_MAX or greater which is impossible.

5106 ↗

(On Diff #65900)

:)

[hans]

lgtm

[jmolloy]

This was committed with Hans' LGTM.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

struct JumpTable {
     /// MBB - the MBB into which to emit the code for the indirect jump.
     MachineBasicBlock *MBB;
     /// Default - the MBB of the default bb, which is a successor of the range
     /// check MBB.  This is when updating PHI nodes in successors.
     MachineBasicBlock *Default;
   };
   struct JumpTableHeader {
     JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H,
-                    bool E = false):
-      First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {}
+                    bool E, APInt Base, unsigned Shift)
+        : First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E), Base(Base),
+          Shift(Shift) {
+      if (Shift == 0)
+        this->Base = First;
+    }
     APInt First;
     APInt Last;
     const Value *SValue;
     MachineBasicBlock *HeaderBB;
     bool Emitted;
+    APInt Base;
+    unsigned Shift;
   };
   typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock;
 
   struct BitTestCase {
     BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr,
                 BranchProbability Prob):
       Mask(M), ThisBB(T), TargetBB(Tr), ExtraProb(Prob) { }
     uint64_t Mask;
private:
   /// Check whether a range of clusters is dense enough for a jump table.
   bool isDense(const CaseClusterVector &Clusters, unsigned *TotalCases,
                unsigned First, unsigned Last, unsigned MinDensity);
 
   /// Build a jump table cluster from Clusters[First..Last]. Returns false if it
   /// decides it's not a good idea.
   bool buildJumpTable(CaseClusterVector &Clusters, unsigned First,
                       unsigned Last, const SwitchInst *SI,
-                      MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster);
+                      MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster,
+                      uint64_t Base, unsigned Shift);
+
+  /// If possible, try and factorize out a power of two from each case value
+  /// and construct a jump table from SI->getCondition() >> Shift.
+  /// Return false if this isn't possible or isn't a good idea.
+  bool buildShiftedJumpTable(CaseClusterVector &Clusters, unsigned *TotalCases,
+                             unsigned Density, const SwitchInst *SI,
+                             MachineBasicBlock *DefaultMBB,
+                             CaseCluster &JTCluster);
 
   /// Find clusters of cases suitable for jump table lowering.
   void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI,
                       MachineBasicBlock *DefaultMBB);
 
   /// Check whether the range [Low,High] fits in a machine word.
   bool rangeFitsInWord(const APInt &Low, const APInt &High);
 

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 }
 
 /// visitJumpTableHeader - This function emits necessary code to produce index
 /// in the JumpTable from switch case.
 void SelectionDAGBuilder::visitJumpTableHeader(JumpTable &JT,
                                                JumpTableHeader &JTH,
                                                MachineBasicBlock *SwitchBB) {
   SDLoc dl = getCurSDLoc();
-
   // Subtract the lowest switch case value from the value being switched on and
   // conditional branch to default mbb if the result is greater than the
   // difference between smallest and largest cases.
   SDValue SwitchOp = getValue(JTH.SValue);
   EVT VT = SwitchOp.getValueType();
   SDValue Sub = DAG.getNode(ISD::SUB, dl, VT, SwitchOp,
-                            DAG.getConstant(JTH.First, dl, VT));
+                            DAG.getConstant(JTH.Base, dl, VT));
+  if (JTH.Shift != 0) {
+    // We need to shift the subtracted value right before calculating the jump
+    // index. This is equivalent to dividing by 2**Shift. We also need to ensure
+    // that the subtracted value divides cleanly by 2**Shift. This can be folded
+    // into the jump table bounds check by rotating the subtracted value right:
+    //
+    //   Idx = rotr(Sub, Shift)
+    //
+    // If any of the low bits of Sub are set, these become high bits and so the
+    // table index comparison will fail.
+    Sub =
+        DAG.getNode(ISD::ROTR, dl, VT, Sub, DAG.getConstant(JTH.Shift, dl, VT));
+  }
 
   // The SDNode we just created, which holds the value being switched on minus
   // the smallest case value, needs to be copied to a virtual register so it
   // can be used as an index into the jump table in a subsequent basic block.
   // This value may be smaller or larger than the target's pointer type, and
   // therefore require extension or truncating.
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   SwitchOp = DAG.getZExtOrTrunc(Sub, dl, TLI.getPointerTy(DAG.getDataLayout()));
void SelectionDAGBuilder::visitLandingPad(const LandingPadInst &LP) {
   setValue(&LP, Res);
 }
 
 void SelectionDAGBuilder::sortAndRangeify(CaseClusterVector &Clusters) {
 #ifndef NDEBUG
   for (const CaseCluster &CC : Clusters)
     assert(CC.Low == CC.High && "Input clusters must be single-case");
 #endif
-
   std::sort(Clusters.begin(), Clusters.end(),
             [](const CaseCluster &a, const CaseCluster &b) {
     return a.Low->getValue().slt(b.Low->getValue());
   });
 
   // Merge adjacent clusters with the same destination.
   const unsigned N = Clusters.size();
   unsigned DstIndex = 0;
static inline bool areJTsAllowed(const TargetLowering &TLI,
   return TLI.isOperationLegalOrCustom(ISD::BR_JT, MVT::Other) ||
          TLI.isOperationLegalOrCustom(ISD::BRIND, MVT::Other);
 }
 
 bool SelectionDAGBuilder::buildJumpTable(CaseClusterVector &Clusters,
                                          unsigned First, unsigned Last,
                                          const SwitchInst *SI,
                                          MachineBasicBlock *DefaultMBB,
-                                         CaseCluster &JTCluster) {
+                                         CaseCluster &JTCluster,
+                                         uint64_t Base, unsigned Shift) {
   assert(First <= Last);
 
   auto Prob = BranchProbability::getZero();
   unsigned NumCmps = 0;
   std::vector<MachineBasicBlock*> Table;
   DenseMap<MachineBasicBlock*, BranchProbability> JTProbs;
 
   // Initialize probabilities in JTProbs.
bool SelectionDAGBuilder::buildJumpTable(CaseClusterVector &Clusters,
   }
   JumpTableMBB->normalizeSuccProbs();
 
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   unsigned JTI = CurMF->getOrCreateJumpTableInfo(TLI.getJumpTableEncoding())
                      ->createJumpTableIndex(Table);
 
   // Set up the jump table info.
+  auto BW = Clusters[First].Low->getValue().getBitWidth();
   JumpTable JT(-1U, JTI, JumpTableMBB, nullptr);
   JumpTableHeader JTH(Clusters[First].Low->getValue(),
                       Clusters[Last].High->getValue(), SI->getCondition(),
-                      nullptr, false);
+                      nullptr, false, APInt(BW, Base), Shift);
   JTCases.emplace_back(std::move(JTH), std::move(JT));
-
   JTCluster = CaseCluster::jumpTable(Clusters[First].Low, Clusters[Last].High,
                                      JTCases.size() - 1, Prob);
   return true;
 }
 
+bool SelectionDAGBuilder::buildShiftedJumpTable(CaseClusterVector &Clusters,
+                                                unsigned *TotalCases,
+                                                unsigned Density,
+                                                const SwitchInst *SI,
+                                                MachineBasicBlock *DefaultMBB,
+                                                CaseCluster &JTCluster) {
+  auto BW = Clusters[0].High->getValue().getBitWidth();
+  if (BW > 64)
+    return false;
+  // This transform is agnostic to the signedness of the input or case values. We
+  // can treat the case values as signed or unsigned. We can optimize more common
+  // cases such as a sequence crossing zero {-4,0,4,8} if we interpret case values
+  // as signed.
+  SmallVector<int64_t,4> Values;
+  for (auto &C : Clusters) {
+    if (C.High != C.Low)
+      // Consecutive values mean the greatest common divisor is one.
+      return false;
+    Values.push_back(C.High->getValue().getSExtValue());
+  }
+
+  // First, transform the values such that they start at zero and ascend.
+  uint64_t Base = Values[0];
+  for (auto &V : Values)
+    V -= (int64_t)Base;
+
+  // Now we have signed numbers that have been shifted so that, given enough
+  // precision, there are no negative values. Since the rest of the transform
+  // is bitwise only, we switch now to an unsigned representation.
+  uint64_t GCD = 0;
+  for (auto &V : Values)
+    GCD = llvm::GreatestCommonDivisor64(GCD, (uint64_t)V);
+  if (GCD <= 1 || !llvm::isPowerOf2_64(GCD))
+    return false;
+  unsigned Shift = llvm::Log2_64(GCD);
+
+  auto XFormedClusters = Clusters;
+  for (auto &C : XFormedClusters) {
+    auto *CI = ConstantInt::get(C.High->getType(),
+                                C.High->getValue().lshr(Shift));
+    C.Low = C.High = cast<ConstantInt>(CI);
+  }
+
+  if (!isDense(XFormedClusters, &TotalCases[0], 0, Clusters.size() - 1,
+               Density))
+    // Transform didn't create a dense switch.
+    return false;
+
+  return buildJumpTable(XFormedClusters, 0, Clusters.size() - 1, SI, DefaultMBB,
+                        JTCluster, Base, Shift);
+}
+
 void SelectionDAGBuilder::findJumpTables(CaseClusterVector &Clusters,
                                          const SwitchInst *SI,
                                          MachineBasicBlock *DefaultMBB) {
 #ifndef NDEBUG
   // Clusters must be non-empty, sorted, and only contain Range clusters.
   assert(!Clusters.empty());
   for (CaseCluster &C : Clusters)
     assert(C.Kind == CC_Range);
   for (unsigned i = 1, e = Clusters.size(); i < e; ++i)
     assert(Clusters[i - 1].High->getValue().slt(Clusters[i].Low->getValue()));
 #endif
 
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   if (!areJTsAllowed(TLI, SI))
     return;
 
   const int64_t N = Clusters.size();
   const unsigned MinJumpTableSize = TLI.getMinimumJumpTableEntries();
+  if (N < MinJumpTableSize)
+    return;
 
   // TotalCases[i]: Total nbr of cases in Clusters[0..i].
   SmallVector<unsigned, 8> TotalCases(N);
 
   for (unsigned i = 0; i < N; ++i) {
     APInt Hi = Clusters[i].High->getValue();
     APInt Lo = Clusters[i].Low->getValue();
     TotalCases[i] = (Hi - Lo).getLimitedValue() + 1;
     if (i != 0)
       TotalCases[i] += TotalCases[i - 1];
   }
 
   unsigned MinDensity = JumpTableDensity;
   if (DefaultMBB->getParent()->getFunction()->optForSize())
     MinDensity = OptsizeJumpTableDensity;
-  if (N >= MinJumpTableSize
-      && isDense(Clusters, &TotalCases[0], 0, N - 1, MinDensity)) {
+  if (isDense(Clusters, &TotalCases[0], 0, N - 1, MinDensity)) {
     // Cheap case: the whole range might be suitable for jump table.
     CaseCluster JTCluster;
-    if (buildJumpTable(Clusters, 0, N - 1, SI, DefaultMBB, JTCluster)) {
+    if (buildJumpTable(Clusters, 0, N - 1, SI, DefaultMBB, JTCluster, 0, 0)) {
       Clusters[0] = JTCluster;
       Clusters.resize(1);
       return;
     }
   }
 
   // The algorithm below is not suitable for -O0.
   if (TM.getOptLevel() == CodeGenOpt::None)
     return;
 
+  // If the cases are in arithmetic progression, we may be able to factorize
+  // to make the table dense.
+  CaseCluster JTCluster;
+  if (buildShiftedJumpTable(Clusters, &TotalCases[0], MinDensity, SI, DefaultMBB,
+                            JTCluster)) {
+    Clusters[0] = JTCluster;
+    Clusters.resize(1);
+    return;
+  }
+
   // Split Clusters into minimum number of dense partitions. The algorithm uses
   // the same idea as Kannan & Proebsting "Correction to 'Producing Good Code
   // for the Case Statement'" (1994), but builds the MinPartitions array in
   // reverse order to make it easier to reconstruct the partitions in ascending
   // order. In the choice between two optimal partitionings, it picks the one
   // which yields more jump tables.
 
   // MinPartitions[i] is the minimum nbr of partitions of Clusters[i..N-1].
for (int64_t i = N - 2; i >= 0; i--) {
     // Baseline: Put Clusters[i] into a partition on its own.
     MinPartitions[i] = MinPartitions[i + 1] + 1;
     LastElement[i] = i;
     NumTables[i] = NumTables[i + 1];
 
     // Search for a solution that results in fewer partitions.
     for (int64_t j = N - 1; j > i; j--) {
       // Try building a partition from Clusters[i..j].
       if (isDense(Clusters, &TotalCases[0], i, j, MinDensity)) {
         unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]);
         bool IsTable = j - i + 1 >= MinJumpTableSize;
         unsigned Tables = IsTable + (j == N - 1 ? 0 : NumTables[j + 1]);
 
         // If this j leads to fewer partitions, or same number of partitions
         // with more lookup tables, it is a better partitioning.
         if (NumPartitions < MinPartitions[i] ||
             (NumPartitions == MinPartitions[i] && Tables > NumTables[i])) {
#endif
   for (unsigned First = 0, Last; First < N; First = Last + 1) {
     Last = LastElement[First];
     assert(Last >= First);
     assert(DstIndex <= First);
     unsigned NumClusters = Last - First + 1;
 
     CaseCluster JTCluster;
     if (NumClusters >= MinJumpTableSize &&
-        buildJumpTable(Clusters, First, Last, SI, DefaultMBB, JTCluster)) {
+        buildJumpTable(Clusters, First, Last, SI, DefaultMBB, JTCluster, 0, 0)) {
       Clusters[DstIndex++] = JTCluster;
     } else {
       for (unsigned I = First; I <= Last; ++I)
         std::memmove(&Clusters[DstIndex++], &Clusters[I], sizeof(Clusters[I]));
     }
   }
   Clusters.resize(DstIndex);
 }

test/CodeGen/ARM/rangereduce-switch.ll

+; RUN: llc -mtriple=thumbv7-linux-gnu < %s -stop-after machine-cp -o /dev/null 2>&1 | FileCheck %s
+
+; CHECK-LABEL: name: test1
+; CHECK: %[[x:.*]] = t2SUBri killed %r0, 97
+; CHECK: %[[y:.*]] = t2RORri killed %[[x]], 2
+; CHECK: t2CMPri %[[y]], 3
+; CHECK: t2Bcc
+; CHECK: t2BR_JT
+define i32 @test1(i32 %a) optsize {
+  switch i32 %a, label %def [
+    i32 97, label %one
+    i32 101, label %two
+    i32 105, label %three
+    i32 109, label %three
+  ]
+
+def:
+  ret i32 8867
+
+one:
+  ret i32 11984
+two:
+  ret i32 1143
+three:
+  ret i32 99783
+}
+
+; Optimization shouldn't trigger; bitwidth > 64
+; CHECK-LABEL: name: test2
+; CHECK-NOT: t2BR_JT
+define i128 @test2(i128 %a) optsize {
+  switch i128 %a, label %def [
+    i128 97, label %one
+    i128 101, label %two
+    i128 105, label %three
+    i128 109, label %three
+  ]
+
+def:
+  ret i128 8867
+
+one:
+  ret i128 11984
+two:
+  ret i128 1143
+three:
+  ret i128 99783
+}
+
+
+; Optimization shouldn't trigger; no holes present
+; CHECK-LABEL: name: test3
+; CHECK-NOT: t2BR_JT
+define i32 @test3(i32 %a) optsize {
+  switch i32 %a, label %def [
+    i32 97, label %one
+    i32 98, label %two
+    i32 99, label %three
+    i32 100, label %three
+  ]
+
+def:
+  ret i32 8867
+
+one:
+  ret i32 11984
+two:
+  ret i32 1143
+three:
+  ret i32 99783
+}
+
+; Optimization shouldn't trigger; not an arithmetic progression
+; CHECK-LABEL: name: test4
+; CHECK-NOT: t2BR_JT
+define i32 @test4(i32 %a) optsize {
+  switch i32 %a, label %def [
+    i32 97, label %one
+    i32 102, label %two
+    i32 105, label %three
+    i32 109, label %three
+  ]
+
+def:
+  ret i32 8867
+
+one:
+  ret i32 11984
+two:
+  ret i32 1143
+three:
+  ret i32 99783
+}
+
+; Optimization shouldn't trigger; not a power of two
+; CHECK-LABEL: name: test5
+; CHECK-NOT: t2BR_JT
+define i32 @test5(i32 %a) optsize {
+  switch i32 %a, label %def [
+    i32 97, label %one
+    i32 102, label %two
+    i32 107, label %three
+    i32 112, label %three
+  ]
+
+def:
+  ret i32 8867
+
+one:
+  ret i32 11984
+two:
+  ret i32 1143
+three:
+  ret i32 99783
+}
+
+; CHECK-LABEL: name: test6
+; CHECK: %[[x:.*]] = t2ADDri killed %r0, 109
+; CHECK: %[[y:.*]] = t2RORri killed %[[x]], 2
+; CHECK: t2CMPri %[[y]], 3
+; CHECK: t2Bcc
+; CHECK: t2BR_JT
+define i32 @test6(i32 %a) optsize {
+  switch i32 %a, label %def [
+    i32 -97, label %one
+    i32 -101, label %two
+    i32 -105, label %three
+    i32 -109, label %three
+  ]
+
+def:
+  ret i32 8867
+
+one:
+  ret i32 11984
+two:
+  ret i32 1143
+three:
+  ret i32 99783
+}
+
+; CHECK-LABEL: name: test7
+; CHECK: %[[z:.*]] = t2UXTB killed %r0, 0
+; CHECK: %[[x:.*]] = t2SUBri killed %[[z]], 220
+; CHECK: %[[y:.*]] = t2RORri killed %[[x]], 2
+; CHECK: t2CMPri %[[y]], 3
+; CHECK: t2Bcc
+; CHECK: t2BR_JT
+define i8 @test7(i8 %a) optsize {
+  switch i8 %a, label %def [
+    i8 220, label %one
+    i8 224, label %two
+    i8 228, label %three
+    i8 232, label %three
+  ]
+
+def:
+  ret i8 8867
+
+one:
+  ret i8 11984
+two:
+  ret i8 1143
+three:
+  ret i8 99783
+}
+
+
+; CHECK-LABEL: test8
+; CHECK: %[[x:.*]] = t2SUBri killed %r0, 97
+; CHECK: %[[y:.*]] = t2RORri killed %[[x]], 2
+; CHECK: t2CMPri %[[y]], 4
+; CHECK: t2Bcc
+; CHECK: t2BR_JT
+define i32 @test8(i32 %a) optsize {
+  switch i32 %a, label %def [
+    i32 97, label %one
+    i32 101, label %two
+    i32 105, label %three
+    i32 113, label %three
+  ]
+
+def:
+  ret i32 8867
+
+one:
+  ret i32 11984
+two:
+  ret i32 1143
+three:
+  ret i32 99783
+}

test/CodeGen/X86/switch-edge-weight.ll

 ; In this switch statement, there is an edge from jump table to default basic
 ; block.
 
   switch i32 %x, label %sw.default [
     i32 4, label %sw.bb
     i32 20, label %sw.bb2
     i32 28, label %sw.bb3
     i32 36, label %sw.bb4
-    i32 124, label %sw.bb5
+    i32 125, label %sw.bb5
   ], !prof !2
 
 sw.bb:
   call void @foo(i32 0)
   br label %sw.epilog
 
 sw.bb2:
   call void @foo(i32 1)