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

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?

Jeff

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

On 10/06/2016 04:11 AM, Richard Biener wrote:
>
> 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.
Agreed.  I hadn't really looked closely at remove_forwarder_block, but 
it has the same check for newly exposed infinite loops so my patch added 
the check for new loop headers in both places.  But I agree it isn't 
necessary here when I look at how remove_forwarder_block is used.


>
> The remove_forwarder_block_with_phi hunk is ok.
I'll extract/install just the remove_forwarder_block_with_phi hunk & the 
testcase.

Thanks,
jeff