[patch tree-optimization]: 3 of 6 Improve reassoc for bitwise operations

[Kai Tietz <ktietz70 at googlemail dot com>]

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  <ktietz@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  <ktietz@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" } } */
+