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

[Victor Kaplansky <VICTORK at il dot ibm dot com>]

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.

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

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

3. The patch adds DCE pass before vectorizer in order to clean-up some dead
phi nodes
which may cause vectorizer inability to perform loop-peeling.

Bootstrapped and tested on powerpc-linux.
Committed to autovect-branch.

-- Victor

2006-06-14  Victor Kaplansky   <victork@il.ibm.com>

        * gcc/tree-scalar-evolution.c (number_of_iterations_in_loop):
        changed to be wrapper of number_of_iterations_in_loop_1
        (number_of_iterations_in_loop_1): New. Same as previous
        number_of_iterations_in_loop, but takes new argument may_be_zero.
        * gcc/tree-scalar-evolution.h (number_of_iterations_in_loop_1): New
        prototype.
        * gcc/tree-ssa-loop-ivopts.c (expr_invariant_in_loop_p): return
true
        for DECL expressions.
        * gcc/tree-vect-analyze.c (vect_get_loop_niters): call to
        number_of_iterations_in_loop_1 instead of
number_of_iterations_in_loop.
        * gcc/passes.c (init_optimization_passes): call to dce before
        vectorizer.
(See attached file: patch.txt)

Attachment: patch.txt
Description: Text document