Ruby1.9/YARVコードへのコンパイルを読む

はじめに †

ここではスクリプト解析で構築した構文木をYARVコードにコンパイルする処理を読解したいと思います。

ruby_exec_node(eval.c) †

スクリプトの解析が終わると解析したNODEツリーを引数にruby_run_node関数が呼ばれ、その中でruby_exec_node関数が呼ばれます。ruby_exec_node関数ではNODEツリーをYARVコードに変換（rb_iseq_new関数）し実行（rb_iseq_eval関数）しています。

rb_iseq_new(iseq.c) †

rb_iseq_new関数は最終的にrb_iseq_new_with_bopt_and_opt関数に行き着きます。どんな引数が渡されるのかを見るために呼び出しフローを見てみましょう。

VALUE iseq = rb_iseq_new(n, rb_str_new2("<main>"),
			 rb_str_new2(file), Qfalse, ISEQ_TYPE_TOP);

rb_iseq_new(NODE *node, VALUE name, VALUE filename,
	      VALUE parent, VALUE type)
{
    return rb_iseq_new_with_opt(node, name, filename, parent, type,
				&COMPILE_OPTION_DEFAULT);
}

static rb_compile_option_t COMPILE_OPTION_DEFAULT = {
    OPT_INLINE_CONST_CACHE, /* int inline_const_cache; */
    OPT_PEEPHOLE_OPTIMIZATION, /* int peephole_optimization; */
    OPT_TAILCALL_OPTIMIZATION, /* int tailcall_optimization */
    OPT_SPECIALISED_INSTRUCTION, /* int specialized_instruction; */
    OPT_OPERANDS_UNIFICATION, /* int operands_unification; */
    OPT_INSTRUCTIONS_UNIFICATION, /* int instructions_unification; */
    OPT_STACK_CACHING, /* int stack_caching; */
    OPT_TRACE_INSTRUCTION, /* int trace_instruction */
};

vm_opts.h

#define OPT_INLINE_CONST_CACHE       1      
#define OPT_PEEPHOLE_OPTIMIZATION    1
#define OPT_TAILCALL_OPTIMIZATION    0
#define OPT_SPECIALISED_INSTRUCTION  1
#define OPT_OPERANDS_UNIFICATION     0
#define OPT_INSTRUCTIONS_UNIFICATION 0
#define OPT_STACK_CACHING            0       
#define OPT_TRACE_INSTRUCTION        0

rb_iseq_new_with_opt(NODE *node, VALUE name, VALUE filename,
		     VALUE parent, VALUE type,
		     const rb_compile_option_t *option)
{
    return rb_iseq_new_with_bopt_and_opt(node, name, filename, parent, type,
					   Qfalse, option);
}

