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

Duncan, 

Thanks for the quick review! Here is a short description (design) of where I am
going with this patch:

1. Motivation: Vectors-of-pointers is the first step in supporting
scatter/gather instructions (available in AVX2, for example). I believe that
this feature was requested on the mailing list before. As mentioned by Hal
Finkel earlier today, this feature is desired by autovectorizers as it
simplifies the abstraction. I can also mention the Intel OpenCL Autovectorizer
and ISPC as two other vectorizers which would benefit from this type.

2. The type Vectors-of-pointers is similar to the pointer type, in the sense
that it cannot be bit-casted and it has no size. It supports the following
conversions:
	a. Bitcast to other vector-of-pointers, as long as the element count is the
same.
	b. No other bit-cast operations are allowed.  
3. The type Vectors-of-pointers can be used by the following instructions:
	a. Insertelement/extractelement/shuffle - just like any other vector
	b. Getelementptr - for address calculations, with the restrictions mentioned
below.
	c. Intrinsics - to implement the scatter/gather operations
	d. IntToPtr, PtrToInt - for conversion to vectors of integers [This is not
implemented in this patch].
4. The getelementptr instruction can be used to access structs, which may cause
a problem for vector-geps when accessing different fields. Currently I limit the
use of vector-gep to vectors of pointers with a single index. In the future, I
may add support for more indices if users of the vector-gep would request for
it. Matt Pharr from ISPC also requested support for vectors of arrays, which are
not supported at this point.
5. The getelementptr indices must all be vectors, if the pointer operand is a
vector of pointers.

Regarding your specific comments, Vectors of pointers are a new type in LLVM, so
I believe that any predictable and sensible behavior is acceptable. Much like
pointers, 'getBitWidth' should return zero. In my current patch
bitcasting of one vector pointer to another vector pointer of the same length is
okay, but any other bitcast is invalid. I added an assert to getInteger to
prevent calling 'getInteger' on vectors of pointers. I agree that
IntToPtr and PtrToInt need to be extended in order to support vectors of
pointers and I plan to add this.

Thank you,
Nadav


	


-----Original Message-----
From: llvm-commits-bounces at cs.uiuc.edu [mailto:llvm-commits-bounces at
cs.uiuc.edu] On Behalf Of Duncan Sands
Sent: Wednesday, November 23, 2011 11:36
To: llvm-commits at cs.uiuc.edu
Subject: Re: [llvm-commits] Vectors of Pointers and Vector-GEP

Hi Nadav,
> 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.
one of the issues with vectors-of-pointers is then you can no longer say what
the size of a vector is without target data, since you don't know what the
size
of a pointer is without target data.  Methods like VectorType::getBitWidth will
have to be deleted.  Methods like VectorType::getTruncatedElementVectorType,
VectorType::getExtendedElementVectorType and VectorType::getInteger will need to
either be removed, or changed to take a target data parameter (which is probably
a layering violation, so they would need to be moved elsewhere).  The PtrToInt
and IntToPtr operations will need to be enhanced to work on vectors, and a
bunch of places that bitcast vectors will need to become more careful, in case
they are trying to bitcast between a vector of pointers and a vector of
integers.

Ciao, Duncan.
_______________________________________________
llvm-commits mailing list
llvm-commits at cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
---------------------------------------------------------------------
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.

On Wed, 2011-11-23 at 22:09 +0200, Rotem, Nadav wrote:
> Duncan, 
> 
> Thanks for the quick review! Here is a short description (design) of where
I am going with this patch:
> 
> 1. Motivation: Vectors-of-pointers is the first step in supporting
scatter/gather instructions (available in AVX2, for example). I believe that
this feature was requested on the mailing list before. As mentioned by Hal
Finkel earlier today, this feature is desired by autovectorizers as it
simplifies the abstraction. I can also mention the Intel OpenCL Autovectorizer
and ISPC as two other vectorizers which would benefit from this type.
> 
> 2. The type Vectors-of-pointers is similar to the pointer type, in the
sense that it cannot be bit-casted and it has no size. It supports the following
conversions:
> 	a. Bitcast to other vector-of-pointers, as long as the element count is
the same.
> 	b. No other bit-cast operations are allowed.  
> 3. The type Vectors-of-pointers can be used by the following instructions:
> 	a. Insertelement/extractelement/shuffle - just like any other vector
> 	b. Getelementptr - for address calculations, with the restrictions
mentioned below.
> 	c. Intrinsics - to implement the scatter/gather operations
> 	d. IntToPtr, PtrToInt - for conversion to vectors of integers [This is not
implemented in this patch].
> 4. The getelementptr instruction can be used to access structs, which may
cause a problem for vector-geps when accessing different fields. Currently I
limit the use of vector-gep to vectors of pointers with a single index. In the
future, I may add support for more indices if users of the vector-gep would
request for it. Matt Pharr from ISPC also requested support for vectors of
arrays, which are not supported at this point.
So long as coverage will be incomplete, I request that you add some kind
of utility function that can be called on a type and set of GEP indicies
(or maybe a GEP instruction itself) to determine whether it can be
vectorized.

