RuJIT開発日記

Ruby処理系向けトレース方式JITコンパイラRuJITの開発日記

RuJITの中間表現 LIR

Ruby向けJITコンパイラ RuJIT Advent Calendar 4日目です.
今日はRuJITの中間表現 LIRを紹介します.
RuJITの中間表現LIRはYARVバイトコードを参考に設計したレジスタベースの中間表現で,実行時に収集した型情報をもった中間表現です.

LIRの定義はlir.defに記述されています.LIRの命令はどのように定義されているのでしょうか?.LIRの各命令は以下の形式にのっとって記述されています.

命令名 :フラグ* (命令の引数リスト)

フラグにはdef, use, trans, effect, frame, terminator, transがあり,それぞれdefは変数定義の有無,useは変数の使用,effectは副作用の有無,frameはメソッドフレーム操作の有無,そしてterminatorはブロックの末端に来て良い命令であることを示しています.

命令の引数リストはそれぞれ”引数の名前:引数の型”の形式をとっており,ここで引数の型はC言語上での型を意味します.

これだけではよくわからないので実例を出しながら説明していきます.
以下にFixnumの加算を扱うLIR命令FixnumAddOverflowの定義を示します.

FixnumAddOverflow :def :use (LHS:lir_t, RHS:lir_t)

FixnumAddOverflow,def, useのフラグを持ち,2つの引数を持つ命令です.
もう1つ例としてArray.set(Index, Value)を表す命令ArraySetの定義を示します.

ArraySet :def :use :effect (Recv:lir_t, Index:lir_t, Val:lir_t)

ArraySetはdef, use, trans, effectのアノテーションを持ち,3つの引数を持つ命令として定義されています.

# コードの自動生成
現在LIRの命令数は130命令程度となっており,命令数は開発当初から増え続ける一方となっています.命令が追加・変更されるたびにLIRの生成,dump関数,フラグの設定を行うのを正しく実装するのは困難を極めます.

そこでRuJITでは各命令用の構造体,命令生成関数,引数へのアクセッサ,dump関数,そして各種フラグを自動で生成する仕組みを導入し開発コストを抑えるようにしています.
例として先程も例としてあげたFixnumAddOverflow命令の定義から生成されたコードを見て行きたいと思います.以下にFixnumAddOverflow命令の定義を再掲しておきます.
FixnumAddOverflow :def :use (LHS:lir_t, RHS:lir_t)

現在RuJITでは主に5つのコード列を生成します.
はじめにopcodeの番号やフラグ管理用の定数定義です.
ここで定義されている値はlir_is_terminator関数やlir_is_guard関数などから直接的・関節的に参照され,RuJITの各機能を記述するのに必要な行数の削減に貢献しています.
1114 #define OPCODE_IFixnumAddOverflow 26
1115 #define LIR_USE_FixnumAddOverflow 1
1116 #define LIR_DEF_FixnumAddOverflow 1
1117 #define LIR_SIDE_EFFECT_FixnumAddOverflow 0
1118 #define LIR_IS_TERMINATOR_FixnumAddOverflow 0
1119 #define LIR_PUSH_FRAME_FixnumAddOverflow 0
1120 #define LIR_IS_GUARD_INST_FixnumAddOverflow 0

続いて命令の構造体の定義を生成します.コード生成やコード最適化器はここで定義された構造体を操作し変形・コード生成を行っていきます.
1121 typedef struct IFixnumAddOverflow {
1122 lir_inst_t base;
1123 lir_t LHS;
1124 lir_t RHS;
1125 } IFixnumAddOverflow;

次はコード生成関数です.RuJITではコード生成の際,一旦LIR命令の実態をスタック上に確保した後ヒープにコピーするという順番で命令の生成を行っています.(このような形になっているのにはいくつか理由がある.主な理由の1つには命令生成後,最適化によってすぐに不要となる命令などがあるため)ADD_INSTマクロによってコードはブロックに追加されていきます.
1127 static lir_t Emit_FixnumAddOverflow(lir_builder_t *builder, lir_t LHS, lir_t RHS)
1128 {
1129 IFixnumAddOverflow *ir = LIR_NEWINST(IFixnumAddOverflow);
1130 ir->LHS = LHS;
1131 ir->RHS = RHS;
1132 return ADD_INST(builder, ir);
1133 }

1146 static lir_t *GetNext_FixnumAddOverflow(lir_inst_t *Inst, int idx)
1147 {
1148 IFixnumAddOverflow *ir = (IFixnumAddOverflow *)Inst;
1149 switch(idx) {
1150 case 0:
1151 return &ir->LHS;
1152 case 1:
1153 return &ir->RHS;
1154 }
1155 return NULL;
1156 }

1134 static void Dump_FixnumAddOverflow(lir_inst_t *Inst)
1135 {
1136 #if DUMP_LIR > 0
1137 IFixnumAddOverflow *ir = (IFixnumAddOverflow *)Inst;
1138 fprintf(stderr, " " FMT_ID " %d FixnumAddOverflow", lir_getid(&ir->base), ir->base.flag);
1139 fprintf(stderr, " LHS:");
1140 fprintf(stderr, FMT(lir_t), DATA(lir_t, ir->LHS));
1141 fprintf(stderr, " RHS:");
1142 fprintf(stderr, FMT(lir_t), DATA(lir_t, ir->RHS));
1143 fprintf(stderr, "\n");
1144 #endif /*DUMP_LIR > 0*/
1145 }