[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

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

Include exhaustive test coverage.

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

Split off from D98857

https://reviews.llvm.org/D98866

[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] Add KnownBits::sextInReg exhaustive tests

Requested by @foad in rG9cf4f493a72f

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

[Support] Add KnownBits::getSignedMinValue/getSignedMaxValue helpers.

Add unit test coverage - a followup will update InstCombineCompares.cpp to use this and could be used by D86578 as well.

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

[KnownBits] Move ValueTracking/SelectionDAG UREM KnownBits handling to KnownBits::urem. NFCI.

Both these have the same implementation - so move them to a single KnownBits copy.

GlobalISel will be a

[KnownBits] Move ValueTracking/SelectionDAG UREM KnownBits handling to KnownBits::urem. NFCI.

Both these have the same implementation - so move them to a single KnownBits copy.

GlobalISel will be able to use this as well with minimal effort.

show more ...

[KnownBits] Move ValueTracking/SelectionDAG UDIV KnownBits handling to KnownBits::udiv. NFCI.

Both these have the same implementation - so move them to a single KnownBits copy.

GlobalISel will be a

[KnownBits] Move ValueTracking/SelectionDAG UDIV KnownBits handling to KnownBits::udiv. NFCI.

Both these have the same implementation - so move them to a single KnownBits copy.

GlobalISel will be able to use this as well with minimal effort.

show more ...

[UnitTests] Add exhaustive tests for KnownBits shl/lshr/ashr

Thanks to @foad for the suggestion.

[KnownBits] Add a sextOrTrunc method

We already offer zextOrTrunc and it seems natural to offer the
same capability for sign extension.

This patch is a preparatory addition useful for future comput

[KnownBits] Add a sextOrTrunc method

We already offer zextOrTrunc and it seems natural to offer the
same capability for sign extension.

This patch is a preparatory addition useful for future computeKnownBits
developments.

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

show more ...

[KnownBits] Add a computeForMul method

This patch refactors the logic in ValueTracking.cpp so that
computeKnownBitsForMul now uses a helper function from KnownBits.

NFC

Differential Revision: http

[KnownBits] Add a computeForMul method

This patch refactors the logic in ValueTracking.cpp so that
computeKnownBitsForMul now uses a helper function from KnownBits.

NFC

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

show more ...

[KnownBits] Implement accurate unsigned and signed max and min

Use the new implementation in ValueTracking, SelectionDAG and
GlobalISel.

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

[DemandedBits] Improve accuracy of Add propagator

The current demand propagator for addition will mark all input bits at and right of the alive output bit as alive. But carry won't propagate beyond

[DemandedBits] Improve accuracy of Add propagator

The current demand propagator for addition will mark all input bits at and right of the alive output bit as alive. But carry won't propagate beyond a bit for which both operands are zero (or one/zero in the case of subtraction) so a more accurate answer is possible given known bits.

I derived a propagator by working through truth tables and using a bit-reversed addition to make demand ripple to the right, but I'm not sure how to make a convincing argument for its correctness in the comments yet. Nevertheless, here's a minimal implementation and test to get feedback.

This would help in a situation where, for example, four bytes (<128) packed into an int are added with four others SIMD-style but only one of the four results is actually read.

Known A: 0_______0_______0_______0_______
Known B: 0_______0_______0_______0_______
AOut: 00000000001000000000000000000000
AB, current: 00000000001111111111111111111111
AB, patch: 00000000001111111000000000000000

Committed on behalf of: @rrika (Erika)

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

show more ...

[KnownBits] Move AND, OR and XOR logic into KnownBits

Summary:
There are at least three clients for KnownBits calculations:
ValueTracking, SelectionDAG and GlobalISel. To reduce duplication the
comm

[KnownBits] Move AND, OR and XOR logic into KnownBits

Summary:
There are at least three clients for KnownBits calculations:
ValueTracking, SelectionDAG and GlobalISel. To reduce duplication the
common logic should be moved out of these clients and into KnownBits
itself.

This patch does this for AND, OR and XOR calculations by implementing
and using appropriate operator overloads KnownBits::operator& etc.

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[NFC][KnownBits] Add getMinValue() / getMaxValue() methods

As it can be seen from accompanying cleanup, it is not unheard of
to write `~Known.Zero` meaning "what maximal value can this KnownBits
pro

[NFC][KnownBits] Add getMinValue() / getMaxValue() methods

As it can be seen from accompanying cleanup, it is not unheard of
to write `~Known.Zero` meaning "what maximal value can this KnownBits
produce". But i think `~Known.Zero` isn't *that* self-explanatory,
as compared to a method with a name.

Note that not all `~Known.Zero` places were cleaned up,
only those where this arguably improves things.

show more ...

[KnownBits] Add computeForAddCarry()

This is for D60460. computeForAddSub() essentially already supports
carries because it has to deal with subtractions. This revision
extracts a lower-level comput

[KnownBits] Add computeForAddCarry()

This is for D60460. computeForAddSub() essentially already supports
carries because it has to deal with subtractions. This revision
extracts a lower-level computeForAddCarry() function, which allows
computing the known bits for add (carry known zero), sub (carry known
one) and addcarry (carry unknown).

As we don't seem to have any yet, I've added a unit test file for
KnownBits and exhaustive tests for the new computeForAddCarry()
functionality, as well the existing computeForAddSub() function.

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

llvm-svn: 358297

show more ...