[PATCH] Fix PR81354 (rewrite gimple_split_edge)

[Bill Schmidt <wschmidt at linux dot vnet dot ibm dot com>]

Hi,

PR81354 identifies a latent bug that can happen in SLSR since the
conditional candidate support was first added.  SLSR relies on the
address of a GIMPLE PHI remaining constant during the course of the
optimization pass, but it needs to split edges.  The use of
make_single_succ_edge and reinstall_phi_args in gimple_split_edge
causes GIMPLE PHI statements to be temporarily expanded to add a
predecessor, and then rebuilt to have the original number of
predecessors.  The expansion usually, if not always, causes the PHI
statement to change address.  Thus gimple_split_edge needs to be
rewritten to perform in-situ replacement of PHI arguments.

The required pieces of make_single_succ_edge have been extracted into
two places:  make_replacement_pred_edge, and some fixup code at the
end of gimple_split_edge.  The division is necessary because the
destination of the original edge must remember its original
predecessors for the switch processing in
gimple_redirect_edge_and_branch_1 to work properly.

The function gimple_redirect_edge_and_branch was factored into two
pieces so that most of it can be used by gimple_split_edge without
calling ssa_redirect_edge, which also interferes with PHIs.  The
useful bits of ssa_redirect_edge are factored out into the next three
lines of gimple_split_edge.

Similarly, redirect_eh_edge had already been similarly factored into
redirect_eh_edge_1 and ssa_redirect_edge.  I took advantage of that
and exposed redirect_eh_edge_1 for use in gimple_redirect_edge_and_branch_1.

I've added the test from PR81354 as a torture test, but as we've seen,
small changes elsewhere in the optimizer can easily hide the problem.

Bootstrapped and tested on powerpc64le-linux-gnu with no regressions.
Is this ok for trunk?  Eventually this needs to be backported to GCC 5,
6, and 7 if that's acceptable, since PR81354 was observed on
gcc-5-branch.  I haven't yet prepared the backports.

Thanks,
Bill


[gcc]

2017-07-30  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

	PR tree-optimization/81354
	* tree-cfg.c (gimple_redirect_edge_and_branch_1): New decl.
	(reinstall_phi_args): Delete function.
	(make_replacement_pred_edge): New function.
	(gimple_split_edge): Rewrite.
	(gimple_redirect_edge_and_branch_1): New function, factored
	from...
	(gimple_redirect_edge_and_branch): ...here.
	(split_critical_edges): Don't re-split already split edges.
	* tree-eh.c (redirect_eh_edge_1): Make visible.
	* tree-eh.h (redirect_eh_edge_1): Likewise.

[gcc/testsuite]

2017-07-30  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

	PR tree-optimization/81354
	* g++.dg/torture/pr81354.C: New file.


Index: gcc/testsuite/g++.dg/torture/pr81354.C
===================================================================
--- gcc/testsuite/g++.dg/torture/pr81354.C	(nonexistent)
+++ gcc/testsuite/g++.dg/torture/pr81354.C	(working copy)
@@ -0,0 +1,24 @@
+// PR81354 reported this test as crashing in a limited range of revisions.
+// { dg-do compile }
+
+struct T { double a; double b; };
+
+void foo(T Ad[], int As[2])
+{
+  int j;
+  int i;
+  int Bs[2] = {0,0};
+  T Bd[16];
+
+  for (j = 0; j < 4; j++) {
+    for (i = 0; i + 1 <= j + 1; i++) {
+      Ad[i + As[0] * j] = Bd[i + Bs[0] * j];
+    }
+
+    i = j + 1;  // <- comment out this line and it does not crash
+    for (; i + 1 < 5; i++) {
+      Ad[i + As[0] * j].a = 0.0;
+      Ad[i + As[0] * j].b = 0.0;
+    }
+  }
+}
Index: gcc/tree-cfg.c
===================================================================
--- gcc/tree-cfg.c	(revision 250721)
+++ gcc/tree-cfg.c	(working copy)
@@ -154,6 +154,7 @@ static void make_gimple_switch_edges (gswitch *, b
 static bool make_goto_expr_edges (basic_block);
 static void make_gimple_asm_edges (basic_block);
 static edge gimple_redirect_edge_and_branch (edge, basic_block);
+static edge gimple_redirect_edge_and_branch_1 (edge, basic_block);
 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block);
 
 /* Various helpers.  */
@@ -2776,35 +2777,6 @@ last_and_only_stmt (basic_block bb)
     return NULL;
 }
 
-/* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
-
-static void
-reinstall_phi_args (edge new_edge, edge old_edge)
-{
-  edge_var_map *vm;
-  int i;
-  gphi_iterator phis;
-
-  vec<edge_var_map> *v = redirect_edge_var_map_vector (old_edge);
-  if (!v)
-    return;
-
-  for (i = 0, phis = gsi_start_phis (new_edge->dest);
-       v->iterate (i, &vm) && !gsi_end_p (phis);
-       i++, gsi_next (&phis))
-    {
-      gphi *phi = phis.phi ();
-      tree result = redirect_edge_var_map_result (vm);
-      tree arg = redirect_edge_var_map_def (vm);
-
-      gcc_assert (result == gimple_phi_result (phi));
-
-      add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
-    }
-
-  redirect_edge_var_map_clear (old_edge);
-}
-
 /* Returns the basic block after which the new basic block created
    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
    near its "logical" location.  This is of most help to humans looking
@@ -2825,6 +2797,24 @@ split_edge_bb_loc (edge edge_in)
   return dest_prev;
 }
 
+/* Create a single-predecessor edge from SRC to DST, replacing the
+   predecessor edge E_IN of DST, with flags FLAGS.  This is done in
+   situ so that phis in DST will not get re-allocated.  */
+
+static edge
+make_replacement_pred_edge (basic_block src, basic_block dest,
+			    edge e_in, int flags)
+{
+  edge e = ggc_cleared_alloc<edge_def> ();
+  n_edges_for_fn (cfun)++;
+  e->src = src;
+  e->dest = dest;
+  e->flags = flags;
+  vec_safe_push (src->succs, e);
+  e->dest_idx = e_in->dest_idx;
+  return e;
+}
+
 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
    Abort on abnormal edges.  */
 
