[WIP][ScalarEvolution] Merge howManyGreaterThans with howManyLessThans.

[efriedma]

Summary

They're basically the same function, so let's not implement it twice. And they've fallen out of sync a bit: howManyLessThans has more features.

Still need to investigate:

1. We're replacing smin/umin expressions with less efficient smax/umax expressions. Not sure how we're supposed to canonicalize here.
2. The isLoopEntryGuardedByCond check is failing in places where it used to succeed.

[mkazantsev]

LGTM, but I think we can remove more copy-paste (see comment). Can go as follow-up.

llvm/lib/Analysis/ScalarEvolution.cpp

11534

Instead of this, can we just have smth like

ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
if (Invert)
  Cond = getSwappedPredicate(Cond);

? This piece still lppks copy-pastish.

[nikic]

There's a minor compile-time impact for this refactoring: https://llvm-compile-time-tracker.com/compare.php?from=57006d2f6d96d8a6836ae901218ed615071b3b8e&to=eca6ad2e31d754420fb114872bfc4060a698155e&stat=instructions It's okay, but you might want to cut down on the number of repeated/redundant getNotSCEV operations you perform. (They're not cached and known to be somewhat expensive.)

llvm/lib/Analysis/ScalarEvolution.cpp

11566

I'm confused by what you're doing here. getNotSCEV has a fold that does ~umin(~x, ~y) to umax(x, y), so the structure you're using here should get undone?

[reames]

Several level of comments.

First, the LT handling is substantially more powerful than the GT handling. e.g. for unknown strides. Given that, this is definitely NOT nfc, and should have accompanying test changes.

Second, I'd prefer this not go in until the underlying LT miscompile we've been discussing is addressed. The GT code handles this case differently, and I'm not sure that pushing GT through this code is safe.

Third, I'd suggest an alternate interface. Please remove the IsSigned and Invert parameters, and just pass through the condition. These two properties can be derived inside the method.

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

11566

getNotSCEV(RHS) and getNotSCEV(Start) will likely be simplified.

[efriedma]

Address review comments. (Still going to look at adding more tests.)

[efriedma]

Note to self: differences between old and new gt codepath that need tests:

1. Now compute max trip count even if RHS is not invariant.
2. Now more aggressive with strides that are not known positive (although this codepath currently has issues...)
3. Now use isUBOnWrap() for stride greater than one.
4. Now compute MaxOrZero.

[efriedma]

Added tests. A couple more cleanups.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

11409

For sanity sake, please actually set Pred here so that if we use it below, we get what we expect.

11531

I'd prefer to make it more powerful if possible.

A couple ideas, not sure if these work out or not:

• Use SimplifyICmpOperands to canonicalize operands to isBasicBlockEntryGuardedByCond.
• Teach isLoopEntryGuardedByCond to undo your not(lhs/rhs) transform.

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

11531

There's actually another layer of complexity here on the main branch: if LHS/RHS are pointers, we have ptrtoint expressions floating around here, which isLoopEntryGuardedByCond also doesn't handle well.

After D105510 is merged, I can try messing with isLoopEntryGuardedByCond etc.

[efriedma]

Show simplified version. Not ready to merge.

[reames]

@efriedma Just to note, I think we've hit the point where howManyLessThans isn't getting any more stable in the near future, and howManyGreaterThans is at least as buggy. If you wanted to rebase this, I'd be up for reviewing with intent to land in near future.

[reames]

Pending action by author, please request review once ready for more discussion. Just getting this off my active review queue.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   /// \p isSigned specifies whether the less-than is signed.
   ///
   /// \p ControlsExit is true when the LHS < RHS condition directly controls
   /// the branch (loops exits only if condition is true). In this case, we can
   /// use NoWrapFlags to skip overflow checks.
   ///
   /// If \p AllowPredicates is set, this call will try to use a minimal set of
   /// SCEV predicates in order to return an exact answer.
+  ///
+  /// If \p Invert is set, the input is actually a greater-than comparison.
+  /// The code will use a binary NOT on the operands, and adjust other logic to
+  /// try to be more precise.
   ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
                              bool isSigned, bool ControlsExit,
-                             bool AllowPredicates = false);
-
-  ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
-                                bool isSigned, bool IsSubExpr,
-                                bool AllowPredicates = false);
+                             bool AllowPredicates, bool Invert);
 
   /// Return a predecessor of BB (which may not be an immediate predecessor)
   /// which has exactly one successor from which BB is reachable, or null if
   /// no such block is found.
   std::pair<const BasicBlock *, const BasicBlock *>
   getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB) const;
 
   /// Test whether the condition described by Pred, LHS, and RHS is true
