コンパイラ演習第 11 回 2006/1/19 大山恵弘佐藤秀明今回の内容バリアント / レコード表現方法型付けパターンマッチ型付け switch 文への変換簡単な最適化マッチング漏れ以降のフェーズでの処理発展 exhaustivenessinformation の利用パター

Size: px

Start display at page:

Download "コンパイラ演習第 11 回 2006/1/19 大山恵弘佐藤秀明今回の内容バリアント / レコード表現方法型付けパターンマッチ型付け switch 文への変換簡単な最適化マッチング漏れ以降のフェーズでの処理発展 exhaustivenessinformation の利用パター"

ひろきえいさか
4 years ago
Views:

1 コンパイラ演習第 11 回 2006/1/19 大山恵弘佐藤秀明今回の内容バリアント / レコード表現方法型付けパターンマッチ型付け switch 文への変換簡単な最適化マッチング漏れ以降のフェーズでの処理発展 exhaustivenessinformation の利用パターン式の拡張バリアント / レコードバリアントのメモリレイアウト先頭にタグを追加したタプルのように配置タグ名は整数にエンコード異なる type のタグは同じ整数を使用してもよい要素数は可変 type t = A of string * int B C of string A 0 B 1 C 2 (0, str1, 13) または (1) または (2, str2 ) またはレコードのメモリレイアウトラベル名でソートしたタプルのように配置 type s = {foo: string; bar: int; baz: float} ソート type s = {bar: int; baz: float; foo: string} (3, 4.22, "hoge") 中間コード上での表現新たにプリミティブを追加バリアント : 生成 / タグ名取得 / 要素取得レコード : 生成 / 要素取得既存のプリミティブに吸収してもよい損をすることもあるかえって実装が大変最適化の精度が落ちる実装方法は各自の判断に任せます 1

2 型付けタグ名 / ラベル名と型情報との関連を管理外部関数としてまとめておくとよいタグ名 / ラベル名から型は一意に決定複数の type で同じ名が使用される場合はエラーパターンマッチ type t = A of string * int B C of string TagEnv(A) = (t, [string; int]) TagEnv(B) = (t, []) TagEnv(C) = (t, [string]) type s = {bar: int; baz: float; foo: string} LabelEnv(bar) = LabelEnv(baz) = LabelEnv(foo) = (s, [bar int; baz float; foo string]) パターン式の導入基本的な定義拡張は後述 p ::= _ c x (p 1,, p n ) c p {l 1 =p 1 ; ; l n =p n } ( パターン式 ) ( ワイルドパターン ) ( 定数パターン ) ( 変数パターン ) ( タプルパターン ) ( バリアントパターン ) ( レコードパターン ) パターン式の型付け (1/2) 同じ名前の変数はパターン式の中に 2 回以上出現できない型システムで保証すると楽 Γ - p : τ, (B) Γ: 前提となる型環境 p: 型付けするパターン式 τ: p の型 B: p の中で束縛される変数の型環境パターン式の型付け (2/2) match 文の導入 ( 変数パターン ) Γ - x : τ, (x : τ) ( タプルパターン ) Γ - p 1 : τ 1, (B 1 ) Γ - p n : τ n, (B n ) for all i j, varname(b i ) varname(b j ) = 0 Γ - (p 1,, p n ) : τ 1 τ n, (B 1,, B n ) タプルの各要素で束縛された変数の名前が重複していないことを確認パターン式で束縛された変数の型環境基本的な定義拡張は後述 e ::= p 1 -> e 1 p n -> e n ( 式 ) ( パターンマッチ ) 2