I think it would be easiest on the user if all GEPs can be vectorized.
The default can just be to break up the vector GEP into some scalar GEPs
and some vector insert/extracts.

Regardless, this feature should really help with vectorization, and I
think it is great that you're implementing it.
> 5. The getelementptr indices must all be vectors, if the pointer operand is
a vector of pointers.
> 
> Regarding your specific comments, Vectors of pointers are a new type in
LLVM, so I believe that any predictable and sensible behavior is acceptable.
Much like pointers, 'getBitWidth' should return zero.
Having getBitWidth return 0 makes sense to me. We'll need to grep the
code and add or change a bunch of if statements, but I think that will
be the case however we do this.

 -Hal 
>  In my current patch bitcasting of one vector pointer to another vector
pointer of the same length is okay, but any other bitcast is invalid. I added an
assert to getInteger to prevent calling 'getInteger' on vectors of
pointers. I agree that IntToPtr and PtrToInt need to be extended in order to
support vectors of pointers and I plan to add this.
> 
> Thank you,
> Nadav
> 
> 
> 	
> 
> 
> -----Original Message-----
> From: llvm-commits-bounces at cs.uiuc.edu [mailto:llvm-commits-bounces at
cs.uiuc.edu] On Behalf Of Duncan Sands
> Sent: Wednesday, November 23, 2011 11:36
> To: llvm-commits at cs.uiuc.edu
> Subject: Re: [llvm-commits] Vectors of Pointers and Vector-GEP
> 
> Hi Nadav,
> 
> > 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.
> 
> one of the issues with vectors-of-pointers is then you can no longer say
what
> the size of a vector is without target data, since you don't know what
the size
> of a pointer is without target data.  Methods like VectorType::getBitWidth
will
> have to be deleted.  Methods like
VectorType::getTruncatedElementVectorType,
> VectorType::getExtendedElementVectorType and VectorType::getInteger will
need to
> either be removed, or changed to take a target data parameter (which is
probably
> a layering violation, so they would need to be moved elsewhere).  The
PtrToInt
> and IntToPtr operations will need to be enhanced to work on vectors, and a
> bunch of places that bitcast vectors will need to become more careful, in
case
> they are trying to bitcast between a vector of pointers and a vector of
> integers.
> 
> Ciao, Duncan.
> _______________________________________________
> llvm-commits mailing list
> llvm-commits at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
> ---------------------------------------------------------------------
> 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:
> Duncan, 
>
> Thanks for the quick review! Here is a short description (design) of
> where I am going with this patch:
Did I miss Duncan's feedback?  It didn't come across to me.

                              -Dave

"Rotem, Nadav" <nadav.rotem at intel.com> writes:
> It went to llvm-commits.
This is a problem.  I can't possibly sort through all of the stuff on
llvm-commits to find design documents like this.

It would be easier if llvm-commits were restricted to, say, commits and
higher-level design and development discussions occurred on, say, -dev.
:)

                                 -Dave

> -----Original Message-----
> From: David A. Greene [mailto:greened at obbligato.org] 
> Sent: Tuesday, November 29, 2011 02:01
> To: Rotem, Nadav
> Cc: Duncan Sands; 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:
>
>> Duncan, 
>>
>> Thanks for the quick review! Here is a short description (design) of
>> where I am going with this patch:
>
> Did I miss Duncan's feedback?  It didn't come across to me.
>
>                               -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.