356 ー付録 B テストスクリプト言語 と push 、算術コマンドだけを実装し、サプルーチン呼び出しは無視した。そのため、 7 章のプロジェクトで使用するテストプログラムは、 " 生の " VM コマンドから構成さ れる (function や return などは使用しない )。そのようなコマンドを使って非公 式なテストを行うために、 VM 工ミュレータは " 生の " VM コマンド この VM コ マンドは、適切に初期化が行われす、ファンクションの形でまとめられていない を実行できる機能を備えている。 仮想メモリセグメント バーチャルマシンの命令をシミュレートする間、 VM 工ミュレータは Hack VM の 仮想メモリセグメント (argument 、 1 〇 cal など ) を管理する。これらのセグメン トはホストの RAM 上に割り当てる必要がある。これは、通常工ミュレータが行うタ スクであり、 call 、 function 、 return コマンドの実行をシミュレートした結果 として現れる。これが意味することは、 サプルーチン呼び出しを含まない " 生の " VM コードをシミュレートするときは、 RAM 内で仮想セグメントを明示的に設定す るように VM 工ミュレータに強制しなければならない ということである。都合の 良いことに、この初期設定はスクリプトのコマンドによって行うことができる。この スクリプトコマンドは、ポインタを操作し、仮想セグメントの RAM アドレスのべー スを制御する。このスクリプトコマンドを使って、 RAM で選択された領域に仮想セ グメントを配置することができる。 B. 4.1 例 FibonacciSeries . vm は一連の VM コマンドから構成され、フイボナッチ数列 の最初のれ個を計算する。このコードはふたつの引数を取る。ふたつの引数は、れの 値と、計算した結果を格納するメモリアドレスの開始位置である。例 B -4 のスクリプ トは、 6 と 4000 を引数に用いてテストするように設計されている。

セグメント argument 10Ca1 s t a t 土 c constant th 土 s that pointer temp 目的 関数の引数を格納する 関数のローカル変数を格納する スタティック変数を格納する。ス タティック変数は、同し vm ファイ ルのすべての関数で共有される O から 32767 までの範囲のすべ ての定数値を持つ擬似セグメント 汎用セグメント。異なるヒープ領 域に対応するように作られてい る。プログラミングのさまざまな ーズで用いられる this と that セグメントのべースア ドレスを持つ 2 つの要素からなる セグメント 固定された 8 つの要素からなるセ グメント。一時的な変数を格納す るために用いられる 7.2 VM 仕様 ( 第 1 部 ) ー 145 コメント 関数に入ると VM 実装によって動的に 割り当てられる 関数に入ると VM 実装によって動的に 割り当てられ、 O に初期化される 各 . vm ファイルに対して、 VM 実装によ り動的に割り当てられる。 . vm ファイル のすべての関数で共有される VM 実装によってエミュレートされる。 プログラムのすべての関数から見える ヒープ上の選択された領域を操作す るために、どのような関数でもこれら のセグメントを使うことができる VM の関数で、 pointe 「の O 番目 ( また は 1 番目 ) をあるアドレスに設定するこ とができる。これにより、 this ( または that ) セグメントをそアドレスの開始 するヒープ領域に設定する 目的に応して VM 関数によって使われ る。プログラムのすべての関数で共有 される 図 7-6 すべての VM 関数から見えるメモリセグメント。現時点では、その使用法やセグメントの配 置について理解する必要はない。詳細については以降の章で明らかになる 図で示した 8 つのメモリセグメントは VM の push と pop コマンドによって明示 的に操作される。これに加えて、 VM はスタックとヒープと呼ばれるデータ構造を暗 黙のうちに扱う。これらのデータ構造は直接操作されることはないが、 VM コマンド を実行した結果として、その背後で、それらのデータ構造の状態が変更される。 スタック 先ほど例として挙げた「 push argument 2 」と「 pop 1 〇 cal 1 」という一連 のコマンドについて考えてみよう。そのような VM 命令において使用するメモリはス タックである。メモリのデータ値を、あるセグメントから別のセグメントへと単純に 移動することはできない。そのためには、スタックを経由する必要がある。スタック が VM アーキテクチャにおける中心的な存在であるにもかかわらず、 VM 言語ではス

