x + 1

コンパイラ演習
第6回
(2011/11/17)
中村晃一野瀬貴史前田俊行
秋山茂樹池尻拓朗
鈴木友博渡邊裕貴
潮田資秀
小酒井隆広
山下諒蔵佐藤春旗
大山恵弘佐藤秀明
住井英二郎
今日の内容
• 実マシンコード生成
– アセンブリ生成 (emit.ml)
– スタブ・ライブラリとのリンク
• 末尾呼出し最適化
– 関数呼出しからの効率的なリターン (emit.ml)
– CPS 変換
• 種々の簡単な拡張
– MinCaml にない機能
実マシンコード生成
1. プログラム本体のアセンブリを生成
2. スタブ（初期化プログラム等）をつける
3. 入出力などのライブラリをリンク
4. アセンブラによりバイナリに変換し完成
ビルドの流れ
MinCaml ソース
MinCaml コンパイラ
SPARC アセンブリ
自作 CPU アセンブリ
stub.c
（自作スタブ）
libmincaml.s
（自作ライブラリ）
SPARC バイナリ
自作アセンブラ
自作リンカ
自作 CPU バイナリ
アセンブリ生成 (emit.ml)
• main.mlの最後のステップ
• save/restore を具体的なストア/ロードに変換
– スタックの状態を追跡 (stackmap, stackset)
• if 文の合流後は両方のスタックの共通部分をとる
• 規約に従うように関数呼出しを変換
– 引数を規定されたレジスタにセット (shuffle 関数)
– リターンアドレスの save/restore
– スタックポインタの管理
• 条件分岐をジャンプに変換
– 分岐用・合流用のラベルを導入
外部ファイル
• スタブ (stub.c)
– ヒープとスタックを確保したのち
MinCaml のエントリポイントを呼び出すコード
• ライブラリ (libmincaml.s)
– 外部関数が定義されている
• 入出力
• 配列生成
• 数値計算
• 自作 CPU 向けの外部ファイルも必要かも
– アーキテクチャ次第
末尾呼出し最適化
• 末尾呼び出しの例
let rec fact x r =
if x <= 1 then r
else fact (x - 1) (r * x)
• 関数の最後の処理が call
• 基本的には関数呼出しの際には
戻り番地(return address) を
保存しておかないといけない
単純にコンパイルすると…
let rec fact x r =
if x <= 1 then r
else fact (x - 1) (r * x)
save(Rret)
add Rsp, 4, Rsp
call fact
nop
sub Rsp, 4, Rsp
restore(Rret)
retl
nop
戻り番地(Rret)だけから
なるフレームをメモリに構成
戻り番地を pop して
直ちにリターン
このコードを再帰的に何度も実行していくと…
その結果
Rret
Rret
Rret
Rret
Rret
Rret
main 関数のフレーム
戻り番地だけを保存した
無駄なフレームが積みあがる！
/＼＿＿_／ヽ
ヽ
／
::::::::::::::::＼つ
. | ,,-‐‐
‐‐-､ .:::| わ
| ､_(o)_,: _(o)_, :::|ぁぁ
. |
::<
.::|あぁ
＼ /( [三] )ヽ ::／ああ
／｀ー‐--‐‐―´＼ぁあ
何がいけなかったのか?
どうすればよいのか?
• 問題の原因：末尾呼出し直後の地点に
律義にリターンしている
– 時間的に無駄
• 何もしない地点へわざわざリターン
– 空間的にも無駄
• いちいち戻り番地を退避
• することがないなら
呼出し元に直接飛べばよい！
– コンパイラで末尾呼出しを認識し最適化する
末尾呼出し最適化の例: before
let f x =
...
(g 8) - 3
...
let g x =
h (x + 1)
最適化する前は律義にgに
戻っているのでもったいない
let h x =
x * 2
末尾呼出し最適化の例: after
let f x =
...
(g 8) - 3
...
let g x =
h (x + 1)
大元の呼出し元に
直接リターン
let h x =
x * 2
末尾呼出し最適化
• 末尾呼出し時の
無駄なジャンプ・退避を除去する
• cf. 自己末尾再帰
– 関数の最後の処理が自分自身の再帰呼び出し
• 末尾呼出し最適化により
単なるループに変換できる
call の直後にリターンする場合
• call をただのジャンプにできる
save(Rret)
add Rsp, n, Rsp
bl Lf
sub Rsp, n, Rsp
restore(Rret)
blr
b Lf
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
この部分を実行する関数（クロージャ）を
新たに導入し
g の引数として渡すようにする
let rec g y = y + y
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
赤枠が f の “+5” だった部分
let rec g y cont = (* contは継続 *)
let result = y + y in cont result
g は実行が終わったら
引数にもらった継続（クロージャ）
を呼び出すことにより「リターン」する
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 21600 337500)
共通課題 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 を改造して
λ 抽象・部分適用を実装せよ
課題の提出先と締め切り
• 提出先: [email protected]
• 締め切り: 2 週間後 (12/01) の午後 1 時 (JST)
• Subject: Report 6 <学籍番号: 5 桁>
半角スペース 1 個ずつ
– 例： Report 6 01099
• 本文にも氏名と学籍番号を明記のこと
 質問は [email protected] まで
今後のトピック（変更の可能性あり）
•
•
•
•
•
•
多相型
基礎的な最適化
レジスタ割付・スケジューリング
並列化・ループ最適化
VM・バイトコードインタプリタ
Garbage Collection

Download Report