Gauche:Inlining

Gauche:Inlining

手続きのコンパイル時インライン展開に関する雑多なメモ。

インライン化の属性

基本的に、束縛がimmutableかつ値が定数(コンパイル時に確定する値)であれば、 コンパイラは変数参照を値に置き換えることができる。その値が手続きであって インライン可能であれば、そこでインライン展開を行える。

インライン化のセマンティクス

inlineされた手続きfooを呼んでいる手続きは、コンパイル後にfooのグローバルな 束縛が置き換えられても影響を受けない。これはinline許可された(inlinableな) 手続きが一種の定数束縛であると考えればおかしくはない。 (define-constantで定義された定数を参照している手続きは、やはりコンパイル時に 定数参照を定数そのものに置き換えてしまうので、その後の定数の変更には影響を受けない) (なお、現在のtrunkではdefine-inlineで定義された束縛の変更は、 define-constantによる束縛と同様、warningを出すようにしている)。

R6RS-ishなセマンティクスでは、ライブラリの外から見える束縛を変更することが そもそも許されていないため、この方針で矛盾は生じない。

R5RSではやや不明確ではあるが、以下の理由でGaucheでは許容範囲と考えている。

ただ、「すべてがいつでも変更可能」という世界を欲した場合、define-inlineを 再定義したらそれを使ってる手続きにも反映されてほしい、という要求はありだと思う。 R7RSのsmall Schemeではこういう可能性を許すゆるい定義に戻ることもありそう。 もしそういうケースをサポートするなら、各手続きは「インライン展開した束縛の リスト」を持っといて、再定義がかかったら再コンパイルかけるようにするかな。 class redefinitionが似たようなことをやってるわけで、やって出来なくはない。 内部が必要以上に複雑になりそうで避けたい話ではあるけれど。

なお、constantな束縛とinlinableな束縛は概念的に同じようなものだし、 統一してしまえばすっきりするんだけど、今のGaucheは実装上の都合でわけてる。 定数置換でコード内に#<subr>が入ると、まだそいつをシリアライズできないので、 precompileで問題が生じるのだ。

インライン化の意義

