B仮想マシン

ここでは、Mae-Bにおける仮想マシン(BVM: B Virtual Machine)について説明します。

メモリ空間

BVMは、実行環境のint型を1ワードとして動作します。

BVMがひとつのプログラムのために割り当てる領域は64Kワードです。その中の配置は下図の通り。

組み込み関数用ダミー領域
Mae-Bはいくつかの組み込み関数(printf()とか)を持っていますが、これらはCで実装されています。本来こういうものもBで作るべきかもしれませんが手を抜いています。そういった組み込み関数の呼び出しアドレスとして予約してあるのがこの領域です。この領域のアドレスをCALLするとそれぞれに対応した組み込み関数が動きます(たとえば0番地をCALLするとprintf()が動く)。
この領域には何のコードもデータも格納しませんが、処理系化アプリケーションコードの何らかのバグで「うっかり実行されてしまった」時に早期に気付けるよう、UNREACHABLE命令で埋めてあります。
関数の実行プログラム領域
ここに関数に含まれるプログラムのバイトコードを格納します。main()関数が先頭に来るとは限らないので、コンパイラはコンパイル終了時にmain()の開始アドレスも返し、実行時にはそこから実行を開始するようにしています(compiler/parser.cのBVM_Compile()関数を参照)。
文字列リテラル領域
プログラム中の文字列リテラルがこの領域に格納されています。
静的変数領域
静的変数の値を格納する領域です。ここで、静的変数とは、グローバル変数とラベルを指します。
「グローバル変数はともかく、ラベルは何の関係が?」と思った人はこちらの謎を参照のこと。
ヒープ領域

getvec()関数による動的メモリ割り当てで割り当てられる領域です。下端をheap_end_addressというレジスタで保持しており、現在の領域で足りなくなればこれの値が増えてヒープ領域が下に伸びます。
スタック領域
スタックのための領域です。最大値のアドレスである65535から上に向かって(アドレスの小さいほうに)伸びます。

BVMインストラクションリファレンス

※「スタック」欄の凡例：

[呼び出す前のスタックの状態] → [呼び出し後のスタックの状態]の形式で記載しています。
[]内で一番右が、スタックのトップです。
「op1」というのは、ひとつめのオペランドを意味します(現状、オペランドは最大でもひとつしかないですが)。
[]内にはできるだけ何の値かわかるように書いたつもりですが、特にその必要もないと思えるものは単にvalue、またはvalue1, value2, ...と書いています。

