miura1729の日記

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

22:03 |

なんだかんだで、2か月以上さぼってました。その6です。

今回はsame_typeの実装の話です。

same_typeはdstというノードがdsigというシグネチャでノードが存在するメソッドやブロックを実行している時、srcというノードのssigというシグネチャでの型と同じになると設定します。same_typeの実際のコードを見てみましょう。

def same_type(dst, src, dsig, ssig, context)
 if dst.is_a?(BaseNode) then
   src.ti_add_observer(dst, dsig, ssig, context)
  end

  ti_update(dst, src, dsig, ssig, context)
end

• ti_add_observer
• ti_update

の2つのメソッドが出てきました。この2つを順に説明します。

ti_add_observer

ti_add_observerはすべてのノードが持っている@ti_observerというインスタンス変数を設定するメソッドです。@ti_observer(tiはtype inferenceの略)は、そのノードの型が変わったら、その変化に応じて型が変化するノード(dstノード)のリストです。@ti_observerはハッシュテーブルになっていてdstノードがキーです。値は、"[srcのシグネチャ, dstのシグネチャ, srcの型が変化したら呼び出すProcオブジェクト]という配列"の配列です。通常、このProcでti_updateを呼び出します。

ti_add_observerのコードを見てみましょう。

def ti_add_observer(dst, dsig, ssig, context)
  if @ti_observer[dst] == nil then
    @ti_observer[dst] = []
    dst.ti_observee.push self
  end
          
  if @ti_observer[dst].all? {|edsig, essig, eprc| 
      (edsig != dsig) or (essig != ssig)
     } then
    prc = lambda { send(:ti_update, dst, self, dsig, ssig, context) }
    @ti_observer[dst].push [dsig, ssig, prc]
  end
 end

やっていることは、@ti_observerにdstのエントリがなければ、空の配列でエントリを作成します。

次に、まだエントリがなければ@ti_observerに追加します。src/dstとも同じシグネチャのエントリが既にあれば、追加されません。

ti_update

次に、ti_updateを見てみます。ti_update(dst, src, dsig, ssig, context)でdstのdsigというシグネチャでの型の候補リストにsrcのssigでの型の候補リストをマージします。マージの結果、型の候補リストが大きくなったら、dstに対して、ti_changedというメソッドを呼び出します。ti_changedは@ti_observerのProcオブジェクトを順番に呼び出します。結果的にdstが変化して影響の受けるノードについて、ti_updateが呼び出され、型情報の拡散が実現できます。

ti_updateのコードを見てみましょう。

def ti_update(dst, src, dsig, ssig, context)
  dtlistorg = dst.type_list(dsig)       # (1)
  dtlist = dtlistorg.flatten            # (1')
  stlist = src.type_list(ssig).flatten  # (2)

  orgsize = dtlist.size                      # (3)
  newdt = merge_type(dtlistorg[1], stlist)   # (4)
  dst.set_type_list(dsig, newdt)             # (5)
  dtsize = dtlistorg[0].size + newdt.size    # (6)

  if orgsize != dtsize then                  # (7)
    dst.type = nil                           # (8)
    dst.ti_changed                           # (9)
    context.convergent = false               # (10)
  end

  dtlist = dst.element_node_list
  stlist = src.element_node_list
  orgsize = dtlist.size
  dst.element_node_list = merge_type(dtlist, stlist)
  if orgsize != dtlist.size then
    dst.ti_changed
    context.convergent = false
  end

 if src.is_escape then
    if dst.is_escape != true then
       dst.is_escape = src.is_escape
    end
  end
end

はじめにdst(影響を受ける側)とsrc(影響を与える側)の型候補リストを得ます。型候補リストはシグネチャ毎にあるのでシグネチャがパラメータで必要です(1), (2)。flattenの意味はかなり特殊な場合の対策なのであまり気にしないでください。

