アカデミック大学の教育プロジェクトとしてのJITコンパイラー

約16年前、 Hotspotの最初のバージョンがリリースされました。JVM実装は、後にSunのJREバンドルに付属する標準の仮想マシンになりました。



この実装の主な違いはJITコンパイラでした。これにより、多くの場合、 遅いJavaに関するステートメントは完全に受け入れられなくなりました。

これで、CLR、Python、Ruby、Perl、さらに素晴らしいプログラミング言語 Rなど、ほとんどすべてのインタープリタープラットフォームが独自のJITトランスレーター実装を取得しました。



この記事の一部として、産業用JITコンパイラーの実装に関するあまり知られていない詳細に光を当てるつもりはありませんが、基本的なことの非常に表面的な紹介であり、関連するトピックに関するトレーニングプロジェクトに関するストーリーです。



したがって、あなたは猫に興味があるかもしれません：

• 基本的に、JITコンパイラが何であるかを理解していないか、わずかな誤解があるため、このアプローチは解釈よりもはるかに優れています。
• インタプリタ言語用の簡単なJITを書きたいと思います。
• あなたはコース「プログラミング言語とコンパイラ」を教え、学生のための実際的なタスクをさらに面白くすることを気にしません。
• あなたはこの絵がどのように描かれるのか疑問に思っています。

JITコンパイルの利点

利点について話すには、まずそれが何であるかを理解します。 遠くから始めましょう。つまり、コンパイルされた言語の定義から始めましょう。



コンパイルされたプログラミング言語とは 、コンパイラによってソースコードが特定のアーキテクチャ（たとえばx86 / ARM）のマシンコードに変換されるプログラミング言語です。 このマシンコードは、プロセッサが完全に理解できる一連のコマンドであり、仲介者なしで実行できます。



解釈されたプログラミング言語は、CPUで直接実行するためにソースがマシンコードに変換されず、特別なインタープリタープログラムを使用して実行されるという点で異なります。

中間オプションとして、多くの言語（Java、C＃、Python）がマシンに依存しないバイトコードに変換されます 。

CPUで直接実行することはできず、実行するにはインタプリタが必要です。



なぜ解釈が遅いのですか？ この質問に対する答えは、奇妙なことに、誰にとっても明らかではありませんが、それは非常に単純ですが、各コマンドを個別に解釈し、このコマンドのセマンティクスをプロセッサ言語に翻訳するために追加のリソースを費やします。 さらに、最新のプロセッサはシーケンシャルコマンドの実行用に最適化されており（ Conveyorを参照）、ほとんどの場合、インタープリターは一連のオプションを備えた巨大なスイッチであり、 遷移予測を行き止まりに駆動します。



バイトコードをプロセッサ言語に変換し、実行のためにCPUに転送することは、これらの問題すべてに対する1回の自然な解決策です。 これは彼らが最も頻繁に行うことであり、このプロセスをJust-in-time-compilation （JIT）と呼びます。 さらに、生成されたコードのさまざまな最適化が最も頻繁に実行されるのは、このフェーズ中です。



さあ、練習しましょう。

問題の声明

私たちの大学のコース「仮想化と仮想マシン」は、ホットスポット、VirtualBox、NativeClientなどのVMのさまざまなクラスの開発に参加し、実装の詳細を直接知っているニコライ・イゴッティによって教えられています。 現代のテクノロジーの素晴らしさのおかげで、コースについては講義室で公開されているため、アカデミック大学の学生である必要はありません。 もちろん、コースの双方向性と講義で聴衆と協力するため、これは少し間違っていることに注意する必要があります。



コースの一環として、試験の入学資格を取得するために、学生は単純なスタック型仮想インタープリターマシンとトランスレーターの実装をCライクな言語のバイトコードに書き込むように求められました。 実際、タスクは一見思われるよりもやや単純です。タスクと共に多くの既製のC ++コードが発行されます。

• 翻訳するまさにプログラミング言語のASTのパーサー。 本当にありがとうございました！ 通常、6年目までに、AUの学生は16の異なるパーサーを書く時間があり、別の再帰下降を書くことはまったく面白くない。
• 詳細なコメント付きの列挙型のバイトコード命令タイプのリスト。
• バイトコードを操作するためのユーティリティクラス：その構築とバイナリ表現を使用します。

このタスク全体のコード名はmathvmです。これは、多くの場合、プログラミング言語の主な目的が何かを数えることであるためです。