const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
                                      const SCEV *End, unsigned BitWidth,
                                      bool IsSigned);
 
   /// 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.
   bool canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
 
-  /// Verify if an linear IV with negative stride can overflow when in a
-  /// greater-than comparison, knowing the invariant term of the comparison,
-  /// the stride.
-  bool canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
-
   /// Get add expr already created or create a new one.
   const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
                                  SCEV::NoWrapFlags Flags);
 
   /// Get mul expr already created or create a new one.
   const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
                                  SCEV::NoWrapFlags Flags);
 

llvm/lib/Analysis/ScalarEvolution.cpp

case ICmpInst::ICMP_EQ: {                     // while (X == Y)
     ExitLimit EL = howFarToNonZero(getMinusSCEV(LHS, RHS), L);
     if (EL.hasAnyInfo()) return EL;
     break;
   }
   case ICmpInst::ICMP_SLT:
   case ICmpInst::ICMP_ULT: {                    // while (X < Y)
     bool IsSigned = Pred == ICmpInst::ICMP_SLT;
     ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsExit,
-                                    AllowPredicates);
+                                    AllowPredicates, /*Invert*/ false);
     if (EL.hasAnyInfo()) return EL;
     break;
   }
   case ICmpInst::ICMP_SGT:
   case ICmpInst::ICMP_UGT: {                    // while (X > Y)
     bool IsSigned = Pred == ICmpInst::ICMP_SGT;
-    ExitLimit EL =
-        howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsExit,
-                            AllowPredicates);
+    ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsExit,
+                                    AllowPredicates, /*Invert*/ true);
     if (EL.hasAnyInfo()) return EL;
     break;
   }
   default:
     break;
   }
 
   auto *ExhaustiveCount =
bool ScalarEvolution::canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride,
   APInt MaxRHS = getUnsignedRangeMax(RHS);
   APInt MaxValue = APInt::getMaxValue(BitWidth);
   APInt MaxStrideMinusOne = getUnsignedRangeMax(getMinusSCEV(Stride, One));
 
   // UMaxRHS + UMaxStrideMinusOne > UMaxValue => overflow!
   return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
 }
 
-bool ScalarEvolution::canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride,
-                                        bool IsSigned) {
-  
-  unsigned BitWidth = getTypeSizeInBits(RHS->getType());
-  const SCEV *One = getOne(Stride->getType());
-
-  if (IsSigned) {
-    APInt MinRHS = getSignedRangeMin(RHS);
-    APInt MinValue = APInt::getSignedMinValue(BitWidth);
-    APInt MaxStrideMinusOne = getSignedRangeMax(getMinusSCEV(Stride, One));
-
-    // SMinRHS - SMaxStrideMinusOne < SMinValue => overflow!
-    return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
-  }
-
-  APInt MinRHS = getUnsignedRangeMin(RHS);
-  APInt MinValue = APInt::getMinValue(BitWidth);
-  APInt MaxStrideMinusOne = getUnsignedRangeMax(getMinusSCEV(Stride, One));
-
-  // UMinRHS - UMaxStrideMinusOne < UMinValue => overflow!
-  return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
-}
-
 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,
APInt MaxEnd = IsSigned ? APIntOps::smin(getSignedRangeMax(End), Limit)
                           : APIntOps::umin(getUnsignedRangeMax(End), Limit);
 
   MaxBECount = computeBECount(getConstant(MaxEnd - MinStart) /* Delta */,
                               getConstant(StrideForMaxBECount) /* Step */);
 
   return MaxBECount;
 }
 
