[ValueTracking] Fix bug of using wrong condition for deducing KnownBits (#124481)

- **[ValueTracking] Add test for issue 124275**
- **[ValueTracking] Fix bug of using wrong condition for deducing

[ValueTracking] Fix bug of using wrong condition for deducing KnownBits (#124481)

- **[ValueTracking] Add test for issue 124275**
- **[ValueTracking] Fix bug of using wrong condition for deducing
KnownBits**

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

Bug was introduced by https://github.com/llvm/llvm-project/pull/114689

Now that computeKnownBits supports breaking out of recursive Phi
nodes, `IncValue` can be an operand of a different Phi than `P`. This
breaks the previous assumptions we had when using the possibly
condition at `CxtI` to constrain `IncValue`.

show more ...

[InstCombine] Move gep of phi fold into separate function

This makes sure that an early return during this fold doesn't end
up skipping later gep folds.

[InstCombine] Infer nusw + nneg -> nuw for getelementptr (#111144)

If the gep is nusw (usually via inbounds) and the offset is
non-negative, we can infer nuw.

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

[InstCombine] Infer nusw + nneg -> nuw for getelementptr (#111144)

If the gep is nusw (usually via inbounds) and the offset is
non-negative, we can infer nuw.

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

show more ...

[InstCombine] Remove some of the complexity-based canonicalization (#91185)

The idea behind this canonicalization is that it allows us to handle less
patterns, because we know that some will be can

[InstCombine] Remove some of the complexity-based canonicalization (#91185)

The idea behind this canonicalization is that it allows us to handle less
patterns, because we know that some will be canonicalized away. This is
indeed very useful to e.g. know that constants are always on the right.

However, this is only useful if the canonicalization is actually
reliable. This is the case for constants, but not for arguments: Moving
these to the right makes it look like the "more complex" expression is
guaranteed to be on the left, but this is not actually the case in
practice. It fails as soon as you replace the argument with another
instruction.

The end result is that it looks like things correctly work in tests,
while they actually don't. We use the "thwart complexity-based
canonicalization" trick to handle this in tests, but it's often a
challenge for new contributors to get this right, and based on the
regressions this PR originally exposed, we clearly don't get this right
in many cases.

For this reason, I think that it's better to remove this complexity
canonicalization. It will make it much easier to write tests for
commuted cases and make sure that they are handled.

show more ...

[InstCombine] Remove root special case in demanded bits simplification

When calling SimplifyDemandedBits (as opposed to
SimplifyDemandedInstructionBits), and there are multiple uses,
always use Simp

[InstCombine] Remove root special case in demanded bits simplification

When calling SimplifyDemandedBits (as opposed to
SimplifyDemandedInstructionBits), and there are multiple uses,
always use SimplifyMultipleUseDemandedBits and drop the special
case for root values.

This fixes the ephemeral value detection, as seen by the restored
assumes in tests. It may result in more or less simplification,
depending on whether we get more out of having demanded bits or
the ability to perform non-multi-use transforms. The change in
the phi-known-bits.ll test is because the icmp operand now gets
simplified based on demanded bits, which then prevents a different
known bits simplification later.

This also makes the code safe against future changes like
https://github.com/llvm/llvm-project/pull/97289, which add more
context that would have to be discarded for the multi-use case.

show more ...

[InstCombine] Canonicalize scalable GEPs to use llvm.vscale intrinsic (#90569)

Canonicalize getelementptr instructions for scalable vector types into
ptradd representation with an explicit llvm.vsc

[InstCombine] Canonicalize scalable GEPs to use llvm.vscale intrinsic (#90569)

Canonicalize getelementptr instructions for scalable vector types into
ptradd representation with an explicit llvm.vscale call. This
representation has better support in BasicAA, which can reason about
llvm.vscale, but not plain scalable GEPs.

show more ...

[ValueTracking] isNonZero sub of ptr2int's with recursive GEP (#68680)

When the sub arguments are ptr2int it is not possible to determine
computeKnownBits() of its arguments.
For scalar case gener

[ValueTracking] isNonZero sub of ptr2int's with recursive GEP (#68680)

When the sub arguments are ptr2int it is not possible to determine
computeKnownBits() of its arguments.
For scalar case generally sub of 2 ptr2int are converted to sub of
indexes.
However a loop with recursive GEP/PHI where the arguments to sub is of
type ptr2int, if it is possible to determine that a sub of this GEP and
another pointer with the same base is KnownNonZero we can return this.
This helps subsequent passes to optimize the loop further.

show more ...

[ValueTracking] isNonEqual Pointers with with a recursive GEP (#70459)

Handles canonical icmp eq(ptr1, ptr2) -> where ptr1/ptr2 is a recursive
GEP.
Can helps scenarios where InstCombineCompares fo

[ValueTracking] isNonEqual Pointers with with a recursive GEP (#70459)

Handles canonical icmp eq(ptr1, ptr2) -> where ptr1/ptr2 is a recursive
GEP.
Can helps scenarios where InstCombineCompares folds icmp eq(sub(ptr2int,
ptr2int), 0) -> icmp eq(ptr1, ptr2)
and
icmp eq(phi(sub(ptr2int, ptr2int), ...)) -> phi i1 (icmp eq(sub(ptr2int,
ptr2int), 0), ....)

show more ...

[ValueTracking] Strengthen analysis in `computeKnownBits` of phi

Use the comparison based analysis to strengthen the standard
knownbits analysis rather than choosing either/or.

Reviewed By: nikic

[ValueTracking] Strengthen analysis in `computeKnownBits` of phi

Use the comparison based analysis to strengthen the standard
knownbits analysis rather than choosing either/or.

Reviewed By: nikic

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

show more ...

[ValueTracking] Improve analysis of knownbits from incoming phi edges.

Just fill in missing cases (TODO) for `ugt`, `uge`, `sgt`, `sge`,
`slt`, and `sle`. These are all in the same spirit as `ult`/`

[ValueTracking] Improve analysis of knownbits from incoming phi edges.

Just fill in missing cases (TODO) for `ugt`, `uge`, `sgt`, `sge`,
`slt`, and `sle`. These are all in the same spirit as `ult`/`uge`, but
each of the other conditions have different constraints.

Proofs: https://alive2.llvm.org/ce/z/gnj4o-

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

show more ...

[ValueTracking] Add tests for getting knownbits from phi-edges; NFC

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