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

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

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

エスケープフラグ: 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 が与えられる = 絶対エスケープしない

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

簡単な例(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 もエスケープする

簡単な例 (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 となる = エスケープする

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

副作用 (代入) がある場合 上手くいかない定義 「エスケープする領域に代入される値は エスケープする」 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

上手くいかない例 以下のコードは型検査をパスするが エスケープしないはずの値が エスケープしてしまう 以下のコードは型検査をパスするが エスケープしないはずの値が エスケープしてしまう 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

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

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

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

共通課題 次のプログラム中で生成される 各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 ()

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

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

参考: 型にもとづく解析いろいろ リージョンベースメモリ管理 Dependent types Resource usage analysis Benjamin C. Pierce, editor. Advanced Topics in Types and Programming Languages, Chapter 3. Dependent types 静的な配列境界検査 http://cs-www.bu.edu/fac/hwxi/ Resource usage analysis 計算資源（ファイル、ソケット等）が 正しく使用されることを保証 http://www.kb.ecei.tohoku.ac.jp/~koba/publications.html Information flow analysis 機密情報が外部に漏れないことを保証 http://www.cs.cornell.edu/Info/People/jgm/lang-based-security/ その他たくさん