/llvm-next-function-merging

An experimental LLVM pass plugin that allows you to apply the State of the Art function merging techniques

Primary LanguageLLVMApache License 2.0Apache-2.0

LLVM Next Function Merging

LLVM Next Function Merging is an experimental LLVM pass plugin that allows you to apply the State of the Art function merging techniques to your program.

The optimization passes are derived from "F3M: Fast Focused Function Merging (CGO'22), Sean Sterling, Rodrigo C. O. Rocha, Hugh Leather, Kim Hazelwood, Michael O'Boyle, Pavlos Petoumenos" and its forked LLVM repository with a few changes for building it as a plugin (Licensed under Apache License v2.0 with LLVM Exceptions).

This repository is a fork of the original repository and allows out-of-tree development from LLVM to focus on the essential improvements.

Quick start

  1. Clone the repository
$ git clone https://github.com/kateinoigakukun/llvm-next-function-merging.git
$ cd llvm-next-function-merging
  1. Configure build directory

You need LLVM 13 to build this plugin. Please add -DLLVM_DIR:PATH=/path/to/lib/cmake/llvm to the CMake configuration in the case of pkg-config cannot find LLVM.

$ cmake -B build -G Ninja
  1. Build the plugin
$ cmake --build ./build
  1. Use the plugin with opt

Note: Since most of passes other than func-merging still use the legacy pass manager, you need to pass --enable-new-pm=false and --load instead of --load-pass-plugin to opt.

opt --load-pass-plugin ./build/lib/Transforms/IPO/LLVMNextFM.so \
  -S ./test/Transforms/NextFM/basic.ll \
  --passes=func-merging

Optimization passes

This plugin provides the following passes:

Pass name Short description Paper Original source
func-merging The current state of the art. Better pair finding algorithm based on MinHash, LSH, and fastfm F3M: Fast Focused Function Merging (CGO'22), HyFM: Function Merging for Free (LCTES'21) ppetoumenos/llvm-project by Pavlos Petoumenos
fastfm Better merging algorithm (SalSSA) Effective Function Merging in the SSA Form (PLDI'20) rcorcs/llvm-project by Rodrigo Rocha
fmsa Merging arbitrary two functions by pairwise sequence alignment Function Merging by Sequence Alignment (CGO'19) rcorcs/fmsa by Rodrigo Rocha
mergesimilarfunc Merging two functions with isomorphic CFGs Exploiting Function Similarity for Code Size Reduction (LCTES 2014) LLVM Patch D22051 by Tobias Edler von Koch

Executing the Tests

This project uses lit to execute the tests as well as other LLVM families do.

$ cmake -B build -G Ninja -D BUILD_TESTING:BOOL=ON
$ cmake --build ./build
$ lit ./build/test

Project Structure

The directory structure of this project is designed to be easy for upstreaming to the LLVM project. Most part of the tree shadows the original LLVM repository structure.