# 機能設計書 53-llvm-sim

## 概要

本ドキュメントは、LLVMプロジェクトにおけるllvm-simツールの機能設計を記述する。llvm-simは、LLVMモジュール内で類似したコードセクションを検出し、その結果をJSON形式でエクスポートするツールである。

### 本機能の処理概要

llvm-simは、LLVM中間表現（IR）の類似性識別機能を活用して、モジュール内の類似コード領域を検出するコマンドラインツールである。コードクローン検出やリファクタリング支援のために、構造的に類似した命令シーケンスを特定し、その情報をJSON形式で出力する。

**業務上の目的・背景**：大規模なコードベースでは、類似したコード（コードクローン）が複数箇所に存在することがある。これらを検出することで、コードの共通化やリファクタリングの対象を特定できる。また、コンパイラ最適化の観点からは、類似コードをマージすることでコードサイズを削減できる可能性がある。llvm-simはIRレベルで類似性を検出することで、ソースコードの表記に依存しない本質的な類似性を発見できる。

**機能の利用シーン**：
- コードクローン検出によるリファクタリング対象の特定
- 関数マージ最適化の候補探索
- コードベースの品質分析
- 重複コードの削減によるバイナリサイズ最適化

**主要な処理内容**：
1. LLVM IRファイルの読み込みとパース
2. 各命令に対する位置番号の付与
3. IRSimilarityIdentifierによる類似性検出
4. 検出された類似グループのJSON形式エクスポート
5. 結果ファイルの出力

**関連システム・外部連携**：
- LLVMのIRSimilarityIdentifier解析パスとの連携
- llvm-linkツールとの併用（複数モジュールをマージして解析）

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

## 関連画面

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

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| N/A | コマンドライン | 主画面 | 入力ファイルの指定、JSON出力の生成 |

## 機能種別

解析処理 / 類似性検出

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| InputSourceFile | string | No | 解析対象のIRファイルパス（省略時は標準入力） | ファイルが存在すること |
| -o | string | No | 出力ファイルパス（省略時は標準出力） | - |

### 入力データソース

- LLVM IRファイル（.ll：テキスト形式、.bc：ビットコード形式）
- 標準入力からのIRストリーム

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| SimilarityGroups | JSON | 類似コード領域のグループ情報 |

### 出力フォーマット

```json
{
  "1": [
    {"start": 10, "end": 25},
    {"start": 50, "end": 65}
  ],
  "2": [
    {"start": 100, "end": 110},
    {"start": 200, "end": 210}
  ]
}
```

各類似グループは数字キー（"1", "2", ...）で識別され、同一グループ内の各エントリは開始・終了の命令番号を持つ。

### 出力先

- 指定ファイルまたは標準出力

## 処理フロー

### 処理シーケンス

```
1. 初期化処理
   └─ InitLLVMによるコマンドライン引数パース
2. IRファイル読み込み
   └─ parseIRFileでモジュールを読み込み
3. 命令番号付与
   └─ 全命令（デバッグ情報除く）に連番を付与
4. 類似性検出
   └─ IRSimilarityIdentifier::findSimilarity()実行
5. JSON出力生成
   └─ 各類似グループをJSON形式に変換
6. ファイル出力
   └─ ToolOutputFileで結果を書き込み
```

### フローチャート