3 match 文の型付けパターン式が束縛した変数の型環境を利用 Γ - e : τ Γ - p 1 : τ, (B 1 ) Γ, B 1 - e 1 : τ' Γ - p n : τ, (B n ) Γ, B n - e n : τ' Γ - p 1 ->e 1 p n ->e n : τ' switch 文への変換 match 文を低レベルなプリミティブに分解定数とのマッチング switch 変数束縛 let 一見うまくいきそうだが e ::= switch e c 1 -> e 1 c n -> e n _ -> e' ( 式 ) (switch) ナイーブに変換すると (1, 2, v, 4) -> e 1 (_, _, _, _) -> e 2 eror ならば e 2 に実行が移ることをどう表現するか? 処理の巻き戻し, x 3,x 4 switch x 1 1 -> (switch x 2 2 -> let v = x 3 in (switch x 4 4 -> e 1 _ -> error) _ -> error) _ -> e 2 いろいろな案マッチングの成否を option 型で表現して返す matche 1 Success(result)->result Failure->e 2 バリアントの生成 / 展開を毎回行うコストマッチングの失敗を例外として処理 trye 1 MatchFailure->e 2 例外処理によるオーバヘッド増加 eror の後にすることを継続として渡すクロージャ作成 / 関数呼び出しが重い eror の後にすることをインライン展開 eror が複数存在するときはコード量爆発最適化のフェーズでやるべきことかも解決策 : 専用プリミティブの追加 fail_match マッチングに失敗 e 1 e 2 e 1 の評価中 fail_match に到達したら e 2 の評価にジャンプ手続き型的な挙動を表現大域的脱出みたいなものただのジャンプだから軽い, x 3,x 4 (switch x 1 1 -> (switch x 2 2 -> let v = x 3 in (switch x 4 4 -> e 1 e 2 バリアント / レコードの処理タプル同様に展開して各要素をマッチングバリアントの場合はタグも展開してマッチングタグは整数定数と同じように扱える {a=1; b=2} -> e 1 {a=2; b=3} -> e 2 let (a, b) = fields(e) in switch a 1 -> (switch b 2 -> e 1 2 -> _ -> fail_match A(1, 2) -> e 1 B -> e 2 let t = tag(e) in switch t A -> ) = fields(e) in (switch x1 ) B -> e 2 _ -> fail_match 3

4 簡単なマッチング最適化 (1/2) 先頭パターンから定数が連続するとき連続する定数の種類ごとにまとめてマッチング定数が連続する部分の候補に結局マッチしなかったらそれ以降の候補にジャンプ ( 1, 8 ) -> e 1 ( 2, _ ) -> e 2 ( 1, 10 ) -> e 3 ( v, _) -> e 4 (switch x 1 1 -> (switch x 2 8 -> e > e 3 2 -> e 2 let v = x 1 in e 4 簡単なマッチング最適化 (2/2) 先頭パターンから同じ名前の変数が連続するときまとめて変数束縛連続するのがワイルドパターンなら束縛すら不要 ( v, 8 ) -> e 1 ( v, 10 ) -> e 2 ( 1, _) -> e 3 (let v = x 1 in switch x 2 8 -> e > e 2 switch x 1 1 -> e 3 _ -> fail_match マッチング漏れで捕捉されない fail_match = マッチするパターンがない場合対処法の例コンパイル時に警告だけ表示実行時の異常終了を実現するしくみが必要例外処理の枠組みで対処してもよいマッチング漏れがあればコンパイルを通さない以降の fail_match の扱い生きている変数 FV(fail_match)=( 以降の処理で生きている変数 ) スタック / レジスタ割り当ての状態 fail_match に到達したら破棄してよい次の処理を追跡する前に状態を巻き戻すアセンブリ生成その後に実行するコードへジャンプ switch のアセンブリ生成 case の数による 2 3 個程度なら if-then-else の連鎖でよいそれ以上ならジャンプテーブルを作成 switch x 0 -> e 0 1 -> e 1 2 -> e 2 mul x, 4, y ld [table+y], z b z nop table:.word label_e0.word label_e1.word label_e2 label_e0: (e 0 の処理 ) label_e1: (e 1 の処理 ) label_e2: (e 2 の処理 ) 発展 : exhaustiveness information 型情報やマッチングの文脈からいろいろなことが分かるマッチングが必ず成功するパターンマッチングが必ず失敗するパターン絶対に使用されないパターン評価結果を変えない判定順序入れ替え行 : 各マッチング候補間の判定順序列 : パターン中の各要素間の判定順序コンパイル時に活用可能コード最適化冗長 / 不完全な match 式について警告を出す 4

5 コード最適化の例 (1/3) 最適化しないと match x 0, y 0 [], _ -> 1 _, [] -> 2 _::_, _::_ -> 3 リストは [] (::) をタグにもつバリアントとみなす (switch x ( (switch y [] -> 2 (switch x (::) -> (switch y ) コード最適化の例 (2/3) match 文の第 2 第 3 パターンを入れ替え (switch x (::) -> (switch y (switch y [] -> 2 絶対に使われないパターンを削除 (switch x (::) -> (switch y ) (switch y [] -> 2) コード最適化の例 (3/3) 冗長なマッチング判定を削除 (switch x _ -> (switch y ) 2 サイズの小さい式をインライン展開 (switch x _ -> (switch y _ -> 2)) 2 不要なを除去 switch x _ -> (switch y _ -> 2) 発展 : パターン式の拡張 p 1. p n p 1,.,p n はすべて同じ型 / 変数束縛を持つ型システムで保証するとよい pwhene e が不成立なら fail_match p 1 asp 2 letp=e letrecfp 1.p n =e など最適化の適用例 : 最大反復回数を定め変化がなくなるまで各フェーズを反復共通課題次の match 文を switch 文に変換せよ最良と思われる変換結果を提出せよ最良の定義は各自で設定すること処理の巻き戻しをどう表現するかは自由 (_, A(4)) -> e 1 (_, A(5)) -> e 2 (1, B) -> e 3 (3, B) -> e 4 (1, A(2)) -> e 5 (1, A(x)) -> e 6 (y, _) -> e 7 コンパイラ係用選択課題パターンマッチを自作コンパイラに実装せよ以下のパターンを扱えるようにすることワイルドパターン定数パターン変数パターンバリアントパターンマッチング漏れに対処することその他の実装方針は自由に決めてよいただし第 2 要素の持ちうるタグは A と B のみ 5

6 課題の提出先と締め切り課題の提出についての注意提出先共通課題の締め切り : 2 週間後 (2/2) の午後 1 時コンパイラ係用課題の締め切り : 2006 年 3 月 31 日 Subject:report11< 学籍番号 >< アカウント > 本文にも氏名と学籍番号を明記のことプログラムだけでなく説明考察感想なども書くこと基本的にはメールの本文に解答を記述多くのソースを送る必要がある課題ではソースを tar ファイルなどに固めてメールに添付のこと参考文献 CamlLight でのパターンマッチ実装法 TheZINCexperiment:aneconomicalimplementation ofthemllanguage htp://pauilac.inria.fr/~xleroy/publi/zinc.ps.gz OCaml が採用したパターンマッチ最適化の手法 OptimizingPatern-Matching htp://pauilac.inria.fr/~maranget/papers/opt-pat.ps.gz パターンマッチ最適化の heuristics WhenDoMatch-compilationHeuristicsMater? htp:// 6

今回の内容エスケープ解析メモリに置かれる値のうちヒープではなくスタックに alocate できるものを発見 Garbagecolection の負荷を軽減 JavaSE6 が採用 2006 年夏にリリース予定 [ 参考 ] リージョン推論静的メモリ管理の一般的枠組み本講義では MLKit[

今回の内容エスケープ解析メモリに置かれる値のうちヒープではなくスタックに alocate できるものを発見 Garbagecolection の負荷を軽減 JavaSE6 が採用 2006 年夏にリリース予定 [ 参考 ] リージョン推論静的メモリ管理の一般的枠組み本講義では MLKit[ コンパイラ演習第 12 回 2006/1/26 大山恵弘佐藤秀明今回の内容エスケープ解析メモリに置かれる値のうちヒープではなくスタックに alocate できるものを発見 Garbagecolection の負荷を軽減 JavaSE6 が採用 2006 年夏にリリース予定 [ 参考 ] リージョン推論静的メモリ管理の一般的枠組み本講義では MLKit[Tofteetal.] をもとに説明します