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

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.

"Rotem, Nadav" <nadav.rotem at intel.com> writes:
> 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.
Ah, I see.  I actually think multiple indices as in multiple vectors of
indices to the GEP above would be pretty rare.

                             -Dave

I agree that a single vector index is sufficient for many cases. Matt Pharr
(from the ISPC compiler), showed me an interesting case where there is a single
pointer into an array. In this case we need to have two indices, where the first
index is zero. Once the basic patch is in, we can start looking at adding
support for arrays and multiple indices.

Nadav

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

"Rotem, Nadav" <nadav.rotem at intel.com> writes:
> 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.
Ah, I see.  I actually think multiple indices as in multiple vectors of
indices to the GEP above would be pretty rare.

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

----- Original Message -----
> "Rotem, Nadav" <nadav.rotem at intel.com> writes:
> 
> > 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.
> 
> Ah, I see.  I actually think multiple indices as in multiple vectors
> of
> indices to the GEP above would be pretty rare.
Nadav, David, 

I'd like to understand a bit better the final role of these pointer vector
types in 64bit architectures, where the pointers are often bigger than the
elements stored/fetch (e.g, 32bits floats/ints).

Will 64bits backends be forced to actually operate with 64bit pointer vectors
all the time? Or will they be able to retain operations on base + 32bit offsets
as such?

In particular, an important use case for 3D software rendering is to be able to
gather <4 x i32> values, from a i32* scalar base pointer in a 64bit
address space, indexed by <N x i32> offsets. [1]  And it is important that
the intermediate <N x i32*> pointer vectors is actually never instanced,
as it wouldn't fit in the hardware SIMD registers, and therefore would
require two gather operations.

It would be nice to see how this use case would look in the proposed IR, and get
assurance that backends will be able to emit efficient code (i.e., a single
gather instruction) from that IR.

Jose

[1] http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-June/040825.html