[ConstantRange] Fix sdiv() with one bit values (PR56333)

Signed one bit values can only be -1 or 0, not positive. The code
was interpreting the 1 as -1 and intersecting with a full range
rather than

[ConstantRange] Fix sdiv() with one bit values (PR56333)

Signed one bit values can only be -1 or 0, not positive. The code
was interpreting the 1 as -1 and intersecting with a full range
rather than an empty one.

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

show more ...

Recommit "[ConstantRange] Improve the implementation of binaryOr"

This recommits https://reviews.llvm.org/rG6990e7477d24ff585ae86549f5280f0be65422a6
as the problematic test has been updated updated

Recommit "[ConstantRange] Improve the implementation of binaryOr"

This recommits https://reviews.llvm.org/rG6990e7477d24ff585ae86549f5280f0be65422a6
as the problematic test has been updated updated in
https://reviews.llvm.org/rG3bd112c720dc614a59e3f34ebf9b45075037bfa0.

show more ...

Revert "[ConstantRange] Improve the implementation of binaryOr"

This reverts commit 6990e7477d24ff585ae86549f5280f0be65422a6.

This change was causing the test compiler-rt/test/fuzzer/merge_two_step

Revert "[ConstantRange] Improve the implementation of binaryOr"

This reverts commit 6990e7477d24ff585ae86549f5280f0be65422a6.

This change was causing the test compiler-rt/test/fuzzer/merge_two_step.test to fail on
our internal bot as well as other build bots such as https://lab.llvm.org/buildbot/#/builders/179/builds/3712.

show more ...

[ConstantRange] Improve the implementation of binaryOr

This diff adjusts binaryOr to take advantage of the analysis
based on KnownBits.

Differential revision: https://reviews.llvm.org/D125933

Test

[ConstantRange] Improve the implementation of binaryOr

This diff adjusts binaryOr to take advantage of the analysis
based on KnownBits.

Differential revision: https://reviews.llvm.org/D125933

Test plan:
1/ ninja check-llvm
2/ ninja check-llvm-unit

show more ...

[APInt] Remove all uses of zextOrSelf, sextOrSelf and truncOrSelf

Most clients only used these methods because they wanted to be able to
extend or truncate to the same bit width (which is a no-op).

[APInt] Remove all uses of zextOrSelf, sextOrSelf and truncOrSelf

Most clients only used these methods because they wanted to be able to
extend or truncate to the same bit width (which is a no-op). Now that
the standard zext, sext and trunc allow this, there is no reason to use
the OrSelf versions.

The OrSelf versions additionally have the strange behaviour of allowing
extending to a *smaller* width, or truncating to a *larger* width, which
are also treated as no-ops. A small amount of client code relied on this
(ConstantRange::castOp and MicrosoftCXXNameMangler::mangleNumber) and
needed rewriting.

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

show more ...

[ConstantRange] Improve the implementation of binaryAnd

This diff adjusts binaryAnd to take advantage of the analysis
based on KnownBits.

Differential revision: https://reviews.llvm.org/D125603

Te

[ConstantRange] Improve the implementation of binaryAnd

This diff adjusts binaryAnd to take advantage of the analysis
based on KnownBits.

Differential revision: https://reviews.llvm.org/D125603

Test plan:
1/ ninja check-llvm
2/ ninja check-llvm-unit

show more ...

[ConstantRange] Implement binaryXor() using known bits

This allows us to compute known high bits. It's not optimal, but
better than nothing.

[ConstantRange] Add toKnownBits() method

Add toKnownBits() method to mirror fromKnownBits(). We know the
top bits that are constant between min and max.

The return value for an empty range is chose

[ConstantRange] Add toKnownBits() method

Add toKnownBits() method to mirror fromKnownBits(). We know the
top bits that are constant between min and max.

The return value for an empty range is chosen to be conservative.

show more ...

[ConstantRange] Add exact union/intersect (NFC)

For some optimizations on comparisons it's necessary that the
union/intersect is exact and not a superset. Add methods that
return Optional<ConstantRa

