[KnownBits] Make `{s,u}{add,sub}_sat` optimal (#113096)

Changes are:
1) Make signed-overflow detection optimal
2) For signed-overflow, try to rule out direction even if we can't
to

[KnownBits] Make `{s,u}{add,sub}_sat` optimal (#113096)

Changes are:
1) Make signed-overflow detection optimal
2) For signed-overflow, try to rule out direction even if we can't
totally rule out overflow.
3) Intersect add/sub assuming no overflow with possible overflow
clamping values as opposed to add/sub without the assumption.

show more ...

[KnownBits] Check that mul is optimal for low order bits (#113316)

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

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

[KnownBitsTest] Add optimality tests to some optimal impls; NFC

Adding optimality test to `add`, `sub`, `avgCeilU` and `avgFloorU`

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

[KnownBits] re-introduce RefinePosionToZero in unittest (#94848)

Context: https://github.com/llvm/llvm-project/pull/94568/files#r1631349423

- Reintroduce the RefinePositionToZero path in the unit

[KnownBits] re-introduce RefinePosionToZero in unittest (#94848)

Context: https://github.com/llvm/llvm-project/pull/94568/files#r1631349423

- Reintroduce the RefinePositionToZero path in the unittest.
- Adjust some inline function argument hints to match the same style.

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

[KnownBitsTest] Standardize variable names in exhaustive tests

[KnownBitsTest] Print name of function when exhaustive tests fail (#89588)

When exhaustive unary/binary tests fail, print the name of the function
being tested as well as the values of the inputs a

[KnownBitsTest] Print name of function when exhaustive tests fail (#89588)

When exhaustive unary/binary tests fail, print the name of the function
being tested as well as the values of the inputs and outputs.

Example of a simulated failure in testing "udiv exact":

unittests/Support/KnownBitsTest.cpp:99: Failure
Value of: checkResult(Name, Exact, Computed, {Known1, Known2},
CheckOptimality)
Actual: false (udiv exact: Inputs = ???1, ????, Computed = ???1, Exact =
0???)
Expected: true

show more ...

[KnownBitsTest] Common up isCorrect and isOptimal. NFC. (#89585)

This de-duplicates the code that prints useful information when a test
fails.

[KnownBits] Simplify optimality checking in unit tests. NFC. (#89368)

Use bool instead of function_ref.

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

Fixes #84212

[ADT] Add signed and unsigned mulh to APInt (#84719)

Fixes #84207

[KnownBits] Remove useless lambdas from unit test

[Support] KnownBitsTest - don't bother creating lambdas in testBinaryOpExhaustive callbacks if we can just use the raw KnownBits/APIntOps function reference. NFCI.

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

[ADT] Add APIntOps::abds signed absolute difference and rename absdiff -> abdu (#84791)

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

[ADT] Add APIntOps::abds signed absolute difference and rename absdiff -> abdu (#84791)

When I created APIntOps::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 APIntOps::abds implementation and renamed APIntOps::absdiff to APIntOps::abdu.

Given that APIntOps::absdiff is so young I don't think we need to create a deprecation wrapper, but I can if anyone thinks it important.

I'll do a KnownBits rename patch after this.

show more ...

[KnownBits] Implement knownbits `lshr`/`ashr` with exact flag

The exact flag basically allows us to set an upper bound on shift
amount when we have a known 1 in `LHS`.

Typically we deduce exact usi

[KnownBits] Implement knownbits `lshr`/`ashr` with exact flag

The exact flag basically allows us to set an upper bound on shift
amount when we have a known 1 in `LHS`.

Typically we deduce exact using knownbits (on non-exact incoming
shifts), so this is particularly impactful, but may be useful in some
circumstances.

Closes #84254

show more ...

[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

[unittest] Fix -Wsign-compare warnings in KnownBits.cpp after #82354

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

[KnownBits] Also test 1-bit values in exhaustive tests (NFC)

Similar to what we do with ConstantRanges, also test 1-bit values
in exhaustive tests, as these often expose special conditions.
This wou

[KnownBits] Also test 1-bit values in exhaustive tests (NFC)

Similar to what we do with ConstantRanges, also test 1-bit values
in exhaustive tests, as these often expose special conditions.
This would have exposed the assertion failure fixed in D151788
earlier.

show more ...