コンパイラ演習 第 6 回 (2011/11/17) 中村 晃一 野瀬 貴史 前田 俊行 秋山 茂樹 池尻 拓朗 鈴木 友博 渡邊 裕貴 潮田 資秀 小酒井 隆広 山下 諒蔵 佐藤 春旗 大山 恵弘 佐藤 秀明 住井 英二郎.

Presentation on theme: "コンパイラ演習 第 6 回 (2011/11/17) 中村 晃一 野瀬 貴史 前田 俊行 秋山 茂樹 池尻 拓朗 鈴木 友博 渡邊 裕貴 潮田 資秀 小酒井 隆広 山下 諒蔵 佐藤 春旗 大山 恵弘 佐藤 秀明 住井 英二郎."— Presentation transcript:

1 コンパイラ演習 第 6 回 (2011/11/17) 中村 晃一 野瀬 貴史 前田 俊行 秋山 茂樹 池尻 拓朗 鈴木 友博 渡邊 裕貴 潮田 資秀 小酒井 隆広 山下 諒蔵 佐藤 春旗 大山 恵弘 佐藤 秀明 住井 英二郎

2 今日の内容 実マシンコード生成 – アセンブリ生成 (emit.ml) – スタブ・ライブラリとのリンク 末尾呼出し最適化 – 関数呼出しからの効率的なリターン (emit.ml) – CPS 変換 種々の簡単な拡張 – MinCaml にない機能

3 実マシンコード生成 1. プログラム本体のアセンブリを生成 2. スタブ（初期化プログラム等）をつける 3. 入出力などのライブラリをリンク 4. アセンブラによりバイナリに変換し完成

4 ビルドの流れ MinCaml ソース MinCaml コンパイラ libmincaml.s SPARC アセンブリ自作 CPU アセンブリ 自作アセンブラ 自作リンカ 自作 CPU バイナリ SPARC バイナリ stub.c （自作スタブ） （自作ライブラリ）

5 アセンブリ生成 (emit.ml) main.ml の最後のステップ save/restore を具体的なストア / ロードに変 換 – スタックの状態を追跡 (stackmap, stackset) if 文の合流後は両方のスタックの共通部分をとる 規約に従うように関数呼出しを変換 – 引数を規定されたレジスタにセット (shuffle 関 数 ) – リターンアドレスの save/restore – スタックポインタの管理 条件分岐をジャンプに変換 – 分岐用・合流用のラベルを導入

6 外部ファイル スタブ (stub.c) – ヒープとスタックを確保したのち MinCaml のエントリポイントを呼び出すコー ド ライブラリ (libmincaml.s) – 外部関数が定義されている 入出力 配列生成 数値計算 自作 CPU 向けの外部ファイルも必要かも – アーキテクチャ次第

7 末尾呼出し最適化 末尾呼び出しの例 関数の最後の処理が call 基本的には関数呼出しの際には 戻り番地 (return address) を 保存しておかないといけない let rec fact x r = if x <= 1 then r else fact (x - 1) (r * x)

8 単純にコンパイルすると … save(R ret ) add R sp, 4, R sp call fact nop sub R sp, 4, R sp restore(R ret ) retl nop let rec fact x r = if x <= 1 then r else fact (x - 1) (r * x) 戻り番地 (R ret ) だけから なるフレームをメモリに構成 戻り番地を pop して 直ちにリターン このコードを再帰的に何度も実行していくと …

9 その結果 main 関数のフレーム R ret 戻り番地だけを保存した 無駄なフレームが積みあが る！ / ＼＿＿ _ ／ヽ ヽ ／ :::::::::::::::: ＼ つ. |,,- ‐‐ ‐‐ - ､.:::| わ | ､ _(o)_,: _(o)_, :::| ぁぁ. | ::<.::| あぁ ＼ /( [ 三 ] ) ヽ :: ／ああ ／｀ー‐ -- ‐‐ ―´ ＼ぁあ

10 何がいけなかったのか ? どうすればよいのか ? 問題の原因： 末尾呼出し直後の地点に 律義にリターンしている – 時間的に無駄 何もしない地点へわざわざリターン – 空間的にも無駄 いちいち戻り番地を退避 することがないなら 呼出し元に直接飛べばよい！ – コンパイラで末尾呼出しを認識し最適化する

11 末尾呼出し最適化の例 : before let f x =... (g 8) - 3... let g x = h (x + 1) let h x = x * 2 最適化する前は律義に g に 戻っているのでもったいな い

12 末尾呼出し最適化の例 : after let f x =... (g 8) - 3... let g x = h (x + 1) let h x = x * 2 大元の呼出し元 に 直接リターン

13 末尾呼出し最適化 末尾呼出し時の 無駄なジャンプ・退避を除去する cf. 自己末尾再帰 – 関数の最後の処理が自分自身の再帰呼び出し 末尾呼出し最適化により 単なるループに変換できる

14 call の直後にリターンする場合 call をただのジャンプにできる save(R ret ) add R sp, n, R sp bl L f sub R sp, n, R sp restore(R ret ) blr b L f

