RFC-020：動的モジュールと FFI 統合

⚠️ 廃止：本文書は廃止され、内容は RFC-026: FFI コアメカニズム に統合されました。

参考:

• RFC-001: 並作モデルとエラー処理システム
• RFC-008: Runtime 並行モデルとスケジューラ疎結合設計
• RFC-018: LLVM AOT コンパイラと L3 透過的並行設計
• RFC-021: ライブラリ駆動 FFI 拡張と他言語呼び出しサポート

概要

本文書は RFC-001、008、018 を基礎として、YaoXiang の並行モデルをさらに詳細化・拡張し、動的モジュール読み込み、外部関数インターフェース（FFI）、およびより精緻なスケジューリング最適化といった実シナリオに対応する。中心となる設計には以下が含まれる：

1. 動的モジュールメタデータ契約：同一言語で記述された動的ライブラリにコンパイル時の依存記述を提供し、主プログラムが静的に DAG を構築しつつ透過的並行性を維持できるようにする。
2. FFI スケジューリングセマンティクス：外部関数は DAG 内でデフォルトで @block ノードとして扱われ、注釈により並列スケジューリングに組み込むこともできる（FFI ツールチェーンの詳細は RFC-021 を参照）。
3. 呼び出しコンテキストに基づく最適化：静的しきい値フォールバックに代わり、コンパイラは DAG における関数の実際の役割（コンシューマ数、副作用など）に基づき、インライン化するか独立ノードとしてスケジュールするかを智能的に決定する。
4. 制御フローと DAG の統合メカニズム：Phi ノードと動的展開を通じて、if、loop などの動的構造をデータフローグラフに自然に組み込む。
5. ランタイムスケジューラのメモリとパフォーマンス最適化：ノードのライフサイクル管理、領域割り当て、ロックフリーキューなどの低コストな抽象化実装を明確化する。

本文書は言語仕様を完成させ、YaoXiang の並行モデルが静的全体プログラム解析にも対応しつつ、動的性質や外部との相互作用にも柔軟に対応し、同時に高いパフォーマンスと開発体験を維持することを目指している。

動機

既存設計の不足

RFC-001/008/018 は洗練された透過的並行モデルを構築したが、現実世界の要求に対しては依然として以下の盲点がある：

• 動的モジュール：プログラムがプラグインや動的リンクライブラリをサポートする場合、主プログラムはコンパイル時にモジュール内部の呼び出し関係や依存を知ることができず、全体 DAG の構築が失敗する。
• FFI 呼び出し：外部関数（C ライブラリなど）は完全にブラックボックスであり、内部に並行処理、ブロッキング、副作用を含む可能性があり、それを通常のノードとして扱うと並行安全性が損なわれる。
• 小関数のスケジューリングオーバーヘッド：RFC-001 で提案された「L1 自動フォールバック」は静的しきい値（命令数 <50）を採用しており、暗黙のルールは開発者の挙動予測を困難にし、複雑な呼び出しコンテキストに適応できない。
• 制御フローと DAG の融合：if、loop などの動的構造の DAG 上での表現がまだ明確でなく、依存解析の正確性に影響する可能性がある。
• ランタイムオーバーヘッド制御：DAG ノード数の増加に伴い、スケジューラのメモリ管理とパフォーマンス最適化を明確化し、ボトルネック化を回避する必要がある。

目標

• 透過的並行という中核哲学を維持しつつ、動的モジュールと FFI に明確、安全、段階的なサポートを提供する。
• スケジューリング最適化を「暗黙の全体ルール」から「コンテキストに基づく智能的判断」へ転換し、予測可能性とパフォーマンスを向上させる。
• DAG の動的制御フロー表現を完成させ、すべてのプログラム構造がデータフローモデルに自然に組み込まれることを保証する。
• スケジューラのメモリ管理とパフォーマンス最適化戦略を明確化し、低コストな抽象化を実現する。

提案

1. 動的モジュールメタデータ契約

1.1 契約内容

YaoXiang でコンパイルされた各動的ライブラリ（.yxo / プラットフォーム固有の動的ライブラリ）には、メタデータ記述ファイル（.yxmeta）を添付する必要がある。これには以下が含まれる：

• エクスポート関数リスト：各関数の完全な型シグネチャ（引数、戻り値、リソースタグ）。
• 副作用タグ：コンパイラが自動導出した @pure / @io（開発者が明示的に上書きすることも可能）。
• リソース依存：各引数がリソース型（例：File）かどうか、戻り値に新しいリソースが含まれるか。
• 呼び出しグラフ要約（オプション）：その関数が呼び出す可能性のある他のエクスポート関数の ID。モジュール間循環依存検出に使用。
• 所有権情報：引数の所有権セマンティクス（借用/ムーブ）、戻り値の所有権。
• 並行安全性：Send/Sync の自動導出結果。

