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

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

[Richard Sandiford]

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?

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.  */

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

[Richard Biener]

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.  */
>

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

[Richard Sandiford]

Richard Biener <richard.guenther@gmail.com> writes:
> 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?

The updates we'd need here would be:

    redirect_immediate_dominators (CDI_DOMINATORS, call, guard_bb);

which undoes the earlier:

    redirect_immediate_dominators (CDI_DOMINATORS, guard_bb, call);

that split_block did.  It just seemed wasteful to call
redirect_immediate_dominators twice to get a no-op.

In other words, there are going to be callers to split_block that
know the second block isn't going to postdominate the first and
where the calling;

    redirect_immediate_dominators (CDI_DOMINATORS, first_block,
                                   second_block);

is taking us further from where we want to be.

Thanks,
Richard

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

[Richard Biener]

On Fri, Oct 30, 2015 at 1:14 PM, Richard Sandiford
<richard.sandiford@arm.com> wrote:
> Richard Biener <richard.guenther@gmail.com> writes:
>> 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?
>
> The updates we'd need here would be:
>
>     redirect_immediate_dominators (CDI_DOMINATORS, call, guard_bb);
>
> which undoes the earlier:
>
>     redirect_immediate_dominators (CDI_DOMINATORS, guard_bb, call);
>
> that split_block did.  It just seemed wasteful to call
> redirect_immediate_dominators twice to get a no-op.
>
> In other words, there are going to be callers to split_block that
> know the second block isn't going to postdominate the first and
> where the calling;
>
>     redirect_immediate_dominators (CDI_DOMINATORS, first_block,
>                                    second_block);
>
> is taking us further from where we want to be.

That's true.  In an ideal world we'd have a CFG hook creating a
(half) diamond directly.

I wonder how other passes work around this issue?  I suppose
they are splitting the block to form the conditonal block and the
joiner?  If you have those and then only split the fallthru edge
between them the redundant work done is minimal.

Richard.

> Thanks,
> Richard
>

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

[Richard Sandiford]

Richard Biener <richard.guenther@gmail.com> writes:
> On Fri, Oct 30, 2015 at 1:14 PM, Richard Sandiford
> <richard.sandiford@arm.com> wrote:
>> Richard Biener <richard.guenther@gmail.com> writes:
>>> 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?
>>
>> The updates we'd need here would be:
>>
>>     redirect_immediate_dominators (CDI_DOMINATORS, call, guard_bb);
>>
>> which undoes the earlier:
>>
>>     redirect_immediate_dominators (CDI_DOMINATORS, guard_bb, call);
>>
>> that split_block did.  It just seemed wasteful to call
>> redirect_immediate_dominators twice to get a no-op.
>>
>> In other words, there are going to be callers to split_block that
>> know the second block isn't going to postdominate the first and
>> where the calling;
>>
>>     redirect_immediate_dominators (CDI_DOMINATORS, first_block,
>>                                    second_block);
>>
>> is taking us further from where we want to be.
>
> That's true.  In an ideal world we'd have a CFG hook creating a
> (half) diamond directly.
>
> I wonder how other passes work around this issue?  I suppose
> they are splitting the block to form the conditonal block and the
> joiner?  If you have those and then only split the fallthru edge
> between them the redundant work done is minimal.

Yeah, but that then makes the code more complicated because you
still need to split the call block from the guard block rather than
the joiner in the EH case.  It also means that you need to do more
set_immediate_dominators (the call is not the immediate dominator
of the join block), whereas with the current code that falls out
naturally.

Is the split_block change really so bad?

Thanks,
Richard

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

[Steven Bosscher]

On Fri, Oct 30, 2015 at 2:11 PM, Richard Sandiford
<richard.sandiford@arm.com> wrote:
> Is the split_block change really so bad?

IMHO: Yes.

split_block just splits some basic block B into two blocks B1/B2
somewhere in the middle of B. The dominance relations between B1 and
B2 are obvious and intuitive. The new flag to split_block is not. The
dominance info is not updated but the loops are? Confusing, if you ask
me...

