[llvm-dev] [RFC] A road map for the function merging optimization

[Rodrigo Rocha via llvm-dev]

Hi everyone,

I would like to discuss a possible road map for having a more powerful
function merging optimization.

At the moment, the function merging optimization in LLVM is focused on
merging completely equivalent functions. On the other end of this spectrum,
for my last paper in CGO'19, "Function Merging by Sequence Alignment", we
proposed a function merging optimization that is able to merge virtually
any two functions.

Just as a reference, I've made available the prototype of my optimization
in this Github repo:
https://github.com/rcorcs/fmsa
In this repo, I have a unified infrastructure that I'm using to perform
both my Function Merging by Sequence Alignment (FMSA) and also an improved
version of the Branch Fusion that was first proposed to reduce divergence
in GPUs. The idea here is to show that this "code merger" infrastructure
based on sequence alignment doesn't need to be used only by the Function
Merger.

FMSA, as an optimization, is composed of two key components: (1) the merge
operation of two arbitrary functions (which should always produce a merged
function, but not necessarily always smaller than the original ones); (2)
the ranking mechanism used for efficient exploration of the search space.

One option would be to have a road map similar to the following:
  - Add the general merge operation as a utility function.
  - Combine this merge operation with the divergence analysis to create the
branch fusion optimization. This would allow the community to validate and
get familiar with the merge operation.
  - Create FMSA with an exploration mechanism (either the ranking-based
one, a hash-based one, or a combination of both). The way I see it, FMSA
could be used with -Oz and the existing "identical"-only merger could be
used with -Os.

An alternative option would be to slowly enable the current function merger
to handle some differences in the code. Each one of the new features could
be added in two steps, first creating a patch that enables the
FunctionComparator to handle it and then, in a second patch, enable the
actual MergeFunctions pass to also handle it.

The key features to enable are:
  - Handle different operands by either reordering the operands or
inserting select instructions.
  - Handle different return types with a union-like approach.
  - Handle different list of parameters.
  - Handle differences within basic blocks.
  - Handle differences in the CFG.
The way I see it, as we enable more and more of these features, we would
get closer and closer to the FMSA merge operation and exploration.
However, the process of integrating the sequence alignment strategy into
the more structural FunctionComparator is not yet clear to me.

A very simple patch that I am preparing in this direction is to enable the
reordering of operands in equivalent commutative instructions.

I would really appreciate some feedback.

Reference:
"Function Merging by Sequence Alignment",
Rodrigo Rocha, Pavlos Petoumenos, Zheng Wang, Murray Cole, Hugh Leather
https://doi.org/10.1109/CGO.2019.8661174

Many thanks,
Rodrigo Rocha
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190315/0d17990f/attachment.html>