Aditya K via llvm-dev
2019-Feb-01 00:40 UTC
[llvm-dev] Status of the function merging pass?
Hi Nikita, Glad to hear that Rust code can benefit a lot from this. I have put patches to enable merge-similar functions with thinLTO. https://reviews.llvm.org/D52896 etc. <https://reviews.llvm.org/D52896> 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. -Aditya ________________________________ From: Nikita Popov <nikita.ppv at gmail.com> Sent: Thursday, January 31, 2019 3:46 PM To: Vedant Kumar Cc: llvm-dev; Reid Kleckner; Aditya K; whitequark at whitequark.org; Teresa Johnson; Duncan P. N. Exon Smith; Jessica Paquette Subject: Re: Status of the function merging pass? On Thu, Jan 31, 2019 at 8:52 PM Vedant Kumar <vsk at apple.com<mailto:vsk at apple.com>> wrote: Hi, 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. 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 (https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp). Is anyone actively working on enabling MergeFunctions in LLVM's default pipelines? Is there a roadmap for doing so? 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. 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)? 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). 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. So, at least for Rust's use case this pass seems to be both quite robust and useful :) Regards, Nikita -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190201/7ec451f7/attachment.html>
JF Bastien via llvm-dev
2019-Feb-01 00:54 UTC
[llvm-dev] Status of the function merging pass?
> On Jan 31, 2019, at 4:40 PM, Aditya K via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > Hi Nikita, > > Glad to hear that Rust code can benefit a lot from this. > > I have put patches to enable merge-similar functions with thinLTO. > https://reviews.llvm.org/D52896 etc. > <https://reviews.llvm.org/D52896> > > 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.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). 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. Once that’s addressed, I think mergefuncs can be improved in a few ways. 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. 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. The fuzzy matching should only be run later, and some science should be put in determining how it interacts with inlining. Vedant, I’m happy to chat in person next time we’re in the same building :-)> -Aditya > > > From: Nikita Popov <nikita.ppv at gmail.com> > Sent: Thursday, January 31, 2019 3:46 PM > To: Vedant Kumar > Cc: llvm-dev; Reid Kleckner; Aditya K; whitequark at whitequark.org; Teresa Johnson; Duncan P. N. Exon Smith; Jessica Paquette > Subject: Re: Status of the function merging pass? > > On Thu, Jan 31, 2019 at 8:52 PM Vedant Kumar <vsk at apple.com <mailto:vsk at apple.com>> wrote: > Hi, > > 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. > > 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 (https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp <https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp>). > > Is anyone actively working on enabling MergeFunctions in LLVM's default pipelines? Is there a roadmap for doing so? > > 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. > > 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)? > > 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). > > 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. > > So, at least for Rust's use case this pass seems to be both quite robust and useful :) > > Regards, > Nikita > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190131/f99e18d0/attachment.html>
Eli Friedman via llvm-dev
2019-Feb-01 01:37 UTC
[llvm-dev] Status of the function merging pass?
Adding back llvmdev; sorry about that. Recently had to switch mail clients, and Outlook’s reply-all button is broken. -Eli From: Eli Friedman Sent: Thursday, January 31, 2019 5:35 PM To: 'JF Bastien' <jfbastien at apple.com>; Aditya K <hiraditya at msn.com>; Vedant Kumar <vsk at apple.com> Subject: RE: [EXT] Re: [llvm-dev] Status of the function merging pass? Specifically on the question of making sure MergeFuncs doesn’t regress, I’m not sure what you think we can do. We have certain extension points which allow changes to IR in general without individually verifying each pass: metadata, and function attributes. Merging can just discard metadata, and refuse to merge functions with mismatched attributes. Similarly, we can add intrinsics which don’t have special semantics (essentially, intrinsics which can be treated as equivalent to function calls); we can also generally ignore those. If anything else about the IR changes, it’s necessary to individually verify each pass to make sure they don’t make any invalid assumptions. We’ll inevitably make mistakes in that verification because our transformation passes aren’t proof-verified. There isn’t really anything about that which is specific to mergefuncs in particular. There are maybe a few changes we could make that would make MergeFuncs more resistant to certain classes of IR changes. For example, we could require that all instructions store all information which isn’t an operand or metadata in a way that would allow MergeFuncs to retrieve it as an opaque blob. Or MergeFuncs could bail out if it sees an instruction with an unknown opcode. But it’s impossible to write an pass that will never need to be updated. -Eli From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces at lists.llvm.org>> On Behalf Of JF Bastien via llvm-dev Sent: Thursday, January 31, 2019 4:54 PM To: Aditya K <hiraditya at msn.com<mailto:hiraditya at msn.com>>; Vedant Kumar <vsk at apple.com<mailto:vsk at apple.com>> Cc: llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> Subject: [EXT] Re: [llvm-dev] Status of the function merging pass? On Jan 31, 2019, at 4:40 PM, Aditya K via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote: Hi Nikita, Glad to hear that Rust code can benefit a lot from this. I have put patches to enable merge-similar functions with thinLTO. https://reviews.llvm.org/D52896 etc. <https://reviews.llvm.org/D52896> 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. 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). 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. Once that’s addressed, I think mergefuncs can be improved in a few ways. 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. 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. The fuzzy matching should only be run later, and some science should be put in determining how it interacts with inlining. Vedant, I’m happy to chat in person next time we’re in the same building :-) -Aditya ________________________________ From: Nikita Popov <nikita.ppv at gmail.com<mailto:nikita.ppv at gmail.com>> Sent: Thursday, January 31, 2019 3:46 PM To: Vedant Kumar Cc: llvm-dev; Reid Kleckner; Aditya K; whitequark at whitequark.org<mailto:whitequark at whitequark.org>; Teresa Johnson; Duncan P. N. Exon Smith; Jessica Paquette Subject: Re: Status of the function merging pass? On Thu, Jan 31, 2019 at 8:52 PM Vedant Kumar <vsk at apple.com<mailto:vsk at apple.com>> wrote: Hi, 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. 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 (https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp). Is anyone actively working on enabling MergeFunctions in LLVM's default pipelines? Is there a roadmap for doing so? 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. 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)? 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). 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. So, at least for Rust's use case this pass seems to be both quite robust and useful :) Regards, Nikita _______________________________________________ LLVM Developers mailing list llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190201/9e345b88/attachment.html>
JF Bastien via llvm-dev
2019-Feb-01 04:30 UTC
[llvm-dev] Status of the function merging pass?
> On Jan 31, 2019, at 5:37 PM, Eli Friedman <efriedma at quicinc.com> wrote: > > Adding back llvmdev; sorry about that. Recently had to switch mail clients, and Outlook’s reply-all button is broken. > > -Eli > > From: Eli Friedman > Sent: Thursday, January 31, 2019 5:35 PM > To: 'JF Bastien' <jfbastien at apple.com>; Aditya K <hiraditya at msn.com>; Vedant Kumar <vsk at apple.com> > Subject: RE: [EXT] Re: [llvm-dev] Status of the function merging pass? > > Specifically on the question of making sure MergeFuncs doesn’t regress, I’m not sure what you think we can do.Define IR in a manner in which individual IR nodes and their properties can’t diverge from how they’re compared / hashes / fuzzy matched. I hate to say it, but say through tablegen.> We have certain extension points which allow changes to IR in general without individually verifying each pass: metadata, and function attributes. Merging can just discard metadata, and refuse to merge functions with mismatched attributes. Similarly, we can add intrinsics which don’t have special semantics (essentially, intrinsics which can be treated as equivalent to function calls); we can also generally ignore those.Agreed, that’s the conservative route. Though for function attributes I’d advocate some knowledge of the relevant ones to enable merging (the same way we merge constants with different visibilities already).> If anything else about the IR changes, it’s necessary to individually verify each pass to make sure they don’t make any invalid assumptions. We’ll inevitably make mistakes in that verification because our transformation passes aren’t proof-verified. There isn’t really anything about that which is specific to mergefuncs in particular.Agreed, and historically we’ve failed at doing this correctly. What I propose above (typing IR definition to comparisons) makes it less error-prone.> There are maybe a few changes we could make that would make MergeFuncs more resistant to certain classes of IR changes. For example, we could require that all instructions store all information which isn’t an operand or metadata in a way that would allow MergeFuncs to retrieve it as an opaque blob. Or MergeFuncs could bail out if it sees an instruction with an unknown opcode. But it’s impossible to write an pass that will never need to be updated.Agreed, I’m just saying that we can avoid the most frequent (and here hard to find) cases.> -Eli > > > From: llvm-dev <llvm-dev-bounces at lists.llvm.org <mailto:llvm-dev-bounces at lists.llvm.org>> On Behalf Of JF Bastien via llvm-dev > Sent: Thursday, January 31, 2019 4:54 PM > To: Aditya K <hiraditya at msn.com <mailto:hiraditya at msn.com>>; Vedant Kumar <vsk at apple.com <mailto:vsk at apple.com>> > Cc: llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> > Subject: [EXT] Re: [llvm-dev] Status of the function merging pass? > > > > > On Jan 31, 2019, at 4:40 PM, Aditya K via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: > > Hi Nikita, > > Glad to hear that Rust code can benefit a lot from this. > > I have put patches to enable merge-similar functions with thinLTO. > https://reviews.llvm.org/D52896 etc. > <https://reviews.llvm.org/D52896> > > 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. > > 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). > > > 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. > > > > Once that’s addressed, I think mergefuncs can be improved in a few ways. > > 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. > > 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. > > The fuzzy matching should only be run later, and some science should be put in determining how it interacts with inlining. > > Vedant, I’m happy to chat in person next time we’re in the same building :-) > > > > -Aditya > > > From: Nikita Popov <nikita.ppv at gmail.com <mailto:nikita.ppv at gmail.com>> > Sent: Thursday, January 31, 2019 3:46 PM > To: Vedant Kumar > Cc: llvm-dev; Reid Kleckner; Aditya K; whitequark at whitequark.org <mailto:whitequark at whitequark.org>; Teresa Johnson; Duncan P. N. Exon Smith; Jessica Paquette > Subject: Re: Status of the function merging pass? > > On Thu, Jan 31, 2019 at 8:52 PM Vedant Kumar <vsk at apple.com <mailto:vsk at apple.com>> wrote: > Hi, > > 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. > > 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 (https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp <https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp>). > > Is anyone actively working on enabling MergeFunctions in LLVM's default pipelines? Is there a roadmap for doing so? > > 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. > > 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)? > > 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). > > 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. > > So, at least for Rust's use case this pass seems to be both quite robust and useful :) > > Regards, > Nikita > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190131/f012472d/attachment.html>
Vedant Kumar via llvm-dev
2019-Feb-01 18:58 UTC
[llvm-dev] Status of the function merging pass?
> On Jan 31, 2019, at 4:40 PM, Aditya K <hiraditya at msn.com> wrote: > > Hi Nikita, > > Glad to hear that Rust code can benefit a lot from this. > > I have put patches to enable merge-similar functions with thinLTO. > https://reviews.llvm.org/D52896 etc. <https://reviews.llvm.org/D52896> > > 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.At the risk of straying too far off-topic: I think this patch is interesting, but would need help to understand it better. Would you mind starting a new thread about it? Specifically, I’d like to know what the marginal benefit is of factoring out dissimilar instructions, versus simply factoring out dissimilar constants. Presumably there’s a compile-time vs. performance vs. code size tradeoff. I think this is worth digging into because equivalence-module-constant-uses merging was sufficient for Swift. vedant> > > -Aditya > > > From: Nikita Popov <nikita.ppv at gmail.com> > Sent: Thursday, January 31, 2019 3:46 PM > To: Vedant Kumar > Cc: llvm-dev; Reid Kleckner; Aditya K; whitequark at whitequark.org; Teresa Johnson; Duncan P. N. Exon Smith; Jessica Paquette > Subject: Re: Status of the function merging pass? > > On Thu, Jan 31, 2019 at 8:52 PM Vedant Kumar <vsk at apple.com <mailto:vsk at apple.com>> wrote: > Hi, > > 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. > > 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 (https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp <https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp>). > > Is anyone actively working on enabling MergeFunctions in LLVM's default pipelines? Is there a roadmap for doing so? > > 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. > > 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)? > > 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). > > 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. > > So, at least for Rust's use case this pass seems to be both quite robust and useful :) > > Regards, > Nikita-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190201/d5f93f7b/attachment.html>
Vedant Kumar via llvm-dev
2019-Feb-01 19:19 UTC
[llvm-dev] Status of the function merging pass?
> On Jan 31, 2019, at 4:54 PM, JF Bastien <jfbastien at apple.com> wrote: > > > >> On Jan 31, 2019, at 4:40 PM, Aditya K via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: >> >> Hi Nikita, >> >> Glad to hear that Rust code can benefit a lot from this. >> >> I have put patches to enable merge-similar functions with thinLTO. >> https://reviews.llvm.org/D52896 etc. >> <https://reviews.llvm.org/D52896> >> >> 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. > > 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). > > > 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.Yes, that’s exactly what I’m getting at. More examples: MergeFunctions miscompiled vararg functions and `musttail` calls up until very recently (llvm.org/PR40345 <http://llvm.org/PR40345>, r351405 resp). 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.> Once that’s addressed, I think mergefuncs can be improved in a few ways. > > 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.Nice!> 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. > > The fuzzy matching should only be run later, and some science should be put in determining how it interacts with inlining. > > Vedant, I’m happy to chat in person next time we’re in the same building :-)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. vedant> > >> -Aditya >> >> >> From: Nikita Popov <nikita.ppv at gmail.com <mailto:nikita.ppv at gmail.com>> >> Sent: Thursday, January 31, 2019 3:46 PM >> To: Vedant Kumar >> Cc: llvm-dev; Reid Kleckner; Aditya K; whitequark at whitequark.org <mailto:whitequark at whitequark.org>; Teresa Johnson; Duncan P. N. Exon Smith; Jessica Paquette >> Subject: Re: Status of the function merging pass? >> >> On Thu, Jan 31, 2019 at 8:52 PM Vedant Kumar <vsk at apple.com <mailto:vsk at apple.com>> wrote: >> Hi, >> >> 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. >> >> 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 (https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp <https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp>). >> >> Is anyone actively working on enabling MergeFunctions in LLVM's default pipelines? Is there a roadmap for doing so? >> >> 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. >> >> 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)? >> >> 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). >> >> 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. >> >> So, at least for Rust's use case this pass seems to be both quite robust and useful :) >> >> Regards, >> Nikita >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190201/046769ce/attachment.html>
Teresa Johnson via llvm-dev
2019-Feb-01 19:34 UTC
[llvm-dev] Status of the function merging pass?
On Fri, Feb 1, 2019 at 10:58 AM Vedant Kumar <vsk at apple.com> wrote:> On Jan 31, 2019, at 4:40 PM, Aditya K <hiraditya at msn.com> wrote: > > > Hi Nikita, > > Glad to hear that Rust code can benefit a lot from this. > > I have put patches to enable merge-similar functions with thinLTO. > https://reviews.llvm.org/D52896 etc. <https://reviews.llvm.org/D52896> > >I had some comments on several of these, but I don't think they were addressed yet? One of my meta comments was that it would be better to have the patches be standalone increments on top of each other (they seemed to be split up somewhat arbitrarily when I looked before - maybe this has been fixed?), and link them in phab as parent/child revisions (so you can get a stack of them displayed in phab to see the relationships). Thanks, Teresa> > 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. > > > At the risk of straying too far off-topic: I think this patch is > interesting, but would need help to understand it better. Would you mind > starting a new thread about it? Specifically, I’d like to know what the > marginal benefit is of factoring out dissimilar instructions, versus simply > factoring out dissimilar constants. Presumably there’s a compile-time vs. > performance vs. code size tradeoff. I think this is worth digging into > because equivalence-module-constant-uses merging was sufficient for Swift. > > vedant > > > > > -Aditya > > > ------------------------------ > *From:* Nikita Popov <nikita.ppv at gmail.com> > *Sent:* Thursday, January 31, 2019 3:46 PM > *To:* Vedant Kumar > *Cc:* llvm-dev; Reid Kleckner; Aditya K; whitequark at whitequark.org; > Teresa Johnson; Duncan P. N. Exon Smith; Jessica Paquette > *Subject:* Re: Status of the function merging pass? > > On Thu, Jan 31, 2019 at 8:52 PM Vedant Kumar <vsk at apple.com> wrote: > > Hi, > > 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. > > 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 ( > https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp > ). > > Is anyone actively working on enabling MergeFunctions in LLVM's default > pipelines? Is there a roadmap for doing so? > > 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. > > 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)? > > > 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). > > 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. > > So, at least for Rust's use case this pass seems to be both quite robust > and useful :) > > Regards, > Nikita > > >-- Teresa Johnson | Software Engineer | tejohnson at google.com | -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190201/f659cb29/attachment.html>