Re: [PATCH][PR tree-optimization/78856] Invalidate cached iteration information when threading across multiple loop headers

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

On Wed, Jan 4, 2017 at 6:31 AM, Jeff Law <law@redhat.com> wrote:
>
> So as noted in the BZ comments the jump threading code has code that detects
> when a jump threading path wants to cross multiple loop headers and
> truncates the jump threading path in that case.
>
> What we should have done instead is invalidate the cached loop information.
>
> Additionally, this BZ shows that just looking at loop headers is not
> sufficient -- we might cross from a reducible to an irreducible region which
> is equivalent to crossing into another loop in that we need to invalidate
> the cached loop iteration information.
>
> What's so damn funny here is that eventually we take nested loops and
> irreducible regions, thread various edges and end up with a nice natural
> loop and no irreducible regions in the end :-)  But the cached iteration
> information is still bogus.
>
> Anyway, this patch corrects both issues.  It treats moving between an
> reducible and irreducible region as crossing a loop header and it
> invalidates the cached iteration information rather than truncating the jump
> thread path.
>
> Bootstrapped and regression tested on x86_64-linux-gnu.  That compiler was
> also used to build all the configurations in config-list.mk.
>
> Installing on the trunk.  I could be convinced to install on the gcc-6
> branch as well since it's affected by the same problem.
>
> Jeff
>
>
> commit 93e3964a4664350446eefe786e3b73eb41d99036
> Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
> Date:   Wed Jan 4 05:31:23 2017 +0000
>
>         PR tree-optimizatin/78856
>         * tree-ssa-threadupdate.c: Include tree-vectorizer.h.
>         (mark_threaded_blocks): Remove code to truncate thread paths that
>         cross multiple loop headers.  Instead invalidate the cached loop
>         iteration information and handle case of a thread path walking
>         into an irreducible region.
>
>         PR tree-optimization/78856
>         * gcc.c-torture/execute/pr78856.c: New test.
>
>     git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@244045
> 138bc75d-0d04-0410-961f-82ee72b054a4
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 3114e02..6b2888f 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,12 @@
> +2017-01-03  Jeff Law  <law@redhat.com>
> +
> +       PR tree-optimizatin/78856
> +       * tree-ssa-threadupdate.c: Include tree-vectorizer.h.
> +       (mark_threaded_blocks): Remove code to truncate thread paths that
> +       cross multiple loop headers.  Instead invalidate the cached loop
> +       iteration information and handle case of a thread path walking
> +       into an irreducible region.
> +
>  2016-12-30  Michael Meissner  <meissner@linux.vnet.ibm.com>
>
>         PR target/78900
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index cd2a065..cadfbc9 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,8 @@
> +2017-01-03  Jeff Law  <law@redhat.com>
> +
> +       PR tree-optimization/78856
> +       * gcc.c-torture/execute/pr78856.c: New test.
> +
>  2017-01-03  Michael Meissner  <meissner@linux.vnet.ibm.com>
>
>         PR target/78953
> diff --git a/gcc/testsuite/gcc.c-torture/execute/pr78856.c
> b/gcc/testsuite/gcc.c-torture/execute/pr78856.c
> new file mode 100644
> index 0000000..80f2317
> --- /dev/null
> +++ b/gcc/testsuite/gcc.c-torture/execute/pr78856.c
> @@ -0,0 +1,25 @@
> +extern void exit (int);
> +
> +int a, b, c, d, e, f[3];
> +
> +int main()
> +{
> +  while (d)
> +    while (1)
> +      ;
> +  int g = 0, h, i = 0;
> +  for (; g < 21; g += 9)
> +    {
> +      int j = 1;
> +      for (h = 0; h < 3; h++)
> +       f[h] = 1;
> +      for (; j < 10; j++) {
> +       d = i && (b ? 0 : c);
> +       i = 1;
> +       if (g)
> +         a = e;
> +      }
> +  }
> +  exit (0);
> +}
> +
> diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
> index adbb6e0..2da93a8 100644
> --- a/gcc/tree-ssa-threadupdate.c
> +++ b/gcc/tree-ssa-threadupdate.c
> @@ -34,6 +34,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "cfgloop.h"
>  #include "dbgcnt.h"
>  #include "tree-cfg.h"
> +#include "tree-vectorizer.h"
>
>  /* Given a block B, update the CFG and SSA graph to reflect redirecting
>     one or more in-edges to B to instead reach the destination of an
> @@ -2084,10 +2085,8 @@ mark_threaded_blocks (bitmap threaded_blocks)
>    /* Look for jump threading paths which cross multiple loop headers.
>
>       The code to thread through loop headers will change the CFG in ways
> -     that break assumptions made by the loop optimization code.
> -
> -     We don't want to blindly cancel the requests.  We can instead do
> better
> -     by trimming off the end of the jump thread path.  */
> +     that invalidate the cached loop iteration information.  So we must
> +     detect that case and wipe the cached information.  */
>    EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
>      {
>        basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
> @@ -2102,26 +2101,16 @@ mark_threaded_blocks (bitmap threaded_blocks)
>                    i++)
>                 {
>                   basic_block dest = (*path)[i]->e->dest;
> +                 basic_block src = (*path)[i]->e->src;
>                   crossed_headers += (dest == dest->loop_father->header);
> +                 /* If we step from a block outside an irreducible region
> +                    to a block inside an irreducible region, then we have
> +                    crossed into a loop.  */
> +                 crossed_headers += ((src->flags & BB_IRREDUCIBLE_LOOP)
> +                                     != (dest->flags &
> BB_IRREDUCIBLE_LOOP));

I'm not sure about this one -- if dest is inside an irreducible region then
dest->loop_father will be the containing loop which may be unrelated
(just crossed).  Either we miss handling of crossed loop headers or
whether dest is inside an irreducible region doesn't matter.

So, don't we want to check only whether we are src is inside a irreducible
region and dest is not?  And in this case we've crossed a loop header
anyway...

>                   if (crossed_headers > 1)
>                     {
> -                     /* Trim from entry I onwards.  */
> -                     for (unsigned int j = i; j < path->length (); j++)
> -                       delete (*path)[j];
> -                     path->truncate (i);
> -
> -                     /* Now that we've truncated the path, make sure
> -                        what's left is still valid.   We need at least
> -                        two edges on the path and the last edge can not
> -                        be a joiner.  This should never happen, but let's
> -                        be safe.  */
> -                     if (path->length () < 2
> -                         || (path->last ()->type
> -                             == EDGE_COPY_SRC_JOINER_BLOCK))
> -                       {
> -                         delete_jump_thread_path (path);
> -                         e->aux = NULL;
> -                       }
> +                     vect_free_loop_info_assumptions (dest->loop_father);
>                       break;
>                     }
>                 }
>