diff mbox

Fix PR 33512 Folding of x & ((~x) | y) into x & y on the tree level

Message ID CA+=Sn1kB41c2bh5LxvmQUn0TTH6aSXTaK9KoTormoAX+HKXYrg@mail.gmail.com
State New
Headers show

Commit Message

Andrew Pinski Jan. 19, 2012, 9 a.m. UTC 
On Tue, Jan 17, 2012 at 1:38 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Tue, Jan 17, 2012 at 8:06 AM, Andrew Pinski
> <andrew.pinski@caviumnetworks.com> wrote:
>> Hi,
>>  This adds the folding of x & ((~x) | y)) into x & y on the tree
>> level via fold-const.c
>> There is already partly done on the RTL level but it would be a good
>> thing for the tree level also.
>>
>>
>> OK for 4.8 (yes I know we have not branched yet but I thought I would
>> send it out so I don't forget about it)?
>> Bootstrapped and tested on x86_64-linux-gnu with no regressions.
>
> Can you instead patch tree-ssa-forwprop.c:simplify_bitwise_binary?

Yes and here is a new patch which also adds optimizing x | ((~x) & y)) to x | y.
Also it adds the optimizing x & (x | y) to x and x | (x & y) to x to
tree-ssa-forwprop.c:simplify_bitwise_binary
since it was an easy extension on top of the ~x case (well I
implemented the one without the ~ first).  I did not remove those
folding from fold-const.c though.

Also I was thinking maybe this belongs in reassociate though I don't
see how to do it.

OK for 4.8, once in stage 1? Again bootstrapped and tested on
x86_64-linux-gnu with no regressions.

Thanks,
Andrew Pinski

ChangeLog:
* tree-ssa-forwprop.c (defcodefor_name): New function.
(simplify_bitwise_binary): Use defcodefor_name.
Simplify "( X | Y) & X" to X and "( X & Y) | X" to X.
Simplify "(~X | Y) & X" to "X & Y" and
"(~X & Y) | X" to "X | Y".

testsuite/ChangeLog:
* gcc.dg/tree-ssa/andor-3.c: New testcase.
* gcc.dg/tree-ssa/andor-4.c: New testcase.
* gcc.dg/tree-ssa/andor-5.c: New testcase.


>
> Thanks,
> Richard.
>
>> Thanks,
>> Andrew Pinski
>>
>> ChangeLog:
>> * fold-const.c (fold_binary_loc <case BIT_AND_EXPR>): Add folding of x
>> & (~x | y) into x & y.
>>
>> testsuite/ChangeLog:
>> * gcc.dg/tree-ssa/andor-3.c: New testcase.

Comments

Richard Biener Jan. 19, 2012, 11:13 a.m. UTC | #1 
On Thu, Jan 19, 2012 at 10:00 AM, Andrew Pinski
<andrew.pinski@caviumnetworks.com> wrote:
> On Tue, Jan 17, 2012 at 1:38 AM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> On Tue, Jan 17, 2012 at 8:06 AM, Andrew Pinski
>> <andrew.pinski@caviumnetworks.com> wrote:
>>> Hi,
>>>  This adds the folding of x & ((~x) | y)) into x & y on the tree
>>> level via fold-const.c
>>> There is already partly done on the RTL level but it would be a good
>>> thing for the tree level also.
>>>
>>>
>>> OK for 4.8 (yes I know we have not branched yet but I thought I would
>>> send it out so I don't forget about it)?
>>> Bootstrapped and tested on x86_64-linux-gnu with no regressions.
>>
>> Can you instead patch tree-ssa-forwprop.c:simplify_bitwise_binary?
>
> Yes and here is a new patch which also adds optimizing x | ((~x) & y)) to x | y.
> Also it adds the optimizing x & (x | y) to x and x | (x & y) to x to
> tree-ssa-forwprop.c:simplify_bitwise_binary
> since it was an easy extension on top of the ~x case (well I
> implemented the one without the ~ first).  I did not remove those
> folding from fold-const.c though.
>
> Also I was thinking maybe this belongs in reassociate though I don't
> see how to do it.