15 if の直後にリターンする場合 合流する必要はない – 下の例では L2 に飛ばずに blr する cmp c0, x, y bg c0, L1... then clause... b L2 L1:... else clause... L2: blr cmp c0, x, y bg c0, L1... then clause... blr L1:... else clause... blr

16 末尾呼出し最適化の実装 アセンブリに変換する際 変換中の式が末尾にあるかどうかを管理 (emit.ml) – Tail ： 末尾 末尾呼出し最適化を実行、または、 結果を返り値用のレジスタにセットしてリターン – NonTail( r ) ： 末尾でない 結果をレジスタ r にセット

17 CPS 変換 すべての call や if を末尾にしてしまう – 末尾でない関数適用 / 条件分岐の 「継続」 を生 成 「継続」 ≒ 「その後にすること」 – クロージャで表現する – すべての関数定義 / 関数適用に 仮引数 / 実引数として継続を追加 – 関数からのリターンは継続の呼出しになる α 変換および A 正規化の完了した K 正規形に対して行うと簡単

18 CPS 変換のイメージ (1/2) let rec f x = g x + 5 let rec g y = y + y この部分を実行する関数 （クロージャ） を 新たに導入し g の引数として渡すようにする

19 CPS 変換のイメージ (2/2) let rec f x cont = (* cont は継続 *) let rec f_cont z = (* 継続をつくる *) let result = z + 5 in cont result in g x f_cont let rec g y cont = (* cont は継続 *) let result = y + y in cont result g は実行が終わったら 引数にもらった継続 （クロージャ） を呼び出すことにより「リターン」 する 赤枠が f の “+5” だった部分

20 CPS 変換の利点 / 欠点 利点： 以降の処理が容易 – 関数呼び出し時の save/restore が不要 – 「リターンアドレス」 の概念が不要 – スタックも不要 欠点： クロージャが頻繁に生成 / 適用され る – 効率的なヒープ管理が必要 エスケープ解析 – スタックに確保してもよいクロージャが見つかる 世代別ガベージコレクション

21 種々の簡単な拡張 レコード・バリアント λ 抽象・部分適用

22 レコード・バリアント レコード： フィールドがアルファベット 順に 並んだタプルと見なす – { foo = 3; bar = 7 } ⇒ (7, 3) バリアント： コンストラクタを整数で表 し それを第 1 要素とするタプルにする – type 'a list = Nil | Cons of 'a * 'a list のとき、 Nil ⇒ (0) 、 Cons(x, y) ⇒ (1, x, y)

23 λ 抽象・部分適用 λ 抽象： let rec に置換 – fun x -> M ⇒ let rec f x = M in f f は fresh な名前 部分適用： let rec と完全適用に置換 – たとえば let rec f x y = x - y のとき、 f 3 ⇒ let rec g y = f 3 y in g g は fresh な名前 – g をはさむことで完全適用にした

24 共通課題 5 問中 3 問解けばよい

25 共通課題 1 以下のプログラムはどのようなアセンブリに コンパイルされるか、末尾呼び出し最適化を しない場合とする場合のそれぞれについて 説明せよ – ヒント： 末尾呼び出し最適化をする場合、手続 き型 言語でループを用いて書いた gcd と同じような アセンブリになる （はず） let rec gcd m n = if m <= 0 then n else if m <= n then gcd m (n - m) else gcd n (m - n) in print_int (gcd 21600 337500)

26 共通課題 2 以下のプログラムを手動で CPS 変換せよ – K 正規化はしてもしなくてもよい 余裕があれば、 CPS 変換した場合としなかった 場合でどのようなアセンブリにコンパイルされる か、両者を比較してみよう let rec ack x y = if x <= 0 then y + 1 else if y <= 0 then ack (x - 1) 1 else ack (x - 1) (ack x (y - 1)) in print_int (ack 3 10)

27 共通課題 3 MinCaml を CPS 変換を用いるように改造してみよ – K 正規形に対して変換するとよい 外部関数呼出しの扱いに注意

28 共通課題 4 「種々の簡単な拡張」 ( の一部 ) を用いる ML プログラムを書け 更にその ML プログラムを 既存の ML コンパイラが どのようにコンパイルするか調べて解説 せよ – 同程度以上に複雑な 他のプリミティブについて調べてもよい

29 共通課題 5 MinCaml を改造して λ 抽象・部分適用を実装せよ

30 課題の提出先と締め切り 提出先 : compiler-report-2011@yl.is.s.u-tokyo.ac.jp 締め切り : 2 週間後 (12/01) の午後 1 時 (JST) Subject: Report 6 – 例： Report 6 01099 本文にも氏名と学籍番号を明記のこと 半角スペース 1 個ずつ  質問は compiler-query-2011@yl.is.s.u-tokyo.ac.jp ま で

31 今後のトピック （変更の可能性あ り） 多相型 基礎的な最適化 レジスタ割付・スケジューリング 並列化・ループ最適化 VM ・バイトコードインタプリタ Garbage Collection