[GSoC][match-and-simplify] add bitwise patterns to match.pd

[GSoC][match-and-simplify] add bitwise patterns to match.pd

[Prathamesh Kulkarni]

[-- Attachment #1: Type: text/plain, Size: 1244 bytes --]

Hi,
  I have tried to add few bitwise patterns from
tree-ssa-forwprop.c:simplify_bitwise_binary and the patterns
mentioned in Simplifications wiki (https://gcc.gnu.org/wiki/Simplifications).

How to write a test-case to match multiple gimple statements ?
Example: For the pattern: ~x | ~y -> ~(x & y)

test-case:
int f(int x, int y)
{
  int t1 = ~x;
  int t2 = ~y;
  return t1 | t2;
}

fdump-tree-forwprop-details output:
gimple_match_and_simplified to _5 = ~_7;
f (int x, int y)
{
  int t2;
  int t1;
  int _5;
  int _7;

  <bb 2>:
  t1_2 = ~x_1(D);
  t2_4 = ~y_3(D);
  _7 = x_1(D) & y_3(D);
  _5 = ~_7;
  return _5;

}

I suppose we want to look for matching both:
 _7 = x_1(D) & y_3(D);
  _5 = ~_7;

so only matching on "gimple_match_and_simplified to _5 = ~_7" won't
be correct ?

The patterns for x & 0 -> 0 and x & -1 -> x don't get fired from forwprop.
I tried:
int f1(int x)
{
  int t1 = 0;
  return x & t1;
}

fdump-tree-forwprop-details shows following:
;; Function f1 (f1, funcdef_no=0, decl_uid=1743, symbol_order=0)

f1 (int x)
{
  int t1;

  <bb 2>:
  return 0;

}

[gcc]
* match.pd: Add few patterns from simplify_bitwise_binary.

[gcc/testsuite]
* gcc.dg/tree-ssa/match-2.c: Add more test-cases.

Thanks and Regards,
Prathamesh

[-- Attachment #2: bitwise_patterns.patch --]
[-- Type: text/x-patch, Size: 6136 bytes --]

Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 211017)
+++ gcc/match.pd	(working copy)
@@ -189,6 +189,121 @@ to (minus @1 @0)
   if (REAL_VALUES_EQUAL (TREE_REAL_CST (@1), dconsthalf))
   (BUILT_IN_SQRT @0))
 
+/* TODO bitwise patterns:
+1] x & x -> x
+2] x & 0 -> 0
+3] x & -1 -> x
+4] x & ~x -> 0
+5] ~x & ~y -> ~(x | y)
+6] ~x | ~y -> ~(x & y)
+7] x & (~x | y) -> y & x
+8] (x | CST1) & CST2  ->  (x & CST2) | (CST1 & CST2)
+9] x ^ x -> 0
+10] x ^ ~0 -> ~x
+11] (x | y) & x -> x
+12] (x & y) | x -> x
+13] (~x | y) & x -> x & y
+14] (~x & y) | x -> x | y
+15] ((a & b) & ~a) & ~b -> 0
+16] ~~x -> x
+*/
+
+/* x & x -> x */
+(match_and_simplify
+  (bit_and @0 @0)
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
+  @0)
+
+/* x & ~x -> 0 */
+(match_and_simplify
+  (bit_and @0 (bit_not @0))
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
+  { build_int_cst (TREE_TYPE (@0), 0); })
+
+/* x & 0 -> 0 */
+(match_and_simplify
+  (bit_and @0 @1)
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && @1 == integer_zero_node)
+  { integer_zero_node; })
+
+/* x & -1 -> x */
+(match_and_simplify
+  (bit_and @0 @1)
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && @1 == integer_minus_one_node)
+  @0) 
+
+/* x ^ x -> 0 */
+(match_and_simplify
+  (bit_xor @0 @0)
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
+  { build_int_cst (TREE_TYPE (@0), 0); })
+
+/* ~x & ~y -> ~(x | y) */
+(match_and_simplify
+  (bit_and (bit_not @0) (bit_not @1))
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE (@1)))
+  (bit_not (bit_ior @0 @1)))
+
+/* ~x | ~y -> ~(x & y) */
+(match_and_simplify
+  (bit_ior (bit_not @0) (bit_not @1))
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE (@1)))
+  (bit_not (bit_and @0 @1)))
+
+/* x & (~x | y) -> y & x */
+(match_and_simplify
+  (bit_and @0 (bit_ior (bit_not @0) @1))
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE (@1)))
+  (bit_and @1 @0))
+
+/* (x | CST1) & CST2 -> (x & CST2) | (CST1 & CST2) */
+(match_and_simplify
+  (bit_and (bit_ior @0 INTEGER_CST_P@1) INTEGER_CST_P@2)
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
+  (bit_ior (bit_and @0 @2) (bit_and @1 @2)))
+
+/* x ^ ~0 -> ~x */
+(match_and_simplify
+  (bit_xor @0 @1)
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && (@1 == integer_minus_one_node))
+  (bit_not @0))
+
+/* (x | y) & x -> x */
+(match_and_simplify
+  (bit_and (bit_ior @0 @1) @0)
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE (@1)))
+  @0)
+
+/* (x & y) | x -> x */
+(match_and_simplify
+  (bit_ior (bit_and @0 @1) @0)
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE (@1)))
+  @0)
+
+/* (~x | y) & x -> x & y */
+(match_and_simplify
+  (bit_and (bit_ior (bit_not @0) @1) @0)
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE (@1)))
+  (bit_and @0 @1))
+
+/* (~x & y) | x -> x & y */
+(match_and_simplify
+  (bit_ior (bit_and (bit_not @0) @1) @0)
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE (@1)))
+  (bit_and @0 @1))
+
+/* ~~x -> x */
+(match_and_simplify
+  (bit_not (bit_not @0))
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
+  @0)
+
+/* ((a & b) & ~a) & ~b -> 0 */
+(match_and_simplify
+  (bit_and (bit_and (bit_and @0 @1) (bit_not @0)) (bit_not @1))
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE (@1)))
+  { integer_zero_node; })
+
 /* ????s
 
    We cannot reasonably match vector CONSTRUCTORs or vector constants
Index: gcc/testsuite/gcc.dg/tree-ssa/match-2.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/match-2.c	(revision 211017)
+++ gcc/testsuite/gcc.dg/tree-ssa/match-2.c	(working copy)
@@ -115,4 +115,97 @@ double f14(double x)
 }
 /* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\)" "forwprop1" } } */
 
