情報科学実験II資料 (6)
Register割り当て + 抽象機械コード生成

田浦

19/11/98

抽象機械コード生成の概要

Closure変換後, 各CPS関数は自由変数を持たない. 全ての変数はその関 数の引数であるか, その関数内のprimitiveで束縛された変数である. 今や関 数は, parameterを所定のregisterに受けとり, 一連のprimitiveを実行した後, 最後にAPPによって他の場所に制御を移すだけのものと考えることができる. 例えば,

(define (f x)
  (+ x (g x)))
は, CPS変換後,
[f (c x) 
   (FIXS [(k (r) (+-two [x r] [v2] [(APPB c (v2))]))] 
     (APPF g (k x)))]
となり, これはclosure変換によって,
(f: (f c x) 
    (FIXS [(k: (k r) 
               (rref [k 2] [x]
                  [(+-two [x r] [v]
                     [(rref [k 1] [c]
                        [(rref [c 0] [c']
                           [(APPB c' (c v))])])])]))]
      (stack [c (label k:) c x] [k]
         [(rref [(label g) 0] [g]
            [(rref [g 0] [g']
               [(APPF g' (g k x))])])])))
となる.(注) もはや, kが, fの内部 で定義されていたこと(つまり, fの中で定義される変数を使っているこ と)は忘れてよい. それらは明示的に, kというclosureから取り出され ているのである. さらにfにとっては, closure変換以前はFIXSという魔 法のoperatorによって作られていた関数kも, もはやfのbody部で stackという命令によって作られるただのrecordに過ぎなくなっている. したがってコード生成器は, 各CPS関数を独立した関数として, 内部の FIXを無視してコードを生成すれば良いことになる.

Register割り当て

抽象機械コード生成において行なう, 唯一の複雑な仕事はregister割り当てで ある. 各変数がどのregisterにあるか(register map, 以下M)を覚えておき ながら, CLO式を再帰的にたどっていく. ある変数の使用が現れたら, その変 数に割り当てられているregisterをMから求めてコードを生成する. その後 その変数が今後使用されていないとわかれば, Mからそれを取り除く. また, ある変数を束縛する演算が現れたら, その場で空いているregisterを見つけ, そのmappingを付け加えた新しいregister mapを以下の命令に渡す. 以下では 簡単のため, CLOの一つの変数に対してレジスタを1つ割り当てるものとする. 後の節で, 16 bit tex2html_wrap_inline350 32 bit問題に対処 する.

例えば上で, f:のコード生成を考えよう. 上でも述べたように内部の FIXSは別途考えれば良く, 今は無視して良い. また, 各式の右にそれぞ れの式内で使われている変数(つまり自由変数)を列挙した.

(f: (f c x)                            |
    (stack [c (label k:) c x] [k]      |    c, x
       [(rref [(label g) 0] [g]        | k,    x
          [(rref [g 0] [g']            | k,    x, g
             [(APPF g' (g k x))])])])) | k,    x, g, g'
最初, Mはconventionにより, register iに第i引数を格納しているとす る. つまり初期状態では, Mは,
M = (f, c, x, tex2html_wrap_inline362 )
となっている(Xは空きを表す. このlistの長さは使用可能なregisterの数に 依存する).

最初の命令のコード生成をはじめる前に, その命令の自由変数が{c, x}であることを使って, Mからfを取り除いておく. 結果としてMは 以下のような状態になる.

(X, c, x, tex2html_wrap_inline362 ).
この状態で,
(stack [c (label k:) c x] [k] ...)
のコード生成をする. オペランドである, (label k:), c, xをどのよう にアクセスするかはわかっている. (label k:)は定数で, c, xは それぞれ, レジスタr1, r2に載っている. 後はkに対して空いて いるregisterを割り当てれば良く, 今, r1を割り当てたとする( r1は現在cが割り当てられているが以降では使用されないので, kのために使用可能である. 詳細は後述).

まとめると,

(stack [c (label k:) c x] [k] ... )
に対しては,
(stack r1 (label k:) r1 r2 r1)
という抽象機械命令を出す. そしてkr1に割り当てられたこと を反映すべく, Mを以下のように更新する:
M = (X, k, x, tex2html_wrap_inline362 ).

Register割当のstrategy: Register Targetting

  このようにして再帰的に式をたどりながらコードを生成していくと, 最後に leafであるAPPにたどりつく. その際に行なうことは現在のregister mapを見 て, 引数を決まったregisterに並び替えることである. N個の変数を配置す るためには最悪1個余分なtemporary registerを用いて, N+1回のmoveが必要 になる. これを減らすためにはprimitiveに対してregisterを割り当てる時点 である程度の「先読み」をすれば良いことになる. 二つの互いに補い合う戦略 がある.

Targetting:
変数vにregisterを割り当てる時, vがこの先のAPP で第i引数として使われており, かつその時点で第i registerが空いてい たら, vにそれを割り当てる.
Anti-Targetting:
逆に, 変数vにregisterを割り当てる時, vが この先のAPPで引数として使われていない場合, APPで使われるregister を避けて割り当てる.

ここで, 「この先のAPP」には実は複数あり得るので, 「もっともありそうな APP」を選ぶ必要が生じ, それにはbranch predictionが必要である(この resumeでは, 真面目なbranch predictionはさぼっている).

16 bit tex2html_wrap_inline350 32 bit問題への対応

単純には, CLO変数一つに対して二つの機械レジスタを割り当てるようにすれ ば良い. そのためのregister mapの変更などは簡単である. ただし, 一つの CPS関数内だけを見て, 1レジスタだけを割り当てれば十分であるとわかる場合 には, 1レジスタだけを割り当てる. 具体的には,

  1. +stack等, 結果として非浮動小数点数が作られる命令 のターゲットには1レジスタだけを割り当てる.
  2. ある変数が整数やポインタとして使われる場合, その変数に対してレジ スタを割り当てる時点で, 1レジスタだけを割り当てる.

Register Spilling (省略!)

もちろん以上のようにしたところで, レジスタがあふれる可能性はある. こ れが起きてしまったら, 大きな番号のレジスタをメモリの固定された場所に割 り当てられた配列を使ってemulateする, というのがもっとも手っ取り早い方 法.

抽象機械

直接本物のtarget machineのコード生成をする代わりに, 複雑なmachine固有 の制約がない抽象機械のコードを生成する. その後に抽象機械のコードを machine固有の制約を加味しながらそれぞれのCPUの命令に変換する. 例えば, 命令長を固定した多くのmachineでは, 足し算のoperandとして, あまり大きな 定数はとれない(これは命令長が固定されているから当然である). 抽象機械に はこの手の制約は差し当たってないものとする.

Operand

抽象機械の命令がoperandとしてとれるものは以下の3種類.

Labelはmachineから見ればただの大きな整数だが, それが必ずしもcompile時 には決まらない(link時に決まる)点が違う.

Registerの数は, 実際の機械から決まる. 実際にはいくつかのregisterが特殊 目的(例えばstack pointer)に予約されるので, 抽象機械のregisterの数は, 実際のregister数よりも少なくなる.

命令セット

CPSに対応する命令

まずCPSにある各primitiveに対応する命令があるとする. 例えば,

(+ [x y] [t] [...])
に対応して,
(+ op0 op1 dest)
という命令がありまた,
(heap [x y z ...] [t] [...])
に対応して,
(heap op0 op1 ... opn dest)
がある. どちらの場合も最後のdestはregisterである.

一般的に, 分岐以外のCPS primitive:

(p [ tex2html_wrap_inline410 ] [ tex2html_wrap_inline412 ] [C])
に対して,
(p tex2html_wrap_inline410 tex2html_wrap_inline412 )
という, 対応する抽象機械命令がありまた, 分岐CPS primitive:
(p [ tex2html_wrap_inline410 ] [] [ C0 C1 ])
に対しては,
(p tex2html_wrap_inline410 l)
という, 比較が真であればラベルlに分岐する命令があると仮定する.

Move

最後のAPPでregisterを並べかえる際に使う.

(move x y)
で, xの内容をyに移す. yはregister.

Jump

最後のAPPで制御を移す時に使う.

(jump x)
で, xにjumpする. xは任意のoperand. 固定した番地ではなく, registerが示す番地にjumpできることが重要である.

Label擬似命令

命令中に,

f:
  (+ r0 r1 r2)
   ...
のように埋め込むことで, (label f:)がその番地を示すようにする. Compilerにとっては次の3つの目的に使われる.

Live-reg擬似命令

各CPS関数の直前においておき, その関数が試みるheap limit checkのsizeおよ び, その関数がどのparameterを使うかを教える. Garbage collectorが使う. 詳しくは後述するが, 文法は,

(live-reg s B)

のようで, sがheap limit checkを試みるword数, Bは各要素が0または1の listで, 長さはparameter渡しに使われるregisterの数である.

例えば, f:という関数が, 10 wordのheap limit checkをし, 第1, 2 parameterを使うのであれば,

(live-reg 10 (0 1 1 0 0 ..))
f:
  (+ r1 r2 r3)
   ...
のように書く. 実際にbinary中に埋め込まれるものは, (live-reg 10 (0 1 1 0 0 ..))をencodeした1ないし2 wordである(これは一見して無意味な命 令がそこに書かれているように見えることになるが, そこの命令を実行しよう と試みるものがいない限り大丈夫である).

コード生成例

以下の例では, いちいち, []()を区別しない(programの出力を indentしただけ). また, parameter渡しに使えるregisterは16個とする.

単純な関数呼びだし

Scheme:

(define (f x)
  (+ x (g x)))

CPS:

(f (k1 x) 
   (fixs ((k3 (r4) 
              (+-two (x r4) (v2) 
                ((appb k1 (v2)))))) 
     (appf g (k3 x))))

CLO:

(f: (f k1 x) 
    (fixs ((k3: (k3 r4) 
                (rref (k3 2) (x) 
                  ((+-two (x r4) (v2) 
                     ((rref (k3 1) (k1) 
                        ((rref (k1 0) (lk1) 
                           ((appb lk1 (k1 v2)))))))))))) 
      (stack (k1 (label k3:) k1 x) (k3) 
        ((rref ((label g) 0) (g) 
           ((rref (g 0) (lg) 
              ((appf lg (g k3 x))))))))))

抽象機械コード:

((live-regs 0 (0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0)) 
 f: 
 (stack r1 (label k3:) r1 r2 r1) 
 (rref (label g) 0 r0) 
 (rref r0 0 r3) 
 (jump r3) 
 (live-regs 0 (1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 
 k3: 
 (rref r0 2 r2) 
 (+-two r2 r1 r1) 
 (rref r0 1 r0) 
 (rref r0 0 r2) 
 (jump r2))

単純なloop

Scheme:

(define (fact n p)
  (if (= n 0)
      p
      (fact (- n 1) (* n p))))
ただし, 単純のため*はprimitiveとする.

CPS:

(fact (k1 n p) 
      (=-two (n 0) () 
        ((appb k1 (p)) 
         (--two (n 1) (v6) 
           ((*-two (n p) (v7) 
              ((appf fact (k1 v6 v7)))))))))

CLO:

(fact: (fact k1 n p) 
       (=-two (n 0) () 
         ((rref (k1 0) (lk1) 
            ((appb lk1 (k1 p))))
          (--two (n 1) (v6) 
            ((*-two (n p) (v7) 
               ((appf (label fact:) (fact k1 v6 v7)))))))))

抽象機械コード:

((live-regs 0 (1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0)) 
 fact: 
 (=-two r2 0 (label l6:))
 (--two r2 1 r4) 
 (*-two r2 r3 r3) 
 (move r4 r2) 
 (jump (label fact:)) 
 l6: 
 (rref r1 0 r2) 
 (move r1 r0) 
 (move r3 r1) 
 (jump r2))

Heap割り当てを含む例

Scheme:

(define (make-3d-point x y z)
  (list x y z))

CPS:

(make-3d-point (k1 x y z) 
               (heap (z '()) (v4) 
                 ((heap (y v4) (v3) 
                    ((heap (x v3) (v2) 
                       ((appb k1 (v2)))))))))

CLO:

(make-3d-point: (make-3d-point k1 x y z) 
                (heap (z '()) (v4) 
                  ((heap (y v4) (v3) 
                     ((heap (x v3) (v2) 
                        ((rref (k1 0) (lk1) ((appb lk1 (k1 v2)))))))))))

抽象機械コード:

r9r10を比べてheap limit checkをする. 本体はlabel l5:から始まる.

((live-regs 9 (0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0)) 
 make-3d-point: 
 (<-two hp hl (label l8:)) 
 (move (label make-3d-point:) tmp0) 
 (rref (label gc) 0 tmp1) 
 (rref tmp1 0 tmp1) 
 (jump tmp1) 
 l8: 
 (heap r4 '() r4) 
 (heap r3 r4 r3) 
 (heap r2 r3 r2) 
 (rref r1 0 r3) 
 (move r1 r0) 
 (move r2 r1) 
 (move r3 r2) 
 (jump r2))

中で関数呼び出しをしまくる例

Scheme:

(define (dist a b c x y)
  (let ((m (f+ (f* a x) (f* b y) c))
        (n (sqrt (f+ (f* a a) (f* b b)))))
    (f/ m n)))
f+, f*, f/, sqrtはすべて関数呼びだし.

CPS:

(dist (k1 a b c x y) 
  (fixs ((k6 (r7) 
    (fixs ((k8 (r9) 
      (fixs ((k4 (r5) 
        (fixs ((k2 (r3) 
          (fixs ((k14 (r15) 
            (fixs ((k16 (r17) 
              (fixs ((k12 (r13) 
                (fixs ((k10 (r11) 
                  (appf f/-two (k1 r3 r11)))) 
                (appf sqrt (k10 r13))))) 
              (appf f+-two (k12 r15 r17))))) 
            (appf f*-two (k16 b b))))) 
          (appf f*-two (k14 a a))))) 
        (appf f+-two (k2 r5 c))))) 
      (appf f+-two (k4 r7 r9))))) 
    (appf f*-two (k8 b y))))) 
  (appf f*-two (k6 a x))))

CLO:

(dist: (dist k1 a b c x y) 
  (fixs ((k6: (k6 r7) 
    (fixs ((k8: (k8 r9) 
      (fixs ((k4: (k4 r5) 
        (fixs ((k2: (k2 r3) 
          (fixs ((k14: (k14 r15) 
            (fixs ((k16: (k16 r17) 
              (fixs ((k12: (k12 r13) 
                (fixs ((k10: (k10 r11) 
                  (rref ((label f/-two) 0) (f/-two) 
                    ((rref (k10 15) (k1) 
                       ((rref (k10 5) (r3) 
                          ((rref (f/-two 0) (lf/-two) 
                             ((appf lf/-two (f/-two k1 r3 r11))))))))))))
                  (stack (k12 (label k10:)) (k10) 
                    ((rref ((label sqrt) 0) (sqrt) 
                       ((rref (sqrt 0) (lsqrt) 
                          ((appf lsqrt (sqrt k10 r13))))))))))) 
                (stack (k16 (label k12:)) (k12) 
                  ((rref ((label f+-two) 0) (f+-two) 
                     ((rref (k16 1) (r15) 
                        ((rref (f+-two 0) (lf+-two) 
                           ((appf lf+-two (f+-two k12 r15 r17))))))))))))) 
              (stack (k14 (label k16:) r15) (k16) 
                ((rref ((label f*-two) 0) (f*-two) 
                   ((rref (k14 7) (b) 
                      ((rref (f*-two 0) (lf*-two) 
                         ((appf lf*-two (f*-two k16 b b))))))))))))) 
            (stack (k2 (label k14:) r3) (k14) 
              ((rref ((label f*-two) 0) (f*-two) 
                 ((rref (k2 8) (a) 
                    ((rref (f*-two 0) (lf*-two) 
                       ((appf lf*-two (f*-two k14 a a))))))))))))) 
          (stack (k4 (label k2:)) (k2) 
            ((rref ((label f+-two) 0) (f+-two) 
               ((rref (k4 6) (c) 
                  ((rref (f+-two 0) (lf+-two) 
                     ((appf lf+-two (f+-two k2 r5 c))))))))))))) 
        (stack (k8 (label k4:)) (k4) 
          ((rref ((label f+-two) 0) (f+-two) 
             ((rref (k8 1) (r7) 
                ((rref (f+-two 0) (lf+-two) 
                   ((appf lf+-two (f+-two k4 r7 r9))))))))))))) 
      (stack (k6 (label k8:) r7) (k8) 
        ((rref ((label f*-two) 0) (f*-two) 
           ((rref (k6 1) (b) 
              ((rref (k6 2) (y) 
                 ((rref (f*-two 0) (lf*-two) 
                    ((appf lf*-two (f*-two k8 b y))))))))))))))) 
    (stack (k1 (label k6:) b y c a k1) (k6) 
      ((rref ((label f*-two) 0) (f*-two) 
         ((rref (f*-two 0) (lf*-two) 
            ((appf lf*-two (f*-two k6 a x))))))))))

抽象機械コード:

((live-regs 0 (1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0))
 dist: 
 (stack r0 (label k7:) r3 r6 r4 r2 r0 r0) 
 (rref (label f*-two) 0 r1) 
 (rref r1 0 r4) 
 (move r5 r3) 
 (jump r4) 
 (live-regs 0 (1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 
 k7: 
 (stack r0 (label k9:) r1 r5) 
 (rref (label f*-two) 0 r1) 
 (rref r0 1 r2) 
 (rref r0 2 r3) 
 (rref r1 0 r4) 
 (move r5 r0) 
 (jump r4) 
 (live-regs 0 (1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 
 k9: 
 (stack r0 (label k5:) r5) 
 (rref (label f+-two) 0 r6) 
 (rref r0 1 r2) 
 (rref r6 0 r4) 
 (move r5 r0) 
 (move r1 r3) 
 (move r6 r1) 
 (jump r4) 
 (live-regs 0 (1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
  k5: 
 (stack r0 (label k3:) r5) 
 (rref (label f+-two) 0 r6) 
 (rref r0 6 r3) 
 (rref r6 0 r4) 
 (move r5 r0) 
 (move r1 r2) 
 (move r6 r1) 
 (jump r4) 
 (live-regs 0 (1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 
 k3: 
 (stack r0 (label k15:) r1 r5) 
 (rref (label f*-two) 0 r1) 
 (rref r0 8 r2) 
 (rref r1 0 r4) 
 (move r5 r0) 
 (move r2 r3) 
 (jump r4) 
 (live-regs 0 (1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 
 k15: 
 (stack r0 (label k17:) r1 r5) 
 (rref (label f*-two) 0 r1) 
 (rref r0 7 r2) 
 (rref r1 0 r4) 
 (move r5 r0) 
 (move r2 r3) 
 (jump r4) 
 (live-regs 0 (1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 
 k17: 
 (stack r0 (label k13:) r5) 
 (rref (label f+-two) 0 r6) 
 (rref r0 1 r2) 
 (rref r6 0 r4) 
 (move r5 r0) 
 (move r1 r3) 
 (move r6 r1) 
 (jump r4) 
 (live-regs 0 (1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 
 k13: 
 (stack r0 (label k11:) r0) 
 (rref (label sqrt) 0 r4) 
 (rref r4 0 r3) 
 (move r1 r2) 
 (move r4 r1) 
 (jump r3) 
 (live-regs 0 (1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 
 k11: 
 (rref (label f/-two) 0 r5) 
 (rref r0 15 r6) 
 (rref r0 5 r2) 
 (rref r5 0 r4) 
 (move r6 r0) 
 (move r1 r3) 
 (move r5 r1) 
 (jump r4))

比較的容易な改善

前回の変換例の最後の例(関数呼び出し)をネタに, 性能の改善について思いを馳せる.

一見して無駄だと思えるのは,

  1. 各浮動小数点ルーチンの開始番地を得るためのメモリアクセス(2回). 例えば, f/を呼ぶためのCPSはCLOでは,
    (rref ((label f/-two) 0) (f/-two) 
      (( ...
         (( ...
            ((rref (f/-two 0) (lf/-two) 
               ((appf lf/-two (f/-two k1 r3 r11))))))))))
    となり, それは最終的な抽象機械コードでは,
     (rref (label f/-two) 0 r5) 
       ...
     (rref r5 0 r4) 
       ...
     (jump r4)
    のように2回間接参照をしている. これらの間接参照の結果, 結局でてくるの は, 少なくともこの場合は(label f/-two:)のことであることを我々は, (f/-twoというルーチンがどこで何をするものか知っているので)知って いる. これを直接, CLOにおいて,
    ( ...
      (( ...
         (( ...
            (( ...
               ((appf (label f/-two:) (f/-two k1 r3 r11))))))))))
    としてしまいたくなる(2命令の節約).
  2. 呼びだし時における返り番地のstackへの書き込み. 最初の関数呼び出しを除くほとんどの各関数呼びだし時にstackに書き込まれ ているのは, 返り番地か, 返り番地+直前の呼び出しの返り値, といったと ころである. これを, 返り番地はなんとかregisterの上にのせたまま呼びだし てしまいたくなる.

2回indirectionについて

良く見ると原因が二つあって, それらは一応独立している.

まず, Min-SchemeFix においては, 1個目は, calling conventionから, 「呼 ばれる関数がclosureを必要としない」ということがわかっていない限り避け られない. 2個目は, 得られるコード番地がわかっていれば避けられる. 一方Min-Scheme においては, 2個目は必要ない. 1個目をやればその時にでて くるのがコード番地である. では1個目についてはどうかというとここでもや はり, 得られるコード番地がわかっていれば避けられる. では, 一般 に得られるコード番地がわかってるかというと, これにはいろいろ条件がつい てややこしい.

まず一般には, CPSの

(APP f (x y z))
を,
(APP (label f:) (f x y z))
として良いわけではない. 第一に, fはtoplevelで定義されているもの ではなく, 関数のパラメータか何かかも知れないし, Min-SchemeFix においては内部で定義されたものかも知れない. それらの場合, (label f:)などというラベルがglobalに存在するわけではない. 第二に, fがたとえtoplevelであったとしても, fそのものが関数として定 義されているわけではなく, fは実はたまたま関数を値に持っている変 数かも知れない. その場合も, (label f:)などというものが存在するわ けではない. 例えば以下のような場合である.
(define (g x)
  ...)

(define f g)
この場合, (label g:), (label g), (label f)は存在するが, (label f:)は存在しない. ここで, (label g:)gを実現する命 令列が書かれている番地, (label g)gのclosureへのpointerが 格納されている番地, (label f)にはこの状況においては, (label g)同様, gのclosureへのpointerが格納されている.

まとめると, どうしても一般的に上の最適化をしたければ, 各toplevel変数に 対して, それが,

(define (f x)
  )
として定義されたものなのか,
(define f ..)
として定義されたものなのかを区別できる必要がある. 分割コンパイルを許す ことを考えると, このための情報は宣言として与えるしかない.

注: Cをよく知っている人へのanalogyをいうと,

f (x);
という呼び出しを見た時に, fが,
f (x)
{
   ...
}
のように定義されているのであれば, そのままfに飛べば良いが, もし fは関数ではなくglobal変数の場合, つまり,
void g (x)
{

}

void (*f)() = g;
のような場合, f (x)を実行するには, 1メモリアクセスが必要である. Cはこの2 caseを宣言により区別できるので前者に対しては効率的なjumpを生 成できるが, Min-Scheme においてはそれが成り立たない. 宣言を付け加えな い限り, 常に後者としてあつかわざるを得ない.

Ad-hocな方法としては, コンパイラに, ((define (f x) ...) の形で 定義される関数の一覧と, そのラベル名の対応表を与えるという方法があ る. その表にある関数の呼び出しに関しては, Min-Scheme だろうがMin-SchemeFix だろうが直接jump先がわかる. 具体的に はclosure変換に対する変更として実現できる.

戻り番地の書き込みについて

FIXSにおいて作られるclosureのformatを変更することで対処できる.

例えば, CLOにおける, sqrtを呼び出すところで,

(stack (k12 (label k10:)) (k10) 
  ((rref ((label sqrt) 0) (sqrt) 
     ((rref (sqrt 0) (lsqrt) 
        ((appf lsqrt (sqrt k10 r13))))))))
今回, stackに書かれているのは, (label k10:)でそれはつまり戻り番 地だけである. これを,
(stack (k12) (k10)    ; 何も書かない!
  ((rref ((label sqrt) 0) (sqrt) 
     ((rref (sqrt 0) (lsqrt) 
        ((appf lsqrt (sqrt (label k10:) k10 r13)))))))) ; 戻り番地もregister

Closure変換アルゴリズムを変更することで実現できる.

FIXH
各関数の第1引数(continuation)を, 二つの語にわける. 例えば,
(FIXH [(f (k x y) ..)] ...)
を,
(FIXH [(f (k0 k x y) ..)] ...)
のように. k0がコード番地(いわゆる戻り番地), kがclosureレ コードへのポインタで, レコードには戻り番地は含まれていない.
APPF
(APPF f (k x y))
において,
FIXS
FIXSにおけるclosure formatは, 戻り番地を格納し ないように変更する.
APPB
(APPB k (r))
を,
kがこのMin-Scheme 関数内で作られた場合:
(APPB (label k:) (k r)),
kがこのMin-Scheme 関数のcontinuation引数の場合:
(APPF k0 (k r)),

とする.

課題

抽象機械コード生成のアルゴリズムを完成させ、いくつか動作確認をした例と ともに一つ提出せよ. Heap limit checkはheap割り当てを行うCPS関数の先頭 で, そのbodyで使われる全てのheap割当のためのcheckを一度に行なうことに する.

抽象機械を飛ばしていきなり実機械コードを出す場合(お勧めはしませんが)は, そのコード生成のアルゴリズムを完成させて提出する.

締切り: 12月2日(水)

今後の予定

参考データ

94年の川道君が作成し, 95年の長野君が手直ししたScheme用のレイトレーシ ングのプログラム( tex2html_wrap_inline472 tau/comp/RT_nagano/)の各fileを今まで述 べた方方でコンパイルした時の統計. すべてコンパイル時に得られたstaticな 統計であり, 実際に走らせた時のものではないので使用には注意が必要.

レジスタ利用

プリミティブのtargetに対してレジスタを割り当てる時どの番号がどのくらい 使われているか. 1 Scheme word = 1 machine wordの場合と, 1 Scheme word = 2 machine wordの場合(括弧内). Anti-Targetting時および Targettingが失敗した時には可能なレジスタのうちもっとも小さな番号を割り 当てる.

tabular312

いいたいことは,

一般にレジスタをたくさん使用する原因となるのは, である. 溢れがいやならこれらを手がかりに直すことができるだろう.

Stack

実行されたstack命令と, 書き込まれた語数. 1 Min-Scheme word = 1 machine word. したがって16 bitを1語と換算すると, もう少し増える.

tabular320

staticに平均すると平均して, 一回につき1.62 word書かれている. つまり一 回関数呼び出しなどでstackに何かを積む場合に, 1.62 wordメモリに退避する ということである. そのうちの1 wordは戻り番地である. 1 wordが16 bitの場 合, 戻り番地のhigh wordは書き込まなくて良い. すると最悪の場合を考える と, 1 + 0.62 * 2 = 2.24 wordになる.

Move

APP時に必要なmoveの数. 1 Min-Scheme word = 2 machine wordで, 今は undefinedであるがために必要のないmoveまで数えている. APPFとAPPBで別に 数えた. x/y/zで, 計z回のAPPに対して, 計y個の引数が渡され, それに 対してx個のmoveが必要であったことを示している.

tabular324

staticな平均をとると, 1 APPFにつき2.77 move, 1 APPBにつき, 2.1 move. また, 1引数につき0.5 moveくらい必要で, targettingがそこそこうまくいっ ているということがいえる.

前章と合わせるとMin-Scheme の関数呼びだし1回の, 非常に大雑把なコストが 見積もれる.

Min-Scheme の関数呼びだし = 2.24 stack write + 2.77 move + 2 indirection + jump + 1 indirection + 2.1 move + jump + 1.24 stack read = 6.48 memory read/write + 4.87 move + 2 jump.
これはstackへの値の退避, 引数の並びかえ, コードアドレスを得るための indirection, jump, 戻り番地を得るための1 indirection, 返り値を返すため のmove, jump, 退避された変数のrestoreを含んでいる. また退避された変数 はrestoreされるとはかぎらないが, 今はrestoreされるとしている.


...となる.
gを呼ぶ時のパラメータの順番が微妙に先週までと違っ ていて, それについては後に説明する.
 

 

〔トップページへ〕 〔「コンパイラ演習レジュメ」のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 11 May, 1999