[ScalarEvolution][NFC] Refactor howManyLessThans

[efriedma]

Summary

Include an actual proof of the property we care about, and add FIXMEs for the missing correctness checks. Also, some related cleanup.

Split off from D105216.

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

11784

Thinking about this a bit more, we might be able to get away with using this path even if we can't prove RHS > Start - Stride. We could use something like (max(RHS, Start - (Stride - 1)) - (Start - (Stride - 1))) /u Stride, I think. Not confident I wrote that exactly right.

Not sure how much that improves things in practice, though; the logic on this path is still predicated on the assumption that Start - (Stride - 1) doesn't overflow.

[efriedma]

Rebased. Comment updated to address review comments.

[efriedma]

Basically everything here has landed.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   /// AddRec and the predicates as a pair, and caches this pair in
   /// PredicatedSCEVRewrites.
   /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
   /// itself (with no predicates) is recorded, and a nullptr with an empty
   /// predicates vector is returned as a pair.
   Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
   createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
 
-  /// Compute the backedge taken count knowing the interval difference, and
-  /// the stride for an inequality.  Result takes the form:
-  /// (Delta + (Stride - 1)) udiv Stride.
-  /// Caller must ensure that this expression either does not overflow or
-  /// that the result is undefined if it does.
-  const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride);
-
   /// Compute ceil(N / D). N and D are treated as unsigned values.
   ///
   /// Since SCEV doesn't have native ceiling division, this generates a
   /// SCEV expression of the following form:
   ///
   /// umin(N, 1) + floor((N - umin(N, 1)) / D)
   ///
   /// A denominator of zero or poison is handled the same way as getUDivExpr().

llvm/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::getUDivCeilSCEV(const SCEV *N, const SCEV *D) {
   // umin(N, 1) + floor((N - umin(N, 1)) / D)
   // This is equivalent to "1 + floor((N - 1) / D)" for N != 0. The umin
   // expression fixes the case of N=0.
   const SCEV *MinNOne = getUMinExpr(N, getOne(N->getType()));
   const SCEV *NMinusOne = getMinusSCEV(N, MinNOne);
   return getAddExpr(MinNOne, getUDivExpr(NMinusOne, D));
 }
 
-const SCEV *ScalarEvolution::computeBECount(const SCEV *Delta,
-                                            const SCEV *Step) {
-  const SCEV *One = getOne(Step->getType());
-  Delta = 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) {
 
   assert(!isKnownNonPositive(Stride) &&
          "Stride is expected strictly positive!");
ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
   }
 
   // Avoid weird loops
   if (!IV || IV->getLoop() != L || !IV->isAffine())
     return getCouldNotCompute();
 
   auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW;
   bool NoWrap = ControlsExit && IV->getNoWrapFlags(WrapType);
-  ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
 
   const SCEV *Stride = IV->getStepRecurrence(*this);
 
   bool PositiveStride = isKnownPositive(Stride);
 
   // Avoid negative or zero stride values.
   if (!PositiveStride) {
     // We can compute the correct backedge taken count for loops with unknown
if (isa<SCEVCouldNotCompute>(Start))
       return Start;
   }
   if (RHS->getType()->isPointerTy()) {
     RHS = getLosslessPtrToIntExpr(RHS);
     if (isa<SCEVCouldNotCompute>(RHS))
       return 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);
     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 =
