Index: llvm/lib/Analysis/InstructionSimplify.cpp
===================================================================
--- llvm/lib/Analysis/InstructionSimplify.cpp
+++ llvm/lib/Analysis/InstructionSimplify.cpp
@@ -2849,6 +2849,55 @@
   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.
+
+  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->getSExtValue() <= CD->getSExtValue())
+    return true;
+
+  // D + B == C + D  ->  B == C
+  if (A == D && CB && CC && CB->getSExtValue() <= CC->getSExtValue())
+    return true;
+
+  // A + C == C + D  ->  A == D
+  if (B == C && CA && CD && CA->getSExtValue() <= CD->getSExtValue())
+    return true;
+
+  // A + D == C + D  ->  A == C
+  if (B == D && CA && CC && CA->getSExtValue() <= CC->getSExtValue())
+    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 +2947,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
@@ -1709,4 +1709,128 @@
   ret i1 %cmp
 }
 
+; 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.
+
+define i1 @icmp_nsw_1(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_1(
+; CHECK-NEXT:    ret i1 true
+;
+  %add5 = add i32 %V, 5
+  %add6 = add nsw i32 %V, 6
+  %s1 = sext i32 %add5 to i64
+  %s2 = sext i32 %add6 to i64
+  %cmp = icmp slt i64 %s1, %s2
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_2(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_2(
+; CHECK-NEXT:    ret i1 true
+;
+  %add5 = add i32 %V, 5
+  %add6 = add nsw i32 %V, 6
+  %cmp = icmp slt i32 %add5, %add6
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_3(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_3(
+; CHECK-NEXT:    ret i1 false
+;
+  %add5 = add i32 %V, 5
+  %add5_2 = add nsw i32 %V, 5
+  %cmp = icmp slt i32 %add5, %add5_2
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_4(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_4(
+; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 5
+; CHECK-NEXT:    [[ADD4:%.*]] = add nsw i32 [[V]], 4
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD4]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %add5 = add i32 %V, 5
+  %add4 = add nsw i32 %V, 4
+  %cmp = icmp slt i32 %add5, %add4
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_5(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_5(
+; 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_6(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_6(
+; 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_7(i32 %V, i32 %arg) {
+; CHECK-LABEL: @icmp_nsw_7(
+; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 5
+; CHECK-NEXT:    [[ADDARG:%.*]] = add nsw i32 [[V]], [[ARG:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADDARG]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %add5 = add i32 %V, 5
+  %addarg = add nsw i32 %V, %arg
+  %cmp = icmp slt i32 %add5, %addarg
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_8(i32 %V, i32 %arg) {
+; CHECK-LABEL: @icmp_nsw_8(
+; CHECK-NEXT:    [[ADDARG:%.*]] = add i32 [[V:%.*]], [[ARG:%.*]]
+; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 [[V]], 5
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADDARG]], [[ADD6]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %addarg = add i32 %V, %arg
+  %add6 = add nsw i32 %V, 5
+  %cmp = icmp slt i32 %addarg, %add6
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_9(i32 %V1, i32 %V2) {
+; CHECK-LABEL: @icmp_nsw_9(
+; CHECK-NEXT:    [[ADD_V1:%.*]] = add i32 [[V1:%.*]], 5
+; CHECK-NEXT:    [[ADD_V2:%.*]] = add nsw i32 [[V2:%.*]], 6
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD_V1]], [[ADD_V2]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %add_V1 = add i32 %V1, 5
+  %add_V2 = add nsw i32 %V2, 6
+  %cmp = icmp slt i32 %add_V1, %add_V2
+  ret i1 %cmp
+}
+
+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:    [[CMP:%.*]] = icmp sgt i32 [[ADD6]], [[ADD5]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %add5 = add i32 %V, 5
+  %add6 = add nsw i32 %V, 5
+  %cmp = icmp sgt i32 %add6, %add5
+  ret i1 %cmp
+}
+
 attributes #0 = { null_pointer_is_valid }