[LLVM][IR] Use splat syntax when printing Constant[Data]Vector. (#112548)

[InstCombine] Drop `samesign` in InstCombine (#112480)

Closes https://github.com/llvm/llvm-project/issues/112476.

[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] Regenerate test checks (NFC)

[InstCombine] Canonicalize Bit Testing by Shifting to Bit 0 (#101838)

Implement a new transformation that fold the bit-testing expression
(icmp ne (and (lshr V B) 1) 0) to (icmp ne (and V (shl 1 B)

[InstCombine] Canonicalize Bit Testing by Shifting to Bit 0 (#101838)

Implement a new transformation that fold the bit-testing expression
(icmp ne (and (lshr V B) 1) 0) to (icmp ne (and V (shl 1 B)) 0) for
constant V. This rule already existed for non-constant V and constants
other than 1; this restriction to non-constant V has been added in
commit c3b2111d975a39d19f0c5d635e2961a4449c5a71 to fix an infinite loop.
Avoid the infinite loop by allowing constant V only if the shift
instruction is an lshr and the constant is 1. Also fold the negated
variant of the LHS.

This transformation necessitates an adaption of existing tests in
`icmp-and-shift.ll` and `load-cmp.ll`. One test in `icmp-and-shift.ll`,
which previously was a negative test, now gets folded. Rename it to
indicate that it is a positive test.

Alive proof: https://alive2.llvm.org/ce/z/vcJJTx

Relates to issue #86813.

show more ...

[InstCombine] fold `(icmp eq/ne (and (shl -1, X), Y), 0)` -> `(icmp eq/ne (lshr Y, X), 0)`

Proofs: https://alive2.llvm.org/ce/z/oSRGBt

Closes #84691

[InstCombine] Tests for `(icmp eq/ne (and (shl -1, X), Y), 0)` -> `(icmp eq/ne (lshr Y, X), 0)`; NFC

[InstCombine] Infer shift flags with unknown shamt (#72535)

Alive2: https://alive2.llvm.org/ce/z/82Wr3q

Related patch:
https://github.com/llvm/llvm-project/commit/2dd52b4527667837cc525aa48435ab5

[InstCombine] Infer shift flags with unknown shamt (#72535)

Alive2: https://alive2.llvm.org/ce/z/82Wr3q

Related patch:
https://github.com/llvm/llvm-project/commit/2dd52b4527667837cc525aa48435ab5cbfa30a0b

show more ...

[InstCombine] Canonicalize (A & B_Pow2) eq/ne B_Pow2 patterns

1. A & B_Pow2 != B_Pow2 -> A & B_Pow2 == 0
https://alive2.llvm.org/ce/z/KVUej4

2. A & B_Pow2 == B_Pow2 -> A & B_Pow2 != 0
https:/

[InstCombine] Canonicalize (A & B_Pow2) eq/ne B_Pow2 patterns

1. A & B_Pow2 != B_Pow2 -> A & B_Pow2 == 0
https://alive2.llvm.org/ce/z/KVUej4

2. A & B_Pow2 == B_Pow2 -> A & B_Pow2 != 0
https://alive2.llvm.org/ce/z/PVv9FR

This allows the patterns to more easily be analyzed elsewhere.

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

show more ...

[InstCombine] add tests for cmp of pow2 mask; NFC

[InstCombine] Optimise shift+and+boolean conversion pattern to simple comparison

if (`C1` is pow2) & (`(C2 & ~(C1-1)) + C1)` is pow2):
((C1 << X) & C2) == 0 -> X >= (Log2(C2+C1) - Log2(C1));
htt

[InstCombine] Optimise shift+and+boolean conversion pattern to simple comparison

if (`C1` is pow2) & (`(C2 & ~(C1-1)) + C1)` is pow2):
((C1 << X) & C2) == 0 -> X >= (Log2(C2+C1) - Log2(C1));
https://alive2.llvm.org/ce/z/EJAl1R
((C1 << X) & C2) != 0 -> X < (Log2(C2+C1) - Log2(C1));
https://alive2.llvm.org/ce/z/3bVRVz

And remove dead code.

Fix: https://github.com/llvm/llvm-project/issues/56124

Reviewed By: spatel

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

show more ...

[InstCombine] Update icmp-and-shift check-next name; NFC

[InstCombine] convert mask and shift of power-of-2 to cmp+select

When the mask is a power-of-2 constant and op0 is a shifted-power-of-2
constant, test if the shift amount equals the offset bit index

[InstCombine] convert mask and shift of power-of-2 to cmp+select

When the mask is a power-of-2 constant and op0 is a shifted-power-of-2
constant, test if the shift amount equals the offset bit index:

(ShiftC << X) & C --> X == (log2(C) - log2(ShiftC)) ? C : 0
(ShiftC >> X) & C --> X == (log2(ShiftC) - log2(C)) ? C : 0

This is an alternate to D127610 with a more general pattern.
We match only shift+and instead of the trailing xor, so we see a few
more tests diffs. I think we discussed this initially in D126617.

Here are proofs for shifts in both directions:
https://alive2.llvm.org/ce/z/CFrLs4

The test diffs look equal or better for IR, and this makes the
patterns more uniform in IR. The backend can partially invert this
in both cases if that is profitable. It is not trivially reversible,
however, so if we find perf regressions that are not easy to undo,
then we may want to revert this.

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

show more ...

[InstCombine] Optimize shl+lshr+and conversion pattern

if `C1` and `C3` are pow2 and `Log2(C3)+C2 < BitWidth`:
((C1 << X) >> C2) & C3 -> X == (Log2(C3)+C2-Log2(C1)) ? C3 : 0;

https://alive2.llv

[InstCombine] Optimize shl+lshr+and conversion pattern

if `C1` and `C3` are pow2 and `Log2(C3)+C2 < BitWidth`:
((C1 << X) >> C2) & C3 -> X == (Log2(C3)+C2-Log2(C1)) ? C3 : 0;

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

Fix issue https://github.com/llvm/llvm-project/issues/55739

Reviewed By: spatel

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

show more ...

[InstCombine] fold shift-right-by-constant with shift-right-of-constant operand

(C2 >> X) >> C1 --> (C2 >> C1) >> X

The shift-left form of this transform has existed since:
16f18ed7b555bce5163

.

[InstCombine] fold shift-right-by-constant with shift-right-of-constant operand

(C2 >> X) >> C1 --> (C2 >> C1) >> X

The shift-left form of this transform has existed since:
16f18ed7b555bce5163

...but it applies to matching shift right opcodes too:
https://alive2.llvm.org/ce/z/c5eQms

show more ...

[InstCombine] Add baseline tests for shift+and+icmp transforms; NFC