仮想レジスタを持つスタックマシンではA正規形は不利？ - Scheme VM を書く
さてあれこれ考える時間です。少ない脳みそをこねましょう。
A正規形にすると let が増え、bind が増え速度的に不利になるかもしれないという話です。
A正規形のパターンごとに考える
A正規形では登場人物が限定されます。これを利用しうまく解析すれば、コンパイル時に let を減らせないでしょうか。
例えば
(let (x V) M) (bind)
Vは値。instruction としては CONSTANT か CLOSURE が該当する。
これらの命令は結果を accumulator に置く。その後 x に bind して M を実行というのが通常の流れ。
仮に M が (func x) だとすれば、bind は必要なくて accumulator の値を PUSH 、APPLY ですむ。
こういうパターンをうまくコンパイルできれば良い。
逆に、bind が必要な場合を考えてみよう。
M が (let (y 0) (+ x y)) だとすると。
(let (x V) (let (y 0) (+ x y)))
となる。
この場合は (let (y 0) ...) の右辺が 0 で x を参照していないから bind を省略できるのか。
擬似コード CONSTANT V, PUSH, CONSTANT 0, NUM_ADD となる。
うーん。ちょっと A正規形のパターンごとに考えるのは複雑かな。一休みしよう。
Gauche のスタックフレームに学ぶ
A正規化で let が増加することは許容する。そのかわり最大限スタックフレーム周りを高速化するのはどうだろうか。
Gauche の実装を見て比較する。
まずは let1 (bind) のフレームをみてみよう。
disasm すると LOCAL-ENV がフレーム作成であることが分かる。
gosh> (disasm (lambda () (let1 x z (+ x y)))) main_code (name=#f, code=0x8158de0, size=8, const=3, stack=9): args: #f 0 GREF-PUSH #<identifier user#z>; z 2 LOCAL-ENV(1) ; (let ((x z)) (+ x y)) 3 LREF0-PUSH-GREF #<identifier user#y>; y 5 PUSH-GREF-TAIL-CALL(2) #<identifier user#+>; (+ x y) 7 RET
CASE(SCM_VM_LOCAL_ENV) {
CHECK_STACK_PARANOIA(ENV_SIZE(0));
FINISH_ENV(SCM_FALSE, ENV);
NEXT;
}
CHECK_STACK_PARANOIA は無視して良い。
/* push environment header to finish the environment frame. env, sp, argp is updated. */ #define FINISH_ENV(info_, up_) \ do { \ ScmEnvFrame *e__ = (ScmEnvFrame*)SP; \ e__->up = up_; \ e__->info = info_; \ e__->size = SP - ARGP; \ SP += ENV_HDR_SIZE; \ ARGP = SP; \ ENV = e__; \ } while (0) /* * Environment frame * * : : * +--------+ * | size=N | * | info | * |...up...|<--- ScmEnvFrame* envp * |arg[N-1]| * |arg[N-2]| * : : * | arg[0] | * +--------+ * : : */ typedef struct ScmEnvFrameRec { struct ScmEnvFrameRec *up; /* static link */ ScmObj info; /* reserved */ ScmWord size; /* size of the frame (excluding header) */ } ScmEnvFrame;
SP は vm->sp、ENV は vm->env 。
FINISH_ENV はちと名前に惑わされそうになるのだけど、スタックトップにフレームを作成する。
作成したフレームにあわせて sp, argp, env などを更新している。
フレームに積まれた、arg[] は env ポインタからのオフセットでアクセスできる。
env から引数がアクセス可能ならば、argp は何に使われるだろうか。
ScmObj *argp; /* Current argument pointer. Points
to the incomplete environment frame
being accumulated. This is a part of
continuation. */
どこまで引数を積んだかを保持しているっぽい。
スタックフレーム破棄タイミングを見てみよう。
gosh> (disasm (lambda () (let1 a b (let1 c d (+ a c)) a))) main_code (name=#f, code=0x80f9d58, size=14, const=3, stack=19): args: #f 0 GREF-PUSH #<identifier user#b>; b 2 LOCAL-ENV(1) ; (let ((a b)) (let1 c d (+ a c)) a) 3 GREF-PUSH #<identifier user#d>; d 5 LOCAL-ENV(1) ; (let ((c d)) (+ a c)) 6 PRE-CALL(2) 11 8 LREF10-PUSH ; a 9 LREF0-PUSH-GREF-CALL(2) #<identifier user#+>; (+ a c) 11 POP-LOCAL-ENV 12 LREF0 ; a 13 RET
POP-LOCAL-ENV を見てみましょう。
CASE(SCM_VM_POP_LOCAL_ENV) {
ENV = ENV->up;
NEXT;
}
一つ上のフレームに上がるだけ。
ふむ。元々Gaucheのフレームを参考にさせていただいているのでこのあたりに大きな違いはない。
考える
(+ (+ a b) c) のA正規形の変換前後での実行コストをまじめに考えよう。以下擬似コードなので注意。
仮想レジスタ(accumulator)が1つあることを前提にしています。
変換前
(+ (+ a b) c) => ref a push ref b add push ref c add
変換後
(let1 t (+ a b) (+ t c)) => ref a push ref b add push enter lref t push ref c add leave
増えたのは enter/lref/leave の3つ。
うーん。変換後の方が明らかに遅くなるよなあ。
Gauche の IForm
Gauche の IForm において上記の例はどのように表現されるだろうか？。もし bind で表現されているようであれば、後続の処理が参考になるかもしれない。
src/compile.scm の compile 手続きで pass1 の結果を出力する様にGaucheに直接手を入れた。
その結果以下のようになった。
#(14 (+ (+ a b) c) (149) (#(14 (+ a b) (149) (#(3 #<identifier user#a>) #(3 #<identifier user#b>))) #(3 #<identifier user#c>)))
定数の意味を調べて当てはめ、デバッグ用のソースコード情報を除くと以下のようになる。（あとから考えたら pp-iform を使って pretty print すれば良かった。)
#($ASM (NUMADD2) (#($ASM (NUMADD2) (#($GREF a) #($GREF b)))) #($GREF c))
あら bind になってないですね。やっぱりそうだよなあ。
オペレータ適用ではなく、手続き呼び出しではどうだろうか？
(func (func a b) c) => #($CALL #($GREF func) (#($CALL #($GREF func) (#($GREF a) #($GREF b)) #f ()) #($GREF c)) #f ())
計算の途中経過に一時変数を割り当てるといったことは pass1 ではやってないみたい。
