mruby/実行コード生成を読むのバックアップ(No.3)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
mruby/実行コード生成を読むへ行く。
- 1 (2012-05-24 (木) 06:25:05)
- 2 (2012-05-27 (日) 23:03:41)
- 3 (2012-06-06 (水) 22:42:38)
- 4 (2012-06-07 (木) 06:13:51)
- 5 (2012-06-07 (木) 21:19:06)
- 6 (2012-06-07 (木) 21:19:06)

mrubyを読む

はじめに
mrb_generate_code(src/codegen.c)
コード生成してみる

はじめに †

スクリプトの解析が終わったら今度はコード生成をするようです。ここら辺、MRI*1よりYARVと似ているような気がします。というわけで、mrb_generate_code()を読むことにします。

↑

mrb_generate_code(src/codegen.c) †

それではさっそくmrb_generate_code()を見てみましょう。

 
 
-
|
|
|
|
|
|
|
!
 
 
 
-
|
|
-
|
!
|
|
-
|
!
-
!
|
!

int
mrb_generate_code(mrb_state *mrb, node *tree)
{
  int start = mrb->irep_len;
  int n;
 
  n = codegen_start(mrb, tree);
  if (n < 0) return n;
 
  return start;
}
 
static int
codegen_start(mrb_state *mrb, node *tree)
{
  codegen_scope *scope = scope_new(mrb, 0, 0);
 
  if (!scope) {
    return -1;
  }
  scope->mrb = mrb;
 
  if (setjmp(scope->jmp) != 0) {
    return -1;
  }
  // prepare irep
  codegen(scope, tree, NOVAL);
  return 0;
}

codegen()はnodeの種類に応じて実行コード生成を行う巨大なswitch文です。このcodegen()が実行コード生成の本体のようです。また、codegen_scopeというのが現在のスコープに関する情報を持っているようなので実行コード生成読解の鍵となるデータ構造と考えていいでしょう。

↑

コード生成してみる †

コード生成時にデータ構造が具体的にどのようになるかは実例で確認、てことでさっそく実際にコード生成をしてみましょう。スクリプト生成の時にも書きましたがmrubyに--verboseオプションを付けると実行コードがダンプされます。

./mruby.exe -c --verbose ../../montecarlo.rb
irep 116 nregs=7 nlocals=4 pools=2 syms=5
000 OP_LOADNIL  R4
001 OP_LOADNIL  R5
002 OP_CLASS    R4      'MonteCarlo'
003 OP_EXEC     R4      I(117)
004 OP_LOADI    R4      10000
005 OP_LOADI    R5      10000
006 OP_LOADNIL  R6
007 OP_SEND     R4      '*'     1
008 OP_MOVE     R1      R4
009 OP_GETCONST R4      'MonteCarlo'
010 OP_LOADNIL  R5
011 OP_SEND     R4      'new'   0
012 OP_MOVE     R5      R1
013 OP_LOADNIL  R6
014 OP_SEND     R4      'pi'    1
015 OP_MOVE     R2      R4
016 OP_LOADSELF R4
017 OP_STRING   R5      'pi = '
018 OP_MOVE     R6      R2
019 OP_STRCAT   R5      R6
020 OP_STRING   R6      ''
021 OP_STRCAT   R5      R6
022 OP_LOADNIL  R6
023 OP_SEND     R4      'puts'  1
024 OP_STOP

irep 117 nregs=3 nlocals=2 pools=0 syms=1
000 OP_TCLASS   R2
001 OP_LAMBDA   R3      I(118)  1
002 OP_METHOD   R2      'pi'
003 OP_LOADNIL  R2
004 OP_RETURN   R4

irep 118 nregs=7 nlocals=5 pools=0 syms=4
000 OP_ENTER    1:0:0:0:0:0:0
001 OP_LOADI    R3      0
002 OP_LOADI    R5      1
003 OP_MOVE     R6      R1
004 OP_RANGE    R5      R5      0
005 OP_LAMBDA   R6      I(119)  2
006 OP_SEND     R5      'each'  0
007 OP_MOVE     R5      R3
008 OP_LOADNIL  R6
009 OP_SEND     R5      'to_f'  0
010 OP_MOVE     R6      R1
011 OP_LOADNIL  R7
012 OP_SEND     R5      '/'     1
013 OP_LOADI    R6      4
014 OP_LOADNIL  R7
015 OP_SEND     R5      '*'     1
016 OP_RETURN   R5