262 い 1 章コンバイラ # 2 : コード生成 メモリ割り当てとメモリアクセス う ) 、「 that 0 」参照を使ってその配列の要素にアクセスする。 ントが所望の配列要素のアドレスを指すように設定し ( 「 p 〇 inter 1 」を使 VM 関数の中で配列の要素にアクセスするためには、最初に仮想 that セグメ の整数である。 ゴ幻 dex 」参照を使って各フィールドへアクセスする。ここで index は 0 以上 が現在のオプジェクトを指すように設定し ( 「 pointer o 」を使う ) 、「 this のオプジェクトのフィールドへアクセスするためには、仮想 thi s セグメント Jack のメソッドまたは Jack のコンストラクタに対応する VM 関数の中で、そ st at i c セグメントを用いて、割り当てとアクセスが行われる。 . j ack クラスファイルのスタティック変数は、対応する . vm ファイルの仮想 とアクセスが行われる。 Jack サプルーチンの引数は、仮想 argument セグメントを用いて、割り当て 当てとアクセスが行われる。 Jack サプルーチンのローカル変数は、仮想 1 〇 cal セグメントを用いて、割り サブルーチン呼び出し トのべースに設定する VM コードをコンパイラは挿入しなければならない。 モリプロックの割り当てを行い、そのオプジェクトのべースを thi s セグメン Jack のコンストラクタをコンパイルする場合、新しいオプジェクトのためにメ を正しく設定する VM コードをコンパイラは挿入しなければならない。同様に Jack のメソッドを VM 関数へコンパイルする場合、 this セグメントのべース するオプジェクトの参照を渡す必要がある。 メソッドに対応する場合、最初にブッシュする引数として、そのメソッドが属 引数をスタックにブッシュしなければならない。呼び出された VM 関数が Jack VM 関数を呼び出す前に、呼び出し側 ( それ自体も VM 関数である ) は関数の うにする。 高水準言語の v 。 id サプルーチンは値を返さない。これに対応するためには次のよ VOid メソッドとファンクションからのリターン

7.5 プロジェクトー 163 規約 VM から Hack へ変換する変換器を書くこと。この変換器は 7.2 節の「 VM 仕様 ( 第 1 部 ) 」と 7.3.1 節の「 Hack プラットフォームの標準 VM マッピング ( 第 1 部 ) 」を満 たさなければならない。本プロジェクトではテスト用に VM プログラムが与えられて いる。あなたが実装した VM 変換器を用いて、この VM プログラムを Hack アセンプ リ言語で書かれたプログラムへ変換せよ。あなたの変換器が生成するアセンプリプロ グラムを本書の CPU 工ミュレータで実行するときは、テストスクリプトと比較ファ イルを用いてテストを行うこと。 7.5.1 実装についての提案 変換器を実装するにあたり、次に示す 2 段階のステージを経て行うことを推奨する。 そのようにすれば、ユニットテストを用いて段階的に進めることができる。 ステージ # 1 : スタック算術コマンド 最初のバージョンとして、 VM 言語の 9 つのスタック算術と論理コマンド、そして このコマンドは先の 9 つのコマンドをテストす 「 push constant x 」コマンド る際に役立つ一一一を実装する。「 push constant x 」コマンドは、汎用的な push コマンドにおける特別なケース ( 最初の引数が c 〇 nstant 、ふたつ目の引数が 10 進 数の定数である ) に該当する。 ステージ # 2 : メモリアクセスコマンド 次のバージョンでは、 VM 言語の pu sh と pop コマンドを実装し、 8 つのメモリセ グメントを扱う。本ステージは次に示す順番で進めることを推奨する。 1 . 2. 3. 4. constant セグメントはすでに対応済みである。 1 〇 cal 、 argument 、 this 、 that セグメントに対応する。 続いて、 p 〇 inter と temp セグメントに対応する。特に、 this と that セグ メントのべースの修正ができるようにする。 最後に、 static セグメントに対応する。

7.3 実装ー 157 p 〇 inter 、 temp このふたつのセグメントは RAM 上の決められた領域に直接マッピングされて いる。 p 〇 inter セグメントは RAM の 3 ~ 4 番目の場所 ()H 工 s と THAH) に マッピングされ、 t emp セグメントは 5 ~ 12 番目の場所 ()5 、 R6 、 、 R12 ) にマッピングされる。そのため、「 poi nt er 幻によるアクセスは RAM 内の 3 十ツ番目のアドレスへ、「 temp 幻は 5 十乞番目のアドレスへとアクセスする アセンプリコードへ変換されるべきである。 C 〇 n S t a n 亡 このセグメントは対象のアーキテクチャ上で物理領域を占有しないため、完全 に仮想的な存在である。 VM 実装は「 constant 幻というアクセスを単に定 数値のツとして扱うだけである。 s t at 土 c Hack 機械語の仕様によると、アセンプリプログラム内で新しいシンボルに最初 に出くわした場合、アセンプラはそのシンポルに新しい RAM アドレスを割り 当てる。この RAM アドレスは 16 番目から始まるアドレスである。 VM ファイ ルを f 、スタティック変数の値を j とすると、アセンプリ言語のシンボルは f . j として表現することができる。たとえば、 xxx . vm には「 push static 3 」 というコマンドが含まれているとしよう。このコマンドは「@xxx . 3 」と「 D=M 」 という Hack のアセンプリコマンドへ変換することができる。さらに、 D の値 をスタックにブッシュするアセンプリコードがその後に続く。この st at i c セ グメントの実装方法はいくらかトリッキーではあるが、要件は満たしている。 アセンブリ言語のシンボル こでは再度、 VM 実装によって使用されるアセンプリ言語のシンポルをすべて示 す。この VM 実装は標準マッピングに対応する。

