RISC-Vエミュレーションの限界を押し広げる
Pushing the limits of RISC-V emulation (shuklaayu.sh)
要約
本記事では、RISC-Vプログラムが非RISC-Vマシン上でベアメタルパフォーマンスにどれだけ近づけるかを解説します。鍵となるのは、生成された基本ブロックをテイルコールで接続し、Clangのpreserve_none呼び出し規約を使用してホットなゲスト状態をホストレジスタに保持する、Ahead-of-Time(AOT)リコンパイラです。これにより、エミュレーション速度のボトルネックを解消し、実行速度を大幅に向上させることが可能になります。
全文翻訳
RISC-Vエミュレーションの限界を押し広げる
2026-07-26
TL;DR
この記事では、RISC-Vプログラムが非RISC-Vマシン上でベアメタルに近いパフォーマンスをどの程度達成できるかを検証しています。鍵となるのは、生成された基本ブロックをテールコールで接続し、Clangのpreserve_none呼び出し規約を使用してホットなゲスト状態をホストレジスタに保持する、事前コンパイル型(ahead-of-time)のリコンパイラです。
最近、私はAxiomで開発中のRISC-V仮想マシンであるOpenVMに取り組んでいます。これはプログラムを実行し、その出力と共に、実行が正しかったことを証明する簡潔な暗号学的証明[1]を生成します。Axiomでの私の在籍中、証明生成は単一CPUからGPUクラスターへとスケールアップし、ワークロードを複数のノードに分散させてきました。しかし、最初のステップは変わっていません。プログラムを実行し、その実行を記録する必要があります。証明フェーズは非常に並列化しやすく、追加のハードウェアでよくスケールしますが、実行は本質的に逐次的です。証明がスケールし続けるにつれて、実行速度がますますボトルネックになっており、この記事はそのステップを高速化することについてです。
実行について調べ始めたとき、私は単純な問いに立ち返っていました。「プログラムはどのくらいの速さで実行されるべきか?」OpenVMはRustのような通常の言語からコンパイルされたRISC-Vプログラムを実行するため、同じプログラムを私のマシン用にネイティブにコンパイルし、それをベースラインとして使用できます。M3 MacBookでは、ネイティブのarm64プログラムは約100ミリ秒で完了しましたが、同じプログラムが私たちのインタープリタを介すると3〜4秒かかりました。仮想マシンが遅くなることは予想していましたが、桁違いに遅くなることは予想していませんでした。
プログラムを実行する最も速い方法は、その邪魔をせず、ハードウェアに直接実行させることです。仮想マシンは、実行を制御し、ゲスト[2]とホストの間のギャップを埋める必要があるため、プログラムを単純にハードウェアに渡すことはできません。代わりに、プログラムを解釈するか、ホストが理解できる命令に変換します。この記事の残りの部分では、基本的なインタープリタから始めて、ゲストとホストの間のオーバーヘッドのレイヤーを段階的に削除しながら、このアイデアをどこまで押し進めることができるかを探求します。
インタープリタのベースライン
RISC-V[3]コードを実行する簡単な方法は、古典的なフェッチ-デコード-実行サイクルをループするインタープリタを使用することです。
問題は、ゲスト命令がしばしば非常に小さいことです。加算やシフトは単一の算術演算しか実行しないかもしれませんが、インタープリタは命令をフェッチし、そのフィールドをデコードし、switch内の正しいケースを選択し、その過程で独自の実行状態を維持する必要があります。インタープリタは、命令を実行するよりも管理に多くの時間を費やす可能性があります。
switch-case
fetch
decode
dispatch + execute
fetch
decode
dispatch + execute
例:デコードされたRISC-V命令
add rd, rs1, rs2のようなRタイプ命令は、フィールドに固定レイアウトを使用します。
opcodeは命令のエンコーディングクラスを識別します。funct3とfunct7フィールドは、そのクラス内の特定の操作にさらに絞り込み、rd、rs1、rs2は関連するレジスタを識別します。
例えば、x5 = x6 + x7を計算するadd x5, x6, x7は、これらのフィールドを次のように埋めます。
opcode: 0110011 (R-type)
funct3: 000 (add)
funct7: 0000000
rd: 00101 (x5)
rs1: 00110 (x6)
rs2: 00111 (x7)
ここで、rd、rs1、rs2はそれぞれレジスタx5、x6、x7を参照します。opcode、funct3、funct7フィールドが組み合わさってadd操作を選択します。
sub命令は同じopcodeとfunct3を使用しますが、funct7を0000000から0100000に変更します。
事前デコード
命令を実行するたびに同じ命令をデコードするのは不要です。プログラムコードは通常静的[4]であるため、各命令を一度事前にデコードして結果を再利用できます。これが事前デコードです。各命令について、その機能、オペランド、およびそれを実行する小さな関数(ハンドラ)へのポインタを格納します。
デコードはもはやホットループの一部ではありません。残っているのは、ハンドラポインタを介したディスパッチ、それに続く各命令のインタープリターループへのリターンです。
predecoded
fetch
dispatch
execute
fetch
dispatch
execute
注: switchインタープリタは命令実装に直接ジャンプしますが、事前デコードされたインタープリタは、すべての命令に対して関数呼び出しとリターンが必要です。
計算済みgotoによるディスパッチ
事前デコードはデコードのコストを削除しました。残りのボトルネックは間接ディスパッチです。すべての命令は、インタープリタが次に実行するものを選択できるように、共有ループに戻る必要があります。これに対する古典的な修正は計算済みgoto [5]です。共有ループに戻る代わりに、各ハンドラはテーブル内で次のオペコードのラベルを検索し、goto *で直接ジャンプします。
事前デコードされた表現は、以前よりもここでシンプルになります。ハンドラポインタはなく、pc / 4でインデックス付けされた配列に一度デコードされた、最初のセクションと同じInstructionがあるだけです。各オペコードは、ディスパッチターゲットとして独自のラベルを持ちます。
各命令は依然としてフェッチおよびディスパッチされる必要がありますが、インタープリタはもはや各ハンドラに対して関数呼び出しとリターンを実行しません。代わりに、各ハンドラはディスパッチシーケンスに制御を転送し、ディスパッチシーケンスは次のハンドラを選択して直接ジャンプします。したがって、実行は、繰り返し呼び出しとリターンの境界ではなく、間接ジャンプを介して1つのハンドラから次のハンドラに移動します。
computed goto
execute
fetch + dispatch
execute
fetch + dispatch
テールコールスレッディング
テールコール[6]は、各ハンドラを通常の関数として維持しながら、ハンドラを一緒にスレッドする別の方法を提供します。ハンドラは、共有ディスパッチループに戻る代わりに、次のハンドラをテールコールできます。
各ハンドラは命令を実行し、pcを前方に移動し、インライン化されたdispatchヘルパーを呼び出して、次のハンドラを見つけてテールコールします。呼び出し元で実行されることは何もないため、コンパイラは呼び出しを単純なジャンプに低レベル化でき、呼び出し元のスタックフレームを保持する必要がありません。これはテールコール削除であり、ハンドラのチェーンが一定のスタック深度で無期限に実行されることを可能にします。Clangのmusttail属性は、この低レベル化を必須にし、テールコールを発行するかプログラムを拒否します。
計算済みgotoとテールコールスレッディングは、ハンドラからハンドラへの制御フローを表現する2つの方法です。一方は関数内のラベルを使用し、もう一方は個別の関数を使用し、必須のテールコールに依存します。
状態をレジスタに保持する
すべてのハンドラは、pcのためにState *を介して到達し、すべての命令でそれを読み書きします。これらの値はすでにテールコールチェーンを介して渡されているため、関数引数として渡すことができます。ホスト呼び出し規約は通常、それらの引数をレジスタに割り当てる[7]ため、コンパイラは頻繁に使用される値を、Stateを介して繰り返しロードおよびストアするのではなく、ホストレジスタに保持できます。
// state->pc is passed as an argument
void handler(State *state, uint64_t pc, ...) {
// ... execute instruction ...
pc = next_pc;
// ... tail call next handler ...
}
これで、pcはすべての命令でStateからロードおよびストアされるのではなく、チェーン全体でレジスタに留まることができます。同じアイデアが、memのような頻繁にアクセスされるインタープリタ状態にも適用されます。
ネイティブ化
事前デコードは繰り返しデコードを削除し、スレッドディスパッチは共有ループを削除しました。残ったのは依然としてインタープリタであり、すべてのゲスト命令が実行される前にハンドラを通過していました。そのオーバーヘッドは、ネイティブ実行との間に依然として大きなギャップを残していました。プログラムはすでに事前に知られていたため、次のステップはそれをホストが実行できるものに直接変換することでした。
手書きのアセンブリバックエンド
簡単な事前コンパイル型(AOT)[8]トランスレータは、一度に1つの命令を処理します。各RISC-V命令は短いホスト命令シーケンスに変換され、生成された断片は必要な制御フローでステッチされます。変換はほぼ機械的です。addはホストの加算になり、ロードはホストのロードになります。逐次命令は自然にフォールスルーでき、固定ターゲットへのジャンプは通常のホストジャンプになります。実行時にターゲットが計算されるジャンプは、ディスパッチテーブルを介したルックアップが必要です。
トランスレータは、単一の線形パスでホストアーキテクチャのアセンブリを出力し、その後、生成されたコードは共有オブジェクトにアセンブルしてロードするだけで済みます。トレードオフは移植性です。命令エンコーディングはアーキテクチャ固有であるため、各ターゲットには独自のバックエンドが必要です。実際には、トランスレータはRISC-Vオペコードごとに1つのケースを持つswitchステートメントであり、それぞれが対応するホストアセンブリを書き込みます。
これにより、ホットパスから残りのインタープリタオーバーヘッドが削除されます。実行はもはやハンドラディスパッチを発生させず、生成されたホスト命令は直接実行され、逐次実行は自然にフォールスルーし、固定ジャンプは通常のホストブランチになります。
assembly backend
execute
execute
execute
execute
execute
execute
レジスタマッピング
残りのインタープリタコストは、ゲスト状態をメモリとレジスタ間で移動することです。単純なトランスレータは、インタープリタが行ったように、依然としてStateを介してすべてのゲストレジスタを読み書きします。
以前使用されたのと同じアイデアがここに適用されます。実行中に渡される値はメモリに格納する必要はありません。ゲストレジスタファイルをState内に保持する代わりに、トランスレータは頻繁に使用されるゲストレジスタをホストレジスタにマッピングし、エントリ時に一度ロードし、実行終了時に書き戻すことができます。
ロードとストアは、変換された実行の境界に移動します。ホットパス内では、ゲストのaddは単一のホスト命令になります。
Clangにバックエンドを任せる
この時点で、トランスレータは事実上、コンパイラバックエンドを独自に再実装しています。ホスト命令を選択し、レジスタを割り当て、各ターゲットアーキテクチャに個別のバックエンドを維持します。より自然なアプローチは、オフザシェルフのコンパイラがすでに理解している言語でコードを生成することです。次に、トランスレータは命令選択、レジスタ割り当て、その他のターゲット固有の詳細をClangに任せることができます。
巨大な単一関数
コンパイラを使用する最も直接的な方法は、プログラム全体を1つの関数にすることです。プログラムをデコードし、各命令をCに変換し、頻繁に使用されるゲストレジスタをローカル変数として保持し、その関数内の制御フローをラベルとgotoで表現します。これにより、コンパイラはプログラム全体をコンテキストとして取得できます。変換された命令間で値を追跡し、レジスタをどこに配置するかを決定し、生成されたコード全体で最適化できます。
制御フローは関数内で直接表現されます。直線的な実行はフォールスルーし、固定ターゲットはラベルになり、実行時まで不明なターゲットのみが間接ジャンプテーブルを必要とします。
Cを生成する理由
生成されたコードは最終的にネイティブ命令になる前にClangを通過するため、トランスレータは直接LLVM IRを発行できます。しかし、このプロジェクトでは、Cの方が有用なインターフェースです。
生成されたCは通常のソースコードのままであり、読み取り、レビュー、diff、および使い慣れたツールでデバッグできます。OpenVMが実行の周りにインストルメンテーションとランタイムフックを追加するにつれて、変更を直接行うことも容易になります。LLVM IRで同じ変更を表現することは、大幅に煩雑になります。
LLVM IRをターゲットにすると、追加のC解析ステップを回避できますが、ジェネレータは低レベルで不安定なコンパイラインターフェースにさらされることになります。Cはより明確な境界を提供し、バックエンドの詳細はClangに任せます。
小さなプログラムでは、これによりコンパイラはゲストプログラム全体を広く可視化できます。レジスタ割り当てと最適化は、変換された領域間の境界なしに、エントリからエグジットまでのすべての値を追跡できます。
しかし、このアプローチはプログラムが大きくなるにつれて破綻します。コンパイラは小さな関数をうまく処理しますが、数千または数百万行を含む関数は、Clangに分析および最適化するための巨大な本体を提供します。コンパイルには非現実的な時間がかかる可能性があり、すべての作業が単一の関数に集中しているため、コア間で効果的に分散できません。
基本ブロックごとにリコンパイルする
プログラム全体を一度に変換すると、Clangは分析しすぎる量になり、一度に1つの命令を変換すると、コンテキストが少なすぎます。基本ブロックは有用な中間地点を提供します。
基本ブロックは、単一のエントリを持つ直線的な命令の最大シーケンスです。制御は最初の命令にのみ入ることができ、制御は最後の命令にのみ出ることができます。
リコンパイラは、各基本ブロックを個別のC関数として発行します。これにより、Clangは複数のゲスト命令にわたって最適化するのに十分なコンテキストを得ながら、各生成関数を効率的にコンパイルできるサイズに保つことができます。
例えば、ブロック
# pc 0x1000slli a0, t0, 13xor t0, t0, a0add a1, t0, a2
は次のように変換されます。
void B_1000(State *state, reg_t t0, reg_t a0, reg_t t1, reg_t a1) {
a0 = t0 << 13;
t0 = t0 ^ a0;
a1 = t0 + a2;
// ... fall through to next block ...
}
重要な違いは、コンパイラが3つの独立した命令ではなく、シーケンス全体を1つの単位として見ることです。中間値をレジスタに保持し、いくつかのゲスト操作を1つのホスト命令に結合できます。ここでは、シフトとXORが、組み込みシフトオペランドを持つ単一のarm64命令に折りたたまれています。
ブロックの識別
ELF実行可能ファイル[9]に含まれる命令シーケンスから、リコンパイラは各生成関数の開始位置と終了位置を特定する必要があります。これは、基本ブロックを識別し、それらを制御フローグラフ(CFG)に接続することによって行われます。ここで、各ノードは1つのブロックを表し、各エッジは可能な制御転送を表します。
基本ブロックを開始する可能性のある命令はブロックリーダーと呼ばれます。プログラムのエントリポイントはリーダーであり、直接分岐またはジャンプのターゲットもリーダーです。制御フロー命令の後の命令も、フォールスルーの可能性がある場合はリーダーです。分析は、定数伝播によって決定されるjalrターゲットなど、命令に直接エンコードされていないターゲットを回復することによって、追加のリーダーを特定する場合があります。
各リーダーから開始して、リコンパイラは別のリーダーまたは分岐、ジャンプ、呼び出し、リターン、またはトラップなどの制御をリダイレクトする可能性のある命令に到達するまで前方デコードします。これにより、識別されたすべてのジャンプターゲットが生成関数の先頭に来ます。
このプロセスにより、既知の制御フローエッジが到達しないため、実行可能テキストの一部が未検出のままになる可能性があります。それらの領域が引き続きコンパイルされることを保証するために、リコンパイラは残りのテキストを線形にスキャンし、セクション境界の後、制御フロー命令の後、および遭遇した直接ターゲットで新しいブロックを開始してブロックに分割します。
命令範囲がわかったら、リコンパイラはそれらを後続に応じて接続します。条件付き分岐には、取られた後続とフォールスルー後続があり、直接ジャンプにはターゲットのみがあります。これらの後続はCFGのエッジになります。
以下の例は、配列を合計する関数にこれらのルールを適用したものです。B_1008の条件付き分岐は1つのブロックを終了し、2つの後続を生成しますが、B_100cの直接ジャンプはループバックエッジを形成します。これらの転送はターゲットを直接エンコードします。最後のjalrはraから宛先を読み取るため、ターゲットは実行時にのみわかります。
01split at branches
02connect the edges
03emit one function per block
guest instructions
split into blocks
B_1000:
addi t0, x0, 0
addi t1, x0, 0
B_1008:
bge t1, a1, B_102c
B_100c:
lw t2, 0(a0)
add t0, t0, t2
addi a0, a0, 4
addi t1, t1, 1
jal x0, B_1008
B_102c:
addi a0, t0, 0
jalr x0, ra, 0
control-flow graph
known edges
i < ni >= nloopra (unresolved)
B_1000
B_1008
B_100c
B_102c
generated C
selected block · B_1008
静的分析は依然として多くの間接ターゲットを回復できます。リターンアドレスを到達可能としてマークし、定数をauipc + jalrシーケンス(遠距離呼び出しに使用)に伝播し、読み取り専用データからコードへのポインタ(関数ポインタ配列やスイッチジャンプテーブルなど)をスキャンします。
しかし、間接ターゲット分析は依然として保守的です。実行が開始される可能性がある証拠がある場合にのみターゲットを記録します。テキスト全体のスイープはカバレッジのためにブロックを追加しますが、実行時にのみ知られるターゲットは静的CFGで未解決のままであり、実行時ディスパッチパスを使用します。
ブロックとその後続がわかったら、直接分岐とジャンプは対応する生成関数へのテールコールになります。
ブロックの接続
ブロックは、その終端でのみ制御を転送します。直接分岐とジャンプは静的に既知の宛先を持つため、生成関数は直接テールコールで終了できます。
if (taken) {
[[clang::musttail]]
return B_taken(state);
}
[[clang::musttail]]
return B_fallthrough(state);
Clangはこれらの呼び出しを通常のジャンプに低レベル化できます。直接エッジに沿ってディスパッチルックアップや明示的なプログラムカウンタ更新は必要ありません。B_1000を実行すると、現在のゲストアドレスが0x1000としてすでに識別されています。
関数リターンを含むjalrは、実行時にレジスタから宛先を計算するため、ディスパッチテーブルを使用します。
state->pc = target_pc;
uint64_t index = __builtin_rotateright64(target_pc - TEXT_START, 2);
if (unlikely(index >= NSLOT)) {
state->halted = true;
return;
}
block_fn next = dispatch_table[index];
[[clang::musttail]]
return next(state);
テーブルにアクセスする前に、ディスパッチパスはターゲットがアラインメントされ、ディスパッチ可能なテキスト内にあることを検証します。そうでない場合、実行は停止します。テーブルには、テキストセクションの各命令スロットに1つのエントリがあります。ブロックリーダーのエントリは生成関数を指し、残りのエントリはフォールバックを使用します。
フォールバックは、生成ブロックの途中の命令など、有効な命令アドレスであるがブロックリーダーではないターゲットを処理します。その場合、ディスパッチテーブルはターゲットアドレスでインタープリタを呼び出します。インタープリタは、実行がコンパイル済みブロックに到達するまで続行し、次に生成コードに制御を戻します。
ブロック間のレジスタ
あるブロックの終わりにすべての32個のゲストレジスタをスピルし、次のブロックで再ロードすると、すべての転送にかなりのメモリトラフィックが追加されます。したがって、ブロックリコンパイラは、テールコールインタープリタで使用されたのと同じアイデアを適用します。各ブロックは、頻繁に使用されるゲストレジスタの固定セットを引数として受け取るため、これらの値はホストレジスタに保持できます。
typedef uint64_t reg_t;
// Abbreviated hot-register set.
[[clang::preserve_none]]
void B_100c(State *, reg_t ra, reg_t sp, reg_t a0, reg_t a1);
[[clang::preserve_none]]
void B_1000(State *state, reg_t ra, reg_t sp, reg_t a0, reg_t a1) {
a0 = a0 + 1;
a0 = a0 << 2;
a0 = a0 + a1;
[[clang::musttail]]
return B_100c(state, ra, sp, a0, a1);
}
引数にはStateポインタとホットゲストレジスタの共有セットが含まれ、使用頻度の低いレジスタはState内に残ります。
通常の呼び出し規約は、限られた数の引数レジスタしか公開しません[10]。Clangのpreserve_none規約は、ほぼすべての汎用レジスタを利用可能にし、呼び出し先はそれらを一切保持しないことを要求します。
通常、これは呼び出し元に、呼び出し前にライブ値があれば保存することを強制します。しかし、ブロック転送はmusttail呼び出しであるため、呼び出し元は決して再開せず、保持するものはありません。preserve_noneとmusttailを組み合わせることで、ブロック間でゲスト状態を渡すために、はるかに多くのホストレジスタが利用可能になります。
| レジスタ容量 | arm64 | x86-64 |
|---|---|---|
| 汎用ホストレジスタ | 31 | 16 |
| 引数レジスタ、標準規約 | 8 | 6 |
引数レジスタ、preserve_none | 24 | 12 |
| リコンパイラが使用する引数レジスタ | 24 | 11 |
| ホットゲストレジスタに利用可能 | ~23 | ~10 |
スクロールして続きを読む →
x86-64実装では、リンク時最適化中にLLVMのレジスタアロケータを使い果たさないように、1つのpreserve_none引数レジスタが未使用のままになります。Stateポインタを考慮すると、arm64で約23個、x86-64で約10個のホットゲストレジスタが残ります。
musttailは互換性のあるシグネチャと一致する呼び出し規約を必要とするため、すべてのブロックは同じホットレジスタセットを使用します。ブロックが変更しないレジスタは、追加の移動なしに通過します。リコンパイラはこのセットを選択し、Clangはそれを利用可能なホストレジスタに割り当てます。
これらの要素が配置されたことで、設計は完了しました。基本ブロックはコンパイラに命令間で最適化するのに十分なコンテキストを提供し、テールコールは既知の制御フローを直接ジャンプに変換し、密なジャンプテーブルは未解決のターゲットを処理します。preserve_noneと組み合わせることで、ブロック境界を越えて頻繁に使用されるゲスト状態をホストレジスタに保持します。
パフォーマンス
ベンチマークは、各ステップが準備時間、実行スループット、および生成された共有オブジェクトサイズにどのように影響するかを測定します。
ベンチマークセットアップ
各ワークロード内で、すべてのゲストバックエンドは同じホスト上で同じRISC-Vバイナリを実行します。ネイティブベースラインは、同等のCから個別にコンパイルされます。すべてのバージョンは同じ出力を生成し、タイムドパスには命令カウントやその他のブックキーピングは含まれません。準備は、新しく生成された成果物に対してエンドツーエンドで測定され、コード生成、コンパイルまたはアセンブリ、生成された共有オブジェクトのロード、および初期化が含まれます。スループットは、一時的なノイズを減らすために繰り返し実行からの最小実行時間から計算されます。それは百万ゲスト命令/秒(MIPS)で報告され、丸められ、各ワークロード内の比率として読むのが最適です。
ベンチマークプログラムと入力[11]は信頼できるため、ゲストメモリアクセスは、アクセスごとの境界チェックなしの保護された線形マッピングを使用します。ただし、生成されたバックエンドは、ディスパッチの前に間接制御フローターゲットの範囲とアラインメントをチェックします。
マシンとビルドの詳細
- 測定はApple M3ラップトップで行われました。絶対結果は実行およびマシンによって異なる場合がありますが、同じ条件下で測定された比較は意味があります。
- エグゼキュータとネイティブベースラインは、Clang 22.1.8を使用して
-O3 -march=native -falign-functions=32 -std=c2yでビルドされました。 - コンパイルされたすべてのゲストは、Clang 22.1.8を使用して
-O3 -std=c2y -march=rv64im_zba_zbb_zbs_zicclsm -mno-scalar-strict-alignでビルドされました。
小規模ワークロード
最初のチャートは、手書きのループ3つとRISC-V用にコンパイルされた8つのCプログラムを組み合わせたものです。
ワークロードの内容
xorshiftは、イテレーション間にシリアル依存関係を持つ64ビット疑似乱数ジェネレータを実行します。sumは、1からNまでの整数を加算します。collatzは、多くの開始値に対してコルラッツ数列を評価します。towersは、20個のディスクに対して再帰的にハノイの塔を解きます。fibは、再帰的に30番目のフィボナッチ数を計算します。ackermannはAckermann(3, 6)を計算します。nqueensは、再帰的バックトラッキングを使用して13クイーン問題の解を数えます。quicksortは、5,000個の生成された整数をソートし、結果のチェックサムを計算します。matmulは、2つの48x48整数行列を乗算し、結果のチェックサムを計算します。crc32は、生成されたデータ8 KiBに対してビットワイズCRC-32を計算します。sha256は、連鎖するSHA-256ブロックを繰り返し圧縮します。
準備時間
| ms | towers | fib | ackermann | sha256 | nqueens | crc32 | quicksort | matmul |
|---|---|---|---|---|---|---|---|---|
| per-instruction translator | 115 | 117 | 117 | 118 | 116 | 117 | 117 | 119 |
| recompiler, one function | 118 | 113 | 108 | 327 | 145 | 143 | 185 | 611 |
| per-block recompiler | 115 | 115 | 118 | 128 | 133 | 123 | 143 | 175 |
すべての3つのバックエンドは、これらのワークロードを1秒未満で完了します。単一関数バックエンドは、生成関数が大きくなるにつれて最も高価になり、行列乗算で約600ミリ秒に達します。
スループット
native host C行は、同じワークロードの個別にコンパイルされたホストバージョンを実行します。そのスループットは、同等のゲストMIPSで報告されます[12]。ループには対応するC実装がないため、ネイティブ結果はありません。
| RISC-V MIPS | xorshift | sum | collatz | towers | fib | ackermann | sha256 | nqueens | crc32 | quicksort | matmul |
|---|---|---|---|---|---|---|---|---|---|---|---|
| switch interpreter | 207 | 196 | 181 | 184 | 179 | 191 | 239 | 177 | 207 | 184 | 192 |
| predecoded | 548 | 552 | 478 | 515 | 499 | 531 | 504 | 402 | 526 | 424 | 475 |
| computed goto | 841 | 560 | 375 | 734 | 700 | 580 | 859 | 426 | 853 | 512 | 829 |
| tail-call interpreter | 1334 | 1404 | 501 | 1005 | 823 | 714 | 1018 | 478 | 991 | 538 | 489 |
| per-instruction, in memory | 1225 | 7547 | 3819 | 4652 | 4531 | 4707 | 4263 | 2102 | 3047 | 2862 | 4834 |
| per-instruction, pinned | 6309 | 7692 | 6001 | 5539 | 5488 | 4735 | 10689 | 3063 | 9453 | 5037 | 12469 |
| recompiler, one function | 6309 | 15385 | 9061 | 5930 | 8432 | 8420 | 11243 | 3487 | 9702 | 5313 | 12469 |
| recompiler, in memory | 6250 | 30770 | 14003 | 6243 | 4205 | 4818 | 16722 | 2690 | 6044 | 7605 | 22642 |
| recompiler, standard cc | 6309 | 30770 | 9242 | 5132 | 4313 | 2576 | 16420 | 2219 | 5343 | 5746 | 25305 |
| recompiler, preserve_none | 6309 | 30770 | 9061 | 14375 | 12878 | 13280 | 16780 | 3709 | 5343 | 6687 | 24583 |
| native host C | – | – | – | 15251 | 15843 | 4104 | 20813 | 3764 | 6044 | 7387 | 71699 |
最も明確な比較は、per-instruction, pinnedとrecompiler, preserve_noneの間です。どちらも同じホットゲストレジスタをハードウェアに保持するため、残りの違いは主に、コンパイラが一度に1つの命令ではなく、基本ブロック全体で最適化する能力を反映するはずです。違いは密に逐次的なコードでは小さく、コンパイラが操作を結合またはベクトル化できる場合ははるかに大きくなります。
preserve_noneは、値がブロック境界を頻繁に横断する場合に最も役立ちます。再帰的なワークロードではうまく機能しますが、広い引数セットがタイトなループ内のレジスタ圧力を増加させるため、パフォーマンスが低下する可能性があります。
このAckermannベンチマークでは、変換されたコードは同等のネイティブCベースラインを超えています。そのゲスト呼び出しとリターンはテール転送になり、再帰はホストスタックフレームを繰り返し作成および削除することなくゲストスタックを成長させます。
注: これらは、個々のメカニズムを分離するために選択された、最小限の参照実装からの小さなベンチマークであり、実際のワークロードでのパフォーマンスを表すものではありません。
大規模ワークロード
より大きなベンチマークは、RISC-V用にコンパイルされ、オペレーティングシステム、システムコール、浮動小数点なしでベアメタルにリンクされた4つのCワークロードです。
より大きなワークロードの内容
CoreMarkは、リスト、行列、状態処理カーネルを固定回数実行し、検証結果を確認します。LZ4は、決定論的な入力を圧縮および解凍し、ラウンドトリップを検証して圧縮データをハッシュします。zstdは、固定ワークスペースと動的割り当てなしで、より大きな圧縮および解凍ラウンドトリップを実行します。SQLiteは、インメモリデータベースを構築し、数千行を挿入し、集計クエリとGROUP BYクエリを実行します。
準備時間
| preparation time (s) | CoreMark | LZ4 | zstd | SQLite |
|---|---|---|---|---|
| per-instruction translator | 0.14 | 0.22 | 1.3 | 3.0 |
| recompiler, one function | 30 | - | - | - |
| per-block recompiler | 0.72 | 2.1 | 21 | 125 |
スクロールして続きを読む →
命令ごとのトランスレータは、固定命令シーケンスを発行してアセンブルするため、最も安価なままです。ブロックリコンパイラは、数万の小さな関数を最適化するためにより多くの時間を費やします。生成された関数はファイルに分割され、並列にコンパイルされますが、最終リンクはThinLTOを使用してファイル境界を越えた最適化を可能にします[13]。
ランナーは、各ワークロードに単一関数バックエンドに最大10分を与えます。CoreMarkは30秒で完了します。LZ4、zstd、SQLiteは制限時間内にコンパイルを完了しないため、それらのスループットとコードサイズの結果にはこのバックエンドは存在しません。
スループット
| RISC-V MIPS | CoreMark | LZ4 | zstd | SQLite |
|---|---|---|---|---|
| per-instruction translator | 5728 | 9832 | 9370 | 6239 |
| recompiler, one function | 5664 | – | – | – |
| per-block recompiler | 8668 | 15025 | 14598 | 7153 |
| native host C | 10312 | 16839 | 16612 | 17816 |
CoreMark、LZ4、zstdでは、ブロックごとのリコンパイラはネイティブスループットの約84〜89%に達します。SQLiteでは、約40%に達します。ネイティブClangは、完全な関数全体で最適化し、ソースレベルのポインタを直接推論できます。リコンパイラは一度に1つの基本ブロックしか見えず、ゲストメモリアクセスは最初にホストアドレスに変換する必要があるため、最適化の機会が少なくなります。
SQLiteは、静的カバレッジの不完全さからも影響を受けます。そのバイトコードインタープリタと実行時に登録された関数ポインタには、静的分析が回復できない多くの宛先が含まれています[14]。広範なコードカバレッジがないと、実行はより頻繁にインタープリタにフォールバックします。テキスト全体をコンパイルするとカバレッジが向上しますが、SQLiteの短く不規則なブロックは、LZ4またはzstdよりも最適化の余地が少なくなります。
注:
LZ4とzstdのRISC-Vビルドはカスタムmemcpyおよびmemmove実装を使用していますが、ネイティブベースラインはホストバージョンを使用しています。
コードサイズ
| shared object (KiB) | CoreMark | LZ4 | zstd | SQLite |
|---|---|---|---|---|
| per-instruction translator | 49 | 194 | 1984 | 4757 |
| recompiler, one function | 97 | - | - | - |
| per-block recompiler | 99 | 510 | 4162 | 10605 |
スクロールして続きを読む →
命令ごとのトランスレータは、ゲスト命令ごとに1つの固定された最適化されていないテンプレートを発行するため、最小のオブジェクトを生成します。ブロックごとのリコンパイラは、Clangにインライン化、アンロール、アラインメントを許可し、その出力を約2〜2.7倍大きくします。単一関数CoreMarkオブジェクトは、命令ごとのトランスレータの出力の約2倍のサイズです。
ブロックごとのSQLiteオブジェクトは約10 MiBに達するため、より大きな変換されたプログラムは、最適化によるスループットの増加とこの増加のバランスを取る必要があります。
トレードオフ
基本ブロックのリコンパイルは、ゲストプログラムが事前に知られており、コンパイルを償却するのに十分な長さまたは頻繁に実行される場合に最も効果的です。規則的で計算負荷の高いワークロードは、各ブロック内でコンパイラにより多くの最適化作業を提供するため、最も恩恵を受けます。
短いプログラム、頻繁に変更されるコード、または間接制御フローが頻繁にインタープリタにフォールバックするワークロードにはあまり適していません。単純な変換と比較して、準備時間の増加、成果物のサイズの増加、および静的制御フローカバレッジへの依存度の増加を犠牲にしてスループットを向上させます。
締めくくり
インタープリテーションとプログラム全体の積極的なコンパイルの間には、まだ大きな設計空間があります。ホットな基本ブロックはより大きな領域に結合される可能性があり、より軽量な最適化はコンパイル時間とコードサイズを削減する可能性があり、未解決のターゲットはインタープリタへのフォールバックの代わりにJITコンパイルをトリガーする可能性があります。その後、このアプローチを拡張して、オンデマンドでプログラムのより多くをコンパイルし、AOTコンパイルの完全な事前コストを回避できます。
この記事で説明されているコア技術は、それ自体は新しいものではありません。私がこれまで見てこなかったのは、ゲストプログラムを効率的に実行するために、musttail、preserve_none、および基本ブロックのリコンパイルのこの組み合わせでした。これらを組み合わせることで、設計は高速であり、ホストアーキテクチャ間で移植可能になります。
リソース
- 効率的なディスパッチテーブルのための計算済みgoto
-
musttailを使用した効率的なインタープリタ musttailおよびpreserve_noneのClangドキュメント- RVR、Rustでの初期リコンパイラ実装
OpenVM v2.1には、リコンパイラがオプションの実行バックエンドとして含まれます。
フットノート
- 証明とは、プログラムが正しく実行されたことを証明するデータであり、プログラムを再実行するよりもはるかに安価に検証できます。Ethereum FoundationのzkEVMプロジェクトは、ネットワークのノードがすべてのトランザクションを再実行するのではなく、ブロックの証明を検証できるような、そのような証明の具体的な応用例です。↩
- ゲストは実行されている仮想マシンです。ホストはそれを実行している基盤となるハードウェアです。↩
- 例は、
M、Zba、Zbb、およびZbs拡張機能を持つRV64Iをターゲットとしており、通常の非アラインメントスカラーロードおよびストアのZicclsmサポートを想定しています。↩ - 自己変更コードの処理は、この記事の範囲外です。↩
&&labelおよびgoto *exprは、標準Cではなく、GNU Cのラベル値拡張機能から来ています。↩- テールコールは、呼び出し元が何も実行しないまま、別の関数に直接制御を転送する関数呼び出しです。↩
- レジスタアクセスは、通常、メモリアクセスよりも桁違いに高速です。↩
- 事前コンパイル(AOT)コンパイルは、実行中にコードを変換するジャストインタイム(JIT)コンパイルとは異なり、プログラム実行前にネイティブコードを生成します。↩
- ELF(Executable and Linkable Format)は、Linuxおよび多くのUnixライクシステムで使用される標準の実行可能ファイル形式です。↩
- 呼び出し規約は、レジスタを呼び出し元保存(caller-saved)と呼び出し先保存(callee-saved)のセットに分割します。呼び出し元保存レジスタは呼び出しによって上書きされる可能性がありますが、呼び出し先保存レジスタは呼び出し先が戻る前に復元する必要があります。↩
- ベンチマークコードはコンパニオンリポジトリで見つけることができます。↩
- ワークロードのRISC-V命令カウントを、同等のネイティブCプログラムの実行時間で割ったものです。↩
- Thin Link-Time Optimization(ThinLTO)は、プログラム全体を巨大な単一ユニットにマージすることなく、コンパイルユニット間で要約情報を共有します。↩
- 分析では、
auipc+jalrシーケンスに定数伝播を使用し、呼び出しとリターンアドレスを照合し、アドレスが取られた関数を追跡し、読み取り専用データからコードポインタをスキャンします。↩