Skip to content

Simplification for (~a & b) && ~a #69050

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
k-arrows opened this issue Oct 14, 2023 · 1 comment · Fixed by #70335
Closed

Simplification for (~a & b) && ~a #69050

k-arrows opened this issue Oct 14, 2023 · 1 comment · Fixed by #70335
Assignees
@dtcxzyw
Labels
llvm:instcombine missed-optimization

Comments

@k-arrows
Copy link

GCC outputs the same sequence of instructions for the following two functions. Clang doesn't simplify the function foo. The transformation from foo to bar can be proved.

int foo(int a, int b)
{
   return (~a & b) && ~a;
}

int bar(int a, int b)
{
   return (~a & b) && b;
}

Godbolt: https://godbolt.org/z/1cfP7Y5x6
Alive2: https://alive2.llvm.org/ce/z/HDJVkD
@dtcxzyw dtcxzyw mentioned this issue Oct 22, 2023
Open
@dtcxzyw dtcxzyw self-assigned this Oct 22, 2023
@dtcxzyw
Copy link
Member

dtcxzyw commented Oct 22, 2023

I guess it will be fixed by further improvement of #69840 by handling more complicated expressions than binops.

@dtcxzyw dtcxzyw mentioned this issue Oct 26, 2023
Merged
nikic added a commit that referenced this issue Oct 27, 2023
@nikic
[InstSimplify] Add tests for #69050 and #69091 (NFC)
ea1909f
nikic added a commit that referenced this issue Oct 30, 2023
@nikic
[InstCombine] Simplify and/or of icmp eq with op replacement (#70335)
1770a2e 
and/or in logical (select) form benefit from generic simplifications via
simplifyWithOpReplaced(). However, the corresponding fold for plain
and/or currently does not exist.

Similar to selects, there are two general cases for this fold
(illustrated with `and`, but there are `or` conjugates).

The basic case is something like `(a == b) & c`, where the replacement
of a with b or b with a inside c allows it to fold to true or false.
Then the whole operation will fold to either false or `a == b`.

The second case is something like `(a != b) & c`, where the replacement
inside c allows it to fold to false. In that case, the operand can be
replaced with c, because in the case where a == b (and thus the icmp is
false), c itself will already be false.

As the test diffs show, this catches quite a lot of patterns in existing
test coverage. This also obsoletes quite a few existing special-case
and/or of icmp folds we have (e.g. simplifyAndOrOfICmpsWithLimitConst),
but I haven't removed anything as part of this patch in the interest of
risk mitigation.

Fixes #69050.
Fixes #69091.
nikic added a commit to nikic/llvm-project that referenced this issue Nov 2, 2023
@nikic
[InstCombine] Simplify and/or of icmp eq with op replacement (llvm#70335
6343a80 
)

and/or in logical (select) form benefit from generic simplifications via
simplifyWithOpReplaced(). However, the corresponding fold for plain
and/or currently does not exist.

Similar to selects, there are two general cases for this fold
(illustrated with `and`, but there are `or` conjugates).

The basic case is something like `(a == b) & c`, where the replacement
of a with b or b with a inside c allows it to fold to true or false.
Then the whole operation will fold to either false or `a == b`.

The second case is something like `(a != b) & c`, where the replacement
inside c allows it to fold to false. In that case, the operand can be
replaced with c, because in the case where a == b (and thus the icmp is
false), c itself will already be false.

As the test diffs show, this catches quite a lot of patterns in existing
test coverage. This also obsoletes quite a few existing special-case
and/or of icmp folds we have (e.g. simplifyAndOrOfICmpsWithLimitConst),
but I haven't removed anything as part of this patch in the interest of
risk mitigation.

Fixes llvm#69050.
Fixes llvm#69091.
nikic added a commit that referenced this issue Nov 3, 2023
@nikic
Reapply [InstCombine] Simplify and/or of icmp eq with op replacement (#…
060de41 
…70335)

Relative to the first attempt, this contains two changes:

First, we only handle the case where one side simplifies to true or
false, instead of calling simplification recursively. The previous
approach would return poison if one operand simplified to poison
(under the equality assumption), which is incorrect.

Second, we do not fold llvm.is.constant in simplifyWithOpReplaced().
We may be assuming that a value is constant, if the equality holds,
but it may not actually be constant. This is nominally just a QoI
issue, but the std::list implementation in libstdc++ relies on the
precise behavior in a way that causes miscompiles.

-----

and/or in logical (select) form benefit from generic simplifications via
simplifyWithOpReplaced(). However, the corresponding fold for plain
and/or currently does not exist.

Similar to selects, there are two general cases for this fold
(illustrated with `and`, but there are `or` conjugates).

The basic case is something like `(a == b) & c`, where the replacement
of a with b or b with a inside c allows it to fold to true or false.
Then the whole operation will fold to either false or `a == b`.

The second case is something like `(a != b) & c`, where the replacement
inside c allows it to fold to false. In that case, the operand can be
replaced with c, because in the case where a == b (and thus the icmp is
false), c itself will already be false.

As the test diffs show, this catches quite a lot of patterns in existing
test coverage. This also obsoletes quite a few existing special-case
and/or of icmp folds we have (e.g. simplifyAndOrOfICmpsWithLimitConst),
but I haven't removed anything as part of this patch in the interest of
risk mitigation.

Fixes #69050.
Fixes #69091.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@dtcxzyw dtcxzyw

Labels
llvm:instcombine missed-optimization
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

[InstCombine] Simplify and/or of icmp eq with op replacement nikic/llvm-project
2 participants
@dtcxzyw @k-arrows