[gcc r13-5092] tree-optimization/106293 - missed DSE with virtual LC PHI

[gcc r13-5092] tree-optimization/106293 - missed DSE with virtual LC PHI

[Richard Biener]

https://gcc.gnu.org/g:4e0b504f26f78ff02e80ad98ebbf8ded3aa6ffa1

commit r13-5092-g4e0b504f26f78ff02e80ad98ebbf8ded3aa6ffa1
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Jan 10 13:48:51 2023 +0100

    tree-optimization/106293 - missed DSE with virtual LC PHI
    
    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.
    
            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.

Diff:
---
 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-46.c |  23 ++++
 gcc/tree-ssa-dse.cc                        | 181 ++++++++++++++++-------------
 2 files changed, 121 insertions(+), 83 deletions(-)

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)
 	{