rb_iseq_new_with_bopt_and_opt(NODE *node, VALUE name, VALUE filename,
				VALUE parent, VALUE type, VALUE bopt,
				const rb_compile_option_t *option)
{

iseq_compile(compile.c) †

コンパイル処理のエントリーポイントとなる関数はiseq_compile関数です。ローカル変数テーブルと引数を処理した上でCOMPILEマクロ経由で子ノードがiseq_compile_each関数に渡されます。

iseq_compile_each(compile.c) †

コンパイルのメイン処理です。NODEのタイプに応じてYARVコードを生成しています。

new_child_iseq(compile.c) †

NODE_CLASSやNODE_DEFNに行き当たるとマクロ経由でnew_child_iseq関数が呼ばれます。new_child_iseq関数はrb_iseq_new_with_opt関数を呼ぶことで再帰的にNODEをYARVコードに変換しています。

LINK_ELEMENT(compile.c) †

compile.cを読んでいるとNODEを変換した結果のYARVコードやラベルがLINK_ELEMENTという構造体に追加されていることがわかります。LINK_ELEMENT構造体はコンパイル時の作業領域で最終的なYARVコードを生成するために必要な情報を格納するものなようです。

ADD_INSNファミリー(compile.h) †

YARVコードを追加するのにはADD_INSNマクロファミリーが使われています。例えばローカル変数を設定するコードは以下のようになります。

ADD_INSN1(ret, nd_line(node), setlocal, INT2FIX(idx));

#define ADD_INSN1(seq, line, insn, op1) \
  ADD_ELEM(seq, (LINK_ELEMENT *) new_insn_body(iseq, line, BIN(insn), 1, (VALUE)op1))
  iseqは関数の引数で渡されたrb_iseq_t*

new_insn_body関数はargc引数で指定された数の追加引数を受け取り設定します。compile_data_alloc関数を呼ぶことで必要に応じて領域を拡大します。

new_insn_core関数はcompile_data_alloc_insn関数（compile_data_alloc関数のラッパーです）を呼んでINSN構造体の領域を確保しデータを設定します。その後、ADD_ELEM関数が呼び出されリストにYARVコード情報がつながれます。結果、ADD_INSN1の呼び出しで以下のデータが設定されることになります。

ADD_SEND_R(compile.h) †

メソッド呼び出しにはADD_SEND_Rマクロが使われています。

#define ADD_SEND_R(seq, line, id, argc, block, flag) \
  ADD_ELEM(seq, (LINK_ELEMENT *) \
           new_insn_send(iseq, line, \
                         (VALUE)id, (VALUE)argc, (VALUE)block, (VALUE)flag))

new_insn_send関数は引数を指定してnew_insn_core関数を呼びsend命令を追加しています。引数は以下の5つです。

メソッドのシンボル表現
引数の数
ブロックを示すInstructionSequenceオブジェクト
フラグ
0

iseq_setup(compile.c) †

iseq_compile関数の最後でiseq_setup関数が呼ばれています。この時点ではまだYARVコードは作業領域に置かれています。iseq_setup関数を呼び出すことで最適化が行われた上でrb_iseq_t構造体に情報が詰め込まれます。

iseq_optimize(compile.c) †

この関数はコンパイルオプションに応じてYARVコードの最適化を行っています。デフォルトではpeephole_optimizationとspecialize_instructionが有効です。

iseq_peephole_optimize(compile.c) †

この関数ではjump命令のすぐ次にあるラベルに飛ぶ意味のないjump命令の除去などの最適化を行っています。

iseq_specialized_instruction(compile.c) †

この関数では演算子メソッドなどのよく出現するsend命令を専用の命令に置き換える最適化を行っています。

insn_operands_unification(optinsn.inc) †

この関数は・・・何もやってない？おそらくvm_opts.hのコンパイルオプションを変更すればわかると思いますが今回は追求を止めておきます。

iseq_insns_unification(compile.c) †

実際にはこの関数はiseq_optimize関数から呼び出されていませんが最適化の一部なのでここに書いておきます。unified_insns_dataが空なので動作がトレースできませんが名前の通り複数の命令を1つにしているようです。

iseq_set_sequence_stackcache(compile.c) †

この関数も同様にiseq_optimize関数からではなくiseq_setup関数から呼び出されます。同じくコンパイルオプションの都合で有益な情報がないので深追いは止めておきます。

iseq_set_sequence(compile.c) †

この関数で作業領域に置かれていたYARVコードがrb_iseq_t構造体に設定されます。

まずLINK_ELEMENTをスキャンして各命令の命令長と命令の数を数え、必要なメモリを確保しています。ラベルの場合は今までの合計命令長を位置として設定します。

次にもう一度LINK_ELEMENTをスキャンし確保したメモリに命令コードを埋め込んでいます。その際、calc_sp_depth関数を呼び出して各命令を実行した後のスタック長および最大スタック長を計算しています。また、insn_op_types関数を呼び出すことで各命令の各引数が何を表しているかが取得し、情報の埋め込みを行っています。例えばjump命令でどれだけ飛べばよいかといった情報が埋め込まれます。

iseq_set_exception_table(compile.c) †

この関数ではコンパイル時にADD_CATCH_ENTRYマクロで追加された、ブロック内でbreakされた場合にどのラベルに移動すればよいかといった情報をrb_iseq_t構造体に設定しています。

iseq_set_optargs_table(compile.c) †

この関数ではデフォルト値付き引数の設定情報をrb_iseq_t構造体に設定しています。この関数は設定するだけですがデフォルト値の設定はなかなか興味深いですね。コメントをそのまま貼り付けるのが一番理解しやすいので転載します。

*   def foo(a, b=expr1, c=expr2)
*   =>
*    b:
*      expr1
*    c:
*      expr2

つまり、b引数が設定されていなかったらbラベルに飛んでexpr1を実行、結果がスタックに積まれることでb引数となるというからくりなようです。確かにRubyって正確にはデフォルト式でデフォルト値を決定するためにメソッド呼び出しとかできますからね*1。

iseq_translate_threaded_code(compile.c) †

この関数では設定した命令コードをより実行に適した形に変換しています。デフォルトだとOPT_DIRECT_THREADED_CODEが有効です。vm_eval関数が書かれているvm_evalbody.cを見るとなかなか難解なコードが書かれていますが簡単に言うと各命令処理ルーチンの開始アドレスが格納されます。

ところでvm_eval関数は2引数なのですがcompile.cからは1引数で呼ばれてます。そういうことってやっても大丈夫なんでしたっけ？

VM::InstructionSequence †

手動コンパイルした結果が合っているか調べるには実際にコンパイルされるコードと比較してみることです。

puts VM::InstructionSequence.compile_file(file).disasm

とするとfileで指定したスクリプトがコンパイルされ、YARVコードが表示されます。ちなみに私は結構間違えていました:-)

