# 機能設計書 82-最適化パス

## 概要

本ドキュメントは、Juliaコンパイラの最適化パス機能の設計を記述する。SSA IR（Static Single Assignment Intermediate Representation）上で動作する複数の最適化パスにより、インライン化・定数畳み込み・デッドコード除去・SROA（Scalar Replacement of Aggregates）などの最適化を実行する。

### 本機能の処理概要

最適化パスは、型推論完了後のSSA IRに対して一連の変換を適用し、実行時のパフォーマンスを向上させる。

**業務上の目的・背景**：Juliaは動的型付け言語であるが、コンパイル時にメソッドの特殊化と最適化を行うことでC言語に匹敵する実行速度を実現する。最適化パスは型推論結果を活用し、不要な計算の除去、関数呼び出しのインライン展開、データ構造の分解といった変換を行うことで、生成されるネイティブコードの品質を大幅に向上させる。

**機能の利用シーン**：最適化パスはJuliaの関数が初めて特定の型引数で呼び出された際のJITコンパイル時、および sysimage のAOTコンパイル時に自動的に実行される。開発者は `@code_typed` で型推論後のIRを、`@code_llvm` で最終的なLLVM IRを確認することで、最適化の効果を検証できる。

**主要な処理内容**：
1. `convert_to_ircode`: CodeInfo から SSA IR への変換
2. `slot2reg`: スロット変数からSSAレジスタへの変換
3. `compact!`: IRのコンパクション（不要な命令の除去・番号の再割当）
4. `ssa_inlining_pass!`: インライン化パス
5. `sroa_pass!`: SROA（構造体のスカラー分解）パス
6. `adce_pass!`: ADCE（Aggressive Dead Code Elimination）パス
7. `ipo_dataflow_analysis!`: 手続き間データフロー解析

**関連システム・外部連携**：型推論エンジン（No.79）から推論結果を受け取り、効果推論（No.81）の結果をIRフラグに反映する。最適化後のIRはコード生成（No.84）に渡される。

**権限による制御**：特になし。コンパイラ内部の自動処理である。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 本機能はコンパイラ内部機能であり、直接的なUI画面は存在しない |

## 機能種別

計算処理（コンパイラ内部のIR変換・最適化処理）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| CodeInfo | CodeInfo | Yes | 型推論済みのコード情報 | 有効なCodeInfoであること |
| OptimizationState | OptimizationState | Yes | 最適化状態（メソッドインスタンス、型情報等を含む） | - |
| InferenceResult | InferenceResult | Yes | 型推論結果 | - |

### 入力データソース

- 型推論エンジン（`abstractinterpretation.jl`）からの `InferenceResult`
- メソッドインスタンスに対応する `CodeInfo`

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| IRCode | IRCode | 最適化済みのSSA IR |
| CodeInfo | CodeInfo | IRCode からシリアライズ可能な CodeInfo に変換した最終出力 |
| inlining_cost | UInt8 | インライン化コスト（将来のインライン判定に使用） |

### 出力先

- `CodeInstance` に格納されてキャッシュされる
- コード生成フェーズ（`codegen.cpp`）に渡される

## 処理フロー

### 処理シーケンス

```
1. optimize() エントリーポイント
   └─ run_passes_ipo_safe() を呼び出し
2. CONVERT: CodeInfo → IRCode 変換
   └─ convert_to_ircode() でSSA形式のIRを生成
3. SLOT2REG: スロット→レジスタ変換
   └─ slot2reg() でスロット変数をSSA値に変換
4. COMPACT_1: 初回コンパクション
   └─ compact!() で不要命令を除去・番号再割当
5. INLINING: インライン化
   └─ ssa_inlining_pass!() で呼び出しサイトのインライン展開
6. COMPACT_2: 2回目コンパクション
   └─ インライン化後の不要命令を除去
7. SROA: 構造体のスカラー分解
   └─ sroa_pass!() で不要なallocを除去
8. ADCE: デッドコード除去
   └─ adce_pass!() で到達不能コードを除去
9. COMPACT_3: 3回目コンパクション（ADCEで変更があった場合のみ）
10. IPO解析: ipo_dataflow_analysis!
    └─ 手続き間データフロー解析と効果の最終確定
11. finishopt!: 最終処理
    └─ IRCode → CodeInfo への変換
```

