r238205 - in /branches/unified-autovect/gcc: Ch...

[sameerad@gcc.gnu.org]

Author: sameerad
Date: Mon Jul 11 08:01:08 2016
New Revision: 238205

URL: https://gcc.gnu.org/viewcvs?rev=238205&root=gcc&view=rev
Log:
Add new pass to perform autovectorization using unified representation - Current
GCC framework does not give complete overview of the loop to be vectorized : it
either breaks the loop across body, or across iterations. Because of which these
data structures can not be reused for our approach which gathers all the
information of loop body at one place using primitive permute operations. Hence,
define new data structures and populate them.

Add support for vectorization of LOAD/STORE instructions
    a. Create permute order tree for the loop with LOAD and STORE instructions
for single or multi-dimensional arrays, aggregates within nested loops.

This change adds new pass to perform autovectorization using unified
representation, defines new data structures to cater to this requirement and
creates primitive reorder tree for LOAD/STORE instructions within the loop.

The whole loop is represented using the ITER_NODE, which have information about
- The preparatory statements for vectorization to be executed before entering
  the loop (like initialization of vectors, prepping for reduction operations,
peeling etc.)
- Vectorizable loop body represented as PRIMOP_TREE (primitive reordering tree)
- Final statements (For peeling, variable loop bound, COLLAPSE operation for
  reduction etc.)
- Other loop attributes (loop bound, peeling needed, dependences, etc.)

Memory accesses within a loop have definite repetitive pattern which can be
captured using primitive permute operators which can be used to  determine
desired permute order for the vector computations.  The PRIMOP_TREE is AST which
records all computations and permutations required to store  destination vector
into continuous memory at the end of all iterations of the  loop. It can have
INTERLEAVE, CONCAT, EXTRACT, SPLIT, ITER or any compute operation as
intermediate node. Leaf nodes can either be memory reference, constant or vector
of loop invariants. Depending upon the operation, PRIMOP_TREE holds appropriate
information about the statement within the loop which is necessary for
vectorization.

At this stage, these data structures are populated by gathering all the
information of the loop, statements within the loop and correlation of the
statements within the loop. Moreover the loop body is analyzed to check if
vectorization of each statement is possible. One has to note however that this
analysis phase will give worst-case estimate of instruction selection, as it
checks if specific named pattern is defined in .md for the target. It not
necessarily  give optimal cover which is aim of the transformation phase using
tree tiling algorithm - and can be invoked only once the loop body is
represented using primitive reoder tree.

At this stage, the focus is to create permute order tree for the loop with LOAD
and STORE instructions only. The code we intend to compile is of the form
FOR(i = 0; i < N; i + +)
{
  stmt 1 : D[k ∗ i + d 1 ] =S 1 [k ∗ i + c 11 ]
  stmt 2 : D[k ∗ i + d 2 ] =S 1 [k ∗ i + c 21 ]
  ...
  stmt k : D[k ∗ i + d k ] =S 1 [k ∗ i + c k 1 ]
}
Here we are assuming that any data reference can be represented using base + k *
index + offset (The data structure struct data_reference from GCC is used
currently for this purpose). If not, the address is normalized to convert to
such representation.

Added:
    branches/unified-autovect/gcc/tree-vect-unified.c
    branches/unified-autovect/gcc/tree-vect-unified.h
Modified:
    branches/unified-autovect/gcc/ChangeLog
    branches/unified-autovect/gcc/Makefile.in
    branches/unified-autovect/gcc/common.opt
    branches/unified-autovect/gcc/hsa.c
    branches/unified-autovect/gcc/passes.def
    branches/unified-autovect/gcc/tree-data-ref.h
    branches/unified-autovect/gcc/tree-pass.h
    branches/unified-autovect/gcc/tree-ssa-loop.c
    branches/unified-autovect/gcc/tree-vect-data-refs.c
    branches/unified-autovect/gcc/tree-vect-loop.c
    branches/unified-autovect/gcc/tree-vectorizer.c
    branches/unified-autovect/gcc/tree-vectorizer.h