Bugfix: SCEV incorrectly marks certain add recurrences as nsw

[sanjoy]

Summary

When creating a scev for sext({X,+,Y}), scev checks if the expression
is equivalent to {sext X,+,zext Y}. If it can prove that, it also
tags the original {X,+,Y} as <nsw>, which is not correct AFAICT.

In the test case I run -scalar-evolution twice because the bug
manifests only once SCEV has run through and seen the sext
expressions (and then does a in-place mutation on {X,+,Y}).

[atrick]

Great catch and test case!

It's not clear to me why the isKnownNonZero check is necessary. Otherwise LGTM.

[sanjoy]

In D7495#120452, @atrick wrote:

Great catch and test case!

It's not clear to me why the isKnownNonZero check is necessary. Otherwise LGTM.

I thought if X is 0 in {S,+,X} then it would "wrap" on every iteration. But ScalarEvolution.h says no-wrap means abs(step) * max-iteration(loop) <= unsigned-max(bitwidth). So this means we cannot assume that a <nw> add-rec will never reach its starting value, right (since step = 0 satisfies the inequality)?

[sanjoy]

In practice it seems the two places that actually do something with <nw> work only with a constant non-zero step size, so it is probably okay to remove the check. But I think the comments in the header file should be changed to state that <nw> means that step is either 0 or abs(step) * max-iteration(loop) <= unsigned-max(bitwidth).

lib/Analysis/ScalarEvolution.cpp

if (AR->isAffine()) {
           }
           // Similar to above, only this time treat the step value as unsigned.
           // This covers loops that count up with an unsigned step.
           OperandExtendedAdd =
             getAddExpr(WideStart,
                        getMulExpr(WideMaxBECount,
                                   getZeroExtendExpr(Step, WideTy)));
           if (SAdd == OperandExtendedAdd) {
-            // Cache knowledge of AR NSW, which is propagated to this AddRec.
-            const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
+            if (isKnownNonZero(Step)) {
+              // If AR wraps around then
+              //
+              //     (Start + I * Step) == Start <=> I * Step == 0
+              //
+              // Assuming Step != 0, there are two possibilities:
+              //
+              //  1. I == 0: this means that the backedge is never taken, and
+              //     hence AR can be marked NW.
+              //
+              //  2. I * Step unsigned-overflowed: this means SAdd !=
+              //     OperandExtendedAdd
+              //
+              // Thus (AR is not NW => SAdd != OperandExtendedAdd) <=>
+              // (SAdd == OperandExtendedAdd => AR is NW)
+              //
+              const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);
+            }
             // Return the expression with the addrec on the outside.
             return getAddRecExpr(getSignExtendAddRecStart(AR, Ty, this),
                                  getZeroExtendExpr(Step, Ty),
                                  L, AR->getNoWrapFlags());
           }
         }
 
         // If the backedge is guarded by a comparison with the pre-inc value

test/Analysis/ScalarEvolution/incorrect-nsw.ll

+; RUN: opt -analyze -scalar-evolution -scalar-evolution < %s | FileCheck %s
+
+define void @bad.nsw() {
+; CHECK-LABEL: Classifying expressions for: @bad.nsw
+; CHECK-LABEL: Classifying expressions for: @bad.nsw
+ entry: 
+  br label %loop
+
+ loop:
+  %i = phi i8 [ -1, %entry ], [ %i.inc, %loop ]
+; CHECK:  %i = phi i8 [ -1, %entry ], [ %i.inc, %loop ]
+; CHECK-NEXT: -->  {-1,+,-128}<nw><%loop>
+; CHECK-NOT: -->  {-1,+,-128}<nsw><%loop>
+
+  %counter = phi i8 [ 0, %entry ], [ %counter.inc, %loop ]
+
+  %i.inc = add i8 %i, -128
+  %i.sext = sext i8 %i to i16
+
+  %counter.inc = add i8 %counter, 1
+  %continue = icmp eq i8 %counter, 1
+  br i1 %continue, label %exit, label %loop
+
+ exit:
+  ret void  
+}
 No newline at end of file