コンパイラ課題メモ

課題に関するメモ的な何か。

目次

  1. コンパイラ課題メモ
    1. 第1回
    2. 第2回
    3. 第3回
    4. 第4回
    5. 第5回
    6. 第6回
    7. 第7回
    8. 第8回
    9. 第9回
    10. 第10回
    11. 第11回
    12. 第12回
    13. コンパイラ係向け課題

第1回

第2回

   1 let rec f x = let y = 1 in x in
   2 let y = 2 in
   3 f y


   1 let rec f _ = f () in
   2 (Array.create 1 f).(0) <- f

第3回

第4回

第5回

第6回

   1 .section        ".rodata"
   2 .align  8
   3 .section        ".text"
   4 gcd.7:
   5         cmp     %i2, 0
   6         bg      ble_else.17
   7         nop
   8         mov     %i3, %i2
   9         retl
  10         nop
  11 ble_else.17:
  12         cmp     %i2, %i3
  13         bg      ble_else.18
  14         nop
  15         sub     %i3, %i2, %i3
  16         b       gcd.7                   ! 末尾再帰
  17         ! 末尾再帰しないなら上のb命令が
  18         !        add %i0, 4, %i0
  19         !        call   gcd.7
  20         !        sub %i0, 4, %i0
  21         !        retl
  22         ! という４文に置きかわる
  23         nop
  24 ble_else.18:
  25         sub     %i2, %i3, %i2
  26         mov     %i3, %o4
  27         mov     %i2, %i3
  28         mov     %o4, %i2
  29         b       gcd.7                   ! 末尾再帰
  30         ! 末尾再帰しないなら上のb命令が
  31         !        add %i0, 4, %i0
  32         !        call   gcd.7
  33         !        sub %i0, 4, %i0
  34         !        retl
  35         ! という４文に置きかわる
  36         nop
  37 .global min_caml_start
  38 min_caml_start:
  39         save    %sp, -112, %sp
  40         set     21600, %i2
  41         set     337500, %i3
  42         st      %o7, [%i0 + 4]
  43         call    gcd.7
  44         add     %i0, 8, %i0     ! delay slot
  45         sub     %i0, 8, %i0
  46         ld      [%i0 + 4], %o7
  47         st      %o7, [%i0 + 4]
  48         call    min_caml_print_int
  49         add     %i0, 8, %i0     ! delay slot
  50         sub     %i0, 8, %i0
  51         ld      [%i0 + 4], %o7
  52         ret
  53         restore


   1 let rec ack x y cont = 
   2         if x <= 0 then cont (y + 1)
   3         else if y <= 0 then ack (x - 1) 1 cont
   4         else ack x (y - 1) (fun result1 -> ack (x - 1) result1 cont)
   5 in ack 3 10 print_int


   1 type record = {foo : int; bar : int};;
   2 let record = {foo = 3; bar = 7} in
   3 let rec f x = x in
   4 let rec g x = x in
   5 print_int (f record.foo + g record.bar)

第7回

-- TakuyaKuwahara 2012-02-29 00:56:16

第8回

第9回

第10回

第11回

第12回

コンパイラ係向け課題

========
氏名　深堀　孔明
学籍番号　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関数）
            それを用いて、各色（レジスタ）の優先度を計算し、もっとも優先度が高いものを選択するようにしている。

プロセッサ・コンパイラ実験/課題メモ (最終更新日時 2012-02-29 01:08:18 更新者 TakuyaKuwahara)