llvm dev - Jan 2019 - Status of the function merging pass?

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)?

thanks,
vedant

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190131/95fdd9b7/attachment.html>

(Disclaimer: I don’t know anything about MergeFunctions; I’m just assuming
functionality from the name)

How does MergeFunctions compare to performing identical code folding (ICF) in
the linker?

From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Vedant
Kumar via llvm-dev <llvm-dev at lists.llvm.org>
Reply-To: Vedant Kumar <vsk at apple.com>
Date: Thursday, January 31, 2019 at 11:52 AM
To: llvm-dev <llvm-dev at lists.llvm.org>
Cc: "nikic at php.net" <nikic at php.net>
Subject: [llvm-dev] Status of the function merging pass?

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)?

thanks,
vedant

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190131/713359d2/attachment.html>

Yikes, Mail.app dropped a bunch of CC’s. I’ll try to re-add them now.

> On Jan 31, 2019, at 12:24 PM, Shoaib Meenai <smeenai at fb.com>
wrote:
> 
> (Disclaimer: I don’t know anything about MergeFunctions; I’m just assuming
functionality from the name)
>  
> How does MergeFunctions compare to performing identical code folding (ICF)
in the linker?
IIUC there are a couple important differences:

1) Linker ICF tends to be fairly restricted. E.g. on Darwin, the linker only
deduplicates if a) the compiler has marked the symbol “auto-hide”, b) the text
of both symbols literally memcmp’s to 0, and c) they have exactly the same
relocations. MergeFunctions results in substantial code size reductions even
with linker deduplication enabled, probably because it can detect more kinds of
equivalent functions.

2) MergeFunctions runs much earlier in the pipeline, so it can save compile-time
(no need to optimize forwarding thunks)

vedant
>  
> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of
Vedant Kumar via llvm-dev <llvm-dev at lists.llvm.org>
> Reply-To: Vedant Kumar <vsk at apple.com>
> Date: Thursday, January 31, 2019 at 11:52 AM
> To: llvm-dev <llvm-dev at lists.llvm.org>
> Cc: "nikic at php.net" <nikic at php.net>
> Subject: [llvm-dev] Status of the function merging pass?
>  
> 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)?
>  
> thanks,
> vedant
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190131/8ab8d944/attachment.html>

On Thu, Jan 31, 2019 at 12:24 PM Shoaib Meenai via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
> (Disclaimer: I don’t know anything about MergeFunctions; I’m just assuming
functionality from the name)
>
>
>
> How does MergeFunctions compare to performing identical code folding (ICF)
in the linker?
>
>
The linker has access to a narrower set of informations, so it can
only merge byte-by-byte identical functions, while, in theory, you can
imagine that mergefunc could discover equivalences (through VN), and
understand that, e.g.
```
func pat(i32 %blah) {
  %0 = sub %blah, 1
   ret %0
}
```
and
```
func tinky(i32 %blah) {
  %0 = add %blah, 0
  ret %0
}
```

are equivalent. Some things to keep in mind:
1) My example is relatively silly, but some slightly more elaborate
patterns might show up in real code
2) I think llvm does enough canonicalization that we should be able to
catch these anyways
3) I don't think the pass as-is in tree does any equivalence finding,
but that's a potential advantage of running this analysis as IR pass.

Thanks,

--
Davide

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190131/d3677c20/attachment.html>

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>