自作QEMUエミュレータ高速化の肝はなにか？　分岐成立時に制御を戻さない最適化方式「TCG Block Chaining」

QEMU高速化テクニックその1 TCG Block Chaining

msyksphinz氏（以下、msyksphinz）：ここからはいくつかQEMUの高速化テクニックを紹介していきます。最初がTCG Block Chainingです。QEMUは命令を変換するんですが、1命令ずつではなくて、ある程度のブロックでまとめて変換します。そのブロックがいわゆるコンパイラなどで出てくるベーシックブロックというもので、おしりが分岐になるまでが基本の変換ブロックです。

例えばRISC-VのBEQ、ブランチにぶつかって分岐に来たら1回実行を制御モードに戻して、分岐先をもう1回制御側で1回フェッチし直して、次の命令をデコードしてジャンプするということを行っています。

1回分岐にぶつかると、どうしても制御を戻さないといけなくなるのですが、だいたいこういう分岐命令の場合は、1回ジャンプ先が決まってしまうと、そのジャンプ先がstaticに決まってしまうので、一度目の実行で次のジャンプ先のブロックが判明すると、そこからはそこに直接飛べばいいということで、予めスタブが入れられています。

この分岐が成立した場合は、ジャンプ命令が入っていて、最初はオフセット0で入っているんですが、この次のブロックがオフセットのところを埋めて、次に分岐が成立した場合は制御を戻さずに直接次のブロックに飛んでくださいという変更を行います。そうすると、次のループからは制御を戻すことなく、分岐成立時は直接次のブロックにジャンプすることができるようになります。

このTCG Block Chainingという技術を私の自作QEMUにも導入して、速度向上結果を測ってみました。結果がこの赤いグラフです。初期実装版に比べると、まぁまぁ速くなったかなと思っています。

これはRustの性能解析ツールを使って、どこが遅くなっているのかをいろいろ調査した結果です。この結果が合っているのかどうかはだいぶ眉唾なんですが、はっきりわかるのは実際にエミュレーションモードで動いている時間はかなり短くて、それ以外のフェッチやデコードなどでかなり時間を取られてしまったというのがわかりました。

なのでQEMUもそうですが、なるべくエミュレーションの状態を維持して、制御を戻すことを防ぐのが、エミュレータの高速化の肝になるのではないかなと思いました。

QEMU高速化テクニックその2 TCG Lookup and Jump

QEMUの高速化テクニックその2、TCG Lookup and Jumpです。これは一般的な用語ではなくて、私が勝手に作りました。さっきの方法は、ジャンプ先がstaticに決まっていないと使えない技で、例えばレジスタ間接ジャンプとかでは使えません。

レジスタ間接ジャンプはどうするかというところですが、例えばRET命令でレジスタを読むと、ジャンプ先のアドレスが決まった段階で小さなテーブルをもっていて、そのテーブルにこのジャンプ先のブロックはどこにありますかとサーチしに行きます。

ブロックが生成済みであることがテーブルヒットすると、そのアドレスをテーブルから引っ張ってきて、そこにジャンプします。アドレスが決まった段階でテーブルをサーチしに行って、見つかれば即ジャンプというかたちで、これも制御が戻ることを防いでいるテクニックです。

これも同じく実装してみました。自作QEMUにこのテクニックを実装すると、もうちょっと速くなりました。Dhrystoneがだいたい2秒ぐらいにまで向上できました。ただQEMUに比べるとまだぜんぜん速くはなくて、倍以上の差をつけられています。

QEMUに導入されているさまざまな高速化テクニック

QEMUはこれ以外にいろいろな高速化テクニックが導入されています。今回、私の実装では実装できなかったんですが、いろいろな最適化方式があります。

QEMUのすごいところは、中間表現のTCGでいろいろな最適化を適用してしまうというところで、いくつか紹介します。例えばレジスタ依存があって、全部に依存がある命令列があったとして、よく見てみると実は起点がx0レジスタ、つまり即値で、この書き込みレジスタの値は実は実行前にすべて計算できるというものになっています。

このような依存関係もQEMUは事前に解析して、x86の命令を出す時は全部即値命令に置き換えてしまうことで高速化を図っています。

下の例は、次の命令がレジスタをすぐに使う場合ですが、普通にx86の命令を生成すると、1回どこかからレジスタの値をx86のレジスタに引っ張ってきて、計算してストアして引っ張ってきて計算してとなるんですが、次の命令で即その値を使うのであれば、1回ストアすることは必要ありません。明らかに不要なメモリアクセスですね。

そういう中間の格納を全部スキップして、実行する命令数を減らすということが行われています。こんな感じでいろいろなテクニックが融合して、QEMUは高速に実行できているということがわかりました。

プログラミングにあった書き方をしないと意味はない

こんな感じでいろいろとQEMUについて勉強したんですが、Rustを使ってよかったかどうかというのは、完全に個人的な私見です。

Rustを使うとこういうエミュレータでも安全に実装できるだろうと思っていました。Rustがなぜ安全なのかというと、コンパイラがx86のアセンブラを出す時に、安全になるRustのアセンブラを出してくれるみたいな、配列外アクセスを検出するものを出してくれるみたいな、そういうところでコンパイラのちからが大きいなというところが見えてきました。

なので、コンパイラのまかり知らぬことを書くといくらRustでも安全ではないということになってしまいます。例えば今回実装した中で、TCG Block Chainingのところでジャンプのオフセットを無理矢理書き換えるみたいなことをしました。

そうすると、メモリにゴリゴリにアクセスするみたいなことを書かないといけなくて、無理矢理書き換えるunsafeなものを大量に作る必要が生じて、「Rustを使ったけど、この大量のunsafeはどうだ」みたいなことになってしまいました。

エミュレータはバイナリを生成するのが目的で、コンパイラはどんなバイナリが作られるかなんてまかり知らないところなので、コンパイラの知らないところに行ってしまうと、それはいくらRustでも知らんとなってしまうというのがちょっと今回の反省点ですね。

なので、単純にQEMUで実装されていることをRustで書き直せばよいというわけではなくて、RustならRustにあった書き方をしないときっと良いプログラム、良いコードは書けないんだなという月並みの反省を最後に書いて私の発表を終わります。ご清聴ありがとうございます。

司会者：ありがとうございました。質疑の時間があります。「エミュレータとシミュレータの違いってよくわかっていないなぁ」というコメントがありましたが、機械屋さんからすると、ここって何か使い分けがありますか？

msyksphinz：私も「いったいどっちが正しいんだろう」という疑問をもちつつ、この資料を書いていたので、正直定義は私もわかりません。ハードウェア屋さんからしてみると、一般的にはCPUのコアのみを見るのを、シミュレータと言っているのかなという気がします。システム全体を模擬すると、エミュレータになるのかなというザックリな印象ですね。そんな感じで非常に曖昧に使っています。

司会者：ありがとうございます。もう1点、「昔々QEMUは遅いと言われていたイメージがあるけど、いつから速いというポジションになったのか」。この発表を見たみなさんも、「QEMU速い！」となっていますが、そういう話は聞いたことがありますか？

msyksphinz：実は私もQEMUは非常に初心者で、QEMUの勉強を始めたのが2020年の終盤なので、ごめんなさい、QEMUが遅い時代は私も知らなくてですね。私がQEMUをいじり出したのは、それこそRISC-VのLinuxブートとかで、公開されているシミュレータとQEMUで同じLinuxを立ち上げるとQEMUがダントツに速かったので、QEMUは速いという前提から入ってしまいました。

司会者：これで時間は以上ですね。ありがとうございました。