diff mbox series

tree-optimization/115388 - wrong DSE in irreductible regions

Message ID 20240610113552.7510B3857022@sourceware.org
State New
Headers show
Series tree-optimization/115388 - wrong DSE in irreductible regions | expand

Commit Message

Richard Biener June 10, 2024, 11:35 a.m. UTC 
The following fixes a latent bug in DSE with regarding to variant
array accesses where the code avoiding bogus DSE in loops fails to
handle irreducible regions.  For those we need to make sure backedges
are marked and discover a header for the irreducible region to check
invariantness.

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

Unfortunately this doesn't seem to fix PR115256, the miscompare
of 502.gcc_r bisected to the same rev.

	PR tree-optimization/115388
	* tree-ssa-dse.cc (dse_classify_store): Handle irreducible
	regions.
	(pass_dse::execute): Make sure to mark backedges.

	* gcc.dg/torture/pr115388.c: New testcase.
---
 gcc/testsuite/gcc.dg/torture/pr115388.c | 34 ++++++++++++++
 gcc/tree-ssa-dse.cc                     | 61 ++++++++++++++++---------
 2 files changed, 74 insertions(+), 21 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/torture/pr115388.c
diff mbox series

Patch

diff --git a/gcc/testsuite/gcc.dg/torture/pr115388.c b/gcc/testsuite/gcc.dg/torture/pr115388.c
new file mode 100644
index 00000000000..c7c902888da
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr115388.c
@@ -0,0 +1,34 @@ 
+/* { dg-do run } */
+
+int printf(const char *, ...);
+int a[10], b, c, d[0], h, i, j, k, l;
+char e = -1, g;
+volatile int f;
+static void n() {
+  while (e >= 0)
+    while (1)
+      ;
+  for (b = 2; b >= 0; b--) {
+    for (k = 0; k < 4; k++) {
+      if (e || i)
+        continue;
+      for (h = 0; h < 2; h++)
+        f;
+    }
+    for (l = 2; l >= 0; l--)
+      g = 0;
+    for (; g < 1; g++)
+      if (c)
+        d[l] = 1;
+    a[9] = 0;
+    a[b] = 1;
+    while (j)
+      printf("\n");
+  }
+}
+int main() {
+  n();
+  if (a[1] != 1)
+    __builtin_abort();
+  return 0;
+}
diff --git a/gcc/tree-ssa-dse.cc b/gcc/tree-ssa-dse.cc
index 9252ca34050..63bf4491cf6 100644
--- a/gcc/tree-ssa-dse.cc
+++ b/gcc/tree-ssa-dse.cc
@@ -1018,8 +1018,11 @@  dse_classify_store (ao_ref *ref, gimple *stmt,
 	  if (defvar == stop_at_vuse)
 	    return DSE_STORE_LIVE;
 
-	  FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
+	  use_operand_p usep;
+	  FOR_EACH_IMM_USE_FAST (usep, ui, defvar)
 	    {
+	      use_stmt = USE_STMT (usep);
+
 	      /* Limit stmt walking.  */
 	      if (++cnt > param_dse_max_alias_queries_per_store)
 		{
@@ -1031,31 +1034,43 @@  dse_classify_store (ao_ref *ref, gimple *stmt,
 		 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 (gphi *phi = dyn_cast <gphi *> (use_stmt))
 		{
 		  /* 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_phi_num_args (phi) == 1)
+		    worklist.safe_push (gimple_phi_result (phi));
+		  else
 		    {
 		      /* 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);
+			 represented by this PHI node.  We handle irreducible
+			 regions by relying on backedge marking and identifying
+			 the head of the (sub-)region.  */
+		      edge e = gimple_phi_arg_edge
+				 (phi, PHI_ARG_INDEX_FROM_USE (usep));
+		      if (e->flags & EDGE_DFS_BACK)
+			{
+			  basic_block rgn_head
+			    = nearest_common_dominator (CDI_DOMINATORS,
+							gimple_bb (phi),
+							e->src);
+			  if (!for_each_index (ref->ref
+					       ? &ref->ref : &ref->base,
+					       check_name, rgn_head))
+			    return DSE_STORE_LIVE;
+			}
+		      /* If we already visited this PHI ignore it for further
+			 processing.  But note we have to check each incoming
+			 edge above.  */
+		      if (!bitmap_bit_p (visited,
+					 SSA_NAME_VERSION (PHI_RESULT (phi))))
+			{
+			  defs.safe_push (phi);
+			  if (!first_phi_def)
+			    first_phi_def = phi;;
+			  last_phi_def = phi;
+			}
 		    }
 		}
 	      /* If the statement is a use the store is not dead.  */
@@ -1681,7 +1696,11 @@  pass_dse::execute (function *fun)
 
   /* Dead store elimination is fundamentally a reverse program order walk.  */
   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS);
-  int n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
+  auto_bitmap exit_bbs;
+  bitmap_set_bit (exit_bbs, EXIT_BLOCK);
+  edge entry = single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (fun));
+  int n = rev_post_order_and_mark_dfs_back_seme (fun, entry,
+						 exit_bbs, false, rpo, NULL);
   for (int i = n; i != 0; --i)
     {
       basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i-1]);