[SCEV] Preserve NSW for AddRec multiplied by -1 if it cannot be signed minimum

[dmakogon]

Summary

This preserves NSW flag for AddRecs multiplied by -1 if we can prove via constant ranges that the AddRec cannot be signed minimum.
An explanation: Let M be signed minimum. If AddRec's range contains M, then M * (-1) will stay M and (M + 1) * (-1) will be signed maximum, so we get a signed overflow.
In all other cases if an AddRec didn't signed overflow, then AddRec * (-1) wouldn't too.

[mkazantsev]

LG, please hold this for couple of days in case if someone has objections.

[nikic]

Can you please rebase this to current main? It doesn't apply cleanly.

llvm/lib/Analysis/ScalarEvolution.cpp

3203

No need to check this if there's no nsw flag in the first place?

[dmakogon]

In D148084#4260667, @nikic wrote:

Can you please rebase this to current main? It doesn't apply cleanly.

Should apply now, forgot to push a test fixup patch before this one.

[dmakogon]

Check AddRec range only if if already has nsw

llvm/lib/Analysis/ScalarEvolution.cpp

if (Ops.size() == 2) {
           if (AnyFolded)
             return getAddExpr(NewOps, SCEV::FlagAnyWrap, Depth + 1);
         } else if (const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
           // Negation preserves a recurrence's no self-wrap property.
           SmallVector<const SCEV *, 4> Operands;
           for (const SCEV *AddRecOp : AddRec->operands())
             Operands.push_back(getMulExpr(Ops[0], AddRecOp, SCEV::FlagAnyWrap,
                                           Depth + 1));
-
+          // Let M be the minimum representable signed value. AddRec with nsw
+          // multiplied by -1 can have signed overflow if and only if it takes a
+          // value of M: M * (-1) would stay M and (M + 1) * (-1) would be the
+          // maximum signed value. In all other cases signed overflow is
+          // impossible.
+          auto FlagsMask = SCEV::FlagNW;
+          if (hasFlags(AddRec->getNoWrapFlags(), SCEV::FlagNSW)) {
+            auto MinInt =
+                APInt::getSignedMinValue(getTypeSizeInBits(AddRec->getType()));
+            if (getSignedRangeMin(AddRec) != MinInt)
+              FlagsMask = setFlags(FlagsMask, SCEV::FlagNSW);
+          }
           return getAddRecExpr(Operands, AddRec->getLoop(),
-                               AddRec->getNoWrapFlags(SCEV::FlagNW));
+                               AddRec->getNoWrapFlags(FlagsMask));
         }
       }
     }
   }
 
   // Skip over the add expression until we get to a multiply.
   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
     ++Idx;

llvm/test/Analysis/ScalarEvolution/addrec-sub-nsw.ll

 define i32 @test_2_non_positive(i32 %n) {
 ; CHECK-LABEL: 'test_2_non_positive'
 ; CHECK-NEXT:  Classifying expressions for: @test_2_non_positive
 ; CHECK-NEXT:    %minus.n = mul i32 %n, -1
 ; CHECK-NEXT:    --> (-1 * %n) U: full-set S: full-set
 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + (1 smax %n))<nsw> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %minus.i = mul i32 %i, -1
-; CHECK-NEXT:    --> {0,+,-1}<nw><%loop> U: [-2147483646,1) S: [-2147483646,1) Exits: (1 + (-1 * (1 smax %n))<nsw>)<nsw> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,-1}<nsw><%loop> U: [-2147483646,1) S: [-2147483646,1) Exits: (1 + (-1 * (1 smax %n))<nsw>)<nsw> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %a = sub i32 %minus.n, %minus.i
 ; CHECK-NEXT:    --> {(-1 * %n),+,1}<nw><%loop> U: full-set S: full-set Exits: (-1 + (-1 * %n) + (1 smax %n)) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %i.next = add nuw nsw i32 %i, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: (1 smax %n) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_2_non_positive
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (1 smax %n))<nsw>
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 2147483646
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (1 smax %n))<nsw>

llvm/test/Analysis/ScalarEvolution/decrementing_addrecs.ll

 ; DEFAULT-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + %n) LoopDispositions: { %loop: Computable }
 ; DEFAULT-NEXT:    %j = phi i32 [ %n.minus.1, %entry ], [ %j.next, %loop ]
 ; DEFAULT-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: full-set S: full-set Exits: 0 LoopDispositions: { %loop: Computable }
 ; DEFAULT-NEXT:    %a = sub i32 %n, %i
 ; DEFAULT-NEXT:    --> {%n,+,-1}<nw><%loop> U: full-set S: full-set Exits: 1 LoopDispositions: { %loop: Computable }
 ; DEFAULT-NEXT:    %b = sub i32 %n.minus.1, %i
 ; DEFAULT-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: full-set S: full-set Exits: 0 LoopDispositions: { %loop: Computable }
 ; DEFAULT-NEXT:    %c = sub i32 2147483647, %i
