[ValueTracking] Add subtraction support for setLimitsForBinOp

[AZero13]

We can determine the range from a subtraction if it has nsw or nuw.

https://alive2.llvm.org/ce/z/tXAKVV

[llvmbot]

@llvm/pr-subscribers-llvm-transforms

@llvm/pr-subscribers-llvm-analysis

Author: AZero13 (AZero13)

Changes

---

Full diff: https://github.com/llvm/llvm-project/pull/143618.diff

1 Files Affected:

• (modified) llvm/lib/Analysis/ValueTracking.cpp (+54)

diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index d8c1096049dce..88e8ea4878fe1 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -9576,6 +9576,60 @@ static void setLimitsForBinOp(const BinaryOperator &BO, APInt &Lower,
   unsigned Width = Lower.getBitWidth();
   const APInt *C;
   switch (BO.getOpcode()) {
+  case Instruction::Sub:
+    if (match(BO.getOperand(1), m_APInt(C)) && !C->isZero()) {
+      bool HasNSW = IIQ.hasNoSignedWrap(&BO);
+      bool HasNUW = IIQ.hasNoUnsignedWrap(&BO);
+
+      // If the caller expects a signed compare, then try to use a signed range.
+      // Otherwise if both no-wraps are set, use the unsigned range because it
+      // is never larger than the signed range. Example:
+      // "sub nuw nsw i8 X, -2" is unsigned [0, 127] vs. signed [-128, 126].
+      if (PreferSignedRange && HasNSW && HasNUW)
+        HasNUW = false;
+
+      if (HasNUW) {
+        // 'sub nuw x, C' produces [0, UINT_MAX - C].
+        Upper = APInt::getAllOnes(Width) - *C + 1;
+      } else if (HasNSW) {
+        if (C->isNegative()) {
+          // 'sub nsw x, -C' produces [SINT_MIN + C, SINT_MAX].
+          Lower = APInt::getSignedMinValue(Width) + *C;
+          Upper = APInt::getSignedMaxValue(Width) + 1;
+        } else {
+          // 'sub nsw x, +C' produces [SINT_MIN, SINT_MAX - C].
+          Lower = APInt::getSignedMinValue(Width);
+          Upper = APInt::getSignedMaxValue(Width) - *C + 1;
+        }
+      }
+    } else if (match(BO.getOperand(0), m_APInt(C))) {
+      bool HasNSW = IIQ.hasNoSignedWrap(&BO);
+      bool HasNUW = IIQ.hasNoUnsignedWrap(&BO);
+
+      // If the caller expects a signed compare, then try to use a signed range.
+      // Otherwise if both no-wraps are set, use the unsigned range because it
+      // is never larger than the signed range. Example:
+      // "sub nuw nsw i8 X, -2" is unsigned [0, 127] vs. signed [-128, 126].
+      if (PreferSignedRange && HasNSW && HasNUW)
+        HasNUW = false;
+
+      if (HasNUW) {
+        // 'sub nuw c, x' produces [0, C].
+        Upper = *C + 1;
+      } else if (HasNSW) {
+        if (C->isNegative()) {
+          // 'sub nsw C, x' produces [SINT_MIN, SINT_MAX - C].
+          Lower = APInt::getSignedMinValue(Width);
+          Upper = APInt::getSignedMaxValue(Width) - *C + 1;
+        } else {
+          // Note that sub 0, INT_MIN is not NSW. It techically is a signed wrap
+          // 'sub nsw C, x' produces [SINT_MIN + 1 + C, SINT_MAX].
+          Lower = APInt::getSignedMinValue(Width) + *C + 1;
+          Upper = APInt::getSignedMaxValue(Width) + 1;
+        }
+      }
+    }
+    break;
   case Instruction::Add:
     if (match(BO.getOperand(1), m_APInt(C)) && !C->isZero()) {
       bool HasNSW = IIQ.hasNoSignedWrap(&BO);

[dtcxzyw]

@AZero13 Please avoid rebasing and force-pushing on your branches... If you don't need pre-commit tests from newer commits, just append a new commit for your change.

[dtcxzyw]

LG