Gauche:Translation:Devlog:手続きインライナの改善

手続きインライナの改善

これは 0.9.6 のコンパイラの内部的な変更に関するものです。ユーザーが観測可能な変更はありません。あなたがコンパイラの内部について興味を持っていれば面白いかもしれません。

＊＊＊

Gauche のプリミティブな手続きの内のいくつかは、 VM 命令としてインライン展開されます。例えば、 Gauche の VM は、ベクタを即値オフセットで参照する命令を持っています。 vector-ref の第 2 引数が定数の場合、その命令が使用されます。

gosh> (disasm (^x (vector-ref x 0)))
CLOSURE #<closure (#f x)>
=== main_code (name=#f, code=0x20e3160, size=3, const=0 stack=0):
signatureInfo: ((#f x))
     0 LREF0                    ; x
     1 VEC-REFI(0)              ; (vector-ref x 0)
     2 RET

これはパフォーマンスにおいてかなり効果的な傾向があります。

define-inline を使ってプロシージャをインライン化可能として定義することもできます。この機能はGauche ランタイムを最適化するために使われてきています。

ただし、 0.9.5 までは、インライン化可能手続きが関数適用の手続き位置に現れる場合にのみにインライン化が制限されます。次の例では、 vector-ref は手続き位置に文字どおりには現れないため、インライン化されませんでした。

gosh> (define-inline (foo ref) (^x (ref x 0)))
foo
gosh> (disasm (^x ((foo vector-ref) x)))
CLOSURE #<closure (#f x)>
=== main_code (name=#f, code=0x2228f50, size=9, const=2 stack=14):
signatureInfo: ((#f x))
     0 LREF0-PUSH               ; x
     1 PRE-CALL(1) 7            ; (foo vector-ref)
     3 GREF-PUSH #<identifier user#vector-ref.2238300>; vector-ref
     5 GREF-CALL(1) #<identifier user#foo.2238340>; (foo vector-ref)
     7 TAIL-CALL(1)             ; ((foo vector-ref) x)
     8 RET

これは悩みの種でした。インライン化とβ簡約の効果が次のようにつながって欲しいと思うのは自然です。

((foo vector-ref) v)
 ↓
(((^[ref] (^x (ref x 0))) vector-ref) v)
 ↓
((^x (vector-ref x 0)) v)
 ↓
(vector-ref v 0)

これを妨げていたのは古いインラインインターフェイスでした。

＊＊＊

Gauche のコンパイラには 5 つのパスがあります。パス 1 はマクロを展開し、入力S式を IForm というグラフに置き換えます。 2 から 4 のパスは IForm 上で最適化を行い、パス 5 は最終的な IForm をたどって VM 命令を出力します。

vector-ref が展開されるのはパス 1 です。インライン化可能手続きにはインライナ手続きが結びつけられていて、それは入力S式とコンパイル時環境 Cenv を取って、展開された IForm を返します。：

Inliner :: Sexpr, Cenv -> IForm

コンパイラがフォーム (fn arg …) を見て fn にインライナがある場合、このフォーム (fn arg …) はそれに渡されて、返ってきた IForm は元のフォームのパス 1 の結果になります。

fn が define-inline で定義されている場合、インライナ手続きは元の手続きの IForm を保持するクロージャです。コンパイラがこの定義を参照する場合：

(define-inline (vref v) (vector-ref v 0))

パス 1 で (^v (vector-ref v 0)) を処理し、その IForm を得ます。今は #<IForm (^v (vector-ref v 0))> と表しましょう。 vref のインライナはこのようなものになります。

(^[sexpr cenv]
  (#Apply #<IForm (^v (vector-ref v 0))>
          (map (cut pass1 <> cenv) (cdr sexpr))))

ここで、擬似関数 "#Apply"は、第 2 引数の IForm のリストに第 1 引数を適用する IForm を作成します。後続の最適化パスは、可能であれば、ローカル変数 v を削除します。 vref の本文をそのままS式で保持して展開するという手も考えられなくはありません：

(^[sexpr cenv]
  (pass1 `(apply (^v (vector-ref v 0)) ,@(cdr sexpr)) cenv))

しかし、そのような方法は衛生性問題に繋がるでしょう。名前の競合を避けるために、 vector-ref の名前を変更する必要があります。パス 1 を実行すると、すべての識別子の参照が解決されるため、衛生上の問題も解決します。

問題はインライナの入力がS式であり、出力が IForm であるということです。つまり、別のインライナの結果にインライナを適用することはできません。上記の foo のケースが予想どおりにインライン化されなかったのはそういった理由でした。

また、パス 3 の間にインライン展開する他の機会もあります。クロージャの最適化と冗長なローカル変数の削除を行うと、インライン化手続きを持つ手続きの呼び出し形式を得ることがあります。パス 3 は IForm を扱っているので、そのような場合にはインライナを適用できませんでした。

＊＊＊

解決策はインライナプロトコルを変更することです。入力S式を取る代わりに、インライナが IForm を取るようにできます：

Inliner :: IForm, [IForm] -> IForm

最初の IForm はインライン化可能手続きの本体で、 2 番目の IForm のリストは IForm からの引数式です。 Cenv の情報は既に IForm に畳み込み済みです。

パス 1 では、インライナを呼び出す前に、手続きと引数を処理します。パス 3 では、単にインライナを呼び出すことができます。

これで、インライン化の効果がつながるようになりました。

;;REF をアクセサとして使用して、
;;指定されたシーケンスの最初の要素をとるプロシージャを返します。
(define-inline (foo ref)
  (^v (ref v 0)))

;;シンボル TYPE に従ってアクセサを返します。
(define-inline (bar type) 
  (cond 
   [(eq? type 'v) vector-ref]
   [(eq? type 'u8) u8vector-ref]))

;;TYPE で指定されたアクセサを使用して、
;; V の最初の要素にアクセスするために foo と bar を使用します。
(define-inline (baz type v)
  (let ((ref (bar type)))
    ((foo ref) v)))

type が定数の場合、 bar の cond 式はコンパイル時に計算され、すべてを VM 命令にインライン化できます。

gosh> (disasm (^v (baz 'v v)))
CLOSURE #<closure (#f v)>
=== main_code (name=#f, code=0x28783e0, size=3, const=0 stack=0):
signatureInfo: ((#f v))
     0 LREF0                    ; v
     1 VEC-REFI(0)              ; (ref v 0)
     2 RET 
gosh> (disasm (^v (baz 'u8 v)))
CLOSURE #<closure (#f v)>
=== main_code (name=#f, code=0x2878340, size=4, const=0 stack=1):
signatureInfo: ((#f v))
     0 LREF0-PUSH               ; v
     1 CONSTI(0) 
     2 UVEC-REF(1)              ; (ref v 0)
     3 RET

＊＊＊

この変更により、パフォーマンスを心配することなく抽象的な記述をすることが出来ます。