[ConstantRange] Add `getClosestToZero()` method - what value[s] are closest to signed zero?

[lebedev.ri]

Summary

This method is needed in the follow-up patches adding
ConstantRange::mulWithNoWrap()/ConstantRange::shlWithNoWrap() support
to detect the all-overflow cases where we should/could return empty-set.

There's an exhaustive test so we know this is correct and optimal.

[lebedev.ri]

Clarify that if we returned two values, they have different polarity, and the negative-one is returned second.

llvm/include/llvm/IR/ConstantRange.h

public:
   APInt getUnsignedMin() const;
 
   /// Return the largest signed value contained in the ConstantRange.
   APInt getSignedMax() const;
 
   /// Return the smallest signed value contained in the ConstantRange.
   APInt getSignedMin() const;
 
+  /// Return the value contained in the ConstantRange with smallest absolute
+  /// value. Returns from 0 to 2 values. If two values are returned,
+  /// the first one is strictly positive, and second one is strictly negative.
+  SmallVector<APInt, 2> getClosestToZero() const;
+
   /// Return true if this range is equal to another range.
   bool operator==(const ConstantRange &CR) const {
     return Lower == CR.Lower && Upper == CR.Upper;
   }
   bool operator!=(const ConstantRange &CR) const {
     return !operator==(CR);
   }
 

llvm/lib/IR/ConstantRange.cpp

 }
 
 APInt ConstantRange::getSignedMin() const {
   if (isFullSet() || isSignWrappedSet())
     return APInt::getSignedMinValue(getBitWidth());
   return getLower();
 }
 
+SmallVector<APInt, 2> ConstantRange::getClosestToZero() const {
+  if (isEmptySet())
+    return {};
+
+  // If the range contains zero, said zero itself is the answer.
+  APInt Zero = APInt::getNullValue(getBitWidth());
+  if (contains(Zero))
+    return {Zero};
+
+  APInt Lower = getLower();
+  APInt Upper = getUpper() - 1;
+
+  // If both limits are equidistant from zero, then we *MUST* return both!
+  // We can don't bother checking for zero, we know we don't have it by now.
+  if (Lower.isNonNegative() && Upper.isNegative() && Lower == -Upper)
+    return {Lower, Upper}; // Return positive one first, and negative second.
+
+  // Return the limit that has smallest absolute value. This is INT_MIN-safe.
+  auto CompareAbs = [](const APInt &A, const APInt &B) {
+    return A.abs().ult(B.abs());
+  };
+  return {std::min({Lower, Upper}, CompareAbs)};
+}
+
 bool ConstantRange::contains(const APInt &V) const {
   if (Lower == Upper)
     return isFullSet();
 
   if (!isUpperWrapped())
     return Lower.ule(V) && V.ult(Upper);
   return Lower.ule(V) || V.ult(Upper);
 }

llvm/unittests/IR/ConstantRangeTest.cpp

if (Min.ugt(Max)) {
       return;
     }
 
     ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
     EXPECT_EQ(Exact, AbsCR);
   });
 }
 
+TEST_F(ConstantRangeTest, getClosestToZero) {
+  unsigned Bits = 4;
+  EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
+    const SmallVector<APInt, 2> ClosestToZero = CR.getClosestToZero();
+
+    EXPECT_EQ(ClosestToZero.empty(), CR.isEmptySet());
+    if (ClosestToZero.empty())
+      return;
+
+    EXPECT_LE(ClosestToZero.size(), 2U);
+    if (ClosestToZero.size() == 2U) {
+      EXPECT_TRUE(ClosestToZero.front().isStrictlyPositive());
+      EXPECT_TRUE(ClosestToZero.back().isNegative());
+      EXPECT_EQ(ClosestToZero.front(), -(ClosestToZero.back()));
+    }
+
+    for (const APInt &V : ClosestToZero)
+      EXPECT_TRUE(CR.contains(V));
+
+    if (llvm::any_of(ClosestToZero, [Bits](const APInt &V) {
+          return V == APInt::getSignedMinValue(Bits);
+        })) {
+      EXPECT_EQ(ClosestToZero.size(), 1U);
+      const APInt *S = CR.getSingleElement();
+      EXPECT_NE(S, nullptr);
+      EXPECT_EQ(*S, ClosestToZero.front());
+
+      return;
+    }
+
+    APInt ClosestToZeroAbs = ClosestToZero.front().abs();
+    for (APInt C = APInt(Bits, 0); C.ult(ClosestToZeroAbs); ++C)
+      EXPECT_FALSE(CR.contains(C) || CR.contains(-C));
+  });
+}
+
 }  // anonymous namespace