コンパイラ演習
第 11 回
2007/12/13 小酒井 隆広 前田 俊行 山下 諒蔵 佐藤 春旗 大山 恵弘 佐藤 秀明 住井 英二郎今日の内容
エスケープ解析 メモリに置かれる値のうち、ヒープではなく スタックに確保できるものを見つける 利点： スタックに確保すると解放が簡単 ヒープの解放は大変 （garbage collection 等）基本的な方針
「型」 に基づいて解析する 具体的には、メモリに置かれる値の型を 「その値が関数からエスケープするか」 を表すフラグで拡張する 「関数からエスケープする」 ＝ 関数から返った後もアクセスされ得る 関数の返値またはその一部となる 関数のスコープ外の変数またはその一部に代入される etc...簡単な例 (1)
タプル p は関数 f から戻った後はアクセス できないので、型 (int * int)false が
与えられる （絶対にエスケープしない）
let f x =
let p = (3, 4) in
(* p : (int * int)false *) let (a, b) = p in
a + b
エスケープフラグ:
true = エスケープするかも false = 絶対エスケープしない
簡単な例 (2)
関数 g のクロージャは関数 f から返される ので、 型 (int -> int)true が与えられる （エスケープする）
let f y =
let g x = x + y in
(* g : (int -> int)true *) g
簡単な例 (3)
関数 g のクロージャがエスケープするので、
g の自由変数である a もエスケープする
let f () =
let a = Array.create 5 0 in (* a : (int array)true *)
let g x = x + a.(2) in
(* g : (int -> int)true *) g
簡単な例 (4)
タプル p は関数 f のスコープ外の領域に
代入されるので、型 (int * int)true となる （エスケープする）
let t = ref (0, 0) in let f () =
let p = (1, 2) in
(* p : (int * int)true *) t := p
副作用 （代入） がない場合の
エスケープの定義
関数の返値はエスケープする 関数クロージャがエスケープするなら、 その関数の自由変数もエスケープする タプルがエスケープするなら、 その各要素もエスケープする 配列がエスケープするなら、 その各要素もエスケープする副作用 （代入） がある場合
うまくいかない定義
「エスケープする領域に代入される値は、
うまくいかない例
以下のコードは型検査をパスするが、
x は h からエスケープしてしまう
let f a x = a.(0) <- x in
(* f : (int arrayfalse) arrayfalse -> int arrayfalse -> unit *)
let a = Array.create ... in let h () =
let x = Array.create ... in (* x : int arrayfalse *)
副作用 （代入） がある場合 再考
案 1： 代入される値 （“<-” の右側） はすべて エスケープするとみなす 案 2： 生成された時の関数のスタックフレーム外に 参照が渡る値はエスケープするとみなす つまり、関数の返値だけでなく、関数呼び出しの 引数として使われる値もエスケープするとみなす など…型に基づくエスケープ解析の手順
(1/2)
1. 対象言語 (MinCaml 等) の型を エスケープフラグで拡張する 2. 何がエスケープして 何がエスケープしない のかを、型付け規則として定義する 型付け規則に従った型検査をパスすれば エスケープ解析が正しくなるように定義する （型付け規則の例は別紙参照）型に基づくエスケープ解析の手順
(2/2)
3. 目的のプログラムに対し型付け規則を適用し、 エスケープフラグに関する制約を抽出 型付け規則を 「下から上に」 当てはめていく この時点では、フラグの値はまだ確定していない 4. 反復法等によりフラグ間の制約を解消 I. とりあえず全てのフラグを false とする II. 制約に矛盾が生じる部分のフラグを true に変更 III.矛盾がなくなるまで II を繰り返す共通課題
次ページのプログラム中で生成される 各タプル、配列に、エスケープフラグを 付加せよ できる限り賢く解析せよ 講義や別紙資料で紹介した戦略よりも賢くできるはず 厳密なアルゴリズム、型付けは考慮せずともよい共通課題
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 ()コンパイラ係用選択課題
エスケープ解析を自作コンパイラまたは MinCaml に実装せよ
副作用については保守的に実装してよい 例： 代入はすべてエスケープとみなす
課題の提出先と締め切り
提出先: [email protected] 締め切り: 4 週間後 (1/10) の午後 1 時 コンパイラ係用課題の締め切り: 2008年 2月 29日 Subject: Report 11 <学籍番号> 例： Report 11 71099 本文にも氏名と学籍番号を明記のこと 半角スペース 1 個ずつ 質問は [email protected] まで参考： 型に基づく解析いろいろ
リージョンベースメモリ管理
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/
