[PATCH] Fix SCCVN to optimistically value-number PHIs with backedges

[Richard Biener <rguenther at suse dot de>]

The following patch fixes a preference that causes SCCVN to fail to
eliminate redundant IVs.  It will prefer to try eliminating IVs to
eliminating degenerate PHIs (if the degenerate PHI has a backedge).
I failed to create a testcase for that - the one below is essentially
what the vectorizer can end up generating (bah).  I believe it
will still work out in the end, just FRE itself won't remove the
PHI node in a single pass iteration but just value-number to
a degenerate PHI (a testcase would still be nice - I'm still trying).

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Richard.

2015-06-10  Richard Biener  <rguenther@suse.de>

	* 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.

Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c	(revision 224324)
+++ gcc/tree-ssa-sccvn.c	(working copy)
@@ -2682,17 +2679,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);
@@ -2745,16 +2749,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;
@@ -2778,15 +2784,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));
@@ -3284,15 +3293,14 @@ visit_phi (gimple phi)
 	  }
       }
 
-  /* 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.  */
   result = vn_phi_lookup (phi);
   if (result)
     changed = set_ssa_val_to (PHI_RESULT (phi), result);
+  /* If 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));
@@ -4182,6 +4190,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);
 
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c	(working copy)
@@ -0,0 +1,22 @@
+/* { 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" } } */