(3)でdstの型候補リストのサイズを求めておきます。(4)でsrcとdstの型候補リストをマージして、(5)でdstに設定します。(6)で新しい型候補リストのサイズを求めます。

もし、(3)と(6)が違う場合次のことをします(7)。

• dst.type(型候補リストから型を1つに決めたもののキャッシュ)をnilにします。型候補リストそのものが変わったのでdst.typeは無意味になります。(8)
• dst.ti_changedを呼び出す。これは前に説明した通り、dstから影響の受けるノードの型候補リストのアップデートを行います。
• context.convergentをfalseにする。これは、型推論が収束したかのフラグでfalseだと推論を繰り返します。型候補リストが変わるような場合だとまだまだ型が変わっていく可能性があるので型推論を終えるわけにはいかないのです。

と、こんな感じです。まだ、続きがありますが、これを説明するためには新たな概念の説明が必要になります。これはelement_node_listです。次回はこれについて説明したいと思います。

みんなが寒いといっているうちに続きを書きたいですがどうなることやら。続く

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

02:56 |

今回は、collect_candidate_typeの説明です。candidateとは候補とかそういった意味です。つまり、そのノードの型になる候補(複数かもしれないし0かもしれない)を収集します。前回説明したとおり、この候補から型を選び出すのが、decide_type_onceです。

collect_candidate_typeは引数にcontextを１つとり*1、contextを返します。 collect_candidate_typeの中で別に何をしてもよいのですが、主に行うのは次の3つです。このうち最初の２つの操作については、すべてのノードのスーパークラスのBaseNodeクラスでメソッドが定義されているのでこれを使います。

• 型候補を加える(add_type)
• 他のノードと同じ型だよということを設定する(same_type)
• 他のノードに対して、 collect_candidate_typeを呼び出す

型候補を加えるのは、リテラルや定数など型が明らかな場合です。たとえば、LiteralNodeではこんな感じで推論するまでもなく型候補を加えてしまいます。

   @type = RubyType::BaseType.from_object(@value) 
   sig = context.to_signature
   add_type(sig, @type)

@valueにはリテラルの値が入ります。add_typeにもシグネチャーを渡さなければなりません。

add_typeは複数の型を設定することもできます。

  add_type(sig, FLOAT)
  add_type(sig, FIXNUM)
  add_type(sig, BIGNUM)

まだ、複数の型をadd_typeで設定する場合はありませんが、nilと本来の値といった複数の型を返すメソッドの型指定で使用する予定です。

次に、同じ型だよということを設定する場合です。これが一番多いと思います。たとえば、次のような場合を考えてみます。

  a = 10

このようなプログラムはローカル変数の代入を表すLocalAssignNodeと10を表すLiteralNodeとに変換されます。

  LocalAssignNode
    @val         -> LitralNode (値は10)
　　@offset   ローカル変数のフレーム上のオフセット
    @depth　　何レベル下のフレームにアクセスするか

LocalAssignNodeの型は@valの型と同じになります。この場合、same_typeというメソッドを使って次のようにします。

   context = @val.collect_candidate_type(context)
   selfsig = context.to_signature
   valsig = context.to_signature
   same_type(self, @val, selfsig, valsig, context)

このプログラムは「selfは@valと同じ型です」という意味になります。ただし、selfはselfsig,@valはvalsigのシグネチャの場合に限ります。シグネチャは現在このノードのあるメソッドやブロックの引数の型ですが、シグネチャでsame_typeを限定する必要があるのでしょうか？たとえば、こんな場合を考えてみます。

  1 << 1
  [] << 1

メソッド<<はselfがfixnumの場合はselfと引数の型は同じです。でも、selfが配列の場合は同じとは限りません。そのため、<<がselfと引数で型が同じと単純に設定してしまうとうまくいきません。でも、シグネチャを指定してselfがFixnumの場合だけ同じであると指定すれば問題ないわけです。

あと、細かい話ですが、

  same_type(self, @val, selfsig, valsig, context)

