Patchwork [tree-optimization] : 1 of 6 Improve reassoc for bitwise operations

login
register
mail settings
Submitter Kai Tietz
Date Oct. 7, 2011, 4:38 p.m.
Message ID <CAEwic4aXauS3U8+m+ADUaN=tOqByf2tsCGm1WRPEfmM1m4p5tQ@mail.gmail.com>
Download mbox | patch
Permalink /patch/118349/
State New
Headers show

Comments

Kai Tietz - Oct. 7, 2011, 4:38 p.m.
Hello,

This patch adds to the break-up pass the facility to sink bitwise-not operations
into bitwise-binary expressions.  Additionally it handles special
cases for ~(~X),
and ~(X cmp Y).

ChangeLog

2011-10-07  Kai Tietz  <ktietz@redhat.com>

	* tree-ssa-reassoc.c (remove_stmt_chain): Helper function
	to remove gimple-assignment tree with all arms.
	(make_new_tmp_statement): Helper function to create temporary
	register expression.
	(expand_not_bitwise_binary): Perform bitwise-not operation on
	gimple-assignment tree.
	(break_up_bitwise_combined_stmt): Break-up handler for bitwise-
	operations.
	(break_up_expr_bb): Adjust to call break_up_bitwise_combined_stmt.

2011-10-07  Kai Tietz  <ktietz@redhat.com>

	* gcc.dg/tree-ssa/reassoc-not-1.c: New file.
	* gcc.dg/tree-ssa/reassoc-not-2.c: New file.
	* gcc.dg/tree-ssa/reassoc-not-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

Patch

Index: gcc/gcc/tree-ssa-reassoc.c
===================================================================
--- gcc.orig/gcc/tree-ssa-reassoc.c
+++ gcc/gcc/tree-ssa-reassoc.c
@@ -46,6 +46,7 @@  along with GCC; see the file COPYING3.

 /* Forwarders.  */
 static gimple build_and_add_sum (tree, tree, tree, enum tree_code);
