コンパイラ演習 第1回 (2011/10/06) 中村 晃一 野瀬 貴史 前田 俊行 秋山 茂樹 池尻 拓朗 鈴木 友博 渡邊 裕貴 潮田 資秀 小酒井 隆広 山下 諒蔵 佐藤 春旗 大山 恵弘 佐藤 秀明 住井 英二郎 プロセッサ・コンパイラ実験 全体の大目標 • 計算機システム を作る – 計算機システムが (ハードもソフトも) “black box” でないことを身をもって学ぶ プロセッサ・コンパイラ実験 全体の進め方 • 班 (4〜5人程度?) に分かれて進める – うち1人をコンパイラ係とする • 具体的には以下を作成する – 自作CPUの設計・実装 – 自作CPU向けのコンパイラ (クロスコンパイラ) – etc. • レイトレーシングプログラムを 正しく動作させることが条件 コンパイラ係の目標 • 自作CPU向けの コンパイラを実装する 演習の進め方 • 毎回講義を15～45分ほど行う – 対象言語: OCaml もどき – 記述言語: OCaml • あとは各自で演習してもらう – コンパイラを実装する、課題を解く等 • 講義資料等は以下に置いておきます – http://www.yl.is.s.u-tokyo.ac.jp /wiki/lectures/CompilerEnshu2011.ja お手本とするコンパイラ • 「美しい日本の ML コンパイラ」 (通称 MinCaml) • 作者: 住井 英二郎 – 対象言語: OCaml もどき – 記述言語: OCaml – 対象CPU: SPARC、PowerPC – URL: http://min-caml.sourceforge.net/ 講義内容 (変更の可能性あり) • • • • • • • • • • • • コンパイラの概要 (今回) K正規化、α変換、最適化 クロージャ変換 仮想マシンコード生成 レジスタ割り当て アセンブリ生成、末尾呼び出し最適化 ？？？？？？？？？？？？？？ ？？？？？？？？？？？？？？ ？？？？？？？？？？？？？？ ？？？？？？？？？？？？？？ ？？？？？？？？？？？？？？ ？？？？？？？？？？？？？？ 基礎編 応用編 課題について • 二種類の課題がある – 共通課題 • 全員が解くことを想定している課題 – コンパイラ係向け課題 • コンパイラ係が解くことを想定している課題 コンパイラ係以外の人の 単位取得条件 • 共通課題を 6 つ以上提出すること かつ • CPU担当教員の出す条件をクリアすること コンパイラ係の人の 単位取得条件 • 自作 CPU (またはシミュレータ) 上で レイトレーシングプログラムが完動すること – MinCaml を改造する形でもよい かつ • 共通課題を 6 つ以上提出すること かつ • コンパイラ係向け課題を 1 つ以上提出すること かつ • CPU担当教員の出す条件をクリアすること コンパイラの概要 コンパイラとは • ある言語のプログラムを 他の言語に翻訳するシステム – gcc • C アセンブリ – javac • Java JVM bytecode – ocamlc • OCaml OCaml VM bytecode – ocamlopt • OCaml アセンブリ – etc. コンパイルの例 アセンブリコード ソースコード let rec gcd m n = if m = 0 then n else if m <= n then gcd m (n - m) else gcd n (m - n) .section ".text" gcd.7: cmp %i2, 0 bne be_else.17 nop mov %i3, %i2 retl nop be_else.17: cmp %i2, %i3 bg ble_else.18 nop sub %i3, %i2, %i3 b gcd.7 nop ble_else.18: sub %i2, %i3, %o5 mov %i3, %i2 mov %o5, %i3 b gcd.7 nop コンパイラの難しいところ 言語間のギャップが大きい ソースコード • 変数 • 関数・クロージャ • 式・文 アセンブリコード • レジスタ・メモリ • ジャンプ・条件分岐 • CPU命令 解決法: ちょっとずつ変換する 概念図 ソースコード • 変数 • 関数・クロージャ • 式・文 中間言語2 • 変数 • ジャンプ・条件分岐 • CPU命令 中間言語1 クロージャ 変換 • 変数 • ジャンプ・条件分岐 • 式・文 仮想マシンコード 生成 レジスタ 割当て アセンブリ • レジスタ・メモリ • ジャンプ・条件分岐 • CPU命令 MinCaml ではこんな感じ (* main.ml *) let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f (Closure.f (iter !limit (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) MinCaml ではこんな感じ (* main.ml *) let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f (Closure.f 字句解析 (iter !limit (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) MinCaml ではこんな感じ (* main.ml *) let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f (Closure.f 構文解析 (iter !limit (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) MinCaml ではこんな感じ (* main.ml *) let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f (Closure.f 型検査 (iter !limit (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) MinCaml ではこんな感じ (* main.ml *) let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f (Closure.f K 正規化 (iter !limit (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) MinCaml ではこんな感じ (* main.ml *) let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f (Closure.f α 変換 (iter !limit (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) MinCaml ではこんな感じ (* main.ml *) let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f (Closure.f 最適化 (iter !limit (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) MinCaml ではこんな感じ (* main.ml *) let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f クロージャ (Closure.f (iter !limit 変換 (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) MinCaml ではこんな感じ (* main.ml *) let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f 仮想マシン (Closure.f (iter !limit コード生成 (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) MinCaml ではこんな感じ (* main.ml *) let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f レジスタ (Closure.f (iter !limit 割当て (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) MinCaml ではこんな感じ (* main.ml *) let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f アセンブリ (Closure.f (iter !limit 生成 (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) 字句解析・構文解析 • 字句解析 – 文字列をトークン (単語)の列に変換する • 構文解析 – トークン列を抽象構文木に変換する • MinCaml では ocamllex、 ocamlyacc を用いる – ML演習第4回参照 MinCaml の型検査 • 基本的には ML の型推論 – ML演習第 6 回参照 • ただし、以下の点に注意 – 推論の実装に reference を用いている – 未定義の変数があった場合に 「外部変数」とみなす – 型多相はサポートしていない K 正規化 • 計算途中の結果にも全て変数をつける – アセンブリに少し近づける – 評価順序が少し明確になる 1 + 2 - 3 + 4 - 5 let let let let d a b c d = = = = 1 a b c + + – 2 3 4 5 in in in in α 変換 • 変数の名前をつけかえる • 全ての変数が互いに異なる名前をもつようにする – 最適化やその後の処理が楽になる let x = 1 in let x = x + 1 in x let x0 = 1 in let x1 = x0 + 1 in x1 最適化 • MinCaml では 以下の 3 つの処理を繰り返し行っている – インライン展開 – 定数たたみこみ – 不要定義削除 • 他にも最適化の手法はたくさんあるので 自分で色々試してみるとよい クロージャ変換 • ネストした関数定義を平らにする 超大雑把な図式 let f a = let g b = a + b in g 3 let g a b = a + b let f a = g a 3 実際には MinCaml では a はクロージャを介して 渡される 仮想マシンコード生成 • よりアセンブリに近い形式に変換する • 実際のアセンブリとの違い – レジスタは無限個ある – if 式や関数呼出しがある – タプルやクロージャ、配列の操作を メモリロード・ストア命令の組み合わせに変換する レジスタ割当て • 仮想マシンコードのレジスタに 実際のレジスタを割り当てる – MinCaml ではそれ程複雑なことはしていない • そこそこの速さ & そこそこの易しさ – MinCaml で性能を出すためには ここの改造は必須の予感 アセンブリ生成 • 実際のアセンブリを出力する – ここでようやく関数呼出しや if 式を 実際の命令に変換している • 加えて末尾呼出しの最適化をしている – ループ最適化を頑張りたい場合には ここではちょっと遅いかも? 課題 共通課題 どれかを解けばよい • 今回は全3問のうち 全部解いてもよい – もちろん 共通課題 その1 • MinCaml を改造し Syntax.t や KNormal.t などの 値を出力できるようにせよ • 出力の形式や方法は問わないが真面目にやれば デバッグのとき役に立つかも • 例えば以下のような感じ 入力 (* test/fib.ml *) let rec fib n = if n <= 1 then 1 else fib (n-1) + fib (n-2) in print_int(fib 30) 出力 … If LE Var(n) Int(1) Int(1) Add … 共通課題 その2 • MinCaml を改造し パースエラー時および型エラー時に どの箇所 (例: 行番号や列番号等) に問題があったかを表示するようにせよ 共通課題 その3 • MinCaml を改造し 出力されたアセンブリのどの命令が 入力されたソースのどの式に対応するかを 判別できるようにせよ – 例えば、対応を表すファイルを コンパイル時に生成するなど 課題の提出先と締切 • 提出先: [email protected] – 質問等は [email protected] まで • 締切: 2 週間後 (10/20) の午後 1 時（JST) – コンパイラ係向け課題の締切は2012年2月28日 • Subject は Report <課題番号> <学籍番号:5桁> とすること – 例: Report 1 11099 • 間にスペースを 1 つずついれること • メールの本文にも氏名と学籍番号を明記すること – 正常に受理されれば 通知メールが届くはずなので確認してください 課題提出についての注意 • プログラムだけでなく 説明・実行例・考察なども書くこと • 基本的にはメール本文に解答を記述すること – ただし、多くのソースコードを 送る必要がある場合には tar などで固めて提出してよい 謝辞 • 本講義では、昨年度までの講義を担当された 以下の方々によって書かれた資料の多くを再 利用させていただいております。 ここに感謝いたします。 住井英二郎先生、大山恵弘先生、 佐藤秀明氏、山下諒蔵氏、佐藤春旗氏、 小酒井隆広氏、潮田資秀氏、 鈴木友博氏、渡邊裕貴氏、 秋山 茂樹氏、池尻 拓朗氏
© Copyright 2024 ExpyDoc
