[PR,tree-optimization/61515] Fix poor compile-time behaviour in tree-ssa-threadedge.c

When we thread across a backedge, we have to do invalidations of 
equivalences.  This changes the method by which we identify which 
objects need invalidation.  Previously we'd walk all the SSA_NAMEs and 
see if any had a current value that needed invalidation.  That is 
obviously expensive if we have a lot of SSA_NAMEs.

This patch implements an idea from Richi, basically walk the equivalency 
unwinder stack, which has equivalences from both DOM and the threader. 
Check the current value of each object in that stack and see if it needs 
invalidation.  Even pathlogical cases this ought to be considerably 
faster than walking all the SSA_NAMEs.

For the reduced testcase, compilation time in the relevant parts of GCC 
go from 40 seconds to less than a second.

Bootstrapped and regression tested on x86_64-unknown-linux-gnu. 
Installed on the trunk.

On Sat, Nov 8, 2014 at 12:00 AM, Jeff Law <law@redhat.com> wrote:
>
> When we thread across a backedge, we have to do invalidations of
> equivalences.  This changes the method by which we identify which objects
> need invalidation.  Previously we'd walk all the SSA_NAMEs and see if any
> had a current value that needed invalidation.  That is obviously expensive
> if we have a lot of SSA_NAMEs.
>
> This patch implements an idea from Richi, basically walk the equivalency
> unwinder stack, which has equivalences from both DOM and the threader. Check
> the current value of each object in that stack and see if it needs
> invalidation.  Even pathlogical cases this ought to be considerably faster
> than walking all the SSA_NAMEs.
>
> For the reduced testcase, compilation time in the relevant parts of GCC go
> from 40 seconds to less than a second.
>
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu. Installed on
> the trunk.

Thanks - can we still avoid walking the stack for each LHS by first computing
which SSA names to invalidate using a bitmap?  For some reason this
didn't work with walking SSA names (see my proposed patch in the PR),
maybe you can figure out why.

But yes, the stack should always be smaller than the number of SSA names
(not sure if we can actually prove that, but ...).

I hope we can backport this to 4.9 after a while.

Thanks,
Richard.

>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 966c0b4..0c8eb79 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,9 @@
> +2014-11-07  Jeff Law  <law@redhat.com>
> +
> +       PR tree-optimization/61515
> +       * tree-ssa-threadedge.c (invalidate_equivalences): Walk the
> unwinding
> +       stack rather than looking at every SSA_NAME's value.
> +
>  2014-11-07  Richard Biener  <rguenther@suse.de>
>
>         PR tree-optimization/63605
> diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
> index de3c819..d5b9696 100644
> --- a/gcc/tree-ssa-threadedge.c
> +++ b/gcc/tree-ssa-threadedge.c
> @@ -290,15 +290,40 @@ fold_assignment_stmt (gimple stmt)
>  }
>
>  /* A new value has been assigned to LHS.  If necessary, invalidate any
> -   equivalences that are no longer valid.  */
> +   equivalences that are no longer valid.   This includes invaliding
> +   LHS and any objects that are currently equivalent to LHS.
> +
> +   Finding the objects that are currently marked as equivalent to LHS
> +   is a bit tricky.  We could walk the ssa names and see if any have
> +   SSA_NAME_VALUE that is the same as LHS.  That's expensive.
> +
> +   However, it's far more efficient to look at the unwinding stack as
> +   that will have all context sensitive equivalences which are the only
> +   ones that we really have to worry about here.   */
>  static void
>  invalidate_equivalences (tree lhs, vec<tree> *stack)
>  {
>
> -  for (unsigned int i = 1; i < num_ssa_names; i++)
> -    if (ssa_name (i) && SSA_NAME_VALUE (ssa_name (i)) == lhs)
> -      record_temporary_equivalence (ssa_name (i), NULL_TREE, stack);
> +  /* The stack is an unwinding stack.  If the current element is NULL
> +     then it's a "stop unwinding" marker.  Else the current marker is
> +     the SSA_NAME with an equivalence and the prior entry in the stack
> +     is what the current element is equivalent to.  */
> +  for (int i = stack->length() - 1; i >= 0; i--)
> +    {
> +      /* Ignore the stop unwinding markers.  */
> +      if ((*stack)[i] == NULL)
> +       continue;
> +
> +      /* We want to check the current value of stack[i] to see if
> +        it matches LHS.  If so, then invalidate.  */
> +      if (SSA_NAME_VALUE ((*stack)[i]) == lhs)
> +       record_temporary_equivalence ((*stack)[i], NULL_TREE, stack);
> +
> +      /* Remember, we're dealing with two elements in this case.  */
> +      i--;
> +    }
>
> +  /* And invalidate any known value for LHS itself.  */
>    if (SSA_NAME_VALUE (lhs))
>      record_temporary_equivalence (lhs, NULL_TREE, stack);
>  }
>