llvm dev - Oct 2013 - [LLVMdev] Fwd: Vectorization of pointer PHI nodes

Hi Nadav, Arnold, (now copying LLVM-dev, not commits),

I'm working on an example of a code that current GCC trunk can vectorize
but LLVM cannot, and after analysing the intermediate IR just before the
loop vectorization and by stepping through the process, I can see that the
vectorizer only recognizes integer and float reduction variables, not
pointers.

My code looks like this:

for (i: 0 -> MAX) {
  a = *read;
  b = *read;
  c = *read;

  // do the same stuff to a, b, c

  *write++ = a;
  *write++ = b;
  *write++ = c;
}

Vectorizing this is very simple and it's a sequence of VLD3 + VOPS + VST3,
which GCC does it nicely, but we don't.

What would be the steps in adding a pointer increment reduction kind
(RK_PointerInc)? I believe the logic would be similar to RK_IntegerAdd, but
with a stride of type size, right?

Or maybe we'd have to translate the loop into something like:

for (i: 0 -> MAX, +=3) {
  write[i] = (op) read[i];
  write[i+1] = (op) read[i+1];
  write[i+2] = (op) read[i+2];
}

So that the reduction variable gets recognized?

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

Hi Renato, 

Thanks for working on this.  As you said, we don't support pointer
reductions.  Handling pointer reductions should be straightforward. You can copy
the logic for handling RK_IntegerAdd and create a new enum entry for
RK_PointerAdd.  You will need to detect the relevant patterns (GEP probably) and
implement the cost model and vectorization parts.  You will need to generate
vector-geps that represent the pointer increment. Vector-GEPs are rare and this
may trigger bugs in other parts of the compiler (Vector GEPs usually live
between the vectorizer, which is a very late pass, until SelectionDAG builder).
I wonder if this pattern is common. Usually before I add new features to the
vectorizer I write code that does an “fprintf” into a file every time I detect
the pattern that I want to optimize.  Next, I run the LLVM test suite and look
at the C files that triggered the patterns. This helps in estimating the
profitability of the optimization and also to find additional interesting cases.

Thanks,
Nadav



On Oct 14, 2013, at 9:29 AM, Renato Golin <renato.golin at linaro.org>
wrote:
> Hi Nadav, Arnold, (now copying LLVM-dev, not commits),
> 
> I'm working on an example of a code that current GCC trunk can
vectorize but LLVM cannot, and after analysing the intermediate IR just before
the loop vectorization and by stepping through the process, I can see that the
vectorizer only recognizes integer and float reduction variables, not pointers.
> 
> My code looks like this:
> 
> for (i: 0 -> MAX) {
>   a = *read;
>   b = *read;
>   c = *read;
> 
>   // do the same stuff to a, b, c
> 
>   *write++ = a;
>   *write++ = b;
>   *write++ = c;
> }
> 
> Vectorizing this is very simple and it's a sequence of VLD3 + VOPS +
VST3, which GCC does it nicely, but we don't.
> 
> What would be the steps in adding a pointer increment reduction kind
(RK_PointerInc)? I believe the logic would be similar to RK_IntegerAdd, but with
a stride of type size, right?
> 
> Or maybe we'd have to translate the loop into something like:
> 
> for (i: 0 -> MAX, +=3) {
>   write[i] = (op) read[i];
>   write[i+1] = (op) read[i+1];
>   write[i+2] = (op) read[i+2];
> }
> 
> So that the reduction variable gets recognized?
> 
> cheers,
> --renato
>

On 14 October 2013 17:44, Nadav Rotem <nrotem at apple.com> wrote:
> Thanks for working on this.  As you said, we don't support pointer
> reductions.  Handling pointer reductions should be straightforward. You can
> copy the logic for handling RK_IntegerAdd and create a new enum entry for
> RK_PointerAdd.

Hi Nadav,

Thanks for the pointers, it's good to see that I wasn't too far away in
the
wrong direction. ;)


You will need to detect the relevant patterns (GEP probably) and
implement
> the cost model and vectorization parts.

There are at least two patterns that I wish to implement: multiple pointers
(previous example) and single pointer, like this:

for () {
  a = *read;
  ...
  *write = a;
}

They'll end up as the same type of vectorization, but the former only works
if the operations on all inputs are identical (which is my case) and will
most likely leave empty lanes in the vectors. But the second is a
traditional vectorization (after loop unrolling) where, by definition, the
operations are the same.

So, because I can have the multiple case, I'll have to check throughout all
operations on all lanes to make sure they're identical, and that might put
some stress on the vectorizer...


You will need to generate vector-geps that represent the pointer
increment.
> Vector-GEPs are rare and this may trigger bugs in other parts of the
> compiler (Vector GEPs usually live between the vectorizer, which is a very
> late pass, until SelectionDAG builder). I wonder if this pattern is common.

I'll pay special attention to them, and will blame you whenever I find a
bug. ;)


Usually before I add new features to the vectorizer I write code that
does
> an “fprintf” into a file every time I detect the pattern that I want to
> optimize.  Next, I run the LLVM test suite and look at the C files that
> triggered the patterns. This helps in estimating the profitability of the
> optimization and also to find additional interesting cases.
>
That is an interesting instrumentation, I'll do that.

Thanks!
--renato
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131014/f3d3682d/attachment.html>

> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu]
> On Behalf Of Renato Golin
> Subject: [LLVMdev] Fwd: Vectorization of pointer PHI nodes
> My code looks like this:
>  a = *read;
>  b = *read;
>  c = *read;
Should we presume you intended to have post-increment operators on the
references to read?

 - Chuck

On 14 October 2013 18:11, Caldarale, Charles R
<Chuck.Caldarale at unisys.com>wrote:
> >  a = *read;
> >  b = *read;
> >  c = *read;
>
> Should we presume you intended to have post-increment operators on the
> references to read?
>
Yes, of course. My bad. ;)

--renato
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131014/5c42f674/attachment.html>