<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="">At a high level I would like to see a better function merger. I think you should incrementally improve the existing one.<div class=""><br class=""></div><div class="">It would be useful to go through previous discussions, e.g.:</div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class=""><ul class=""><li class=""><a href="https://reviews.llvm.org/D22051" class="">https://reviews.llvm.org/D22051</a></li><li class=""><a href="https://reviews.llvm.org/D52896" class="">https://reviews.llvm.org/D52896</a></li></ul></div></blockquote><div class=""><br class=""></div><div class="">As I see it, the main problem to mergefuncs today is that it has a view of IR which tends to diverge from actual IR. I think this needs to be fixed, and mergefuncs turned on by default, before we try to improve it. Somehow, declaring LLVM IR shouldn’t be able to diverge from how mergefuncs compares and hashes IR. i.e. LLVM contributors shouldn’t be able to inadvertently break mergefuncs by adding a new property to an existing IR node.</div><div class=""><br class=""></div><div class="">If you do this, we can then turn mergefuncs on by default, then improve it.</div><div class=""><br class=""></div><div class="">One improvement I’d like to see is for a simple mergefuncs to run early, because that reduces compile-time. You can then have a late mergefuncs which performs more work (including partial merging).</div><div class=""><br class=""></div><div class="">I’m happy to help review patches along the way.</div><div class=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Mar 15, 2019, at 2:29 PM, Rodrigo 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 everyone,<div class=""><br class=""></div><div class="">I would like to discuss a possible road map for having a more powerful function merging optimization.</div><div class=""><br class=""></div><div class="">At the moment, the function merging optimization in LLVM is focused on merging completely equivalent functions. On the other end of this spectrum, for my last paper in CGO'19, "Function Merging by Sequence Alignment", we proposed a function merging optimization that is able to merge virtually any two functions.<br class=""></div><div class=""><br class=""></div><div class="">Just as a reference, I've made available the prototype of my optimization in this Github repo:</div><div class=""><a href="https://github.com/rcorcs/fmsa" class="">https://github.com/rcorcs/fmsa</a><br class=""></div><div class="">In this repo, I have a unified infrastructure that I'm using to perform both my Function Merging by Sequence Alignment (FMSA) and also an improved version of the Branch Fusion that was first proposed to reduce divergence in GPUs. The idea here is to show that this "code merger" infrastructure based on sequence alignment doesn't need to be used only by the Function Merger.</div><div class=""><br class=""></div><div class="">FMSA, as an optimization, is composed of two key components: (1) the merge operation of two arbitrary functions (which should always produce a merged function, but not necessarily always smaller than the original ones); (2) the ranking mechanism used for efficient exploration of the search space.</div><div class=""><br class=""></div><div class="">One option would be to have a road map similar to the following:</div><div class=""> - Add the general merge operation as a utility function.</div><div class=""> - Combine this merge operation with the divergence analysis to create the branch fusion optimization. This would allow the community to validate and get familiar with the merge operation.</div><div class=""> - Create FMSA with an exploration mechanism (either the ranking-based one, a hash-based one, or a combination of both). The way I see it, FMSA could be used with -Oz and the existing "identical"-only merger could be used with -Os.</div><div class=""><br class=""></div><div class="">An alternative option would be to slowly enable the current function merger to handle some differences in the code. Each one of the new features could be added in two steps, first creating a patch that enables the FunctionComparator to handle it and then, in a second patch, enable the actual MergeFunctions <span class="inbox-inbox-only-ins inbox-inbox-gr_ inbox-inbox-gr_gramm inbox-inbox-gr_inline_cards inbox-inbox-gr_run_anim inbox-inbox-gr_543 inbox-inbox-Grammar inbox-inbox-gr-alert inbox-inbox-replaceWithoutSep" id="inbox-inbox-543" style="display:inline;border-bottom:2px solid transparent;background-repeat:no-repeat">pass</span> to also handle it.</div><div class=""><br class=""></div><div class="">The key features to enable are:</div><div class=""> - Handle different operands by either reordering the operands or inserting select instructions.</div><div class=""> - Handle different return types with a union-like approach.</div><div class=""> - Handle different list of parameters.</div><div class=""> - Handle differences within basic blocks.<br class=""></div><div class=""> - Handle differences in the CFG.</div><div class="">The way I see it, as we enable more and more of these features, we would get closer and closer to the FMSA merge operation and exploration. However, the process of integrating the sequence alignment strategy into the more structural FunctionComparator is not yet clear to me.</div><div class=""><br class=""></div><div class="">A very simple patch that I am preparing in this direction is to enable the reordering of operands in equivalent commutative instructions.</div><div class=""><br class=""></div><div class="">I would really appreciate some feedback.<br class=""></div><div class=""><br class=""></div><div class="">Reference:</div><div class="">"Function Merging by Sequence Alignment",</div><div class="">Rodrigo Rocha, Pavlos Petoumenos, Zheng Wang, Murray Cole, Hugh Leather<br class=""></div><div class=""><a href="https://doi.org/10.1109/CGO.2019.8661174" class="">https://doi.org/10.1109/CGO.2019.8661174</a><br class=""></div><div class=""><br class=""></div><div class="">Many thanks,</div><div class="">Rodrigo Rocha</div><div class=""><br class=""></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="">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></div></body></html>