[3/4,v2] Enhance SCEV to follow copies of SSA_NAMEs.

(Previous message: https://gcc.gnu.org/ml/gcc-patches/2015-12/msg02159.html)
On Sat, Dec 26, 2015 at 18:58 PM, Richard Biener <richard.guenther@gmail.com> wrote:

>> I'm not sure whether adding a pass_copy_prop is the right thing here, but since
>> loop-header-copying can create such opportunities, it seems good to take them!
>
> Aww.  I'd rather have general infrastructure (like SCEV) deal with
> those non-propagated copies.
>
> There are likely other missed propagation / folding opportunities
> caused from partial peeling.
>
> Richard.

I take your second point, but I am concerned that this leads to duplication of
copy-propagation code throughout the compiler?

However, this patch does that. Making analyze_initial_condition (alone) follow
copies, is enough to solve my case of missed vectorization of pr65947-2.c;
but I also used the routine in analyze_scalar_evolution_1, as it found copies
to follow in both bootstrap and a significant number of testcases:

c-c++-common/gomp/pr58472.c
gcc.c-torture/execute/20000422-1.c
gcc.c-torture/execute/20041213-2.c
gcc.c-torture/execute/20100430-1.c
gcc.c-torture/execute/pr49712.c
gcc.c-torture/execute/pr58640.c
gcc.dg/Warray-bounds-13.c
gcc.dg/graphite/block-{1,5,6}.c
gcc.dg/graphite/interchange-12.c
gcc.dg/graphite/interchange-mvt.c
gcc.dg/graphite/pr19910.c
gcc.dg/graphite/uns-block-1.c
gcc.dg/loop-unswitch-{2,4}.c
gcc.dg/pr59670.c
gcc.dg/torture/matrix-{1,2,3,4,5,6}.c
gcc.dg/torture/pr24750-1.c
gcc.dg/torture/transpose-{1,2,3,4,5,6}.c

...some of which were resolved to constants.

(Of course, this approach is not as thorough as adding a pass_copy_prop. E.g. it
does *not* enable vectorization of the inlined copy in pr65947-9.c.)

Bootstrapped + check-gcc + check-g++ on ARM, AArch64, x86_64.

gcc/ChangeLog:

	* tree-scalar-evolution.c (follow_copies): New.
	(analyze_initial_condition, analyze_scalar_evolution_1): Call previous.
---
 gcc/tree-scalar-evolution.c | 53 ++++++++++++++++++++++++++++++---------------
 1 file changed, 36 insertions(+), 17 deletions(-)

On Thu, Jan 14, 2016 at 11:29 AM, Alan Lawrence <alan.lawrence@arm.com> wrote:
> (Previous message: https://gcc.gnu.org/ml/gcc-patches/2015-12/msg02159.html)
> On Sat, Dec 26, 2015 at 18:58 PM, Richard Biener <richard.guenther@gmail.com> wrote:
>
>>> I'm not sure whether adding a pass_copy_prop is the right thing here, but since
>>> loop-header-copying can create such opportunities, it seems good to take them!
>>
>> Aww.  I'd rather have general infrastructure (like SCEV) deal with
>> those non-propagated copies.
>>
>> There are likely other missed propagation / folding opportunities
>> caused from partial peeling.
>>
>> Richard.
>
> I take your second point, but I am concerned that this leads to duplication of
> copy-propagation code throughout the compiler?
>
> However, this patch does that. Making analyze_initial_condition (alone) follow
> copies, is enough to solve my case of missed vectorization of pr65947-2.c;
> but I also used the routine in analyze_scalar_evolution_1, as it found copies
> to follow in both bootstrap and a significant number of testcases:
>
> c-c++-common/gomp/pr58472.c
> gcc.c-torture/execute/20000422-1.c
> gcc.c-torture/execute/20041213-2.c
> gcc.c-torture/execute/20100430-1.c
> gcc.c-torture/execute/pr49712.c
> gcc.c-torture/execute/pr58640.c
> gcc.dg/Warray-bounds-13.c
> gcc.dg/graphite/block-{1,5,6}.c
> gcc.dg/graphite/interchange-12.c
> gcc.dg/graphite/interchange-mvt.c
> gcc.dg/graphite/pr19910.c
> gcc.dg/graphite/uns-block-1.c
> gcc.dg/loop-unswitch-{2,4}.c
> gcc.dg/pr59670.c
> gcc.dg/torture/matrix-{1,2,3,4,5,6}.c
> gcc.dg/torture/pr24750-1.c
> gcc.dg/torture/transpose-{1,2,3,4,5,6}.c
>
> ...some of which were resolved to constants.
>
> (Of course, this approach is not as thorough as adding a pass_copy_prop. E.g. it
> does *not* enable vectorization of the inlined copy in pr65947-9.c.)
>
> Bootstrapped + check-gcc + check-g++ on ARM, AArch64, x86_64.
>
> gcc/ChangeLog:
>
>         * tree-scalar-evolution.c (follow_copies): New.
>         (analyze_initial_condition, analyze_scalar_evolution_1): Call previous.
> ---
>  gcc/tree-scalar-evolution.c | 53 ++++++++++++++++++++++++++++++---------------
>  1 file changed, 36 insertions(+), 17 deletions(-)
>
> diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
> index 9b33693..357eb8f 100644
> --- a/gcc/tree-scalar-evolution.c
> +++ b/gcc/tree-scalar-evolution.c
> @@ -1522,6 +1522,37 @@ analyze_evolution_in_loop (gphi *loop_phi_node,
>    return evolution_function;
>  }
>
> +/* While VAR is an SSA_NAME whose definition is a straight copy of another name,
> +   or (perhaps via a degenerate phi) a constant, follows that definition.
> +   Returns the constant, or the earliest SSA_NAME whose definition is neither
> +   constant nor copy.  */
> +
> +static tree
> +follow_copies (tree var)
> +{
> +  while (TREE_CODE (var) == SSA_NAME)
> +    {
> +      gimple *def = SSA_NAME_DEF_STMT (var);
> +      if (gphi *phi = dyn_cast <gphi *> (def))
> +       {
> +         tree rhs = degenerate_phi_result (phi);
> +         /* Don't follow degenerate phi's of SSA_NAMES, that can break
> +            loop-closed SSA form.  */
> +         if (rhs && is_gimple_min_invariant (rhs))
> +           var = rhs;
> +         break;
> +       }
> +      else if (gimple_assign_single_p (def)
> +              && !gimple_vuse (def)

The vuse test is not necessary

> +              && (gimple_assign_rhs_code (def) == SSA_NAME
> +                  || is_gimple_min_invariant (gimple_assign_rhs1 (def))))

and the is_gimple_min_invariant (rhs1) test is not sufficient if you
consider - (-INT_MIN) with -ftrapv for example.

I'd say you should do

  else if (gassign *ass = dyn_cast <gassign *> (def))
    {
       tree_code code = gimple_assign_rhs_code (ass);
       if (code == SSA_NAME
           || CONSTANT_CLASS_P (code))
         var = gimple_assign_rhs1 (ass);
       else
         break;
    }

> +       var = gimple_assign_rhs1 (def);
> +      else
> +       break;
> +    }
> +  return var;
> +}
> +
>  /* Given a loop-phi-node, return the initial conditions of the
>     variable on entry of the loop.  When the CCP has propagated
>     constants into the loop-phi-node, the initial condition is
> @@ -1574,21 +1605,9 @@ analyze_initial_condition (gphi *loop_phi_node)
>    if (init_cond == chrec_not_analyzed_yet)
>      init_cond = chrec_dont_know;
>
> -  /* During early loop unrolling we do not have fully constant propagated IL.
> -     Handle degenerate PHIs here to not miss important unrollings.  */
> -  if (TREE_CODE (init_cond) == SSA_NAME)
> -    {
> -      gimple *def = SSA_NAME_DEF_STMT (init_cond);
> -      if (gphi *phi = dyn_cast <gphi *> (def))
> -       {
> -         tree res = degenerate_phi_result (phi);
> -         if (res != NULL_TREE
> -             /* Only allow invariants here, otherwise we may break
> -                loop-closed SSA form.  */
> -             && is_gimple_min_invariant (res))
> -           init_cond = res;
> -       }
> -    }
> +  /* We may not have fully constant propagated IL.  Handle degenerate PHIs here
> +     to not miss important early loop unrollings.  */
> +  init_cond = follow_copies (init_cond);
>
>    if (dump_file && (dump_flags & TDF_SCEV))
>      {
> @@ -1968,8 +1987,8 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
>    if (bb == NULL
>        || !flow_bb_inside_loop_p (loop, bb))
>      {
> -      /* Keep the symbolic form.  */
> -      res = var;
> +      /* Keep symbolic form, but look through obvious copies for constants.  */

You're also looing for SSA names copied so the comment is sligntly wrong.

Ok with those changes.

Thanks,
Richard.

> +      res = follow_copies (var);
>        goto set_and_end;
>      }
>
> --
> 1.9.1
>