インライン化のメリットは何か。ネイティブコンパイラならば、 call/ret及び関数の入り口出口処理を省けるので高速化できるというのが すぐ思いつくが、Gaucheの場合VMレベルでの通常のインストラクション ディスパッチとcall/ret処理は(#<subr>や#<procedure>の呼び出しの 場合は)あんまり大きな差はでない。もちろん多少は速くなるけど、 本当のメリットは別のところにあると思う。

別のメリットとは、関数単体のコンパイル時にはわからなかった情報が、 呼び出し箇所を見ることで得られる、ということだ。例えば実引数が 定数である場合、関数本体をインライン展開すればそこから定数畳み込みが 行える可能性が増える。

コンパイルを部分評価の一種と考えればわかりやすい。可変部分が減れば減っただけ、 より特化したコードが生成できる。

0.9までのGaucheでは、インライン展開後に判明した情報による最適化は 限定的にしか行っていないので、たとえば組み込みのfoldをdefine-inlineで再定義しても、 あまりメリットはない。0.9で(fold cons '() xs)をコンパイルしてみる。

gosh> (define compile-p2 (with-module gauche.internal compile-p2))
compile-p2
gosh> (define-inline (fold kons knil lis . more)
  (if (null? more)
    (let loop ((lis lis) (knil knil))
      (if (null-list? lis) knil (loop (cdr lis) (kons (car lis) knil))))
    (let loop ((liss (cons lis more)) (knil knil))
      (receive (cars cdrs)
          ((with-module gauche.internal %zip-nary-args) liss knil)
        (if cars
          (loop cdrs (apply kons cars))
          knil)))))
fold
gosh> (compile-p2 '(fold cons '() xs))
($let ((kons[2;0] ($gref cons))
       (lis[2;0] ($gref xs))
       (more[2;0] ($LIST )
       )
  ($if ($asm (NULLP)
         ($lref more[2;0]))
    ($letrec ((loop[2;0] ($lambda[loop;0] (lis[3;0] knil[2;0])
                           ($if ($let ((l[3;0] ($lref lis[3;0]))
                                       )
                                  ($if ($asm (NULLP)
                                         ($lref l[3;0]))
                                    ($it)
                                    ($if ($asm (PAIRP)
                                           ($lref l[3;0]))
                                      ($const #f)
                                      ($call ($gref error)
                                        ($const "argument must be a list, but got:")
                                        ($lref l[3;0])))))
                             ($lref knil[2;0])
                             ($call ($lref loop[2;0])
                               ($asm (CDR)
                                 ($lref lis[3;0]))
                               ($call ($lref kons[2;0])
                                 ($asm (CAR)
                                   ($lref lis[3;0]))
                                 ($lref knil[2;0]))))))
              )
      ($call ($lref loop[2;0])
        ($lref lis[2;0])
        ($const ())))
    ($letrec ((loop[2;0] ($lambda[loop;0] (liss[1;0] knil[2;0])
                           ($receive (cars[2;0] cdrs[1;0])
                               ($call ($gref %zip-nary-args)
                                 ($lref liss[1;0])
                                 ($lref knil[2;0]))
                             ($if ($lref cars[2;0])
                               ($call ($lref loop[2;0])
                                 ($lref cdrs[1;0])
                                 ($asm (TAIL-APPLY 2)
                                   ($lref kons[2;0])
                                   ($lref cars[2;0])))
                               ($lref knil[2;0])))))
              )
      ($call ($lref loop[2;0])
        ($asm (CONS)
          ($lref lis[2;0])
          ($lref more[2;0]))
        ($const ())))))

ただfoldの中身がだらだら展開されてるだけで、実行時間への貢献はほとんどない。

現在手元にあるコードで同じ式をコンパイルするとこうなる。

gosh> (compile-p2 '(fold cons '() xs))
($let ((kons[1:0] ($gref cons))
       (lis[2:0] ($gref xs))
       )
  ($call[embed] ($lambda[loop:2] (lis[5:0] knil[3:0])
                  ($label #0
                    ($if ($asm (NULLP)
                           ($lref lis[5:0]))
                      ($lref knil[3:0])
                      ($if ($asm (PAIRP)
                             ($lref lis[5:0]))
                        ($label #1
                          ($call[jump] ($call[embed] ($lambda[loop:2] (lis[5:0] knil[3:0])
                                                       label#0)
                                         ($lref lis[2:0])
                                         ($const ()))
                            ($asm (CDR)
                              ($lref lis[5:0]))
                            ($asm (CONS)
                              ($asm (CAR)
                                ($lref lis[5:0]))
                              ($lref knil[3:0]))))
                        ($if ($call ($gref error)
                               ($const "argument must be a list, but got:")
                               ($lref lis[5:0]))
                          ($lref knil[3:0])
                          label#1)))))
    ($lref lis[2:0])
    ($const ())))

特に後者が効いて、速度は0.9の倍くらいになる。

(なお、最初のkonsへの($gref cons)の束縛は最適化で除去可能なはずだけど できてない。まだどっかおかしい。)

ビルトイン・インライン関数

Schemeレベルでインライン化するこれまでの話とはちょっと違って、 VM命令レベルでインライン化する関数についての話。 例えばconsは、VMがCONSインストラクションを持っているので直接 そいつにコンパイルされる。 Cコンパイラでもmemcpyみたいなプリミティブがコンパイラに認識されて アセンブラでインライン展開されるけど、そういうのに近い話だ。

0.9現在、VMインストラクションレベルでのインライン展開は 次のいずれかの形式で指定される。

で、特に後者で気になっていたのが、「意味的に似たコードが複数箇所に存在してしまう」 ということだった。例えばzero?はstdlib.stub内でsubrとして定義されている。

(define-cproc zero? (obj::<number>) ::<boolean> :fast-flonum :constant
  (result (and (SCM_REALP obj) (== (Scm_Sign obj) 0))))

と同時に、コンパイラ中でNUMEQ2インストラクションを使ったゼロとの比較に展開される。

(define-builtin-inliner zero?
  (lambda (form cenv)
    (match form
      [(_ arg)
       ($asm form `(,NUMEQ2) `(,(pass1 arg cenv) ,($const 0)))]
      [else (error "wrong number of arguments for zero?:" form)])))

一方は実行時環境での値に対する操作、他方はコンパイル次環境でのコードに対する操作なので 具体的にやってることは全く違うのだけれども、ここには重複がある。 「zero?のsubr定義で走るコード」と、 「inlinerで生成されるVMアセンブラ+VMインストラクション」と、 同じ動作を実現するのに二とおりのコードが使われている。 これはあまり嬉しくない。 (こうなったのは、もともとインライン展開が無くてsubrのみ だったところに、後からインライン展開に使えるVMインストラクションが 追加されたという歴史的な経緯なのだが)。

もうコンパイラのインライン展開はだいぶ枯れてきたので、そろそろこういうケースで コードを統合する時期と見た。

具体的には、「コンパイラがzero?をインライン展開することを前提として」、 zero?を次のように定義すれば良い。

(define (zero? obj) (zero? obj))

bodyのzero?はコンパイラによってインライン展開されるので無限ループにはならない。 そしてzero?の動作をするコードはinliner+NUMEQ2インストラクションに一本化されることになる。

ただ、基本関数をこのように定義するのには注意が必要だ。

環境を持つ関数のインライン展開

再び、Schemeで定義した関数のインライン展開について。

現在(0.9)でのインライン展開は、展開すべき関数本体のマクロ展開後の 中間表現を保存しておいて、呼び出し箇所にそれをそのまま展開する、 というふうにしている。

;; インライン化可能な関数の定義
(define-inline (foo x y) (when x (foo1 y)))

;; fooに束縛されるクロージャにアタッチされる中間表現
($lambda[#f.0] (x.1 y.1)
  ($if ($lref x.1)
    ($call ($gref user#foo1)
      ($lref y.1))
    ($const #<undef>)))

;; 呼び出し箇所
(define (bar z) (foo #t z))

;; インライン展開を行わない場合のbarの中間表現
($lambda[#f.0] (z.1)
  ($call ($gref user#foo)
    ($const #t)
    ($lref z.1)))

;; fooがインライン展開されるとこうなる (fooにアタッチされてたlambdaの
;; 中間表現がletに置き換えられてるのに注目)。
($lambda[#f.0] (z.1)
  ($let ([x.1 ($const #t)]
         [y.1 ($lref z.1)])
    ($if ($lref x.1)
      ($call ($gref user#foo1)
        ($lref y.1))
      ($const #<undef>))))

;; 最適化パス後にはこうなる。
($lambda[#f.0] (z.1)
  ($call ($gref user#foo1)
    ($lref z.1)))

最初の中間表現の段階で束縛変数の分類は済ませてるので、 インライン展開が変数の衝突を起こすことはない。

しかし高階関数を多用してると、 直接lambdaで定義した関数ではない場合も展開して欲しくなる。

(define (foo a) (lambda (b c) (vector a b c)))

(define-inline bar (foo 1))

(bar 2 3)
;; 今のGaucheではbarの呼び出しは展開されない
($call ($gref user#bar)
  ($const 2)
  ($const 3))

;; 展開できるなら最終的にこうなってくれるはず
($asm (VEC 3)
  ($const 1)
  ($const 2)
  ($const 3))

この例はわざとらしいけど、コンビネータライブラリみたいなのでは こういうことは良くある。Schemeレベルでの手続き呼び出しは さほど重くないのだけれど、PEGみたいに一番内側のクロージャが 「一文字読む」みたいな細かい粒度で、外側のコンビネータで ループを作ってる場合、内側のクロージャが展開されてread-charの 直接呼び出しになってくれるとかなりうれしい。

今の方法(クロージャのコンパイル時中間表現を持っとく方法)では こういうインライン展開は原理的にできない。 クロージャの中間コードは、そのクロージャのコンパイル時にまだ確定していない 外側の環境を参照しているからだ。

安直に中間表現を展開すると、その後のコード生成フェーズで 存在していないローカル変数を参照しているというエラーになる。

もうひとつの安直な方法は、 barの参照をその定義で置き換えてしまう方法だが:

(bar 2 3) => ((foo 1) 2 3)

これはコンビネータの中で重たい計算や副作用のある 計算をしている場合に、それが重複して計算されることに なるのでまずい。

;; 定義を置き換える方法ではまずい例
(define (foo x) 
  (let ((y (very-heavy-calculation x)))
    (side-effecting-calculation)
    (lambda (z) (vector y z))))

このようなケースでインライン展開を可能にするには、 「実行時に定まるbarの環境」を参照するようなコードを 「barの呼び出し箇所のコンパイル」に反映させる必要がある。

More ...