[SCEV] add NW flag for AddExpr (start + stride)

[shchenz]

Summary

%i = phi i4 [ %start, %entry ], [ %i.next, %loop ]
%i.next = add nsw i4 %i, %stride

If we know that SCEV {(%start + %stride), +, %stride} poison value wil cause UB, it is safe to add SCEV::FlagNSW for it. And it should also be safe for (%start + %stride) to add SCEV::FlagNSW.

[reames]

LGTM, but please update your submit comment to emphasize that the only reason this is correct is that we've proven that the inc can't be poison without triggering UB in the original program. (i.e. it's not the fact the add is nsw which lets us do this, it's the fact that the add is nsw and can be proven to trigger UB if actually poison)

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN,
 
   ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV;
 
   // We can add Flags to the post-inc expression only if we
   // know that it is *undefined behavior* for BEValueV to
   // overflow.
   if (auto *BEInst = dyn_cast<Instruction>(BEValueV))
     if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L))
-      (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
+      (void)getAddRecExpr(getAddExpr(StartVal, Accum, Flags), Accum, L, Flags);
 
   return PHISCEV;
 }
 
 const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
   const Loop *L = LI.getLoopFor(PN->getParent());
   if (!L || L->getHeader() != PN->getParent())
     return nullptr;

llvm/trunk/test/Analysis/ScalarEvolution/limit-depth.ll

; CHECK-NEXT:  -->  (2 * 3 * 4 * 5 * 6 * 7 * %a * %b * %c * %d * %e * %f)
   %s1 = mul i32 %p1, %p2
   %s2 = mul i32 %s1, %p3
   ret void
 }
 
 define void @test_sext(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32 %f) {
 ; CHECK-LABEL: @test_sext
 ; CHECK:        %se2 = sext i64 %iv2.inc to i128
-; CHECK-NEXT:   -->  {(1 + (sext i64 {(sext i32 (1 + %a) to i64),+,1}<nsw><%loop> to i128))<nsw>,+,1}<nsw><%loop2>
+; CHECK-NEXT:   -->  {(1 + (sext i64 {(sext i32 (1 + %a)<nsw> to i64),+,1}<nsw><%loop> to i128))<nsw>,+,1}<nsw><%loop2>
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ %a, %entry ], [ %iv.inc, %loop ]
   %iv.inc = add nsw i32 %iv, 1
   %cond = icmp sle i32 %iv.inc, 50
   br i1 %cond, label %loop, label %between

llvm/trunk/test/Analysis/ScalarEvolution/nsw.ll

 
 bb5:                                              ; preds = %bb2
   ret void
 }
 
 declare void @f(i32)
 
 ; CHECK-LABEL: nswnowrap
-; CHECK: --> {(1 + %v)<nsw>,+,1}<nsw><%for.body>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (1 + ((1 + %v)<nsw> smax %v))
+; CHECK: --> {(1 + %v)<nsw>,+,1}<nsw><%for.body>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (2 + %v)
 define void @nswnowrap(i32 %v, i32* %buf) {
 entry:
   %add = add nsw i32 %v, 1
   br label %for.body
 
 for.body:
   %i.04 = phi i32 [ %v, %entry ], [ %inc, %for.body ]
   %inc = add nsw i32 %i.04, 1

llvm/trunk/test/Analysis/ScalarEvolution/trip-count12.ll

 ; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s
 
 ; CHECK: Determining loop execution counts for: @test
-; CHECK: Loop %for.body: backedge-taken count is ((-2 + %len) /u 2)
+; CHECK: Loop %for.body: backedge-taken count is ((-2 + %len)<nsw> /u 2)
 ; CHECK: Loop %for.body: max backedge-taken count is 1073741823
 
 define zeroext i16 @test(i16* nocapture %p, i32 %len) nounwind readonly {
 entry:
   %cmp2 = icmp sgt i32 %len, 1
   br i1 %cmp2, label %for.body.preheader, label %for.end
 
 for.body.preheader:                               ; preds = %entry

llvm/trunk/test/Analysis/ScalarEvolution/trip-count9.ll

loop:
   %i.next = add nsw i4 %i, 2
   %t = icmp slt i4 %i.next, %n
   br i1 %t, label %loop, label %exit
 exit:
   ret void
 }
 
 ; CHECK: Determining loop execution counts for: @nsw_startx
-; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))
+; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x)<nsw> smax %n))
 ; CHECK: Loop %loop: max backedge-taken count is -1
 define void @nsw_startx(i4 %n, i4 %x) {
 entry:
   %s = icmp sgt i4 %n, 0
   br i1 %s, label %loop, label %exit
 loop:
   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
   %i.next = add nsw i4 %i, 1
   %t = icmp slt i4 %i.next, %n
   br i1 %t, label %loop, label %exit
 exit:
   ret void
 }
 
 ; CHECK: Determining loop execution counts for: @nsw_startx_step2
-; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax %n)) /u 2)
+; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x)<nsw> smax %n)) /u 2)
 ; CHECK: Loop %loop: max backedge-taken count is 7
 define void @nsw_startx_step2(i4 %n, i4 %x) {
 entry:
   %s = icmp sgt i4 %n, 0
   br i1 %s, label %loop, label %exit
 loop:
   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
   %i.next = add nsw i4 %i, 2
loop:
   %i.next = add nsw i4 %i, 2
   %t = icmp slt i4 %i.next, %m
   br i1 %t, label %loop, label %exit
 exit:
   ret void
 }
 
 ; CHECK: Determining loop execution counts for: @even_nsw_startx
-; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))
+; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x)<nsw> smax (2 * %n)))
 ; CHECK: Loop %loop: max backedge-taken count is -2
 define void @even_nsw_startx(i4 %n, i4 %x) {
 entry:
   %m = shl i4 %n, 1
   %s = icmp sgt i4 %m, 0
   br i1 %s, label %loop, label %exit
 loop:
   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
   %i.next = add nsw i4 %i, 1
   %t = icmp slt i4 %i.next, %m
   br i1 %t, label %loop, label %exit
 exit:
   ret void
 }
 
 ; CHECK: Determining loop execution counts for: @even_nsw_startx_step2
-; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2)
+; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x)<nsw> smax (2 * %n))) /u 2)
 ; CHECK: Loop %loop: max backedge-taken count is 7
 define void @even_nsw_startx_step2(i4 %n, i4 %x) {
 entry:
   %m = shl i4 %n, 1
   %s = icmp sgt i4 %m, 0
   br i1 %s, label %loop, label %exit
 loop:
   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
   %i.next = add nsw i4 %i, 2
   %t = icmp slt i4 %i.next, %m
   br i1 %t, label %loop, label %exit
 exit:
   ret void
 }