メタデータ形式はバイナリまたは構造化テキスト（例：MessagePack）とし、解析効率を保証する。

1.2 コンパイル時処理

主プログラムをコンパイルする際、動的モジュール関数への呼び出しに遭遇すると：

1. 対応するモジュールの .yxmeta ファイルを読み取る。
2. グローバル DAG 内にプレースホルダノードを作成し、メタデータから取得した入出力依存、副作用タグなどを記録する。
3. プレースホルダノードは通常ノードと同様に依存解析に参加し、スケジューラは実行順序を事前に計画できる。

1.3 ランタイムバインディング

動的モジュールの読み込み時：

• ランタイムで実際の関数シグネチャとメタデータの一致を検証する（バージョンミスマッチ防止）。
• プレースホルダノードと実際の関数ポインタをバインドする。

サブグラフスケジューリングセマンティクスについて：動的モジュールが独立したサブ DAG を持つ場合（例：モジュール自体が並行ロジックを含む）、そのサブグラフは独立したスケジューリングユニットとして実行される。その境界はモジュールのエクスポート関数によって定義される：エクスポート関数を呼び出すと、サブグラフが一つのまとまりとして実行開始され、その関数が戻るまで継続する。サブグラフ内部のノードスケジューリングはサブグラフ自身のスケジューラが担当し（モジュール内部では標準スケジューラを引き続き使用可能）、サブグラフと主 DAG のやりとりは入出力データフローのみに限定される。つまり主 DAG 内のプレースホルダノードはサブグラフの開始と終了のみを気にするのであり、その内部スケジューリングには介入しない。この設計はモジュールのカプセル化を保証しつつ、主 DAG の静的な完全性を維持する。

1.4 安全性保証

• 動的モジュールが契約に違反した場合（例：@pure を主張しつつグローバル状態を変更する）、結果は開発者が責任を負う（FFI の unsafe 境界と同様）。ただし同一言語のため、ランタイムチェック（メモリ分離など）でセキュリティを強化することは可能だが、オーバーヘッドが増加する。
• モジュール間循環依存：モジュール A が B を呼び出し、B が A を呼び出す場合でメタデータに呼び出し関係が宣言されていれば、コンパイラが検出してエラーを報告できる。宣言されていなければ、ランタイムでデッドロックが発生する可能性があり、スケジューラが検出して panic する。

2. DAG における FFI のスケジューリングセマンティクス

FFI の完全なツールチェーンサポート（動的ライブラリ読み込み、バインディング生成、型変換、メモリ所有権）は RFC-021 で定義されている。本節では FFI 呼び出しの DAG スケジューリングにおける振る舞いのみを記述する。

2.1 デフォルトのスケジューリング振る舞い

外部関数（native("symbol") で宣言）は DAG 内でデフォルトで @block ノード として扱われる：

• DAG 並列スケジューリングに参加せず、現在のスレッドで同期実行される。
• 実行中、スケジューラはその内部並行性に干渉しない。
• 戻り値は利用可能だが、呼び出し自体は依存辺を生成しない。

2.2 任意の並行注釈

開発者は注釈により FFI 呼び出しを DAG スケジューリングに組み込むことができる（詳細は RFC-021 §2.2 を参照）：

• @pure：通常の DAG ノードとして扱い、依存のない他のノードと並列実行可能。
• @io：リソース依存解析に参加し、同一リソースへの複数回の呼び出しを自動的に直列化する。

2.3 スケジューラへの影響

FFI ノードはスケジューラ内で通常のノードと同じ TaskNode 構造を使用し、違いは effect が Block にマークされている点のみ。スケジューラは Block ノードに遭遇すると並列スケジューリングをスキップし、直接同期実行する。

3. 呼び出しコンテキストに基づく最適化

RFC-001 の「L1 自動フォールバック」静的しきい値に代わり、コンパイラが各呼び出し点の DAG における実際のコンテキストに基づき智能的に判断する。

3.1 最適化の判断根拠

コンパイラは各関数呼び出しノードを解析する：

