##master-page:LecturePageTemplate #format wiki #language ja = コンパイラ課題メモ = 課題に関するメモ的な何か。 <> == 第1回 == == 第2回 == * 共通課題(1)スライドに載ってる式をK正規化してα変換。さらにA正規化 * KNormal.fの返り値がK正規化されてアルファ変換された式になっているので、それをもとにすると間違いにくいかもしれません。 * 共通課題(2)共通部分式除去を実装 * [[https://github.com/furaga/cpu/blob/74540950f776a53674e4cf586e9c99c6a093780b/compiler/cse.ml|これ]]。バグってるかもしれないのでご注意を。 * 共通課題(3)インライン展開するときにα変換や回数制限がないと困る例をあげよ * アルファ変換しないと、関数内のローカル変数と実引数の変数名がかぶったときとかにおかしくなるので、例えば以下のようなコードがバグると思う。 {{{#!highlight ocaml let rec f x = let y = 1 in x in let y = 2 in f y }}} * インライン展開が終わらない例はたとえば以下のようなもの。畳み込みが行われる限り、多分これが最小。 {{{#!highlight ocaml let rec f _ = f () in (Array.create 1 f).(0) <- f }}} == 第3回 == == 第4回 == * 共通課題(1)自作CPUを含めて3つ以上のアーキテクチャについて関数呼び出し規約を比較して論じよ * コミュ力があればできる。僕は出来なかった。 == 第5回 == == 第6回 == * 共通課題(1)スライドに載ってるコードをコンパイルした際の末尾呼び出し最適化の有無による違いを述べよ * 改造してないmin-camlでコンパイルするとこんな感じ。末尾再帰しないとジャンプ命令(b)が４命令に増える。 {{{#!highlight ocaml .section ".rodata" .align 8 .section ".text" gcd.7: cmp %i2, 0 bg ble_else.17 nop mov %i3, %i2 retl nop ble_else.17: cmp %i2, %i3 bg ble_else.18 nop sub %i3, %i2, %i3 b gcd.7 ! 末尾再帰 ! 末尾再帰しないなら上のb命令が ! add %i0, 4, %i0 ! call gcd.7 ! sub %i0, 4, %i0 ! retl ! という４文に置きかわる nop ble_else.18: sub %i2, %i3, %i2 mov %i3, %o4 mov %i2, %i3 mov %o4, %i2 b gcd.7 ! 末尾再帰 ! 末尾再帰しないなら上のb命令が ! add %i0, 4, %i0 ! call gcd.7 ! sub %i0, 4, %i0 ! retl ! という４文に置きかわる nop .global min_caml_start min_caml_start: save %sp, -112, %sp set 21600, %i2 set 337500, %i3 st %o7, [%i0 + 4] call gcd.7 add %i0, 8, %i0 ! delay slot sub %i0, 8, %i0 ld [%i0 + 4], %o7 st %o7, [%i0 + 4] call min_caml_print_int add %i0, 8, %i0 ! delay slot sub %i0, 8, %i0 ld [%i0 + 4], %o7 ret restore }}} * 共通課題(2)スライドに載ってるコードをCPS変換せよ * こんな感じかな {{{#!highlight ocaml let rec ack x y cont = if x <= 0 then cont (y + 1) else if y <= 0 then ack (x - 1) 1 cont else ack x (y - 1) (fun result1 -> ack (x - 1) result1 cont) in ack 3 10 print_int }}} * 共通課題(4)種々の簡単な拡張を用いるMLプログラムを書き、それを既存のMLコンパイラがどうコンパイルするか調べよ * こんな感じのプログラムからocamloptでx86のアセンブリコードを生成（たしか-Sをつけるとできる）してにらめっこ。 {{{#!highlight ocaml type record = {foo : int; bar : int};; let record = {foo = 3; bar = 7} in let rec f x = x in let rec g x = x in print_int (f record.foo + g record.bar) }}} * 以下みたいな感じにレコードのポインタと値がメモリ上に割り当てられてるっぽい。 * record = MEM[camlRecord__3@GOTPCREL + %rip] * record.foo = MEM[MEM[camlRecord__3@GOTPCREL + %rip]] * record.bar = MEM[8 + MEM[camlRecord__3@GOTPCREL + %rip]] 　 == 第7回 == * 割合楽な課題だと思います。オススメ（by TakuyaKuwahara） * 軽く方針？的なものを書いとく。 * オーバーロードするときは、KNormalの構文木をわざわざいじらないで済むようにすると良い。以下は整数・浮動小数問わず使える+演算子の例。 * [流れ] * (1)パース時、"1.0 + 2.0"、"1 + 2" のような構文を両方受け付けるようにし、これらをまとめて一つのデータ表現Add(*,*)とする * (2)Typingモジュールで、型チェッカはAddの引数の方が'''揃っているか'''だけ確認する。（現状では「両方とも整数型か？」を確認している） * (3)KNormalモジュールで、Addの型を確認して整数ならAdd、浮動小数ならFAddに変換してしまう。 * 型で分岐する方法は、私はあらかじめSyntaxモジュールのAddのフィールドを拡張して型を表すフィールドを用意（Letを参照）し、Typingモジュールで推論された型をそこに入れておいた。 * あと、試してないけど普通にAddの引数がIntかFloatかで分岐してもいけると思う。 * 上でもちょっと触れたけど、例えば追加する演算子を「ビットの反転にも数のNegateにも使える演算子~」とかにすると、パーサに新たな識別子導入・型推論規則追加・ビット反転をKNormal型でどう表すかなどの新たな問題が生じるので、そこをうまく解決できるものにしないと改造しなければならないモジュールが増えかねない。 * 最低限改造しなきゃならないのはSyntax・Parser・Typing・KNormal。上でも述べたようにSyntaxはそのままでもいけるかも？ * というより、もしSyntaxそのままでいけるならParserもいじらないで行けそうな気がします。 -- TakuyaKuwahara <> == 第8回 == * 共通課題(2)スライドの冗長性除去の方法のコーナーケースと改善案 * 「コンパイラの構成と最適化」第2版のp310, p311の内容そのまま。 == 第9回 == == 第10回 == == 第11回 == == 第12回 == == コンパイラ係向け課題 == * グラフ彩色によるレジスタ割り当てを実装せよ。（第9回より） * ただの捨て問ですが、がんばって[[https://github.com/furaga/cpu/tree/master/compiler|実装しました]]。読めるものならどうぞ( * クロージャがないときのみ実行する、再帰関数による後退辺を無視、といくらか簡略化した実装となっています。 * 事前にクロージャをできるかぎり駆逐しておかないとレイトレとかでは使えないのでご注意を。 * グラフ彩色に関係あるのは * [[https://github.com/furaga/cpu/blob/master/compiler/block.ml|block.ml]] * 主にAsm.progをBlock.progに変換。その他補助関数置き場 * [[https://github.com/furaga/cpu/blob/master/compiler/toAsm.ml|toAsm.ml]] * Block.progをAsm.progに逆変換 * [[https://github.com/furaga/cpu/blob/master/compiler/liveness.ml|liveness.ml]] * 生存解析 * [[https://github.com/furaga/cpu/blob/master/compiler/coloring.ml|coloring.ml]] * グラフ彩色 * [[https://github.com/furaga/cpu/blob/master/compiler/regAllocWithColoring.ml|regAllocWithColoring.ml]] * 彩色しつつレジスタ割り当て * 一応提出したレポート全文を載せてみる。[8]のところは僕の考えた最強のアイディア(笑)なので多分あまり妥当ではない {{{ ======== 氏名　深堀　孔明 学籍番号　05-111020 ======== コンパイラ向け課題 ============ 彩色によるレジスタ割り当てに関するファイルは block.ml（主にAsm.progをBlock.progに変換。その他補助関数置き場） toAsm.ml（Block.progをAsm.progに逆変換） liveness.ml（生存解析） coloring.ml（グラフ彩色） regAllocWithColoring.ml（彩色しつつレジスタ割り当て） の5つ。 レジスタ割り当てのアルゴリズムは以下の通り(「最新コンパイラ構成技法」11.4の擬似コードに準拠)。生存区間分割は行っていない。 1. Virtual.f関数で生成されたプログラム（Asm.prog型）を基本ブロック単位のプログラム（Block.prog型）に変形する(Block.f関数) 2. 各関数毎に以下の操作を実行して彩色をする。その結果をもとに実際にレジスタを割り当てる。最終的にはAsm.progに逆変換されたものが出力される。 ただし関数呼び出しのとき、その関数内で値が変わらないレジスタは退避しないようにしている。（RegAllocWithColoring.f関数） （以下、関数ごとの処理） 3. 基本ブロック単位で生存解析。各ブロックの出口生存・入口生存を求める（Liveness.analysis関数）。 ただし基本ブロック単位でのgen, kill集合は事前にBlock.set_def_use関数の中で求められている。 4. 各ブロックの出口生存の情報などを元に干渉グラフを作成（Coloring.Build関数） （5, 6, 7はColoring.main関数のwhileループ内の各関数で処理） 5. 干渉グラフから次数がレジスタ数未満のノード（変数）を取り除いてスタック（Coloring.select_stack）に積んでいく。すべてのノードを取り去るまで５を繰り返す。 ノードの選び方については下記。 6. レジスタ数以上の次数のノードしか残ってないなら、適当に一個選んでそれを干渉グラフから取り除いてスタックに積む。 選び方については下記。 7. 5, 6のとき、Mov命令、FMov命令のオペランドになるノードがあったら、可能な限り合併する。 合併したノードは一方をスタックに積み、他方は専用のストレージ（Coloring.coalesced_nodes）に入れる。 8. ノードを全部取り去ったら、スタックからノードを一個ずつ取り出していき、隣り合うノードとは別の色（レジスタ）を割り当てていく。（Coloring.assign_colors関数） 色の選び方は下記。 9. Coloring.coalesced_nodesから一個ずつノードを取り出していき、対応するノード（Mov, FMov命令のもう一方のオペランド）と同じ色を割り当てる 10. 8, 9で割り当てられないノードがあったら、スピルする。 具体的には、 ① 割り当てられなかったすべてのノードについて、そのノードが定義・使用される各命令の直後・直前にそれぞれSave, Restore命令を挿入する。 ② ①で変形したプログラムに対して3以降を実行する。 上の5・6・8についてはノードないし色の選択に自由度があるが、以下のように選択している。 [5] 5で干渉グラフから取り去られる時期が遅いものほどColoring.assign_colors関数で先に色が割り当てられる。 また、仮引数や関数呼び出しの引数・返り値はできるだけ優先されて色が割り当てられるべきである。 そこで、 ① ②～④以外のノード ② 関数呼び出しの返り値 ③ 関数呼び出しの実引数 ④ 仮引数 という順番で選ぶことにしている。（Coloring.choose_simplify_node関数） [6] 6で選ばれる時期が早いノードほど優先的にスピルされる。 そこで「コンパイラの構成と最適化」p423の[Chai82]の方法に準拠して、 （そのノードが定義・使用される命令数）/ （次数） が最小となるノードを先に選ぶようにしている。（Coloring.choose_spill_node関数） [8] 8で選ばれる色については、例えば「関数呼び出しのとき、実引数は仮引数と同じ色にしたい」などといった要望がありうる。 そこで、Coloring.wish_envというストレージを用意して、 この変数はこのレジスタ（変数）と同じにしたい（Target） この変数はこのレジスタ（変数）とは違うものにしたい（Avoid） という要望を格納しておき（Coloring.set_wish_env_in_call関数） それを用いて、各色（レジスタ）の優先度を計算し、もっとも優先度が高いものを選択するようにしている。 }}}