2005年06月30日

MinCaml読解ノート: 仮想マシンコード生成

このフェーズではSPARCアセンブリに準じた仮想マシンコードを生成する。

「概説」によると、仮想である所以は次の2点。

  • 変数(レジスタ)が無限にある
  • ブランチやジャンプの代わりにif-then-elseや関数呼び出しがある

つまり、これまで変数であったものが「無限にある仮想レジスタ」という位置付けに横滑りする。 条件分岐で枝分かれする中間コードの構造は変更しない。

MinCamlのコードの規約

SPARCプロセッサの概要は既に説明したが、これからマシンコードに落とし込む上で必要となるレジスタの使い方などを整理しておく。

クロージャやタプルはヒープ上に取る。ヒープは拡大する一方で、ガベージコレクションはしない。クロージャの実体は [関数のポインタ, 自由変数1, 自由変数2, ..., 自由変数n] というレコード。浮動小数点数が入る場合、その要素がダブルワード境界になるようパディングする。タプルも同様のレコード。

MinCamlでは、次のような決まりでレジスタを使う。

スタックポインタ (reg_sp)
%i0 [Cと違う。Cは%o6がスタックポインタ]
リターンアドレス (reg_ra)
%o7 [C等と同じ]
ヒープポインタ (reg_hp)
%i1
引数
残りの汎用レジスタ全て (regs = %i2%i7, %l0%l7, %o0%o5)
浮動小数点数の引数
浮動小数点レジスタ全て (fregs = %f0,%f2,...,%f30)
戻り値
%i2または%f0 (汎用レジスタの最初のレジスタ)
クロージャを指すレジスタ (reg_cl)
%o5

クロージャを呼ぶときは、まずreg_clにクロージャのアドレスをセットし、その先頭にある関数へのポインタをレジスタにロードして呼び出す。

関数内では変数は全て仮想レジスタと考えるので、クロージャの自由変数は関数先頭で全部レジスタにロードしてしまう。以後はレジスタ渡しされた引数やローカル変数と区別されなくなる。

仮想マシンコードの表現

仮想マシンコードのデータ型はsparcAsm.mlで定義される。このうち、命令列のデータ型がSparcAsm.t、個々の命令がSparcAsm.expである。

type t =
  | Ans of exp
  | Let of (Id.t * Type.t) * exp * t
  | Forget of Id.t * t

Forgetは今は措くとして、命令列がLetのリストであることがより明確となった。次図のように、命令列は一連のLetと末尾のAnsによるリストとなる(ただしexpには条件分岐があり得る)。

Let-Let-//-Ans
|   |      |
exp exp    exp

SparcAsm.expにはSPARC概要で述べた命令が並べられ、それに条件分岐や関数呼び出しに対応する仮想命令が加わっている。これらの構成子は入力オペランドとなるレジスタと即値をとる。出力レジスタは命令を指すLetノードの方で決まる。

and exp =
  | ...
  | Mov of Id.t
  | Neg of Id.t
  | Add of Id.t * id_or_imm
  | Sub of Id.t * id_or_imm
  | Ld of Id.t * id_or_imm
  | St of Id.t * Id.t * id_or_imm
  | ...
  | IfEq of Id.t * id_or_imm * t * t
  | IfLE of Id.t * id_or_imm * t * t
  | ...
  | CallCls of Id.t * Id.t list * Id.t list
  | CallDir of Id.l * Id.t list * Id.t list

実装

virtual.mlで定義される関数はclassify, separate, expand, g, h, f の6つ。 中間コードから仮想マシンコードへの変換の中心はVirtual.gである。 Virtual.hは関数の本体のコード生成、Viruatl.fはプログラムを構成する各関数の本体とメインの式それぞれについて変換を呼び出す。

virtual.mlで定義されるグローバル変数dataは浮動小数点数のテーブルである。 SPARCでは浮動小数点数は即値に出来ないため、定数のテーブルを作っておいてロードする。そのためにプログラム中に出現する浮動小数点数を記録する。

大きい関数を見る前に、まずは小さいものから片付けておく。 classifyは(変数名, 型)のリストxtsについてのfold_leftで、 ただし要素の型によって違う関数を適用する(Unitの場合は何もしない)。 separateexpandはこれを用いる。

separateは変数を整数と浮動小数点数に仕分けし、 整数型の変数のリスト, 浮動小数点数のリストの2つのリストを返す。

expandはレコード中の変数のオフセットを計算しながら処理を進めるclassifyと言える。関数にはリストの要素のほか、計算中のオフセットも渡される。オフセットの計算では浮動小数点数のダブルワード境界のアラインメントを考慮する。

Virtual.g

整数の即値や算術演算のようなものはそのまま対応する命令一つに変換する。

例:

  | Closure.Add(x, y) -> Ans(Add(x, V(y)))

浮動小数点数の場合、既に述べたように即値として扱えない。そこでラベルを生成して値と共にテーブルdataに登録し、まずはこれも新しく生成した変数(レジスタ)xにアドレスを代入、そのレジスタの指すアドレスから値をロードするという2命令に変換する。

条件分岐はClosure.tと同じ構造の仮想命令なのでそのまま。

関数やクロージャの呼び出しも仮想命令なのでほとんどそのままである。

Let((x,t),e1,e2)e1を変換したコードの後ろにe2を変換したコードを繋げる。 e1の末尾のAnsは変数xLetに置き換えられる。

変数の参照はmov命令になる。

Closure.MakeClsの変換

クロージャの生成(Closure.MakeCls)は、トップレベル関数と束縛する自由変数を順にレコードにストアする処理である。

ここでの核心はoffsetstore_fvの計算である。expandはオフセットを計算しながらリスト中の変数の型に応じて与えられた関数を呼ぶから、store_fvにはストア命令のリストが返される。

このストア命令のリストが実は自由変数の並びと逆になっているところがミソである。パディングが絡むオフセット計算はレコードの並び通りの順で行う必要がある。しかし実際に動くとき、ストア命令の実行は並び順の通りでなくても構わない。この着想のお蔭でこの処理が以前の版に比べ簡単になっている。

実はこれと同じ処理はもう一つある。タプルの生成がそれで、どちらも一連の変数をレコードにストアする処理である。

Virtual.h

関数の式を仮想マシンコードに変換する。関数は最初に自由変数を全てレジスタにロードする処理を入れる。これは丁度Closure.MakeClsを変換したときの逆の処理であるが、やっていることはストア命令がロード命令になっただけでほとんど同じである。

クロージャの生成にタプル生成という同種の処理があったように、こちらも同じ構造の処理がある。Closure.LetTupleの変換がそれである。

この記事へのトラックバックURL
http://blog.seesaa.jp/tb/4732876
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス:

ホームページアドレス:

コメント: [必須入力]

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。