-; DEFAULT-NEXT:    --> {2147483647,+,-1}<nw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: (-2147483648 + (-1 * %n)) LoopDispositions: { %loop: Computable }
+; DEFAULT-NEXT:    --> {2147483647,+,-1}<nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: (-2147483648 + (-1 * %n)) LoopDispositions: { %loop: Computable }
 ; DEFAULT-NEXT:    %i.next = add nuw nsw i32 %i, 1
 ; DEFAULT-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %n LoopDispositions: { %loop: Computable }
 ; DEFAULT-NEXT:    %j.next = add nsw i32 %j, -1
 ; DEFAULT-NEXT:    --> {(-2 + %n),+,-1}<nw><%loop> U: full-set S: full-set Exits: -1 LoopDispositions: { %loop: Computable }
 ; DEFAULT-NEXT:  Determining loop execution counts for: @test_step_1_flags
 ; DEFAULT-NEXT:  Loop %loop: backedge-taken count is (-1 + %n)
 ; DEFAULT-NEXT:  Loop %loop: constant max backedge-taken count is 2147483646
 ; DEFAULT-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %n)

 ; EXPENSIVE_SHARPENING-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + %n) LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %j = phi i32 [ %n.minus.1, %entry ], [ %j.next, %loop ]
 ; EXPENSIVE_SHARPENING-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: 0 LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %a = sub i32 %n, %i
 ; EXPENSIVE_SHARPENING-NEXT:    --> {%n,+,-1}<nw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: 1 LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %b = sub i32 %n.minus.1, %i
 ; EXPENSIVE_SHARPENING-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: 0 LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %c = sub i32 2147483647, %i
-; EXPENSIVE_SHARPENING-NEXT:    --> {2147483647,+,-1}<nw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: (-2147483648 + (-1 * %n)) LoopDispositions: { %loop: Computable }
+; EXPENSIVE_SHARPENING-NEXT:    --> {2147483647,+,-1}<nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: (-2147483648 + (-1 * %n)) LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %i.next = add nuw nsw i32 %i, 1
 ; EXPENSIVE_SHARPENING-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %n LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:    %j.next = add nsw i32 %j, -1
 ; EXPENSIVE_SHARPENING-NEXT:    --> {(-2 + %n),+,-1}<nsw><%loop> U: full-set S: [-1,2147483646) Exits: -1 LoopDispositions: { %loop: Computable }
 ; EXPENSIVE_SHARPENING-NEXT:  Determining loop execution counts for: @test_step_1_flags
 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: backedge-taken count is (-1 + %n)
 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: constant max backedge-taken count is 2147483646
 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %n)

llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll

 ; CHECK-NEXT:  -->  {2,+,1}<%loop1>
 ; CHECK:       %tmp4 = add nuw nsw i64 %tmp, 1
 ; CHECK-NEXT:  -->  {3,+,1}<nuw><%loop1>
 ; CHECK:       %tmp7 = phi i64 [ %tmp15, %loop2 ], [ 2, %loop1 ]
 ; CHECK-NEXT:  -->  {2,+,1}<nuw><nsw><%loop2> U: [2,9223372036854775807) S: [2,9223372036854775807)
 ; CHECK:       %tmp9 = sext i8 %tmp8 to i64
 ; CHECK-NEXT:  -->  (sext i8 %tmp8 to i64) U: [-128,128) S: [-128,128)
 ; CHECK:       %tmp10 = sub i64 %tmp9, %tmp7
-; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i64) + {-2,+,-1}<nw><%loop2>) U: [9223372036854775682,126) S: [9223372036854775682,126)
+; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i64) + {-2,+,-1}<nsw><%loop2>) U: [9223372036854775682,126) S: [9223372036854775682,126)
 ; CHECK:       %tmp11 = add i64 %tmp10, undef
 ; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i64) + {(-2 + undef),+,-1}<nw><%loop2>)
 ; CHECK:       %tmp13 = trunc i64 %tmp11 to i32
 ; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i32) + {(-2 + (trunc i64 undef to i32)),+,-1}<%loop2>)
 ; CHECK:       %tmp14 = sub i32 %tmp13, %tmp2
 ; `{{[{][{]}}` is the ugliness needed to match `{{`
 ; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i32) + {{[{][{]}}(-4 + (trunc i64 undef to i32)),+,-1}<%loop1>,+,-1}<%loop2>)
 ; CHECK:       %tmp15 = add nuw nsw i64 %tmp7, 1

llvm/test/Analysis/ScalarEvolution/sext-iv-2.ll

 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
 
 ; CHECK: %tmp3 = sext i8 %tmp2 to i32
 ; CHECK: -->  (sext i8 {0,+,1}<%bb1> to i32) U: [-128,128) S: [-128,128)               Exits: -1
 ; CHECK: %tmp4 = mul i32 %tmp3, %i.02
-; CHECK: -->  ((sext i8 {0,+,1}<%bb1> to i32) * {0,+,1}<nuw><nsw><%bb>) U: [-3968,3938) S: [-3968,3938)                Exits: {0,+,-1}<nw><%bb>
+; CHECK: -->  ((sext i8 {0,+,1}<%bb1> to i32) * {0,+,1}<nuw><nsw><%bb>) U: [-3968,3938) S: [-3968,3938)                Exits: {0,+,-1}<nsw><%bb>
 
 ; These sexts are not foldable.
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64"
 
 @table = common global [32 x [256 x i32]] zeroinitializer, align 32    ; <ptr> [#uses=2]
 
 define i32 @main() nounwind {