2026/04/15 21:00
JIT コンパイラーを C インタープリターに統合するための手順です。 1．JIT コンパイラーのソースコードをコンパイルしてオブジェクトファイルを作成し、インタープリター実行時に動的リンクすることで結合します。 2．C のループから JIT で生成された機械語コードへ制御を転送する軽量なブリッジ関数を実装します。 3．JIT コード内で発生した低レベルの例外と、C インタープリターが期待する高レベルの例外の間でのマッピングを行い、例外の伝播処理を実装します。
RSS: https://news.ycombinator.com/rss
要約▶
日本語訳:
最も重要な進展は、既存のコードとの完全な互換性を保ちつつ、低速な C インタプリターを高速な即時実行（JIT）コンパイルされた仮想マシンへ自動変換する yk の「メータースレーシング」技術です。約 400 行もの専門的な C アノテーション（
yk_promoteyk_idempotent本文
C インタプリターは一般的な言語実装手法であり、Lua、Ruby、Python などの標準的なリファレンス実装の基礎となっています。不幸にも、C インタプリターは遅く、特に JIT コンパイラを駆動する言語実装と比べた場合尤为顕著です。本記事では、C インタプリターに対してごく少数のコード変更を加えるだけで、それを自動的に JIT コンパイルを行う仮想マシン（VM）へと変換できることを示します。これは、以前は到達不可能だった「参考実装との完全互換性を維持しつつも性能が向上した」という設計空間上の一点を提供します。
この仕組みを実現するシステムは「yk」であり、これにはしばらく取り組んできました。ここで期待値を適切に設定させておきます。yk はアルファステージのソフトウェアであり、生産環境で即用できる状態ではありません。しかし、単なるハッカティブな研究プロトタイプとは比較にならないほど、機能範囲と品質において進歩している段階です。プログラムが停止する TODO 箇所や、実行が最適化されておらずサブオプティマルに続く欠落部分を見つけやすく、まだ望む最適化の全てを実現しておりません。また現在では x64 アーキテクチュアのみの実装であり、性能に関する強い結論を引き出すために必要なような言語の多様さやベンチマークもまだ揃っていません。
とは言え、既に興味深い結果が見て取れます。プログラミング言語の性能を見るのは難しいですが、こちらの動画でイメージを掴んでいただけるかもしれません。まず、Mandelbrot プログラムを通常の PUC Lua VM（参考実装）および yklua（自動導出された JIT コンパイラーを持つ PUC Lua のフォーク版）を通じて実行します：
[動画]
私は承知していますと自白しますが、上記のビデオでは平均を上回る性能を示す選択的な例を用いています。ビデオで見られる約 4 倍の改善ではなく、現在の Lua ベンチマークスイートにおける幾何平均はより現実的と言える値で、わずかに 2 倍未満です。小さなベンチマークには、私が後述する技術の影響を平坦化させやすい傾向があり、そのため「本物」のプログラム群では平均してさらに低い値となります。
驚くべきことに、PUC Lua への追加は約 400 行（LoC）、変更されたコードは 50 行未満です。これは yk が提供するトレードオフを明確にする助けとなるはずです：yklua は素晴らしいかつ手作業で慎重に設計された LuaJIT のような性能の頂点には達していませんが、LuaJIT はまだ 13 年前の Lua 5.1 という過去に留まっているのに対し、yklua は PUC Lua の更新を容易に追従できます。本記事の目的は、このトレードオフのどちらかが優れていると述べることにあるわけではありません。その両者のトレードオフが存在すること、そして yk が以前には主に手の届かない領域である設計空間の一部を埋めることを示すことにあります。
yk に Lua 固有の性質は一切ありません。他にもいくつかの小型実装と共に、最近 MicroPython の調整にも数日費やしており – おそらく名称のパターンをご存じかと – ykmicropython が生まれました。MicroPython インタプリターには現在サポートしていないイディオムが使われており、それらを遭遇するベンチマークは現時点では極めて悪い性能を示しています。しかし、そのような部分に頻繁にヒットしないプログラムであれば、既に有意な性能向上を確認できます。Mandelbrot ベンチマークは ykmicropython が最も得意とする領域ではありませんが、それでも違いは確認できます（通常の MicroPython が上部、yklua 版が下部）：
[動画]
将来的には、C インタプリターを持つ方々 – 大きくとも小さくとも – が yk を利用して最小限の労力で JIT コンパイラーを追加し、無料で追加性能を獲得できることを期待しています。
本記事では yk が創られた理由、なぜこのように機能するのか、および関与している技術的課題について説明します。この記事の長さにもかかわらず、私が言うべき全てを網羅することは到底できず、必然的に記述内容を簡略化する必要があります。今後の記事でより詳細やニュアンスを追加し、yk の進化を追跡できれば幸いです。
本稿における作業は、Shopify および英国王立工学院によって資金援助を受けた共同研究であり、両者に感謝申し上げます。もちろん私はどちらの組織も代表しているわけではありませんが、両者への多大な助成に対し深く謝意を表します。この記事で紹介する作業は Edd Barrett 氏、Lukas Diekmann 氏、Pavel Durov 氏との共同努力です。また、当初 yk は単なる小規模デモしかなかった時代にその早期支援者として惜しみなく支えていただいた、亡くなられた Chris Seaton 氏へのこの作業を捧げます。彼は私たちが友人と考えた方々の中でどれほど見なされているか。
なぜ JIT コンパイラーは難しいのか
多くのプログラミング言語はインタプリタとして実装されています。これは動的型付け言語で最も一般的なアプローチですが、CPU シミュレーターからドメイン特化言語に至るまで、意外に多くの他の言語でも同様の状況です。インタプリターは単純に書ける反面、優れた性能は持ちません。
そのため、インタプリターに Just-In-Time (JIT) コンパイラーを追加することが一般的です。JIT コンパイルの基本的な命題は、「過去短期間でのプログラム実行様式は、将来の実行様式を示唆する」というものです。したがって JIT コンパイラーは投機的にプログラムを最適化し、その推測が成り立てば良好な性能を得られ、推測が破綻すれば（一時的であっても）性能低下が生じます。
JIT コンパイラーは実行中のプログラムを観察し、ホット（頻繁に実行される部分）とその周辺コンテキスト（例：使用されているオブジェクトの型など）を特定して抽出・最適化し、それらをマシナ言語（以下「JIT コード」と呼ぶ）にコンパイルします。その後、この JIT コンパイルされたコードでインタプリタの代わりに実行が行われます。
JIT コンパイラーの作成は困難かつ高コストです。最も顕著なのは、繊細で複雑な部品を多数含み、著者は複数分野の専門家である必要があることです。軽微な過ちが数日の挫折に満ちたデバッグをも招き、アーキテクチャ的な錯誤は数年かかっても是正できません。10 年前にも私よりも詳しい有識者が HotSpot（通称「JVM」、標準的な Java VM）には既に 1,000 人以上分の人年を費やしていると推定していたほどです。Chrome に搭載されている JavaScript JIT コンパイル型 VM の V8 も、多数のメンバーが長年にわたり取り組んできた製品です。
より不透明なのは、複雑さゆえに進化させることが困難である点です。たとえてある言語バージョンに対する完全互換的な JIT コンパイラーを作成できても、言語仕様の管理側は仕様の拡張や変更を余儀なくされます。言語仕様の変更が JIT コンパイラー内部深く埋め込まれた前提を崩し、後者を仕様に追いつかせることが難しくなります。最終的には「遅れ」が「決して追いつかない」という状況へ変化し、それが不関連性の始まりとなることが多いです。
さらに JIT コンパイラーで完全（「完全」！）な互換性を達成するのも困難です。多くの場合、最良の JIT コンパイラーを作成するには新しい VM を作成する必要があり、そのためには事実上完全に互換性を諦めることを意味します。新しい VM は既存の拡張モジュールとの相互運用ができず、ファイナライザーを異なるタイミングで実行したり、標準ライブラリの全機能を実装しないなどです。ユーザーが新しい VM を試みて既存のソフトウェアが動作しなければ、さらに実験を行うことはなく、その VM に時間を無駄にするまいと決意するに至る傾向があります。
JIT コンパイラーの作成が極めて困難であることを示す最も良い証拠は、公開されている Python 用の JIT コンパイラーを列挙してみることです：Cinder、IronPython、Jython、Nuitka、Psyco、Pyjion、PyPy、Pyston、S6、Shed Skin、Skybison、Starkiller、TrufflePython、Unladen Swallow、WPython、Zippy。これらの中で今も活動しているものはほとんどなく、有識な人々の関与や多数のユーザーの希望にもかかわらずです。
自動的な JIT コンパイラー
上記の問題を回避するには、いかにしても自動的に JIT コンパイラーを作成する必要があります。インタプリタから自動的に JIT コンパイラーを作成する方法には主に 2 つのアプローチがあり、それらの代表例として RPython（PyPy プロジェクトの一部）における meta-tracing と Truffle における (ある種の) partial evaluation を挙げることができます。
RPython および Truffle は技術的偉業であり、私は両プロジェクトの成果に引き続き畏敬の念を抱いています。それぞれの異なる方法とトレードオフを通じて、インタプリターから驚異的な高性能な JIT コンパイラーを生み出すことができます。しかしながら、課題があります：いずれのシステムも新しいインタプリタの作成を必要とします。これにより、私が以前述べた「ほぼだが完全には互換でない」問題に直面します。おそらくこの理由から、両システムとも優れた性能にもかかわらず、広範な使用に見られることはありませんでした。
C インタプリターからの JIT コンパイラーの導出
最適化に興味を持っている大部分の言語は英語仕様に伴いますが、ユーザーは実際には参考インタプリタの動作を事実上の仕様と見做す傾向があります。言語弁護士という立場からはユーザーは明らかに間違っていましたが、ほとんどの方が言語弁護士が存在することに気づいていません – 彼らは手元のタスクを完了することに主に関心があります！
これの意味するところは、数年も完全には内部化しなかったほど明らかです：多くの言語において、C インタプリターが真実の源となっています。正しいか誤りかはさておき、その真実から逸脱した実装 – たとえ些細なことであっても – は大勢の利用者の受け入れられません。
これは RPython や Truffle が素晴らしいものであるとしても、設計空間に重要なギャップを残しています。私が最終的にこの現実を目覚めさせた際、私たちが答えなければならない問題は明らかになりました：C インタプリターから自動的に JIT コンパイラーを導出することは可能でしょうか？もしそれができれば、より速い言語実装を利用しない多くのユーザーが抱える互換性問題を防ぐことができます。
他の方々は少なくとも一定程度この類の着想を持っており、同様の目的を共有するいくつかの研究成果が存在します：特に忘れ去られがちな論文と後の copy-and-patch です。これらのアプローチに必要な（時には大きな）手動作業を置いといても、それらの基本的な目標はインタプリタのコアループを JIT コンパイルすることです。これは価値のあることですが、多くのプログラムはそのループの外側で時間を過ごしています。例えとして「オブジェクト o1 == o2 かどうか」といった基本的機能も、コアループ外にある関数へ委譲されることが多いです。私の見解では、良い性能を得るためには、コアインタプリタループをはるかに超えたコードインライン化が可能である必要があります。
結局のところ、私の小さな脳の中で、現実的に目標を達成できる唯一の技術は meta-tracing であるとしました。そして実際、yk はまさにそれをやっているのです：C インタプリターに対して meta-trace を適用します。これが通常の C Lua VM に数行追加することで JIT コンパイラーへと変換できた理由です。
しかし「C 向けの meta-tracing」という単なるフレーズほど簡単なものではありません。率直に言えば、丸い穴に四角い釘を無理やり押しこもうとするのと同じで、私が出会った複数の人物から礼儀正しくも「絶対に成功しないだろう」と言われました。実際、この実用化に向けて大小さまざまな問題を解決する必要がありました。
トレースとメタトレーシング
メタトレーシングは説明が難しい技術ですが、できる限り努力します。まず用語を再定義しましょう：Truffle よりも採用されている用語に従います。「ホスト言語」はインタプリタを書いた言語（例：C）であり、「ゲスト言語」は実装される言語（例：Lua、Ruby、お好みの CPU シミュレーターなど）です。
トレース
簡潔に非メタのトレーシング型 JIT コンパイルを見てみましょう。そのようなシステムはゲストプログラム内のホットループ（for や while ループなど）を探します。それを見つけると、次のループ反転の実行をトレース（記録）し、最適化してマシナコードへとコンパイルします。インタプリタが次にそのループを実行する際、JIT コードに実行を渡します。
例えば、以下のゲスト言語プログラムを考えます：
for x in ... do if x > 0 then y = y + 3 end end
この for ループがホットになりトレース対象となったと仮定しましょう。特定の反転では x が具体的に正の値を持ったとします。得られるトレースは概ね以下のように見えます：
OP_LOOKUP("x") guard true, pop() > 0 OP_LOOKUP("y") OP_INT(3) OP_ADD OP_SET("y")
トレースは主に、実行されたゲスト言語操作（オPCODE やバイトコード）の記録です。これをマシナコードに JIT コンパイルし、インタプリタの代わりに使用します。
ただしトレースには一見奇妙な点があります：for ループを実行した際、x > 0 が true に評価され if 文の true ブランチが実行されました。上記スニペットでは y = y + 3 は明示的にありますが、if がガーデに変わっています。形式的には、トレースは制御フローを直列化していると言えます。平易な英語で言えば、トレースは if 文の真偽どちらか一方だけを記録し、両方を同時には記録しません。
つまり、トレースはプログラムの一部のみを記録しており、ある時点でそのサブセットを超えて実行が進む必要があります。ガーデはその点を記録します：ガーデが破綻すると、残りのトレースは無効です。この場合、JIT コンパイルされたコードはインタプリタへ再最適化（deoptimise）する必要があります。
これにより、トレーシング型 JIT コンパイラーと一般的な「メソッドベース」の JIT コンパイラーとの根本的な違いが直ちにわかります。後者は頻繁に実行される関数を探し、見つければその関数を (ランタイム！) 従来の GCC/Clang などが関数をコンパイルするのと同じ方法でコンパイルします。つまりメソッドベースの JIT コンパイラーは、トレーシング型よりも遥かに多くのプログラム動作を捉えたコードを生み出します。
長い記憶を持つ読者の中には、Firefox の最初の JavaScript JIT コンパイラーが TraceMonkey だったことを覚えているかもしれません。名前の通り JavaScript 向けのトレーシング型 JIT コンパイラーでしたが、性能記録は一様ではなく、2〜3 年後メソッドベースの JIT コンパイラーに置換されました。この経験から数年来の人々が「トレーシング型 JIT コンパイラーはあらゆる面で劣る」と宣言してきました。
私の見解はよりニュアンス豊かです。十分な時間と資金があり、新しい領域（グリーンフィールド）がある場合、メソッドベースの JIT コンパイラーが一般的に優れているでしょう。しかしその 3 つの要素を欠く場合は、技術的な選択も異なります。yk は明示的に「グリーンフィールドがない場合」を対象としています。
メタトレーシング
メタトレーシングとトレーシングはどう違うでしょうか？トレーシング型 JIT コンパイラーは特定のゲスト言語に特化しており、手書きのトレースレコーダー、手書きの最適化器、手書きのコードジェネレーターを含みます。一方、メタトレーシングシステムは「お好みのゲスト言語用のインタプリタを渡していただき、残りの仕事を手伝います」と言います。これを行うには、ホスト言語のインタプリタがゲスト言語を実行している間の動作を記録します。
例えば C インタプリターがある場合：
Instruction *code = ...; int pc = 0; Value **stack = ...; while (true) { Instruction i = code[pc]; switch (GET_OPCODE(i)) { case OP_LOOKUP: push(lookup(GET_OPVAL())); pc++; break; case OP_ADD: push(pop() + pop()); pc++; break; case OP_JGT: if (pop() > 0) pc++; else pc += GET_OPVAL(i); break; case ...: ... } }
以前のゲスト言語のスニペットが以下のトレースに導きます：
push(lookup("x")); pc++; guard true, pop() > 0; pc++; push(lookup("y")); pc++; push(3); pc++; push(pop() + pop()); pc++; set("y", pop()); pc++;
これはホスト言語インタプリタ自体がゲストプログラムを実行している間に実行されたコードの記録であることを示唆します。ここで見る (メタ-)トレースは、C インタプリタの動作に対するトレースです。このトレースはメタトレーサーによって自動的に構築され、その後最適化器およびコードジェネレーターへ渡されます。つまり、メタトレーシングは非メタのトレーシング型 JIT コンパイラで手書きしなければならない部分を自動化します。
メタトレーシングにはもう一つ強調すべき点があります：それは自然かつ積極的に関数呼び出しへのインライン化を行います。つまり
push(...)pushguard true, *used < *capacity; storage[*used] = elem; *used += 1;
このインライン化能力はメタトレーシングの強みの根本であり、yk が以前の C インタプリター加速アプローチと異なる理由です。
C インタプリタからメタトレーシング対応インタプリタへ
メタトレーシングの高次アイデアを見た後、次に yk はどのように C インタプリタをメタトレーシング対応なものに変換するかという疑問があります。最初の重要な部分は、LLVM のフォーク – 待ってください – ykllvm を使用してインタプリタをコンパイルすることです。基本的にはインタプリターの Makefile で cc と ld を以下のようになるだけです：
'yk-config release --cc' -o vm.o vm.c 'yk-config release --ldflags' -o vm vm.o
より深く言えば、ykllvm は主に 3 つの機能を追加します：トレース記録能力、IR シリアル化（トレース記録後にインタプリタを再構築可能に）、デ最適化の実現。後者は後で見ることにし、まず最初の 2 つから始めましょう。
ゲスト言語レベルでホットループを検出した際、インタプリタの動作を記録する方法が必要です。いくつかの方法がありますが、現在採用しているのは各基本ブロックに
__yk_trace_basicblock(id)ykllvm 経由でコンパイルされたインタプリターは概ね以下に相当します：
Instruction *code = ...; int pc = 0; Value **stack = ...; while (true) { __yk_tracebasicblock(0); Instruction i = code[pc]; switch (GET_OPCODE(i)) { case OP_LOOKUP: __yk_tracebasicblock(1); push(lookup(GET_OPVAL())); pc++; break; case OP_ADD: __yk_tracebasicblock(2); push(pop() + pop()); pc++; break; case OP_JGT: __yk_tracebasicblock(2); if (pop() > 0) { __yk_tracebasicblock(3); pc++; } else { __yk_tracebasicblock(4); pc += GET_OPVAL(i); } break; case ...: ... } }
トレースを記録すると [0, 1, 0, 1, 0, 2, ...] という基本ブロック ID のシーケンスが得られ、これは OP_LOOKUP; OP_LOOKUP; OP_ADD を実行しているゲストプログラムの表現です。
この基本ブロック ID のシーケンスを手に入れれば、次に ykllvm のインタプリタ IR（中間表現）ビューを再構築する必要があります。概ね言えば、ykllvm がコンパイル中に構築したインタプリターのツリー/グラフ表現と考えられます。yklua の通常の LLVM IR の一部をテキストで表すと：
359: ; preds = %341 %360 = load ptr, ptr %355, align 8, !tbaa !11 %361 = load ptr, ptr %352, align 8, !tbaa !11 %362 = call ptr @luaH_getshortstr(ptr noundef %361, ptr noundef %360) #18 %363 = getelementptr inbounds nuw i8, ptr %362, i64 %364 = load i8, ptr %363, align 8, !tbaa !9 %365 = and i8 %364, 15 %366 = icmp eq i8 %365, 0 br i1 %366, label %371, label %367 367: ; preds = %359 %368 = load i64, ptr %362, align 8, !tbaa !11 store i64 %368, ptr %345, align 8, !tbaa !11 %369 = load i8, ptr %363, align 8, !tbaa !9 %370 = getelementptr inbounds nuw i8, ptr %345, i64 8 store i8 %369, ptr %370, align 8, !tbaa !9 br label %3329 371: ; preds = %341, %359 %372 = phi ptr [ %362, %359 ], [ null, %341 ] store ptr %203, ptr %171, align 8, !tbaa !11 %373 = load ptr, ptr %172, align 8, !tbaa !11 store ptr %373, ptr %13, align 8, !tbaa !11 call void @luaV_finishget(ptr noundef nonnull %0, ptr noundef nonnull %352, ptr noundef %355, ptr noundef %345, ptr noundef %372) %374 = load volatile i32, ptr %173, align 8, !tbaa !11 br label %3329
ykllvm はそれを少し異なる IR に変換します：いくつかの項目を調整し（例：恐ろしく複雑な getelementptr 命令を扱いやすいバリアントに分割）、サフェアポイントを追加します（後ほど戻ってきます）：
bb47: %47_0: ptr = ptr_add %46_2, 8 %47_1: i8 = load %47_0 %47_2: i8 = and %47_1, 15i8 %47_3: i1 = eq %47_2, 0i8 condbr %47_3, bb49, bb48 [safepoint: 396i64, (%0_0, %0_2, %0_5, %0_6, ... bb48: %48_0: i64 = load %46_2 *%45_3 = %48_0 %48_2: i8 = load %47_0 %48_3: ptr = ptr_add %45_3, 8 *%48_3 = %48_2 br bb812 bb49: %49_0: ptr = phi bb47 -> %46_2, bb45 -> 0x0 *%6_10 = %29_0 %49_2: ptr = load %11_5 *%0_21 = %49_2 call luaV_finishget(%0_0, %45_10, %45_13, %45_3, %49_0) [safepoint: 397i64, ... br bb50
この「ykllvm IR」はシリアル化され（適度に効率的なバイトシーケンスに変換）、「通常コンパイルされた」C コードと並んだバイナリの特殊セクションに配置されます。トレースが記録されると、基本ブロック ID（例：47）を ykllvm IR の断片へとマッピングし、それらを組み合わせ、最適化してコンパイルできます。前述したように、「C インタプリターのメタトレーシング」という枠組みでこの記事を説明しましたが、実際にはより適切に「LLVM IR のビューに対するメタトレーシング」と記述できるでしょう。
トレースの最適化
記録された基本ブロックのトレースを単に結合してマシナコードにコンパイルしただけでは、最大でも中程度の性能向上しか得られません。実際、yk では __yk_trace_basicblock などの理由により、以前の手法よりも状況が悪くなる可能性があります！
必要なのはトレースの最適化です。yk にはいくつかの従来のコンパイラ最適化機能を内蔵しています。例：定数畳み込みにより、以下のトレースを処理できます：
%7: i8 = 8 %8: i8 = 7 %9: i8 = add %7, %8 call print(%9)
これを最適化して：
%9: i8 = 15 call print(%9)
にします。デッドロード/ストア解析により、以下のトレースを処理できます：
%8: ptr = ... %9: i8 = ... store %9, %8 ; %9 の値を %8 に格納 %11: i8 = load %8 call print(%11)
これを最適化して：
%8: ptr = ... %9: i8 = ... store %9, %8 call print(%9)
などにします。
最適化の補助
上記の最適化は有効かつ高速に実行されますが、通常のインタプリタ上では効果是中程度です。根本的な理由は、C インタプリターは任意のプログラムであり、yk の最適化器は部分的には安全に最適化できず、またはそうしても価値があるか確信できないためです。
幸運にも、インタプリタ作成者は大幅に最適化を助ける追加知識を持っています。それはゲスト言語に関する情報（例：関数のオPCODE は不変）やインタプリタに関する情報（例：無制限に見えるループは実際には小さな回数だけ実行される）などがあります。
重要なのは、この知識が直接 C コードには表れていないことです。必要なのは、インタプリタ作成者がこの追加知識を yk に伝え、最適化器が活用できるようにすることです。幸運にも RPython は这方面的な知的重労働を多く行い、多くの概念を再利用できます。驚くべきことに、C コードの数行を追加または調整するだけで、JIT コンパイルされたコードの性能に著しい向上をもたらせます。その理由を理解するために、yk が提供する主要な最適化機能 2 つの詳細に入ります。
プロモーション
まずはコア機能の 1 つである「プロモーション」から始めましょう。これはランタイム値をトレース内の定数として「焼付け」（burn）し、関連するガーデ（後続の実行で値が変更された場合、再最適化が発生して実行が正しいことを保証）も伴います。
yk は
yk_promoteyk_promote例えば以前の C インタプリターで OP_INT(x) を以下のように実装すると仮定します：
... case OP_INT: push(yk_promote(constant_pool[GET_OPVAL(i)])); pc++; break;
yk_promotetmp = constant_pool[i & 8] push(tmp)
yk_promotetmp = constant_pool[i & 8] guard true, tmp == 3 push(3)
悪いニュースはガーデを挿入しなければならない点（推測が成り立たない場合）ですが、良いニュースはガーデの後で tmp が未知の値ではなく定数 3 であると確実であることです。これは – 少し手抜きして説明しますが、詳細に込めると時間がかかります – 次のようなシーケンスを見たら：
tmp = constant_pool[i & 8] guard true, tmp == 3 push(3) pc += 1 i = code[pc] tmp = constant_pool[i & 8] guard true, tmp == 4 push(4) push(pop() + pop())
最後の命令をスタックを見ないで
push(7)イディオプンツ関数
上記の例から推測できるように、
yk_promote必要な追加ツールはイデオポテンツ関数の表現方法です：これは同じ入力を与えれば常に同じ出力を返す関数です。yk は
yk_idempotent以前の C インタプリターの以下の行を思い起こしてください：
Instruction i = code[pc];
特定の pc に対して常に同じ Instruction を返すと仮定します（例：pc 4 では常に OP_ADD）。この行を関数呼び出しに変えます：
Instruction i = load_inst(yk_promote(code + pc));
そして適切な
yk_idempotentload_inst__attribute__((yk_idempotent)) Instruction load_inst(Instruction *pc) { return *pc; }
トレース記録中に yk は
load_instload_instyk_promoteload_inst(0x1234)明らかな利点はオPCODE のロード自体を削除できた点ですが、本当にやろうとしているのは yk の最適化器が命令デコードに対して自由に動作できるよう開放したことです。例え
GET_OPVAL#define GET_OPVAL(i) ((i & 0b11110000) >> 4)
であれば、yk は i が 0b01110111 であることを知っていれば、
GET_OPVAL(i)良いニュースはここで終わりません。pc をプロモーションしたので、
pc += GET_OPVAL(i)load_instyk_idempotent他の最適化
yk は他にも最適化機能を提供します。例えばデフォルトでは yk はループを含むホスト言語関数をトレースにインライン化せず、
yk_unrollしかし全ての可能な最適化を網羅するのではなく、私の説明から皆さんが始めて気づいていただけているように、多くの C インタプリターには yk を助ける低掛かりな果実がたくさんあることにあります。実際、この記事の冒頭で示した大部分の性能向上はインタプリタへの基本調整（数個の
yk_promoteyk_idempotentyk_unroll開かれている質問は「さらにどの程度の利益を得られるか」です。私の直感では：かなり多いですが、それはあなたが導入する変更の侵襲性に大きく依存します。
最小限には、インタプリタを yk 向けにするための単純なリファクタリングがあります。例えば、非常に大きな重要な関数に単一の無制限ループがある場合、そのループを独立した関数へ移動することで大規模関数をインライン化可能です。より困難ですがインタプリタ依存度が高いのは Self スタイルのマプを追加することであり、yk の最適化器に多くの機会を開きます。
逆方向のコード生成
yk は十分に大きくなり、複雑になり、新規性も多いため、可能な限り他から優れたアイデアを窃取しています。最近活用している 1 つのアイデアは LuaJIT から由来します：yk はトレースを逆方向に進んでマシナコードを生成します。これはより良いコードを速く生成でき、実装复杂性を減らせることが分かりました。おそらく yk がこのことを行う第 2 システムであるため、その利点の概要を提供する価値があります。
例え：
%5: i8 = load %4 %6: i8 = load %4 %7: i8 = add %5, %6
yk はまず add の x64 コードを生成し、その後 2 つのロードを生成します。这样做る主な理由は単純なレジスタ割り当てと暗黙的なデッドコード除去です。
レジスタ割り当てはコンパイラにとって簡単なはずですが、実はそうでない場合があります。変数（例：トレースの %x 変数）を CPU レジスタ（例：rax）に割り当てます。レジスタが不足する（現代 CPU で一般的に 16 個）とスタック（無限に近いサイズ）へ移動させます。無造作に行うと変数がスタックに多く残り、性能が急激に低下します。
前述したように良いレジスタ割り当ては簡単ではありません。実際、「十分な速度で動くコードを生成する」と「使用不可能な遅いコンパイラを作らない」の間のトレードオフが極めて困難であり、レジスタ割り当ては数十年も継続的に研究されてきました。その理由を簡潔に要約するのは難しいですが、基本的にはプログラムで任意に遠く前後を見て良いレジスタ割り当てが必要であり、それは複雑な制御フローを持つプログラムにとって困難かつ高コストです。
幸運にもトレーシングコンパイラでは LuaJIT が全く異なるアプローチを採用することを示しました：逆方向のコード生成です。通常の前方コード生成では変数に比較的自由なレジスタを割り当てて、後続のトレース部分がそれを良選択だと祈ります。一方、逆方向コード生成では現在が良選択であることを知りながら変数にレジスタを割り当て、必要な調整は「以前」のコードへ任せます。これら 2 つの選択は一見同等そうですが、実際にはそうではありません。
しばらくの間 yk は前方コード生成を採用していました。レジスタ割り当て器は扱いにくく壊れやすく、概ね良いコードを生成するには初期逆方向パスが必要でした（変数のライフタイム計算や、「この変数は後で rdi に間違いなく入る」といった判断）。
初期逆方向パスが必要だったことは、LuaJIT のアプローチを採用するきっかけとなりました。最初に逆方向コード生成が頭を痛めたことを認めましょう：前方コード生成の方が直感的です。しかし慣れると、最終的なレジスタ割り当て器は比較的扱いやすくなりました。重要なのは使いやすい、実行が高速、そして前方コード生成よりも遥かに良いコードを生成することです。
前述したように逆方向コード生成は暗黙的にデッドコード除去を行います。プラットフォームバックエンドが変数 %7 をどのレジスタに置くか尋ねる時、それは暗黙的に「%7 は後続のトレースで使われる」と宣言しているのです。これを 1 ビットで記録します。つまり %7 のライフタイムを計算する必要はなく、最初の遭遇（逆方向コード生成では最終使用）時に発見します。その後 %7 を処理する際に「この変数は副作用を持つか？」（あるならコード生成が必要）、「そうでない場合は後続のトレースで使われるか？」（後者条件がデッドコード除去）を判断します。全体として、デッドコード除去は 10 行未満です。
これを強調するのは、トレースには大量のデッドコードが含まれているためです（トレース最適化やプラットフォーム固有のコード生成トリックによるもの）。例：
%2: ptr = ... %3: ptradd %2, 8 %4: load %3
x64 では yk は以下の x64 コードを生成します：
; %2: ptr = ... mov rax, ... ; %3: ptradd %2, 8 ; %4: load %3 load rdi, [rax+8]
ptradd 命令のためのコードは生成されません（ロードがそれを間接的に組み込んだため）。これは自明のように見えますが、%3 のためのレジスタを使用せず済んだことを意味します。頻繁に行う必要はありませんが、レジスタ割り当てに大きなポジティブな影響を与えます！
場所 (Locations)
鋭い読者は私がインタプリタがゲスト言語ループの所在を yk に伝える方法について明瞭化していないことに気づいたかもしれません。予期通り、yk は Lua や Ruby や Python のループが始まり終る場所を全く知りません：実際、such languages が while ループを持つか別の構文を持つかさえ知りません。
yk にループの所在を伝えるため、インタプリタは control point に location を渡します。location は単純で、ゲストプログラムの一部（通常はユーザープログラムの特定の OPCODE）に関する情報を yk に伝えます。control point はより複雑で、インタプリタ内で yk に制御権を渡し location とともに発生する地点です。control point 呼び出しは何もしない場合、トレースを開始する場合、またはコンパイルされたトレースの実行を開始する場合もあります。
私たちの目的では、location を 2 つの風味に分けて考えられます：
- null: このゲストレベルの pc はループの開始点ではない。
- loop: このゲストレベルの pc はループの開始点である。
これらはそれぞれ
yk_location_nullyk_location_newYkLocation は意図的にマシン語幅で定義されており、効率的に格納できます（例：関連 OPCODE に隣接して）。最も簡単な方法はユーザープログラムの各 OPCODE に対して 1 つ YkLocation の配列を作成することです。例え backwards jump OPCODE OP_JMP で while ループを表現する言語があれば、以下のように YkLocation の配列を作成します：
Instruction *code = ...; YkLocation *yklocs = calloc(sizeof(YkLocation), prog_len); for (int pc = 0; pc < prog_len; pc++) { Instruction i = code[pc]; if (prog[pc] == OP_JMP && GET_OPVAL(i) < 0) yklocs[pc] = yk_location_new(); else yklocs[pc] = yk_location_null(); }
そして主なループに control point 呼び出しを以下のように挿入します（yk を
yk_mt_new(NULL)YkMT *mt = yk_mt_new(NULL); Instruction *code = ...; YkLocation *yklocs = ...; int pc = 0; Value **stack = ...; while (true) { Instruction i = code[pc]; yk_mt_control_point(mt, &yklocs[pc]); switch (GET_OPCODE(i)) { case OP_LOOKUP: ... ...
基本的にはインタプリタでこれだけ行うと実装完了です。その後「ループの正しい開始点はどこか」「何谓ループか（例：再帰呼び出し）」「良いトレースは何か（多いことも悪い）」など深い疑問が残ります。一部はインタプリタ作成者の問題、一部は yk の助けを必要とし、まだインタプリタ作成者が必要とする全ての機能を実装していません。ここでは詳しく語らず、今後数日以内にこのテーマに戻る予定です：最近いくつか有望な設計を試みているためです。
デ最適化 (Deoptimisation)
以前「推測」と「再最適化」について多く話しました。要約すると、値を推測する際にガーデを残し、ガーデが破綻すると JIT コンパイルされたコードから C インタプリタへ戻ります。
専門知識を持つ人々にとって「C インタプリタに戻る」は技術用語で言うなら「狂気」のように聞こえます：LLVM がコンパイルしたバイナリの任意のポイントをどこにでも飛び込むようなことのように思えるからです。
幸いなことにそれは可能です – ただしかなりの作業と一部のトレードオフの受容が必要です。詳細に入る前に大まかな必要な動作を考えましょう。control point から JIT コンパイルされたコードの実行が始まる際、新しい関数フレームは作成されません：代わりに AOT (Ahead-Of-Time) LLVM コンパイルバイナリの関数フレームを継承し、その後自分で好きなものを末端に追加します。
ガーデが破綻した時、プログラムを停止させ、スタックを AOT バイナリに適した形状に調整し、適切なレジスタに値を入れ、AOT バイナリの正しいオフセットへジャンプする必要があります。
LLVM がそのようなユースケースを意識して構築されていないことに驚かないでしょう。幸いなことに必要な基本的な道具を持っています：stackmap。これは LLVM IR 上のある時点でレジスタとスタックのレイアウトを伝えます。その上で stackmap に基づく独自の safe point コンセプトを作りました：本質的に safe point は通常の LLVM 命令と stackmap のペアです。本質的に ykllvm は各分岐と関数呼び出しで safe point を記録します。トレース内でガーデが作成される間際、yk はそれに関連する safe point スタックを知ります。「スタック」という理由はインライン化によるもの：ガーデに関連する分岐は、トレース開始点から多数の関数深さにある可能性。各関数呼び出しの前に safe point を記録することで、AOT フレームのスタック（有ったはずが）の内容を知るようになります。
stackmap は概念的に単純です：LLVM 変数 %7 に対して「この値はレジスタ rdi, r8 およびスタックオフセット 0x7F に格納されている」といった情報を記録します。しかし実際には LLVM のこの部分はまだ実験的であり完全には行われていないため、1 つの場所のみ（例：%7 は rdi に）しか記録しません。さらにインライン関数に渡されるcallee-saved レジスタなどの追加情報を知る必要もありました。したがって ykllvm では stackmap を拡張してそれを遂行できるようにしました。
次に LLVM が stackmap を自由に移動させ、それらと元の隣接命令の間に挿入する指令を許すという事実に対処する必要がありました。これにより stackmap は正確な情報を含まず、もはや有効な safe point でなくなります！これを解決するために、stackmap を適切な隣接命令と再関連付けし、stackmap を適切に更新する新しいパスを導入しました。
ただし LLVM のいくつかの部分は我々のパスの能力を超えて問題を扱います。我々の解決策は残念ながら可追跡関数で一部の最適化をオフにするというものです。これはインタプリタを若干遅くしますが、幸いに yk のトレース最適化器はコードがトレースされた際に失われた性能を取り戻せます。
デ最適化は LLVM とは無関係な全く別の根本的な問題を提起します：スタックポインターはどうなるか？以下のコードを考えてください：
int x = ...; int *y = &x; if (z) printf("%d\n", *y);
trace を記録する際 z が false だが、後続で true になると仮定します：その時点でデ最適化し、スタックアドレスで printf を呼び出します。しかしこのスタックアドレスは JIT コンパイルされたコード実行時のスタックレイアウトに関連しており、AOT スタックでは同じ住所である可能性は低いのです。
幸いなことに解決策は単純です：シャドウスタックを導入します（新規に作成されたスレッドごとに新しいシャドウスタックを作成）で、その上にアドレスが取りたい変数を配置します。シャドウスタックは AOT および JIT フレーム間で共有され – 後者はそれを延長または変更しないため – 、JIT も AOT でも x の住所は同じになります。
結論
数週間前、ようやく yklua を Lua-5.4.6 から Lua 5.5.0 に移植しました：それは 2 年分の Lua 変更です。何時間かかったでしょうか？30 分を退屈なリンカ関連の奇妙なことに費やし、外部 Lua テストが Lua-5.5 で動作しなくなったことにもほとんど同じ時間を費やしました。「難しい」部分は最大でも 1 時間かかりました：以前のシステムではそのような変更は数ヶ月かかっただろうとさえあります。
この逸話的エピソードにもかかわらず、yk が言語性能設計空間に真の新しい点を提供し、多数の言語とユーザーに利益をもたらす可能性があることを感じていただければ幸いです。ただし yk が完成品であるようなpretend することを望みません：決してそうではありません！改善が必要なことは山のようにあります。一部は微小で少数の人にしか認識されませんが、他の部分はより深い影響を与えます。例えば執筆時点では、yklua は yk のいくつかのギャップに遭遇する形で動作しており、結果としての性能はユーモラスに悪いです。これら多くのギャップは既知であり、埋めることはロケットサイエンスではありませんが、作業が必要です。
ただし yk が持つ約束をご覧いただければ幸いです：yklua をこのように迅速に更新できることが私にとってまだ魔法のように思えます！もちろん yk の完全な約束を現実化するまでまだ多くの作業が必要ですが、我々は非常に小さなチームです（4 月時点で寛大にも数えると 1.5 人）。したがってそのペースについて現実的 باشید ください！
yk を試したい方へは、yk book から始めることをお勧めします。楽しんでください！
謝辞：Edd Barrett 氏と Lukas Diekmann 氏へのコメントに感謝。