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 を呼び、元データに関数呼び出し関係を既に宣言している場合、コンパイラは検出されてエラーを報告可能。未宣言の場合、実行時にデッドロックが発生する可能性があります。

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

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

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 に対応）。
  • 条件変数と2つの分岐の出力を入力とする 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 アリーナメモリアロケーション

動的に生成された大量の一時ノード（ループ反復など）に対して、アリーナアロケータを使用：

• ループ展開ごとに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 両端キュー