[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] Make `avg{Ceil,Floor}S` optimal (#110688)

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

KnownBits: refine srem for high-bits (#109121)

KnownBits::srem does not correctly set the leader zero-bits, omitting
the fact that LHS may be known-negative or known-non-negative. Fix this.

Aliv

KnownBits: refine srem for high-bits (#109121)

KnownBits::srem does not correctly set the leader zero-bits, omitting
the fact that LHS may be known-negative or known-non-negative. Fix this.

Alive2 proof: https://alive2.llvm.org/ce/z/Ugh-Dq

show more ...

[KnownBits] avgCompute - don't create on-the-fly Carry. NFC.

Use the internal computeForAddCarry directly since we know the exact values of the carry bit.

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

[KnownBits] Factor out and improve the lowbit computation for {u,s}div

There are some new cases if the division is `exact`:
1: If `TZ(LHS) == TZ(RHS)` then the result is always Odd
2: If `TZ

[KnownBits] Factor out and improve the lowbit computation for {u,s}div

There are some new cases if the division is `exact`:
1: If `TZ(LHS) == TZ(RHS)` then the result is always Odd
2: If `TZ(LHS) > TZ(RHS)` then the `TZ(LHS)-TZ(RHS)` bits of the
result are zero.
Proofs: https://alive2.llvm.org/ce/z/3rAZqF

As well, return zero in known poison cases to be consistent rather
than just working about the bits we are changing.

Reviewed By: nikic

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

show more ...

[KnownBits] Return `0` for poison {s,u}div inputs

It seems consistent to always return zero for known poison rather than
varying the value. We do the same elsewhere.

Differential Revision: https://

[KnownBits] Return `0` for poison {s,u}div inputs

It seems consistent to always return zero for known poison rather than
varying the value. We do the same elsewhere.

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

show more ...

[KnownBits] Cleanup some misspelling / logic in {u,s}div

Chronically misspelled 'denominator' as 'denuminator' and a few other
cases.

On the logic side, no longer require `RHS` to be strictly posit

[KnownBits] Cleanup some misspelling / logic in {u,s}div

Chronically misspelled 'denominator' as 'denuminator' and a few other
cases.

On the logic side, no longer require `RHS` to be strictly positive in
`sdiv`. This in turn means we need to handle a possible zero `denom`
in the APInt division.

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

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] Partially synchronize shift implementations (NFC)

And remove some bits of effectively dead code.

[KnownBits] Add fast-path for shl with unknown shift amount (NFC)

We currently don't call into KnownBits::shl() from ValueTracking
if the shift amount is unknown. If we do try to do so, we get
signi

[KnownBits] Add fast-path for shl with unknown shift amount (NFC)

We currently don't call into KnownBits::shl() from ValueTracking
if the shift amount is unknown. If we do try to do so, we get
significant compile-time regressions, because evaluating all 64
shift amounts if quite expensive, and mostly pointless in this case.
Add a fast-path for the case where the shift amount is the full
[0, BitWidth-1] range. This primarily requires a more accurate
estimate of the max shift amount, to avoid taking the fast-path in
too many cases.

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

show more ...

[KnownBits] Simplify shl. NFCI.

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

[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] Reduce number of overflow checks for uadd/sub_sat (NFCI)

Only check for overflow on the min/max values, don't also check
for predicates in addition to that.

[KnownBits] Use early return for unknown LHS for shifts (NFC)

Make it clear that the leading/trailing zeros handling is only
relevant for the unknown LHS case, which is a fast path to avoid
the full

[KnownBits] Use early return for unknown LHS for shifts (NFC)

Make it clear that the leading/trailing zeros handling is only
relevant for the unknown LHS case, which is a fast path to avoid
the full shift amount loop in cases where it would not produce
better results.

show more ...

[KnownBits] Check for conflict-freedom in exhaustive tests

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