VirtualMachine本: Chapter 2 Emulation: Interpretation and Binary Translation
Virtual Machines: Versatile Platforms For Systems And Processes
やっとダイナミックなバイナリトランスレートの話がでてきましたよ。
(2009.2.9 Chapter毎に整理しました)
Source ISAとTarget ISAが異なるときの話。しかし、そうじゃない場合にもこのテクニックは使える。binary optimizationとか、特権命令実行時のemulation的動作とか。
2.1 Basic Interpretation
普通のエミュレーション。メインループがあって、デコード・命令ディスパッチを実行。ブランチが多すぎて遅い。
この章で突然「FORTHは"threaded code" interpretation modelで有名」と出てきて驚く。FORTHは昔だいぶ遊んだけど、それ知らないぞ(と思ったのですが、threaded codeのところを読んだら納得できました)
2.2 Threaded Interpretation
各Instruction emulationの最後に、decodeして対応するインストラクションを実行する。テーブルをひき、そこへ飛ぶコードを追加する。メインループはもういらない。これは、デコード結果からテーブルをひいてジャンプ、なので
"indirect" threaded interpretationと呼ばれる。
2.3 Predecoding and Direct Threaded Interpretation
ループは消えたけど、毎回デコードのオーバーヘッドがある。
2.3.1
そこでプレデコード。デコードして扱いやすい形で再度格納。
2.3.2 Direct Threaded Interpretation
デコード結果の「オペランド」のところに、そのオペランドを実行するアドレスを直接いれる。メモリルックアップが1回減らせる。
2.4 Interpreting a Complex Instruction set
ここまではPowerPCを例にしていたが、IA32みたいなCISCでは大変。
IA32だと、General Decodeしてから、特殊な処理に分岐するのが基本的な動き。
2.4.2 Threaded Interpretation
RISCに比べてdecode処理が複雑ででかい。各instruction interpreterの最後にdecode処理を書いていたら、インタプリタがでかくなる。
ということで、一般的なケースに特化したdecode-and-dispatchルーチンをいれる。特殊なケースはブランチしてとばす。
Direct Threaded Interpretationをやろうとするといろいろ問題。とくに2つ:
- predecoded instructionは長くなる傾向がある。メモリをいっぱいくう。
instruction types毎に中間コード用意するなど
あるいは、小さいインストラクションに分解するなど → これはCISCからRISCへのbinary translateに似ている - code discovery。実行しないと命令の境界が分からない場合があり、プレデコード困難。
binary translationでも問題になるので、あとでくわしく取り扱う。
また、2段階のdecode-dispatchになる。これもbinary translationと非常に似ている。
binary translationはポータビリティに欠ける、が、retargetable binary translatorが開発されている
(p46)
2.4.3 High-performance IA-32 Interpreter
FX!32をベースにした例。オリジナルのAlphaじゃなくて、PowerPCのアセンブラで記述されているが、PowerPCをよく知らないのでほとんど理解できない。IA32の1インストラクションをAlphaの30インストラクション相当で実行できるらしい。
2.5 Binary Translation
2.4まではインタプリタだけど、target ISAのバイナリコードに変換するとパフォーマンスがあがる。
インタプリタと違って、source ISA状態のマッピングをtarget ISAのレジスタに直接おくことで、コンテクストブロックをメモリから読み込むオーバーヘッドを削除できる。
2.6 Code Discovery And Dynamic Translation
2.6.1 The Code Discovery Problem
スタティックにプレデコードしたりバイナリトランスレートしたりすることを考えてみる。(特にCISCなISAでは)これはかならずしも簡単じゃない(それどころか不可能な場合もある)。命令境界がどこかわからないし、生成されたコードのなかにデータとかパディングがはいっていることだってある。
RISCであれば、1命令1ワードだったりするが、たとえばIA32だと、任意のバイトが本当に命令境界なのか判断する方法はない。
2.6.2 The Code-Location Problem
間接ジャンプだと、ターゲット側に展開された命令列のどこに飛べばいいかわからない(ただしRISCやJavaVMではこういう問題は起こらない)
2.6.3 Incremental Predecoding and Translation
2.6節のハイライト! (ってそんなに気合いをいれるほどのことはない)。プレデコードとトランスレーションはきわめて似たプロセスなので、この本では「トランスレーション」と呼びます。
Emulation Manager、インタプリタとトランスレータ、トランスレートされたコード(のキャッシュ)、そしてソースPCからターゲットPCへのマッピングを示すハッシュテーブルをそろえれば、ダイナミックにインクリメンタルなトランスレートができます。
Emulation Managerは、マップを使ってコードキャッシュを探し、ヒットすればトランスレートされたブロックを呼びます。ヒットしなければ、インタプリタ・トランスレータを呼んで、次のブロックをインタープリト・トランスレートし、マップにトランスレートされた結果をいれます。
このときの、トランスレートの単位は「Dynamic Basic Blocks」。ブランチで入ってきたポイントから、ブランチで出るポイントまでを(動的に)認識したものです(これにたいして、Static Basic Blocksは、静的構造を解析してエントリポイント・エグジットポイントで切ったもの)。
Dynamic Basic Blocksの特徴として「他の大きなブロックの一部が、新たに小さなブロックになることがある」です。これは、大きなブロックの途中に、エントリポイントがある場合などですね。(p57の図がわかりやすい) このダブりがあることで、すでにトランスレートされたコードの途中にブランチしたら、みたいな複雑な処理がいらなくなっています
こんどは、ブロックごとに「キャッシュを探す」「Emulation Managerに戻る」オーバーヘッドをへらすことが考えられます。キャッシュを探す、については、SourceのPCをTargetのレジスタにいれとくとか、コードブロックの最後に次のSource PCを置いておき、そこをlink register経由でアクセスする方法とかがあります。
他にも問題がいろいろ。これらはChapter3や4で扱われます。
- self-modifying code
- self-referencing code
- precise traps
2.6.4: Same-ISA Emulation
同じISAでもEmulationがありうる。Emulation Managerが常にコントロールをもち、かつモニタ(= code management)できる。この一例が"simulation"。2.9でcase studyとして扱われる。
2つめの例は、ISAが同じだがOSが異なる場合。このときはsystem callをemulationする。
3つめの例は、特権命令を扱うエミュレーション(Chapter 8)。
4つめは、Chapter10であつかう"program shepherding"。セキュリティ的監視。
さいごが、ランタイムでのbinary optimization。
Chapter 3に突入したけど、ここでの復習が追いつかない!
2.7 Control Transfer Optimization
2.6までの「シンプルな」トランスレート方法では、Source PC/Target PCのルックアップや、ブロックごとにEmulation Managerへコントロールが戻ることがどうしても起きる。このオーバーヘッドを減らす方法いろいろ。
2.7.1 Translation Chaining
インタプリンタのスレッディングと同じようなテクニック(名前から見当つくよね)。トランスレートされたブロックをチェーンするのだ。
次のブロックがまだトランスレートされていない場合は、通常のスタブコードが入る。
2.7.2 Software Indirect Jump Prediction
ソフトウェア分岐予測! これは本質的には「inline caching」の実装である。分岐先のコードを、出現しそうな順に、ifのなかで即値で埋め込んでおくのです。
なので、profilingとセットでやる必要がある。
2.7.3 Shadow Stack
sourceのstackへ戻り値を格納すると同時に、target側でEmulation Managerが管理する"shadow stack"にtargetの戻り先PCを格納する。stackからpopするときは値のチェックをしてconsistencyをみる。
VM本2章の終わりのほうです。
2.8 Instruction Set Issues
インストラクションセットエミュレーションについて、まだまだいろいろあるけどそのうちの一部を扱います。
2.8.1 Register Architectures
レジスタはストレージヒエラルキのてっぺんにいるので、パフォーマンスに影響がでかい。
レジスタ割り当ての戦略についてbinary translation, interpreterのそれぞれで、一般論を。
2.8.2 Condition Codes
フラグの類について。sourceとtargetでISAが違えば、同じではない。MIPSみたいにcondition codeがないようなものもある。
source instructionの実行のたびにcondition codeを更新する手もあるが、これは遅いし、通常必要でもない。lazy evaluationがよく使われるテクニック。condition codeに影響がある、最近実行された命令とそのオペランドを記録しておき、必要になったらcondition codeを生成する。
この方法でも、実行中にtrapが発生した場合に問題がある。trap発生したら、preciseなソース状態を作らなくてはならない。このへんはあと(4.5.2)で議論する。
2.8.3 Data Formats and Arithmetic
浮動小数点のフォーマットはかなり統一されているが、たとえばIA32では80bitの中間結果がつかわれるが、ほかの多くのISAでは64bitみたいな差がある。
ほかにもいろいろ。PowerPCでは連続した乗算・加算のインストラクションがあるが、これはエミュレートできない場合がある(途中でオーバーフローしちゃうとか)。アドレッシングモードが違うとか、即値の長さが違うとか。
2.8.4 Memory Address Resolution
sourceとTargetでアクセスできるメモリの単位が違う。たとえばbyte単位でのメモリアクセスができないISAもある。
2.8.5Memory Data Alignment
メモリのアラインメントもISAで違う。いろんなやりかたがあるけど、プロファイルをとるような方法もある。Chapter4で議論する。
2.8.6 Byte Order
BigEndian, LittleEndianなISAがある。
両方サポートしているＩＳＡもある。
2.8.7 Addressing Architecture
サイズが違う、特権レベルが違うなどいろいろ。
2.9 Case Study: Shade and the Role of Emulation During Simulation
"Shade"という、high-performanceなsimulationのケーススタディ。
"simulation"は、「内部動作までのシミュレート」を意味する。emulationは表面の動作のみ。
あまり細かいことはかいていないが、code cacheのメカニズムがシンプル。source PCからhash経由で、translated codeの場所がひかれる。hashのさすさきには、n個の"source/target"ペアがはいってる。新しく使われたのが、せんとうにくる。もしいっぱいになれば、n個目が押し出される。そういうわけで、translateされたけど、danglingになるtranslated codeがある(本文中では"orphan"って表現されてる)。
code cacheはあたまからつめられていく。もし最後に到達したら、単純にすべてフラッシュされる。そういうわけで、danglingなコードはそのうち消える。
このメカニズムはシンプルだけど、効率ほんとにいいのか? と疑問に思うが、いいんだろうな、確かめるためには論文にあたればよさそう。
2.10 Summary: Performance Tradeoffs
2章のまとめ。つぎのものたちが出てきています。
- Decode-and-Dispatch
- メモリ要求少ない、スタートアップ速い、定常動作遅い、ポータビリティ高い
- Indirect Threaded Interpreter
- メモリ要求少ない、スタートアップ速い、定常動作遅い(Decode-Dispatchよりはまし)、ポータビリティ高い
- Direct Threaded Interpreter with Predecoding
- メモリ要求多い、スタートアップ遅い、定常動作普通、ポータビリティ普通
- Binary Translation
- メモリ要求多い、スタートアップとても遅い、定常動作速い、ポータビリティダメ