[SCEV] Generalize MatchBinaryAddToConst to support non-add expressions.

[fhahn]

Summary

This patch generalizes MatchBinaryAddToConst to support matching
(A + C1), (A + C2), instead of just matching (A + C1), A.

The existing cases can be handled by treating non-add expressions A as
A + 0.

[mkazantsev]

I think this is wrong.

llvm/lib/Analysis/ScalarEvolution.cpp

10129–10130

Is lack of nsw in (X + C2) intentional? If yes, the counter-example to this is

X = SINT_MIN
C1 = 1
C2 = -1

(X + C1)<nsw> = SINT_MIN + 1 <= (X - 1) = SINT_MAX, but obviously C1 > C2.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

10129–10130

I'm not sure whether two-ways implication is required here, or one way implication is enough. It was two-ways in old code. If I'm wrong here, please let me know.

[fhahn]

Add <nsw> and <nuw> to the sub-expressions where it was missing.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

10129–10130

The comment is missing <nsw> from the second expression, the actual checks enforce nsw for both (same for nuw below). I updated the comment.

I'm not sure whether two-ways implication is required here, or one way implication is enough. It was two-ways in old code. If I'm wrong here, please let me know.

The new reasoning should handle both previous checks I think , as, X s<= (X + C) treated as X + 0 s<= (X + C) and (X + C) s<= X is treated as (X + C) s<= X + 0

[mkazantsev]

Ok, thanks for clarification. With this clarification looks fine. Please give me some time to run it through my fuzz corps.

[reames]

For an optional follow up change, I believe we can avoid checking the wrap flags for one operand, if C1 and C2 share the same sign.

Consider:
(X + C1) s<= (X + C2)<nsw> if C1 s<= C2 and both are positive
(X + C1)<nsw> s<= (X + C2) if C1 s<= C2 and both are negative

If X + C2 does not signed wrap, and C1 s<= C2, then X+C1 also can not wrap if both are positive. As a result, we don't need to check for the wrap flag on LHS as we've proven it. The negative case is the inverse. The mixed sign case does require both checks as the two could overflow off different ends of the range. (Actually, can they? Is there any single value of X which you can add a value to and both wrap above and wrap below? Might be worth further thought.)

It's also worth noting that we can *disprove* cases here as well.

Consider:
// (X + C1)<nsw> s<= (X + C2)<nsw> == false if C1 s> C2.

This would require a change to the API (probably returning an optional bool), but might be interesting to short circuit later checks. Again, follow up change (if interested).

[mkazantsev]

Ok, looks good!

[lebedev.ri]

Looks good to me

[fhahn]

For an optional follow up change, I believe we can avoid checking the wrap flags for one operand, if C1 and C2 share the same sign.

Thanks, I'll try to look into this as a follow-up.

In D104634#2830649, @mkazantsev wrote:

Ok, thanks for clarification. With this clarification looks fine. Please give me some time to run it through my fuzz corps.

Thanks for the testing ahead of landing! I'll wait a day or so with landing, in case one of my earlier patches surfaces any issues.

[fhahn]

Remove test changes that depend on D102834.

llvm/lib/Analysis/ScalarEvolution.cpp

