llvm dev - Apr 2012 - [LLVMdev] [llvm-commits] Vectors of Pointers and Vector-GEP

Hi Hal!

This is great!   Vector-selects are always profitable compared to scalar
selects. They are even emulated using a few Xor/And/Or instructions on platforms
that don't have a native 'blend' support.

Vector-geps on the other hand are only useful in very specific cases.  Currently
we do not support Load/Store instructions with a pointer-vector operand, so you
need to extract each pointer element prior to loading and storing.
X86 supports a complex addressing modes which means that most GEPs are included
in the load/store instruction and they cost nothing. So, performing vector-gep
on these instructions would actually be slower. Vector-geps are only useful if
your hardware supports scatter/gather using a vector of pointers/indices.  For
example AVX2 has support for the 'gather' instruction which receives a
vector of indices.  In many cases it is possible to lower vector-gep
instructions into a gather instruction, but this is currently not supported by
LLVM.

Thanks,
Nadav


 
-----Original Message-----
From: Hal Finkel [mailto:hfinkel at anl.gov] 
Sent: Saturday, April 14, 2012 11:02
To: Rotem, Nadav
Cc: David A. Greene; Jose Fonseca; LLVM Developers Mailing List
Subject: Re: [LLVMdev] [llvm-commits] Vectors of Pointers and Vector-GEP

On Tue, 6 Dec 2011 09:19:43 +0200
"Rotem, Nadav" <nadav.rotem at intel.com> wrote:
> Hi,
> 
> I just wanted to let you know that I committed the pointer-vector 
> patch.
Nadav,

I just committed a change to BBVectorizer to allow it to generate these (and
also vector selects) [>= r154735]. If you have cases where you think these
should be generated, and they're now not generated by the vectorizer, please
let me know.

Thanks again,
Hal
> 
> Thanks,
> Nadav
> 
> -----Original Message-----
> From: David A. Greene [mailto:greened at obbligato.org]
> Sent: Tuesday, December 06, 2011 00:10
> To: Jose Fonseca
> Cc: David A. Greene; Rotem, Nadav; LLVM Developers Mailing List
> Subject: Re: [LLVMdev] [llvm-commits] Vectors of Pointers and 
> Vector-GEP
> 
> Jose Fonseca <jfonseca at vmware.com> writes:
> 
> > I was referring to gathering a vector of sparse 32bit words, all 
> > relative from a base scalar pointer in a 64bit address space, where 
> > the offsets are in a 32bit integer vector.  My other reply gave a 
> > more detailed and concrete example.
> 
> Yep, I saw that.  I think LLVM IR should support it directly.
> 
> > Anyway, from Nadav's and your other replies on this thread it is
now
> > clear to me that even if the IR doesn't express base scalar
pointers
> > w/ vector indices directly, the backend can always match and emit 
> > the most efficient machine instruction. This addresses my main 
> > concern.
> 
> It can, but it would have to go through varying amounts of pain to do 
> so.  This is such a common operation that the IR should really support 
> it directly.
> 
>                            -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.
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


--
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory
---------------------------------------------------------------------
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 Sun, 15 Apr 2012 20:02:36 +0000
"Rotem, Nadav" <nadav.rotem at intel.com> wrote:
> Hi Hal!
> 
> This is great!   Vector-selects are always profitable compared to
> scalar selects. They are even emulated using a few Xor/And/Or
> instructions on platforms that don't have a native 'blend'
support.
> 
> Vector-geps on the other hand are only useful in very specific
> cases.  Currently we do not support Load/Store instructions with a
> pointer-vector operand, so you need to extract each pointer element
> prior to loading and storing. X86 supports a complex addressing modes
> which means that most GEPs are included in the load/store instruction
> and they cost nothing. So, performing vector-gep on these
> instructions would actually be slower. Vector-geps are only useful if
> your hardware supports scatter/gather using a vector of
> pointers/indices.  For example AVX2 has support for the 'gather'
> instruction which receives a vector of indices.  In many cases it is
> possible to lower vector-gep instructions into a gather instruction,
> but this is currently not supported by LLVM. 
At the moment, the only cases where I've seen these vectorized in the
current implementation is where some vectorizable integer calculation
was done and then converted into pointers used by GEPs. I am not sure
how common this is in real code.

