set_sequence @ compile.c - ひとり勉強会

では、ステップ４に進みます。
ここまでのステップで、Ruby の構文木が、命令 (struct INST) とラベル (struct LABEL) のリンクリストへと変換されました。リンクリストのままだと直接実行するにはまだ向かないので、次は、これをYARVの仮想マシン語のバイト列へと変換します。前回まではRubyのソースをYARVのアセンブラ言語のソースに落とす作業で、次がそれをマシン語に直すアセンブル担当みたいなものです。
あ、「リンクリストのままだと直接実行するにはまだ向かないので」・・・って自分で書いてみて気づきましたが、なんで向かないのだろう。

"次の命令に進む" のは、ポインタをたどるより配列の添え字を増やす方が速い
例外ハンドラの範囲指定などが "このラベルからこのラベルの間" という形なので、ラベルが前後比較できる構造になってないとダメ

この辺りでしょうか。Threaded codeとかにしやすいとかもあるのかな。

static int
set_sequence(yarv_iseq_t *iseq, LINK_ANCHOR *anchor)
{
  ... 略 ...
  /* set label position */
  list = FIRST_ELEMENT(anchor);
  k = pos = 0;
  while (list) {
    switch (list->type) {
      case ISEQ_ELEMENT_INSN:{
        iobj = (INSN *)list;
        pos += insn_data_length(iobj);
        k += 1;
        break;
      }
      case ISEQ_ELEMENT_LABEL:{
        lobj = (LABEL *)list;
        lobj->position = pos;
        lobj->set = Qtrue;
        break;
      }
      ... 略 ...
    }
    list = list->next;
  }

まず最初にやる作業は、ラベルの位置の計算です。YARVのマシン語は可変長命令で、命令ごとにバイト数が違います。先頭から順にinsn_data_length関数で長さを調べて（この関数の中では単純にテーブルを引いて長さを調べてます）、順に足し算していきます。あと、変数kで命令の個数を数えています。

  /* make instruction sequence */
  generated_iseq = ALLOC_N(VALUE, pos);
  insn_info_tbl = ALLOC_N(struct insn_info_struct, k);

  ... ここでアセンブル ...

  {
    iseq->iseq = (void *)generated_iseq;
    iseq->size = pos;
    iseq->insn_info_tbl = insn_info_tbl;
    iseq->insn_info_size = k;
    iseq->stack_max = stack_max;
  }

generated_iseq が、これから作るマシン語列のためのメモリ領域です。posバイト…じゃなくて、VALUEの配列なので、posワードの領域です。insn_info_tblは

struct insn_info_struct {
  unsigned short position;
  unsigned short line_no;
};

こういう構造体の配列で、各命令が元のRubyソースのどこに対応するかを覚えています。どちらも最終的に、iseq構造体のメンバとして記憶されます。
YARVのマシン語は、n引数の命令なら

[命令ID][引数1][引数2]...[引数n]

という(n+1)ワードの列です。なので、INSN構造体をワード列に変換する処理は、

list = FIRST_ELEMENT(anchor);
k = pos = sp = 0;

while (list) {
  switch (list->type) {
    case ISEQ_ELEMENT_INSN:{
      iobj = (INSN *)list;
      insn = iobj->insn_id;
      generated_iseq[pos] = insn;

命令IDを先頭ワードに入れて、次に、引数を先頭から順番に

      types = insn_op_types(insn);
      for (j = 0; types[j]; j++) {
        char type = types[j];
        switch (type) {
        ...
        case TS_NUM:
          generated_iseq[pos + 1 + j] = FIX2INT(operands[j]);
          break;

後ろのワードに詰めていく、というループになります。

        }
      }
      insn_info_tbl[k].line_no = iobj->line_no;
      insn_info_tbl[k].position = pos;
      pos += len;
      k++;
      break;
   }
  }

引数にはいくつか種類があります。例えばbranchif命令ならジャンプ先のラベルを引数にとりますし、getlocal命令はローカル変数テーブルのインデックスが引数です。

type	引数の種類	使用例
TS_OFFSET	ラベル	branchif
TS_CDHASH	ハッシュ	opt_case_dispatch
TS_LINDEX	ローカル変数表の添字	getlocal
TS_DINDEX	ブロックローカル変数表の添字	getdynamic
TS_NUM	整数	newarray
TS_ISEQ	命令列	send(のブロック引数)
TS_VALUE	Rubyオブジェクト	putobject
TS_IC	インラインキャッシュ	getinlinecache
TS_ID	ID、シンボル	send(のメソッド名引数)
TS_GENTRY	グローバル変数	getglobal

で、命令ごとに決まっているこの種類に応じて、insn->operandsに格納されている値を適切な方法でVALUE値へと変換します。

case TS_OFFSET:{
  /* label(destination position) */
  lobj = (LABEL *)operands[j];
  if (lobj->sp == -1) {
    lobj->sp = sp;
  }
  generated_iseq[pos + 1 + j] =
    lobj->position - (pos + len);
  break;
}

例えばラベル（TS_OFFSET）なら、operandsにはLABEL構造体へのポインタが入っていますが、ここから、さっき計算したラベルの位置を取得します。現在の命令からの相対アドレスを格納することになっているようなので、現在の命令が終わった直後のアドレス（pos+len）との差をとっています。

case TS_CDHASH:{
  VALUE lits = operands[j];
  VALUE map = rb_hash_new();
  for (i=0; i < RARRAY_LEN(lits); i+=2) {
    VALUE obj = rb_ary_entry(lits, i);
    VALUE lv  = rb_ary_entry(lits, i+1);
    lobj = (LABEL *)(lv & ~1);
    ...略...                
    rb_hash_aset(map, obj,
      INT2FIX(lobj->position - (pos+len)));
  }
  generated_iseq[pos + 1 + j] = map;

ハッシュ引数の場合、case式の最適化に使っていたので、operandsには[key,label,key,label,...]式のRubyの配列オブジェクトが入っています。これをRubyのハッシュオブジェクトに変換して格納しています。
他の場合は元々のoperandがポインタか整数かシンボルなので、そのままVALUEとしてワード列に突っ込んでました。あと、ちょっと説明さぼりましたが、TS_OFFSETのところで引用したコードに書いてあるように、各ラベルごとに、そのラベルに到達するときのスタックの深さ(sp)を記憶しています。

k = pos = sp = 0;
while (list) {
  switch (list->type) {
    case ISEQ_ELEMENT_INSN:{
      if (iobj->insn_id == BIN(emptstack) && sp == 0) {
        iobj->insn_id = BIN(nop);
      }
      else {
         sp = calc_sp_depth(sp, iobj);
         if (sp > stack_max) {
           stack_max = sp;
         }
      }
      ... 略 ...
    }
    case ISEQ_ELEMENT_LABEL:{
      lobj = (LABEL *)list;
      if (lobj->sp == -1) {
        lobj->sp = sp;
      }
      else {
        sp = lobj->sp;
      }
      break;
    }

命令の引数としてか、直接ラベルとしてか、どちらかで最初に出てきたときに、スタックの深さが記憶されます。
これで、マシン語のワード列が完成。