Index: llvm/lib/Analysis/InstructionSimplify.cpp
===================================================================
--- llvm/lib/Analysis/InstructionSimplify.cpp
+++ llvm/lib/Analysis/InstructionSimplify.cpp
@@ -2849,6 +2849,59 @@
   return nullptr;
 }
 
+
+static bool NoOverFlow(CmpInst::Predicate Pred, bool NoLHSWrapProblem,
+    bool NoRHSWrapProblem, Value *A, Value *B, Value *C, Value *D){
+  // It's safe if both operands have NSW set.
+  if (NoLHSWrapProblem && NoRHSWrapProblem)
+    return true;
+
+  // TODO: only support icmp slt for now.
+  if (Pred != CmpInst::ICMP_SLT)
+    return false;
+
+  // If only one of 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.
+
+  if (!NoRHSWrapProblem)
+    return false;
+
+  ConstantInt *CA = dyn_cast<ConstantInt>(A);
+  ConstantInt *CB = dyn_cast<ConstantInt>(B);
+  ConstantInt *CC = dyn_cast<ConstantInt>(C);
+  ConstantInt *CD = dyn_cast<ConstantInt>(D);
+
+  // C + B == C + D  ->  B == D
+  if (A == C && CB && CD && CB->getValue().isNonNegative() &&
+      CB->getValue().slt(CD->getValue()))
+    return true;
+
+  // D + B == C + D  ->  B == C
+  if (A == D && CB && CC && CB->getValue().isNonNegative() &&
+      CB->getValue().slt(CC->getValue()))
+    return true;
+
+  // A + C == C + D  ->  A == D
+  if (B == C && CA && CD && CA->getValue().isNonNegative() &&
+      CA->getValue().slt(CD->getValue()))
+    return true;
+
+  // A + D == C + D  ->  A == C
+  if (B == D && CA && CC && CA->getValue().isNonNegative() &&
+      CA->getValue().slt(CC->getValue()))
+    return true;
+
+  return false;
+}
+
+
 /// 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 +2951,8 @@
         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) {
+    if (A && C && (A == C || A == D || B == C || B == D) &&
+        NoOverFlow(Pred, NoLHSWrapProblem, NoRHSWrapProblem, A, B, C, D)) {
       // 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
@@ -1715,12 +1715,7 @@
 
 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
@@ -1834,4 +1826,18 @@
   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 }