tree-optimization/115388 - wrong DSE in irreductible regions

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.

	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.

2 files changed, 74 insertions, 21 deletions

diff --git a/gcc/testsuite/gcc.dg/torture/pr115388.c b/gcc/testsuite/gcc.dg/torture/pr115388.c
new file mode 100644
index 0000000..c7c9028
--- /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 9252ca3..63bf449 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]);