re PR tree-optimization/51988 (value_replacement in PHIOPT should handle even the cases where there are other PHIs even with non equal value)

2012-03-09  Andrew Pinski  <apinski@cavium.com>

	PR middle-end/51988
	* tree-ssa-phiopt.c: Include tree-pretty-print.h for
	print_generic_expr.
	(tree_ssa_phiopt_worker): Go through all the PHIs for
	value_replacement instead of just the singleton one.
	(value_replacement): Change return type to int.  Return 0 instead of
	false.
	Allow the middle basic block to contain more than just the definings
	tatement. 
	Handle non empty middle basic blocks.
	* Makefile.in (tree-ssa-phiopt.o): Add tree-pretty-print.h.

2012-03-09  Andrew Pinski  <apinski@cavium.com>

	PR middle-end/51988
	* gcc.dg/tree-ssa/phi-opt-8.c: New testcase.
	* gcc.dg/tree-ssa/phi-opt-9.c: New testcase.

From-SVN: r185131

6 files changed, 139 insertions, 35 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 31bad53..1bce1c7 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2012-03-09  Andrew Pinski  <apinski@cavium.com>
+
+	PR middle-end/51988
+	* tree-ssa-phiopt.c: Include tree-pretty-print.h for
+	print_generic_expr.
+	(tree_ssa_phiopt_worker): Go through all the PHIs for
+	value_replacement instead of just the singleton one.
+	(value_replacement): Change return type to int.  Return 0 instead of
+	false.
+	Allow the middle basic block to contain more than just the definings
+	tatement. 
+	Handle non empty middle basic blocks.
+	* Makefile.in (tree-ssa-phiopt.o): Add tree-pretty-print.h.
+
 2012-03-09  Jiangning Liu  <jiangning.liu@arm.com>
 
 	* tree-scalar-evolution (interpret_rhs_expr): generate chrec for
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 6e7148f..b519099 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -2355,7 +2355,7 @@ tree-ssa-phiopt.o : tree-ssa-phiopt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    $(TM_H) $(GGC_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) \
    $(TREE_FLOW_H) $(TREE_PASS_H) $(TREE_DUMP_H) langhooks.h $(FLAGS_H) \
    $(DIAGNOSTIC_H) $(TIMEVAR_H) pointer-set.h domwalk.h $(CFGLOOP_H) \
-   $(TREE_DATA_REF_H)
+   $(TREE_DATA_REF_H) tree-pretty-print.h
 tree-nrv.o : tree-nrv.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    $(TM_H) $(TREE_H) $(FUNCTION_H) $(BASIC_BLOCK_H) $(FLAGS_H) \
    $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TIMEVAR_H) $(TREE_DUMP_H) $(TREE_PASS_H) \
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index ad8c218..f1c9845 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2012-03-09  Andrew Pinski  <apinski@cavium.com>
+
+	PR middle-end/51988
+	* gcc.dg/tree-ssa/phi-opt-8.c: New testcase.
+	* gcc.dg/tree-ssa/phi-opt-9.c: New testcase.
+
 2012-03-09  Jiangning Liu  <jiangning.liu@arm.com>
 
 	* gcc.dg/tree-ssa/scev-3.c: New.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-8.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-8.c
new file mode 100644
index 0000000..31dab46
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-8.c
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized -fdump-tree-phiopt1" } */
+
+int g(int,int);
+int f(int t, int c)
+{
+  int d = 0;
+  int e = 0;
+  if (t)
+    {
+      d = 1;
+      e = t;
+    }
+  else d = 0, e = 0;
+  return g(e,d);
+}
+
+/* This testcase should be reduced to e = t; d = t != 0; in phiopt1
+   but currently is not as PHI-OPT does not reduce the t PHI as we have
+   two phis.  Note this is fixed with
+   http://gcc.gnu.org/ml/gcc-patches/2012-01/msg01195.html .  */
+/* { dg-final { scan-tree-dump-not "if" "phiopt1" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump "g .t_\[0-9\]*.D.," "optimized" } } */
+/* { dg-final { scan-tree-dump-not "PHI" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "phiopt1" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-9.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-9.c
new file mode 100644
index 0000000..dccea7b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-9.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+int g(int,int);
+int f(int t, int c)
+{
+  int d = 0;
+  int e = 0;
+  if (t)
+    {
+      d = c+1;
+      e = t;
+    }
+  else d = 0, e = 0;
+  return g(e,d);
+}
+
+/* The value e should have been replaced with t and there should be only one PHI. */
+/* { dg-final { scan-tree-dump "g .t_\[0-9\]*.D.," "optimized" } } */
+/* { dg-final { scan-tree-dump-times "PHI" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c
index 0cef8ee..c195e3b 100644
--- a/gcc/tree-ssa-phiopt.c
+++ b/gcc/tree-ssa-phiopt.c
@@ -36,13 +36,14 @@ along with GCC; see the file COPYING3.  If not see
 #include "domwalk.h"
 #include "cfgloop.h"
 #include "tree-data-ref.h"
+#include "tree-pretty-print.h"
 
 static unsigned int tree_ssa_phiopt (void);
 static unsigned int tree_ssa_phiopt_worker (bool);
 static bool conditional_replacement (basic_block, basic_block,
 				     edge, edge, gimple, tree, tree);
-static bool value_replacement (basic_block, basic_block,
-			       edge, edge, gimple, tree, tree);
+static int value_replacement (basic_block, basic_block,
+			      edge, edge, gimple, tree, tree);
 static bool minmax_replacement (basic_block, basic_block,
 				edge, edge, gimple, tree, tree);
 static bool abs_replacement (basic_block, basic_block,
@@ -314,7 +315,24 @@ tree_ssa_phiopt_worker (bool do_store_elim)
 	{
 	  gimple_seq phis = phi_nodes (bb2);
 	  gimple_stmt_iterator gsi;
+	  bool candorest = true;
+	  /* Value replacement can work with more than one PHI
+	     so try that first. */
+	  for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
+	    {
+	      phi = gsi_stmt (gsi);
+	      arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
+	      arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
+	      if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
+		{
+		  candorest = false;
+	          cfgchanged = true;
+		  break;
+		}
+	    }
 
