<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">How does it compare to the new machine outliner pass in llvm?<div class=""><br class=""></div><div class=""><a href="https://www.youtube.com/watch?v=yorld-WSOeU" class="">https://www.youtube.com/watch?v=yorld-WSOeU</a></div><div class=""><a href="http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html" class="">http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html</a></div><div class=""><br class=""></div><div class="">- Matthias<br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Aug 2, 2018, at 10:30 AM, JF Bastien 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 style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><br class="Apple-interchange-newline"><br class=""><blockquote type="cite" class=""><div class="">On Aug 2, 2018, at 8:58 AM, Rodrigo Caetano Rocha 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="">Hi Hal,<div class=""><br class=""></div><div class="">Because my function merging strategy is able to merge any two function, allowing for different CFGs, different parameters, etc.</div><div class="">I am unable to use just a simple hash value to compare whether or not two functions are similar.</div></div></div></blockquote><div class=""><br class=""></div><div class="">Can you give us more detail on what criteria you use for “fuzzy” merging? Jason Koenig had uploaded a prototype of something similar in 2015, based on mergefuncs.</div><div class=""><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="">Therefore, the idea is to have an infrastructure which allows me to compare whether or not two functions are similar without having traverse the two function (basically performing a merge for all pairs).</div><div class="">I'm precomputing a fingerprint of all functions, which is then cached for later use (this might also be useful to enable this function merging with ThinLTO).</div><div class="">At the moment, this fingerprint is just a map of opcode -> number of occurrences in the function, which is just a ~64-int-array.</div></div></div></blockquote><div class=""><br class=""></div><div class="">The difficulty with mergefuncs is keeping its comparator / hasher in sync with IR. All it takes is one new IR property to break it, and I think the only want to fix this issue is to have comparison / hashing be part of the IR definition. How would you solve this issue?</div><div class=""><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="">Then, for each functions being considered for a merge, I'm able to rank the candidates with a PriorityQueue.</div><div class=""><br class=""></div><div class="">Hopefully, we are able to do that in a very lightweight manner.</div><div class=""><br class=""></div><div class="">After that, the more expensive bit will be actually performing the merge and then checking for profitability, using the TTI for code-size.</div><div class=""><br class=""></div><div class="">I haven't given much thought about adapting this infrastructure for the SLP Vectorizer, but perhaps something similar could also work there.</div><div class=""><br class=""></div><div class="">Cheers,</div><div class=""><br class=""></div><div class="">Rodrigo Rocha<br class=""></div><div class=""><br class=""></div></div><br class=""><div class="gmail_quote"><div dir="ltr" class="">On Thu, 2 Aug 2018 at 16:43 Hal Finkel <<a href="mailto:hfinkel@anl.gov" class="">hfinkel@anl.gov</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div text="#000000" bgcolor="#FFFFFF" class=""><br class=""><div class="m_-4787981321377026353moz-cite-prefix">On 08/02/2018 10:25 AM, Rodrigo Caetano Rocha via llvm-dev wrote:<br class=""></div><blockquote type="cite" class=""><div dir="ltr" class="">Hi everyone,<div class=""><br class=""></div><div class="">I'm currently working on a new function merging optimization that is more general than the current LLVM function merging optimization that works only on identical functions.</div><div class=""><br class=""></div><div class="">I would like to know if the community has any interest in having a more powerful function merging optimization.</div></div></blockquote><br class=""></div><div text="#000000" bgcolor="#FFFFFF" class="">Yes, I think there is certainly interest in this space.</div></blockquote></div></div></blockquote><div class=""><br class=""></div><div class="">Yes.</div><div class=""><br class=""></div><div class="">I'd also be interested in hearing about how this combines with MachineOutliner. I expect they find some redundant things, but mostly help each other.</div><div class=""><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div text="#000000" bgcolor="#FFFFFF" class=""><blockquote type="cite" class=""><div dir="ltr" class=""><div class="">---- More Details ----</div><div class=""><br class=""></div><div class="">Up until now, I have been focusing on the quality of the code reduction.</div><div class=""><br class=""></div><div class="">Some preliminary result on SPEC'06 in a full LTO fashion:</div><div class="">The baseline has no function merge but the optimization pipeline is the same, and I am comparing my function merge with LLVM's identical function merge, where everything else in the optimization pipeline is the same as the baseline.</div><div class="">Average reduction in the final exectuable file over the baseline: 5.55% compared to 0.49% of the identical merge.</div><div class=""><div class=""><span class="m_-4787981321377026353inbox-inbox-gr_ m_-4787981321377026353inbox-inbox-gr_run_anim m_-4787981321377026353inbox-inbox-gr_366 m_-4787981321377026353inbox-inbox-gr-alert m_-4787981321377026353inbox-inbox-doubleReplace m_-4787981321377026353inbox-inbox-gr_inline_cards m_-4787981321377026353inbox-inbox-replaceWithoutSep m_-4787981321377026353inbox-inbox-only-ins m_-4787981321377026353inbox-inbox-gr_gramm m_-4787981321377026353inbox-inbox-Grammar" id="m_-4787981321377026353inbox-inbox-366" style="display: inline; border-bottom-width: 2px; border-bottom-style: solid; border-bottom-color: transparent; background-repeat: no-repeat no-repeat;">Average</span> reduction in the total number of instructions over the baseline: 7.04% compared to 0.47% of the identical merge.</div></div></div></blockquote></div></blockquote></div></div></blockquote><div class=""><br class=""></div><div class="">IIRC this roughly matches Jason’s results on Chrome / Firefox: a few percentage point reduction. Can you try large applications like Chrome / Firefox / WebKit to get more real-world numbers? It’s interesting to compare what you get from regular builds as well as LTO builds (which will take forever, but expose much more duplication).</div><div class=""><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div text="#000000" bgcolor="#FFFFFF" class=""><blockquote type="cite" class=""><div dir="ltr" class=""><div class="">The highest reduction on the executable file is of about 20% (both 429.mcf and 447.dealII) and the highest reduction on the total number of instructions is of about 37% (447.dealII).</div><div class=""><br class=""></div><div class="">It has an average slowdown of about 1%, but having no statistical difference from the baseline in most of the benchmarks in the SPEC'06 suite.</div></div></blockquote></div></blockquote></div></div></blockquote><div class=""><br class=""></div><div class="">Jason’s (uncommitted) work found *speedups* when compiling all of Chrome. The way he did this was with an early and fast mergefuncs which didn’t try to be fuzzy: it just tried to remove code duplication, which means the optimizer spent less time because there were fewer functions. He then had a later mergefuncs which did fuzzy matching and tried to pick up more things. Keeping it somewhat later is important because merging similar functions might make it less attractive to inlining (because the merged functions are now slightly more complex).</div><div class=""><br class=""></div><div class=""><br class=""></div><blockquote type="cite" class=""><div class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div text="#000000" bgcolor="#FFFFFF" class=""><blockquote type="cite" class=""><div dir="ltr" class=""><div class="">Because this new function merging technique is able to merge any pair of functions, except for a few restrictions, the exploration strategy is critical for having an acceptable compilation time.</div><div class=""><br class=""></div><div class="">At the moment I'm starting to focus more on simplifying the optimization and reducing the overhead in compilation time.</div><div class="">My optimization has an exploration threshold which can be tuned to trade-off compilation time overhead for a more aggressive merge.</div><div class="">It does *not* perform n^2 merge operations. Instead, I have a ranking strategy based on a similarity metric computed from the function's "fingerprint".</div></div></blockquote><br class=""></div><div text="#000000" bgcolor="#FFFFFF" class="">Can you explain in more detail how this works?<br class=""><br class="">(I'm also, as a side note, keeping my eye out for things like this that might also help us efficiently do more-compile-time-efficient SLP vetorization).<br class=""><br class=""> -Hal<br class=""><br class=""><blockquote type="cite" class=""></blockquote></div><div text="#000000" bgcolor="#FFFFFF" class=""><blockquote type="cite" class=""><div dir="ltr" class=""><div class="">The threshold limits the exploration to focus on the top functions of the rank.</div><div class="">The idea is to make the ranking mechanism as lightweight as possible.</div><div class=""><br class=""></div><div class="">Cheers,</div><div class=""><br class=""></div><div class="">Rodrigo Rocha</div></div><br class=""><fieldset class="m_-4787981321377026353mimeAttachmentHeader"></fieldset><br class=""></blockquote></div><div text="#000000" bgcolor="#FFFFFF" class=""><blockquote type="cite" class=""><pre class="">_______________________________________________
LLVM Developers mailing list
<a class="m_-4787981321377026353moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a class="m_-4787981321377026353moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre></blockquote></div><div text="#000000" bgcolor="#FFFFFF" class=""><br class=""><pre class="m_-4787981321377026353moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre></div></blockquote></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=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class=""></div></blockquote></div><br class="" style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;"><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">_______________________________________________</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">LLVM Developers mailing list</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><a href="mailto:llvm-dev@lists.llvm.org" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">llvm-dev@lists.llvm.org</a><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></div></blockquote></div><br class=""></div></body></html>