[PATCH] [4.3 projects] vectorization of induction

[Dorit Nuzman <DORIT at il dot ibm dot com>]

This adds support for vectorization of induction - e.g.:
       for (i=0; i<N; i++)
         a[i] = i;

When a stmt to be vectorized has a use that is defined by a loop-header-phi
which had been recognized in advance as defining an induction computation,
we call 'get_initial_def_for_induction' to generate vector instructions
that initialize the vector of ivs and bump it in the loop:

     loop prolog:
         vec_init = [X, X+S, X+2*S, X+3*S]
         vec_step = [VF*S, VF*S, VF*S, VF*S]
     loop:
         vec_iv = PHI <vec_init, vec_loop>
         ...
         STMT
         ...
         vec_loop = vec_iv + vec_step;


(where X is the initial condition of the induction, S is the step of the
induction, and VF is the vectorization factor - 4 in the example).

So most of the new logic is in 'get_initial_def_for_induction' (which also
takes care of induction in a loop that has multiple data types). Other bits
that this patch includes:
- Support reduction with an induction as one of its arguments - e.g.: 'for
(i..) sum += i;' For this
purpose we now first detect all induction phis in
'vect_analyze_scalar_cycles', and only then
detect reductions (instead of doing it together in one pass).
- Just for debugging purposes, to allow testing how reduction works with
induction (i.e. the above testcase), I added a flag that lets me disable
scev-cprop pass (it's on by default) cause otherwise it optimizes away such
loop (and rightfully so, but I still want to test the above).
- A few minor formatting fixes.

Bootstrapped and tested on the vectorizer testcases on powerpc-linux.
Bootstrapped with vectorization enabled and tested on the vectorizer
testcases on i386-linux.
Full makecheck in progress.

ok to commit once testing completes?

:ADDPATCH vectorizer (ssa, loops):

thanks,
dorit

ChangeLog:
2006-12-31  Dorit Nuzman  <dorit@il.ibm.com>
            Victor Kaplansky  <victork@il.ibm.com>

        * tree-vectorizer.c (vect_is_simple_use): Support induction.
        (vect_is_simple_reduction): Support reduction with induction as
        one of the operands.
        (vect_is_simple_iv_evolution): Fix formatting.
        * tree-vect-analyze.c (vect_mark_stmts_to_be_vectorized): Fix
        formatting.  Don't mark induction phis for vectorization.
        (vect_analyze_scalar_cycles): Analyze all inductions, then
reductions.
        * tree-vect-transform.c (get_initial_def_for_induction): New
function.
        (vect_get_vec_def_for_operand): Support induction.
        (vect_get_vec_def_for_stmt_copy): Fix formatting and add check for
        induction case.
        (vectorizable_reduction): Support reduction with induction as one
of
        the operands.
        (vectorizable_type_demotion): Use def-type of stmt argument rather
        than dummy def-type.

        * tree-ssa-loop.c (gate_scev_const_prop): Return the value of
        flag_tree_scev_cprop.
        * common.opt (tree-scev-cprop): New flag.

        * tree-vect-transform.c (vect_create_destination_var): Use 'kind'
in
        call to vect_get_new_vect_var.


testsuite/ChangeLog:
2006-12-31  Dorit Nuzman  <dorit@il.ibm.com>

        * gcc.dg/vect/vect.exp: Add support for -fno-tree-scev-cprop tests.
        * gcc.dg/vect/vect-iv-1.c: New test.
        * gcc.dg/vect/vect-iv-2.c: New test.
        * gcc.dg/vect/vect-iv-3.c: New test.
        * gcc.dg/vect/vect-iv-4.c: New test.
        * gcc.dg/vect/vect-iv-5.c: New test.
        * gcc.dg/vect/vect-iv-6.c: New test.
        * gcc.dg/vect/vect-iv-7.c: New test.
        * gcc.dg/vect/vect-iv-8.c: New test.
        * gcc.dg/vect/vect-iv-9.c: New test.
        * gcc.dg/vect/vect-iv-10.c: New test.
        * gcc.dg/vect/vect-iv-11.c: New test.
        * gcc.dg/vect/no-tree-scev-cprop-vect-iv-1.c: New test.
        * gcc.dg/vect/no-tree-scev-cprop-vect-iv-2.c: New test.
        * gcc.dg/vect/vect-14.c: Now vectorizable.
        * gcc.dg/vect/pr21591.c: Additional loop vectorized (initilization
loop).
        * gcc.dg/vect/vect-27.c: Likewise.
        * gcc.dg/vect/vect-29.c Likewise.
        * gcc.dg/vect/vect-dv-2.c: Likewise.
        * gcc.dg/vect/vect-reduc-dot-u16a.c: Likewise.
        * gcc.dg/vect/vect-reduc-dot-u16b.c: Likewise.
        * gcc.dg/vect/vect-widen-mult-u16.c: Likewise.

Patch:
(See attached file: induction.txt)

Attachment: induction.txt
Description: Text document