miura1729の日記

yarv2llvmを作り直した場合について気をつけること

22:14 |

なんか、yarv2llvmのデバッグがはまってきたので作り直す場合に同じ失敗を繰り返さないようにするためのメモ。思い出したら順次書いておきます。

• add_same_typeによる型の関連づけ → ユニフケーション のサイクルは複数回繰り返さなければならない場合がある。例えば、レシーバーのクラスが決まらないので、メソッドが決まらないといった場合でも一度、add_same_typeによる型の関連づけ → ユニフケーション のサイクルをまわすと決められる場合がある。このような場合、決まったレシーバから型推論が進められる。このように、不定回の型推論のサイクルに耐えられるようにプログラムの構造を作るべきだし、型推論の停止判定のアルゴリズムもちゃんと考慮すべきである。現在は、３回繰り返すとかad-hocなことをしている。

• ユニフケーションは思ったよりたくさん行い、コンパイル時間増大の主原因になる。効率よくユニフケーションが出来るように考えるべきである。Prologのコードとかを研究すべき。

• if/whileなどの制御構造の実現が実は一番難しい。これらの構造は値を持つけど、その値の管理方法をきちんと考えておかないとはまる。さらに、PHI命令を生成する方法もちゃんと考慮しておくこと。当然、これらの値も型推論の対象だし、PHI命令は同じ型じゃないとエラーになる。さらに、if文はelse節を省略するのがほとんどなのでたいてい型が矛盾する。YARVの生成するラベルだけでは荒い(例えば、branchif/branchunless/jump命令の後にはラベルが必要)のでLLVMに落とせるようにラベル付けを行う必要がある。このラベル生成のアルゴリズムもちゃんと考慮しておく必要がある。

• 型オブジェクトはかなり柔軟性を持たせる必要がある。例えば、String#packなどの型推論を行うことを考えると、メソッド毎にフックがつけられるようにすべきである。また、出来ればメソッド定義ではなくメソッド呼出し毎に型付けを行ったほうがうまく行くと思う。ただし、メソッド呼出し毎に違うメソッドが定義されてメモリがたくさん必要になる場合がある。もちろん、同じ型のメソッドはちゃんと１つにまとめる仕組みがひつようになる。

• 型が決まっていない状態とNilClassで決まった状態とSelfを使うことをnilで省略している場合(関数型メソッド)をちゃんと区別できるようにすること。特にメソッドテーブルについては解析途中でレシーバの型が決まった場合の対処方法を検討しておくこと。レシーバの型が決まった後に型が未定義なものとしてテーブルの検索がありえるか。

• ブロック/selfを引数で渡す場合・渡さない場合をちゃんと考えること。ブロックを渡しても渡さなくてもいいメソッドの扱い方もちゃんと考えておくこと。

• Rubyでは引数の数が異なる場合は引数の型・戻り値の型が全然異なる場合が多い。そのため、引数の数、オプショナルか等の情報をメソッドテーブルに持たせるかメソッド名にエンコードして、別々のメソッドとして扱うようにする。

• opt_*命令は使わないようにコンパイルする。結局、ユーザ定義のメソッドを呼び出さないといけないとsend命令の処理を繰り返す必要があるのでopt_*はInline Methodとして扱うようにする。

• yarv2llvmではトップレベルの環境で定義したメソッドはselfを渡さないようにしている。このことで、第２のキラーアプリ(第1はaoベンチ)のfibのスピードアップに貢献しているが、いかんせんプログラムが複雑になる。このあたりは、継承しつつシンプルなコードになるようにする。このメソッドが動的メソッドディパッチに対象になる場合はselfを渡す必要があるので全体を一度見る必要がある。

• Rubyが持つ膨大な組み込みメソッドは出来ればyarv2llvm自身で書きたいが、そうするとコンパイル時間が爆発する。そうかといって、あらかじめコンパイルしておくことは型情報が得られない・引数の型によって生成するコードが違ってくる、といった理由でなかなか難しい。

• 配列等に適用するイテレータは要素に色々な型が入りうるのでなかなか難しい。型推論のアルゴリズムを検討するときは、Array#collectあたりがちゃんと動くことを念頭に入れるべきである。

• パスは2では足りない。こんな構造になるのではないか。

• requre/includeを展開する。パスが決まらないとかトップレベル以外のところにあるとかは後回し。多分、evalと同じ様にコンパイルする必要がある。ただし、静的に解決できるif文はこの時点で展開しておく。

• 全体を見て、使われているメソッド、グローバル変数、マクロ等の一覧を作る。組み込みメソッドが再定義されている場合はどこから再定義されているかを記録しておく。トップレベル以外のところで再定義されている場合はとりあえずは考えない。ここの時点でメソッドにブロック・selfを渡す必要があるのかなどをメソッド定義のレベルの決定事項を決定しておく。メソッド呼び出しはレシーバーの型推論を行っていないので何も決定できない。

• 全体を見て、変数・メソッド・リテラル等に同じ型のリンクを張る。ここはyarv2llvmの1パス目とほぼ同じ。リンクを張ったとき張っった場所を記録しておくこと。

• 一旦、リンクを張ったら全体の型を決定する。簡単な場合はこれで全部の型が決定できるが、普通はこれだけでは決定できない。まだ、決定できない情報が残っている場合は、リンク張り -> 決定を繰り返す。例えばa[0] = 1とした場合、aが配列ならaの要素は整数というリンクが張れるが、整数の場合は何のリンクも張れない。aが配列か整数かどうかは即座にわからない場合がある。

• 決定した型情報を元にllvmコードに落とす。この部分はllvmのapiを直に呼ぶのではなく、１つレイアをかます。

• 生成したコードを実行する。コンパイルしたコードをセーブできるようにするか？すると、少しパフォーマンスが落ちるのでうーん。