yarvarch.ja

#title  YARVアーキテクチャ
#set author 日本 Ruby の会 ささだこういち


- 2005-03-03(Thu) 00:31:12 +0900 いろいろと書き直し

----

* これは？

[[YARV: Yet Another RubyVM|http://www.atdot.net/yarv]] の 設計メモです。


YARV は、Ruby プログラムのための次の機能を提供します。

- Compiler
- VM Generator
- VM (Virtual Machine)
- Assembler
- Dis-Assembler
- (experimental) JIT Compiler
- (experimental) AOT Compiler


現在の YARV は Ruby インタプリタの拡張ライブラリとして実装しています。こ
れにより、Ruby インタプリタの必要な機能（パーサ、オブジェクト管理、既存
の拡張ライブラリ）などがほぼそのまま利用できます。

ただし、いくつかのパッチを Ruby インタプリタに当てなければなりません。

今後は、Ruby 本体のインタプリタ部分（eval.c）を置き換えることを目指して
開発を継続する予定です。


* Compiler (compile.h, compile.c)

コンパイラは、Ruby インタプリタのパーサによって生成された構文木（RNode 
データによる木）を YARV 命令列に変換します。YARV 命令については後述しま
す。

とくに難しいことはしていませんが、スコープなどの開始時にローカル変数の初
期化などを行い、あとは構文木を辿り変換していきます。

変換中は Ruby の Array オブジェクトに YARV 命令オブジェクト、およびオペ
ランドを格納していき、最後に実行できる形に変換します。コンパイラでは、コ
ンパイル中に生成するメモリ領域の管理が問題になることがありますが、YARV 
の場合、Ruby インタプリタがすべて面倒をみてくれるのでこの部分は非常に楽
に作ることができました（ガーベージコレクタによって自動的にメモリ管理をし
てくれるため）。

YARV 命令は、命令を示す識別子、オペランドなど、すべて 1 word （マシンで
表現できる自然な値。C 言語ではポインタのサイズ。Ruby インタプリタ用語で
は VALUE のサイズ）で表現されます。そのため、YARV 命令はいわゆる「バイト
コード」ではありません。そのため、YARV の説明などでは「命令列」という用
語を使っています。

1 word であるため、メモリの利用効率は多少悪くなりますが、アクセス速度な
どを考慮すると、本方式が一番いいと考えております。たとえばオペランドをコ
ンスタントプールに格納し、インデックスのみをオペランドで示すことも可能で
すが、間接アクセスになってしまうので性能に影響が出るため、却下しました。


* VM Generator (rb/insns2vm.rb, insns.def)

rb/insns2vm.rb というスクリプトは、insns.def というファイルを読み込み、
VM のために必要なファイルを生成します。具体的には、命令を実行する部分を
生成しますが、ほかにもコンパイルに必要な情報、最適化に必要な情報、やアセ
ンブラ、逆アセンブラに必要な情報を示すファイルも生成します。


** 命令記述

insns.def には、各命令がどのような命令であるかを記述します。具体的には次
の情報を記述します。

- 命令の名前
- その命令のカテゴリ、コメント（英語、日本語）
- オペランドの名前
- その命令実行前にスタックからポップする値
- その命令実行後にスタックにプッシュする値
- その命令のロジック（C 言語で記述）

たとえば、スタックに self をおく putself という命令は次のように記述しま
す。

#code
/**
  @c put
  @e put self.
  @j self を置く。
 */
DEFINE_INSN
putself
()
()
(VALUE val)
{
  val = GET_SELF();
}
#end

この場合、オペランドと、スタックからポップする値は無いことになります。命
令終了後、self をスタックトップに置きたいわけですが、それは val という、
スタックにプッシュする値として宣言しておいた変数に代入しておくことで、こ
れを変換するとスタックトップに置く C プログラムが生成されます。

細かいフォーマットは insns.def の冒頭を参照してください。そんなに難しく
ないと思います。

insnhelper.h というファイルに、命令ロジックを記述するために必要なマクロ
が定義されています。また、VM の内部構造に関する定義は vm.h というファイ
ルにあります。


* VM (Virtual Machine, vm.h, vm.c)

VM は、実際にコンパイルした結果生成される YARV 命令列を実行します。まさ
に、この部分が YARV のキモになり、将来的には eval.c をこの VM で置き換え
たいと考えています。

現在の Ruby インタプリタで実行できるすべてのことが、この VM で実現できる
ように作っています（現段階ではまだ完全ではありませんが、そうなるべきです）。

VM は、単純なスタックマシンとして実装しています。スレッドひとつにスタッ
クひとつを保持します。スタックの領域はヒープから取得するので、柔軟な領域
設定が可能です。


** レジスタ

VM は 5 つの仮想的なレジスタによって制御されます。

- PC (Program Counter)
- SP (Stack Pointer)
- CFP (Control Frame Pointer)
- LFP (Local Frame Pointer)
- DFP (Dynamic Frame Pointer)

PC は現在実行中の命令列の位置を示します。SP はスタックトップの位置を示し
ます。CFP、LFP、DFP はそれぞれフレームの情報を示します。詳細は後述します。


** スタックフレーム

obsolete (update soon)


** フレームデザインについての補足

Lisp の処理系などをかんがえると、わざわざブロックローカルフレームとメソ
ッドローカルフレームのようなものを用意するのは奇異に見えるかもしれません。
あるフレームを、入れ子構造にして、ローカル変数のアクセスはその入れ子を外
側に辿れば必ずたどり着くことができるからです（つまり、lfp は必要ない）。

しかし、Ruby ではいくつか状況が違います。まず、メソッドローカルな情報が
あること、具体的にはブロックとself（callee からみると reciever）です。こ
の情報をそれぞれのフレームにもたせるのは無駄です。

また、Ruby2.0 からはブロックローカル変数はなくなります（ブロックローカル
引数は残るので、構造自体はあまり変わりません）。そのため、メソッドローカ
ル変数へのアクセスが頻発することが予想されます。

このとき、メソッドローカル変数へのアクセスのたびにフレーム（スコープ）の
リストをたどるのは無駄であると判断し、明示的にメソッドローカルスコープと
ブロックフレームを分離し、ブロックフレームからはメソッドローカルフレーム
が lfpレジスタによって容易にアクセスできるようにしました。


** メソッド呼び出しについて

メソッド呼び出しは、YARV 命令列で記述されたメソッドか、C で記述されたメ
ソッドかによってディスパッチ手法が変わります。

YARV 命令列であった場合、上述したスタックフレームを作成して命令を継続し
ます。とくに VM の関数を再帰呼び出すすることは行ないません。

C で記述されたメソッドだった場合、単純にその関数を呼び出します（ただし、
バックトレースを正しく生成するためにメソッド呼び出しの情報を付加してから
行ないます）。

このため、VM 用スタックを別途用意したものの、プログラムによってはマシン
スタックを使い切ってしまう可能性があります（C -> Ruby -> C -> ... という
呼び出しが続いた場合）。これは、現在では避けられない仕様となっています。


** 例外

例外は、Java の JVM と同様に例外テーブルを用意することで実現します。例外
が発生したら、当該フレームを、例外テーブルを検査します。そこで、例外が発
生したときの PC の値に合致するエントリがあった場合、そのエントリに従って
動作します。もしエントリが見つからなかった場合、スタックを撒き戻してまた
同様にそのスコープの例外テーブルを検査します。

また、break、return（ブロック中）、retry なども同様の仕組みで実現します。

*** 例外テーブル

例外テーブルエントリは具体的には次の情報が格納されています。

- 対象とする PC の範囲
- 対象とする例外の種類
- もし対象となったときにジャンプする先（種類による）
- もし対象となったときに起動するブロックの iseq


*** rescue

rescue 節はブロックとして実現しています。$! の値を唯一の引数として持ちま
す。

#code
begin
rescue A
rescue B
rescue C
end
#end

は、次のような Ruby スクリプトに変換されます。

#code
{|err|
  case err
  when A === err
  when B === err
  when C === err
  else
    raise # yarv の命令では throw
  end
}
#end


*** ensure

正常系（例外が発生しなかった場合）と異常系（例外が発生したときなど）の2
種類の命令列が生成されます。正常系では、ただの連続したコード領域としてコ
ンパイルされます。また、異常系ではブロックとして実装します。最後は必ず 
throw 命令で締めることになります。


*** break, return（ブロック中）、retry

break 文、ブロック中の return 文、retry 文は throw 命令としてコンパイル
されます。どこまで戻るかは、break をフックする例外テーブルのエントリが判
断します。


** 定数の検索

定数という名前なのに、Ruby ではコンパイル時に決定しません。というか、い
つまでも再定義可能になっています。

定数アクセスのためのRuby記述は次のようになります。

#code
Ruby表現:
expr::ID::...::ID
#end

これは、yarv命令セットでは次のようになります。

#code
(expr)
getconstant ID
...
getconstant ID
#end


*** 定数検索パス

もし expr が nil だった場合、定数検索パスに従って定数を検索します。この
挙動は今後 Ruby 2.0 に向けて変更される場合があります。

+ クラス、モジュールの動的ネスト関係（プログラムの字面上）をルートまで辿る
+ 継承関係をルート（Object）まで辿る

このため、クラス、モジュールの動的ネスト関係を保存しなければなりません。
このために、thread_object には klass_nest_stack というものを用意しました。
これは、現在のネストの情報を保存します。

メソッド定義時、その現在のネスト情報をメソッド定義時に（dupして）加える
ことで、そのメソッドの実行時、そのネスト情報を参照することが可能になりま
す。

トップレベルでは、その情報はないことになります。

クラス/モジュール定義文実行時は、現在の情報そのものを参照することになり
ます。これは、クラススコープ突入時、その情報をクラス定義文にコピーします
（すでにコピーされていれば、これを行いません）。

これにより、動的なネスト情報を統一的に扱うことができます。


** 最適化手法

YARV では高速化を目的としているので、さまざまな最適化手法を利用していま
す。詳細は割愛しますが、以下に述べる最適化などを行なっております。


*** threaded code

GCC の C 言語拡張である値としてのラベルを利用して direct threaded code 
を実現しています。


*** Peephole optimization

いくつかの簡単な最適化をしています。


*** inline method cache

命令列の中にメソッド検索結果を埋め込みます。


*** inline constant cache

命令列の中に定数検索結果を埋め込みます。


*** ブロックと Proc オブジェクトの分離

ブロック付きメソッド呼び出しが行なわれたときにはすぐにはブロックを Proc 
オブジェクトとして生成しません。これにより、必要ない Proc オブジェクトの
生成を抑えています。

Proc メソッドは、実際に必要になった時点で作られ、そのときに環境（スコー
プ上に確保された変数など）をヒープに保存します。


*** 特化命令

Fixnum 同士の加算などを正直に関数呼び出しによって行なうと、コストがかか
るので、これらのプリミティブな操作を行なうためのメソッド呼び出しは専用命
令を用意しました。


*** 命令融合

複数の命令を 1 命令に変換します。融合命令は opt_insn_unif.def の記述によ
り自動的に生成されます。


*** オペランド融合

複数のオペランドを含めた命令を生成します。融合命令は opt_operand.def の
記述によって自動的に生成されます。


*** stack caching

スタックトップを仮想レジスタに保持するようにします。現在は 2 個の仮想レ
ジスタを想定し、5状態のスタックキャッシングを行ないます。スタックキャッ
シングする命令は自動的に生成されます。


*** JIT Compile

機械語を切り貼りします。非常に実験的なコードものしか作っておりません。ほ
とんどのプログラムは動きません。


*** AOT Compile

YARV 命令列を C 言語に変換します。まだ十分な最適化を行なえておりませんが、
それなりに動きます。rb/aotc.rb がコンパイラです。


* Assembler (rb/yasm.rb)

YARV 命令列のアセンブラを用意しました。使い方は rb/yasm.rb を参照してく
ださい（まだ、例示してある生成手法のすべてをサポートしているわけではあり
ません）。


* Dis-Assembler (disasm.c)

YARV 命令列を示すオブジェクト YARVCore::InstructionSequence には disasm 
メソッドがあります。これは、命令列を逆アセンブルした文字列を返します。


* YARV 命令セット

<%= d %>

* その他

** テスト

test/test_* がテストケースです。一応、ミスなく動くはずです。逆にいうと、
このテストに記述されている例ではきちんと動作するということです。


** ベンチマーク

benchmark/bm_* にベンチマークプログラムがおいてあります。


** 今後の予定

まだまだやらなければいけないこと、未実装部分がたくさんありますんでやって
いかなければなりません。一番大きな目標は eval.c を置き換えることでしょう
か。


*** Verifier

YARV 命令列は、ミスがあっても動かしてしまうため危険である可能性がありま
す。そのため、スタックの利用状態をきちんと事前に検証するようなベリファイ
アを用意しなければならないと考えています。


*** Compiled File の構想

Ruby プログラムをこの命令セットにシリアライズしたデータ構造をファイルに
出力できるようにしたいと考えています。これを利用して一度コンパイルした命
令列をファイルに保存しておけば、次回ロード時にはコンパイルの手間、コスト
を省くことができます。


**** 全体構成

次のようなファイル構成を考えていますが、まだ未定です。

#code
u4 : 4 byte unsigned storage
u2 : 2 byte unsigned storage
u1 : 1 byte unsigned storage

every storages are little endian :-)

CompiledFile{
  u4 magic;

  u2 major;
  u2 minor;

  u4 character_code;

  u4 constants_pool_count;
  ConstantEntry constants_pool[constants_pool_count];

  u4 block_count;
  blockEntry blocks[block_count];

  u4 method_count;
  MethodEntry methods[method_count];
}
#end

Java classfile のパクリ。