[SCEV] Set nowrap for finite non-strict predicates for addrecs

[nikic]

Summary

While we cannot mark the add 1 as nowrap in general (because we only know that it holds at this specific comparison), we can mark it for addrecs in this loop, because their defining scope (in which nowrap must hold) is limited to that loop (and we also know that there are no other normal or abnormal exits, so we're definitely executing this comparison).

This fixes the regression reported in https://reviews.llvm.org/D145510#4259519.

[efriedma]

I don't understand why this is safe. You're checking that the LHS is an AddRec (which is bound to the loop in question), but then you're adding the flags to math on the RHS (which is not).

[nikic]

In D148107#4262287, @efriedma wrote:

I don't understand why this is safe. You're checking that the LHS is an AddRec (which is bound to the loop in question), but then you're adding the flags to math on the RHS (which is not).

Uh yeah, I have honestly no idea what I was thinking here.

[reames]

I don't think this holds. I think it would hold if you were adding to LHS, but RHS is an unrelated loop invariant value.

What prevents this:
if (rhs + 1 would not overflow) {

for (int i = 0; i < rhs; i++) { ... }

}
else {

use (rhs+1).

}

llvm/lib/Analysis/ScalarEvolution.cpp

if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(InnerLHS)) {
         Flags = setFlags(Flags, SCEV::FlagNW);
         SmallVector<const SCEV*> Operands{AR->operands()};
         Flags = StrengthenNoWrapFlags(this, scAddRecExpr, Operands, Flags);
         setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), Flags);
       }
     }
   }
 