I still have plans to create that piecewise gimple_fold (see my proposal
from early last year) that would be the container for this kind of pattern
matching.  It would then be usable from reassoc as well (but reassoc
has the issue of only collecting one kind of op, so its simplification
wouldn't trigger reliably on these).

http://gcc.gnu.org/ml/gcc-patches/2011-03/msg01099.html

> OK for 4.8, once in stage 1? Again bootstrapped and tested on
> x86_64-linux-gnu with no regressions.

Ok.

Thanks,
Richard.

> Thanks,
> Andrew Pinski
>
> ChangeLog:
> * tree-ssa-forwprop.c (defcodefor_name): New function.
> (simplify_bitwise_binary): Use defcodefor_name.
> Simplify "( X | Y) & X" to X and "( X & Y) | X" to X.
> Simplify "(~X | Y) & X" to "X & Y" and
> "(~X & Y) | X" to "X | Y".
>
> testsuite/ChangeLog:
> * gcc.dg/tree-ssa/andor-3.c: New testcase.
> * gcc.dg/tree-ssa/andor-4.c: New testcase.
> * gcc.dg/tree-ssa/andor-5.c: New testcase.
>
>
>>
>> Thanks,
>> Richard.
>>
>>> Thanks,
>>> Andrew Pinski
>>>
>>> ChangeLog:
>>> * fold-const.c (fold_binary_loc <case BIT_AND_EXPR>): Add folding of x
>>> & (~x | y) into x & y.
>>>
>>> testsuite/ChangeLog:
>>> * gcc.dg/tree-ssa/andor-3.c: New testcase.
Andrew Pinski April 21, 2012, 4:05 a.m. UTC | #2 
On Thu, Jan 19, 2012 at 3:13 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Thu, Jan 19, 2012 at 10:00 AM, Andrew Pinski
> <andrew.pinski@caviumnetworks.com> wrote:
>> On Tue, Jan 17, 2012 at 1:38 AM, Richard Guenther
>> <richard.guenther@gmail.com> wrote:
>>> On Tue, Jan 17, 2012 at 8:06 AM, Andrew Pinski
>>> <andrew.pinski@caviumnetworks.com> wrote:
>>>> Hi,
>>>>  This adds the folding of x & ((~x) | y)) into x & y on the tree
>>>> level via fold-const.c
>>>> There is already partly done on the RTL level but it would be a good
>>>> thing for the tree level also.
>>>>
>>>>
>>>> OK for 4.8 (yes I know we have not branched yet but I thought I would
>>>> send it out so I don't forget about it)?
>>>> Bootstrapped and tested on x86_64-linux-gnu with no regressions.
>>>
>>> Can you instead patch tree-ssa-forwprop.c:simplify_bitwise_binary?
>>
>> Yes and here is a new patch which also adds optimizing x | ((~x) & y)) to x | y.
>> Also it adds the optimizing x & (x | y) to x and x | (x & y) to x to
>> tree-ssa-forwprop.c:simplify_bitwise_binary
>> since it was an easy extension on top of the ~x case (well I
>> implemented the one without the ~ first).  I did not remove those
>> folding from fold-const.c though.
>>
>> Also I was thinking maybe this belongs in reassociate though I don't
>> see how to do it.
>
> I still have plans to create that piecewise gimple_fold (see my proposal
> from early last year) that would be the container for this kind of pattern
> matching.  It would then be usable from reassoc as well (but reassoc
> has the issue of only collecting one kind of op, so its simplification
> wouldn't trigger reliably on these).
>
> http://gcc.gnu.org/ml/gcc-patches/2011-03/msg01099.html
>
>> OK for 4.8, once in stage 1? Again bootstrapped and tested on
>> x86_64-linux-gnu with no regressions.
>
> Ok.

Here is an updated patch which fixes a bug which I found while doing
the treecombine branch.  I rewrote defcodefor_name so more than
SSA_NAMEs can be passed to it.

OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

Thanks,
Andrew Pinski

ChangeLog:

ChangeLog:
* tree-ssa-forwprop.c (defcodefor_name): New function.
(simplify_bitwise_binary): Use defcodefor_name instead of manually
Simplify "( X | Y) & X" to X and "( X & Y) | X" to X.
Simplify "(~X | Y) & X" to "X & Y" and
"(~X & Y) | X" to "X | Y".

testsuite/ChangeLog:
* gcc.dg/tree-ssa/andor-3.c: New testcase.
* gcc.dg/tree-ssa/andor-4.c: New testcase.
* gcc.dg/tree-ssa/andor-5.c: New testcase.

>
> Thanks,
> Richard.
>
>> Thanks,
>> Andrew Pinski
>>
>> ChangeLog:
>> * tree-ssa-forwprop.c (defcodefor_name): New function.
>> (simplify_bitwise_binary): Use defcodefor_name.
>> Simplify "( X | Y) & X" to X and "( X & Y) | X" to X.
>> Simplify "(~X | Y) & X" to "X & Y" and
>> "(~X & Y) | X" to "X | Y".
>>
>> testsuite/ChangeLog:
>> * gcc.dg/tree-ssa/andor-3.c: New testcase.
>> * gcc.dg/tree-ssa/andor-4.c: New testcase.
>> * gcc.dg/tree-ssa/andor-5.c: New testcase.
>>
>>
>>>
>>> Thanks,
>>> Richard.
>>>
>>>> Thanks,
>>>> Andrew Pinski
>>>>
>>>> ChangeLog:
>>>> * fold-const.c (fold_binary_loc <case BIT_AND_EXPR>): Add folding of x
>>>> & (~x | y) into x & y.
>>>>
>>>> testsuite/ChangeLog:
>>>> * gcc.dg/tree-ssa/andor-3.c: New testcase.
diff mbox

Patch

Index: testsuite/gcc.dg/tree-ssa/andor-3.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/andor-3.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/andor-3.c	(revision 0)
@@ -0,0 +1,24 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int f(int y, int x)
+{
+  return x & ((~x) | y);
+}
+int f1(int y, int x)
+{
+  return x & (y | (~x));
+}
+int f2(int y, int x)
+{
+  return ((~x) | y) & x;
+}
+int f3(int y, int x)
+{
+  return (y | (~x)) & x;
+}
+
+
+/* { dg-final { scan-tree-dump-times "~x" 0 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "x_..D. \& y_..D." 4 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: testsuite/gcc.dg/tree-ssa/andor-4.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/andor-4.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/andor-4.c	(revision 0)
@@ -0,0 +1,24 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int f(int y, int x)
+{
+  return x | ((~x) & y);
+}
+int f1(int y, int x)
+{
+  return x | (y & (~x));
+}
+int f2(int y, int x)
+{
+  return ((~x) & y) | x;
+}
+int f3(int y, int x)
+{
+  return (y & (~x)) | x;
+}
+
+
+/* { dg-final { scan-tree-dump-times "~x" 0 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "x_..D. \\\| y_..D." 4 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: testsuite/gcc.dg/tree-ssa/andor-5.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/andor-5.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/andor-5.c	(revision 0)
@@ -0,0 +1,50 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int f(int y, int x)
+{
+  int a = x | y;
+  return a & x;
+}
+int f1(int y, int x)
+{
+  int a = y | x;
+  return a & x;
+}
+int f2(int y, int x)
+{
+  int a = x | y;
+  return x & a;
+}
+int f3(int y, int x)
+{
+  int a = x | y;
+  return x & a;
+}
+int f4(int y, int x)
+{
+  int a = x & y;
+  return a | x;
+}
+int f5(int y, int x)
+{
+  int a = y & x;
+  return a | x;
+}
+int f6(int y, int x)
+{
+  int a = x & y;
+  return x | a;
+}
+int f7(int y, int x)
+{
+  int a = x & y;
+  return x | a;
+}
+/* These all should be optimized to just return x; */
+
+
+/* { dg-final { scan-tree-dump-times "\\\|" 0 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\&" 0 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return x_..D.;" 8 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: tree-ssa-forwprop.c
===================================================================
--- tree-ssa-forwprop.c	(revision 183295)
+++ tree-ssa-forwprop.c	(working copy)
@@ -1742,6 +1742,24 @@  simplify_bitwise_binary_1 (enum tree_cod
   return NULL_TREE;
 }
 
+/* Given a ssa_name in NAME see if it was defined by an assignment and
+   set CODE to be the code and ARG1 to the first operand on the rhs and ARG2
+   to the second operand on the rhs. */
+static inline void
+defcodefor_name (tree name, enum tree_code *code, tree *arg1, tree *arg2)
+{
+  gimple def;
+  gcc_assert (TREE_CODE (name) == SSA_NAME);
+  def = SSA_NAME_DEF_STMT (name);
+  if (is_gimple_assign (def))
+    {
+      *code = gimple_assign_rhs_code (def);
+      *arg1 = gimple_assign_rhs1 (def);
+      if (arg2)
+        *arg2 = gimple_assign_rhs2 (def);
+    }
+}
+
 /* Simplify bitwise binary operations.
    Return true if a transformation applied, otherwise return false.  */
 
@@ -1753,33 +1771,18 @@  simplify_bitwise_binary (gimple_stmt_ite
   tree arg2 = gimple_assign_rhs2 (stmt);
   enum tree_code code = gimple_assign_rhs_code (stmt);
   tree res;
-  gimple def1 = NULL, def2 = NULL;
-  tree def1_arg1, def2_arg1;
+  tree def1_arg1, def1_arg2, def2_arg1, def2_arg2;
   enum tree_code def1_code, def2_code;
 
   def1_code = TREE_CODE (arg1);
   def1_arg1 = arg1;
-  if (TREE_CODE (arg1) == SSA_NAME)
-    {
-      def1 = SSA_NAME_DEF_STMT (arg1);
-      if (is_gimple_assign (def1))
-	{
-	  def1_code = gimple_assign_rhs_code (def1);
-	  def1_arg1 = gimple_assign_rhs1 (def1);
-	}
-    }
+  if (def1_code == SSA_NAME)
+    defcodefor_name (arg1, &def1_code, &def1_arg1, &def1_arg2);
 
   def2_code = TREE_CODE (arg2);
   def2_arg1 = arg2;
-  if (TREE_CODE (arg2) == SSA_NAME)
-    {
-      def2 = SSA_NAME_DEF_STMT (arg2);
-      if (is_gimple_assign (def2))
-	{
-	  def2_code = gimple_assign_rhs_code (def2);
-	  def2_arg1 = gimple_assign_rhs1 (def2);
-	}
-    }
+  if (def2_code == SSA_NAME)
+    defcodefor_name (arg2, &def2_code, &def2_arg1, &def2_arg2);
 
   /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)).  */
   if (TREE_CODE (arg2) == INTEGER_CST
@@ -1838,10 +1841,10 @@  simplify_bitwise_binary (gimple_stmt_ite
   if (code == BIT_AND_EXPR
       && def1_code == BIT_IOR_EXPR
       && TREE_CODE (arg2) == INTEGER_CST
-      && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
+      && TREE_CODE (def1_arg2) == INTEGER_CST)
     {
       tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2),
-			      arg2, gimple_assign_rhs2 (def1));
+			      arg2, def1_arg2);
       tree tem;
       gimple newop;
       if (integer_zerop (cst))
