[ConstantRange] Estimate tighter lower (upper) bounds for masked binary and (or) (#120352)

Fixes #118108.

Co-author: Yingwei Zheng (@dtcxzyw)

IR: de-duplicate two CmpInst routines (NFC) (#116866)

De-duplicate the functions getSignedPredicate and getUnsignedPredicate,
nearly identical versions of which were present in CmpInst and ICmpInst

IR: de-duplicate two CmpInst routines (NFC) (#116866)

De-duplicate the functions getSignedPredicate and getUnsignedPredicate,
nearly identical versions of which were present in CmpInst and ICmpInst,
creating less confusion.

show more ...

[ConstantRange] Perform increment on APInt (NFC)

This handles the edge case where BitWidth is 1 and doing the
increment gets a value that's not valid in that width, while we
just want wrap-around.

[ConstantRange] Perform increment on APInt (NFC)

This handles the edge case where BitWidth is 1 and doing the
increment gets a value that's not valid in that width, while we
just want wrap-around.

Split out of https://github.com/llvm/llvm-project/pull/80309.

show more ...

[ConstantRange] Improve `shlWithNoWrap` (#101800)

Closes https://github.com/dtcxzyw/llvm-tools/issues/22.

[ConstantRange] Add support for `shlWithNoWrap` (#100594)

This patch adds initial support for `ConstantRange:: shlWithNoWrap` to
fold https://github.com/dtcxzyw/llvm-tools/issues/22. However, this

[ConstantRange] Add support for `shlWithNoWrap` (#100594)

This patch adds initial support for `ConstantRange:: shlWithNoWrap` to
fold https://github.com/dtcxzyw/llvm-tools/issues/22. However, this
patch cannot fix the original issue. Improvements will be submitted in subsequent patches.

show more ...

[ConstantRange] Infer nonnegative for mul nuw nsw (#100554)

Alive2: https://alive2.llvm.org/ce/z/byzmsV

[ConstantRange] Optimize icmp() implementation (NFC)

These are pretty hot code paths, so provide direct implementations
for them, instead of going through makeSatisfyingICmpRegion().

ConstantRange: add query for isAllPositive (#97420)

ConstantRange has queries for isAllNegative and isAllNonNegative, but
misses a query for isAllPositive. Add this function.

[LVI][ConstantRange] Generalize mask not equal conditions handling

Extend `V & Mask != 0` for non-zero constants if satisfiable, when
retrieving constraint value information from a non-equality comp

[LVI][ConstantRange] Generalize mask not equal conditions handling

Extend `V & Mask != 0` for non-zero constants if satisfiable, when
retrieving constraint value information from a non-equality comparison.

Proof: https://alive2.llvm.org/ce/z/dc5BeT.

Motivating example: https://github.com/gcc-mirror/gcc/blob/master/gcc/testsuite/gcc.dg/tree-ssa/vrp76.c.

show more ...

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

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

close: #94436

[ConstantRange][LVI] Add support for `multiplyWithNoWrap`

Introduce support for computing multiplication ranges when nowrap
flags are known. This is achieved by intersecting the multiplication
range

[ConstantRange][LVI] Add support for `multiplyWithNoWrap`

Introduce support for computing multiplication ranges when nowrap
flags are known. This is achieved by intersecting the multiplication
range with the saturating one. Note that we may still conservatively
return overdefined when handling non-wrapped/non-sign-wrapped ranges.

show more ...

[ConstantRange] Fix off by 1 bugs in UIToFP and SIToFP handling. (#86041)

We were passing the min and max values of the range to the ConstantRange
constructor, but the constructor expects the upper

[ConstantRange] Fix off by 1 bugs in UIToFP and SIToFP handling. (#86041)

We were passing the min and max values of the range to the ConstantRange
constructor, but the constructor expects the upper bound to 1 more than
the max value so we need to add 1.

We also need to use getNonEmpty so that passing 0, 0 to the constructor
creates a full range rather than an empty range. And passing smin,
smax+1 doesn't cause an assertion.

I believe this fixes at least some of the reason #79158 was reverted.

show more ...

[ConstantRange] Improve ConstantRange::binaryXor (#80146)

`ConstantRange::binaryXor` gives poor results as it currently depends on
`KnownBits::operator^`.
Since `sub A, B` is canonicalized into `x

[ConstantRange] Improve ConstantRange::binaryXor (#80146)

`ConstantRange::binaryXor` gives poor results as it currently depends on
`KnownBits::operator^`.
Since `sub A, B` is canonicalized into `xor A, B` if `B` is the subset
of `A`, this patch reverts the transform in `ConstantRange::binaryXor`,
which will give better results.

Alive2: https://alive2.llvm.org/ce/z/bmTMV9
Fixes #79696.

show more ...

[ConstantRange] Handle `Intrinsic::cttz` (#67917)

This patch adds support for `Intrinsic::cttz` in ConstantRange. It
calculates the range in O(1) with the LCP-based method.

Migrated from https:/

[ConstantRange] Handle `Intrinsic::cttz` (#67917)

This patch adds support for `Intrinsic::cttz` in ConstantRange. It
calculates the range in O(1) with the LCP-based method.

Migrated from https://reviews.llvm.org/D153505.

show more ...

[ConstantRange] Handle `Intrinsic::ctpop` (#68310)

This patch adds support for `Intrinsic::ctpop` in ConstantRange. It
calculates the range in O(1) with the LCP-based method.

Migrated from https

[ConstantRange] Handle `Intrinsic::ctpop` (#68310)

This patch adds support for `Intrinsic::ctpop` in ConstantRange. It
calculates the range in O(1) with the LCP-based method.

Migrated from https://reviews.llvm.org/D153505.

show more ...

[ConstantRange] Optimize smul nowrap with constant (NFC)

Don't call makeExactMulNSWRegion() twice with the same value.

[ConstantRange] Make shl() for negative LHS more precise

This differs from the positive case in that shifting by a larger
amount makes the result smaller, not larger.

[ConstantRange] Calculate precise range for multiply by -1

These are pretty common in SCEV, so make sure we get a precise
result by mapping to the sub() operation.

Use APInt::getSignificantBits instead of APInt::getMinSignedBits (NFC)

Note that getMinSignedBits has been soft-deprecated in favor of
getSignificantBits.

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

[ConstantRange] Handle `Intrinsic::ctlz`

Introduce ConstantRange support for ctlz intrinsic, including
exhaustive testing. Among other things, LVI may now be able to
propagate information about cltz

[ConstantRange] Handle `Intrinsic::ctlz`

Introduce ConstantRange support for ctlz intrinsic, including
exhaustive testing. Among other things, LVI may now be able to
propagate information about cltz constant ranges lattice values.

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

show more ...

[ConstantRange] Fix single bit abs range (PR59887)

For a full range input, we would produce an empty range instead
of a full range. The change to the SMin.isNonNegative() branch is
an optimality fix

[ConstantRange] Fix single bit abs range (PR59887)

For a full range input, we would produce an empty range instead
of a full range. The change to the SMin.isNonNegative() branch is
an optimality fix, because we should account for the potentially
discarded SMin value in the IntMinIsPoison case.

Change TestUnaryOpExhaustive to test both 4 and 1 bits, to both
cover this specific case in unit tests, and make sure all other
unary operations deal with 1-bit inputs correctly.

Fixes https://github.com/llvm/llvm-project/issues/59887.

show more ...

[APInt] Convert GetMostSignificantDifferentBit to std::optional

[ConstantRange] Fix nsw nowrap region for 1 bit integers (PR59301)

The special case for V=1 was incorrect for one bit types, where
1 is also -1. Remove it, and use getNonEmpty() to handle the full
r

[ConstantRange] Fix nsw nowrap region for 1 bit integers (PR59301)

The special case for V=1 was incorrect for one bit types, where
1 is also -1. Remove it, and use getNonEmpty() to handle the full
range case instead.

Adjust the exhaustive nowrap tests to test both 5 bit and 1 bit
types.

Fixes https://github.com/llvm/llvm-project/issues/59301.

show more ...

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

Many llvm/IR/* files have been migrated by other contributors.
This migrates most remaining files.