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

Fixes #118108.

Co-author: Yingwei Zheng (@dtcxzyw)

[ConstantRangeTest] Set APInt signed flags where needed (NFC)

Split out from https://github.com/llvm/llvm-project/pull/80309 to
avoid assertion failures in the future.

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

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

Migrate away from the soft-deprecated functions in APInt.h (NFC)

Note that those functions on the left hand side are soft-deprecated in
favor of those on the right hand side:

getMinSignedBits ->

Migrate away from the soft-deprecated functions in APInt.h (NFC)

Note that those functions on the left hand side are soft-deprecated in
favor of those on the right hand side:

getMinSignedBits -> getSignificantBits
getNullValue -> getZero
isNullValue -> isZero
isOneValue -> isOne

show more ...

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] Test 1 bit ranges in exhaustive tests (NFC)

There have been multiple cases where range calculations were wrong
in the 1 bit case. Make sure we catch these by not specifying the
bit w

[ConstantRange] Test 1 bit ranges in exhaustive tests (NFC)

There have been multiple cases where range calculations were wrong
in the 1 bit case. Make sure we catch these by not specifying the
bit width explicitly, and letting the test framework pick it (which
will now always test 1 and 4 bits both).

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

[llvm] Use std::optional instead of Optional

This is part of an effort to migrate from llvm::Optional to
std::optional:

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

[llvm] Use std::optional instead of Optional

This is part of an effort to migrate from llvm::Optional to
std::optional:

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

show more ...

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

[llvm/unittests] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the am

[llvm/unittests] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount of manual work required in migrating from Optional to
std::optional.

This is part of an effort to migrate from llvm::Optional to
std::optional:

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

show more ...

[ConstantRangeTest] Migrate known bits test to generic infrastructure (NFC)

This can't make use of TestBinaryOpExhaustive, but it can make use
of the general TestRange approach that collects the pre

[ConstantRangeTest] Migrate known bits test to generic infrastructure (NFC)

This can't make use of TestBinaryOpExhaustive, but it can make use
of the general TestRange approach that collects the precise elements
in a bit vector.

This allows us to remove the obsolete "op range gatherer" infrastructure.

show more ...

[ConstantRangeTest] Move nowrap binop tests to generic infrastructure (NFC)

Move testing for add/sub with nowrap flags to TestBinaryOpExhaustive,
rather than separate homegrown exhaustive testing fu

[ConstantRangeTest] Move nowrap binop tests to generic infrastructure (NFC)

Move testing for add/sub with nowrap flags to TestBinaryOpExhaustive,
rather than separate homegrown exhaustive testing functions.

show more ...