[llvm] Don't use Optional::getValue (NFC)

[KnownBits] Add operator==

Checking whether two KnownBits are the same is somewhat common,
mainly in test code.

I don't think there is a lot of room for confusion with "determine
what the KnownBits

[KnownBits] Add operator==

Checking whether two KnownBits are the same is somewhat common,
mainly in test code.

I don't think there is a lot of room for confusion with "determine
what the KnownBits for an icmp eq would be", as that has a
different result type (this is what the eq() method implements,
which returns Optional<bool>).

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

show more ...

[KnownBits] Add support for X*X self-multiplication (update)

Rename the SelfMultiply argument to make it clearer that the argument must not be undef

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

[KnownBits] Add support for X*X self-multiplication (update)

Rename the SelfMultiply argument to make it clearer that the argument must not be undef

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

show more ...

[Support] improve known bits analysis for leading zeros of multiply

Instead of summing leading zeros on the input operands, multiply the
max possible values of those inputs and count the leading zer

[Support] improve known bits analysis for leading zeros of multiply

Instead of summing leading zeros on the input operands, multiply the
max possible values of those inputs and count the leading zeros of
the result. This can give us an extra zero bit (typically in cases
where one of the operands is a known constant).

This allows folding away the remaining 'add' ops in the motivating
bug (modeled in the PhaseOrdering IR test):
https://github.com/llvm/llvm-project/issues/48399

Fixes #48399

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

show more ...

[Support] improve known bits analysis for multiply by power-of-2 (1 set bit)

This can be viewed as recognizing that multiply-by-power-of-2 doesn't
have a carry into the top bit of an M-bit * N-bit n

[Support] improve known bits analysis for multiply by power-of-2 (1 set bit)

This can be viewed as recognizing that multiply-by-power-of-2 doesn't
have a carry into the top bit of an M-bit * N-bit number.

Enhancing canonicalization of mul -> select might also handle some of
these if we were ok with increasing instruction count with casts in
some cases.

This doesn't help https://llvm.org/PR49055 , but it's a simpler
pattern that we miss.
Note: "-sccp" already gets these examples using a constant
range analysis.

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

show more ...

[Support] replace check with assert in known bits of mul calculation; NFC

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

[KnownBits] Add support for X*X self-multiplication

Add KnownBits handling and unit tests for X*X self-multiplication cases which guarantee that bit1 of their results will be zero - see PR48683.

ht

[KnownBits] Add support for X*X self-multiplication

Add KnownBits handling and unit tests for X*X self-multiplication cases which guarantee that bit1 of their results will be zero - see PR48683.

https://alive2.llvm.org/ce/z/NN_eaR

The next step will be to add suitable test coverage so this can be enabled in ValueTracking/DAG/GlobalISel - currently only a single Analysis/ScalarEvolution test is affected.

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

show more ...

[KnownBits] Rename KnownBits::computeForMul to KnownBits::mul. NFCI.

As promised in D98866

Add debug printers for KnownBits [nfc]

[KnownBits] Add knownbits analysis for mulhs/mulu 'multiply high' instructions

Split off from D98857

https://reviews.llvm.org/D98866

[KnownBits] Add min/max shift amount handling to shl/lshr/ashr KnownBits helpers

Pulled out of the original D90479 patch - also includes the "impossible shift amount" filtering from computeKnownBits

[KnownBits] Add min/max shift amount handling to shl/lshr/ashr KnownBits helpers

Pulled out of the original D90479 patch - also includes the "impossible shift amount" filtering from computeKnownBitsFromShiftOperator.

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

show more ...

Revert rGd65ddca83ff85c7345fe9a0f5a15750f01e38420 - "[ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in LSHR/SHL (PR44526)"

This is causing sanitizer test failures that I haven

Revert rGd65ddca83ff85c7345fe9a0f5a15750f01e38420 - "[ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in LSHR/SHL (PR44526)"

This is causing sanitizer test failures that I haven't been able to fix yet.

show more ...

[ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in LSHR/SHL (PR44526)

Followup to D72573 - as detailed in https://blog.regehr.org/archives/1709 we don't make use of the known l

[ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in LSHR/SHL (PR44526)

Followup to D72573 - as detailed in https://blog.regehr.org/archives/1709 we don't make use of the known leading/trailing zeros for shifted values in cases where we don't know the shift amount value.

Stop ValueTracking returning zero for poison shift patterns and use the KnownBits shift helpers directly.

Extend KnownBits::shl to combine all possible shifted combinations if both min/max shift amount values are in range.

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

show more ...

[KnownBits] Pull out repeated getMinValue() calls from shift analysis. NFCI.

[KnownBits][RISCV] Improve known bits for srem.

The result must be less than or equal to the LHS side, so any
leading zeros in the left hand side must also exist in the result.
This is stronger than

[KnownBits][RISCV] Improve known bits for srem.

The result must be less than or equal to the LHS side, so any
leading zeros in the left hand side must also exist in the result.
This is stronger than the previous behavior where we only considered
the sign bit being 0.

The affected test case used the sign bit being known 0 to change
a sign extend to a zero extend pre type legalization. After type
legalization the types were promoted to i64, but we no longer
knew bit 31 was zero. This shifts are are the equivalent of an
AND with 0xffffffff or zext_inreg X, i32. This patch allows us to
see that bit 31 is zero and remove the shifts.

Reviewed By: RKSimon

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

show more ...

[Support] Simplify KnownBits::sextInReg implementation.

As noted by @foad in rG9cf4f493a72f all we need to do is sextInReg both KnownBits One and Zero.

[Support] Ensure KnownBits::sextInReg can handle the src == dst sext-in-reg case.

This was resulting in assertions inside APInt::zext that we were extending to the same bitwidth.

[Support] Simplify KnownBits::icmp helpers. NFC.

Remove some special cases that aren't really any simpler than the
general case.

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

[Support] Add KnownBits::icmp helpers.

Check if all possible values for a pair of knownbits give the same icmp result - these are based off the checks performed in InstCombineCompares.cpp and D86578

[Support] Add KnownBits::icmp helpers.

Check if all possible values for a pair of knownbits give the same icmp result - these are based off the checks performed in InstCombineCompares.cpp and D86578.

Add exhaustive unit test coverage - a followup will update InstCombineCompares.cpp to use this.

show more ...

[DAG] Move SelectionDAG implementation to KnownBits::setInReg(). NFCI.

[KnownBits] Combine abs() implementations

ValueTracking was using a more powerful abs() implementation. Roll
it into KnownBits::abs(). Also add an exhaustive test for abs(),
in both the poisoning an

[KnownBits] Combine abs() implementations

ValueTracking was using a more powerful abs() implementation. Roll
it into KnownBits::abs(). Also add an exhaustive test for abs(),
in both the poisoning and non-poisoning variants.

show more ...

[KnownBits] Merge the minimum shift amount and leading/trailing shift value bits handling.

By starting with the source shift value minimum leading/trailing bits, we can then add the minimum known sh

[KnownBits] Merge the minimum shift amount and leading/trailing shift value bits handling.

By starting with the source shift value minimum leading/trailing bits, we can then add the minimum known shift amount to more accurately predict the minimum leading/trailing bits of the result.

This is currently only covered by the exhaustive unit tests in KnownBitsTests.cpp, but will help with some of the regressions encountered in D90479 (PR44526).

show more ...

[KnownBits] Add KnownBits::commonBits helper. NFCI.

We have a frequent pattern where we're merging two KnownBits to get the common/shared bits, and I just fell for the gotcha where I tried to use th

[KnownBits] Add KnownBits::commonBits helper. NFCI.

We have a frequent pattern where we're merging two KnownBits to get the common/shared bits, and I just fell for the gotcha where I tried to use the & operator to merge them........

show more ...

[KnownBits] Move ValueTracking SREM KnownBits handling to KnownBits::srem. NFCI.

Move the ValueTracking implementation to KnownBits, the SelectionDAG version is more limited so I'm intending to repl

[KnownBits] Move ValueTracking SREM KnownBits handling to KnownBits::srem. NFCI.

Move the ValueTracking implementation to KnownBits, the SelectionDAG version is more limited so I'm intending to replace that as a separate commit.

show more ...