[PATCH] Fix up rotate expansion

[PATCH] Fix up rotate expansion

[Jakub Jelinek]

Hi!

Our rotate expansion if rotate optab isn't present for the respective
mode looks unsafe for rotations by variable count if that count could
be 0, because then it invokes right or left shift by bitsize.
While on most targets the hw will probably do the right thing
(it is fine if x << 32 will either yield x or 0, in both cases
that ored together with x >> 0 aka x will still yield x), perhaps gcc
could try to optimize based on the fact that undefined behavior can't
happen, so IMHO it is better to generate a safer sequence.

Ok for trunk?

2013-05-10  Jakub Jelinek  <jakub@redhat.com>

	* expmed.c (expand_shift_1): For rotations by const0_rtx just
	return shifted.  Use (-op1) & (prec - 1) as other_amount
	instead of prec - op1.

--- gcc/expmed.c.jj	2013-05-07 10:26:46.000000000 +0200
+++ gcc/expmed.c	2013-05-10 11:54:34.659987038 +0200
@@ -2166,7 +2166,8 @@ expand_shift_1 (enum tree_code code, enu
 	    {
 	      /* If we have been unable to open-code this by a rotation,
 		 do it as the IOR of two shifts.  I.e., to rotate A
-		 by N bits, compute (A << N) | ((unsigned) A >> (C - N))
+		 by N bits, compute
+		 (A << N) | ((unsigned) A >> ((-N) & (C - 1)))
 		 where C is the bitsize of A.
 
 		 It is theoretically possible that the target machine might
@@ -2181,14 +2182,22 @@ expand_shift_1 (enum tree_code code, enu
 	      rtx temp1;
 
 	      new_amount = op1;
-	      if (CONST_INT_P (op1))
+	      if (op1 == const0_rtx)
+		return shifted;
+	      else if (CONST_INT_P (op1))
 		other_amount = GEN_INT (GET_MODE_BITSIZE (mode)
 					- INTVAL (op1));
 	      else
-		other_amount
-		  = simplify_gen_binary (MINUS, GET_MODE (op1),
-					 GEN_INT (GET_MODE_PRECISION (mode)),
-					 op1);
+		{
+		  other_amount
+		    = simplify_gen_unary (NEG, GET_MODE (op1),
+					  op1, GET_MODE (op1));
+		  other_amount
+		    = simplify_gen_binary (AND, GET_MODE (op1),
+					   other_amount,
+					   GEN_INT (GET_MODE_PRECISION (mode)
+						    - 1));
+		}
 
 	      shifted = force_reg (mode, shifted);
 

	Jakub

Re: [PATCH] Fix up rotate expansion

[Jeff Law]

On 05/10/2013 08:53 AM, Jakub Jelinek wrote:
> Hi!
>
> Our rotate expansion if rotate optab isn't present for the respective
> mode looks unsafe for rotations by variable count if that count could
> be 0, because then it invokes right or left shift by bitsize.
> While on most targets the hw will probably do the right thing
> (it is fine if x << 32 will either yield x or 0, in both cases
> that ored together with x >> 0 aka x will still yield x), perhaps gcc
> could try to optimize based on the fact that undefined behavior can't
> happen, so IMHO it is better to generate a safer sequence.
>
> Ok for trunk?
>
> 2013-05-10  Jakub Jelinek  <jakub@redhat.com>
>
> 	* expmed.c (expand_shift_1): For rotations by const0_rtx just
> 	return shifted.  Use (-op1) & (prec - 1) as other_amount
> 	instead of prec - op1.
Found by inspection?  Presumably the rotate was synthesized by GCC from 
some other set of operations.  To be optimizable, we'd have to prove the 
original sequence triggered undefined behaviour.

Seems that we ought to have a testcase, even though it probably means 
scanning the tree dumps to pick up the undefined behaviour.  Approved 
with a testcase.


Out of curiosity, do we recognize the original sequence created by 
expand_shift_1 as a rotate if they appeared in the original source?



jeff

Re: [PATCH] Fix up rotate expansion

[Jakub Jelinek]

On Fri, May 10, 2013 at 05:18:34PM -0600, Jeff Law wrote:
> On 05/10/2013 08:53 AM, Jakub Jelinek wrote:
> >Hi!
> >
> >Our rotate expansion if rotate optab isn't present for the respective
> >mode looks unsafe for rotations by variable count if that count could
> >be 0, because then it invokes right or left shift by bitsize.
> >While on most targets the hw will probably do the right thing
> >(it is fine if x << 32 will either yield x or 0, in both cases
> >that ored together with x >> 0 aka x will still yield x), perhaps gcc
> >could try to optimize based on the fact that undefined behavior can't
> >happen, so IMHO it is better to generate a safer sequence.
> >
> >Ok for trunk?
> >
> >2013-05-10  Jakub Jelinek  <jakub@redhat.com>
> >
> >	* expmed.c (expand_shift_1): For rotations by const0_rtx just
> >	return shifted.  Use (-op1) & (prec - 1) as other_amount
> >	instead of prec - op1.

> Found by inspection?

Yes.

>  Presumably the rotate was synthesized by GCC
> from some other set of operations.  To be optimizable, we'd have to
> prove the original sequence triggered undefined behaviour.

See http://gcc.gnu.org/PR57157 and
http://gcc.gnu.org/ml/gcc-patches/2013-05/msg00453.html
Until recently only the bit_rotate: code in fold-const.c was pattern
matching {L,R}ROTATE_EXPR and handled only the
(x << y) {+|^} (x >> (b - y))
patterns which is indeed undefined behavior for y == 0.
But since the above change trunk also handles the
(x << y) {+|^} (x >> ((-y) & (b - 1))
pattern which is valid even for y = 0, thus the above patch adjusts
what we generate.  The info whether rotation count 0 was valid or not is
unfortunately lost, adding two new {L,R}ROTATE0_EXPR tree codes might be
overkill for this.

> Seems that we ought to have a testcase, even though it probably
> means scanning the tree dumps to pick up the undefined behaviour.
> Approved with a testcase.

I have added lots of testcases recently, for rotation by zero perhaps
something similar to rotate-1a.c from above can be added as rotate-2b.c
and rotate-4b.c, and test zero rotation.

	Jakub

[PATCH] Fix up rotate expansion (take 2)

[Jakub Jelinek]

On Sat, May 11, 2013 at 09:05:52AM +0200, Jakub Jelinek wrote:
> > Seems that we ought to have a testcase, even though it probably
> > means scanning the tree dumps to pick up the undefined behaviour.
> > Approved with a testcase.
> 
> I have added lots of testcases recently, for rotation by zero perhaps
> something similar to rotate-1a.c from above can be added as rotate-2b.c
> and rotate-4b.c, and test zero rotation.

Thanks for forcing me to do more testcases, I've actually found a serious
bug in my recent patch.  The (X << Y) OP (X >> ((-Y) & (B - 1))) style
patterns can only be recognized as rotates if OP is |, because
while they act as rotates for Y != 0, they act differently for Y == 0.
For (X << Y) OP (X >> (B - Y)) that is not an issue, because for Y == 0
they trigger undefined behavior.

Fixed thusly, plus added coverage for rotates by 0.  And rotate-5.c
testcase is to test the expmed.c change.

2013-05-10  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/45216
	PR tree-optimization/57157
	* tree-ssa-forwprop.c (simplify_rotate): Only recognize
	the (-Y) & (B - 1) variant if OP is |.
	* expmed.c (expand_shift_1): For rotations by const0_rtx just
	return shifted.  Use (-op1) & (prec - 1) as other_amount
	instead of prec - op1.

	* c-c++-common/rotate-1.c: Add 32 tests with +.
	* c-c++-common/rotate-1a.c: Adjust.
	* c-c++-common/rotate-2.c: Add 32 tests with +, expect
	only 48 rotates.
	* c-c++-common/rotate-2b.c: New test.
	* c-c++-common/rotate-3.c: Add 32 tests with +.
	* c-c++-common/rotate-4.c: Add 32 tests with +, expect
	only 48 rotates.
	* c-c++-common/rotate-4b.c: New test.
	* c-c++-common/rotate-5.c: New test.

--- gcc/tree-ssa-forwprop.c.jj	2013-05-10 10:39:13.000000000 +0200
+++ gcc/tree-ssa-forwprop.c	2013-05-11 09:57:39.627194037 +0200
@@ -2135,10 +2135,10 @@ simplify_bitwise_binary (gimple_stmt_ite
    (X << (int) Y) OP (X >> (int) (B - Y))
    ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
    ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) (B - Y)))
-   (X << Y) OP (X >> ((-Y) & (B - 1)))
-   (X << (int) Y) OP (X >> (int) ((-Y) & (B - 1)))
-   ((T) ((T2) X << Y)) OP ((T) ((T2) X >> ((-Y) & (B - 1))))
-   ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
+   (X << Y) | (X >> ((-Y) & (B - 1)))
+   (X << (int) Y) | (X >> (int) ((-Y) & (B - 1)))
+   ((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
@@ -2293,7 +2293,8 @@ simplify_rotate (gimple_stmt_iterator *g
 		 && host_integerp (cdef_arg2[i], 0)
 		 && tree_low_cst (cdef_arg2[i], 0)
 		    == TYPE_PRECISION (rtype) - 1
-		 && TREE_CODE (cdef_arg1[i]) == SSA_NAME)
+		 && TREE_CODE (cdef_arg1[i]) == SSA_NAME
+		 && gimple_assign_rhs_code (stmt) == BIT_IOR_EXPR)
 	  {
 	    tree tem;
 	    enum tree_code code;
--- gcc/expmed.c.jj	2013-05-07 10:26:46.000000000 +0200
+++ gcc/expmed.c	2013-05-11 09:11:54.087412982 +0200
@@ -2166,7 +2166,8 @@ expand_shift_1 (enum tree_code code, enu
 	    {
 	      /* If we have been unable to open-code this by a rotation,
 		 do it as the IOR of two shifts.  I.e., to rotate A
-		 by N bits, compute (A << N) | ((unsigned) A >> (C - N))
+		 by N bits, compute
+		 (A << N) | ((unsigned) A >> ((-N) & (C - 1)))
 		 where C is the bitsize of A.
 
 		 It is theoretically possible that the target machine might
@@ -2181,14 +2182,22 @@ expand_shift_1 (enum tree_code code, enu
 	      rtx temp1;
 
 	      new_amount = op1;
-	      if (CONST_INT_P (op1))
+	      if (op1 == const0_rtx)
+		return shifted;
+	      else if (CONST_INT_P (op1))
 		other_amount = GEN_INT (GET_MODE_BITSIZE (mode)
 					- INTVAL (op1));
 	      else
-		other_amount
-		  = simplify_gen_binary (MINUS, GET_MODE (op1),
-					 GEN_INT (GET_MODE_PRECISION (mode)),
-					 op1);
+		{
+		  other_amount
+		    = simplify_gen_unary (NEG, GET_MODE (op1),
+					  op1, GET_MODE (op1));
+		  other_amount
+		    = simplify_gen_binary (AND, GET_MODE (op1),
+					   other_amount,
+					   GEN_INT (GET_MODE_PRECISION (mode)
+						    - 1));
+		}
 
 	      shifted = force_reg (mode, shifted);
 
--- gcc/testsuite/c-c++-common/rotate-1.c.jj	2013-05-10 10:39:13.000000000 +0200
+++ gcc/testsuite/c-c++-common/rotate-1.c	2013-05-11 10:11:22.725252954 +0200
@@ -1,7 +1,7 @@
 /* Check rotate pattern detection.  */
 /* { dg-do compile } */
 /* { dg-options "-O2 -fdump-tree-optimized" } */
-/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 64 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 96 "optimized" } } */
 /* { dg-final { cleanup-tree-dump "optimized" } } */
 
 unsigned int
