miura1729の日記

ytljitの型推論の説明(その4)

22:35 |

　ytljitでao benchが動いたらruby-listにアナウンスするんだ！と決めているのですが、なかなか動かなくて苦労しています。

さて、型推論の説明の続きです。ytljitではYARVの命令列をノードと呼ぶオブジェクトのグラフ(VMと呼んでいる)に変換し、その後そのグラフをトラバースして機械語に変換します。ちょうどノードはYARVと機械語の中間くらいの命令に相当します。YARVや機械語のようにシーケンシャル(ジャンプはあるけど)ではなく、グラフ構造になっているのは型推論のためです。関連のあるノードを素早く(O(1)で)アクセスするためです。

型推論はこんな手順で行います

• データフロー解析を行ってデータの依存関係を調べる。例えば、ローカル変数の参照を表すノードなら、この変数に値を設定したノード(分岐やジャンプがあるので1つとは限らない)を集める
• 次のようなことを各ノードについて行う。すべてのノードについて行って、推論が収束するまで繰り返す
  1. 明らかに型が決められるノードについては型を設定する。例えばリテラルや定数など
  2. 各ノードについて同じ型になるノードのリンクを作る例えば、
     • 変数の設定ノードなら設定する値と変数の型は同じ
     • メソッドの呼び出しなら、渡す引数とメソッド定義の仮引数の変数の型は同じ。メソッド定義のメソッドの戻りの型とメソッド呼び出しノードの型は同じ
• 実際にノードの型が知りたかったらノードに対して、decide_type_onceメソッドを実行する

訳が分からないと思いますが、順番に説明していきます。

初めのデータの依存関係を調べるところは、私が説明するよりドラゴンとか虎の表紙の本を読んでもらった方がずっといいと思います。特別なことはしていないと思います。各ノードで定義されているcollect_infoメソッドがこの処理にあたります。

推論部分の説明をします。これは各ノードで定義されているcollect_candidate_typeメソッドで行います。

collect_candidate_typeの説明の前に重要な点を2つ挙げます。

• 各ノードは複数の型になり得ます。

例えば、

 if foo
   a = 1
 else
   a = 1.0
 end

とした場合、変数aの型はFixnumまたはFloatです。ytljitではこうした場合、FixnumまたはFloatという情報を保持します。しかし、コンパイルに型情報を使う場合、このようなFixnumまたはFloatという曖昧な情報では使い物になりません。そこで、decide_type_onceメソッドを用意しました。このメソッドは複数の型の候補から1つの型を決定するメソッドです。いろいろな状況でいろいろな戦略が考えられます。例えば、FixnumとFloatならFixnumをFloatに変換して、Floatと推論するとか、RubyのObject型に推論して必ずboxing処理を入れるとか、Fixnum/Floatを両方表すことのできる独自フォーマットを導入するとかです。この戦略をノード毎に設定出来るわけです。

• シグネチャが重要な働きをします

前から何度も出てきているシグネチャーが重要な働きをします。型情報を得るにはノードが決まれば決まるわけではなく、シグネチャーも必要になります。シグネチャーが異なれば同じノードでも違う型情報を持ちます。

長くなってきたのでこれで中断します。次は、collect_candidate_typeの中身について説明します。

続く