+static void remove_stmt_chain (tree);

 /*  This is a simple global reassociation pass.  It is, in part, based
     on the LLVM pass of the same name (They do some things more/less
@@ -53,8 +54,11 @@  static gimple build_and_add_sum (tree, t

     It consists of five steps:

-    1. Breaking up subtract operations into addition + negate, where
+    1. Breaking up expressions
+    1.1. Breaking up subtract operations into addition + negate, where
     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.

     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.
@@ -560,6 +564,265 @@  get_unary_op (tree name, enum tree_code
   return NULL_TREE;
 }

+/* Create a temporary register expression with type TYPE, tree code CODE, and
+   operands OP1 and OP2.  If REF_DEF is a valid gimple statement, we use its
+   location information for new generated temporary.
+   Function returns left-hand-side of new generated temporary register.  */
+
+static tree
+make_new_tmp_statement (tree type, enum tree_code code, tree op1, tree op2,
+			gimple ref_def)
+{
+  gimple sum;
+  tree tmpvar = create_tmp_reg (type, NULL);
+  add_referenced_var (tmpvar);
+  sum = build_and_add_sum (tmpvar, op1, op2, code);
+  if (ref_def)
+    gimple_set_location (sum, gimple_location (ref_def));
+  return gimple_get_lhs (sum);
+}
+
+/* Perform on tree LHS with optional definition statement EXPR
+   the logic-not operation.  TYPE is of kind boolean.  */
+
+static tree
+expand_not_bitwise_binary (tree type, tree lhs, gimple expr)
+{
+  enum tree_code code = ERROR_MARK;
+  tree op1 = NULL, op2 = NULL;
+  gimple s1 = NULL, s2 = NULL;
+
+  if (TREE_CODE (lhs) == INTEGER_CST)
+    return fold_build1 (BIT_NOT_EXPR, type, lhs);
+
+  if (expr && is_gimple_assign (expr))
+    code = gimple_assign_rhs_code (expr);
+
+  /* If statement lhs isn't a single-use statement,
+     we don't want to modify it. So we can do only default-case
+     operation for it.  */
+  if (code != ERROR_MARK && !has_single_use (lhs))
+    code = ERROR_MARK;
+
+  if (TREE_CODE_CLASS (code) == tcc_comparison
+      || code == BIT_XOR_EXPR
+      || code == BIT_AND_EXPR
+      || code == BIT_IOR_EXPR)
+    {
+      op1 = gimple_assign_rhs1 (expr);
+      op2 = gimple_assign_rhs2 (expr);
+    }
+  /* ~(~X) -> X.  */
+  else if (code == BIT_NOT_EXPR)
+    return gimple_assign_rhs1 (expr);
+  else
+    return make_new_tmp_statement (TREE_TYPE (lhs), BIT_NOT_EXPR, lhs,
+				   NULL_TREE, expr);
+
+  /* ~(X cmp Y) -> X cmp' Y, with cmp'=inverted comparison code, if allowed.
+     Otherwise fall through to default case.  */
+  if (TREE_CODE_CLASS (code) == tcc_comparison)
+    {
+      enum tree_code ncode;
+      tree op1type = TREE_TYPE (op1);
+
+      ncode = invert_tree_comparison (code,
+				      HONOR_NANS (TYPE_MODE (op1type)));
+      if (ncode != ERROR_MARK)
+	return make_new_tmp_statement (type, ncode, op1, op2, expr);
+    }
+  /* Handle transformation for ~(A & B) -> ~A | ~B or ~(A | B) -> ~A & ~B.  */
+  else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+    {
+      /* See if left-hand operand is a gimple-assign, and has single-use. */
+      if (TREE_CODE (op1) != SSA_NAME
+          || !(s1 = SSA_NAME_DEF_STMT (op1))
+          || !is_gimple_assign (s1)
+          || !has_single_use (op1))
+	s1 = NULL;
+      /* See if right-hand operand is a gimple-assign, and has
+         single-use. */
+      if (TREE_CODE (op2) != SSA_NAME
+          || !(s2 = SSA_NAME_DEF_STMT (op2))
+          || !is_gimple_assign (s2)
+          || !has_single_use (op2))
+	s2 = NULL;
+
+      /* We have to do inversion in one step to avoid looping.  */
+      op1 = expand_not_bitwise_binary (type, op1, s1);
+      op2 = expand_not_bitwise_binary (type, op2, s2);
+
+      code = (code == BIT_AND_EXPR ? BIT_IOR_EXPR : BIT_AND_EXPR);
+
+      if (TREE_CODE (op2) == INTEGER_CST)
+        {
+	  if ((code == BIT_AND_EXPR && integer_zerop (op2))
+	      || (code == BIT_IOR_EXPR && integer_all_onesp (op2)))
+	    {
+	      remove_stmt_chain (op1);
+	      return op2;
+	    }
+	  else if ((code == BIT_AND_EXPR && integer_all_onesp (op2))
+	           || (code == BIT_IOR_EXPR && integer_zerop (op2)))
+	    return op1;
+	}
+      return make_new_tmp_statement (type, code, op1, op2, expr);
+    }
+  /* ~(A ^ B) -> ~A ^ B.  Handle here special cases for B being
+     an integer constant, or being a logical-not.  */
+  else if (code == BIT_XOR_EXPR)
+    {
+      /* See if left-hand operand is a gimple-assign, and has single-use. */
+      if (TREE_CODE (op1) != SSA_NAME
+          || !(s1 = SSA_NAME_DEF_STMT (op1))
+          || !is_gimple_assign (s1)
+          || !has_single_use (op1))
+	s1 = NULL;
+      /* See if right-hand operand is a gimple-assign, and has
+         single-use. */
+      if (TREE_CODE (op2) != SSA_NAME
+          || !(s2 = SSA_NAME_DEF_STMT (op2))
+          || !is_gimple_assign (s2)
+          || !has_single_use (op2))
+	s2 = NULL;
+
+      /* If right-hand operand isn't a bit-not expression and not
+         an integeral constant, then we apply bit-not on left-hand
+         operand.  */
+      if (TREE_CODE (op2) != INTEGER_CST
+	  && (!s2 || gimple_assign_rhs_code (s2) != BIT_NOT_EXPR))
+        op1 = expand_not_bitwise_binary (type, op1, s1);
+      else
+        op2 = expand_not_bitwise_binary (type, op2, s2);
+
+      if (TREE_CODE (op2) == INTEGER_CST && integer_zerop (op2))
+	return op1;
+      if (TREE_CODE (op2) == INTEGER_CST && integer_all_onesp (op2))
+        {
+	  remove_stmt_chain (op2);
+	  return make_new_tmp_statement (type, BIT_NOT_EXPR, op1, NULL, expr);
+	}
+      return make_new_tmp_statement (type, BIT_XOR_EXPR, op1, op2, expr);
+    }
+
+  gcc_assert (types_compatible_p (type, TREE_TYPE (lhs)));
+
+  /* Default case lhs -> ~lhs  */
+  return make_new_tmp_statement (TREE_TYPE (lhs), BIT_NOT_EXPR, lhs,
+				 NULL_TREE, expr);
+}
+
+/* Break up STMT if it is a combined statement made out of
+   bitwise operations.  Handle expansion of ~(A op B).  */
+
+static bool
+break_up_bitwise_combined_stmt (gimple stmt)
+{
+  tree op1, op2, old_op1, old_op2;
+  gimple op1_def, op2_def;
+  enum tree_code code = gimple_assign_rhs_code (stmt);
+  tree type = TREE_TYPE (gimple_assign_lhs (stmt));
+  gimple_stmt_iterator gsi;
+
+  op1 = gimple_assign_rhs1 (stmt);
+  old_op1 = op1;
+  old_op2 = op2 = NULL_TREE;
+
+  /* Check that CODE can be handled and that left-hand operand
+     is of kind SSA_NAME.  */
+  if (code != BIT_NOT_EXPR
+      || TREE_CODE (op1) != SSA_NAME)
+    return false;
+
+  /* If left-hand operand isn't a gimple-assign, or isn't single-used,
+     the we can't do anything.  */
+  op1_def = SSA_NAME_DEF_STMT (op1);
+  if (!op1_def
+      || !is_gimple_assign (op1_def)
+      || !has_single_use (op1))
+    return false;
+
+  /* Handle expansion for ~X.  */
+  if (code == BIT_NOT_EXPR)
+    {
+      enum tree_code inner_code = gimple_assign_rhs_code (op1_def);
+
+      if (inner_code == BIT_NOT_EXPR)
+        {
+	  op1 = gimple_assign_rhs1 (op1_def);
+	  gsi = gsi_for_stmt (stmt);
+	  gimple_assign_set_rhs_from_tree (&gsi, op1);
+	  update_stmt (gsi_stmt (gsi));
+	  remove_stmt_chain (old_op1);
+	  return true;
+	}
+      else if (TREE_CODE_CLASS (inner_code) == tcc_comparison)
+        {
+	  enum tree_code ncode;
+	  tree op1type;
+
+	  op1 = gimple_assign_rhs1 (op1_def);
+	  op2 = gimple_assign_rhs2 (op1_def);
+	  op1type = TREE_TYPE (op1);
+	  ncode = invert_tree_comparison (inner_code,
+					  HONOR_NANS (TYPE_MODE (op1type)));
+	  if (ncode == ERROR_MARK)
+	    return false;
+	  gsi = gsi_for_stmt (stmt);
+	  gimple_assign_set_rhs_with_ops (&gsi, ncode, op1, op2);
+	  update_stmt (gsi_stmt (gsi));
+	  remove_stmt_chain (old_op1);
+	  return true;
+	}
+      if (inner_code != BIT_AND_EXPR && inner_code != BIT_IOR_EXPR
+          && inner_code != BIT_XOR_EXPR)
+	return false;
+
+      op1 = gimple_assign_rhs1 (op1_def);
+      op2 = gimple_assign_rhs2 (op1_def);
+
+      op1_def = op2_def = NULL;
+
+      if (TREE_CODE (op1) != SSA_NAME
+	  || (op1_def = SSA_NAME_DEF_STMT (op1)) == NULL
+	  || !is_gimple_assign (op1_def))
+	op1_def = NULL;
+
+      if (TREE_CODE (op2) != SSA_NAME
+	  || (op2_def = SSA_NAME_DEF_STMT (op2)) == NULL
+	  || !is_gimple_assign (op2_def))
+	op2_def = NULL;
+
+      /* Transform as best representation either from
+         ~(X ^ Y) to ~X ^ Y, or from ~(X ^ Y) to X ^ Y.  */
+      if (inner_code == BIT_XOR_EXPR)
+	{
+          if (TREE_CODE (op2) != INTEGER_CST
+	      && (!op2_def || !is_gimple_assign (op2_def)
+	          || !has_single_use (op2)
+	          || gimple_assign_rhs_code (op2_def) != BIT_NOT_EXPR))
+            op1 = expand_not_bitwise_binary (type, op1, op1_def);
+          else
+            op2 = expand_not_bitwise_binary (type, op2, op2_def);
+	}
+      /* Transform ~(X | Y) -> ~X & Y, or ~(X & Y) -> ~X | ~Y.  */
+      else
+	{
+          op1 = expand_not_bitwise_binary (type, op1, op1_def);
+          op2 = expand_not_bitwise_binary (type, op2, op2_def);
+	  inner_code = (inner_code == BIT_AND_EXPR ? BIT_IOR_EXPR
+						   : BIT_AND_EXPR);
+	}
+      gsi = gsi_for_stmt (stmt);
+      gimple_assign_set_rhs_with_ops (&gsi, inner_code, op1, op2);
+      update_stmt (gsi_stmt (gsi));
+      remove_stmt_chain (old_op1);
+      return true;
+    }
+
+  return false;
+}
+
 /* If CURR and LAST are a pair of ops that OPCODE allows us to
    eliminate through equivalences, do so, remove them from OPS, and
    return true.  Otherwise, return false.  */
