続 Gauche の $if の最適化 - Scheme VM を書く

昨日の説明は分かりづらかったので擬似バイトコードで説明しよう。

(if (if test1 then1 else1) then0 else0)

のコードは

test1 branch then1 jmp[A] else1 label[A] branch then0 jmp[B] else label[B]

とコンパイルされます。
branch は直前の評価結果で分岐する命令です。

これの特殊型として then1 が it のもの

(if (if test1 it else1) then0 else0)

は同じようにコンパイルされます。

test1 branch it jmp[A] else1 label[A] branch then0 jmp[B] else0 label[B]

よーく眺めていると branch の直後に it がある場合、test1 の評価結果である it は必ず #t であることが分かります。
つまりこう書けます。

test1 branch #t jmp[A] else1 label[A] branch then0 jmp[B] else0 label[B]

するとさらに jmp[A] 後の branch の結果も明らかに then0 に飛びます。

test1 branch then0 jmp[B] else1 branch then0 jmp[B] else0 label[B]

と短くできます。 then0 が2箇所でてくるのでどちらかはラベルにして jmp することを考えると

test1 branch jmp[A] else1 branch [A] then0 jmp[B] else0 [B]

のようになります。
つまり test1 が #t のときには it branch の分だけ実行命令数が減ります。

同様に

(if (if test1 then1 it) then0 else0)
=>
test1 branch then1 jmp[A] it label[A] branch then0 jmp[B] else0 label[B]
=>
test1 branch then1 jmp[A] #f label[A] branch then0 jmp[B] else0 label[B]
=>
test1 branch then1 jmp[A] jmp[C] label[A] branch then0 jmp[B] label[C] else0 label[B]

となります。