1 1 . 1 背景 253 シュテープルであり、ハッシュテープルは単一のスコープを示す。リストの要素はリ ストの次の要素の中にネスト化されていることを意味する。たとえば、コンパイラが 現在のスコープにおけるテープル内で識別子を見つけることができなければ、リスト の次のテープルで、その識別子を探そうとする。そのため、もし x が、あるコードセ グメント ( たとえば、メソッド ) で宣言されていなければ、 x はそのセグメントを所 有するコードセグメント ( たとえば、クラス ) で宣言されているかもしれない。 変数操作 どのようなコンパイラを開発するにしても、必す遭遇する基本的な問題がある。それ は、ソースプログラムで宣言されるさまざまな型の変数を、対象とするプラットフォー ム上へどのように対応づけるか、という問題である。これは簡単な問題ではない。そ もそも変数の型が異なれば、それに必要なメモリサイズも異なる。そのため、メモリ と変数のマッピングは 1 対 1 に対応しない。さらに、変数の属性が異なれば、そのラ イフサイクルも異なる。たとえば、スタティック変数はひとつだけ存在し、プログラ ムが実行されている間すっと存在するようにしなければならない。一方、クラスがイ ンスタンス化されれば、インスタンスごとにフィールド変数をコピーし、インスタン スが破棄されるタイミングで、そのインスタンスのメモリを再利用できるようにしな ければならない。また、サプルーチンが呼ばれるたびに、新しいローカル変数と引数 のコピーが生成される必要がある一一再帰呼び出しを行う場合、この必要性が明らか になるであろう。 以上が " 悪い知らせ " である。しかし、これには " 良い知らせ " もある。それは、 のような困難な作業はすでに解決済みである、ということでる。我々が採用した 2 段 階構成のアーキテクチャでは、変数のメモリ割り当てはバックエンドである VM が代 わりに行う。特に、我々が 7 章と 8 章で構築したバーチャルマシンは、ほとんどの高 水準言語で必要とされる変数の属性一一スタティック変数、ローカル変数、引数、オ に対応できるメカニズムを備えている。変数の プジェクトのフィールド変数など 割り当てと破棄に関する詳細は、グローバルスタックと仮想メモリセグメントを使っ て、 VM のレベルで扱われる。 このような機能は簡単には実現できないことをもう一度思い出そう。実際、グロー バルスタックと仮想メモリセグメントをハードウェアのプラットフォーム上へマッピ ングする VM 実装を、これまで頑張って作ってきたのである。そして、この努力が報 われるのは、 、一衄がどのような言語であったとしても、カから VM へ んといつ新ⅱロ