典型的なmathvmプログラム：

function int fib(int x) { if (x <= 1) { return x; } int r = fib(x - 1); return r + fib(x - 2); } print(fib(35), '\n');
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

言語の主な機能：

• データ型の操作：int、double、string、それらに対する算術演算。
• 標準制御構造：if、while、for、print。
• クロージャーの存在の結果として、関数内で関数を宣言する機能。 この機能は、インタープリターを設計するときに多くの質問を引き起こしましたが、クロージャーを操作するための指示が利用できることを考えると、つまずきのブロックにはなりませんでした。
• ネイティブ関数を宣言する機能 。 つまり、ネイティブでマークされた本体とシンボルの名前のない関数を宣言できます。これは、パラメーターRTLD_DEFAULTを使用してdlsymを介して仮想マシンによってロードできます。
  
  たとえば、次のように：
  
  

   function void printfIDS(string format, int x1, double x2, string x3) native 'printf'; printfIDS('%d %f %s\n', 1, 2, 'abc');
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

  
  
  

最後のポイントはタスクをもっと楽しくするように思えます：

• 第一に、実行時に関数へのポインターを持っている場合、以前に未知の引数セットを関数に渡す方法がすぐにはわかりません。署名と計算された引数はメモリの特定の場所に保存されます。 これは完全にクロスプラットフォームの方法では不可能であることは多かれ少なかれ明らかであり、少なくとも呼び出し規約を修正する必要があります。 人気のあるUNIXシステムで使用されているSystem V ABIからの呼び出し規約に同意しました。
  
  しかし、その後であっても、最も痛みのない目標を達成する方法は明らかではないようです。
  
  頭に浮かんだのは、引数を対応するレジスタとスタックのセルに分解するコードを備えた巨大で恐ろしいアセンブラの挿入だけでした。 その結果、私はわずかに異なるソリューションを選択しました。これについては以下で説明します。
  
  
• ネイティブ関数は、結果の言語の機能を大幅に拡張します。 数日間のフェージングの後、インタープリターと翻訳者が準備が整い、台形との鈍い数値統合の代わりに、 このような何かがあなたの頭脳で始まり、画面にクールなサイケデリックなアニメーションを描画します（記事の冒頭のスクリーンショットを参照）。これは素晴らしいボーナスです。
  
  

気配りのある読者は、何らかの理由で、プログラムが最後のアイテムから描画される1秒あたりのフレーム数（FPS）を計算することに気付くでしょう。 この指標により、通訳者のパフォーマンスを評価することができるため、誰かに退屈そうに思えた教育プロセスに競争心をもたらすことができます。

通訳者がこれで最速であり、同様のベンチマークがいくつか自動的に試験に合格し、さらに同僚の愛と尊敬を得る学生。 このゲームをプレイする最初のスレッドではないことに注意してください。通常、勝つためにはJITコンパイラを実装する必要がありました。

難しさ

単純なバイトコード命令のセマンティクスをx86命令セットの対応する要素に単純に変換することは本質的に難しいように思われますか？

1. コンパイルされた言語があれば、文字通りアセンブリ言語でテキストを生成し、それに応じてアセンブルして実行可能ファイルを作成できます。
   
   しかし、JITブロードキャストのフレームワークでは、プロセスをこれらの2つのフェーズに分割することは許されない贅沢であり、VMプロセスのメモリでマシンコードをすぐに生成する方法を何らかの方法で学習する必要があります。
   
   
2. また、すべてのメモリ領域がマシンコードの記述に適しているわけではありません。 より正確には、どこかに書き込むことができますが、実行可能としてマークされたページを持つメモリ領域にのみ実行を転送できます。 単純なmalloc'omではできないようです。
3. 理想的には、もちろん、結果のマシンコードはできるだけ早く動作するはずです。

アスミット

Asmjitは、最初の2つの問題を解決するのに非常に適しています。過去数年間に1人が大部分を開発し、著者の他のプロジェクトで使用されたオープンソースライブラリ、およびGTA San Andreas MPサーバーのスクリプトのJITです 。

名前が示すように、その主な使命は、ジャストインタイムマシンコードを生成するための便利なAPIを作成することです。 そのパブリックインターフェイスは、2つの部分に分けることができます。