[ConstantRange] Add exact union/intersect (NFC)

For some optimizations on comparisons it's necessary that the
union/intersect is exact and not a superset. Add methods that
return Optional<ConstantRange> only if the result is exact.

For the sake of simplicity this is implemented by comparing
the subset and superset approximations for now, but it should be
possible to do this more directly, as unionWith() and intersectWith()
already distinguish the cases where the result is imprecise for the
preferred range type functionality.

show more ...

[ConstantRange] Support zero size in isSizeLargerThan()

From an API perspective, it does not make a lot of sense that 0
is not a valid argument to this function. Add the exact check needed
to suppor

[ConstantRange] Support zero size in isSizeLargerThan()

From an API perspective, it does not make a lot of sense that 0
is not a valid argument to this function. Add the exact check needed
to support it.

show more ...

[ConstantRange] Add getEquivalentICmp() variant with offset (NFCI)

Add a variant of getEquivalentICmp() that produces an optional
offset. This allows us to create an equivalent icmp for all ranges.

[ConstantRange] Add getEquivalentICmp() variant with offset (NFCI)

Add a variant of getEquivalentICmp() that produces an optional
offset. This allows us to create an equivalent icmp for all ranges.

Use this in the with.overflow folding code, which was doing this
adjustment separately -- this clarifies that the fold will indeed
always apply.

show more ...

[ConstantRange] Sign-flipping of signedness-invariant comparisons

For certain combination of LHS and RHS constant ranges,
the signedness of the relational comparison predicate is irrelevant.

This i

[ConstantRange] Sign-flipping of signedness-invariant comparisons

For certain combination of LHS and RHS constant ranges,
the signedness of the relational comparison predicate is irrelevant.

This implements complete and precise model for all predicates,
as confirmed by the brute-force tests. I'm not sure if there are
some more cases that we can handle here.

In a follow-up, CVP will make use of this.

Reviewed By: nikic

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

show more ...

[ConstantRange] Optimize smul_sat() (NFC)

Base the implementation on the APInt smul_sat() implementation,
which is much more efficient than performing calculations in
double the bitwidth.

[ConstantRange] Add fast signed multiply

The multiply() implementation is very slow -- it performs six
multiplications in double the bitwidth, which means that it will
typically work on allocated AP

[ConstantRange] Add fast signed multiply

The multiply() implementation is very slow -- it performs six
multiplications in double the bitwidth, which means that it will
typically work on allocated APInts and bypass fast-path
implementations. Add an additional implementation that doesn't
try to produce anything better than a full range if overflow is
possible. At least for the BasicAA use-case, we really don't care
about more precise modeling of overflow behavior. The current
use of multiply() is fine while the implementation is limited to
a single index, but extending it to the multiple-index case makes
the compile-time impact untenable.

show more ...

[ConstantRange] Compute precise shl range for single elements

