llvm dev - Aug 2018 - New and more general Function Merging optimization for code size

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>

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
vetorization).

 -Hal
> 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>

Hi Hal,

Because my function merging strategy is able to merge any two function,
allowing for different CFGs, different parameters, etc.
I am unable to use just a simple hash value to compare whether or not two
functions are similar.

Therefore, the idea is to have an infrastructure which allows me to compare
whether or not two functions are similar without having traverse the two
function (basically performing a merge for all pairs).
I'm precomputing a fingerprint of all functions, which is then cached for
later use (this might also be useful to enable this function merging with
ThinLTO).
At the moment, this fingerprint is just a map of opcode -> number of
occurrences in the function, which is just a ~64-int-array.

Then, for each functions being considered for a merge, I'm able to rank the
candidates with a PriorityQueue.

Hopefully, we are able to do that in a very lightweight manner.

After that, the more expensive bit will be actually performing the merge
and then checking for profitability, using the TTI for code-size.

I haven't given much thought about adapting this infrastructure for the SLP
Vectorizer, but perhaps something similar could also work there.

Cheers,

Rodrigo Rocha


On Thu, 2 Aug 2018 at 16:43 Hal Finkel <hfinkel at anl.gov> wrote:
>
> 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
> vetorization).
>
>  -Hal
>
> 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 listllvm-dev at
lists.llvm.orghttp://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/1b55e0d5/attachment.html>