llvm dev - Nov 2011 - [LLVMdev] Vectors of Pointers and Vector-GEP

Hi,

Following the discussion in last week's LLVM developers conference I started
working on support for vectors-of-pointers.  Vectors of pointers are needed for
supporting scatter/gather operations and are the first step in the direction of
supporting predicated architectures.  In the attached patch, I change the
LLVM-IR in order to support vectors-of-pointers and added basic support for
vector-gep.  In following patches I plan to extend the vector-gep support to
more indices and add scatter/gather intrinsics.

I started by implementing vector-gep support for a simple case where there is a
single index.  The reason for this limitation, as noted by Dan Gohman, is that
pointers may point to structs, and vectors of indices may point to different
members in the struct. I am aware of the fact that supporting multiple indices
is an important feature and I do intend to add support for multiple indices in
the future.

Please review the attached patch.

Thanks,
Nadav
---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111123/fe164964/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: vector_gep.patch
Type: application/octet-stream
Size: 14203 bytes
Desc: vector_gep.patch
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111123/fe164964/attachment.obj>

On Wed, 2011-11-23 at 11:18 +0200, Rotem, Nadav wrote:
> Hi, 
> 
>  
> 
> Following the discussion in last week’s LLVM developers conference I
> started working on support for vectors-of-pointers.  Vectors of
> pointers are needed for supporting scatter/gather operations and are
> the first step in the direction of supporting predicated
> architectures.  
This is also important for vanilla (auto-)vectorization. At least in the
context of my basic-block autovectorizer, the fact that there is no
vector GEP results in a lot of missed vectorization opportunities.

 -Hal
> In the attached patch, I change the LLVM-IR in order to support
> vectors-of-pointers and added basic support for vector-gep.  In
> following patches I plan to extend the vector-gep support to more
> indices and add scatter/gather intrinsics. 
> 
>  
> 
> I started by implementing vector-gep support for a simple case where
> there is a single index.  The reason for this limitation, as noted by
> Dan Gohman, is that pointers may point to structs, and vectors of
> indices may point to different members in the struct. I am aware of
> the fact that supporting multiple indices is an important feature and
> I do intend to add support for multiple indices in the future.
> 
>  
> 
> Please review the attached patch. 
> 
>  
> 
> Thanks,
> 
> Nadav
> 
> 
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
> 
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
> _______________________________________________
> llvm-commits mailing list
> llvm-commits at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

"Rotem, Nadav" <nadav.rotem at intel.com> writes:
> Hi,
>
> Following the discussion in last week’s LLVM developers conference I
started working on support for vectors-of-pointers.  Vectors of pointers are
> needed for supporting scatter/gather operations and are the first step in
the direction of supporting predicated architectures.  In the attached
> patch, I change the LLVM-IR in order to support vectors-of-pointers and
added basic support for vector-gep.  In following patches I plan to extend
> the vector-gep support to more indices and add scatter/gather intrinsics.
>
> I started by implementing vector-gep support for a simple case where there
is a single index.  The reason for this limitation, as noted by Dan
> Gohman, is that pointers may point to structs, and vectors of indices may
point to different members in the struct. I am aware of the fact that
> supporting multiple indices is an important feature and I do intend to add
support for multiple indices in the future.
So glad to see this happening!

But I'm unclear about your description.  A vector GEP produces a vector
of pointers, right?  And a scatter/gather operation takes a vector of
pointers as the list of addresses to fetch?

What does the non-unit stride case look like?  I have two ways I think
about a gather/scatter or non-unit stride access.

1. Vector-of-indices

This looks something like:

V1 <- Base + V2

where Base is a base address and V2 is a vector of offsets from the
base.

2. Vector-of-addresses

This looks omsething like:

V1 <- Offset + V2

Where Offset is an offset value applied to each address in V2.

The first form is somewhat more convenient for striding through an array
while the second is somewhat more convenient for doing gather/scatter on
a set of "random" address locations (think operating on a field in
several randomly-allocated structs).

The multiple-index case (if I understand what you mean) is just a
special case of the above, where the values in V2 have been adjusted to
point to the various different fields.

Can you explain with some example what your proposal provides and how it
relates to #1 and #2 above?  I'm just trying to understand the overall
scheme.

Thanks!

                           -Dave

David, 

Thanks for the support! I sent a detailed email with the overall plan. But just
to reiterate, the GEP would look like this:

	%PV = getelementptr <4 x i32*> %base, <4 x i32> <i32 1, i32 2,
i32 3, i32 4>

Where the index of the GEP is a vector of indices. I am not against having
multiple indices. I just want to start with a basic set of features.

Thanks,
Nadav

 


-----Original Message-----
From: David A. Greene [mailto:greened at obbligato.org] 
Sent: Tuesday, November 29, 2011 01:57
To: Rotem, Nadav
Cc: llvm-commits at cs.uiuc.edu; LLVM Developers Mailing List
Subject: Re: [llvm-commits] Vectors of Pointers and Vector-GEP

"Rotem, Nadav" <nadav.rotem at intel.com> writes:
> Hi,
>
> Following the discussion in last week’s LLVM developers conference I
started working on support for vectors-of-pointers.  Vectors of pointers are
> needed for supporting scatter/gather operations and are the first step in
the direction of supporting predicated architectures.  In the attached
> patch, I change the LLVM-IR in order to support vectors-of-pointers and
added basic support for vector-gep.  In following patches I plan to extend
> the vector-gep support to more indices and add scatter/gather intrinsics.
>
> I started by implementing vector-gep support for a simple case where there
is a single index.  The reason for this limitation, as noted by Dan
> Gohman, is that pointers may point to structs, and vectors of indices may
point to different members in the struct. I am aware of the fact that
> supporting multiple indices is an important feature and I do intend to add
support for multiple indices in the future.
So glad to see this happening!

But I'm unclear about your description.  A vector GEP produces a vector
of pointers, right?  And a scatter/gather operation takes a vector of
pointers as the list of addresses to fetch?

What does the non-unit stride case look like?  I have two ways I think
about a gather/scatter or non-unit stride access.

1. Vector-of-indices

This looks something like:

V1 <- Base + V2

where Base is a base address and V2 is a vector of offsets from the
base.

2. Vector-of-addresses

This looks omsething like:

V1 <- Offset + V2

Where Offset is an offset value applied to each address in V2.

The first form is somewhat more convenient for striding through an array
while the second is somewhat more convenient for doing gather/scatter on
a set of "random" address locations (think operating on a field in
several randomly-allocated structs).

The multiple-index case (if I understand what you mean) is just a
special case of the above, where the values in V2 have been adjusted to
point to the various different fields.

Can you explain with some example what your proposal provides and how it
relates to #1 and #2 above?  I'm just trying to understand the overall
scheme.

Thanks!

                           -Dave
---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

greened at obbligato.org (David A. Greene) writes:
> "Rotem, Nadav" <nadav.rotem at intel.com> writes:
>
>> Following the discussion in last week’s LLVM developers conference I
>> started working on support for vectors-of-pointers.  Vectors of
>> pointers are needed for supporting scatter/gather operations and are
>> the first step in the direction of supporting predicated
>> architectures.
I just want to make clear that gather/scatter and prediction are
orthogonal concepts.  You don't need one to do the other.  You can use
scatter/gather to vectorize conditional code but it's not the same as
true predication, which is generally much more efficient.

                               -Dave