2007/1/18 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎

Presentation on theme: "2007/1/18 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎"— Presentation transcript:

1 2007/1/18 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎
コンパイラ演習 第 12 回 2007/1/18 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎

2 今日の内容 Garbage Collection (ごみ集め) 配列境界検査

3 Garbage Collection 概論 遠藤敏夫さんの資料を使います 遠藤敏夫さん 東京工業大学松岡研究室特任講師

4 演習でどの GC を実装するか? たぶん copying GC が一番楽 興味があれば mark-sweep GC に 挑戦してみるのも良い
コンパイラ側の改造が多いのをいとわなければ reference count もおもしろい さらに余裕があれば incremental GC、generational GC も

5 GC 導入のための コンパイラの変更 (1) ヒープ確保コードを改造 ヒープからのメモリ確保コードを改造
Copying GC を採用する場合、ヒープを２つ準備 ヒープからのメモリ確保コードを改造 ヒープポインタとヒープリミットを比較、ヒープがあふれそうなら GC ルーチンに飛ぶ ヒープ上データの作成・アクセスコードを改造 配列やタプルなどのヒープ上データに、 型やサイズを示すタグを付加 採用する GC に従い、 mark bit 領域や reference count 領域などを追加。 それらを操作するコードも追加

6 GC導入のための コンパイラの変更 (2) GC が rootset を得るための処理を追加
フレームに保存された PC の値から、 そのフレームの各ワードの型を得るための表を作る, or スタックに値をプッシュする際に、 その値の型の情報もどこかに書き込む など 大域変数のアドレスと型を GC ルーチンが知るための機構を導入 レジスタの値を GC ルーチンの前で退避、 GC ルーチンの後で回復

7 配列境界検査 GC のための拡張と同様に、 データ構造にタグを付加 配列アクセスを行う命令列の前に、 配列長と添字を比較する命令を出力 3
配列アクセスを行う命令列の前に、 配列長と添字を比較する命令を出力 3 23 23 859 859 1110 1110

8 共通課題 MinCaml コンパイラに以下の改造を加えよ 配列長を示すタグを配列に付加する
配列アクセスの前に、配列範囲検査を行う。 配列範囲外にアクセスしようとしていたら、 プログラムを終了させるなどの処理を行う 変更したソースファイルを固めて送ってください。変更していないソースファイルを 送る必要はありません。

9 コンパイラ係用選択課題 Garbage Collection を自作コンパイラまたは MinCaml に実装せよ
使用する GC アルゴリズムは自由 ごみをたくさん作りながら動く サンプルプログラムを記述し、 それが複数回の GC を経て 動き続けることを確認すること コンパイラと GC のソースファイルを 固めて送ってください。

10 課題の提出先と締め切り 提出先: compiler-enshu@yl.is.s.u-tokyo.ac.jp
共通課題の締め切り： 2007年2月1日の午後 1 時 コンパイラ係用課題の締め切り： 2007年2月28日 Subject: Report 12 <学籍番号> <アカウント> 本文にも氏名と学籍番号を明記のこと

11 コンパイラ係の成績評価に ついて (1) 選択課題を一つ以上提出して下さい オブジェクト指向、多相型、例外、 パターンマッチ、etc
これらと同等以上の難度を有する言語機構 の実装をもって選択課題の提出 とみなすことは可能です

12 コンパイラ係の成績評価に ついて (2) 自作コンパイラの特徴・独創的な点などの説明
各コンパイラ係を 前田、佐藤、山下が面談をします 基本的にはレイトレ競技会の付近の日または当日 場所は地下端末室、時間は 20 分程度 やること： 自作コンパイラの特徴・独創的な点などの説明 自作コンパイラによる、プログラム（レイトレ含む）のコンパイル・実行のデモ 自作コンパイラでコンパイルしたレイトレが自作 CPU またはシミュレータ上で動く様子を見せて下さい