-ScalarEvolution::ExitLimit
-ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
-                                  const Loop *L, bool IsSigned,
-                                  bool ControlsExit, bool AllowPredicates) {
+ScalarEvolution::ExitLimit ScalarEvolution::howManyLessThans(
+    const SCEV *LHS, const SCEV *RHS, const Loop *L, bool IsSigned,
+    bool ControlsExit, bool AllowPredicates, bool Invert) {
   SmallPtrSet<const SCEVPredicate *, 4> Predicates;
 
+  // If this is actually a greater-than comparison, invert the
+  // LHS/RHS to make it a less-than comparison.
+  if (Invert) {
+    LHS = getNotSCEV(LHS);
+    RHS = getNotSCEV(RHS);
+  }
+
   const SCEVAddRecExpr *IV = dyn_cast<SCEVAddRecExpr>(LHS);
   bool PredicatedIV = false;
 
   if (!IV && AllowPredicates) {
     // Try to make this an AddRec using runtime tests, in the first X
     // iterations of this loop, where X is the SCEV expression found by the
     // algorithm below.
     IV = convertSCEVToAddRecWithPredicates(LHS, L, Predicates);
     PredicatedIV = true;
   }
 
   // Avoid weird loops
   if (!IV || IV->getLoop() != L || !IV->isAffine())
     return getCouldNotCompute();
 
   bool NoWrap = ControlsExit &&
                 IV->getNoWrapFlags(IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW);
 
   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
     // strides if we can prove that the loop is not an infinite loop with side
     // effects. Here's the loop structure we are trying to handle -
     //
     // i = start
     // do {
if (!PositiveStride) {
     // Avoid proven overflow cases: this will ensure that the backedge taken
     // count will not generate any unsigned overflow. Relaxed no-overflow
     // conditions exploit NoWrapFlags, allowing to optimize in presence of
     // undefined behaviors like the case of C language.
     if (canIVOverflowOnLT(RHS, Stride, IsSigned) && !isUBOnWrap())
       return getCouldNotCompute();
   }
 
-  ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SLT
-                                      : ICmpInst::ICMP_ULT;
   const SCEV *Start = IV->getStart();
   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 *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.
+  //
+  // Specialize for less-than versus greater-than. This isn't a matter of
+  // correctness: we inverted the inputs at the beginning of the function, so
+  // both paths are theoretically equivalent. But isLoopEntryGuardedByCond
+  // isn't very powerful, so we want to look for more likely patterns.
+  // And min/max simplification isn't very powerful, so we want to choose to
+  // generate smin vs smax as appropriate.
   const SCEV *BECount;
+  if (!Invert) {
+    ICmpInst::Predicate Cond =
+        IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
     if (isLoopEntryGuardedByCond(L, Cond, getMinusSCEV(Start, Stride), RHS))
       BECount = BECountIfBackedgeTaken;
     else {
       // If we know that RHS >= Start in the context of loop, then we know that
       // max(RHS, Start) = RHS at this point.
       if (isLoopEntryGuardedByCond(
-            L, IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE, RHS, Start))
+              L, IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE, RHS,
+              Start))
         End = RHS;
       else
         End = IsSigned ? getSMaxExpr(RHS, Start) : getUMaxExpr(RHS, Start);
       BECount = computeBECount(getMinusSCEV(End, Start), Stride);
     }
+  } else {
+    ICmpInst::Predicate Cond =
+        IsSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
+    if (isLoopEntryGuardedByCond(
+            L, Cond, getNotSCEV(getMinusSCEV(Start, Stride)), getNotSCEV(RHS)))
+      BECount = BECountIfBackedgeTaken;
+    else {
+      // If we know that RHS >= Start in the context of loop, then we know that
+      // max(RHS, Start) = RHS at this point.
+      if (isLoopEntryGuardedByCond(
+              L, IsSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE,
+              getNotSCEV(RHS), getNotSCEV(Start)))
+        End = RHS;
+      else {
+        End = IsSigned
+                  ? getNotSCEV(getSMinExpr(getNotSCEV(RHS), getNotSCEV(Start)))
+                  : getNotSCEV(getUMinExpr(getNotSCEV(RHS), getNotSCEV(Start)));
+      }
+      BECount = computeBECount(getMinusSCEV(End, Start), Stride);
+    }
+  }
 
   const SCEV *MaxBECount;
   bool MaxOrZero = false;
   if (isa<SCEVConstant>(BECount))
     MaxBECount = BECount;
   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);
   }
 
   if (isa<SCEVCouldNotCompute>(MaxBECount) &&
       !isa<SCEVCouldNotCompute>(BECount))
     MaxBECount = getConstant(getUnsignedRangeMax(BECount));
 
   return ExitLimit(BECount, MaxBECount, MaxOrZero, Predicates);
 }
 
