Fix PR87263

Message ID alpine.LSU.2.20.1809131611450.16707@zhemvz.fhfr.qr
State New
Headers show
Series
  • Fix PR87263
Related show

Commit Message

Richard Biener Sept. 13, 2018, 2:13 p.m.
I'm using this PR as an excuse to put in the pending non-iteration
"iteration" rewrite.  This ensures that we've at least visited one
predecessor of a block and re-instantiates only visiting reachable
blocks.

{O1,}-Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.

It probably doesn't fully fix PR87263 but the regression police will
come up with more testcases soonish.

Richard.

2018-09-13  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/87263
	* tree-ssa-sccvn.c (visit_phi): Revert some earlier changes.
	(struct unwind_state): Add max_rpo field.
	(do_rpo_vn): Allow up-to-date loop state to be used when not iterating.
	Compute max_rpo, the max RPO number a block can be backwards reached
	from.  Re-write non-iterating mode to a RPO ordered worklist approach,
	separating it from the iterating mode.

	* gcc.dg/torture/pr87263.c: New testcase.
	* gcc.dg/torture/ssa-fre-2.c: Likewise.
	* gcc.dg/torture/ssa-fre-3.c: Likewise.
	* gcc.dg/torture/ssa-fre-4.c: Likewise.

Patch

Index: gcc/testsuite/gcc.dg/torture/pr87263.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr87263.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/torture/pr87263.c	(working copy)
@@ -0,0 +1,24 @@ 
+/* { dg-do compile } */
+
+int a, b, c;
+
+int main ()
+{ 
+  int g, *h[3] = {&g, &g, &g};
+  if (h[2] == 0)
+    ;
+  else
+    { 
+      int i[1];
+      if (a)
+	while (a)
+	  L:;
+      else
+	{
+	  int k = b;
+	}
+    }
+  if ((b < c) > b)
+    goto L;
+  return 0;
+}
Index: gcc/testsuite/gcc.dg/torture/ssa-fre-2.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/ssa-fre-2.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/torture/ssa-fre-2.c	(working copy)
@@ -0,0 +1,21 @@ 
+/* { dg-do run } */
+
+int x;
+int main()
+{
+  int i = 0;
+  x = 0;
+  if (x)
+    {
+      for (; i < 10; ++i)
+	{
+doit:
+	  x = i;
+	}
+    }
+  if (!x)
+    goto doit;
+  if (x != 9)
+    __builtin_abort ();
+  return 0;
+}
Index: gcc/testsuite/gcc.dg/torture/ssa-fre-3.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/ssa-fre-3.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/torture/ssa-fre-3.c	(working copy)
@@ -0,0 +1,23 @@ 
+/* { dg-do compile } */
+/* { dg-skip-if "" { *-*-* } { "-O0" } { "" } } */
+/* { dg-additional-options "-fdump-tree-fre1" } */
+
+int x;
+int main()
+{
+  x = 0;
+  int z = x;
+  int w = 1;
+  for (int i = 0; i < 32; ++i)
+    {
+      if (z)
+	w = 2;
+      else
+	w = 1;
+      if (w == 2)
+	__builtin_abort ();
+    }
+  return w;
+}
+
+/* { dg-final { scan-tree-dump-not "abort" "fre1" } } */
Index: gcc/testsuite/gcc.dg/torture/ssa-fre-4.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/ssa-fre-4.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/torture/ssa-fre-4.c	(working copy)
@@ -0,0 +1,17 @@ 
+/* { dg-do compile } */
+/* { dg-skip-if "" { *-*-* } { "-O0" } { "" } } */
+/* { dg-additional-options "-fdump-tree-fre1" } */
+
+int x;
+int main()
+{
+  x = 0;
+  if (x)
+    {
+      for (int i = 0; i < 10; ++i)
+	x = i;
+    }
+  return x;
+}
+
+/* { dg-final { scan-tree-dump "return 0;" "fre1" } } */
Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c	(revision 264267)
+++ gcc/tree-ssa-sccvn.c	(working copy)
@@ -4198,10 +4198,7 @@  visit_phi (gimple *phi, bool *inserted,
 	  }
       }
 
-  /* If the value we want to use is the backedge and that wasn't visited
-     yet or if we should take it as VARYING but it has a non-VARYING
-     value drop to VARYING.  This only happens when not iterating.
-     If we value-number a virtual operand never value-number to the
+  /* If we value-number a virtual operand never value-number to the
      value from the backedge as that confuses the alias-walking code.
      See gcc.dg/torture/pr87176.c.  If the value is the same on a
      non-backedge everything is OK though.  */