if (CmpInst::isSigned(Pred))
     return CheckRanges(getSignedRange(LHS), getSignedRange(RHS));
 
   return CheckRanges(getUnsignedRange(LHS), getUnsignedRange(RHS));
 }
 
 bool ScalarEvolution::isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred,
                                                     const SCEV *LHS,
                                                     const SCEV *RHS) {
-  // Match Result to (X + Y)<ExpectedFlags> where Y is a constant integer.
-  // Return Y via OutY.
-  auto MatchBinaryAddToConst =
-      [this](const SCEV *Result, const SCEV *X, APInt &OutY,
+  // Match X to (A + C1)<ExpectedFlags> and Y to (A + C2)<ExpectedFlags>, where
+  // C1 and C2 are constant integers. If either X or Y are not add expressions,
+  // consider them as X + 0 and Y + 0 respectively. C1 and C2 are returned via
+  // OutC1 and OutC2.
+  auto MatchBinaryAddToConst = [this](const SCEV *X, const SCEV *Y,
+                                      APInt &OutC1, APInt &OutC2,
                                       SCEV::NoWrapFlags ExpectedFlags) {
-    const SCEV *NonConstOp, *ConstOp;
-    SCEV::NoWrapFlags FlagsPresent;
+    const SCEV *XNonConstOp, *XConstOp;
+    const SCEV *YNonConstOp, *YConstOp;
+    SCEV::NoWrapFlags XFlagsPresent;
+    SCEV::NoWrapFlags YFlagsPresent;
 
-    if (!splitBinaryAdd(Result, ConstOp, NonConstOp, FlagsPresent) ||
-        !isa<SCEVConstant>(ConstOp) || NonConstOp != X)
+    if (!splitBinaryAdd(X, XConstOp, XNonConstOp, XFlagsPresent)) {
+      XConstOp = getZero(X->getType());
+      XNonConstOp = X;
+      XFlagsPresent = ExpectedFlags;
+    }
+    if (!isa<SCEVConstant>(XConstOp) ||
+        (XFlagsPresent & ExpectedFlags) != ExpectedFlags)
+      return false;
+
+    if (!splitBinaryAdd(Y, YConstOp, YNonConstOp, YFlagsPresent)) {
+      YConstOp = getZero(Y->getType());
+      YNonConstOp = Y;
+      YFlagsPresent = ExpectedFlags;
+    }
+
+    if (!isa<SCEVConstant>(YConstOp) ||
+        (YFlagsPresent & ExpectedFlags) != ExpectedFlags)
+      return false;
+
+    if (YNonConstOp != XNonConstOp)
       return false;
 
-    OutY = cast<SCEVConstant>(ConstOp)->getAPInt();
-    return (FlagsPresent & ExpectedFlags) == ExpectedFlags;
+    OutC1 = cast<SCEVConstant>(XConstOp)->getAPInt();
+    OutC2 = cast<SCEVConstant>(YConstOp)->getAPInt();
+
+    return true;
   };
 
-  APInt C;
+  APInt C1;
+  APInt C2;
 
   switch (Pred) {
   default:
     break;
 
   case ICmpInst::ICMP_SGE:
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_SLE:
-    // X s<= (X + C)<nsw> if C >= 0
-    if (MatchBinaryAddToConst(RHS, LHS, C, SCEV::FlagNSW) && C.isNonNegative())
+    // (X + C1)<nsw> s<= (X + C2)<nsw> if C1 s<= C2.
+    if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.sle(C2))
       return true;
 
-    // (X + C)<nsw> s<= X if C <= 0
-    if (MatchBinaryAddToConst(LHS, RHS, C, SCEV::FlagNSW) &&
-        !C.isStrictlyPositive())
-      return true;
     break;
 
   case ICmpInst::ICMP_SGT:
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_SLT:
-    // X s< (X + C)<nsw> if C > 0
-    if (MatchBinaryAddToConst(RHS, LHS, C, SCEV::FlagNSW) &&
-        C.isStrictlyPositive())
+    // (X + C1)<nsw> s< (X + C2)<nsw> if C1 s< C2.
+    if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.slt(C2))
       return true;
 
-    // (X + C)<nsw> s< X if C < 0
-    if (MatchBinaryAddToConst(LHS, RHS, C, SCEV::FlagNSW) && C.isNegative())
-      return true;
     break;
 
   case ICmpInst::ICMP_UGE:
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_ULE:
-    // X u<= (X + C)<nuw> for any C
-    if (MatchBinaryAddToConst(RHS, LHS, C, SCEV::FlagNUW))
+    // (X + C1)<nuw> u<= (X + C2)<nuw> for C1 u<= C2.
+    if (MatchBinaryAddToConst(RHS, LHS, C2, C1, SCEV::FlagNUW) && C1.ule(C2))
       return true;
+
     break;
 
   case ICmpInst::ICMP_UGT:
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_ULT:
-    // X u< (X + C)<nuw> if C != 0
-    if (MatchBinaryAddToConst(RHS, LHS, C, SCEV::FlagNUW) && !C.isNullValue())
+    // (X + C1)<nuw> u< (X + C2)<nuw> if C1 u< C2.
+    if (MatchBinaryAddToConst(RHS, LHS, C2, C1, SCEV::FlagNUW) && C1.ult(C2))
       return true;
     break;
   }
 
   return false;
 }
 
 bool ScalarEvolution::isKnownPredicateViaSplitting(ICmpInst::Predicate Pred,