[Bug middle-end/109986] New: missing fold (~a | b) ^ a => ~(a & b)

[Bug middle-end/109986] New: missing fold (~a | b) ^ a => ~(a & b)

[vanyacpp at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109986

            Bug ID: 109986
           Summary: missing fold (~a | b) ^ a => ~(a & b)
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: vanyacpp at gmail dot com
  Target Milestone: ---

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

This can be optimized to `return ~(a | b);`. This transformation is done by
LLVM, but not by GCC.

[Bug middle-end/109986] missing fold (~a | b) ^ a => ~(a & b)

[vanyacpp at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109986

--- Comment #1 from Ivan Sorokin <vanyacpp at gmail dot com> ---
(In reply to Ivan Sorokin from comment #0)
> int foo(int a, int b)
> {
>     return (~a | b) ^ a;
> }
> 
> This can be optimized to `return ~(a | b);`. This transformation is done by
> LLVM, but not by GCC.

Correction: it can be optimized to `return ~(a & b);`.

[Bug middle-end/109986] missing fold (~a | b) ^ a => ~(a & b)

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109986

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2023-05-26
             Status|UNCONFIRMED                 |NEW
           Severity|normal                      |enhancement
     Ever confirmed|0                           |1

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
GCC does handle:
int f0(int a, int b)
{
    return (a | b) ^ a;
}

And:
int f1(int a, int b)
{
    return (a | ~b) ^ a;
}

[Bug middle-end/109986] missing fold (~a | b) ^ a => ~(a & b)

[vanyacpp at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109986

--- Comment #3 from Ivan Sorokin <vanyacpp at gmail dot com> ---
I tried to investigate why GCC is able to simplify `(a | b) ^ a` and `(a | ~b)
^ a` from comment 2, but not similarly looking `(~a | b) ^ a` from comment 0.

`(a | b) ^ a` matches the following pattern from match.pd:

/* (X | Y) ^ X -> Y & ~ X*/
(simplify
 (bit_xor:c (convert1? (bit_ior:c @@0 @1)) (convert2? @0))
 (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
  (convert (bit_and @1 (bit_not @0)))))

`(a | ~b) ^ a` matches another pattern:

/* (~X | C) ^ D -> (X | C) ^ (~D ^ C) if (~D ^ C) can be simplified.  */
(simplify
 (bit_xor:c (bit_ior:cs (bit_not:s @0) @1) @2)
  (bit_xor (bit_ior @0 @1) (bit_xor! (bit_not! @2) @1)))

With substitution `X = b, C = a, D = a` it gives:

(b | a) ^ (~a ^ a)
(b | a) ^ -1
~(b | a)

`(~a | b) ^ a` is not simplifiable by this pattern because it requires that `~D
^ C` is simplifiable further, but `~a ^ b` is not. In any case, even if it were
applicable it would produce `(a | b) ^ (~a ^ b)` which has more operations than
the original expression.

[Bug middle-end/109986] missing fold (~a | b) ^ a => ~(a & b)

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109986

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:2a3556376c69a1fb588dcf25225950575e42784f

commit r14-2751-g2a3556376c69a1fb588dcf25225950575e42784f
Author: Drew Ross <drross@redhat.com>
Date:   Mon Jul 24 17:51:28 2023 +0200

    match.pd: Implement missed optimization (~X | Y) ^ X -> ~(X & Y) [PR109986]

    Adds a simplification for (~X | Y) ^ X to be folded into ~(X & Y).
    Also adds the macro bitwise_equal_p for generic and gimple which
    returns true iff EXPR1 and EXPR2 have the same value. This helps
    to reduce the number of nop_converts necessary to match the pattern.

            PR middle-end/109986

    gcc/ChangeLog:

            * generic-match-head.cc (bitwise_equal_p): New macro.
            * gimple-match-head.cc (bitwise_equal_p): New macro.
            (gimple_nop_convert): Declare.
            (gimple_bitwise_equal_p): Helper for bitwise_equal_p.
            * match.pd ((~X | Y) ^ X -> ~(X & Y)): New simplification.

    gcc/testsuite/ChangeLog:

            * gcc.c-torture/execute/pr109986.c: New test.
            * gcc.dg/tree-ssa/pr109986.c: New test.

    Co-authored-by: Jakub Jelinek <jakub@redhat.com>

[Bug middle-end/109986] missing fold (~a | b) ^ a => ~(a & b)

[vanyacpp at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109986

--- Comment #5 from Ivan Sorokin <vanyacpp at gmail dot com> ---
(In reply to CVS Commits from comment #4)
> commit r14-2751-g2a3556376c69a1fb588dcf25225950575e42784f
> Author: Drew Ross <drross@redhat.com>
> Co-authored-by: Jakub Jelinek <jakub@redhat.com>

Thank you!

[Bug middle-end/109986] missing fold (~a | b) ^ a => ~(a & b)

[gabravier at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109986

Gabriel Ravier <gabravier at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gabravier at gmail dot com

--- Comment #6 from Gabriel Ravier <gabravier at gmail dot com> ---
Seems to be fixed on trunk, except that I've noticed that the f0 example does
some weird operations on BPF, but that seems like a separate issue.

[Bug middle-end/109986] missing fold (~a | b) ^ a => ~(a & b)

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109986

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
   Target Milestone|---                         |14.0
         Resolution|---                         |FIXED

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed, I will file some bool ones in a few minutes.