@@ -387,3 +387,195 @@ f64 (unsigned char x, unsigned long int
 {
   return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) ^ (x >> y);
 }
+
+unsigned int
+f65 (unsigned int x, unsigned int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - y));
+}
+
+unsigned int
+f66 (unsigned int x, unsigned long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - y));
+}
+
+unsigned int
+f67 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << 1) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - 1));
+}
+
+unsigned int
+f68 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - 1)) + (x >> 1);
+}
+
+unsigned short int
+f69 (unsigned short int x, unsigned int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_SHORT__ - y));
+}
+
+unsigned short int
+f70 (unsigned short int x, unsigned long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_SHORT__ - y));
+}
+
+unsigned char
+f71 (unsigned char x, unsigned int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ - y));
+}
+
+unsigned char
+f72 (unsigned char x, unsigned long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ - y));
+}
+
+unsigned int
+f73 (unsigned int x, unsigned int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - y));
+}
+
+unsigned int
+f74 (unsigned int x, unsigned long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - y));
+}
+
+unsigned int
+f75 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << 1) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - 1));
+}
+
+unsigned int
+f76 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - 1)) + (x >> 1);
+}
+
+unsigned short int
+f77 (unsigned short int x, unsigned int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned short) - y));
+}
+
+unsigned short int
+f78 (unsigned short int x, unsigned long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned short) - y));
+}
+
+unsigned char
+f79 (unsigned char x, unsigned int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned char) - y));
+}
+
+unsigned char
+f80 (unsigned char x, unsigned long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned char) - y));
+}
+
+unsigned int
+f81 (unsigned int x, unsigned int y)
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - y)) + (x >> y);
+}
+
+unsigned int
+f82 (unsigned int x, unsigned long int y)
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - y)) + (x >> y);
+}
+
+unsigned int
+f83 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - 1)) + (x >> 1);
+}
+
+unsigned int
+f84 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << 1) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - 1));
+}
+
+unsigned short int
+f85 (unsigned short int x, unsigned int y)
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_SHORT__ - y)) + (x >> y);
+}
+
+unsigned short int
+f86 (unsigned short int x, unsigned long int y)
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_SHORT__ - y)) + (x >> y);
+}
+
+unsigned char
+f87 (unsigned char x, unsigned int y)
+{
+  return (x << (__CHAR_BIT__ - y)) + (x >> y);
+}
+
+unsigned char
+f88 (unsigned char x, unsigned long int y)
+{
+  return (x << (__CHAR_BIT__ - y)) + (x >> y);
+}
+
+unsigned int
+f89 (unsigned int x, unsigned int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - y)) + (x >> y);
+}
+
+unsigned int
+f90 (unsigned int x, unsigned long int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - y)) + (x >> y);
+}
+
+unsigned int
+f91 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - 1)) + (x >> 1);
+}
+
+unsigned int
+f92 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << 1) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - 1));
+}
+
+unsigned short int
+f93 (unsigned short int x, unsigned int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned short) - y)) + (x >> y);
+}
+
+unsigned short int
+f94 (unsigned short int x, unsigned long int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned short) - y)) + (x >> y);
+}
+
+unsigned char
+f95 (unsigned char x, unsigned int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) + (x >> y);
+}
+
+unsigned char
+f96 (unsigned char x, unsigned long int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) + (x >> y);
+}
--- gcc/testsuite/c-c++-common/rotate-1a.c.jj	2013-05-10 10:39:13.000000000 +0200
+++ gcc/testsuite/c-c++-common/rotate-1a.c	2013-05-11 10:16:15.702552070 +0200
@@ -21,13 +21,18 @@ unsigned int expected[] = {
 0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf,
 0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf,
 0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf,
+0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf,
+0x91a2b3c0, 0x91a2b3c0, 0x2468acf0, 0x91a2b3c, 0xb3c2, 0xb3c2, 0xc3, 0xc3,
+0x91a2b3c0, 0x91a2b3c0, 0x2468acf0, 0x91a2b3c, 0xb3c2, 0xb3c2, 0xc3, 0xc3,
+0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf,
 0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf };
 
 #define F(n) __typeof (f##n) f##n __attribute__((noinline, noclone));
 #define D(n) F(n##0) F(n##1) F(n##2) F(n##3) F(n##4) F(n##5) F(n##6) F(n##7) F(n##8) F(n##9)
 #define ALL \
 F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(8) F(9) \
