# 機能設計書 11-BOLT

## 概要

本ドキュメントは、LLVMプロジェクトにおけるBOLT（Binary Optimization and Layout Tool）の機能設計書である。BOLTはポストリンク最適化ツールであり、実行プロファイルに基づいてバイナリのコードレイアウトを最適化し、アプリケーションの実行性能を向上させる。

### 本機能の処理概要

BOLTは、リンク済みのバイナリ実行ファイルに対して、実行時プロファイルデータを活用した最適化を行うツールである。従来のコンパイル時最適化では得られない、実行時の振る舞いに基づいた最適化を実現する。

**業務上の目的・背景**：大規模なアプリケーション（特にデータセンターで稼働するサーバーアプリケーション）では、コードのキャッシュ効率が性能に大きく影響する。BOLTは、実行プロファイルに基づいてホットコード（頻繁に実行されるコード）を連続したメモリ領域に配置することで、命令キャッシュのヒット率を向上させ、分岐予測の精度を改善する。Facebookでの実績では、大規模アプリケーションで最大15%の性能向上が報告されている。

**機能の利用シーン**：
- 本番環境でのプロファイル収集後、リリースバイナリの最適化
- 継続的インテグレーション/継続的デリバリー（CI/CD）パイプラインでの自動最適化
- パフォーマンスクリティカルなアプリケーションのチューニング

**主要な処理内容**：
1. ELF/MachOバイナリの読み込みと解析
2. 制御フローグラフ（CFG）の再構築
3. perf等から収集したプロファイルデータの取り込み
4. 基本ブロックの並び替え（ブランチ直線化）
5. 関数の並び替え（ホット関数のグルーピング）
6. 同一コードの折りたたみ（ICF: Identical Code Folding）
7. 最適化されたバイナリの出力

**関連システム・外部連携**：
- Linux perf：プロファイルデータの収集（LBR/BRBE対応）
- LLVMコアライブラリ：MC（Machine Code）レイヤーの活用
- リンカ（LLD等）：--emit-relocsオプションでリロケーション情報を保持

**権限による制御**：特になし。ただし、バイナリファイルへの読み書き権限が必要。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | CLIツールのため画面なし |

## 機能種別

バイナリ最適化処理 / コードレイアウト最適化 / プロファイルガイド最適化

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| InputFilename | string | Yes | 最適化対象のELF/MachOバイナリファイルパス | ファイル存在確認、形式チェック |
| -o (OutputFilename) | string | Yes | 出力ファイルパス | - |
| -data / -b | string | No | プロファイルデータファイル（.fdata形式） | ファイル存在確認 |
| -p (PerfData) | string | No | perf.dataファイル（直接読み込み用） | ファイル形式チェック |
| -reorder-blocks | enum | No | ブロック並び替えアルゴリズム（ext-tsp等） | 有効な値のチェック |
| -reorder-functions | enum | No | 関数並び替えアルゴリズム（cdsort等） | 有効な値のチェック |
| -split-functions | bool | No | 関数分割の有効化 | - |
| -split-all-cold | bool | No | 全コールドコードの分割 | - |
| -update-debug-sections | bool | No | デバッグ情報の更新 | - |
| -instrument | bool | No | インストルメンテーションモード | - |

### 入力データソース

1. **バイナリファイル**：ELFまたはMachO形式の実行ファイル（シンボルテーブル必須、--emit-relocs推奨）
2. **プロファイルデータ**：
   - perf.data：Linux perfで収集したサンプリングデータ
   - .fdata：BOLT固有のプロファイル形式（perf2boltで変換）
   - インストルメンテーションデータ：BOLTで計装したバイナリから収集

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 最適化バイナリ | ELF/MachO | コードレイアウトが最適化されたバイナリファイル |
| .bolt.info | note section | BOLT処理情報（リビジョン、オプション等） |
| .bolt.text | code section | 最適化されたコード領域 |
| DynoStats | stdout | 最適化による統計情報（-dyno-stats有効時） |

### 出力先

- 最適化されたバイナリファイル（-oオプションで指定）
- 標準出力（統計情報、進捗情報）
- 標準エラー出力（警告、エラーメッセージ）

## 処理フロー

### 処理シーケンス

```
1. 初期化とバイナリ読み込み
   └─ ターゲットアーキテクチャの初期化、ELF/MachOファイルのオープン

2. RewriteInstance作成
   └─ BinaryContextの構築、セクション情報の読み込み

3. オブジェクト探索（discoverFileObjects）
   └─ シンボルテーブルからBinaryFunctionオブジェクトを作成

4. 特殊セクションの読み込み（readSpecialSections）
   └─ .eh_frame、.gcc_except_table等の例外処理情報

5. プロファイルデータの読み込み（setProfile）
   └─ .fdataまたはperf.dataからプロファイル情報を取得

6. 逆アセンブル（disassembleFunctions）
   └─ 各関数の命令列を解析、MCInstオブジェクトに変換

7. CFG構築（buildFunctionsCFG）
   └─ 基本ブロックの識別、制御フロー解析

8. プロファイル適用（processProfileData）
   └─ 実行頻度情報をCFGノードに付与

9. 最適化パス実行（runOptimizationPasses）
   └─ ブロック並び替え、関数並び替え、ICF等

10. コード生成とリンク（emitAndLink）
    └─ 最適化後のコードを中間オブジェクトに出力、リンク

11. バイナリ書き出し（rewriteFile）
    └─ 最終的なELF/MachOファイルの生成
```

