<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">CC: D.M.Berris. for the specific of X-ray.<div class=""><br class=""></div><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jan 16, 2017, at 7:41 PM, Sean Silva via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Would it make sense for xray instrumentation be part of -fprofile-generate? PGO will affect inlining decisions etc for the optimized binary, but the collected traces during the instrumented build would still have quite a bit of useful information.</div></div></blockquote><div><br class=""></div><div>As I remember, X-ray is only adding nops at compile time and the instrumentation is only added/enabled at runtime, so I’m not sure how it’ll play with -fprofile-generate ?</div><div><br class=""></div><div>— </div><div>Mehdi</div><div><br class=""></div><div><br class=""></div><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><div class="gmail_extra"><br class=""><div class="gmail_quote">On Mon, Jan 16, 2017 at 4:33 PM, Xinliang David Li <span dir="ltr" class=""><<a href="mailto:xinliangli@gmail.com" target="_blank" class="">xinliangli@gmail.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="">Google GCC records profile data (dynamic callgraph) in a special named section in ELF object file to be consumed by the plugin. Those sections will be discarded later by the linker. <div class=""><br class=""></div><div class="">There are pros and cons of using xray for layout purpose. The call trace from xray is certainly more powerful for layout purpose, but it adds addtional complexity to the optimized build process. You would need to collect xray trace profile on the optimized binary (presumably built with PGO already) and rebuild without xray nop insertion and function layout. </div><span class="HOEnZb"><font color="#888888" class=""><div class=""><br class=""></div><div class="">David</div></font></span></div><div class="gmail_extra"><br class=""><div class="gmail_quote"><div class=""><div class="h5">On Mon, Jan 16, 2017 at 3:40 PM, Sean Silva via llvm-dev <span dir="ltr" class=""><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>></span> wrote:<br class=""></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class=""><div class="h5"><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote"><div class=""><div class="m_2603856233747166285h5">On Mon, Jan 16, 2017 at 3:34 PM, Sean Silva <span dir="ltr" class=""><<a href="mailto:chisophugis@gmail.com" target="_blank" class="">chisophugis@gmail.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote"><div class=""><div class="m_2603856233747166285m_-7837440205302842452h5">On Mon, Jan 16, 2017 at 3:32 PM, Sean Silva <span dir="ltr" class=""><<a href="mailto:chisophugis@gmail.com" target="_blank" class="">chisophugis@gmail.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote"><div class=""><div class="m_2603856233747166285m_-7837440205302842452m_4008972156106747560h5">On Mon, Jan 16, 2017 at 2:31 PM, Davide Italiano <span dir="ltr" class=""><<a href="mailto:davide@freebsd.org" target="_blank" class="">davide@freebsd.org</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Mon, Jan 16, 2017 at 2:07 PM, Mehdi Amini <<a href="mailto:mehdi.amini@apple.com" target="_blank" class="">mehdi.amini@apple.com</a>> wrote:<br class="">
><br class="">
> On Jan 16, 2017, at 1:47 PM, Sean Silva <<a href="mailto:chisophugis@gmail.com" target="_blank" class="">chisophugis@gmail.com</a>> wrote:<br class="">
><br class="">
><br class="">
><br class="">
> On Mon, Jan 16, 2017 at 1:25 PM, Davide Italiano <<a href="mailto:davide@freebsd.org" target="_blank" class="">davide@freebsd.org</a>> wrote:<br class="">
>><br class="">
>> On Mon, Jan 16, 2017 at 12:31 PM, Sean Silva via llvm-dev<br class="">
>> <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> wrote:<br class="">
>> > Do we have any open projects on LLD?<br class="">
>> ><br class="">
>> > I know we usually try to avoid any big "projects" and mainly add/fix<br class="">
>> > things<br class="">
>> > in response to user needs, but just wondering if somebody has any ideas.<br class="">
>> ><br class="">
>><br class="">
>> I'm not particularly active in lld anymore, but the last big item I'd<br class="">
>> like to see implemented is Pettis-Hansen layout.<br class="">
>> <a href="http://perso.ensta-paristech.fr/~bmonsuez/Cours/B6-4/Articles/papers15.pdf" rel="noreferrer" target="_blank" class="">http://perso.ensta-paristech.f<wbr class="">r/~bmonsuez/Cours/B6-4/Article<wbr class="">s/papers15.pdf</a><br class="">
>> (mainly because it improves performances of the final executable).<br class="">
>> GCC/gold have an implementation of the algorithm that can be used as<br class="">
>> base. I'll expand if anybody is interested.<br class="">
>> Side note: I'd like to propose a couple of llvm projects as well, I'll<br class="">
>> sit down later today and write them.<br class="">
><br class="">
><br class="">
><br class="">
> I’m not sure, can you confirm that such layout optimization on ELF requires<br class="">
> -ffunction-sections?<br class="">
><br class="">
<br class="">
</span>For the non-LTO case, I think so.<br class="">
<span class=""><br class="">
> Also, for clang on OSX the best layout we could get is to order functions in<br class="">
> the order in which they get executed at runtime.<br class="">
><br class="">
<br class="">
</span>That's what we already do for lld. We collect and order file (run a<br class="">
profiler) and pass that to the linker that lays out functions<br class="">
accordingly.<br class="">
This is to improve startup time for a class of startup-time-sensitive<br class="">
operations. The algorithm proposed by Pettis (allegedly) aims to<br class="">
reduce the TLB misses as it tries to lay out hot functions (or<br class="">
functions that are likely to be called together near in the final<br class="">
binary).<br class=""></blockquote><div class=""><br class=""></div></div></div><div class="">IIRC from when I looked at the paper a while ago, it is mostly just a "huffman tree construction" type algorithm (agglomerating based on highest probability) and assumes that if two functions are hot then they are likely to be needed together. This is not always the case.</div><div class=""><br class=""></div><div class="">E.g. consider a server that accepts RPC requests and based on those requests either does Foo or Bar which are largely disjoint. It's entirely possible for the top two functions of the profile to be one in Foo and one in Bar, but laying them out near each other doesn't make sense since there is never locality (for a given RPC, either Foo or Bar gets run). A static call graph analysis can provide the needed signals to handle this case better. </div><span class="m_2603856233747166285m_-7837440205302842452m_4008972156106747560HOEnZb"><font color="#888888" class=""><div class=""><br class=""></div></font></span></div></div></div></blockquote><div class=""><br class=""></div></div></div><div class="">Hence you said "allegedly" :) I know we've talked about this before. Just wanted to put the backstory of the "allegedly" on the list.</div></div></div></div></blockquote><div class=""><br class=""></div></div></div><div class="">Looks like I remembered this wrong. The algorithm in section 3.2 of the paper is call-graph aware. It does do greedy coalescing like a Huffman tree construction algorithms, but constrains the available coalescing operations at each step by call graph adjacency (in fact, what it is "greedy" about is the hotness of the edges between call graph nodes and not the nodes themselves).</div><div class=""><div class="m_2603856233747166285h5"><div class=""><br class=""></div><div class="">-- Sean Silva</div><div class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><span class="m_2603856233747166285m_-7837440205302842452HOEnZb"><font color="#888888" class=""><div class=""><br class=""></div><div class="">-- Sean Silva</div></font></span><div class=""><div class="m_2603856233747166285m_-7837440205302842452h5"><div class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><span class="m_2603856233747166285m_-7837440205302842452m_4008972156106747560HOEnZb"><font color="#888888" class=""><div class=""></div><div class="">-- Sean Silva</div></font></span><div class=""><div class="m_2603856233747166285m_-7837440205302842452m_4008972156106747560h5"><div class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<span class=""><br class="">
><br class="">
> For FullLTO it is conceptually pretty easy to get profile data we need for<br class="">
> this, but I'm not sure about the ThinLTO case.<br class="">
><br class="">
> Teresa, Mehdi,<br class="">
><br class="">
> Are there any plans (or things already working!) for getting profile data<br class="">
> from ThinLTO in a format that the linker can use for code layout? I assume<br class="">
> that profile data is being used already to guide importing, so it may just<br class="">
> be a matter of siphoning that off.<br class="">
><br class="">
><br class="">
> I’m not sure what kind of “profile information” is needed, and what makes it<br class="">
> easier for MonolithicLTO compared to ThinLTO?<br class="">
><br class="">
> Or maybe that layout code should be inside LLVM; maybe part of the general<br class="">
> LTO interface? It looks like the current gcc plugin calls back into gcc for<br class="">
> the actual layout algorithm itself (function call<br class="">
> find_pettis_hansen_function_la<wbr class="">yout) rather than the reordering logic living<br class="">
> in the linker:<br class="">
> <a href="https://android.googlesource.com/toolchain/gcc/+/3f73d6ef90458b45bbbb33ef4c2b174d4662a22d/gcc-4.6/function_reordering_plugin/function_reordering_plugin.c" rel="noreferrer" target="_blank" class="">https://android.googlesource.c<wbr class="">om/toolchain/gcc/+/3f73d6ef904<wbr class="">58b45bbbb33ef4c2b174d4662a22d/<wbr class="">gcc-4.6/function_reordering_pl<wbr class="">ugin/function_reordering_plugi<wbr class="">n.c</a><br class="">
><br class="">
><br class="">
> I was thinking about this: could this be done by reorganizing the module<br class="">
> itself for LTO?<br class="">
><br class="">
> That wouldn’t help non-LTO and ThinLTO though.<br class="">
<br class="">
</span>This is a dimension that I think can be explored. The fact that it<br class="">
wouldn't help with other modes of operation is completely orthogonal,<br class="">
in particular until it's proven that this kind of optimization makes<br class="">
sense with ThinLTO (and if it doesn't, it can be an optimization ran<br class="">
only during full LTO).<br class="">
<div class="m_2603856233747166285m_-7837440205302842452m_4008972156106747560m_1399328833334621314HOEnZb"><div class="m_2603856233747166285m_-7837440205302842452m_4008972156106747560m_1399328833334621314h5"><br class="">
--<br class="">
Davide<br class="">
<br class="">
"There are no solved problems; there are only problems that are more<br class="">
or less solved" -- Henri Poincare<br class="">
</div></div></blockquote></div></div></div><br class=""></div></div>
</blockquote></div></div></div><br class=""></div></div>
</blockquote></div></div></div><br class=""></div></div>
<br class=""></div></div><span class="">______________________________<wbr class="">_________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/<wbr class="">mailman/listinfo/llvm-dev</a><br class="">
<br class=""></span></blockquote></div><br class=""></div>
</blockquote></div><br class=""></div></div></div>
_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></div></body></html>