Scheme処理系 Gauche の最適化まとめ前編
shiro さんが開発されている Scheme 処理系 Gauche 0.8.12 の最適化処理を勉強のためにまとめました。
よく Gauche のコードは宝の山だと聞きますが、その一端を分かってもらえるとうれしいです。
基本的にGaucheのコードのコメントをまとめただけです。
Scheme のソースコードと簡単な英語が読める人はこのまとめを読むより src/compile.scm を直接読んだ方が正確に理解できると思います。
前提1 コンパイルと実行の流れ
Gauche はスタックマシン型の仮想マシンでコードを実行します。
そのため Scheme のコードはスタックマシンで実行可能なコードにコンパイルされます。
つまり
という流れでコードが実行されることになります。
今回取り上げる、最適化は上の流れの「コンパイル」の時に行われるものです。
さらに実は「コンパイル」は3工程に分かれていて（これを3 passという）、最適化は2番目の工程（Pass 2）にあたります。
ちなみに各工程で行われているのは（compile.scmのコメントそのまんまですが）
- Pass 1 (パース):
- Pass 2 (最適化):
のようになっています。
前提2 IForm
Gache の最適化は入力が IForm で出力も IForm です。
なので軽く IForm の事を理解しておいた方がよいでしょう。特に難しいことはありません。
元のコードにほんの少し付加情報をくっつけたものです。例を見てみましょう。
(let ([a 0] [b 1]) (let ([c 2]) (+ a b c)))
この Scheme のコードを IForm に変換すると以下のようになります。
($let ((a[1;0] ($const 0)) (b[1;0] ($const 1)) ) ($let ((c[1;0] ($const 2)) ) ($asm (NUMADD2) ($asm (NUMADD2) ($lref a[1;0]) ($lref b[1;0])) ($lref c[1;0]))))
そんなに違いはありませんね。
let は $let に、定数は $const というタグ付きになっています。
$lref はローカル変数参照です。
また加算は NUMADD2 という2引数の単純な加算の組み合わせとして展開されています。
なお定数が $const というタグ付きになっているのは最適化の時にとても役立ちます。
他に IForm には実装上の特性もあります。Schemeのコードがリストなのに対して IForm はベクタになっています。これによりトラバース時に各要素へのアクセスが高速かつ容易になります。
また $let などのタグは整数定数なので、各タグに対する処理の分岐時に有効利用できます。（タグをベクタのインデックスとして使うとか）
最適化
前置きが長くなりましたが最適化を見ていきます。
ローカル変数参照最適化
まずはローカル変数参照 $lref の最適化から。
ローカル変数参照をその初期値と置き換えられるかをチェックします。
もしその変数が set! （代入）されない事が分かっている場合、初期値が $const であればそのまま初期値に置き換えることができます。
(let ([a 1)]) (+ 1 a))
のような場合、(+ 1 a) は a の値が set! で変わることはないので (+ 1 1) としても良いですね。
また初期値が $lref であり、その変数が set! されることがなければ置き換えることもできます。例を見ましょう。
(let ([a 3]) (let ([b a]) (+ 1 b)))
このとき a は set! されないことが分かっているので b は a の初期値で置き換えることが出来ます
つまり以下のようになります。
(let ([a 3]) (let ([b 3]) (+ 1 3)))
これを繰り返すと使われない let が出てきますね！。
if の最適化
続いて if の最適化。これはちょっと難しいです。
if は
if test then else
という形が基本ですが、then または else で test の結果をそのまま使うような場合があります。
例えば
(let ([a (func xxx)]) (if a a hoge))
のような場合です。（分かりづらいかな？ aif が分かっている人には it のことと説明すれば分かってもらえると思います）
で、この test の評価結果の参照を $it と IForm では表現します。
最適化の条件ですが、if の test 部分に if があり、さらに then か else で $it を参照している場合に余計なコード生成を防ぎます。
compile.scm にのっているサンプルそのままですが
($if ($if <t0> ($it) <e0>) <then> <else>) -- (A) => ($if <t0> #0=($label L0 <then>) ($if <e0> #0# <else>)) -- (B)
(A) のように if が入れ子になっていると通常 4通りの分岐先がありますが、else に $it があるので実は分岐先は3通りと1つ減ります。
このようなパターンで無駄なコードを吐かないようにするのがこの最適化です。
let の最適化
前述のローカル変数参照の最適化を行うと、不要な let が出てくる場合がありました。
その場合、let を削除して let の body を $seq （beginのようなもの）にまとめることができます。
この let の削除はとても効果があり、スタックへの変数の push や let を出るときの後始末などが不要になります。
さてクロージャとCallの最適化がまだ残っているのですが疲れたので今日はここまで。
間違いがあったらごめんなさい。