### フローチャート

```mermaid
flowchart TD
    A[開始] --> B[バイナリ読み込み]
    B --> C{ELF or MachO?}
    C -->|ELF| D[RewriteInstance作成]
    C -->|MachO| E[MachORewriteInstance作成]
    D --> F[関数探索・逆アセンブル]
    E --> F
    F --> G{プロファイルあり?}
    G -->|Yes| H[プロファイル読み込み]
    G -->|No| I[基本最適化のみ]
    H --> J[CFG構築]
    I --> J
    J --> K[最適化パス実行]
    K --> L[コード生成]
    L --> M[バイナリ書き出し]
    M --> N[終了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | シンボル要件 | 入力バイナリにはシンボルテーブルが必要 | 常時 |
| BR-02 | リロケーション推奨 | 最大の最適化効果には--emit-relocsが必要 | 関数並び替え時 |
| BR-03 | プロファイル鮮度 | プロファイルはバイナリと一致するべき | プロファイル使用時 |
| BR-04 | アーキテクチャ制限 | X86-64およびAArch64のみサポート | 常時 |

### 計算ロジック

**DynoStats（動的統計）の計算**：
- 実行命令数 = 各基本ブロックの命令数 x 実行回数の総和
- 分岐予測ミス推定 = 条件分岐の taken/not-taken 比率に基づく推定

## データベース操作仕様

### 操作別データベース影響一覧

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| - | - | - | データベース操作なし（ファイルベース処理） |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| BOLT-ERROR | ファイルエラー | 入力ファイルが存在しない | 正しいパスを指定 |
| BOLT-ERROR | 形式エラー | 非対応バイナリ形式 | ELF/MachO形式を使用 |
| BOLT-WARNING | プロファイル警告 | staleプロファイル検出 | プロファイルを再収集 |
| BOLT-ERROR | アーキテクチャエラー | 非対応アーキテクチャ | X86-64/AArch64を使用 |

### リトライ仕様

リトライ不要（バッチ処理）

## トランザクション仕様

該当なし（ファイル操作のみ）

## パフォーマンス要件

- 大規模バイナリ（数百MB）でも数分以内に処理完了
- 並列処理による最適化パスの高速化（jemalloc/tcmalloc推奨）

## セキュリティ考慮事項

- 入力バイナリの整合性検証
- 出力バイナリのパーミッション保持
- デバッグ情報の適切な更新（シンボル情報の整合性維持）

## 備考

- GCC8以降の-freorder-blocks-and-partitionオプションとは非互換
- PIEおよび共有ライブラリ（.so）もサポート
- BOLT処理済みバイナリは.note.bolt_infoセクションで識別可能

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

まず、BOLTの中核となるデータ構造を理解することが重要である。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | BinaryContext.h | `bolt/include/bolt/Core/BinaryContext.h` | バイナリ全体のコンテキスト管理、BinaryFunction/BinaryDataのマップ |
| 1-2 | BinaryFunction.h | `bolt/include/bolt/Core/BinaryFunction.h` | 関数の内部表現、CFG、基本ブロック |
| 1-3 | BinaryBasicBlock.h | `bolt/include/bolt/Core/BinaryBasicBlock.h` | 基本ブロックの構造、命令列の保持 |

**読解のコツ**: BinaryContextはシングルトン的に使用され、すべてのBinaryFunctionへのアクセス点となる。`BinaryFunctions`マップ（アドレス->関数）が中心的なデータ構造。

#### Step 2: エントリーポイントを理解する

処理の起点となるファイル・関数を特定する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | llvm-bolt.cpp | `bolt/tools/driver/llvm-bolt.cpp` | main関数、モード選択（bolt/perf2bolt/boltdiff） |

**主要処理フロー**:
1. **176-203行目**: main関数の開始、ターゲット初期化、モード選択
2. **227-268行目**: RewriteInstanceの作成とプロファイル設定
3. **267行目**: `RI.run()`で全処理を実行

#### Step 3: RewriteInstanceの処理フローを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | RewriteInstance.h | `bolt/include/bolt/Rewrite/RewriteInstance.h` | クラス定義、主要メソッドのシグネチャ |
| 3-2 | RewriteInstance.cpp | `bolt/lib/Rewrite/RewriteInstance.cpp` | run()メソッドの実装、処理シーケンス |

**主要処理フロー**:
- **run()メソッド**: discoverFileObjects -> readSpecialSections -> disassembleFunctions -> buildFunctionsCFG -> runOptimizationPasses -> emitAndLink -> rewriteFile

#### Step 4: 最適化パスを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | BinaryPassManager.h | `bolt/include/bolt/Rewrite/BinaryPassManager.h` | パス管理クラス |
| 4-2 | BinaryPasses.cpp | `bolt/lib/Passes/BinaryPasses.cpp` | 各種最適化パスの実装 |
| 4-3 | ReorderFunctions.cpp | `bolt/lib/Passes/ReorderFunctions.cpp` | 関数並び替えアルゴリズム |
| 4-4 | SplitFunctions.cpp | `bolt/lib/Passes/SplitFunctions.cpp` | 関数分割（hot/cold分離） |

#### Step 5: プロファイル処理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | DataAggregator.h | `bolt/include/bolt/Profile/DataAggregator.h` | perfデータの集約 |
| 5-2 | YAMLProfileReader.cpp | `bolt/lib/Profile/YAMLProfileReader.cpp` | YAMLプロファイルの読み込み |

### プログラム呼び出し階層図

```
main() [llvm-bolt.cpp]
    │
    ├─ boltMode() / perf2boltMode()
    │      └─ コマンドライン解析
    │
    ├─ RewriteInstance::create()
    │      └─ BinaryContext::createBinaryContext()
    │
    ├─ RewriteInstance::setProfile()
    │      ├─ DataAggregator (perf.data)
    │      └─ YAMLProfileReader (.fdata)
    │
    └─ RewriteInstance::run()
           │
           ├─ discoverFileObjects()
           │      └─ BinaryFunction作成
           │
           ├─ readSpecialSections()
           │      └─ .eh_frame解析
           │
           ├─ disassembleFunctions()
           │      └─ MCDisassembler使用
           │
           ├─ buildFunctionsCFG()
           │      └─ BinaryBasicBlock構築
           │
           ├─ processProfileData()
           │      └─ 実行頻度の付与
           │
           ├─ runOptimizationPasses()
           │      ├─ ReorderBlocks
           │      ├─ ReorderFunctions
           │      ├─ SplitFunctions
           │      └─ IdenticalCodeFolding
           │
           ├─ emitAndLink()
           │      └─ JITLinkLinker
           │
           └─ rewriteFile()
                  └─ ELF/MachO書き出し
```

### データフロー図

```
[入力]                    [処理]                         [出力]

ELF/MachO Binary ──────▶ RewriteInstance ──────────────▶ 最適化済みバイナリ
                              │
                              ├─▶ BinaryContext
                              │       │
perf.data ─────────────────▶ │       ├─▶ BinaryFunction[]
  or                         │       │       │
.fdata Profile ────────────▶ │       │       └─▶ BinaryBasicBlock[]
                              │       │               │
                              │       │               └─▶ MCInst[]
                              │       │
                              │       └─▶ Profile Data
                              │
                              └─▶ Optimization Passes
                                      │
                                      └─▶ 統計情報（stdout）
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| llvm-bolt.cpp | `bolt/tools/driver/llvm-bolt.cpp` | ソース | メインエントリーポイント |
| RewriteInstance.h | `bolt/include/bolt/Rewrite/RewriteInstance.h` | ヘッダー | ELFリライト処理のインターフェース |
| RewriteInstance.cpp | `bolt/lib/Rewrite/RewriteInstance.cpp` | ソース | ELFリライト処理の実装 |
| MachORewriteInstance.h | `bolt/include/bolt/Rewrite/MachORewriteInstance.h` | ヘッダー | MachOリライト処理のインターフェース |
| BinaryContext.h | `bolt/include/bolt/Core/BinaryContext.h` | ヘッダー | バイナリコンテキスト管理 |
| BinaryContext.cpp | `bolt/lib/Core/BinaryContext.cpp` | ソース | バイナリコンテキスト実装 |
| BinaryFunction.h | `bolt/include/bolt/Core/BinaryFunction.h` | ヘッダー | 関数の内部表現 |
| BinaryFunction.cpp | `bolt/lib/Core/BinaryFunction.cpp` | ソース | 関数処理の実装 |
| BinaryBasicBlock.h | `bolt/include/bolt/Core/BinaryBasicBlock.h` | ヘッダー | 基本ブロックの内部表現 |
| BinaryPassManager.h | `bolt/include/bolt/Rewrite/BinaryPassManager.h` | ヘッダー | 最適化パス管理 |
| BinaryPassManager.cpp | `bolt/lib/Rewrite/BinaryPassManager.cpp` | ソース | パス管理の実装 |
| DataAggregator.h | `bolt/include/bolt/Profile/DataAggregator.h` | ヘッダー | perfデータ集約 |
| DataAggregator.cpp | `bolt/lib/Profile/DataAggregator.cpp` | ソース | perfデータ処理実装 |
| CMakeLists.txt | `bolt/CMakeLists.txt` | 設定 | ビルド設定 |
| README.md | `bolt/README.md` | ドキュメント | プロジェクト概要 |