irep 119 nregs=7 nlocals=4 pools=0 syms=4
000 OP_LOADSELF R4
001 OP_LOADNIL  R5
002 OP_SEND     R4      'rand'  0
003 OP_MOVE     R1      R4
004 OP_LOADSELF R4
005 OP_LOADNIL  R5
006 OP_SEND     R4      'rand'  0
007 OP_MOVE     R2      R4
008 OP_MOVE     R4      R1
009 OP_MOVE     R5      R1
010 OP_LOADNIL  R6
011 OP_SEND     R4      '*'     1
012 OP_MOVE     R5      R2
013 OP_MOVE     R6      R2
014 OP_LOADNIL  R7
015 OP_SEND     R5      '*'     1
016 OP_LOADNIL  R6
017 OP_ADD      R4      '+'     1
018 OP_LOADI    R5      1
019 OP_LOADNIL  R6
020 OP_LE       R4      '<='    1
021 OP_JMPNOT   R4      028
022 OP_GETUPVAR R4      3       0
023 OP_LOADI    R5      1
024 OP_LOADNIL  R6
025 OP_ADD      R4      '+'     2
026 OP_SETUPVAR R4      3       0
027 OP_LOADNIL  R4
028 OP_RETURN   R4

トップレベル、クラス定義、メソッド定義、ブロックの4つのコードブロックが出力されることがわかります。また、以下のことがわかります。

symsはコードブロック内で使っているシンボルの数と思われる
poolsはコードブロック内で使っている文字列の数と思われる
nlocalsはコードブロック内のローカル変数の数と思われるがやや数が合わない
nregsはコードブロック内で使っているレジスタ数な気がするがややずれてるところがある

なお、各実行コードの説明はsrc/opcode.h内に書かれています。

ところで、irepのrepって何の略なんでしょうね？iはInstructionだと思いますが。

ちなみに、irepの番号がいきなり116から始まっているのは初期化時にRubyで書かれたライブラリの定義コードを読み込んでいるためと思われます。（つまり、115以前はライブラリ定義のirep）

↑

NODE_SCOPE †

ではnodeツリーをたどってどうやってコードが生成されていくかを眺めていきましょう。まずはルートのNODE_SCOPEです。なお、今後示すcase文はcodegen()の巨大なswitch文中のcase文です。

  1
  2
  3

  case NODE_SCOPE:
    scope_body(s, tree);
    break;

 
 
-
|
|
|
-
|
|
!
-
|
|
!
|
|
|
!

static int
scope_body(codegen_scope *s, node *tree)
{
  codegen_scope *scope = scope_new(s->mrb, s, tree->car);
  int idx = scope->idx;
 
  if (!s->iseq) {
    codegen(scope, tree->cdr, VAL);
    genop(scope, MKOP_A(OP_STOP, 0));
  }
  else {
    codegen(scope, tree->cdr, VAL);
    genop(scope, MKOP_AB(OP_RETURN, cursp(), OP_R_NORMAL));
  }
  scope_finish(scope, idx);
 
  return idx - s->idx;
}

というわけで新しいスコープを作ってcodegen()を再帰呼び出ししています。トップレベルなのでs->iseqはNULL、すなわち、実行コードの最後はOP_STOPが埋め込まれるようです。

scope_new()、scope_finish()も見てみましょう。

 
 
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
!
 
 
 
-
|
|
|
|
|
|
|
|
-
|
|
!
-
|
|
!
-
|
|
!
|
|
|
|
|
!

static codegen_scope*
scope_new(mrb_state *mrb, codegen_scope *prev, node *lv)
{
  mrb_pool *pool = mrb_pool_open(mrb);
  codegen_scope *p = mrb_pool_alloc(pool, sizeof(codegen_scope));
  if (!p) return 0;
 
  memset(p, 0, sizeof(codegen_scope));
  p->mrb = mrb;
  p->mpool = pool;
  if (!prev) return p;
  p->prev = prev;
  p->ainfo = -1;
 
  p->mrb = prev->mrb;
  p->icapa = 1024;
  p->iseq = mrb_malloc(mrb, sizeof(mrb_code)*p->icapa);
 
  p->pcapa = 32;
  p->pool = mrb_malloc(mrb, sizeof(mrb_value)*p->pcapa);
 
  p->syms = mrb_malloc(mrb, sizeof(mrb_sym)*256);
 
  p->lv = lv;
  p->sp += node_len(lv)+2;
  p->nlocals = p->sp;
 
  p->idx = mrb->irep_len++;
 
  return p;
}
 
