[RFA] [PR tree-optimization/71661] Fix forwarder removal when new loops are exposed

[Richard Biener]

On Wed, Oct 5, 2016 at 5:58 PM, Jeff Law <law@redhat.com> wrote:
>
> Removal of forwarder blocks is a two step process.
>
> First we build a worklist of potential forwarder blocks,  Then we iterate
> over that worklist attempting to remove each potential forwarder block in
> the worklist.
>
> The code which builds the worklist is aware that we do not want to remove a
> forwarder that is a loop header and avoids putting such blocks into the
> worklist.
>
> The problem is that removing a forwarder block may turn an irreducible
> region into a natural loop, which of course will have a loop header. But
> that loop header could not be recognized as such during the initial building
> of the worklist.
>
> So as a result if removal of a forwarder block exposes a new loop and the
> header of that newly exposed loop appears to be a forwarder block, we may
> forward through the newly exposed loop header too.  That can squash two
> loops into a single loop, which invalidates the cached iteration information
> and other stuff which can in turn cause incorrect code generation (as seen
> by 71661).
>
> There's two ways to address this problem.  First we could invalidate the
> cached loop info when this situation occurs.  Second, we could avoid
> forwarding through the newly exposed loop header.
>
> The patch takes the latter approach.  Based on the CFG transformations for
> 71661, I think we're better off leaving the newly exposed loop alone --
> we've exposed a nice simple loop nest, collapsing the nest into a single
> loop with multiple latch edges just seems wrong.
>
> Bootstrapped and regression tested on x86_64-linux.gnu.  OK for the trunk?

The remove_forwarder_block hunk is redundant (I've fixed a similar bug there
by checking in tree_forwarder_block_p).  This function doesn't operate from
a worklist and thus shouldn't have the issue.

The remove_forwarder_block_with_phi hunk is ok.

Thanks,
Richard.

> Jeff
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 2b56878..33ee250 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,10 @@
> +2016-10-05  Jeff Law  <law@redhat.com>
> +
> +       PR tree-optimization/71661
> +       * tree-cfgcleanup.c (remove_forwarder_block): Handle case when
> removal
> +       of a forwarder exposes a new natural loop.
> +       (remove_forwarder_block_with_phi): Likewise.
> +
>  2016-10-05  Martin Sebor  <msebor@redhat.com>
>
>         PR bootstrap/77819
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index fa1f310..3bba95d 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,8 @@
> +2016-10-05  Jeff Law  <law@redhat.com>
> +
> +        PR tree-optimization/71661
> +       * gcc.dg/tree-ssa/pr71661.c: New test.
> +
>  2016-10-05  Richard Biener  <rguenther@suse.de>
>
>         PR middle-end/77826
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71661.c
> b/gcc/testsuite/gcc.dg/tree-ssa/pr71661.c
> new file mode 100644
> index 0000000..c273ea1
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71661.c
> @@ -0,0 +1,31 @@
> +/* { dg-do run } */
> +/* { dg-options "-O3 -fdisable-tree-ethread" } */
> +
> +extern void exit (int);
> +
> +int a, b;
> +
> +void
> +fn1 ()
> +{
> +  unsigned c = 0;
> +  int d;
> +  b = a;
> +  if (a < 0)
> +    goto L1;
> +  for (; a < 1; a++)
> +    d = 0;
> +  for (; d < 2; d++)
> +    {
> +      for (c = 0; c < 3; c++)
> +      L1:
> +        a = 2;
> +    }
> +}
> +
> +int
> +main ()
> +{
> +  fn1 ();
> +  exit (0);
> +}
> diff --git a/gcc/tree-cfgcleanup.c b/gcc/tree-cfgcleanup.c
> index 6052872..e3cb8ee 100644
> --- a/gcc/tree-cfgcleanup.c
> +++ b/gcc/tree-cfgcleanup.c
> @@ -418,6 +418,11 @@ remove_forwarder_block (basic_block bb)
>    if (dest == bb)
>      return false;
>
> +  /* Removal of forwarders may expose new natural loops and thus
> +     a block may turn into a loop header.  */
> +  if (current_loops && bb_loop_header_p (bb))
> +    return false;
> +
>    /* If the destination block consists of a nonlocal label or is a
>       EH landing pad, do not merge it.  */
>    label = first_stmt (dest);
> @@ -840,6 +845,11 @@ remove_forwarder_block_with_phi (basic_block bb)
>    if (dest == bb)
>      return false;
>
> +  /* Removal of forwarders may expose new natural loops and thus
> +     a block may turn into a loop header.  */
> +  if (current_loops && bb_loop_header_p (bb))
> +    return false;
> +
>    /* If the destination block consists of a nonlocal label, do not
>       merge it.  */
>    label = first_stmt (dest);
>