Index: include/llvm/Analysis/ValueTracking.h
===================================================================
--- include/llvm/Analysis/ValueTracking.h
+++ include/llvm/Analysis/ValueTracking.h
@@ -105,6 +105,13 @@
                        const Instruction *CxtI = nullptr,
                        const DominatorTree *DT = nullptr);
 
+  /// Returns true if the given value is known be negative (i.e. non-positive
+  /// and non-zero).
+  bool isKnownNegative(Value *V, const DataLayout &DL, unsigned Depth = 0,
+                       AssumptionCache *AC = nullptr,
+                       const Instruction *CxtI = nullptr,
+                       const DominatorTree *DT = nullptr);
+
   /// isKnownNonEqual - Return true if the given values are known to be
   /// non-equal when defined. Supports scalar integer types only.
   bool isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL,
Index: include/llvm/IR/PatternMatch.h
===================================================================
--- include/llvm/IR/PatternMatch.h
+++ include/llvm/IR/PatternMatch.h
@@ -1312,6 +1312,43 @@
   return Signum_match<Val_t>(V);
 }
 
+//===----------------------------------------------------------------------===//
+// Matchers for two-operands operators with the operators in either order
+//
+
+/// \brief Matches an ICmp with a predicate over LHS and RHS in either order.
+/// Does not swap the predicate.
+template<typename LHS, typename RHS>
+inline match_combine_or<CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>,
+                        CmpClass_match<RHS, LHS, ICmpInst, ICmpInst::Predicate>>
+m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
+  return m_CombineOr(m_ICmp(Pred, L, R), m_ICmp(Pred, R, L));
+}
+
+/// \brief Matches an And with LHS and RHS in either order.
+template<typename LHS, typename RHS>
+inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::And>,
+                        BinaryOp_match<RHS, LHS, Instruction::And>>
+m_c_And(const LHS &L, const RHS &R) {
+  return m_CombineOr(m_And(L, R), m_And(R, L));
+}
+
+/// \brief Matches an Or with LHS and RHS in either order.
+template<typename LHS, typename RHS>
+inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Or>,
+                        BinaryOp_match<RHS, LHS, Instruction::Or>>
+m_c_Or(const LHS &L, const RHS &R) {
+  return m_CombineOr(m_Or(L, R), m_Or(R, L));
+}
+
+/// \brief Matches an Xor with LHS and RHS in either order.
+template<typename LHS, typename RHS>
+inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Xor>,
+                        BinaryOp_match<RHS, LHS, Instruction::Xor>>
+m_c_Xor(const LHS &L, const RHS &R) {
+  return m_CombineOr(m_Xor(L, R), m_Xor(R, L));
+}
+
 } // end namespace PatternMatch
 } // end namespace llvm
 
Index: lib/Analysis/InstructionSimplify.cpp
===================================================================
--- lib/Analysis/InstructionSimplify.cpp
+++ lib/Analysis/InstructionSimplify.cpp
@@ -2616,21 +2616,48 @@
     }
   }
 
-  // icmp pred (or X, Y), X
-  if (LBO && match(LBO, m_CombineOr(m_Or(m_Value(), m_Specific(RHS)),
-                                    m_Or(m_Specific(RHS), m_Value())))) {
-    if (Pred == ICmpInst::ICMP_ULT)
-      return getFalse(ITy);
-    if (Pred == ICmpInst::ICMP_UGE)
-      return getTrue(ITy);
-  }
-  // icmp pred X, (or X, Y)
-  if (RBO && match(RBO, m_CombineOr(m_Or(m_Value(), m_Specific(LHS)),
-                                    m_Or(m_Specific(LHS), m_Value())))) {
-    if (Pred == ICmpInst::ICMP_ULE)
-      return getTrue(ITy);
-    if (Pred == ICmpInst::ICMP_UGT)
-      return getFalse(ITy);
+  {
+    Value *Y = nullptr;
+    // icmp pred (or X, Y), X
+    if (LBO && match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS)))) {
+      if (Pred == ICmpInst::ICMP_ULT)
+        return getFalse(ITy);
+      if (Pred == ICmpInst::ICMP_UGE)
+        return getTrue(ITy);
+
+      if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) {
+        bool RHSKnownNonNegative, RHSKnownNegative;
+        bool YKnownNonNegative, YKnownNegative;
+        ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, Q.DL, 0,
+                       Q.AC, Q.CxtI, Q.DT);
+        ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, Q.DL, 0, Q.AC,
+                       Q.CxtI, Q.DT);
+        if (RHSKnownNonNegative && YKnownNegative)
+          return Pred == ICmpInst::ICMP_SLT ? getTrue(ITy) : getFalse(ITy);
+        if (RHSKnownNegative || YKnownNonNegative)
+          return Pred == ICmpInst::ICMP_SLT ? getFalse(ITy) : getTrue(ITy);
+      }
+    }
+    // icmp pred X, (or X, Y)
+    if (RBO && match(RBO, m_c_Or(m_Value(Y), m_Specific(LHS)))) {
+      if (Pred == ICmpInst::ICMP_ULE)
+        return getTrue(ITy);
+      if (Pred == ICmpInst::ICMP_UGT)
+        return getFalse(ITy);
+
+      if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE) {
+        bool LHSKnownNonNegative, LHSKnownNegative;
+        bool YKnownNonNegative, YKnownNegative;
+        ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0,
+                       Q.AC, Q.CxtI, Q.DT);
+        ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, Q.DL, 0, Q.AC,
+                       Q.CxtI, Q.DT);
+        if (LHSKnownNonNegative && YKnownNegative)
+          return Pred == ICmpInst::ICMP_SGT ? getTrue(ITy) : getFalse(ITy);
+        if (LHSKnownNegative || YKnownNonNegative)
+          return Pred == ICmpInst::ICMP_SGT ? getFalse(ITy) : getTrue(ITy);
+      }
+    }
   }
 
   // icmp pred (and X, Y), X
Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp
+++ lib/Analysis/ValueTracking.cpp
@@ -195,6 +195,14 @@
     isKnownNonZero(V, DL, Depth, AC, CxtI, DT);
 }
 
