re PR tree-optimization/59100 (requesting optimization of safe rotate function)

2014-05-08  Marc Glisse  <marc.glisse@inria.fr>

	PR tree-optimization/59100
gcc/
	* tree-ssa-phiopt.c: Include tree-inline.h.
	(neutral_element_p, absorbing_element_p): New functions.
	(value_replacement): Handle conditional binary operations with a
	neutral or absorbing element.
gcc/testsuite/
	* gcc.dg/tree-ssa/phi-opt-12.c: New file.
	* gcc.dg/tree-ssa/phi-opt-13.c: Likewise.

From-SVN: r210212

5 files changed, 157 insertions, 3 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 4bfa078..5b03676 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2014-05-08  Marc Glisse  <marc.glisse@inria.fr>
+
+	PR tree-optimization/59100
+	* tree-ssa-phiopt.c: Include tree-inline.h.
+	(neutral_element_p, absorbing_element_p): New functions.
+	(value_replacement): Handle conditional binary operations with a
+	neutral or absorbing element.
+
 2014-05-08  Richard Biener  <rguenther@suse.de>
 
 	* tree-ssa-sccvn.c (vn_get_expr_for): Valueize operands before
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index ce196b0..ad7a652 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2014-05-08  Marc Glisse  <marc.glisse@inria.fr>
+
+	PR tree-optimization/59100
+	* gcc.dg/tree-ssa/phi-opt-12.c: New file.
+	* gcc.dg/tree-ssa/phi-opt-13.c: Likewise.
+
 2014-05-08  Richard Sandiford  <rdsandiford@googlemail.com>
 
 	PR tree-optimization/61095
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-12.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-12.c
new file mode 100644
index 0000000..b52c6d7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-12.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-phiopt1" } */
+
+int f(int a, int b, int c) {
+  if (c > 5) return c;
+  if (a == 0) return b;
+  return a + b;
+}
+
+unsigned rot(unsigned x, int n) {
+  const int bits = __CHAR_BIT__ * __SIZEOF_INT__;
+  return (n == 0) ? x : ((x << n) | (x >> (bits - n)));
+}
+
+unsigned m(unsigned a, unsigned b) {
+  if (a == 0)
+    return 0;
+  else
+    return a & b;
+}
+
+/* { dg-final { scan-tree-dump-times "goto" 2 "phiopt1" } } */
+/* { dg-final { cleanup-tree-dump "phiopt1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-13.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-13.c
new file mode 100644
index 0000000..3e09c21
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-13.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+// Division is expensive
+long f(long a, long b) {
+  if (__builtin_expect(b == 1, 1)) return a;
+  return a / b;
+}
+
+/* { dg-final { scan-tree-dump-times "goto " 2 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c
index 28a6ea7..d4aaf42 100644
--- a/gcc/tree-ssa-phiopt.c
+++ b/gcc/tree-ssa-phiopt.c
@@ -54,6 +54,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "expr.h"
 #include "optabs.h"
 #include "tree-scalar-evolution.h"
+#include "tree-inline.h"
 
 #ifndef HAVE_conditional_move
 #define HAVE_conditional_move (0)
@@ -659,6 +660,64 @@ operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
   return false;
 }
 
+/* Returns true if ARG is a neutral element for operation CODE
+   on the RIGHT side.  */
+
+static bool
+neutral_element_p (tree_code code, tree arg, bool right)
+{
+  switch (code)
+    {
+    case PLUS_EXPR:
+    case BIT_IOR_EXPR:
+    case BIT_XOR_EXPR:
+      return integer_zerop (arg);
+
+    case LROTATE_EXPR:
+    case RROTATE_EXPR:
+    case LSHIFT_EXPR:
+    case RSHIFT_EXPR:
+    case MINUS_EXPR:
+    case POINTER_PLUS_EXPR:
+      return right && integer_zerop (arg);
+
+    case MULT_EXPR:
+      return integer_onep (arg);
+
+    case TRUNC_DIV_EXPR:
+    case CEIL_DIV_EXPR:
+    case FLOOR_DIV_EXPR:
+    case ROUND_DIV_EXPR:
+    case EXACT_DIV_EXPR:
+      return right && integer_onep (arg);
+
+    case BIT_AND_EXPR:
+      return integer_all_onesp (arg);
+
+    default:
+      return false;
+    }
+}
+
+/* Returns true if ARG is an absorbing element for operation CODE.  */
+
+static bool
+absorbing_element_p (tree_code code, tree arg)
+{
+  switch (code)
+    {
+    case BIT_IOR_EXPR:
+      return integer_all_onesp (arg);
+
+    case MULT_EXPR:
+    case BIT_AND_EXPR:
+      return integer_zerop (arg);
+
+    default:
+      return false;
+    }
+}
+
 /*  The function value_replacement does the main work of doing the value
     replacement.  Return non-zero if the replacement is done.  Otherwise return
     0.  If we remove the middle basic block, return 2.
@@ -683,9 +742,7 @@ value_replacement (basic_block cond_bb, basic_block middle_bb,
 
   /* If there is a statement in MIDDLE_BB that defines one of the PHI
      arguments, then adjust arg0 or arg1.  */
