diff mbox series

match.pd: recognize a signed rotate

Message ID 20200323132225.GA22674@localhost.localdomain
State New
Headers show
Series match.pd: recognize a signed rotate | expand

Commit Message

Jeff Law via Gcc-patches March 23, 2020, 1:22 p.m. UTC
Hi all,

A rotate of a signed integer is not recognized so far.

  int32_t f (int32_t x)
  {
    return (x << 5) | (int32_t)((uint32_t)x >> 27);
  }

The code above is unoptimized in contrast to a version consisting only
of unsigned integers.  I'm wondering if this is intended or not.  Since
GCC has well defined behavior for shifts where the first operand is
signed, I assumed that this also holds for rotates.

The attached patch adds a pattern to match.pd for such signed rotates.
Any comments about this?

Note, for the sake of simplicity the attached patch does not handle the
case where the input is a signed integer and the result is an unsigned,
i.e., the following case is not covered:

  uint32_t f (int32_t x)
  {
    return (x << 5) | ((uint32_t)x >> 27);
  }

My gut feeling was that it's not worth it to have another pattern for
such an impure rotate. Maybe I'm wrong?

Cheers,
Stefan

Comments

Jeff Law via Gcc-patches March 23, 2020, 3:29 p.m. UTC | #1
On Mon, Mar 23, 2020 at 2:23 PM Stefan Schulze Frielinghaus via
Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>
> Hi all,
>
> A rotate of a signed integer is not recognized so far.
>
>   int32_t f (int32_t x)
>   {
>     return (x << 5) | (int32_t)((uint32_t)x >> 27);
>   }
>
> The code above is unoptimized in contrast to a version consisting only
> of unsigned integers.  I'm wondering if this is intended or not.  Since
> GCC has well defined behavior for shifts where the first operand is
> signed, I assumed that this also holds for rotates.
>
> The attached patch adds a pattern to match.pd for such signed rotates.
> Any comments about this?
>
> Note, for the sake of simplicity the attached patch does not handle the
> case where the input is a signed integer and the result is an unsigned,
> i.e., the following case is not covered:
>
>   uint32_t f (int32_t x)
>   {
>     return (x << 5) | ((uint32_t)x >> 27);
>   }
>
> My gut feeling was that it's not worth it to have another pattern for
> such an impure rotate. Maybe I'm wrong?

I wonder if we can leverage the bswap pass for rotate detection
(see find_bswap_or_nop which matches the symbolic number
against either 1:1 or byte-swapped variants, to be added would be
rotate and shift patterns).

Richard.

> Cheers,
> Stefan
Jeff Law via Gcc-patches March 23, 2020, 3:34 p.m. UTC | #2
On Mon, Mar 23, 2020 at 04:29:12PM +0100, Richard Biener wrote:
> I wonder if we can leverage the bswap pass for rotate detection
> (see find_bswap_or_nop which matches the symbolic number
> against either 1:1 or byte-swapped variants, to be added would be
> rotate and shift patterns).

That pass can only handle cases where the shift counts are multiple of
BITS_PER_UNIT, the whole infrastructure is based on being able to track
movements of bytes.

	Jakub
Jeff Law via Gcc-patches March 23, 2020, 3:44 p.m. UTC | #3
On Mon, Mar 23, 2020 at 4:34 PM Jakub Jelinek <jakub@redhat.com> wrote:
>
> On Mon, Mar 23, 2020 at 04:29:12PM +0100, Richard Biener wrote:
> > I wonder if we can leverage the bswap pass for rotate detection
> > (see find_bswap_or_nop which matches the symbolic number
> > against either 1:1 or byte-swapped variants, to be added would be
> > rotate and shift patterns).
>
> That pass can only handle cases where the shift counts are multiple of
> BITS_PER_UNIT, the whole infrastructure is based on being able to track
> movements of bytes.

That's true, but also an artifact of the symbolic number encoding.

>         Jakub
>
Jeff Law via Gcc-patches March 24, 2020, 9:45 a.m. UTC | #4
On Mon, Mar 23, 2020 at 04:44:56PM +0100, Richard Biener wrote:
> On Mon, Mar 23, 2020 at 4:34 PM Jakub Jelinek <jakub@redhat.com> wrote:
> >
> > On Mon, Mar 23, 2020 at 04:29:12PM +0100, Richard Biener wrote:
> > > I wonder if we can leverage the bswap pass for rotate detection
> > > (see find_bswap_or_nop which matches the symbolic number
> > > against either 1:1 or byte-swapped variants, to be added would be
> > > rotate and shift patterns).
> >
> > That pass can only handle cases where the shift counts are multiple of
> > BITS_PER_UNIT, the whole infrastructure is based on being able to track
> > movements of bytes.
> 
> That's true, but also an artifact of the symbolic number encoding.

I'm pretty new to match.pd and in general to GCC.  Is there something
which speaks against solving this in match.pd?  If so and the bswap pass
is also not the right place, do you have something else in mind?
Jeff Law via Gcc-patches March 24, 2020, 2:10 p.m. UTC | #5
On Tue, Mar 24, 2020 at 10:45 AM Stefan Schulze Frielinghaus
<stefansf@linux.ibm.com> wrote:
>
> On Mon, Mar 23, 2020 at 04:44:56PM +0100, Richard Biener wrote:
> > On Mon, Mar 23, 2020 at 4:34 PM Jakub Jelinek <jakub@redhat.com> wrote:
> > >
> > > On Mon, Mar 23, 2020 at 04:29:12PM +0100, Richard Biener wrote:
> > > > I wonder if we can leverage the bswap pass for rotate detection
> > > > (see find_bswap_or_nop which matches the symbolic number
> > > > against either 1:1 or byte-swapped variants, to be added would be
> > > > rotate and shift patterns).
> > >
> > > That pass can only handle cases where the shift counts are multiple of
> > > BITS_PER_UNIT, the whole infrastructure is based on being able to track
> > > movements of bytes.
> >
> > That's true, but also an artifact of the symbolic number encoding.
>
> I'm pretty new to match.pd and in general to GCC.  Is there something
> which speaks against solving this in match.pd?  If so and the bswap pass
> is also not the right place, do you have something else in mind?

For match.pd the patterns tend to be unwieldly so currently this is
pattern-matched in tree-ssa-forwprop.c:simplify_rotate which is the
place I'd see to extend.

Richard.
diff mbox series

Patch

diff --git a/gcc/match.pd b/gcc/match.pd
index 9cb37740f1e..0297f8c9c89 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2986,6 +2986,18 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
      { tree rotate_type = TREE_TYPE (@0); }
       (convert (rotate (convert:rotate_type @1) @2))))))
 
+/* Recognize a signed rotate: assume that X is signed and C1+C2=width(X) holds,
+   then (X << C1) | (s)((u)X >> C2) -> X r>> C2 where (s) and (u) denote the
+   signed and unsigned types of X, respectively.  */
+(simplify
+ (bit_ior
+  (lshift @0 INTEGER_CST@1)
+  (convert (rshift@3 (convert @0) INTEGER_CST@2)))
+ (if (wi::eq_p (wi::add (wi::to_wide (@1), wi::to_wide (@2)),
+		TYPE_PRECISION (TREE_TYPE (@0)))
+      && TYPE_UNSIGNED (TREE_TYPE (@3)))
+  (rrotate @0 @2)))
+
 /* Simplifications of conversions.  */
 
 /* Basic strip-useless-type-conversions / strip_nops.  */