Index: lib/Analysis/InlineCost.cpp
===================================================================
--- lib/Analysis/InlineCost.cpp
+++ lib/Analysis/InlineCost.cpp
@@ -1028,22 +1028,40 @@
     if (isa<ConstantInt>(V))
       return true;
 
-  // Otherwise, we need to accumulate a cost proportional to the number of
-  // distinct successor blocks. This fan-out in the CFG cannot be represented
-  // for free even if we can represent the core switch as a jumptable that
-  // takes a single instruction.
+  // Otherwise, we assume the most general case where the big swith is lowered
+  // into a balanced binary tree, the probability of entering each case is
+  // equal, and no case can be merged.  The cost of the switch is proportional
+  // to the size of the tree.  See visitSwitch() of SelectionDAGBuilder.cpp
+  // about the detail of constructing the tree.
   //
   // NB: We convert large switches which are just used to initialize large phi
   // nodes to lookup tables instead in simplify-cfg, so this shouldn't prevent
   // inlining those. It will prevent inlining in cases where the optimization
   // does not (yet) fire.
-  SmallPtrSet<BasicBlock *, 8> SuccessorBlocks;
-  SuccessorBlocks.insert(SI.getDefaultDest());
-  for (auto I = SI.case_begin(), E = SI.case_end(); I != E; ++I)
-    SuccessorBlocks.insert(I.getCaseSuccessor());
-  // Add cost corresponding to the number of distinct destinations. The first
-  // we model as free because of fallthrough.
-  Cost += (SuccessorBlocks.size() - 1) * InlineConstants::InstrCost;
+  SmallVector<unsigned, 4> SwitchWorkList;
+  SwitchWorkList.push_back(SI.getNumCases());
+  Cost -= InlineConstants::InstrCost;
+  while (!SwitchWorkList.empty()) {
+    unsigned NumCases = SwitchWorkList.back();
+    SwitchWorkList.pop_back();
+
+    if (NumCases <= 3)
+      // Do not split the tree if the number of remaining cases is less than 3.
+      // Just compare switch condition with each case value.  Suppose each
+      // comparison includes one compare and one conditional branch.
+      Cost += (2 * NumCases * InlineConstants::InstrCost);
+    else {
+      // Split the remaining nodes and add one more comparison.
+      unsigned NumLeft = NumCases / 2;
+      unsigned NumRight = NumCases - NumLeft;
+      SwitchWorkList.push_back(NumLeft);
+      SwitchWorkList.push_back(NumRight);
+      Cost += (2 * InlineConstants::InstrCost);
+    }
+    // Exit early if Cost is already larger than Threshold.
+    if (Cost > Threshold)
+      return false;
+  }
   return false;
 }
 
Index: test/Transforms/Inline/switch.ll
===================================================================
--- test/Transforms/Inline/switch.ll
+++ test/Transforms/Inline/switch.ll
@@ -1,7 +1,7 @@
 ; RUN: opt < %s -inline -inline-threshold=20 -S | FileCheck %s
 ; RUN: opt < %s -passes='cgscc(inline)' -inline-threshold=20 -S | FileCheck %s
 
-define i32 @callee(i32 %a) {
+define i32 @callee1(i32 %a) {
   switch i32 %a, label %sw.default [
     i32 0, label %sw.bb0
     i32 1, label %sw.bb1
@@ -52,10 +52,36 @@
   ret i32 42
 }
 
+define i32 @callee2(i32 %a) {
+  switch i32 %a, label %sw.default [
+    i32 0, label %sw.bb0
+    i32 1, label %sw.bb0
+    i32 2, label %sw.bb0
+    i32 3, label %sw.bb0
+    i32 4, label %sw.bb0
+    i32 5, label %sw.bb0
+    i32 6, label %sw.bb0
+    i32 7, label %sw.bb0
+    i32 8, label %sw.bb0
+    i32 9, label %sw.bb0
+  ]
+
+sw.default:
+  br label %return
+
+sw.bb0:
+  br label %return
+
+return:
+  ret i32 42
+}
+
 define i32 @caller(i32 %a) {
 ; CHECK-LABEL: @caller(
-; CHECK: call i32 @callee(
+; CHECK: call i32 @callee1(
+; CHECK: call i32 @callee2(
 
-  %result = call i32 @callee(i32 %a)
-  ret i32 %result
+  %result1 = call i32 @callee1(i32 %a)
+  %result2 = call i32 @callee2(i32 %a)
+  ret i32 %result1
 }