diff mbox series

[v2] tree-optimization/79958 - make DSE track multiple paths

Message ID 20240516080231.BB04C3849AC6@sourceware.org
State New
Headers show
Series [v2] tree-optimization/79958 - make DSE track multiple paths | expand

Commit Message

Richard Biener May 16, 2024, 8:01 a.m. UTC 
DSE currently gives up when the path we analyze forks.  This leads
to multiple missed dead store elimination PRs.  The following fixes
this by recursing for each path and maintaining the visited bitmap
to avoid visiting CFG re-merges multiple times.  The overall cost
is still limited by the same bound, it's just more likely we'll hit
the limit now.  The patch doesn't try to deal with byte tracking
once a path forks but drops info on the floor and only handling
fully dead stores in that case.

This version adds some testsuite adjustments to avoid regressions.
Will push after retesting completed.

Richard.

	PR tree-optimization/79958
	PR tree-optimization/109087
	PR tree-optimization/100314
	PR tree-optimization/114774
	* tree-ssa-dse.cc (dse_classify_store): New forwarder.
	(dse_classify_store): Add arguments cnt and visited, recurse
	to track multiple paths when we end up with multiple defs.

	* gcc.dg/tree-ssa/ssa-dse-48.c: New testcase.
	* gcc.dg/tree-ssa/ssa-dse-49.c: Likewise.
	* gcc.dg/tree-ssa/ssa-dse-50.c: Likewise.
	* gcc.dg/tree-ssa/ssa-dse-51.c: Likewise.
	* gcc.dg/graphite/pr80906.c: Avoid DSE of last data reference
	in loop.
	* g++.dg/ipa/devirt-24.C: Adjust for extra DSE.
	* g++.dg/warn/Wuninitialized-pr107919-1.C: Use more important
	-O2 optimization level, -O1 regresses.
---
 gcc/testsuite/g++.dg/ipa/devirt-24.C          |  4 ++-
 .../g++.dg/warn/Wuninitialized-pr107919-1.C   |  2 +-
 gcc/testsuite/gcc.dg/graphite/pr80906.c       |  2 +-
 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-48.c    | 17 ++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-49.c    | 18 +++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-50.c    | 25 +++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-51.c    | 24 ++++++++++++++
 gcc/tree-ssa-dse.cc                           | 31 ++++++++++++++++---
 8 files changed, 116 insertions(+), 7 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-48.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-49.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-50.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-51.c
diff mbox series

Patch

diff --git a/gcc/testsuite/g++.dg/ipa/devirt-24.C b/gcc/testsuite/g++.dg/ipa/devirt-24.C
index 7b5b806dd05..333c03cd8dd 100644
--- a/gcc/testsuite/g++.dg/ipa/devirt-24.C
+++ b/gcc/testsuite/g++.dg/ipa/devirt-24.C
@@ -37,4 +37,6 @@  C *b = new (C);
   }
 }
 /* { dg-final { scan-ipa-dump-times "Discovered a virtual call to a known target" 1 "inline" { xfail *-*-* } } } */
-/* { dg-final { scan-ipa-dump-times "Aggregate passed by reference" 2 "cp"  } } */
+/* We used to have IPA CP see two aggregates passed to sort() but as the
+   first argument is unused DSE now elides the vptr initialization.  */
+/* { dg-final { scan-ipa-dump-times "Aggregate passed by reference" 1 "cp"  } } */
diff --git a/gcc/testsuite/g++.dg/warn/Wuninitialized-pr107919-1.C b/gcc/testsuite/g++.dg/warn/Wuninitialized-pr107919-1.C
index dd631dc8bfe..067a44a462e 100644
--- a/gcc/testsuite/g++.dg/warn/Wuninitialized-pr107919-1.C
+++ b/gcc/testsuite/g++.dg/warn/Wuninitialized-pr107919-1.C
@@ -1,6 +1,6 @@ 
 // { dg-do compile }
 // { dg-require-effective-target c++17 }
-// { dg-options "-O -Wuninitialized" }
+// { dg-options "-O2 -Wuninitialized" }
 
 #include <memory>
 #include <variant>
diff --git a/gcc/testsuite/gcc.dg/graphite/pr80906.c b/gcc/testsuite/gcc.dg/graphite/pr80906.c
index 59c7f59cadf..ec3840834fc 100644
--- a/gcc/testsuite/gcc.dg/graphite/pr80906.c
+++ b/gcc/testsuite/gcc.dg/graphite/pr80906.c
@@ -18,7 +18,7 @@  ec (int lh[][2])
 	  --bm;
 	if (bm != 0)
 	  --c5;