-    computeBECount(getMinusSCEV(End, Start), Stride);
-  // If the loop entry is guarded by the result of the backedge test of the
-  // first loop iteration, then we know the backedge will be taken at least
-  // once and so the backedge taken count is as above. If not then 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;
-  if (isLoopEntryGuardedByCond(L, Cond, getMinusSCEV(OrigStart, Stride), OrigRHS))
-    BECount = BECountIfBackedgeTaken;
-  else {
+  const SCEV *BECountIfBackedgeTaken = nullptr;
+  ICmpInst::Predicate CondGE =
+      IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE;
+  ICmpInst::Predicate CondGT =
+      IsSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
+
+  if (isLoopEntryGuardedByCond(L, CondGT, RHS,
+                               getMinusSCEV(OrigStart, Stride))) {
+    // FIXME: Missing check:
+    //     isLoopEntryGuardedByCond(L, CondGT, Start, StartMinusStride)
+    //
+    // Suppose "Stride > 0", "Start - Stride" doesn't overflow, and
+    // "RHS > Start - Stride".
+    //
+    // If RHS >= Start, in general, the backedge-taken count is
+    // "ceil((RHS - Start) / Stride)".  This is equvalent to
+    // "((RHS - Start) + (Stride - 1)) /u Stride" in arbitrary-precision math.
+    // We can reassociate that to "((RHS - 1) - (Start - Stride)) /u Stride".
+    // According to our preconditions, "RHS - 1" and "Start - Stride" can't
+    // overflow, and "((RHS - 1) - (Start - Stride))" fits into an unsigned
+    // integer, so we can just emit that expression directly.
+    //
+    // If "RHS < Start", in general, the backedge-taken count is zero.
+    // "RHS < Start" implies "((RHS - 1) - (Start - Stride)) < Stride",
+    // so the above formula evaluates to zero.
+    //
+    // Note that this is actually equivalent to the "floor((D + (S - 1)) / S)"
+    // used in the general case; it's just rearranged to match the above proof.
+    const SCEV *MinusOne = getMinusOne(Stride->getType());
+    const SCEV *Numerator =
+        getMinusSCEV(getAddExpr(RHS, MinusOne), getMinusSCEV(Start, Stride));
+    BECount = getUDivExpr(Numerator, Stride);
+  } else {
     auto canProveRHSGreaterThanEqualStart = [&]() {
       auto CondGE = IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE;
       if (isLoopEntryGuardedByCond(L, CondGE, OrigRHS, OrigStart))
         return true;
 
       // (RHS > Start - 1) implies RHS >= Start.
       // * "RHS >= Start" is trivially equivalent to "RHS > Start - 1" if
       //   "Start - 1" doesn't overflow.
       // * For signed comparison, if Start - 1 does overflow, it's equal
       //   to INT_MAX, and "RHS >s INT_MAX" is trivially false.
       // * For unsigned comparison, if Start - 1 does overflow, it's equal
       //   to UINT_MAX, and "RHS >u UINT_MAX" is trivially false.
       //
       // FIXME: Should isLoopEntryGuardedByCond do this for us?
       auto CondGT = IsSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
       auto *StartMinusOne = getAddExpr(OrigStart,
                                        getMinusOne(OrigStart->getType()));
       return isLoopEntryGuardedByCond(L, CondGT, OrigRHS, StartMinusOne);
     };
 
+    const SCEV *End;
     // If we know that RHS >= Start in the context of loop, then we know that
     // max(RHS, Start) = RHS at this point.
-    if (canProveRHSGreaterThanEqualStart())
+    if (canProveRHSGreaterThanEqualStart()) {
       End = RHS;
-    else
+    } else {
+      // If RHS < Start, the backedge will be taken zero times.  So in
+      // general, we can write the backedge-taken count as:
+      //
+      //     RHS >= Start ? ceil((RHS - Start) / Stride) : 0
+      //
+      // We convert it to the following to make it more convenient for SCEV:
+      //
+      //     ceil((max(RHS, Start) - Start) / Stride)
       End = IsSigned ? getSMaxExpr(RHS, Start) : getUMaxExpr(RHS, Start);
-    BECount = computeBECount(getMinusSCEV(End, Start), Stride);
+
+      // See what would happen if we assume the backedge is taken. This is
+      // used to compute MaxBECount.
+      BECountIfBackedgeTaken = getUDivCeilSCEV(getMinusSCEV(RHS, Start), Stride);
+    }
+    // Convert ceil(D / S) to floor((D + (S - 1)) / S).
+    // FIXME: The addition can overflow, in general.  Will be addressed in a
+    // followup.
+    const SCEV *MinusOne = getMinusOne(Stride->getType());
+    const SCEV *Delta = getMinusSCEV(End, Start);
+    BECount =
+        getUDivExpr(getAddExpr(Delta, getAddExpr(Stride, MinusOne)), Stride);
   }
 
   const SCEV *MaxBECount;
   bool MaxOrZero = false;
-  if (isa<SCEVConstant>(BECount))
+  if (isa<SCEVConstant>(BECount)) {
     MaxBECount = BECount;
-  else if (isa<SCEVConstant>(BECountIfBackedgeTaken)) {
+  } else if (BECountIfBackedgeTaken &&
+             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);
if (isa<SCEVCouldNotCompute>(Start))
       return Start;
   }
   if (End->getType()->isPointerTy()) {
     End = getLosslessPtrToIntExpr(End);
     if (isa<SCEVCouldNotCompute>(End))
       return End;
   }
 
-  const SCEV *BECount = computeBECount(getMinusSCEV(Start, End), Stride);
+  // Compute ((Start - End) + (Stride - 1)) / Stride.
+  // FIXME: Both the subtraction and the addition can overflow. Holding off on
+  // fixing this for now; we plan to merge howManyGreaterThans with
+  // howManyLessThans.
+  const SCEV *One = getOne(Stride->getType());
+  const SCEV *BECount = getUDivExpr(
+      getAddExpr(getMinusSCEV(Start, End), getMinusSCEV(Stride, One)), Stride);
 
   APInt MaxStart = IsSigned ? getSignedRangeMax(Start)
                             : getUnsignedRangeMax(Start);
 
   APInt MinStride = IsSigned ? getSignedRangeMin(Stride)
                              : getUnsignedRangeMin(Stride);
 
   unsigned BitWidth = getTypeSizeInBits(LHS->getType());