0. RyuJITチュートリアル - RyuJITの歴史とアーキテクチャ

RyuJIT は .NET の JIT コンパイラであり、IL コードを実行可能な機械語コードに変換する役割を担っています。

このシリーズは RyuJIT チュートリアルとして、複数回に分けて公開予定です。.NET コンパイラに興味がある方や、.NET の JIT コンパイラ開発に参加したい方に参考となる資料を提供することを目的としています。

とはいえ、実際には私がコミュニティで RyuJIT 開発に関わる中で得た経験や見解を共有する形になります。何かの参考になれば幸いです。内容に不備がありましたらご容赦ください。

## はじめに

RyuJIT は、元々「JITBlue」とも呼ばれ、マイクロソフトが 2014 年頃に .NET 用に開発した次世代 JIT コンパイラです。「Ryu」は日本語の「竜（りゅう）」から取られており、コンパイラの古典的な名著「ドラゴンブック」へのオマージュとも言えます。

.NET 自体は 20 世紀末に誕生したプラットフォームで、当時から使われてきた従来の JIT コンパイラが約 20 年間稼働していました。それにもかかわらず、新しい JIT が必要になったのはなぜでしょうか？その背景には、技術的な進化と .NET の歴史があります。

### 歴史的背景

.NET の最初の JIT コンパイラは「JIT32」と呼ばれており、その名の通り 32 ビットアーキテクチャ向けに設計されたものです。このコンパイラの歴史は 1996 年にさかのぼります。当時は 32 ビットが主流であり、それ以外のアーキテクチャはほとんど考慮されていませんでした。JIT32 は非常に軽量で、良質なコード生成が可能でした。

しかし、21 世紀に入ると IA64 アーキテクチャが登場し、.NET は 64 ビットサーバーでも動作する必要が生じました。このため、マイクロソフトは C++ コンパイラのバックエンド「UTC（Universal Tuple Compiler）」を最適化エンジンとして採用しました。その結果、IA64 に対応する一方で、リソース集約型のコンパイラが誕生し、多くの計算資源を必要とするようになりました。

その後、AMD64 アーキテクチャが誕生しましたが、IA64 用のコンパイラを AMD64 に単純移植する形で「JIT64」が誕生しました。この JIT64 はその後 10 年以上にわたり利用され続けました。しかし、64 ビットはサーバー専用のアーキテクチャではなくなり、個人用コンピューターでも普及するようになりました。

さらに、2010 年頃に Windows RT を ARM デバイス上で動作させる試みがあり、.NET も ARM32 をサポートする必要が生じました。しかし、リソースの限られた端末向けには、JIT32 を ARM32 に移植する選択肢しかありませんでした。移植には多大な労力がかかりましたが、結果的にはコード品質はあまり良いものではありませんでした。「動けば良い」といった状況でした。

そして 2012 年には ARM64 の登場が迫ってきました。この時点で次のような問題が明らかになっていました。

- x86 用の JIT32 は時代遅れ
- x64 用の JIT64 はコンパイルが遅く、リソース消費が激しい
- ARM32 用の JIT32 はコード品質が低く、改善が困難

このような状況の中で、ARM64 用の JIT をどのように実装するかが課題となりました。どの既存のコンパイラも現代の JIT の要件を満たしていませんでした。

このような背景から、RyuJIT（JITBlue）プロジェクトがスタートしました。新しい JIT を開発するからには、最新のアーキテクチャに対応する必要がありました。RyuJIT の目標は次の通りです。

- 高品質なコード生成（高パフォーマンス）
- 高いスループット（コンパイルの高速化）
- すべてのアーキテクチャで一貫した予測可能な性能

これを実現するために、最新のコンパイラアーキテクチャを採用しました。

- SSA（Static Single Assignment）ベースの最適化アルゴリズム
- 型情報を活用する VN（Value Numbering）
- SIMD などの新機能に対応する単一コードベース
- アーキテクチャ固有部分（lowering、codegen）の分離

など、多くの工夫が取り入れられています。

### RyuJIT

RyuJIT は、JIT32 のツリー型 IR（中間表現）構造を再利用しつつ、フロントエンドの大部分を再設計しました。ツリー型の IR を採用することで、Rationalization（合理化）ステップにおいて、ツリー型 IR を線形 IR に変換し、改良されたバックエンドに引き渡す設計となっています。バックエンドのレジスタ割り当てでは、JIT64 のようなグラフ彩色アルゴリズムではなく、LSRA（Linear Scan Register Allocation） を採用し、コンパイル速度の向上を図りました。

