[ConstantRange] Add abs() support

[nikic]

Summary

Add support for abs() to ConstantRange. This will allow to handle abs select flavor in LVI and I think it will also come in handy for srem implementation.

The implementation is slightly tricky, because a) abs of signed min is signed min and b) sign-wrapped ranges may have an abs() that is smaller than a full range, so we need to explicitly handle them.

[lebedev.ri]

I agree that the test makes sense, and the *logic* of the ConstantRange::abs() implementation makes sense.
But i'm not sure about INT_MIN handling.
The test certainly works, because we are only checking 4-bit values, while APInt is 64-bit or more.
What happens for ConstantRange's of larger width?
Maybe you should return ConstantRange with bitwidth larger by one if INT_MIN is included?

[nikic]

In D61084#1477695, @lebedev.ri wrote:

The test certainly works, because we are only checking 4-bit values, while APInt is 64-bit or more.
What happens for ConstantRange's of larger width?

The bit width doesn't make a difference here: If the signed min for the particular bitwidth is in the original range, it will also be in the result range.

Maybe you should return ConstantRange with bitwidth larger by one if INT_MIN is included?

I don't think this would be particularly useful, at least in the context where this is intended to be used: The abs() implementation here models the semantics of SPF_ABS, which maps signed min onto signed min, and it's important to preserve that edge-case behavior.

We have similar code for handling abs of signed min in ValueTracking: https://github.com/llvm-mirror/llvm/blob/4d4155f08ea87c6909ddd6db4610c3d6c8034983/lib/Analysis/ValueTracking.cpp#L5669-L5679

[lebedev.ri]

In D61084#1477747, @nikic wrote:

In D61084#1477695, @lebedev.ri wrote:

The test certainly works, because we are only checking 4-bit values, while APInt is 64-bit or more.
What happens for ConstantRange's of larger width?

The bit width doesn't make a difference here: If the signed min for the particular bitwidth is in the original range, it will also be in the result range.

Maybe you should return ConstantRange with bitwidth larger by one if INT_MIN is included?

I don't think this would be particularly useful, at least in the context where this is intended to be used: The abs() implementation here models the semantics of SPF_ABS, which maps signed min onto signed min, and it's important to preserve that edge-case behavior.

We have similar code for handling abs of signed min in ValueTracking: https://github.com/llvm-mirror/llvm/blob/4d4155f08ea87c6909ddd6db4610c3d6c8034983/lib/Analysis/ValueTracking.cpp#L5669-L5679

Okay, that clarifies things, thank you for pointing that out.
I believe ubsan will not complain here about negations, since APInt::negate() is always used.
LG.

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

public:
   ConstantRange usub_sat(const ConstantRange &Other) const;
 
   /// Perform a signed saturating subtraction of two constant ranges.
   ConstantRange ssub_sat(const ConstantRange &Other) const;
 
   /// Return a new range that is the logical not of the current set.
   ConstantRange inverse() const;
 
+  /// Calculate absolute value range. If the original range contains signed
+  /// min, then the resulting range will also contain signed min.
+  ConstantRange abs() const;
+
   /// Represents whether an operation on the given constant range is known to
   /// always or never overflow.
   enum class OverflowResult { AlwaysOverflows, MayOverflow, NeverOverflows };
 
   /// Return whether unsigned add of the two ranges always/never overflows.
   OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const;
 
   /// Return whether signed add of the two ranges always/never overflows.

llvm/trunk/lib/IR/ConstantRange.cpp

 ConstantRange ConstantRange::inverse() const {
   if (isFullSet())
     return getEmpty();
   if (isEmptySet())
     return getFull();
   return ConstantRange(Upper, Lower);
 }
 
+ConstantRange ConstantRange::abs() const {
+  if (isEmptySet())
+    return getEmpty();
+
+  if (isSignWrappedSet()) {
+    APInt Lo;
+    // Check whether the range crosses zero.
+    if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
+      Lo = APInt::getNullValue(getBitWidth());
+    else
+      Lo = APIntOps::umin(Lower, -Upper + 1);
+
+    // SignedMin is included in the result range.
+    return ConstantRange(Lo, APInt::getSignedMinValue(getBitWidth()) + 1);
+  }
+
+  APInt SMin = getSignedMin(), SMax = getSignedMax();
+
+  // All non-negative.
+  if (SMin.isNonNegative())
+    return *this;
+
+  // All negative.
+  if (SMax.isNegative())
+    return ConstantRange(-SMax, -SMin + 1);
+
+  // Range crosses zero.
+  return ConstantRange(APInt::getNullValue(getBitWidth()),
+                       APIntOps::umax(-SMin, SMax) + 1);
+}
+
 ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow(
     const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return OverflowResult::MayOverflow;
 
   APInt Min = getUnsignedMin(), Max = getUnsignedMax();
   APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
 

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

TestSignedBinOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.ssub_sat(CR2);
       },
       [](const APInt &N1, const APInt &N2) {
         return N1.ssub_sat(N2);
       });
 }
 
+TEST_F(ConstantRangeTest, Abs) {
+  unsigned Bits = 4;
+  EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
+    // We're working with unsigned integers here, because it makes the signed
+    // min case non-wrapping.
+    APInt Min = APInt::getMaxValue(Bits);
+    APInt Max = APInt::getMinValue(Bits);
+    ForeachNumInConstantRange(CR, [&](const APInt &N) {
+      APInt AbsN = N.abs();
+      if (AbsN.ult(Min))
+        Min = AbsN;
+      if (AbsN.ugt(Max))
+        Max = AbsN;
+    });
+
+    ConstantRange AbsCR = CR.abs();
+    if (Min.ugt(Max)) {
+      EXPECT_TRUE(AbsCR.isEmptySet());
+      return;
+    }
+
+    ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
+    EXPECT_EQ(Exact, AbsCR);
+  });
+}
+
 }  // anonymous namespace