YARVソースコード勉強会(10)

今日から、最適化の部分を読みにかかります。の、前に。
元旦にRuby本家にYARVがマージされたそうです（[ruby-dev: 30061]）。今年からはこちらを読んでいこうと思います。レポジトリのURLは

• http://svn.ruby-lang.org/repos/ruby/trunk

で、今週はさっきチェックアウトした時点での最新の rev.11578 を読んでいます。

最適化の流れ

だいぶ間が空いてしまったので、まずは流れのおさらいから。

• yarvcore_eval_parsed @ yarvcore.c
  • th_compile_from_node @ yarvcore.c
    • yarv_iseq_new_with_opt @ iseq.c
      • iseq_compile @ compile.c
        • iseq_compile_each @ compile.c
        • iseq_setup @ compile.c

第3回〜第9回まで読んだのがiseq_compile_each、Rubyの構文木をYARVの命令のリストに変換する関数でした。その次に来るのが、iseq_setup。この関数の前半は、生成された命令リストの最適化を行っています。

static int
iseq_setup(yarv_iseq_t *iseq, LINK_ANCHOR *anchor)
{
  iseq_optimize(iseq, anchor);
  if (iseq->compile_data->option->instructions_unification) {
	iseq_insns_unification(iseq, anchor);
  }
  if (iseq->compile_data->option->stack_caching) {
	set_sequence_stackcaching(iseq, anchor);
  }
  ...続く...

コメントやチェックコードなどは勝手にわたしが除いて転載しております。大筋はこんな感じということで。さて、最適化ステップは３段階に分かれているようです。最初のiseq_optimizeはさらに内部で３つに分かれています。

static int
iseq_optimize(yarv_iseq_t *iseq, LINK_ANCHOR *anchor)
{
  LINK_ELEMENT *list;
  const int do_peephole =
    iseq->compile_data->option->peephole_optimization;
  const int do_si =
    iseq->compile_data->option->specialized_instruction;
  const int do_ou =
    iseq->compile_data->option->operands_unification;
  list = FIRST_ELEMENT(anchor);
    
  while (list) {
    if (list->type == ISEQ_ELEMENT_INSN) {
      if (do_peephole) {
        iseq_peephole_optimize(iseq, list);
      }
      if (do_si) {
        iseq_specialized_instruction(iseq, (INSN *)list);
      }
      if (do_ou) {
        insn_operands_unification((INSN *)list);
      }
    }
    list = list->next;
  }
  return COMPILE_OK;
}

命令１個１個をwhileループで回って、各命令に対して最適化をほどこしています。
まとめると、この段階で行われる最適化は５つ。

最適化	関数名
覗き穴最適化		iseq_peephole_optimize
特化命令	iseq_specialized_instruction
オペランド融合	insn_operands_unification
命令融合	iseq_insns_unification
スタックキャッシング	set_sequence_stackcaching

それぞれ順番に見ていきます。

iseq_peephole_optimize

コンパイル結果を局所的に見て、ちょこちょこっと命令列を効率の良いものに書き換えていく最適化を、ピープホール最適化（覗き穴最適化）と言います。現在のYARVでは、無駄なジャンプ命令を見つけては書き換えるというピープホール最適化を行っています。

static int
iseq_peephole_optimize(yarv_iseq_t *iseq, LINK_ELEMENT *list)
{
    INSN *iobj = (INSN *)list;
  again:

iseqという命令列の中の、iobjという命令を最適化しようと試みます。まずは、無条件ジャンプ命令だった場合の最適化。

  if (iobj->insn_id == BIN(jump)) {
	INSN *niobj, *diobj, *piobj;
	diobj = (INSN *)get_destination_insn(iobj);
	niobj = (INSN *)get_next_insn(iobj);

    if (diobj == niobj) {
      REMOVE_ELEM(&iobj->link);
    }

直後の命令にジャンプするような命令は無駄です。別にジャンプしなくても放っておけば直後の命令に行きますから。というわけで、そういう命令を見つけたら削除しています。

  else if (iobj != diobj && diobj->insn_id == BIN(jump)) {
    OPERAND_AT(iobj, 0) = OPERAND_AT(diobj, 0);
    goto again;
  }

ジャンプ先がさらにジャンプ命令だった場合、２段ジャンプするよりは、１回で最終目的地までジャンプした方が効率的ですねという最適化。同じ効率化は、条件ジャンプ命令(branchif/branchunless)命令の先が無条件ジャンプ命令だった場合、にも使えます。

  if (iobj->insn_id == BIN(branchif) ||
    iobj->insn_id == BIN(branchunless)) {
    INSN *nobj = (INSN *)get_destination_insn(iobj);
      if (nobj->insn_id == BIN(jump)) {
        OPERAND_AT(iobj, 0) = OPERAND_AT(nobj, 0);
    }
  }

などなど。この辺りについては、YARV Maniacs 【第7回】 にささださんによる解説があります。

iseq_specialized_instruction

こちらについては YARV Maniacs 【第9回】 で丸々１回をさいて解説されています。引用させていただくと、

すでに述べたように「1 + 2」のようなプログラムは Ruby では「1.+(2)」と解釈されますが、コンパイル時にチェックして、

• 呼び出すメソッドが "+"
• 引数の数が 1 つ
• ブロックなどは付かない

という場合には汎用の "send" 命令ではなく、"opt_plus" 命令にコンパイルします

という最適化だそうです。これを行うコードは

static int
iseq_specialized_instruction(yarv_iseq_t *iseq, INSN *iobj)
{
  if (iobj->insn_id == BIN(send)) {
    ID mid = SYM2ID(OPERAND_AT(iobj, 0));
    int argc = FIX2INT(OPERAND_AT(iobj, 1));
    VALUE block = OPERAND_AT(iobj, 2);
    VALUE flag = OPERAND_AT(iobj, 3);

    if (block == 0 && flag == INT2FIX(0)) {
      ...
      if (argc == 1) {
        ...
        if (mid == idPLUS) {
          insn_set_specialized_instruction(iobj, BIN(opt_plus));
        }

で、まさにそのまま解説の通りでした。insn_set_specialized_instruction もそのまんまです。

static int
insn_set_specialized_instruction(INSN *iobj, int insn_id)
{
  iobj->insn_id = insn_id;
  iobj->operand_size = 0;
  return COMPILE_OK;
}

では次。

insn_operands_unification

オペランド融合。この最適化は現在はOFFになってるみたいです。一応ソースだけ読んでみました。

この関数は、ビルド時に定義ファイル"opt_operand.def"から自動生成されます。（自動生成スクリプトは"tool/insns2vm.rb"。）定義ファイルの中身はこんな感じで、

getlocal 2
getlocal 3
getlocal 4

setlocal 2
setlocal 3
setlocal 4

getdynamic *, 0
getdynamic 1, 0
...

１行が１個の融合命令に対応しています。例えば最初の行「getlocal 2」は、getlocal_OP_2 という融合命令を定義しています。この定義に対応して、insn_operands_unification 関数が自動生成されます（Makefileと同じディレクトリの、optinsn.incというファイルです）。

static INSN *
insn_operands_unification(INSN *insnobj){
#ifdef OPT_OPERANDS_UNIFICATION
  /* optimize rule */
  switch(insnobj->insn_id){

case BIN(getlocal):
  if(
    insnobj->operands[0] == INT2FIX(2)
  ){
    insnobj->insn_id = BIN(getlocal_OP_2);
    insnobj->operand_size = 0;
    break;
  }
  if(
    insnobj->operands[0] == INT2FIX(3)
  ){
    insnobj->insn_id = BIN(getlocal_OP_3);
    insnobj->operand_size = 0;
    break;
  }
  ...

getlocal命令に引数2を渡している箇所を、getlocal_OP_2 という専用命令に置き換える、という処理ですね。まだ読んでませんがたぶん実行時は、命令ごとにdispatchしてから、オペランドの必要な命令ではオペランドを読み取って、実際の処理…という流れになっているんだと思います。なので、よくあるオペランドについては固定した専用命令を作ってしまって、読み取り処理を省いた方が効率的になり得るのでしょう。かと言って全ての可能なオペランドについて全部融合命令を作ることはできませんから、よくあるパターンについてだけ、定義しておくという形になっています。

iseq_insns_unification

命令融合。こちらも同じく現在はOFFになってるみたいです。一応ソースだけ読んでみました。

さっき見たオペランド融合は、よくある「命令＋オペランド」の組を１個の専用融合命令に置き換えてしまう最適化でした。こっちの命令融合というのは、よく連続する命令、「命令＋命令」の組を１個の専用融合命令に置き換えてしまう最適化です。仕組み的には３命令以上の連続「命令＋命令＋命令＋...」も一気に融合するケースも考えて作られていましたが、実際には使われていない模様。

融合したい命令＋命令の組は、ビルド時に定義ファイル"opt_insn_unif.def"から自動生成されます。（自動生成スクリプトはオペランド融合のものと同じ、"tool/insns2vm.rb"。）定義ファイルの中身はこんな感じで、

putobject putobject
putobject putstring
putobject setlocal
putobject setdynamic

putstring putstring
putstring putobject
putstring setlocal
putstring setdynamic
...

たとえば最初の行はputobjectの直後にまたputobjectするパターンをまとめる、UNIFIED_putobject_putobject という専用命令を定義しています。この定義に対応して、テーブルが自動生成されます（Makefileと同じディレクトリの、optunifs.incというファイルです）。

static int UNIFIED_putobject_0[] = {  BIN(UNIFIED_putobject_putobject), 3, 
  BIN(putobject)};
static int UNIFIED_putobject_1[] = {  BIN(UNIFIED_putobject_putstring), 3, 
  BIN(putstring)};
static int UNIFIED_putobject_2[] = {  BIN(UNIFIED_putobject_setlocal), 3, 
  BIN(setlocal)};
static int UNIFIED_putobject_3[] = {  BIN(UNIFIED_putobject_setdynamic), 3, 
  BIN(setdynamic)};
...
static int *UNIFIED_putobject[] = {(int *)5, 
  UNIFIED_putobject_0,
  UNIFIED_putobject_1,
  UNIFIED_putobject_2,
  UNIFIED_putobject_3};
...
static int **unified_insns_data[] = {
  0,
  UNIFIED_getlocal,
  0,
  ...
  0,
  0,
  UNIFIED_putobject,
  UNIFIED_putstring,
  0,
  ...

unified_insns_data[１個目の命令] とテーブルをひくと、１個目の命令に対応する融合命令のリストが手に入ります。そのリストでループをまわして、次の命令と２個目の命令で一致するものがあったら置き換え、なければ何もしない、という処理で最適化が行われます。

static int
iseq_insns_unification(yarv_iseq_t *iseq, LINK_ANCHOR *anchor)
{
  list = FIRST_ELEMENT(anchor);
  while (list) {
    if (list->type == ISEQ_ELEMENT_INSN) {
      iobj = (INSN *)list;
      id = iobj->insn_id;
      if (unified_insns_data[id] != 0) {
        int **entry = unified_insns_data[id];
}

テーブルを引いて、

        for (j = 1; j < (int)entry[0]; j++) {
          int *unified = entry[j];
          LINK_ELEMENT *li = list->next;

ループを回して、

        for (k = 2; k < unified[1]; k++) {
          if (li->type != ISEQ_ELEMENT_INSN ||
              ((INSN *)li)->insn_id != unified[k]) {
             goto miss;
          }
          li = li->next;
        }

次の命令ととマッチしていたら

        /* matched */
        niobj =
         new_unified_insn(iseq, unified[0], unified[1] - 1,
           list);
        ... 続く ...

置き換え、となっています。

set_sequence_stackcaching

YARV Maniacs【第8回】 によると「性能上の問題から、現時点では有効にできないようにしてあります」とのことです。一応ソースだけ読んでみました。

スタックの先頭付近最大２個分だけ特別な領域（AレジスタとBレジスタ）に持っておいて、スタック操作命令の数を減らしたりしようという最適化です。yarv-dev:354 のささださんの投稿がわかりやすかったです。
具体的には、各命令を「レジスタに値が載ってない場合バージョン」「Aレジスタにスタック先頭の値が載ってる場合バージョン」「Bレジスタに(以下同文」「Aに先頭、Bに2番目が載ってる場合バージョン」「Bに先頭、Aに2番目が載ってる場合バージョン」の５バージョンに増やします。

増やし方の定義テーブルは、ビルド時に"insns.def"（YARV命令の基本定義ファイル）から例によって "tool/insns2vm.rb" によって生成されます。（Makefileと同じディレクトリの、opt_sc.incというファイルです）。

static VALUE sc_insn_info[][SC_STATE_SIZE] = {
  {
SC_ERROR,
    BIN(nop_SC_xx_xx),
    BIN(nop_SC_ax_ax),
    BIN(nop_SC_bx_bx),
    BIN(nop_SC_ab_ab),
    BIN(nop_SC_ba_ba)},
  {
SC_ERROR,
    BIN(getlocal_SC_xx_ax),
    BIN(getlocal_SC_ax_ab),
    BIN(getlocal_SC_bx_ba),
    BIN(getlocal_SC_ab_ba),
    BIN(getlocal_SC_ba_ab)},
...

static VALUE sc_insn_next[] = {
  SCS_XX,
  SCS_XX,
  ...
  SCS_XX,
  SCS_XX,
  SCS_AX,
  SCS_BX,

sc_insn_infoが増えた命令テーブルで、sc_insn_nextは、あるレジスタ＆スタック状態でどの命令を実行したらどういう状態に遷移するか、のテーブルです。この２つのテーブルを使って、全部の命令を書き換えていくのがset_sequence_stackcaching関数です。

static int
set_sequence_stackcaching(yarv_iseq_t *iseq, LINK_ANCHOR *anchor)
{
#if OPT_STACK_CACHING
　 ...
      case BIN(pop):{
         switch (state) {
         case SCS_AX:
         case SCS_BX:
             state = SCS_XX;
             break;
         case SCS_AB:
             state = SCS_AX;
             break;
         case SCS_BA:
             state = SCS_BX;
             break;
         case SCS_XX:
             goto normal_insn;
         default:
             rb_bug("unreachable");
         }
         /* remove useless pop */
         REMOVE_ELEM(list);
         list = list->next;
         goto redo_point;
      }

詳細を見てもそのまんまで特にこれといった点もないので、テーブルを引いていない特別な場合、pop命令の部分だけ抜粋しました。状態の遷移がまず計算されています。popの場合、レジスタに値が載っている時は状態が変わるだけで何も実行時にすることがなくなるので、命令を丸ごと１個取り除けます。

まとめ

今日はYARVの最適化フェーズについてでした。

• ピープホール最適化
• 特化命令
• (オペランド融合)
• (命令融合)
• (スタックキャッシング)

専用命令を新しく作る系の最適化に関しては、定義ファイルから新しい命令を自動生成という形になっているのが面白いなーと思いました。

• insns.def
  • 普通の命令の定義
  • スタックキャッシング命令の計算にも使われる
• opt_operand.def
  • オペランド融合命令の定義
• opt_insn_unif.def
  • 命令融合命令の定義

というわけで、また来週！