-	lh[0][0] = 0;
+	lh[hp][0] = 0;
 	m3 *= jv;
       }
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-48.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-48.c
new file mode 100644
index 00000000000..edfc62c7e4a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-48.c
@@ -0,0 +1,17 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-dse1-details" } */
+
+int a;
+int foo (void);
+int bar (void);
+
+void
+baz (void)
+{
+  int *b[6];
+  b[0] = &a;
+  if (foo ())
+    a |= bar ();
+}
+
+/* { dg-final { scan-tree-dump "Deleted dead store: b\\\[0\\\] = &a;" "dse1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-49.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-49.c
new file mode 100644
index 00000000000..1eec284a415
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-49.c
@@ -0,0 +1,18 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fno-tree-dce -fdump-tree-dse1-details" } */
+
+struct X { int i; };
+void bar ();
+void foo (int b)
+{
+  struct X x;
+  x.i = 1;
+  if (b)
+    {
+      bar ();
+      __builtin_abort ();
+    }
+  bar ();
+}
+
+/* { dg-final { scan-tree-dump "Deleted dead store: x.i = 1;" "dse1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-50.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-50.c
new file mode 100644
index 00000000000..7c42ae6a67a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-50.c
@@ -0,0 +1,25 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-dse1-details" } */
+
+extern void foo(void);
+static int a, *c, g, **j;
+int b;
+static void e() {
+  int k, *l[5] = {&k, &k, &k, &k, &k};
+  while (g) {
+    j = &l[0];
+    b++;
+  }
+}
+static void d(int m) {
+  int **h[30] = {&c}, ***i[1] = {&h[3]};
+  if (m)
+    foo();
+  e();
+}
+int main() {
+  d(a);
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Deleted dead store" 8 "dse1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-51.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-51.c
new file mode 100644
index 00000000000..ac9d1bb1fc8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-51.c
@@ -0,0 +1,24 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fstrict-aliasing -fdump-tree-dse1-details" } */
+
+int a;
+short *p;
+void
+test (int b)
+{
+  a=1;
+  if (b)
+    {
+      (*p)++;
+      a=2;
+      __builtin_printf ("1\n");
+    }
+  else
+    {
+      (*p)++;
+      a=3;
+      __builtin_printf ("2\n");
+    }
+}
+
+/* { dg-final { scan-tree-dump "Deleted dead store: a = 1;" "dse1" } } */
diff --git a/gcc/tree-ssa-dse.cc b/gcc/tree-ssa-dse.cc
index fce4fc76a56..9252ca34050 100644
--- a/gcc/tree-ssa-dse.cc
+++ b/gcc/tree-ssa-dse.cc
@@ -971,14 +971,13 @@  static hash_map<gimple *, data_reference_p> *dse_stmt_to_dr_map;
    if only clobber statements influenced the classification result.
    Returns the classification.  */
 
-dse_store_status
+static dse_store_status
 dse_classify_store (ao_ref *ref, gimple *stmt,
 		    bool byte_tracking_enabled, sbitmap live_bytes,
-		    bool *by_clobber_p, tree stop_at_vuse)
+		    bool *by_clobber_p, tree stop_at_vuse, int &cnt,
+		    bitmap visited)
 {
   gimple *temp;
-  int cnt = 0;
-  auto_bitmap visited;
   std::unique_ptr<data_reference, void(*)(data_reference_p)>
     dra (nullptr, free_data_ref);
 
@@ -1238,6 +1237,19 @@  dse_classify_store (ao_ref *ref, gimple *stmt,
       /* If all defs kill the ref we are done.  */
       if (defs.is_empty ())
 	return DSE_STORE_DEAD;
+      /* If more than one def survives we have to analyze multiple
+	 paths.  We can handle this by recursing, sharing 'visited'
+	 to avoid redundant work and limiting it by shared 'cnt'.
+	 For now do not bother with byte-tracking in this case.  */
+      while (defs.length () > 1)
+	{
+	  if (dse_classify_store (ref, defs.last (), false, NULL,
+				  by_clobber_p, stop_at_vuse, cnt,
+				  visited) != DSE_STORE_DEAD)
+	    break;
+	  byte_tracking_enabled = false;
+	  defs.pop ();
+	}
       /* If more than one def survives fail.  */
       if (defs.length () > 1)
 	{
@@ -1265,6 +1277,17 @@  dse_classify_store (ao_ref *ref, gimple *stmt,
   while (1);
 }
 
+dse_store_status
+dse_classify_store (ao_ref *ref, gimple *stmt,
+		    bool byte_tracking_enabled, sbitmap live_bytes,
+		    bool *by_clobber_p, tree stop_at_vuse)
+{
+  int cnt = 0;
+  auto_bitmap visited;
+  return dse_classify_store (ref, stmt, byte_tracking_enabled, live_bytes,
+			     by_clobber_p, stop_at_vuse, cnt, visited);
+}
+
 
 /* Delete a dead call at GSI, which is mem* call of some kind.  */
 static void