Index: llvm/lib/Analysis/InstructionSimplify.cpp
===================================================================
--- llvm/lib/Analysis/InstructionSimplify.cpp
+++ llvm/lib/Analysis/InstructionSimplify.cpp
@@ -2849,6 +2849,39 @@
   return nullptr;
 }
 
+
+// If only one of the icmp's operands has NSW flags, try to prove that:
+//
+//   icmp slt (x + C1), (x +nsw C2)
+//
+// is equivalent to:
+//
+//   icmp slt C1, C2
+//
+// which is true if x + C2 has the NSW flags set and C1 < C2 && C1 >= 0.
+//
+static bool trySimplifyICmpWithAdds(CmpInst::Predicate Pred, Value *LHS,
+                                    Value *RHS) {
+  // TODO: only support icmp slt for now.
+  if (Pred != CmpInst::ICMP_SLT)
+    return false;
+
+  // Canonicalize nsw add as RHS.
+  if (!match(RHS, m_NSWAdd(m_Value(), m_Value())))
+    std::swap(LHS, RHS);
+  if (!match(RHS, m_NSWAdd(m_Value(), m_Value())))
+    return false;
+
+  Value *X;
+  const APInt *C1, *C2;
+  if (!match(LHS, m_c_Add(m_Value(X), m_APInt(C1))) ||
+      !match(RHS, m_c_Add(m_Specific(X), m_APInt(C2))))
+    return false;
+
+  return C1->slt(*C2) && C1->isNonNegative();
+}
+
+
 /// TODO: A large part of this logic is duplicated in InstCombine's
 /// foldICmpBinOp(). We should be able to share that and avoid the code
 /// duplication.
@@ -2898,8 +2931,9 @@
         return V;
 
     // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow.
-    if (A && C && (A == C || A == D || B == C || B == D) && NoLHSWrapProblem &&
-        NoRHSWrapProblem) {
+    bool CanSimplify = (NoLHSWrapProblem && NoRHSWrapProblem) ||
+                       trySimplifyICmpWithAdds(Pred, LHS, RHS);
+    if (A && C && (A == C || A == D || B == C || B == D) && CanSimplify) {
       // Determine Y and Z in the form icmp (X+Y), (X+Z).
       Value *Y, *Z;
       if (A == C) {
Index: llvm/test/Transforms/InstSimplify/compare.ll
===================================================================
--- llvm/test/Transforms/InstSimplify/compare.ll
+++ llvm/test/Transforms/InstSimplify/compare.ll
@@ -1711,16 +1711,11 @@
 
 ; Test simplifications for: icmp (X+Y), (X+Z) -> icmp Y,Z
 ; Test the overflow check when the RHS has NSW set and constant Z is greater
-; or equal than Y, then we know X+Y also can't overflow.
+; than Y, then we know X+Y also can't overflow.
 
 define i1 @icmp_nsw_1(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_1(
-; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 5
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 [[V]], 6
-; CHECK-NEXT:    [[S1:%.*]] = sext i32 [[ADD5]] to i64
-; CHECK-NEXT:    [[S2:%.*]] = sext i32 [[ADD6]] to i64
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[S1]], [[S2]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add5 = add i32 %V, 5
   %add6 = add nsw i32 %V, 6
@@ -1732,10 +1727,7 @@
 
 define i1 @icmp_nsw_2(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_2(
-; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 5
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 [[V]], 6
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add5 = add i32 %V, 5
   %add6 = add nsw i32 %V, 6
@@ -1743,6 +1735,115 @@
   ret i1 %cmp
 }
 
+define i1 @icmp_nsw_22(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_22(
+; CHECK-NEXT:    ret i1 true
+;
+  %add5 = add nsw i32 %V, 5
+  %add6 = add nsw i32 %V, 6
+  %cmp = icmp slt i32 %add5, %add6
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_23(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_23(
+; CHECK-NEXT:    [[ADD5:%.*]] = add nsw i32 [[V:%.*]], 5
+; CHECK-NEXT:    [[ADD6:%.*]] = add i32 [[V]], 6
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %add5 = add nsw i32 %V, 5
+  %add6 = add i32 %V, 6
+  %cmp = icmp slt i32 %add5, %add6
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_false(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_false(
+; CHECK-NEXT:    ret i1 false
+;
+  %add5 = add nsw i32 %V, 6
+  %add6 = add i32 %V, 5
+  %cmp = icmp slt i32 %add5, %add6
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_false_2(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_false_2(
+; CHECK-NEXT:    ret i1 false
+;
+  %add5 = add nsw i32 %V, 6
+  %add6 = add nsw i32 %V, 5
+  %cmp = icmp slt i32 %add5, %add6
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_false_3(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_false_3(
+; CHECK-NEXT:    [[ADD5:%.*]] = add nsw i32 [[V:%.*]], 5
+; CHECK-NEXT:    [[ADD6:%.*]] = add i32 [[V]], 5
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %add5 = add nsw i32 %V, 5
+  %add6 = add i32 %V, 5
+  %cmp = icmp slt i32 %add5, %add6
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_false_4(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_false_4(
+; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 6
+; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 [[V]], 5
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %add5 = add i32 %V, 6
+  %add6 = add nsw i32 %V, 5
+  %cmp = icmp slt i32 %add5, %add6
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_i8(i8 %V) {
+; CHECK-LABEL: @icmp_nsw_i8(
+; CHECK-NEXT:    ret i1 true
+;
+  %add5 = add i8 %V, 5
+  %add6 = add nsw i8 %V, 6
+  %cmp = icmp slt i8 %add5, %add6
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_i16(i16 %V) {
+; CHECK-LABEL: @icmp_nsw_i16(
+; CHECK-NEXT:    ret i1 true
+;
+  %add5 = add i16 %V, 5
+  %add6 = add nsw i16 %V, 6
+  %cmp = icmp slt i16 %add5, %add6
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_i64(i64 %V) {
+; CHECK-LABEL: @icmp_nsw_i64(
+; CHECK-NEXT:    ret i1 true
+;
+  %add5 = add i64 %V, 5
+  %add6 = add nsw i64 %V, 6
+  %cmp = icmp slt i64 %add5, %add6
+  ret i1 %cmp
+}
+
+define <4 x i1> @icmp_nsw_vec(<4 x i32> %V) {
+; CHECK-LABEL: @icmp_nsw_vec(
+; CHECK-NEXT:    ret <4 x i1> <i1 true, i1 true, i1 true, i1 true>
+;
+  %add5 = add <4 x i32> %V, <i32 5, i32 5, i32 5, i32 5>
+  %add6 = add nsw <4 x i32> %V, <i32 6, i32 6, i32 6, i32 6>
+  %cmp = icmp slt <4 x i32> %add5, %add6
+  ret <4 x i1> %cmp
+}
+
 define i1 @icmp_nsw_3(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_3(
 ; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 5
@@ -1824,14 +1925,27 @@
 define i1 @icmp_nsw_10(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_10(
 ; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 5
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 [[V]], 5
+; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 [[V]], 6
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[ADD6]], [[ADD5]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add5 = add i32 %V, 5
-  %add6 = add nsw i32 %V, 5
+  %add6 = add nsw i32 %V, 6
   %cmp = icmp sgt i32 %add6, %add5
   ret i1 %cmp
 }
 
+define i1 @icmp_nsw_11(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_11(
+; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], -125
+; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 [[V]], -99
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %add5 = add i32 %V, -125
+  %add6 = add nsw i32 %V, -99
+  %cmp = icmp slt i32 %add5, %add6
+  ret i1 %cmp
+}
+
 attributes #0 = { null_pointer_is_valid }