5.2 仮想機械コードへの変換

仮想機械コードの仕様（OCamlデータ型）を以下に示す．

`vm.ml` (冒頭部分)

module S = Syntax
module F = Flat

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

type binOp = S.binOp

type id = int
type label = string

type operand =
    Param of int     (* param(n) *)
  | Local of id      (* local(ofs) *)
  | Proc  of label   (* labimm(l) *)
  | IntV  of int     (* imm(n) *)

type instr =
    Move of id * operand (* local(ofs) <- op *)
  | BinOp of id * S.binOp * operand * operand
    (* local(ofs) <- bop(op_1, op_2) *)
  | Label of label (* l: *)
  | BranchIf of operand * label (* if op then goto l *)
  | Goto of label (* goto l *)
  | Call of id * operand * operand list
    (* local(ofs) <- call op_f(op_1, ..., op_n) *)
  | Return of operand (* return(op) *)
  | Malloc of id * operand list (* new ofs [op_1, ..., op_n] *)
  | Read of id * operand * int (* read ofs #i(op) *)
  | BEGIN of label (* データフロー解析で内部的に使用 *)
  | END of label   (* データフロー解析で内部的に使用 *)

type decl =
    ProcDecl of label * int * instr list  (* int は局所変数の個数 *)

講義テキストの言語 $\mathcal{V}$ との違いはわずかである：

フラット表現と言語 $\mathcal{C}$ の間の違いと同様に，プログラムは関数宣言の列に過ぎず，_toplevelを特別扱いする．
言語 $\mathcal{V}$ ではオフセット（ofs）と呼んでいた概念を，仮想機械コードではid型で表現する．

Warning: その実体はint型であるため，実質的には講義テキストのオフセットと同じものを表しているが，この資料ではレジスタ割付けで類似の概念を「オフセット」と呼んでおり，混乱を避けるため別の呼び方にしている．

また，言語 $\mathcal{V}$ のオフセットはバイト単位で計算していたが，idはワード単位で計算するものとする．このように定義することで，特定のアーキテクチャやOSに依存しない表現を保つことができる．

Note: たとえば，将来的にRaspberry Piの標準OSが64ビット化するかも知れない．
malloc命令の追加．第2オペランドで指定される値の列を格納するためのメモリ領域をヒープ中に確保し，それらの値を順に格納する．確保したメモリ領域の先頭アドレスは，第1オペランドで指定される場所に入れられる．
read命令の追加．第2オペランドで指定されるアドレスから，第3オペランドで指定されるワード（バイトではないことに注意）分だけ離れたメモリ領域に含まれている値を読み出し，第1オペランドで指定される場所に入れる．
BEGIN命令，END命令の追加．これらはデータフロー解析でだけ用いる内部表現である．この章では扱わない．

なお，講義テキストの言語 $\mathcal{V}$ の表現をvm.ml中にコメントとして書いてあるが，minimlcコマンドの-vオプションでは異なるフォーマットで表示される．混乱を避けるため，（OCamlのデータ型も含めた）対応関係を以下の表に示す．

仮想機械コードのフォーマット

OCamlデータ型`instr`	`minimlc -v`	言語 $\mathcal{V}$
`Move (` $\!id$ `,` $\!op$ `)`	`move t` $\!id$ `,` $op$	local( $id$ ) $\;\leftarrow\;$ $op$
`BinOp (` $\!id$ `,` $\!bop$ `,` $\!op_1$ `,` $\!op_2$ `)`	$bop$ `t` $\!id$ `,` $op_1$ `,` $op_2$	local( $id$ ) $\;\leftarrow\;$ $bop$ ( $op_1$ , $op_2$ )
`Label` $l$	$l$ `:`	$l$ `:`
`BranchIf (` $\!op$ `,` $\!l$ `)`	`bif` $op$ `,` $l$	if $op$ then goto $l$
`Goto` $l$	`goto` $l$	goto $l$
`Call (` $\!id$ `,` $\!op_f$ `, [` $\!op_1$ `;` $\ldots$ `;` $op_n$ `])`	`call t` $\!id$ `,` $\!op_f$ `(` $\!op_1$ `,` $\ldots$ `,` $op_n$ `)`	local( $id$ ) $\;\leftarrow\;$ call $op_f$ ( $op_1,\ldots,op_n$ )
`Return` $op$	`ret` $op$	return( $op$ )
`Malloc (` $\!id$ `, [` $\!op_1$ `;` $\ldots$ `;` $op_n$ `])`	`new t` $\!id$ `, [` $\!op_1$ `,` $\ldots$ `,` $op_n$ `]`	—
`Read (` $\!id$ `,` $\!op$ `,` $\!i$ `)`	`read t` $\!id$ `, #` $\!i$ `(` $op$ `)`	—

このように，仮想機械コードと言語 $\mathcal{V}$ との間に本質的な違いは殆どないため，仮想機械コードへの変換は変換 $\mathcal{VT}$ とほぼ同じである．フラット表現の組に関する式（TupleExp，ProjExp）は言語 $\mathcal{C}$ に含まれていないが，それぞれ自明に対応するmalloc命令とread命令に変換するだけである．loop式とrecur式は，goto命令を使ったループに変換すれば良い．まず，loop式は，その構文の類似性からも想像できるとおり，let式と同じ仮想機械コードへと変換する．ただし，本体式の先頭にはrecur式（の変換後の命令）のジャンプ先としてフレッシュなラベルをつけておく．recur式では，一番内側のloop式のラベルへのgoto命令を実行するが，その直前に，recur式の引数を一番内側のloop式の束縛変数に対応するローカル変数へ格納する必要がある．たとえば：

loop i = 1 in
let j = i + 1 in
recur j

という単純なループは，次の仮想機械の命令列へ変換する：

  move    t1, 1
L0:
  add     t2, t1, 1
  move    t1, t2
  goto    L0

課題8(必須) 仮想機械コード生成: vm.mlのtrans関数を完成させることにより，フラット表現から仮想機械コードへの変換を実現しなさい．

vm.ml (冒頭部分)

仮想機械コードのフォーマット

`vm.ml` (冒頭部分)