# 機能設計書 79-型推論

## 概要

本ドキュメントは、Julia言語における型推論エンジンの設計を記述する。抽象解釈（abstract interpretation）ベースの型推論エンジンによって、コンパイル時に関数の引数型から戻り値型や中間変数の型を推論する機能を提供する。

### 本機能の処理概要

型推論機能は、Juliaコンパイラの中核コンポーネントであり、ソースコードの低レベルIR（CodeInfo）に対して抽象解釈を適用し、各SSA値と変数の型情報を推論する。推論結果はコード最適化（インライン化、定数畳み込み、デッドコード除去等）と効率的なネイティブコード生成の基盤となる。

**業務上の目的・背景**：Juliaは動的型付け言語でありながら静的型付け言語に匹敵する性能を目指している。これを実現するための鍵が型推論エンジンである。関数呼び出し時に引数の具象型が確定すると、型推論エンジンがメソッド本体の全ての式の型を推論し、これにより型特化されたネイティブコードの生成が可能となる。型推論の精度がJuliaの実行性能を直接左右する。

**機能の利用シーン**：JITコンパイル時の自動型推論（ユーザーが意識せずに実行される）、`@code_typed`による推論結果の確認、`Base.return_types`による戻り値型の取得、コンパイラ開発でのデバッグなどで使用される。

**主要な処理内容**：
1. `abstract_call_gf_by_type` - ジェネリック関数呼び出しの抽象的評価
2. `abstract_call_method` - 個別メソッドの型推論
3. `abstract_call_method_with_const_args` - 定数引数による定数伝播
4. `typeinf` - メソッドインスタンスの型推論メインループ
5. `abstract_eval_statement` - 個別文の抽象評価
6. `abstract_eval_call` - 関数呼び出しの抽象評価
7. メソッドマッチング（find_method_matches）
8. 効果推論（副作用・例外・終了性のEffects解析）
9. 条件型（Conditional）の伝播
10. MustAlias による精密なフィールド型追跡

**関連システム・外部連携**：型格子（Type Lattice）、効果推論（Effects）、最適化パス（SSA IR最適化）、コード生成（LLVM codegen）と連携。

**権限による制御**：特別な権限制御はない。generated functionsからのコードリフレクションは制限される。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 2 | Juliaプロンプト（julia>） | 補助機能 | @code_warntype等で型推論結果を表示 |

## 機能種別

コンパイラ解析処理

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| interp | AbstractInterpreter | Yes | 抽象インタプリタ（通常NativeInterpreter） | 有効なインタプリタ |
| method | Method | Yes | 推論対象メソッド | 有効なメソッド |
| argtypes | Vector{Any} | Yes | 引数の型情報リスト | 型格子の要素 |
| sv | InferenceState | Yes | 推論状態 | 有効な推論コンテキスト |

### 入力データソース

- JITコンパイラからのメソッドコンパイル要求
- code_typed等のリフレクションAPIからの明示的な推論要求

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| rettype | Any | 推論された戻り値型 |
| exctype | Any | 推論された例外型 |
| effects | Effects | 推論された副作用情報 |
| code | CodeInfo | 型注釈済みIR |
| edge | CodeInstance | キャッシュ用のコードインスタンス |

### 出力先

- コンパイラの最適化パスへの入力
- コードキャッシュへの格納
- リフレクションAPIの戻り値

## 処理フロー

### 処理シーケンス

```
1. 推論要求の受付
   └─ typeinf(interp, frame) でInferenceStateを初期化
2. IRの各文を順次抽象評価
   └─ abstract_eval_statement で各SSA文を評価
3. 関数呼び出しの処理
   └─ abstract_eval_call → abstract_call_gf_by_type
4. メソッドマッチング
   └─ find_method_matches で候補メソッドを検索
5. 各メソッドの推論
   └─ abstract_call_method で個別メソッドを推論
6. 定数伝播の試行
   └─ abstract_call_method_with_const_args
7. 結果の合成
   └─ 全メソッドの結果をjoin（上界結合）
8. 効果の推論
   └─ Effects の合成と伝播
9. 条件型の伝播
   └─ Conditional / MustAlias の伝播
10. ワーカーリスト処理
    └─ 未処理の依存推論を再帰的に処理
```

