[InstCombine] Add mul with negated power of 2 constant to canEvaluateShifted.

If we are right shifting a multiply by a negated power of 2 where
the power of 2 is the same as the shift amount, we can

[InstCombine] Add mul with negated power of 2 constant to canEvaluateShifted.

If we are right shifting a multiply by a negated power of 2 where
the power of 2 is the same as the shift amount, we can replace with
a negate followed by an And.

New tests have not been committed yet but the patch shows the diffs.
Let me know if you want any changes or additional tests.

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

show more ...

[InstCombine] Avoid some calls to ConstantExpr::get() (NFCI)

Replace some calls to ConstantExpr::get() with IRBuilder APIs
(which will also constant fold if possible).

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with
the cleanup of InstructionSimplify in one commit.

This is the alternative to the less invasive clang-format only patch: D126783

Reviewed By: spatel, rengolin

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

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] remove unnecessary one-use check from (C2 << X) << C1 fold

The restriction goes back to:
16f18ed7b555bce51
...but the fold only replaces a shift with a shift, so that's not necessary.

[InstCombine] remove unnecessary one-use check from (C2 << X) << C1 fold

The restriction goes back to:
16f18ed7b555bce51
...but the fold only replaces a shift with a shift, so that's not necessary.
Generalizing to other opcodes is planned as a follow-up.

show more ...

Revert "[InstCombine] invert canonicalization for cast of signbit test"

This reverts commit 3794cc0e996481e10307b67c8436aa44e0d65d22.
This change is suspected of causing bots to hang at stage 2
comp

Revert "[InstCombine] invert canonicalization for cast of signbit test"

This reverts commit 3794cc0e996481e10307b67c8436aa44e0d65d22.
This change is suspected of causing bots to hang at stage 2
compiles, so reverting to confirm and investigate.

show more ...

[InstCombine] invert canonicalization for cast of signbit test

The existing transform was wrong in 3 ways:
1. It created an extra instruction when the source and dest types don't match.
2. It did no

[InstCombine] invert canonicalization for cast of signbit test

The existing transform was wrong in 3 ways:
1. It created an extra instruction when the source and dest types don't match.
2. It did not account for an extra use of the icmp, so could create 2 extra insts.
3. It favored bit hacks over icmp (icmp generally has better analysis).

This fixes #54692 (modeled by the PhaseOrdering tests).

This is a minimal step to fix the bug, but we should likely invert
the sibling transform for the "is negative" pattern too.

The backend should be able to invert this back to a shift if that
leads to better codegen.

show more ...

[InstCombine] try to narrow more shifted bswap-of-zext

Try to narrow more bswap, if the shift amount is less than the zext
(bswap (zext X)) >> C --> (zext (bswap X)) << C'

https://alive2.llvm.org/c

[InstCombine] try to narrow more shifted bswap-of-zext

Try to narrow more bswap, if the shift amount is less than the zext
(bswap (zext X)) >> C --> (zext (bswap X)) << C'

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

Reviewed By: RKSimon

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

show more ...

[InstCombine] C0 >> (X - C1) --> (C0 << C1) >> X

With the right pre-conditions, we can fold the offset
into the shifted constant:
https://alive2.llvm.org/ce/z/drMRBU
https://alive2.llvm.org/ce/z/cUQ

[InstCombine] C0 >> (X - C1) --> (C0 << C1) >> X

With the right pre-conditions, we can fold the offset
into the shifted constant:
https://alive2.llvm.org/ce/z/drMRBU
https://alive2.llvm.org/ce/z/cUQv-_

Fixes #55016

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

show more ...

[InstCombine] C0 <<{nsw, nuw} (X - C1) --> (C0 >> C1) << X (2nd try)

The first attempt at this missed a check to make sure the offset
constant was in range and caused many bot failures.

That was mi

[InstCombine] C0 <<{nsw, nuw} (X - C1) --> (C0 >> C1) << X (2nd try)

The first attempt at this missed a check to make sure the offset
constant was in range and caused many bot failures.

That was missed in the Alive2 proof because on overshift creates
poison rather than the assert from APInt. Here's an alternate
attempt at a proof using count-trailing-zeros:
https://alive2.llvm.org/ce/z/pnXQYR