### フローチャート

```mermaid
flowchart TD
    A[optimize: 開始] --> B[run_passes_ipo_safe]
    B --> C[CONVERT: CodeInfo → IRCode]
    C --> D[SLOT2REG: スロット → SSA]
    D --> E[COMPACT_1]
    E --> F[INLINING: インライン化]
    F --> G[COMPACT_2]
    G --> H[SROA: 構造体分解]
    H --> I[ADCE: デッドコード除去]
    I --> J{変更あり?}
    J -->|Yes| K[COMPACT_3]
    J -->|No| L[IPOデータフロー解析]
    K --> L
    L --> M[finishopt!: IRCode → CodeInfo]
    M --> N[完了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-82-01 | パス順序 | 各最適化パスは定められた順序で実行される（CONVERT→SLOT2REG→COMPACT→INLINING→COMPACT→SROA→ADCE） | 常時 |
| BR-82-02 | インライン化判定 | インライン化コストが閾値以下、または @inline 宣言がある場合にインライン展開される | INLINING パス |
| BR-82-03 | 効果ベース除去 | IR_FLAGS_REMOVABLE（effect_free & nothrow & terminates）が設定された未使用文は削除可能 | ADCE パス |
| BR-82-04 | 定数畳み込み | is_foldable な呼び出しは定数に畳み込まれる | INLINING/SROA パス |
| BR-82-05 | IR検証 | デバッグビルドでは最適化後にIRの整合性検証（verify_ir）が実行される | is_asserts() が true の場合 |

### 計算ロジック

インライン化コスト計算:
- `inlining_cost()` は CodeInfo からコスト値を取得
- `MAX_INLINE_COST` を超えるとインライン化されない
- `@inline` 宣言があると `MIN_INLINE_COST` が設定される

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

本機能はデータベースを使用しない。

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

該当なし。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | IR検証エラー | verify_ir が不正なIRを検出 | assert失敗（デバッグビルドのみ）。コンパイラバグとして報告 |
| - | 無効な optimize_until 引数 | 存在しないパス名が指定された | ArgumentError を throw |

### リトライ仕様

該当なし。

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

該当なし。

## パフォーマンス要件

- 各最適化パスはIRのサイズに対してほぼ線形時間で完了すべき
- compact! は全体で最大3回実行されるため、効率的な実装が重要
- インライン化はコードサイズ膨張を制御するためにコスト閾値を設定

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

- 最適化は意味保存変換であるべきで、プログラムの観測可能な動作を変更してはならない
- `@inbounds` による境界チェック除去はセキュリティリスクとなりうるが、効果推論の noub ビットで制御される

## 備考

- `optimize_until` パラメータにより、特定のパスまでで最適化を中断可能（テスト・デバッグ用）
- 各パスは `@pass` マクロで登録され、`ALL_PASS_NAMES` で列挙可能
- `@zone` マクロにより各パスのプロファイリングが可能

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | optimize.jl | `Compiler/src/optimize.jl` | IR フラグ定数（18-63行目）: IR_FLAG_CONSISTENT 等のビットフラグ定義 |
| 1-2 | optimize.jl | `Compiler/src/optimize.jl` | OptimizationState 構造体（201-254行目）: 最適化の全状態を保持 |
| 1-3 | optimize.jl | `Compiler/src/optimize.jl` | InliningState 構造体（154-166行目）: インライン化状態 |
| 1-4 | ir.jl | `Compiler/src/ssair/ir.jl` | IRCode のデータ構造定義 |

**読解のコツ**: `@pass` マクロ（1028-1038行目）は各最適化パスを登録するDSLであり、`@zone` でプロファイリングしつつ `optimize_until` による早期終了もサポートする。

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | optimize.jl | `Compiler/src/optimize.jl` | optimize 関数（1020-1025行目）: 最上位エントリーポイント |
| 2-2 | optimize.jl | `Compiler/src/optimize.jl` | run_passes_ipo_safe 関数（1044-1076行目）: パスの逐次実行 |

**主要処理フロー**:
1. **1020行目**: optimize() がエントリー、run_passes_ipo_safe() を呼出
2. **1056行目**: CONVERT パス（CodeInfo → IRCode）
3. **1057行目**: SLOT2REG パス
4. **1059行目**: COMPACT_1 パス
5. **1060行目**: INLINING パス
6. **1062行目**: COMPACT_2 パス
7. **1063行目**: SROA パス
8. **1064行目**: ADCE パス
9. **1065-1067行目**: ADCE で変更があれば COMPACT_3

#### Step 3: インライン化パスを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | inlining.jl | `Compiler/src/ssair/inlining.jl` | ssa_inlining_pass! 関数（73-80行目）: インライン化の全体フロー |
| 3-2 | inlining.jl | `Compiler/src/ssair/inlining.jl` | InliningTodo 構造体（10-27行目）: インライン化候補の表現 |
| 3-3 | inlining.jl | `Compiler/src/ssair/inlining.jl` | UnionSplit 構造体（55-63行目）: Union型の分割インライン化 |

#### Step 4: SROAパスを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | passes.jl | `Compiler/src/ssair/passes.jl` | SSADefUse 構造体（28-47行目）: mutabale structの使用/定義追跡 |
| 4-2 | passes.jl | `Compiler/src/ssair/passes.jl` | compute_live_ins 関数（49-56行目）: 生存区間の計算 |

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

```
optimize()
    |
    +-- run_passes_ipo_safe()
    |      +-- convert_to_ircode()
    |      +-- slot2reg()
    |      +-- compact!()
    |      +-- ssa_inlining_pass!()
    |      |      +-- assemble_inline_todo!()
    |      |      +-- batch_inline!()
    |      +-- compact!()
    |      +-- sroa_pass!()
    |      +-- adce_pass!()
    |      +-- compact!() (条件付き)
    |      +-- verify_ir() (デバッグ時のみ)
    |
    +-- ipo_dataflow_analysis!()
    +-- finishopt!()
         +-- ir_to_codeinf!()