• コンシューマ数：そのノードの結果がいくつの下流ノードで使用されるか。1 ならインライン化候補の資格を持つ。1 より大きければ結果共有のため独立ノードとして保持する必要がある。
• 副作用：ノードに @io 副作用がある場合、順序保証のため独立ノードとして保持する必要がある。
• 計算量推定：命令数などのヒューリスティックを参考にはするが、硬直的なしきい値とはせず、インライン化の利益評価にのみ使用する。
• リソース依存：ノードがリソース変数（例：File）に関与し、そのリソース変数が上下流間で受け渡される場合、インライン化により依存チェーンが破壊される可能性があるため注意が必要。

3.2 インライン化操作

インライン化と決定した場合：

• そのノードの計算ロジックを唯一下流ノードのコードに直接埋め込む。
• DAG からそのノードを削除し、その入力を直接下流ノードの入力とする。
• 最終コード生成時、インライン化された関数は独立したスケジューリングユニットを生成しない。

3.3 インライン化の制限

• 再帰関数やループ本体内の呼び出しは通常インライン化せず、無限展開を防ぐ。
• モジュール境界をまたぐ（動的モジュール、FFI）関数はインライン化しない。
• 開発者は @noinline 注釈でインライン化を強制禁止したり、@forceinline でコンパイラにインライン化を試みるよう指示できる。

3.4 可観測性

コンパイラは最適化レポートを生成すべきである（--emit-optimization-report で有効化）。これには以下の情報を含む：

• 各インライン化ポイント：インライン化された関数名、呼び出し位置、インライン化の理由（例「唯一のコンシューマで純粋関数」）。
• 独立ノードとして保持された理由：例「複数のコンシューマがある」「副作用を含む」「モジュール間呼び出し」など。
• 判断統計：インライン化総数、保持ノード数。開発者が最適化効果を評価するのに役立つ。

レポート出力形式はテキストまたは JSON が可能で、ツールによる解析に適している。

4. 制御フローと DAG の統合

4.1 条件分岐（if）の処理

Phi ノード（SSA 形式を参考）を導入して分岐合流点を表現する：

• コンパイル時に各 if 式に対し以下を構築する：
  • 2 つの分岐サブ DAG（それぞれ then と else に対応）。
  • 1 つの Phi ノード。入力には条件変数と両分岐の出力を含む。
• Phi ノードのセマンティクス：条件変数が準備完了したら、その値に応じて対応する分岐の出力を自身の出力として選択する。
• ランタイムでは、Phi ノードは条件変数に依存する。条件が準備完了すると、選択された分岐の下流リストに自身を動的に追加し、その分岐の結果を待機する。

DAG の例：

        cond
       /    \
  then DAG  else DAG
       \    /
        Phi
         |
      後続ノード

4.2 ループ（loop/while）の処理

ループはフィードバック辺を持つサブ DAG として扱われ、ランタイムでオンデマンド展開される：

• コンパイル時にループ本体を識別し、ループテンプレートを構築する。含まれる要素：
  • 条件ノード。
  • ループ本体のサブ DAG。
  • イテレーション間で受け渡される状態変数。
• ランタイムでループ結果が必要になったとき（例：ループ終了後の累積値使用）、スケジューラが動的にイテレーションを展開する：
  1. 初回に条件ノードをスケジュールし、真なら最初のイテレーションのサブ DAG をインスタンス化する。入力には初期状態と外部変数を含む。
  2. イテレーション完了後、新しい状態が生成される。条件ノードを再度スケジュールする（新しい状態に依存）し、継続するかを決定する。
  3. 条件が偽になるまで繰り返し、最後のイテレーションの出力がループ結果となる。

複雑な例：ループ条件がループ本体内部の更新に依存する場合

let mut x = 0
while x < 10 {
    x = compute(x)  // x はループ本体で更新される
}

このパターンでは、条件ノード x < 10 はイテレーションごとに更新される x に依存する。DAG 表現は以下の通り：

• ループテンプレートは状態変数 x を含み、初期値は 0。
• 各イテレーション：まず条件ノードを実行（現在の x に依存）、真なら x = compute(x) を実行して新しい x を生成し、再び条件ノードに入る。
• ランタイムで上記フローに従い動的展開し、条件が偽になるまで継続する。

イテレーション間の依存は状態変数により自然にデータフローを形成し、依存のあるイテレーションは自動的に直列化され、依存のないイテレーションは並列化可能（例：map）。

4.3 無限ループの特別な処理

単一の無限ループは主 DAG として直接同期実行される（スケジューリングオーバーヘッドなし）。複数の無限ループはバックグラウンド DAG として、スケジューラが時分割で並行実行する。

5. ランタイムスケジューラのメモリとパフォーマンス最適化

