[ConstantRange] Support subtraction in makeGuaranteedNoWrapRegion.

[jgalenson]

Summary

Previously ConstantRange::makeGuaranteedNoWrapRegion only handled addition. This adds support for subtraction.

[sanjoy]

lgtm

llvm/trunk/include/llvm/IR/ConstantRange.h

public:
   static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred,
                                            const APInt &Other);
 
   /// Return the largest range containing all X such that "X BinOpC Y" is
   /// guaranteed not to wrap (overflow) for all Y in Other.
   ///
   /// NB! The returned set does *not* contain **all** possible values of X for
   /// which "X BinOpC Y" does not wrap -- some viable values of X may be
-  /// missing, so you cannot use this to constrain X's range.  E.g. in the last
-  /// example, "(-2) + 1" is both nsw and nuw (so the "X" could be -2), but (-2)
-  /// is not in the set returned.
+  /// missing, so you cannot use this to constrain X's range.  E.g. in the
+  /// fourth example, "(-2) + 1" is both nsw and nuw (so the "X" could be -2),
+  /// but (-2) is not in the set returned.
   ///
   /// Examples:
   ///  typedef OverflowingBinaryOperator OBO;
   ///  #define MGNR makeGuaranteedNoWrapRegion
   ///  MGNR(Add, [i8 1, 2), OBO::NoSignedWrap) == [-128, 127)
   ///  MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap) == [0, -1)
   ///  MGNR(Add, [i8 0, 1), OBO::NoUnsignedWrap) == Full Set
   ///  MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap | OBO::NoSignedWrap)
   ///    == [0,INT_MAX)
   ///  MGNR(Add, [i8 -1, 6), OBO::NoSignedWrap) == [INT_MIN+1, INT_MAX-4)
+  ///  MGNR(Sub, [i8 1, 2), OBO::NoSignedWrap) == [-127, 128)
+  ///  MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap) == [1, 0)
+  ///  MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap | OBO::NoSignedWrap)
+  ///    == [1,INT_MAX)
   static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
                                                   const ConstantRange &Other,
                                                   unsigned NoWrapKind);
 
   /// Set up \p Pred and \p RHS such that
   /// ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.  Return true if
   /// successful.
   bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const;

llvm/trunk/lib/IR/ConstantRange.cpp

assert(BinOp >= Instruction::BinaryOpsBegin &&
          BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
 
   assert((NoWrapKind == OBO::NoSignedWrap ||
           NoWrapKind == OBO::NoUnsignedWrap ||
           NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
          "NoWrapKind invalid!");
 
   unsigned BitWidth = Other.getBitWidth();
-  if (BinOp != Instruction::Add)
+  ConstantRange Result(BitWidth);
+
+  switch (BinOp) {
+  default:
     // Conservative answer: empty set
     return ConstantRange(BitWidth, false);
 
+  case Instruction::Add:
     if (auto *C = Other.getSingleElement())
       if (C->isNullValue())
         // Full set: nothing signed / unsigned wraps when added to 0.
         return ConstantRange(BitWidth);
-
-  ConstantRange Result(BitWidth);
-
     if (NoWrapKind & OBO::NoUnsignedWrap)
       Result =
           SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
                                                 -Other.getUnsignedMax()));
-
     if (NoWrapKind & OBO::NoSignedWrap) {
       const APInt &SignedMin = Other.getSignedMin();
       const APInt &SignedMax = Other.getSignedMax();
-
       if (SignedMax.isStrictlyPositive())
         Result = SubsetIntersect(
             Result,
             ConstantRange(APInt::getSignedMinValue(BitWidth),
                           APInt::getSignedMinValue(BitWidth) - SignedMax));
-
       if (SignedMin.isNegative())
         Result = SubsetIntersect(
-          Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
-                                APInt::getSignedMinValue(BitWidth)));
+            Result,
+            ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
     }
+    return Result;
 