@@ -4209,9 +4206,7 @@  visit_phi (gimple *phi, bool *inserted,
       && !seen_non_backedge
       && TREE_CODE (backedge_val) == SSA_NAME
       && sameval == backedge_val
-      && (SSA_NAME_IS_VIRTUAL_OPERAND (backedge_val)
-	  || !SSA_VISITED (backedge_val)
-	  || SSA_VAL (backedge_val) != backedge_val))
+      && SSA_NAME_IS_VIRTUAL_OPERAND (backedge_val))
     /* Note this just drops to VARYING without inserting the PHI into
        the hashes.  */
     result = PHI_RESULT (phi);
@@ -6226,6 +6221,9 @@  struct unwind_state
   /* Whether to handle this as iteration point or whether to treat
      incoming backedge PHI values as varying.  */
   bool iterate;
+  /* Maximum RPO index this block is reachable from.  */
+  int max_rpo;
+  /* Unwind state.  */
   void *ob_top;
   vn_reference_t ref_top;
   vn_phi_t phi_top;
@@ -6311,8 +6309,8 @@  do_rpo_vn (function *fn, edge entry, bit
     }
 
   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fn) - NUM_FIXED_BLOCKS);
-  int n = rev_post_order_and_mark_dfs_back_seme (fn, entry, exit_bbs,
-						 iterate, rpo);
+  int n = rev_post_order_and_mark_dfs_back_seme
+    (fn, entry, exit_bbs, !loops_state_satisfies_p (LOOPS_NEED_FIXUP), rpo);
   /* rev_post_order_and_mark_dfs_back_seme fills RPO in reverse order.  */
   for (int i = 0; i < n / 2; ++i)
     std::swap (rpo[i], rpo[n-i-1]);
@@ -6382,6 +6380,7 @@  do_rpo_vn (function *fn, edge entry, bit
     {
       basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[i]);
       rpo_state[i].visited = 0;
+      rpo_state[i].max_rpo = i;
       bb->flags &= ~BB_EXECUTABLE;
       bool has_backedges = false;
       edge e;
@@ -6391,15 +6390,18 @@  do_rpo_vn (function *fn, edge entry, bit
 	  if (e->flags & EDGE_DFS_BACK)
 	    has_backedges = true;
 	  if (! iterate && (e->flags & EDGE_DFS_BACK))
-	    {
-	      e->flags |= EDGE_EXECUTABLE;
-	      /* ???  Strictly speaking we only need to unconditionally
-		 process a block when it is in an irreducible region,
-		 thus when it may be reachable via the backedge only.  */
-	      bb->flags |= BB_EXECUTABLE;
-	    }
+	    e->flags |= EDGE_EXECUTABLE;
 	  else
 	    e->flags &= ~EDGE_EXECUTABLE;
+	  if (e == entry)
+	    continue;
+	  if (bb_to_rpo[e->src->index] > i)
+	    rpo_state[i].max_rpo = MAX (rpo_state[i].max_rpo,
+					bb_to_rpo[e->src->index]);
+	  else
+	    rpo_state[i].max_rpo
+	      = MAX (rpo_state[i].max_rpo,
+		     rpo_state[bb_to_rpo[e->src->index]].max_rpo);
 	}
       rpo_state[i].iterate = iterate && has_backedges;
     }
@@ -6442,120 +6444,165 @@  do_rpo_vn (function *fn, edge entry, bit
 	    }
     }
 
-  /* Go and process all blocks, iterating as necessary.  */
-  int idx = 0;
   uint64_t nblk = 0;
-  do
-    {
-      basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[idx]);
+  int idx = 0;
+  if (iterate)
+    /* Go and process all blocks, iterating as necessary.  */
+    do
+      {
+	basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[idx]);
+
+	/* If the block has incoming backedges remember unwind state.  This
+	   is required even for non-executable blocks since in irreducible
+	   regions we might reach them via the backedge and re-start iterating
+	   from there.
+	   Note we can individually mark blocks with incoming backedges to
+	   not iterate where we then handle PHIs conservatively.  We do that
+	   heuristically to reduce compile-time for degenerate cases.  */
+	if (rpo_state[idx].iterate)
+	  {
+	    rpo_state[idx].ob_top = obstack_alloc (&vn_tables_obstack, 0);
+	    rpo_state[idx].ref_top = last_inserted_ref;
+	    rpo_state[idx].phi_top = last_inserted_phi;
+	    rpo_state[idx].nary_top = last_inserted_nary;
+	  }
 
