7.3 レジスタ割付け

本実験演習の仮想機械コードでは局所変数の数に上限はなく，そのため，前章の素朴なコード生成手法では，同じく（物理メモリサイズの上限はあるものの）spレジスタを下げれば下げるだけ必要なメモリ領域を確保できるフレーム中に局所変数を配置していた．しかし，前章でも述べたとおり，物理レジスタをまったく利用しないこの方法だと実行効率が悪いので，できればなるべく多くの仮想機械コードの局所変数を，空いている物理レジスタに割り付けたい．

「汎用レジスタ」の概念を追加した仮想機械よりさらに低水準な中間表現をレジスタ機械 (register machine)コードと呼ぶことにする．OCamlのデータ型としては以下のように定義される．

reg.ml

exception Error of string
let err s = raise (Error s)

type binOp = Vm.binOp

type offset = int
type label = string

type reg = int       (* 汎用レジスタ．0以上の整数 *)

(* コード生成が swap に利用するための専用レジスタ．
   実際にどの物理レジスタを用いるかはアーキテクチャ依存 *)
let reserved_reg = -1

type dest =
    R of reg     (* レジスタ *)
  | L of offset  (* 局所領域の関数フレーム中の相対位置  *)

type operand =
    Param of int
  | Reg   of reg
  | Proc  of label
  | IntV  of int

type instr =
    Move     of reg * operand
  | Load     of reg * offset
  | Store    of reg * offset
  | BinOp    of reg * Vm.binOp * operand * operand
  | Label    of label
  | BranchIf of operand * label
  | Goto     of label
  | Call     of dest * operand * operand list
  | Return   of operand
  | Malloc   of dest * operand list
  | Read     of dest * operand * int

type decl =
    ProcDecl of label * int * instr list (* int: 局所領域の個数 *)

type prog = decl list

なお，前章で説明したとおり，実際のARMにはレジスタ-レジスタ以外の演算を行うことのできるアドレッシングモードが用意されているが，ここでは簡単のため，MIPSのような厳密なロードストアアーキテクチャの中間表現を採用する．仮想機械の仕様との主な違いは次のとおり：

• 仮想機械ではVm.id型で番号のつけられていた局所変数を，レジスタ機械では：

  1. 汎用レジスタを表すreg型．各レジスタには0からはじまるユニークな整数IDがつけられているものとする．配布コードでは，arm_spec.ml中の変数nregで利用可能な汎用レジスタの個数を定義し，また，arm_reg.ml中の連想リストreg_mappingsによりARMの場合のIDと実際のレジスタとの対応関係を定義している．

  2. フレーム中の場所を表すoffset型．fpレジスタからのワード単位のオフセットで指定される．

  の2種類に分けられる．

• 演算のオペランドを表す型（operand型）からVm.Localを取り除き，代わりにRegが追加されている．

• Move命令，BinOp命令等のデスティネーションにはVm.id型ではなくreg型を指定する．

• メモリアクセス用に専用のLoad，Store命令が追加されている．

レジスタ割付け処理は，仮想機械コードからレジスタ機械コードへの変換を行うことによって実現する．簡単な式「1*2+3*4」の仮想機械コードにレジスタ割付けを行なうことを考えてみよう．

$ ./minimlc -O -G -v
# 1*2+3*4;;
...
(* [VM code] *)
proc _toplevel(3) =
  mul	t1, 1, 2
  mul	t2, 3, 4
  add	t0, t1, t2
  ret	t0
...
#

局所変数t0–t2が使われている．仮に汎用レジスタが2個しかないとしよう．素朴に考えれば，3つの局所変数の中から2つを選び，残りはスタックのフレーム上に置くしかなさそうである．

しかし，生存変数解析を用いると，もう少し賢く割り付けることが可能である．上の仮想機械コードの生存変数解析の結果を以下に示す．

この解析結果から，局所変数t1の値が生きている区間は「mul t1, 1, 2」の直後から「add t0, t1, t2」の直前までであり，また，局所変数t0の値が生きている区間は，「add t0, t1, t2」の直後から「ret t0」の直前までであることが見てとれる．つまり，t0とt1が同時に生きている瞬間はないことが分かる．そのような場合，これら2つの局所変数に対し同じ汎用レジスタを使うように割り付けても，互いに干渉しないため，何も問題がない．

一方，「add t0, t1, t2」の直前のプロパティを見ると分かるように，t1とt2は同時に生きている瞬間があるため，これらを同じ汎用レジスタに割り付けるわけにはいかない．

以上の考察の下，レジスタ割付けを行うと，上の仮想機械コードは次のようなレジスタ機械コードへと変換できる．

$ ./minimlc -O -G -v
# 1*2+3*4;;
...
(* [Reg code] *)
proc _toplevel(0) =
  mul	r0, 1, 2
  mul	r1, 3, 4
  add	r0, r0, r1
  ret	r0
...
#

局所変数t0とt1をレジスタr0に，局所変数t2をレジスタr1に割り付けており，スタック中のフレームには何も置かずに済んでいる．

このレジスタ割付け問題は，グラフ彩色 (graph coloring)と呼ばれる有名なグラフ問題から次のようにして帰着できるのだが，残念ながらグラフ彩色はNP完全であることが知られている．

• グラフのノードを各局所変数とする．
• 色の個数を利用可能な汎用レジスタの個数とする．
• ノード間のエッジは，両端の局所変数が同時に生きている瞬間があることを意味する．
• 隣接しているノードは必ず異なる色となるよう，すべてのノードに色を塗る．