<div dir="ltr">Hi Hal,<div><br></div><div><div class="uyb8Gf"><div class="F3hlO"><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)">> FWIW, this is one of the primary motivators for <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf" target="_blank">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf</a> (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).<br>><br>> 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.</div><div><br></div><div>I like that proposal. It's dated late 2014 - is it still making progress?</div><div><br></div><div>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++.</div><div><br></div><div>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?)</div><div><br></div><div>Cheers,</div><div><br></div><div>James</div></div></div></div><br><div class="gmail_quote"><div dir="ltr">On Fri, 1 Apr 2016 at 17:55 Hal Finkel <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"><br><hr><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><b>From: </b>"James Molloy via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br><b>To: </b>"LLVM Dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>, "Chandler Carruth" <<a href="mailto:chandlerc@google.com" target="_blank">chandlerc@google.com</a>><br><b>Sent: </b>Friday, April 1, 2016 2:56:25 AM<br><b>Subject: </b>[llvm-dev] RFC: std::vector and identified objects</blockquote></div></div><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><br><br><div dir="ltr">Hi,<div><br></div><div>Consider this code:</div><div>std::vector v;</div><div>v.resize(256);</div><div>for (i = 0; i < ... ; ++i) {</div><div>  a += v[b[i]];</div><div>}</div><div><br></div><div>This is a gather loop, and should be able to be vectorized. <b>however</b>...</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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?</div></div></blockquote></div></div><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"></blockquote>FWIW, this is one of the primary motivators for <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf" target="_blank">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf</a> (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).<br><br>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.</div></div><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"><br><br><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><div dir="ltr"><div> Or is the inliner just doing a poor job?</div></div></blockquote></div></div><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000">Perhaps this too ;)<br><br> -Hal<br><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"></blockquote></div></div><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><div dir="ltr"><div></div><div><br></div><div>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.</div><div><br></div><div>Any information welcome :)</div><div><br></div><div>Cheers,</div><div><br></div><div>James</div></div>
<br></blockquote></div></div><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt">_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br></blockquote></div></div><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></div></blockquote></div></div>