JIT コンパイルが再帰して困った

Books

Mona Wiki

Mona OS

2010/01/08

mosh

JIT コンパイラが Scheme で書かれているので、JIT コンパイラ自身も JIT コンパイルされる可能性があることに気付いた。そうすると

手続き A を JIT コンパイルしようとする。
JIT コンパイラ中の手続き B が閾値を超えて call される。
手続き B を JIT コンパイルしようとする。
JIT コンパイラ中の手続き B が閾値を超えて call される。
手続き B を JIT コンパイルしようとする。

と繰り返されてしまう。同じ手続き B が再帰的に何回も JIT コンパイルされるのが問題なので、手続き B にコンパイル中フラグをつければ良いかと思ったがそうも行かない。

例えば以下のような場合を考えれば分かる。

(define (jit-compile x)
  ...
  ...
  (map (lambda (x) (+ x 2)) lst)
  ...)

手続き B が (lambda (x) (+ x 2)) だとすると jit-compile の呼び出し毎に、新しい手続きがアロケーションされるので、ソースコード上は同じ手続きでも実行時には別の手続きなのだ。(コンパイラが賢ければ、(lambda (x) (+ x 2)) を静的にくくりだす事も可能だがそれはまた別の話なので置いておく)

上記のような事情から、JIT コンパイラは再帰的に起動しない。グローバルで JIT コンパイル中フラグを持つ。という方針にしようかと思う。ただし欠点があって良く呼ばれるであろう JIT コンパイラ自身が JIT の恩恵を受けられない。

もっと良い方法はないだろうか。

Permalink | コメント(8) | トラックバック(0) | 23:49

コメントを書く

shiro 2010/01/09 04:48 ブートストラップ問題の一種のような感じですね。閾値を越えたら自動JITというのをオフにして、指定した手続きだけJITするモードをつけといて、最初にJITに突入した時にJITコード自身をそのモードでJITしてしまう、とか?

