JIT Design and Implementation

この文書は、コード生成が完了し、最適化されていないLLVM IRが生成された後のJuliaのJITの設計と実装について説明しています。JITは、このIRを最適化して機械コードにコンパイルし、現在のプロセスにリンクしてコードを実行可能にする責任を負っています。

Introduction

JITは、コンパイルリソースの管理、以前にコンパイルされたコードの検索、新しいコードのコンパイルを担当しています。これは主にLLVMのOn-Request-Compilation（ORCv2）技術に基づいており、同時コンパイル、遅延コンパイル、別プロセスでのコードコンパイルの能力など、いくつかの便利な機能をサポートしています。LLVMはLLJITの形で基本的なJITコンパイラを提供していますが、Juliaは多くのORCv2 APIを直接使用して独自のカスタムJITコンパイラを作成しています。

Overview

Codegenは、型推論によって生成された元のJulia SSA IRから1つ以上のJulia関数のIRを含むLLVMモジュールを生成します（上記のコンパイラ図でtranslateとしてラベル付けされています）。また、コードインスタンスとLLVM関数名のマッピングも生成します。しかし、JuliaベースのコンパイラがJulia IRに対していくつかの最適化を適用したにもかかわらず、codegenによって生成されたLLVM IRにはまだ多くの最適化の機会が含まれています。したがって、JITが最初に行うステップは、LLVMモジュールに対してターゲット非依存の最適化パイプライン^[tdp]を実行することです。次に、JITはターゲット依存の最適化パイプラインを実行し、ターゲット固有の最適化とコード生成を含み、オブジェクトファイルを出力します。最後に、JITは生成されたオブジェクトファイルを現在のプロセスにリンクし、コードを実行可能にします。これらすべては、src/jitlayers.cppのコードによって制御されています。

現在、最適化-コンパイル-リンクパイプラインには、一度に1つのスレッドのみが入ることが許可されています。これは、私たちのリンカーの1つ（RuntimeDyld）によって課せられた制限によるものです。しかし、JITは同時最適化とコンパイルをサポートするように設計されており、RuntimeDyldがすべてのプラットフォームで完全に置き換えられたときに、リンカーの制限は解除されると予想されています。

Optimization Pipeline

最適化パイプラインはLLVMの新しいパスマネージャに基づいていますが、パイプラインはJuliaのニーズに合わせてカスタマイズされています。パイプラインはsrc/pipeline.cppで定義されており、以下に詳述するいくつかのステージを通じて進行します。

1. 初期の簡素化

   1. これらのパスは、主にIRを簡素化し、パターンを正規化するために使用され、後のパスがそれらのパターンをより簡単に特定できるようにします。さらに、分岐予測ヒントや注釈などのさまざまな内在的呼び出しは、他のメタデータや他のIR機能に低下されます。 SimplifyCFG（制御フローグラフの簡素化）、DCE（デッドコードの排除）、およびSROA（アグリゲートのスカラー置換）は、ここでの重要なプレーヤーのいくつかです。

2. 早期最適化

   1. これらのパスは通常安価であり、主にIR内の命令数を減らし、他の命令に知識を伝播させることに焦点を当てています。例えば、EarlyCSEは共通部分式の排除を行うために使用され、InstCombineおよびInstSimplifyは、操作をより安価にするためのいくつかの小さなピーphole最適化を実行します。

3. ループ最適化

   1. これらのパスはループを正準化し、簡素化します。ループはしばしばホットコードであり、ループ最適化はパフォーマンスにとって非常に重要です。ここでの主要なプレーヤーには LoopRotate、LICM、および LoopFullUnroll が含まれます。また、IRCE パスの結果として、特定の境界が決して超えられないことを証明できるため、いくつかの境界チェックの排除もここで発生します。

4. スカラー最適化

   1. スカラー最適化パイプラインには、GVN（グローバル値番号付け）、SCCP（スパース条件定数伝播）、およびもう一回の境界チェック除去など、いくつかの高コストだが強力なパスが含まれています。これらのパスは高コストですが、大量のコードを削除し、ベクトル化をはるかに成功させ、効果的にすることができます。いくつかの他の簡素化および最適化パスが、より高コストのものと交互に配置され、彼らが行う必要のある作業量を減らします。

5. ベクトル化

   1. Automatic vectorization は、CPU集中的なコードに対して非常に強力な変換です。簡単に言うと、ベクトル化は single instruction on multiple data (SIMD) の実行を可能にし、例えば8つの加算操作を同時に行うことができます。しかし、コードがベクトル化可能であり、かつベクトル化する価値があることを証明するのは難しく、これは主に事前の最適化パスに依存してIRをベクトル化する価値のある状態に整えることに依存しています。

6. 内因的低下

   1. Juliaは、オブジェクトの割り当て、ガーベジコレクション、例外処理などの理由から、いくつかのカスタムインタリンズを挿入します。これらのインタリンズは、最適化の機会をより明確にするために元々配置されましたが、現在はLLVM IRに低下され、IRが機械コードとして出力されることを可能にしています。

7. クリーンアップ

   1. これらのパスは最後のチャンスの最適化であり、融合乗算加算伝播や除算余り簡略化などの小さな最適化を実行します。さらに、半精度浮動小数点数をサポートしないターゲットでは、半精度命令がここで単精度命令に変換され、サニタイザサポートを提供するためのパスが追加されます。

Target-Dependent Optimization and Code Generation

LLVMは、特定のプラットフォームのTargetMachine内で、ターゲット依存の最適化と機械コード生成を同じパイプラインで提供します。これらのパスには、命令選択、命令スケジューリング、レジスタ割り当て、および機械コードの発行が含まれます。LLVMのドキュメントはこのプロセスの良い概要を提供しており、LLVMのソースコードはパイプラインとパスの詳細を確認するのに最適な場所です。

