Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ 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(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 Index: llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll +++ 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: