LoginSignup
5
1
FUJITSUAdvent Calendar 2023Day 22
@joule(joule s)in富士通 ソフトウェア技術者コミュニティ

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

Last updated at Posted at 2023-12-21

この記事はFUJITSU Advent Calendar 2023の22日目の投稿です。

LLVM Projectの実行バイナリの最適化ツールBOLTについて書きたいと思います。

BOLTの最適化

論文によると、BOLTの主要な最適化はメモリ配置最適化です。これは実行オブジェクト(ELF)のメモリアドレスをソートして、アクセス頻度の高い処理（関数や基本ブロック）の命令コードがキャッシュ(I-Cache)に残りやすいように再配置するというものです。

sample.png
メモリ再配置はメモリのホットスポットをソートするイメージ（右が最適化後）
引用元: Optimizing the Linux Kernel with LLVM

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

インストール方法

インストール方法にしたがってビルド・インストールすることができます。

適用方法

BOLTはELFのリロケーション情報と実行プロファイルを利用します。
ドキュメントに沿って以下の手順で最適化します。

  • 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の最適化を試してみました。ここでは3つのstageで以下のようにclangを作成しています。（手順はAppendixに記載しました）

  • 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に対してシンボリックリンクを張ることで置き換えられます。

$ 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])の再配置されたセクションが追加されていることがわかります。

$ 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
測定スクリプト 
$ 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

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

環境

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

Appendix: Clangの最適化の手順

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

stage1: ビルド用のclangを作成

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

スクリプト 
$ 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

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

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

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

スクリプト 
$ 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

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

スクリプト 
$ 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

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

$ 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を指定します。

スクリプト 
$ 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 ## 並列数はメモリ不足を考慮して設定

stage3: stage2のclangをBOLTで最適化

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

スクリプト 
$ 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 ## 並列数はメモリ不足を考慮して設定

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

$ 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を適用します。

$ 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を参照することで確認できます。

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
1