@@ -2832,7 +2822,7 @@ static basic_block
 gimple_split_edge (edge edge_in)
 {
   basic_block new_bb, after_bb, dest;
-  edge new_edge, e;
+  edge e, f;
 
   /* Abnormal edges cannot be split.  */
   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
@@ -2841,15 +2831,33 @@ gimple_split_edge (edge edge_in)
 
   after_bb = split_edge_bb_loc (edge_in);
 
+  /* Create a new block, and an edge F from that block to the original
+     destination.  */
   new_bb = create_empty_bb (after_bb);
   new_bb->frequency = EDGE_FREQUENCY (edge_in);
   new_bb->count = edge_in->count;
-  new_edge = make_single_succ_edge (new_bb, dest, EDGE_FALLTHRU);
+  f = make_replacement_pred_edge (new_bb, dest, edge_in, EDGE_FALLTHRU);
 
-  e = redirect_edge_and_branch (edge_in, new_bb);
+  /* Redirect the original edge to its new successor.  */
+  e = gimple_redirect_edge_and_branch_1 (edge_in, new_bb);
   gcc_assert (e == edge_in);
-  reinstall_phi_args (new_edge, e);
+  e->dest = new_bb;
+  vec_safe_push (new_bb->preds, e);
+  e->dest_idx = 0;
 
+  /* Fix up the predecessor edge for DEST to now be F.  We can't do
+     this prior to gimple_redirect_edge_and_branch_1 without raising
+     havoc in the switch code.  */
+  int idx = -1;
+  for (unsigned int i = 0; i < EDGE_COUNT (dest->preds); i++)
+    if (EDGE_PRED (dest, i) == edge_in)
+      {
+	idx = i;
+	break;
+      }
+  gcc_assert (idx != -1);
+  EDGE_PRED (dest, idx) = f;
+
   return new_bb;
 }
 
@@ -5740,12 +5748,10 @@ gimple_try_redirect_by_replacing_jump (edge e, bas
   return NULL;
 }
 
+/* Primary worker for gimple_redirect_edge_and_branch.  */
 
-/* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
-   edge representing the redirected branch.  */
-
 static edge
-gimple_redirect_edge_and_branch (edge e, basic_block dest)
+gimple_redirect_edge_and_branch_1 (edge e, basic_block dest)
 {
   basic_block bb = e->src;
   gimple_stmt_iterator gsi;
@@ -5759,7 +5765,10 @@ static edge
     return NULL;
 
   if (e->flags & EDGE_EH)
-    return redirect_eh_edge (e, dest);
+    {
+      redirect_eh_edge_1 (e, dest, false);
+      return e;
+    }
 
   if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
     {
@@ -5887,9 +5896,19 @@ static edge
       gcc_assert (e->flags & EDGE_FALLTHRU);
       break;
     }
+  return e;
+}
 
-  /* Update/insert PHI nodes as necessary.  */
+/* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
+   edge representing the redirected branch.  */
 
+static edge
+gimple_redirect_edge_and_branch (edge e, basic_block dest)
+{
+  edge f = gimple_redirect_edge_and_branch_1 (e, dest);
+  if (f != e)
+    return f;
+
   /* Now update the edges in the CFG.  */
   e = ssa_redirect_edge (e, dest);
 
@@ -8636,13 +8655,18 @@ split_critical_edges (void)
   basic_block bb;
   edge e;
   edge_iterator ei;
+  int first_free_block;
 
   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
      mappings around the calls to split_edge.  */
   start_recording_case_labels ();
+  first_free_block = last_basic_block_for_fn (cfun);
   FOR_ALL_BB_FN (bb, cfun)
     {
+      /* Don't re-split edges we've already split.  */
+      if (bb->index >= first_free_block)
+	continue;
       FOR_EACH_EDGE (e, ei, bb->succs)
         {
 	  if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
Index: gcc/tree-eh.c
===================================================================
--- gcc/tree-eh.c	(revision 250721)
+++ gcc/tree-eh.c	(working copy)
@@ -2279,7 +2279,7 @@ make_eh_edges (gimple *stmt)
    If false, we're being called from generic cfg manipulation code and we
    should preserve our place within the region tree.  */
 
-static void
+void
 redirect_eh_edge_1 (edge edge_in, basic_block new_bb, bool change_region)
 {
   eh_landing_pad old_lp, new_lp;
Index: gcc/tree-eh.h
===================================================================
--- gcc/tree-eh.h	(revision 250721)
+++ gcc/tree-eh.h	(working copy)
@@ -32,6 +32,7 @@ extern int lookup_stmt_eh_lp (gimple *);
 extern bool make_eh_dispatch_edges (geh_dispatch *);
 extern void make_eh_edges (gimple *);
 extern edge redirect_eh_edge (edge, basic_block);
+extern void redirect_eh_edge_1 (edge, basic_block, bool);
 extern void redirect_eh_dispatch_edge (geh_dispatch *, edge, basic_block);
 extern bool operation_could_trap_helper_p (enum tree_code, bool, bool, bool,
 					   bool, tree, bool *);