On Tue, Jan 17, 2012 at 1:38 AM, Richard Guenther
<richard.guent...@gmail.com> wrote:
> On Tue, Jan 17, 2012 at 8:06 AM, Andrew Pinski
> <andrew.pin...@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.
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;
}