+  bool IsSigned = ICmpInst::isSigned(Pred);
   switch (Pred) {
   case ICmpInst::ICMP_NE: {                     // while (X != Y)
     // Convert to: while (X-Y != 0)
     if (LHS->getType()->isPointerTy()) {
       LHS = getLosslessPtrToIntExpr(LHS);
       if (isa<SCEVCouldNotCompute>(LHS))
         return LHS;
     }
if (RHS->getType()->isPointerTy()) {
       if (isa<SCEVCouldNotCompute>(RHS))
         return RHS;
     }
     ExitLimit EL = howFarToNonZero(getMinusSCEV(LHS, RHS), L);
     if (EL.hasAnyInfo()) return EL;
     break;
   }
   case ICmpInst::ICMP_SLE:
-  case ICmpInst::ICMP_ULE:
+  case ICmpInst::ICMP_ULE: {
     // Since the loop is finite, an invariant RHS cannot include the boundary
     // value, otherwise it would loop forever.
     if (!EnableFiniteLoopControl || !ControllingFiniteLoop ||
         !isLoopInvariant(RHS, L))
       break;
-    RHS = getAddExpr(getOne(RHS->getType()), RHS);
+
+    // This particular add will not overflow, but this does not necessarily
+    // hold globally. However, if this is an addrec in this loop, then the
+    // addition can never overflow in its validity scope (otherwise behavior
+    // would be undefined).
+    SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
+    if (const auto *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
+      if (AddRec->getLoop() == L)
+        Flags = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW;
+    RHS = getAddExpr(getOne(RHS->getType()), RHS, Flags);
     [[fallthrough]];
+  }
   case ICmpInst::ICMP_SLT:
   case ICmpInst::ICMP_ULT: { // while (X < Y)
-    bool IsSigned = ICmpInst::isSigned(Pred);
     ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsOnlyExit,
                                     AllowPredicates);
     if (EL.hasAnyInfo())
       return EL;
     break;
   }
   case ICmpInst::ICMP_SGE:
-  case ICmpInst::ICMP_UGE:
+  case ICmpInst::ICMP_UGE: {
     // Since the loop is finite, an invariant RHS cannot include the boundary
     // value, otherwise it would loop forever.
     if (!EnableFiniteLoopControl || !ControllingFiniteLoop ||
         !isLoopInvariant(RHS, L))
       break;
-    RHS = getAddExpr(getMinusOne(RHS->getType()), RHS);
+
+    // See comment on the sle/ule case. We can only handle the signed case
+    // here, because we're performing an add -1, not sub 1.
+    SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
+    if (const auto *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
+      if (AddRec->getLoop() == L && IsSigned)
+        Flags = SCEV::FlagNSW;
+    RHS = getAddExpr(getMinusOne(RHS->getType()), RHS, Flags);
     [[fallthrough]];
+  }
   case ICmpInst::ICMP_SGT:
   case ICmpInst::ICMP_UGT: { // while (X > Y)
-    bool IsSigned = ICmpInst::isSigned(Pred);
     ExitLimit EL = howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsOnlyExit,
                                        AllowPredicates);
     if (EL.hasAnyInfo())
       return EL;
     break;
   }
   default:
     break;

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

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-max-iterations=0  -scalar-evolution-classify-expressions=0  2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare void @non_exit_use(i32 %i) #0
 
 define void @sle_pre_inc(i32 %len) willreturn {
 ; CHECK-LABEL: 'sle_pre_inc'
 ; CHECK-NEXT:  Determining loop execution counts for: @sle_pre_inc
-; CHECK-NEXT:  Loop %for.body: backedge-taken count is (0 smax (1 + %len))
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (0 smax (1 + %len)<nsw>)
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483647
-; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (0 smax (1 + %len))
-; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (0 smax (1 + %len))
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (0 smax (1 + %len)<nsw>)
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (0 smax (1 + %len)<nsw>)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
 
 for.body:
   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
   call void @non_exit_use(i32 %iv) nounwind willreturn
   %inc = add i32 %iv, 1
   %cmp = icmp sle i32 %iv, %len
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:
   ret void
 }
 
 define void @sle_post_inc(i32 %len) willreturn {
 ; CHECK-LABEL: 'sle_post_inc'
 ; CHECK-NEXT:  Determining loop execution counts for: @sle_post_inc
-; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (1 smax (1 + %len)))<nsw>
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (1 smax (1 + %len)<nsw>))<nsw>
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483646
-; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + (1 smax (1 + %len)))<nsw>
-; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (1 smax (1 + %len)))<nsw>
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + (1 smax (1 + %len)<nsw>))<nsw>
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (1 smax (1 + %len)<nsw>))<nsw>
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
 
 for.body:
   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]

 
 for.end:
   ret void
 }
 
 define void @ule_pre_inc(i32 %len) willreturn {
 ; CHECK-LABEL: 'ule_pre_inc'
 ; CHECK-NEXT:  Determining loop execution counts for: @ule_pre_inc
-; CHECK-NEXT:  Loop %for.body: backedge-taken count is (1 + %len)
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (1 + %len)<nuw>
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -1
-; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (1 + %len)
-; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (1 + %len)
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (1 + %len)<nuw>
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (1 + %len)<nuw>
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
 
 for.body:
   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
   call void @non_exit_use(i32 %iv) nounwind willreturn
   %inc = add i32 %iv, 1
   %cmp = icmp ule i32 %iv, %len
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:
   ret void
 }
 
 define void @ule_post_inc(i32 %len) willreturn {
 ; CHECK-LABEL: 'ule_post_inc'
 ; CHECK-NEXT:  Determining loop execution counts for: @ule_post_inc
-; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (1 umax (1 + %len)))
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is %len
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2
-; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + (1 umax (1 + %len)))
-; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (1 umax (1 + %len)))
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is %len
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is %len
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
 
 for.body:
   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]

 
 for.end:
   ret void
 }
 
 define void @sge_pre_inc(i32 %end) willreturn {
 ; CHECK-LABEL: 'sge_pre_inc'
 ; CHECK-NEXT:  Determining loop execution counts for: @sge_pre_inc
-; CHECK-NEXT:  Loop %for.body: backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)<nsw>)))
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2147483548
-; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
-; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)<nsw>)))
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)<nsw>)))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
 
 for.body:
   %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
   call void @non_exit_use(i32 %iv) nounwind willreturn
   %inc = add i32 %iv, -1
   %cmp = icmp sge i32 %iv, %end
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:
   ret void
 }
 
 define void @sge_post_inc(i32 %end) willreturn {
 ; CHECK-LABEL: 'sge_post_inc'
 ; CHECK-NEXT:  Determining loop execution counts for: @sge_post_inc
-; CHECK-NEXT:  Loop %for.body: backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)<nsw>)))
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2147483548
-; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
-; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)<nsw>)))
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)<nsw>)))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
 
 for.body:
   %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]

llvm/test/Transforms/IndVarSimplify/rewrite-loop-exit-value.ll

 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INC8:%.*]] = phi i16 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[INC8]], 1
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i16 [[INC8]], [[M:%.*]]
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i16 [[MUL]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[CRIT_EDGE:%.*]], label [[FOR_BODY]]
 ; CHECK:       crit_edge:
-; CHECK-NEXT:    [[TMP0:%.*]] = add i16 [[END]], 1
-; CHECK-NEXT:    [[SMAX:%.*]] = call i16 @llvm.smax.i16(i16 [[TMP0]], i16 0)
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i16 [[END]], 32767
+; CHECK-NEXT:    [[TMP0:%.*]] = call i16 @llvm.smax.i16(i16 [[END]], i16 -1)
+; CHECK-NEXT:    [[SMAX:%.*]] = add nsw i16 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i16 [[SMAX]], 0
 ; CHECK-NEXT:    [[UMIN:%.*]] = zext i1 [[TMP1]] to i16
 ; CHECK-NEXT:    [[TMP2:%.*]] = sub nsw i16 [[SMAX]], [[UMIN]]
 ; CHECK-NEXT:    [[UMAX:%.*]] = call i16 @llvm.umax.i16(i16 [[M]], i16 1)
 ; CHECK-NEXT:    [[TMP3:%.*]] = udiv i16 [[TMP2]], [[UMAX]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = add i16 [[TMP3]], [[UMIN]]
 ; CHECK-NEXT:    ret i16 [[TMP4]]
 ;
 entry: