
<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=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Jan 31, 2019, at 4:54 PM, JF Bastien <<a href="mailto:jfbastien@apple.com" class="">jfbastien@apple.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><br class="Apple-interchange-newline"><br class="" style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;"><blockquote type="cite" class="" style="font-family: Helvetica; font-size: 14px; 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; text-decoration: none;"><div class="">On Jan 31, 2019, at 4:40 PM, Aditya K 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 class="" style="caret-color: rgb(0, 0, 0); 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; font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;">Hi Nikita,</div><div class="" style="caret-color: rgb(0, 0, 0); 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; font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;"><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); 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; font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;">Glad to hear that Rust code can benefit a lot from this.</div><div class="" style="caret-color: rgb(0, 0, 0); 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; font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;"> <span class="Apple-converted-space"> </span><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); 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; font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;">I have put patches to enable merge-similar functions with thinLTO.<span class="Apple-converted-space"> </span></div><div class="" style="caret-color: rgb(0, 0, 0); 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; font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;"><div class="" style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;"><a href="https://reviews.llvm.org/D52896" class="">https://reviews.llvm.org/D52896 etc.<br class=""></a></div><div class="" style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;"><br class=""></div>This is more powerful than existing merge-functions pass and all we need to do is port these patches to trunk llvm. I'd be happy to help with this effort.</div></div></blockquote><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class=""><br class=""></div><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class="">I still don’t understand why we should ditch mergefuncs instead of incrementally improving it. I’d like to understand what’s actually changing incrementally, and first fix the fundamental flaw mergefuncs has (as I discuss below).</div><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class=""><br class=""></div><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class=""><br class=""></div><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class="">To answer Vedant’s question: I think the fundamental problem with mergefuncs is that it needs to understand IR perfectly, for equality comparison, hashing, and “fuzzy” matching. Any solution that’s on-by-default should address this issue: when we change IR we cannot allow mergefuncs to suddenly be wrong in a subtle way. For example, when we added cmpxchg “failure” order, mergefuncs needed to know about it, otherwise it could merge functions which differed only in failure ordering and suddenly generate code that was *wrong* in an incredibly hard to diagnose manner.</div></div></blockquote><div><br class=""></div><div>Yes, that’s exactly what I’m getting at. More examples: MergeFunctions miscompiled vararg functions and `musttail` calls up until very recently (<a href="http://llvm.org/PR40345" class="">llvm.org/PR40345</a>, r351405 resp).</div><div><br class=""></div><div>As Eli pointed out, the problem isn’t entirely avoidable. I think the interesting question here is whether (or, "how to”) make it more tractable.</div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class="">Once that’s addressed, I think mergefuncs can be improved in a few ways.</div><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class=""><br class=""></div><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class="">First it can be run early to remove exact duplicates. This will speed up build times. I had an intern, Jason, work on mergefuncs a few years ago and he measured speedups when compiling Chrome just though an early run.</div></div></blockquote><div><br class=""></div><div>Nice!</div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class="">Then mergefuncs should be improved to do fuzzy matching, where it determines that functions are similar enough that they can be variants of each other with an extra argument passed in to specialize each “flavor”. Jason had posted a patch for this back then as well, and it yielded some gains on Chrome’s binary size. He hadn’t explored the full breadth of specializations (do you just find differences in constants, or branch around entire code blocks, etc). There’s extra science to perform around different optimization levels.</div><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class=""><br class=""></div><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class="">The fuzzy matching should only be run later, and some science should be put in determining how it interacts with inlining.</div><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class=""><br class=""></div><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class="">Vedant, I’m happy to chat in person next time we’re in the same building :-)</div></div></blockquote><div><br class=""></div><div>That’d be nice :). At this point I’m still trying to wrap my head around how to put function comparison on sounder footing. Down the road, fuzzy matching seems like a promising area to work on.</div><div><br class=""></div><div>vedant</div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class=""><br class=""></div><div style="caret-color: rgb(255, 255, 255); color: rgb(255, 255, 255); font-family: Helvetica; font-size: 14px; 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; text-decoration: none;" class=""><br class=""></div><blockquote type="cite" class="" style="font-family: Helvetica; font-size: 14px; 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; text-decoration: none;"><div class=""><div class="" style="caret-color: rgb(0, 0, 0); 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; font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;">-Aditya<br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); 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; font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;"><br class=""></div><div 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;"><div id="appendonsend" class=""></div><div class="" style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;"><br class=""></div><div class="" style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt;"></div><hr tabindex="-1" class="" style="display: inline-block; width: 809.46875px;"><div id="divRplyFwdMsg" dir="ltr" class=""><font face="Calibri, sans-serif" class="" style="font-size: 11pt;"><b class="">From:</b><span class="Apple-converted-space"> </span>Nikita Popov <<a href="mailto:nikita.ppv@gmail.com" class="">nikita.ppv@gmail.com</a>><br class=""><b class="">Sent:</b><span class="Apple-converted-space"> </span>Thursday, January 31, 2019 3:46 PM<br class=""><b class="">To:</b><span class="Apple-converted-space"> </span>Vedant Kumar<br class=""><b class="">Cc:</b><span class="Apple-converted-space"> </span>llvm-dev; Reid Kleckner; Aditya K;<span class="Apple-converted-space"> </span><a href="mailto:whitequark@whitequark.org" class="">whitequark@whitequark.org</a>; Teresa Johnson; Duncan P. N. Exon Smith; Jessica Paquette<br class=""><b class="">Subject:</b><span class="Apple-converted-space"> </span>Re: Status of the function merging pass?</font><div class=""> </div></div><div class=""><div dir="ltr" class=""><div class="x_gmail_quote"><div dir="ltr" class="x_gmail_attr">On Thu, Jan 31, 2019 at 8:52 PM Vedant Kumar <<a href="mailto:vsk@apple.com" class="">vsk@apple.com</a>> wrote:<br class=""></div><blockquote class="x_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 class="">Hi,<div class=""><br class=""></div><div class="">I'm interested in finding ways to reduce code size. LLVM's MergeFunctions pass seems like a promising option, and I'm curious about its status in tree.</div><div class=""><br class=""></div><div class="">Enabling MergeFunctions gives a 1% code size reduction across the entire iOS shared cache (a collection of a few hundred system-critical DSO's). The numbers are even more compelling for Swift code. In fact, the swift compiler enables MergeFunctions by default when optimizing, along with an even more aggressive merging pass which handles equivalence-modulo-constant-uses (<a href="https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp" target="_blank" class="">https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp</a>).</div><div class=""><br class=""></div><div class="">Is anyone actively working on enabling MergeFunctions in LLVM's default pipelines? Is there a roadmap for doing so?</div><div class=""><br class=""></div><div class="">ISTM that preventing miscompiles when merging functions is a serious, unsolved problem. I.e., it's hard for the MergeFunctions pass to be *really sure* that two functions are a) really identical and b) safe to merge.</div><div class=""><br class=""></div><div class="">Is there a systematic solution at the IR-level, given that the semantics of IR are subject to change? Is extensive testing the only solution? Or is this intractable, and the only safe approach is to perform merging post-regalloc (or, at some late point when equivalence is easier to determine)?</div></div></blockquote><div class=""><br class=""></div><div class="">In Rust we've been running with MergeFunctions enabled by default for a while now, and have recently also enabled the use of aliases instead of thunks. Apart from some initial bugs we didn't encounter any significant issues (one minor issue with NVPTX not supporting aliases and having CC restrictions).</div><div class=""><br class=""></div><div class="">As Rust tends to be quite heavy on monomorphization, MergeFuncs can give significant binary size reductions. I don't have any comprehensive numbers, but from checking this on a pet project just now, it reduces final artifact size by 13% and I've seen some similar numbers in the ~10% range quoted before.</div><div class=""><br class=""></div><div class="">So, at least for Rust's use case this pass seems to be both quite robust and useful :)<br class=""></div><div class=""><br class=""></div><div class="">Regards,<br class=""></div><div class="">Nikita<br class=""></div></div></div></div></div><span 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; float: none; display: inline !important;">_______________________________________________</span><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 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; float: none; display: inline !important;">LLVM Developers mailing list</span><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 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; float: none; display: inline !important;"><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a></span><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 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; float: none; display: inline !important;"><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></span></div></blockquote></blockquote></div><br class=""></body></html>