Index: lib/Transforms/InstCombine/InstCombineCompares.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -2399,12 +2399,35 @@
   ICmpInst::Predicate PredA, PredB;
   if (match(SI->getTrueValue(), m_ConstantInt(Equal)) &&
       match(SI->getCondition(), m_ICmp(PredA, m_Value(LHS), m_Value(RHS))) &&
-      PredA == ICmpInst::ICMP_EQ &&
-      match(SI->getFalseValue(),
-            m_Select(m_ICmp(PredB, m_Specific(LHS), m_Specific(RHS)),
-                     m_ConstantInt(Less), m_ConstantInt(Greater))) &&
-      PredB == ICmpInst::ICMP_SLT) {
-    return true;
+      PredA == ICmpInst::ICMP_EQ) {
+    if (match(SI->getFalseValue(),
+              m_Select(m_ICmp(PredB, m_Specific(LHS), m_Specific(RHS)),
+                       m_ConstantInt(Less), m_ConstantInt(Greater))) &&
+        PredB == ICmpInst::ICMP_SLT)
+      return true;
+
+    if (match(RHS, m_Zero())) {
+      // RHS = 0 is a special case. Here we expected to see something like:
+      //   select i1 (a < 0), i32 Less, i32 Greater
+      // however such select could have been recognized as a bit test of the
+      // highest big by other combine transforms. Here we try to recognize this
+      // select in some particular cases.
+      // Try to recognize:
+      //   select i1 (a < 0), i32 -1, i32 Greater
+      // simplified in form:
+      //   (a s>> 31) | Greater
+      // If %a was negative, then the result of "ashr" is -1 and the result of
+      // "or" is also -1. If %a was non-negative, then the result of "ashr" is 0
+      // and the result of "or" is "Greater".
+      Value *ShiftValue = ConstantInt::get(
+          LHS->getType(), LHS->getType()->getIntegerBitWidth() - 1);
+      if (match(SI->getFalseValue(),
+                m_Or(m_AShr(m_Specific(LHS), m_Specific(ShiftValue)),
+                     m_ConstantInt(Greater)))) {
+        Less = ConstantInt::get(Greater->getType(), -1, true);
+        return true;
+      }
+    }
   }
   return false;
 }
Index: test/Transforms/InstCombine/three-way-comparison.ll
===================================================================
--- /dev/null
+++ test/Transforms/InstCombine/three-way-comparison.ll
@@ -0,0 +1,243 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; Test that various patterns of three-ways comparison are recognized.
+
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
+
+declare void @foo(i32 %x)
+
+define i32 @compare_against_arbitrary_value(i32 %x, i32 %c) {
+; TODO: We can prove that if %x s> %c then %x != c, so there should be no actual
+;       calculations in callfoo block. @foo can be invoked with 1. We only do it
+;       for constants that are not 0 currently while it could be generalized.
+; CHECK-LABEL: @compare_against_arbitrary_value(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], [[C:%.*]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[X]], [[C]]
+; CHECK-NEXT:    [[SELECT2:%.*]] = zext i1 [[CMP1]] to i32
+; CHECK-NEXT:    call void @foo(i32 [[SELECT2]])
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, %c
+  %cmp2 = icmp slt i32 %x, %c
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_zero(i32 %x) {
+; TODO: We can prove that if %x s> %c then %x != c, so there should be no actual
+;       calculations in callfoo block. @foo can be invoked with 1. For some
+;       reasons it does not happen for constant zero while it does happen for
+;       other constants.
+; CHECK-LABEL: @compare_against_zero(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 0
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X]], 31
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], 1
+; CHECK-NEXT:    call void @foo(i32 [[TMP2]])
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 0
+  %cmp2 = icmp slt i32 %x, 0
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_one(i32 %x) {
+; CHECK-LABEL: @compare_against_one(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 1
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 1
+  %cmp2 = icmp slt i32 %x, 1
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_two(i32 %x) {
+; CHECK-LABEL: @compare_against_two(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 2
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 2
+  %cmp2 = icmp slt i32 %x, 2
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_three(i32 %x) {
+; CHECK-LABEL: @compare_against_three(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 3
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 3
+  %cmp2 = icmp slt i32 %x, 3
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_four(i32 %x) {
+; CHECK-LABEL: @compare_against_four(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 4
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 4
+  %cmp2 = icmp slt i32 %x, 4
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_five(i32 %x) {
+; CHECK-LABEL: @compare_against_five(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 5
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 5
+  %cmp2 = icmp slt i32 %x, 5
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_six(i32 %x) {
+; CHECK-LABEL: @compare_against_six(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 6
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 6
+  %cmp2 = icmp slt i32 %x, 6
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}