[Bug tree-optimization/63568] New: Missed optimization (a & ~mask) | (b & mask) = a ^ ((a ^ b) & mask)

[Bug tree-optimization/63568] New: Missed optimization (a & ~mask) | (b & mask) = a ^ ((a ^ b) & mask)

[olegendo at gcc dot gnu.org]

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

            Bug ID: 63568
           Summary: Missed optimization (a & ~mask) | (b & mask) = a ^ ((a
                    ^ b) & mask)
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: olegendo at gcc dot gnu.org
            Target: sh*-*-*

As of 216350, compiling the following example on SH with -O2

unsigned int test (unsigned int a, unsigned int b, unsigned int m)
{
  return (a & ~m) | (b & m);
}

results in:
        not     r6,r0
        and     r0,r4
        and     r6,r5
        mov     r4,r0
        rts
        or      r5,r0

A shorter way is to do the same is:
        xor     r4,r5
        and     r5,r6
        mov     r6,r0
        rts
        xor     r4,r0

If this kind of stuff is done as part of tree optimization, then this is
probably not SH specific, although I haven't checked with other targets.

[Bug tree-optimization/63568] Missed optimization (a & ~mask) | (b & mask) = a ^ ((a ^ b) & mask)

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-10-17
                 CC|                            |rguenth at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Looks like three vs. four ops and thus is simpler in general.  Easy to
implement
as simplification on match-and-simplify branch.

[Bug tree-optimization/63568] Missed optimization (a & ~mask) | (b & mask) = a ^ ((a ^ b) & mask)

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |mpolacek at gcc dot gnu.org
           Assignee|unassigned at gcc dot gnu.org      |mpolacek at gcc dot gnu.org
   Target Milestone|---                         |5.0

--- Comment #2 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
I'll try to come up with a match-and-simplify simplification.

[Bug middle-end/63568] Missed optimization (a & ~mask) | (b & mask) = a ^ ((a ^ b) & mask)

[mpolacek at gcc dot gnu.org]

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

--- Comment #3 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
FWIW, I used this to check the whether the transformation is correct:

int
main ()
{
  for (int i = -1000; i < 1000; ++i)
    for (int a = -1000; a < 1000; ++a)
      for (int b = -1000; b < 1000; ++b)
    {
      int x = (a & ~i) | (b & i);
      int y = a ^ ((a ^ b) & i);
      //__builtin_printf ("%d %d\n", x, y);
      if (x != y)
        __builtin_abort ();
    }
}

[Bug middle-end/63568] Missed optimization (a & ~mask) | (b & mask) = a ^ ((a ^ b) & mask)

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Not necessarily 3 vs. 4 ops, many targets have andnot instruction and can do it
also in 3 ops.

[Bug middle-end/63568] Missed optimization (a & ~mask) | (b & mask) = a ^ ((a ^ b) & mask)

[mpolacek at gcc dot gnu.org]

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

--- Comment #5 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
True.  E.g. on my x86_64 i7 Nehalem I see (using ./cc1 -quiet -O2 qq.c -mbmi) 

        andn    %edi, %edx, %edi
        andl    %edx, %esi
        movl    %edi, %eax
        orl     %esi, %eax
        ret

for return (a & ~m) | (b & m); and

        xorl    %edi, %esi
        movl    %edi, %eax
        andl    %esi, %edx
        xorl    %edx, %eax
        ret

for return a ^ ((a ^ b) & m);

[Bug middle-end/63568] Missed optimization (a & ~mask) | (b & mask) = a ^ ((a ^ b) & mask)

[rguenther at suse dot de]

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

--- Comment #6 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 16 Dec 2014, mpolacek at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63568
> 
> --- Comment #5 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
> True.  E.g. on my x86_64 i7 Nehalem I see (using ./cc1 -quiet -O2 qq.c -mbmi) 
> 
>         andn    %edi, %edx, %edi
>         andl    %edx, %esi
>         movl    %edi, %eax
>         orl     %esi, %eax
>         ret
> 
> for return (a & ~m) | (b & m); and
> 
>         xorl    %edi, %esi
>         movl    %edi, %eax
>         andl    %esi, %edx
>         xorl    %edx, %eax
>         ret
> 
> for return a ^ ((a ^ b) & m);

The former is also better for instruction level parallelism - but
that just asks for a clever enough expander / combiner that can
generate that from the latter.

I think on GIMPLE we want to canoncalize to the variant with less
(gimple) operations.  single-use restrictions may apply (with
the lack of a global unified combine / CSE phase)

[Bug middle-end/63568] Missed optimization (a & ~mask) | (b & mask) = a ^ ((a ^ b) & mask)

[olegendo at gcc dot gnu.org]

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

--- Comment #7 from Oleg Endo <olegendo at gcc dot gnu.org> ---
If you decide not to do the transform at the tree level, please change this to
a target PR and assign it to me.

[Bug middle-end/63568] Missed optimization (a & ~mask) | (b & mask) = a ^ ((a ^ b) & mask)

[mpolacek at gcc dot gnu.org]

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

--- Comment #9 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Author: mpolacek
Date: Wed Dec 17 11:48:33 2014
New Revision: 218816

URL: https://gcc.gnu.org/viewcvs?rev=218816&root=gcc&view=rev
Log:
    PR middle-end/63568
    * match.pd: Add (x & ~m) | (y & m) -> ((x ^ y) & m) ^ x pattern.

    * gcc.dg/pr63568.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/pr63568.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/match.pd
    trunk/gcc/testsuite/ChangeLog

[Bug middle-end/63568] Missed optimization (a & ~mask) | (b & mask) = a ^ ((a ^ b) & mask)

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #10 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Fixed.