re PR tree-optimization/66502 (SCCVN can't handle PHIs optimistically optimally)

2015-08-13  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/66502
	PR tree-optimization/67167
	* tree-ssa-sccvn.c (vn_phi_compute_hash): Do not include
	backedge arguments.
	(vn_phi_lookup): Adjust.
	(vn_phi_insert): Likewise.
	(visit_phi): Prefer to value-number to another PHI node
	over value-numbering to a PHI argument.
	(init_scc_vn): Mark DFS back edges.

	* gcc.dg/tree-ssa/ssa-fre-46.c: New testcase.

From-SVN: r226850

4 files changed, 73 insertions, 25 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index ae73d58..6b62396 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,17 @@
 2015-08-13  Richard Biener  <rguenther@suse.de>
 
+	PR tree-optimization/66502
+	PR tree-optimization/67167
+	* tree-ssa-sccvn.c (vn_phi_compute_hash): Do not include
+	backedge arguments.
+	(vn_phi_lookup): Adjust.
+	(vn_phi_insert): Likewise.
+	(visit_phi): Prefer to value-number to another PHI node
+	over value-numbering to a PHI argument.
+	(init_scc_vn): Mark DFS back edges.
+
+2015-08-13  Richard Biener  <rguenther@suse.de>
+
 	* gimple.h (gcall::code_): New constant static member.
 	(gcond::code_): Likewise.
 	* gimple.c (gcall::code_): Define.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 1b49702..79d408e 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2015-08-13  Richard Biener  <rguenther@suse.de>
+
+	PR tree-optimization/66502
+	PR tree-optimization/67167
+	* gcc.dg/tree-ssa/ssa-fre-46.c: New testcase.
+
 2015-08-12  Paolo Carlini  <paolo.carlini@oracle.com>
 
 	PR c++/53330
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c
new file mode 100644
index 0000000..d6e6351
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-fre1-details" } */
+
+int x[1024];
+int foo (int a, int s, unsigned int k)
+{
+  int i = a, j = a;
+  int sum = 0;
+  do
+    {
+      sum += x[i];
+      sum += x[j];
+      i += s;
+      j += s;
+    }
+  while (k--);
+  return sum;
+}
+
+/* We want to remove the redundant induction variable and thus its PHI node.  */
+/* { dg-final { scan-tree-dump "Removing dead stmt \[^\r\n\]*PHI" "fre1" } } */
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 003433c..73d1070 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -2663,17 +2663,24 @@ static inline hashval_t
 vn_phi_compute_hash (vn_phi_t vp1)
 {
   inchash::hash hstate (vp1->block->index);
-  int i;
   tree phi1op;
   tree type;
+  edge e;
+  edge_iterator ei;
 
   /* If all PHI arguments are constants we need to distinguish
      the PHI node via its type.  */
   type = vp1->type;
   hstate.merge_hash (vn_hash_type (type));
 
-  FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
+  FOR_EACH_EDGE (e, ei, vp1->block->preds)
     {
+      /* Don't hash backedge values they need to be handled as VN_TOP
+         for optimistic value-numbering.  */
+      if (e->flags & EDGE_DFS_BACK)
+	continue;
+
+      phi1op = vp1->phiargs[e->dest_idx];
       if (phi1op == VN_TOP)
 	continue;
       inchash::add_expr (phi1op, hstate);
@@ -2726,16 +2733,18 @@ vn_phi_lookup (gimple phi)
 {
   vn_phi_s **slot;
   struct vn_phi_s vp1;
-  unsigned i;
+  edge e;
+  edge_iterator ei;
 
   shared_lookup_phiargs.truncate (0);
+  shared_lookup_phiargs.safe_grow (gimple_phi_num_args (phi));
 
   /* Canonicalize the SSA_NAME's to their value number.  */
-  for (i = 0; i < gimple_phi_num_args (phi); i++)
+  FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
     {
-      tree def = PHI_ARG_DEF (phi, i);
+      tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
       def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
-      shared_lookup_phiargs.safe_push (def);
+      shared_lookup_phiargs[e->dest_idx] = def;
     }
   vp1.type = TREE_TYPE (gimple_phi_result (phi));
   vp1.phiargs = shared_lookup_phiargs;
@@ -2759,15 +2768,18 @@ vn_phi_insert (gimple phi, tree result)
 {
   vn_phi_s **slot;
   vn_phi_t vp1 = current_info->phis_pool->allocate ();
-  unsigned i;
   vec<tree> args = vNULL;
+  edge e;
+  edge_iterator ei;
+
+  args.safe_grow (gimple_phi_num_args (phi));
 
   /* Canonicalize the SSA_NAME's to their value number.  */
-  for (i = 0; i < gimple_phi_num_args (phi); i++)
+  FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
     {
-      tree def = PHI_ARG_DEF (phi, i);
+      tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
       def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
-      args.safe_push (def);
+      args[e->dest_idx] = def;
     }
   vp1->value_id = VN_INFO (result)->value_id;
   vp1->type = TREE_TYPE (gimple_phi_result (phi));
@@ -3252,28 +3264,23 @@ visit_phi (gimple phi)
 	if (def == VN_TOP)
 	  continue;
 	if (sameval == VN_TOP)
+	  sameval = def;
+	else if (!expressions_equal_p (def, sameval))
 	  {
-	    sameval = def;
-	  }
-	else
-	  {
-	    if (!expressions_equal_p (def, sameval))
-	      {
-		allsame = false;
-		break;
-	      }
+	    allsame = false;
+	    break;
 	  }
       }
 
-  /* If all value numbered to the same value, the phi node has that
-     value.  */
-  if (allsame)
-    return set_ssa_val_to (PHI_RESULT (phi), sameval);
-
-  /* Otherwise, see if it is equivalent to a phi node in this block.  */
+  /* First see if it is equivalent to a phi node in this block.  We prefer
+     this as it allows IV elimination - see PRs 66502 and 67167.  */
   result = vn_phi_lookup (phi);
   if (result)
     changed = set_ssa_val_to (PHI_RESULT (phi), result);
+  /* Otherwise all value numbered to the same value, the phi node has that
+     value.  */
+  else if (allsame)
+    changed = set_ssa_val_to (PHI_RESULT (phi), sameval);
   else
     {
       vn_phi_insert (phi, PHI_RESULT (phi));
@@ -4163,6 +4170,8 @@ init_scc_vn (void)
   int *rpo_numbers_temp;
 
   calculate_dominance_info (CDI_DOMINATORS);
+  mark_dfs_back_edges ();
+
   sccstack.create (0);
   constant_to_value_id = new hash_table<vn_constant_hasher> (23);