[SCEV]When safe, compute MinStart as unsigned_min(Start - Stride) + Stride in computeMaxBECountForLT

[zzheng]

Summary

https://bugs.llvm.org/show_bug.cgi?id=42175

$ cat loop-small-runtime-upperbound.ll

target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"

@global = dso_local local_unnamed_addr global i32 0, align 4
@global.1 = dso_local local_unnamed_addr global i8* null, align 4

define dso_local void @hoge(i8 %arg) {
entry:
  %x = load i32, i32* @global, align 4
  %0 = icmp ult i32 %x, 17
  br i1 %0, label %loop, label %exit

loop:
  %iv = phi i32 [ %x, %entry ], [ %iv.next, %loop ]
  %iv.next = add nuw i32 %iv, 8
  %1 = load i8*, i8** @global.1, align 4
  %2 = getelementptr inbounds i8, i8* %1, i32 1
  store i8* %2, i8** @global.1, align 4
  store i8 %arg, i8* %1, align 1
  %3 = icmp ult i32 %iv.next, 17
  br i1 %3, label %loop, label %exit

exit:                                             ; preds = %bb12, %bb
  ret void
}

$ opt loop-small-runtime-upperbound.ll -analyze -scalar-evolution
...

The loop runs a max of 3 iters, but SCEV computes max BE-taken count as 3.
The same issue is also found in test/Analysis/ScalarEvolution/2008-11-18-Stride2.ll, where max BE-taken count is 333 instead of 334.

In computeMaxBECountForLT(), when Start is a (C + %x), where C is a constant and %x is an unknown, getUnsignedRangeMin(Start) returns full-set because of %x.
But loop entry is guarded by:

%0 = icmp ult i32 %x, 17

so x is known in [0, 17), thus MinStart shall be C rather than 0.

[zzheng]

re-upload with full context

[efriedma]

lib/Analysis/ScalarEvolution.cpp

10451

If I'm following correctly, this is sort of similar to what we do in ScalarEvolution::howFarToZero: If Start - Stride doesn't overflow, instead of querying unsigned_min(Start) directly, we can use unsigned_min(Start - Stride) + Stride instead.

It looks like this is actually computing unsigned_min(Start) + Stride, though, which I don't think is correct.

It's not obvious to me that the case where Stride is not a constant (so it's actually unsigned_min(Start - Stride) + unsigned_min(Stride)) works the same way as the case where Stride is a constant, although it seems plausible.

[zzheng]

ping?

[efriedma]

Is the isLoopEntryGuardedByCond actually proving what you need it to prove? Even if Start-Stride is in the range [0, End), that doesn't necessarily imply Start-Stride doesn't overflow. For example, suppose Start is 0, End is -1, and Stride is 2.

I guess if we prove both Stride and End are nonnegative, it's okay.

[efriedma]

I think this is sound now.

Could you add some test coverage for the cases we don't and/or can't transform? Maybe also a test where "end" is known-positive, but not constant.

lib/Analysis/ScalarEvolution.cpp

10460

Probably easier to understand the C form of the loop, at first glance: for (unsigned i = start; i < 17; i += 8) { [...] }

10473

cast<>

test/Analysis/ScalarEvolution/2008-11-18-Stride2.ll

8

Fix this comment?

[reames]

I may be missing the obvious, but the code as written appears to be assuming the post-increment form of the induction variable is passed in, not the pre-increment form. What ensures that?

If I'm reading this right, you're basically trying to get a more specific range for Start, using the fact proved by the loop entry guard right? I've seen such cases come up several times recently in things I've worked on, maybe it's time to add a getUnsignedRangeAtScope(SCEV, Loop) variant? (Just as we have a getSCEVAtScope)

[zzheng]

Added new test

[zzheng]

For the case in this issue, Start and L are not enough, we also need Stride, to calculate correct MinStart, requiring getUnsignedRangeAtScope() take to SCEV* parameters, I think it's a little confusing.

[zzheng]

test/Analysis/ScalarEvolution/pr42175-MaxBECountForULT.ll

62 ↗

(On Diff #211336)

@reames , is this pre-increment form of IV you are concerned? This case isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULT, (Start-Stride), End) returns false.

[zzheng]

ping?

[zzheng]

rebased moved to monorepo

include/llvm/Analysis/ScalarEvolution.h

