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

[Rodrigo Caetano Rocha via llvm-dev]

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.

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