なお、デフォルトでは最適化されたものが出てくるので最適化されていないものが見たい場合は、

VM::InstructionSequence.compile_option = false

とすると最適化が行われません。なお、inline_const_cacheは変換時にコードが埋め込まれるのでinline_const_cacheもオフにしてしまうと手動コンパイル結果と食い違ってしまいます。その場合は、

VM::InstructionSequence.compile_option = {:inline_const_cache => true}

とするとinline_const_cacheを有効にできます。

コンパイルしてみる †

実際にNODEをコンパイルしてみると動きがよくわかるでしょう。スクリプト解析を読むで作成したNODEツリーを変換してみましょう。

NODE_SCOPE †

NODEツリーの頂点はNODE_SCOPEです。というわけでiseq_compile関数ではiseq_set_local_table関数が呼ばれてlocal_tableが設定されます。

local_table = ID("n"), ID("pi")
local_table_size = 2
local_size = 2 + 1

次にiseq_set_arguments関数が呼ばれますが引数はないのでelseの方が実行されます。

arg_simple = 1

次のswitch文ではISEQ_TYPE_TOPなので単純にCOMPILEマクロが呼ばれます。debug_compileは無視するとしてiseq_compile_each関数が呼ばれます。

どのような引数が渡されるのか見てみましょう。

COMPILE(ret, "scoped node", node->nd_body);

#define COMPILE(anchor, desc, node) iseq_compile_each(iseq, anchor, node, 0)

iseq_compile_each(rb_iseq_t *iseq, LINK_ANCHOR *ret, NODE * node, int poped)

一連のコンパイルが終わると最後にleaveが追加されます。

NODE_BLOCK †

NODE_BLOCKのそれぞれの要素に対してCOMPILE_マクロ（先ほどとは違い、_が付いています）が呼び出されています。popedはリストの最後だけ0でそれ以外は1なようです*2。

NODE_CLASS †

ブロックの一番初めはNODE_CLASSなのでNODE_CLASSの処理に移りましょう。まずNEW_CHILD_ISEQVALマクロが実行されます。引数は以下の通りです。

#define NEW_CHILD_ISEQVAL(node, name, type) new_child_iseq(iseq, node, name, iseq->self, type)
  node = NODE_SCOPE
  name = "<class:MonteCarlo>"
  type = ISEQ_TYPE_CLASS

