# 機能設計書 54-llvm-reduce

## 概要

本ドキュメントは、LLVMプロジェクトにおけるllvm-reduceツールの機能設計を記述する。llvm-reduceは、バグを再現するLLVM IRテストケースを自動的に最小化するデルタデバッグツールである。

### 本機能の処理概要

llvm-reduceは、与えられた「興味深さテスト（interestingness test）」を満たしながら、LLVM IRまたはMIRファイルを可能な限り小さく削減するコマンドラインツールである。デルタデバッギング手法を用いて、バグを再現するために必要最小限のコードを特定し、開発者がバグの原因を特定しやすくする。

**業務上の目的・背景**：コンパイラのバグ報告において、大規模なテストケースは原因特定を困難にする。llvm-reduceは、バグを再現する最小のテストケースを自動的に生成することで、開発者の負担を大幅に軽減する。これは、bugpointツールの再設計の一環として開発された、より高速で効率的な削減ツールである。

**機能の利用シーン**：
- コンパイラクラッシュのテストケース削減
- 最適化バグの再現コード最小化
- バグ報告用テストケースの作成
- リグレッションテストの簡素化

**主要な処理内容**：
1. 入力IRファイルの読み込みとパース
2. 興味深さテストの初期検証
3. 複数のデルタパスを順次実行
4. 各パスで要素を削減しながらテストを繰り返し実行
5. 削減結果の出力

**関連システム・外部連携**：
- ユーザー定義の興味深さテストスクリプト（シェルスクリプト等）
- LLVMのIRReader、MIR機能との連携

**権限による制御**：本ツールはファイルシステムへの読み書きアクセスと、外部プログラムの実行権限を必要とする。

## 関連画面

本ツールはCLI（コマンドラインインターフェース）ツールであり、GUI画面は存在しない。

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| N/A | コマンドライン | 主画面 | 入力ファイル、テストスクリプト、オプションの指定 |

## 機能種別

テストケース削減 / デルタデバッグ

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| InputFilename | string | Yes | 削減対象のIR/MIRファイル | ファイルが存在すること |
| --test | string | Yes | 興味深さテストの実行ファイル | 実行可能ファイルであること |
| --test-arg | list<string> | No | テストに渡す引数 | - |
| --output / -o | string | No | 出力ファイル名（デフォルト: reduced.ll/bc/mir） | - |
| -x | enum | No | 入力言語（ir または mir） | ir/mirのいずれか |
| --in-place | bool | No | 入力ファイルを直接上書き | - |
| --delta-passes | string | No | 実行するデルタパス（カンマ区切り） | 有効なパス名 |
| --skip-delta-passes | string | No | スキップするデルタパス | 有効なパス名 |
| --max-pass-iterations | int | No | パス全体の最大反復回数（デフォルト: 5） | 正の整数 |
| --output-bitcode | bool | No | テキストIRの代わりにビットコードで出力 | - |
| --preserve-debug-environment | bool | No | クラッシュデバッグ機能を無効にしない | - |
| --print-delta-passes | bool | No | 利用可能なデルタパス一覧を表示 | - |

### 入力データソース

- LLVM IRファイル（.ll：テキスト形式、.bc：ビットコード形式）
- MIRファイル（.mir形式）

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| ReducedFile | file | 削減されたIR/MIRファイル |
| ProgressLog | text | 削減プロセスの進捗情報 |

### 出力先

- 指定された出力ファイル（または標準出力）
- 進捗情報は標準エラー出力

## 処理フロー

### 処理シーケンス

```
1. 初期化処理
   └─ コマンドライン引数パース、デバッグ機能無効化
2. 入力ファイル読み込み
   └─ parseReducerWorkItemでIR/MIRをロード
3. 出力タイプ決定
   └─ ビットコードか、テキストIRかを決定
4. TestRunner初期化
   └─ テスト環境のセットアップ
5. 初期興味深さテスト
   └─ 入力が「興味深い」ことを確認
6. デルタパス実行
   └─ runDeltaPassesで各削減パスを実行
7. 結果出力
   └─ 削減されたファイルを出力
```

### フローチャート