+  case Instruction::Sub:
+    if (auto *C = Other.getSingleElement())
+      if (C->isNullValue())
+        // Full set: nothing signed / unsigned wraps when subtracting 0.
+        return ConstantRange(BitWidth);
+    if (NoWrapKind & OBO::NoUnsignedWrap)
+      Result =
+          SubsetIntersect(Result, ConstantRange(Other.getUnsignedMax(),
+                                                APInt::getMinValue(BitWidth)));
+    if (NoWrapKind & OBO::NoSignedWrap) {
+      const APInt &SignedMin = Other.getSignedMin();
+      const APInt &SignedMax = Other.getSignedMax();
+      if (SignedMax.isStrictlyPositive())
+        Result = SubsetIntersect(
+            Result,
+            ConstantRange(APInt::getSignedMinValue(BitWidth) + SignedMax,
+                          APInt::getSignedMinValue(BitWidth)));
+      if (SignedMin.isNegative())
+        Result = SubsetIntersect(
+            Result,
+            ConstantRange(APInt::getSignedMinValue(BitWidth),
+                          APInt::getSignedMinValue(BitWidth) + SignedMin));
+    }
     return Result;
   }
+}
 
 bool ConstantRange::isFullSet() const {
   return Lower == Upper && Lower.isMaxValue();
 }
 
 bool ConstantRange::isEmptySet() const {
   return Lower == Upper && Lower.isMinValue();
 }

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E;
       (void)I.sadd_ov(C, Overflow);
       EXPECT_FALSE(Overflow);
 
       (void)I.uadd_ov(C, Overflow);
       EXPECT_FALSE(Overflow);
     }
   }
 
+  for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
+    APInt C(4, Const, true /* = isSigned */);
+
+    auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
+        Instruction::Sub, C, OBO::NoUnsignedWrap);
+
+    EXPECT_FALSE(NUWRegion.isEmptySet());
+
+    auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
+        Instruction::Sub, C, OBO::NoSignedWrap);
+
+    EXPECT_FALSE(NSWRegion.isEmptySet());
+
+    auto NoWrapRegion = ConstantRange::makeGuaranteedNoWrapRegion(
+        Instruction::Sub, C, OBO::NoSignedWrap | OBO::NoUnsignedWrap);
+
+    EXPECT_FALSE(NoWrapRegion.isEmptySet());
+    EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion));
+
+    for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
+         ++I) {
+      bool Overflow = false;
+      (void)I.usub_ov(C, Overflow);
+      EXPECT_FALSE(Overflow);
+    }
+
+    for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
+         ++I) {
+      bool Overflow = false;
+      (void)I.ssub_ov(C, Overflow);
+      EXPECT_FALSE(Overflow);
+    }
+
+    for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E;
+         ++I) {
+      bool Overflow = false;
+
+      (void)I.ssub_ov(C, Overflow);
+      EXPECT_FALSE(Overflow);
+
+      (void)I.usub_ov(C, Overflow);
+      EXPECT_FALSE(Overflow);
+    }
+  }
+
   auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
       Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
       OBO::NoSignedWrap);
   EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
               NSWForAllValues.getSingleElement()->isMinValue());
 
+  NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
+      Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
+      OBO::NoSignedWrap);
+  EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
+              NSWForAllValues.getSingleElement()->isMaxValue());
+
   auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
       Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
       OBO::NoUnsignedWrap);
   EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
               NUWForAllValues.getSingleElement()->isMinValue());
 
+  NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
+      Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
+      OBO::NoUnsignedWrap);
+  EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
+              NUWForAllValues.getSingleElement()->isMaxValue());
+
   auto NUWAndNSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
       Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
       OBO::NoUnsignedWrap | OBO::NoSignedWrap);
   EXPECT_TRUE(NUWAndNSWForAllValues.isSingleElement() &&
               NUWAndNSWForAllValues.getSingleElement()->isMinValue());
 
