LLVM-BOLTのメモリ配置最適化

この記事は[FUJITSU Advent Calendar 2023](https://qiita.com/advent-calendar/2023/fujitsu)の22日目の投稿です。

[LLVM Project](https://llvm.org)の実行バイナリの最適化ツール[BOLT](https://github.com/llvm/llvm-project/tree/main/bolt)について書きたいと思います。

### BOLTの最適化

[論文](https://research.facebook.com/publications/bolt-a-practical-binary-optimizer-for-data-centers-and-beyond)によると、BOLTの主要な最適化はメモリ配置最適化です。これは実行オブジェクト(ELF)のメモリアドレスをソートして、アクセス頻度の高い処理（関数や基本ブロック）の命令コードがキャッシュ(I-Cache)に残りやすいように再配置するというものです。

![sample.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/490241/3a11b977-3924-35e6-d0eb-8827aad5c062.png)
メモリ再配置はメモリのホットスポットをソートするイメージ（右が最適化後）
引用元: [Optimizing the Linux Kernel with LLVM](https://llvm.org/devmtg/2023-05/slides/TechnicalTalks-May10/11-Panchenko-Optimizing-the-LinuxKernel-with-LLVM%20BOLT.pdf)

また、これに加えていくつかのアーキレベルの最適化が可能です。
BOLTはオブジェクトを逆アセンブルし、LLVMバックエンドの後段の中間表現(MC/MCInst)まで戻して命令を解析しています。そのため、コンパイラレベル(IRレベル)の最適化はできませんが、マシンコードに近い状態での細かい最適化が可能のようです。

### インストール方法

[インストール方法](https://github.com/llvm/llvm-project/tree/main/bolt#installation)にしたがってビルド・インストールすることができます。

### 適用方法

BOLTはELFのリロケーション情報と実行プロファイルを利用します。
[ドキュメント](https://github.com/llvm/llvm-project/tree/main/bolt#usage)に沿って以下の手順で最適化します。

- Step 0: 実行オブジェクト(ELF)の生成
最適化対象の実行オブジェクトはリンク時に```-Wl,-q```オプションを付与し、リロケーション情報(```.rela.text```)を保持しておく必要があります。
- Step 1: プロファイルの取得
```perf record```でサンプリングプロファイルを取得します。
```$ perf record -e cycles:u -j any,u -o perf.data -- <executable> <args> ...```
- Step 2: プロファイルの変換
```perf2bolt```でプロファイルをBOLTの形式に変換します。
```$ perf2bolt -p perf.data -o perf.fdata <executable>```
- Step 3: 最適化
```llvm-bolt```で実行オブジェクトを最適化します。
```$ llvm-bolt <executable> -o <executable>.bolt -data=perf.fdata -reorder-blocks=ext-tsp -reorder-functions=hfsort -split-functions -split-all-cold -split-eh -dyno-stats```

### アプリケーションへの適用例

実践事例の[Clangの最適化](https://github.com/llvm/llvm-project/blob/main/bolt/docs/OptimizingClang.md)を試してみました。ここでは3つのstageで以下のように```clang```を作成しています。（手順は[Appendix](https://qiita.com/joule/items/955ffa9992abbc61335d#appendix-clang%E3%81%AE%E6%9C%80%E9%81%A9%E5%8C%96%E3%81%AE%E6%89%8B%E9%A0%86)に記載しました）

- stage1: ビルド用の```clang```を作成
- stage2: PGO, LTOで最適化した```clang```を作成
- stage3: stage2の```clang```をBOLTで最適化

LLVMのバージョンはrelease/17.xとしました。
stage2での```clang```を```clang-17.org```、BOLTで最適化した```clang```を```clang-17.bolt```とします。以下のようにPATHを通した```clang-17```に対してシンボリックリンクを張ることで置き換えられます。

```bash
$ mv clang-17 clang-17.org
$ ln -fs clang-17.bolt clang-17  # BOLT適用のClangが使われる
$ ln -fs clang-17.org  clang-17  # オリジナルのClangが使われる
```

BOLTで最適化した```clang-17.bolt```は.textとしてHot([27])とCold([28])の再配置されたセクションが追加されていることがわかります。

```text
$ readelf -S stage2-prof-use-lto/install/bin/clang-17.bolt | grep text
  [13] .bolt.org.text    PROGBITS         0000000001c423c0  01c413c0
  [27] .text             PROGBITS         0000000005600000  05400000
  [28] .text.cold        PROGBITS         0000000006079b00  05e79b00
```

それぞれの```clang```で再度別の```clang```をビルドさせたときの性能（実行時間、命令数、L1-icacheミス数、分岐ミス数）を測定したところ以下のようになりました。（8並列で実行）

- PGO+LTOで最適化した```clang```

```
908.873482227 seconds time elapsed
23756046943016      instructions
 1291835627141      L1-icache-misses
  180990120408      branch-misses
```

- PGO+LTO+BOLTで最適化した```clang```

```
828.821684585 seconds time elapsed
23688958701467      instructions
 1039604605495      L1-icache-misses
  174180292775      branch-misses
```          

<details><summary>測定スクリプト</summary>

```bash
$ CPATH=${TOPLEV}/stage2-prof-use-lto/install/bin/
$ cmake -G Ninja ${TOPLEV}/llvm-project/llvm \
  -DLLVM_ENABLE_PROJECTS="clang" \
  -DLLVM_TARGETS_TO_BUILD=X86 -DCMAKE_BUILD_TYPE=Release \
  -DCMAKE_C_COMPILER=$CPATH/clang -DCMAKE_CXX_COMPILER=$CPATH/clang++ \
  -DLLVM_USE_LINKER=lld -DCMAKE_INSTALL_PREFIX=${TOPLEV}/stage4-eval/install

$ ninja clean
$ perf stat -e instructions,L1-icache-misses,branch-misses ninja clang
```

</details>

BOLTを適用したことで、10%近く実行時間が短縮しています👏
この例では、評価と同じ条件（```clang```をビルドしたとき）で取得したプロファイルをつかってBOLTの最適化をしています。プロファイル取得時と異なるタスクでは、最適化の効果は薄くなる可能性があります。

#### 環境
CPU: Intel Core(TM) i7-9700 CPU
MEM: DDR4-2666
OS:  Ubuntu 22.04

---

### Appendix: Clangの最適化の手順

流れは以下のとおりです。

https://github.com/llvm/llvm-project/blob/main/bolt/docs/OptimizingClang.md

#### stage1: ビルド用の```clang```を作成

最適化対象の```clang```のビルドに使用する```clang```を```gcc```でビルドします。
```TOPLEV```は任意のディレクトリで、直下に```llvm-project```のソースコードをダウンロードしています。

<details><summary>スクリプト</summary>

```bash
$ mkdir {TOPLEV}/stage1
$ cd {TOPLEV}/stage1
$ cmake -G Ninja ${TOPLEV}/llvm-project/llvm -DLLVM_TARGETS_TO_BUILD=X86 \
  -DCMAKE_BUILD_TYPE=Release \
  -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++ -DCMAKE_ASM_COMPILER=gcc \
  -DLLVM_ENABLE_PROJECTS="clang;lld" \
  -DLLVM_ENABLE_RUNTIMES="compiler-rt" \
  -DCOMPILER_RT_BUILD_SANITIZERS=OFF -DCOMPILER_RT_BUILD_XRAY=OFF \
  -DCOMPILER_RT_BUILD_LIBFUZZER=OFF \
  -DCMAKE_INSTALL_PREFIX=${TOPLEV}/stage1/install
$ ninja install
```

</details>

#### stage2: PGO, LTOで最適化した```clang```を作成

ここでは、PGO+LTOで最適化した```clang```をビルドしています。
PGOはプロファイルを利用した最適化です。そのため、インストルメント（計測機能）を埋め込んだ```clang```で何らかのタスク（コンパイル）を行い、実行プロファイルの取得することになります。

1). インストルメントを埋め込んだ```clang```のビルド
まずは、インストルメントを埋め込んだ```clang```をビルドします。

<details><summary>スクリプト</summary>

```bash
$ export CPATH=${TOPLEV}/stage1/install/bin
$ mkdir ${TOPLEV}/stage2-prof-gen
$ cd ${TOPLEV}/stage2-prof-gen
$ cmake -G Ninja ${TOPLEV}/llvm-project/llvm -DLLVM_TARGETS_TO_BUILD=X86 \
    -DCMAKE_BUILD_TYPE=Release \
    -DCMAKE_C_COMPILER=${CPATH}/clang -DCMAKE_CXX_COMPILER=${CPATH}/clang++ \
    -DLLVM_ENABLE_PROJECTS="clang;lld" \
    -DLLVM_USE_LINKER=lld -DLLVM_BUILD_INSTRUMENTED=ON \
    -DCMAKE_INSTALL_PREFIX=${TOPLEV}/stage2-prof-gen/install
$ ninja install
```

</details>

2). プロファイルの取得
インストルメントを埋め込んだ```clang```でタスクを実行し、プロファイルを取得します。
ここでは、再度```clang```をビルドするというタスクをしています。プロファイルは```stage2-prof-gen/profiles```に配置されます。

<details><summary>スクリプト</summary>

```bash
$ export CPATH=${TOPLEV}/stage2-prof-gen/install/bin
$ mkdir ${TOPLEV}/stage2-train
$ cd ${TOPLEV}/stage2-train
$ cmake -G Ninja ${TOPLEV}/llvm-project/llvm -DLLVM_TARGETS_TO_BUILD=X86 \
    -DCMAKE_BUILD_TYPE=Release \
    -DCMAKE_C_COMPILER=${CPATH}/clang -DCMAKE_CXX_COMPILER=${CPATH}/clang++ \
    -DLLVM_ENABLE_PROJECTS="clang" \
    -DLLVM_USE_LINKER=lld -DCMAKE_INSTALL_PREFIX=${TOPLEV}/stage2-train/install
$ ninja clang
```

</details>

プロファイルは```stage2-prof-gen/profiles```に配置されます。
複数のプロファイルが配置されるため、以下のコマンドでマージします。

```bash
$ cd ${TOPLEV}/stage2-prof-gen/profiles
$ ${TOPLEV}/stage1/install/bin/llvm-profdata merge -output=clang.profdata *
```

3). PGO+LTOの最適化を有効にし```clang```をビルド
取得したプロファイルによるPGO、およびLTOを有効にして```clang```をビルドします。コンパイラはstage1の```clang```を使用します。
また、この```clang```はBOLTを適用することになるため、リンクオプションとして```-Wl,-q```を指定します。

<details><summary>スクリプト</summary>

```bash
$ export CPATH=${TOPLEV}/stage1/install/bin
$ mkdir ${TOPLEV}/stage2-prof-use-lto
$ cd ${TOPLEV}/stage2-prof-use-lto
$ export LDFLAGS="-Wl,-q"
$ cmake -G Ninja ${TOPLEV}/llvm-project/llvm -DLLVM_TARGETS_TO_BUILD=X86 \
    -DCMAKE_BUILD_TYPE=Release \
    -DCMAKE_C_COMPILER=${CPATH}/clang -DCMAKE_CXX_COMPILER=${CPATH}/clang++ \
    -DLLVM_ENABLE_PROJECTS="clang;lld" \
    -DLLVM_ENABLE_LTO=Full \
    -DLLVM_PROFDATA_FILE=${TOPLEV}/stage2-prof-gen/profiles/clang.profdata \
    -DLLVM_USE_LINKER=lld \
    -DCMAKE_INSTALL_PREFIX=${TOPLEV}/stage2-prof-use-lto/install

ninja -j 1 install ## 並列数はメモリ不足を考慮して設定
```

</details>

#### stage3: stage2の```clang```をBOLTで最適化

stage2で作成した```clang```にBOLTを適用して最適化します。
前述の通り、BOLTはプロファイルを使用します。stage3では、まずそのプロファイルを```perf```で取得します。


<details><summary>スクリプト</summary>

```bash
$ export CPATH=${TOPLEV}/stage2-prof-use-lto/install/bin
$ mkdir ${TOPLEV}/stage3
$ cd ${TOPLEV}/stage3
$ export LDFLAGS="-Wl,-q"
$ cmake -G Ninja ${TOPLEV}/llvm-project/llvm \
  -DLLVM_ENABLE_PROJECTS="clang" \
  -DLLVM_TARGETS_TO_BUILD=X86 -DCMAKE_BUILD_TYPE=Release \
  -DCMAKE_C_COMPILER=${CPATH}/clang -DCMAKE_CXX_COMPILER=${CPATH}/clang++ \
  -DLLVM_USE_LINKER=lld -DCMAKE_INSTALL_PREFIX=${TOPLEV}/stage3/install

ninja -j 1 install ## 並列数はメモリ不足を考慮して設定
```

</details>

プロファイル```prof.data```が取得できたら、それをBOLTの読み込める形式に変換します。```clang-17```が最適化対象です。

```bash
$ export CPATH=${TOPLEV}/stage2-prof-use-lto/install/bin
$ perf2bolt $CPATH/clang-17 -p perf.data -o clang-17.fdata -w clang-17.yaml
```

変換後の```clang-17.yaml```を使ってBOLTを適用します。

```bash
$ llvm-bolt $CPATH/clang-17 -o $CPATH/clang-17.bolt -b clang-17.yaml \
    -reorder-blocks=ext-tsp -reorder-functions=hfsort+ -split-functions \
    -split-all-cold -dyno-stats -icf=1 -use-gnu-stack
```

```${TOPLEV}/stage2-prof-use-lto/install/bin/clang-17.bolt```が作成されていることを確認します。
BOLTが適用されているかどうかは.noteを参照することで確認できます。

```bash
$ readelf -p .note.bolt_info stage2-prof-use-lto/install/bin/clang-17.bolt | grep BOLT
  [    10]  BOLT revision: 6009708b4367171ccdbf4b5905cb6a803753fe18, command line: llvm-bolt ...
```