[KnownBits] Make `avg{Ceil,Floor}S` optimal (#110688)

Rewrite the signed functions in terms of the unsigned ones which are
already optimal.

[KnownBits] Add KnownBits::add and KnownBits::sub helper wrappers. (#99468)

[KnownBits] Remove commonBits (#95430)

commonBits has been deprecated since:

commit d8229e2f1424504f7ea81a0dcc7326d122be2872
Author: Jay Foad <jay.foad@amd.com>
Date: Wed May 10 16:50:3

[KnownBits] Remove commonBits (#95430)

commonBits has been deprecated since:

commit d8229e2f1424504f7ea81a0dcc7326d122be2872
Author: Jay Foad <jay.foad@amd.com>
Date: Wed May 10 16:50:33 2023 +0100

show more ...

[KnownBits] Remove `hasConflict()` assertions (#94568)

Allow KnownBits to represent "always poison" values via conflict.

close: #94436

[llvm] Add KnownBits implementations for avgFloor and avgCeil (#86445)

This PR is to address the issue #84640

[KnownBits] Make abdu and abds optimal (#89081)

Fixes #84212

[Support] Add KnownBits::abds signed absolute difference and rename absdiff -> abdu (#84897)

When I created KnownBits::absdiff, I totally missed that we already have ISD::ABDS/ABDU nodes, and we use

[Support] Add KnownBits::abds signed absolute difference and rename absdiff -> abdu (#84897)

When I created KnownBits::absdiff, I totally missed that we already have ISD::ABDS/ABDU nodes, and we use this term in other places/targets as well.

I've added the KnownBits::abds implementation and renamed KnownBits::absdiff to KnownBits::abdu.

Followup to #84791

show more ...

[KnownBits] Add API support for `exact` in `lshr`/`ashr`; NFC

[KnownBits] Make `nuw` and `nsw` support in `computeForAddSub` optimal

Just some improvements that should hopefully strengthen analysis.

Closes #83580

[KnownBits] Add API for `nuw` flag in `computeForAddSub`; NFC

[KnownBits] Add KnownBits::absdiff to compute the absolute difference of 2 unsigned values (#82354)

Equivalent to "umax(A, B) - umin(A, B)"

This is just an initial correctness implementation, hop

[KnownBits] Add KnownBits::absdiff to compute the absolute difference of 2 unsigned values (#82354)

Equivalent to "umax(A, B) - umin(A, B)"

This is just an initial correctness implementation, hopefully we can make this optimal in the future.

show more ...

[Support] Add KnownBits::computeForSubBorrow (#67788)

- [Support] Add KnownBits::computeForSubBorrow
- [CodeGen] Implement USUBC, USUBO_CARRY, and SSUBO_CARRY with
KnownBits::computeForSubBorrow

[Support] Add KnownBits::computeForSubBorrow (#67788)

- [Support] Add KnownBits::computeForSubBorrow
- [CodeGen] Implement USUBC, USUBO_CARRY, and SSUBO_CARRY with
KnownBits::computeForSubBorrow
- [CodeGen] Compute unknown bits for Carry/Borrow for ADD/SUB
- [CodeGen] Compute known bits of Carry/Borrow for UADDO, SADDO, USUBO,
and SSUBO

Fixes #65893

---------

Co-authored-by: Shafik Yaghmour <shafik@users.noreply.github.com>

show more ...

[ValueTracking] Directly use KnownBits shift functions

Make ValueTracking directly call the KnownBits shift helpers, which
provides more precise results.

Unfortunately, ValueTracking has a special

[ValueTracking] Directly use KnownBits shift functions

Make ValueTracking directly call the KnownBits shift helpers, which
provides more precise results.

Unfortunately, ValueTracking has a special case where sometimes we
determine non-zero shift amounts using isKnownNonZero(). I have my
doubts about the usefulness of that special-case (it is only tested
in a single unit test), but I've reproduced the special-case via an
extra parameter to the KnownBits methods.

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

show more ...

[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] 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 `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] Define and use intersectWith and unionWith

Define intersectWith and unionWith as two complementary ways of
combining KnownBits. The names are chosen for consistency with
ConstantRange.

[KnownBits] Define and use intersectWith and unionWith

Define intersectWith and unionWith as two complementary ways of
combining KnownBits. The names are chosen for consistency with
ConstantRange.

Deprecate commonBits as a synonym for intersectWith.

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

show more ...

[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] Improve `KnownBits::rem(X, Y)` in cases where we can deduce low-bits of output

The first `cttz(Y)` bits in `X` are translated 1-1 in the output.

Alive2 Links:
https://alive2.llvm.or

[KnownBits] Improve `KnownBits::rem(X, Y)` in cases where we can deduce low-bits of output

The first `cttz(Y)` bits in `X` are translated 1-1 in the output.

Alive2 Links:
https://alive2.llvm.org/ce/z/Qc47p7
https://alive2.llvm.org/ce/z/19ut5H

Reviewed By: RKSimon

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

show more ...

Use APInt::count{l,r}_{zero,one} (NFC)

Use APInt::popcount instead of APInt::countPopulation (NFC)

This is for consistency with the C++20-style bit manipulation
functions in <bit>.

[KnownBits] Add blsi and blsmsk

Reviewed By: nikic

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

[KnownBits] Add missing const to a couple of methods

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

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