-D(1) D(2) D(3) D(4) D(5) F(60) F(61) F(62) F(63) F(64)
+D(1) D(2) D(3) D(4) D(5) D(6) D(7) D(8) \
+F(90) F(91) F(92) F(93) F(94) F(95) F(96)
 ALL
 
 int
--- gcc/testsuite/c-c++-common/rotate-2.c.jj	2013-05-10 10:39:13.000000000 +0200
+++ gcc/testsuite/c-c++-common/rotate-2.c	2013-05-11 10:35:38.127716820 +0200
@@ -1,7 +1,9 @@
 /* Check rotate pattern detection.  */
 /* { dg-do compile } */
 /* { dg-options "-O2 -fdump-tree-optimized" } */
-/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 64 "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" } } */
 /* { dg-final { cleanup-tree-dump "optimized" } } */
 
 unsigned int
@@ -387,3 +389,195 @@ f64 (unsigned char x, unsigned long int
 {
   return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) ^ (x >> y);
 }
+
+unsigned int
+f65 (unsigned int x, unsigned int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
+}
+
+unsigned int
+f66 (unsigned int x, unsigned long int y)
+{
+  return (x << y) + (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) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
+}
+
+unsigned short int
+f70 (unsigned short int x, unsigned long int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
+}
+
+unsigned char
+f71 (unsigned char x, unsigned int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ - 1)));
+}
+
+unsigned char
+f72 (unsigned char x, unsigned long int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ - 1)));
+}
+
+unsigned int
+f73 (unsigned int x, unsigned int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
+}
+
+unsigned int
+f74 (unsigned int x, unsigned long int y)
+{
+  return (x << y) + (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) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
+}
+
+unsigned short int
+f78 (unsigned short int x, unsigned long int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
+}
+
+unsigned char
+f79 (unsigned char x, unsigned int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
+}
+
+unsigned char
+f80 (unsigned char x, unsigned long int y)
+{
+  return (x << y) + (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);
+}
+
+unsigned int
+f82 (unsigned int x, unsigned long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >> y);
+}
+
+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);
+}
+
+unsigned short int
+f86 (unsigned short int x, unsigned long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) + (x >> y);
+}
+
+unsigned char
+f87 (unsigned char x, unsigned int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ - 1))) + (x >> y);
+}
+
+unsigned char
+f88 (unsigned char x, unsigned long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ - 1))) + (x >> y);
+}
+
+unsigned int
+f89 (unsigned int x, unsigned int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) + (x >> y);
+}
+
+unsigned int
+f90 (unsigned int x, unsigned long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) + (x >> y);
+}
+
+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);
+}
+
+unsigned short int
+f94 (unsigned short int x, unsigned long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) + (x >> y);
+}
+
+unsigned char
+f95 (unsigned char x, unsigned int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) + (x >> y);
+}
+
+unsigned char
+f96 (unsigned char x, unsigned long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) + (x >> y);
+}
--- gcc/testsuite/c-c++-common/rotate-2b.c.jj	2013-05-11 09:46:48.588912339 +0200
+++ gcc/testsuite/c-c++-common/rotate-2b.c	2013-05-11 10:19:22.767376497 +0200
@@ -0,0 +1,49 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -Wno-overflow" } */
+
+extern
+#ifdef __cplusplus
+"C"
+#endif
+void abort (void);
+
+#ifndef ROTATE_N
+#define ROTATE_N "rotate-2.c"
+#endif
+
+#include ROTATE_N
+
+unsigned int expected[] = {
+0x12345678, 0x12345678, 0x2468acf0, 0x91a2b3c, 0x5678, 0x5678, 0x78, 0x78,
+0x12345678, 0x12345678, 0x2468acf0, 0x91a2b3c, 0x5678, 0x5678, 0x78, 0x78,
+0x0, 0x0, 0x2468acf0, 0x91a2b3c, 0x0, 0x0, 0x0, 0x0,
+0x0, 0x0, 0x2468acf0, 0x91a2b3c, 0x0, 0x0, 0x0, 0x0,
+0x12345678, 0x12345678, 0x91a2b3c, 0x2468acf0, 0x5678, 0x5678, 0x78, 0x78,
+0x12345678, 0x12345678, 0x91a2b3c, 0x2468acf0, 0x5678, 0x5678, 0x78, 0x78,
+0x0, 0x0, 0x91a2b3c, 0x2468acf0, 0x0, 0x0, 0x0, 0x0,
+0x0, 0x0, 0x91a2b3c, 0x2468acf0, 0x0, 0x0, 0x0, 0x0,
+0x2468acf0, 0x2468acf0, 0x2468acf0, 0x91a2b3c, 0xacf0, 0xacf0, 0xf0, 0xf0,
+0x2468acf0, 0x2468acf0, 0x2468acf0, 0x91a2b3c, 0xacf0, 0xacf0, 0xf0, 0xf0,
+0x2468acf0, 0x2468acf0, 0x91a2b3c, 0x2468acf0, 0xacf0, 0xacf0, 0xf0, 0xf0,
+0x2468acf0, 0x2468acf0, 0x91a2b3c, 0x2468acf0, 0xacf0, 0xacf0, 0xf0, 0xf0 };
+
+#define F(n) __typeof (f##n) f##n __attribute__((noinline, noclone));
+#define D(n) F(n##0) F(n##1) F(n##2) F(n##3) F(n##4) F(n##5) F(n##6) F(n##7) F(n##8) F(n##9)
+#define ALL \
+F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(8) F(9) \
+D(1) D(2) D(3) D(4) D(5) D(6) D(7) D(8) \
+F(90) F(91) F(92) F(93) F(94) F(95) F(96)
+ALL
+
+int
+main ()
+{
+#if __CHAR_BIT__ != 8 || __SIZEOF_SHORT__ != 2 || __SIZEOF_INT__ != 4
+  return 0;
+#else
+#undef F
+#define F(n) if ((unsigned int) f##n (0x12345678U, 0) != expected[n - 1]) abort ();
+  ALL
+  return 0;
+#endif
+}
--- gcc/testsuite/c-c++-common/rotate-3.c.jj	2013-05-10 10:39:13.000000000 +0200
+++ gcc/testsuite/c-c++-common/rotate-3.c	2013-05-11 10:14:41.003101647 +0200
@@ -1,7 +1,7 @@
 /* Check rotate pattern detection.  */
 /* { dg-do compile } */
 /* { dg-options "-O2 -fdump-tree-optimized" } */
-/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 64 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 96 "optimized" } } */
 /* { dg-final { cleanup-tree-dump "optimized" } } */
 
 unsigned int
@@ -387,3 +387,195 @@ f64 (unsigned char x, long int y)
 {
   return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) ^ (x >> y);
 }
