[tree-ssa] RFC - tree vectorizer

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

Hi,

Here is the first implementation of a basic loop vectorizer, as described
in http://gcc.gnu.org/projects/tree-ssa/vectorization.html. A real patch
will follow shortly - this one is relative to an old tree-ssa snapshot and
also includes bits from an old version of Sebastian's IV evolution
analyzer. But I think it's in a shape that allows people to start to take a
look and comment (please do!).

      A few comments/questions:
As I described in http://gcc.gnu.org/ml/gcc/2003-12/msg00908.html, memory
references are vectorized using a pointer to vector type which is used to
point to the accessed array; e.g., the following scalar code:
      (1a) int a[N] = {0,1,2,3};
      (2a) for (i...) {int x = a[i]; ...} #VUSE a_1
becomes:
      (1b) int a[N] = {0,1,2,3}
      (2b) v4si *ptr = (v4si *)a;
      (3b) for (i...) {v4si vx = *(ptr + 16 * i); ...}
Unfortunately, due to the aliasing semantics in gcc, the compiler marks
reads/writes via 'ptr' as referencing a different alias set than the
reads/writes via 'a[i]' (because they have different types). Therefore,
unless I use -fno-strict-aliasing, the resulting code does not run
correctly (in the example above, the load in (3b) is hoisted before the
stores that initialize array 'a'...). How do I force '*ptr' references into
the same alias set as 'a[i]' references?

Also with respect to the load in (3b) - I wasn't sure what would be the
right way to handle it's vuses. I had an implementation where I "copied"
the vuses from the scalar operation to the vector operation, however (a) I
had to mark the stmt as "unmodify" or else these vuses would be lost, and
(b) in some cases some of these vuses/vdefs are really over conservative,
and it seems that there's no point in continuing to represent dependences
that are not really there. On the other hand, does the following assumption
always hold in tree-ssa: A stmt has a memory reference if and only if it
has vuses/vdefs? If that's true and we want it to continue to hold after
vectorization, then I'll have to somehow create vuses/vdefs. In the current
implementation, stmts like the load in (3b) remain without any vuses.

      Attached below is the code for the vectorizer, consisting of two new
files (tree-vectorizer.c,h), and a diff file (vect_patch) that contains the
following changes (and also bits from the IV analyzer patch...):

      * Makefile.in: new files tree-vectorizer.c,h

      * tree-dump.c: (dump_files): new dump file for the new
vectorization pass.
      * tree.h: (TDI_vect): Same.

      * timevar.def (TV_TREE_VECTORIZATION): support new
vectorization pass.

      * opts.c: (flag_tree_vetorize): new flag to enable/disable the
new vectorization pass.
      * common.opt: Same.
      * toplev.c: Same.
      * flags.h: Same.

      * tree-optimize.c: (optimize_function_tree): invoke the new
vetorization pass.

      * defaults.h: (UNITS_PER_SIMD_WORD): define.
      * config/rs6000/rs6000.h: Same.

      * target-def.h (TARGET_VECTYPE_FOR_SCALAR_TYPE): declare a new
target hook for vectorization.
      * target.h (vectype_for_scalar_type): Same.
      * config/rs6000/rs6000.c: (rs6000_vectype_for_scalar_type):
      implement the above new target hook.

      * tree-flow.h: (struct stmt_ann_d): new field (aux) to allow
recording information per stmt.
      * tree-flow-inline.h: (stmt_info): access function to the
above new field.

      With respect to this last change in tree-flow.h - I added a new field
to stmt_ann in order to record information per stmt during vectorization. I
wanted to add a field similar to the "void *aux" in 'struct loop' for
example, but I guess that won't be possible as it is managed by the ggc?
The other option is to use a stmt ID; since that's currently not available,
I guess I'd have to add an int field and assign IDs myself / use a hash
table. Recommendations?

      Also attached below is a small set of examples of loops that can and
can't be vectorized (tested for correctness on powerpc-apple-darwin6.4).
The vectorizer is fairly limited at the moment, and indeed the next step
will be to relax these restrictions one by one. First however I'll bring it
up to date with the tree-ssa branch, or rather the loop optimizer
sub-branch ( http://gcc.gnu.org/ml/gcc-patches/2003-12/msg01419.html.
Sebastian - were you going to open this sub-branch?).

thanks,
dorit

(See attached file: vect_patch)(See attached file: tree-vectorizer_h)(See
attached file: tree-vectorizer_c) (See attached file: vec_test_SF_c)

Attachment: vect_patch
Description: Binary data

Attachment: tree-vectorizer_h
Description: Binary data

Attachment: tree-vectorizer_c
Description: Binary data

Attachment: vec_test_SF_c
Description: Binary data