[ScalarEvolution] Fix pointer/int confusion in howManyLessThans.

[efriedma]

Summary

In general, howManyLessThans doesn't really want to work with pointers at all; the result is an integer, and the operands of the icmp are effectively integers. However, isLoopEntryGuardedByCond doesn't like extra ptrtoint casts, so the arguments to isLoopEntryGuardedByCond need to be computed without those casts.

Somehow, the values got mixed up with the recent howManyLessThans improvements; fix the confused values, and add a better comment to explain what's happening.

[reames]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
   //      1a) canIVOverflowOnLT, and b) step of one
   //   2) We can show that if overflow occurs, the loop must execute UB
   //      before any possible exit.
   // Note that we have not yet proved RHS invariant (in general).
 
   const SCEV *Start = IV->getStart();
 
   // Preserve pointer-typed Start/RHS to pass to isLoopEntryGuardedByCond.
-  // Use integer-typed versions for actual computation.
+  // If we convert to integers, isLoopEntryGuardedByCond will miss some cases.
+  // Use integer-typed versions for actual computation; we can't subtract
+  // pointers in general.
   const SCEV *OrigStart = Start;
   const SCEV *OrigRHS = RHS;
   if (Start->getType()->isPointerTy()) {
     Start = getLosslessPtrToIntExpr(Start);
     if (isa<SCEVCouldNotCompute>(Start))
       return Start;
   }
   if (RHS->getType()->isPointerTy()) {
return ExitLimit(getCouldNotCompute() /* ExactNotTaken */, MaxBECount,
                      false /*MaxOrZero*/, Predicates);
   }
 
   // We use the expression (max(End,Start)-Start)/Stride to describe the
   // backedge count, as if the backedge is taken at least once max(End,Start)
   // is End and so the result is as above, and if not max(End,Start) is Start
   // so we get a backedge count of zero.
   const SCEV *BECount = nullptr;
-  auto *StartMinusStride = getMinusSCEV(OrigStart, Stride);
+  auto *OrigStartMinusStride = getMinusSCEV(OrigStart, Stride);
   // Can we prove (max(RHS,Start) > Start - Stride?