興味深いエピソードとして、RyuJIT の初期構想では、フロントエンドの大部分を再設計し、Rationalization 後に旧 JIT32 のバックエンドをそのまま使う計画でした。しかし、開発を進めるうちに、これは完全に誤った選択であることが判明しました。結局、バックエンドも新規に開発することになり、現在のアーキテクチャが確立されたのです。

旧 JIT64 は線形 IR をベースにしていました。これは UTC（Universal Tuple Compiler）が線形 IR に特化していたためです。ただし、IL を線形 IR に変換する際には多大なオーバーヘッドが発生していました。一方、RyuJIT は最初から IL をツリー型 IR としてインポートします。この手法は線形 IR よりもはるかに軽量で、高速なコンパイルを可能にしました。ツリー型 IR を活用することで、RyuJIT はより効率的なコード生成を行えるようになったのです。

RyuJIT では、静的単一代入形式（SSA: Static Single Assignment） を基盤とした最適化アルゴリズムが採用され、従来の字句的（Lexical）なアルゴリズムから意味的（Semantic）なアプローチへと進化しました。これにより、より洗練された最適化が可能になりました。

特に VN（Value Numbering） ベースの最適化技術の導入により、RyuJIT はコードの品質向上に成功しました。VN は SSA を基盤とするため、RyuJIT はさまざまな線形または準線形アルゴリズムを適用でき、コンパイル速度と最適化効率の両方を大幅に向上させることができました。

## アーキテクチャ  

RyuJIT は設計上、ランタイムから完全に独立した独立型のコンパイラコンポーネントとして構築されています。これは特定のランタイム実装に依存しないため、RyuJIT を他のプロジェクトに統合して使用することが非常に容易です。  

この特性を生かして、いくつかの興味深いプロジェクトが誕生しました。例えば：  

- **Pyjion:** RyuJIT を利用して Python に JIT コンパイル機能を追加するプロジェクト  
- **CoreRT/NativeAOT:** RyuJIT をコード生成エンジンとして使用する AOT（Ahead-of-Time）コンパイラ  
- **NativeAOT-LLVM:** RyuJIT と LLVM を組み合わせ、IL を WebAssembly のネイティブコードに変換するプロジェクト  

RyuJIT は **マルチアーキテクチャ対応**、**優れたコンパイル速度**、**高品質なコード生成** を兼ね備えており、高性能なコンパイラとして非常に魅力的です。コンパイルの速さと生成コードの性能のバランスをうまく取っているため、JIT コンパイラだけでなく AOT コンパイラとしても活用可能です。  

実際、「JIT」という名前が付いているものの、そのモジュール化された設計により、AOT コンパイラへの組み込みも問題なく行えます。この汎用性の高さが RyuJIT の強みと言えるでしょう。  

## コンパイルのフェーズ  

RyuJIT のコンパイルプロセスは、いくつかのフェーズ（Phase）に分かれており、全体のコンパイルフローは次のようになります：  

![overview.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/638932/87ad757d-9c86-8503-a033-0cd567e42d47.png)

`Importer` から `Rationalization` までがRyuJIT のフロントエンド、`Lowering` から `Emitter` までが RyuJIT のバックエンドとして機能します。  

### Importer 

IL コードは最初に Importer によって RyuJIT の IR（中間表現）にインポートされます。  
この段階でさまざまな組み込み関数（intrinsics）が展開されます。  

### Inliner

メソッド呼び出しがインライン化（Inlining）されるかどうかを判断します。この段階では、さまざまなヒューリスティクス（経験則）を用いて、メソッドをインライン化するメリットを計算し、実行するかを決定します。  

### Morph

このフェーズでは、基本ブロック（BB）に対してさまざまな変換が行われ、後続の最適化フェーズに備えます。  

- ポインタ解析: オブジェクトの配置先がヒープかスタックかを決定  
- デッドコード削除: 不要なコードやアドレスの公開を削除  
- 使用-定義（Use-Def）グラフの構築: `forward substitution`、`physical promotion`、`copy omission` などの最適化に必要されます
- GS Cookie 挿入: セキュリティ保護用の Cookie を挿入  
- `QMARK` と `COLON` の展開: 条件式の評価を基本ブロックに展開  

