[patch] Vectorize nested cycles

[Ira Rosen]

Hi,

This patch distinguishes between inner-most loop reductions and nested
cycles (i.e., cycles in the inner loop when vectorizing the outer loop).
The most important difference is that in the later case the vectorizer does
not change the order of computation, and, therefore, the usual restrictions
that we have for reduction vectorization can be relaxed (e.g.,
associativity and commutativity).

Bootstrapped with vectorization enabled on powerpc64-suse-linux and
regtested on x86_64-suse-linux.
Committed revision 148518.

Ira

ChangeLog:

      * tree-parloops.c (loop_parallel_p): Call vect_is_simple_reduction
      with additional parameter.
      * tree-vectorizer.h (enum vect_def_type): Add new value
      vect_nested_cycle.
      (enum vect_relevant): Add comments.
      (vect_is_simple_reduction): Add new argument.
      * tree-vect-loop.c (vect_analyze_scalar_cycles_1): Add comments.
      Detect nested cycles.
      (vect_is_simple_reduction): Update documentation, add an argument to
      distinguish inner-loop reduction from nested cycle, detect nested
      cycles, fix printings and indentation, don't swap operands in case
      of nested cycle.
      (get_initial_def_for_reduction): Handle subtraction.
      (vect_create_epilog_for_reduction): Add new argument to specify
      reduction variable.
      (vect_finalize_reduction): Handle subtraction, fix comments.
      (vectorizable_reduction): Handle nested cycles. In case of nested
cycle
      keep track of the reduction variable position. Call
      vect_is_simple_reduction with additional parameter. Use original
      statement code in reduction epilogue for nested cycle. Call
      vect_create_epilog_for_reduction with additional parameter.
      * tree-vect-patterns.c (vect_recog_dot_prod_pattern): Assert
inner-loop
      vectorization.
      (vect_recog_widen_sum_pattern): Likewise.
      * tree-vect-stmts.c (process_use): Distinguish between nested cycles
      and reductions.
      (vect_mark_stmts_to_be_vectorized): Likewise.
      (vect_get_vec_def_for_operand): Handle nested cycles.

testsuite/ChangeLog:

      * gcc.dg/vect/vect-outer-4g.c: Don't look for pattern not allowed
      printing.
      * gcc.dg/vect/vect-outer-4k.c, gcc.dg/vect/vect-outer-4l.c,
      gcc.dg/vect/vect-outer-4f.c: Likewise.
      * gcc.dg/vect/vect-nest-cycle-1.c: New test.
      * gcc.dg/vect/vect-nest-cycle-2.c, gcc.dg/vect/vect-nest-cycle-3.c:
      Likewise.
      * gcc.dg/vect/vect-outer-1a.c: Fail because of strided access in
outer
      loop.

(See attached file: nested-cycles.txt)
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: nested-cycles.txt
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20090616/834e1e15/attachment.txt>