2005年07月29日

MinCaml読解ノート 目次

MinCaml読解ノートが一通り完了したので、目次として各記事へのリンクを列挙する。

MinCaml読解ノートは、MinCamlコンパイラを筆者が読んだ結果を元に理解の参考のために動作やソースコードに対する解説を加えたものであって、住井氏自身による「速攻MinCamlコンパイラ概説」による解説を補い、詳しい補足や場合によりソースコードに即した説明により読者の理解の一助となることを意図している。

MinCamlの記述言語であるObjective Camlについての知識は「超特急: 一時間でわかるML超入門」の内容のみを前提とし、その範囲を超えた機能が使われ理解を妨げそうなときには説明を付した。筆者自身も当初Objective Camlについては「超入門」を読んだだけの内容しか知らなかったので、同じようにObjective Camlの知識に乏しい方でもさほど支障は生じないと思われる。

またMinCamlがターゲットとするSPARCについてもMinCamlの理解に必要と思われる範囲で簡単に説明する記事を挿入した。

  1. ビルドと全体の流れ
  2. 字句解析
  3. 構文解析
  4. 型推論
  5. K正規化
  6. α変換
  7. β簡約
  8. ネストしたletの簡約
  9. インライン展開
  10. 定数畳み込み
  11. 不要定義削除
  12. クロージャ変換
  13. SPARC概要
  14. 仮想マシンコード生成
  15. 13bit即値最適化
  16. レジスタ割り当て
  17. アセンブリ出力

MinCaml読解ノート: アセンブリ出力

ようやく最終フェーズである。いよいよasに与えるアセンブリソース(*.s)を出力する。このフェーズの各関数に共通する引数ocはファイル(*.s)への出力チャネルである。

基本的には仮想マシンコードの命令に対応するアセンブリを出力するだけである。 但し次の仮想命令に伴う処理が必要となる。

  • Save, Restore: スタックからのロード・ストアを生成。スタック上の変数の配置とその管理。
  • IfEq等の条件分岐: 分岐命令、それぞれの分岐のコード、ラベルとジャンプ命令の生成。
  • CallDir, CallCls: レジスタへの引数のセット。末尾呼び出しでない場合はスタックポインタの操作も。末尾呼び出しの最適化。

命令列や命令のアセンブリ出力(Emit.gEmit.g'等)には最後の値を返すレジスタの指定であるdestが与えられる。これは命令に出力オペランドを持たず、命令列も最後はAnsノードなので同様に出力先を持たないためである。

命令列のアセンブリ出力 (Emit.g)

命令列中の命令について繰り返しg'を呼ぶ。その出力先はNonTail(Letが保持する出力レジスタ)であるが、命令列の末尾(Ansノード)ではdestを渡す。

命令のアセンブリ出力 (Emit.g')

TailNonTailで大きく分かれる。

NonTailの場合は出力レジスタが与えられているので命令をそのままアセンブリ出力する。

Tailの場合は戻り値を返すレジスタを使って同様に出力した後、関数から戻るret命令を生成している。アセンブリ命令を一旦バッファに入れ、retを一つ前の命令と順番を入れ替えれば無駄なnopを無くせるが、そこまではやっていない。

Save, Restoreとスタックの管理

Save, Restoreはスタック上の変数へのストア・ロード命令に変換される。

スタック上の変数の配置を管理するのは大域変数のstackmapstacksetである。

stackmapはスタック上の配置を表す変数名のリストである。MinCamlで扱うオブジェクトが1ワードのもの(整数やポインタ)とダブルワードのもの(浮動小数点数)しかないことを利用し、後者は同じ要素2つで表す。これによって、stackmap上での添字を4倍すれば変数のスタック上の位置(スタックポインタからの相対)が得られる。浮動小数点数を挿入する場合は必要に応じて1ワードのパディングに相当するダミーの変数名を先に追加する。

関数やクロージャが呼ばれるときは、スタックの先頭にreg_raが保持している現在の関数からのリターンアドレスを退避してから呼び出す。

これを示すようにstacksizeは変数の占める大きさより常に1ワード大きく計算する。

条件分岐命令のアセンブリ出力 (g'_tail_ifまたはg'_nontail_if)

スタックの状態を管理するstacksetが大域変数なので、保存して巻戻しつつ分岐するときとしないときの命令列をそれぞれ出力している。stacksetのみを巻戻しstackmapは触らないのは意図されたもので、これにより真偽それぞれの場合の命令列で同じ変数が異なるアドレスに割り付けられることを防いでいる。

g'_tail_ifの方はそれぞれの命令列の先でリターンするので簡単であるが、g'_nontail_ifは合流のためにラベルとジャンプを生成する必要がある。

関数適用・クロージャ適用のアセンブリ出力 (Emit.g')

まずg'_argsで引数(とクロージャへのポインタ)をレジスタに載せるコードを生成する。

このとき移動する順番をうまく考えないと、必要な値を他にコピーする前にレジスタを上書きしてしまいかねない。この順番を工夫するのが関数shuffleである。

猶、クロージャの自由変数は関数先頭でクロージャレコードからロードするコードが既に生成されている。仮想マシンコード生成を参照のこと。

現在の関数からのリターンアドレスをreg_raが保持しているが、これも関数呼び出しで破壊されるのでスタックの先頭に退避する。

末尾呼び出しであれば呼び出し先の関数にジャンプする。

そうでない場合はスタックポインタをスタックの先頭に進めてからcall命令で呼び出し、戻ってきたらスタックポインタを戻す(スタックポインタを進める命令はcall命令の次に書いてあるが、SPARCの性質によりcall命令より先に実行される)。その後reg_raにリターンアドレスを復元する。

ある関数でのスタックの使われ方は図のようになる。この例ではvar1, var2, var3, fvar1がレジスタ溢れによってスタックに退避される変数であり、そのうちfvar1は浮動小数点数である。raddrreg_raから退避するリターンアドレスである。

|     |
+-----+<-- reg_sp
|var1 |
+-----+
|var2 |
+-----+
|var3 |
+-----+
| -   |
+-----+
|fvar1|
+- - -+
|fvar1|
+-----+
|raddr|
+-----+<-- 別の関数を呼ぶときの reg_sp
|     |

shuffleのアルゴリズム

引数それぞれについて移動先となるレジスタに他の引数が載っていないか調べ、他の引数を破壊しないものから先にmov命令を出力する。

そうすると最後に循環するレジスタのリストが残るか、リストが空になる。

循環が残る場合はスワップ用レジスタを介してそのうち2つを入れ替えることにより循環を一つ破壊し、残りを再びshuffleする。

プログラムのメインルーチンのアセンブリ出力 (Emit.f)

min_caml_startというC関数として見えるように出力する。そのためここだけsave命令とrestore命令によりレジスタウィンドウの操作を行うコードを出力する。

このmin_caml_startはstub.cの中のmainから呼び出され、(Cの関数呼び出し規約により)%i0%i1にそれぞれ第一第二引数として渡されたスタック領域、ヒープ領域が入る。MinCamlではこれらをそのままreg_sp, reg_hpとしている。

広告


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

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

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


×

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