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

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

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

2 エスケープ解析 今回の内容 メモリに置かれる値のうち ヒープではなくスタックに確保できるもの を見つけることができる
メモリに置かれる値のうち ヒープではなくスタックに確保できるもの を見つけることができる 利点: スタックに確保すると解放が簡単 ヒープの解放は大変 ガーベジコレクション等が必要

3 基本的な方針 「型」にもとづいて解析する 具体的には メモリに置かれる値の型を 「その値が関数からエスケープするか」 を表すフラグで拡張する
メモリに置かれる値の型を 「その値が関数からエスケープするか」 を表すフラグで拡張する 「関数からエスケープする」 = 関数から帰った後もアクセスされうる 関数の返り値またはその一部となる 関数のスコープ外の変数またはその一部に代入される など

4 エスケープフラグ: true = エスケープするかも
簡単な例 (1/4) エスケープフラグ: true = エスケープするかも false = 絶対エスケープしない let f x = let p = (3, 4) in (* p : (int × int)false *) let (a, b) = p in a + b in ... 組 p は関数 f から戻った後はアクセスできないので、 型 (int × int)false が与えられる = 絶対エスケープしない

5 簡単な例 (2/4) let f y = let g x = x + y in (* g : (int → int)true *) g
関数gのclosureは関数fから返されるので、 型(int → int)trueが与えられる = エスケープする

6 簡単な例(3/4) 関数 g の closure がエスケープするので、 g の自由変数である配列 a もエスケープする let f y =
let a = Array.create 5 0 in (* a : (int array)true *) let g x = x + a.(2) in (* g : (int → int)true *) g in ... 関数 g の closure がエスケープするので、 g の自由変数である配列 a もエスケープする

7 簡単な例 (4/4) let t = ref (0, 0) in let f () = let p = (1, 2) in (* p : (int × int)true *) t := p in ... 組 p は関数 f のスコープ外の領域に 代入されるので、型 (int × int)true となる = エスケープする

8 副作用 (代入) がない場合の エスケープの定義
関数の返り値はエスケープする 関数 closure がエスケープするなら 関数の自由変数もエスケープする Tuple がエスケープするなら その各要素もエスケープする 配列がエスケープするなら その各要素もエスケープする

9 副作用 (代入) がある場合 上手くいかない定義 「エスケープする領域に代入される値は エスケープする」 a はエスケープする
「エスケープする領域に代入される値は 　エスケープする」 a はエスケープする g : (int arraytrue) arraytrue let a = Array.create 1 0 in g.(0)  a a はエスケープしない? g : (int arrayfalse) arrayfalse let a = Array.create 1 0 in g.(0)  a

10 上手くいかない例 以下のコードは型検査をパスするが エスケープしないはずの値が エスケープしてしまう
以下のコードは型検査をパスするが エスケープしないはずの値が エスケープしてしまう f : (int arrayfalse) arrayfalse  int arrayfalse  unit let g = Array.create … in let rec h () = let a = Array.create … in f g a in h (); g.(0).(0) g はエスケープしない a もエスケープしない? もし f が次のような関数だったら let rec f g a = g.(0)  a

11 副作用 (代入) がある場合再考 案1: 代入される値は全てエスケープするとみなす “”の右側は全てエスケープするとみなす
案1: 代入される値は全てエスケープするとみなす “”の右側は全てエスケープするとみなす 案2: 生成された時の関数のスタックフレーム外に 参照が渡る値はエスケープするとみなす 関数の返り値のみならず 引数として使われた時点でエスケープするとみなす など…

12 型にもとづくエスケープ解析 の手順 (1/2) 対象言語 (MinCaml 等) の型を エスケープフラグで拡張する
何がエスケープして 何がエスケープしないのかを 型付け規則として定義する 型付け規則に従った型検査をパスすれば エスケープ解析が正しくなるように定義する (型付け規則の例は別紙参照)

13 型にもとづくエスケープ解析 の手順 (2/2) 目的のプログラムに対して型付け規則を適用し エスケープフラグに関する制約を抽出
目的のプログラムに対して型付け規則を適用し エスケープフラグに関する制約を抽出 型付け規則を「下から上に」当てはめていく この時点でフラグの値はまだ確定していない 反復法等によりフラグ間の制約を解消 とりあえず全てのフラグを false とする 制約に矛盾が生じる部分からフラグを true に変更 矛盾がなくなるまで II.を繰り返す (型付けの例は別紙参照)

14 共通課題 次のプログラム中で生成される 各tuple/array にエスケープフラグを付加せよ できる限り賢く解析せよ
講義と別紙資料で紹介した戦略よりも賢くできるはず 厳密なアルゴリズム/型付けは考慮せずともよい let a = Array.create 1 (1, 2) in let b = (3, 4) in let rec g p = p in let rec f () = let c = if (条件式) then a else Array.create 1 (g (5, 6)) in c.(0) <- b; c in f ()

15 コンパイラ係用選択課題 エスケープ解析を実装せよ。 副作用については保守的に実装してもよい 例: 代入はすべてエスケープとみなす

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

17 参考: 型にもとづく解析いろいろ リージョンベースメモリ管理 Dependent types Resource usage analysis
Benjamin C. Pierce, editor. Advanced Topics in Types and Programming Languages, Chapter 3. Dependent types 静的な配列境界検査 Resource usage analysis 計算資源（ファイル、ソケット等）が 正しく使用されることを保証 Information flow analysis 機密情報が外部に漏れないことを保証 その他たくさん