### Loop Optimizations

このフェーズではループ最適化が行われます。  

- ループ検出と変換: ループの構造を分析して最適化  
- 代表的な最適化:
  - `loop inversion`（ループ反転）  
  - `loop cloning`（ループ複製）  
  - `loop unrolling`（ループ展開）  

また、不必要な `try-catch-finally` ブロックの削除も試みられます。  

### SSA および VN ベースの最適化

SSA（Static Single Assignment） と VN（Value Numbering）を使用してデータフロー解析を行います。  

- VN ベースの最適化
  - `loop invariants hosting`（ループ不変式の昇格）  
  - `copy propagation`（コピー除去）  
  - `branch removal`（不要な分岐の削除）  
  - `CSE`（共通部分式削除）  
  - `assertion propagation`（アサーションの伝搬）  
  - `bounds check elimination`（境界チェックの削除）  
  - `induction variable optimization`（誘導変数の最適化）  
  - `dead-store removal`（不要なストアの削除）  

この段階では `try-catch-finally` ブロックの除去や、型キャスト、静的メンバーの初期化とスレッドローカルアクセスのインライン化なども行われます。  
ブール式の簡略化や `switch` の検出も実施され、`jump table` への展開のために必要な情報を備えます。  

### Rationalization

このフェーズでは IR の線形表現を構築し、IR をツリー型のままツリー探索もできるようにしつつ、線形 IR としても扱えるようにします。この線形 IR は、バックエンドのすべてのフェーズで使用されます。  

- `COMMA` 演算子や `statement` の削除により、基本ブロック（BB）の実行順序が完全に `GenTree` のリンクリストによって表現されるようになります。  
- このフェーズ後の RyuJIT IR は、LLVM IR に簡単に変換可能です。  

### Lowering

IR を実行順序に従って遍歴し、`jump table` の展開やアドレッシングモードの計算を行います。各ノードに対してレジスタの要求と制約を計算し、次のレジスタ割り当てフェーズに備えます。  

このフェーズはアーキテクチャ固有であり、ターゲットとなる CPU ごとに独自の実装が存在します。  

### Register Allocation

レジスタ割り当てを行うフェーズです。ここでは、効率の良い線形スキャン（LSRA: Linear Scan Register Allocation）アルゴリズムを使用して、各命令に対して適切なレジスタを割り当てます。  

### Code Generation

最後はコード生成（Code Generation）のフェーズです。  

- フレームレイアウトの決定: スタックフレームの構造を決定  
- コード生成: 実行順序に従って各ブロックを遍歴し、コードと GC、デバッグ情報を生成  
- プロローグとエピローグの生成: 関数の開始と終了のためのコードを出力  

このフェーズもアーキテクチャ固有で、各プラットフォームごとに異なる実装が用意されています。  

## アーキテクチャの分離設計  

現在の RyuJIT は、次のような広範なアーキテクチャのサポートを提供しています：  

- x86 / x64
- ARM32 / ARM64
- LoongArch64
- RISC-V64

前述したアーキテクチャ固有部分の分離設計を思い出してください。この設計によって、新しいアーキテクチャやプラットフォームのサポートを RyuJIT に追加することが非常に簡単になっています。  

また、前述のNativeAOT-LLVM プロジェクトは、この分離設計の良い例です。  

このプロジェクトでは、Rationalization フェーズ後の RyuJIT IR を LLVM IR に変換し、LLVM のコンパイラバックエンドを活用してコードの最適化を行っています。

さらに、Lowering と Code Generation フェーズのインターフェースを使用して WebAssembly プラットフォーム向けの実装を独自に作成しました。これにより、RyuJIT と LLVM の両方の最適化を享受できると同時に、RyuJIT に WebAssembly サポートを拡張することにも成功しました。  

## 結びに  

今回はここまでとします。  

JIT コンパイラは非常に複雑なプロジェクトであり、ランタイムとの多岐にわたる相互作用を伴います。次回以降の記事では、次のトピックを取り上げる予定です：  

- RyuJIT とランタイムの連携や型システムのリクエスト方法  
- RyuJIT 開発のツールチェーンとワークフロー  
- 実際の例を用いた主要なコンパイルフェーズの紹介
- 主要な最適化の仕組み

これらのトピックを順に掘り下げていきますので、どうぞお楽しみに！