Index: llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/include/llvm/Analysis/ScalarEvolution.h +++ llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1200,11 +1200,9 @@ /// Simplify LHS and RHS in a comparison with predicate Pred. Return true /// iff any changes were made. If the operands are provably equal or /// unequal, LHS and RHS are set to the same value and Pred is set to either - /// ICMP_EQ or ICMP_NE. ControllingFiniteLoop is set if this comparison - /// controls the exit of a loop known to have a finite number of iterations. + /// ICMP_EQ or ICMP_NE. bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, - const SCEV *&RHS, unsigned Depth = 0, - bool ControllingFiniteLoop = false); + const SCEV *&RHS, unsigned Depth = 0); /// Return the "disposition" of the given SCEV with respect to the given /// loop. Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -9089,9 +9089,7 @@ bool ControllingFiniteLoop = ControlsExit && loopHasNoAbnormalExits(L) && loopIsFiniteByAssumption(L); // Simplify the operands before analyzing them. - (void)SimplifyICmpOperands(Pred, LHS, RHS, /*Depth=*/0, - (EnableFiniteLoopControl ? ControllingFiniteLoop - : false)); + (void)SimplifyICmpOperands(Pred, LHS, RHS, /*Depth=*/0); // If we have a comparison of a chrec against a constant, try to use value // ranges to answer this query. @@ -9164,17 +9162,35 @@ if (EL.hasAnyInfo()) return EL; break; } + case ICmpInst::ICMP_SLE: + case ICmpInst::ICMP_ULE: + // Since the loop is finite, an invariant RHS cannot include the boundary + // value, otherwise it would loop forever. + if (!EnableFiniteLoopControl || !ControllingFiniteLoop || + !isLoopInvariant(RHS, L)) + break; + RHS = getAddExpr(getOne(RHS->getType()), RHS); + [[fallthrough]]; case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_ULT: { // while (X < Y) - bool IsSigned = Pred == ICmpInst::ICMP_SLT; + bool IsSigned = ICmpInst::isSigned(Pred); ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsExit, AllowPredicates); if (EL.hasAnyInfo()) return EL; break; } + case ICmpInst::ICMP_SGE: + case ICmpInst::ICMP_UGE: + // Since the loop is finite, an invariant RHS cannot include the boundary + // value, otherwise it would loop forever. + if (!EnableFiniteLoopControl || !ControllingFiniteLoop || + !isLoopInvariant(RHS, L)) + break; + RHS = getAddExpr(getMinusOne(RHS->getType()), RHS); + [[fallthrough]]; case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_UGT: { // while (X > Y) - bool IsSigned = Pred == ICmpInst::ICMP_SGT; + bool IsSigned = ICmpInst::isSigned(Pred); ExitLimit EL = howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsExit, AllowPredicates); @@ -10570,8 +10586,7 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, const SCEV *&RHS, - unsigned Depth, - bool ControllingFiniteLoop) { + unsigned Depth) { bool Changed = false; // Simplifies ICMP to trivial true or false by turning it into '0 == 0' or // '0 != 0'. @@ -10700,15 +10715,10 @@ } // If possible, canonicalize GE/LE comparisons to GT/LT comparisons, by - // adding or subtracting 1 from one of the operands. This can be done for - // one of two reasons: - // 1) The range of the RHS does not include the (signed/unsigned) boundaries - // 2) The loop is finite, with this comparison controlling the exit. Since the - // loop is finite, the bound cannot include the corresponding boundary - // (otherwise it would loop forever). + // adding or subtracting 1 from one of the operands. switch (Pred) { case ICmpInst::ICMP_SLE: - if (ControllingFiniteLoop || !getSignedRangeMax(RHS).isMaxSignedValue()) { + if (!getSignedRangeMax(RHS).isMaxSignedValue()) { RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, SCEV::FlagNSW); Pred = ICmpInst::ICMP_SLT; @@ -10721,7 +10731,7 @@ } break; case ICmpInst::ICMP_SGE: - if (ControllingFiniteLoop || !getSignedRangeMin(RHS).isMinSignedValue()) { + if (!getSignedRangeMin(RHS).isMinSignedValue()) { RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS, SCEV::FlagNSW); Pred = ICmpInst::ICMP_SGT; @@ -10734,7 +10744,7 @@ } break; case ICmpInst::ICMP_ULE: - if (ControllingFiniteLoop || !getUnsignedRangeMax(RHS).isMaxValue()) { + if (!getUnsignedRangeMax(RHS).isMaxValue()) { RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, SCEV::FlagNUW); Pred = ICmpInst::ICMP_ULT; @@ -10746,7 +10756,7 @@ } break; case ICmpInst::ICMP_UGE: - if (ControllingFiniteLoop || !getUnsignedRangeMin(RHS).isMinValue()) { + if (!getUnsignedRangeMin(RHS).isMinValue()) { RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS); Pred = ICmpInst::ICMP_UGT; Changed = true; @@ -10766,8 +10776,7 @@ // Recursively simplify until we either hit a recursion limit or nothing // changes. if (Changed) - return SimplifyICmpOperands(Pred, LHS, RHS, Depth + 1, - ControllingFiniteLoop); + return SimplifyICmpOperands(Pred, LHS, RHS, Depth + 1); return Changed; } Index: llvm/test/Analysis/ScalarEvolution/finite-trip-count.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/finite-trip-count.ll +++ llvm/test/Analysis/ScalarEvolution/finite-trip-count.ll @@ -9,10 +9,10 @@ define void @SLE(i32 %len) willreturn { ; CHECK-LABEL: 'SLE' ; CHECK-NEXT: Determining loop execution counts for: @SLE -; CHECK-NEXT: Loop %for.body: backedge-taken count is (0 smax (1 + %len)) +; CHECK-NEXT: Loop %for.body: backedge-taken count is (0 smax (1 + %len)) ; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is 2147483647 -; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (0 smax (1 + %len)) -; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (0 smax (1 + %len)) +; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (0 smax (1 + %len)) +; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (0 smax (1 + %len)) ; CHECK-NEXT: Predicates: ; CHECK: Loop %for.body: Trip multiple is 1 ; @@ -55,10 +55,10 @@ define void @ULE(i32 %len) willreturn { ; CHECK-LABEL: 'ULE' ; CHECK-NEXT: Determining loop execution counts for: @ULE -; CHECK-NEXT: Loop %for.body: backedge-taken count is (1 + %len) +; CHECK-NEXT: Loop %for.body: backedge-taken count is (1 + %len) ; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is -1 -; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (1 + %len) -; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (1 + %len) +; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (1 + %len) +; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (1 + %len) ; CHECK-NEXT: Predicates: ; CHECK: Loop %for.body: Trip multiple is 1 ; @@ -101,10 +101,10 @@ define void @SGE(i32 %end) willreturn { ; CHECK-LABEL: 'SGE' ; CHECK-NEXT: Determining loop execution counts for: @SGE -; CHECK-NEXT: Loop %for.body: backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)))) +; CHECK-NEXT: Loop %for.body: backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)))) ; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is -2147483548 -; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)))) -; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)))) +; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)))) +; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)))) ; CHECK-NEXT: Predicates: ; CHECK: Loop %for.body: Trip multiple is 1 ; @@ -190,14 +190,13 @@ ret void } -; FIXME: It would be better to compute ((-2 + %n) /u 2) as trip count here. define void @pr54191(i64 %n) mustprogress { ; CHECK-LABEL: 'pr54191' ; CHECK-NEXT: Determining loop execution counts for: @pr54191 -; CHECK-NEXT: Loop %loop: backedge-taken count is ((-3 + (4 smax (1 + %n))) /u 2) -; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 4611686018427387901 -; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-3 + (4 smax (1 + %n))) /u 2) -; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-3 + (4 smax (1 + %n))) /u 2) +; CHECK-NEXT: Loop %loop: backedge-taken count is ((-2 + %n) /u 2) +; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 4611686018427387902 +; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-2 + %n) /u 2) +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-2 + %n) /u 2) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 ; Index: llvm/test/Transforms/IndVarSimplify/pr60944.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/pr60944.ll +++ llvm/test/Transforms/IndVarSimplify/pr60944.ll @@ -3,7 +3,6 @@ @x = global i32 0 -; FIXME: This is a miscompile. ; %loop2 is never entered and we cannot derive any fact about %iv from it. define i32 @main(i32 %iv.start, i32 %arg2) mustprogress { ; CHECK-LABEL: define i32 @main @@ -21,7 +20,8 @@ ; CHECK-NEXT: br label [[LOOP_LATCH]] ; CHECK: loop.latch: ; CHECK-NEXT: [[IV_NEXT]] = sdiv i32 [[ARG2]], [[IV]] -; CHECK-NEXT: br i1 false, label [[LOOP_EXIT:%.*]], label [[LOOP]] +; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i32 [[IV]], -1 +; CHECK-NEXT: br i1 [[CMP2]], label [[LOOP_EXIT:%.*]], label [[LOOP]] ; CHECK: loop.exit: ; CHECK-NEXT: [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[LOOP_LATCH]] ] ; CHECK-NEXT: ret i32 [[IV_NEXT_LCSSA]] Index: llvm/test/Transforms/IndVarSimplify/range-iter-threshold.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/range-iter-threshold.ll +++ llvm/test/Transforms/IndVarSimplify/range-iter-threshold.ll @@ -1,37 +1,35 @@ -; RUN: opt -passes=indvars -S %s | FileCheck --check-prefix=COMMON --check-prefix=DEFAULT %s -; RUN: opt -passes=indvars -scev-range-iter-threshold=1 -S %s | FileCheck --check-prefix=COMMON --check-prefix=LIMIT %s +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2 +; RUN: opt -passes=indvars -S %s | FileCheck --check-prefix=COMMON %s +; RUN: opt -passes=indvars -scev-range-iter-threshold=1 -S %s | FileCheck --check-prefix=COMMON %s target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" define i32 @test(i1 %c.0, i32 %m) { -; COMMON-LABEL: @test( +; COMMON-LABEL: define i32 @test +; COMMON-SAME: (i1 [[C_0:%.*]], i32 [[M:%.*]]) { ; COMMON-NEXT: entry: ; COMMON-NEXT: br label [[OUTER_HEADER:%.*]] ; COMMON: outer.header: -; COMMON-NEXT: [[INDVARS_IV1:%.*]] = phi i64 [ [[INDVARS_IV_NEXT2:%.*]], [[OUTER_LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ] -; DEFAULT-NEXT: [[INDVARS_IV:%.*]] = phi i32 [ [[INDVARS_IV_NEXT:%.*]], [[OUTER_LATCH]] ], [ 2, [[ENTRY]] ] -; COMMON-NEXT: [[IV_1:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_1_NEXT:%.*]], [[OUTER_LATCH]] ] +; COMMON-NEXT: [[IV_1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[OUTER_LATCH:%.*]] ] ; COMMON-NEXT: [[MAX_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[MAX_1:%.*]], [[OUTER_LATCH]] ] +; COMMON-NEXT: [[TMP0:%.*]] = sext i32 [[IV_1]] to i64 ; COMMON-NEXT: br label [[INNER_1:%.*]] ; COMMON: inner.1: -; COMMON-NEXT: [[C_1:%.*]] = icmp ult i64 0, [[INDVARS_IV1]] +; COMMON-NEXT: [[C_1:%.*]] = icmp slt i64 0, [[TMP0]] ; COMMON-NEXT: br i1 [[C_1]], label [[INNER_1]], label [[INNER_2_HEADER_PREHEADER:%.*]] ; COMMON: inner.2.header.preheader: ; COMMON-NEXT: br label [[INNER_2_HEADER:%.*]] ; COMMON: inner.2.header: ; COMMON-NEXT: [[IV_3:%.*]] = phi i32 [ [[IV_3_NEXT:%.*]], [[INNER_2_LATCH:%.*]] ], [ 0, [[INNER_2_HEADER_PREHEADER]] ] -; COMMON-NEXT: br i1 [[C_0:%.*]], label [[OUTER_LATCH]], label [[INNER_2_LATCH]] +; COMMON-NEXT: br i1 [[C_0]], label [[OUTER_LATCH]], label [[INNER_2_LATCH]] ; COMMON: inner.2.latch: ; COMMON-NEXT: [[IV_3_NEXT]] = add i32 [[IV_3]], 1 -; DEFAULT-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[IV_3_NEXT]], [[INDVARS_IV]] -; LIMIT-NEXT: [[EXITCOND:%.*]] = icmp ugt i32 [[IV_3]], [[IV_1]] -; COMMON-NEXT: br i1 [[EXITCOND]], label [[OUTER_LATCH]], label [[INNER_2_HEADER]] +; COMMON-NEXT: [[C_2:%.*]] = icmp ugt i32 [[IV_3]], [[IV_1]] +; COMMON-NEXT: br i1 [[C_2]], label [[OUTER_LATCH]], label [[INNER_2_HEADER]] ; COMMON: outer.latch: -; COMMON-NEXT: [[MAX_1]] = phi i32 [ [[M:%.*]], [[INNER_2_LATCH]] ], [ 0, [[INNER_2_HEADER]] ] -; COMMON-NEXT: [[INDVARS_IV_NEXT2]] = add nuw nsw i64 [[INDVARS_IV1]], 1 -; COMMON-NEXT: [[IV_1_NEXT]] = add nuw i32 [[IV_1]], 1 +; COMMON-NEXT: [[MAX_1]] = phi i32 [ [[M]], [[INNER_2_LATCH]] ], [ 0, [[INNER_2_HEADER]] ] +; COMMON-NEXT: [[IV_1_NEXT]] = add i32 [[IV_1]], 1 ; COMMON-NEXT: [[C_3:%.*]] = icmp ugt i32 [[IV_1]], [[MAX_0]] -; DEFAULT-NEXT: [[INDVARS_IV_NEXT]] = add i32 [[INDVARS_IV]], 1 ; COMMON-NEXT: br i1 [[C_3]], label [[EXIT:%.*]], label [[OUTER_HEADER]], !llvm.loop [[LOOP0:![0-9]+]] ; COMMON: exit: ; COMMON-NEXT: ret i32 0 Index: llvm/test/Transforms/IndVarSimplify/rewrite-loop-exit-value.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/rewrite-loop-exit-value.ll +++ llvm/test/Transforms/IndVarSimplify/rewrite-loop-exit-value.ll @@ -169,9 +169,9 @@ ; CHECK-NEXT: [[CMP_NOT:%.*]] = icmp sgt i16 [[MUL]], [[END:%.*]] ; CHECK-NEXT: br i1 [[CMP_NOT]], label [[CRIT_EDGE:%.*]], label [[FOR_BODY]] ; CHECK: crit_edge: -; CHECK-NEXT: [[TMP0:%.*]] = call i16 @llvm.smax.i16(i16 [[END]], i16 -1) -; CHECK-NEXT: [[SMAX:%.*]] = add nsw i16 [[TMP0]], 1 -; CHECK-NEXT: [[TMP1:%.*]] = icmp ne i16 [[SMAX]], 0 +; CHECK-NEXT: [[TMP0:%.*]] = add i16 [[END]], 1 +; CHECK-NEXT: [[SMAX:%.*]] = call i16 @llvm.smax.i16(i16 [[TMP0]], i16 0) +; CHECK-NEXT: [[TMP1:%.*]] = icmp ult i16 [[END]], 32767 ; CHECK-NEXT: [[UMIN:%.*]] = zext i1 [[TMP1]] to i16 ; CHECK-NEXT: [[TMP2:%.*]] = sub nsw i16 [[SMAX]], [[UMIN]] ; CHECK-NEXT: [[UMAX:%.*]] = call i16 @llvm.umax.i16(i16 [[M]], i16 1)