Page MenuHomePhabricator

[ConstantRange] Add toKnownBits() method
Needs ReviewPublic

Authored by lebedev.ri on Thu, Oct 24, 8:22 AM.



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())

Diff Detail

Event Timeline

lebedev.ri created this revision.Thu, Oct 24, 8:22 AM
nikic added inline comments.Thu, Oct 24, 9:52 AM

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 added inline comments.Thu, Oct 24, 9:56 AM

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 added inline comments.Thu, Oct 24, 10:40 AM

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

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 marked 2 inline comments as done.

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

lebedev.ri edited the summary of this revision. (Show Details)

Ok, 100% match to brute-force knownbits.

lebedev.ri marked an inline comment as done.Fri, Oct 25, 6:55 AM
nikic added inline comments.Fri, Oct 25, 9:12 AM

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.


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


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

lebedev.ri marked an inline comment as done.Fri, Oct 25, 9:26 AM
lebedev.ri added inline comments.

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

lebedev.ri marked 5 inline comments as done.

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


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.

Add one extra sanity check assertion.

lebedev.ri marked an inline comment as done.Sat, Oct 26, 1:20 AM
lebedev.ri added inline comments.

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.

Rebased, NFC.

nikic added a comment.Sat, Oct 26, 2:08 PM

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.


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


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.