(define (jit-entry fn)
(cond [(jitted? jit-entry) ; まだ自分自身をJITしてなかったら
(parameterize ([auto-jit-mode #f]) ; 自動JIT off
(jit-entry jit-entry) ; 自分自身を強制JIT
)
(jit-entry fn)] ; 改めてリクエストされた関数をJIT
[else ... 実際のJIT処理...]))

jitted?な条件判断が入るのが嫌なら、こういうケースだけJIT時にこのスタブを取り除いちゃうような特殊パスを設けるって方法もあるかも。

それと、JITの対象を「手続きオブジェクト自体」ではなくて「手続きのコード部分」に限れば (「手続きオブジェクト」＝「手続きのコード部分」＋「環境」)、lambdaの評価時に毎回新しい手続きがアロケートされようとも、コード部分は共通なんで関係ないんじゃないかと思うんですが、環境もひっくるめた最適化をやってるんでしょうか。つまり (lambda (x) (map (lambda (y) (+ x y)) big-list)) で、x=1で呼ばれたら(lambda (y) (+ x y)) は (lambda (y) (+ 1 y)) としてJITコンパイルする、とか。これはこれで強力そうですが、こうやってるとしたらJIT自身のJITの時だけは環境をあきらめてコード部分だけJITする、というモードにするって手もありそうですね。

インドリ 2010/01/09 08:41 .NETの場合は、メソッドテーブルのアドレスをJITにより書き換えるので、
同じメソッドが呼ばれた場合には同じ2度目以降はコンパイルされないのでループしないようです。
つまり、仮想マシンの関数の呼び出しが管理されていれば、再帰してもループする事はないと思います。

1. 手続き A を JIT コンパイルしようとする。
コンパイル済みメモリ領域を確保して、手続きAの新しい関数アドレスを変更する。
2. JIT コンパイラ中の手続き B が閾値を超えて call される。
3. 手続き B を JIT コンパイルしようとする。
コンパイル済みメモリ領域を確保して、手続きBの関数アドレスを変更する。
4. JIT コンパイラ中の手続き B が閾値を超えて call される。
手続きBの新しい関数アドレスをコールする。
5. 手続き B を JIT コンパイルしようとする。×
既にJITされた関数なのでコンパイルしない。

と言う事になるのではないでしょうか？
ただし、JITコンパイルされた関数か否かは管理する必要がありますし、
この方法は関数アドレスを設定する時の難しさは伴うと思われます。

shiro 2010/01/09 10:16 いや、moshでもJITコンパイルは対象関数のコードを置き換えてると思いますよ。ただ「対象関数」というのがクロージャである場合、コード上は同じ手続きBであってもクロージャの実体が違うって話ですよね。

で、私のコメントの後半は、クロージャを対象にするのではなくてクロージャ＝コード+環境、のコード部分だけを対象にしたらいいんではないか、それなら共通だから、という話です。ただし、最適化の余地は減りますよ、と。

インドリ 2010/01/09 12:37 成程、クロージャも対象でしたか。それは盲点でした。
そうなれば、確かに対象を変える方がいいかもしれませんね。
クロージャの環境部分は本当にどうすればいいのだろう・・・
一般的に最適化は静的部分にするものだから、動的なものに対しては対象から外すのはスマートな方法だと思います。
これは全体的な話しなのですが、粒度を細かくすれば管理のコストも発生するし難しい話しですね。
コスト＜スピードにしなければならないので、ある程度粒度を大きくするのが良いかと。
お二人の話しは何時も勉強になります。

インドリ 2010/01/09 13:01 これは参考になるか分かりませんが、何らかの手がかりになるかもしれないので一応書きます。
.NETではラムダ式や無名関数は、コンパイラが勝手に名前を付けて関数として定義し、それを呼ぶ形式になっています。
なので、どうやらコード片を一つの関数として扱っているようです。

shiro 2010/01/09 13:35 まあ静的にわかる部分を最適化するのが「普通」ですね。ただここでは「実行時にn回以上呼ばれたら」みたいな実行時最適化を試みてるわけで、その時点で固定されてる環境情報を使っちゃうというのは静的最適化にはできない芸当で優れものだと思います。

インドリ 2010/01/09 17:43 私もそう思います。
.NETでは猫も杓子もJITするのに、Moshはn回以上呼ばれたら行う。
これは非常に高度な事だと思います。
私はJITの実装経験がないのでお力になれませんが、ひげぽんさんならば、
shiroさんが仰った

> (lambda (x) (map (lambda (y) (+ x y)) big-list)) で、x=1で呼ばれたら(lambda (y) (+ x y)) は (lambda (y) (+ 1 y)) としてJITコンパイルする

これが実現できるのではないかと思ってワクワクしております。
もし何らかの事情で出来ないにしても、ひげぽんさならば理論的で納得できる答えを出してくれそうです。
私も早く学習してJITがある本格的なコンパイラ作りたい。
学習のモチベーションになるので、この日記がある事を感謝しております。

higepon 2010/01/09 18:22 > shiro さん

> 最初にJITに突入した時にJITコード自身をそのモードでJITしてしまう、とか?

なるほど。現状の jit コンパイラは Scheme 手続きをコンパイルするだけで、その手続きに中に含まれ、動的に生成される手続きをコンパイル出来ないという制限があります。
多分 jit コンパイラよりも jit コンパイラが頻繁に呼び出される手続きが jit コンパイルされる方がうれしいってのが問題ですね。

と書いていて思ったんですが、jit コンパイル対象をマークして queue に入れておけばよい気がしてきました。
ただ無駄に複雑になるのがバランスが難しいところです。

> 環境もひっくるめた最適化をやってるんでしょうか。

やってないです。コード部分というのはスマートで良さそうです。ただちょっと変更が大きくなってしまいそうなので手を出しづらいところではあります。

> インドリさん

shiro さんのおっしゃる通り「いや、moshでもJITコンパイルは対象関数のコードを置き換えています」。