[autovect] [patch] vectorize in cases when number of iterations may be zero

[Zdenek Dvorak]

Hello,

> 1. Sometimes scev analysis cannot resolve unambiguously if loop is executed
> at all.
> For example:
> 
>       1 int
>       2 foo (short *in, short *out)
>       3 {
>       4   unsigned i;
>       5   unsigned N;
>       6   unsigned M;
>       7   int acc;
>       8
>       9   for (N = 0; N < 16; N++)
>      10     {
>      11       M = 500 - N;
>      12
>      13       acc = 0;
>      14
>      15       for (i = 0; i < M; i++)
>      16         {
>      17           acc += in[i + M];
>      18         }
>      19
>      20       out[N] = (short) acc;
>      21     }
>      22
>      23   return acc;
>      24 }
> 
> number_of_iterations_in_loop returns chrec_dont_know for the loop at
> line:15.
> The only reason is that according to SCEV analysis it's possible that loop
> will
> be executed 0 times. In this case we still want to vectorize the loop.

when loop header is copied, this should not be the case -- it should be
possible to determine that the loop is executed at least once.  Looking
at the dumps, the problem is that VRP determines that M cannot be 0, and
thus the copied loop header is removed.  What should be done here is to
make us preserve the information about value ranges of ssa names, and to
use them in expression simplification.  But anyway, I suppose there are
cases where it is useful to vetorize the loop even if it is not possible
to determine that the loop rolls at least once.

> The patch below, changes the behavior of number_of_iterations_in_loop,
> when it is called from vectorizer.

Why do you create a new wrapper for this, instead of just using
number_of_iterations_exit directly (which would give you the same
information)?

> 2. The patch makes expr_invariant_in_loop_p to consider DECL expressions to
> consider as loop-invariant.

> Index: gcc/tree-ssa-loop-ivopts.c
> ===================================================================
> --- gcc/tree-ssa-loop-ivopts.c	(revision 114653)
> +++ gcc/tree-ssa-loop-ivopts.c	(working copy)
> @@ -1372,6 +1372,9 @@ expr_invariant_in_loop_p (struct loop *l
>    if (is_gimple_min_invariant (expr))
>      return true;
>  
> +  if (DECL_P (expr))
> +    return true;
> +
>    if (TREE_CODE (expr) == SSA_NAME)
>      {
>        def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));


This is definitely wrong.  expr_invariant_in_loop_p cannot know that the
decl is not changed in the loop (in fact, if it were not changed in the
loop, load motion would move it out of the loop before, so you would
never get it as an argument of expr_invariant_in_loop_p).  I also do not
see why you need this change in the example you mention.

Zdenek