```mermaid
flowchart TD
    A[開始] --> B[コマンドライン引数パース]
    B --> C[IRファイル読み込み]
    C --> D{読み込み成功?}
    D -->|No| E[エラー終了]
    D -->|Yes| F[命令番号マップ作成]
    F --> G[各関数・基本ブロック・命令を走査]
    G --> H[IRSimilarityIdentifier初期化]
    H --> I[findSimilarity実行]
    I --> J[JSON出力ファイル作成]
    J --> K[類似グループをJSON形式で出力]
    K --> L{出力成功?}
    L -->|No| M[エラー終了]
    L -->|Yes| N[正常終了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | デバッグ情報除外 | デバッグ用命令は番号付与・類似性検出の対象外 | 常時 |
| BR-02 | 命令番号は1から開始 | 最初の命令に番号1を割り当て、以降連番 | 常時 |
| BR-03 | 類似グループ番号 | 検出順に1から連番で付与 | 類似グループ出力時 |
| BR-04 | 複数モジュール対応 | 複数モジュールを比較する場合はllvm-linkで事前マージ | 複数ファイル比較時 |

### 計算ロジック

- IRSimilarityIdentifierは、命令の構造的類似性（オペコード、オペランドタイプ、制御フロー構造等）を考慮して類似領域を特定する
- 最小類似長やその他のパラメータはIRSimilarityIdentifierのデフォルト値を使用

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

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

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| file_not_found | 入力エラー | 指定ファイルが存在しない | ファイルパスを確認 |
| parse_error | 解析エラー | IRファイルの形式が不正 | 正しいIRファイルを使用 |
| output_error | 出力エラー | 出力ファイルの作成に失敗 | 出力パスとパーミッションを確認 |

### リトライ仕様

リトライ処理は実装されていない（単発実行ツール）。

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

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

## パフォーマンス要件

特に明示的な性能要件はないが、IRSimilarityIdentifierの類似性検出アルゴリズムは命令数に依存した計算量を持つ。

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

- ファイル読み書き権限を必要とする
- 不正な形式のファイルに対してはエラーを返す

## 備考

- 複数モジュール間の類似性を検出する場合は、先にllvm-linkでモジュールをマージする必要がある
- 出力JSONは可視化ツールとの連携を想定している

---

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

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

### 推奨読解順序

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

類似性検出に使用される主要なデータ構造を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | IRSimilarityIdentifier.h | `llvm/include/llvm/Analysis/IRSimilarityIdentifier.h` | IRSimilarityCandidate、SimilarityGroup等の定義 |

**読解のコツ**: IRSimilarityIdentifierはLLVMの解析パスであり、SimilarityGroupList型が類似グループのリストを表す。

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

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | llvm-sim.cpp | `llvm/tools/llvm-sim/llvm-sim.cpp` | main関数と全体処理フロー |

**主要処理フロー**:
1. **108-111行目**: InitLLVMとコマンドライン引数パース
2. **113-121行目**: IRファイルの読み込みとエラー処理
3. **125-133行目**: 命令番号マップの作成（LLVMInstNum）
4. **136-138行目**: IRSimilarityIdentifierによる類似性検出
5. **140-145行目**: exportToFile関数で結果出力

#### Step 3: 命令番号付与処理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | llvm-sim.cpp | `llvm/tools/llvm-sim/llvm-sim.cpp` | 命令番号マッピング（129-133行目） |

**主要処理フロー**:
- **129行目**: InstructionNumber = 1 で初期化
- **130-133行目**: 三重ループで全命令を走査
- instructionsWithoutDebug()でデバッグ命令を除外

#### Step 4: JSON出力処理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | llvm-sim.cpp | `llvm/tools/llvm-sim/llvm-sim.cpp` | exportToFile関数（61-106行目） |

**主要処理フロー**:
- **66-69行目**: ToolOutputFileで出力ファイル作成
- **71行目**: json::OStreamでJSONストリーム初期化
- **74-100行目**: 類似グループをJSONオブジェクトとして出力
- **103行目**: Out->keep()でファイルを確定

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

```
main()
    │
    ├─ InitLLVM()
    ├─ cl::ParseCommandLineOptions()
    │
    ├─ parseIRFile()
    │      └─ SMDiagnostic (エラー報告)
    │
    ├─ 命令番号マップ作成
    │      └─ Function -> BasicBlock -> Instruction ループ
    │
    ├─ IRSimilarityIdentifier::findSimilarity()
    │
    └─ exportToFile()
           ├─ ToolOutputFile()
           ├─ json::OStream
           ├─ getPositionInModule()
           └─ Out->keep()
```

### データフロー図

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

IRファイル      ───▶ parseIRFile()        ───▶ Module
(.ll/.bc)             │
                      ▼
                命令番号マップ作成
                      │
                      ▼
              IRSimilarityIdentifier
              ::findSimilarity()
                      │
                      ▼
              SimilarityGroupList
                      │
                      ▼
              exportToFile()         ───▶ JSON出力
                                          (ファイル/stdout)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| llvm-sim.cpp | `llvm/tools/llvm-sim/llvm-sim.cpp` | ソース | メインエントリーポイント |
| CMakeLists.txt | `llvm/tools/llvm-sim/CMakeLists.txt` | ビルド設定 | ビルド構成の定義 |
| IRSimilarityIdentifier.h | `llvm/include/llvm/Analysis/IRSimilarityIdentifier.h` | ヘッダー | 類似性検出クラス定義 |
| IRSimilarityIdentifier.cpp | `llvm/lib/Analysis/IRSimilarityIdentifier.cpp` | ソース | 類似性検出実装 |
