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:
--- 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
! 	 is unsuccessful we will jump to the association code.  */
!       goto bit_rotate;
      case BIT_AND_EXPR:

More information about the Gcc-patches mailing list