No.	命令	オペランド	意味	スタック
1	`UNREACHABLE`	なし	絶対に通らないところに配置する不正命令。この命令が実行されたらエラーメッセージを出力して終了する。	[] → []
2	`PUSH`	pushする整数値	整数をスタックにpushする。	[] → [op1]
3	`PUSH_AUTO`	pushする変数のベースレジスタからのオフセット	自動変数の値をスタックにpushする。	[] → [自動変数の値]
4	`PUSH_STATIC`	pushする値を格納しているアドレス。	指定したアドレスの内容をスタックにpushする。	[] → [アドレスの内容]
5	`POP_AUTO`	pop先の変数のベースレジスタからのオフセット	スタックのトップの値を自動変数にpopする。	[value] → []
6	`POP_STATIC`	pop先のアドレス	スタックトップの値を指定したアドレスにpopする。	[value] → []
7	`PUSH_AUTO_ADDRESS`	対象の変数のベースレジスタからのオフセット	自動変数のアドレスをスタックにpushする。	[] → [自動変数のアドレス]
8	`PUSH_BY_STACK`	なし	スタックトップに格納されているアドレスに格納されている値をpushする。	[アドレス] → [左のアドレスの内容]
9	`POP_BY_STACK`	なし	スタックトップのアドレスに、スタックの2番目に格納されている値をpopする。	[value, ポップ先のアドレス] → []
10	`POP`	なし	スタックトップの値をひとつ捨てる。	[value] → []
11	`PUSH_N`	スタックを進める数	オペランドの数だけスタックポインタを進める(オペランドの数だけダミーの値をpushするような動作。ただしスタックの内容自体は変化しない)。	[] → [dummy1, dummy2, dummy3, ...(op1の数だけ)]
12	`POP_N`	スタックを戻す数	オペランドの数だけスタックポインタを戻す(オペランドの数だけダミーの値をpopするような動作)。	[dummy1, dummy2, dummy3, ...(op1の数だけ)] → []
13	`DUPLICATE`	なし	スタックトップの値をスタックトップにpushする。	[value] → [value, value]
14	`ADD`	なし	スタックトップのふたつの値を加算してスタックに積む。	[value1, value2] → [value1 + value2]
15	`SUB`	なし	スタックの2番目の値からスタックトップの値を減算してスタックに積む。	[value1, value2] → [value1 - value2]
16	`MUL`	なし	スタックトップのふたつの値を乗算してスタックに積む。	[value1, value2] → [value1 * value2]
17	`DIV`	なし	スタックの2番目の値をスタックトップの値で除算してスタックに積む。	[value1, value2] → [value1 / value2]
18	`MOD`	なし	スタックの2番目の値をスタックトップの値で割った余りをスタックに積む。	[value1, value2] → [value1 % value2]
19	`MINUS`	なし	スタックトップの値の符号を逆転させた値をスタックに積む。	[value] → [-value]
20	`LEFT_SHIFT`	なし	スタックの2番目の値をスタックトップの値だけ左シフトした値をスタックに積む。	[value1, value2] → [value1 << value2]
21	`RIGHT_SHIFT`	なし	スタックの2番目の値をスタックトップの値だけ右シフトした値をスタックに積む。	[value1, value2] → [value1 >> value2]
22	`EQ`	なし	スタックの2番目の値とスタックトップの値を比較し、等しければ1を、等しくなければ0をスタックに積む。	[value1, value2] → [value1 == value2]
23	`NE`	なし	スタックの2番目の値とスタックトップの値を比較し、等しければ0を、等しくなければ1をスタックに積む。	[value1, value2] → [value1 != value2]
24	`GT`	なし	スタックの2番目の値とスタックトップの値を比較し、2番目の値 > スタックトップの値であれば1を、そうでなければ0をスタックに積む。	[value1, value2] → [value1 > value2]
25	`GE`	なし	スタックの2番目の値とスタックトップの値を比較し、2番目の値 >= スタックトップの値であれば1を、そうでなければ0をスタックに積む。	[value1, value2] → [value1 >= value2]
26	`LT`	なし	スタックの2番目の値とスタックトップの値を比較し、2番目の値 < スタックトップの値であれば1を、そうでなければ0をスタックに積む。	[value1, value2] → [value1 < value2]
27	`LE`	なし	スタックの2番目の値とスタックトップの値を比較し、2番目の値 <= スタックトップの値であれば1を、そうでなければ0をスタックに積む。	[value1, value2] → [value1 <= value2]
28	`LOGICAL_NOT`	なし	スタックトップの値が0であれば1を、0でなければ0をスタックに積む。	[value] → [!value]
29	`BIT_AND`	なし	スタックの2番目の値とスタックトップの値の論理積を取得しスタックに積む。	[value1, value2] → [value1 & value2]
30	`BIT_OR`	なし	スタックの2番目の値とスタックトップの値の論理和を取得しスタックに積む。	[value1, value2] → [value1 \| value2]
31	`BIT_XOR`	なし	スタックの2番目の値とスタックトップの値の排他的論理和を取得しスタックに積む。	[value1, value2] → [value1 ^ value2]
32	`BIT_NOT`	なし	スタックトップの値のビットNOTを取得しスタックに積む。	[value] → [~value]
33	`JUMP`	ジャンプ先のアドレス	オペランドで指定されたアドレスにジャンプする。	[] → []
34	`JUMP_IF_TRUE`	ジャンプ先のアドレス	スタックトップの値が非ゼロなら、オペランドで指定されたアドレスにジャンプする。	[value] → []
35	`JUMP_IF_FALSE`	ジャンプ先のアドレス	スタックトップの値がゼロなら、オペランドで指定されたアドレスにジャンプする。	[value] → []
36	`JUMP_STACK`	なし	スタックトップのアドレスにジャンプする。	[value] → []
37	`CALL`	なし	スタックトップのアドレスの関数を呼び出す。詳細は「関数呼び出し」を参照。	[argn, ..., arg2, arg1] →[argn, ..., arg2, arg1, nargs, base, pc]
38	`SAVE_RETURN_VALUE`	なし	スタックトップの値を、戻り値用レジスタに退避する。	[] → [value]
39	`RETURN`	なし	関数から戻る。実行中の関数が`main()`関数だったら処理を終了する。詳細は「関数呼び出し」を参照。	[argn, ..., arg2, arg1, nargs, base, pc] →[argn, ..., arg2, arg1, nargs]
40	`PUSH_RETURN_VALUE`	なし	戻り値用レジスタの値をpushする。	[] → [value]