-  if (isLoopEntryGuardedByCond(L, Cond, StartMinusStride, Start) &&
-      isLoopEntryGuardedByCond(L, Cond, StartMinusStride, RHS)) {
+  if (isLoopEntryGuardedByCond(L, Cond, OrigStartMinusStride, OrigStart) &&
+      isLoopEntryGuardedByCond(L, Cond, OrigStartMinusStride, OrigRHS)) {
     // In this case, we can use a refined formula for computing backedge taken
     // count.  The general formula remains:
     //   "End-Start /uceiling Stride" where "End = max(RHS,Start)"
     // We want to use the alternate formula:
     //   "((End - 1) - (Start - Stride)) /u Stride"
     // Let's do a quick case analysis to show these are equivalent under
     // our precondition that max(RHS,Start) > Start - Stride.
     // * For RHS <= Start, the backedge-taken count must be zero.
     //   "((End - 1) - (Start - Stride)) /u Stride" reduces to
     //   "((Start - 1) - (Start - Stride)) /u Stride" which simplies to
     //   "Stride - 1 /u Stride" which is indeed zero for all non-zero values
     //     of Stride.  For 0 stride, we've use umin(1,Stride) above, reducing
     //     this to the stride of 1 case.
     // * For RHS >= Start, the backedge count must be "RHS-Start /uceil Stride".
     //   "((End - 1) - (Start - Stride)) /u Stride" reduces to
     //   "((RHS - 1) - (Start - Stride)) /u Stride" reassociates to
     //   "((RHS - (Start - Stride) - 1) /u Stride".
     //   Our preconditions trivially imply no overflow in that form.
     const SCEV *MinusOne = getMinusOne(Stride->getType());
     const SCEV *Numerator =
-        getMinusSCEV(getAddExpr(RHS, MinusOne), StartMinusStride);
-    if (!isa<SCEVCouldNotCompute>(Numerator)) {
-      BECount = getUDivExpr(Numerator, Stride);
-    }
-  }
+        getMinusSCEV(getAddExpr(RHS, MinusOne), getMinusSCEV(Start, Stride));
 
   const SCEV *BECountIfBackedgeTaken = nullptr;
   if (!BECount) {
     auto canProveRHSGreaterThanEqualStart = [&]() {
       auto CondGE = IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE;
       if (isLoopEntryGuardedByCond(L, CondGE, OrigRHS, OrigStart))
         return true;
 

llvm/test/Analysis/ScalarEvolution/no-wrap-symbolic-becount.ll

 }
 
 define void @pointer_iv_nowrap_guard(i32* %startptr, i32* %endptr) local_unnamed_addr {
 ; CHECK-LABEL: 'pointer_iv_nowrap_guard'
 ; CHECK-NEXT:  Classifying expressions for: @pointer_iv_nowrap_guard
 ; CHECK-NEXT:    %init = getelementptr inbounds i32, i32* %startptr, i64 2000
 ; CHECK-NEXT:    --> (8000 + %startptr)<nuw> U: [8000,0) S: [8000,0)
 ; CHECK-NEXT:    %iv = phi i32* [ %init, %entry ], [ %iv.next, %loop ]
-; CHECK-NEXT:    --> {(8000 + %startptr)<nuw>,+,4}<nuw><%loop> U: [8000,0) S: [8000,0) Exits: (8000 + (4 * ((-8001 + (-1 * (ptrtoint i32* %startptr to i64)) + ((8004 + (ptrtoint i32* %startptr to i64))<nuw> umax (ptrtoint i32* %endptr to i64))) /u 4))<nuw> + %startptr) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {(8000 + %startptr)<nuw>,+,4}<nuw><%loop> U: [8000,0) S: [8000,0) Exits: (8000 + (4 * ((-8001 + (-1 * (ptrtoint i32* %startptr to i64)) + (ptrtoint i32* %endptr to i64)) /u 4))<nuw> + %startptr) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = getelementptr inbounds i32, i32* %iv, i64 1
-; CHECK-NEXT:    --> {(8004 + %startptr)<nuw>,+,4}<nuw><%loop> U: [8004,0) S: [8004,0) Exits: (8004 + (4 * ((-8001 + (-1 * (ptrtoint i32* %startptr to i64)) + ((8004 + (ptrtoint i32* %startptr to i64))<nuw> umax (ptrtoint i32* %endptr to i64))) /u 4))<nuw> + %startptr) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {(8004 + %startptr)<nuw>,+,4}<nuw><%loop> U: [8004,0) S: [8004,0) Exits: (8004 + (4 * ((-8001 + (-1 * (ptrtoint i32* %startptr to i64)) + (ptrtoint i32* %endptr to i64)) /u 4))<nuw> + %startptr) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @pointer_iv_nowrap_guard
-; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-8001 + (-1 * (ptrtoint i32* %startptr to i64)) + ((8004 + (ptrtoint i32* %startptr to i64))<nuw> umax (ptrtoint i32* %endptr to i64))) /u 4)
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-8001 + (-1 * (ptrtoint i32* %startptr to i64)) + (ptrtoint i32* %endptr to i64)) /u 4)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is 4611686018427385902
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-8001 + (-1 * (ptrtoint i32* %startptr to i64)) + ((8004 + (ptrtoint i32* %startptr to i64))<nuw> umax (ptrtoint i32* %endptr to i64))) /u 4)
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-8001 + (-1 * (ptrtoint i32* %startptr to i64)) + (ptrtoint i32* %endptr to i64)) /u 4)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %init = getelementptr inbounds i32, i32* %startptr, i64 2000
   %cmp2 = icmp ult i32* %init, %endptr
   br i1 %cmp2, label %loop, label %end