```mermaid
flowchart TD
    A[開始] --> B[コマンドライン引数パース]
    B --> C{--print-delta-passes?}
    C -->|Yes| D[パス一覧表示して終了]
    C -->|No| E[入力ファイル読み込み]
    E --> F{読み込み成功?}
    F -->|No| G[エラー終了]
    F -->|Yes| H[TestRunner初期化]
    H --> I{初期テスト成功?}
    I -->|No| J[興味深くないエラー]
    I -->|Yes| K[runDeltaPasses実行]
    K --> L[デルタパス反復]
    L --> M{複雑度低下?}
    M -->|Yes| L
    M -->|No| N[結果出力]
    N --> O[正常終了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 興味深さ保持 | 各削減ステップで興味深さテストを通過する必要がある | 常時 |
| BR-02 | 反復上限 | 最大反復回数に達するか、複雑度が低下しなくなるまで反復 | デルタパス実行時 |
| BR-03 | パス選択 | --delta-passesで特定パスのみ実行可能 | オプション指定時 |
| BR-04 | 入力形式自動判別 | ファイル拡張子から入力形式（IR/MIR）を判別 | -x未指定時 |
| BR-05 | デバッグ機能無効化 | デフォルトでクラッシュレポートとシンボル化を無効化 | --preserve-debug-environment未指定時 |

### 計算ロジック

デルタデバッグアルゴリズム：
- 各デルタパスは特定の要素（関数、基本ブロック、命令等）を削除候補として列挙
- 二分探索的に削除候補をテストし、興味深さを保持しながら最大限削減
- 複雑度スコア（getComplexityScore）が低下しなくなるまで反復

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

本ツールはデータベースを使用しない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| 1 | 入力エラー | 入力ファイルが指定されていない | ファイルを指定 |
| 1 | 設定エラー | --testオプションが指定されていない | テストスクリプトを指定 |
| 2 | 検証エラー | 入力が興味深さテストを通過しない | テストスクリプトを確認 |

### リトライ仕様

デルタパス内で各削減候補のテストを反復実行する。

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

該当なし（ファイル入出力処理）。

## パフォーマンス要件

デルタデバッグは興味深さテストを多数回実行するため、テストスクリプトの実行時間が全体の実行時間に大きく影響する。

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

- 外部プログラム（興味深さテスト）を実行するため、信頼できるスクリプトのみを使用すること
- デフォルトでコアファイル生成を抑制

## 備考

- bugpointの後継として設計された、より高速な削減ツール
- IR用とMIR用の異なるデルタパスセットを持つ

---

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

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

### 推奨読解順序

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

削減処理に使用される主要なデータ構造を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | ReducerWorkItem.h | `llvm/tools/llvm-reduce/ReducerWorkItem.h` | ReducerWorkItemクラス（削減対象の抽象化） |
| 1-2 | TestRunner.h | `llvm/tools/llvm-reduce/TestRunner.h` | TestRunnerクラス（テスト実行環境） |
| 1-3 | DeltaPass.h | `llvm/tools/llvm-reduce/DeltaPass.h` | DeltaPass構造体（各削減パスの定義） |

**読解のコツ**: ReducerWorkItemはIR/MIRの両方を扱う抽象化レイヤー。TestRunnerが外部テストスクリプトとの連携を担当。

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

処理の起点となるmain関数を読み解く。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | llvm-reduce.cpp | `llvm/tools/llvm-reduce/llvm-reduce.cpp` | main関数とコマンドラインオプション |

**主要処理フロー**:
1. **137-146行目**: InitLLVMとコマンドライン引数パース
2. **148-156行目**: --print-delta-passesの処理
3. **158-175行目**: 入力ファイルとテストの検証
4. **177-178行目**: デバッグ機能無効化
5. **183-184行目**: parseReducerWorkItemで入力読み込み
6. **195-197行目**: TestRunner初期化
7. **203-206行目**: 初期興味深さテスト
8. **209行目**: runDeltaPasses実行
9. **211-215行目**: 結果出力

#### Step 3: デルタパス管理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | DeltaManager.cpp | `llvm/tools/llvm-reduce/DeltaManager.cpp` | runDeltaPasses関数、パス選択ロジック |
| 3-2 | DeltaPasses.def | `llvm/tools/llvm-reduce/DeltaPasses.def` | IR/MIR用デルタパスの定義 |

**主要処理フロー**:
- **78-92行目**: IR_PassesとMIR_Passesの定義
- **94-109行目**: runAllDeltaPasses - 全パス実行
- **176-202行目**: runDeltaPasses - メイン反復ループ

#### Step 4: 個別デルタパスを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | deltas/ReduceFunctions.cpp | `llvm/tools/llvm-reduce/deltas/ReduceFunctions.cpp` | 関数削減パスの実装例 |
| 4-2 | deltas/Delta.cpp | `llvm/tools/llvm-reduce/deltas/Delta.cpp` | デルタデバッグの基本実装 |

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

```
main()
    │
    ├─ InitLLVM()
    ├─ cl::ParseCommandLineOptions()
    │
    ├─ printDeltaPasses() [--print-delta-passes時]
    │
    ├─ disableEnvironmentDebugFeatures()
    │
    ├─ parseReducerWorkItem()
    │      └─ IRReader / MIRParser
    │
    ├─ TestRunner::TestRunner()
    │
    ├─ ReducerWorkItem::isReduced()
    │      └─ (興味深さテスト実行)
    │
    └─ runDeltaPasses()
           ├─ handlePassList()
           └─ runAllDeltaPasses() / runDeltaPassName()
                  └─ runDeltaPass()
                         └─ Delta pass実装 (ReduceFunctions等)
```

### データフロー図

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

IR/MIRファイル  ───▶ parseReducerWorkItem() ───▶ ReducerWorkItem
                        │
                        ▼
テストスクリプト ───▶ TestRunner
                        │
                        ▼
                  runDeltaPasses()
                        │
                        ├─ 要素削除候補生成
                        │
                        ├─ 興味深さテスト実行
                        │
                        └─ 成功時: 削減版を保持
                              │
                              ▼
                        writeOutput()  ───▶ 削減結果
                                            (ファイル)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| llvm-reduce.cpp | `llvm/tools/llvm-reduce/llvm-reduce.cpp` | ソース | メインエントリーポイント |
| DeltaManager.cpp | `llvm/tools/llvm-reduce/DeltaManager.cpp` | ソース | デルタパス管理 |
| DeltaManager.h | `llvm/tools/llvm-reduce/DeltaManager.h` | ヘッダー | パス管理インターフェース |
| TestRunner.cpp | `llvm/tools/llvm-reduce/TestRunner.cpp` | ソース | テスト実行実装 |
| TestRunner.h | `llvm/tools/llvm-reduce/TestRunner.h` | ヘッダー | テスト実行インターフェース |
| ReducerWorkItem.cpp | `llvm/tools/llvm-reduce/ReducerWorkItem.cpp` | ソース | 削減対象実装 |
| ReducerWorkItem.h | `llvm/tools/llvm-reduce/ReducerWorkItem.h` | ヘッダー | 削減対象インターフェース |
| DeltaPasses.def | `llvm/tools/llvm-reduce/DeltaPasses.def` | 定義 | デルタパス一覧 |
| deltas/*.cpp | `llvm/tools/llvm-reduce/deltas/` | ソース | 各種デルタパス実装 |