-ScalarEvolution::ExitLimit
-ScalarEvolution::howManyGreaterThans(const SCEV *LHS, const SCEV *RHS,
-                                     const Loop *L, bool IsSigned,
-                                     bool ControlsExit, bool AllowPredicates) {
-  SmallPtrSet<const SCEVPredicate *, 4> Predicates;
-  // We handle only IV > Invariant
-  if (!isLoopInvariant(RHS, L))
-    return getCouldNotCompute();
-
-  const SCEVAddRecExpr *IV = dyn_cast<SCEVAddRecExpr>(LHS);
-  if (!IV && AllowPredicates)
-    // Try to make this an AddRec using runtime tests, in the first X
-    // iterations of this loop, where X is the SCEV expression found by the
-    // algorithm below.
-    IV = convertSCEVToAddRecWithPredicates(LHS, L, Predicates);
-
-  // Avoid weird loops
-  if (!IV || IV->getLoop() != L || !IV->isAffine())
-    return getCouldNotCompute();
-
-  bool NoWrap = ControlsExit &&
-                IV->getNoWrapFlags(IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW);
-
-  const SCEV *Stride = getNegativeSCEV(IV->getStepRecurrence(*this));
-
-  // Avoid negative or zero stride values
-  if (!isKnownPositive(Stride))
-    return getCouldNotCompute();
-
-  // Avoid proven overflow cases: this will ensure that the backedge taken count
-  // will not generate any unsigned overflow. Relaxed no-overflow conditions
-  // exploit NoWrapFlags, allowing to optimize in presence of undefined
-  // behaviors like the case of C language.
-  if (!Stride->isOne() && !NoWrap)
-    if (canIVOverflowOnGT(RHS, Stride, IsSigned))
-      return getCouldNotCompute();
-
-  ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SGT
-                                      : ICmpInst::ICMP_UGT;
-
-  const SCEV *Start = IV->getStart();
-  const SCEV *End = RHS;
-  if (!isLoopEntryGuardedByCond(L, Cond, getAddExpr(Start, Stride), RHS)) {
-    // If we know that Start >= RHS in the context of loop, then we know that
-    // min(RHS, Start) = RHS at this point.
-    if (isLoopEntryGuardedByCond(
-            L, IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE, Start, RHS))
-      End = RHS;
-    else
-      End = IsSigned ? getSMinExpr(RHS, Start) : getUMinExpr(RHS, Start);
-  }
-
-  const SCEV *BECount = computeBECount(getMinusSCEV(Start, End), Stride);
-
-  APInt MaxStart = IsSigned ? getSignedRangeMax(Start)
-                            : getUnsignedRangeMax(Start);
-
-  APInt MinStride = IsSigned ? getSignedRangeMin(Stride)
-                             : getUnsignedRangeMin(Stride);
-
-  unsigned BitWidth = getTypeSizeInBits(LHS->getType());
-  APInt Limit = IsSigned ? APInt::getSignedMinValue(BitWidth) + (MinStride - 1)
-                         : APInt::getMinValue(BitWidth) + (MinStride - 1);
-
-  // Although End can be a MIN expression we estimate MinEnd considering only
-  // the case End = RHS. This is safe because in the other case (Start - End)
-  // is zero, leading to a zero maximum backedge taken count.
-  APInt MinEnd =
-    IsSigned ? APIntOps::smax(getSignedRangeMin(RHS), Limit)
-             : APIntOps::umax(getUnsignedRangeMin(RHS), Limit);
-
-  const SCEV *MaxBECount = isa<SCEVConstant>(BECount)
-                               ? BECount
-                               : computeBECount(getConstant(MaxStart - MinEnd),
-                                                getConstant(MinStride));
-
-  if (isa<SCEVCouldNotCompute>(MaxBECount))
-    MaxBECount = BECount;
-
-  return ExitLimit(BECount, MaxBECount, false, Predicates);
-}
-
 const SCEV *SCEVAddRecExpr::getNumIterationsInRange(const ConstantRange &Range,
                                                     ScalarEvolution &SE) const {
   if (Range.isFullSet())  // Infinite loop.
     return SE.getCouldNotCompute();
 
   // If the start is a non-zero constant, shift the range to simplify things.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
     if (!SC->getValue()->isZero()) {