次にcompile_cpath関数が呼ばれています。cpathはNODE_COLON2でcpath->nd_headは0なのでputnilが追加されます。

次にnode->nd_superが指定してCOMPILEマクロが呼ばれますがnd_superは0なので同様にputnilが追加されます。

その後、defineclass("MonteCarlo", iseqval, 0)が追加されます。iseqvalはNEW_CHILD_ISEQVALマクロで作られたクラス定義です。

最後にpopedが1なのでpopが追加されます。

NODE_DEFN †

new_child_iseq関数が呼ばれることでrb_iseq_new_with_opt → iseq_compile → iseq_compile_eachと再帰呼び出しされてまたiseq_compile_each関数にやってきます。NODE型はNODE_DEFNなのでNEW_ISEQVALマクロが実行されます。

#define NEW_ISEQVAL(node, name, type) new_child_iseq(iseq, node, name, 0, type)
  node = NODE_SCOPE
  name = "pi"
  type = ISEQ_TYPE_METHOD

次にputnilが追加されます。

次にdefinemethod("pi", iseqval, 0)が追加されます。

最後にpopedが0なのでputnilが追加されます。

iseq_set_arguments †

というわけでまた再帰呼び出しされてiseq_compile関数に来ます。今回は引数があるのでiseq_set_arguments関数を眺めることにしましょう。NODEに従って読み進めていくと以下のようになりました。

argc = 1
arg_opts = 0
arg_simple = 1
arg_size = 1

NODE_LASGN †

それではNODE_DEFN以下のコンパイルに進みましょう。まずNODE_BLOCKを経由してNODE_LASGN(count = 0)に行き着きます。

get_local_var_idx関数を実行することで変数のIDがlocal_tableの何番目かが返ってきます。countは1番目（0始まり）です。

次にrhsを指定してCOMPILEマクロが実行されます。NODE_LITなのでputobject(0)が追加されます。

最後にsetlocal(3 - 1)が追加されます。

NODE_ITER †

NODE_BLOCKの次の要素はNODE_ITERです。まずブロックの先頭に戻るためのラベルが追加されます。

次にブロックのNODEツリーを引数にNEW_CHILD_ISEQVALマクロが呼ばれて結果がcompile_data->current_blockに設定されています。

node = NODE_SCOPE
name = "block in pi"
type = ISEQ_TYPE_BLOCK

次にメソッド呼び出しの部分（(1..n).each）がCOMPILEマクロにかけられます。NODE_CALLがsendに変換され、ブロックとして上で変換したInstructionSequenceオブジェクトが指定されます。

次にブロックを抜けるためのラベルが追加されます。

次にpopedが1なのでpopが追加されます。

最後にADD_CATCH_ENTRYマクロを使用してcompile_data->catch_table_aryに情報を追加しています。catch_table_aryはbreakなどの場合にどこに移動するかを識別する情報のようです。

NODE_DASGN_CURR †

ブロックの初めのNODE_BLOCKはNODE_DASGN_CURR(x = rand)です。NODE_LASGNに似てますが少し違うようです。まずrhsを指定してCOMPILEマクロが実行されています。

変数のIDからインデックスを取得するのにget_dyna_var_idx関数が呼ばれています。get_local_var_idxとの違いは現在の変数テーブルに変数がなかったら親を探してさかのぼったレベルを返すところです。

最後にsetdynamic(2 - 0, 0)が追加されます。

NODE_VCALL †

rhsはNODE_VCALLです。SUPPORT_JOKEは飛ばして:-)、まずレシーバが設定されています。ADD_CALL_RECEIVERマクロを展開するとputnilが追加されるようです。

次に引数の設定ですがNODE_VCALLなので何も追加されません。

その後、flagにVM_CALL_VCALL_BITとVM_CALL_FCALL_BIT（コメントにも書いてありますがVCALLは同時にFCALLなのでFCALL_BITも設定されます。case文はbreakで抜けていません）が設定され、ADD_SEND_Rマクロが呼び出されてsendが追加されます。

