[KnownBits] Check functions that return zero for poison results

Differential Revision: https://reviews.llvm.org/D151456

[KnownBits] Add support for nuw/nsw on shifts

Implement precise nuw/nsw support in the KnownBits implementation,
replacing the rather crude handling in ValueTracking.

Differential Revision: https:/

[KnownBits] Add support for nuw/nsw on shifts

Implement precise nuw/nsw support in the KnownBits implementation,
replacing the rather crude handling in ValueTracking.

Differential Revision: https://reviews.llvm.org/D151208

show more ...

[KnownBits] Check for conflict-freedom in exhaustive tests

And make sure udiv() Exact does not produce conflicts.

[KnownBits] Add implementations for saturating add/sub functions

These where previously missing. Even in the case where overflow is
indeterminate we can still deduce some of the low/high bits.

Revi

[KnownBits] Add implementations for saturating add/sub functions

These where previously missing. Even in the case where overflow is
indeterminate we can still deduce some of the low/high bits.

Reviewed By: RKSimon

Differential Revision: https://reviews.llvm.org/D150102

show more ...

[KnownBits] Improve implementation of `KnownBits::abs`

`abs` preserves the lowest set bit, so if we know the lowest set bit,
set it in the output.

As well, implement the case where the operand is k

[KnownBits] Improve implementation of `KnownBits::abs`

`abs` preserves the lowest set bit, so if we know the lowest set bit,
set it in the output.

As well, implement the case where the operand is known negative.

Reviewed By: foad, RKSimon

Differential Revision: https://reviews.llvm.org/D150100

show more ...

[KnownBits] Improve `KnownBits::udiv`

We can more precisely determine the upper bits doing `MaxNum /
MinDenum` as opposed to only using the MSB.

As well, if the `exact` flag is set, we can sometime

[KnownBits] Improve `KnownBits::udiv`

We can more precisely determine the upper bits doing `MaxNum /
MinDenum` as opposed to only using the MSB.

As well, if the `exact` flag is set, we can sometimes determine some
of the low-bits.

Differential Revision: https://reviews.llvm.org/D150094

show more ...

[KnownBits] Add implementation for `KnownBits::sdiv`

Can figure out some of the upper bits (similiar to `udiv`) if we know
the sign of the inputs.

As well, if we have the `exact` flag we can someti

[KnownBits] Add implementation for `KnownBits::sdiv`

Can figure out some of the upper bits (similiar to `udiv`) if we know
the sign of the inputs.

As well, if we have the `exact` flag we can sometimes determine some
low-bits.

Differential Revision: https://reviews.llvm.org/D150093

show more ...

[KnownBits] Handle shifts over wide types

Do not assert if the bit width is larger than 64 bits. This case
is currently hidden from the IR layer by other checks, but gets
exposed with future changes.

[KnownBits] Make shl/lshr/ashr implementations optimal

The implementations for shifts were suboptimal in the case where
the max shift amount was >= bitwidth. In that case we should still
use the usu

[KnownBits] Make shl/lshr/ashr implementations optimal

The implementations for shifts were suboptimal in the case where
the max shift amount was >= bitwidth. In that case we should still
use the usual code clamped to BitWidth-1 rather than just giving up
entirely.

Additionally, there was an implementation bug where the known zero
bits for the individual shift amounts were not set in the shl/lshr
implementations. I think after these changes, we'll be able to drop
some of the code in ValueTracking which *also* evaluates all possible
shift amounts and has been papering over this issue.

For the "all poison" case I've opted to return an unknown value for
now. It would be better to return zero, but this has fairly
substantial test fallout, so I figured it's best to not mix it into
this change. (The "correct" return value would be a conflict, but
given that a lot of our APIs assert conflict-freedom, that's probably
not the best idea to actually return.)

Differential Revision: https://reviews.llvm.org/D150587

show more ...

[KnownBitsTest] Remove stray semicolons

[KnownBitsTest] Align with ConstantRange test infrastructure (NFC)

Align the way we perform exhaustive tests for KnownBits with what
we do for ConstantRange. Test each case separately by specifying

[KnownBitsTest] Align with ConstantRange test infrastructure (NFC)

Align the way we perform exhaustive tests for KnownBits with what
we do for ConstantRange. Test each case separately by specifying
a function on KnownBits and one on APInts. Additionally, specify
a callback that determines which cases are supposed to be optimal,
rather than only correct. Unlike the ConstantRange case there is
a well-defined, unique notion of optimality for KnownBits.

If a failure occurs, print out the inputs, computed result and
exact result. Adjust the printing function to produce the output
in a format that is meaningful for KnownBits, i.e. print the
actual known bits, using ? to signify unknowns and ! to signify
conflicts.

show more ...

[KnownBits] Add blsi and blsmsk

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D142519

std::optional::value => operator*/operator->

value() has undesired exception checking semantics and calls
__throw_bad_optional_access in libc++. Moreover, the API is unavailable without
_LIBCPP_NO_E

std::optional::value => operator*/operator->