-      /* If the block has incoming backedges remember unwind state.  This
-         is required even for non-executable blocks since in irreducible
-	 regions we might reach them via the backedge and re-start iterating
-	 from there.
-	 Note we can individually mark blocks with incoming backedges to
-	 not iterate where we then handle PHIs conservatively.  We do that
-	 heuristically to reduce compile-time for degenerate cases.  */
-      if (rpo_state[idx].iterate)
-	{
-	  rpo_state[idx].ob_top = obstack_alloc (&vn_tables_obstack, 0);
-	  rpo_state[idx].ref_top = last_inserted_ref;
-	  rpo_state[idx].phi_top = last_inserted_phi;
-	  rpo_state[idx].nary_top = last_inserted_nary;
-	}
+	if (!(bb->flags & BB_EXECUTABLE))
+	  {
+	    if (dump_file && (dump_flags & TDF_DETAILS))
+	      fprintf (dump_file, "Block %d: BB%d found not executable\n",
+		       idx, bb->index);
+	    idx++;
+	    continue;
+	  }
+
+	if (dump_file && (dump_flags & TDF_DETAILS))
+	  fprintf (dump_file, "Processing block %d: BB%d\n", idx, bb->index);
+	nblk++;
+	todo |= process_bb (avail, bb,
+			    rpo_state[idx].visited != 0,
+			    rpo_state[idx].iterate,
+			    iterate, eliminate, do_region, exit_bbs);
+	rpo_state[idx].visited++;
+
+	/* Verify if changed values flow over executable outgoing backedges
+	   and those change destination PHI values (that's the thing we
+	   can easily verify).  Reduce over all such edges to the farthest
+	   away PHI.  */
+	int iterate_to = -1;
+	edge_iterator ei;
+	edge e;
+	FOR_EACH_EDGE (e, ei, bb->succs)
+	  if ((e->flags & (EDGE_DFS_BACK|EDGE_EXECUTABLE))
+	      == (EDGE_DFS_BACK|EDGE_EXECUTABLE)
+	      && rpo_state[bb_to_rpo[e->dest->index]].iterate)
+	    {
+	      int destidx = bb_to_rpo[e->dest->index];
+	      if (!rpo_state[destidx].visited)
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "Unvisited destination %d\n",
+			     e->dest->index);
+		  if (iterate_to == -1 || destidx < iterate_to)
+		    iterate_to = destidx;
+		  continue;
+		}
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "Looking for changed values of backedge"
+			 " %d->%d destination PHIs\n",
+			 e->src->index, e->dest->index);
+	      vn_context_bb = e->dest;
+	      gphi_iterator gsi;
+	      for (gsi = gsi_start_phis (e->dest);
+		   !gsi_end_p (gsi); gsi_next (&gsi))
+		{
+		  bool inserted = false;
+		  /* While we'd ideally just iterate on value changes
+		     we CSE PHIs and do that even across basic-block
+		     boundaries.  So even hashtable state changes can
+		     be important (which is roughly equivalent to
+		     PHI argument value changes).  To not excessively
+		     iterate because of that we track whether a PHI
+		     was CSEd to with GF_PLF_1.  */
+		  bool phival_changed;
+		  if ((phival_changed = visit_phi (gsi.phi (),
+						   &inserted, false))
+		      || (inserted && gimple_plf (gsi.phi (), GF_PLF_1)))
+		    {
+		      if (!phival_changed
+			  && dump_file && (dump_flags & TDF_DETAILS))
+			fprintf (dump_file, "PHI was CSEd and hashtable "
+				 "state (changed)\n");
+		      if (iterate_to == -1 || destidx < iterate_to)
+			iterate_to = destidx;
+		      break;
+		    }
+		}
+	      vn_context_bb = NULL;
+	    }
+	if (iterate_to != -1)
+	  {
+	    do_unwind (&rpo_state[iterate_to], iterate_to, avail, bb_to_rpo);
+	    idx = iterate_to;
+	    if (dump_file && (dump_flags & TDF_DETAILS))
+	      fprintf (dump_file, "Iterating to %d BB%d\n",
+		       iterate_to, rpo[iterate_to]);
+	    continue;
+	  }
+
+	idx++;
+      }
+    while (idx < n);
+
+  else /* !iterate */
+    {
+      /* Process all blocks greedily with a worklist that enforces RPO
+         processing of reachable blocks.  */
+      auto_bitmap worklist;
+      bitmap_set_bit (worklist, 0);
+      while (!bitmap_empty_p (worklist))
+	{
+	  int idx = bitmap_first_set_bit (worklist);
+	  bitmap_clear_bit (worklist, idx);
+	  basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[idx]);
+	  gcc_assert ((bb->flags & BB_EXECUTABLE)
+		      && !rpo_state[idx].visited);
 
-      if (!(bb->flags & BB_EXECUTABLE))
-	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    fprintf (dump_file, "Block %d: BB%d found not executable\n",
-		     idx, bb->index);
-	  idx++;
-	  continue;
-	}
+	    fprintf (dump_file, "Processing block %d: BB%d\n", idx, bb->index);
 
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "Processing block %d: BB%d\n", idx, bb->index);
-      nblk++;
-      todo |= process_bb (avail, bb,
-			  rpo_state[idx].visited != 0,
-			  rpo_state[idx].iterate,
-			  iterate, eliminate, do_region, exit_bbs);
-      rpo_state[idx].visited++;
-
-      if (iterate)
-	{
-	  /* Verify if changed values flow over executable outgoing backedges
-	     and those change destination PHI values (that's the thing we
-	     can easily verify).  Reduce over all such edges to the farthest
-	     away PHI.  */
-	  int iterate_to = -1;
+	  /* When we run into predecessor edges where we cannot trust its
+	     executable state mark them executable so PHI processing will
+	     be conservative.
+	     ???  Do we need to force arguments flowing over that edge
+	     to be varying or will they even always be?  */
 	  edge_iterator ei;
 	  edge e;
-	  FOR_EACH_EDGE (e, ei, bb->succs)
-	    if ((e->flags & (EDGE_DFS_BACK|EDGE_EXECUTABLE))
-		== (EDGE_DFS_BACK|EDGE_EXECUTABLE)
-		&& rpo_state[bb_to_rpo[e->dest->index]].iterate)
+	  FOR_EACH_EDGE (e, ei, bb->preds)
+	    if (!(e->flags & EDGE_EXECUTABLE)
+		&& !rpo_state[bb_to_rpo[e->src->index]].visited
+		&& rpo_state[bb_to_rpo[e->src->index]].max_rpo >= (int)idx)
 	      {
-		int destidx = bb_to_rpo[e->dest->index];
-		if (!rpo_state[destidx].visited)
-		  {
-		    if (dump_file && (dump_flags & TDF_DETAILS))
-		      fprintf (dump_file, "Unvisited destination %d\n",
-			       e->dest->index);
-		    if (iterate_to == -1
-			|| destidx < iterate_to)
-		      iterate_to = destidx;
-		    continue;
-		  }
 		if (dump_file && (dump_flags & TDF_DETAILS))
-		  fprintf (dump_file, "Looking for changed values of backedge "
-			   "%d->%d destination PHIs\n",
+		  fprintf (dump_file, "Cannot trust state of predecessor "
+			   "edge %d -> %d, marking executable\n",
 			   e->src->index, e->dest->index);
-		vn_context_bb = e->dest;
-		gphi_iterator gsi;
-		for (gsi = gsi_start_phis (e->dest);
-		     !gsi_end_p (gsi); gsi_next (&gsi))
-		  {
-		    bool inserted = false;
-		    /* While we'd ideally just iterate on value changes
-		       we CSE PHIs and do that even across basic-block
-		       boundaries.  So even hashtable state changes can
-		       be important (which is roughly equivalent to
-		       PHI argument value changes).  To not excessively
-		       iterate because of that we track whether a PHI
-		       was CSEd to with GF_PLF_1.  */
-		    bool phival_changed;
-		    if ((phival_changed = visit_phi (gsi.phi (),
-						     &inserted, false))
-			|| (inserted && gimple_plf (gsi.phi (), GF_PLF_1)))
-		      {
-			if (!phival_changed
-			    && dump_file && (dump_flags & TDF_DETAILS))
-			  fprintf (dump_file, "PHI was CSEd and hashtable "
-				   "state (changed)\n");
-			if (iterate_to == -1
-			    || destidx < iterate_to)
-			  iterate_to = destidx;
-			break;
-		      }
-		  }
-		vn_context_bb = NULL;
+		e->flags |= EDGE_EXECUTABLE;
 	      }
-	  if (iterate_to != -1)
-	    {
-	      do_unwind (&rpo_state[iterate_to], iterate_to,
-			 avail, bb_to_rpo);
-	      idx = iterate_to;
-	      if (dump_file && (dump_flags & TDF_DETAILS))
-		fprintf (dump_file, "Iterating to %d BB%d\n",
-			 iterate_to, rpo[iterate_to]);
-	      continue;
-	    }
-	}
 
-      idx++;
+	  nblk++;
+	  todo |= process_bb (avail, bb, false, false, false, eliminate,
+			      do_region, exit_bbs);
+	  rpo_state[idx].visited++;
+
+	  FOR_EACH_EDGE (e, ei, bb->succs)
+	    if ((e->flags & EDGE_EXECUTABLE)
+		&& e->dest->index != EXIT_BLOCK
+		&& (!do_region || !bitmap_bit_p (exit_bbs, e->dest->index))
+		&& !rpo_state[bb_to_rpo[e->dest->index]].visited)
+	      bitmap_set_bit (worklist, bb_to_rpo[e->dest->index]);
+	}
     }
-  while (idx < n);
 
   /* If statistics or dump file active.  */
   int nex = 0;