For the common case where the shift amount is constant (a single
element range) we can easily compute a precise range (up to
unsigned en

[ConstantRange] Compute precise shl range for single elements

For the common case where the shift amount is constant (a single
element range) we can easily compute a precise range (up to
unsigned envelope), so do that.

show more ...

[APInt] Stop using soft-deprecated constructors and methods in llvm. NFC.

Stop using APInt constructors and methods that were soft-deprecated in
D109483. This fixes all the uses I found in llvm, exc

[APInt] Stop using soft-deprecated constructors and methods in llvm. NFC.

Stop using APInt constructors and methods that were soft-deprecated in
D109483. This fixes all the uses I found in llvm, except for the APInt
unit tests which should still test the deprecated methods.

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

show more ...

[APInt] Normalize naming on keep constructors / predicate methods.

This renames the primary methods for creating a zero value to `getZero`
instead of `getNullValue` and renames predicates like `isAl

[APInt] Normalize naming on keep constructors / predicate methods.

This renames the primary methods for creating a zero value to `getZero`
instead of `getNullValue` and renames predicates like `isAllOnesValue`
to simply `isAllOnes`. This achieves two things:

1) This starts standardizing predicates across the LLVM codebase,
following (in this case) ConstantInt. The word "Value" doesn't
convey anything of merit, and is missing in some of the other things.

2) Calling an integer "null" doesn't make any sense. The original sin
here is mine and I've regretted it for years. This moves us to calling
it "zero" instead, which is correct!

APInt is widely used and I don't think anyone is keen to take massive source
breakage on anything so core, at least not all in one go. As such, this
doesn't actually delete any entrypoints, it "soft deprecates" them with a
comment.

Included in this patch are changes to a bunch of the codebase, but there are
more. We should normalize SelectionDAG and other APIs as well, which would
make the API change more mechanical.

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

show more ...

[ConstantRanges] Use APInt for constant case for urem/srem.

Currently UREM & SREM on constant ranges produces overly pessimistic
results for single element constant ranges.

Delegate to APInt's impl

[ConstantRanges] Use APInt for constant case for urem/srem.

Currently UREM & SREM on constant ranges produces overly pessimistic
results for single element constant ranges.

Delegate to APInt's implementation if both operands are single element
constant ranges. We already do something similar for other binary
operators, like binary AND.

Fixes PR49731.

Reviewed By: lebedev.ri

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

show more ...

[NFC][ConstantRange] Add 'icmp' helper method

"Does the predicate hold between two ranges?"

Not very surprisingly, some places were already doing this check,
without explicitly naming the algorithm

[NFC][ConstantRange] Add 'icmp' helper method

"Does the predicate hold between two ranges?"

Not very surprisingly, some places were already doing this check,
without explicitly naming the algorithm, cleanup them all.

show more ...

Revert "[NFC][ConstantRange] Add 'icmp' helper method"

This reverts commit 17cf2c94230bc107e7294ef84fad3b47f4cd1b73.

[NFC][ConstantRange] Add 'icmp' helper method

"Does the predicate hold between two ranges?"

Not very surprisingly, some places were already doing this check,
without explicitly naming the algorithm

[NFC][ConstantRange] Add 'icmp' helper method

"Does the predicate hold between two ranges?"

Not very surprisingly, some places were already doing this check,
without explicitly naming the algorithm, cleanup them all.

show more ...

[ConstantRange] Handle wrapping ranges in min/max (PR48643)

When one of the inputs is a wrapping range, intersect with the
union of the two inputs. The union of the two inputs corresponds
to the res

[ConstantRange] Handle wrapping ranges in min/max (PR48643)

When one of the inputs is a wrapping range, intersect with the
union of the two inputs. The union of the two inputs corresponds
to the result we would get if we treated the min/max as a simple
select.

This fixes PR48643.

show more ...

[ConstantRange] Handle wrapping range in binaryNot()

We don't need any special handling for wrapping ranges (or empty
ranges for that matter). The sub() call will already compute a
correct and preci

[ConstantRange] Handle wrapping range in binaryNot()

We don't need any special handling for wrapping ranges (or empty
ranges for that matter). The sub() call will already compute a
correct and precise range.

We only need to adjust the test expectation: We're now computing
an optimal result, rather than an unsigned envelope.

show more ...

[ConstantRange] Introduce getMinSignedBits() method

Similar to the ConstantRange::getActiveBits(), and to similarly-named
methods in APInt, returns the bitwidth needed to represent
the given signed

[ConstantRange] Introduce getMinSignedBits() method

Similar to the ConstantRange::getActiveBits(), and to similarly-named
methods in APInt, returns the bitwidth needed to represent
the given signed constant range

show more ...

[ConstantRange] Introduce getActiveBits() method

Much like APInt::getActiveBits(), computes how many bits are needed
to be able to represent every value in this constant range,
treating the values a

[ConstantRange] Introduce getActiveBits() method

Much like APInt::getActiveBits(), computes how many bits are needed
to be able to represent every value in this constant range,
treating the values as unsigned.

show more ...