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

[Hal Finkel via llvm-dev]

----- Original Message -----

> 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/20160401/0a77f045/attachment.html>