[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

2148

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

2148

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 the known bits valid for the given range.
+  KnownBits toKnownBits() const;
+
   /// 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);
 }
 
+KnownBits ConstantRange::toKnownBits() const {
+  KnownBits Known(getBitWidth());
+
+  // If the range has no/all members, or has a wrap, then "no known bits"
+  // is as precise as we can get.
+  if (isEmptySet() || isFullSet() || isSignWrappedSet() || isWrappedSet())
+    return Known; // No bits known.
+
+  // We know all bits of a constant.
+  if (const APInt *SingleElement = getSingleElement()) {
+    Known.One = *SingleElement;
+    Known.Zero = ~*SingleElement;
+    return Known;
+  }
+
+  Known.One = getUnsignedMin();
+  Known.Zero = ~getUnsignedMin();
+
+  auto HighestTransientBit = APIntOps::GetMostSignificantDifferentBit(
+      getUnsignedMin(), getUnsignedMax());
+  assert(
+      HighestTransientBit.hasValue() &&
+      "Since the constant range does not consist of a single constant, there "
+      "must be some some different bits, so we must have found the threshold.");
+  assert((getBitWidth() - (1 + *HighestTransientBit)) >= 1 &&
+         "If we get here, we know *at least* the (common) sign bit.");
+
+  // We need to claim to not know all low bits up to and including
+  // HighestTransientBit. But since `getUnsignedMin()` was used as baseline,
+  // that bit itself isn't known to be One, so we don't need to unset it as One.
+  Known.One.clearLowBits(*HighestTransientBit);
+  Known.Zero.clearLowBits(1 + *HighestTransientBit);
+
+  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())

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

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;
       }
 
+      // KB -> CR conversion is precisely identical to brute-force approach.
       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, ToKnownBitsExhaustive) {
+  unsigned Bits = 6;
+  KnownBits Known(Bits);
+  EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
+    if (CR.isEmptySet())
+      return;
+
+    // Acquire precise KnownBits knowledge for a given constant range via the
+    // brute-force approach. That results in conservatively-larger value range.
+    Known.Zero.setAllBits();
+    Known.One.setAllBits();
+    ForeachNumInConstantRange(CR, [&](const APInt &N) {
+      Known.Zero &= ~N;
+      Known.One &= N;
+    });
+    ASSERT_FALSE(Known.hasConflict());
+    // But not every value found in known bits is found in constant range!
+
+    // If we produce constant range from known bits, it may be conservatively
+    // larger than the reference constant range. The reference constant range
+    // must be contained within the new constant range.
+    ConstantRange UnsignedCRFromKB(ConstantRange::fromKnownBits(Known, false));
+    ConstantRange SignedCRFromKB(ConstantRange::fromKnownBits(Known, true));
+    EXPECT_EQ(SignedCRFromKB, UnsignedCRFromKB);
+    EXPECT_TRUE(UnsignedCRFromKB.contains(CR));
+
+    // If we distill constant range into known bits, the result is a precise
+    // match to the known-bits we got via brute-force.
+    KnownBits KBFromCR(CR.toKnownBits());
+    EXPECT_EQ(KBFromCR, 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.
   EXPECT_TRUE(Empty.isAllNegative());
   EXPECT_TRUE(Empty.isAllNonNegative());
   EXPECT_FALSE(Full.isAllNegative());
   EXPECT_FALSE(Full.isAllNonNegative());