[patch tree-ssa-forwprop]: Improve binary and/or/xor folding

[patch tree-ssa-forwprop]: Improve binary and/or/xor folding

[Kai Tietz]

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

Hello,

This patch improves via type-sinking folding of binary and, or, and
xor operations.
First we do sinking also for compatible types with same precision, as
those don't need to be preserved for these operations.
Additional try to fold patterns (TYPE) X bin-op (Y CMP Z) and (TYPE) X
bin-op !Y, if type of X is
compatible to Y.

ChangeLog gcc

2011-06-22  Kai Tietz  <ktietz@redhat.com>

	* tree-ssa-forwprop.c (simplify_bitwise_binary):
	Improve binary folding regarding casts.


ChangeLog gcc/testsuite

2011-06-22  Kai Tietz  <ktietz@redhat.com>

	* gcc.dg/binop-notand1a.c: New test.
	* gcc.dg/binop-notand2a.c: New test.
	* gcc.dg/binop-notand3a.c: New test.
	* gcc.dg/binop-notand4a.c: New test.
	* gcc.dg/binop-notand5a.c: New test.
	* gcc.dg/binop-notand6a.c: New test.

Bootstrapped and regression tested for all standard languages, Ada,
and Obj-C++. Ok for apply?

Regards,
Kai