+	  if (!candorest)
+	    continue;
 	  /* Check to make sure that there is only one non-virtual PHI node.
 	     TODO: we could do it with more than one iff the other PHI nodes
 	     have the same elements for these two edges.  */
@@ -343,8 +361,6 @@ tree_ssa_phiopt_worker (bool do_store_elim)
 	  /* Do the replacement of conditional if it can be done.  */
 	  if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 	    cfgchanged = true;
-	  else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
-	    cfgchanged = true;
 	  else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 	    cfgchanged = true;
 	  else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
@@ -624,12 +640,12 @@ jump_function_from_stmt (tree *arg, gimple stmt)
 }
 
 /*  The function value_replacement does the main work of doing the value
-    replacement.  Return true if the replacement is done.  Otherwise return
-    false.
+    replacement.  Return non-zero if the replacement is done.  Otherwise return
+    0.  If we remove the middle basic block, return 2.
     BB is the basic block where the replacement is going to be done on.  ARG0
     is argument 0 from the PHI.  Likewise for ARG1.  */
 
-static bool
+static int
 value_replacement (basic_block cond_bb, basic_block middle_bb,
 		   edge e0, edge e1, gimple phi,
 		   tree arg0, tree arg1)
@@ -638,37 +654,36 @@ value_replacement (basic_block cond_bb, basic_block middle_bb,
   gimple cond;
   edge true_edge, false_edge;
   enum tree_code code;
+  bool emtpy_or_with_defined_p = true;
 
   /* If the type says honor signed zeros we cannot do this
      optimization.  */
   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
-    return false;
+    return 0;
 
-  /* Allow a single statement in MIDDLE_BB that defines one of the PHI
-     arguments.  */
+  /* 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))
+  if (!gsi_end_p (gsi) && is_gimple_debug (gsi_stmt (gsi)))
+    gsi_next_nondebug (&gsi);
+  while (!gsi_end_p (gsi))
     {
-      if (is_gimple_debug (gsi_stmt (gsi)))
-	gsi_next_nondebug (&gsi);
-      if (!gsi_end_p (gsi))
+      gimple stmt = gsi_stmt (gsi);
+      tree lhs;
+      gsi_next_nondebug (&gsi);
+      if (!is_gimple_assign (stmt))
 	{
-	  gimple stmt = gsi_stmt (gsi);
-	  tree lhs;
-	  gsi_next_nondebug (&gsi);
-	  if (!gsi_end_p (gsi))
-	    return false;
-	  if (!is_gimple_assign (stmt))
-	    return false;
-	  /* Now try to adjust arg0 or arg1 according to the computation
-	     in the single statement.  */
-	  lhs = gimple_assign_lhs (stmt);
-	  if (!((lhs == arg0
-		 && jump_function_from_stmt (&arg0, stmt))
-		|| (lhs == arg1
-		    && jump_function_from_stmt (&arg1, stmt))))
-	    return false;
+	  emtpy_or_with_defined_p = false;
+	  continue;
 	}
+      /* Now try to adjust arg0 or arg1 according to the computation
+	 in the statement.  */
+      lhs = gimple_assign_lhs (stmt);
+      if (!(lhs == arg0
+	     && jump_function_from_stmt (&arg0, stmt))
+	    || (lhs == arg1
+		&& jump_function_from_stmt (&arg1, stmt)))
+	emtpy_or_with_defined_p = false;
     }
 
   cond = last_stmt (cond_bb);
@@ -676,7 +691,7 @@ value_replacement (basic_block cond_bb, basic_block middle_bb,
 
   /* This transformation is only valid for equality comparisons.  */
   if (code != NE_EXPR && code != EQ_EXPR)
-    return false;
+    return 0;
 
   /* We need to know which is the true edge and which is the false
       edge so that we know if have abs or negative abs.  */
@@ -720,12 +735,34 @@ value_replacement (basic_block cond_bb, basic_block middle_bb,
       else
 	arg = arg1;
 
-      replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
+      /* If the middle basic block was empty or is defining the
+	 PHI arguments and this is a singleton phi then we can remove
+         the middle basic block. */
+      if (emtpy_or_with_defined_p
+	  && gimple_seq_singleton_p (phi_nodes (gimple_bb (phi))))
+	{
+          replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
+	  /* Note that we optimized this PHI.  */
+	  return 2;
+	}
+      else
+	{
+	  /* Replace the PHI arguments with arg. */
+	  SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
+	  SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "PHI ");
+	      print_generic_expr (dump_file, gimple_phi_result (phi), 0);
+	      fprintf (dump_file, " reduced for COND_EXPR in block %d to ", cond_bb->index);
+	      print_generic_expr (dump_file, arg, 0);
+	      fprintf (dump_file, ".\n");
+            }
+          return 1;
+	}
 
-      /* Note that we optimized this PHI.  */
-      return true;
     }
-  return false;
+  return 0;
 }
 
 /*  The function minmax_replacement does the main work of doing the minmax