@@ -2076,6 +2339,49 @@  remove_visited_stmt_chain (tree var)
     }
 }

+/* Remove def stmt of VAR if VAR has zero uses and recurse
+   on rhs1, rhs2, and rhs3 operand if so.  */
+
+static void
+remove_stmt_chain (tree var)
+{
+  gimple stmt;
+  gimple_stmt_iterator gsi;
+  tree var2, var3;
+
+  while (1)
+    {
+      if (TREE_CODE (var) != SSA_NAME || !has_zero_uses (var))
+	return;
+      stmt = SSA_NAME_DEF_STMT (var);
+      if (!stmt || !is_gimple_assign (stmt))
+	return;
+      var = gimple_assign_rhs1 (stmt);
+      var2 = var3 = NULL_TREE;
+
+      switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
+        {
+	case  GIMPLE_TERNARY_RHS:
+	  var3 = gimple_assign_rhs3 (stmt);
+	  /* Fall through.  */
+	case GIMPLE_BINARY_RHS:
+	  var2 = gimple_assign_rhs2 (stmt);
+	  break;
+	default:
+	  break;
+	}
+      gsi = gsi_for_stmt (stmt);
+      gsi_remove (&gsi, true);
+      release_defs (stmt);
+      /* Recurse on optional second and third operand,
+         if those arguments are of kind SSA_NAME.  */
+      if (var2 && TREE_CODE (var2) == SSA_NAME)
+        remove_stmt_chain (var2);
+      if (var3 && TREE_CODE (var3) == SSA_NAME)
+        remove_stmt_chain (var3);
+    }
+}
+
 /* This function checks three consequtive operands in
    passed operands vector OPS starting from OPINDEX and
    swaps two operands if it is profitable for binary operation
@@ -2777,6 +3083,14 @@  can_reassociate_p (tree op)
    we want to break up k = t - q, but we won't until we've transformed q
    = b - r, which won't be broken up until we transform b = c - d.

+   Break up logical-not expressions of bitwise boolean-typed and/or/xor
+   operations for being able to optimize wihin combined conditions.
+   ~(A | B) -> ~A | ~B
+   ~(A & B) -> ~A & ~B
+   ~(A ^ B) -> A ^ ~B (special case if B is a constant)
+   If A or B are comparisons or are bitwise-not statement, then sink bit-not
+   into expression, if it is a single-use statement.
+
    En passant, clear the GIMPLE visited flag on every statement.  */

 static void