+bool llvm::isKnownNegative(Value *V, const DataLayout &DL, unsigned Depth,
+                           AssumptionCache *AC, const Instruction *CxtI,
+                           const DominatorTree *DT) {
+  bool NonNegative, Negative;
+  ComputeSignBit(V, NonNegative, Negative, DL, Depth, AC, CxtI, DT);
+  return Negative;
+}
+
 static bool isKnownNonEqual(Value *V1, Value *V2, const Query &Q);
 
 bool llvm::isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL,
@@ -508,34 +516,6 @@
   return ::isValidAssumeForContext(const_cast<Instruction *>(I), CxtI, DT);
 }
 
-template<typename LHS, typename RHS>
-inline match_combine_or<CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>,
-                        CmpClass_match<RHS, LHS, ICmpInst, ICmpInst::Predicate>>
-m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
-  return m_CombineOr(m_ICmp(Pred, L, R), m_ICmp(Pred, R, L));
-}
-
-template<typename LHS, typename RHS>
-inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::And>,
-                        BinaryOp_match<RHS, LHS, Instruction::And>>
-m_c_And(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_And(L, R), m_And(R, L));
-}
-
-template<typename LHS, typename RHS>
-inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Or>,
-                        BinaryOp_match<RHS, LHS, Instruction::Or>>
-m_c_Or(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_Or(L, R), m_Or(R, L));
-}
-
-template<typename LHS, typename RHS>
-inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Xor>,
-                        BinaryOp_match<RHS, LHS, Instruction::Xor>>
-m_c_Xor(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_Xor(L, R), m_Xor(R, L));
-}
-
 static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero,
                                        APInt &KnownOne, unsigned Depth,
                                        const Query &Q) {
Index: test/Transforms/InstSimplify/compare.ll
===================================================================
--- test/Transforms/InstSimplify/compare.ll
+++ test/Transforms/InstSimplify/compare.ll
@@ -1203,3 +1203,140 @@
 ; CHECK-LABEL: @tautological9(
 ; CHECK: ret i1 true
 }
+
+declare void @helper_i1(i1)
+; Series of tests for icmp s[lt|ge] (or A, B), A and icmp s[gt|le] A, (or A, B)
+define void @icmp_slt_sge_or(i32 %Ax, i32 %Bx) {
+; 'p' for positive, 'n' for negative, 'x' for potentially either.
+; %D is 'icmp slt (or A, B), A'
+; %E is 'icmp sge (or A, B), A' making it the not of %D
+; %F is 'icmp sgt A, (or A, B)' making it the same as %D
+; %G is 'icmp sle A, (or A, B)' making it the not of %D
+  %Aneg = or i32 %Ax, 2147483648
+  %Apos = and i32 %Ax, 2147483647
+  %Bneg = or i32 %Bx, 2147483648
+  %Bpos = and i32 %Bx, 2147483647
+
+  %Cpp = or i32 %Apos, %Bpos
+  %Dpp = icmp slt i32 %Cpp, %Apos
+  %Epp = icmp sge i32 %Cpp, %Apos
+  %Fpp = icmp sgt i32 %Apos, %Cpp
+  %Gpp = icmp sle i32 %Apos, %Cpp
+  %Cpx = or i32 %Apos, %Bx
+  %Dpx = icmp slt i32 %Cpx, %Apos
+  %Epx = icmp sge i32 %Cpx, %Apos
+  %Fpx = icmp sgt i32 %Apos, %Cpx
+  %Gpx = icmp sle i32 %Apos, %Cpx
+  %Cpn = or i32 %Apos, %Bneg
+  %Dpn = icmp slt i32 %Cpn, %Apos
+  %Epn = icmp sge i32 %Cpn, %Apos
+  %Fpn = icmp sgt i32 %Apos, %Cpn
+  %Gpn = icmp sle i32 %Apos, %Cpn
+
+  %Cxp = or i32 %Ax, %Bpos
+  %Dxp = icmp slt i32 %Cxp, %Ax
+  %Exp = icmp sge i32 %Cxp, %Ax
+  %Fxp = icmp sgt i32 %Ax, %Cxp
+  %Gxp = icmp sle i32 %Ax, %Cxp
+  %Cxx = or i32 %Ax, %Bx
+  %Dxx = icmp slt i32 %Cxx, %Ax
+  %Exx = icmp sge i32 %Cxx, %Ax
+  %Fxx = icmp sgt i32 %Ax, %Cxx
+  %Gxx = icmp sle i32 %Ax, %Cxx
+  %Cxn = or i32 %Ax, %Bneg
+  %Dxn = icmp slt i32 %Cxn, %Ax
+  %Exn = icmp sge i32 %Cxn, %Ax
+  %Fxn = icmp sgt i32 %Ax, %Cxn
+  %Gxn = icmp sle i32 %Ax, %Cxn
+
+  %Cnp = or i32 %Aneg, %Bpos
+  %Dnp = icmp slt i32 %Cnp, %Aneg
+  %Enp = icmp sge i32 %Cnp, %Aneg
+  %Fnp = icmp sgt i32 %Aneg, %Cnp
+  %Gnp = icmp sle i32 %Aneg, %Cnp
+  %Cnx = or i32 %Aneg, %Bx
+  %Dnx = icmp slt i32 %Cnx, %Aneg
+  %Enx = icmp sge i32 %Cnx, %Aneg
+  %Fnx = icmp sgt i32 %Aneg, %Cnx
+  %Gnx = icmp sle i32 %Aneg, %Cnx
+  %Cnn = or i32 %Aneg, %Bneg
+  %Dnn = icmp slt i32 %Cnn, %Aneg
+  %Enn = icmp sge i32 %Cnn, %Aneg
+  %Fnn = icmp sgt i32 %Aneg, %Cnn
+  %Gnn = icmp sle i32 %Aneg, %Cnn
+
+  call void @helper_i1(i1 %Dpp)
+  call void @helper_i1(i1 %Epp)
+  call void @helper_i1(i1 %Fpp)
+  call void @helper_i1(i1 %Gpp)
+  call void @helper_i1(i1 %Dpx)
+  call void @helper_i1(i1 %Epx)
+  call void @helper_i1(i1 %Fpx)
+  call void @helper_i1(i1 %Gpx)
+  call void @helper_i1(i1 %Dpn)
+  call void @helper_i1(i1 %Epn)
+  call void @helper_i1(i1 %Fpn)
+  call void @helper_i1(i1 %Gpn)
+  call void @helper_i1(i1 %Dxp)
+  call void @helper_i1(i1 %Exp)
+  call void @helper_i1(i1 %Fxp)
+  call void @helper_i1(i1 %Gxp)
+  call void @helper_i1(i1 %Dxx)
+  call void @helper_i1(i1 %Exx)
+  call void @helper_i1(i1 %Fxx)
+  call void @helper_i1(i1 %Gxx)
+  call void @helper_i1(i1 %Dxn)
+  call void @helper_i1(i1 %Exn)
+  call void @helper_i1(i1 %Fxn)
+  call void @helper_i1(i1 %Gxn)
+  call void @helper_i1(i1 %Dnp)
+  call void @helper_i1(i1 %Enp)
+  call void @helper_i1(i1 %Fnp)
+  call void @helper_i1(i1 %Gnp)
+  call void @helper_i1(i1 %Dnx)
+  call void @helper_i1(i1 %Enx)
+  call void @helper_i1(i1 %Fnx)
+  call void @helper_i1(i1 %Gnx)
+  call void @helper_i1(i1 %Dnn)
+  call void @helper_i1(i1 %Enn)
+  call void @helper_i1(i1 %Fnn)
+  call void @helper_i1(i1 %Gnn)
+; CHECK-LABEL: @icmp_slt_sge_or
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 %Dpx)
+; CHECK: call void @helper_i1(i1 %Epx)
+; CHECK: call void @helper_i1(i1 %Fpx)
+; CHECK: call void @helper_i1(i1 %Gpx)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 %Dxx)
+; CHECK: call void @helper_i1(i1 %Exx)
+; CHECK: call void @helper_i1(i1 %Fxx)
+; CHECK: call void @helper_i1(i1 %Gxx)
+; CHECK: call void @helper_i1(i1 %Dxn)
+; CHECK: call void @helper_i1(i1 %Exn)
+; CHECK: call void @helper_i1(i1 %Fxn)
+; CHECK: call void @helper_i1(i1 %Gxn)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+  ret void
+}