FIx pr58640

The problem shown by pr58640 is the more aggressive jump threading is 
recording a jump threading opportunity that crosses through two loop 
headers.

The updating code is not prepared to update the CFG and loop structures 
in that situation.  The net result is we have two latch edges for a 
particular loop.  This causes the full unrolling code to go a bit nuts 
with a particular block is considered unreachable and has no outgoing 
edges.  It is (of course) reachable and falling off the end of the block 
results in bad things happening.

The easiest fix would be to simply cancel the jump threading request 
entirely.  However, we can do better by merely truncating the request 
immediately prior to crossing the second loop entry point.

In fact, the code we generate for pr58640 is considerably better when we 
truncate the path rather than eliminating the jump threading request 
entirely.

Bootstrapped and regression tested on x86_64-unknown-linux-gnu. 
Installed onto the trunk.
commit 7aec1a83e5c18ddb0f053b28f62a1c242ab9e477
Author: Jeff Law <law@redhat.com>
Date:   Fri Oct 11 14:24:11 2013 -0600

    	PR tree-optimization/58640
    	* tree-ssa-threadupdate.c (mark_threaded_blocks): Truncate jump threading
    	paths that cross over two loop entry points.
    
    	* gcc.c-torture/execute/pr58640.c: New test.

On Fri, Oct 11, 2013 at 10:31 PM, Jeff Law <law@redhat.com> wrote:
>
> The problem shown by pr58640 is the more aggressive jump threading is
> recording a jump threading opportunity that crosses through two loop
> headers.
>
> The updating code is not prepared to update the CFG and loop structures in
> that situation.  The net result is we have two latch edges for a particular
> loop.

The "proper" fix for this is to clear loop->latch (a NULL latch means that
we have multiple latches) and make sure that
LOOPS_MAY_HAVE_MULTIPLE_LATCHES is set.

It may also be that we disambiguate the multiple latches later but in
a way that makes associated loop information (like maximum number
of iterations) incorrect (for example if your threading "merges" two loops
and then disambiguation creates loops effectively swapped, attaching
the associated loop info to the wrong one).

>  This causes the full unrolling code to go a bit nuts with a
> particular block is considered unreachable and has no outgoing edges.  It is
> (of course) reachable and falling off the end of the block results in bad
> things happening.
>
> The easiest fix would be to simply cancel the jump threading request
> entirely.  However, we can do better by merely truncating the request
> immediately prior to crossing the second loop entry point.
>
> In fact, the code we generate for pr58640 is considerably better when we
> truncate the path rather than eliminating the jump threading request
> entirely.
>
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu. Installed
> onto the trunk.
>
>
> commit 7aec1a83e5c18ddb0f053b28f62a1c242ab9e477
> Author: Jeff Law <law@redhat.com>
> Date:   Fri Oct 11 14:24:11 2013 -0600
>
>         PR tree-optimization/58640
>         * tree-ssa-threadupdate.c (mark_threaded_blocks): Truncate jump
> threading
>         paths that cross over two loop entry points.
>
>         * gcc.c-torture/execute/pr58640.c: New test.
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 41e29dc..9f4e297 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,9 @@
> +2013-10-11  Jeff Law  <law@redhat.com>
> +
> +       PR tree-optimization/58640
> +       * tree-ssa-threadupdate.c (mark_threaded_blocks): Truncate jump
> threading
> +       paths that cross over two loop entry points.
> +
>  2013-10-11  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>
>
>         * config/rs6000/vsx.md (*vsx_le_perm_load_v2di): Generalize to
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 87ff2a7..bb2ede4 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,7 @@
> +2013-10-11  Jeff Law  <law@redhat.com>
> +
> +       * gcc.c-torture/execute/pr58640.c: New test.
> +
>  2013-10-11  Paolo Carlini  <paolo.carlini@oracle.com>
>
>         PR c++/58633
> diff --git a/gcc/testsuite/gcc.c-torture/execute/pr58640.c
> b/gcc/testsuite/gcc.c-torture/execute/pr58640.c
> new file mode 100644
> index 0000000..7786b8d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.c-torture/execute/pr58640.c
> @@ -0,0 +1,32 @@
> +int a, b, c, d = 1, e;
> +
> +static signed char
> +foo ()
> +{
> +  int f, g = a;
> +
> +  for (f = 1; f < 3; f++)
> +    for (; b < 1; b++)
> +      {
> +        if (d)
> +          for (c = 0; c < 4; c++)
> +            for (f = 0; f < 3; f++)
> +              {
> +                for (e = 0; e < 1; e++)
> +                  a = g;
> +                if (f)
> +                  break;
> +              }
> +        else if (f)
> +          continue;
> +        return 0;
> +      }
> +  return 0;
> +}
> +
> +int
> +main ()
> +{
> +  foo ();
> +  exit (0);
> +}
> diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
> index 2adea1b..3e34567 100644
> --- a/gcc/tree-ssa-threadupdate.c
> +++ b/gcc/tree-ssa-threadupdate.c
> @@ -1354,6 +1354,68 @@ mark_threaded_blocks (bitmap threaded_blocks)
>    else
>      bitmap_copy (threaded_blocks, tmp);
>
> +  /* 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.  */
> +  EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
> +    {
> +      basic_block bb = BASIC_BLOCK (i);
> +      FOR_EACH_EDGE (e, ei, bb->preds)
> +       {
> +         if (e->aux)
> +           {
> +             vec<jump_thread_edge *> *path = THREAD_PATH (e);
> +
> +             /* Basically we're looking for a situation where we can see
> +                3 or more loop structures on a jump threading path.  */
> +
> +             struct loop *first_father = (*path)[0]->e->src->loop_father;
> +             struct loop *second_father = NULL;
> +             for (unsigned int i = 0; i < path->length (); i++)
> +               {
> +                 /* See if this is a loop father we have not seen before.
> */
> +                 if ((*path)[i]->e->dest->loop_father != first_father
> +                     && (*path)[i]->e->dest->loop_father != second_father)
> +                   {
> +                     /* We've already seen two loop fathers, so we
> +                        need to trim this jump threading path.  */
> +                     if (second_father != NULL)
> +                       {
> +                         /* 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))
> +                           {
> +                             for (unsigned int i = 0; i < path->length ();
> i++)
> +                               delete (*path)[i];
> +                             path->release ();
> +                             e->aux = NULL;
> +                           }
> +                         break;
> +                       }
> +                     else
> +                       {
> +                         second_father = (*path)[i]->e->dest->loop_father;
> +                       }
> +                   }
> +               }
> +           }
> +       }
> +    }
> +
>    BITMAP_FREE (tmp);
>  }
>
>