Inside yarv2llvm(その2) - miura1729の日記

yarv2llvmは2パスです。Rubyの言語仕様では1パスで実現することが可能です(と思います、ちょっと自信ないです)が、型推論で後に来る情報も利用したいので２パスにしています。2パスにしてうれしい例を挙げます。

  def foo(a)
     a
  end

  foo 1

ここで、fooを定義したところだけだと、aの型は決められません。関数型言語だと型変数が出てきて

  foo: 'a -> 'a

とか型推論するのでしょうが、その情報ではllvmに落とすのには役に立たないです。そこで、プログラムの全体を見回して、fooがどう使われているか調べています。この例では、foo 1という使い方からfoo: Fixnum -> Fixnumと推論します。これだと、Fixnum(llvmではInt32TyかInt64Ty)の命令を生成すればいいことがわかります。こういうことで、全体を見回して型が決定するまで、fooの命令が生成できないことがわかります。

1パス目は、yarv2llvmの命令をトラバースして処理結果をllvmのbitコードを生成する関数(Procオブジェクト)の形で出力します。2パス目はその関数を単に呼び出します。つまり、普通、木構造で表現されるであろう解析結果が関数で表現されています。こうすることで、効率のいいコンパイルが実現できます。また、木構造のノードがクロージャに対応するわけですが、ノードに比べて何かと融通が効くので効率よくプログラムが書けます。ただし、自由度が高いのでちょっと気を抜くとすぐ訳がわからなくなります。

例として、1 + 1をみてみます。とりあえず、コンパイラの流れだけなの型推論の話は無視します。
こんな感じのYARVコードになります。

  putobject 1
  putobject 1
  opt_plus

第1回で書いたとおり、@expstackをコンパイル時にYARVのスタックの代わりに使います。2つのputobject 1はそれぞれ1を@expstackにpushします。ただし、ただの1では無く

  lambda {|b, context|
     1.llvm
  }

という形でpushします。lambdaの２つの引数はまた後で説明します。llvmrubyではllvmメソッドを呼び出すとそのレシーバーのllvm表現を返します。
次にopt_plusでは、@expstackから2つのデータをpopして、その結果を足す関数を生成して、それを@expstackにpushします。こんな感じです。

  a1 = @expstack.pop
  a0 = @expstack.pop
  @expstack.push lambda {|b, context|
    val1 = a1.call(b, context)
    val0 = a0.call(b, context)
    b.add(val1, val0)
  }

こんな感じで、関数をつなげていって最後にcallすると芋づる式にコードが出てきます。
単に遅延評価するために関数を生成しているのではなく、関数を生成しながら色々な情報を蓄えておいて2パス目でcallするときに参照するようにしています。色々な情報を蓄えますが、一番顕著なのは型情報でしょう。次回は型推論の概要を説明したいと思います。

続く