-  gsi = gsi_after_labels (middle_bb);
-  if (!gsi_end_p (gsi) && is_gimple_debug (gsi_stmt (gsi)))
-    gsi_next_nondebug (&gsi);
+  gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
   while (!gsi_end_p (gsi))
     {
       gimple stmt = gsi_stmt (gsi);
@@ -781,6 +838,55 @@ value_replacement (basic_block cond_bb, basic_block middle_bb,
 	}
 
     }
+
+  /* Now optimize (x != 0) ? x + y : y to just y.
+     The following condition is too restrictive, there can easily be another
+     stmt in middle_bb, for instance a CONVERT_EXPR for the second argument.  */
+  gimple assign = last_and_only_stmt (middle_bb);
+  if (!assign || gimple_code (assign) != GIMPLE_ASSIGN
+      || gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS
+      || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
+	  && !POINTER_TYPE_P (TREE_TYPE (arg0))))
+    return 0;
+
+  /* Size-wise, this is always profitable.  */
+  if (optimize_bb_for_speed_p (cond_bb)
+      /* The special case is useless if it has a low probability.  */
+      && profile_status_for_fn (cfun) != PROFILE_ABSENT
+      && EDGE_PRED (middle_bb, 0)->probability < PROB_EVEN
+      /* If assign is cheap, there is no point avoiding it.  */
+      && estimate_num_insns (assign, &eni_time_weights)
+	 >= 3 * estimate_num_insns (cond, &eni_time_weights))
+    return 0;
+
+  tree lhs = gimple_assign_lhs (assign);
+  tree rhs1 = gimple_assign_rhs1 (assign);
+  tree rhs2 = gimple_assign_rhs2 (assign);
+  enum tree_code code_def = gimple_assign_rhs_code (assign);
+  tree cond_lhs = gimple_cond_lhs (cond);
+  tree cond_rhs = gimple_cond_rhs (cond);
+
+  if (((code == NE_EXPR && e1 == false_edge)
+	|| (code == EQ_EXPR && e1 == true_edge))
+      && arg0 == lhs
+      && ((arg1 == rhs1
+	   && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
+	   && neutral_element_p (code_def, cond_rhs, true))
+	  || (arg1 == rhs2
+	      && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
+	      && neutral_element_p (code_def, cond_rhs, false))
+	  || (operand_equal_for_phi_arg_p (arg1, cond_rhs)
+	      && (operand_equal_for_phi_arg_p (rhs2, cond_lhs)
+		  || operand_equal_for_phi_arg_p (rhs1, cond_lhs))
+	      && absorbing_element_p (code_def, cond_rhs))))
+    {
+      gsi = gsi_for_stmt (cond);
+      gimple_stmt_iterator gsi_from = gsi_for_stmt (assign);
+      gsi_move_before (&gsi_from, &gsi);
+      replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
+      return 2;
+    }
+
   return 0;
 }