+  NUWAndNSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
+      Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
+      OBO::NoUnsignedWrap | OBO::NoSignedWrap);
+  EXPECT_TRUE(NUWAndNSWForAllValues.isSingleElement() &&
+              NUWAndNSWForAllValues.getSingleElement()->isMaxValue());
+
+  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
+      Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
+  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
+      Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
+  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
+      Instruction::Add, APInt(32, 0),
+      OBO::NoUnsignedWrap | OBO::NoSignedWrap).isFullSet());
+  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
+      Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
+  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
+      Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
+  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
+      Instruction::Sub, APInt(32, 0),
+      OBO::NoUnsignedWrap | OBO::NoSignedWrap).isFullSet());
+
   ConstantRange OneToFive(APInt(32, 1), APInt(32, 6));
   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
                 Instruction::Add, OneToFive, OBO::NoSignedWrap),
             ConstantRange(APInt::getSignedMinValue(32),
                           APInt::getSignedMaxValue(32) - 4));
   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
                 Instruction::Add, OneToFive, OBO::NoUnsignedWrap),
             ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5));
   EXPECT_EQ(
       ConstantRange::makeGuaranteedNoWrapRegion(
           Instruction::Add, OneToFive, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
       ConstantRange(APInt::getMinValue(32), APInt::getSignedMaxValue(32) - 4));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Sub, OneToFive, OBO::NoSignedWrap),
+            ConstantRange(APInt::getSignedMinValue(32) + 5,
+                          APInt::getSignedMinValue(32)));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Sub, OneToFive, OBO::NoUnsignedWrap),
+            ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32)));
+  EXPECT_EQ(
+      ConstantRange::makeGuaranteedNoWrapRegion(
+          Instruction::Sub, OneToFive, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
+      ConstantRange(APInt::getMinValue(32) + 5, APInt::getSignedMinValue(32)));
 
   ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1));
   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
                 Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap),
             ConstantRange(APInt::getSignedMinValue(32) + 5,
                           APInt::getSignedMinValue(32)));
   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
                 Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
             ConstantRange(APInt(32, 0), APInt(32, 2)));
   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
                 Instruction::Add, MinusFiveToMinusTwo,
                 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
             ConstantRange(APInt(32, 0), APInt(32, 2)));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap),
+            ConstantRange(APInt::getSignedMinValue(32),
+                          APInt::getSignedMaxValue(32) - 4));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
+            ConstantRange(APInt::getMaxValue(32) - 1,
+                          APInt::getMinValue(32)));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Sub, MinusFiveToMinusTwo,
+                OBO::NoUnsignedWrap | OBO::NoSignedWrap),
+            ConstantRange(APInt::getMaxValue(32) - 1,
+                          APInt::getMinValue(32)));
 
   ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2));
   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
                 Instruction::Add, MinusOneToOne, OBO::NoSignedWrap),
             ConstantRange(APInt::getSignedMinValue(32) + 1,
                           APInt::getSignedMinValue(32) - 1));
   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
                 Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap),
             ConstantRange(APInt(32, 0), APInt(32, 1)));
   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
                 Instruction::Add, MinusOneToOne,
                 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
             ConstantRange(APInt(32, 0), APInt(32, 1)));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap),
+            ConstantRange(APInt::getSignedMinValue(32) + 1,
+                          APInt::getSignedMinValue(32) - 1));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap),
+            ConstantRange(APInt::getMaxValue(32),
+                          APInt::getMinValue(32)));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Sub, MinusOneToOne,
+                OBO::NoUnsignedWrap | OBO::NoSignedWrap),
+            ConstantRange(APInt::getMaxValue(32),
+                          APInt::getMinValue(32)));
+
+  ConstantRange One(APInt(32, 1), APInt(32, 2));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Add, One, OBO::NoSignedWrap),
+            ConstantRange(APInt::getSignedMinValue(32),
+                          APInt::getSignedMaxValue(32)));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Add, One, OBO::NoUnsignedWrap),
+            ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));
+  EXPECT_EQ(
+      ConstantRange::makeGuaranteedNoWrapRegion(
+          Instruction::Add, One, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
+      ConstantRange(APInt(32, 0), APInt::getSignedMaxValue(32)));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Sub, One, OBO::NoSignedWrap),
+            ConstantRange(APInt::getSignedMinValue(32) + 1,
+                          APInt::getSignedMinValue(32)));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Sub, One, OBO::NoUnsignedWrap),
+            ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
+  EXPECT_EQ(
+      ConstantRange::makeGuaranteedNoWrapRegion(
+          Instruction::Sub, One, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
+      ConstantRange(APInt::getMinValue(32) + 1, APInt::getSignedMinValue(32)));
 }
 
 TEST(ConstantRange, GetEquivalentICmp) {
   APInt RHS;
   CmpInst::Predicate Pred;
 
   EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))
                   .getEquivalentICmp(Pred, RHS));