value() has undesired exception checking semantics and calls
__throw_bad_optional_access in libc++. Moreover, the API is unavailable without
_LIBCPP_NO_EXCEPTIONS on older Mach-O platforms (see
_LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS).

This commit fixes LLVMAnalysis and its dependencies.

show more ...

[Support] llvm::Optional => std::optional

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

[Support] Add KnownBits::concat method

Add a method for the various cases where we need to concatenate 2 KnownBits together (BUILD_PAIR and SHIFT_PARTS in particular) - uses the existing APInt::conc

[Support] Add KnownBits::concat method

Add a method for the various cases where we need to concatenate 2 KnownBits together (BUILD_PAIR and SHIFT_PARTS in particular) - uses the existing APInt::concat 'HiBits.concat(LoBits)' convention

Differential Revision: https://reviews.llvm.org/D130557

show more ...

[llvm] Use value instead of getValue (NFC)

[llvm] Use has_value instead of hasValue (NFC)

Revert "Don't use Optional::hasValue (NFC)"

This reverts commit aa8feeefd3ac6c78ee8f67bf033976fc7d68bc6d.

Don't use Optional::hasValue (NFC)

[KnownBits] Add operator==

Checking whether two KnownBits are the same is somewhat common,
mainly in test code.

I don't think there is a lot of room for confusion with "determine
what the KnownBits

[KnownBits] Add operator==

Checking whether two KnownBits are the same is somewhat common,
mainly in test code.

I don't think there is a lot of room for confusion with "determine
what the KnownBits for an icmp eq would be", as that has a
different result type (this is what the eq() method implements,
which returns Optional<bool>).

Differential Revision: https://reviews.llvm.org/D125692

show more ...

[ValueTracking][SelectionDAG] Rename ComputeMinSignedBits->ComputeMaxSignificantBits. NFC

This function returns an upper bound on the number of bits needed
to represent the signed value. Use "Max" t

[ValueTracking][SelectionDAG] Rename ComputeMinSignedBits->ComputeMaxSignificantBits. NFC

This function returns an upper bound on the number of bits needed
to represent the signed value. Use "Max" to match similar functions
in KnownBits like countMaxActiveBits.

Rename APInt::getMinSignedBits->getSignificantBits. Keeping the old
name around to keep this patch size down. Will do a bulk rename as
follow up.

Rename KnownBits::countMaxSignedBits->countMaxSignificantBits.

Reviewed By: lebedev.ri, RKSimon, spatel

Differential Revision: https://reviews.llvm.org/D116522

show more ...

[Support] Add KnownBits::countMaxSignedBits(). Make KnownBits::countMinSignBits() always return at least 1.

Even if we don't have any known bits, we can assume that there is
at least 1 sign bit. Thi

[Support] Add KnownBits::countMaxSignedBits(). Make KnownBits::countMinSignBits() always return at least 1.

Even if we don't have any known bits, we can assume that there is
at least 1 sign bit. This is consistent with ComputeNumSignBits
which always returns at least 1.

Add KnownBits::countMaxSignedBits() which computes the number of
bits needed to represent all signed values with those known bits.
This is the signed equivalent of countMaxActiveBits().

Split from D116469.

Reviewed By: lebedev.ri

Differential Revision: https://reviews.llvm.org/D116500

show more ...

[KnownBits] Introduce `countMaxActiveBits()` and use it in a few places

[APInt] Stop using soft-deprecated constructors and methods in llvm. NFC.

Stop using APInt constructors and methods that were soft-deprecated in
D109483. This fixes all the uses I found in llvm, exc

[APInt] Stop using soft-deprecated constructors and methods in llvm. NFC.

Stop using APInt constructors and methods that were soft-deprecated in
D109483. This fixes all the uses I found in llvm, except for the APInt
unit tests which should still test the deprecated methods.

Differential Revision: https://reviews.llvm.org/D110807

show more ...

[APInt] Normalize naming on keep constructors / predicate methods.

This renames the primary methods for creating a zero value to `getZero`
instead of `getNullValue` and renames predicates like `isAl

[APInt] Normalize naming on keep constructors / predicate methods.

This renames the primary methods for creating a zero value to `getZero`
instead of `getNullValue` and renames predicates like `isAllOnesValue`
to simply `isAllOnes`. This achieves two things:

1) This starts standardizing predicates across the LLVM codebase,
following (in this case) ConstantInt. The word "Value" doesn't
convey anything of merit, and is missing in some of the other things.

2) Calling an integer "null" doesn't make any sense. The original sin
here is mine and I've regretted it for years. This moves us to calling
it "zero" instead, which is correct!

APInt is widely used and I don't think anyone is keen to take massive source
breakage on anything so core, at least not all in one go. As such, this
doesn't actually delete any entrypoints, it "soft deprecates" them with a
comment.

Included in this patch are changes to a bunch of the codebase, but there are
more. We should normalize SelectionDAG and other APIs as well, which would
make the API change more mechanical.

Differential Revision: https://reviews.llvm.org/D109483

show more ...