[InstCombine] Fold `X udiv Y` to `X lshr cttz(Y)` if Y is a power of 2 (#121386)

Fixes #115767

This PR folds `X udiv Y` to `X lshr cttz(Y)` if Y is a power of two
since bitwise operations are fa

[InstCombine] Fold `X udiv Y` to `X lshr cttz(Y)` if Y is a power of 2 (#121386)

Fixes #115767

This PR folds `X udiv Y` to `X lshr cttz(Y)` if Y is a power of two
since bitwise operations are faster than division.

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

show more ...

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

[InstCombine] Infer nneg flag from shift users (#71947)

This patch sets `nneg` flag when the zext is only used by a shift.

Alive2: https://alive2.llvm.org/ce/z/h3xKjP
Compile-time impact:
https

[InstCombine] Infer nneg flag from shift users (#71947)

This patch sets `nneg` flag when the zext is only used by a shift.

Alive2: https://alive2.llvm.org/ce/z/h3xKjP
Compile-time impact:
https://llvm-compile-time-tracker.com/compare.php?from=bd611264993f64decbce178d460caf1d1cb05f59&to=26bc473b239010bb24ff1bc39d58b42ecbbc4730&stat=instructions:u

This is an alternative to #71906.

show more ...

[InstCombine] Don't mix X << Y / Z << Y with X << Y / X << Z (#69302)

Fixes #69291.
This patch improve the logic handling different patterns to avoid mixing these
pattern.

[InstCombine] Fold (X << Y) / (X << Z) -> 1 << Y >> Z (#68863)

Resolve #68857.
Alive2 proofs:
[Whole proofs](https://alive2.llvm.org/ce/z/A5b85F)

[InstCombine] Fix buggy `(mul X, Y)` -> `(shl X, Log2(Y))` transform PR62175

Bug was because we recognized patterns like `(shl 4, Z)` as a power of
2 we could take Log2 of (`2 + Z`), but doing `(shl

[InstCombine] Fix buggy `(mul X, Y)` -> `(shl X, Log2(Y))` transform PR62175

Bug was because we recognized patterns like `(shl 4, Z)` as a power of
2 we could take Log2 of (`2 + Z`), but doing `(shl X, (2 + Z))` can
cause a poison shift.
https://alive2.llvm.org/ce/z/yuJm_k

The fix is to verify that `Log2(Y)` will be a non-poisonous shift
amount. We can do this with:
`nsw` flag:
- https://alive2.llvm.org/ce/z/yyyJBr
- https://alive2.llvm.org/ce/z/YgubD_
`nuw` flag:
- https://alive2.llvm.org/ce/z/-4mpyV
- https://alive2.llvm.org/ce/z/a6ik6r
Prove `Y != 0`:
- https://alive2.llvm.org/ce/z/ced4su
- https://alive2.llvm.org/ce/z/X-JJHb

Reviewed By: nikic

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

show more ...

[InstCombine] canonicalize cmp+select as umin/umax

(V == 0) ? 1 : V --> umax(V, 1)
(V == UMAX) ? UMAX-1 : V --> umin(V, UMAX-1)

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

This is one pair of the variants

[InstCombine] canonicalize cmp+select as umin/umax

(V == 0) ? 1 : V --> umax(V, 1)
(V == UMAX) ? UMAX-1 : V --> umin(V, UMAX-1)

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

This is one pair of the variants discussed in issue #60374.

Enhancements for the other end of the constant range and
signed variants are potential follow-ups, but that may
require more work because we canonicalize at least one
min/max like that to icmp+zext.

show more ...

[InstCombine] Fold (X << Z) / (X * Y) -> (1 << Z) / Y

Alive2: https://alive2.llvm.org/ce/z/CBJLeP

[InstCombine] complete (X << Z) / (Y << Z) --> X / Y

Add one more situations for this fold.
For unsigned div, 'nsw' on both shifts + 'nuw' on the dividend.

Alive2: https://alive2.llvm.org/ce/z/sELF

[InstCombine] complete (X << Z) / (Y << Z) --> X / Y

Add one more situations for this fold.
For unsigned div, 'nsw' on both shifts + 'nuw' on the dividend.

Alive2: https://alive2.llvm.org/ce/z/sELF76

Reviewed By: spatel

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

show more ...

[InstCombine] add nuw to any (1<<x)

https://alive2.llvm.org/ce/z/9EjDKE

This was mentioned as a missing fold in D139598.

It can unlock follow-on folds in some cases.
This verifies one of the chang

[InstCombine] add nuw to any (1<<x)

https://alive2.llvm.org/ce/z/9EjDKE

This was mentioned as a missing fold in D139598.

It can unlock follow-on folds in some cases.
This verifies one of the changed tests:
https://alive2.llvm.org/ce/z/B_btDM

show more ...

[InstCombine] Add tests for udiv with shl-mul; NFC

[InstCombine] Add tests for (X << Z) / (X * Y) -> (1 << Z) / Y. nfc

[InstCombine] add test for udiv with shl divisor; NFC

This would solve an example from issue #58137 more
generally, but it may require adding a canonicalization
for shift + shift to shift + add.

[InstCombine] fold sdiv with common shl amount in operands

(X << Z) / (Y << Z) --> X / Y

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

This requires a surprising "nuw" constraint because we have
to guard ag

[InstCombine] fold sdiv with common shl amount in operands

(X << Z) / (Y << Z) --> X / Y

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

This requires a surprising "nuw" constraint because we have
to guard against immediate UB via signed-div overflow with
-1 divisor.

This extends 008a89037a49ca0d9 and is another transform
derived from issue #58137.

show more ...

[InstCombine] fold udiv with common shl amount in operands

(X << Z) / (Y << Z) --> X / Y

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

This fixes the motivating example from issue #58137,
but it is not the

[InstCombine] fold udiv with common shl amount in operands

(X << Z) / (Y << Z) --> X / Y

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

This fixes the motivating example from issue #58137,
but it is not the most general transform. We should
probably also convert left-shift in the divisor to
right-shift in the dividend for that, but that exposes
another missed canonicalization for shifts and adds.

show more ...

[InstCombine] propagate "exact" through folds of div

These folds were added recently with:
6b869be8100d
8da2fa856f1b
...but they didn't account for the "exact" attribute,
and that can be safely prop

[InstCombine] propagate "exact" through folds of div

These folds were added recently with:
6b869be8100d
8da2fa856f1b
...but they didn't account for the "exact" attribute,
and that can be safely propagated:
https://alive2.llvm.org/ce/z/F_WhnR
https://alive2.llvm.org/ce/z/ft9Cgr

show more ...

[InstCombine] add "exact" to div tests to show missing propagation; NFC

[InstCombine] add tests for div with shl operands; NFC

[InstCombine] fold udiv with common factor

((X *nuw Y) >> Z) / X --> Y >> Z

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

This is similar to 6b869be8100d / 8da2fa856f1b, but I have
not found a signed equiva

[InstCombine] fold udiv with common factor

((X *nuw Y) >> Z) / X --> Y >> Z

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

This is similar to 6b869be8100d / 8da2fa856f1b, but I have
not found a signed equivalent, so it's just an unsigned
match for now.

show more ...

[InstCombine] add 'exact' to udiv test for more coverage; NFC

[InstCombine] add tests for udiv with common factor; NFC

[InstCombine] add tests for udiv with shift-left divisor; NFC

issue #58137

[InstCombine] fold sdiv with hidden common factor

(X * Y) s/ (X << Z) --> Y s/ (1 << Z)

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

issue #58137

[InstCombine] fold udiv with hidden common factor

(X * Y) u/ (X << Z) --> Y u>> Z

https://alive2.llvm.org/ce/z/4G9D_W

[InstCombine] add tests for div with common factor; NFC