[LLVMdev] First attempt at recognizing pointer reduction

[Arnold Schwaighofer]

On Oct 24, 2013, at 2:40 AM, Renato Golin <renato.golin at linaro.org> wrote:

> 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.

Yes.
>  
> 
> 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).

See you at the dev meeting then.

> 
> 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

Yes I think this is what we should start with. This is similar to 3. (4 should just fall off).
> 
> 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)

This will need support for non-unit stride  pointer inductions.
> 
> With the dependency being:
> 
> 1 -> { 2, 3} -> {4, 5}

Yep.
> 
> cheers,
> --renato