JITコンパイルでの冒険　パート2：x64 JIT

このシリーズの最初のパート(訳注:POSTDの翻訳記事へのリンクです)で簡単にBFソース言語を紹介し、最適化レベルが高まる4つのインタプリタについて述べました。実際にJITをいじる前に背景を知る上で役に立つと思います。

さらに背景を知る上で有効なのが、2013年に私が書いた『JITの方法 – 入門編』という記事です。ここでは、実行時に実行可能なx64機械コードの生成と実際にLinux上で実行するために必要な基本ツールについて説明しました。初めての方はまずこれらの記事を読んでください。

JITの2つの段階

以前にも書きましたが、JIT手法を2段階に分けて考えると理解しやすいと思います。

  1. プログラム実行時に機械コードを作成する。
  2. 作成した機械コードもプログラム実行時に実行する。

BF JITの第2段階は前記事で説明した方法と全く同じ内容です。詳細はjit_utilsのJitProgramクラスを参照してください。今回は、BFをx64機械コードに変換する第1段階に集中的して説明します。このシリーズのパート1の定義に基づき、実際にBFコンパイラ（BFソースからx64機械コードへのコンパイル）を開発します。

コンパラ、アセンブラ及び命令のコード化

伝統的にコンパイルは複数の段階に分けられています。実際のソース言語コンパイラは高水準な言語をターゲット固有のアセンブリに変換してくれます。その後、アセンブラはアセンブリを実際の機械コードに変換します1。アセンブリ言語は生機械コードよりも重要な利点を多く提供してくれます。顕著な例として以下が含まれます。

  • 命令のコード化：レジスタr13の内容をインクリメントするためにinc %r13を書いた方が、0x49, 0xFF, 0xC5を書くよりも確かにいいでしょう。一般的なアーキテクチャに命令のコード化を適用するのは非常に複雑です。

  • ラベルの命名やジャンプ命令・コール命令の手順：jl loopを書いた方が、命令のコード化を考えたり、同時にloopラベルの相対的位置を考えたり、差分のコード化を行ったりするよりも簡単です（言うまでもありませんが、差分は命令を間に追加するたびに変わり、その都度再計算する必要があります）。関数においても、アドレスを使うよりもcall fooを使って実行する方が簡単です。

プログラミングの分野において私の指針の1つは、問題の解決策（例：Xを行うためのライブラリ）に飛び込む前に、まずは手動で試してみる価値があるということです（ライブラリを使わずXを手動で行う）。歯を食いしばって問題に対峙することは、提供されている解決策やライブラリのありがたみが実感できる最高の手段です。

この姿勢で進めるので、最初のJITは完全に手書きします。

単純なJIT – 手動でのx64命令のコード化

まず、この記事のJITはsimplejit.cppです。パート1のインタプリタ同様、全ての動作はmainから起動され、1つの関数（ここではsimplejitと呼びます）で実行されます。simplejitはBFソースを介して、x64機械コードをメモリバッファに出力します。最終的には、BFプログラムを実行するためにこの機械コードにジャンプします。

初めの部分は以下のとおりです。

  1. std::vector<uint8_t> memory(MEMORY_SIZE, 0);
  2.  
  3. // プログラムで使用するレジスタ:
  4. //
  5. // r13: データポインタはmemory.data()のアドレスを保持。
  6. //
  7. // rax、rdi、rsi、rdxはABIごとにシステムコールの作成に使用。
  8.  
  9. CodeEmitter emitter;
  10.  
  11. // 変換ループの全体を通して、このスタックは修正場所のオフセットを
  12. // (エミッタコードベクトルの中に)保持。
  13. std::stack<size_t> open_bracket_stack;
  14.  
  15. // movabs <メモリデータのアドレス>, %r13
  16. emitter.EmitBytes({0x49, 0xBD});
  17. emitter.EmitUint64((uint64_t)memory.data());

いつものようにstd::vectorにBFメモリバッファがあります。出力されたプログラム全体で使われている規則をコメントによって明らかにしています。ここでは、 “データポインタ” はr13にあります。

CodeEmitterはバイトとワードをバイトのベクトルに付加する非常に簡単なユーティリティです。ここに全コードがあります。リトルエンディアンの前提を除いてプラットフォームに依存しません（EmitUint64の場合は、64バイトの最下位バイトから書き込んでいきます）。

