[PATCH] tree-optimization/106293 - missed DSE with virtual LC PHI

[Richard Biener <rguenther@suse.de>]

Degenerate virtual PHIs can break DSEs fragile heuristic as to what
defs it can handle for further processing.  The following enhances
it to look through degenerate PHIs by means of a worklist, processing
the degenerate PHI defs uses to the defs array.  The rewrite of
virtuals into loop-closed SSA caused this to issue appear more often.
The patch itself is mostly re-indenting the new loop body.

Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.

	PR tree-optimization/106293
	* tree-ssa-dse.cc (dse_classify_store): Use a worklist to
	process degenerate PHI defs.

	* gcc.dg/tree-ssa/ssa-dse-46.c: New testcase.
---
 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-46.c |  23 +++
 gcc/tree-ssa-dse.cc                        | 181 +++++++++++----------
 2 files changed, 121 insertions(+), 83 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-46.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-46.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-46.c
new file mode 100644
index 00000000000..68b36433ffc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-46.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dse1" } */
+
+int a;
+static long b = 4073709551612, d;
+short c;
+void foo();
+char e(int **f) {
+  **f = 0;
+  if (a) {
+    unsigned long *g = &b;
+    unsigned long **h = &g;
+    for (; d;) {
+      foo();
+      for (; c;) {
+        unsigned long ***i = &h;
+      }
+    }
+  }
+  return 1;
+}
+
+/* { dg-final { scan-tree-dump-not "&b" "dse1" } } */
diff --git a/gcc/tree-ssa-dse.cc b/gcc/tree-ssa-dse.cc
index 89e2fa2c3f5..46ab57d5754 100644
--- a/gcc/tree-ssa-dse.cc
+++ b/gcc/tree-ssa-dse.cc
@@ -984,108 +984,123 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
       else
 	defvar = gimple_vdef (temp);
 
-      /* If we're instructed to stop walking at region boundary, do so.  */
-      if (defvar == stop_at_vuse)
-	return DSE_STORE_LIVE;
-
       auto_vec<gimple *, 10> defs;
       gphi *first_phi_def = NULL;
       gphi *last_phi_def = NULL;
-      FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
+
+      auto_vec<tree, 10> worklist;
+      worklist.quick_push (defvar);
+
+      do
 	{
-	  /* Limit stmt walking.  */
-	  if (++cnt > param_dse_max_alias_queries_per_store)
-	    {
-	      fail = true;
-	      break;
-	    }
+	  defvar = worklist.pop ();
+	  /* If we're instructed to stop walking at region boundary, do so.  */
+	  if (defvar == stop_at_vuse)
+	    return DSE_STORE_LIVE;
 
-	  /* In simple cases we can look through PHI nodes, but we
-	     have to be careful with loops and with memory references
-	     containing operands that are also operands of PHI nodes.
-	     See gcc.c-torture/execute/20051110-*.c.  */
-	  if (gimple_code (use_stmt) == GIMPLE_PHI)
+	  FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
 	    {
-	      /* If we already visited this PHI ignore it for further
-		 processing.  */
-	      if (!bitmap_bit_p (visited,
-				 SSA_NAME_VERSION (PHI_RESULT (use_stmt))))
+	      /* Limit stmt walking.  */
+	      if (++cnt > param_dse_max_alias_queries_per_store)
 		{
-		  /* If we visit this PHI by following a backedge then we have
-		     to make sure ref->ref only refers to SSA names that are
-		     invariant with respect to the loop represented by this
-		     PHI node.  */
-		  if (dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt),
-				      gimple_bb (use_stmt))
-		      && !for_each_index (ref->ref ? &ref->ref : &ref->base,
-					  check_name, gimple_bb (use_stmt)))
-		    return DSE_STORE_LIVE;
-		  defs.safe_push (use_stmt);
-		  if (!first_phi_def)
-		    first_phi_def = as_a <gphi *> (use_stmt);
-		  last_phi_def = as_a <gphi *> (use_stmt);
+		  fail = true;
+		  break;
 		}
