はじめに

現在、mruby用のコンパイラを書こうとしていてその一環として、こんなものを作っています。永らく型推論器だと思っていたのですが、どうも型推論器には当たらないことが分かってきました。そこでここでは今作っているプログラムについて説明します。
基本的にやっていることはプログラム全体を走査して型情報を集めて表示する(またはそれを使ってコンパイルする)ということです。一言で行ってしまうと簡単ですが実際に実装しようとするとなかなか大変です。

まず型情報を集めると言ってもどこから元を集めればいいのでしょうか？命令列は簡単に得られますが、そのオペランドになっているレジスタに何が入っているかは自明ではありません。明らかにレジスタの内容が分かる定数のレジスタを元にレジスタの参照関係が扱いやすく整理されている必要があります。さらに、mrubyのVMではデータはレジスタにだけあるのではありません。インスタンス変数、グローバル変数、定数などもあります。こういったものの型も集めなければ全体の型情報は得られません。そのため、型情報を集めるための中間コードの設計がとても大事になります。この辺の話は中間コードの章で説明します。

集める型をどのような構造に入れるかも自明ではありません。たとえばRubyのカオスな型システムだとある時点でFixnumだと思ってたものが別の所だとStringだったとしても不思議ではありません。いろんな変な状況が現れても大丈夫な構造を用意する必要があります。
また、Rubyではメソッドの引数についてオーバーロードをゆるすというよりオーバーロードと言う言葉すら無意味なほど ガバガバ 自由度の高い言語なのでそのあたりを何とかする必要があります。このプログラムではTUP(Tuppleから)という概念を使ってそれを実現しています。これも重要な概念でしょう。

ここまで説明すると枠組みが出来上がりますので、ここの命令毎にルールを説明します。命令によっては色々ヒューリスティクなことをしているのでまあ説明する必要があるでしょう。

VMの命令のルールを説明して終わりなわけがありません。mrubyにはC(死んだはずなんだけどね)で書かれたメソッドがありこれら毎に型のルールを指定しないといけません。多くは自明なものですが中には複雑なルールもあります。

次に条件分岐の扱いです。普通は条件分岐は辿れるとこ全部を辿らればいいのですが、例えば、

  if !block.nil? then
     block.call(n)
  end

みたいなコードでblockがnilではcallは呼べないよ　というエラーは誰もが受け取りたくないでしょう。そういうわけである程度条件分岐の条件を見て適切な制御をしています。その説明も章を設けて行います。

とりあえずこんな感じの文章が出来るはずです。

中間コード

このプログラムではmrubyのバイトコード命令毎に入力から出力に型を伝搬していくのが主な動作になります。この時、入力と出力というのは自明ではありません。そういうとレジスタには番号が付いているから簡単では？と思われるかもしれませんが、同じレジスタの番号でも上書きされていれば別のレジスタとして扱わなければなりません。
昔作ったコンパイラの経験から条件分岐の処理は特に面倒になるため基本ブロックにきっちり分けて管理する必要性を感じました。
また、mrubyのJITの経験からレジスタ割り当てをおこなう場合はレジスタの生存期間が簡単にわかるようになっている必要があるという知見を得ました。

以上のことから中間コードはSSAベースが最適と言う結論になりました。ところが、mrubyのVMのバイトコードをSSAに変換すると言うのはなかなか煩雑なものです。考えた末、SSAと同等のコードが得られる方法を思いついたのでそれを実装しています。この方法ではコードはグラフになるためテキストにエンコードするのが煩雑になるという欠点があります。

mrubyのバイトコードをSSAに変換するには次のような手順で行います、
　　* バイトコードを分岐を含まない基本ブロックごとに分ける
　　* 同じ名前のレジスタでも代入ごとに別の名前を付けて区別できるようにする(単一代入化)
　　* 基本ブロック間でのレジスタのやり取りはどこのブロックからやってくるのか明示する(phi命令)

基本ブロックに分ける

バイトコードを分岐を含まない基本ブロックで分けるためには命令列(irep->iseq)について切れ目の位置を記録しておいて、その切れ目の位置で分ければよいわけです。切れ目の位置は次のようなところです。
　　* JMP/JMPIF/JMPNOT/RETURN/RESCUE などのpcが単純なインクリメントではない命令
　　* 上記命令の飛び先
　　* 命令列の終わり(最後は必ずRETURNで終わるので実質必要ない)

命令列を分けた後、命令の実行関係で基本ブロックごとにリンクを貼ります。RETURN/JMPなどは1本ですが、JMPIF/JMPNOTは2本(条件が真偽それぞれの飛び先)あります。

単一代入化

