Re: Try to update dominance info in tree-call-cdce.c

[Richard Biener <richard dot guenther at gmail dot com>]

On Fri, Oct 30, 2015 at 12:18 PM, Richard Sandiford
<richard.sandiford@arm.com> wrote:
> The pass would free the dominance info after making a change, but it
> should be pretty easy to keep the information up-to-date when the call
> has no EH edges.  In a way the main hurdle was split_block, which seemed
> to assume that the new block would postdominate the old one, and that
> all blocks immediately dominated by the old block are now immediately
> dominated by the new one.
>
> Tested on x86_64-linux-gnu, arm-linux-gnueabi and aarch64-linux-gnu.
> OK to install?

Hmm, I don't understand why split_block needs to be touched.  The operation
itself correctly updates dominator info.  It is up to the pass to fix things up
if it does further CFG modifications that make the new block no longer
post-dominate the old one.

So why do you need the split_block change?

Richard.

> Thanks,
> Richard
>
>
> gcc/
>         * cfghooks.h (split_block): Add a flag to say whether all blocks
>         dominated by the old block are now dominated by the new one.
>         * cfghooks.c (split_block_1, split_block): Likewise,
>         (split_block_after_labels): Update accordingly.
>         * tree-call-cdce.c (shrink_wrap_one_built_in_call): Try to update
>         the dominance info; free it if we can't.
>         (pass_call_cdce::execute): Don't free the dominance info here.
>
> diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c
> index 2c5c96c..82c427f 100644
> --- a/gcc/cfghooks.c
> +++ b/gcc/cfghooks.c
> @@ -483,12 +483,18 @@ redirect_edge_and_branch_force (edge e, basic_block dest)
>    return ret;
>  }
>
> -/* Splits basic block BB after the specified instruction I (but at least after
> -   the labels).  If I is NULL, splits just after labels.  The newly created edge
> -   is returned.  The new basic block is created just after the old one.  */
> +/* Splits basic block BB after the specified instruction I (but at least
> +   after the labels).  If I is NULL, splits just after labels.
> +
> +   The newly created edge is returned.  The new basic block is created
> +   just after the old one.  It is assumed that the old block will dominate
> +   the new one; the caller can use set_immediate_dominator if this
> +   assumption is wrong.  If ASSUME_POSTDOM, it is further assumed that
> +   the new block will postdominate the old block, so that all blocks
> +   dominated by the old block are now also dominated by the new one.  */
>
>  static edge
> -split_block_1 (basic_block bb, void *i)
> +split_block_1 (basic_block bb, void *i, bool assume_postdom)
>  {
>    basic_block new_bb;
>    edge res;
> @@ -506,7 +512,8 @@ split_block_1 (basic_block bb, void *i)
>
>    if (dom_info_available_p (CDI_DOMINATORS))
>      {
> -      redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
> +      if (assume_postdom)
> +       redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
>        set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
>      }
>
> @@ -533,15 +540,15 @@ split_block_1 (basic_block bb, void *i)
>  }
>
>  edge
> -split_block (basic_block bb, gimple *i)
> +split_block (basic_block bb, gimple *i, bool assume_postdom)
>  {
> -  return split_block_1 (bb, i);
> +  return split_block_1 (bb, i, assume_postdom);
>  }
>
>  edge
> -split_block (basic_block bb, rtx i)
> +split_block (basic_block bb, rtx i, bool assume_postdom)
>  {
> -  return split_block_1 (bb, i);
> +  return split_block_1 (bb, i, assume_postdom);
>  }
>
>  /* Splits block BB just after labels.  The newly created edge is returned.  */
> @@ -549,7 +556,7 @@ split_block (basic_block bb, rtx i)
>  edge
>  split_block_after_labels (basic_block bb)
>  {
> -  return split_block_1 (bb, NULL);
> +  return split_block_1 (bb, NULL, true);
>  }
>
>  /* Moves block BB immediately after block AFTER.  Returns false if the
> diff --git a/gcc/cfghooks.h b/gcc/cfghooks.h
> index a0cb6fd..8f6b465 100644
> --- a/gcc/cfghooks.h
> +++ b/gcc/cfghooks.h
> @@ -208,8 +208,8 @@ extern edge redirect_edge_succ_nodup (edge, basic_block);
>  extern bool can_remove_branch_p (const_edge);
>  extern void remove_branch (edge);
>  extern void remove_edge (edge);
> -extern edge split_block (basic_block, rtx);
> -extern edge split_block (basic_block, gimple *);
> +extern edge split_block (basic_block, rtx, bool = true);
> +extern edge split_block (basic_block, gimple *, bool = true);
>  extern edge split_block_after_labels (basic_block);
>  extern bool move_block_after (basic_block, basic_block);
>  extern void delete_basic_block (basic_block);
> diff --git a/gcc/tree-call-cdce.c b/gcc/tree-call-cdce.c
> index 57be8a4..72828dd 100644
> --- a/gcc/tree-call-cdce.c
> +++ b/gcc/tree-call-cdce.c
> @@ -735,6 +735,32 @@ shrink_wrap_one_built_in_call (gcall *bi_call)
>    if (nconds == 0)
>      return false;
>
> +  /* The cfg we want to create looks like this:
> +
> +          [guard n-1]         <- guard_bb (old block)
> +            |    \
> +            | [guard n-2]                   }
> +            |    / \                        }
> +            |   /  ...                      } new blocks
> +            |  /  [guard 0]                 }
> +            | /    /   |                    }
> +           [ call ]    |     <- bi_call_bb  }
> +            | \        |
> +            |  \       |
> +            |   [ join ]     <- join_tgt_bb (old iff call must end bb)
> +            |
> +        possible EH edges (only if [join] is old)
> +
> +     When [join] is new, the immediate dominators for these blocks are:
> +
> +     1. [guard n-1]: unchanged
> +     2. [call]: [guard n-1]
> +     3. [guard m]: [guard m+1] for 0 <= m <= n-2
> +     4. [join]: [guard n-1]
> +
> +     We punt for the more complex case case of [join] being old and
> +     simply free the dominance info.  We also punt on postdominators,
> +     which aren't expected to be available at this point anyway.  */
>    bi_call_bb = gimple_bb (bi_call);
>
>    /* Now find the join target bb -- split bi_call_bb if needed.  */
> @@ -745,9 +771,13 @@ shrink_wrap_one_built_in_call (gcall *bi_call)
>        join_tgt_in_edge_from_call = find_fallthru_edge (bi_call_bb->succs);
>        if (join_tgt_in_edge_from_call == NULL)
>          return false;
> +      free_dominance_info (CDI_DOMINATORS);
>      }
>    else
> -    join_tgt_in_edge_from_call = split_block (bi_call_bb, bi_call);
> +    /* The old block ([guard n-1], currently called bi_call_bb) is the
> +       immediate dominator of join_tgt_bb.  join_tgt_bb will also
> +       postdominate the guard block.  */
> +    join_tgt_in_edge_from_call = split_block (bi_call_bb, bi_call, true);
>
>    bi_call_bsi = gsi_for_stmt (bi_call);
>
> @@ -772,7 +802,10 @@ shrink_wrap_one_built_in_call (gcall *bi_call)
>    ci++;
>    gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND);
>
> -  bi_call_in_edge0 = split_block (bi_call_bb, cond_expr);
> +  /* The old block (for [guard n-1]) is the immediate dominator of the
> +     new block (for the call).  The call block does not postdominate
> +     the guard block.  */
> +  bi_call_in_edge0 = split_block (bi_call_bb, cond_expr, false);
>    bi_call_in_edge0->flags &= ~EDGE_FALLTHRU;
>    bi_call_in_edge0->flags |= EDGE_TRUE_VALUE;
>    guard_bb = bi_call_bb;
> @@ -790,6 +823,7 @@ shrink_wrap_one_built_in_call (gcall *bi_call)
>        guard_bb->count - bi_call_in_edge0->count;
>
>    /* Code generation for the rest of the conditions  */
> +  basic_block prev_guard_bb = NULL;
>    while (nconds > 0)
>      {
>        unsigned ci0;
> @@ -809,7 +843,12 @@ shrink_wrap_one_built_in_call (gcall *bi_call)
>        nconds--;
>        ci++;
>        gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND);
> -      guard_bb_in_edge = split_block (guard_bb, cond_expr);
> +
> +      /* The old block (for the guard we just added) is the immediate
> +        dominator of the new block (for the previous guard).  The new
> +        block does not postdominate the old one; the immediate postdominator
> +        of the old block is still join_tgt_bb.  */
> +      guard_bb_in_edge = split_block (guard_bb, cond_expr, false);
>        guard_bb_in_edge->flags &= ~EDGE_FALLTHRU;
>        guard_bb_in_edge->flags |= EDGE_FALSE_VALUE;
>
> @@ -822,6 +861,13 @@ shrink_wrap_one_built_in_call (gcall *bi_call)
>        guard_bb_in_edge->probability =
>            inverse_probability (bi_call_in_edge->probability);
>        guard_bb_in_edge->count = guard_bb->count - bi_call_in_edge->count;
> +
> +      /* If this is [guard m] for m >= 2, make [guard m-1] the immediate
> +        dominator of [guard m-2].  */
> +      if (prev_guard_bb && dom_info_available_p (CDI_DOMINATORS))
> +       set_immediate_dominator (CDI_DOMINATORS, prev_guard_bb,
> +                                guard_bb_in_edge->dest);
> +      prev_guard_bb = guard_bb_in_edge->dest;
>      }
>
>    if (dump_file && (dump_flags & TDF_DETAILS))
> @@ -931,7 +977,6 @@ pass_call_cdce::execute (function *fun)
>
>    if (something_changed)
>      {
> -      free_dominance_info (CDI_DOMINATORS);
>        free_dominance_info (CDI_POST_DOMINATORS);
>        /* As we introduced new control-flow we need to insert PHI-nodes
>           for the call-clobbers of the remaining call.  */
>