@@ -2785,21 +3099,34 @@  break_up_expr_bb (basic_block bb)
   gimple_stmt_iterator gsi;
   basic_block son;

-  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
     {
       gimple stmt = gsi_stmt (gsi);
       gimple_set_visited (stmt, false);

-      if (!is_gimple_assign (stmt)
-	  || !can_reassociate_p (gimple_assign_lhs (stmt)))
+      if (!is_gimple_assign (stmt))
+        {
+	  gsi_next (&gsi);
+	  continue;
+        }
+      if (break_up_bitwise_combined_stmt (stmt))
 	continue;

+      if (!can_reassociate_p (gimple_assign_lhs (stmt)))
+        {
+	  gsi_next (&gsi);
+	  continue;
+	}
+
       /* Look for simple gimple subtract operations.  */
       if (gimple_assign_rhs_code (stmt) == MINUS_EXPR)
 	{
 	  if (!can_reassociate_p (gimple_assign_rhs1 (stmt))
 	      || !can_reassociate_p (gimple_assign_rhs2 (stmt)))
-	    continue;
+	    {
+	      gsi_next (&gsi);
+	      continue;
+	    }

 	  /* Check for a subtract used only in an addition.  If this
 	     is the case, transform it into add of a negate for better
@@ -2811,6 +3138,8 @@  break_up_expr_bb (basic_block bb)
       else if (gimple_assign_rhs_code (stmt) == NEGATE_EXPR
 	       && can_reassociate_p (gimple_assign_rhs1 (stmt)))
 	VEC_safe_push (tree, heap, plus_negates, gimple_assign_lhs (stmt));
+
+      gsi_next (&gsi);
     }
   for (son = first_dom_son (CDI_DOMINATORS, bb);
        son;
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-not-1.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-not-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);
+  int r2 = (a | d | c) | ~b;
+  return (~r1 | r2);
+}
+
+/* { 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-not-2.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-not-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 & ~c & b;
+  int r2 = ~a | b | ~d;
+  return (~r1 | r2);
+}
+
+/* { 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-not-3.c
===================================================================
--- /dev/null
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/reassoc-not-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 & ~c & b;
+  int r2 = ~a | b | ~d;
+  return (r1 & ~r2);
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
+