[-- Attachment #2: fw_sink.txt --]
[-- Type: text/plain, Size: 7457 bytes --]

Index: gcc/gcc/tree-ssa-forwprop.c
===================================================================
--- gcc.orig/gcc/tree-ssa-forwprop.c	2011-06-17 11:52:51.000000000 +0200
+++ gcc/gcc/tree-ssa-forwprop.c	2011-06-22 12:36:49.432774100 +0200
@@ -1682,10 +1682,11 @@ simplify_bitwise_binary (gimple_stmt_ite
   if (CONVERT_EXPR_CODE_P (def1_code)
       && CONVERT_EXPR_CODE_P (def2_code)
       && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
-      /* Make sure that the conversion widens the operands or that it
-	 changes the operation to a bitfield precision.  */
+      /* Make sure that the conversion widens the operands, or has same
+	 precision,  or that it changes the operation to a bitfield
+	 precision.  */
       && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
-	   < TYPE_PRECISION (TREE_TYPE (arg1)))
+	   <= TYPE_PRECISION (TREE_TYPE (arg1)))
 	  || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
 	      != MODE_INT)
 	  || (TYPE_PRECISION (TREE_TYPE (arg1))
@@ -1704,6 +1705,88 @@ simplify_bitwise_binary (gimple_stmt_ite
       return true;
     }
 
+  /* Try to fold (TYPE) X op (Y CMP Z), or (TYPE) X op !Y, if type
+     of X is compatible to type of Y.  */
+  if (CONVERT_EXPR_CODE_P (def1_code)
+      && (TREE_CODE_CLASS (def2_code) == tcc_comparison
+	  || def2_code == TRUTH_NOT_EXPR)
+      && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1)))
+    {
+      tree t;
+      if (def2_code == TRUTH_NOT_EXPR)
+	t = fold_build1_loc (gimple_location (def2), def2_code,
+			     TREE_TYPE (def1_arg1), def2_arg1);
+      else
+	t = fold_build2_loc (gimple_location (def2), def2_code,
+			     TREE_TYPE (def1_arg1), def2_arg1,
+			       gimple_assign_rhs2 (def2));
+      t = fold_binary_loc (gimple_location (stmt), code,
+			   TREE_TYPE (def1_arg1), def1_arg1, t);
+      if (t && TREE_CODE (t) == INTEGER_CST)
+	{
+	  t = fold_convert (TREE_TYPE (arg1), t);
+	  gimple_assign_set_rhs_from_tree (gsi, t);
+	  update_stmt (gsi_stmt (*gsi));
+	  return true;
+        }
+      else if (t && TREE_CODE_CLASS (TREE_CODE (t)) == tcc_comparison)
+	{
+	  gimple newop;
+	  tree tem = create_tmp_reg (boolean_type_node, NULL);
+	  newop = gimple_build_assign_with_ops (TREE_CODE (t), tem,
+	  					TREE_OPERAND (t, 0),
+	  					TREE_OPERAND (t, 1));
+	  tem = make_ssa_name (tem, newop);
+	  gimple_assign_set_lhs (newop, tem);
+	  gsi_insert_before (gsi, newop, GSI_SAME_STMT);
+	  gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
+					    tem, NULL_TREE, NULL_TREE);
+	  update_stmt (gsi_stmt (*gsi));
+	  return true;
+	}
+    }
+
+  /* Try to fold (Y CMP Z) op (TYPE) X, or !Y op (TYPE) X, if type
+     of X is compatible to type of Y.  */
+  if (CONVERT_EXPR_CODE_P (def2_code)
+      && (TREE_CODE_CLASS (def1_code) == tcc_comparison
+	  || def1_code == TRUTH_NOT_EXPR)
+      && types_compatible_p (TREE_TYPE (def2_arg1), TREE_TYPE (def1_arg1)))
+    {
+      tree t;
+      if (def1_code == TRUTH_NOT_EXPR)
+	t = fold_build1_loc (gimple_location (def1), def1_code,
+			     TREE_TYPE (def2_arg1), def1_arg1);
+      else
+	t = fold_build2_loc (gimple_location (def1), def1_code,
+			     TREE_TYPE (def2_arg1), def1_arg1,
+			       gimple_assign_rhs2 (def1));
+      t = fold_binary_loc (gimple_location (stmt), code,
+			   TREE_TYPE (def2_arg1), t, def2_arg1);
+      if (t && TREE_CODE (t) == INTEGER_CST)
+	{
+	  t = fold_convert (TREE_TYPE (arg2), t);
+	  gimple_assign_set_rhs_from_tree (gsi, t);
+	  update_stmt (gsi_stmt (*gsi));
+	  return true;
+        }
+      else if (t && TREE_CODE_CLASS (TREE_CODE (t)) == tcc_comparison)
+	{
+	  gimple newop;
+	  tree tem = create_tmp_reg (boolean_type_node, NULL);
+	  newop = gimple_build_assign_with_ops (TREE_CODE (t), tem,
+	  					TREE_OPERAND (t, 0),
+	  					TREE_OPERAND (t, 1));
+	  tem = make_ssa_name (tem, newop);
+	  gimple_assign_set_lhs (newop, tem);
+	  gsi_insert_before (gsi, newop, GSI_SAME_STMT);
+	  gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
+					    tem, NULL_TREE, NULL_TREE);
+	  update_stmt (gsi_stmt (*gsi));
+	  return true;
+	}
+    }
+
   /* (a | CST1) & CST2  ->  (a & CST2) | (CST1 & CST2).  */
   if (code == BIT_AND_EXPR
       && def1_code == BIT_IOR_EXPR
Index: gcc/gcc/testsuite/gcc.dg/binop-notand1a.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-notand1a.c	2011-06-22 11:03:03.735901300 +0200
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (char a, unsigned short b)
+{
+  return (a & !a) | (b & !b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/binop-notand2a.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-notand2a.c	2011-06-22 11:05:43.629705200 +0200
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int a)
+{
+  return (!a & 1) != (a == 0);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/binop-notand3a.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-notand3a.c	2011-06-22 11:09:05.107289600 +0200
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (short a)
+{
+  return (!a & 1) != ((a == 0) & 1);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/binop-notand4a.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-notand4a.c	2011-06-22 11:09:43.515666900 +0200
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (unsigned char a, _Bool b)
+{
+  return (!a & a) | (b & !b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/binop-notand5a.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-notand5a.c	2011-06-22 11:10:11.556727600 +0200
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (long a, unsigned long b)
+{
+  return (a & (a == 0)) | (b & !b);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/testsuite/gcc.dg/binop-notand6a.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/binop-notand6a.c	2011-06-22 11:10:30.816673300 +0200
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (unsigned long a, long b)
+{
+  return (a & !a) | (b & (b == 0));
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */

Re: [patch tree-ssa-forwprop]: Improve binary and/or/xor folding

[Richard Guenther]

On Wed, Jun 22, 2011 at 3:09 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Hello,
>
> This patch improves via type-sinking folding of binary and, or, and
> xor operations.
> First we do sinking also for compatible types with same precision, as
> those don't need to be preserved for these operations.
> Additional try to fold patterns (TYPE) X bin-op (Y CMP Z) and (TYPE) X
> bin-op !Y, if type of X is
> compatible to Y.
>
> ChangeLog gcc
>
> 2011-06-22  Kai Tietz  <ktietz@redhat.com>
>
>        * tree-ssa-forwprop.c (simplify_bitwise_binary):
>        Improve binary folding regarding casts.
>
>
> ChangeLog gcc/testsuite
>
> 2011-06-22  Kai Tietz  <ktietz@redhat.com>
>
>        * gcc.dg/binop-notand1a.c: New test.
>        * gcc.dg/binop-notand2a.c: New test.
>        * gcc.dg/binop-notand3a.c: New test.
>        * gcc.dg/binop-notand4a.c: New test.
>        * gcc.dg/binop-notand5a.c: New test.
>        * gcc.dg/binop-notand6a.c: New test.
>
> Bootstrapped and regression tested for all standard languages, Ada,
> and Obj-C++. Ok for apply?

The first hunk is ok, the 2nd not - please don't use fold here.  Also
your comment says what it tries to match, but not what it tries
to produce.  So - what is the transformation you are trying to do?
The code is also two duplicates of exactly the same stuff.

Btw, I see TRUTH_NOT_EXPR is still around, why's that so?

Thanks,
Richard.

> Regards,
> Kai
>

Re: [patch tree-ssa-forwprop]: Improve binary and/or/xor folding

[Kai Tietz]

2011/6/27 Richard Guenther <richard.guenther@gmail.com>:
> On Wed, Jun 22, 2011 at 3:09 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> Hello,
>>
>> This patch improves via type-sinking folding of binary and, or, and
>> xor operations.
>> First we do sinking also for compatible types with same precision, as
>> those don't need to be preserved for these operations.
>> Additional try to fold patterns (TYPE) X bin-op (Y CMP Z) and (TYPE) X
>> bin-op !Y, if type of X is
>> compatible to Y.
>>
>> ChangeLog gcc
>>
>> 2011-06-22  Kai Tietz  <ktietz@redhat.com>
>>
>>        * tree-ssa-forwprop.c (simplify_bitwise_binary):
>>        Improve binary folding regarding casts.
>>
>>
>> ChangeLog gcc/testsuite
>>
>> 2011-06-22  Kai Tietz  <ktietz@redhat.com>
>>
>>        * gcc.dg/binop-notand1a.c: New test.
>>        * gcc.dg/binop-notand2a.c: New test.
>>        * gcc.dg/binop-notand3a.c: New test.
>>        * gcc.dg/binop-notand4a.c: New test.
>>        * gcc.dg/binop-notand5a.c: New test.
>>        * gcc.dg/binop-notand6a.c: New test.
>>
>> Bootstrapped and regression tested for all standard languages, Ada,
>> and Obj-C++. Ok for apply?
>
> The first hunk is ok, the 2nd not - please don't use fold here.  Also
> your comment says what it tries to match, but not what it tries
> to produce.  So - what is the transformation you are trying to do?
> The code is also two duplicates of exactly the same stuff.
>
> Btw, I see TRUTH_NOT_EXPR is still around, why's that so?
>
> Thanks,
> Richard.

Ok, I will sent first hunk as separate patch.  The second hunk shall
try to do simple simple folding like X & !X -> 0 (which is handled by
fold-const, too). As special case we have here also (type) X & !X,
and for case X & (type) !X. Later case can happen as soon as we
preserve casts from boolean-type.
I was thinking about implementing here the optimizations for all
binary and/or/xor the foldings to constant directly in
forward-propagate. This might be the better choice. Should I put this
into a separate function in forward-propagation, or should I put this
folding function into a different file?

Regards,
Kai

Re: [patch tree-ssa-forwprop]: Improve binary and/or/xor folding

[Richard Guenther]

On Mon, Jun 27, 2011 at 12:58 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2011/6/27 Richard Guenther <richard.guenther@gmail.com>:
>> On Wed, Jun 22, 2011 at 3:09 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>> Hello,
>>>
>>> This patch improves via type-sinking folding of binary and, or, and
>>> xor operations.
>>> First we do sinking also for compatible types with same precision, as
>>> those don't need to be preserved for these operations.
>>> Additional try to fold patterns (TYPE) X bin-op (Y CMP Z) and (TYPE) X
>>> bin-op !Y, if type of X is
>>> compatible to Y.
>>>
>>> ChangeLog gcc
>>>
>>> 2011-06-22  Kai Tietz  <ktietz@redhat.com>
>>>
>>>        * tree-ssa-forwprop.c (simplify_bitwise_binary):
>>>        Improve binary folding regarding casts.
>>>
>>>
>>> ChangeLog gcc/testsuite
>>>
>>> 2011-06-22  Kai Tietz  <ktietz@redhat.com>
>>>
>>>        * gcc.dg/binop-notand1a.c: New test.
>>>        * gcc.dg/binop-notand2a.c: New test.
>>>        * gcc.dg/binop-notand3a.c: New test.
>>>        * gcc.dg/binop-notand4a.c: New test.
>>>        * gcc.dg/binop-notand5a.c: New test.
>>>        * gcc.dg/binop-notand6a.c: New test.
>>>
>>> Bootstrapped and regression tested for all standard languages, Ada,
>>> and Obj-C++. Ok for apply?
>>
>> The first hunk is ok, the 2nd not - please don't use fold here.  Also
>> your comment says what it tries to match, but not what it tries
>> to produce.  So - what is the transformation you are trying to do?
>> The code is also two duplicates of exactly the same stuff.
>>
>> Btw, I see TRUTH_NOT_EXPR is still around, why's that so?
>>
>> Thanks,
>> Richard.
>
> Ok, I will sent first hunk as separate patch.  The second hunk shall
> try to do simple simple folding like X & !X -> 0 (which is handled by
> fold-const, too). As special case we have here also (type) X & !X,
> and for case X & (type) !X. Later case can happen as soon as we
> preserve casts from boolean-type.
> I was thinking about implementing here the optimizations for all
> binary and/or/xor the foldings to constant directly in
> forward-propagate. This might be the better choice. Should I put this
> into a separate function in forward-propagation, or should I put this
> folding function into a different file?

The function is fine I think, but if you want X & !X -> 0 and similar
patterns then I don't see why you need to hand things to fold at all.
Just pattern-match the cases you are interested in.  Eventually
add a helper function that can pattern-match !*X like

tree
match_unop_chain (enum tree_code code, tree name, tree stop_at
                             int *times)
{
  *times = 0;
  while (TREE_CODE (name) == SSA_NAME)
  {
  gimple def_stmt = SSA_NAME_DEF_STMT (name);
  if (gimple_assign_rhs_code (def_stmt) != code)
    break;
  ++*times;
  name = gimple_assign_rhs1 (def_stmt);
  if (name == stop_at)
   break;
  }
  return name;
}

and use that, checking for even/odd *times.  The above assumes
that code cancels itself out, like ~ or ! or -.  Untested of course.

Richard.


>
> Regards,
> Kai
>