は、selfが@valと同じ型であると指定していますが、@valとselfが同じ型であるとは言っていません。つまり、selfが別のところでsame_typeやadd_typeで別の型が候補に加わっても@valには影響がありません。相互に影響をもたらしたいなら、

  same_type(self, @val, selfsig, valsig, context)
  same_type(@val, self, valsig, selfsig, context)

と2つsame_typeを書く必要があります。このように片方にしか影響が及ばないことを利用して複数の型の候補が現れて型推論が出来なくなった場合、その影響範囲を小さくすることができます。

最後の他のノードのcollect_candidate_typeを呼び出すのはそれほど説明することはありません。ただし、add_typeもsame_typeも副作用を持ちますのでcollect_candidate_typeを呼び出す順番に注意する必要があります。

次はsame_typeの実装について書きたいと思います。同じ型という情報をどう保持するのか、どう更新するのか。Observerパターンを使っているとかそんな話です。

続く

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の中身について説明します。

続く

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

18:14 |

しつこいようですが、シグネチャーはメソッド呼び出しの際の引数を推論した結果の型オブジェクトの配列です。そして、型推論の際には必ずシグネチャが必要になります。

この2つのことから勘のいい人は気づくかも知れませんが(私はプログラムしてバグるまで気づかなかった)、シグネチャーを作るのにシグネチャーがいるのです。普通のメソッドだとそれほど問題ではないのですが、ブロック付きのメソッドの場合、シグネチャの型が一発で決まらないので、この辺の話が重くのしかかります。これが(その1)で書いたバグの根本の原因であろう(まだ取れてないので想像)と思うのですが、この辺はよくわかってないので分かったら書きます。

　次にメソッドの引数の話をします。ytljitではユーザが指定する普通の引数のほかに隠れ引数を渡します。隠れ引数は現在のところ次の3つです(例外処理とかで増えるかもしれない)。

1. 親のブロックまたはメソッドのフレーム
2. メソッド呼び出しの際に渡されたブロックのコードの先頭アドレス
3. self

これらの型オブジェクトもシグネチャーの配列に入ります。1番目の親のブロックの型はフレームは現在のところ、常にNilClassです。

2番目のブロックの先頭アドレスのの型はブロックの戻り値の型が入ります。この、引数のおかげで違う型のブロックを渡しても破たんすることなく推論できます。

　# 両方がどっかで同じプログラム中に出てくる
  [1, 2, 3].map { |e| e.to_s }　　# 文字列を返すブロックをmapに渡す
  [1, 2, 3].map { |e| e.to_f }　　# Floatを返すブロックをmapに渡す

こんなコードすごくありがちですから、これが全部動的に型チェックされると大変です。

ブロックの戻り値の型を決めるためには、メソッドコールの際に渡しているブロックを型推論する必要があるのですが、そのためにはメソッド中のyieldの引数の推論を行う必要があって、このシグネチャーが必要になるのです。堂々めぐりですが、何とかなりそうです。「なります」と言い切れないのがつらいところ。

selfは問題ないでしょう。推論出来なければダイナミックメソッドサーチが必要になるので型チェックが増えるどころの騒ぎじゃないです。

なんか、わけのわからない愚痴っぽい文になってしましたが、次回は型推論メソッド(collect_candidate_type)が何をやっているか書きたいと思います。

続く　(と思う)

(追記)

うっかり、前回の伏線を回収し忘れたので書きます。型推論contextのcurrent_method_signature_node とcurrent_methodの話です。

何度も書いている通り、型推論では必ずシグネチャーが必要になります。そこで、現在推論中のメソッドのシグネチャを型推論contextに持たせています。

ただ、シグネチャーは推論が進んでいくと変わる可能性があるので、型オブジェクトの配列という形で持たず毎回推論するようにしています。

具体的には今推論中のメソッドを呼び出したsend命令の引数を表現するノードの配列(current_method_signature_node)とメソッドノード(current_method)いう形で保持しています。そして、シグネチャーが必要になったら毎回推論してシグネチャーを作っています。