static void
scope_finish(codegen_scope *s, int idx)
{
  mrb_state *mrb = s->mrb;
  mrb_irep *irep;
 
  mrb_add_irep(mrb, idx);
  irep = mrb->irep[idx] = mrb_malloc(mrb, sizeof(mrb_irep));
 
  irep->idx = idx;
  irep->flags = 0;
  if (s->iseq) {
    irep->iseq = codegen_realloc(s, s->iseq, sizeof(mrb_code)*s->pc);
    irep->ilen = s->pc;
  }
  if (s->pool) {
    irep->pool = codegen_realloc(s, s->pool, sizeof(mrb_value)*s->plen);
    irep->plen = s->plen;
  }
  if (s->syms) {
    irep->syms = codegen_realloc(s, s->syms, sizeof(mrb_sym)*s->slen);
    irep->slen = s->slen;
  }
 
  irep->nlocals = s->nlocals;
  irep->nregs = s->nregs;
 
  mrb_pool_close(s->mpool);
}

nlocalsがローカル変数の数と一致しない理由がわかりました。そういえばYARVでも特殊変数用にスタックを割り当てていた気がします。本当にそうなのかはコード実行のところで見ることにします。

また、scope_finish()を見るとわかるようにスコープを閉じるとmrb_stateにirepが追加されるようです。

↑

NODE_CLASS †

次にNODE_CLASSです。

 
-
|
|
-
|
|
!
-
|
|
!
-
|
!
-
|
!
-
|
|
!
|
|
|
|
|
-
|
!
!

  case NODE_CLASS:
    {
      int idx;
 
      if (tree->car->car == (node*)0) {
        genop(s, MKOP_A(OP_LOADNIL, cursp()));
        push();
      }
      else if (tree->car->car == (node*)1) {
        genop(s, MKOP_A(OP_OCLASS, cursp()));
        push();
      }
      else {
        codegen(s, tree->car->car, VAL);
      }
      if (tree->cdr->car) {
        codegen(s, tree->cdr->car, VAL);
      }
      else {
        genop(s, MKOP_A(OP_LOADNIL, cursp()));
        push();
      }
      pop(); pop();
      idx = new_msym(s, (mrb_sym)tree->car->cdr);
      genop(s, MKOP_AB(OP_CLASS, cursp(), idx));
      idx = scope_body(s, tree->cdr->cdr->car);
      genop(s, MKOP_ABx(OP_EXEC, cursp(), idx));
      if (val) {
        push();
      }
    }
    break;

parse.yに書かれたNODE_CLASSの構造を考えると初めのif文で生成しているコードはクラスを定義するモジュールの参照、2つ目のif文でスーパークラスを参照しているようです。今回はトップレベルに、スーパークラス指定はなしなので両方OP_LOADNILが埋め込まれることになります。その後、クラス定義をしているirepを作ってそれを呼び出すコードを生成しています。

↑

NODE_DEF †

深さ優先にクラス定義の中に入っていくことにします。というわけでNODE_DEFを見てみます。

 
-
|
|
|
|
|
|
|
|
-
|
!
!

  case NODE_DEF:
    {
      int sym = new_msym(s, (mrb_sym)tree->car);
      int idx = lambda_body(s, tree->cdr, 0);
 
      genop(s, MKOP_A(OP_TCLASS, cursp()));
      push();
      genop(s, MKOP_Abc(OP_LAMBDA, cursp(), idx, OP_L_METHOD));
      pop();
      genop(s, MKOP_AB(OP_METHOD, cursp(), sym));
      if (val) {
        genop(s, MKOP_A(OP_LOADNIL, cursp()));
      }
    }
    break;

lambda_body()ですがちょっと長めです。部分部分にわけて説明します。

 
 
-
|
|
|
|
|

static int
lambda_body(codegen_scope *s, node *tree, int blk)
{
  int idx, base = s->idx;
  mrb_code c;
 
  s = scope_new(s->mrb, s, tree->car);
  idx = s->idx;

まず新しいスコープを作っています。

-
|
|
!
!
|
|
|
-
|
-
|
|
|
|
|
|
-
|
!
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|

  if (blk) {
    struct loopinfo *lp = loop_push(s, LOOP_BLOCK);
    lp->pc1 = new_label(s);
  }
}
 
ブロック定義の場合の処理がされていますが今はメソッド定義なので飛ばします。
 
