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]);
