Arantium Maestum

プログラミング、囲碁、読書の話題

論文メモ：ORBIT: An Optimizing Compiler for Scheme

言語処理系 論文メモ

CPS形式のコンパイラIRについて調べていてORBITというコンパイラについての話が出てきたので、1986年に出た論文ORBIT: An Optimizing Compiler for Schemeを読んでみた。

ORBITはGuy SteeleのRABBITというScheme Compilerから「CPS形式をIRとして使う」というアイデアを受け継ぎ、さらにそのIRに対して最適化を行うことでより実用的なコンパイラを目指したもの。Yale大学で研究が行われていたらしいLisp方言T Programming Languageのコンパイラとして実装された。T Programming Languageに関しては、なぜかPaul GrahamのウェブサイトにOlin Shiversの回顧録が載っている。

新規性

T言語はアカデミックなリサーチ言語に留まらず、実際にユーザのいる実用的なScheme実装だったらしい（ただしこの段階ではまだSchemeもスタンダードされていないので、「Steele & SussmanのLambda Papersに影響されたLexical ScopeなLisp」くらいの意味だが）。RABBITは完全にアカデミックな成果物（Steeleの修士研究）なので、ORBITはCPS IRを採用した初の実用的コンパイラだと言える。

ORBITコンパイラ中身の新規性としては

The new ideas in Orbit include:

  1. An extension to CPS conversion called assignment conversion that facilitates treatment of assigned variables. (See section 3.)

  2. Compact and efficient runtime data representations, the most important being those for lexical closures, which are represented in different ways depending on information gleaned from a static analysis of their use. (See sections 4 and 5.)

  3. A register allocation strategy based on trace scheduling that optimizes register usage across forks and joins (and which, because of CPS conversion, includes procedure calls). (See section 6.)

  4. An integral table-driven assembler that uses hints from the code generator to order blocks so as to min- imize the number and size of jumps. (See section 7.)

  5. A technique for defining the behavior of primitive operations in Scheme source modules rather than in the internal logic of the compiler. (See section 9.1.)

  6. Flexibility in configuring the runtime support system for user programs. (See section 9.2.)

とのこと。特に１と２は自作言語を作る上でも参考になりそう（３以降は少しマニアックというかプロダクト感が強い印象）

コンパイラのフェーズ

ORBITによるコンパイルは９つのフェーズを通る：

  1. α変換
  2. CPS変換
  3. 代入変換
  4. 最適化
  5. 関数宣言の追加
  6. クロージャのアロケーション戦略決定
  7. クロージャのデータ表現決定
  8. コード作成
  9. アセンブル

１、２は最近ブログでも書いたので割愛。

３の代入変換（Assignment Conversion）というのはSchemeの変数がset!で破壊的代入可能なのだが、その対象となる変数に関しては値をMLでいうところのrefつまり明示的にミュータブルなcellに変換してしまう、というコンパイラ・パス。Schemeが裏でMLみたいになっている、というのはなかなか面白い。

5、８、９は面白いことが書いてあるのだが割愛。最適化とクロージャに関する決定について見ていく。

最適化

フェーズ４の最適化に関しては以下の８つが行われている：

1 ((lambda () body)) => body

無名な０引数関数を定義し、即呼び出している場合はクロージャを作成せずに関数本体の式をそのまま評価するような形にする。

2 ((lambda (x) (. . . x . . . ) y) => (. . . y . . . ) if x is referenced only once or if it appears that the reduced cost of accessing y offsets the increase in code size that results from duplicating Y.

いわゆるβ簡約。

3 Constant folding of primitive operations, including conditionals.

定数畳み込み。

4 Substituting values that are defined in this module or in another module whose declaration file (see section 3.6) is being used in the compilation

これは定数畳み込みに近いものだろうか？

5 Removing unused arguments to procedures.

CPS変換をしているので関数の引数は副作用がないことが保証されている。なので使われない仮引数は消されても大丈夫（実引数の評価時に副作用がある場合、CPS変換で引数じゃなくても副作用が起こるように変換されている）

6 Removing side-effect free calls whose results are not used.

これはまあ当然。こんなコードが本当にコンパイラに渡されるのだろうか？CPS変換などの経緯でそういう無駄なコードが作成されるのだろうか。

7 Various optimizations specific to primitive operations, involving multiple value returns, mutually recursive definitions, etc.

多値の扱いなど、このブログ記事では詳細には立ち入らないが論文に書いてある詳細（3.5 Other Transformationsの部分）がなかなか面白い。CPS変換していることで、関数のリターンは別の関数（継続）の末尾呼び出しになるわけで、タプルなどのデータ構造を使わず直接「二つ以上の値を関数から返す」ということが表現できるようになる。

8 Transformations of conditional expressions to effect “boolean short-circuiting;”

ネストしたif式はいろいろと変換が可能らしい。

The organization and simplicity that CPS and assignment conversion bring to the intermediate code allows a few fairly simple transformations such as these to produce highly optimized code.

というわけでCPS形式は最適化しやすい、とのこと。コードのプリミティブの少なさと、複雑な式が現われる箇所に対する厳しい制約のおかげで、少数かつ簡単な最適化が効きやすい、というのがメリットのようだ。

Closure Strategy/Representation Analysis

クロージャ（主に関数内の自由変数によって捕捉される「環境」）をヒープ・スタック・レジスタのどこで表現するかはコンパイラが決定する。関数がどこで使用されるか（あるいはどこで使われるかがある程度予測可能かどうか）が静的に解析され、それを元にレジスタに置けるか、それがダメならスタック、それがダメならヒープ、とクロージャの置かれる領域が決定される。

またRepresentation Analysisとしては、同じ（あるいは重なり合っている）環境を共有する関数らをクロージャ化する場合には同一のストラクチャにまとめてしまうことで環境部分の重複を避ける、Closure Hoistingという手法が使われる。

それ以外

レジスタの割り当てやコード作成、アセンブルなどに関してもいろいろ工夫があるようで論文では結構詳しく書かれている。ここでは割愛。

その後

主著者のDavid Kranzはこの研究をそのまま書き上げて博士論文にしたらしい。同じ題名「ORBIT: An Optimizing Compiler for Scheme」をつけたようだ。残念ながらこちらは軽く検索した範囲ではネット上に見つからなかった。

CPSをIRとして使ったコンパイル手法はORBIT/T Programming Languageの後、Appel他のSML of New Jerseyにも使われており、Appelはその経験をベースにCompiling with Continuationsという本を書いている。そこからANFが出てきて云々、という話は以前ブログに書いた通り。

そろそろCompiling with Continuationsを実装しながら読むべきかもしれない。