Gauche:Inlining
手続きのコンパイル時インライン展開に関する雑多なメモ。
インライン化の属性
- 「インラインの方法」、つまり「この手続きをインライン展開するならどうしたら良いか」 という情報は手続き自体に属する。
- 「インライン許可」、つまり「この手続きはインライン展開が可能ならやっていいよ」 という属性は束縛に属する。
基本的に、束縛がimmutableかつ値が定数(コンパイル時に確定する値)であれば、 コンパイラは変数参照を値に置き換えることができる。その値が手続きであって インライン可能であれば、そこでインライン展開を行える。
インライン化のセマンティクス
inlineされた手続きfooを呼んでいる手続きは、コンパイル後にfooのグローバルな 束縛が置き換えられても影響を受けない。これはinline許可された(inlinableな) 手続きが一種の定数束縛であると考えればおかしくはない。 (define-constantで定義された定数を参照している手続きは、やはりコンパイル時に 定数参照を定数そのものに置き換えてしまうので、その後の定数の変更には影響を受けない) (なお、現在のtrunkではdefine-inlineで定義された束縛の変更は、 define-constantによる束縛と同様、warningを出すようにしている)。
R6RS-ishなセマンティクスでは、ライブラリの外から見える束縛を変更することが そもそも許されていないため、この方針で矛盾は生じない。
R5RSではやや不明確ではあるが、以下の理由でGaucheでは許容範囲と考えている。
- 「既存のトップレベル束縛を置き換えても組み込み手続きには影響を与えない (chapter6)」 ことからSchemeの標準組み込み手続きをSchemeの標準組み込み手続き内で インライン展開することは正当化される。
- define-inlineで定義されているinlinableな手続きについてはそもそもその束縛自体が R5RSの範囲外であるので、それを置き換えることが既にコンパイルされた手続きに 影響を与えないことは拡張仕様と考えられる。(たとえばdefine-syntaxによる束縛は 再定義がコンパイル済みの手続きに影響を与えない。それと同様に、特殊な束縛を 拡張機能として導入した、と考えれば良い)
- Schemeの標準組み込み手続きを置き換えることがコンパイル済みのユーザ定義手続きに 影響を与えべきか、についてはグレーゾーン。そもそもトップレベル束縛の意味が 曖昧なので。
ただ、「すべてがいつでも変更可能」という世界を欲した場合、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 ())))
- foldの呼び出し時にリストはひとつしか与えられていない、つまりmore引数が '()であることがわかるので、最初の (if (null? more) ...) の分岐は 条件成立時のみのコードに置き換えられる。
- kons引数が組み込みのconsであることがわかるので、inner loopで konsを呼び出している箇所をVMのCONSインストラクションに展開できる。
特に後者が効いて、速度は0.9の倍くらいになる。
(なお、最初のkonsへの($gref cons)の束縛は最適化で除去可能なはずだけど できてない。まだどっかおかしい。)
ビルトイン・インライン関数
Schemeレベルでインライン化するこれまでの話とはちょっと違って、 VM命令レベルでインライン化する関数についての話。 例えばconsは、VMがCONSインストラクションを持っているので直接 そいつにコンパイルされる。 Cコンパイラでもmemcpyみたいなプリミティブがコンパイラに認識されて アセンブラでインライン展開されるけど、そういうのに近い話だ。
0.9現在、VMインストラクションレベルでのインライン展開は 次のいずれかの形式で指定される。
- define-cprocによるsubr定義中にVMインストラクションが指定される。 その関数に正確に対応するVMインストラクションがある場合。
- compile.scm内で、define-builtin-inlinerで定義された展開ルーチンが コンパイラのpass 1の一部として呼ばれる。 こちらは複数の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インストラクションに一本化されることになる。
ただ、基本関数をこのように定義するのには注意が必要だ。
- 上の定義はコアにコンパイルインされてなければならない。 つまり、コンパイラの初期化ルーチンがbuiltin-inlinerをアタッチする時点では既に定義されて いなければならない。0.9では、*.stubの初期化ルーチンとscmlib.scmの初期化 ルーチンが走った後にcompile.scmの初期化ルーチンが走ることでそれを担保している。
- ということは、上のzero?をインライン展開するのはその時点でのcompile.scmによる インライン展開ルーチンではなくて、「ひとつ前の」compile.scmによるインライン展開 ルーチンだ (0.9.1_preをコンパイルするのは0.9リリース版のコンパイラ)。 あるバージョンのインライン展開ルーチンにバグを持ち込んでしまった場合、 compile.scmを直しても、直したバージョンをリリースする際にコンパイルされる zero?の本体にはバグが入ったままになる。完全にバグが「抜けきる」のは 直したcompile.scmのバージョンをリリースして、それでビルドされるさらに次のバージョン。 (バグが深刻なら、中間バージョンはzero?の定義をインライン展開を使わないように 一時的に変更する必要があるだろう)。
- あと、一度こういう定義をやると、コンパイラの最適化ルーチンが絶対に壊れない ように気をつけないとならない。0.9までの状態なら、最適化が壊れてたとしても、 最適化を切ってビルドすれば一応動くものはできるので、それでバグを直した版を ビルドしてインストールし、再び最適化onでビルドすれば良い。 しかし、上のように基本関数の定義がインライン展開を当てにしてたものだと、 最適化を切ってコンパイルしたらzero?は無限ループになってしまう。 (「インライン展開以外の最適化を切る」というオプションをつけとくのが安全か。)
環境を持つ関数のインライン展開
再び、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の呼び出し箇所のコンパイル」に反映させる必要がある。