Original commit message:

This is similar to an existing pre-shift-of-constant fold:
8a9c70fc01e6
...but in this case, we need no-wrap on the shl and a negative
offset:
https://alive2.llvm.org/ce/z/_RVz99

show more ...

Revert "[InstCombine] Add one use limitation for (X * C2) << C1 --> X * (C2 << C1)"

This reverts commit b543d28df7b067dcda833c717a59faa28c1151a1.

[InstCombine] Add one use limitation for (X * C2) << C1 --> X * (C2 << C1)

Follow up D123453, add one-use limitation for
(X * C2) << C1 --> X * (C2 << C1)
to make consistent with
lshr (mul nuw x, M

[InstCombine] Add one use limitation for (X * C2) << C1 --> X * (C2 << C1)

Follow up D123453, add one-use limitation for
(X * C2) << C1 --> X * (C2 << C1)
to make consistent with
lshr (mul nuw x, MulC), ShAmtC -> mul nuw x, (MulC >> ShAmtC)

Reviewed By: spatel

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

show more ...

Revert "[InstCombine] C0 <<{nsw, nuw} (X - C1) --> (C0 >> C1) << X"

This reverts commit 5819f4a422865fc9a8ea4dc772769e14010ff6a7.
This caused bots to fail with a crash/assert during the fold,
so som

Revert "[InstCombine] C0 <<{nsw, nuw} (X - C1) --> (C0 >> C1) << X"

This reverts commit 5819f4a422865fc9a8ea4dc772769e14010ff6a7.
This caused bots to fail with a crash/assert during the fold,
so some constraint was missed.

show more ...

[InstCombine] C0 <<{nsw, nuw} (X - C1) --> (C0 >> C1) << X

This is similar to an existing pre-shift-of-constant fold:
8a9c70fc01e6
...but in this case, we need no-wrap on the shl and a negative
offs

[InstCombine] C0 <<{nsw, nuw} (X - C1) --> (C0 >> C1) << X

This is similar to an existing pre-shift-of-constant fold:
8a9c70fc01e6
...but in this case, we need no-wrap on the shl and a negative
offset:
https://alive2.llvm.org/ce/z/_RVz99

Fixes #54890

show more ...

[InstCombine] Fold mul nuw+lshr to a single multiplication when the latter is a factor

if c is divisible by (1 << ShAmtC), we can fold this pattern:
lshr (mul nuw x, c), ShAmtC -> mul nuw x, (c >> S

[InstCombine] Fold mul nuw+lshr to a single multiplication when the latter is a factor

if c is divisible by (1 << ShAmtC), we can fold this pattern:
lshr (mul nuw x, c), ShAmtC -> mul nuw x, (c >> ShAmtC)

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

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

Reviewed By: spatel, lebedev.ri, craig.topper

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

show more ...

[InstCombine] remove likely redundant ValueTracking-based folds for shifts

This is not expected to have a functional difference as discussed in the
post-commit comments for 8a9c70fc01e6. All of the

[InstCombine] remove likely redundant ValueTracking-based folds for shifts

This is not expected to have a functional difference as discussed in the
post-commit comments for 8a9c70fc01e6. All of the motivating tests for
the older fold still optimize as expected because other code can infer
the 'nuw'.

show more ...

[InstCombine] C0 shift (X add nuw C) --> (C0 shift C) shift X

With 'nuw' we can convert the increment of the shift amount
into a pre-shift (constant fold) of the shifted constant:
https://alive2.llv

[InstCombine] C0 shift (X add nuw C) --> (C0 shift C) shift X

With 'nuw' we can convert the increment of the shift amount
into a pre-shift (constant fold) of the shifted constant:
https://alive2.llvm.org/ce/z/FkTyR2

Fixes issue #41976

show more ...

[InstCombine] guard against splat-mul corner case

The test is already simplified, and I'm not sure how
to write a test to exercise the new clause. But it
protects the 2-bit pattern from miscompiling

[InstCombine] guard against splat-mul corner case

The test is already simplified, and I'm not sure how
to write a test to exercise the new clause. But it
protects the 2-bit pattern from miscompiling as noted
in D123453.

https://alive2.llvm.org/ce/z/QPyVfv
(If we managed to fall into the mul transform, it
would wrongly create a zero on this pattern.)

show more ...

[InstCombine] try to narrow shifted bswap-of-zext (2nd try)

The first attempt at this missed a validity check.
This version includes a test of the narrow source
type for modulo-16-bits.

Original co

[InstCombine] try to narrow shifted bswap-of-zext (2nd try)

The first attempt at this missed a validity check.
This version includes a test of the narrow source
type for modulo-16-bits.

Original commit message:

This is the IR counterpart to 370ebc9d9a573d6
which provided a bswap narrowing fix for issue #53867.

Here we can be more general (although I'm not sure yet
what would happen for illegal types in codegen - too
rare to worry about?):
https://alive2.llvm.org/ce/z/3-CPfo

This will be more effective if we have moved the shift
after the bswap as proposed in D122010, but it is
independent of that patch.

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

show more ...

Revert "[InstCombine] try to narrow shifted bswap-of-zext"

This reverts commit 9e9bda2e8f5b88715bad767a4b7740df32b040d2.

This causes a backend error when building the Linux kernel for arm64.
See ht

Revert "[InstCombine] try to narrow shifted bswap-of-zext"

This reverts commit 9e9bda2e8f5b88715bad767a4b7740df32b040d2.

This causes a backend error when building the Linux kernel for arm64.
See https://reviews.llvm.org/D122166 for a simplified reproducer.

show more ...

[InstCombine] try to narrow shifted bswap-of-zext

This is the IR counterpart to 370ebc9d9a573d6
which provided a bswap narrowing fix for issue #53867.

Here we can be more general (although I'm not

[InstCombine] try to narrow shifted bswap-of-zext

This is the IR counterpart to 370ebc9d9a573d6
which provided a bswap narrowing fix for issue #53867.

Here we can be more general (although I'm not sure yet
what would happen for illegal types in codegen - too
rare to worry about?):
https://alive2.llvm.org/ce/z/3-CPfo

This will be more effective if we have moved the shift
after the bswap as proposed in D122010, but it is
independent of that patch.

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

show more ...

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cl

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120817

show more ...

[InstCombine] try to fold binop with phi operands

This is an alternate version of D115914 that handles/tests all binary opcodes.

I suspect that we don't see these patterns too often because -simpli

[InstCombine] try to fold binop with phi operands

This is an alternate version of D115914 that handles/tests all binary opcodes.

I suspect that we don't see these patterns too often because -simplifycfg
would convert the minimal cases into selects rather than leave them in phi form
(note: instcombine has logic holes for combining the select patterns too though,
so that's another potential patch).

We only create a new binop in a predecessor that unconditionally branches to
the final block.
https://alive2.llvm.org/ce/z/C57M2F
https://alive2.llvm.org/ce/z/WHwAoU (not safe to speculate an sdiv for example)
https://alive2.llvm.org/ce/z/rdVUvW (but it is ok on this path)

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

show more ...

[InstCombine] add one-use check to opposite shift folds

Test comments say this might be intentional, but I don't
see any hard evidence to support it. The extra instruction
shows up as a potential re

[InstCombine] add one-use check to opposite shift folds

Test comments say this might be intentional, but I don't
see any hard evidence to support it. The extra instruction
shows up as a potential regression in D117680.

One test does show a missed fold that might be recovered
with better demanded bits analysis.

show more ...

[InstCombine] fold opposite shifts around an add

((X << C) + Y) >>u C --> (X + (Y >>u C)) & (-1 >>u C)

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

This replaces a shift with an 'and', and in the case
wher

[InstCombine] fold opposite shifts around an add

((X << C) + Y) >>u C --> (X + (Y >>u C)) & (-1 >>u C)

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

This replaces a shift with an 'and', and in the case
where the add has a constant operand, it eliminates
both shifts.

As noted in the TODO comment, we already have this fold when
the shifts are in the opposite order (and that code handles
bitwise logic ops too).

Fixes #52851

show more ...