Do you think we should also add vector scatter/gather loads and stores?

 -Hal
> 
> Thanks,
> Nadav
> 
> 
>  
> -----Original Message-----
> From: Hal Finkel [mailto:hfinkel at anl.gov] 
> Sent: Saturday, April 14, 2012 11:02
> To: Rotem, Nadav
> Cc: David A. Greene; Jose Fonseca; LLVM Developers Mailing List
> Subject: Re: [LLVMdev] [llvm-commits] Vectors of Pointers and
> Vector-GEP
> 
> On Tue, 6 Dec 2011 09:19:43 +0200
> "Rotem, Nadav" <nadav.rotem at intel.com> wrote:
> 
> > Hi,
> > 
> > I just wanted to let you know that I committed the pointer-vector 
> > patch.
> 
> Nadav,
> 
> I just committed a change to BBVectorizer to allow it to generate
> these (and also vector selects) [>= r154735]. If you have cases where
> you think these should be generated, and they're now not generated by
> the vectorizer, please let me know.
> 
> Thanks again,
> Hal
> 
> > 
> > Thanks,
> > Nadav
> > 
> > -----Original Message-----
> > From: David A. Greene [mailto:greened at obbligato.org]
> > Sent: Tuesday, December 06, 2011 00:10
> > To: Jose Fonseca
> > Cc: David A. Greene; Rotem, Nadav; LLVM Developers Mailing List
> > Subject: Re: [LLVMdev] [llvm-commits] Vectors of Pointers and 
> > Vector-GEP
> > 
> > Jose Fonseca <jfonseca at vmware.com> writes:
> > 
> > > I was referring to gathering a vector of sparse 32bit words, all 
> > > relative from a base scalar pointer in a 64bit address space,
> > > where the offsets are in a 32bit integer vector.  My other reply
> > > gave a more detailed and concrete example.
> > 
> > Yep, I saw that.  I think LLVM IR should support it directly.
> > 
> > > Anyway, from Nadav's and your other replies on this thread it
is
> > > now clear to me that even if the IR doesn't express base
scalar
> > > pointers w/ vector indices directly, the backend can always match
> > > and emit the most efficient machine instruction. This addresses
> > > my main concern.
> > 
> > It can, but it would have to go through varying amounts of pain to
> > do so.  This is such a common operation that the IR should really
> > support it directly.
> > 
> >                            -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.
> > 
> > 
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
> 
> --
> Hal Finkel
> Postdoctoral Appointee
> Leadership Computing Facility
> Argonne National Laboratory
> ---------------------------------------------------------------------
> 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.
> 


-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

Hal Finkel <hfinkel at anl.gov> writes:
>> Vector-geps on the other hand are only useful in very specific
>> cases.
> At the moment, the only cases where I've seen these vectorized in the
> current implementation is where some vectorizable integer calculation
> was done and then converted into pointers used by GEPs. I am not sure
> how common this is in real code.
It is quite common in HPC codes.  It gets used for loops like this:

   for(...) {
     a[i] = b[x[i]] + c[y[i]];
   }
> Do you think we should also add vector scatter/gather loads and stores?
I'm not sure about this.  Intrisics might be good enough.  The question
comes down to how much the LLVM optimizer needs to know about them.
Alias and dependence analysis can often figure quite a bit out if they
try hard enough but that would require native IR instructions, I think.

In addition, I suspect more and more architectures are going to start
supporting G/S so a generic instruction would make the IR more portable
and we wouldn't have to reinvent the wheel for each target.

                                 -Dave