[ConstantRange] Disallow NUW | NSW in makeGuaranteedNoWrapRegion()

[nikic]

Summary

As motivated in D60598, this drops support for specifying both NUW and NSW in makeGuaranteedNoWrapRegion(). None of the users of this function currently make use of this.

When both NUW and NSW are specified, the exact nowrap region has two disjointed parts and makeGNWR() returns one of them. This result doesn't seem to be useful for anything, but makes the semantics of the function fuzzier.

After this change, I'd land an NFC rename from makeGuaranteedNoWrapRegion() to makeExactNoWrapRegion().

[lebedev.ri]

That was added in D13612 This will be used in a future change to ScalarEvolution.,
but indeed, the (OBO::NoSignedWrap | OBO::NoUnsignedWrap) combination is not used anywhere.
I'm wondering if @sanjoy has any comments?

[sanjoy]

In D60632#1465299, @lebedev.ri wrote:

That was added in D13612 This will be used in a future change to ScalarEvolution.,
but indeed, the (OBO::NoSignedWrap | OBO::NoUnsignedWrap) combination is not used anywhere.
I'm wondering if @sanjoy has any comments?

I don't remember if I had any specific plans for (OBO::NoSignedWrap | OBO::NoUnsignedWrap) but please remove it if it is unused today.

[lebedev.ri]

LG

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

public:
   /// returns the exact answer when the superset of 'union over all y in Other
   /// is exactly same as the subset of intersection over all y in Other.
   /// { x : icmp op x y is true}'.
   ///
   /// Example: Pred = ult and Other = i8 3 returns [0, 3)
   static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred,
                                            const APInt &Other);
 
-  /// Return the largest range containing all X such that "X BinOpC Y" is
+  /// Return the exact range containing all X such that "X BinOpC Y" is
   /// guaranteed not to wrap (overflow) for all Y in Other.
   ///
-  /// If only one of NoUnsignedWrap or NoSignedWrap is specified, the returned
-  /// range is exact: It contains *all* possible values of X for which
-  /// "X BinOpC Y" does not wrap. However, if both NUW and NSW are specified, it
-  /// may return only a subset of non-wrapping values. In this case the
-  /// returned region cannot be used 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.
+  /// NoWrapKind must be one of OBO::NoUnsignedWrap or OBO::NoSignedWrap.
   ///
   /// 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

ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
   auto SubsetIntersect =
       [](const ConstantRange &CR0, const ConstantRange &CR1) {
     return CR0.inverse().unionWith(CR1.inverse()).inverse();
   };
 
   assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
 
   assert((NoWrapKind == OBO::NoSignedWrap ||
-          NoWrapKind == OBO::NoUnsignedWrap ||
-          NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
+          NoWrapKind == OBO::NoUnsignedWrap) &&
          "NoWrapKind invalid!");
 
   unsigned BitWidth = Other.getBitWidth();
   ConstantRange Result(BitWidth, /* full */ true);
 
   switch (BinOp) {
   default:
     // Conservative answer: empty set
     return getEmpty(BitWidth);
 
   case Instruction::Add:
     if (auto *C = Other.getSingleElement())
       if (C->isNullValue())
         // Full set: nothing signed / unsigned wraps when added to 0.
         return getFull(BitWidth);
-    if (NoWrapKind & OBO::NoUnsignedWrap)
-      Result =
-          SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
-                                                -Other.getUnsignedMax()));
-    if (NoWrapKind & OBO::NoSignedWrap) {
+
+    if (NoWrapKind == OBO::NoUnsignedWrap)
+      return 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)));
     }
     return Result;
 
   case Instruction::Sub:
     if (auto *C = Other.getSingleElement())
       if (C->isNullValue())
         // Full set: nothing signed / unsigned wraps when subtracting 0.
         return getFull(BitWidth);
-    if (NoWrapKind & OBO::NoUnsignedWrap)
-      Result =
-          SubsetIntersect(Result, ConstantRange(Other.getUnsignedMax(),
-                                                APInt::getMinValue(BitWidth)));
-    if (NoWrapKind & OBO::NoSignedWrap) {
+
+    if (NoWrapKind == OBO::NoUnsignedWrap)
+      return 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;
-  case Instruction::Mul: {
-    if (NoWrapKind == (OBO::NoSignedWrap | OBO::NoUnsignedWrap)) {
-      return SubsetIntersect(
-          makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoSignedWrap),
-          makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoUnsignedWrap));
-    }
 
+  case Instruction::Mul: {
     // Equivalent to calling makeGuaranteedNoWrapRegion() on [V, V+1).
     const bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
     const auto makeSingleValueRegion = [Unsigned,
                                         BitWidth](APInt V) -> ConstantRange {
       // Handle special case for 0, -1 and 1. See the last for reason why we
       // specialize -1 and 1.
       if (V == 0 || V.isOneValue())
         return getFull(BitWidth);

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
 
     EXPECT_FALSE(NUWRegion.isEmptySet());
 
     auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
         Instruction::Add, C, OBO::NoSignedWrap);
 
     EXPECT_FALSE(NSWRegion.isEmptySet());
 
-    auto NoWrapRegion = ConstantRange::makeGuaranteedNoWrapRegion(
-        Instruction::Add, 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.uadd_ov(C, Overflow);
       EXPECT_FALSE(Overflow);
     }
 
     for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
          ++I) {
       bool Overflow = false;
       (void)I.sadd_ov(C, Overflow);
       EXPECT_FALSE(Overflow);
     }
-
-    for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E;
-         ++I) {
-      bool Overflow = false;
-
-      (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());
 
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)));
 }
 
 template<typename Fn>
 void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp,
                                 unsigned NoWrapKind, Fn OverflowFn) {
   // When using 4 bits this test needs ~3s on a debug build.
   unsigned Bits = 3;
   EnumerateTwoConstantRanges(Bits,
for (int64_t V = std::numeric_limits<int8_t>::min();
       bool Overflow;
       (void)APInt(8, I, /*isSigned=*/true)
           .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow);
       EXPECT_EQ(!Overflow, Range.contains(APInt(8, V, /*isSigned=*/true)));
     }
   }
 }
 
-TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedAndSignedSingleValue) {
-  typedef OverflowingBinaryOperator OBO;
-
-  for (uint64_t I = std::numeric_limits<uint8_t>::min();
-       I <= std::numeric_limits<uint8_t>::max(); I++) {
-    auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
-        Instruction::Mul, ConstantRange(APInt(8, I), APInt(8, I + 1)),
-        OBO::NoUnsignedWrap | OBO::NoSignedWrap);
-
-    for (uint64_t V = std::numeric_limits<uint8_t>::min();
-         V <= std::numeric_limits<uint8_t>::max(); V++) {
-      bool UOverflow;
-      (void)APInt(8, I).umul_ov(APInt(8, V), UOverflow);
-      bool SOverflow;
-      (void)APInt(8, I).smul_ov(APInt(8, V), SOverflow);
-      EXPECT_EQ(!(UOverflow || SOverflow), Range.contains(APInt(8, V)));
-    }
-  }
-}
-
 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedRange) {
   typedef OverflowingBinaryOperator OBO;
 
   for (uint64_t Lo = std::numeric_limits<uint8_t>::min();
        Lo <= std::numeric_limits<uint8_t>::max(); Lo++) {
     for (uint64_t Hi = Lo; Hi <= std::numeric_limits<uint8_t>::max(); Hi++) {
       EXPECT_EQ(
           ConstantRange::makeGuaranteedNoWrapRegion(