Rodrigo Rocha via llvm-dev
2019-Mar-15 21:29 UTC
[llvm-dev] [RFC] A road map for the function merging optimization
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>
JF Bastien via llvm-dev
2019-Mar-15 23:53 UTC
[llvm-dev] [RFC] A road map for the function merging optimization
At a high level I would like to see a better function merger. I think you should incrementally improve the existing one. It would be useful to go through previous discussions, e.g.: https://reviews.llvm.org/D22051 <https://reviews.llvm.org/D22051> https://reviews.llvm.org/D52896 <https://reviews.llvm.org/D52896> As I see it, the main problem to mergefuncs today is that it has a view of IR which tends to diverge from actual IR. I think this needs to be fixed, and mergefuncs turned on by default, before we try to improve it. Somehow, declaring LLVM IR shouldn’t be able to diverge from how mergefuncs compares and hashes IR. i.e. LLVM contributors shouldn’t be able to inadvertently break mergefuncs by adding a new property to an existing IR node. If you do this, we can then turn mergefuncs on by default, then improve it. One improvement I’d like to see is for a simple mergefuncs to run early, because that reduces compile-time. You can then have a late mergefuncs which performs more work (including partial merging). I’m happy to help review patches along the way.> On Mar 15, 2019, at 2:29 PM, Rodrigo Rocha via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > 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 <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 <https://doi.org/10.1109/CGO.2019.8661174> > > Many thanks, > Rodrigo Rocha > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190315/1e1776d5/attachment.html>