[Bug middle-end/98710] New: missing optimization (x | c) & ~(y | c) -> x & ~(y | c)

[Bug middle-end/98710] New: missing optimization (x | c) & ~(y | c) -> x & ~(y | c)

[vanyacpp at gmail dot com]

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

            Bug ID: 98710
           Summary: missing optimization (x | c) & ~(y | c) -> x & ~(y |
                    c)
           Product: gcc
           Version: 10.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: vanyacpp at gmail dot com
  Target Milestone: ---

On this function clang generates slightly shorter code

unsigned foo(unsigned x, unsigned y, unsigned c)
{
    return (x | c) & ~(y | c);
}

because it notices that the expression can be simplified to x & ~(y | c). It
would be great if GCC can do the same.

https://godbolt.org/z/3ob6eb

[Bug middle-end/98710] missing optimization (x | c) & ~(y | c) -> x & ~(y | c)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
   Last reconfirmed|                            |2021-04-26
             Status|UNCONFIRMED                 |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I will be implementing this for GCC 12.

[Bug middle-end/98710] missing optimization (x | c) & ~(y | c) -> x & ~(y | c)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2021-04-26 00:00:00         |2023-5-12

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(x | c) & ~(y | c) ->
(x | c) & (~y & ~c) ->
(x & ~y & ~c) | (c & ~y & ~c) ->
(x & ~y & ~c) ->
x & ~(y | c)


Just this simple:
(simplify
 (bit_and:c (bit_ior:c @0 @1) (bit_not@3 (bit_ior:c @1 @2)))
 (bit_and @0 @3))

No reason to rewrite @3 part again.

[Bug middle-end/98710] missing optimization (x | c) & ~(y | c) -> x & ~(y | c)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=103536

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
```
unsigned foo(unsigned x, unsigned y, unsigned c)
{
    return (x | c) & ~(y | c); // x & ~(y | c);
}

unsigned foo_or(unsigned x, unsigned y, unsigned c)
{
    return (x & c) | ~(y & c); // x | ~(y & c);
}

unsigned foo2(unsigned x, unsigned y, unsigned c)
{
    return x & ~(y | x); // 0
}
unsigned foo2_or(unsigned x, unsigned y, unsigned c)
{
    return x | ~(y & x); // -1
}
```

// (x | c) & ~(y | c) -> x & ~(y | c)
// (x & c) | ~(y & c) -> x | ~(y & c)
(for bitop (bit_and bit_ior)
     rbitop (bit_ior bit_and)
 (bitop:c (rbitop:c @0 @1) (bit_not@3 (rbitop:c @1 @2)))
 (bitop @0 @3))

// x & ~(y | x) -> 0
// x | ~(y & x) -> -1
(for bitop (bit_and bit_ior)
     rbitop (bit_ior bit_and)
 (bitop:c @0 (bit_not (rbitop:c @0 @1)))
 (if (bitop == BIT_AND_EXPR)
  { build_zero_cst (type); }
  { build_minus_one_cst (type); }))

[Bug middle-end/98710] missing optimization (x | c) & ~(y | c) -> x & ~(y | c)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |https://gcc.gnu.org/piperma
                   |                            |il/gcc-patches/2023-Septemb
                   |                            |er/629180.html
           Keywords|                            |patch

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Patch posted:
https://gcc.gnu.org/pipermail/gcc-patches/2023-September/629180.html

[Bug middle-end/98710] missing optimization (x | c) & ~(y | c) -> x & ~(y | c)

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:ab286761bf703a43bbd8495cd3fc33a7e88c8440

commit r14-3723-gab286761bf703a43bbd8495cd3fc33a7e88c8440
Author: Andrew Pinski <apinski@marvell.com>
Date:   Sun Sep 3 14:26:53 2023 -0700

    MATCH: Add `(x | c) & ~(y | c)` and `x & ~(y | x)` patterns [PR98710]

    Adding some more simple bit_and/bit_ior patterns.
    How often these show up, I have no idea.

    OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

    gcc/ChangeLog:

            PR tree-optimization/98710
            * match.pd (`(x | c) & ~(y | c)`, `(x & c) | ~(y & c)`): New
pattern.
            (`x & ~(y | x)`, `x | ~(y & x)`): New patterns.

    gcc/testsuite/ChangeLog:

            PR tree-optimization/98710
            * gcc.dg/tree-ssa/andor-7.c: New test.
            * gcc.dg/tree-ssa/andor-8.c: New test.

[Bug middle-end/98710] missing optimization (x | c) & ~(y | c) -> x & ~(y | c)

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed.

[Bug middle-end/98710] missing optimization (x | c) & ~(y | c) -> x & ~(y | c)

[vanyacpp at gmail dot com]

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

--- Comment #7 from Ivan Sorokin <vanyacpp at gmail dot com> ---
(In reply to Andrew Pinski from comment #6)
> Fixed.

Thank you!

[Bug middle-end/98710] missing optimization (x | c) & ~(y | c) -> x & ~(y | c)

[vanyacpp at gmail dot com]

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

--- Comment #8 from Ivan Sorokin <vanyacpp at gmail dot com> ---
>     How often these show up, I have no idea.

Perhaps I should have written this in the original message.

The original expression "(x | c) & ~(y | c)" is obviously a reduced version of
what happens in real code. The idea is the following: When we are working with
bitsets "|" can be read as adding bits and "&~" as removing. Therefore the
expression can be read as first adding "c" to "x" and then removing "y | c"
from the result.

So the simplification

(x | c) & ~(y | c) -> x & ~(y | c)

means there is no need to add "c" if later we remove something containing "c".