Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp
===================================================================
--- llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -4485,9 +4485,6 @@
   if (Instruction *Res = foldICmpWithConstant(I))
     return Res;
 
-  if (Instruction *Res = foldICmpUsingKnownBits(I))
-    return Res;
-
   // Test if the ICmpInst instruction is used exclusively by a select as
   // part of a minimum or maximum operation. If so, refrain from doing
   // any other folding. This helps out other analyses which understand
@@ -4706,6 +4703,13 @@
     if (match(Op1, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op0 == X)
       return foldICmpAddOpConst(X, Cst, I.getSwappedPredicate());
   }
+
+  // This may be expensive in compile-time, and transforms based on known bits
+  // can make further analysis more difficult, so we use it as the last resort
+  // if we cannot do anything better.
+  if (Instruction *Res = foldICmpUsingKnownBits(I))
+    return Res;
+
   return Changed ? &I : nullptr;
 }
 
Index: llvm/trunk/test/Analysis/ValueTracking/non-negative-phi-bits.ll
===================================================================
--- llvm/trunk/test/Analysis/ValueTracking/non-negative-phi-bits.ll
+++ llvm/trunk/test/Analysis/ValueTracking/non-negative-phi-bits.ll
@@ -8,7 +8,7 @@
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ult i64 [[INDVARS_IV_NEXT]], 40
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ult i64 [[INDVARS_IV]], 39
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
Index: llvm/trunk/test/Transforms/InstCombine/icmp-shl-nsw.ll
===================================================================
--- llvm/trunk/test/Transforms/InstCombine/icmp-shl-nsw.ll
+++ llvm/trunk/test/Transforms/InstCombine/icmp-shl-nsw.ll
@@ -69,11 +69,9 @@
 ; icmp sgt with shl nsw with a constant compare operand and constant
 ; shift amount can always be reduced to icmp sgt alone.
 
