SLP-based reduction vectorization

[Anton Youdkevitch]

Here is the prototype for doing vectorized reduction
using SLP approach. I would appreciate feedback if this
is a feasible approach and if overall the direction is
right.

The idea is to vectorize reduction like this

S = A[0]+A[1]+...A[N];

into

Sv = Av[0]+Av[1]+...+Av[N/VL];


So that, for instance, the following code:

typedef double T;
T sum;

void foo (T*  __restrict__ a)
{
        sum = a[0]+ a[1] + a[2]+ a[3] + a[4]+ a[5] + a[6]+ a[7];
}


instead of:

foo:
.LFB23:
        .cfi_startproc
        movsd   (%rdi), %xmm0
        movsd   16(%rdi), %xmm1
        addsd   8(%rdi), %xmm0
        addsd   24(%rdi), %xmm1
        addsd   %xmm1, %xmm0
        movsd   32(%rdi), %xmm1
        addsd   40(%rdi), %xmm1
        addsd   %xmm1, %xmm0
        movsd   48(%rdi), %xmm1
        addsd   56(%rdi), %xmm1
        addsd   %xmm1, %xmm0
        movsd   %xmm0, sum2(%rip)
        ret
        .cfi_endproc


be compiled into:

foo:
.LFB11:
        .cfi_startproc
        movupd  32(%rdi), %xmm0
        movupd  48(%rdi), %xmm3
        movupd  (%rdi), %xmm1
        movupd  16(%rdi), %xmm2
        addpd   %xmm3, %xmm0
        addpd   %xmm2, %xmm1
        addpd   %xmm1, %xmm0
        haddpd  %xmm0, %xmm0
        movlpd  %xmm0, sum(%rip)
        ret
        .cfi_endproc


As this is a very crude prototype there are some things
to consider.

1. As the current SLP framework assumes presence of
group stores I cannot use directly it as reduction
does not require group stores (or even stores at all),
so, I'm partially using the existing functionality but
sometimes I have to create a stripped down version
of it for my own needs;

2. The current version considers only PLUS reduction
as it is encountered most often and therefore is the
most practical;

3. While normally SLP transformation should operate
inside single basic block this requirement greatly
restricts it's practical application as in a code
complex enough there will be vectorizable subexpressions
defined in basic block(s) different from that where the
reduction result resides. However, for the sake of
simplicity only single uses in the same block are
considered now;

4. For the same sake the current version does not deal
with partial reductions which would require partial sum
merging and careful removal of the scalars that participate
in the vector part. The latter gets done automatically
by DCE in the case of full reduction vectorization;

5. There is no cost model yet for the reasons mentioned
in the paragraphs 3 and 4.

Thanks in advance.

-- 
  Anton
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-WIP-BB-only-SLP-reduction.patch
Type: text/x-diff
Size: 9526 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20190121/c5885318/attachment.bin>