[Bug tree-optimization/108874] New: [10/11/12/13 Regression] Missing bswap detection

[Bug tree-optimization/108874] New: [10/11/12/13 Regression] Missing bswap detection

[ktkachov at gcc dot gnu.org]

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

            Bug ID: 108874
           Summary: [10/11/12/13 Regression] Missing bswap detection
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ktkachov at gcc dot gnu.org
  Target Milestone: ---

If we look at the arm testcases in gcc.target/arm/rev16.c
typedef unsigned int __u32;

__u32
__rev16_32_alt (__u32 x)
{
  return (((__u32)(x) & (__u32)0xff00ff00UL) >> 8)
         | (((__u32)(x) & (__u32)0x00ff00ffUL) << 8);
}

__u32
__rev16_32 (__u32 x)
{
  return (((__u32)(x) & (__u32)0x00ff00ffUL) << 8)
         | (((__u32)(x) & (__u32)0xff00ff00UL) >> 8);
}

we should be able to generate rev16 instructions for aarch64 (and arm) i.e.
recognise a __builtin_bswap16 essentially.
GCC fails to do so and generates:
__rev16_32_alt:
        lsr     w1, w0, 8
        lsl     w0, w0, 8
        and     w1, w1, 16711935
        and     w0, w0, -16711936
        orr     w0, w1, w0
        ret
__rev16_32:
        lsl     w1, w0, 8
        lsr     w0, w0, 8
        and     w1, w1, -16711936
        and     w0, w0, 16711935
        orr     w0, w1, w0
        ret

whereas clang manages to recognise it all into:
__rev16_32_alt:                         // @__rev16_32_alt
        rev16   w0, w0
        ret
__rev16_32:                             // @__rev16_32
        rev16   w0, w0
        ret

does the bswap pass need some tweaking perhaps?

Looks like this worked fine with GCC 5 but broke in the GCC 6 timeframe so
marking as a regression

[Bug tree-optimization/108874] [10/11/12/13 Regression] Missing bswap detection

[ktkachov at gcc dot gnu.org]

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

