On October 13, 2017 9:36:48 PM GMT+02:00, Jakub Jelinek <ja...@redhat.com>
wrote:
>Hi!
>
>The forwprop rotate pattern recognizer is able to detect various
>patterns, but for the case where we want to support all rotate
>counts without UB, it requires
>Y &= B - 1;
>R = (X << Y) | (X >> ((-Y) & (B - 1)));
>where
>R = (X << (Y & (B - 1))) | (X >> ((-Y) & (B - 1)));
>is another reasonable way to write the same thing (don't mask it
>for the case of negation twice).
>
>The following patch teaches forwprop to handle that.
>
>Also, we weren't recognizing rotates of constant X by variable
>shift count Y.
>
>And finally, I've noticed there is a missing check that B is a power of
>two, which matters for the & (B - 1) style patterns - if it is
>not a pow2p, then it isn't doing what we expect it to be.
>
>Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
OK.
Richard.
>2017-10-13 Jakub Jelinek <ja...@redhat.com>
>
> PR middle-end/62263
> PR middle-end/82498
> * tree-ssa-forwprop.c (simplify_rotate): Allow def_arg1[N]
> to be any operand_equal_p operands. For & (B - 1) require
> B to be power of 2. Recognize
> (X << (Y & (B - 1))) | (X >> ((-Y) & (B - 1))) and similar patterns.
>
> * c-c++-common/rotate-5.c (f2): New function. Move old
> function to ...
> (f4): ... this. Use 127 instead of 128.
> (f3, f5, f6): New functions.
> (main): Test all f[1-6] functions, with both 0 and 1 as
> second arguments.
> * c-c++-common/rotate-6.c: New test.
> * c-c++-common/rotate-6a.c: New test.
> * c-c++-common/rotate-7.c: New test.
> * c-c++-common/rotate-7a.c: New test.
> * c-c++-common/rotate-8.c: New test.
>
>--- gcc/tree-ssa-forwprop.c.jj 2017-09-14 22:15:12.000000000 +0200
>+++ gcc/tree-ssa-forwprop.c 2017-10-13 14:35:31.763191645 +0200
>@@ -1491,9 +1491,14 @@ defcodefor_name (tree name, enum tree_co
> applied, otherwise return false.
>
> We are looking for X with unsigned type T with bitsize B, OP being
>- +, | or ^, some type T2 wider than T and
>+ +, | or ^, some type T2 wider than T. For:
> (X << CNT1) OP (X >> CNT2) iff CNT1 + CNT2 == B
> ((T) ((T2) X << CNT1)) OP ((T) ((T2) X >> CNT2)) iff CNT1 + CNT2 == B
>+
>+ transform these into:
>+ X r<< CNT1
>+
>+ Or for:
> (X << Y) OP (X >> (B - Y))
> (X << (int) Y) OP (X >> (int) (B - Y))
> ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
>@@ -1503,12 +1508,23 @@ defcodefor_name (tree name, enum tree_co
> ((T) ((T2) X << Y)) | ((T) ((T2) X >> ((-Y) & (B - 1))))
> ((T) ((T2) X << (int) Y)) | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
>
>- and transform these into:
>- X r<< CNT1
>+ transform these into:
> X r<< Y
>
>+ Or for:
>+ (X << (Y & (B - 1))) | (X >> ((-Y) & (B - 1)))
>+ (X << (int) (Y & (B - 1))) | (X >> (int) ((-Y) & (B - 1)))
>+ ((T) ((T2) X << (Y & (B - 1)))) | ((T) ((T2) X >> ((-Y) & (B -
>1))))
>+ ((T) ((T2) X << (int) (Y & (B - 1)))) \
>+ | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
>+
>+ transform these into:
>+ X r<< (Y & (B - 1))
>+
> Note, in the patterns with T2 type, the type of OP operands
>- might be even a signed type, but should have precision B. */
>+ might be even a signed type, but should have precision B.
>+ Expressions with & (B - 1) should be recognized only if B is
>+ a power of 2. */
>
> static bool
> simplify_rotate (gimple_stmt_iterator *gsi)
>@@ -1578,7 +1594,9 @@ simplify_rotate (gimple_stmt_iterator *g
> def_arg1[i] = tem;
> }
> /* Both shifts have to use the same first operand. */
>- if (TREE_CODE (def_arg1[0]) != SSA_NAME || def_arg1[0] !=
>def_arg1[1])
>+ if (!operand_equal_for_phi_arg_p (def_arg1[0], def_arg1[1])
>+ || !types_compatible_p (TREE_TYPE (def_arg1[0]),
>+ TREE_TYPE (def_arg1[1])))
> return false;
> if (!TYPE_UNSIGNED (TREE_TYPE (def_arg1[0])))
> return false;
>@@ -1649,8 +1667,10 @@ simplify_rotate (gimple_stmt_iterator *g
> /* The above sequence isn't safe for Y being 0,
> because then one of the shifts triggers undefined behavior.
> This alternative is safe even for rotation count of 0.
>- One shift count is Y and the other (-Y) & (B - 1). */
>+ One shift count is Y and the other (-Y) & (B - 1).
>+ Or one shift count is Y & (B - 1) and the other (-Y) & (B - 1).
>*/
> else if (cdef_code[i] == BIT_AND_EXPR
>+ && pow2p_hwi (TYPE_PRECISION (rtype))
> && tree_fits_shwi_p (cdef_arg2[i])
> && tree_to_shwi (cdef_arg2[i])
> == TYPE_PRECISION (rtype) - 1
>@@ -1675,17 +1695,50 @@ simplify_rotate (gimple_stmt_iterator *g
> rotcnt = tem;
> break;
> }
>- defcodefor_name (tem, &code, &tem, NULL);
>+ tree tem2;
>+ defcodefor_name (tem, &code, &tem2, NULL);
> if (CONVERT_EXPR_CODE_P (code)
>- && INTEGRAL_TYPE_P (TREE_TYPE (tem))
>- && TYPE_PRECISION (TREE_TYPE (tem))
>+ && INTEGRAL_TYPE_P (TREE_TYPE (tem2))
>+ && TYPE_PRECISION (TREE_TYPE (tem2))
> > floor_log2 (TYPE_PRECISION (rtype))
>- && type_has_mode_precision_p (TREE_TYPE (tem))
>- && (tem == def_arg2[1 - i]
>- || tem == def_arg2_alt[1 - i]))
>+ && type_has_mode_precision_p (TREE_TYPE (tem2)))
> {
>- rotcnt = tem;
>- break;
>+ if (tem2 == def_arg2[1 - i]
>+ || tem2 == def_arg2_alt[1 - i])
>+ {
>+ rotcnt = tem2;
>+ break;
>+ }
>+ }
>+ else
>+ tem2 = NULL_TREE;
>+
>+ if (cdef_code[1 - i] == BIT_AND_EXPR
>+ && tree_fits_shwi_p (cdef_arg2[1 - i])
>+ && tree_to_shwi (cdef_arg2[1 - i])
>+ == TYPE_PRECISION (rtype) - 1
>+ && TREE_CODE (cdef_arg1[1 - i]) == SSA_NAME)
>+ {
>+ if (tem == cdef_arg1[1 - i]
>+ || tem2 == cdef_arg1[1 - i])
>+ {
>+ rotcnt = def_arg2[1 - i];
>+ break;
>+ }
>+ tree tem3;
>+ defcodefor_name (cdef_arg1[1 - i], &code, &tem3, NULL);
>+ if (CONVERT_EXPR_CODE_P (code)
>+ && INTEGRAL_TYPE_P (TREE_TYPE (tem3))
>+ && TYPE_PRECISION (TREE_TYPE (tem3))
>+ > floor_log2 (TYPE_PRECISION (rtype))
>+ && type_has_mode_precision_p (TREE_TYPE (tem3)))
>+ {
>+ if (tem == tem3 || tem2 == tem3)
>+ {
>+ rotcnt = def_arg2[1 - i];
>+ break;
>+ }
>+ }
> }
> }
> }
>--- gcc/testsuite/c-c++-common/rotate-5.c.jj 2013-05-13
>13:03:31.000000000 +0200
>+++ gcc/testsuite/c-c++-common/rotate-5.c 2017-10-13 13:36:17.130077499
>+0200
>@@ -15,12 +15,40 @@ f1 (unsigned long long x, unsigned int y
> return (x << y) | (x >> ((-y) & 63));
> }
>
>+__attribute__((noinline, noclone))
>+unsigned long long
>+f2 (unsigned long long x, unsigned int y)
>+{
>+ return (x << y) + (x >> ((-y) & 63));
>+}
>+
>+__attribute__((noinline, noclone))
>+unsigned long long
>+f3 (unsigned long long x, unsigned int y)
>+{
>+ return (x << y) ^ (x >> ((-y) & 63));
>+}
>+
> #if __CHAR_BIT__ * __SIZEOF_INT128__ == 128
> __attribute__((noinline, noclone))
> unsigned __int128
>-f2 (unsigned __int128 x, unsigned int y)
>+f4 (unsigned __int128 x, unsigned int y)
> {
>- return (x << y) | (x >> ((-y) & 128));
>+ return (x << y) | (x >> ((-y) & 127));
>+}
>+
>+__attribute__((noinline, noclone))
>+unsigned __int128
>+f5 (unsigned __int128 x, unsigned int y)
>+{
>+ return (x << y) + (x >> ((-y) & 127));
>+}
>+
>+__attribute__((noinline, noclone))
>+unsigned __int128
>+f6 (unsigned __int128 x, unsigned int y)
>+{
>+ return (x << y) ^ (x >> ((-y) & 127));
> }
> #endif
> #endif
>@@ -31,12 +59,45 @@ main ()
> #if __CHAR_BIT__ * __SIZEOF_LONG_LONG__ == 64
> if (f1 (0x123456789abcdef0ULL, 0) != 0x123456789abcdef0ULL)
> abort ();
>+ if (f2 (0x123456789abcdef0ULL, 0) != 0x2468acf13579bde0ULL)
>+ abort ();
>+ if (f3 (0x123456789abcdef0ULL, 0) != 0)
>+ abort ();
>+ if (f1 (0x123456789abcdef0ULL, 1) != 0x2468acf13579bde0ULL)
>+ abort ();
>+ if (f2 (0x123456789abcdef0ULL, 1) != 0x2468acf13579bde0ULL)
>+ abort ();
>+ if (f3 (0x123456789abcdef0ULL, 1) != 0x2468acf13579bde0ULL)
>+ abort ();
> #if __CHAR_BIT__ * __SIZEOF_INT128__ == 128
>- if (f2 ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
>+ if (f4 ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
> | 0x0fedcba987654321ULL, 0)
> != ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
> | 0x0fedcba987654321ULL))
> abort ();
>+ if (f5 ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
>+ | 0x0fedcba987654321ULL, 0)
>+ != ((((unsigned __int128) 0x2468acf13579bde0ULL) << 64)
>+ | 0x1fdb97530eca8642ULL))
>+ abort ();
>+ if (f6 ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
>+ | 0x0fedcba987654321ULL, 0) != 0)
>+ abort ();
>+ if (f4 ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
>+ | 0x0fedcba987654321ULL, 1)
>+ != ((((unsigned __int128) 0x2468acf13579bde0ULL) << 64)
>+ | 0x1fdb97530eca8642ULL))
>+ abort ();
>+ if (f5 ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
>+ | 0x0fedcba987654321ULL, 1)
>+ != ((((unsigned __int128) 0x2468acf13579bde0ULL) << 64)
>+ | 0x1fdb97530eca8642ULL))
>+ abort ();
>+ if (f6 ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
>+ | 0x0fedcba987654321ULL, 1)
>+ != ((((unsigned __int128) 0x2468acf13579bde0ULL) << 64)
>+ | 0x1fdb97530eca8642ULL))
>+ abort ();
> #endif
> #endif
> return 0;
>--- gcc/testsuite/c-c++-common/rotate-6.c.jj 2017-10-13
>12:58:07.310836490 +0200
>+++ gcc/testsuite/c-c++-common/rotate-6.c 2017-10-13 13:29:01.901294238
>+0200
>@@ -0,0 +1,582 @@
>+/* Check rotate pattern detection. */
>+/* { dg-do compile } */
>+/* { dg-options "-O2 -fno-ipa-icf -fdump-tree-optimized" } */
>+/* Rotates should be recognized only in functions with | instead of +
>or ^,
>+ or in functions that have constant shift counts (unused attribute
>on y). */
>+/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 48 "optimized" } }
>*/
>+
>+unsigned int
>+f1 (unsigned int x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) | (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f2 (unsigned int x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) | (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f3 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << 1) | (x >> ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ -
>1)));
>+}
>+
>+unsigned int
>+f4 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) | (x >>
>1);
>+}
>+
>+unsigned short int
>+f5 (unsigned short int x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) | (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned short int
>+f6 (unsigned short int x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) | (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned char
>+f7 (unsigned char x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ - 1))) | (x >> ((-y) & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned char
>+f8 (unsigned char x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ - 1))) | (x >> ((-y) & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned int
>+f9 (unsigned int x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) | (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f10 (unsigned int x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) | (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f11 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << 1) | (x >> ((-1) & (__CHAR_BIT__ * sizeof (unsigned
>int) - 1)));
>+}
>+
>+unsigned int
>+f12 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << ((-1) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) |
>(x >> 1);
>+}
>+
>+unsigned short int
>+f13 (unsigned short int x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) |
>(x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned short int
>+f14 (unsigned short int x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) |
>(x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned char
>+f15 (unsigned char x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) | (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned char
>+f16 (unsigned char x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) | (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned int
>+f17 (unsigned int x, unsigned int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) ^ (x <<
>(y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f18 (unsigned int x, unsigned long int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) ^ (x <<
>(y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f19 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x >> ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) ^ (x <<
>1);
>+}
>+
>+unsigned int
>+f20 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x >> 1) ^ (x << ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ -
>1)));
>+}
>+
>+unsigned short int
>+f21 (unsigned short int x, unsigned int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) ^ (x <<
>(y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned short int
>+f22 (unsigned short int x, unsigned long int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) ^ (x <<
>(y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned char
>+f23 (unsigned char x, unsigned int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ - 1))) ^ (x << (y & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned char
>+f24 (unsigned char x, unsigned long int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ - 1))) ^ (x << (y & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned int
>+f25 (unsigned int x, unsigned int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) ^
>(x << (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f26 (unsigned int x, unsigned long int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) ^
>(x << (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f27 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x >> ((-1) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) ^
>(x << 1);
>+}
>+
>+unsigned int
>+f28 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x >> 1) ^ (x << ((-1) & (__CHAR_BIT__ * sizeof (unsigned
>int) - 1)));
>+}
>+
>+unsigned short int
>+f29 (unsigned short int x, unsigned int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)))
>^ (x << (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned short int
>+f30 (unsigned short int x, unsigned long int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)))
>^ (x << (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned char
>+f31 (unsigned char x, unsigned int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) ^
>(x << (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned char
>+f32 (unsigned char x, unsigned long int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) ^
>(x << (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned int
>+f33 (unsigned int x, unsigned int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) | (x <<
>((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f34 (unsigned int x, unsigned long int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) | (x <<
>((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f35 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x >> 1) | (x << ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ -
>1)));
>+}
>+
>+unsigned int
>+f36 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x >> ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) | (x <<
>1);
>+}
>+
>+unsigned short int
>+f37 (unsigned short int x, unsigned int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) | (x <<
>((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned short int
>+f38 (unsigned short int x, unsigned long int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) | (x <<
>((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned char
>+f39 (unsigned char x, unsigned int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ - 1))) | (x << ((-y) & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned char
>+f40 (unsigned char x, unsigned long int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ - 1))) | (x << ((-y) & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned int
>+f41 (unsigned int x, unsigned int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) | (x
><< ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f42 (unsigned int x, unsigned long int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) | (x
><< ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f43 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x >> 1) | (x << ((-1) & (__CHAR_BIT__ * sizeof (unsigned
>int) - 1)));
>+}
>+
>+unsigned int
>+f44 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x >> ((-1) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) |
>(x << 1);
>+}
>+
>+unsigned short int
>+f45 (unsigned short int x, unsigned int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) |
>(x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned short int
>+f46 (unsigned short int x, unsigned long int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) |
>(x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned char
>+f47 (unsigned char x, unsigned int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) | (x
><< ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned char
>+f48 (unsigned char x, unsigned long int y)
>+{
>+ return (x >> (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) | (x
><< ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned int
>+f49 (unsigned int x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) ^ (x >>
>(y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f50 (unsigned int x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) ^ (x >>
>(y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f51 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) ^ (x >>
>1);
>+}
>+
>+unsigned int
>+f52 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << 1) ^ (x >> ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ -
>1)));
>+}
>+
>+unsigned short int
>+f53 (unsigned short int x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) ^ (x >>
>(y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned short int
>+f54 (unsigned short int x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) ^ (x >>
>(y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned char
>+f55 (unsigned char x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ - 1))) ^ (x >> (y & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned char
>+f56 (unsigned char x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ - 1))) ^ (x >> (y & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned int
>+f57 (unsigned int x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) ^
>(x >> (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f58 (unsigned int x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) ^
>(x >> (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f59 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << ((-1) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) ^
>(x >> 1);
>+}
>+
>+unsigned int
>+f60 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << 1) ^ (x >> ((-1) & (__CHAR_BIT__ * sizeof (unsigned
>int) - 1)));
>+}
>+
>+unsigned short int
>+f61 (unsigned short int x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)))
>^ (x >> (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned short int
>+f62 (unsigned short int x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)))
>^ (x >> (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned char
>+f63 (unsigned char x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) ^
>(x >> (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned char
>+f64 (unsigned char x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) ^
>(x >> (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned int
>+f65 (unsigned int x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f66 (unsigned int x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f67 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << 1) + (x >> ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ -
>1)));
>+}
>+
>+unsigned int
>+f68 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >>
>1);
>+}
>+
>+unsigned short int
>+f69 (unsigned short int x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) + (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned short int
>+f70 (unsigned short int x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) + (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned char
>+f71 (unsigned char x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ - 1))) + (x >> ((-y) & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned char
>+f72 (unsigned char x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ - 1))) + (x >> ((-y) & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned int
>+f73 (unsigned int x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) + (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f74 (unsigned int x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) + (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f75 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << 1) + (x >> ((-1) & (__CHAR_BIT__ * sizeof (unsigned
>int) - 1)));
>+}
>+
>+unsigned int
>+f76 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << ((-1) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) +
>(x >> 1);
>+}
>+
>+unsigned short int
>+f77 (unsigned short int x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) +
>(x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned short int
>+f78 (unsigned short int x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) +
>(x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned char
>+f79 (unsigned char x, unsigned int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) + (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned char
>+f80 (unsigned char x, unsigned long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) + (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned int
>+f81 (unsigned int x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >>
>(y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f82 (unsigned int x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >>
>(y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f83 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >>
>1);
>+}
>+
>+unsigned int
>+f84 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << 1) + (x >> ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ -
>1)));
>+}
>+
>+unsigned short int
>+f85 (unsigned short int x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) + (x >>
>(y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned short int
>+f86 (unsigned short int x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) + (x >>
>(y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned char
>+f87 (unsigned char x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ - 1))) + (x >> (y & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned char
>+f88 (unsigned char x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ - 1))) + (x >> (y & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned int
>+f89 (unsigned int x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) +
>(x >> (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f90 (unsigned int x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) +
>(x >> (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f91 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << ((-1) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) +
>(x >> 1);
>+}
>+
>+unsigned int
>+f92 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << 1) + (x >> ((-1) & (__CHAR_BIT__ * sizeof (unsigned
>int) - 1)));
>+}
>+
>+unsigned short int
>+f93 (unsigned short int x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)))
>+ (x >> (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned short int
>+f94 (unsigned short int x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)))
>+ (x >> (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned char
>+f95 (unsigned char x, unsigned int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) +
>(x >> (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned char
>+f96 (unsigned char x, unsigned long int y)
>+{
>+ return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) +
>(x >> (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>--- gcc/testsuite/c-c++-common/rotate-6a.c.jj 2017-10-13
>12:58:10.977791838 +0200
>+++ gcc/testsuite/c-c++-common/rotate-6a.c 2017-10-13
>13:24:05.786890355 +0200
>@@ -0,0 +1,6 @@
>+/* { dg-do run } */
>+/* { dg-options "-O2 -Wno-overflow" } */
>+
>+#define ROTATE_N "rotate-6.c"
>+
>+#include "rotate-1a.c"
>--- gcc/testsuite/c-c++-common/rotate-7.c.jj 2017-10-13
>13:40:16.575272270 +0200
>+++ gcc/testsuite/c-c++-common/rotate-7.c 2017-10-13 13:41:16.843566194
>+0200
>@@ -0,0 +1,582 @@
>+/* Check rotate pattern detection. */
>+/* { dg-do compile } */
>+/* { dg-options "-O2 -fno-ipa-icf -fdump-tree-optimized" } */
>+/* Rotates should be recognized only in functions with | instead of +
>or ^,
>+ or in functions that have constant shift counts (unused attribute
>on y). */
>+/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 48 "optimized" } }
>*/
>+
>+unsigned int
>+f1 (unsigned int x, int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) | (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f2 (unsigned int x, long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) | (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f3 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << 1) | (x >> ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ -
>1)));
>+}
>+
>+unsigned int
>+f4 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) | (x >>
>1);
>+}
>+
>+unsigned short int
>+f5 (unsigned short int x, int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) | (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned short int
>+f6 (unsigned short int x, long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) | (x >>
>((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned char
>+f7 (unsigned char x, int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ - 1))) | (x >> ((-y) & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned char
>+f8 (unsigned char x, long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ - 1))) | (x >> ((-y) & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned int
>+f9 (unsigned int x, int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) | (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f10 (unsigned int x, long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) | (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f11 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << 1) | (x >> ((-1) & (__CHAR_BIT__ * sizeof (unsigned
>int) - 1)));
>+}
>+
>+unsigned int
>+f12 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x << ((-1) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) |
>(x >> 1);
>+}
>+
>+unsigned short int
>+f13 (unsigned short int x, int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) |
>(x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned short int
>+f14 (unsigned short int x, long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) |
>(x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
>+}
>+
>+unsigned char
>+f15 (unsigned char x, int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) | (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned char
>+f16 (unsigned char x, long int y)
>+{
>+ return (x << (y & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) | (x
>>> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
>+}
>+
>+unsigned int
>+f17 (unsigned int x, int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) ^ (x <<
>(y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f18 (unsigned int x, long int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) ^ (x <<
>(y & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
>+}
>+
>+unsigned int
>+f19 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x >> ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) ^ (x <<
>1);
>+}
>+
>+unsigned int
>+f20 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x >> 1) ^ (x << ((-1) & (__CHAR_BIT__ * __SIZEOF_INT__ -
>1)));
>+}
>+
>+unsigned short int
>+f21 (unsigned short int x, int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) ^ (x <<
>(y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned short int
>+f22 (unsigned short int x, long int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) ^ (x <<
>(y & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
>+}
>+
>+unsigned char
>+f23 (unsigned char x, int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ - 1))) ^ (x << (y & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned char
>+f24 (unsigned char x, long int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ - 1))) ^ (x << (y & (__CHAR_BIT__
>- 1)));
>+}
>+
>+unsigned int
>+f25 (unsigned int x, int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) ^
>(x << (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f26 (unsigned int x, long int y)
>+{
>+ return (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) ^
>(x << (y & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
>+}
>+
>+unsigned int
>+f27 (unsigned int x, int y __attribute__((unused)))
>+{
>+ return (x >> ((-1) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) ^
>(x << 1);
>+}
>+
>+unsigned int
>+f28 (unsigned int x, int y __attribute__((unu
