[LLVMdev] First attempt at recognizing pointer reduction

[Renato Golin]

On 23 October 2013 23:05, Arnold Schwaighofer <aschwaighofer at apple.com>wrote:

> A reduction is something like:
>
> for (i= …) {
>  r+= a[i];
> }
> return r;
>

Ok, so "reduction" is just a reduction in the map-reduce sense, and nothing
else.


You don’t need to transform them in the legality phase. Believe me ;). Look
> at how we handle stride one pointer inductions at the moment (they are also
> memory phis) - they are based off a canonical induction variable that we
> create during the actual vectorization. Everything before that is done
> virtually without having to transform code until we actually know we want
> to vectorize it.
>

Oh, so that's what I was missing. When Nadav said about pointer reduction,
I thought that was how we were should be dealing with memory PHIs in the
end. I'll see how stride 1 pointer induction traverses the code and where
to add stride N (but not sooner than I try to teach strides to non-pointer
cases).

I'll also add the reduction case, like:

for (i .. N/3) {
  r += a[3*i] ..;
  r += a[3*i+1] ..;
  r += a[3*i+2] ..;
}
return r;

And see how it should work. (later, too).


Basically for pointer inductions we store the start value. When we come to
> actually vectorize the loop we create a canonical induction variable that
> starts at zero and strides by the vector factor (VF). Any use of the
> original pointer induction variable in the vectorized loop is simply:
>

Thanks, I'll have a look (again). ;)

I'll open some Bugzilla bugs and assign to me, one for each type of loop to
be vectorized, in sequence (depends on) and using some of the test we
discussed in the mailing list. That way, we'll be able to agree on the
order and implementation beforehand. Feel free to share them with me if you
have time in the interim, I'll mainly be two weeks away from now (Connect,
holidays, LLVM meeting).

So far, we have covered:

1. simple stride: for (N/3) { a[3*i] = b[3*i]; a[3*i+1] = b[3*i+1];
a[3*i+2] = b[3*i+2]; }
 * The simplest form, needs only basic checks & vectorization logic

2. re-rolling possible: for (N/3) { a[3*i] = b[3*i] + K; a[3*i+1] =
b[3*i+1] + K; a[3*i+2] = b[3*i+2] + K; }
 * can be re-rolled for simple optimization (already implemented)
 * doesn't need interleaved data, even if vectorized directly via stride
access

3. re-rolling impossible: for (N/3) { a[3*i] = b[3*i] + I; a[3*i+1] =
b[3*i+1] + J; a[3*i+2] = b[3*i+2] + K; }
 * can't be re-rolled and does need interleaved data access

4. reduction stride: for (N/3) { a += b[3*i]; a += b[3*i+1]; a += b[3*i+2];
} return a;
 * May work with case above implemented, may need additional reduction logic
 * can be any of the three types above

5. memory stride: for (N/3) { a++ = b++; a++ = b++; a++ = b++; }
 * should be transformed into one of the cases above first, than vectorized
as them
 * can be any of the three types above (1, 2, 3)

With the dependency being:

1 -> { 2, 3} -> {4, 5}

cheers,
--renato
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131024/41e81dc6/attachment.html>