+
+unsigned int
+f65 (unsigned int x, int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - y));
+}
+
+unsigned int
+f66 (unsigned int x, long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - y));
+}
+
+unsigned int
+f67 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << 1) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - 1));
+}
+
+unsigned int
+f68 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - 1)) + (x >> 1);
+}
+
+unsigned short int
+f69 (unsigned short int x, int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_SHORT__ - y));
+}
+
+unsigned short int
+f70 (unsigned short int x, long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_SHORT__ - y));
+}
+
+unsigned char
+f71 (unsigned char x, int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ - y));
+}
+
+unsigned char
+f72 (unsigned char x, long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ - y));
+}
+
+unsigned int
+f73 (unsigned int x, int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - y));
+}
+
+unsigned int
+f74 (unsigned int x, long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - y));
+}
+
+unsigned int
+f75 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << 1) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - 1));
+}
+
+unsigned int
+f76 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - 1)) + (x >> 1);
+}
+
+unsigned short int
+f77 (unsigned short int x, int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned short) - y));
+}
+
+unsigned short int
+f78 (unsigned short int x, long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned short) - y));
+}
+
+unsigned char
+f79 (unsigned char x, int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned char) - y));
+}
+
+unsigned char
+f80 (unsigned char x, long int y)
+{
+  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned char) - y));
+}
+
+unsigned int
+f81 (unsigned int x, int y)
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - y)) + (x >> y);
+}
+
+unsigned int
+f82 (unsigned int x, long int y)
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - y)) + (x >> y);
+}
+
+unsigned int
+f83 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - 1)) + (x >> 1);
+}
+
+unsigned int
+f84 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << 1) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - 1));
+}
+
+unsigned short int
+f85 (unsigned short int x, int y)
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_SHORT__ - y)) + (x >> y);
+}
+
+unsigned short int
+f86 (unsigned short int x, long int y)
+{
+  return (x << (__CHAR_BIT__ * __SIZEOF_SHORT__ - y)) + (x >> y);
+}
+
+unsigned char
+f87 (unsigned char x, int y)
+{
+  return (x << (__CHAR_BIT__ - y)) + (x >> y);
+}
+
+unsigned char
+f88 (unsigned char x, long int y)
+{
+  return (x << (__CHAR_BIT__ - y)) + (x >> y);
+}
+
+unsigned int
+f89 (unsigned int x, int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - y)) + (x >> y);
+}
+
+unsigned int
+f90 (unsigned int x, long int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - y)) + (x >> y);
+}
+
+unsigned int
+f91 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - 1)) + (x >> 1);
+}
+
+unsigned int
+f92 (unsigned int x, int y __attribute__((unused)))
+{
+  return (x << 1) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - 1));
+}
+
+unsigned short int
+f93 (unsigned short int x, int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned short) - y)) + (x >> y);
+}
+
+unsigned short int
+f94 (unsigned short int x, long int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned short) - y)) + (x >> y);
+}
+
+unsigned char
+f95 (unsigned char x, int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) + (x >> y);
+}
+
+unsigned char
+f96 (unsigned char x, long int y)
+{
+  return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) + (x >> y);
+}
--- gcc/testsuite/c-c++-common/rotate-4.c.jj	2013-05-10 10:39:13.000000000 +0200
+++ gcc/testsuite/c-c++-common/rotate-4.c	2013-05-11 10:35:56.784601368 +0200
@@ -1,7 +1,9 @@
 /* Check rotate pattern detection.  */
 /* { dg-do compile } */
 /* { dg-options "-O2 -fdump-tree-optimized" } */
-/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 64 "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" } } */
 /* { dg-final { cleanup-tree-dump "optimized" } } */
 
 unsigned int
@@ -387,3 +389,195 @@ f64 (unsigned char x, long int y)
 {
   return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) ^ (x >> y);
 }
+
+unsigned int
+f65 (unsigned int x, int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
+}
+
+unsigned int
+f66 (unsigned int x, long int y)
+{
+  return (x << y) + (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, int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
+}
+
+unsigned short int
+f70 (unsigned short int x, long int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
+}
+
+unsigned char
+f71 (unsigned char x, int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ - 1)));
+}
+
+unsigned char
+f72 (unsigned char x, long int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ - 1)));
+}
+
+unsigned int
+f73 (unsigned int x, int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
+}
+
+unsigned int
+f74 (unsigned int x, long int y)
+{
+  return (x << y) + (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, int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
+}
+
+unsigned short int
+f78 (unsigned short int x, long int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
+}
+
+unsigned char
+f79 (unsigned char x, int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
+}
+
+unsigned char
+f80 (unsigned char x, long int y)
+{
+  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
+}
+
+unsigned int
+f81 (unsigned int x, int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >> y);
+}
+
+unsigned int
+f82 (unsigned int x, long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >> y);
+}
+
+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, int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) + (x >> y);
+}
+
+unsigned short int
+f86 (unsigned short int x, long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) + (x >> y);
+}
+
+unsigned char
+f87 (unsigned char x, int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ - 1))) + (x >> y);
+}
+
+unsigned char
+f88 (unsigned char x, long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ - 1))) + (x >> y);
+}
+
+unsigned int
+f89 (unsigned int x, int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) + (x >> y);
+}
+
+unsigned int
+f90 (unsigned int x, long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) + (x >> y);
+}
+
+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, int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) + (x >> y);
+}
+
+unsigned short int
+f94 (unsigned short int x, long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) + (x >> y);
+}
+
+unsigned char
+f95 (unsigned char x, int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) + (x >> y);
+}
+
+unsigned char
+f96 (unsigned char x, long int y)
+{
+  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) + (x >> y);
+}
--- gcc/testsuite/c-c++-common/rotate-4b.c.jj	2013-05-11 10:19:37.190287705 +0200
+++ gcc/testsuite/c-c++-common/rotate-4b.c	2013-05-11 10:31:46.249115585 +0200
@@ -0,0 +1,6 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -Wno-overflow" } */
+
+#define ROTATE_N "rotate-4.c"
+
+#include "rotate-2b.c"
--- gcc/testsuite/c-c++-common/rotate-5.c.jj	2013-05-11 10:20:17.094179336 +0200
+++ gcc/testsuite/c-c++-common/rotate-5.c	2013-05-11 10:29:06.360066035 +0200
@@ -0,0 +1,43 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+extern
+#ifdef __cplusplus
+"C"
+#endif
+void abort (void);
+
+#if __CHAR_BIT__ * __SIZEOF_LONG_LONG__ == 64
+__attribute__((noinline, noclone))
+unsigned long long
+f1 (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)
+{
+  return (x << y) | (x >> ((-y) & 128));
+}
+#endif
+#endif
+
+int
+main ()
+{
+#if __CHAR_BIT__ * __SIZEOF_LONG_LONG__ == 64
+  if (f1 (0x123456789abcdef0ULL, 0) != 0x123456789abcdef0ULL)
+    abort ();
+#if __CHAR_BIT__ * __SIZEOF_INT128__ == 128
+  if (f2 ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
+	  | 0x0fedcba987654321ULL, 0)
+      != ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
+          | 0x0fedcba987654321ULL))
+    abort ();
+#endif
+#endif
+  return 0;
+}


	Jakub

Re: [PATCH] Fix up rotate expansion (take 2)

[Richard Biener]

On Sat, 11 May 2013, Jakub Jelinek wrote:

> On Sat, May 11, 2013 at 09:05:52AM +0200, Jakub Jelinek wrote:
> > > Seems that we ought to have a testcase, even though it probably
> > > means scanning the tree dumps to pick up the undefined behaviour.
> > > Approved with a testcase.
> > 
> > I have added lots of testcases recently, for rotation by zero perhaps
> > something similar to rotate-1a.c from above can be added as rotate-2b.c
> > and rotate-4b.c, and test zero rotation.
> 
> Thanks for forcing me to do more testcases, I've actually found a serious
> bug in my recent patch.  The (X << Y) OP (X >> ((-Y) & (B - 1))) style
> patterns can only be recognized as rotates if OP is |, because
> while they act as rotates for Y != 0, they act differently for Y == 0.
> For (X << Y) OP (X >> (B - Y)) that is not an issue, because for Y == 0
> they trigger undefined behavior.
> 
> Fixed thusly, plus added coverage for rotates by 0.  And rotate-5.c
> testcase is to test the expmed.c change.

Ok.

Thanks,
Richard.

