[InstCombine] Fold `X Pred C2 ? X BOp C1 : C2 BOp C1` to `min/max(X, C2) BOp C1` (#116888)

Fixes #82414.

General Proof: https://alive2.llvm.org/ce/z/ERjNs4
Proof for Tests: https://alive2.llvm.

[InstCombine] Fold `X Pred C2 ? X BOp C1 : C2 BOp C1` to `min/max(X, C2) BOp C1` (#116888)

Fixes #82414.

General Proof: https://alive2.llvm.org/ce/z/ERjNs4
Proof for Tests: https://alive2.llvm.org/ce/z/K-934G

This PR transforms `select` instructions of the form `select (Cmp X C1)
(BOp X C2) C3` to `BOp (min/max X C1) C2` iff `C3 == BOp C1 C2`.

This helps in eliminating a noop loop in
https://github.com/rust-lang/rust/issues/123845 but does not improve
optimizations.

show more ...

[InstCombine] Fold `umax(X, C) + -C` into `usub.sat(X, C)` (#118195)

Alive2: https://alive2.llvm.org/ce/z/oSWe5S
Closes https://github.com/llvm/llvm-project/issues/118155

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

[InstCombine] Use `m_NotForbidPoison` when folding `(X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)` (#114345)

Alive2: https://alive2.llvm.org/ce/z/mTGCo-
We cannot reuse `~X` if `m_AllOnes` matches a

[InstCombine] Use `m_NotForbidPoison` when folding `(X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)` (#114345)

Alive2: https://alive2.llvm.org/ce/z/mTGCo-
We cannot reuse `~X` if `m_AllOnes` matches a vector constant with some
poison elts. An alternative solution is to create a new not instead of
reusing `~X`. But it doesn't worth the effort because we need to add a
one-use check.

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

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] Canonicalize more saturated-add variants (#100008)

LLVM is not evaluating X u > C, a, b the same way it evaluates X <= C, b, a.

To fix this, let's move the folds to after the canonica

[InstCombine] Canonicalize more saturated-add variants (#100008)

LLVM is not evaluating X u > C, a, b the same way it evaluates X <= C, b, a.

To fix this, let's move the folds to after the canonicalization of -1 to TrueVal.

Let's allow splat vectors with poison elements to be recognized too!

Finally, for completion, handle the one case that isn't caught by the above checks because it is canonicalized to eq:
X == -1 ? -1 : X + 1 -> uadd.sat(X, 1)

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

show more ...

[InstCombine] Pre-commit tests for #100008 (NFC)

[ValueTracking][LVI] Consolidate vector constant range calculation

Add a common helper used for computeConstantRange() and LVI. The
implementation is a mix of both, with the efficient handling for
C

[ValueTracking][LVI] Consolidate vector constant range calculation

Add a common helper used for computeConstantRange() and LVI. The
implementation is a mix of both, with the efficient handling for
ConstantDataVector taken from computeConstantRange(), and the
general handling (including non-splat poison) from LVI.

show more ...

[InstCombine] Add test for computeConstantRange() with non-splat poison (NFC)

[PatternMatch] Do not accept undef elements in m_AllOnes() and friends (#88217)

Change all the cstval_pred_ty based PatternMatch helpers (things like
m_AllOnes and m_Zero) to only allow poison elem

[PatternMatch] Do not accept undef elements in m_AllOnes() and friends (#88217)

Change all the cstval_pred_ty based PatternMatch helpers (things like
m_AllOnes and m_Zero) to only allow poison elements inside vector
splats, not undef elements.

Historically, we used to represent non-demanded elements in vectors
using undef. Nowadays, we use poison instead. As such, I believe that
support for undef in vector splats is no longer useful.

At the same time, while poison splat elements are pretty much always
safe to ignore, this is not generally the case for undef elements. We
have existing miscompiles in our tests due to this (see the
masked-merge-*.ll tests changed here) and it's easy to miss such cases
in the future, now that we write tests using poison instead of undef
elements.

I think overall, keeping support for undef elements no longer makes
sense, and we should drop it. Once this is done consistently, I think we
may also consider allowing poison in m_APInt by default, as doing that
change is much less risky than doing the same with undef.

This change involves a substantial amount of test changes. For most
tests, I've just replaced undef with poison, as I don't think there is
value in retaining both. For some tests (where the distinction between
undef and poison is important), I've duplicated tests.

show more ...

[ValueTracking] Add support for non-splat vecs in computeConstantRange (#72365)

Related patch: https://github.com/llvm/llvm-project/pull/68331
This missed optimization is discovered with the help o

[ValueTracking] Add support for non-splat vecs in computeConstantRange (#72365)

Related patch: https://github.com/llvm/llvm-project/pull/68331
This missed optimization is discovered with the help of
https://github.com/AliveToolkit/alive2/pull/962.

show more ...

[InstCombine] Remove instcombine-infinite-loop-threshold option

This option has been superseded by the fixpoint verification
functionality.

[ValueTracking] Fix incorrect computeConstantRange() arguments

The second argument is ForSigned, not UseInstrInfo.

[InstCombine] Add extra test for non-overflowing usub.sat (NFC)

Same as the existing one, but with both nuw and nsw on the add.

[InstCombine] Fold zero check followed by decrement to usub.sat

Fold (a == 0) : 0 ? a - 1 into usub.sat(a, 1).

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

[InstCombine] Add tests for saturating subtract by one (NFC)

Tests for D140798.

[test] Switch to use -passes syntax in a bunch of test cases

Should cover most of the tests for GVN, GVNHoist, GVNSink, GlobalOpt,
GlobalSplit, InstCombine, Reassociate, SROA and TailCallElim that
h

[test] Switch to use -passes syntax in a bunch of test cases

Should cover most of the tests for GVN, GVNHoist, GVNSink, GlobalOpt,
GlobalSplit, InstCombine, Reassociate, SROA and TailCallElim that
had not been updated earlier.

show more ...

[test][InstCombine] Update some test cases to use opaque pointers

These tests cases were converted using the script at
https://gist.github.com/nikic/98357b71fd67756b0f064c9517b62a34

Differential Re

[test][InstCombine] Update some test cases to use opaque pointers

These tests cases were converted using the script at
https://gist.github.com/nikic/98357b71fd67756b0f064c9517b62a34

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

show more ...

[InstCombine] Canonicalize SPF to min/max intrinsics

Now that integer min/max intrinsics have good support in both
InstCombine and other passes, start canonicalizing SPF min/max
to intrinsic min/max

[InstCombine] Canonicalize SPF to min/max intrinsics

Now that integer min/max intrinsics have good support in both
InstCombine and other passes, start canonicalizing SPF min/max
to intrinsic min/max.

Once this sticks, we can stop matching SPF min/max in various
places, and can remove hacks we have for preventing infinite loops
and breaking of SPF canonicalization.

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

show more ...

[InstCombine] X - usub.sat(X, Y) => umin(X, Y)

Pattern regressed in LLVM 9 with the introduction of usub.sat.

Fixes https://bugs.llvm.org/show_bug.cgi?id=42178#c2

Reviewed By: nikic

Differential

[InstCombine] X - usub.sat(X, Y) => umin(X, Y)

Pattern regressed in LLVM 9 with the introduction of usub.sat.

Fixes https://bugs.llvm.org/show_bug.cgi?id=42178#c2

Reviewed By: nikic

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

show more ...

[InstCombine] canonicalizeSaturatedAdd(): last fold is only valid for strict comparison (PR48390)

We could create uadd.sat under incorrect circumstances
if a select with -1 as the false value was ca

[InstCombine] canonicalizeSaturatedAdd(): last fold is only valid for strict comparison (PR48390)

We could create uadd.sat under incorrect circumstances
if a select with -1 as the false value was canonicalized
by swapping the T/F values. Unlike the other transforms
in the same function, it is not invariant to equality.

Some alive proofs: https://alive2.llvm.org/ce/z/emmKKL

Based on original patch by David Green!

Fixes https://bugs.llvm.org/show_bug.cgi?id=48390

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

show more ...

[NFC][InstCombine] Add test coverage for @llvm.uadd.sat canonicalization

The non-strict variants are already handled because they are canonicalized
to strict variants by swapping hands in both the s

[NFC][InstCombine] Add test coverage for @llvm.uadd.sat canonicalization

The non-strict variants are already handled because they are canonicalized
to strict variants by swapping hands in both the select and icmp,
and the fold simply considers that strictness is irrelevant here.

But that isn't actually true for the last pattern, as PR48390 reports.

show more ...

[InstCombine] usub.sat(a, b) + b => umax(a, b) (PR42178)

Fixes https://bugs.llvm.org/show_bug.cgi?id=42178 by folding
usub.sat(a, b) + b to umax(a, b). The backend will expand umax
back to usubsat i

[InstCombine] usub.sat(a, b) + b => umax(a, b) (PR42178)

Fixes https://bugs.llvm.org/show_bug.cgi?id=42178 by folding
usub.sat(a, b) + b to umax(a, b). The backend will expand umax
back to usubsat if that is profitable.

We may also want to handle uadd.sat(a, b) - b in the future.

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

show more ...

Reapply [IRBuilder] Always respect inserter/folder

Some IRBuilder methods that were originally defined on
IRBuilderBase do not respect custom IRBuilder inserters/folders,
because those were not acce

Reapply [IRBuilder] Always respect inserter/folder

Some IRBuilder methods that were originally defined on
IRBuilderBase do not respect custom IRBuilder inserters/folders,
because those were not accessible prior to D73835. Fix this by
making use of existing (and now accessible) IRBuilder methods,
which will handle inserters/folders correctly.

There are some changes in OpenMP and Instrumentation tests, where
bitcasts now get constant folded. I've also highlighted one
InstCombine test which now finishes in two rather than three
iterations, thanks to new instructions being inserted into the
worklist.

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

show more ...

Revert "[IRBuilder] Always respect inserter/folder"

This reverts commit f12fb2d99b8dd0dbef1c79f1d401200150f2d0bd.

I missed some changes in instrumentation test cases.