5.1 ノードのライフサイクル管理

• 各ノードは参照カウント（アトミック変数）を維持し、その結果に依存するコンシューマ数を表す。
• ノード実行完了し結果を全下流に受け渡した後、参照カウントがゼロになり、ノードメモリを解放可能。
• 結果値自体も参照カウント（Arc<T>）を採用するが、最適化可能：結果が 1 人のコンシューマのみによって使用される場合、カウントオーバーヘッドを避けるため所有権を直接ムーブする。

5.2 領域メモリ割り当て（Arena）

動的に生成される大量の短寿命ノード（例：ループイテレーション）に対しては、領域アロケータを使用する：

• 1 回のループ展開に対して 1 つのメモリ領域を割り当てる。
• 領域内のノードは連続的に割り当てられ、全体として解放されるため、フラグメンテーションと解放オーバーヘッドを削減。
• 領域終了時、すべてのノードメモリを一括回収する。

5.3 ロックフリーデータ構造

• 依存カウンタ：AtomicUsize を使用し、fetch_sub でアトミックにデクリメント。
• レディキュー：Chase-Lev 両端キューを採用（各スレッドローカルキュー + ワークスティーリング）、ロック競合を削減。
• 下流リスト：作成後は読み取り専用とし、同時変更を回避。

5.4 適応スケジューリング

• システム内に無限ループが 1 つだけの場合、直接同期実行し、ゼロスケジューリングオーバーヘッド。
• タスク粒度とシステム負荷に基づき、並列度を動的に調整する（例：キューの長さを監視し、ワーカースレッド数を調整）。

5.5 低コスト抽象化原則

すべてのスケジューリングオーバーヘッドはタスク数に比例し、各タスクの追加オーバーヘッド（生成、キューイング、依存処理）は数十ナノ秒台に抑える。超細粒度タスクに対しては、インライン化最適化（第 3 節参照）でスケジューリングを回避する。

詳細設計

6.1 動的モジュールメタデータ形式（ドラフト）

// メタデータファイル構造（簡略化）
struct Metadata {
    version: u32,
    functions: Vec<FuncMeta>,
}

struct FuncMeta {
    name: String,
    signature: TypeSignature,
    effects: EffectTag,      // Pure | IO | Block
    resource_params: Vec<usize>, // 引数インデックスリスト。リソース型の引数を示す
    calls: Vec<String>,       // 呼び出される他のエクスポート関数名（オプション）
    ownership: OwnershipInfo,
    send_sync: SendSync,      // Send/Sync を満たすか
}

6.2 スケジューラコアデータ構造

struct TaskNode {
    id: TaskId,
    deps: Vec<TaskId>,                // 上流依存
    remaining_deps: AtomicUsize,
    inputs: Vec<Option<Value>>,
    result: Option<Value>,
    func: Executable,
    downstream: Vec<TaskId>,           // 下流ノード（作成後読み取り専用）
    effect: EffectTag,
    arena_id: Option<ArenaId>,         // 所属領域（オプション）
}

struct Scheduler {
    ready_queues: PerThreadQueue<TaskId>, // 各スレッドローカルキュー
    global_work_stealer: WorkStealer,
    arenas: ArenaAllocator,               // 領域アロケータ
}

6.3 コンテキストに基づく最適化解析

コンパイラは MIR 層で以下のステップを実行する：

1. グローバル呼び出しグラフとデータ依存グラフを構築。
2. 各関数呼び出しノードについて、その出次数（コンシューマ数）を計算。
3. 出次数が 1 で、関数が副作用なし（@pure）、かつ非再帰なら「インライン化候補」とマーク。
4. ヒューリスティック（例：命令数）を組み合わせてインライン化の利益を評価し、インライン化するか決定。
5. インライン化時、呼び出しノードのコードを下流に埋め込み、依存関係を更新。

6.4 制御フローノード表現

enum NodeKind {
    Normal(FuncId),
    Phi { cond: TaskId, then_branch: TaskId, else_branch: TaskId },
    LoopTemplate { cond: FuncId, body: FuncId, state_var: VarId },
    // ...
}

ランタイムで動的展開する際、LoopTemplate は一連の Normal ノードインスタンスを生成する。

トレードオフ

利点

