Gauche:アドホックなletフレーム除去

Gauche:アドホックなletフレーム除去

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でこの手のパターンを最適化してみた。

0.9.2

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
commit a202785

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*をサポートする場合はこの変換で初期化式の評価順序が変わらないように 制約をつける必要がある。

検討課題

(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の出力などマクロ展開結果にはわりと良く出てくるので、 かなり特殊なケースのように見えて実は案外有効かもしれん。

More ...