diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1843,7 +1843,7 @@ /// assert these preconditions so please be careful. const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride, const SCEV *End, unsigned BitWidth, - bool IsSigned); + bool IsSigned, const Loop *L); /// Verify if an linear IV with positive stride can overflow when in a /// less-than comparison, knowing the invariant term of the comparison, 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 @@ -10486,8 +10486,8 @@ const SCEV *Stride, const SCEV *End, unsigned BitWidth, - bool IsSigned) { - + bool IsSigned, + const Loop *L) { assert(!isKnownNonPositive(Stride) && "Stride is expected strictly positive!"); // Calculate the maximum backedge count based on the range of values @@ -10496,6 +10496,23 @@ APInt MinStart = IsSigned ? getSignedRangeMin(Start) : getUnsignedRangeMin(Start); + // In below loop: + // void foo (unsigned x, ...) { + // for (unsigned i=x; i<17; i+=8) {...} + // } + // Start is (%x + 8), Stride is 8, End is 17. Given that loop entry is guarded + // by ult %x, 17, we know %x is in [0, 17) if loop is entered, and min start + // shall be 8. + auto *S = getMinusSCEV(Start, Stride); + if (!IsSigned && isa(Stride) && isLoopInvariant(End, L) && + // Prove that (Start - Stride) is in [0, End) + isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULT, S, End) && + // Prove that (Start - Stride) doesn't overflow. + isKnownNonNegative(Stride) && isKnownNonNegative(End)) + // Compute MinStart as getUnsignedRangeMin(Start-Stride) + Stride. + MinStart = getUnsignedRangeMin(S) + + cast(Stride)->getAPInt(); + APInt StrideForMaxBECount = IsSigned ? getSignedRangeMin(Stride) : getUnsignedRangeMin(Stride); @@ -10619,7 +10636,7 @@ // checked above). if (!isLoopInvariant(RHS, L)) { const SCEV *MaxBECount = computeMaxBECountForLT( - Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned); + Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned, L); return ExitLimit(getCouldNotCompute() /* ExactNotTaken */, MaxBECount, false /*MaxOrZero*/, Predicates); } @@ -10656,7 +10673,7 @@ MaxOrZero = true; } else { MaxBECount = computeMaxBECountForLT( - Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned); + Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned, L); } if (isa(MaxBECount) && diff --git a/llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride2.ll b/llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride2.ll --- a/llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride2.ll +++ b/llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride2.ll @@ -1,11 +1,10 @@ ; RUN: opt < %s -analyze -scalar-evolution 2>&1 | FileCheck %s ; CHECK: Loop %bb: backedge-taken count is ((999 + (-1 * %x)) /u 3) -; CHECK: Loop %bb: max backedge-taken count is 334 +; CHECK: Loop %bb: max backedge-taken count is 333 -; This is a tricky testcase for unsigned wrap detection which ScalarEvolution -; doesn't yet know how to do. +; This is a tricky testcase for unsigned wrap detection define i32 @f(i32 %x) nounwind readnone { entry: diff --git a/llvm/test/Analysis/ScalarEvolution/pr42175-MaxBECountForULT.ll b/llvm/test/Analysis/ScalarEvolution/pr42175-MaxBECountForULT.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/ScalarEvolution/pr42175-MaxBECountForULT.ll @@ -0,0 +1,109 @@ +; RUN: opt -analyze -scalar-evolution %s | FileCheck %s +; Test different unsigned wrap scenarios in computeMaxBECountForLT() + +@global = dso_local local_unnamed_addr global i8 0, align 4 + +; unsigned i=x; +; do { +; ... +; i+=8; +; } while (i<17); +; Loop entry is not guarded by exit condition. +; CHECK-LABEL: @foo +; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + (17 umax (8 + %x))) /u 8) +; CHECK: Loop %loop: max backedge-taken count is 3 +define void @foo(i32 %x) { +entry: + br label %loop + +loop: + %iv = phi i32 [ %x, %entry ], [ %iv.next, %loop ] + %iv.next = add nuw i32 %iv, 8 + %cmp = icmp ult i32 %iv.next, 17 + br i1 %cmp, label %loop, label %exit + +exit: + ret void +} + +; for(unsigned i=x; i<17; i+=8) {...} +; Loop is is guarded by exit condition. +; CHECK-LABEL: @foo2 +; CHECK: Loop %loop: backedge-taken count is ((16 + (-1 * %x)) /u 8) +; CHECK: Loop %loop: max backedge-taken count is 2 +define void @foo2(i32 %x) { +entry: + %e = icmp ult i32 %x, 17 + br i1 %e, label %loop, label %exit + +loop: + %iv = phi i32 [ %x, %entry ], [ %iv.next, %loop ] + %iv.next = add nuw i32 %iv, 8 + %cmp = icmp ult i32 %iv.next, 17 + br i1 %cmp, label %loop, label %exit + +exit: + ret void +} + +; for(unsigned i=x; i<17; i+=8) {...} +; Loop is is guarded by exit condition. +; CHECK-LABEL: @foo3 +; CHECK: Loop %loop: backedge-taken count is ((7 + (-1 * %x) + (17 umax %x)) /u 8) +; CHECK: Loop %loop: max backedge-taken count is 3 + +define void @foo3(i32 %x) { +entry: + %e = icmp ult i32 %x, 17 + br i1 %e, label %loop, label %exit + +loop: + %iv = phi i32 [ %x, %entry ], [ %iv.next, %loop ] + %cmp = icmp ult i32 %iv, 17 + %iv.next = add nuw i32 %iv, 8 + br i1 %cmp, label %loop, label %exit + +exit: + ret void +} + +; y is loop invariant but not known non-negative. +; for(unsigned char i=x; i