#code(C){{
  tree = tree->cdr;
  if (tree->car) {
    int ma, oa, ra, pa, ka, kd, ba, a;
    int pos, i;
    node *n, *opt;
 
    ma = node_len(tree->car->car);
    n = tree->car->car;
    while (n) {
      n = n->cdr;
    }
    oa = node_len(tree->car->cdr->car);
    ra = tree->car->cdr->cdr->car ? 1 : 0;
    pa = node_len(tree->car->cdr->cdr->cdr->car);
    ka = kd = 0;
    ba = tree->car->cdr->cdr->cdr->cdr ? 1 : 0;
 
    a = ((ma & 0x1f) << 18)
      | ((oa & 0x1f) << 13)
      | ((ra & 1) << 12)
      | ((pa & 0x1f) << 7)
      | ((ka & 0x1f) << 2)
      | ((kd & 1)<< 1)
      | (ba & 1);
    s->ainfo = (((ma+oa) & 0x3f) << 6) /* (12bits = 6:1:5) */
      | ((ra & 1) << 5)
      | (pa & 0x1f);
    genop(s, MKOP_Ax(OP_ENTER, a));

tree->carは引数情報が入っています。それぞれ、

ma: 通常引数
oa: オプション引数
ra: 残余引数
pa: ポスト引数*2
ka: キーワード引数*3
ba: ブロック引数

を示しており、その情報がコードに埋め込まれるようです。

 
-
|
|
!
-
|
!
 
 
-
|
|
|
|
|
|
|
|
|
!
-
|
!
!

    pos = new_label(s);
    for (i=0; i
      new_label(s);
      genop(s, MKOP_Ax(OP_JMP, 0));
    }
    if (oa > 0) {
      genop(s, MKOP_Ax(OP_JMP, 0));
    }
    opt = tree->car->cdr->car;
    i = 0;
    while (opt) {
      int idx;
 
      dispatch(s, pos+i);
      codegen(s, opt->car->cdr, VAL);
      idx = lv_idx(s, (mrb_sym)opt->car->car);
      pop();
      genop_peep(s, MKOP_AB(OP_MOVE, idx, cursp()), NOVAL);
      i++;
      opt = opt->cdr;
    }
    if (oa > 0) {
      dispatch(s, pos+i);
    }
  }

オプション引数の処理を行っています。コードをそのまま解説してもわかる人は少数でしょうからまず実例を示します。

def foo(a = 1, b = 'xxx')
end

上記のRubyスクリプトの実行コードは以下のようになります。

$ ./mruby.exe -c --verbose ../../optarg.rb
irep 117 nregs=6 nlocals=5 pools=1 syms=0
000 OP_ENTER    0:2:0:0:0:0:0
001 OP_JMP              004
002 OP_JMP              005
003 OP_JMP              006
004 OP_LOADI    R1      1
005 OP_STRING   R2      'xxx'
006 OP_RETURN   R4

実行系はまだ見てませんが何となく以下の挙動をするんだろうなぁということがわかります。

foo()と呼んだら001から実行される（つまり、004から実行される）
foo(2)と呼んだら002から実行される（つまり、005から実行される）
foo(3, 'zzz')と呼んだら003から実行される（つまり、006から実行される）

なんでこんなめんどくさいことを・・・、と思われるかもしれませんがRubyのオプション引数はデフォルト値ではなく、デフォルト「式」なのでこうしないといけません。例えば、以下のスクリプトのように、

def bar
  123
end

def foo(a = 1, b = bar)
end

./mruby.exe -c --verbose ../../optarg2.rb
irep 118 nregs=6 nlocals=5 pools=0 syms=1
000 OP_ENTER    0:2:0:0:0:0:0
001 OP_JMP              004
002 OP_JMP              005
003 OP_JMP              009
004 OP_LOADI    R1      1
005 OP_LOADSELF R5
006 OP_LOADNIL  R6
007 OP_SEND     R5      'bar'   0
008 OP_MOVE     R2      R5
009 OP_RETURN   R4

と、bの値を決定するために別メソッドが呼び出されることもあるのです。

話が長くなりましたが以上を踏まえてオプション引数処理として何をやっているかというと、

まず、OP_JMPを埋め込み
各オプション引数について
1. OP_JMPのジャンプ先を決定し（dispatch()に書かれています）
2. デフォルト式に対応するコードを生成し
3. デフォルト式の結果を
最後にメソッド本体へのOP_JMP先を決定して終わり

ということをしています。ちなみに、genop_peep()というのは冗長なコードを簡約する処理なようです。また、上記のコードではOP_JMPが絶対アドレスジャンプになっていますが、実際のコードは相対アドレスジャンプになっているようなのでdispatch()を見るときは注意してください。

 
 
 
-
|
!
-
|
!
 
 
 
!

  codegen(s, tree->cdr->car, VAL);
  pop();
  c = s->iseq[s->pc-1];
  if (GET_OPCODE(c) != OP_RETURN || GETARG_B(c) != OP_R_NORMAL || s->pc == s->lastlabel) {
    genop(s, MKOP_AB(OP_RETURN, cursp(), OP_R_NORMAL));
  }
  if (blk) {
    loop_pop(s, NOVAL);
  }
  scope_finish(s, idx);
 
  return idx - base;
}

ようやく、メソッド定義のコードを生成し、最後にreturnの処理を入れて*4終わりです。