• X86Assemblerは、基本的に次の3つのことを実行できる低レベルインターフェイスです。
  
  
  1. 実行特権でメモリの割り当てを開始します。
  2. 命令/データを順番に配置し、コードの他のセクションからの遷移がある場所にラベルを配置します。
     
     コードを操作するために、ライブラリには一連のオペランドクラスがあります：GpReg、XmmReg、Imm、Mem、およびクラス内の各命令には、この命令に有効なオーバーロードの同じセットを持つ同じ名前のメソッドがあります。 たとえば、シグネチャmov（X86Mem＆、X86Mem＆）があるメソッドは、あるはずです。
     
     
  3. いっぱいになったメモリの先頭へのポインタを取得します。これは、関数へのポインタ、エントリポイントとして使用できます。
  
  
  
• X86Compilerは、カプセル化するX86Assemblerの高レベルラッパーです。
  
  
  • 関数定義の側と呼び出しの場所の両方で、指定された呼び出し規約に従って関数を作成し、引数を操作します（ところで、ネイティブ関数を実装する最も簡単な方法） 。
    
    
  • レジスターの割り当て：変数（GpVarまたはXmmVar）を定義することができ、コンパイラーは変数の保存場所を選択します。 検索しなかった予約はすぐに行いますが、どの割り当てアルゴリズムが使用されているかは知りません。 私が言える唯一のことは、簡単な実験で利用可能なレジスタがかなり合理的に使用されたことです。
  
  
  

私の実装では、アセンブラーを使用しました。このアセンブラーは、その透明性とより優れた制御性を実現しました。



Asmjitを使用した最も簡単な実例：

 #include "asmjit/asmjit.h" #include <iostream> int main(int argc, char** argv) { using namespace std; using namespace asmjit; using namespace asmjit::x86; JitRuntime runtime; // RAII object X86Assembler assembler(&runtime); assembler.add(rdi, rsi); // add second argument to first assembler.mov(rax, rdi); // mov result to return register assembler.ret(); void * address = assembler.make(); cout << reinterpret_cast<int64_t (*) (int64_t, int64_t)>(address)(2, 2) << endl; // 4 return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

アセンブラーに精通している人はあまり質問すべきではないと思います。 言及する唯一のものは、割り当てられたメモリの寿命に責任があるランタイムオブジェクトです。 彼女は彼のデストラクタ（ RAII ）を呼び出した後に解放されます。

より多くの使用例は、ライブラリテストのあるディレクトリまたはリポジトリにあります。

デバッグ

奇妙なことに、生成されたコードのデバッグは特に邪悪ではありません。

まず、何か問題が発生した場合、Amsjitログを注意深く見ることができます。 ログでは、受け取ったアセンブラコードと、ここに表示された場所からのコメントを確認できます。

これでも役に立たない場合は、最新のデバッガー（gdb / VS）のほとんどで、逆アセンブリを使用してデバッグモードで動作する可能性があります。 つまり、生成された関数への呼び出しの代わりにブレークポイントを置くことができ、 Step Intoはアセンブラーコードを使用して画面に転送します。そこで、ほぼ通常どおりステップごとにデバッグできます。

重要です

• 10のうち3つの場合、30分でコンパイラではなく、解釈されたプログラム自体にエラーが見つかります。
  
  
• 残念ながら、Asmjitはまだあまり集中的に使用されていないため、さまざまな程度の厄介なバグが含まれている可能性があります。 したがって、ログがまさにあなたが望んでいたものであることに注意してください。 私は何にも出くわしませんでしたが、クラスメートは幸運ではありませんでした。無効なコードが生成されたという事実はログにも表示されず、デバッガーにのみ表示されました。
  
  

最適化

3日間のアクティブなプログラミングとデバッグの後、最初の完全に洗練されていないバージョンのJITトランスレーターが登場しました。このバージョンでは、スタックと変数のすべての値がメモリーに毎回保存されていました。

そのようなソリューションでさえ、最大6 FPSのインタープリターで得られた6 FPSで約6倍のパフォーマンスの向上をもたらしました。



一般に、学期の初め、ゲームのルールが明確になったとき、私はナポレオンの計画を立てました。SSAでのバイトコード変換とスマートレジスタ割り当てアルゴリズムを使用して、すべてを大人の方法で行うことです。

しかし、時間と平凡なco病の深刻な不足のために、すべてがやや平凡になりました。

レジスタ割り当て

念のため、プログラムのパフォーマンスに関して最も重要なポイントの1つは、使用可能なCPUレジスタを使用する効率であることを思い出させてください。

