Author: Yingwei Zheng Date: 2025-03-18T15:59:51-07:00 New Revision: 2cc53628fbe88d00c8f54bfd54530330f191ebfc
URL: https://github.com/llvm/llvm-project/commit/2cc53628fbe88d00c8f54bfd54530330f191ebfc DIFF: https://github.com/llvm/llvm-project/commit/2cc53628fbe88d00c8f54bfd54530330f191ebfc.diff LOG: [SCEV] Check whether the start is non-zero in `ScalarEvolution::howFarToZero` (#131522) https://github.com/llvm/llvm-project/pull/94525 assumes that the loop will be infinite when the stride is zero. However, it doesn't hold when the start value of addrec is also zero. Closes https://github.com/llvm/llvm-project/issues/131465. (cherry picked from commit c5a491e9ea22014b65664b6e09134b4f055933e2) Added: llvm/test/Transforms/LoopUnroll/pr131465.ll Modified: llvm/lib/Analysis/ScalarEvolution.cpp llvm/test/Analysis/ScalarEvolution/trip-count-unknown-stride.ll Removed: ################################################################################ diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index c71202c8dd58e..b8069df4e6598 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -10635,10 +10635,11 @@ ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(const SCEV *V, if (ControlsOnlyExit && AddRec->hasNoSelfWrap() && loopHasNoAbnormalExits(AddRec->getLoop())) { - // If the stride is zero, the loop must be infinite. In C++, most loops - // are finite by assumption, in which case the step being zero implies - // UB must execute if the loop is entered. - if (!loopIsFiniteByAssumption(L) && !isKnownNonZero(StepWLG)) + // If the stride is zero and the start is non-zero, the loop must be + // infinite. In C++, most loops are finite by assumption, in which case the + // step being zero implies UB must execute if the loop is entered. + if (!(loopIsFiniteByAssumption(L) && isKnownNonZero(Start)) && + !isKnownNonZero(StepWLG)) return getCouldNotCompute(); const SCEV *Exact = diff --git a/llvm/test/Analysis/ScalarEvolution/trip-count-unknown-stride.ll b/llvm/test/Analysis/ScalarEvolution/trip-count-unknown-stride.ll index 2d02cb6194f4c..1f08a620b2e15 100644 --- a/llvm/test/Analysis/ScalarEvolution/trip-count-unknown-stride.ll +++ b/llvm/test/Analysis/ScalarEvolution/trip-count-unknown-stride.ll @@ -329,10 +329,9 @@ define void @ne_nsw_nonneg_step(ptr nocapture %A, i32 %n, i32 %s) mustprogress { ; ; CHECK-LABEL: 'ne_nsw_nonneg_step' ; CHECK-NEXT: Determining loop execution counts for: @ne_nsw_nonneg_step -; CHECK-NEXT: Loop %for.body: backedge-taken count is (((-1 * %s) + %n) /u %s) -; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 -1 -; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (((-1 * %s) + %n) /u %s) -; CHECK-NEXT: Loop %for.body: Trip multiple is 1 +; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. +; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. +; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. ; entry: %nonneg_step = icmp sge i32 %s, 0 @@ -442,10 +441,9 @@ define void @ne_nuw_nonneg_step(ptr nocapture %A, i32 %n, i32 %s) mustprogress { ; ; CHECK-LABEL: 'ne_nuw_nonneg_step' ; CHECK-NEXT: Determining loop execution counts for: @ne_nuw_nonneg_step -; CHECK-NEXT: Loop %for.body: backedge-taken count is (((-1 * %s) + %n) /u %s) -; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 -1 -; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (((-1 * %s) + %n) /u %s) -; CHECK-NEXT: Loop %for.body: Trip multiple is 1 +; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. +; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. +; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. ; entry: %nonneg_step = icmp sge i32 %s, 0 @@ -493,6 +491,26 @@ for.end: ; preds = %for.body, %entry ret void } +define i32 @pr131465(i1 %x) mustprogress { +; CHECK-LABEL: 'pr131465' +; CHECK-NEXT: Determining loop execution counts for: @pr131465 +; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. +; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. +; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. +; +entry: + %inc = zext i1 %x to i32 + br label %for.body + +for.body: + %indvar = phi i32 [ 2, %entry ], [ %next, %for.body ] + %next = add nsw i32 %indvar, %inc + %exitcond = icmp eq i32 %next, 2 + br i1 %exitcond, label %for.end, label %for.body + +for.end: + ret i32 0 +} declare void @llvm.assume(i1) diff --git a/llvm/test/Transforms/LoopUnroll/pr131465.ll b/llvm/test/Transforms/LoopUnroll/pr131465.ll new file mode 100644 index 0000000000000..643b020c6c110 --- /dev/null +++ b/llvm/test/Transforms/LoopUnroll/pr131465.ll @@ -0,0 +1,43 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5 +; RUN: opt -S -passes=loop-unroll -unroll-runtime %s | FileCheck %s + +define i32 @pr131465(i1 %x) mustprogress { +; CHECK-LABEL: define i32 @pr131465( +; CHECK-SAME: i1 [[X:%.*]]) #[[ATTR0:[0-9]+]] { +; CHECK-NEXT: [[ENTRY:.*]]: +; CHECK-NEXT: [[INC:%.*]] = zext i1 [[X]] to i32 +; CHECK-NEXT: br label %[[FOR_BODY:.*]] +; CHECK: [[FOR_BODY]]: +; CHECK-NEXT: [[INDVAR:%.*]] = phi i32 [ 2, %[[ENTRY]] ], [ [[NEXT_1:%.*]], %[[FOR_BODY_1:.*]] ] +; CHECK-NEXT: [[NEXT:%.*]] = add nsw i32 [[INDVAR]], [[INC]] +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[NEXT]], 2 +; CHECK-NEXT: br i1 [[EXITCOND]], label %[[FOR_END:.*]], label %[[FOR_BODY_1]], !llvm.loop [[LOOP0:![0-9]+]] +; CHECK: [[FOR_BODY_1]]: +; CHECK-NEXT: [[NEXT_1]] = add nsw i32 [[NEXT]], [[INC]] +; CHECK-NEXT: [[EXITCOND_1:%.*]] = icmp eq i32 [[NEXT_1]], 2 +; CHECK-NEXT: br i1 [[EXITCOND_1]], label %[[FOR_END]], label %[[FOR_BODY]], !llvm.loop [[LOOP2:![0-9]+]] +; CHECK: [[FOR_END]]: +; CHECK-NEXT: ret i32 0 +; +entry: + %inc = zext i1 %x to i32 + br label %for.body + +for.body: + %indvar = phi i32 [ 2, %entry ], [ %next, %for.body ] + %next = add nsw i32 %indvar, %inc + %exitcond = icmp eq i32 %next, 2 + br i1 %exitcond, label %for.end, label %for.body, !llvm.loop !0 + +for.end: + ret i32 0 +} + +; Force runtime unrolling. +!0 = !{!0, !{!"llvm.loop.unroll.count", i32 2}} +;. +; CHECK: [[LOOP0]] = distinct !{[[LOOP0]], [[META1:![0-9]+]]} +; CHECK: [[META1]] = !{!"llvm.loop.unroll.count", i32 2} +; CHECK: [[LOOP2]] = distinct !{[[LOOP2]], [[META3:![0-9]+]]} +; CHECK: [[META3]] = !{!"llvm.loop.unroll.disable"} +;. _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
