ささだです。

M. Anton Ertl, et al. Combining Stack Caching with Dynamic
Superinstructions SIGPLAN 2004 Workshop on Interpreters, Virtual
Machines, and Emulators (IVME ’04) Proceedings, pages 7-14

http://www.csc.uvic.ca/~csc586a/papers/ertlgregg04ivme.pdf


を読んでいるんですが、どうにもわからない点がいくつか。

　以下、stack caching を SC と略します。

3.1 static or dynamic stack caching

　dynamic SC はコード量が多くなるから駄目だ！（I-Cache miss とか増える
し）　って言ってるんだけど、dynamic superinstructions はそもそも膨大な量
のコードを生成すると思うんですが。


3.2 using state transition

　ここでは生成する命令数を使う工夫について述べている。

* 生成する命令数を減らすため、使用頻度の低い命令は各状態について作るん
じゃなくて、状態遷移＋基本命令で使う。これは納得。dynamic
superinstructions だから、状態遷移命令のディスパッチオーバーヘッドも要ら
ない。賢い。

　これについては、YARV では利用頻度の低い命令をひとつの命令にまとめて、
その中でもう一段ディスパッチ（こっちは switch/case ですが）しようと思っ
ています。まだやってないですけど。これによって、随分命令数が減るはず。
（このディスパッチも高速化するべきなのかなぁ。ダブルディスパッチとか言っ
て...意味が違う）

　YARV では、命令開始時にスタックから取ってくる値を "..." と指定すること
で、スタックキャッシュの状態を全部フラッシュ、つまりレジスタに値が乗って
いた場合、スタックに全部書き戻すということをやります。利用頻度の低い命令
（たとえばクラス・メソッド定義命令）をこんなふうに作る予定。

* Another opportunity... からの段落

　ここで何を言っているのかわからない。

　T(Sx->Sy) を、スタックキャッシュの状態を Sx から Sy にする命令とする。

　S2 （2つキャッシュ）での iadd （S2_iadd）があれば、

    T(S1->S2) + S2_iadd または
    T(S0->S2) + S2_iadd があればよい。

　という話なんでしょうか。しかし、それは前の * の話とあまり変わんないよ
うな。そうでもないかな。

　これを一般化して、

  n 個の値をスタックから取ってくる命令 I があった場合、n 未満のキャッ
シュ状態の命令を生成する必要は無い（T(Sx -> Sn) を前にくっつければよい）
ということか。（3.2 下から3段落目）

　で、次の段落の「スタックから何も取ってこないで、n 個後で乗っける命令」
についての話がわからない。なんで n レジスタ未満でスタートする場合の操作
が必要ないんだろう。


　なにやら、私はここで言っているスタックキャッシュの状態遷移について誤解
しているかもしれない。

　レジスタが2個、a, b とあったとき、状態を縦、レジスタの利用状況を横とし
て、表にすると、

    a     b
S0  x
S1  1st   x
S2  2nd   1st

　こんなのを想定している？　つまり、S2 -> S1 への状態遷移は a = b という
操作、S1 から S2 への状態遷移は b = a; a = stack[sp--] という操作？


3.3 Optimal code generation

　で、通常命令列をスタックキャッシュ命令列に変換する話が出てるんだけど、
コスト最小のパスを最短経路問題にして求めればよい、と言っている。

　で、T(S2 -> S1) のコストと、T(S2 -> S0) のコストを同様（3）に見積もっ
ているのがわからない。スタックに2個乗っけるか、1個乗っけるかはコストが違
うと思うんだけど。

　それとも、ここでは命令実行のコストは考えないで、1命令一律 3 というコス
トとして見積もっているのかな。それなら納得。

　しかし、3というコストはどこから来たんだ。

　あと、注釈5として、3レジスタキャッシュでひとつの値がローカル変数にあ
たった場合、そのコストを考慮して 3 番目のレジスタキャッシュは行わなかっ
た、と書いてるんだけど、その場合 S2->S3 の遷移コストを上げて計算したって
ことなのかなぁ。

-- 
// SASADA Koichi at atdot dot net
//


--
ML: yarv-dev quickml.atdot.net
使い方: http://www.atdot.net/~ko1/quickml