Shiro(2011/08/23 16:49:17 PDT): もうちょっと真面目に依存性解析すればより一般的な 最適化になるかもしれないけど。
とあるマクロの展開とそのコンパイル結果を見てて、 次のような式が冗長にコンパイルされてるのに気づいた:
((lambda (x) (g x)) (f a))
これは (g (f a))
と全く等価なはずだけど、今のコンパイラは
(let ((x (f a))) (g x))
ってとこまで変形して最適化を諦めちゃうので、無駄なPUSH-LOCAL-ENV
が生成される。
commit a202785でこの手のパターンを最適化してみた。
gosh> (disasm (lambda () ((lambda (x) (/ x)) (- n)))) CLOSURE #<closure #f> main_code (name=#f, code=0x1fabc40, size=8, const=2, stack=8): args: #f 0 GREF #<identifier user#n>; n 2 NEGATE ; (- n) 3 PUSH-LOCAL-ENV(1) ; ((lambda (x) (/ x)) (- n)) 4 LREF0-PUSH ; x 5 GREF-TAIL-CALL(1) #<identifier user#/>; (/ x) 7 RET gosh> (time (dotimes (n 10000000) ((lambda (x) (/ x)) (- n)))) ;(time (dotimes (n 10000000) ((lambda (x) (/ x)) (- n)))) ; real 3.219 ; user 3.220 ; sys 0.000
gosh> (disasm (lambda () ((lambda (x) (/ x)) (- n)))) CLOSURE #<closure #f> === main_code (name=#f, code=0x241ba80, size=6, const=2 stack=4): args: #f 0 GREF #<identifier user#n>; n 2 NEGATE ; (- n) 3 PUSH-GREF-TAIL-CALL(1) #<identifier user#/>; (/ x) 5 RET gosh> (time (dotimes (n 10000000) ((lambda (x) (/ x)) (- n)))) ;(time (dotimes (n 10000000) ((lambda (x) (/ x)) (- n)))) ; real 2.661 ; user 2.660 ; sys 0.000
PUSH-LOCAL-ENV
の直後にLREF
している、というパターンを
pass5のpeepholeで見つけようかとも思ったのだが、
(let ([p (f a)] [q (g b)]) (h q 0 p) (foo)) => (begin (h (g b) 0 (f a)) (foo))
くらいになるとpass2のlet最適化のところで見つけちゃった方がやりやすい。
なおこの例はlet/letrecのinit式の評価順序が入れ替え可能であることに 依存している。let*はpass1でletのネストに変換されてるから問題ないけど、 letrec*をサポートする場合はこの変換で初期化式の評価順序が変わらないように 制約をつける必要がある。
(let1 p (f a) (let1 q (g p) (h q)))
のようなパターンは
(let1 p (f a) (h (g p)))
まで変形されるが (h (g (f a)))
とは
ならない。ネストした呼び出しの引数を追っかければ良いのだが、
(let1 p (f a) (let1 q (g (z) p) (h q)))
のように別の引数で呼び出しが
挟まる場合、(z)
が副作用を持ち得るので外側のletは外せない。
このへんをどこまでちゃんとやるかって話になる。
(2011/08/23 18:10:25 PDT): ネストした呼び出しについては、それほどややこしく考える必要はないかも。 ネストが一本の鎖になっていれば置き換えOKで、途中で分岐してればNG、でいいかな。
一本鎖: f0 --> f1 --> f2 --> f3 --> p \-> q constの枝はあってもok f0 --> f1 --> f2 --> f3 --> p \-> 0 \-> 1 \-> 2 \> q 他の枝はNG f0 --> f1 --> f2 --> f3 --> p \-> 0 \-> q \-> 2 f0 --> f1 --> f2 --> f3 --> p \-> 0 \-> f5 \-> q
(2011/08/24 05:32:09 PDT): というわけでネストした呼び出しにも対応 (4f4421c)。
この最適化パスが呼ばれるようなコードを手で書くことは少ないけれど、 matchの出力などマクロ展開結果にはわりと良く出てくるので、 かなり特殊なケースのように見えて実は案外有効かもしれん。