これは、主な計算アクティビティがそれらでのみ実行可能であることに加えて、さらに、L1キャッシュにあるメモリへの読み取り/書き込みも、レジスタでの同様の操作よりも最大2倍長く機能するためです。

最も難しいのではなく、むしろ効果的なヒューリスティックなソリューションを使用しました：仮想マシンスタックの最初の要素、汎用スロット（文字列/整数）の7要素、浮動小数点数のスロットの14要素をレジスタに格納します。

関数のフレームワークで最もホットな変数は実際にスタックの一番下にあり、すべての計算に関与するため、このソリューションは最も正当化されているようです。

さらに、関数を呼び出すときに引数のレイアウトと同じレジスタを使用すると、場合によっては呼び出しの場所で時間を節約できます。

これらのアイデアを実装した結果、 9 FPSのアクセラレーションが得られ、45 FPSに達しました。

のぞき穴の最適化

生成に対する単純な古典的アプローチの1つは、いわゆるPeephole最適化です。これは、特定の命令シーケンスを見つけて他のより生産的な命令に置き換えるという考え方です。



たとえば、mathvmバイトコードの表現力が不足しているため、（x0 <= x1）のような比較演算子は次のように説明する必要があります。

 LOADIVAR_0 LOADIVAR_1 IF_CMPLE L1 ILOAD_0 //   0    JA L2 //   L1: ILOAD_1 L2: ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

命令の鑑定家x'86は、このようなコードははるかに短く、単一の条件付きジャンプなしで記述できると言います。

 mov rdi, %(var0) mov rsi, %(var1) cmp rdi, rsi setle al movzx rax, al
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

他の場合にも同様の構造があります：否定演算子、forループ。 これらのパターンの検出と修正により、 4 FPSから49ポイントに加速しました。

クロージャーの最適化

各関数のプロローグとエピローグでクロージャーを確実に機能させるために、最後の呼び出しの変数がスタック外の特別に割り当てられたメモリ領域にあるアドレスを保存しました。

さらに、以前のベースポインターを保存および復元する必要があります。 この喜びはすべて、メモリを積極的に使用している人を含め、各通話に最大7つの追加の指示を残しました。

実際、ほとんどの関数はそれ自体にクロージャーを含んでいないため、これらの損失は回避できます。

したがって、短絡の存在について受信したバイトコード全体の追加分析を実行し、対応する冗長な命令が削除された結果、漫画はさらに3 FPSを高速に描画し始めました。

インライン化

マイクロ最適化に関するストーリーの最後のポイントは、 インライン化またはロシア語の「埋め込み」です。 産業用コンパイラが小さな関数を呼び出すコストと格闘する方法：呼び出された関数のコードは、プロローグ/エピローグおよび他の「不要な」命令なしで、呼び出しの場所で単純に複製されます。 確かに、実際には、コンパイラは非常に慎重に埋め込むという決定に近づいていることに注意する必要があります-結果のマシンコードのサイズは、作業の品質の尺度でもあります。



ただし、私の場合は、推定された時間であるため、埋め込まれたすべて（非再帰呼び出し）を埋め込むことを試みました。

そして、ここで、奇妙なことに、ASTからバイトコードへの変換レベルで作業する方が簡単であることがわかりました。



得られた2 FPSの増加は、以前の場合ほど重要ではありませんでしたが、合計53〜54 FPS（ほぼ9倍の加速）は喜ばせざるを得ませんでした。 同じ注文の加速は、他の利用可能なベンチマークで観察されました。



興味深いことに、私の単純なJITトランスレータでさえ、インタープリターをまったく起動せず、すべてのコードをすぐにコンパイルしましたが、最高のパフォーマンスを得るにはウォームアップを数回繰り返しました。

これは、必要なすべてがコンパイルされるだけでなく、プログラムのプロファイルを修正するために、ベンチマークでのウォームアップが必要であるという事実に関する権威ある人々の声明を示しています。

まとめ

その結果、私の実装は最速になりましたが、これは私が最もcな存在であるという事実とはあまり関係がありませんが、JITの最も単純な実装さえも作成したという事実はありません。

したがって、少なくともいくつかのスポーツの陰謀の欠如は勝利を覆い隠した。



私の実装のソースは、 リポジトリのimplディレクトリにあります。

コードの品質について事前に謝罪しますが、これはまだおもちゃのプロジェクトであり、これ以上サポートする予定はありません。



ご清聴ありがとうございました！