tree-optimization/100221 - improve DSE a bit

When facing multiple PHI defs and one feeding the other we can
postpone processing uses of one and thus can proceed.

2022-05-20  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/100221
	* tree-ssa-dse.cc (contains_phi_arg): New function.
	(dse_classify_store): Postpone PHI defs that feed another PHI in defs.

	* gcc.dg/tree-ssa/ssa-dse-44.c: New testcase.
	* gcc.dg/tree-ssa/ssa-dse-45.c: Likewise.

3 files changed, 84 insertions, 5 deletions

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c
new file mode 100644
index 0000000..aaec41d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-44.c
@@ -0,0 +1,19 @@
+/* { dg-do link } */
+/* { dg-options "-O -fdump-tree-dse1-details" } */
+
+extern void foo(void);
+int a, b;
+static int c;
+int main()
+{
+  if (c)
+    foo ();
+  int *g = &c;
+  int **h = &g;
+  int ***h1 = &h;
+  if (a)
+    while (b)
+      b = 0;
+}
+
+/* { dg-final { scan-tree-dump "Deleted dead store: g = &c;" "dse1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c
new file mode 100644
index 0000000..fd92d7b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-45.c
@@ -0,0 +1,24 @@
+/* { dg-do link } */
+/* { dg-options "-O" } */
+
+extern void foo(void);
+int a, b;
+static int c;
+static void f() {
+  while (a)
+    for (; b; b--)
+      ;
+}
+void i() {
+  if (c)
+    foo();
+  int *g = &c;
+  {
+    int **h[1] = {&g};
+    f();
+  }
+}
+int main() {
+  i();
+  return 0;
+}
diff --git a/gcc/tree-ssa-dse.cc b/gcc/tree-ssa-dse.cc
index 881a2d0..ea50de7 100644
--- a/gcc/tree-ssa-dse.cc
+++ b/gcc/tree-ssa-dse.cc
@@ -898,6 +898,17 @@ dse_optimize_redundant_stores (gimple *stmt)
     }
 }
 
+/* Return whether PHI contains ARG as an argument.  */
+
+static bool
+contains_phi_arg (gphi *phi, tree arg)
+{
+  for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
+    if (gimple_phi_arg_def (phi, i) == arg)
+      return true;
+  return false;
+}
+
 /* A helper of dse_optimize_stmt.
    Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it
    according to downstream uses and defs.  Sets *BY_CLOBBER_P to true
@@ -949,8 +960,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	return DSE_STORE_LIVE;
 
       auto_vec<gimple *, 10> defs;
-      gimple *first_phi_def = NULL;
-      gimple *last_phi_def = NULL;
+      gphi *first_phi_def = NULL;
+      gphi *last_phi_def = NULL;
       FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
 	{
 	  /* Limit stmt walking.  */
@@ -973,8 +984,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 		{
 		  defs.safe_push (use_stmt);
 		  if (!first_phi_def)
-		    first_phi_def = use_stmt;
-		  last_phi_def = use_stmt;
+		    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.  */
@@ -1046,6 +1057,7 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	  use_operand_p use_p;
 	  tree vdef = (gimple_code (def) == GIMPLE_PHI
 		       ? gimple_phi_result (def) : gimple_vdef (def));
+	  gphi *phi_def;
 	  /* If the path to check starts with a kill we do not need to
 	     process it further.
 	     ???  With byte tracking we need only kill the bytes currently
@@ -1079,7 +1091,31 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 			   && bitmap_bit_p (visited,
 					    SSA_NAME_VERSION
 					      (PHI_RESULT (use_stmt))))))
-	    defs.unordered_remove (i);
+	    {
+	      defs.unordered_remove (i);
+	      if (def == first_phi_def)
+		first_phi_def = NULL;
+	      else if (def == last_phi_def)
+		last_phi_def = NULL;
+	    }
+	  /* If def is a PHI and one of its arguments is another PHI node still
+	     in consideration we can defer processing it.  */
+	  else if ((phi_def = dyn_cast <gphi *> (def))
+		   && ((last_phi_def
+			&& phi_def != last_phi_def
+			&& contains_phi_arg (phi_def,
+					     gimple_phi_result (last_phi_def)))
+		       || (first_phi_def
+			   && phi_def != first_phi_def
+			   && contains_phi_arg
+				(phi_def, gimple_phi_result (first_phi_def)))))
+	    {
+	      defs.unordered_remove (i);
+	      if (phi_def == first_phi_def)
+		first_phi_def = NULL;
+	      else if (phi_def == last_phi_def)
+		last_phi_def = NULL;
+	    }
 	  else
 	    ++i;
 	}