[llvm-dev] New and more general Function Merging optimization for code size

Hal Finkel via llvm-dev llvm-dev at lists.llvm.org
Thu Aug 2 08:43:03 PDT 2018

On 08/02/2018 10:25 AM, Rodrigo Caetano Rocha via llvm-dev wrote:
> Hi everyone,
> 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.
> I would like to know if the community has any interest in having a
> more powerful function merging optimization.

Yes, I think there is certainly interest in this space.

> ---- More Details ----
> Up until now, I have been focusing on the quality of the code reduction.
> Some preliminary result on SPEC'06 in a full LTO fashion:
> 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.
> Average reduction in the final exectuable file over the baseline:
> 5.55% compared to 0.49% of the identical merge.
> Average reduction in the total number of instructions over the
> baseline: 7.04% compared to 0.47% of the identical merge.
> 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).
> 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.
> 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.
> At the moment I'm starting to focus more on simplifying the
> optimization and reducing the overhead in compilation time.
> My optimization has an exploration threshold which can be tuned to
> trade-off compilation time overhead for a more aggressive merge.
> 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".

Can you explain in more detail how this works?

(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


> The threshold limits the exploration to focus on the top functions of
> the rank.
> The idea is to make the ranking mechanism as lightweight as possible.
> Cheers,
> Rodrigo Rocha
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

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

More information about the llvm-dev mailing list