[InstSimpify] Simplifying `(xor (sub C_Mask, X), C_Mask)` -> `X` (#122552)

- **[InstSimpify] Add tests for simplifying `(xor (sub C_Mask, X),
C_Mask)`; NFC**
- **[InstSimpify] Simplifying `(xor (s

[InstSimpify] Simplifying `(xor (sub C_Mask, X), C_Mask)` -> `X` (#122552)

- **[InstSimpify] Add tests for simplifying `(xor (sub C_Mask, X),
C_Mask)`; NFC**
- **[InstSimpify] Simplifying `(xor (sub C_Mask, X), C_Mask)` -> `X`**

Helps address regressions with folding `clz(Pow2)`.

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

show more ...

[InstSimplify] Use multi-op replacement when simplify `select` (#121708)

- **[InstSimplify] Refactor `simplifyWithOpsReplaced` to allow multiple
replacements; NFC**
- **[InstSimplify] Use multi-op

[InstSimplify] Use multi-op replacement when simplify `select` (#121708)

- **[InstSimplify] Refactor `simplifyWithOpsReplaced` to allow multiple
replacements; NFC**
- **[InstSimplify] Use multi-op replacement when simplify `select`**

In the case of `select X | Y == 0 :...` or `select X & Y == -1 : ...`
we can do more simplifications by trying to replace both `X` and `Y`
with the respective constant at once.

Handles some cases for https://github.com/llvm/llvm-project/pull/121672
more generically.

show more ...

[InstSimplify] Simplify both operands of select before comparing (#121753)

In the simplifySelectWithEquivalence fold, simplify both operands before
comparing them, instead of comparing one simplifi

[InstSimplify] Simplify both operands of select before comparing (#121753)

In the simplifySelectWithEquivalence fold, simplify both operands before
comparing them, instead of comparing one simplified operand with a
non-simplified operand. This is slightly more powerful.

show more ...

[InstCombine] Fold `A == MIN_INT ? B != MIN_INT : A < B` to `A < B` (#120177)

This PR folds:
`A == MIN_INT ? B != MIN_INT : A < B` to `A < B`
`A == MAX_INT ? B != MAX_INT : A > B` to `A > B`

[InstCombine] Fold `A == MIN_INT ? B != MIN_INT : A < B` to `A < B` (#120177)

This PR folds:
`A == MIN_INT ? B != MIN_INT : A < B` to `A < B`
`A == MAX_INT ? B != MAX_INT : A > B` to `A > B`

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

This helps in optimizing comparison of optional unsigned non-zero types
in https://github.com/rust-lang/rust/issues/49892.

Rust compiler's current output: https://rust.godbolt.org/z/9fxfq3Gn8

show more ...

[InstSimplify] Treat float binop with identity as refining (#120098)

If x is NaN, then fmul (x, 1) may produce a different NaN value.

Our float semantics explicitly permit folding fmul (x, 1) to

[InstSimplify] Treat float binop with identity as refining (#120098)

If x is NaN, then fmul (x, 1) may produce a different NaN value.

Our float semantics explicitly permit folding fmul (x, 1) to x, but we
can't do this when we're replacing a select input, as selects are
supposed to preserve the exact bitwise value.

Fixes
https://github.com/llvm/llvm-project/pull/115152#issuecomment-2545773114.

show more ...

PatternMatch: migrate to CmpPredicate (#118534)

With the introduction of CmpPredicate in 51a895a (IR: introduce struct
with CmpInst::Predicate and samesign), PatternMatch is one of the first
key p

PatternMatch: migrate to CmpPredicate (#118534)

With the introduction of CmpPredicate in 51a895a (IR: introduce struct
with CmpInst::Predicate and samesign), PatternMatch is one of the first
key pieces of infrastructure that must be updated to match a CmpInst
respecting samesign information. Implement this change to Cmp-matchers.

This is a preparatory step in migrating the codebase over to
CmpPredicate. Since we no functional changes are desired at this stage,
we have chosen not to migrate CmpPredicate::operator==(CmpPredicate)
calls to use CmpPredicate::getMatching(), as that would have visible
impact on tests that are not yet written: instead, we call
CmpPredicate::operator==(Predicate), preserving the old behavior, while
also inserting a few FIXME comments for follow-ups.

show more ...

[InstSimplify] Remove foldSelectWithBinaryOp (#118913)

As mentioned in https://github.com/llvm/llvm-project/issues/118815, the
purpose of this simplification is superseded by
https://github.com/ll

[InstSimplify] Remove foldSelectWithBinaryOp (#118913)

As mentioned in https://github.com/llvm/llvm-project/issues/118815, the
purpose of this simplification is superseded by
https://github.com/llvm/llvm-project/pull/76621, so we should have it
deleted.

show more ...

IR: introduce struct with CmpInst::Predicate and samesign (#116867)

Introduce llvm::CmpPredicate, an abstraction over a floating-point
predicate, and a pack of an integer predicate with samesign in

IR: introduce struct with CmpInst::Predicate and samesign (#116867)

Introduce llvm::CmpPredicate, an abstraction over a floating-point
predicate, and a pack of an integer predicate with samesign information,
in order to ease extending large portions of the codebase that take a
CmpInst::Predicate to respect the samesign flag.

We have chosen to demonstrate the utility of this new abstraction by
migrating parts of ValueTracking, InstructionSimplify, and InstCombine
from CmpInst::Predicate to llvm::CmpPredicate. There should be no
functional changes, as we don't perform any extra optimizations with
samesign in this patch, or use CmpPredicate::getMatching.

The design approach taken by this patch allows for unaudited callers of
APIs that take a llvm::CmpPredicate to silently drop the samesign
information; it does not pose a correctness issue, and allows us to
migrate the codebase piece-wise.

show more ...

[InstSimplify] Generalize simplification of icmps with monotonic operands (#69471)

InstSimplify currently folds patterns like `(x | y) uge x` and `(x & y)
ule x` to true. However, it cannot handle

[InstSimplify] Generalize simplification of icmps with monotonic operands (#69471)

InstSimplify currently folds patterns like `(x | y) uge x` and `(x & y)
ule x` to true. However, it cannot handle combinations of such
situations, such as `(x | y) uge (x & z)` etc.

To support this, recursively collect operands of monotonic instructions
(that preserve either a greater-or-equal or less-or-equal relationship)
and then check whether any of them match.

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

show more ...

[InstSimplify] Generalize `simplifyAndOrOfFCmps` to handle fabs (#116590)

This patch generalizes https://github.com/llvm/llvm-project/issues/81027
to handle pattern `and/or (fcmp ord/uno X, 0), (fc

[InstSimplify] Generalize `simplifyAndOrOfFCmps` to handle fabs (#116590)

This patch generalizes https://github.com/llvm/llvm-project/issues/81027
to handle pattern `and/or (fcmp ord/uno X, 0), (fcmp pred fabs(X), Y)`.
Alive2: https://alive2.llvm.org/ce/z/tsgUrz
The correctness is straightforward because `fcmp ord/uno X, 0.0` is
equivalent to `fcmp ord/uno fabs(X), 0.0`. We may generalize it to
handle fneg as well.

Address comment
https://github.com/llvm/llvm-project/pull/116065#pullrequestreview-2434796846

show more ...

InstSimplify: support floating-point equivalences (#115152)

Since cd16b07 (IR: introduce CmpInst::isEquivalence), there is now an
isEquivalence routine in CmpInst that we can use to determine
equi

InstSimplify: support floating-point equivalences (#115152)

Since cd16b07 (IR: introduce CmpInst::isEquivalence), there is now an
isEquivalence routine in CmpInst that we can use to determine
equivalence in simplifySelectWithICmpEq. Implement this, extending the
code from integer-equalities to integer and floating-point equivalences.

show more ...

[InstSimplify] Correctly handle comparison with zero-size allocs (#115728)

InstSimplify currently folds alloc1 == alloc2 to false, even if one of
them is a zero-size allocation. A zero-size allocat

[InstSimplify] Correctly handle comparison with zero-size allocs (#115728)

InstSimplify currently folds alloc1 == alloc2 to false, even if one of
them is a zero-size allocation. A zero-size allocation may have the same
address as another allocation.

This also disables the fold for the case where we're comparing a
zero-size alloc with the middle of another allocation. It's possible
that this case is legal to fold depending on our precise zero-size
allocation semantics, but LangRef currently doesn't specify this either
way, so we shouldn't make assumptions here.

show more ...

[InstSimplify] Fix incorrect poison propagation when folding phi (#96631)

We can only replace phi(X, undef) with X, if X is known not to be
poison. Otherwise, the result may be more poisonous on th

[InstSimplify] Fix incorrect poison propagation when folding phi (#96631)

We can only replace phi(X, undef) with X, if X is known not to be
poison. Otherwise, the result may be more poisonous on the undef branch.

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

show more ...

[InstSimplify][InstCombine][ConstantFold] Move vector div/rem by zero fold to InstCombine (#114280)

Previously we fold `div/rem X, C` into `poison` if any element of the
constant divisor `C` is zer

[InstSimplify][InstCombine][ConstantFold] Move vector div/rem by zero fold to InstCombine (#114280)

Previously we fold `div/rem X, C` into `poison` if any element of the
constant divisor `C` is zero or undef. However, it is incorrect when
threading udiv over an vector select:
https://alive2.llvm.org/ce/z/3Ninx5
```
define <2 x i32> @vec_select_udiv_poison(<2 x i1> %x) {
%sel = select <2 x i1> %x, <2 x i32> <i32 -1, i32 -1>, <2 x i32> <i32 0, i32 1>
%div = udiv <2 x i32> <i32 42, i32 -7>, %sel
ret <2 x i32> %div
}
```
In this case, `threadBinOpOverSelect` folds `udiv <i32 42, i32 -7>, <i32
-1, i32 -1>` and `udiv <i32 42, i32 -7>, <i32 0, i32 1>` into
`zeroinitializer` and `poison`, respectively. One solution is to
introduce a new flag indicating that we are threading over a vector
select. But it requires to modify both `InstSimplify` and
`ConstantFold`.

However, this optimization doesn't provide benefits to real-world
programs:

https://dtcxzyw.github.io/llvm-opt-benchmark/coverage/data/zyw/opt-ci/actions-runner/_work/llvm-opt-benchmark/llvm-opt-benchmark/llvm/llvm-project/llvm/lib/IR/ConstantFold.cpp.html#L908

https://dtcxzyw.github.io/llvm-opt-benchmark/coverage/data/zyw/opt-ci/actions-runner/_work/llvm-opt-benchmark/llvm-opt-benchmark/llvm/llvm-project/llvm/lib/Analysis/InstructionSimplify.cpp.html#L1107

This patch moves the fold into InstCombine to avoid breaking numerous
existing tests.

Fixes #114191 and #113866 (only poison-safety issue).

show more ...

ValueTracking: introduce llvm::isNotCrossLaneOperation (#112011)

Factor out and unify common code from InstSimplify and InstCombine that
partially guard against cross-lane vector operations into
l

ValueTracking: introduce llvm::isNotCrossLaneOperation (#112011)

Factor out and unify common code from InstSimplify and InstCombine that
partially guard against cross-lane vector operations into
llvm::isNotCrossLaneOperation in ValueTracking.

Alive2 proofs for changed tests: https://alive2.llvm.org/ce/z/68H4ka

show more ...

[CmpInstAnalysis] Return decomposed bit test as struct (NFC) (#109819)

decomposeBitTestICmp() currently returns the result via two out
parameters plus an in-place modification of Pred. This changes

[CmpInstAnalysis] Return decomposed bit test as struct (NFC) (#109819)

decomposeBitTestICmp() currently returns the result via two out
parameters plus an in-place modification of Pred. This changes it to
return an optional struct instead.

The motivation here is twofold. First, I'd like to extend this code to
handle cases where the comparison is against a value other than zero,
which would mean yet another out parameter. Second, while doing that I
was badly bitten by the in-place modification, so I'd like to get rid of
it.

show more ...

[InstSimplify] Simplify `uadd.sat(X, Y) u>= X + Y` and `usub.sat(X, Y) u<= X, Y` (#104698)

These patterns are found in harfbuzz/typst.

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

[NFC] Cleanup in ADT and Analysis headers. (#104484)

Remove unused directly includes and forward declarations in ADT and
Analysis headers.

[InstSimplify] Fold (insertelement Splat(C), C, X) -> Splat(C) (#102315)

The index doesn't matter here.

[PatternMatch] Use `m_SpecificCmp` matchers. NFC. (#100878)

Compile-time improvement:
http://llvm-compile-time-tracker.com/compare.php?from=13996378d81c8fa9a364aeaafd7382abbc1db83a&to=861ffa4ec5f7b

[PatternMatch] Use `m_SpecificCmp` matchers. NFC. (#100878)

Compile-time improvement:
http://llvm-compile-time-tracker.com/compare.php?from=13996378d81c8fa9a364aeaafd7382abbc1db83a&to=861ffa4ec5f7bde5a194a7715593a1b5359eb581&stat=instructions:u
baseline: 803eaf29267c6aae9162d1a83a4a2ae508b440d3
```
Top 5 improvements:
stockfish/movegen.ll 2541620819 2538599412 -0.12%
minetest/profiler.cpp.ll 431724935 431246500 -0.11%
abc/luckySwap.c.ll 581173720 580581935 -0.10%
abc/kitTruth.c.ll 2521936288 2519445570 -0.10%
abc/extraUtilTruth.c.ll 1216674614 1215495502 -0.10%
Top 5 regressions:
openssl/libcrypto-shlib-sm4.ll 1155054721 1155943201 +0.08%
openssl/libcrypto-lib-sm4.ll 1155054838 1155943063 +0.08%
spike/vsm4r_vv.ll 1296430080 1297039258 +0.05%
spike/vsm4r_vs.ll 1312496906 1313093460 +0.05%
nuttx/lib_rand48.c.ll 126201233 126246692 +0.04%
Overall: -0.02112308%
```

show more ...

[InstSimplify] Fix simplifyAndOrWithICmpEq with undef refinement (#98898)

The final case in Simplify (where Res == Absorber and the predicate is
inverted) is not generally safe when the simplificat

[InstSimplify] Fix simplifyAndOrWithICmpEq with undef refinement (#98898)

The final case in Simplify (where Res == Absorber and the predicate is
inverted) is not generally safe when the simplification is a refinement.
In particular, we may simplify assuming a specific value for undef, but
then chose a different one later.

However, it *is* safe to refine poison in this context, unlike in the
equivalent select folds. This is the reason why this fold did not use
AllowRefinement=false in the first place, and using that option would
introduce a lot of test regressions.

This patch takes the middle path of disabling undef refinements in
particular using the getWithoutUndef() SimplifyQuery option. However,
this option doesn't actually work in this case, because the problematic
fold is inside constant folding, and we currently don't propagate this
option all the way from InstSimplify over ConstantFolding to
ConstantFold. Work around this by explicitly checking for undef operands
in simplifyWithOpReplaced().

Finally, make sure that places where AllowRefinement=false also use
Q.getWithoutUndef(). I don't have a specific test case for this (the
original one does not work because we don't simplify selects with
constant condition in this mode in the first place) but this seems like
the correct thing to do to be conservative.

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

show more ...

[InstSimplify] Fold ptrtoint(ptradd(P,X-ptrtoint(P))) to X (#98649)

This is a special case of the general ptrtoint(gep) to add(ptrtoint)
transform that is particularly profitable, as everything fol

[InstSimplify] Fold ptrtoint(ptradd(P,X-ptrtoint(P))) to X (#98649)

This is a special case of the general ptrtoint(gep) to add(ptrtoint)
transform that is particularly profitable, as everything folds away.

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

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

show more ...

[InstSimplify] Only handle canonical forms in `simplifyAndOrOfFCmps`. NFC. (#98136)

This patch avoids calling `isKnownNeverNaN` in `simplifyAndOrOfFCmps`
since `fcmp ord/uno X, NNAN` will be canoni

[InstSimplify] Only handle canonical forms in `simplifyAndOrOfFCmps`. NFC. (#98136)

This patch avoids calling `isKnownNeverNaN` in `simplifyAndOrOfFCmps`
since `fcmp ord/uno X, NNAN` will be canonicalized into `fcmp ord/uno X,
0.0` in InstCombine.

show more ...

[InstSimplify] fold uno/ord comparison if fpclass is always NaN (#97763)

In InstSimplify we already fold `fcmp ord/uno` to a constant when both
operands are known to be non-NaN. This change slightl

[InstSimplify] fold uno/ord comparison if fpclass is always NaN (#97763)

In InstSimplify we already fold `fcmp ord/uno` to a constant when both
operands are known to be non-NaN. This change slightly generalizes this
to also handle the case where either of the operands is known to always
be NaN.

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

show more ...

[InstSimplify] Add simplification for `({u,s}rem (mul {nuw,nsw} X, C1), C0)`

We can simplify these to `0` if `C1 % C0 == 0`

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

Closes #97037