--- Comment #1 from ktkachov at gcc dot gnu.org ---
(In reply to ktkachov from comment #0)
> If we look at the arm testcases in gcc.target/arm/rev16.c
> typedef unsigned int __u32;
> 
> __u32
> __rev16_32_alt (__u32 x)
> {
>   return (((__u32)(x) & (__u32)0xff00ff00UL) >> 8)
>          | (((__u32)(x) & (__u32)0x00ff00ffUL) << 8);
> }
> 
> __u32
> __rev16_32 (__u32 x)
> {
>   return (((__u32)(x) & (__u32)0x00ff00ffUL) << 8)
>          | (((__u32)(x) & (__u32)0xff00ff00UL) >> 8);
> }
> 

this isn't a simple __builtin_bswap16 as that returns a uint16_t, this is sort
of a __builtin_swap16 in each of the half-words of the u32

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |needs-bisection
            Version|unknown                     |13.0
   Target Milestone|---                         |10.5
          Component|tree-optimization           |target
             Target|                            |arm

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
The regression is probably rtl-optimization/target specific since we never had
this kind of pattern detected on the tree/GIMPLE level and there's no builtin
or IFN for this shuffling on u32.

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[ktkachov at gcc dot gnu.org]

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

--- Comment #3 from ktkachov at gcc dot gnu.org ---
(In reply to Richard Biener from comment #2)
> The regression is probably rtl-optimization/target specific since we never
> had this kind of pattern detected on the tree/GIMPLE level and there's no
> builtin or IFN for this shuffling on u32.

FWIW a colleague reported that he bisected the failure to
g:98e30e515f184bd63196d4d500a682fbfeb9635e though I haven't tried it myself.
We do have patterns for these in aarch64 and arm, but combine would need to
match about 5 insns to get there and that's beyond its current limit of 4

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to ktkachov from comment #3)
> (In reply to Richard Biener from comment #2)
> > The regression is probably rtl-optimization/target specific since we never
> > had this kind of pattern detected on the tree/GIMPLE level and there's no
> > builtin or IFN for this shuffling on u32.
> 
> FWIW a colleague reported that he bisected the failure to
> g:98e30e515f184bd63196d4d500a682fbfeb9635e though I haven't tried it myself.

There's a slight difference in before/after since GENERIC folding only
applied the (X & C2) << C1 into (X << C1) & (C2 << C1) transform
when the new BIT_AND "simplified":

-         tem = fold_binary_loc (loc, BIT_AND_EXPR, type, shift, mask);
-         if (tem)
-           return tem;

The transform was added in r0-84712-g22164c3db76535 for some rotate
patterns, tested by gcc.dg/fold-rotate-1.c, the pattern was meanwhile
extended to cover other bit operations as well.

> We do have patterns for these in aarch64 and arm, but combine would need to
> match about 5 insns to get there and that's beyond its current limit of 4

maybe some helper patterns no longer catch the differently canonicalized forms?

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-02-23
             Target|arm                         |arm, aarch64
           Keywords|needs-bisection             |
             Status|UNCONFIRMED                 |NEW

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
How it worked before because of the following combine, removing 1 instruction
and then doing the 4->1 matching:

Trying 7 -> 10:

(set (reg:SI 80 [ D.3188 ])
    (ior:SI (lshiftrt:SI (reg:SI 81 [ D.3187 ])
            (const_int 8 [0x8]))
        (reg:SI 84 [ D.3187 ])))



So we could match add a pattern/split that matching this combine:
Trying 6, 7 -> 10:
    6: r99:SI=r97:SI 0>>0x8
    7: r100:SI=r99:SI&0xff00ff
      REG_DEAD r99:SI
   10: r98:SI=r100:SI|r102:SI
      REG_DEAD r102:SI
      REG_DEAD r100:SI
Failed to match this instruction:
(set (reg:SI 98)
    (ior:SI (and:SI (lshiftrt:SI (reg/v:SI 97 [ x ])
                (const_int 8 [0x8]))
            (const_int 16711935 [0xff00ff]))
        (reg:SI 102)))

into two, pushing the and before the shift right.

Note this would require modifying both the arm and aarch64 backends but it
seems doable.

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|arm, aarch64                |aarch64
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I split out the arm version to PR 108933 since I am going to implement the
aarch64 backend change I recommended in comment #5 .

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[crazylht at gmail dot com]

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

Hongtao.liu <crazylht at gmail dot com> changed:

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

--- Comment #7 from Hongtao.liu <crazylht at gmail dot com> ---
Can we recognize it as bswap32 + roatate 16 in match.pd when backend supports
boths, and then it should be easy for aarch64/arm to tranform bswap + ratate
into rev16 at rtl level.

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[pinskia at gcc dot gnu.org]

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

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Hongtao.liu from comment #7)
> Can we recognize it as bswap32 + roatate 16 in match.pd when backend
> supports boths, and then it should be easy for aarch64/arm to tranform bswap
> + ratate into rev16 at rtl level.

That definitely would be better in the general case (note it might not be in
match.pd though) though doing:
(set (reg:SI 98)
    (ior:SI (and:SI (lshiftrt:SI (reg/v:SI 97 [ x ])
                (const_int 8 [0x8]))
            (const_int 16711935 [0xff00ff]))
        (reg:SI 102)))

as
(set (reg:SI 98)
     (ior:SI
      (lshiftrt:SI
       (and:SI (reg/v:SI 97 [ x ])  (const_int 0xff00ff00) )
       (const_int 8 [0x8]))
      (reg:SI 102)))

in the aarch64 backend would produce better code for some other examples too
and not just rev16 generation really.
Take:
```
unsigned f(unsigned x, unsigned b)
{
  return ((x & 0xff00ff00U) >> 8) | b;
}
```

GCC 5 used to produce:
        and     w0, w0, -16711936
        orr     w0, w1, w0, lsr 8
        ret

While the tunk does:
        lsr     w0, w0, 8
        and     w0, w0, 16711935
        orr     w0, w0, w1
        ret

Note xor and addition should be handled in a similar way too.
That is these has a similar regression:
unsigned f(unsigned x, unsigned b)
{
  return ((x & 0xff00ff00U) >> 8) ^ b;
}
unsigned f1(unsigned x, unsigned b)
{
  return ((x & 0xff00ff00U) >> 8) + b;
}

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[pinskia at gcc dot gnu.org]

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

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #8)
> (set (reg:SI 98)
>     (ior:SI (and:SI (lshiftrt:SI (reg/v:SI 97 [ x ])
>                 (const_int 8 [0x8]))
>             (const_int 16711935 [0xff00ff]))
>         (reg:SI 102)))
> 
> as
> (set (reg:SI 98)
>      (ior:SI
>       (lshiftrt:SI
>        (and:SI (reg/v:SI 97 [ x ])  (const_int 0xff00ff00) )
>        (const_int 8 [0x8]))
>       (reg:SI 102)))

Note there are some similar define_split already in the aarch64 backend around
lines 4688. For shift left, but not for shift right.

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[pinskia at gcc dot gnu.org]

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

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 54629
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54629&action=edit
Patch but need to add testcases

here is the patch which adds the define_split to aarch64 md file that helps
combine and we produce the rev16 again for the original testcase and fixes the
testcases in comment #8 too.

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #54629|0                           |1
        is obsolete|                            |

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 54630
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54630&action=edit
Patch with testcases

Testing this patch now and will submit it once to finishes building/running the
testsuite.

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch
                URL|                            |https://gcc.gnu.org/piperma
                   |                            |il/gcc-patches/2023-March/6
                   |                            |13696.html

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Patch submitted here:
https://gcc.gnu.org/pipermail/gcc-patches/2023-March/613696.html

Note I had made a few mistakes in the testcase in the patch which was attached
but fixed them before submitting it.

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[cvs-commit at gcc dot gnu.org]

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

--- Comment #13 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:fcbc5c190c40b51c82f827830ce403c07d628960

commit r13-6591-gfcbc5c190c40b51c82f827830ce403c07d628960
Author: Andrew Pinski <apinski@marvell.com>
Date:   Fri Mar 10 00:53:39 2023 +0000

    Fix PR 108874: aarch64 code regression with shift and ands

    After r6-2044-g98e30e515f184b, code like "((x & 0xff00ff00U) >> 8)"
    would be optimized like (x >> 8) & 0xff00ffU which is normally better
    except on aarch64, the shift right could be combined with another
    operation in some cases. So we need to add a few define_splits
    to the aarch64 backends that match "((x >> shift) & CST0) OP Y"
    and splits it to:
    TMP = X & CST1
    (TMP >> shift) OP Y

    Note this also gets us to matching rev16 back too so I added a
    testcase to make sure we don't lose that matching any more.
    Note when the generic patch to recognize those as bswap ROT 16,
    we might regress again and need to add a few more patterns to
    the aarch64 backend but will deal with that once that happens.

    Committed as approved after a bootstrapp/test on aarch64-linux-gnu with no
regressions.

    gcc/ChangeLog:

            * config/aarch64/aarch64.md: Add a new define_split
            to help combine.

    gcc/testsuite/ChangeLog:

            * gcc.target/aarch64/rev16_2.c: New test.
            * gcc.target/aarch64/shift_and_operator-1.c: New test.

[Bug target/108874] [10/11/12/13 Regression] Missing bswap detection

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |13.0
             Status|ASSIGNED                    |RESOLVED
      Known to fail|13.0                        |
   Target Milestone|10.5                        |13.0
         Resolution|---                         |FIXED

--- Comment #14 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed on the trunk, this can be backported if anyone wants to do that testing
but since it took over 5 years to notice it because there was no testcase for
it, I am not going to do the backporting.