This is an archive of the discontinued LLVM Phabricator instance.

[ConstantRange] Add toKnownBits() method
AbandonedPublic

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

Details

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

Diff Detail

Event Timeline

lebedev.ri created this revision.Oct 24 2019, 8:22 AM
nikic added inline comments.Oct 24 2019, 9:52 AM
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 added inline comments.Oct 24 2019, 9:56 AM
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 added inline comments.Oct 24 2019, 10:40 AM
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.

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.
PTAL.

lebedev.ri marked an inline comment as done.Oct 25 2019, 6:55 AM
nikic added inline comments.Oct 25 2019, 9:12 AM
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 marked an inline comment as done.Oct 25 2019, 9:26 AM
lebedev.ri added inline comments.
llvm/lib/IR/ConstantRange.cpp
103

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.

llvm/lib/IR/ConstantRange.cpp
103
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.

Add one extra sanity check assertion.

lebedev.ri marked an inline comment as done.Oct 26 2019, 1:20 AM
lebedev.ri added inline comments.
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.

Rebased, NFC.

nikic added a comment.Oct 26 2019, 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.

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.

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 added a comment.Jan 10 2020, 1:49 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.

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.

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.

@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.

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 abandoned this revision.Aug 12 2020, 2:24 PM