Your situation, where a pass knows the dominance relations will
change, is unusual. The extra work to fix up the ET tree twice should
be negligible anyway.

Ciao!
Steven

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

[Richard Sandiford]

Steven Bosscher <stevenb.gcc@gmail.com> writes:
> On Fri, Oct 30, 2015 at 2:11 PM, Richard Sandiford
> <richard.sandiford@arm.com> wrote:
>> Is the split_block change really so bad?
>
> IMHO: Yes.

Fair enough :-)

> split_block just splits some basic block B into two blocks B1/B2
> somewhere in the middle of B. The dominance relations between B1 and
> B2 are obvious and intuitive. The new flag to split_block is not. The
> dominance info is not updated but the loops are? Confusing, if you ask
> me...
>
> Your situation, where a pass knows the dominance relations will
> change, is unusual. The extra work to fix up the ET tree twice should
> be negligible anyway.

I just thought that the cfg was in practice never going to stay in the
state that it is on return from split_block.  The caller is bound to
add (at least) another edge somewhere.

Here's a version that works with split_block rather than against it.
Tested on x86_64-linux-gnu, arm-linux-gnueabi and aarch64-linux-gnu.
OK to install?

Thanks,
Richard

    
gcc/
    	* 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/tree-call-cdce.c b/gcc/tree-call-cdce.c
index ffc1c4e..a5f38ce 100644
--- a/gcc/tree-call-cdce.c
+++ b/gcc/tree-call-cdce.c
@@ -731,6 +731,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.  */
@@ -741,6 +767,7 @@ 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);
@@ -820,6 +847,15 @@ shrink_wrap_one_built_in_call (gcall *bi_call)
       guard_bb_in_edge->count = guard_bb->count - bi_call_in_edge->count;
     }
 
+  if (dom_info_available_p (CDI_DOMINATORS))
+    {
+      /* The split_blocks leave [guard 0] as the immediate dominator
+	 of [call] and [call] as the immediate dominator of [join].
+	 Fix them up.  */
+      set_immediate_dominator (CDI_DOMINATORS, bi_call_bb, guard_bb);
+      set_immediate_dominator (CDI_DOMINATORS, join_tgt_bb, guard_bb);
+    }
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       location_t loc;
@@ -927,7 +963,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.  */

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

[Jeff Law]

On 11/02/2015 08:53 AM, Richard Sandiford wrote:
> Steven Bosscher <stevenb.gcc@gmail.com> writes:
>> On Fri, Oct 30, 2015 at 2:11 PM, Richard Sandiford
>> <richard.sandiford@arm.com> wrote:
>>> Is the split_block change really so bad?
>>
>> IMHO: Yes.
>
> Fair enough :-)
I tend to agree.  If the caller needs a more complex control flow and 
dominance/post-dominance relationship set up, then it seems like it 
belongs in the caller.

If there's enough commonality in cases where the caller is going to do 
something more complex with the CFG, then perhaps there could be a 
function to (as Richi suggests) create diamonds, half diamonds or 
something else commonly needed.

>
> I just thought that the cfg was in practice never going to stay in the
> state that it is on return from split_block.  The caller is bound to
> add (at least) another edge somewhere.
Perhaps.  But that functionality (assuming it's common) can be layered 
on top of split_block pretty easily it seems.


>
> Here's a version that works with split_block rather than against it.
> Tested on x86_64-linux-gnu, arm-linux-gnueabi and aarch64-linux-gnu.
> OK to install?
>
> Thanks,
> Richard
>
>
> gcc/
>      	* 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.
OK.

Thoughts on emitting something into the dump file in tree-call-cdce.c 
which indicates when the dominators/post-dominators are invalidated?  Or 
better yet, put it in free_dominance_info.  Then we could have a 
testcase which verifies that we're updating rather than recomputing in 
the case which led to this change, and in cases where there's EH bits to 
update that we recompute.

Jeff