ここで出力された機械コードの最初の部分は以下の通りです。

  1. // movabs <メモリデータのアドレス>, %r13
  2. emitter.EmitBytes({0x49, 0xBD});
  3. emitter.EmitUint64((uint64_t)memory.data());

しかもいい感じです。ホストからの要素を混ぜ（C++プログラムが出力）、コードのJITを行います。まず、movabsの使用に注意してください。movabsは、x64命令で、64ビットの直値をレジスタに置くのに便利です。まさにこれをしたいのです。memoryのデータバッファのアドレスをr13に置きたいのです。16進値の暗黙のシーケンスを使ったEmitBytesの起動の前に、コメントでアセンブリのスニペットがあります。アセンブリは人間の読者のための説明で、16進値は機械が理解するための実際のコードです。

次に出てくるのが、次のBF命令を見て対応する機械コードを出力するBFコンパイルループです。このコンパイラは単一パスで動作します。この後分かりますが、ジャンプ命令の扱いには注意が必要です。

  1. for (size_t pc = 0; pc < p.instructions.size(); ++pc) {
  2.   char instruction = p.instructions[pc];
  3.   switch (instruction) {
  4.   case '>':
  5.     // inc %r13
  6.     emitter.EmitBytes({0x49, 0xFF, 0xC5});
  7.     break;
  8.   case '<':
  9.     // dec %r13
  10.     emitter.EmitBytes({0x49, 0xFF, 0xCD});
  11.     break;
  12.   case '+':
  13.     // メモリはバイトアドレスなので、addb/subbを変更に使用
  14.     // addb $1, 0(%r13)
  15.     emitter.EmitBytes({0x41, 0x80, 0x45, 0x00, 0x01});
  16.     break;
  17.   case '-':
  18.     // subb $1, 0(%r13)
  19.     emitter.EmitBytes({0x41, 0x80, 0x6D, 0x00, 0x01});
  20.     break;

至って簡単だと思います。データポインタがr13で、それを>と<でインクリメントとデクリメントし、+と-によってポイント先がインクリメントとデクリメントされます。少し微妙な点はBFの実装にバイト値メモリを選択したことです。つまり、メモリの読み込みや書き込みの際に注意が必要で、デフォルトの64ビットアドレスではなく、バイトアドレス（上のaddとsubのbサフィックス）を使う必要がありす。

.と,に対して出力されるコードはもっと面白いです。外部からの依存を一切避けるため、直接Linuxシステムコールを起動します。.はWRITE、,はREADです。ここでx64のABIを raxのシステムコール識別子と共に使います。

  1.   // stdoutに１バイト出力、fd=1(stdout用)で
  2.   // 書き込みシステムコールを呼び出す、buf=addressのバイト、count=1
  3.   //
  4.   // mov $1, %rax
  5.   // mov $1, %rdi
  6.   // mov %r13, %rsi
  7.   // mov $1, %rdx
  8.   // syscall
  9.   emitter.EmitBytes({0x48, 0xC7, 0xC0, 0x01, 0x00, 0x00, 0x00});
  10.   emitter.EmitBytes({0x48, 0xC7, 0xC7, 0x01, 0x00, 0x00, 0x00});
  11.   emitter.EmitBytes({0x4C, 0x89, 0xEE});
  12.   emitter.EmitBytes({0x48, 0xC7, 0xC2, 0x01, 0x00, 0x00, 0x00});
  13.   emitter.EmitBytes({0x0F, 0x05});
  14.   break;
  15. case ',':
  16.   // stdinに１バイト出力、fd=0 (stdin用)で
  17.   // 読み込みシステムコールを呼び出す。
  18.   // buf=addressのバイト、count=1.
  19.   emitter.EmitBytes({0x48, 0xC7, 0xC0, 0x00, 0x00, 0x00, 0x00});
  20.   emitter.EmitBytes({0x48, 0xC7, 0xC7, 0x00, 0x00, 0x00, 0x00});
  21.   emitter.EmitBytes({0x4C, 0x89, 0xEE});
  22.   emitter.EmitBytes({0x48, 0xC7, 0xC2, 0x01, 0x00, 0x00, 0x00});
  23.   emitter.EmitBytes({0x0F, 0x05});
  24.   break;

確実にコメントが役に立っていると思いませんか。これらスニペットが、手動での命令をコード化をやめて、アセンブリ言語を使うきっかけになればと思います。

BFの中でジャンプ命令が一番面白いと思います。[は以下のようにします。

  1. case '[':
  2.   // ジャンプの場合、潜在的に短いジャンプや緩和のために
  3.   // 常に32ビットPC相対の命令を出力。
  4.  
  5.   // cmpb $0, 0(%r13)
  6.   emitter.EmitBytes({0x41, 0x80, 0x7d, 0x00, 0x00});
  7.  
  8.   // スタック内の位置を保存し、後で修正。
  9.   // 4つのプレースホルダのゼロでJZ（32ビット相対オフセット）を出力。
  10.   open_bracket_stack.push(emitter.size());
  11.   emitter.EmitBytes({0x0F, 0x84});
  12.   emitter.EmitUint32(0);
  13.   break;

この時点では移動先が分からないことに注意してください。対応する]に行くことになりますが、まだ遭遇していません。従って、コンパイルを単一パス2にしておくためにジャンプのプレースホルダ値を返し、対応するラベルに遭遇した後に修正を行うことで、伝統的な手法の後埋めを使用することになります。さらに1点注意しなければならないのは、単純さを保つために常に32ビットPC相対ジャンプを使うことです。多くの場合、短いジャンプにすることで数バイト節約することができます（詳しくは アセンブラ緩和についての記事を参照してください）。しかし、努力する価値はないと思います。

対応する]をコンパイルするのはちょっと大変です。コメントで何が起きているか理解してもらえると思います。さらに、プログラムは賢さよりも読みやすさを重視して最適化しています。

  1. case ']': {
  2.   if (open_bracket_stack.empty()) {
  3.     DIE << "unmatched closing ']' at pc=" << pc;
  4.   }
  5.   size_t open_bracket_offset = open_bracket_stack.top();
  6.   open_bracket_stack.pop();
  7.  
  8.   // cmpb $0, 0(%r13)
  9.   emitter.EmitBytes({0x41, 0x80, 0x7d, 0x00, 0x00});
  10.  
  11.   // この閉じブラケットにジャンプするJZを指すopen_bracket_offset
  12.   // このJZのオフセットの修正と共に正しいオフセットを出力する
  13.   // JNZが必要。注意点は、[と]が、対応ブラケットを見つけた
  14.   // *後*に条件を満たせば命令にジャンプ
  15.  
  16.   // ジャンプのオフセットを算出。ジャンプ開始の算出は、
  17.   // ジャンプ命令の後からで、対象はスタックに保存された命令の後の命令
  18.   size_t jump_back_from = emitter.size() + 6;
  19.   size_t jump_back_to = open_bracket_offset + 6;
  20.   uint32_t pcrel_offset_back =
  21.       compute_relative_32bit_offset(jump_back_from, jump_back_to);
  22.  
  23.   // jnz <open_bracket_location>
  24.   emitter.EmitBytes({0x0F, 0x85});
  25.   emitter.EmitUint32(pcrel_offset_back);
  26.  
  27.   // 対応[への前進ジャンプを修正。"ジャンプ先"オフセットに
  28.   // jmpのサイズを追加する必要がないことに注意。
  29.   // jmpは出力済みのため、エミッタサイズは前に押し出されている。
  30.   size_t jump_forward_from = open_bracket_offset + 6;
  31.   size_t jump_forward_to = emitter.size();
  32.   uint32_t pcrel_offset_forward =
  33.       compute_relative_32bit_offset(jump_forward_from, jump_forward_to);
  34.   emitter.ReplaceUint32AtOffset(open_bracket_offset + 2,
  35.                                 pcrel_offset_forward);
  36.   break;
  37. }

これでコンパイルループを終わります。最終的にvectorに実行可能な機械コードができました。このコードはホストプログラム（memory.data()のアドレス）を指していますが、ホストプログラムの寿命はJITコードの寿命を上回るので、問題ありません。実際に機械コードを起動しましょう。

  1. // ... コンパイルループの後
  2.  
  3. // 出力コードは関数としてC++呼び出されるため、
  4. // 正しい呼び出し規則が必要。'ret'を出力して、呼び出し元へ 
  5. // 規則的に返す
  6. emitter.EmitByte(0xC3);
  7.  
  8. // 実行可能なメモリに出力コードをロードし、実行。
  9. std::vector<uint8_t> emitted_code = emitter.code();
  10. JitProgram jit_program(emitted_code);
  11.  
  12. // JittedFuncは出力されたJIT関数のC++タイプ。
  13. // C++で出力された関数は呼び出し可能、x64 System V ABIに遵守。
  14. using JittedFunc = void (*)(void);
  15.  
  16. JittedFunc func = (JittedFunc)jit_program.program_memory();
  17. func();

コール命令については『JITの方法 – 入門編』を読んでご存知だと思います。ここでは可能な限り最も単純な関数を選択したことに注目してください。引数もなければ、返される値もありません。これ以降のセクションで応用していきます。

JITを動かしてみる

パート1では、画面に数字の１から5を表示する普通のBFプログラムをお見せしました。

  1. ++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++
  2. >+++++
  3. [<+.>-]

では、これをコンパイラがどのように変換するか見てみましょう。simplejit内のコードベクトルは短命です（メモリに一時的に存在します）が、バイナリファイルにシリアル化し、その後で逆アセンブルできます（objdump -D -b binary -mi386:x86-64を使って）。以下の逆アセンブリ一覧にコメント説明を書き込みました。

  1.  # memory.data()アドレスの実行時はr13; 注意点は
  2.  # JITの呼び出しことに値が異なる可能性が高いこと。
  3.  
  4.   0:   49 bd f0 54 e3 00 00    movabs $0xe354f0,%r13
  5.   7:   00 00 00
  6.  
  7.  # ＋の初期シーケンスに対して48個の命令シーケンスは全て同じことを行う。
  8.  # これにより最適化インタプリタをミス可能性あり。
  9.  # ご心配なく、記事後半で解決します。
  10.  
  11.   a:   41 80 45 00 01          addb   $0x1,0x0(%r13)
  12.   f:   41 80 45 00 01          addb   $0x1,0x0(%r13)
  13.  
  14.  # [...] 46 more 'addb'
  15.  
  16.  # >+++++
  17.  
  18.  fa:   49 ff c5                inc    %r13
  19.  fd:   41 80 45 00 01          addb   $0x1,0x0(%r13)
  20. 102:   41 80 45 00 01          addb   $0x1,0x0(%r13)
  21. 107:   41 80 45 00 01          addb   $0x1,0x0(%r13)
  22. 10c:   41 80 45 00 01          addb   $0x1,0x0(%r13)
  23. 111:   41 80 45 00 01          addb   $0x1,0x0(%r13)
  24.  
  25.  # ループです。後埋め処理によって相対ジャンプオフセットは
  26.  # 'je'命令に挿入済みであることに注意。
  27.  
  28. 116:   41 80 7d 00 00          cmpb   $0x0,0x0(%r13)
  29. 11b:   0f 84 35 00 00 00       je     0x156
  30. 121:   49 ff cd                dec    %r13
  31. 124:   41 80 45 00 01          addb   $0x1,0x0(%r13)
  32.  
  33.  # '.'はWRITEのシステムコールに変換。
  34.  
  35. 129:   48 c7 c0 01 00 00 00    mov    $0x1,%rax
  36. 130:   48 c7 c7 01 00 00 00    mov    $0x1,%rdi
  37. 137:   4c 89 ee                mov    %r13,%rsi
  38. 13a:   48 c7 c2 01 00 00 00    mov    $0x1,%rdx
  39. 141:   0f 05                   syscall
  40. 143:   49 ff c5                inc    %r13
  41. 146:   41 80 6d 00 01          subb   $0x1,0x0(%r13)
  42. 14b:   41 80 7d 00 00          cmpb   $0x0,0x0(%r13)
  43.  
  44.  # ループの初めにジャンプで戻る。
  45.  
  46. 150:   0f 85 cb ff ff ff       jne    0x121
  47.  
  48.  # 以上で終わり。
  49.  
  50. 156:   c3                      retq

パフォーマンスはどうか

パート1のインタプリタに照らしてここで作成したJITのパフォーマンスを測定しましょう。ナイーブなインタプリタよりもoptinterp3は約10倍も高速化されていました。では、JITはどうでしょう。最適化はされていないことに注意してください（ナイーブなインタプリタのようにループを繰り返すたびにジャンプ先を再計算する必要はありません）。どうでしょう。結果を見たら驚くかもしれません。

単純なJITは、mandelbrotを2.89秒で処理し、factorを0.94秒で処理します。opt3interpよりもかなり高速です。以下は比較です（偏りを避けるため低速なインタプリタは除外しています）。

BF opt3 vs simplejit

なぜこうなるのでしょうか。opt3interpの最適化は重点的に実施されています。ループ全体を単一操作に折り畳んでいます。このようなことはsimplejitではではありえません。上で、addbによって長ったらしい+の格好悪いシーケンスが返されるのを見ました。

理由はJITの基本的なパフォーマンスが非常に良いからなのです。パート1でも簡単に触れましたが、最高速のインタプリタによって1つの命令を解釈するために必要なものは何かを考えてみます。

  1. pcを進めて、それをプログラムサイズと比較する。
  2. pcでの命令を取得する。
  3. 命令の値に基づいて適切なcaseに切り替える。
  4. そのcaseを実行する。

これには、少なくとも2つの分岐を備えた一連の機械命令が必要になります（1つはループ用、1つはswitch用）。その一方で、JITは分岐のない1つの命令を出します。インタプリタコンパイル時のコンパイラの動作にもよりますが、恐らく、どのBF演算を実行するにもJITで実行する方が4倍から8倍高速だと思います。最適化されないため、大量のBF演算を実行することにはなりますが、基本的なパフォーマスのギャップを縮めるには至りません。この記事の後半で最適化したJITでパフォーマンスの向上を見てみましょう。

でもその前に、まず、手間のかかる命令のコード化を見てみましょう。

手動での命令のコード化

約束されているように、simplejitは完全に自己完結しています。外部のライブラリを使う必要もなく、全ての命令を独自にコード化します。これがどれだけ手間のかかる処理かは分かりやすく、詳細なコメントなしにはコードからは読み取ることができません。さらには、コード変更も大変で、思いもよらない形で変更が生じることがあります。例えば、命令で別のレジスタを使いたいとした場合、出力されるコードの変更は直感的ではありません。add %r8, %r9は0x4C, 0x01, 0xC8としてコード化されますが、add %r8, %r10は0x4C, 0x01, 0xD0になります。レジスタはサブバイト二ブルで指定さるため、どこに何が行くのかを覚えておく良い記憶力及び豊富な経験を必要とします。

関連する命令は同じように見えると思いますか。そうではないのです。例えば、inc %r13は0x49, 0xFF, 0xC0にコード化されます。はっきり言うと、Melでない限り、苦労するでしょう。では、複数のアーキテクチャ用にコードを出力することをサポートしなければならないとしたらどうでしょう。

このため、全コンパイラ、VMや関連のプロジェクトにはそれぞれコード化を手伝う独自のレイヤを持っているのです。同時にラベルやジャンプ演算のような関連タスクも持っています。プロジェクト外で使用できるように公開されてはいません。DynASM (developed as part of the LuaJIT project)のようなものは別途使用するためにパッケージになっています。DynASMは、命令のコード化以外に提供するものがない低水準のフレームワークの一例です。中には、レジスタ割り当てのようにコンパイラ以上のことを実行する水準のフレームワークもあります。その例として挙げられるのが、libjitやLLVMです。

asmjit

命令のコード化に使えるライブラリを探していた時にDynASMを試してみました。取り組み方が面白いと思いました。Josh Habermanの記事を読めば分かりますが、単純なBF JITに使えます。しかし、アバンダンウェアっぽ過ぎると感じました。しかも、独創的なLuaに依存するプリプロセッサ的アプローチが好きではありません。

そして必要条件を満たす別のプロジェクトを見つけたのです。プリプロセッサのない純粋なC++ライブラリであるasmjitです。asmjitは、グラフィックコードのための高速カーネル開発を容易にするために、約3年前に始まったものです。dynasmのドキュメンテーションに優ってはいませんが、単にC++ライブラリであることが、ドキュメンテーションにない質問の答えがあった場合、ソースをいじればいいと思わせてくれました。さらに、Githubでの質疑に対する応答が活発で早いだけでなく、機能の追加もが積極的で早いのです。このことからも、これ以降はasmjitを使用したBF JITを見ていきます。ライブラリの重要なチュートリアルとしても役に立つと思います。

simpleasmjit – 正当な命令コードを持つJIT

simpleasmjit.cppを入力します。simplejitと同じ単純なJIT（最適化なし）ですが、命令のコード化やラベルなどにasmjitを使用します。さらに楽しくするために色々と混ぜ合わせます。まず、JITした機能シグネチャをvoid (*)(void)からvoid (*)(uint64_t)に変更します。BFメモリバッファのアドレスは、ハードコードされるのではなく、JITした関数に引数として渡されます。

次に、システムコールではなく、実際のC関数を使って文字を出力・入力します。また、putcharとgetcharがシステムによってはマクロである場合があるので、これらのアドレスを取るのには危険が伴います。そのため、実際のC++関数でラップすることで、出力されたコードに安全にその関数を取り込むことができます。

  1. void myputchar(uint8_t c) {
  2.   putchar(c);
  3. }
  4.  
  5. uint8_t mygetchar() {
  6.   return getchar();
  7. }

simpleasmjitはasmjitの実行時間やコードホルダ、アセンブラを初期化することから始めます3。

  1. asmjit::JitRuntime jit_runtime;
  2. asmjit::CodeHolder code;
  3. code.init(jit_runtime.getCodeInfo());
  4. asmjit::X86Assembler assm(&code);

次にデータポインタにニーモニック名を付けて、メモリバッファのアドレスのコピーを入れます（x64 ABIの1番目の関数の引数として、最初はrdiにあります）。

  1. // データポンタを引数としてJITした関数に渡す。
  2. // そうすることでrdiに入る。r13へ移動。
  3. asmjit::X86Gp dataptr = asmjit::x86::r13;
  4. assm.mov(dataptr, asmjit::x86::rdi);

そして、全BF演算に対しコードを出力する通常のBF処理ループに入ります。

  1. for (size_t pc = 0; pc < p.instructions.size(); ++pc) {
  2.   char instruction = p.instructions[pc];
  3.   switch (instruction) {
  4.   case '>':
  5.     // inc %r13
  6.     assm.inc(dataptr);
  7.     break;
  8.   case '<':
  9.     // dec %r13
  10.     assm.dec(dataptr);
  11.     break;
  12.   case '+':
  13.     // addb $1, 0(%r13)
  14.     assm.add(asmjit::x86::byte_ptr(dataptr), 1);
  15.     break;
  16.   case '-':
  17.     // subb $1, 0(%r13)
  18.     assm.sub(asmjit::x86::byte_ptr(dataptr), 1);
  19.     break;

違いに気づいたと思います。もはや曖昧な16進コードはありません。assm.inc（dataptr）の方が0x49, 0xFF, 0xC5よりもずっといいとは思いませんか。

入力・出力にはラッパ関数を呼び出します。

  1. case '.':
  2.   // myputchar [dataptr]の呼び出し
  3.   assm.movzx(asmjit::x86::rdi, asmjit::x86::byte_ptr(dataptr));
  4.   assm.call(asmjit::imm_ptr(myputchar));
  5.   break;
  6. case ',':
  7.   // [dataptr] = mygetcharの呼び出し。
  8.   // 関係ないデータの上書きを避けるため、低位バイトのみをメモリに保存。
  9.   assm.call(asmjit::imm_ptr(mygetchar));
  10.   assm.mov(asmjit::x86::byte_ptr(dataptr), asmjit::x86::al);
  11.   break;

秘訣は関数のアドレスを出力されたコードに置くimm_ptr修飾子です。

最後にasmjitラベルのおかげで[と]の扱いも簡単です。実際に出力される前に使うことができます。

  1. case '[': {
  2.   assm.cmp(asmjit::x86::byte_ptr(dataptr), 0);
  3.   asmjit::Label open_label = assm.newLabel();
  4.   asmjit::Label close_label = assm.newLabel();
  5.  
  6.   // もし、[dataptr] = 0; close_labelがまだバインドされていない場合は
  7.   // 閉じ']'の先にジャンプ。
  8.   // しかし、asmjitによってジャンプを今出力し、後埋めを後回しにする。
  9.   assm.jz(close_label);
  10.  
  11.   // open_labelはジャンプを超えてバインド。概して以下を出力。
  12.   //
  13.   //    cmpb 0(%r13), 0
  14.   //    jz close_label
  15.   // open_label:
  16.   //    ...
  17.   assm.bind(open_label);
  18.  
  19.   // スタックに両方のラベルを保存。
  20.   open_bracket_stack.push(BracketLabels(open_label, close_label));
  21.   break;
  22. }
  23. case ']': {
  24.   if (open_bracket_stack.empty()) {
  25.     DIE << "unmatched closing ']' at pc=" << pc;
  26.   }
  27.   BracketLabels labels = open_bracket_stack.top();
  28.   open_bracket_stack.pop();
  29.  
  30.   //    cmpb 0(%r13), 0
  31.   //    jnz open_label
  32.   // close_label:
  33.   //    ...
  34.   assm.cmp(asmjit::x86::byte_ptr(dataptr), 0);
  35.   assm.jnz(labels.open_label);
  36.   assm.bind(labels.close_label);
  37.   break;
  38. }

どのラベルをジャンプに使って全く同じLabelを出力したのかを覚えておく必要があります。asmjitが自身で後埋めをします。さらに、自動的にジャンプオフセットを算出します。

コード出力をすれば、呼び出しができます。

  1. using JittedFunc = void (*)(uint64_t);
  2.  
  3. JittedFunc func;
  4. asmjit::Error err = jit_runtime.add(&func, &code);
  5. // [...]
  6. // 呼び出し、メモリのアドレスをパラメータとして渡す。
  7. func((uint64_t)memory.data());

以上です。このJITは事実上simplejitと全く同じコードを出力するため、動作も全く同じです。ここのポイントはasmjitのようなライブラリを使ってコードを出力することがどれだけ簡単で楽なのか知ってもらうことです。ゴチャゴチャとしたコードやオフセット演算などを隠してくれるため、出力される命令のシーケンスのようなプログラム固有の部分に集中することができます。

optasmjit – BFの最適化にJITを組み合わせる

最後にパート1で開発した賢い最適化をJITに組み合わせます。ここでは、パート１のoptinterp3をJITのバックエンドに固定します。結果はoptasmjit.cppになります。

覚えていると思いますが、8つのBF演算の代わりに、整数の引数を持つ拡張セットがあり、場合によっては高水準の演算を伝達します。

  1. enum class BfOpKind {
  2.   INVALID_OP = 0,
  3.   INC_PTR,
  4.   DEC_PTR,
  5.   INC_DATA,
  6.   DEC_DATA,
  7.   READ_STDIN,
  8.   WRITE_STDOUT,
  9.   LOOP_SET_TO_ZERO,
  10.   LOOP_MOVE_PTR,
  11.   LOOP_MOVE_DATA,
  12.   JUMP_IF_DATA_ZERO,
  13.   JUMP_IF_DATA_NOT_ZERO
  14. };

BF演算からBfOpKindのシーケンスに変換する段階はoptinterp3での段階と全く同じです。では、新しい演算がどのように実装されているか見てみましょう。

  1. case BfOpKind::INC_PTR:
  2.   assm.add(dataptr, op.argument);
  3.   break;

インタプリタの時のように1のインクリメントは追加した引数に置き換えられます。ここでは、異なる命令を使用します。incの代わりにaddを使います4。では、もっと面白いものをお見せしましょう。

  1. case BfOpKind::LOOP_MOVE_DATA: {
  2.   // 現在のデータが０でない場合のみ移動。
  3.   //
  4.   //   cmpb 0(%r13), 0
  5.   //   jz skip_move
  6.   //   <...> データの移動。
  7.   // skip_move:
  8.   asmjit::Label skip_move = assm.newLabel();
  9.   assm.cmp(asmjit::x86::byte_ptr(dataptr), 0);
  10.   assm.jz(skip_move);
  11.  
  12.   assm.mov(asmjit::x86::r14, dataptr);
  13.   if (op.argument < 0) {
  14.     assm.sub(asmjit::x86::r14, -op.argument);
  15.   } else {
  16.     assm.add(asmjit::x86::r14, op.argument);
  17.   }
  18.   // オリジナルポインタの値を一時的にraxで保持。
  19.   // 新しい位置にalを使って追加。
  20.   // これにより対象位置のみが影響: addb %al, 0(%r13)
  21.   assm.mov(asmjit::x86::rax, asmjit::x86::byte_ptr(dataptr));
  22.   assm.add(asmjit::x86::byte_ptr(asmjit::x86::r14), asmjit::x86::al);
  23.   assm.mov(asmjit::x86::byte_ptr(dataptr), 0);
  24.   assm.bind(skip_move);
  25.   break;
  26. }

繰り返しになりますが、このコードはasmjitで書く方が簡単です。また、メモリに触れるときに、バイトに粒状されたデータを細心の注意払って処理することにも注目してください。これを開発する際には、いくつかの厄介なバグに遭遇しました。実際、BFメモリセルに機械固有のワードサイズ（この場合は64ビット）を使用すると、全てが簡単になりました。 8ビットのセルは、言語の共通の意味に近く、さらに挑発してくれます。

パフォーマンス

では、optasmjitのパフォーマンスが最速のインタプリタや最適化されていないJITに比べてどうなのか見てみましょう。mandelbrotは0.93秒、factorは0.3秒。3つの比較は以下の通りです。

BF opt3 vs simplejit vs optasmjit

特に最適化したインタプリタとのパフォーマスの差はとても大きいことが分かります。JITは4倍も高速です。単純なインタプリアをも比較に入れるとoptasmjitは約40倍も高速です。同じグラフで比較するのが困難です。

BF full performance comparison for part 2

JITは楽しい

個人的にJITは楽しいと思います。手作業で全ての命令を出力するコンパイラを作成できるのがいいです。しかし、asmjitのような処理を簡単にするライブラリなしではコード化に手間がかかります。

今回のパートは内容が濃かったと思います。optasmjitはBFのための本物の最適化JITです。以下のことを実現してくれます。

  • BFソースをパースする。
  • 高水準演算のシーケンスに変換する。
  • これら演算を最適化する。
  • 演算をタイトなx64アセンブリをメモリにコンパイルして実行する。

これらのステップを実際のコンパイラ専門用語に結び付けましょう。BfOpKind演算はコンパイラIRとして見ることができます。ほとんどの場合、コンパイルの最初のステップは、人が読めるソースコードをIRに変換することです(現実的な言語においては変換自体が複数のステップに分割されています)。演算からアセンブリへの変換・コンパイルは、しばしば “下げる” と言われます。コンパイラによっては複数のステップや中間IRが必要となります。

大量のコードになってしまうため、記事に載せなかったコードがたくさんあります。ここで触れたファイルの全ソースファイルを見て理解することをお勧めします。JITは全て単一単体のC++ファイルです。

  1. 伝統的にと言った理由は、現代の多くのコンパイラはもうこのように動作しないからです。例えば、LLVMはIRを機械コードレベルの命令を表すはるかに低水準のIRにコンパイルします。アセンブリはこのIRから出力されますが、機械コードも直接出力されるため、アセンブラはコンパイラに統合されます。 ↩

  2. コンパイラによっては2回のパスを実行します。パート1の最初のインタプリタの最適化に類似しています。2回目のパスがどのオフセットを出力すればいいのか分かるよう、1回目のパスで情報（対応する全ての）の場所など）を収集します。 ↩

  3. 詳細については、asmjitのドキュメントを参照してください。また、asmjitには、レジスタ割り当てなどの、より洗練された処理を行う “コンパイラ” レイヤがあります。 この記事ではベースアセンブリレイヤだけを使用しています。 ↩

  4. 最初からincの代わりにadd 1を使えばよかったのでは、と思っている方もいるでしょう。確かにそうです。実際、複雑なマルチポートパイプラインのx64 CPUが使われている昨今、別のinc命令がある正当な理由が存在したのかもしれませんが、どちらが高速なのかははっきりしません。多様性を示すため両方をお見せしました。 ↩

Previous Post