> 2013-05-10  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/45216
> 	PR tree-optimization/57157
> 	* tree-ssa-forwprop.c (simplify_rotate): Only recognize
> 	the (-Y) & (B - 1) variant if OP is |.
> 	* expmed.c (expand_shift_1): For rotations by const0_rtx just
> 	return shifted.  Use (-op1) & (prec - 1) as other_amount
> 	instead of prec - op1.
> 
> 	* c-c++-common/rotate-1.c: Add 32 tests with +.
> 	* c-c++-common/rotate-1a.c: Adjust.
> 	* c-c++-common/rotate-2.c: Add 32 tests with +, expect
> 	only 48 rotates.
> 	* c-c++-common/rotate-2b.c: New test.
> 	* c-c++-common/rotate-3.c: Add 32 tests with +.
> 	* c-c++-common/rotate-4.c: Add 32 tests with +, expect
> 	only 48 rotates.
> 	* c-c++-common/rotate-4b.c: New test.
> 	* c-c++-common/rotate-5.c: New test.
> 
> --- gcc/tree-ssa-forwprop.c.jj	2013-05-10 10:39:13.000000000 +0200
> +++ gcc/tree-ssa-forwprop.c	2013-05-11 09:57:39.627194037 +0200
> @@ -2135,10 +2135,10 @@ simplify_bitwise_binary (gimple_stmt_ite
>     (X << (int) Y) OP (X >> (int) (B - Y))
>     ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
>     ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) (B - Y)))
> -   (X << Y) OP (X >> ((-Y) & (B - 1)))
> -   (X << (int) Y) OP (X >> (int) ((-Y) & (B - 1)))
> -   ((T) ((T2) X << Y)) OP ((T) ((T2) X >> ((-Y) & (B - 1))))
> -   ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
> +   (X << Y) | (X >> ((-Y) & (B - 1)))
> +   (X << (int) Y) | (X >> (int) ((-Y) & (B - 1)))
> +   ((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
> @@ -2293,7 +2293,8 @@ simplify_rotate (gimple_stmt_iterator *g
>  		 && host_integerp (cdef_arg2[i], 0)
>  		 && tree_low_cst (cdef_arg2[i], 0)
>  		    == TYPE_PRECISION (rtype) - 1
> -		 && TREE_CODE (cdef_arg1[i]) == SSA_NAME)
> +		 && TREE_CODE (cdef_arg1[i]) == SSA_NAME
> +		 && gimple_assign_rhs_code (stmt) == BIT_IOR_EXPR)
>  	  {
>  	    tree tem;
>  	    enum tree_code code;
> --- gcc/expmed.c.jj	2013-05-07 10:26:46.000000000 +0200
> +++ gcc/expmed.c	2013-05-11 09:11:54.087412982 +0200
> @@ -2166,7 +2166,8 @@ expand_shift_1 (enum tree_code code, enu
>  	    {
>  	      /* If we have been unable to open-code this by a rotation,
>  		 do it as the IOR of two shifts.  I.e., to rotate A
> -		 by N bits, compute (A << N) | ((unsigned) A >> (C - N))
> +		 by N bits, compute
> +		 (A << N) | ((unsigned) A >> ((-N) & (C - 1)))
>  		 where C is the bitsize of A.
>  
>  		 It is theoretically possible that the target machine might
> @@ -2181,14 +2182,22 @@ expand_shift_1 (enum tree_code code, enu
>  	      rtx temp1;
>  
>  	      new_amount = op1;
> -	      if (CONST_INT_P (op1))
> +	      if (op1 == const0_rtx)
> +		return shifted;
> +	      else if (CONST_INT_P (op1))
>  		other_amount = GEN_INT (GET_MODE_BITSIZE (mode)
>  					- INTVAL (op1));
>  	      else
> -		other_amount
> -		  = simplify_gen_binary (MINUS, GET_MODE (op1),
> -					 GEN_INT (GET_MODE_PRECISION (mode)),
> -					 op1);
> +		{
> +		  other_amount
> +		    = simplify_gen_unary (NEG, GET_MODE (op1),
> +					  op1, GET_MODE (op1));
> +		  other_amount
> +		    = simplify_gen_binary (AND, GET_MODE (op1),
> +					   other_amount,
> +					   GEN_INT (GET_MODE_PRECISION (mode)
> +						    - 1));
> +		}
>  
>  	      shifted = force_reg (mode, shifted);
>  
> --- gcc/testsuite/c-c++-common/rotate-1.c.jj	2013-05-10 10:39:13.000000000 +0200
> +++ gcc/testsuite/c-c++-common/rotate-1.c	2013-05-11 10:11:22.725252954 +0200
> @@ -1,7 +1,7 @@
>  /* Check rotate pattern detection.  */
>  /* { dg-do compile } */
>  /* { dg-options "-O2 -fdump-tree-optimized" } */
> -/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 64 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 96 "optimized" } } */
>  /* { dg-final { cleanup-tree-dump "optimized" } } */
>  
>  unsigned int
> @@ -387,3 +387,195 @@ f64 (unsigned char x, unsigned long int
>  {
>    return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) ^ (x >> y);
>  }
> +
> +unsigned int
> +f65 (unsigned int x, unsigned int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - y));
> +}
> +
> +unsigned int
> +f66 (unsigned int x, unsigned long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - y));
> +}
> +
> +unsigned int
> +f67 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << 1) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - 1));
> +}
> +
> +unsigned int
> +f68 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - 1)) + (x >> 1);
> +}
> +
> +unsigned short int
> +f69 (unsigned short int x, unsigned int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_SHORT__ - y));
> +}
> +
> +unsigned short int
> +f70 (unsigned short int x, unsigned long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_SHORT__ - y));
> +}
> +
> +unsigned char
> +f71 (unsigned char x, unsigned int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ - y));
> +}
> +
> +unsigned char
> +f72 (unsigned char x, unsigned long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ - y));
> +}
> +
> +unsigned int
> +f73 (unsigned int x, unsigned int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - y));
> +}
> +
> +unsigned int
> +f74 (unsigned int x, unsigned long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - y));
> +}
> +
> +unsigned int
> +f75 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << 1) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - 1));
> +}
> +
> +unsigned int
> +f76 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - 1)) + (x >> 1);
> +}
> +
> +unsigned short int
> +f77 (unsigned short int x, unsigned int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned short) - y));
> +}
> +
> +unsigned short int
> +f78 (unsigned short int x, unsigned long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned short) - y));
> +}
> +
> +unsigned char
> +f79 (unsigned char x, unsigned int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned char) - y));
> +}
> +
> +unsigned char
> +f80 (unsigned char x, unsigned long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned char) - y));
> +}
> +
> +unsigned int
> +f81 (unsigned int x, unsigned int y)
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - y)) + (x >> y);
> +}
> +
> +unsigned int
> +f82 (unsigned int x, unsigned long int y)
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - y)) + (x >> y);
> +}
> +
> +unsigned int
> +f83 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - 1)) + (x >> 1);
> +}
> +
> +unsigned int
> +f84 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << 1) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - 1));
> +}
> +
> +unsigned short int
> +f85 (unsigned short int x, unsigned int y)
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_SHORT__ - y)) + (x >> y);
> +}
> +
> +unsigned short int
> +f86 (unsigned short int x, unsigned long int y)
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_SHORT__ - y)) + (x >> y);
> +}
> +
> +unsigned char
> +f87 (unsigned char x, unsigned int y)
> +{
> +  return (x << (__CHAR_BIT__ - y)) + (x >> y);
> +}
> +
> +unsigned char
> +f88 (unsigned char x, unsigned long int y)
> +{
> +  return (x << (__CHAR_BIT__ - y)) + (x >> y);
> +}
> +
> +unsigned int
> +f89 (unsigned int x, unsigned int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - y)) + (x >> y);
> +}
> +
> +unsigned int
> +f90 (unsigned int x, unsigned long int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - y)) + (x >> y);
> +}
> +
> +unsigned int
> +f91 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - 1)) + (x >> 1);
> +}
> +
> +unsigned int
> +f92 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << 1) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - 1));
> +}
> +
> +unsigned short int
> +f93 (unsigned short int x, unsigned int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned short) - y)) + (x >> y);
> +}
> +
> +unsigned short int
> +f94 (unsigned short int x, unsigned long int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned short) - y)) + (x >> y);
> +}
> +
> +unsigned char
> +f95 (unsigned char x, unsigned int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) + (x >> y);
> +}
> +
> +unsigned char
> +f96 (unsigned char x, unsigned long int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) + (x >> y);
> +}
> --- gcc/testsuite/c-c++-common/rotate-1a.c.jj	2013-05-10 10:39:13.000000000 +0200
> +++ gcc/testsuite/c-c++-common/rotate-1a.c	2013-05-11 10:16:15.702552070 +0200
> @@ -21,13 +21,18 @@ unsigned int expected[] = {
>  0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf,
>  0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf,
>  0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf,
> +0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf,
> +0x91a2b3c0, 0x91a2b3c0, 0x2468acf0, 0x91a2b3c, 0xb3c2, 0xb3c2, 0xc3, 0xc3,
> +0x91a2b3c0, 0x91a2b3c0, 0x2468acf0, 0x91a2b3c, 0xb3c2, 0xb3c2, 0xc3, 0xc3,
> +0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf,
>  0x2468acf, 0x2468acf, 0x91a2b3c, 0x2468acf0, 0xacf, 0xacf, 0xf, 0xf };
>  
>  #define F(n) __typeof (f##n) f##n __attribute__((noinline, noclone));
>  #define D(n) F(n##0) F(n##1) F(n##2) F(n##3) F(n##4) F(n##5) F(n##6) F(n##7) F(n##8) F(n##9)
>  #define ALL \
>  F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(8) F(9) \
> -D(1) D(2) D(3) D(4) D(5) F(60) F(61) F(62) F(63) F(64)
> +D(1) D(2) D(3) D(4) D(5) D(6) D(7) D(8) \
> +F(90) F(91) F(92) F(93) F(94) F(95) F(96)
>  ALL
>  
>  int
> --- gcc/testsuite/c-c++-common/rotate-2.c.jj	2013-05-10 10:39:13.000000000 +0200
> +++ gcc/testsuite/c-c++-common/rotate-2.c	2013-05-11 10:35:38.127716820 +0200
> @@ -1,7 +1,9 @@
>  /* Check rotate pattern detection.  */
>  /* { dg-do compile } */
>  /* { dg-options "-O2 -fdump-tree-optimized" } */
> -/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 64 "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" } } */
>  /* { dg-final { cleanup-tree-dump "optimized" } } */
>  
>  unsigned int
> @@ -387,3 +389,195 @@ f64 (unsigned char x, unsigned long int
>  {
>    return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) ^ (x >> y);
>  }
> +
> +unsigned int
> +f65 (unsigned int x, unsigned int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
> +}
> +
> +unsigned int
> +f66 (unsigned int x, unsigned long int y)
> +{
> +  return (x << y) + (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) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
> +}
> +
> +unsigned short int
> +f70 (unsigned short int x, unsigned long int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
> +}
> +
> +unsigned char
> +f71 (unsigned char x, unsigned int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ - 1)));
> +}
> +
> +unsigned char
> +f72 (unsigned char x, unsigned long int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ - 1)));
> +}
> +
> +unsigned int
> +f73 (unsigned int x, unsigned int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
> +}
> +
> +unsigned int
> +f74 (unsigned int x, unsigned long int y)
> +{
> +  return (x << y) + (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) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
> +}
> +
> +unsigned short int
> +f78 (unsigned short int x, unsigned long int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
> +}
> +
> +unsigned char
> +f79 (unsigned char x, unsigned int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
> +}
> +
> +unsigned char
> +f80 (unsigned char x, unsigned long int y)
> +{
> +  return (x << y) + (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);
> +}
> +
> +unsigned int
> +f82 (unsigned int x, unsigned long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >> y);
> +}
> +
> +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);
> +}
> +
> +unsigned short int
> +f86 (unsigned short int x, unsigned long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) + (x >> y);
> +}
> +
> +unsigned char
> +f87 (unsigned char x, unsigned int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ - 1))) + (x >> y);
> +}
> +
> +unsigned char
> +f88 (unsigned char x, unsigned long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ - 1))) + (x >> y);
> +}
> +
> +unsigned int
> +f89 (unsigned int x, unsigned int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) + (x >> y);
> +}
> +
> +unsigned int
> +f90 (unsigned int x, unsigned long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) + (x >> y);
> +}
> +
> +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);
> +}
> +
> +unsigned short int
> +f94 (unsigned short int x, unsigned long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) + (x >> y);
> +}
> +
> +unsigned char
> +f95 (unsigned char x, unsigned int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) + (x >> y);
> +}
> +
> +unsigned char
> +f96 (unsigned char x, unsigned long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) + (x >> y);
> +}
> --- gcc/testsuite/c-c++-common/rotate-2b.c.jj	2013-05-11 09:46:48.588912339 +0200
> +++ gcc/testsuite/c-c++-common/rotate-2b.c	2013-05-11 10:19:22.767376497 +0200
> @@ -0,0 +1,49 @@
> +/* { dg-do run } */
> +/* { dg-options "-O2 -Wno-overflow" } */
> +
> +extern
> +#ifdef __cplusplus
> +"C"
> +#endif
> +void abort (void);
> +
> +#ifndef ROTATE_N
> +#define ROTATE_N "rotate-2.c"
> +#endif
> +
> +#include ROTATE_N
> +
> +unsigned int expected[] = {
> +0x12345678, 0x12345678, 0x2468acf0, 0x91a2b3c, 0x5678, 0x5678, 0x78, 0x78,
> +0x12345678, 0x12345678, 0x2468acf0, 0x91a2b3c, 0x5678, 0x5678, 0x78, 0x78,
> +0x0, 0x0, 0x2468acf0, 0x91a2b3c, 0x0, 0x0, 0x0, 0x0,
> +0x0, 0x0, 0x2468acf0, 0x91a2b3c, 0x0, 0x0, 0x0, 0x0,
> +0x12345678, 0x12345678, 0x91a2b3c, 0x2468acf0, 0x5678, 0x5678, 0x78, 0x78,
> +0x12345678, 0x12345678, 0x91a2b3c, 0x2468acf0, 0x5678, 0x5678, 0x78, 0x78,
> +0x0, 0x0, 0x91a2b3c, 0x2468acf0, 0x0, 0x0, 0x0, 0x0,
> +0x0, 0x0, 0x91a2b3c, 0x2468acf0, 0x0, 0x0, 0x0, 0x0,
> +0x2468acf0, 0x2468acf0, 0x2468acf0, 0x91a2b3c, 0xacf0, 0xacf0, 0xf0, 0xf0,
> +0x2468acf0, 0x2468acf0, 0x2468acf0, 0x91a2b3c, 0xacf0, 0xacf0, 0xf0, 0xf0,
> +0x2468acf0, 0x2468acf0, 0x91a2b3c, 0x2468acf0, 0xacf0, 0xacf0, 0xf0, 0xf0,
> +0x2468acf0, 0x2468acf0, 0x91a2b3c, 0x2468acf0, 0xacf0, 0xacf0, 0xf0, 0xf0 };
> +
> +#define F(n) __typeof (f##n) f##n __attribute__((noinline, noclone));
> +#define D(n) F(n##0) F(n##1) F(n##2) F(n##3) F(n##4) F(n##5) F(n##6) F(n##7) F(n##8) F(n##9)
> +#define ALL \
> +F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(8) F(9) \
> +D(1) D(2) D(3) D(4) D(5) D(6) D(7) D(8) \
> +F(90) F(91) F(92) F(93) F(94) F(95) F(96)
> +ALL
> +
> +int
> +main ()
> +{
> +#if __CHAR_BIT__ != 8 || __SIZEOF_SHORT__ != 2 || __SIZEOF_INT__ != 4
> +  return 0;
> +#else
> +#undef F
> +#define F(n) if ((unsigned int) f##n (0x12345678U, 0) != expected[n - 1]) abort ();
> +  ALL
> +  return 0;
> +#endif
> +}
> --- gcc/testsuite/c-c++-common/rotate-3.c.jj	2013-05-10 10:39:13.000000000 +0200
> +++ gcc/testsuite/c-c++-common/rotate-3.c	2013-05-11 10:14:41.003101647 +0200
> @@ -1,7 +1,7 @@
>  /* Check rotate pattern detection.  */
>  /* { dg-do compile } */
>  /* { dg-options "-O2 -fdump-tree-optimized" } */
> -/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 64 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 96 "optimized" } } */
>  /* { dg-final { cleanup-tree-dump "optimized" } } */
>  
>  unsigned int
> @@ -387,3 +387,195 @@ f64 (unsigned char x, long int y)
>  {
>    return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) ^ (x >> y);
>  }
> +
> +unsigned int
> +f65 (unsigned int x, int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - y));
> +}
> +
> +unsigned int
> +f66 (unsigned int x, long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - y));
> +}
> +
> +unsigned int
> +f67 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << 1) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - 1));
> +}
> +
> +unsigned int
> +f68 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - 1)) + (x >> 1);
> +}
> +
> +unsigned short int
> +f69 (unsigned short int x, int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_SHORT__ - y));
> +}
> +
> +unsigned short int
> +f70 (unsigned short int x, long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * __SIZEOF_SHORT__ - y));
> +}
> +
> +unsigned char
> +f71 (unsigned char x, int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ - y));
> +}
> +
> +unsigned char
> +f72 (unsigned char x, long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ - y));
> +}
> +
> +unsigned int
> +f73 (unsigned int x, int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - y));
> +}
> +
> +unsigned int
> +f74 (unsigned int x, long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - y));
> +}
> +
> +unsigned int
> +f75 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << 1) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - 1));
> +}
> +
> +unsigned int
> +f76 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - 1)) + (x >> 1);
> +}
> +
> +unsigned short int
> +f77 (unsigned short int x, int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned short) - y));
> +}
> +
> +unsigned short int
> +f78 (unsigned short int x, long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned short) - y));
> +}
> +
> +unsigned char
> +f79 (unsigned char x, int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned char) - y));
> +}
> +
> +unsigned char
> +f80 (unsigned char x, long int y)
> +{
> +  return (x << y) + (x >> (__CHAR_BIT__ * sizeof (unsigned char) - y));
> +}
> +
> +unsigned int
> +f81 (unsigned int x, int y)
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - y)) + (x >> y);
> +}
> +
> +unsigned int
> +f82 (unsigned int x, long int y)
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - y)) + (x >> y);
> +}
> +
> +unsigned int
> +f83 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_INT__ - 1)) + (x >> 1);
> +}
> +
> +unsigned int
> +f84 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << 1) + (x >> (__CHAR_BIT__ * __SIZEOF_INT__ - 1));
> +}
> +
> +unsigned short int
> +f85 (unsigned short int x, int y)
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_SHORT__ - y)) + (x >> y);
> +}
> +
> +unsigned short int
> +f86 (unsigned short int x, long int y)
> +{
> +  return (x << (__CHAR_BIT__ * __SIZEOF_SHORT__ - y)) + (x >> y);
> +}
> +
> +unsigned char
> +f87 (unsigned char x, int y)
> +{
> +  return (x << (__CHAR_BIT__ - y)) + (x >> y);
> +}
> +
> +unsigned char
> +f88 (unsigned char x, long int y)
> +{
> +  return (x << (__CHAR_BIT__ - y)) + (x >> y);
> +}
> +
> +unsigned int
> +f89 (unsigned int x, int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - y)) + (x >> y);
> +}
> +
> +unsigned int
> +f90 (unsigned int x, long int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - y)) + (x >> y);
> +}
> +
> +unsigned int
> +f91 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned int) - 1)) + (x >> 1);
> +}
> +
> +unsigned int
> +f92 (unsigned int x, int y __attribute__((unused)))
> +{
> +  return (x << 1) + (x >> (__CHAR_BIT__ * sizeof (unsigned int) - 1));
> +}
> +
> +unsigned short int
> +f93 (unsigned short int x, int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned short) - y)) + (x >> y);
> +}
> +
> +unsigned short int
> +f94 (unsigned short int x, long int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned short) - y)) + (x >> y);
> +}
> +
> +unsigned char
> +f95 (unsigned char x, int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) + (x >> y);
> +}
> +
> +unsigned char
> +f96 (unsigned char x, long int y)
> +{
> +  return (x << (__CHAR_BIT__ * sizeof (unsigned char) - y)) + (x >> y);
> +}
> --- gcc/testsuite/c-c++-common/rotate-4.c.jj	2013-05-10 10:39:13.000000000 +0200
> +++ gcc/testsuite/c-c++-common/rotate-4.c	2013-05-11 10:35:56.784601368 +0200
> @@ -1,7 +1,9 @@
>  /* Check rotate pattern detection.  */
>  /* { dg-do compile } */
>  /* { dg-options "-O2 -fdump-tree-optimized" } */
> -/* { dg-final { scan-tree-dump-times "r\[<>]\[<>]" 64 "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" } } */
>  /* { dg-final { cleanup-tree-dump "optimized" } } */
>  
>  unsigned int
> @@ -387,3 +389,195 @@ f64 (unsigned char x, long int y)
>  {
>    return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) ^ (x >> y);
>  }
> +
> +unsigned int
> +f65 (unsigned int x, int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1)));
> +}
> +
> +unsigned int
> +f66 (unsigned int x, long int y)
> +{
> +  return (x << y) + (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, int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
> +}
> +
> +unsigned short int
> +f70 (unsigned short int x, long int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
> +}
> +
> +unsigned char
> +f71 (unsigned char x, int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ - 1)));
> +}
> +
> +unsigned char
> +f72 (unsigned char x, long int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ - 1)));
> +}
> +
> +unsigned int
> +f73 (unsigned int x, int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1)));
> +}
> +
> +unsigned int
> +f74 (unsigned int x, long int y)
> +{
> +  return (x << y) + (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, int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
> +}
> +
> +unsigned short int
> +f78 (unsigned short int x, long int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
> +}
> +
> +unsigned char
> +f79 (unsigned char x, int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
> +}
> +
> +unsigned char
> +f80 (unsigned char x, long int y)
> +{
> +  return (x << y) + (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
> +}
> +
> +unsigned int
> +f81 (unsigned int x, int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >> y);
> +}
> +
> +unsigned int
> +f82 (unsigned int x, long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_INT__ - 1))) + (x >> y);
> +}
> +
> +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, int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) + (x >> y);
> +}
> +
> +unsigned short int
> +f86 (unsigned short int x, long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1))) + (x >> y);
> +}
> +
> +unsigned char
> +f87 (unsigned char x, int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ - 1))) + (x >> y);
> +}
> +
> +unsigned char
> +f88 (unsigned char x, long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ - 1))) + (x >> y);
> +}
> +
> +unsigned int
> +f89 (unsigned int x, int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) + (x >> y);
> +}
> +
> +unsigned int
> +f90 (unsigned int x, long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned int) - 1))) + (x >> y);
> +}
> +
> +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, int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) + (x >> y);
> +}
> +
> +unsigned short int
> +f94 (unsigned short int x, long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1))) + (x >> y);
> +}
> +
> +unsigned char
> +f95 (unsigned char x, int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) + (x >> y);
> +}
> +
> +unsigned char
> +f96 (unsigned char x, long int y)
> +{
> +  return (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1))) + (x >> y);
> +}
> --- gcc/testsuite/c-c++-common/rotate-4b.c.jj	2013-05-11 10:19:37.190287705 +0200
> +++ gcc/testsuite/c-c++-common/rotate-4b.c	2013-05-11 10:31:46.249115585 +0200
> @@ -0,0 +1,6 @@
> +/* { dg-do run } */
> +/* { dg-options "-O2 -Wno-overflow" } */
> +
> +#define ROTATE_N "rotate-4.c"
> +
> +#include "rotate-2b.c"
> --- gcc/testsuite/c-c++-common/rotate-5.c.jj	2013-05-11 10:20:17.094179336 +0200
> +++ gcc/testsuite/c-c++-common/rotate-5.c	2013-05-11 10:29:06.360066035 +0200
> @@ -0,0 +1,43 @@
> +/* { dg-do run } */
> +/* { dg-options "-O2" } */
> +
> +extern
> +#ifdef __cplusplus
> +"C"
> +#endif
> +void abort (void);
> +
> +#if __CHAR_BIT__ * __SIZEOF_LONG_LONG__ == 64
> +__attribute__((noinline, noclone))
> +unsigned long long
> +f1 (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)
> +{
> +  return (x << y) | (x >> ((-y) & 128));
> +}
> +#endif
> +#endif
> +
> +int
> +main ()
> +{
> +#if __CHAR_BIT__ * __SIZEOF_LONG_LONG__ == 64
> +  if (f1 (0x123456789abcdef0ULL, 0) != 0x123456789abcdef0ULL)
> +    abort ();
> +#if __CHAR_BIT__ * __SIZEOF_INT128__ == 128
> +  if (f2 ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
> +	  | 0x0fedcba987654321ULL, 0)
> +      != ((((unsigned __int128) 0x123456789abcdef0ULL) << 64)
> +          | 0x0fedcba987654321ULL))
> +    abort ();
> +#endif
> +#endif
> +  return 0;
> +}
> 
> 
> 	Jakub
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend

Re: [PATCH] Fix up rotate expansion (take 2)

[DJ Delorie]

Doing some work on the msp430 failures, I discovered that this patch:

> --- gcc/expmed.c.jj	2013-05-07 10:26:46.000000000 +0200
> +++ gcc/expmed.c	2013-05-11 09:11:54.087412982 +0200
> @@ -2181,14 +2182,22 @@ expand_shift_1 (enum tree_code code, enu
>  	      rtx temp1;
>  
>  	      new_amount = op1;
> -	      if (CONST_INT_P (op1))
> +	      if (op1 == const0_rtx)
> +		return shifted;
> +	      else if (CONST_INT_P (op1))
>  		other_amount = GEN_INT (GET_MODE_BITSIZE (mode)
>  					- INTVAL (op1));
>  	      else
> -		other_amount
> -		  = simplify_gen_binary (MINUS, GET_MODE (op1),
> -					 GEN_INT (GET_MODE_PRECISION (mode)),
> -					 op1);
> +		{
> +		  other_amount
> +		    = simplify_gen_unary (NEG, GET_MODE (op1),
> +					  op1, GET_MODE (op1));
> +		  other_amount
> +		    = simplify_gen_binary (AND, GET_MODE (op1),
> +					   other_amount,
> +					   GEN_INT (GET_MODE_PRECISION (mode)
> +						    - 1));
> +		}
>  
>  	      shifted = force_reg (mode, shifted);
>  

causes an ICE in gcc.c-torture/execute/20020226-1.c, which we tried to
avoid by adding an "addneghi" pattern (which itself has a bug, hence me
investigating).

It seems like the code creates an (and (neg ...)) RTL pattern in
HImode.  If you try to do an SImode shift, that pattern (the shift
count portion) needs to be converted HI->SI to match the msp430's
shift pattern (it's an ABI call, must be SImode).  The code that does
that hits the "convert by parts" case and just copies the generated
RTL to a register, using emit_move, *without* checking to see if it's
valid.

The result is that the (and (neg ...)) RTL makes it all the way to
recog and fails to match anything.

Where would/should such validation take place?

Reproducible if you take out the "andneghi" pattern in msp430.md

Re: [PATCH] Fix up rotate expansion (take 2)

[Jakub Jelinek]

On Wed, Apr 16, 2014 at 10:22:52PM -0400, DJ Delorie wrote:
> > +		{
> > +		  other_amount
> > +		    = simplify_gen_unary (NEG, GET_MODE (op1),
> > +					  op1, GET_MODE (op1));
> > +		  other_amount
> > +		    = simplify_gen_binary (AND, GET_MODE (op1),
> > +					   other_amount,
> > +					   GEN_INT (GET_MODE_PRECISION (mode)
> > +						    - 1));
> > +		}
> >  
> >  	      shifted = force_reg (mode, shifted);
> >  
> 
> causes an ICE in gcc.c-torture/execute/20020226-1.c, which we tried to
> avoid by adding an "addneghi" pattern (which itself has a bug, hence me
> investigating).

I don't see why you would need such an pattern.  Here is what happens
on x86_64 if I forcefully ignore the rotate patterns to excersize this code:

#8  0x0000000000a20bd7 in expand_simple_unop (mode=SImode, code=NEG, op0=0x7ffff19f7600, target=0x7ffff19fc2c0, unsignedp=0)
    at ../../gcc/optabs.c:2511
#9  0x00000000007f180c in force_operand (value=0x7ffff19fd040, target=0x7ffff19fc2c0) at ../../gcc/expr.c:7212
#10 0x00000000007f1457 in force_operand (value=0x7ffff19ddd68, target=0x0) at ../../gcc/expr.c:7154
#11 0x00000000007c8509 in force_reg (mode=SImode, x=0x7ffff19ddd68) at ../../gcc/explow.c:683
#12 0x00000000007dd502 in convert_move (to=0x7ffff19fc2a0, from=0x7ffff19ddd68, unsignedp=1) at ../../gcc/expr.c:607
#13 0x00000000007ddde0 in convert_modes (mode=QImode, oldmode=SImode, x=0x7ffff19ddd68, unsignedp=1) at ../../gcc/expr.c:798
#14 0x0000000000a1ddba in expand_binop_directly (mode=SImode, binoptab=ashl_optab, op0=0x7ffff19f78c0, op1=0x7ffff19ddd68, target=0x0, 
    unsignedp=1, methods=OPTAB_LIB_WIDEN, last=0x7ffff19f4f78) at ../../gcc/optabs.c:1437
#15 0x0000000000a1e18e in expand_binop (mode=SImode, binoptab=ashl_optab, op0=0x7ffff19f78c0, op1=0x7ffff19ddd68, target=0x0, unsignedp=1, 
    methods=OPTAB_LIB_WIDEN) at ../../gcc/optabs.c:1546
