Scheme処理系 Gauche の最適化まとめ後編
昨日の続きです。クロージャとcallの最適化。
クロージャは lambda、call は手続きの呼び出しのことです。
((lambda (...) ...) arg ...)
呼び出される手続きが、lambda 式の場合。この呼び出し自体を let に変換する事が出来ます。
($call ($lambda .. (LVar ...) Body) Arg ...) => ($let (LVar ...) (Arg ...) Body)
この lambda がここでしか使われていないことが文脈的に保証されていることが重要です。（ということが後の方のクロージャ最適化を見ると分かります。）
ちなみにこの変換が意味をなすのは
クロージャ生成コスト + call のコスト > let のコスト
クロージャ最適化
クロージャ最適化の手前の時点で、静的に束縛されているクロージャがどこで呼び出されているかということが判明しています。
その情報を使い最適化することになります。
ちなみにクロージャ最適化とは、「クロージャ作成と呼び出しコストが高いのでできるだけクロージャを作らないようにすること」だと思われます。
ある変数に束縛されたクロージャを A としてそれがインライン展開可能かを見ていきます。
インライン展開可能になるには、以下の4つの条件を満たしている必要があります。
1. A が "leak out" していないこと
A が call されている部分以外に、Aが参照されていないことが1つ目の条件です。つまり (A ...) というような手続き呼び出しの位置のみで A が参照されていることが求められます。
もしも (set! hoge A) とか (func A) のように他の場所に A の内容が漏れている("leak out")場合、クロージャの生成が避けられないのでインライン展開不可となります。
Aの参照カウントと A の call位置の個数を比較することで、この条件を満たしているか調べられます。
2. A が非末尾位置で自己再帰していないこと
非末尾位置で自己再帰している場合はインライン展開できません。
そもそも自己再帰している場合、body をいくら展開しても自分自身が出てくるので展開のしようがないですね。
ただし、末尾位置での自己再帰の場合は違います。これは次で説明します。
3. Aが末尾位置で自己再帰している場合に lambda 境界を越えていないこと
ちょっと難しいです。というかかなり難しい。
まず末尾位置での再帰は jump に変換できることを思い出してください。
例えば
(define (func x) ... (func hoge))
みたいな末尾再帰は func のお尻から func の頭に jump しているのと考えることも出来ます。
これとインライン展開を組み合わせると、末尾位置で自己再帰しているクロージャは
[先頭][何らかの処理][お尻][先頭にjump]
という名前なしの命令列として展開できることに気づくと思います。
ただし必ずしも上のようにうまくいくわけではありません。以下のように自分自身の呼び出しが lambda 式の境界を越えていると難しいです。
これが3番目の条件「Aが末尾位置で自己再帰している場合に lambda 境界を越えていないこと」になります。
(letrec ((foo (lambda (...) ..... (foo ...)) ;; これは OK ... (letrec ((foo (lambda (...) .... (lambda () ... (foo ...)) ;; これは NG
4. 最後の条件
最後は以下の2つのどちらかを満たしていれば OK とします。
- 1つの LOCAL call しかない場合
- TAIL-REC call が1つもなく、クロージャのサイズが小さいこと
上の条件は、一ヶ所なら文句なくインライン展開しよう。
下の条件は何か所も call されている場合も考えられるから、あまり大きなクロージャは展開しないようにしよう。という意図ですね。
4つの条件を満たしたら
4つの条件を満たした場合、そのクロージャの生成と変数への束縛はなくなり、そのかわり body が call されている場所にインライン展開されます。
LOCAL call は EMBED に、TAIL-REC は JUMP として展開されます。