• 動的モジュールの安全な統合：メタデータ契約により、動的ライブラリが主プログラムと並行モデルを共有しつつ、静的 DAG の完全性を維持できる。
• FFI の段階的な組み込み：開発者は外部関数に段階的に注釈を追加でき、安全なデグレードから高効率な並行へ移行可能。
• 最適化が予測可能：コンテキストに基づく判断が暗黙のしきい値に代わり、振る舞いが透明で、開発者はツールを通じて最適化を理解できる。
• 制御フローの自然な組み込み：Phi ノードと動的展開により、DAG がすべてのプログラム構造を表現でき、特別な構文は不要。
• スケーラブルなパフォーマンス：領域割り当て、ロックフリーキューなどの設計により、スケジューラが大規模並行処理に対応可能。

欠点

• メタデータ契約がコンパイルの複雑性を増加：動的ライブラリに対してメタデータを生成・解析する必要があり、ツールチェーンのサポートが必要。
• FFI 注釈が開発者の正確性に依存：誤った注釈はデータ競合を引き起こす可能性があり、ドキュメントとツールによるヒントでリスク低減が必要。
• コンテキスト最適化解析が時間を消費：全体解析はコンパイル時間を増加させる可能性があるが、増分コンパイルで緩和可能。
• 動的展開がランタイムオーバーヘッドを増加：ループ展開は動的ノード生成を必要とするが、領域割り当てで緩和可能。

実装戦略

段階区分（優先度提案を含む）

実装優先度の提案：初期段階で完璧な実装を追求する必要はなく、まず簡単な方案でシステムを動作させ、その後徐々に最適化すればよい。例えば：

• 参照カウントは直接 Arc を使用可能。
• ロックフリーキューは成熟したライブラリ（例：crossbeam の deque）を使用可能。
• 領域割り当てはまず単純な bump allocator を使用し、後で最適化。

段階 1：基本サポート（v0.7）

• [ ] FFI がデフォルトで @block にデグレードされるよう実装。
• [ ] FFI で使用する @pure、@io 注釈を追加。
• [ ] リソースラッパー型（例：File）とその基本メソッドを実装。

段階 2：動的モジュールメタデータ（v0.8）

• [ ] メタデータ形式を設計し、動的ライブラリに対して .yxmeta を生成するようコンパイラを修正。
• [ ] 主プログラムコンパイル時のメタデータ読み取りとプレースホルダノード作成を実装。
• [ ] ランタイムバインディング機構を実装。

段階 3：コンテキスト最適化（v0.9）

• [ ] 呼び出しグラフ解析を実装し、ノードの出次数を計算。
• [ ] インライン化判断とコード生成サポートを追加。
• [ ] 最適化レポート出力を実装（インライン化ポイント、理由などを含む）。

段階 4：制御フロー DAG 融合（v0.10）

• [ ] Phi ノードと条件分岐のコンパイル時表現を実装。
• [ ] ループテンプレートと動的展開ランタイムを実装。
• [ ] 無限ループのバックグラウンドスケジューリングを完成。

段階 5：パフォーマンス最適化（v1.0）

• [ ] 領域アロケータを実装。
• [ ] ロックフリーキューとワークスティーリングを最適化。
• [ ] ベンチマークとチューニング。

他の RFC との関係

• RFC-001：副作用処理と並行階層を拡張し、自動フォールバックをコンテキスト最適化で置換。
• RFC-008：動的モジュールと FFI のランタイムサポートを補足し、スケジューラの疎結合設計を維持。
• RFC-018：DAG 構築とスケジューラ実装を詳細化し、Phi ノードと動的展開を追加。

付録：設計決定記録

決定	決定内容	日付	記録者
動的モジュールがメタデータ契約を提供	メタデータファイル + ランタイムバインディングを採用	2026-03-14	晨煦
FFI がデフォルトで @block にデグレード	はい、開発者は段階的に注釈可能	2026-03-14	晨煦
コンテキスト最適化が静的しきい値を置換	出次数、副作用などに基づく智能的判断	2026-03-14	晨煦
条件分岐処理に Phi ノードを導入	SSA を参考、動的に分岐を選択	2026-03-14	晨煦
ループの動的展開	オンデマンドでイテレーションをインスタンス化、依存の直列化をサポート	2026-03-14	晨煦
短寿命ノードに領域割り当てを使用	メモリ効率とキャッシュ局所性を向上	2026-03-14	晨煦

参考文献

• RFC-001: 並作モデルとエラー処理システム
• RFC-008: Runtime 並行モデルとスケジューラ疎結合設計
• RFC-018: LLVM AOT コンパイラと L3 透過的並行設計
• RFC-021: ライブラリ駆動 FFI 拡張と他言語呼び出しサポート
• SSA 形式と Phi 関数
• Chase-Lev 両端キュー