+/* x & x -> x */
+int f15(int x)
+{
+  int t1 = x;
+  return t1 & x;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* x & ~x -> 0 */
+int f16(int x)
+{
+  int t1 = ~x;
+  return t1 & x;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= 0" "forwprop1" } } */
+
+/* x ^ x -> 0 */
+int f17(int x)
+{
+  int t1 = x;
+  return t1 ^ x;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= 0" "forwprop1" } } */
+
+/* ~~x -> 0 */
+int f18(int x)
+{
+  int t1 = ~x;
+  return ~t1;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* (x | y) & x -> x */
+int f19(int x, int y)
+{
+  int t1 = x | y;
+  return t1 & x;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* (x & y) | x -> x */
+int f20(int x, int y)
+{
+  int t1 = x & y;
+  return t1 | x;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* (~x & y) | x -> x & y */
+int f21(int x, int y)
+{
+  int t1 = ~x;
+  int t2 = t1 & y;
+  return t2 | x;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\) & y_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* (~x | y) & x -> x & y */
+int f22(int x, int y)
+{
+  int t1 = ~x;
+  int t2 = t1 | y;
+  return t2 & x;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\) & y_\\d\+\\(D\\)" "forwprop1" } } */
+
+/*  ((x & y) & ~x) & ~y -> 0 */
+int f23(int x, int y)
+{
+  int t1 = x & y;
+  int t2 = ~x;
+  int t3 = t1 & t2;
+  int t4 = ~y;
+  return t3 & t4;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= 0" "forwprop1" } } */
+
+/* x & 0 -> 0 */
+int f24(int x)
+{
+  int t1 = 0;
+  return x & t1;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= 0" "forwprop1" } } */
+
+/* x & -1 -> x */
+int f25(int x)
+{
+  int t1 = -1;
+  return x & t1;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\)" "forwprop1" } } */
+
 /* { dg-final { cleanup-tree-dump "forwprop2" } } */

Re: [GSoC][match-and-simplify] add bitwise patterns to match.pd

[Richard Biener]

On Mon, Jun 2, 2014 at 1:33 PM, Prathamesh Kulkarni
<bilbotheelffriend@gmail.com> wrote:
> Hi,
>   I have tried to add few bitwise patterns from
> tree-ssa-forwprop.c:simplify_bitwise_binary and the patterns
> mentioned in Simplifications wiki (https://gcc.gnu.org/wiki/Simplifications).
>
> How to write a test-case to match multiple gimple statements ?
> Example: For the pattern: ~x | ~y -> ~(x & y)
>
> test-case:
> int f(int x, int y)
> {
>   int t1 = ~x;
>   int t2 = ~y;
>   return t1 | t2;
> }
>
> fdump-tree-forwprop-details output:
> gimple_match_and_simplified to _5 = ~_7;
> f (int x, int y)
> {
>   int t2;
>   int t1;
>   int _5;
>   int _7;
>
>   <bb 2>:
>   t1_2 = ~x_1(D);
>   t2_4 = ~y_3(D);
>   _7 = x_1(D) & y_3(D);
>   _5 = ~_7;
>   return _5;
>
> }
>
> I suppose we want to look for matching both:
>  _7 = x_1(D) & y_3(D);
>   _5 = ~_7;
>
> so only matching on "gimple_match_and_simplified to _5 = ~_7" won't
> be correct ?

Yeah, that's a forwprop debugging dump issue and/or of the API
it uses.  The gimple_match_and_simplify overload using a
gimple_stmt_iterator * inserts the other stmts before it instead
of delaying that to the caller (and gives it the chance to dump it).

You can do the old-school testing by scanning for the IL itself,
not some gimple_match_and_simplified dump.  Thus in addition
to the above also scan for

{ dg-final { scan-tree-dump "\[xy\]_\\d\+\\(D\\) & \[xy\]_\\d\+\\(D\\)" } }

> The patterns for x & 0 -> 0 and x & -1 -> x don't get fired from forwprop.
> I tried:
> int f1(int x)
> {
>   int t1 = 0;
>   return x & t1;
> }
>
> fdump-tree-forwprop-details shows following:
> ;; Function f1 (f1, funcdef_no=0, decl_uid=1743, symbol_order=0)
>
> f1 (int x)
> {
>   int t1;
>
>   <bb 2>:
>   return 0;
>
> }

That's because constant propagation (which runs before forwprop)
already simplified the statement.

I have a patch to make use of match-and-simplify from
gimple_fold_stmt_to_constant but I have to clean it up.
I'll give writing testcases a thought there (hopefully will
post and commit a patch later today).

Richard.

>
> [gcc]
> * match.pd: Add few patterns from simplify_bitwise_binary.
>
> [gcc/testsuite]
> * gcc.dg/tree-ssa/match-2.c: Add more test-cases.
>
> Thanks and Regards,
> Prathamesh

Re: [GSoC][match-and-simplify] add bitwise patterns to match.pd

[Richard Biener]

On Mon, Jun 2, 2014 at 2:53 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Jun 2, 2014 at 1:33 PM, Prathamesh Kulkarni
> <bilbotheelffriend@gmail.com> wrote:
>> Hi,
>>   I have tried to add few bitwise patterns from
>> tree-ssa-forwprop.c:simplify_bitwise_binary and the patterns
>> mentioned in Simplifications wiki (https://gcc.gnu.org/wiki/Simplifications).
>>
>> How to write a test-case to match multiple gimple statements ?
>> Example: For the pattern: ~x | ~y -> ~(x & y)
>>
>> test-case:
>> int f(int x, int y)
>> {
>>   int t1 = ~x;
>>   int t2 = ~y;
>>   return t1 | t2;
>> }
>>
>> fdump-tree-forwprop-details output:
>> gimple_match_and_simplified to _5 = ~_7;
>> f (int x, int y)
>> {
>>   int t2;
>>   int t1;
>>   int _5;
>>   int _7;
>>
>>   <bb 2>:
>>   t1_2 = ~x_1(D);
>>   t2_4 = ~y_3(D);
>>   _7 = x_1(D) & y_3(D);
>>   _5 = ~_7;
>>   return _5;
>>
>> }
>>
>> I suppose we want to look for matching both:
>>  _7 = x_1(D) & y_3(D);
>>   _5 = ~_7;
>>
>> so only matching on "gimple_match_and_simplified to _5 = ~_7" won't
>> be correct ?
>
> Yeah, that's a forwprop debugging dump issue and/or of the API
> it uses.  The gimple_match_and_simplify overload using a
> gimple_stmt_iterator * inserts the other stmts before it instead
> of delaying that to the caller (and gives it the chance to dump it).
>
> You can do the old-school testing by scanning for the IL itself,
> not some gimple_match_and_simplified dump.  Thus in addition
> to the above also scan for
>
> { dg-final { scan-tree-dump "\[xy\]_\\d\+\\(D\\) & \[xy\]_\\d\+\\(D\\)" } }
>
>> The patterns for x & 0 -> 0 and x & -1 -> x don't get fired from forwprop.
>> I tried:
>> int f1(int x)
>> {
>>   int t1 = 0;
>>   return x & t1;
>> }
>>
>> fdump-tree-forwprop-details shows following:
>> ;; Function f1 (f1, funcdef_no=0, decl_uid=1743, symbol_order=0)
>>
>> f1 (int x)
>> {
>>   int t1;
>>
>>   <bb 2>:
>>   return 0;
>>
>> }
>
> That's because constant propagation (which runs before forwprop)
> already simplified the statement.
>
> I have a patch to make use of match-and-simplify from
> gimple_fold_stmt_to_constant but I have to clean it up.
> I'll give writing testcases a thought there (hopefully will
> post and commit a patch later today).

Btw,

/* x & 0 -> 0 */
(match_and_simplify
  (bit_and @0 @1)
  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && @1 == integer_zero_node)
  { integer_zero_node; })

/* x & -1 -> x */
(match_and_simplify
  (bit_and @0 @1)
  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && @1 == integer_minus_one_node)
  @0)

are too restrictive due to comparing @1 against very special tree nodes.
The patch I just committed uses integer_zerop and integer_all_onesp
instead.

I have simplfied some of the if-exprs, operands are guaranteed
to match.  Also if we settle on the solution of providing 'type'
as the type of the outermost expression we can simplify them
as bitwise expressions don't change types.

Most of the patterns would also apply in commutated form, thus
I guess thinking of a good solution for that is next on the list
after the decision tree stuff.

/* ((a & b) & ~a) & ~b -> 0 */
(match_and_simplify
  (bit_and (bit_and (bit_and @0 @1) (bit_not @0)) (bit_not @1))
  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && INTEGRAL_TYPE_P (TREE_TYPE (@1)))
  { integer_zero_node; })

isn't this too complex and instead already (a & b) & ~a is 0?  Also
that would be still doing two steps in one as we already have
a & ~a -> 0 so the pattern (if wanted) should only do the association
(a & b) & ~a -> (a & ~a) & b?  (note that generally this is something
for a reassociation pass, not for simple pattern matching)

I have applied the patch with these changes.

Richard.


> Richard.
>
>>
>> [gcc]
>> * match.pd: Add few patterns from simplify_bitwise_binary.
>>
>> [gcc/testsuite]
>> * gcc.dg/tree-ssa/match-2.c: Add more test-cases.
>>
>> Thanks and Regards,
>> Prathamesh