diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -2340,25 +2340,42 @@
   // Can we use context to prove the fact we need?
   if (!CtxI)
     return false;
-  // We can prove that add(x, constant) doesn't wrap if isKnownPredicateAt can
-  // guarantee that x <= max_int - constant at the given context.
-  // TODO: Support other operations.
-  if (BinOp != Instruction::Add)
+  // TODO: Support mul.
+  if (BinOp == Instruction::Mul)
     return false;
   auto *RHSC = dyn_cast<SCEVConstant>(RHS);
   // TODO: Lift this limitation.
   if (!RHSC)
     return false;
   APInt C = RHSC->getAPInt();
-  // TODO: Also lift this limitation.
-  if (Signed && C.isNegative())
-    return false;
   unsigned NumBits = C.getBitWidth();
-  APInt Max =
-      Signed ? APInt::getSignedMaxValue(NumBits) : APInt::getMaxValue(NumBits);
-  APInt Limit = Max - C;
+  bool IsSub = (BinOp == Instruction::Sub);
+  bool IsNegativeConst = (Signed && C.isNegative());
+  // Compute the direction and magnitude by which we need to check overflow.
+  bool OverflowDown = IsSub ^ IsNegativeConst;
+  APInt Magnitude = C;
+  if (IsNegativeConst) {
+    if (C == APInt::getSignedMinValue(NumBits))
+      // TODO: SINT_MIN on inversion gives the same negative value, we don't
+      // want to deal with that.
+      return false;
+    Magnitude = -C;
+  }
+
   ICmpInst::Predicate Pred = Signed ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
-  return isKnownPredicateAt(Pred, LHS, getConstant(Limit), CtxI);
+  if (OverflowDown) {
+    // To avoid overflow down, we need to make sure that MIN + Magnitude <= LHS.
+    APInt Min = Signed ? APInt::getSignedMinValue(NumBits)
+                       : APInt::getMinValue(NumBits);
+    APInt Limit = Min + Magnitude;
+    return isKnownPredicateAt(Pred, getConstant(Limit), LHS, CtxI);
+  } else {
+    // To avoid overflow up, we need to make sure that LHS <= MAX - Magnitude.
+    APInt Max = Signed ? APInt::getSignedMaxValue(NumBits)
+                       : APInt::getMaxValue(NumBits);
+    APInt Limit = Max - Magnitude;
+    return isKnownPredicateAt(Pred, LHS, getConstant(Limit), CtxI);
+  }
 }
 
 std::optional<SCEV::NoWrapFlags>
diff --git a/llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll b/llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll
--- a/llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll
+++ b/llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll
@@ -19,7 +19,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
@@ -68,7 +68,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
@@ -477,7 +477,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
@@ -528,7 +528,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
@@ -578,7 +578,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw i32 [[IV]], 1
 ; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
@@ -631,7 +631,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw nsw i64 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]]
@@ -685,7 +685,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw nsw i64 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]]
@@ -736,7 +736,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i64 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw i64 [[IV]], 1
 ; CHECK-NEXT:    [[NARROW:%.*]] = trunc i64 [[IV_NEXT]] to i32
 ; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp ult i32 [[NARROW]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]]
@@ -788,7 +788,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i64 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw i64 [[IV]], 1
 ; CHECK-NEXT:    [[NARROW:%.*]] = trunc i64 [[IV_NEXT]] to i32
 ; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp uge i32 [[NARROW]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label [[FAIL:%.*]], label [[BACKEDGE]]
@@ -842,7 +842,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
@@ -893,7 +893,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
@@ -943,7 +943,7 @@
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nuw i32 [[IV]], 1
 ; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge: