[ScalarEvolution] Try harder to prove overflow in howManyLessThans.

[efriedma]

Summary

If we have an instruction "add nsw (IV - Stride), Stride" feeding into the icmp, we know Start - Stride doesn't overflow.

It's unfortunate we can't deduce this more directly, but we don't really have any SCEV infrastructure to support this sort of check.

[efriedma]

Missed a test update

[reames]

Not really a fan of the structure of this change. Bear with me as I talk through a couple of approaches (only the last of which may work.)

Let me throw out an approach for this in terms of SCEVs. I'm going to use the variable names from foo1 in trip-count-unknown-stride.ll to make this understandable.
%i.05 = {0, +, %s}
%add = {0 + %s, +, %s}

The condition we need to prove is that (0 + %s - %s < 0 + %s. (Remember that the start here is in terms of %add, not %i.05.)

One tactic would be to prove (0 - %s) < 0. (i.e. cancel %s on either side - we don't care whether the addition of %s would wrap in that step.) This reduces to proving %s > 0. This is interesting as we already have a framework for proving strides positive. Maybe we can extend that?

Interestingly, we can do that with SCEV. Consider the following code:

if (!PositiveStride) {
  if (IsSigned && NoWrap &&
      isLoopInvariant(RHS, L) && IV->getStart() == Stride &&
      isLoopEntryGuardedByCond(L, Cond, getZero(RHS->getType()), RHS) && 
      loopIsFiniteByAssumption(L))
    PositiveStride = true;
}

I'd written this for another purpose which didn't work out, but I think the structure is valid. This is maybe too specific for a zero start on i.05 - though maybe we can generalize?

Anyways, that isn't a fully solution, but I'd strongly prefer you try to use a SCEV proof here over mixing IR and SCEV proofs.

[efriedma]

Added another interesting case to look at. Still considering possible solutions that don't involve poking at IR directly.

[efriedma]

The easiest thing here would be if SCEV recorded the flags somewhere... but unfortunately, we don't; when we discover the flags aren't universally applicable, we throw them away. We could try to construct some sort of side-table, I guess, to provide an API getNoWrapFlagsWithContext(SCEV*, Instruction*). So basically the same logic as this, but factored away.

One alternative I considered is looking at the nowrap flags of the AddRec "IV - Stride". We do often manage to deduce nsw/nuw, and if the backedge is taken, it proves Start - Stride doesn't overflow. But if we're doing that, I'm not sure how we prove the case where the backedge isn't taken.

[efriedma]

Any comments on whether we want to merge this patch? Or how we can encode the necessary information into ScalarEvolution? (Really, I'm more concerned about the pointer_iv_nowrap_guard case than the unknown-stride case.)

[reames]

LGTM. I'm not completely opposed to this and don't want to block progress further. I do think we need something better and more general. If you've got some time in the next couple days, I'd really like to get on a call and chat through what that might be.

One, possibly crazy, idea would be to use the SCEV <-> Value maps we have, and then do a forward propagation on the values to see if a given addrec being poison is guaranteed to trigger UB before the latch is taken. In this case, we should be able to map from the addrec to the IR expressions, and then find the poison reaching latch without needing to explicitly pass in the conditions.

llvm/lib/Analysis/ScalarEvolution.cpp

11846–11847

I don't understand this line of the diff. Can you remove for the moment, and do this in a separate change?

The mixed usage of OrigStart and Start here is confusing.

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

125 ↗

(On Diff #360226)

Please land this separately, and then rebase over so that the landed diff shows the change.

[efriedma]

Committed new test separately. Split off the Start/OrigStart thing to D109465.

[reames]

@efriedma Can I ask you to prioritize landing this? I suspect this is going to reduce the test diffs implied by any fix to D106852, and I'd like to get this in so we can build on it.

(For context, we're likely to loose ability to infer flags on the add forming the start expression for the post-increment IV. As such, being able to directly derive the fact from the IR - this patch - becomes much more relevant. )

[efriedma]

Rebased

[efriedma]

(This currently doesn't apply cleanly.)

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   /// \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.
   ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
                              bool isSigned, bool ControlsExit,
-                             bool AllowPredicates = false);
+                             bool AllowPredicates, ICmpInst *OrigCond);
 
   ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
                                 bool isSigned, bool IsSubExpr,
                                 bool AllowPredicates = false);
 
   /// 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.

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, ExitCond);
     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,
const SCEV *ScalarEvolution::computeMaxBECountForLT(const SCEV *Start,
   // MaxBECount = ceil((max(MaxEnd, MinStart) - MinStart) / Stride)
   MaxEnd = IsSigned ? APIntOps::smax(MaxEnd, MinStart)
                     : APIntOps::umax(MaxEnd, MinStart);
 
   return getUDivCeilSCEV(getConstant(MaxEnd - MinStart) /* Delta */,
                          getConstant(StrideForMaxBECount) /* Step */);
 }
 
 ScalarEvolution::ExitLimit
 ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
                                   const Loop *L, bool IsSigned,
-                                  bool ControlsExit, bool AllowPredicates) {
+                                  bool ControlsExit, bool AllowPredicates,
+                                  ICmpInst *OrigCond) {
   SmallPtrSet<const SCEVPredicate *, 4> Predicates;
 
   const SCEVAddRecExpr *IV = dyn_cast<SCEVAddRecExpr>(LHS);
   bool PredicatedIV = false;
 
   auto canAssumeNoSelfWrap = [&](const SCEVAddRecExpr *AR) {
     // Can we prove this loop *must* be UB if overflow of IV occurs?
     // Reasoning goes as follows:
ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
 
   // 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 *OrigStartMinusStride = getMinusSCEV(OrigStart, Stride);
   // Can we prove (max(RHS,Start) > Start - Stride?
-  if (isLoopEntryGuardedByCond(L, Cond, OrigStartMinusStride, OrigStart) &&
-      isLoopEntryGuardedByCond(L, Cond, OrigStartMinusStride, OrigRHS)) {
+  if (isLoopEntryGuardedByCond(L, Cond, OrigStartMinusStride, OrigRHS)) {
+    auto MaySubOverflow = [&]() {
+      // Start - Stride < Start implies no overflow.
+      if (isLoopEntryGuardedByCond(L, Cond, OrigStartMinusStride, OrigStart))
+        return false;
+      // Check if we have an IR instruction feeding into the branch
+      // "add nsw IVMinusStride, Stride"
+      if (getSCEV(OrigCond->getOperand(0)) == IV) {
+        if (auto *Add = dyn_cast<AddOperator>(OrigCond->getOperand(0))) {
+          if (IsSigned ? Add->hasNoSignedWrap() : Add->hasNoUnsignedWrap()) {
+            if (getSCEV(Add->getOperand(1)) == Stride)
+              return false;
+          }
+        }
+        if (auto *GEP = dyn_cast<GetElementPtrInst>(OrigCond->getOperand(0))) {
+          if (!IsSigned && GEP->isInBounds()) {
+            if (getSCEV(GEP->getOperand(0)) == getMinusSCEV(IV, Stride))
+              return false;
+          }
+        }
+      }
+      return true;
+    };
     // 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.
+    if (!MaySubOverflow()) {
       const SCEV *MinusOne = getMinusOne(Stride->getType());
       const SCEV *Numerator =
           getMinusSCEV(getAddExpr(RHS, MinusOne), getMinusSCEV(Start, Stride));
       BECount = getUDivExpr(Numerator, 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/trip-count-unknown-stride.ll

 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
 
 ; ScalarEvolution should be able to compute trip count of the loop by proving
 ; that this is not an infinite loop with side effects.
 
 ; CHECK-LABEL: Determining loop execution counts for: @foo1
-; CHECK: backedge-taken count is ((-1 + (%n smax %s)) /u %s)
+; CHECK: backedge-taken count is ((-1 + %n) /u %s)
 
 ; We should have a conservative estimate for the max backedge taken count for
 ; loops with unknown stride.
 ; CHECK: max backedge-taken count is -1
 
 target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
 
 define void @foo1(i32* nocapture %A, i32 %n, i32 %s) mustprogress {

llvm/test/Transforms/LoopReroll/nonconst_lb.ll

 ;  }
 ;}
 define void @foo(i32* nocapture %A, i32* nocapture readonly %B, i32 %m, i32 %n) {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP34:%.*]] = icmp slt i32 [[M:%.*]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP34]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
 ; CHECK:       for.body.preheader:
-; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[M]], 4
-; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[N]], i32 [[TMP0]])
-; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[SMAX]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = sub i32 [[TMP1]], [[M]]
-; CHECK-NEXT:    [[TMP3:%.*]] = lshr i32 [[TMP2]], 2
-; CHECK-NEXT:    [[TMP4:%.*]] = shl nuw i32 [[TMP3]], 2
-; CHECK-NEXT:    [[TMP5:%.*]] = add nuw nsw i32 [[TMP4]], 3
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[TMP0]], [[M]]
+; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
+; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw i32 [[TMP2]], 2
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i32 [[TMP3]], 3
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i32 [ 0, [[FOR_BODY_PREHEADER]] ], [ [[INDVAR_NEXT:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[TMP6:%.*]] = add i32 [[M]], [[INDVAR]]
-; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i32 [[TMP6]]
-; CHECK-NEXT:    [[TMP7:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
-; CHECK-NEXT:    [[MUL:%.*]] = shl nsw i32 [[TMP7]], 2
-; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i32 [[TMP6]]
+; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[M]], [[INDVAR]]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i32 [[TMP5]]
+; CHECK-NEXT:    [[TMP6:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[MUL:%.*]] = shl nsw i32 [[TMP6]], 2
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i32 [[TMP5]]
 ; CHECK-NEXT:    store i32 [[MUL]], i32* [[ARRAYIDX2]], align 4
 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i32 [[INDVAR]], 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INDVAR]], [[TMP5]]
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INDVAR]], [[TMP4]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end.loopexit:
 ; CHECK-NEXT:    br label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp34 = icmp slt i32 %m, %n