[InstCombine] Simplify `(X / C0) * C1 + (X % C0) * C2` to `(X / C0) * (C1 - C2 * C0) + X * C2` (#76285)

Since `DivRemPairPass` runs after `ReassociatePass` in the optimization
pipeline, I decided t

[InstCombine] Simplify `(X / C0) * C1 + (X % C0) * C2` to `(X / C0) * (C1 - C2 * C0) + X * C2` (#76285)

Since `DivRemPairPass` runs after `ReassociatePass` in the optimization
pipeline, I decided to do this simplification in `InstCombine`.

Alive2: https://alive2.llvm.org/ce/z/Jgsiqf
Fixes #76128.

show more ...

[InstCombine] Regard zext nneg as sext when folding add(zext neg(add)) (#88887)

fixes #88348
proof:
https://alive2.llvm.org/ce/z/fJnM7t
test will be added later

---------

Signed-off-by: Zel

[InstCombine] Regard zext nneg as sext when folding add(zext neg(add)) (#88887)

fixes #88348
proof:
https://alive2.llvm.org/ce/z/fJnM7t
test will be added later

---------

Signed-off-by: ZelinMa557 <3388706467@qq.com>

show more ...

[IR][PatternMatch] Only accept poison in getSplatValue() (#89159)

In #88217 a large set of matchers was changed to only accept poison
values in splats, but not undef values. This is because we now

[IR][PatternMatch] Only accept poison in getSplatValue() (#89159)

In #88217 a large set of matchers was changed to only accept poison
values in splats, but not undef values. This is because we now use
poison for non-demanded vector elements, and allowing undef can cause
correctness issues.

This patch covers the remaining matchers by changing the AllowUndef
parameter of getSplatValue() to AllowPoison instead. We also carry out
corresponding renames in matchers.

As a followup, we may want to change the default for things like m_APInt
to m_APIntAllowPoison (as this is much less risky when only allowing
poison), but this change doesn't do that.

There is one caveat here: We have a single place
(X86FixupVectorConstants) which does require handling of vector splats
with undefs. This is because this works on backend constant pool
entries, which currently still use undef instead of poison for
non-demanded elements (because SDAG as a whole does not have an explicit
poison representation). As it's just the single use, I've open-coded a
getSplatValueAllowUndef() helper there, to discourage use in any other
places.

show more ...

[InstCombine] Don't use dominating conditions to transform sub into xor. (#88566)

Other passes are unable to reverse this transform if we use dominating
conditions.

Fixes #88239.

[ValueTracking] Restore isKnownNonZero parameter order. (#88873)

Prior to #85863, the required parameters of llvm::isKnownNonZero were
Value and DataLayout. After, they are Value, Depth, and Simpli

[ValueTracking] Restore isKnownNonZero parameter order. (#88873)

Prior to #85863, the required parameters of llvm::isKnownNonZero were
Value and DataLayout. After, they are Value, Depth, and SimplifyQuery,
where SimplifyQuery is implicitly constructible from DataLayout. The
change to move Depth before SimplifyQuery needed callers to be updated
unnecessarily, and as commented in #85863, we actually want Depth to be
after SimplifyQuery anyway so that it can be defaulted and the caller
does not need to specify it.

show more ...

[ValueTracking] Convert `isKnownNonZero` to use SimplifyQuery (#85863)

This patch converts `isKnownNonZero` to use SimplifyQuery. Then we can
use the context information from `DomCondCache`.

Fix

[ValueTracking] Convert `isKnownNonZero` to use SimplifyQuery (#85863)

This patch converts `isKnownNonZero` to use SimplifyQuery. Then we can
use the context information from `DomCondCache`.

Fixes https://github.com/llvm/llvm-project/issues/85823.
Alive2: https://alive2.llvm.org/ce/z/QUvHVj

show more ...

[LLVM] Remove nuw neg (#86295)

This patch removes APIs that creating NUW neg. It is a trivial case
because `sub nuw 0, X` always gets simplified into zero.
I believe there is no optimization oppor

[LLVM] Remove nuw neg (#86295)

This patch removes APIs that creating NUW neg. It is a trivial case
because `sub nuw 0, X` always gets simplified into zero.
I believe there is no optimization opportunities in the real-world
applications that we can take advantage of the nuw flag.

Motivated by
https://github.com/llvm/llvm-project/pull/84792#discussion_r1524891134.

Compile-time improvement:
https://llvm-compile-time-tracker.com/compare.php?from=d1f182c895728d89c5c3d198b133e212a5d9d4a3&to=da7b7478b7cbb32c09d760f6b8d0e67901e0d533&stat=instructions:u

show more ...

[InstCombine] integrate `N{U,S}WAddLike` into existing folds

Just went a quick replacement of `N{U,S}WAdd` with the `Like` variant
that old matches `or disjoint`

Closes #86082

[InstCombine] Add folds for `(fp_binop ({s|u}itofp x), ({s|u}itofp y))`

The full fold is one of the following:
1) `(fp_binop ({s|u}itofp x), ({s|u}itofp y))`
-> `({s|u}itofp (int_binop x, y))`
2

[InstCombine] Add folds for `(fp_binop ({s|u}itofp x), ({s|u}itofp y))`

The full fold is one of the following:
1) `(fp_binop ({s|u}itofp x), ({s|u}itofp y))`
-> `({s|u}itofp (int_binop x, y))`
2) `(fp_binop ({s|u}itofp x), FpC)`
-> `({s|u}itofp (int_binop x, (fpto{s|u}i FpC)))`

And support the following binops:
`fmul` -> `mul`
`fadd` -> `add`
`fsub` -> `sub`

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

The proofs timeout, so they must be reproduced locally.

Closes #82555

show more ...

[InstCombine] Move folding `(add (sitofp x), (sitofp y))` impl to InstructionCombiner; NFC

[InstCombine] Fold (sub (xor X, (sext C)), (sext C)) => (select C (neg X), X) (#79417)

This is useful when computing absdiff.

Correctness prove: https://alive2.llvm.org/ce/z/eMbxps,
https://aliv

[InstCombine] Fold (sub (xor X, (sext C)), (sext C)) => (select C (neg X), X) (#79417)

This is useful when computing absdiff.

Correctness prove: https://alive2.llvm.org/ce/z/eMbxps,
https://alive2.llvm.org/ce/z/SNCWJe.

---------

Co-authored-by: Yingwei Zheng <dtcxzyw@qq.com>

show more ...

[ValueTracking][NFC] Pass `SimplifyQuery` to `computeKnownFPClass` family (#80657)

This patch refactors the interface of the `computeKnownFPClass` family
to pass `SimplifyQuery` directly.
The moti

[ValueTracking][NFC] Pass `SimplifyQuery` to `computeKnownFPClass` family (#80657)

This patch refactors the interface of the `computeKnownFPClass` family
to pass `SimplifyQuery` directly.
The motivation of this patch is to compute known fpclass with
`DomConditionCache`, which was introduced by
https://github.com/llvm/llvm-project/pull/73662. With
`DomConditionCache`, we can do more optimization with context-sensitive
information.

Example (extracted from
[fmt/format.h](https://github.com/fmtlib/fmt/blob/e17bc67547a66cdd378ca6a90c56b865d30d6168/include/fmt/format.h#L3555-L3566)):
```
define float @test(float %x, i1 %cond) {
%i32 = bitcast float %x to i32
%cmp = icmp slt i32 %i32, 0
br i1 %cmp, label %if.then1, label %if.else

if.then1:
%fneg = fneg float %x
br label %if.end

if.else:
br i1 %cond, label %if.then2, label %if.end

if.then2:
br label %if.end

if.end:
%value = phi float [ %fneg, %if.then1 ], [ %x, %if.then2 ], [ %x, %if.else ]
%ret = call float @llvm.fabs.f32(float %value)
ret float %ret
}
```
We can prove the signbit of `%value` is always zero. Then the fabs can
be eliminated.

show more ...

[InstCombine] Add folds for `(add/sub/disjoint_or/icmp C, (ctpop (not x)))`

`(ctpop (not x))` <-> `(sub nuw nsw BitWidth(x), (ctpop x))`. The
`sub` expression can sometimes be constant folded depend

[InstCombine] Add folds for `(add/sub/disjoint_or/icmp C, (ctpop (not x)))`

`(ctpop (not x))` <-> `(sub nuw nsw BitWidth(x), (ctpop x))`. The
`sub` expression can sometimes be constant folded depending on the use
case of `(ctpop (not x))`.

This patch adds fold for the following cases:

`(add/sub/disjoint_or C, (ctpop (not x))`
-> `(add/sub/disjoint_or C', (ctpop x))`
`(cmp pred C, (ctpop (not x))`
-> `(cmp swapped_pred C', (ctpop x))`

Where `C'` depends on how we constant fold `C` with `BitWidth(x)` for
the given opcode.

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

Closes #77859

show more ...

[InstCombine] Fold the `log2_ceil` idiom (#76661)

This patch folds the `log2_ceil` idiom:
```
(BW - ctlz(A)) + (is_power2(A) ? 0 : 1) ->
zext(ctpop(A) >u/!= 1) + (ctlz(A, true) ^ (BW - 1)) (canon

[InstCombine] Fold the `log2_ceil` idiom (#76661)

This patch folds the `log2_ceil` idiom:
```
(BW - ctlz(A)) + (is_power2(A) ? 0 : 1) ->
zext(ctpop(A) >u/!= 1) + (ctlz(A, true) ^ (BW - 1)) (canonical form) ->
BW - ctlz(A - 1, false)
```

Alive2: https://alive2.llvm.org/ce/z/6mSbdi

show more ...

[InstCombine] Refactor folding of commutative binops over select/phi/minmax (#76692)

This patch cleans up the duplicate code for folding commutative binops
over `select/phi/minmax`.

Related comm

[InstCombine] Refactor folding of commutative binops over select/phi/minmax (#76692)

This patch cleans up the duplicate code for folding commutative binops
over `select/phi/minmax`.

Related commits:
+ select support:
https://github.com/llvm/llvm-project/commit/88cc35b27e6c7966ab2463fa06d3dd970e88df64
+ phi support:
https://github.com/llvm/llvm-project/commit/8674a023bcacb677ce48b8831e2ae35b5aa2d8ef
+ minmax support:
https://github.com/llvm/llvm-project/commit/624973806c5644ccfa84805319b5852edb68d48d

show more ...

[InstCombine] Use ConstantInt::getSigned to sign extend -2 for large types. (#76464)

Using ContantInt::get will zero extend.

Fixes #76441

[InstCombine] Explicitly set disjoint flag when converting xor to or. (#74229)

[InstCombine] Use disjoint flag in add of or fold

Use disjoint instead of haveNoCommonBitsSet(), which is slightly
stronger in case the information used to infer disjoint has been
lost.

Introduce t

[InstCombine] Use disjoint flag in add of or fold

Use disjoint instead of haveNoCommonBitsSet(), which is slightly
stronger in case the information used to infer disjoint has been
lost.

Introduce the m_DisjointOr() matcher to make handling cases like
this cleaner.

show more ...

[InstCombine] Add one-use limitation to box multiply fold (#72876)

Check the operands of I are used in no more than one place, which can
not be deleted, cause a mul instruction has far more weight

[InstCombine] Add one-use limitation to box multiply fold (#72876)

Check the operands of I are used in no more than one place, which can
not be deleted, cause a mul instruction has far more weight than add and
shl instruction in IR, thus this method cannot achieve the goal of
simplifying instructions, just return null.

show more ...

[InstCombine] Handle equality comparison when flooring by constant 2

Support `icmp eq` when reducing signed divisions by power of 2 to
arithmetic shift right, as `icmp ugt` may have been canonicaliz

[InstCombine] Handle equality comparison when flooring by constant 2

Support `icmp eq` when reducing signed divisions by power of 2 to
arithmetic shift right, as `icmp ugt` may have been canonicalized
into `icmp eq` by the time additions are folded into `ashr`.

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

Proof: https://alive2.llvm.org/ce/z/8-eUdb.

show more ...

[InstCombine] Set disjoint flag when turning Add into Or. (#72702)

The disjoint flag was recently added to IR in #72583

[InstCombine] Add transform for `~X + ~Y)` -> `-2 - Y - X`

Proof: https://alive2.llvm.org/ce/z/36FySK

Closes #66787.

[InstCombine] Replace `isFreeToInvert` + `CreateNot` with `getFreelyInverted`

This is nearly an NFC, the only change is potentially to order that
values are created/names.

Otherwise it is a slight

[InstCombine] Replace `isFreeToInvert` + `CreateNot` with `getFreelyInverted`

This is nearly an NFC, the only change is potentially to order that
values are created/names.

Otherwise it is a slight speed boost/simplification to avoid having to
go through the `getFreelyInverted` recursive logic twice to simplify
the extra `not` op.

show more ...

[InstCombine] Make `isFreeToInvert` check recursively.

Some Instructions (select/min/max) are inverted by just inverting the
operands. So the answer of whether they are free to invert is really
just

[InstCombine] Make `isFreeToInvert` check recursively.

Some Instructions (select/min/max) are inverted by just inverting the
operands. So the answer of whether they are free to invert is really
just whether the operands are free to invert.

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

show more ...

[InstCombine] Add folds for `(X + Y) - (W + Z)`

If `Y` and `Z` are constant then we can simplify to `(X - W) + (Y -
Z)`. If `Y == Z` we can fold to `X - W`.

Note these transform exist outside of In

[InstCombine] Add folds for `(X + Y) - (W + Z)`

If `Y` and `Z` are constant then we can simplify to `(X - W) + (Y -
Z)`. If `Y == Z` we can fold to `X - W`.

Note these transform exist outside of InstCombine. The purpose of this
commit is primarily to make it so that folds can generate these
simplifiable patterns without having to worry about creating an inf
loop.

show more ...