PGO-CO

Profile guided optimization of LLVM-IR via combinatorial optimization and metaheuristics.

This repository is part of an end of degree work: A Combinatorial Approach for Profile Guided Optimization with Metaheuristics.

IMPORTANT NOTE: This project is a preliminary work in approaching code optimizations from the CO and metaheuristics perspective. The objective is not to reach state-of-the-art performance, but to motivate the research in this direction, and open new doors to efficient and intelligent code optimizations.

Description

Code optimization is one of the main tasks that a modern compiler is expected to handle. However, the number of different code optimization scenarios that compilers have to face is vast.

With the objective to address the maximum number of code optimization scenarios as possible, most compilers employ conservative and generalist heuristics in their decision taking process, missing many code optimization opportunities.

In recent years, the growing popularity of ML, has guided multiple attempts to replace the mentioned heuristics with ML based systems. However, the learning and inference cost of ML models, has stopped these proposals to reach real-world environments.

In this work, we propose a new approach for improving code optimization heuristics. Concretely, we focus on the basic block ordering code optimization, and formalize it as a combinatorial problem, with the objective to apply CO algorithms to solve such problem.

Conducted experiments reveal that our CO approach is comparable to the one implemented in the widely used clang compiler, even being able to improve its results in some of the collected metrics.

How to build

First, ensure that you have the following dependencies:

• Rust (tested in 1.61)
• LLVM (tested in v12.0.1)
• clang (tested in v12.0.1)

Then, clone this repository and move inside:

git clone https://git.sr.ht/~mikelma/pgo_co
cd pgo_co

Once inside the repo, you can build the project as the following:

# to build fully optimized
cargo build --profile opt 

# or, to build as debug
cargo build

If the --features log CLI option is given in to the cargo build command, the optimizer tool will generate a CSV log file with a variety optimization stats when it is run.

Once the command finishes, compiled binaries will be located inside target/opt (if it was a debug build, in target/debug).

Tools

These are the tools that compose the project:

• inspector: Given an annotated(*) LLVM IR bitcode file, outputs a bunch of information about the relevant profiling metadata contained in the IR.

• generator: Generates a combinatorial problem instance file from an annotated LLVM IR bitcode.

• optimizer: Given an LLVM IR bitcode file to optimize, and its instance (the one generated by generator tool), optimizes the basic block layout of the program.

(*) With annotated, I refer to LLVM IR that contains profiling metadata, see this, and this for more info.

How to use

In the following lines, the steps to optimize your program with our PGO approach are listed. Note that our optimization operates on LLVM IR, thus, it can be applied to any programming language that translates to LLVM.

1. The first step is to generate profiling data about the program to optimize. Clang's documentation has an excellent guide on how to do this (link). If your project does not use clang, you can refer to the specific guide on PGO of your compiler of choice. Anyhow, the objective of this step is to generate one or multiple whatever.profraw files with the profiling data.

2. Link all the .profraw files into a single .profdata file with the following command:

llvm-profdata merge -output=code.profdata *.profraw

3. Compile your program into a single LLVM, annotated, IR bitcode file. This can be done adding the -flto and -fprofile-instr-use=code.profdata flags in your compilation command (if you use clang or a compatible compiler), as it will generate a bunch of .o files that contain LLVM IR bitcode, that can be linked by running: llvm-link *.o -o linked.bc.

4. Generate an CO problem instance file with the following command: ./generator -i linked.bc -o myprogram.json

5. Optimize linked.bc with: ./optimizer -i linked.bc -p myprogram.json -o optimized.ll

6. Finally you can compile the optimized LLVM IR to a binary (linked to the libraries you might need):

clang optimized.ll -o myprogram  <the linker flags you might need>

License

This project is distributed under the terms of the GLPv3 license. See LICENSE for more details.