Fix PR81354 (rewrite gimple_split_edge)

On Sun, Jul 30, 2017 at 8:04 PM, Bill Schmidt
<wschmidt@linux.vnet.ibm.com> wrote:
> 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.

I don't like make_replacement_pred_edge too much.  Wouldn't it work
to make sure we first shrink and then re-grow like if we simply do the
redirect_edge_and_branch before the make_single_succ_edge call?
At least quick testing shows it fixes the testcase on the GCC 6 branch for me.

Sorry for misleading you to a complex solution.

Thanks,
Richard.

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

Fix PR81354 (rewrite gimple_split_edge)

Commit Message

Comments

Patch