[GSoC] doubts in writing rotate patterns

[Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>]

This patch adds the following rotate pattern:
((T) ((T2) X << CNT1)) + ((T) ((T2) X >> CNT2))     iff CNT1 + CNT2 == B

Depends on the following patch (not yet committed):
https://gcc.gnu.org/ml/gcc-patches/2014-08/msg00128.html

* genmatch.c (dt_simplify::capture_max): Change value to 6.
* match-rotate.pd: Add new rotate pattern

[gcc/testsuite/gcc.dg/tree-ssa]
 * match-rotate.c (rotate_5): New test-case.

I have come across some issues while writing the following pattern:
(X << Y) OP (X >> (B - Y))

I wrote the following pattern (assuming OP as plus)
(match_and_simplify
  (plus (lshift @0 @1)
          (rshift @0 (minus INTEGER_CST_P@2 @1))

  (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type)
       && TYPE_PRECISION (type)
             == GET_MODE_PRECISION (TYPE_MODE (type))
       && wi::eq_p (TYPE_PRECISION (type), @2))

   (lrotate @0 @1))

a) Is the condition TYPE_PRECISION (type) == GET_MODE_...()
required ? I used it because it was also used in first pattern.

I tried with the following test-case (which wasn't simplified, however
simplify_rotate simplified it correctly).

//  (X << Y) OP (X >> (B - Y))

unsigned
f (unsigned x, unsigned y)
{
  unsigned t1 = x << y;
  unsigned t2 = 32 - y;
  unsigned t3 = x >> t2;
  unsigned t4 = t1 + t3;

  return t4;
}

forwprop1 input (output of ccp1 pass):
f (unsigned int x, unsigned int y)
{
  unsigned int t4;
  unsigned int t3;
  unsigned int t2;
  unsigned int t1;
  int y.0_2;
  int t2.1_6;

  <bb 2>:
  y.0_2 = (int) y_1(D);
  t1_4 = x_3(D) << y.0_2;
  t2_5 = 32 - y_1(D);
  t2.1_6 = (int) t2_5;
  t3_7 = x_3(D) >> t2.1_6;
  t4_8 = t1_4 + t3_7;
  t4_9 = t4_8;
  return t4_9;

}

It appears that implicit casts eg - (int) y_1(D) get generated
(do lshift/rshift expect signed 2nd operand ?)
I tried with the following, however neither is this version of the
pattern matched:

/*  (X << Y) OP (X >> (B - Y)) */
(match_and_simplify
  (plus (lshift @2 (convert@0 @3))
          (rshift @2 (convert@1 (minus INTEGER_CST_P@4 @3))))
  (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type)
       && TYPE_PRECISION (type)
             == GET_MODE_PRECISION (TYPE_MODE (type))
       && wi::eq_p (TYPE_PRECISION (type), @4)))
  (lrotate @2 @3))

and different types generate different sets of gimple statements
(more implicit casts in different places),
for example with unsigned char, following input was generated for
forwprop1:

f (unsigned char x, unsigned char y)
{
  unsigned char t4;
  unsigned char t3;
  unsigned char t2;
  unsigned char t1;
  int _2;
  int _4;
  int _5;
  int _8;
  int _9;
  int _10;

  <bb 2>:
  _2 = (int) x_1(D);
  _4 = (int) y_3(D);
  _5 = _2 << _4;
  t1_6 = (unsigned char) _5;
  t2_7 = 8 - y_3(D);
  _8 = (int) x_1(D);
  _9 = (int) t2_7;
  _10 = _8 >> _9;
  t3_11 = (unsigned char) _10;
  t4_12 = t1_6 + t3_11;
  t4_13 = t4_12;
  return t4_13;

}

How to handle the pattern for different types ?

Thanks,
Prathamesh

Index: gcc/genmatch.c
===================================================================
--- gcc/genmatch.c	(revision 213343)
+++ gcc/genmatch.c	(working copy)
@@ -412,7 +412,7 @@ struct dt_operand: public dt_node
 struct dt_simplify: public dt_node
 {
   static const unsigned level_max = UINT_MAX;
-  static const unsigned capture_max = 4;
+  static const unsigned capture_max = 6;
   simplify *s; 
   unsigned pattern_no;
   dt_operand *indexes[capture_max]; 
Index: gcc/match-rotate.pd
===================================================================
--- gcc/match-rotate.pd	(revision 213343)
+++ gcc/match-rotate.pd	(working copy)
@@ -27,3 +27,14 @@ along with GCC; see the file COPYING3.
       && tree_fits_uhwi_p (@1) && tree_fits_uhwi_p (@2)
       && wi::eq_p (TYPE_PRECISION (type), wi::add (@1, @2))))
   (lrotate @0 @1)))
+
+/*  ((T) ((T2) X << CNT1)) OP ((T) ((T2) X >> CNT2)) iff CNT1 + CNT2 == B */
+(for op in plus bit_ior bit_xor
+(match_and_simplify
+  (op:c (convert@2 (lshift (convert@0 @3) INTEGER_CST_P@4))
+	(convert (rshift (convert@1 @3) INTEGER_CST_P@5)))
+  (if (types_compatible_p (TREE_TYPE (@0), TREE_TYPE (@1))
+       && TYPE_UNSIGNED (TREE_TYPE (@2))
+       && TYPE_PRECISION (TREE_TYPE (@0)) > TYPE_PRECISION (TREE_TYPE (@2))
+       && wi::eq_p (TYPE_PRECISION (TREE_TYPE (@2)), wi::add (@4, @5))))
+  (lrotate @3 @4)))
Index: gcc/testsuite/gcc.dg/tree-ssa/match-rotate.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/match-rotate.c	(revision 213343)
+++ gcc/testsuite/gcc.dg/tree-ssa/match-rotate.c	(working copy)
@@ -41,4 +41,20 @@ rotate_4 (unsigned char x)
 }
 /* { dg-final { scan-tree-dump "gimple_match_and_simplified to rotate_4_val_\\d\+ = x_\\d\+\\(D\\) r<< 5" "forwprop1" } } */
 
+/* ((T) ((T2) X << CNT1)) OP ((T) ((T2) X >> CNT2)) iff CNT1 + CNT2 == B */
+unsigned char
+rotate_5 (unsigned char x)
+{
+  unsigned short t1 = (unsigned short) x;
+  unsigned short t2 = t1 << 3;
+  unsigned char t3 = (unsigned char) t2;
+
+  unsigned short t4 = t1 >> 5;
+  unsigned char t5 = (unsigned char) t4;
+
+  unsigned char rotate_5_val = t3 + t5;
+  return rotate_5_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to rotate_5_val_\\d\+ = x_\\d\+\\(D\\) r<< 3" "forwprop1" } } */
+
 /* { dg-final { cleanup-tree-dump "forwprop1" } } */