Index: lib/Transforms/Utils/SimplifyCFG.cpp
===================================================================
--- lib/Transforms/Utils/SimplifyCFG.cpp
+++ lib/Transforms/Utils/SimplifyCFG.cpp
@@ -249,7 +249,11 @@
                                        const TargetTransformInfo &TTI) {
   assert(isSafeToSpeculativelyExecute(I) &&
          "Instruction is not safe to speculatively execute!");
-  return TTI.getUserCost(I);
+  unsigned Cost = TTI.getUserCost(I);
+  // Cost of the instruction should be no less than TCC_Basic.
+  if (Cost < TargetTransformInfo::TCC_Basic)
+    Cost = TargetTransformInfo::TCC_Basic;
+  return Cost;
 }
 
 /// If we have a merge point of an "if condition" as accepted above,
Index: test/Transforms/SimplifyCFG/no_if_conversion_to_overhead.ll
===================================================================
--- /dev/null
+++ test/Transforms/SimplifyCFG/no_if_conversion_to_overhead.ll
@@ -0,0 +1,66 @@
+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+; int lower_bound(int *first, int *last, int val) {
+;  int len = last - first;
+;  while (len > 0) {
+;    int half = len >> 1;
+;    int *middle = first + half;
+;    if (*middle < val) {
+;      first = middle;
+;      first++;
+;      len = len - half - 1;
+;    }
+;    else
+;      len = half;
+;  }
+;  return *first;
+; }
+
+; If-conversion should not happen for this function because the overhead
+; it introduced would over-weight its benefit.
+
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z11lower_boundPiS_i(i32* %first, i32* %last, i32 %val) #0 {
+entry:
+  %sub.ptr.lhs.cast = ptrtoint i32* %last to i64
+  %sub.ptr.rhs.cast = ptrtoint i32* %first to i64
+  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
+  %sub.ptr.div12 = lshr exact i64 %sub.ptr.sub, 2
+  %conv = trunc i64 %sub.ptr.div12 to i32
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %entry
+  %len.0 = phi i32 [ %conv, %entry ], [ %len.1, %if.end ]
+  %first.addr.0 = phi i32* [ %first, %entry ], [ %first.addr.1, %if.end ]
+  %cmp = icmp sgt i32 %len.0, 0
+  br i1 %cmp, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+; CHECK-NOT: select
+  %shr = ashr i32 %len.0, 1
+  %idx.ext = sext i32 %shr to i64
+  %add.ptr = getelementptr inbounds i32, i32* %first.addr.0, i64 %idx.ext
+  %0 = load i32, i32* %add.ptr, align 4
+  %cmp1 = icmp slt i32 %0, %val
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:                                          ; preds = %while.body
+  %incdec.ptr = getelementptr inbounds i32, i32* %add.ptr, i64 1
+  %sub = sub nsw i32 %len.0, %shr
+  %sub2 = add nsw i32 %sub, -1
+  br label %if.end
+
+if.else:                                          ; preds = %while.body
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %len.1 = phi i32 [ %sub2, %if.then ], [ %shr, %if.else ]
+  %first.addr.1 = phi i32* [ %incdec.ptr, %if.then ], [ %first.addr.0, %if.else ]
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  %1 = load i32, i32* %first.addr.0, align 4
+  ret i32 %1
+}