Linking

現在、Juliaは古いRuntimeDyldリンカーと新しいJITLinkリンカーの間を移行しています。JITLinkには、RuntimeDyldにはないいくつかの機能が含まれており、同時リンクや再入可能リンクなどがありますが、現在はプロファイリング統合の良好なサポートが欠けており、RuntimeDyldがサポートするすべてのプラットフォームをまだサポートしていません。時間が経つにつれて、JITLinkはRuntimeDyldを完全に置き換えることが期待されています。JITLinkに関する詳細はLLVMのドキュメントに記載されています。

Execution

コードが現在のプロセスにリンクされると、それは実行可能になります。この事実は、invoke、specsigflags、および specptr フィールドを適切に更新することによって生成コードインスタンスに知らされます。コードインスタンスは、これらのフィールドのすべての組み合わせが任意の時点で有効である限り、invoke、specsigflags、および specptr フィールドのアップグレードをサポートします。これにより、JITは既存のコードインスタンスを無効にすることなくこれらのフィールドを更新でき、将来の並行JITをサポートします。具体的には、以下の状態が有効である可能性があります：

1. invoke は NULL であり、specsigflags は 0b00 であり、specptr は NULL です。

   1. これはコードインスタンスの初期状態であり、コードインスタンスがまだコンパイルされていないことを示しています。

2. invokeは非NULLで、specsigflagsは0b00、specptrはNULLです。

   1. これは、codeinstが特別化なしでコンパイルされておらず、codeinstを直接呼び出すべきであることを示しています。この場合、invokeはspecsigflagsまたはspecptrフィールドを読み取らないため、これらはinvokeポインタを無効にすることなく変更できます。

3. invokeは非null、specsigflagsは0b10、specptrは非nullです

   1. これは、codeinstがコンパイルされたことを示していますが、codegenによって特別な関数シグネチャは不要と見なされました。

4. invokeは非null、specsigflagsは0b11、specptrは非nullです

   1. これは、codeinstがコンパイルされ、codegenによって特化した関数シグネチャが必要であると見なされたことを示しています。specptrフィールドには、特化した関数シグネチャへのポインタが含まれています。invokeポインタは、specsigflagsおよびspecptrフィールドの両方を読み取ることが許可されています。

さらに、更新プロセス中に発生するさまざまな遷移状態があります。これらの潜在的な状況に対処するために、これらの codeinst フィールドを扱う際には、以下の書き込みおよび読み取りパターンを使用する必要があります。

1. invoke、specsigflags、および specptr を記述する際：

   1. NULLだったと仮定してspecptrの原子比較交換操作を実行します。この比較交換操作は、書き込みの残りのメモリ操作に対する順序保証を提供するために、少なくとも取得-解放順序を持つ必要があります。
   2. specptrが非NULLの場合、書き込み操作を中止し、specsigflagsのビット0b10が書き込まれるのを待ちます。
   3. specsigflagsの新しい低ビットを最終値に書き込みます。これは緩やかな書き込みである可能性があります。
   4. 新しい invoke ポインタを最終値に書き込みます。これは、invoke の読み取りと同期するために、少なくともリリースメモリ順序を持っている必要があります。
   5. specsigflagsの2番目のビットを1に設定します。これは、specsigflagsの読み取りと同期するために、少なくともリリースメモリ順序である必要があります。このステップは書き込み操作を完了し、すべての他のスレッドにすべてのフィールドが設定されたことを通知します。

2. invoke、specsigflags、および specptr をすべて読むとき:

   1. invokeフィールドを少なくとも取得メモリ順序で読み取ります。このロードはinitial_invokeと呼ばれます。
   2. initial_invokeがNULLの場合、codeinstはまだ実行可能ではありません。invokeはNULLであり、specsigflagsは0b00として扱うことができ、specptrはNULLとして扱うことができます。
   3. specptrフィールドを少なくとも取得メモリ順序で読み取ります。
   4. specptrがNULLの場合、initial_invokeポインタは正しい実行を保証するためにspecptrに依存してはなりません。したがって、invokeは非NULLであり、specsigflagsは0b00として扱うことができ、specptrはNULLとして扱うことができます。
   5. specptrが非NULLである場合、initial_invokeはspecptrを使用する最終的なinvokeフィールドではない可能性があります。これは、specptrが書き込まれたが、invokeがまだ書き込まれていない場合に発生する可能性があります。したがって、少なくとも取得メモリ順序で1に設定されるまで、specsigflagsの2番目のビットでスピンします。
   6. invokeフィールドを少なくとも取得メモリ順序で再読み込みします。このロードはfinal_invokeと呼ばれます。
   7. specsigflags フィールドを任意のメモリ順序で読み取ります。
   8. invoke は final_invoke であり、 specsigflags はステップ 7 で読み取った値で、 specptr はステップ 3 で読み取った値です。

3. specptrを異なるが同等の関数ポインタに更新する場合：

   1. 新しい関数ポインタを specptr にリリースストアを実行します。ここでの競合は無害でなければならず、古い関数ポインタは依然として有効である必要があり、新しいポインタも有効である必要があります。specptr にポインタが書き込まれた後は、それが後で上書きされるかどうかにかかわらず、常に呼び出し可能でなければなりません。

これらの書き込み、読み取り、および更新のステップは複雑ですが、JITが既存のcodeinstを無効にすることなくcodeinstを更新できること、また既存のinvokeポインタを無効にすることなくcodeinstを更新できることを保証します。これにより、JITは将来的により高い最適化レベルで関数を再最適化する可能性があり、また将来的には関数の同時コンパイルをサポートすることができます。