```

### データフロー図

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

CodeInfo          --> convert_to_ircode             --> IRCode (初期)
IRCode (初期)     --> slot2reg                      --> IRCode (SSA化)
IRCode (SSA化)    --> compact!                      --> IRCode (圧縮)
IRCode (圧縮)     --> ssa_inlining_pass!            --> IRCode (インライン済)
IRCode (IL済)     --> compact!                      --> IRCode (再圧縮)
IRCode (再圧縮)   --> sroa_pass!                    --> IRCode (SROA済)
IRCode (SROA済)   --> adce_pass!                    --> IRCode (DCE済)
IRCode (DCE済)    --> ir_to_codeinf!                --> CodeInfo (最終)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| optimize.jl | `Compiler/src/optimize.jl` | ソース | 最適化パスのメインループ・OptimizationState定義 |
| ssair/ir.jl | `Compiler/src/ssair/ir.jl` | ソース | IRCode データ構造の定義 |
| ssair/inlining.jl | `Compiler/src/ssair/inlining.jl` | ソース | インライン化パスの実装 |
| ssair/passes.jl | `Compiler/src/ssair/passes.jl` | ソース | SROA・ADCEパスの実装 |
| ssair/slot2ssa.jl | `Compiler/src/ssair/slot2ssa.jl` | ソース | スロット→SSA変換 |
| ssair/verify.jl | `Compiler/src/ssair/verify.jl` | ソース | IR検証 |
| ssair/EscapeAnalysis.jl | `Compiler/src/ssair/EscapeAnalysis.jl` | ソース | エスケープ解析 |
| ssair/irinterp.jl | `Compiler/src/ssair/irinterp.jl` | ソース | IR上の再推論 |
| ssair/basicblock.jl | `Compiler/src/ssair/basicblock.jl` | ソース | 基本ブロックデータ構造 |
| ssair/domtree.jl | `Compiler/src/ssair/domtree.jl` | ソース | 支配木の構築 |
| effects.jl | `Compiler/src/effects.jl` | ソース | 効果推論（IRフラグの元情報） |