286 い 2 章オペレーティンクシステム このアルゴリズムは明らかにむだが多い。なぜなら、使わなくなったオプジェクト の領域を再利用しないからである。 改善版メモリ割り当てアルゴリズム ルゴリズムは破棄したメモリプロックを女 e な t に追加する。詳細は図 12-7 に示す。 使用していないオプジェクトのメモリプロックを再利用する命令を実行した場合、ア 体は女 e から取り除かれる。 域が残されていなければ、または、残された領域が小さすぎたら、そのセグメント全 り当てを行った後に残された部分セグメントになる。もしそのセグメントにメモリ領 値は破棄するときに用いる ) 。続いて、女 e の中でこのセグメントが更新され、割 場所、つまりわん c ん [ ー 1 ] の場所には、そのセグメントの長さが保持されている。この たメモリセグメントの開始場所がリターンされるが、そのリターンされるひとつ前の セグメントが見つかれば、必要なメモリプロックがそこから取られる ( 割り当てられ 要求されたサイズを満たすことができる最初のセグメントを見つける。一旦、適した 要求されたサイズに最も近いセグメントを見つける。一方、 first-fit アルゴリズムは、 めのよく知られたヒューリスティックな方法がふたつある。 best-fit アルゴリズムは、 は女 ee カを探し、適したセグメントを見つけなければならない。この探索を行うた あるサイズのメモリプロックを割り当てるように命令した場合、このアルゴリズム 図 12-7 ( 左上 ) では、一般的な厄畆の状態を図示する。 と segment . next==segment[l] という記法を用いて実装することができる。 たっ分 ) に格納することができる。たとえば、 segment.length==segment [0] へのポインタである。このふたつのフィールドは、セグメントの最初のメモリ位置 ( ふ 含む。ふたつのフィールドとは、自身のセグメントの長さと、リストの次のセグメント て管理する。この連結リストを女“ s と呼ぶ。各セグメントはふたつのフィールドを このアルゴリズムは、利用可能なメモリセグメントを連結リスト (linkedlist) を使っ

358 ー付録 B テストスクリプト言語 that は ] that セグメントの i 番目の値。 temp[i] t emp セグメントの i 番目の値。 VM セグメントへのポインタ 10Ca1 RAM 内における 1 〇 ca 1 セグメントのべースアドレス。 a rgument RAM 内における argument セグメントのべースアドレス。 SP currentFunction スタックポインタの値。 RAM の i 番目の値。 は ] 実装に関係する変数 RAM 内における that セグメントのべースアドレス。 that RAM 内における thi s セグメントのべースアドレス。 this た位置にプレークポイントを設定するために用いることができる。 「 sys . init . 3 」が含まれる。これは、読み込んだ VM プログラムにおいて、選択し たとえば、 sys . init ファンクションの 3 行目に到達したとき、 1 ine 変数には ー fu 月 c 〇月は「関数内の行番号」を意味する。 ここで current—functi 〇 n—name は「現在の関数の名前」、 line—index— Current—funCti 〇 n—name . _line—index—in—functi 〇 n 次の形式の文字列を含む ( 読み込み専用 ) 。 line 現在実行している関数の名前 ( 読み込み専用 ) 。

156 ー 7 章バーチャルマシン # 1 : スタック操作 Hack 機械語の仕様によると、アセンプリプログラム内では、 RAM アドレスの 0 か ら 15 番目は RO から RI 5 のシンポルを用いて参照することができる。さらに、 RAM アドレスの 0 から 4 番目 ( つまり、 R0 から R4 ) はシンポルの sp 、 LCL 、 ARG 、 TH 工 s 、 THAT を用いて参照できることが仕様書に書かれてある。実際、この仕様は、 VM 実 装の可読性を高める目的を見通してアセンプリ言語に導入したものである。これらの VM 環境におけるレジスタは次に示す使われ方を想定する。 レジスタ RAM[()I RAMIII RAM121 RAM[31 RAM141 RAM 一 121 RAM 卩 3 ー 1 司 名前 S P LCL ARG T H 工 S THAT 使用法 スタックポインタ : スタックの最上位の次を指す。 現在の VM 関数における loca セグメントの べースアドレスを指す。 現在の VM 関数における argument セグメントの べースアドレスを指す。 現在の ( ヒープ内における ) this セグメントの べースアドレスを指す。 現在の ( ヒープ内における ) that セグメントの べースアドレスを指す。 temp セグメントの値を保持する。 汎用的なレジスタとして VM 実装で用いることができる。 メモリセグメントマッピング 10Ca1 、 argument 、 this 、 that これらのセグメントは RAM 上に直接マッピング ( 対応づけ ) されている。そ の RAM 上の場所を保持するために、専用のレジスタ ( それぞれ LCL 、 ARG 、 TH 工 s 、 THAT に対応 ) に物理べースアドレスが保持される。そのため、これら のセグメントにおいて乞番目の要素へのアクセスは、 RAM 内の ( se 十り番 目のアドレスへアクセスするアセンプリコードへ変換されるべきである。 で base は各セグメント用のレジスタに格納された値である。

freeList 4 データ構造 9 5 freeList 4 12.1 背景ー 訓 oc ( 5 ) の後 6 3 287 5 returned block lnit ializ at ion: freeList = / 肥叩召 0 “ 女 ee 力なた〃 e = null 女“力なたんル = / 肥叩カ e ル s me れたん〃可ん > s た e を満たすセグメントを得るために alloc(size) : / / s た e で指定された大きさのメモリを割り当てる 図 1 2 - 7 改善版メモリ割り当ての概要 ( 再利用あり ) カ℃ e 力なに s me を追加する seg 襯 e れみ = 0 の e 屋ー 1 deAIIoc( 0 り ec り : / / 使わないオブジェクトの破棄を行う Return わ / oc ん わ / oc んに = size 十 1 / / 破棄に備え、プロックサイズを記憶する 割り当てを反映するために女託 s を更新する ( もしくは、残るセグメントが小さい場合、そのセグメントすべて ) わ / oc ん = 見つかったセグメントで必要な部分セグメント ( もしくはデフラグを行う ) そのようなセグメントが見つからない場合、失敗を返す best ー fit またはⅱ rst 一蹴アルゴリズムを用いて女“力なを探索する