[PATCH] Improve PHI handling in DSE

[PATCH] Improve PHI handling in DSE

[Richard Biener]

This improves handling of PHI defs when walking uses in
dse_classify_store to track two PHI defs.  This happens
when there are CFG merges and one PHI feeds into another.
If we decide to want more then using a sbitmap for this might be
the way to go.

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

2021-05-03  Richard Biener  <rguenther@suse.de>

	* tree-ssa-dse.c (dse_classify_store): Track two PHI defs.

	* gcc.dg/tree-ssa/ssa-dse-42.c: New testcase.
	* gcc.dg/pr81192.c: Disable DSE.
---
 gcc/testsuite/gcc.dg/pr81192.c             |  4 +++-
 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-42.c | 20 +++++++++++++++++++
 gcc/tree-ssa-dse.c                         | 23 +++++++++++++---------
 3 files changed, 37 insertions(+), 10 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-42.c

diff --git a/gcc/testsuite/gcc.dg/pr81192.c b/gcc/testsuite/gcc.dg/pr81192.c
index 71bbc13a0e9..6cab6056558 100644
--- a/gcc/testsuite/gcc.dg/pr81192.c
+++ b/gcc/testsuite/gcc.dg/pr81192.c
@@ -1,4 +1,4 @@
-/* { dg-options "-Os -fdump-tree-pre-details -fdisable-tree-evrp" } */
+/* { dg-options "-Os -fdump-tree-pre-details -fdisable-tree-evrp -fno-tree-dse" } */
 
 /* Disable tree-evrp because the new version of evrp sees
 <bb 3> :
@@ -16,6 +16,8 @@ produces
   # iftmp.2_12 = PHI <2147483647(3), iftmp.2_11(4)> 
 which causes the situation being tested to dissapear before we get to PRE.  */
 
+/* Likewise disable DSE which also elides the tail merging "opportunity".  */
+
 #if __SIZEOF_INT__ == 2
 #define unsigned __UINT32_TYPE__
 #define int __INT32_TYPE__
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-42.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-42.c
new file mode 100644
index 00000000000..34108c83828
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-42.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-dse1" } */
+
+int a[2];
+void foo(int i, int k, int j)
+{
+  a[0] = i;
+  if (k)
+    a[0] = a[i] + k;
+  else
+    {
+      if (j)
+        a[1] = 1;
+      a[0] = a[i] + 3;
+    }
+  a[0] = 0;
+}
+
+/* The last stores to a[0] and a[1] remain.  */
+/* { dg-final { scan-tree-dump-times " = " 2 "dse1" } } */
diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
index e0a944c704a..dfa6d314727 100644
--- a/gcc/tree-ssa-dse.c
+++ b/gcc/tree-ssa-dse.c
@@ -799,7 +799,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	return DSE_STORE_LIVE;
 
       auto_vec<gimple *, 10> defs;
-      gimple *phi_def = NULL;
+      gimple *first_phi_def = NULL;
+      gimple *last_phi_def = NULL;
       FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
 	{
 	  /* Limit stmt walking.  */
@@ -825,7 +826,9 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 				 SSA_NAME_VERSION (PHI_RESULT (use_stmt))))
 		{
 		  defs.safe_push (use_stmt);
-		  phi_def = use_stmt;
+		  if (!first_phi_def)
+		    first_phi_def = use_stmt;
+		  last_phi_def = use_stmt;
 		}
 	    }
 	  /* If the statement is a use the store is not dead.  */
@@ -889,6 +892,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	  gimple *def = defs[i];
 	  gimple *use_stmt;
 	  use_operand_p use_p;
+	  tree vdef = (gimple_code (def) == GIMPLE_PHI
+		       ? gimple_phi_result (def) : gimple_vdef (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
@@ -901,8 +906,7 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	    }
 	  /* If the path ends here we do not need to process it further.
 	     This for example happens with calls to noreturn functions.  */
-	  else if (gimple_code (def) != GIMPLE_PHI
-		   && has_zero_uses (gimple_vdef (def)))
+	  else if (has_zero_uses (vdef))
 	    {
 	      /* But if the store is to global memory it is definitely
 		 not dead.  */
@@ -912,12 +916,13 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	    }
 	  /* In addition to kills we can remove defs whose only use
 	     is another def in defs.  That can only ever be PHIs of which
-	     we track a single for simplicity reasons (we fail for multiple
-	     PHIs anyways).  We can also ignore defs that feed only into
+	     we track two for simplicity reasons, the first and last in
+	     {first,last}_phi_def (we fail for multiple PHIs anyways).
+	     We can also ignore defs that feed only into
 	     already visited PHIs.  */
-	  else if (gimple_code (def) != GIMPLE_PHI
-		   && single_imm_use (gimple_vdef (def), &use_p, &use_stmt)
-		   && (use_stmt == phi_def
+	  else if (single_imm_use (vdef, &use_p, &use_stmt)
+		   && (use_stmt == first_phi_def
+		       || use_stmt == last_phi_def
 		       || (gimple_code (use_stmt) == GIMPLE_PHI
 			   && bitmap_bit_p (visited,
 					    SSA_NAME_VERSION
-- 
2.26.2