レジスタ

BVMは仮想的なCPUなので、当然レジスタもあります(実態は単なるローカル変数またはファイル内static変数ですが)。

pc
プログラムカウンタ(program counter)です。現在実行中のコードのアドレスを指します。
sp
スタックポインタ(stack pointer)です。スタックの一番上の要素の一つ上(次にpushされる要素のが入るところ)を指します。
base
ベースポインタ。実行中の関数の、最初のローカル変数のアドレスを指します。ローカル変数と引数は、ベースポインタからの相対距離で参照します(「関数呼び出し」も参照)。コンパイラが頑張ればspからの距離でも参照できるのでしょうが、そこまで頑張れないのでbaseレジスタを導入しました。
return_value
関数からの戻り値を保持するレジスタです。呼び出された関数側でいったん戻り値をreturn_valueに格納し(SAVE_RETURN_VALUE)、呼び出し側でそれを取り出してスタックに積みます(PUSH_RETURN_VALUE)。
current_arg_count
現在実行中の関数の引数の数です。
heap_start_address
ヒープ領域の開始アドレスです。実行を開始したら動きません。
heap_end_address
ヒープ領域の終了アドレスです。ヒープ領域が不足すると一定サイズ単位で(現実装では1024ワード)増えます。

関数呼び出し

Bから、組み込み関数以外の、Bで作られた関数を呼ぶ場合、以下のような動きになります。

呼び出し側で、引数を後ろからスタックに積む。
呼び出し側で、引数の数をスタックに積む。
呼び出し側で、呼び出し先のアドレスをスタックに積む。
CALL命令の実行。これにより以下が行われる。
1. スタックに、現在のプログラムカウンタとベースポインタを退避する。
2. 引数の数をレジスタcurrent_arg_countにセットする。
3. 呼び出し先関数のアドレスをプログラムカウンタにセットする。
呼び出された側で、ローカル変数の数ぶん、PUSH_Nによりスタックを伸ばしてローカル変数の領域を確保する。

図にするとスタックは以下のようになっています(これは、関数が呼び出されて、呼び出された側のプログラムがちょっと動いて計算のためにスタックが使われている状態だと思ってください)。

こうなっていれば、ローカル変数と引数は、すべてbaseからの固定の相対距離(オフセット)で参照できます。命令の中のPUSH_AUTOとかPOP_AUTOとかオペランドはこのオフセットです。

関数の実行が終わってリターンするときの動きは以下。

呼び出され側で、戻り値をスタックに積む。
呼び出され側で、スタックに積んだ戻り値を、return_valueレジスタに退避する。
呼び出され側で、スタックポインタを戻して自身のローカル変数の領域を解放する。
RETURNを実行する。これにより、プログラムカウンタとベースポインタが復元され、呼び出し元に処理が戻る。
呼び出し側で、引数の数+1だけスタックを減らして(spの値を増やして)引数をスタックから除去する。+1なのは、「引数の数」もスタックに積んでいるから。
return_valueレジスタに退避された戻り値をスタックに積む(ただし、関数呼び出しだけからなる式文では、この手順は無駄なので省略する)。

組み込み関数

printf(fmt, arg1, arg2, ...)
Cと同じようなprintf()です。%c、%d、%o、%sが使えますが、桁数とかの指定はできません。
putnumb(val)
整数valを表示します。GCOS8版のputnumb()を見るとオプションで桁数とか埋める文字の指定ができるようですが、その機能はありません。
putchar(ch)
chを標準出力に出力します。ここで、chには最大4文字が格納されている可能性があります。
getchar()
標準入力から1文字取得します。ここでの1文字はASCIIの1文字です。1回で4文字取れたりはしません。
char(s, n)
文字列sのn番目(0オリジン)の文字を取得します。
lchar(s, n, c)
文字列sのn番目(0オリジン)にcを格納します。
getstr(s)
標準入力から改行までの文字列を読み込んで、sにセットします。
putstr(s)
文字列sを標準出力に出力します。
nargs()
現在の関数の引数の数を返します。
getvec(n)
ヒープからn+1ワードの領域を返します。
rlsevec(v, n)
getvec()で確保した領域vを解放します。nはその領域のサイズです。
dump_free_list()
getvec(), rlsevec()のテストのために私が付けたもので、普通は使いません。
exit()
プログラムを終了します。現状の実装では、インタプリタの呼び出し元に戻るのではなくて、プログラムそのものを(Cの)exit(0)で終了します(手抜きです)。