おそらく一番めんどくさい話。同じ名前のレジスタであっても途中で代入すると別の名前のレジスタとして扱わないといけないと言う話。SSAを知っている人以外は意味不明だと思うので、SSAの別の資料を見てください。学術的にはレジスタのリネームとか色々やりようがあるだろうけど、ここでは簡単で泥臭い方法を用いてます。

その方法とはレジスタをオブジェクトとして実体を用意してレジスタの代入のたびに新しいレジスタをアロケートするというものです。つまり、SSAで面倒くさいレジスタの名前付けがオブジェクトのアドレスで勝手にできてしまうわけです。しかも、型推論にはレジスタにいろいろな付加情報を加える必要がある(例えば型)のでレジスタをオブジェクトにするのはとても都合の良いことです。

中間コードを図にするとこんな感じになります。

命令オブジェクトは@OPに命令のオペコードがシンボルで入り、@inregが入力レジスタの配列、@outregが出力レジスターの配列です。ADD R2, 1, :+みたいな命令ではR2は入力レジスタであり、出力レジスタになるわけですが、別のレジスタとして取り扱います。出力レジスタは必ずその場でアロケートした(または、インスタンス変数みたいに別の場所に格納してある)レジスタになります。入力レジスタと出力レジスタは必ず分離することが大切です。前回のytljitでは入力レジスタと出力レジスタを区別しなかったばっかりにうまくいかなかった知見があります。

型表現

前章で説明した中間コードを辿って言ってレジスタオブジェクトの型を決めていきます。レジスタは2つのレベルで型の情報を持ちます。それぞれ@same, @typeというインスタンス変数に保持します。
@sameは自分(レジスタ)と同じ型を持つレジスタの集合を表します。@typeは実際に自分の型を保持します。

なぜ、@sameが必要でしょうか？確かに、後から説明するようにレジスタがもつ型情報を別のレジスタに拡散していく形で型の推定をおこなうわけですが、@sameを使わずに@typeに直接入れてもよさそうなのにって思われるかもしれません。しかし、それではうまくいかない場合があります。元になるレジスタも実は型が確定していなくて後から確定する場合もあるからです。そういう場合には、@sameに同じ型のレジスタだよって情報だけ覚えておいて、あとから@typeを更新します。

また、@sameは複数のレジスタを入れることが出来るので、必ずしも@sameに入っているレジスタと同じ型になるとは限りません。例えばif文でthen節とelse節が別の型を返した場合、ifの型はthen節とelse節と違うそれらのユニオンになります。

型オブジェクト

　型そのものは型オブジェクトという型を表現するオブジェクトを用意します。型オブジェクトが満たすべき条件は、同じ型は同じに違う型は違うと区別できることです。簡単そうですが、非常に難しくおそらく最後まで細かい条件づけの調整が続くと思われます。型オブジェクトは型を表現したものですが、さらに分類できそれぞれサブクラスになっています。

BasicType

PrimitiveType

LiteralType

ContainerType

ProcType

tup

Rubyは引数に型の制約を付けるという発想が無いため、メソッドの引数は必ず多相性を持ちます。同じメソッドでも別の型のオブジェクトを引数で渡すと全く別の動作をする可能性があります。つまり、違う引数の型で呼び出す場合は同じメソッドであっても違うメソッドとして取り扱うべきです。しかし、メソッドが同じか違うのかを区別する方法が必要になります。ナイーブな方法としてレジスタの型情報を引数の型の組と型のテーブルにするという方法が考えられます。これは、ytljitで使用したのですが、非常に効率が悪いです。そこで、引数の型の組にユニークな整数を割り当てそれをキーにするという方法を採用しました。この整数をTUP (Tupleより)とこのプログラムでは呼んでいます。

Array

Proc

Procはメソッドやブロックのオブジェクトです。irepと環境(mrubyのEnvオブジェクト)をwrapしています。Procオブジェクトで難しいのは2つのProcオブジェクトがあった場合の同一性です。一見、irepだけ見ればよさそうですが、それではうまくいかない場合があります。
例えば、

  def foo(&block)
    self.collect {|x| block.call(x)}
  end

のようなプログラムは {|x| block.call(x)} の部分のProcオブジェクトはirep(プログラムコード)だけだと常に同じになってしまいます。ここで、blockに例えばFixnumを返すProcオブジェクトとFloatを返すProcオブジェクトを渡しても同じ型になってしまうので、たとえばFixnum|Floatという型になってしまいます。

そこで、Procオブジェクトは持っている環境に閉じ込められている変数の型も同一性を判定するのに用いるようにしています。こうすると、blockは{|x| block.call(x)}の環境に閉じ込められている変数ですので、blockの型によって別々のProcオブジェクトとして扱うことが出来ます。

インストラクションのルール例

LOADNIL

MOVE

SEND

組み込みメソッドのルール例

Array#[]

条件分岐の扱い