| Age | Commit message (Collapse) | Author |
|---|
|
(#143471)
When folding `X Pred C2 ? X BOp C1 : C2 BOp C1` to `min/max(X, C2) BOp
C1`, if NUW/NSW flags are present on `X BOp C1` and could be safely
applied to `C2 BOp C1`, then they may be added on the BOp after the fold
is complete. https://alive2.llvm.org/ce/z/n_3aNJ
Preserving these flags can allow subsequent transforms to re-order the
min/max and BOp, which in the case of NVPTX would allow for some
potential future transformations which would improve
instruction-selection.
|
|
(#143445)
|
|
Add the following folds for integer min max folding in InstCombine:
- (X > Y) ? X : (Y - 1) ==> MIN(X, Y - 1)
- (X < Y) ? X : (Y + 1) ==> MAX(X, Y + 1)
These are safe when overflow corresponding to the sign of the comparison
is poison. (proof https://alive2.llvm.org/ce/z/oj5iiI).
The most common of these patterns is likely the minimum case which
occurs in some internal library code when clamping an integer index to a
range (The maximum cases are included for completeness). Here is a
simplified example:
int clampToWidth(int idx, int width) {
if (idx >= width)
return width - 1;
return idx;
}
https://cuda.godbolt.org/z/nhPzWrc3W
|
|
Extend folding for `X Pred C2 ? X BOp C1 : C2 BOp C1` to `min/max(X, C2)
BOp C1` to allow min and max as `BOp`. This ensures a constant clamping
pattern is folded into a pair of min/max instructions. Here is a
simplified example of a case where this folding is not occurring
currently.
int clampToU8(int v) {
if (v < 0) return 0;
if (v > 255) return 255;
return v;
}
https://godbolt.org/z/78jhKPWbv
Generic proof: https://alive2.llvm.org/ce/z/cdpLYy
|
|
Before this patch, InstCombine hung because it replaced a value with a
more complex one:
```
%sel = select i1 %cmp, i32 %smax, i32 0 ->
%sel = select i1 %cmp, i32 %masked, i32 0 ->
%sel = select i1 %cmp, i32 %smax, i32 0 ->
...
```
This patch makes this replacement more conservative. It only performs
the replacement iff the new value is one of the operands of the original
value.
Closes https://github.com/llvm/llvm-project/issues/142405.
|
|
Having a finite Depth (or recursion limit) for computeKnownBits is very
limiting, but is currently a load-bearing necessity, as all KnownBits
are recomputed on each call and there is no caching. As a prerequisite
for an effort to remove the recursion limit altogether, either using a
clever caching technique, or writing a easily-invalidable KnownBits
analysis, make the Depth argument in APIs in ValueTracking uniformly the
last argument with a default value. This would aid in removing the
argument when the time comes, as many callers that currently pass 0
explicitly are now updated to omit the argument altogether.
|
|
Previously,
https://github.com/llvm/llvm-project/commit/3d6b53980ce4ee855484fc8ae6ac3f99c85e48c3
propagates FMF from fcmp to avoid performance regressions. With the help
of https://github.com/llvm/llvm-project/pull/139861,
https://github.com/llvm/llvm-project/pull/141015, and
https://github.com/llvm/llvm-project/pull/141914, we can still convert
SPF into fabs/minnum/maxnum intrinsics even if some flags are missing.
This patch propagates FMF from select to address the long-standing
issue.
Closes https://github.com/llvm/llvm-project/issues/140994.
|
|
Alive2: https://alive2.llvm.org/ce/z/dCZBB_
Fix remaining regressions caused by https://github.com/llvm/llvm-project/pull/141010.
|
|
more cases (#141015)
This patch was originally part of
https://github.com/llvm/llvm-project/pull/139861. It generalizes
`ignoreSignBitOfZero/NaN` to handle more instructions/intrinsics.
BTW, I find it mitigates performance regressions caused by
https://github.com/llvm/llvm-project/pull/141010 (IR diff
https://github.com/dtcxzyw/llvm-opt-benchmark/pull/2365/files). We don't
need to propagate FMF from fcmp into select, since we can infer demanded
properties from the user of select.
|
|
zero/NaN (#139861)
When the only user of select is a fcmp or a fp operation with nnan/nsz,
the sign bit of zero/NaN can be ignored.
Alive2: https://alive2.llvm.org/ce/z/ZcxeIv
Compile-time impact:
https://llvm-compile-time-tracker.com/compare.php?from=7add1bcd02b1f72d580bb2e64a1fe4a8bdc085d9&to=cb419c7cbddce778673f3d4b414ed9b8064b8d6e&stat=instructions:u
Closes https://github.com/llvm/llvm-project/issues/133367.
|
|
Proof: https://alive2.llvm.org/ce/z/nCrvfr
Closes https://github.com/llvm/llvm-project/issues/136430
|
|
As per the LangRef and IEEE 754-2008 standard, the sign bit of NaN is
preserved if there is no floating-point operation being performed.
See also
https://github.com/llvm/llvm-project/commit/862e35e25a68502433da0a8d0819448ff5745339
for reference.
Alive2: https://alive2.llvm.org/ce/z/QYtEGj
Closes https://github.com/llvm/llvm-project/issues/136646
|
|
foldSelectICmpAnd. (#131902)
The commit that was removed from
https://github.com/llvm/llvm-project/pull/127905 due to the conflict
with https://github.com/llvm/llvm-project/pull/128741.
The use of common code results in that the foldSelectICmpAndBinOp also
use knownbits in the same way as was added for foldSelectICmpAnd in
https://github.com/llvm/llvm-project/pull/128741.
proof for the use of knowbits in foldSelectICmpAndBinOp:
https://alive2.llvm.org/ce/z/RYXr_k
|
|
proof: https://alive2.llvm.org/ce/z/Ey6BoT
|
|
Make use of known bits when trying to decompose a select/icmp bittest and folding it into an and. This means we can fold when additional information, for instance via a range attribute or metadata, allows us to conclude that the resulting mask is in fact a power of two.
|
|
Proof: https://alive2.llvm.org/ce/z/mzL6W2
Closes https://github.com/llvm/llvm-project/issues/128441.
|
|
for `trunc nuw` saves a instruction and otherwise only other
instructions without the select, same behavior as for bit test before.
proof: https://alive2.llvm.org/ce/z/a6QmyV
|
|
Disable fold when it will result in more instructions.
|
|
It is always safe to add poison-generating flags for `BinOp Y,
Identity`.
Proof: https://alive2.llvm.org/ce/z/8BLEpq
and https://alive2.llvm.org/ce/z/584Bb4
Then we can propagate flags from one of the arms:
```
select Cond, Y, (BinOp flags Y, Z) ->
select Cond, (BinOp flags Y, Identity), (BinOp flags Y, Z) ->
BinOp flags Y, (select Cond, Identity, Z)
```
This patch is proposed to avoid information loss caused by
https://github.com/llvm/llvm-project/pull/127390.
|
|
For convenience this patch drops nsw for `sub`. It also allows this fold
with `ctlz_zero_undef`.
Alive2: https://alive2.llvm.org/ce/z/VmvqSt
|
|
This patch extends
https://github.com/llvm/llvm-project/commit/f6bb156fb10cd83953a34f75b78835cdf399ee8b
to handle minmax intrinsics.
Motivating case: https://alive2.llvm.org/ce/z/JFKbYn
Addresses a regression caused by
https://github.com/llvm/llvm-project/pull/121958.
It also works for `*.sat`. But no real-world benefit is observed.
|
|
Consider the following pattern:
```
%cmp = fcmp <pred> double %x, 0.000000e+00
%negX = fneg <fmf> double %x
%sel = select i1 %cmp, double %x, double %negX
```
We cannot propagate ninf from fneg to select since `%negX` may not be
chosen. Similarly, we cannot propagate nnan unless `%negX` is guaranteed
to be selected when `%x` is NaN.
This patch also propagates nnan/ninf from fcmp to avoid regression in
`PhaseOrdering/generate-fabs.ll`.
Alive2: https://alive2.llvm.org/ce/z/t6U-tA
Closes https://github.com/llvm/llvm-project/issues/121430 and
https://github.com/llvm/llvm-project/issues/113989.
|
|
Changes: There was a serious bug in the previous patch, leading to a
miscompile. See #122723 for the miscompile report from Alexander, and
the follow-up investigation by Nikita. The patch has since been
reworked, and now includes the testcase from the miscompile.
Follow up on 4a0d53a (PatternMatch: migrate to CmpPredicate) to get rid
of one of the FIXMEs it introduced by replacing a predicate comparison
with CmpPredicate::getMatching.
Co-authored-by: Nikita Popov <npopov@redhat.com>
|
|
Reverts llvm/llvm-project#122723 due to a miscompilation
See
https://github.com/llvm/llvm-project/pull/122723#issuecomment-2608777844
for details and the test case.
|
|
Follow up on 4a0d53a (PatternMatch: migrate to CmpPredicate) to get rid
of one of the FIXMEs it introduced by replacing a predicate comparison
with CmpPredicate::getMatching.
|
|
This fold matches complex patterns, for which we have no proof of
real-world relevance, and which does not actually handle the originally
motivating cases from https://github.com/llvm/llvm-project/issues/71792
either.
In https://github.com/llvm/llvm-project/pull/121708 and
https://github.com/llvm/llvm-project/pull/121753 we have handled some
simpler variants by extending existing folds.
I propose to remove this code until we have evidence that it is useful
for something.
|
|
ValueTracking. NFC. (#122064)
Needed by https://github.com/llvm/llvm-project/pull/121958.
|
|
Closes https://github.com/llvm/llvm-project/issues/121771.
|
|
Up to now, the only way to set specified FMF flags in IRBuilder is to
use `FastMathFlagGuard`. It makes the code ugly and hard to maintain.
This patch introduces a helper class `FMFSource` to replace the original
parameter `Instruction *FMFSource` in IRBuilder. To maximize the
compatibility, it accepts an instruction or a specified FMF.
This patch also removes the use of `FastMathFlagGuard` in some simple
cases.
Compile-time impact:
https://llvm-compile-time-tracker.com/compare.php?from=f87a9db8322643ccbc324e317a75b55903129b55&to=9397e712f6010be15ccf62f12740e9b4a67de2f4&stat=instructions%3Au
|
|
Close https://github.com/llvm/llvm-project/issues/121428
|
|
The fcmp + fadd + sel => fcmp + sel + fadd xfrm performs incorrect
transformation when select branch values are swapped. This change fixes
this.
|
|
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
|
|
(#120011)
This patch is proposed to reduce the number of selects with undefs
introduced by https://github.com/llvm/llvm-project/pull/119884.
|
|
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.
|
|
fmax/fmin (#117977)
Preserve `nnan` constraint only if present on both `fcmp` and `select`.
Alive2: https://alive2.llvm.org/ce/z/ZNDjzt
|
|
We had a separate fold that handled just the trivial case where we're
replacing exactly the argument of the select. Handle this in select
value equivalence by relaxing the infinite loop protection to allow a
replacement of a non-constant with a constant.
This also fixes https://github.com/llvm/llvm-project/issues/113301, as
the separate fold did not handle undef values correctly.
|
|
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.
|
|
(#116983)
See the following case:
```
define i1 @test_logical_and_icmp_samesign(i8 %x) {
%cmp1 = icmp ne i8 %x, 9
%cmp2 = icmp samesign ult i8 %x, 11
%and = select i1 %cmp1, i1 %cmp2, i1 false
ret i1 %and
}
```
Currently we cannot convert this logical and into a bitwise and due to
the `samesign` flag. But if `%cmp2` evaluates to `poison`, we can infer
that `%cmp1` is either `poison` or `true` (`samesign` violation
indicates that X is negative). Therefore, `%and` still evaluates to
`poison`.
This patch converts a logical and into a bitwise and iff TV is poison
implies that Cond is either poison or true. Likewise, we convert a
logical or into a bitwise or iff FV is poison implies that Cond is
either poison or false.
Note:
1. This logic is implemented in InstCombine. Not sure whether it is
profitable to move it into ValueTracking and call `impliesPoison(TV/FV,
Sel)` instead.
2. We only handle the case that `ValAssumedPoison` is `icmp samesign
pred X, C1` and `V` is `icmp pred X, C2`. There are no suitable variants
for `isImpliedCondition` to pass the fact that X is [non-]negative.
Alive2: https://alive2.llvm.org/ce/z/eorFfa
Motivation: fix [a major
regression](https://github.com/dtcxzyw/llvm-opt-benchmark/pull/1724#discussion_r1849663863)
to unblock https://github.com/llvm/llvm-project/pull/112742.
|
|
Closes https://github.com/llvm/llvm-project/issues/112076
|
|
Since cd16b07 (IR: introduce CmpInst::isEquivalence), there is now an
isEquivalence routine in CmpInst that we can use to determine
equivalence in foldSelectValueEquivalence. Implement this, extending it
to include floating-point equivalences as well.
|
|
Transform `fcmp + fadd + sel` into `fcmp + sel + fadd` which enables the
possibility of transforming `fcmp + sel` into `maxnum/minnum`
intrinsics.
Alive2 results:
https://alive2.llvm.org/ce/z/2cmimW
https://alive2.llvm.org/ce/z/Qh9ZJt
https://alive2.llvm.org/ce/z/vtLj3R
|
|
--> 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.
|
|
Relands #114356. Compared to the last version, this patch only merges
poison-generating/nsz flags from the select to fix LV regression in
`llvm/test/Transforms/PhaseOrdering/AArch64/predicated-reduction.ll`.
|
|
Reverts llvm/llvm-project#114356 because it caused test failures.
https://lab.llvm.org/buildbot/#/builders/190/builds/8601
https://luci-milo.appspot.com/ui/p/fuchsia/builders/toolchain.ci/clang-base-linux-x64/b8732549597609293617/overview
|
|
Closes https://github.com/llvm/llvm-project/issues/113423.
|
|
Add a helper for shared folds between logical and bitwise and/or
and move the and/or of icmp and fcmp folds in there. This makes
it easier to extend to more folds.
A possible extension would be to base the current and/or of icmp
reassociation logic on this helper, so that it for example also
applies to fcmp.
|
|
InstCombinerImpl::foldSelectInstWithICmp has some inlined code for
select-icmp-xor simplification, but this simplification is already done
by other code, via another path:
(X & Y) == 0 ? X : X ^ Y ->
((X & Y) == 0 ? 0 : Y) ^ X ->
(X & Y) ^ X ->
X & ~Y
Cover the cases that it claims to simplify, and demonstrate that
stripping it doesn't cause test changes.
|
|
Closes https://github.com/llvm/llvm-project/issues/112476.
|
|
Today, InstCombine can fold fcmp+select patterns to minnum/maxnum
intrinsics when the nnan and nsz flags are set. The ordering of the
operands in both the fcmp and select instructions is important for the
folding to occur.
maxnum patterns:
1. (a op b) ? a : b -> maxnum(a, b), where op is one of {ogt, oge}
2. (a op b) ? b : a -> maxnum(a, b), where op is one of {ule, ult}
The second pattern is supposed to make the order of the operands in the
select instruction irrelevant. However, the pattern matching code uses
the CmpInst::getInversePredicate method to invert the comparison
predicate. This method doesn't take into account the fast-math flags,
which can lead missing the folding opportunity.
The patch extends the pattern matching code to handle unordered fcmp
instructions. This allows the folding to occur even when the select
instruction has the operands in the inverse order.
New maxnum patterns:
1. (a op b) ? a : b -> maxnum(a, b), where op is one of {ugt, uge}
2. (a op b) ? b : a -> maxnum(a, b), where op is one of {ole, olt}
The same changes are applied to the minnum intrinsic.
|
|
foldSelectEquivalence currently doesn't support GVN-like replacements on
vector types. Put in the checks for potentially lane-crossing
operations, and lift the limitation.
|
