本実験演習の仮想機械コードでは局所変数の数に上限はなく,そのため,前章の素朴なコード生成手法では,同じく(物理メモリサイズの上限はあるものの)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
型で番号のつけられていた局所変数を,レジスタ機械では:-
汎用レジスタを表す
reg
型.各レジスタには0からはじまるユニークな整数IDがつけられているものとする.配布コードでは,arm_spec.ml
中の変数nreg
で利用可能な汎用レジスタの個数を定義し,また,arm_reg.ml
中の連想リストreg_mappings
によりARMの場合のIDと実際のレジスタとの対応関係を定義している. -
フレーム中の場所を表す
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完全であることが知られている.
- グラフのノードを各局所変数とする.
- 色の個数を利用可能な汎用レジスタの個数とする.
- ノード間のエッジは,両端の局所変数が同時に生きている瞬間があることを意味する.
- 隣接しているノードは必ず異なる色となるよう,すべてのノードに色を塗る.
- 課題12(任意) レジスタ機械コード生成
- 生存変数解析モジュールによる解析結果を用いて,仮想機械コードをレジスタ機械コードに変換しなさい.
Reg.trans
関数の第1引数で指定される整数は利用可能な汎用レジスタの個数である.なるべく多くの局所変数を汎用レジスタに割り付けるよう工夫すること.
- 課題13(任意) ARMコード生成 その2
arm_reg.ml
のcodegen
関数を完成させることにより,課題12で生成したレジスタ機械コードからARMアセンブリコードを生成しなさい.