Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
===================================================================
--- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -2420,6 +2420,7 @@
   DEBUG(dbgs() << "Selecting best pivot: \n"
                << "First: " << First << ", Last: " << Last <<'\n'
                << "LSize: " << LSize << ", RSize: " << RSize << '\n');
+  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   for (CaseItr I = CR.Range.first, J=I+1, E = CR.Range.second;
        J!=E; ++I, ++J) {
     const APInt &LEnd = cast<ConstantInt>(I->High)->getValue();
@@ -2430,9 +2431,13 @@
     // Use volatile double here to avoid excess precision issues on some hosts,
     // e.g. that use 80-bit X87 registers.
     volatile double LDensity =
-        LSize.roundToDouble() / (LEnd - First + 1ULL).roundToDouble();
+        LSize.ult(TLI.getMinimumJumpTableEntries())
+            ? 0.0
+            : LSize.roundToDouble() / (LEnd - First + 1ULL).roundToDouble();
     volatile double RDensity =
-        RSize.roundToDouble() / (Last - RBegin + 1ULL).roundToDouble();
+        RSize.ult(TLI.getMinimumJumpTableEntries())
+            ? 0.0
+            : RSize.roundToDouble() / (Last - RBegin + 1ULL).roundToDouble();
     volatile double Metric = Range.logBase2() * (LDensity + RDensity);
     // Should always split in some non-trivial place
     DEBUG(dbgs() <<"=>Step\n"
@@ -2450,13 +2455,8 @@
     RSize -= J->size();
   }
 
-  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
-  if (areJTsAllowed(TLI)) {
-    // If our case is dense we *really* should handle it earlier!
-    assert((FMetric > 0) && "Should handle dense range earlier!");
-  } else {
+  if (FMetric == 0 || !areJTsAllowed(TLI))
     Pivot = CR.Range.first + Size/2;
-  }
   splitSwitchCase(CR, Pivot, WorkList, SV, SwitchBB);
   return true;
 }
Index: test/CodeGen/X86/switch-bt.ll
===================================================================
--- test/CodeGen/X86/switch-bt.ll
+++ test/CodeGen/X86/switch-bt.ll
@@ -99,3 +99,61 @@
 if.end:
   ret void
 }
+
+; Ensure that optimizing for jump tables doesn't needlessly deteriorate the
+; created binary tree search. See PR22262.
+define void @test4(i32 %x, i32* %y) {
+; CHECK-LABEL: test4:
+
+entry:
+  switch i32 %x, label %sw.default [
+    i32 10, label %sw.bb
+    i32 20, label %sw.bb1
+    i32 30, label %sw.bb2
+    i32 40, label %sw.bb3
+    i32 50, label %sw.bb4
+    i32 60, label %sw.bb5
+  ]
+sw.bb:
+  store i32 1, i32* %y
+  br label %sw.epilog
+sw.bb1:
+  store i32 2, i32* %y
+  br label %sw.epilog
+sw.bb2:
+  store i32 3, i32* %y
+  br label %sw.epilog
+sw.bb3:
+  store i32 4, i32* %y
+  br label %sw.epilog
+sw.bb4:
+  store i32 5, i32* %y
+  br label %sw.epilog
+sw.bb5:
+  store i32 6, i32* %y
+  br label %sw.epilog
+sw.default:
+  store i32 7, i32* %y
+  br label %sw.epilog
+sw.epilog:
+  ret void
+
+; The balanced binary switch here would start with a comparison against 39, but
+; it is currently starting with 29 because of the density-sum heuristic.
+; CHECK: cmpl $29
+; CHECK: jg
+; CHECK: cmpl $10
+; CHECK: jne
+; CHECK: cmpl $49
+; CHECK: jg
+; CHECK: cmpl $30
+; CHECK: jne
+; CHECK: cmpl $20
+; CHECK: jne
+; CHECK: cmpl $50
+; CHECK: jne
+; CHECK: cmpl $40
+; CHECK: jne
+; CHECK: cmpl $60
+; CHECK: jne
+}