[ConstantRange] Add toKnownBits() method

[lebedev.ri]

Summary

Currently there is only one-way transform from KnownBits to ConstantRange.
Having an opposite transform could be good for consistency/testing coverage.

This could be also be of limited use for exact deduction on right-shifts,
although that will be limited to constant LHS, and won't fit within
existing ConstantRange::makeGuaranteedNoWrapRegion() interface
(it expects RHS and provides possible LHS'es, while there
we'd provide LHS and as about possible RHS's)

Also, this could be used to improve bitwise binary ops ConstantRange modelling (binaryAnd(), binaryOr(), binaryXor())

[nikic]

llvm/lib/IR/ConstantRange.cpp

88

This doesn't look right. Consider a simple range like [0b001, 0b010]. This should give known bits 0b0xx, but what you compute is One = 0b001 and Zero = 0b101, which is conflicting in the lower bit.

[nikic]

llvm/unittests/IR/ConstantRangeTest.cpp

2144

Your test is checking that the result of toKnownBits() is correct under the assumption that it came from ConstantRange::fromKnownBits(). However, fromKnownBits() can not produce all possible ranges.

[lebedev.ri]

llvm/unittests/IR/ConstantRangeTest.cpp

2144

Thanks for pointing that out, i indeed haven't fully thought that trough, as i was mostly wondering if this should exist at all.

[nikic]

Possible use case: A better implementation for binaryAnd/binaryOr. Conceptually, those can be implemented by doing:

KnownBits Known = toKnownBits();
KnownBits OtherKnown = Other.toKnownBits();

// and
Known.One &= OtherKnown.One;
Known.Zero |= OtherKnown.Zero;

return fromKnownBits(Known, /* IsSigned */ false);

[lebedev.ri]

Improve test framework; not sure how to compute the knownbits yet though.

[lebedev.ri]

Ok, 100% match to brute-force knownbits.
PTAL.

[nikic]

llvm/lib/IR/ConstantRange.cpp

77

Any reason not to make this an instance method, i.e. CR.toKnownBits(). We only need the static method for fromKnownBits() because we're working on a non-ConstantRange type.

103

Rather than looping over bits, which seems rather expensive to me, I'd suggest expressing this in terms of (V0 ^ V1).countLeadingZeros().

117

Why is it necessary to clear one more bit in the Zero case?

[lebedev.ri]

llvm/lib/IR/ConstantRange.cpp

103

This is the brute-force approach, i'm sinking it into APIntOps with proper implementation...

[lebedev.ri]

Rebased, hoisted the math into APIntOps::GetPositionOfMostSignificantDifferentBit()/D69439.

llvm/lib/IR/ConstantRange.cpp

103

D69439

117

Technically, it's the other way around, we can/need to clean exactly 1 + *Bit low bits from them,
but in the case of Known.One, the 1 + *Bit bit is already always unset (because i used getUnsignedMin()),
so it doesn't require unsetting.

[lebedev.ri]

Add one extra sanity check assertion.

[lebedev.ri]

llvm/lib/IR/ConstantRange.cpp

117

To spell this out further:
HighestTransientBit is the most significant bit that is different between getUnsignedMin() and getUnsignedMax().
All bits (if any) that are higher/more significant/more MSB are all identical.
Which means, since getUnsignedMin() (which is less than getUnsignedMax()) is used as baseline reference
for Known.One and Known.Zero, the HighestTransientBit'th bit is *not* One, it is Zero.
So we only need to unset the Zero knowledge about it. But sure, we could unset both the One and Zero knowledge,
but that won't ever matter since this algo already results in precise match.

Let me know if that did/didn't explain it.

[lebedev.ri]

Rebased, NFC.

[nikic]

So, this looks fine, but I'm still not quite clear on the use-case. I thought this might be useful for computing ranges of bit ops, but now that I see the implementation, I don't think that's the case. We just get the known top bits, but lose any information about the low bits (which can still be used, though in an operation-specific manner).

We should probably have some case where we can actually use this before landing.