private:
   /// Compute the maximum backedge count based on the range of values
   /// permitted by Start, End, and Stride. This is for loops of the form
   /// {Start, +, Stride} LT End.
   ///
   /// Precondition: the induction variable is known to be positive.  We *don't*
   /// 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,
   /// the stride and the knowledge of NSW/NUW flags on the recurrence.
   bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
                           bool NoWrap);
 
   /// Verify if an linear IV with negative stride can overflow when in a

lib/Analysis/ScalarEvolution.cpp

Delta = Equality ? getAddExpr(Delta, Step)
                    : getAddExpr(Delta, getMinusSCEV(Step, One));
   return getUDivExpr(Delta, Step);
 }
 
 const SCEV *ScalarEvolution::computeMaxBECountForLT(const SCEV *Start,
                                                     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
   // permitted by Start, End, and Stride.
   const SCEV *MaxBECount;
   APInt MinStart =
       IsSigned ? getSignedRangeMin(Start) : getUnsignedRangeMin(Start);
 
+  // If loop entry is guarded by an ULT, with a constant Stride, we know
+  // (Start-Stride) is in [0, End).
+  auto *S = getMinusSCEV(Start, Stride);
+  if (!IsSigned && isa<SCEVConstant>(Stride) && isLoopInvariant(End, L) &&
+      isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULT, S, End))
+    MinStart = getUnsignedRangeMin(S) +
+               dyn_cast<SCEVConstant>(Stride)->getAPInt();
+
   APInt StrideForMaxBECount =
       IsSigned ? getSignedRangeMin(Stride) : getUnsignedRangeMin(Stride);
 
   // We already know that the stride is positive, so we paper over conservatism
   // in our range computation by forcing StrideForMaxBECount to be at least one.
   // In theory this is unnecessary, but we expect MaxBECount to be a
   // SCEVConstant, and (udiv <constant> 0) is not constant folded by SCEV (there
   // is nothing to constant fold it to).
   APInt One(BitWidth, 1, IsSigned);
   StrideForMaxBECount = APIntOps::smax(One, StrideForMaxBECount);
 
   APInt MaxValue = IsSigned ? APInt::getSignedMaxValue(BitWidth)
                             : APInt::getMaxValue(BitWidth);
   APInt Limit = MaxValue - (StrideForMaxBECount - 1);
 
   // Although End can be a MAX expression we estimate MaxEnd considering only
   // the case End = RHS of the loop termination condition. This is safe because
   // in the other case (End - Start) is zero, leading to a zero maximum backedge
   // taken count.
   APInt MaxEnd = IsSigned ? APIntOps::smin(getSignedRangeMax(End), Limit)
                           : APIntOps::umin(getUnsignedRangeMax(End), Limit);
 
   MaxBECount = computeBECount(getConstant(MaxEnd - MinStart) /* Delta */,
                               getConstant(StrideForMaxBECount) /* Step */,
                               false /* Equality */);
 
   return MaxBECount;
ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
   const SCEV *End = RHS;
   // When the RHS is not invariant, we do not know the end bound of the loop and
   // cannot calculate the ExactBECount needed by ExitLimit. However, we can
   // calculate the MaxBECount, given the start, stride and max value for the end
   // bound of the loop (RHS), and the fact that IV does not overflow (which is
   // 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);
   }
   // If the backedge is taken at least once, then it will be taken
   // (End-Start)/Stride times (rounded up to a multiple of Stride), where Start
   // is the LHS value of the less-than comparison the first time it is evaluated
   // and End is the RHS.
   const SCEV *BECountIfBackedgeTaken =
ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
   else if (isa<SCEVConstant>(BECountIfBackedgeTaken)) {
     // If we know exactly how many times the backedge will be taken if it's
     // taken at least once, then the backedge count will either be that or
     // zero.
     MaxBECount = BECountIfBackedgeTaken;
     MaxOrZero = true;
   } else {
     MaxBECount = computeMaxBECountForLT(
-        Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned);
+        Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned, L);
   }
 
   if (isa<SCEVCouldNotCompute>(MaxBECount) &&
       !isa<SCEVCouldNotCompute>(BECount))
     MaxBECount = getConstant(getUnsignedRangeMax(BECount));
 
   return ExitLimit(BECount, MaxBECount, MaxOrZero, Predicates);
 }

test/Analysis/ScalarEvolution/2008-11-18-Stride2.ll

 ; 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.
 
 define i32 @f(i32 %x) nounwind readnone {
 entry:
   %0 = icmp ugt i32 %x, 999    ; <i1> [#uses=1]
   br i1 %0, label %bb2, label %bb.nph
 
 bb.nph:   ; preds = %entry
   br label %bb