-	    }
-	  /* If the statement is a use the store is not dead.  */
-	  else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
-	    {
-	      if (dse_stmt_to_dr_map
-		  && ref->ref
-		  && is_gimple_assign (use_stmt))
+
+	      /* In simple cases we can look through PHI nodes, but we
+		 have to be careful with loops and with memory references
+		 containing operands that are also operands of PHI nodes.
+		 See gcc.c-torture/execute/20051110-*.c.  */
+	      if (gimple_code (use_stmt) == GIMPLE_PHI)
 		{
-		  if (!dra)
-		    dra.reset (create_data_ref (NULL, NULL, ref->ref, stmt,
-						false, false));
-		  bool existed_p;
-		  data_reference_p &drb
-		    = dse_stmt_to_dr_map->get_or_insert (use_stmt, &existed_p);
-		  if (!existed_p)
-		    drb = create_data_ref (NULL, NULL,
-					   gimple_assign_rhs1 (use_stmt),
-					   use_stmt, false, false);
-		  if (!dr_may_alias_p (dra.get (), drb, NULL))
+		  /* Look through single-argument PHIs.  */
+		  if (gimple_phi_num_args (use_stmt) == 1)
+		    worklist.safe_push (gimple_phi_result (use_stmt));
+
+		  /* If we already visited this PHI ignore it for further
+		     processing.  */
+		  else if (!bitmap_bit_p (visited,
+					  SSA_NAME_VERSION
+					    (PHI_RESULT (use_stmt))))
 		    {
-		      if (gimple_vdef (use_stmt))
-			defs.safe_push (use_stmt);
-		      continue;
+		      /* If we visit this PHI by following a backedge then we
+			 have to make sure ref->ref only refers to SSA names
+			 that are invariant with respect to the loop
+			 represented by this PHI node.  */
+		      if (dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt),
+					  gimple_bb (use_stmt))
+			  && !for_each_index (ref->ref ? &ref->ref : &ref->base,
+					      check_name, gimple_bb (use_stmt)))
+			return DSE_STORE_LIVE;
+		      defs.safe_push (use_stmt);
+		      if (!first_phi_def)
+			first_phi_def = as_a <gphi *> (use_stmt);
+		      last_phi_def = as_a <gphi *> (use_stmt);
 		    }
 		}
+	      /* If the statement is a use the store is not dead.  */
+	      else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
+		{
+		  if (dse_stmt_to_dr_map
+		      && ref->ref
+		      && is_gimple_assign (use_stmt))
+		    {
+		      if (!dra)
+			dra.reset (create_data_ref (NULL, NULL, ref->ref, stmt,
+						    false, false));
+		      bool existed_p;
+		      data_reference_p &drb
+			= dse_stmt_to_dr_map->get_or_insert (use_stmt,
+							     &existed_p);
+		      if (!existed_p)
+			drb = create_data_ref (NULL, NULL,
+					       gimple_assign_rhs1 (use_stmt),
+					       use_stmt, false, false);
+		      if (!dr_may_alias_p (dra.get (), drb, NULL))
+			{
+			  if (gimple_vdef (use_stmt))
+			    defs.safe_push (use_stmt);
+			  continue;
+			}
+		    }
 
-	      /* Handle common cases where we can easily build an ao_ref
-		 structure for USE_STMT and in doing so we find that the
-		 references hit non-live bytes and thus can be ignored.
+		  /* Handle common cases where we can easily build an ao_ref
+		     structure for USE_STMT and in doing so we find that the
+		     references hit non-live bytes and thus can be ignored.
 
-		 TODO: We can also use modref summary to handle calls.  */
-	      if (byte_tracking_enabled
-		  && is_gimple_assign (use_stmt))
-		{
-		  ao_ref use_ref;
-		  ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt));
-		  if (valid_ao_ref_for_dse (&use_ref)
-		      && operand_equal_p (use_ref.base, ref->base,
-					  OEP_ADDRESS_OF)
-		      && !live_bytes_read (&use_ref, ref, live_bytes))
+		     TODO: We can also use modref summary to handle calls.  */
+		  if (byte_tracking_enabled
+		      && is_gimple_assign (use_stmt))
 		    {
-		      /* If this is a store, remember it as we possibly
-			 need to walk the defs uses.  */
-		      if (gimple_vdef (use_stmt))
-			defs.safe_push (use_stmt);
-		      continue;
+		      ao_ref use_ref;
+		      ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt));
+		      if (valid_ao_ref_for_dse (&use_ref)
+			  && operand_equal_p (use_ref.base, ref->base,
+					      OEP_ADDRESS_OF)
+			  && !live_bytes_read (&use_ref, ref, live_bytes))
+			{
+			  /* If this is a store, remember it as we possibly
+			     need to walk the defs uses.  */
+			  if (gimple_vdef (use_stmt))
+			    defs.safe_push (use_stmt);
+			  continue;
+			}
 		    }
-		}
 
-	      fail = true;
-	      break;
+		  fail = true;
+		  break;
+		}
+	      /* We have visited ourselves already so ignore STMT for the
+		 purpose of chaining.  */
+	      else if (use_stmt == stmt)
+		;
+	      /* If this is a store, remember it as we possibly need to walk the
+		 defs uses.  */
+	      else if (gimple_vdef (use_stmt))
+		defs.safe_push (use_stmt);
 	    }
-	  /* We have visited ourselves already so ignore STMT for the
-	     purpose of chaining.  */
-	  else if (use_stmt == stmt)
-	    ;
-	  /* If this is a store, remember it as we possibly need to walk the
-	     defs uses.  */
-	  else if (gimple_vdef (use_stmt))
-	    defs.safe_push (use_stmt);
 	}
+      while (!fail && !worklist.is_empty ());
 
       if (fail)
 	{
-- 
2.35.3