-; Known bits analysis turns this into an equality predicate.
-
 define i1 @icmp_sgt1(i8 %x) {
 ; CHECK-LABEL: @icmp_sgt1(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 %x, -64
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 %x, -64
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl nsw i8 %x, 1
@@ -144,11 +142,10 @@
   ret i1 %cmp
 }
 
-; Known bits analysis turns this into an equality predicate.
 
 define i1 @icmp_sgt8(i8 %x) {
 ; CHECK-LABEL: @icmp_sgt8(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 %x, 63
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 %x, 62
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl nsw i8 %x, 1
@@ -158,11 +155,9 @@
 
 ; Compares with 126 and 127 are recognized as always false.
 
-; Known bits analysis turns this into an equality predicate.
-
 define i1 @icmp_sgt9(i8 %x) {
 ; CHECK-LABEL: @icmp_sgt9(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 %x, -1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 %x, -1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl nsw i8 %x, 7
@@ -210,11 +205,9 @@
 ;
 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 
-; Known bits analysis turns this into an equality predicate.
-
 define i1 @icmp_sle1(i8 %x) {
 ; CHECK-LABEL: @icmp_sle1(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 %x, -64
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 %x, -63
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl nsw i8 %x, 1
@@ -285,11 +278,9 @@
   ret i1 %cmp
 }
 
-; Known bits analysis turns this into an equality predicate.
-
 define i1 @icmp_sle8(i8 %x) {
 ; CHECK-LABEL: @icmp_sle8(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 %x, 63
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 %x, 63
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl nsw i8 %x, 1
@@ -299,11 +290,9 @@
 
 ; Compares with 126 and 127 are recognized as always true.
 
-; Known bits analysis turns this into an equality predicate.
-
 define i1 @icmp_sle9(i8 %x) {
 ; CHECK-LABEL: @icmp_sle9(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 %x, -1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 %x, 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl nsw i8 %x, 7
@@ -353,4 +342,3 @@
   %cmp = icmp ne i8 %shl, -128
   ret i1 %cmp
 }
-
Index: llvm/trunk/test/Transforms/InstCombine/icmp-shr-lt-gt.ll
===================================================================
--- llvm/trunk/test/Transforms/InstCombine/icmp-shr-lt-gt.ll
+++ llvm/trunk/test/Transforms/InstCombine/icmp-shr-lt-gt.ll
@@ -1,3 +1,4 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define i1 @lshrugt_01_00(i4 %x) {
@@ -1834,7 +1835,7 @@
 
 define i1 @lshrugt_01_06_exact(i4 %x) {
 ; CHECK-LABEL: @lshrugt_01_06_exact(
-; CHECK-NEXT:    [[C:%.*]] = icmp eq i4 %x, -2
+; CHECK-NEXT:    [[C:%.*]] = icmp ugt i4 %x, -4
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = lshr exact i4 %x, 1
@@ -1945,7 +1946,7 @@
 
 define i1 @lshrugt_02_02_exact(i4 %x) {
 ; CHECK-LABEL: @lshrugt_02_02_exact(
-; CHECK-NEXT:    [[C:%.*]] = icmp eq i4 %x, -4
+; CHECK-NEXT:    [[C:%.*]] = icmp ugt i4 %x, -8
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = lshr exact i4 %x, 2
@@ -2226,7 +2227,7 @@
 
 define i1 @lshrult_01_01_exact(i4 %x) {
 ; CHECK-LABEL: @lshrult_01_01_exact(
-; CHECK-NEXT:    [[C:%.*]] = icmp eq i4 %x, 0
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i4 %x, 2
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = lshr exact i4 %x, 1
@@ -2286,7 +2287,7 @@
 
 define i1 @lshrult_01_07_exact(i4 %x) {
 ; CHECK-LABEL: @lshrult_01_07_exact(
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i4 %x, -2
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i4 %x, -2
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = lshr exact i4 %x, 1
@@ -2377,7 +2378,7 @@
 
 define i1 @lshrult_02_01_exact(i4 %x) {
 ; CHECK-LABEL: @lshrult_02_01_exact(
-; CHECK-NEXT:    [[C:%.*]] = icmp eq i4 %x, 0
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i4 %x, 4
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = lshr exact i4 %x, 2
@@ -2397,7 +2398,7 @@
 
 define i1 @lshrult_02_03_exact(i4 %x) {
 ; CHECK-LABEL: @lshrult_02_03_exact(
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i4 %x, -4
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i4 %x, -4
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = lshr exact i4 %x, 2
@@ -2524,7 +2525,7 @@
 
 define i1 @lshrult_03_01_exact(i4 %x) {
 ; CHECK-LABEL: @lshrult_03_01_exact(
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i4 %x, -8
+; CHECK-NEXT:    [[C:%.*]] = icmp sgt i4 %x, -1
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = lshr exact i4 %x, 3
@@ -2801,7 +2802,7 @@
 
 define i1 @ashrsgt_01_15_exact(i4 %x) {
 ; CHECK-LABEL: @ashrsgt_01_15_exact(
-; CHECK-NEXT:    [[C:%.*]] = icmp sgt i4 %x, -1
+; CHECK-NEXT:    [[C:%.*]] = icmp sgt i4 %x, -2
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = ashr exact i4 %x, 1
@@ -2948,7 +2949,7 @@
 
 define i1 @ashrsgt_02_15_exact(i4 %x) {
 ; CHECK-LABEL: @ashrsgt_02_15_exact(
-; CHECK-NEXT:    [[C:%.*]] = icmp sgt i4 %x, -1
+; CHECK-NEXT:    [[C:%.*]] = icmp sgt i4 %x, -4
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = ashr exact i4 %x, 2
@@ -3093,7 +3094,7 @@
 
 define i1 @ashrsgt_03_15_exact(i4 %x) {
 ; CHECK-LABEL: @ashrsgt_03_15_exact(
-; CHECK-NEXT:    [[C:%.*]] = icmp sgt i4 %x, -1
+; CHECK-NEXT:    [[C:%.*]] = icmp ne i4 %x, -8
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = ashr exact i4 %x, 3
Index: llvm/trunk/test/Transforms/InstCombine/icmp_sdiv_with_and_without_range.ll
===================================================================
--- llvm/trunk/test/Transforms/InstCombine/icmp_sdiv_with_and_without_range.ll
+++ llvm/trunk/test/Transforms/InstCombine/icmp_sdiv_with_and_without_range.ll
@@ -2,7 +2,8 @@
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 ; Test that presence of range does not cause unprofitable transforms with bit
-; arithmetics, and instcombine behaves exactly the same as without the range.
+; arithmetics. InstCombine needs to be smart about dealing with range-annotated
+; values.
 
 define i1 @without_range(i32* %A) {
 ; CHECK-LABEL: @without_range(
@@ -19,8 +20,7 @@
 define i1 @with_range(i32* %A) {
 ; CHECK-LABEL: @with_range(
 ; CHECK-NEXT:    [[A_VAL:%.*]] = load i32, i32* [[A:%.*]], align 8, !range !0
-; CHECK-NEXT:    [[B_MASK:%.*]] = and i32 [[A_VAL]], 2147483646
-; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[B_MASK]], 0
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i32 [[A_VAL]], 2
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %A.val = load i32, i32* %A, align 8, !range !0
Index: llvm/trunk/test/Transforms/LoopVectorize/X86/masked_load_store.ll
===================================================================
--- llvm/trunk/test/Transforms/LoopVectorize/X86/masked_load_store.ll
+++ llvm/trunk/test/Transforms/LoopVectorize/X86/masked_load_store.ll
@@ -2052,8 +2052,7 @@
 ; AVX512-NEXT:    [[PROL_ITER_CMP:%.*]] = icmp eq i64 [[PROL_ITER_SUB]], 0
 ; AVX512-NEXT:    br i1 [[PROL_ITER_CMP]], label [[FOR_BODY_PROL_LOOPEXIT:%.*]], label [[FOR_BODY_PROL]], !llvm.loop !50
 ; AVX512:       for.body.prol.loopexit:
-; AVX512-NEXT:    [[DOTMASK:%.*]] = and i64 [[TMP24]], 9984
-; AVX512-NEXT:    [[TMP28:%.*]] = icmp eq i64 [[DOTMASK]], 0
+; AVX512-NEXT:    [[TMP28:%.*]] = icmp ult i64 [[TMP24]], 48
 ; AVX512-NEXT:    br i1 [[TMP28]], label [[FOR_END:%.*]], label [[FOR_BODY:%.*]]
 ; AVX512:       for.body:
 ; AVX512-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT_3:%.*]], [[FOR_INC_3:%.*]] ], [ [[INDVARS_IV_NEXT_PROL]], [[FOR_BODY_PROL_LOOPEXIT]] ]