ここがかなり重くて全体の実行時間の6割を費やしているので何とかキャッシュできないか考えています。

さて、シグネチャーを作るために型推論する場合、シグネチャーが必要になります。型推論contextには呼び出し元の引数のノードが入っているので、呼び出し元のメソッドのシグネチャーが必要になります。同様に、呼び出し元のメソッドのシグネチャーを推論する場合はその呼び出し元の呼び出し元がが必要になります。つまり、呼出し履歴の全部のノードを取っておく必要があります。

そういう理由でcurrent_method_signature_nodeとcurrent_methodはスタックのような構造になっています。

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

22:46 |

2回目はシグネチャーを作る話です。シグネチャーはメソッドの引数の型オブジェクトを配列でまとめたものです。型オブジェクトという未定義の言葉が出てきたので、これから説明します。

型オブジェクトはRubyのクラスをWrapしたオブジェクトです。型オブジェクトはBOXING/UNBOXINGの2種類があり、Rubyのクラスと独立して設定できます。つまり、BOXINGなFixnumもUNBOXINGなArrayなんてのも表現可能です。それぞれの型オブジェクトは、次のようなメソッドを持っていて、コード生成時にあんまり型による場合分けとかせずに、型推論の結果による最適化が出来るようになっています。

1. gen_boxing (BOX化するアセンブラコードを生成する)
2. gen_unboxing (UNBOX化するアセンブラコードを生成する)
3. gen_copy (そのクラスのデータをコピーするコードを生成する)

例えば、FIXNUMによる足し算(c=a + b)は

atype.gen_unboxing(a)
btype.gen_unboxing(b)
c = a + b　　# a + b はUNBOXのFixnumでのみ正しく計算できる
ctype.gen_boxing(c)

みたいな感じで定義しておけば、a, b, cの推論結果によって勝手にBOXING/UNBOXINGのコードを入れたり入れなかったりしてくれるわけです。細かい実装は型オブジェクトについてはytljitのコードのlib/ytljit 中のvm_type.rbを、gen_*についてはvm_type_gen.rbを見てみてください。

型オブジェクトの説明が終わって、次にシグネチャに非常に関連のある型推論contextについて説明します。

ノード(ytljit内部VMの命令の単位)毎に推論メソッド(collect_candidate_type)が定義してあり、型推論はこれを呼び出すことで行います。あるノードの推論メソッド中に別のノードの推論メソッドを呼び出して、その結果を使って自分の推論を行うとかやっています。このような構造になっているとどうしても型推論処理全体で参照できる変数が欲しくなります。このような変数をグローバル変数でとっても良いわけですが、嫌だったので型推論contextというオブジェクトにまとめて、引数として渡すようにしました。また、推論メソッドでは必ず型推論contextを返すようにして、ある推論メソッド中で書き換えるとその情報がその後のノードにも伝わるようになっています。

なお、このような構造は型推論だけではなく、プログラムの構造解析やコード生成もそうなっています。contextとせず、わざわざ型推論contextとしたのはコード生成contextとかもあるからです。

さて、この型推論contextにはこのようなインスタンス変数があります。

1. @top_node 　　 　　　　　　　一番元となるノード
2. @visit_top_node 　　　　　　　クラス・メソッド・ブロックの一番先頭のノードのうち、型推論が行われた物が入る。同じ推論を何度も繰り返さないためのもの
3. @convergent 　　　　　　　 推論が収束したか。型推論が終わってもこれがfalseならもう１度推論を繰り返す。
4. @current_method_signature_node 現在推論中のノードのメソッド・ブロックの引数のノードの配列
5. @current_method　　　　　　　　 現在推論中のノードのメソッド・ブロックの先頭のノードの配列

最後の２つがシグネチャと大きく関係します。

ちょっと長くなってきたのでここで中断します。

続く　(といいなー)