NODE_IF †

まずnode->nd_condがコンパイルされます。NODE_CALLなのでそのままCOMPILEマクロに通されます。

次にbranchunless(elseラベル)とjump(thenラベル)が追加されます。

次にthenラベルが追加され、thenの部分をコンパイル、jump(endラベル)が追加されます。

次にelseラベルが追加され、elseの部分がコンパイルされます。

最後にendラベルが追加されます。

NODE_CALL †

条件部はNODE_CALL(x * x + y * y <= 1)です。NODE_VCALLに似ていますが今回はレシーバも引数もあります。

まずレシーバがCOMPILEマクロにかけられます。レシーバ(x * x + y * y)のレシーバ(x * x)までNODE_CALLなのですが先に進みます。

次にsetup_args関数が呼ばれて引数が追加されます。引数はNODE_ARRAYなのでcompile_array関数（compile_array_関数のラッパーでpopedに0が渡されています）にかけられます。要素はNODE_LITが1つだけなのでputobject(1)が追加されます（opt_pがQfalseでpopedが0なのでnewarray(1)が追加されますが、setup_args関数に戻ってくると取り除かれます）。

その後、ADD_SEND_Rマクロが呼ばれてsendが追加されます。

NODE_DVAR †

次にレシーバ部を何回か再帰してNODE_DVAR(x)に行き着きます。NODE_DASGN_CURRと同様に get_dyna_var_idx関数で情報を取得した後、getdynamic(2 - 0, 0)が追加されます。

NODE_DOT2 †

始点(1)と終点(n)がCOMPILEマクロにかけられ、その後にnewrange(0)が追加されます。

NODE_CALL(poped = 0) †

メソッド定義の最後のNODE_BLOCKはNODE_CALLです。popedが0なのでpopが追加されません。ここまで見てきて気づいた人は気づいたと思うのですがどうやらYARVはスタックマシンのようです。ごそごそした結果、スタックの一番上にある値がメソッドの戻り値になるというわけですね。

NODE_CONST †

しばらくは既存の知識でどうにかなるとして、NODE_CONST(MonteCarlo)もスルーしようかなと思ったらおもしろいことをしてるので書いておきます。compile->option->inline_const_cacheが有効（デフォルトだと有効）の場合、以下のような命令コードが追加されます。

:開始ラベル
getinlinecache(0, 終了ラベル)
getconstant(:MonteCarlo)
setinlinecache(開始ラベル)
:終了ラベル

見てわかるようにキャッシュされてたらgetconstantがバイパスされています。Rubyではクラスは定数でクラスを参照することは多いからという理由でこの最適化がされてると思われます。

NODE_DSTR †

最後にNODE_DSTR("pi = #{pi}")です。compile_dstr関数が呼ばれています。

compile_dstr関数ではまずputobject("pi = ")が追加されます。その後、NODE_ARRAYの各要素がCOMPILEマクロにかけられます。要素はNODE_EVSTRでNODE_EVSTRの要素はNODE_LVARなのでgetlocal(2 - 1)とtostringが追加されます。最後にconcatstrings(2)が追加されます。

コンパイル結果 †

というわけでNODEからYARVコードへのコンパイルが完了しました。コンパイル結果と、peepholeおよびspecialized_instruction最適化を施した結果を示します。見方は以下のようになります。

>>>>>>>> 識別名(他から参照される名前)
rb_iseq_tの変数値
**** code
YARV擬似コード
引数あり命令(引数1, 引数2, ...)
:ラベルはこう書かれている
<<<<<<<< 識別名

montecarlo.yarv.txt montecarlo.yarv.opt.txt

おわりに †

今回はNODEツリーからYARVコードへのコンパイルを見てきました。コンパイル処理では各NODEを素直に変換した後、最適化を行い、最終的なバイトコード*3に変換を行っています。

それではコードの実行へ進みましょう。