SASADA Koichi <ko1 atdot.net> writes:

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

dynamic SCにおいて，ある基本ブロックを統合してsuperinstructionを作った
とします．

このとき，各stack state S1, ..., Sn に対応するnative codeを作る必要が
あります(実行時までstack stateは分からないから)．

しかし，static SCだと，1つの基本ブロックに対して作るnative codeのイン
スタンスは1個ですみます．

> 3.2 using state transition

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

> * Another opportunity... からの段落
> 
> 　ここで何を言っているのかわからない。
> 
> 　T(Sx->Sy) を、スタックキャッシュの状態を Sx から Sy にする命令とする。
> 
> 　S2 （2つキャッシュ）での iadd （S2_iadd）があれば、
> 
>     T(S1->S2) + S2_iadd または
>     T(S0->S2) + S2_iadd があればよい。
> 
> 　という話なんでしょうか。しかし、それは前の * の話とあまり変わんないよ
> うな。そうでもないかな。

前の*の話の特殊例といえるかも知れません．
もともと「状態遷移+基本命令」の形をしている場合．

上のYARVのアプローチとまさに逆ですよね．
 
> 　これを一般化して、
> 
>   n 個の値をスタックから取ってくる命令 I があった場合、n 未満のキャッ
> シュ状態の命令を生成する必要は無い（T(Sx -> Sn) を前にくっつければよい）
> ということか。（3.2 下から3段落目）

そういうことですね．

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

同様に，
「レジスタが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--] という操作？

Figure 2を見ると，まさにそういうことですよね．

> 3.3 Optimal code generation
> 
> 　で、通常命令列をスタックキャッシュ命令列に変換する話が出てるんだけど、
> コスト最小のパスを最短経路問題にして求めればよい、と言っている。
> 
> 　で、T(S2 -> S1) のコストと、T(S2 -> S0) のコストを同様（3）に見積もっ
> ているのがわからない。スタックに2個乗っけるか、1個乗っけるかはコストが違
> うと思うんだけど。

これは単なる例で，実際にはnative codeの長さをコストとして使うのでは．

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

x86の命令長が，メモリアクセスについてはレジスタアクセスより長かったか
らでは．

				前田敦司

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