### フローチャート

```mermaid
flowchart TD
    A[typeinf開始] --> B[InferenceState初期化]
    B --> C[IR文の走査ループ]
    C --> D{文の種類}
    D -->|call| E[abstract_eval_call]
    D -->|assign| F[型の更新]
    D -->|return| G[rettype合成]
    D -->|goto/branch| H[制御フロー解析]
    E --> I[abstract_call_gf_by_type]
    I --> J[find_method_matches]
    J --> K[abstract_call_method × N]
    K --> L{定数伝播可能?}
    L -->|Yes| M[abstract_call_method_with_const_args]
    L -->|No| N[結果使用]
    M --> O{改善された?}
    O -->|Yes| P[定数伝播結果を使用]
    O -->|No| N
    N --> Q[結果のjoin合成]
    Q --> R[Effects合成]
    R --> C
    G --> S[推論完了・結果キャッシュ]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-79-01 | ワールドエイジ | 推論はworld ageで有効なメソッドのみ考慮 | 全推論 |
| BR-79-02 | 再帰検出 | 再帰的呼び出しはLimitedAccuracyで近似される | 再帰関数 |
| BR-79-03 | Union分割 | Union引数型はmax_union_splittingまで分割して推論 | Union型引数 |
| BR-79-04 | 定数伝播条件 | const_propの結果がtype推論より精密な場合のみ使用 | const_prop |
| BR-79-05 | bail_out | トップレベルの非具象呼び出しは推論をスキップ | トップレベル |
| BR-79-06 | 型の単調性 | 推論結果は型格子上で単調に安定に収束する | 固定点計算 |

### 計算ロジック

型推論は抽象解釈（abstract interpretation）に基づく固定点計算である。各SSA値の型を型格子上の要素として表現し、IRの各文を抽象的に評価することで型を伝播する。制御フロー合流点ではjoin（上界結合）を取り、結果が収束するまでループする。

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

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

該当なし（ただし、推論結果はグローバルコードキャッシュに格納される）

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | 推論失敗 | マッチするメソッドなし | Any型を返す |
| - | 推論打ち切り | 再帰が深すぎる / 型が複雑すぎる | LimitedAccuracyまたはAnyに拡大 |
| - | bail_out | トップレベル非具象呼び出し | Any型を返す |

### リトライ仕様

推論の再試行はワークリスト駆動で自動的に行われる。LimitedAccuracyの原因が解消された場合、再推論が実行される。

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

該当なし

## パフォーマンス要件

- 型推論はJITコンパイルの主要なオーバーヘッドの一つ
- 推論結果はCodeInstanceとしてキャッシュされ、同じ型の再推論を回避
- max_methods パラメータで推論するメソッド数の上限を制御
- max_union_splitting でUnion分割の上限を制御

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

特になし（コンパイラ内部処理）

## 備考

- 型推論はJuliaのパフォーマンスの鍵であり、`@code_warntype`で推論結果を確認できる
- 推論精度が低い場合（型が`Any`として推論される場合）、実行時のパフォーマンスが大幅に低下する
- `Compiler/src/abstractinterpretation.jl` は数千行の大規模ファイルである

---

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

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

### 推奨読解順序

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

型推論に関わるデータ構造を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | abstractinterpretation.jl | `Compiler/src/abstractinterpretation.jl` | SlotRefinement（3-6行目）、FailedMethodMatch（49-51行目）、MethodMatchTarget（53-58行目）、MethodMatches（60-64行目）、CallInferenceState（92-107行目） |
| 1-2 | typelattice.jl | `Compiler/src/typelattice.jl` | Conditional / MustAlias / LimitedAccuracy 等の格子要素型 |

**読解のコツ**: 型推論のコアデータ構造は `CallInferenceState`（推論中の関数呼び出し状態）と `MethodMatches`（メソッドマッチング結果）。`rettype`、`exctype`、`all_effects` が推論で蓄積される主要な結果。

#### Step 2: メソッドマッチングと呼び出し解析を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | abstractinterpretation.jl | `Compiler/src/abstractinterpretation.jl` | abstract_call_gf_by_type（109-200行目）: ジェネリック関数呼び出しの推論メインルーチン。find_method_matchesでメソッド候補を取得し、各メソッドについてabstract_call_methodを呼び出す |

**主要処理フロー**:
1. **109-112行目**: 格子と部分順序の取得。`ipo_lattice`、`typeinf_lattice`
2. **119行目**: `find_method_matches` でメソッド候補を検索
3. **147-166行目**: 各メソッドに対して `abstract_call_method` を呼び出し
4. **167-199行目**: `handle1` - 定数伝播の試行、結果の合成

#### Step 3: 定数伝播を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | abstractinterpretation.jl | `Compiler/src/abstractinterpretation.jl` | abstract_call_method_with_const_args: 定数引数による精密な推論。const_prop結果がtype推論結果より精密な場合のみ使用 |

**主要処理フロー**:
- **177-198行目**: 定数伝播の結果判定。`this_const_rt ⊑ₚ this_rt` の場合に定数伝播結果を使用
- **194行目**: 効果のみが改善された場合も定数伝播結果を採用

#### Step 4: 条件型と精密な型伝播を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | abstractinterpretation.jl | `Compiler/src/abstractinterpretation.jl` | can_propagate_conditional（17-26行目）、propagate_conditional（28-39行目）: 条件分岐による型の精密化 |

**主要処理フロー**:
- **17-26行目**: `can_propagate_conditional` - InterConditional返り値で条件伝播可能か判定
- **28-39行目**: `propagate_conditional` - then/else分岐の型を更新

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

```
typeinf(interp, frame)
    │
    ├─ abstract_eval_statement(interp, stmt, sv)
    │      │
    │      ├─ abstract_eval_call(interp, stmt, ...)
    │      │      │
    │      │      └─ abstract_call_gf_by_type(interp, func, arginfo, ...)
    │      │             │
    │      │             ├─ find_method_matches(interp, argtypes, ...)
    │      │             │
    │      │             ├─ abstract_call_method(interp, method, sig, ...)
    │      │             │      └─ typeinf(interp, new_frame)  // 再帰
    │      │             │
    │      │             └─ abstract_call_method_with_const_args(...)
    │      │                    └─ typeinf(interp, new_frame)  // const-prop
    │      │
    │      ├─ abstract_eval_new(...)   // new文
    │      └─ abstract_eval_phi(...)   // phi文
    │
    └─ finish(interp, frame)
           └─ 結果キャッシュ