llvm/lib/IR/ConstantRange.cpp

92

getUnsignedMin() is used three times and not free. Store in var?

117

I understand the reasoning, but would suggest to just clear 1 + HighestTransientBit in both cases -- apart from degenerate cases it doesn't matter for performance, and it saves having to explain it in comments.

[lebedev.ri]

In D69387#1722346, @nikic wrote:

So, this looks fine, but I'm still not quite clear on the use-case. I thought this might be useful for computing ranges of bit ops, but now that I see the implementation, I don't think that's the case. We just get the known top bits, but lose any information about the low bits (which can still be used, though in an operation-specific manner).

We should probably have some case where we can actually use this before landing.

Would we not be better-off using this rather than whatever conservative implementation we currently have for binaryAnd()/binaryOr()/binaryXor()?

[nikic]

In D69387#1814981, @lebedev.ri wrote:

In D69387#1722346, @nikic wrote:

So, this looks fine, but I'm still not quite clear on the use-case. I thought this might be useful for computing ranges of bit ops, but now that I see the implementation, I don't think that's the case. We just get the known top bits, but lose any information about the low bits (which can still be used, though in an operation-specific manner).

We should probably have some case where we can actually use this before landing.

Would we not be better-off using this rather than whatever conservative implementation we currently have for binaryAnd()/binaryOr()/binaryXor()?

That's what I initially thought as well, but I don't think it's the case. For example, binaryAnd() currently returns [0, umin(A.umax(), B.umax())]. If we have A unknown and B=[0, 0b0100] then we get as result [0, 0b0100]. If we base this on toKnownBits(), we'd get [0, 0b0111]`, because only the top bit ends up being known.

Which is what made me think that toKnownBits() is likely not really a useful primitive, as it looses to much information.

[lebedev.ri]

In D69387#1814994, @nikic wrote:

In D69387#1814981, @lebedev.ri wrote:

In D69387#1722346, @nikic wrote:

So, this looks fine, but I'm still not quite clear on the use-case. I thought this might be useful for computing ranges of bit ops, but now that I see the implementation, I don't think that's the case. We just get the known top bits, but lose any information about the low bits (which can still be used, though in an operation-specific manner).

We should probably have some case where we can actually use this before landing.

Would we not be better-off using this rather than whatever conservative implementation we currently have for binaryAnd()/binaryOr()/binaryXor()?

That's what I initially thought as well, but I don't think it's the case. For example, binaryAnd() currently returns [0, umin(A.umax(), B.umax())]. If we have A unknown and B=[0, 0b0100] then we get as result [0, 0b0100]. If we base this on toKnownBits(), we'd get [0, 0b0111]`, because only the top bit ends up being known.

And binaryXor()?

Which is what made me think that toKnownBits() is likely not really a useful primitive, as it looses to much information.

[lebedev.ri]

@nikic

In D69387#1815006, @lebedev.ri wrote:

In D69387#1814994, @nikic wrote:

In D69387#1814981, @lebedev.ri wrote:

In D69387#1722346, @nikic wrote:

So, this looks fine, but I'm still not quite clear on the use-case. I thought this might be useful for computing ranges of bit ops, but now that I see the implementation, I don't think that's the case. We just get the known top bits, but lose any information about the low bits (which can still be used, though in an operation-specific manner).

We should probably have some case where we can actually use this before landing.

Would we not be better-off using this rather than whatever conservative implementation we currently have for binaryAnd()/binaryOr()/binaryXor()?

