# XOR -> Rotate

Jeffrey A Law law@cygnus.com
Thu Oct 14 01:54:00 GMT 1999

```This is similar in concept to Marc Espie's patch to combine to detect
an XOR which is really a rotate.

The difference is it works on the tree structures (ie, we turn the expression
into a rotate before we even start generating rtl).  It also catches variable
rotate expressions like this:

int rot(unsigned int a, unsigned int b, unsigned int c)
{
return((a << (32 - c)) ^ (a >> c));
}

I looked into trying to catch variable rotates in combine, but none of my
attempts actually managed to get enough information down to simplify_logical
to detect a variable rotate.

Anyway, I've already spent more time looking at this than it's ever going to
save in CPU cycles :-)

* fold-const.c (fold): Detect rotates built from BIT_XOR_EXPRs.

Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/fold-const.c,v
retrieving revision 1.76
diff -c -3 -p -r1.76 fold-const.c
*** fold-const.c	1999/09/20 17:12:03	1.76
--- fold-const.c	1999/10/14 08:48:13
*************** fold (expr)
*** 5097,5107 ****
--- 5097,5111 ----
if (t1 != NULL_TREE)
return t1;

+      bit_rotate:
/* (A << C1) | (A >> C2) if A is unsigned and C1+C2 is the size of A
is a rotate of A by C1 bits.  */
/* (A << B) | (A >> (Z - B)) if A is unsigned and Z is the size of A
is a rotate of A by B bits.  */

+       /* Both transformations noted above also apply to when the inner
+ 	 operation is an XOR.  */
+
code0 = TREE_CODE (arg0);
code1 = TREE_CODE (arg1);
if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
*************** fold (expr)
*** 5170,5176 ****
return non_lvalue (convert (type, arg0));
if (integer_all_onesp (arg1))
return fold (build1 (BIT_NOT_EXPR, type, arg0));
!       goto associate;

case BIT_AND_EXPR:
bit_and:
--- 5174,5182 ----
return non_lvalue (convert (type, arg0));
if (integer_all_onesp (arg1))
return fold (build1 (BIT_NOT_EXPR, type, arg0));
!       /* See if this can be simplified into a rotate first.  If that
!       goto bit_rotate;

case BIT_AND_EXPR:
bit_and:

```