[SCEV] Infer NSW when subtracting expressions with the same signs

[dmakogon]

Summary

When creating a SCEV for X - Y infer NSW for the resulting expression if X and Y are either both non-positive or non-negative.
In these cases there can be no signed overflow.

[mkazantsev]

I'd suspect that contextual analysis on SCEV creation might have negative CT impact.

llvm/lib/Analysis/ScalarEvolution.cpp

7717

There is certain semblance b/w what you are doing and what willNotOverflow is doing. I also have an improvement for it that makes it support sub with context: D148618. I think it's a superset of (w/ this patch) of what you are trying to achieve.

Will calling this function w/ right context help here? If yes, you could do it for both add and sub.

I have a concern about using of context-aware checkers in SCEV creation. It might be OK since it is only done once, but I'm not sure what's the real impact on CT. Might be expensive, @nikic WDYT?

7728

If both LHS and RHS have loops, you can use the one that is lower.

llvm/lib/Analysis/ScalarEvolution.cpp

 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/SaveAndRestore.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/LoopUtils.h"
 #include <algorithm>
 #include <cassert>
 #include <climits>
 #include <cstdint>
 #include <cstdlib>
 #include <map>
 #include <memory>
 #include <numeric>
case Instruction::URem:
       RHS = getSCEV(BO->RHS);
       return getURemExpr(LHS, RHS);
     case Instruction::Sub: {
       SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
       if (BO->Op)
         Flags = getNoWrapFlagsFromUB(BO->Op);
       LHS = getSCEV(BO->LHS);
       RHS = getSCEV(BO->RHS);
+
+      // Try to prove NSW based on operands signs. Subtracting non-negative
+      // values cannot overflow, as well as subtracting non-positives ones.
+      if (!hasFlags(Flags, SCEV::FlagNSW)) {
+        // If one of the operands is an AddRec, then the resulting expression
+        // makes sense only in the loop of that AddRec, so we can safely use the
+        // loop as context to get facts about operands signs.
+        const Loop *L = nullptr;
+        if (auto *AR = dyn_cast<SCEVAddRecExpr>(LHS))
+          L = AR->getLoop();
+        if (!L)
+          if (auto *AR = dyn_cast<SCEVAddRecExpr>(RHS))
+            L = AR->getLoop();
+        enum class SCEVExprSign { NonNegative, NonPositive, Unknown };
+        auto GetExprSign = [&](const SCEV *S) -> SCEVExprSign {
+          if (isKnownNonNegative(S) ||
+              (L && isKnownNonNegativeInLoop(S, L, *this)))
+            return SCEVExprSign::NonNegative;
+          if (isKnownNonPositive(S) ||
+              (L && isKnownNonPositiveInLoop(S, L, *this)))
+            return SCEVExprSign::NonPositive;
+          return SCEVExprSign::Unknown;
+        };
+        auto LHSSign = GetExprSign(LHS);
+        auto RHSSign = GetExprSign(RHS);
+        if (LHSSign != SCEVExprSign::Unknown && LHSSign == RHSSign)
+          Flags = setFlags(Flags, SCEV::FlagNSW);
+      }
+
       return getMinusSCEV(LHS, RHS, Flags);
     }
     case Instruction::And:
       // For an expression like x&255 that merely masks off the high bits,
       // use zext(trunc(x)) as the SCEV expression.
       if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
         if (CI->isZero())
           return getSCEV(BO->RHS);

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

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s
 
 define i32 @test_1_non_negative(i32 %n) {
 ; CHECK-LABEL: 'test_1_non_negative'
 ; CHECK-NEXT:  Classifying expressions for: @test_1_non_negative
 ; 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:    %a = sub i32 %n, %i
-; CHECK-NEXT:    --> {%n,+,-1}<nw><%loop> U: full-set S: full-set Exits: (1 + (-1 * (1 smax %n))<nsw> + %n) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {%n,+,-1}<nsw><%loop> U: full-set S: full-set Exits: (1 + (-1 * (1 smax %n))<nsw> + %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_1_non_negative
 ; 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>
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + (1 smax %n))<nsw>
 ; CHECK-NEXT:   Predicates:

 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}<nsw><%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:  Classifying expressions for: @test_step_1_flags
 ; DEFAULT-NEXT:    %n.minus.1 = sub nsw i32 %n, 1
 ; DEFAULT-NEXT:    --> (-1 + %n) U: full-set S: full-set
 ; DEFAULT-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 ; 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:    --> {%n,+,-1}<nsw><%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}<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 }

 ; EXPENSIVE_SHARPENING-NEXT:  Classifying expressions for: @test_step_1_flags
 ; EXPENSIVE_SHARPENING-NEXT:    %n.minus.1 = sub nsw i32 %n, 1
 ; EXPENSIVE_SHARPENING-NEXT:    --> (-1 + %n) U: full-set S: full-set
 ; EXPENSIVE_SHARPENING-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
 ; 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:    --> {%n,+,-1}<nsw><%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}<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 }