That's what I initially thought as well, but I don't think it's the case. For example, binaryAnd() currently returns [0, umin(A.umax(), B.umax())]. If we have A unknown and B=[0, 0b0100] then we get as result [0, 0b0100]. If we base this on toKnownBits(), we'd get [0, 0b0111]`, because only the top bit ends up being known.

And binaryXor()?

Which is what made me think that toKnownBits() is likely not really a useful primitive, as it looses to much information.

llvm/include/llvm/IR/ConstantRange.h

static ConstantRange getNonEmpty(APInt Lower, APInt Upper) {
     return ConstantRange(std::move(Lower), std::move(Upper));
   }
 
   /// Initialize a range based on a known bits constraint. The IsSigned flag
   /// indicates whether the constant range should not wrap in the signed or
   /// unsigned domain.
   static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned);
 
+  /// Get a known bits valid for a given range.
+  static KnownBits toKnownBits(const ConstantRange &Range);
+
   /// Produce the smallest range such that all values that may satisfy the given
   /// predicate with any value contained within Other is contained in the
   /// returned range.  Formally, this returns a superset of
   /// 'union over all y in Other . { x : icmp op x y is true }'.  If the exact
   /// answer is not representable as a ConstantRange, the return value will be a
   /// proper superset of the above.
   ///
   /// Example: Pred = ult and Other = i8 [2, 5) returns Result = [0, 4)

llvm/include/llvm/Support/KnownBits.h

 
 public:
   // Default construct Zero and One.
   KnownBits() {}
 
   /// Create a known bits object of BitWidth bits initialized to unknown.
   KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
 
+  /// Return true if this KnownBits is equal to another KnownBits.
+  bool operator==(const KnownBits &CR) const {
+    return Zero == CR.Zero && One == CR.One;
+  }
+  bool operator!=(const KnownBits &KB) const { return !operator==(KB); }
+
   /// Get the bit width of this value.
   unsigned getBitWidth() const {
     assert(Zero.getBitWidth() == One.getBitWidth() &&
            "Zero and One should have the same width!");
     return Zero.getBitWidth();
   }
 
   /// Returns true if there is conflicting information.
public:
 
   /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
   static KnownBits computeForAddCarry(
       const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
 
   /// Compute known bits resulting from adding LHS and RHS.
   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
                                     KnownBits RHS);
+
+  /// Print out the bounds to a stream.
+  void print(raw_ostream &OS) const;
+
+  /// Allow printing from a debugger easily.
+  void dump() const;
 };
 
+inline raw_ostream &operator<<(raw_ostream &OS, const KnownBits &KB) {
+  KB.print(OS);
+  return OS;
+}
+
 } // end namespace llvm
 
 #endif

llvm/lib/IR/ConstantRange.cpp

ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known,
   // If we don't know the sign bit, pick the lower bound as a negative number
   // and the upper bound as a non-negative one.
   APInt Lower = Known.One, Upper = ~Known.Zero;
   Lower.setSignBit();
   Upper.clearSignBit();
   return ConstantRange(Lower, Upper + 1);
 }
 
+// The implementation of ConstantRange::toKnownBits() is a verbatim
+// backtransform of what is being done in the ConstantRange::fromKnownBits().
+KnownBits ConstantRange::toKnownBits(const ConstantRange &Range) {
+  KnownBits Known(Range.getBitWidth());
+
+  if (Range.isFullSet())
+    return Known; // No bits known.
+
+  if (Range.isAllNonNegative() || Range.isAllNegative()) {
+    Known.One = Range.getLower();
+    Known.Zero = ~(Range.getUpper() - 1);
+    return Known;
+  }
+
+  Known.One = Range.getLower();
+  Known.One.clearSignBit();
+
+  Known.Zero = Range.getUpper() - 1;
+  Known.Zero.setSignBit();
+  Known.Zero = ~Known.Zero;
+
+  return Known;
+}
+
 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
                                                    const ConstantRange &CR) {
   if (CR.isEmptySet())
     return CR;
 
   uint32_t W = CR.getBitWidth();
   switch (Pred) {
   default:
     llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
   case CmpInst::ICMP_EQ:
     return CR;
   case CmpInst::ICMP_NE:
     if (CR.isSingleElement())
       return ConstantRange(CR.getUpper(), CR.getLower());
     return getFull(W);
   case CmpInst::ICMP_ULT: {
     APInt UMax(CR.getUnsignedMax());
     if (UMax.isMinValue())
       return getEmpty(W);
     return ConstantRange(APInt::getMinValue(W), std::move(UMax));
   }
   case CmpInst::ICMP_SLT: {
     APInt SMax(CR.getSignedMax());
     if (SMax.isMinSignedValue())
       return getEmpty(W);

llvm/lib/Support/KnownBits.cpp

 //===-- KnownBits.cpp - Stores known zeros/ones ---------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains a class for representing known zeros and ones used by
 // computeKnownBits.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/KnownBits.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 static KnownBits computeForAddCarry(
     const KnownBits &LHS, const KnownBits &RHS,
     bool CarryZero, bool CarryOne) {
   assert(!(CarryZero && CarryOne) &&
          "Carry can't be zero and one at the same time");
if (NSW) {
       // a negative one, can't wrap into non-negative.
       else if (LHS.isNegative() && RHS.isNegative())
         KnownOut.makeNegative();
     }
   }
 
   return KnownOut;
 }
+
+void KnownBits::print(raw_ostream &OS) const {
+  OS << "Known-zero: " << Zero << ", Known-one: " << One;
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+LLVM_DUMP_METHOD void KnownBits::dump() const { print(dbgs()); }
+#endif

llvm/unittests/IR/ConstantRangeTest.cpp

TEST_F(ConstantRangeTest, FromKnownBits) {
   // 01.0.1.0 -> 01000100 (68) to 01101110 (110)
   Known.Zero = 145;
   Known.One = 68;
   ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1));
   EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false));
   EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true));
 }
 
-TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) {
+TEST_F(ConstantRangeTest, FromToKnownBitsExhaustive) {
   unsigned Bits = 4;
   unsigned Max = 1 << Bits;
   KnownBits Known(Bits);
   for (unsigned Zero = 0; Zero < Max; ++Zero) {
     for (unsigned One = 0; One < Max; ++One) {
       Known.Zero = Zero;
       Known.One = One;
       if (Known.hasConflict() || Known.isUnknown())
for (unsigned One = 0; One < Max; ++One) {
           continue;
 
         if (Num.ult(MinUnsigned)) MinUnsigned = Num;
         if (Num.ugt(MaxUnsigned)) MaxUnsigned = Num;
         if (Num.slt(MinSigned)) MinSigned = Num;
         if (Num.sgt(MaxSigned)) MaxSigned = Num;
       }
 
-      ConstantRange UnsignedCR(MinUnsigned, MaxUnsigned + 1);
-      ConstantRange SignedCR(MinSigned, MaxSigned + 1);
-      EXPECT_EQ(UnsignedCR, ConstantRange::fromKnownBits(Known, false));
-      EXPECT_EQ(SignedCR, ConstantRange::fromKnownBits(Known, true));
+      ConstantRange ReferenceUnsignedCR(MinUnsigned, MaxUnsigned + 1);
+      ConstantRange ReferenceSignedCR(MinSigned, MaxSigned + 1);
+
+      ConstantRange UnsignedCRFromKB(
+          ConstantRange::fromKnownBits(Known, false));
+      ConstantRange SignedCRFromKB(ConstantRange::fromKnownBits(Known, true));
+
+      // Conversion from reference known bits to constant range is precisely
+      // identical to reference constant range.
+      EXPECT_EQ(ReferenceUnsignedCR, UnsignedCRFromKB);
+      EXPECT_EQ(ReferenceSignedCR, SignedCRFromKB);
+
+      KnownBits KBFromReferenceUnsignedCR(
+          ConstantRange::toKnownBits(ReferenceUnsignedCR));
+      KnownBits KBFromReferenceSignedCR(
+          ConstantRange::toKnownBits(ReferenceSignedCR));
+
+      // Conversion from reference constant range is precisely
+      // identical to reference known bits.
+      EXPECT_EQ(KBFromReferenceUnsignedCR, KBFromReferenceSignedCR);
+      EXPECT_EQ(KBFromReferenceUnsignedCR, Known);
     }
   }
 }
 
 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.