情報科学実験II資料 (1)
課題説明

田浦

1/10/98

最終目標

以下は全てが達成できなかった場合の典型的な逃げ道:

演習の進め方

毎回, コンパイラ係が達成すべき課題を出す(目安として, 2週間後に締切るが, 最終的にコンパイラを動かすことが目標なのであまりこだわらなくてよい). 課題を出した1週間後に, 具体的な方法を詳しく述べる(できるだけその方法を 聞く前に自分で解いてみる).

説明は一般的なコンパイラの概要説明というよりも, 具体的なSchemeコンパイ ラの作成を, 順を追って説明する.

進度予定

もちろんこんなものは一応書いてみただけで, このとおり進む可能性は低い.

  1. 概要説明
  2. 作成するコンパイラのおおまかな構造,構文解析
  3. 中間コードContinuation Passing Style (CPS)とCPSへの変換
  4. CPS上の最適化
  5. Closure Conversion
  6. Abstract Machineコード生成
  7. マシンコード生成
  8. Garbage Collection
  9. 予備日
  10. 予備日
  11. 予備日
  12. 予備日

CPU Architecture設計上の注意書

このコンパイラの実験では, できるだけ単純に, 楽にコンパイラを作ることを 目標にする. 逆に, 話しをできるだけ単純にするために犠牲にしている, ある いはさぼる予定である項目をあげる. この犠牲, あるいはさぼりが全体に甚大 な影響を与えないために, 自作CPUに対して仮定している事項を書いてお く. もちろんCPUを全くこれに沿って作らなくても, 逃げ道はあるので, 以下 のarchitectureにこだわることはない(むしろ説明する方式を元に各自の architectureにあわせて方法を工夫することを推奨する).

これから説明するコンパイル技法は,

言語およびarchitectureを, もっとも自然にsupportするように作られている. まず, 最初の項目の具体的に意味するところは, 浮動小数点も整数もことごと く同じ大きさであるということで, 特にray tracingのために浮動小数点は32 bitなくてはいけないから, 結果として全て32 bitになる. 整数やポインタに 対して32 bit割り当てることは(演習で作るCPUではおそらく)無駄なので, そ れを避けるための簡単な工夫は授業でも取り上げる.

2番目の項目の詳しい内容は以下の通り. コンパイラは最終的に中間変数の値 を保持すべき場所をregisterに割り当て, ある時点でもういらない(今後使わ れない)registerの値は他の変数に割り当てるようにする. ここでややこしい のは, もし同時に必要なregisterの数がmachine registerの数を越えたらどう するかということである. 実際にはこれはmachine registerの数が多くあれば (たとえあ32個)非常に稀になるが, それでもおきてしまった場合は, 何らかの 形でそれをmemoryに退避する必要がある(これをregister spillingと呼ぶ). そのmemroyをどのように確保し, またコンパイラが現在どの値はregisterに載っ ておりどの値がmemoryに退避されているかを扱わなくてはいけないのはそれな りに大変な(というよりも苦労のわりに実りの少ない)作業である. 去年は, spillingは授業で扱っていない.

注意としては, 例えば, 全ての変数を同じsizeにして, かつ1 registerが16 bitの場合一つの変数につきregisterを二つ消費し, 結果としてregisterの数 は半分になったように見えるということである. だから16 bit x 32の場合, 同時に保持できる変数の数は16個ということになる.

最後の項目は, コンパイルに使用する中間言語での演算がこの形をとるという ことである. Accumulator machineで3 operand machineをemulateできるが, naiveなemulateでは遅くなるため, 無駄なmoveの除去など, 新たな最適化をす る必要が生ずる.

参考文献

[1]は伝統的なPascal,C等の言語(しばしばAlgol-likeと 呼ばれる)のコンパイル法について詳しく述べている.中間言語しては, いわ ゆるQuad (4つ組)を用いており, その上でのoptimization (dataflow analysis)やregister allocationなどが詳しく述べられている. SchemeやMLな どのmodernな言語については詳しく述べられていないが,例えばcompilerの全 体の構成法なども述べられており, compilerに関する予備知識が少ない場合で も楽に読める.

講義の内容は,[3]をもとにしている.これはおもに SML/NJのコンパイラについて書かれた本で,もちろん話の大部分はSchemeにも 当てはまる. Closure, call/ccなどの実現法が詳しく述べられている. また中 間言語としてはCPSを使っている. 講義ではこの本の内容を,対象言語を単純 化してできるだけ分かりやすくして説明する.また, Cなどの伝統的な compilerに関する知識を仮定してはいないが, それらを知っていた方が理解は しやすい.

Garbage Collectionに関するsurveyは, [2]がよい文献である.

課題の提出方法

課題は全て, compexあてに送る(田浦と, TAの遠藤に送られる). Subjectは, 班名と課題番号とする. 例:

To: compex
Subject: hogehoge 1

課題 1

コンパイラ係は, メールアドレスcompexあてに, 自己紹介と, どの言語のコン パイラを作る予定であるかを書いたメールを送る.

締切り: 10月14日(水).

References

1
Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers Principles, Techniques, and Tools. Addison-Wesley, 1990.

2
Andrew W. Appel. Garbage Collection, chapter 4, pages 89-100. The MIT Press, 1991.

3
Andrew W. Appel. Compiling with Continuation. Cambridge University Press, 1992.

 

〔トップページへ〕 〔「コンパイラ演習レジュメ」のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 9 May, 1999