[SCEV] Replace assert with returning CouldNotComp in computeMaxBECountForLT.

[fhahn]

Summary

This patch removes the bail out for signed predicates and non-positive
strides in howManyLessThans and updates computeMaxBECountForLT to return
SCEVCouldNotCompute for signed predicates with negative strides.

AFAICT bail-out was only added because computeMaxBECountForLT may not
handle negative signed strides correctly. Instead of not calling
computeMaxBECountForLT at all because we bail out earlier, we can
instead return SCEVCouldNotCompute in computeMaxBECountForLT.

The max backedge taken count will be computed as the max value of the
symbolic backedge taken count.

This improves precision in cases where we can compute symbolic backedge
taken counts and also fixes a crash.

Fixes #57818.

[fhahn]

ping :)

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::computeMaxBECountForLT(const SCEV *Start,
                                                     const SCEV *End,
                                                     unsigned BitWidth,
                                                     bool IsSigned) {
   // The logic in this function assumes we can represent a positive stride.
   // If we can't, the backedge-taken count must be zero.
   if (IsSigned && BitWidth == 1)
     return getZero(Stride->getType());
 
-  // This code has only been closely audited for negative strides in the
+  // This code below only been closely audited for negative strides in the
   // unsigned comparison case, it may be correct for signed comparison, but
   // that needs to be established.
-  assert((!IsSigned || !isKnownNonPositive(Stride)) &&
-         "Stride is expected strictly positive for signed case!");
+  if (IsSigned && isKnownNegative(Stride))
+    return getCouldNotCompute();
 
   // Calculate the maximum backedge count based on the range of values
   // permitted by Start, End, and Stride.
   APInt MinStart =
       IsSigned ? getSignedRangeMin(Start) : getUnsignedRangeMin(Start);
 
   APInt MinStride =
       IsSigned ? getSignedRangeMin(Stride) : getUnsignedRangeMin(Stride);
if (!PositiveStride) {
     //
     // The positive stride case is the same as isKnownPositive(Stride) returning
     // true (original behavior of the function).
     //
     if (PredicatedIV || !NoWrap || !loopIsFiniteByAssumption(L) ||
         !loopHasNoAbnormalExits(L))
       return getCouldNotCompute();
 
-    // This bailout is protecting the logic in computeMaxBECountForLT which
-    // has not yet been sufficiently auditted or tested with negative strides.
-    // We used to filter out all known-non-positive cases here, we're in the
-    // process of being less restrictive bit by bit.
-    if (IsSigned && isKnownNonPositive(Stride))
-      return getCouldNotCompute();
-
     if (!isKnownNonZero(Stride)) {
       // If we have a step of zero, and RHS isn't invariant in L, we don't know
       // if it might eventually be greater than start and if so, on which
       // iteration.  We can't even produce a useful upper bound.
       if (!isLoopInvariant(RHS, L))
         return getCouldNotCompute();
 
       // We allow a potentially zero stride, but we need to divide by stride

llvm/test/Analysis/ScalarEvolution/max-trip-count.ll

 exit:
   ret void
 }
 
 
 ; Max backedge-taken count is zero.
 define void @bool_stride(i1 %s, i1 %n) mustprogress {
 ; CHECK-LABEL: Determining loop execution counts for: @bool_stride
-; CHECK: Loop %loop: Unpredictable backedge-taken count.
-; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+; CHECK: Loop %loop: backedge-taken count is false
+; CHECK: Loop %loop: max backedge-taken count is false
 entry:
   br label %loop
 
 loop:
   %i = phi i1 [ -1, %entry ], [ %i.next, %loop ]
   %i.next = add nsw i1 %i, %s
   %t = icmp slt i1 %i.next, %n
   br i1 %t, label %loop, label %exit

llvm/test/Analysis/ScalarEvolution/trip-count-negative-stride.ll

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 define void @slt_129_unknown_start(i8 %start) mustprogress {
 ; CHECK-LABEL: 'slt_129_unknown_start'
 ; CHECK-NEXT:  Determining loop execution counts for: @slt_129_unknown_start
-; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (((127 + (-1 * (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))<nuw><nsw> + (-1 * %start) + (0 smax (-127 + %start)<nsw>)) /u -127) + (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 2
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (((127 + (-1 * (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))<nuw><nsw> + (-1 * %start) + (0 smax (-127 + %start)<nsw>)) /u -127) + (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.05 = phi i8 [ %add, %for.body ], [ %start, %entry ]
   %add = add nsw i8 %i.05, 129
   %cmp = icmp slt i8 %add, 0
for.body:                                         ; preds = %entry, %for.body
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 declare void @llvm.assume(i1)
 
+; Test case for PR57818.
+define void @step_is_neg_addrec_slt_8(i64 %n) {
+; CHECK-LABEL: 'step_is_neg_addrec_slt_8'
+; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_slt_8
+; CHECK-NEXT:  Loop %inner: backedge-taken count is (7 /u {0,+,-1}<nuw><nsw><%outer.header>)
+; CHECK-NEXT:  Loop %inner: max backedge-taken count is -2147483640
+; CHECK-NEXT:  Loop %inner: Predicated backedge-taken count is (7 /u {0,+,-1}<nuw><nsw><%outer.header>)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %inner: Trip multiple is 1
+; CHECK-NEXT:  Loop %outer.header: backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: max backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: Predicated backedge-taken count is 0
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %outer.header: Trip multiple is 1
+;
+entry:
+  br label %outer.header
+
+outer.header:
+  %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
+  %ec.1 = icmp eq i64 %outer.iv, 100
+  br i1 %ec.1, label %inner.ph, label %exit
+
+inner.ph:
+  %outer.trunc = trunc i64 %outer.iv to i32
+  br label %inner
+
+inner:
+  %inner.iv = phi i32 [ 0, %inner.ph ], [ %inner.iv.next, %inner ]
+  %inner.iv.next = add nsw i32 %inner.iv, %outer.trunc
+  %inner.c = icmp slt i32 %inner.iv.next, 8
+  br i1 %inner.c, label %inner, label %outer.latch, !llvm.loop !0
+
+outer.latch:
+  %outer.iv.next = add nsw i64 %outer.iv, -1
+  br label %outer.header
+
+exit:
+  ret void
+}
+
+define void @step_is_neg_addrec_slt_var(i32 %n) {
+; CHECK-LABEL: 'step_is_neg_addrec_slt_var'
+; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_slt_var
+; CHECK-NEXT:  Loop %inner: backedge-taken count is ((((-1 * (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))<nuw><nsw> + {0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n)) /u (1 umax {0,+,-1}<nuw><nsw><%outer.header>)) + (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))
+; CHECK-NEXT:  Loop %inner: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %inner: Predicated backedge-taken count is ((((-1 * (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))<nuw><nsw> + {0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n)) /u (1 umax {0,+,-1}<nuw><nsw><%outer.header>)) + (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %inner: Trip multiple is 1
+; CHECK-NEXT:  Loop %outer.header: backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: max backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: Predicated backedge-taken count is 0
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %outer.header: Trip multiple is 1
+;
+entry:
+  br label %outer.header
+
+outer.header:
+  %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
+  %ec.1 = icmp eq i64 %outer.iv, 100
+  br i1 %ec.1, label %inner.ph, label %exit
+
+inner.ph:
+  %outer.trunc = trunc i64 %outer.iv to i32
+  br label %inner
+
+inner:
+  %inner.iv = phi i32 [ 0, %inner.ph ], [ %inner.iv.next, %inner ]
+  %inner.iv.next = add nsw i32 %inner.iv, %outer.trunc
+  %inner.c = icmp slt i32 %inner.iv.next, %n
+  br i1 %inner.c, label %inner, label %outer.latch, !llvm.loop !0
+
+outer.latch:
+  %outer.iv.next = add nsw i64 %outer.iv, -1
+  br label %outer.header
+
+exit:
+  ret void
+}
+
+define void @step_is_neg_addrec_unknown_start(i32 %n) {
+; CHECK-LABEL: 'step_is_neg_addrec_unknown_start'
+; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_unknown_start
+; CHECK-NEXT:  Loop %inner: backedge-taken count is ((((-1 * (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))<nuw><nsw> + {(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>)) /u (1 umax {0,+,-1}<%outer.header>)) + (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))
+; CHECK-NEXT:  Loop %inner: max backedge-taken count is -2147483640
+; CHECK-NEXT:  Loop %inner: Predicated backedge-taken count is ((((-1 * (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))<nuw><nsw> + {(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>)) /u (1 umax {0,+,-1}<%outer.header>)) + (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %inner: Trip multiple is 1
+; CHECK-NEXT:  Loop %outer.header: backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: max backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: Predicated backedge-taken count is 0
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %outer.header: Trip multiple is 1
+;
+entry:
+  br label %outer.header
+
+outer.header:
+  %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
+  %ec.1 = icmp eq i64 %outer.iv, 100
+  br i1 %ec.1, label %inner.ph, label %exit
+
+inner.ph:
+  %outer.trunc = trunc i64 %outer.iv to i32
+  br label %inner
+
+inner:
+  %inner.iv = phi i32 [ %n, %inner.ph ], [ %inner.iv.next, %inner ]
+  %inner.iv.next = add nsw i32 %inner.iv, %outer.trunc
+  %inner.c = icmp slt i32 %inner.iv.next, 8
+  br i1 %inner.c, label %inner, label %outer.latch, !llvm.loop !0
+
+outer.latch:
+  %outer.iv.next = add nsw i64 %outer.iv, -1
+  br label %outer.header
+
+exit:
+  ret void
+}
 
+!0 = distinct !{!0, !1}
+!1 = !{!"llvm.loop.mustprogress"}