こうした組み込み関数は、以下のような形式で定義されていて、BVMから呼び出されます(これはputnumb()の例)。

static int
fun_putnumb(int argc, int *args, int *memory)
{
    return fprintf(st_current_output, "%d", args[0]);
}

argcは引数の数、argsは引数の配列で、args[0], args[1], ... と指定することで順に引数が取り出せます。memoryは、BVMが確保している64Kワードの領域そのものの先頭アドレスです。たとえば最初の引数でポインタが渡されたら、memory[args[0]]でそのポインタの指す先の内容を取り出すことができます。

ヒープ(getvec(), rlsevec())

getvec(), rlsevec()はCのmalloc()とfree()に相当する関数です。

ただし、Cのfree()は開放すべき領域のポインタだけ渡せばよいですが、Bのrlsevec()は開放すべき領域へのポインタと、その領域のサイズも必要です。

なぜこうなっているのか、どんな実装であるべきなのか、いろいろ考えました。

まず、MH-TSS版のリファレンスのrlsevec()の説明を見ると、こんなことが書いてあります。

-- this function releases the n+1 words of the static vector v back to the system. Calling this routine with an automatic vector v as argument results in immediate or eventual disaster!

訳)-- この関数は静的ベクトル v の n+1 ワードをシステムに解放する。自動ベクトル v を引数としてこのルーチンを呼び出すと、即時または遅延した災害を引き起こす！

そりゃまあ自動変数の領域を開放したらろくでもないことが起きるでしょうが、じゃあ静的変数ならいいの? というのが気になります。そもそも「この関数は静的ベクトルvの～」とか書いてあるし。

それどころか、GCOS8版のマニュアルを見ると、こんなことが書いてあります。

All memory allocation is done by manipulating a linked list of free memory called the free list. The free list initially includes the so-called "core hole". You can use RLSEVEC to return any area of memory which is not on the free list, as long as the address of the memory is greater than the load address of RLSEVEC. If you attempt to release memory which is already on the free list, in whole or in part, RLSEVEC immediately aborts your program.

訳)すべてのメモリ割り当ては、フリーリストと呼ばれる空きメモリの連結リストを操作することで行われます。フリーリストには初期状態ではいわゆる「コアホール」が含まれています。RLSEVECを使用すれば、そのメモリのアドレスがRLSEVECのロードアドレスより大きい限り、フリーリスト上にない任意のメモリ領域を返すことができます。フリーリスト上に既に存在するメモリを、全体または一部を問わず解放しようとすると、RLSEVECは直ちにプログラムを中止します。

「任意のメモリ領域を返すことができます」と書いてある……

このあたりをいろいろ考えた結果、以下のようにしました。

メモリは、空きエリアを連結リストで保持することで管理する。使用中の領域は連結リストにつながないし、ヘッダ情報も持たない。
getvec()が呼び出されたら、フリーリストから十分な領域の空きエリアを探し、そこから必要な分を切り出して返す。空きエリアはその分縮める。
rlsevec()が呼び出されたら、その領域の中にヘッダを埋めてフリーリストにつなぐ。ただし、前後に空きエリアがあった場合、その連結(coalescing)は行う。

coalescingが要るかどうかは迷いましたが、この方法でcoalescingなしだと、たとえば「連結リストを作るので固定サイズの領域をたくさんgetvec()する」という(たいへんよくある)コードを書いたとき、rlsevec()で領域を解放しても、その領域はgetvec()した領域よりヘッダ分狭いので、結局再利用できません。さすがにそれでは使えないよなあ、ということでcoalescingありとしました。GCOS8のマニュアルを見ると「フリーリスト上に既に存在するメモリを、全体または一部を問わず解放しようとすると、RLSEVECは直ちにプログラムを中止します」とあり、こんなことができるならrlsevec()の度にフリーリストをひととおりスキャンしているということでもありますし。

そして、この方式だと、普通の静的変数の配列を、rlsevec()で以降のgetvec()で使えるように「返す」ことができます。

公開日: 2026/01/18

間違い等ありましたら、掲示板にご連絡願います。

前のページ(実装) | 次のページ(コンパイラの実装) | ひとつ上のページへ戻る | トップページへ戻る