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

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

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

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

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

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

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

単純にコンパイルすると … 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 して 直ちにリターン このコードを再帰的に何度も実行していくと …

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

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

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

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

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

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

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

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

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

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

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” だった部分

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

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

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

λ 抽象・部分適用 λ 抽象： 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 をはさむことで完全適用にした

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

共通課題 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 )

共通課題 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)

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

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

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

課題の提出先と締め切り 提出先 : 締め切り : 2 週間後 (12/01) の午後 1 時 (JST) Subject: Report 6 – 例： Report 本文にも氏名と学籍番号を明記のこと 半角スペース 1 個ずつ  質問は ま で

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