```

### データフロー図

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

Method +                  typeinf
argtypes ──────────▶     │
                         ├─ IR走査ループ
                         │    └─ abstract_eval_statement
                         │           │
                         │           ├─ abstract_call_gf_by_type
                         │           │      ├─ find_method_matches
                         │           │      ├─ abstract_call_method × N
                         │           │      └─ join(results)
                         │           │
                         │           └─ 型の更新
                         │
                         └─ 収束判定 ──────────────────▶ CodeInfo(型注釈済み)
                                                        rettype
                                                        exctype
                                                        Effects
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| abstractinterpretation.jl | `Compiler/src/abstractinterpretation.jl` | ソース | 型推論のメインロジック |
| typeinfer.jl | `Compiler/src/typeinfer.jl` | ソース | typeinf メインループとキャッシュ管理 |
| typelattice.jl | `Compiler/src/typelattice.jl` | ソース | 型格子の定義と操作 |
| typelimits.jl | `Compiler/src/typelimits.jl` | ソース | 型の複雑さ制限ヒューリスティクス |
| tfuncs.jl | `Compiler/src/tfuncs.jl` | ソース | 組み込み関数の型推論ルール |
| effects.jl | `Compiler/src/effects.jl` | ソース | 副作用推論 |
| inferencestate.jl | `Compiler/src/inferencestate.jl` | ソース | InferenceState型定義 |
