public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] Fix PRs 66502 and 67167
@ 2015-08-13  7:46 Richard Biener
  2015-08-21  9:45 ` Jiong Wang
  0 siblings, 1 reply; 5+ messages in thread
From: Richard Biener @ 2015-08-13  7:46 UTC (permalink / raw)
  To: gcc-patches


Given there is now PR67167 I am going forward with the earlier posted
patch to switch SCCVN to PHI elimination in favor of another PHI
(to remove IVs) rather than in favor of its only executable edge value.

I still see no way to capture both cases without detecting the choice
and re-numbering the SCC twice, eventually choosing the "better" outcome.
And then the situation where both cases happen in the same SCC is not
handled either.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

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.

Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c	(revision 226807)
+++ gcc/tree-ssa-sccvn.c	(working copy)
@@ -2655,17 +2655,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);
@@ -2718,16 +2725,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;
@@ -2751,15 +2760,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));
@@ -3244,28 +3256,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));
@@ -4155,6 +4162,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" } } */

^ permalink raw reply	[flat|nested] 5+ messages in thread
end of thread, other threads:[~2015-11-06 10:36 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-08-13  7:46 [PATCH] Fix PRs 66502 and 67167 Richard Biener
2015-08-21  9:45 ` Jiong Wang
2015-08-21  9:53   ` Richard Biener
2015-08-21 10:05     ` Jiong Wang
2015-11-06 10:36       ` Jiong Wang

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).