Index: lib/Transforms/Utils/SimplifyCFG.cpp
===================================================================
--- lib/Transforms/Utils/SimplifyCFG.cpp
+++ lib/Transforms/Utils/SimplifyCFG.cpp
@@ -4968,6 +4968,83 @@
   return true;
 }
 
+// Try and transform a switch that has "holes" in it to a contiguous sequence
+// of cases.
+//
+// A switch such as: switch(i) {case 5: case 9: case 13: case 17:} can be
+// range-reduced to: switch ((i-5) / 4) {case 0: case 1: case 2: case 3:}.
+//
+// This converts a sparse switch into a dense switch which allows better
+// lowering and could also allow transforming into a lookup table.
+static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder,
+                              const DataLayout &DL,
+                              const TargetTransformInfo &TTI) {
+  if (SI->getCondition()->getType()->getIntegerBitWidth() > 64)
+    return false;
+  // Only bother with this optimization if there are more than 2 switch cases.
+  if (SI->getNumCases() <= 2)
+    return false;
+  SmallVector<uint64_t,4> Values;
+  for (auto &C : SI->cases())
+    Values.push_back(C.getCaseValue()->getValue().getLimitedValue());
+  std::sort(Values.begin(), Values.end());
+
+  bool HasHoles = Values.back() != SI->getNumCases() - 1;
+  if (!HasHoles)
+    // This switch is already dense.
+    return false;
+
+  uint64_t Base = Values[0];
+  for (auto &V : Values)
+    V -= Base;
+  uint64_t GCD = 0;
+  for (auto &V : Values)
+    GCD = llvm::GreatestCommonDivisor64(GCD, V);
+
+  if (GCD <= 1)
+    // No common divisor found.
+    return false;
+
+  // We can range-reduce this switch (X) to switch (X - Base) / GCD.
+  // This should be profitable if the resulting switch has no holes -
+  // this should result in a better lowering.
+  // FIXME: Have some sort of density metric and key the heuristic off of that?
+  HasHoles = Values.back() / GCD != SI->getNumCases() - 1;
+  if (HasHoles || !llvm::isPowerOf2_64(GCD))
+    return false;
+
+  auto *Ty = SI->getCondition()->getType();
+  Builder.SetInsertPoint(SI);
+  auto *Sub = Builder.CreateSub(SI->getCondition(), ConstantInt::get(Ty, Base));
+  auto *Div = Builder.CreateUDiv(Sub, ConstantInt::get(Ty, GCD));
+  auto *Rem = Builder.CreateURem(Sub, ConstantInt::get(Ty, GCD));
+  auto *Cmp = Builder.CreateICmpEQ(Rem, ConstantInt::get(Ty, 0));
+  SI->replaceUsesOfWith(SI->getCondition(), Div);
+
+  BasicBlock *OldBB = SI->getParent();
+  SplitBlock(OldBB, SI);
+  OldBB->getTerminator()->eraseFromParent();
+  BranchInst::Create(SI->getParent(), SI->getDefaultDest(), Cmp, OldBB);
+
+  // Correct any PHIs at the destination.
+  for (auto &I : *SI->getDefaultDest()) {
+    auto *PN = dyn_cast<PHINode>(&I);
+    if (!PN)
+      break;
+    auto *V = PN->getIncomingValueForBlock(SI->getParent());
+    PN->addIncoming(V, OldBB);
+  }
+
+  for (auto &C : SI->cases()) {
+    auto *Orig = C.getCaseValue();
+    auto BW = Orig->getValue().getBitWidth();
+    auto Sub = Orig->getValue() - APInt(BW, Base);
+    auto *New = ConstantInt::get(Ty, Sub.udiv(APInt(BW, GCD)));
+    SI->replaceUsesOfWith(Orig, New);
+  }
+  return true;
+}
+
 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   BasicBlock *BB = SI->getParent();
 
@@ -5011,6 +5088,9 @@
   if (SwitchToLookupTable(SI, Builder, DL, TTI))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
+  if (ReduceSwitchRange(SI, Builder, DL, TTI))
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+
   return false;
 }
 
Index: test/Transforms/SimplifyCFG/rangereduce.ll
===================================================================
--- /dev/null
+++ test/Transforms/SimplifyCFG/rangereduce.ll
@@ -0,0 +1,117 @@
+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+; CHECK-LABEL: @test1
+; CHECK: %1 = sub i32 %a, 97
+; CHECK: %2 = udiv i32 %1, 2
+; CHECK: %3 = urem i32 %1, 2
+; CHECK: %4 = icmp eq i32 %3, 0
+; CHECK: br i1 %4, label %.split, label %def
+; CHECK:.split:
+; CHECK:  switch i32 %2, label %def [
+; CHECK:    i32 0, label %one
+; CHECK:    i32 1, label %two
+; CHECK:    i32 2, label %three
+; CHECK:  ]
+; CHECK: phi i32 [ 8867, %.split ], [ 11984, %one ], [ 1143, %two ], [ 99783, %three ], [ 8867, %0 ]
+define i32 @test1(i32 %a) {
+  switch i32 %a, label %def [
+    i32 97, label %one
+    i32 99, label %two
+    i32 101, 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: @test2
+; CHECK: switch i128 %a, label %def
+define i128 @test2(i128 %a) {
+  switch i128 %a, label %def [
+    i128 97, label %one
+    i128 99, label %two
+    i128 101, 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: @test3
+; CHECK: switch i32 %a, label %def
+define i32 @test3(i32 %a) {
+  switch i32 %a, label %def [
+    i32 97, label %one
+    i32 98, label %two
+    i32 99, 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: @test4
+; CHECK: switch i32 %a, label %def
+define i32 @test4(i32 %a) {
+  switch i32 %a, label %def [
+    i32 97, label %one
+    i32 99, label %two
+    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 a power of two
+; CHECK-LABEL: @test5
+; CHECK: switch i32 %a, label %def
+define i32 @test5(i32 %a) {
+  switch i32 %a, label %def [
+    i32 97, label %one
+    i32 100, label %two
+    i32 103, label %three
+  ]
+
+def:
+  ret i32 8867
+
+one:
+  ret i32 11984
+two:
+  ret i32 1143
+three:
+  ret i32 99783
+}