[llvm-dev] RFC: std::vector and identified objects

[James Molloy via llvm-dev]

Hi Hal,

> FWIW, this is one of the primary motivators for
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf (which I
need to get back to working on soon). The size is also important
information (but likely not as important as the aliasing in this case - it
is more important if you have conditional accesses and lack hardware
predicated loads/stores).
>
> In this case, where the object is local, I can imagine some smarter IPA
(function attributes or otherwise) helping. I think that, in general, we'll
probably need to provide some attributes that can be used to adorn the
std::vector implementation, translated into some associated intrinsics
and/or metadata, that will allow the backend to compute these various
properties.

I like that proposal. It's dated late 2014 - is it still making progress?

Would it be appropriate to prototype these attributes in clang and teach
libc++ about them? That way we could optimize such idioms better even
before this extension gets accepted into C++.

I'm just trying to scope out the work required before I can get this
workload to be optimized properly (do I "just" have to implement an
extension in clang and the appropriate LLVM extensions/metadata, or do I
have to wait until that proposal proceeds further?)

Cheers,

James

On Fri, 1 Apr 2016 at 17:55 Hal Finkel <hfinkel at anl.gov> wrote:

>
> ------------------------------
>
> *From: *"James Molloy via llvm-dev" <llvm-dev at lists.llvm.org>
> *To: *"LLVM Dev" <llvm-dev at lists.llvm.org>, "Chandler Carruth" <
> chandlerc at google.com>
> *Sent: *Friday, April 1, 2016 2:56:25 AM
> *Subject: *[llvm-dev] RFC: std::vector and identified objects
>
>
>
> Hi,
>
> Consider this code:
> std::vector v;
> v.resize(256);
> for (i = 0; i < ... ; ++i) {
>   a += v[b[i]];
> }
>
> This is a gather loop, and should be able to be vectorized. *however*...
>
> I as a programmer can see that the size of v.data() is at least 256. I
> know because of the contract of std::vector that v.data() is a unique heap
> object that doesn't alias anything.
>
> However, LLVM knows none of this. Only if I force-inline
> std::vector::__append and friends does LLVM actually see the operator
> new(256) call - without that LLVM has no idea of the underlying storage of
> v, or of its size.
>
> Now, the vectorizer can emit runtime pointer checks, but one thing it
> absolutely requires is knowledge of the maximum size of a pointed-to object
> so it can do range intersection analysis. Without this information, it
> can't even emit a runtime pointer check.
>
> So this RFC is about what exactly is going wrong here. I don't understand
> quite how we intend LLVM to gain this information - are we missing some
> intrinsics or abstractions?
>
> FWIW, this is one of the primary motivators for
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf (which
> I need to get back to working on soon). The size is also important
> information (but likely not as important as the aliasing in this case - it
> is more important if you have conditional accesses and lack hardware
> predicated loads/stores).
>
> In this case, where the object is local, I can imagine some smarter IPA
> (function attributes or otherwise) helping. I think that, in general, we'll
> probably need to provide some attributes that can be used to adorn the
> std::vector implementation, translated into some associated intrinsics
> and/or metadata, that will allow the backend to compute these various
> properties.
>
>
> Or is the inliner just doing a poor job?
>
> Perhaps this too ;)
>
>  -Hal
>
>
> I can't imagine that in the common case inlining all the way to operator
> new() would be beneficial - it's only beneficial in this case because the
> object is newly constructed so all of the branches in __append can be
> folded away when inlining.
>
> Any information welcome :)
>
> Cheers,
>
> James
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160404/cd13b2fb/attachment.html>