@@ -1871,10 +1874,10 @@  simplify_bitwise_binary (gimple_stmt_ite
        || code == BIT_XOR_EXPR)
       && def1_code == code 
       && TREE_CODE (arg2) == INTEGER_CST
-      && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
+      && TREE_CODE (def1_arg2) == INTEGER_CST)
     {
       tree cst = fold_build2 (code, TREE_TYPE (arg2),
-			      arg2, gimple_assign_rhs2 (def1));
+			      arg2, def1_arg2);
       gimple_assign_set_rhs1 (stmt, def1_arg1);
       gimple_assign_set_rhs2 (stmt, cst);
       update_stmt (stmt);
@@ -1901,6 +1904,101 @@  simplify_bitwise_binary (gimple_stmt_ite
       return true;
     }
 
+  if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+    {
+      enum tree_code ocode = code == BIT_AND_EXPR ? BIT_IOR_EXPR : BIT_AND_EXPR;
+      if (def1_code == ocode)
+	{
+	  tree x = arg2;
+	  /* ( X | Y) & X -> X */
+	  /* ( X & Y) | X -> X */
+	  if (x == def1_arg1
+	      || x == def1_arg2)
+	    {
+	      gimple_assign_set_rhs_from_tree (gsi, x);
+	      update_stmt (gsi_stmt (*gsi));
+	      return true;
+	    }
+	  if (TREE_CODE (def1_arg1) == SSA_NAME)
+	    {
+	      enum tree_code coden;
+	      tree a1, a2;
+	      defcodefor_name (def1_arg1, &coden, &a1, &a2);
+	      /* (~X | Y) & X -> X & Y */
+	      /* (~X & Y) | X -> X | Y */
+	      if (coden == BIT_NOT_EXPR && a1 == x)
+		{
+		  gimple_assign_set_rhs_with_ops (gsi, code,
+						  x, def1_arg2);
+		  gcc_assert (gsi_stmt (*gsi) == stmt);
+		  update_stmt (stmt);
+		  return true;
+		}
+	    }
+	  if (TREE_CODE (def1_arg2) == SSA_NAME)
+	    {
+	      enum tree_code coden;
+	      tree a1, a2;
+	      defcodefor_name (def1_arg2, &coden, &a1, &a2);
+	      /* (Y | ~X) & X -> X & Y */
+	      /* (Y & ~X) | X -> X | Y */
+	      if (coden == BIT_NOT_EXPR && a1 == x)
+		{
+		  gimple_assign_set_rhs_with_ops (gsi, code,
+						  x, def1_arg1);
+		  gcc_assert (gsi_stmt (*gsi) == stmt);
+		  update_stmt (stmt);
+		  return true;
+		}
+	    }
+	}
+      if (def2_code == ocode)
+	{
+	  tree x = arg1;
+	  /* X & ( X | Y) -> X */
+	  /* X | ( X & Y) -> X */
+	  if (x == def2_arg1
+	      || x == def2_arg2)
+	    {
+	      gimple_assign_set_rhs_from_tree (gsi, x);
+	      update_stmt (gsi_stmt (*gsi));
+	      return true;
+	    }
+	  if (TREE_CODE (def2_arg1) == SSA_NAME)
+	    {
+	      enum tree_code coden;
+	      tree a1;
+	      defcodefor_name (def2_arg1, &coden, &a1, NULL);
+	      /* (~X | Y) & X -> X & Y */
+	      /* (~X & Y) | X -> X | Y */
+	      if (coden == BIT_NOT_EXPR && a1 == x)
+		{
+		  gimple_assign_set_rhs_with_ops (gsi, code,
+						  x, def2_arg2);
+		  gcc_assert (gsi_stmt (*gsi) == stmt);
+		  update_stmt (stmt);
+		  return true;
+		}
+	    }
+	  if (TREE_CODE (def2_arg2) == SSA_NAME)
+	    {
+	      enum tree_code coden;
+	      tree a1;
+	      defcodefor_name (def2_arg2, &coden, &a1, NULL);
+	      /* (Y | ~X) & X -> X & Y */
+	      /* (Y & ~X) | X -> X | Y */
+	      if (coden == BIT_NOT_EXPR && a1 == x)
+		{
+		  gimple_assign_set_rhs_with_ops (gsi, code,
+						  x, def2_arg1);
+		  gcc_assert (gsi_stmt (*gsi) == stmt);
+		  update_stmt (stmt);
+		  return true;
+		}
+	    }
+	}
+    }
+
   return false;
 }