#16 0x00000000007d12c9 in expand_shift_1 (code=LSHIFT_EXPR, mode=SImode, shifted=0x7ffff19f78c0, amount=0x7ffff19ddd68, target=0x0, unsignedp=1)
    at ../../gcc/expmed.c:2287
#17 0x00000000007d1209 in expand_shift_1 (code=RROTATE_EXPR, mode=SImode, shifted=0x7ffff19f78c0, amount=0x7ffff19f7600, target=0x0, unsignedp=1)
    at ../../gcc/expmed.c:2275

i.e. the other_amount expression (and (neg ()) (const_int)) is, unless
it is a general_operand (shouldn't be usually the case) is first forced
to register with whatever mode it has (GET_MODE (op1)), and forcing it
into a register forces even the operands of the AND using force_operand,
thus separate NEG and separate AND insn, and then finally is mode converted
(zero extended or truncated) into whatever mode the shift pattern requires.

	Jakub

Re: [PATCH] Fix up rotate expansion (take 2)

[DJ Delorie]

The x86 case differs from the msp430 case in that the x86 case makes
the count a *smaller* mode (SI->QI) where the msp430 case makes it
*bigger* (HI->SI).  msp430 uses the "Handle expanding beyond a word"
case in convert_move() (msp430's word is HImode), ending in the
multiword-by-hand case.