Hello,
This patch adds to the break-up pass the facility to expand (X | Y) ==/!= 0
expression. This enables in later reassociation pass better results.
ChangeLog
2011-10-07 Kai Tietz <kti...@redhat.com>
* tree-ssa-reassoc.c (expand_cmp_ior): Helper for expanding
(X | Y) ==/!= 0 statments.
(break_up_bitwise_combined_stmt): Make use of expand_cmp_ior.
2011-10-07 Kai Tietz <kti...@redhat.com>
* gcc.dg/tree-ssa/reassoc-cmpior-1.c: New file.
* gcc.dg/tree-ssa/reassoc-cmpior-2.c: New file.
* gcc.dg/tree-ssa/reassoc-cmpior-3.c: New file.
Bootstrapped and regression-tested for all languages plus Ada and
Obj-C++ on x86_64-pc-linux-gnu.
Ok for apply?
Regards,
Kai
Index: gcc/gcc/tree-ssa-reassoc.c
===================================================================
--- gcc.orig/gcc/tree-ssa-reassoc.c
+++ gcc/gcc/tree-ssa-reassoc.c
@@ -59,6 +59,8 @@ static void remove_stmt_chain (tree);
it would promote the reassociation of adds.
1.2. Breaking up to normalized form for bitwise-not operations
on bitwise-binary and for bitwise-not operation on compares.
+ 1.3 Breaking up combined expression made out of boolean-typed bitwise
+ expressions for improving simplification.
2. Left linearization of the expression trees, so that (A+B)+(C+D)
becomes (((A+B)+C)+D), which is easier for us to rewrite later.
@@ -712,8 +714,89 @@ expand_not_bitwise_binary (tree type, tr
NULL_TREE, expr);
}
+/* Routine to expand (X | Y) ==/!= 0 and doing
+ simplification on (X cmp Y) ==/!= 0.
+ - (X | Y) == 0 to (X == 0) & (Y == 0)
+ - (X | Y) != 0 to (X != 0) | (Y != 0).
+ - (X cmp Y) == 0 to (X cmp' Y) with cmp'=invert of cmp.
+ - (X cmp Y) != 0 to (X cmp Y).
+
+ The argument CODE can be either NE_EXPR, or EQ_EXPR. It indicates
+ what kind of expansion is performed. */
+
+static tree
+expand_cmp_ior (tree op, tree type, enum tree_code code)
+{
+ tree op1, op2;
+ gimple s = NULL;
+ enum tree_code hcode;
+
+ /* Handle integral constant value case. */
+ if (TREE_CODE (op) == INTEGER_CST)
+ {
+ if (code == EQ_EXPR)
+ return fold_convert (type, (integer_zerop (op) ? integer_one_node
+ : integer_zero_node));
+ return fold_convert (type, (!integer_zerop (op) ? integer_one_node
+ : integer_zero_node));
+ }
+
+ /* If operand OP isn't a gimple-assign, or has non-single use,
+ then simply creat a comparison != 0 for it. */
+ if (TREE_CODE (op) != SSA_NAME
+ || !(s = SSA_NAME_DEF_STMT (op))
+ || !is_gimple_assign (s)
+ || !has_single_use (op))
+ return make_new_tmp_statement (type, code, op,
+ build_zero_cst (TREE_TYPE (op)), s);
+
+ hcode = gimple_assign_rhs_code (s);
+
+ /* Operand code of OP isn't of comparison kind, and not
+ a bitwise-not, then creat a comparison != 0 for it. */
+ if (TREE_CODE_CLASS (hcode) != tcc_comparison
+ && hcode != BIT_IOR_EXPR)
+ return make_new_tmp_statement (type, code, op,
+ build_zero_cst (TREE_TYPE (op)), s);
+
+ op1 = gimple_assign_rhs1 (s);
+ op2 = gimple_assign_rhs2 (s);
+
+ /* Simplify (X cmp Y) != 0 -> (X cmp Y), and
+ (X cmp Y) == 0 -> X cnp' Y, with cmp' = inverted cmp. */
+ if (TREE_CODE_CLASS (hcode) == tcc_comparison)
+ {
+ tree op1type = TREE_TYPE (op1);
+
+ if (code == EQ_EXPR)
+ {
+ enum tree_code ncode;
+ ncode = invert_tree_comparison (hcode,
+ HONOR_NANS (TYPE_MODE (op1type)));
+ if (ncode != ERROR_MARK)
+ return make_new_tmp_statement (type, ncode, op1, op2, s);
+ }
+ else
+ return make_new_tmp_statement (type, hcode, op1, op2, s);
+ }
+
+ /* Break up (X | Y) ==/!= 0 case. */
+ if (hcode == BIT_IOR_EXPR)
+ {
+ op1 = expand_cmp_ior (op1, type, code);
+ op2 = expand_cmp_ior (op2, type, code);
+ return make_new_tmp_statement (type, (code == EQ_EXPR ? BIT_AND_EXPR
+ : BIT_IOR_EXPR),
+ op1, op2, s);
+ }
+ return make_new_tmp_statement (type, code, op,
+ build_zero_cst (TREE_TYPE (op)), s);
+}
+
+
/* Break up STMT if it is a combined statement made out of
- bitwise operations. Handle expansion of ~(A op B). */
+ bitwise operations. Handle expansion of ~(A op B), and
+ (A | B) !=/== 0. */
static bool
break_up_bitwise_combined_stmt (gimple stmt)
@@ -728,9 +811,13 @@ break_up_bitwise_combined_stmt (gimple s
old_op1 = op1;
old_op2 = op2 = NULL_TREE;
+ if (code == EQ_EXPR || code == NE_EXPR)
+ old_op2 = op2 = gimple_assign_rhs2 (stmt);
+
/* Check that CODE can be handled and that left-hand operand
is of kind SSA_NAME. */
- if (code != BIT_NOT_EXPR
+ if ((code != BIT_NOT_EXPR
+ && code != EQ_EXPR && code != NE_EXPR)
|| TREE_CODE (op1) != SSA_NAME)
return false;
@@ -742,8 +829,42 @@ break_up_bitwise_combined_stmt (gimple s
|| !has_single_use (op1))
return false;
- /* Handle expansion for ~X. */
- if (code == BIT_NOT_EXPR)
+ if (code == NE_EXPR || code == EQ_EXPR)
+ {
+ tree inner_op1, inner_op2;
+
+ /* Check that operands have integral type and
+ see if it has as second argument a constant zero valued
+ operand. */
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (op1))
+ || TREE_CODE (op2) != INTEGER_CST
+ || !integer_zerop (op2))
+ return false;
+
+ /* Check for pattern X | Y == 0 and X | Y != 0 */
+ if (gimple_assign_rhs_code (op1_def) != BIT_IOR_EXPR)
+ return false;
+
+ inner_op1 = gimple_assign_rhs1 (op1_def);
+ inner_op2 = gimple_assign_rhs2 (op1_def);
+
+ /* Expand (X | Y) == 0 -> (X == 0) & (Y == 0)
+ and (X | Y) != 0 -> (X != 0) | (Y != 0) */
+
+ op1 = expand_cmp_ior (inner_op1, type, code);
+ op2 = expand_cmp_ior (inner_op2, type, code);
+
+ gsi = gsi_for_stmt (stmt);
+ gimple_assign_set_rhs_with_ops (&gsi, (code == NE_EXPR ? BIT_IOR_EXPR
+ : BIT_AND_EXPR),
+ op1, op2);
+ update_stmt (gsi_stmt (gsi));
+ remove_stmt_chain (old_op1);
+ remove_stmt_chain (old_op2);
+ return true;
+ }
+ /* Handle expansion for expansion of ~X. */
+ else if (code == BIT_NOT_EXPR)
{
enum tree_code inner_code = gimple_assign_rhs_code (op1_def);
@@ -3091,6 +3212,10 @@ can_reassociate_p (tree op)
If A or B are comparisons or are bitwise-not statement, then sink bit-not
into expression, if it is a single-use statement.
+ Break up (X | Y) == 0 into (X == 0) & (Y == 0).
+
+ Break up (X | Y) != 0 into (X != 0) | (Y != 0).
+
En passant, clear the GIMPLE visited flag on every statement. */
static void
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-1.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-1.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, int b, int c, int d)
+{
+ int r1 = (a | b | c) == 0;
+ int r2 = (a | d | c) != 0 | b == 0;
+ return (r1 == 0 | r2 != 0);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
+
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-2.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-2.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, int b, int c, int d)
+{
+ int r1 = a != 0 & c != 0 & b != 0;
+ int r2 = a == 0 | b != 0 | d == 0;
+ return (r1 == 0 | r2 != 0);
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
+
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-3.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-cmpior-3.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -ffast-math" } */
+
+int foo (int a, int b, int c, int d)
+{
+ int r1 = a != 0 & c != 0 & b != 0;
+ int r2 = a == 0 | b != 0 | d == 0;
+ return (r1 != 0 & r2 == 0);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
+
