[ConstantRange] Add isNegative() and isNonNegative() methods

[nikic]

Summary

Add isNegative() and isNonNegative() methods to ConstantRange, which determine whether all values in the constant range are negative/non-negative. The naming follows KnownBits, where these methods have the same meaning. Could also use something like isAllNegative() and isAllNonNegative(), if that's more clear.

Motivation is to replace existing KnownBits calls when switching over computeOverflowForSignedAdd() to use ranges only (https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ValueTracking.cpp#L4154).

[lebedev.ri]

Looks good.

The naming follows KnownBits, where these methods have the same meaning.
Could also use something like isAllNegative() and isAllNonNegative(), if that's more clear.

I think,
In KnownBits case, we either know signbit (and thus the sign), or we don't.
If we do know it, then we can answer if that KnownBits is negative / non-negative.

Here, in ConstantRange, we don't just know sign. We know *range*.
So negative/non-negative becomes ambigious, at least to me.
Does it mean that the *whole* range is like that (the intended meaning),
or only at least some part of the range?

So yes, i would personally prefer the variants with All.

llvm/lib/IR/ConstantRange.cpp

393–395 ↗

(On Diff #193697)

Hm, i would prefer to do

if(isEmptySet())
  return true; // Empty set is all-negative.
if(isFullSet())
  return false; // Full set is not all-negative.

since it is arguably more obvious.
Not sure it is better though.

llvm/unittests/IR/ConstantRangeTest.cpp

1648 ↗

(On Diff #193697)

Can you also explicitly check full sets?

[nikic]

Rename to isAllNegative() and isAllNonNegative(), explicitly check empty/full set in isNegative() implementation, add explicit test for full ranges.

[lebedev.ri]

LG, thank you.

llvm/unittests/IR/ConstantRangeTest.cpp

1664 ↗

(On Diff #193716)

Hmm, can we also check that

if(!CR.isEmptySet() && !CR.isFullSet())
  EXPECT_NE(AllNegative, AllNonNegative);

?

[nikic]

llvm/unittests/IR/ConstantRangeTest.cpp

1664 ↗

(On Diff #193716)

This doesn't hold in general, as AllNegative and AllNonNegative may both be false for ranges that cross zero (but are not necessarily full). E.g. [-5, 6) is neither negative nor non-negative.

[lebedev.ri]

llvm/unittests/IR/ConstantRangeTest.cpp

1664 ↗

(On Diff #193716)

Hmm, of course it is.
I believe i meant EXPECT_FALSE(AllNegative && AllNonNegative);.

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

public:
   bool isSingleElement() const { return getSingleElement() != nullptr; }
 
   /// Return the number of elements in this set.
   APInt getSetSize() const;
 
   /// Compare set size of this range with the range CR.
   bool isSizeStrictlySmallerThan(const ConstantRange &CR) const;
 
-  // Compare set size of this range with Value.
+  /// Compare set size of this range with Value.
   bool isSizeLargerThan(uint64_t MaxSize) const;
 
+  /// Return true if all values in this range are negative.
+  bool isAllNegative() const;
+
+  /// Return true if all values in this range are non-negative.
+  bool isAllNonNegative() const;
+
   /// Return the largest unsigned value contained in the ConstantRange.
   APInt getUnsignedMax() const;
 
   /// Return the smallest unsigned value contained in the ConstantRange.
   APInt getUnsignedMin() const;
 
   /// Return the largest signed value contained in the ConstantRange.
   APInt getSignedMax() const;

llvm/trunk/lib/IR/ConstantRange.cpp

ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
   // If this a full set, we need special handling to avoid needing an extra bit
   // to represent the size.
   if (isFullSet())
     return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
 
   return (Upper - Lower).ugt(MaxSize);
 }
 
+bool ConstantRange::isAllNegative() const {
+  // Empty set is all negative, full set is not.
+  if (isEmptySet())
+    return true;
+  if (isFullSet())
+    return false;
+
+  return !isUpperSignWrapped() && !Upper.isStrictlyPositive();
+}
+
+bool ConstantRange::isAllNonNegative() const {
+  // Empty and full set are automatically treated correctly.
+  return !isSignWrappedSet() && Lower.isNonNegative();
+}
+
 APInt ConstantRange::getUnsignedMax() const {
   if (isFullSet() || isUpperWrapped())
     return APInt::getMaxValue(getBitWidth());
   return getUpper() - 1;
 }
 
 APInt ConstantRange::getUnsignedMin() const {
   if (isFullSet() || isWrappedSet())

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

protected:
   static ConstantRange Full;
   static ConstantRange Empty;
   static ConstantRange One;
   static ConstantRange Some;
   static ConstantRange Wrap;
 };
 
 template<typename Fn>
-static void EnumerateTwoConstantRanges(unsigned Bits, Fn TestFn) {
+static void EnumerateConstantRanges(unsigned Bits, Fn TestFn) {
   unsigned Max = 1 << Bits;
-  for (unsigned Lo1 = 0; Lo1 < Max; Lo1++) {
-    for (unsigned Hi1 = 0; Hi1 < Max; Hi1++) {
-      // Enforce ConstantRange invariant.
-      if (Lo1 == Hi1 && Lo1 != 0 && Lo1 != Max - 1)
-        continue;
-
-      ConstantRange CR1(APInt(Bits, Lo1), APInt(Bits, Hi1));
-      for (unsigned Lo2 = 0; Lo2 < Max; Lo2++) {
-        for (unsigned Hi2 = 0; Hi2 < Max; Hi2++) {
-          // Enforce ConstantRange invariant.
-          if (Lo2 == Hi2 && Lo2 != 0 && Lo2 != Max - 1)
-            continue;
+  for (unsigned Lo = 0; Lo < Max; Lo++) {
+    for (unsigned Hi = 0; Hi < Max; Hi++) {
+      if (Lo == Hi && Lo != 0 && Lo != Max - 1)
 
-          ConstantRange CR2(APInt(Bits, Lo2), APInt(Bits, Hi2));
-          TestFn(CR1, CR2);
-        }
-      }
-    }
+      ConstantRange CR(APInt(Bits, Lo), APInt(Bits, Hi));
+      TestFn(CR);
+
+template<typename Fn>
+static void EnumerateTwoConstantRanges(unsigned Bits, Fn TestFn) {
+  EnumerateConstantRanges(Bits, [&](const ConstantRange &CR1) {
+    EnumerateConstantRanges(Bits, [&](const ConstantRange &CR2) {
+      TestFn(CR1, CR2);
+    });
+  });
+}
+
+template<typename Fn>
+static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) {
+  // The loop is based on the set size to correctly handle empty/full ranges.
+  unsigned Size = CR.getSetSize().getLimitedValue();
+  APInt N = CR.getLower();
+  for (unsigned I = 0; I < Size; ++I, ++N) {
+    TestFn(N);
   }
 }
 
 ConstantRange ConstantRangeTest::Full(16, true);
 ConstantRange ConstantRangeTest::Empty(16, false);
 ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
for (unsigned One = 0; One < Max; ++One) {
       ConstantRange UnsignedCR(MinUnsigned, MaxUnsigned + 1);
       ConstantRange SignedCR(MinSigned, MaxSigned + 1);
       EXPECT_EQ(UnsignedCR, ConstantRange::fromKnownBits(Known, false));
       EXPECT_EQ(SignedCR, ConstantRange::fromKnownBits(Known, true));
     }
   }
 }
 
+TEST_F(ConstantRangeTest, Negative) {
+  // All elements in an empty set (of which there are none) are both negative
+  // and non-negative. Empty & full sets checked explicitly for clarity, but
+  // they are also covered by the exhaustive test below.
+  EXPECT_TRUE(Empty.isAllNegative());
+  EXPECT_TRUE(Empty.isAllNonNegative());
+  EXPECT_FALSE(Full.isAllNegative());
+  EXPECT_FALSE(Full.isAllNonNegative());
+
+  unsigned Bits = 4;
+  EnumerateConstantRanges(Bits, [](const ConstantRange &CR) {
+    bool AllNegative = true;
+    bool AllNonNegative = true;
+    ForeachNumInConstantRange(CR, [&](const APInt &N) {
+      if (!N.isNegative())
+        AllNegative = false;
+      if (!N.isNonNegative())
+        AllNonNegative = false;
+    });
+    assert((CR.isEmptySet() || !AllNegative || !AllNonNegative) &&
+           "Only empty set can be both all negative and all non-negative");
+
+    EXPECT_EQ(AllNegative, CR.isAllNegative());
+    EXPECT_EQ(AllNonNegative, CR.isAllNonNegative());
+  });
+}
+
 }  // anonymous namespace