【低レイヤ入門】C言語で作る自作VMを少しOSらしくする: small-asmの分岐先をラベルで書く | UNIX Cafe

自作VM開発記 18

この連載では、C言語で小さなVM（仮想マシン）を作っています。ここでのVMは、自分で決めた命令を読み、数値を保存したり文字を表示したりするプログラムです。今回は、そのVMで動かすプログラムの「移動先」を、数字の代わりに名前で書けるようにします。

前回は、自作アセンブラの small-asm にメモリ操作とサブルーチン呼び出しの書き方を追加しました。アセンブラは、MOVI R0, 65 のような文字で書いた命令を、VMが読める数値へ変換する道具です。命令を書くファイルを .asm、変換した数値を保存するファイルを .bin としています。small-asmは手元のパソコンで変換を担当し、VMはできあがったファイルを実行します。

その結果、AとBをメモリへ保存し、同じ表示処理を2回呼ぶプログラムを書けました。ただし、呼び出し先は CALLI 0x28 と数値で指定しています。表示処理の前に命令を追加すると、表示処理の位置も変わります。今回は、その位置をsmall-asmに数えてもらいます。

Day 38: tools/small-asm.c
        programs/asm-label-call.asm
        tools/test-small-asm-labels.py

今回の練習ノートとコードは、GitHubの handmade-vm-os に置いています。

今回のゴールは、同じAとBを名前付きの呼び出しで表示すること

まず、追加後のサンプルを動かします。Cコンパイラとmakeを用意し、このプロジェクトの Makefile があるディレクトリで次を実行してください。CコンパイラはCのソースを実行ファイルへ変換する道具、makeは必要な生成手順を順に実行する道具です。

make run-asm-label-call

ビルド時のコマンド表示を除くと、結果は次の3行です。キーボードから文字を入力する必要はありません。

A
B
CPU halted.

前回と同じ表示ですが、呼び出し先の書き方が変わっています。programs/asm-label-call.asm の命令列を見てみましょう。このコードは説明だけの記法ではなく、今回のsmall-asmで変換できます。

; Day 38: the same bytes as asm-memory-call.asm, with forward references.
MOVI R1, 0x500
MOVI R0, 65
STB [R1], R0
INC R1
MOVI R0, 66
STB [R1], R0
MOVI R1, 0x500
CALLI print_byte
CALLI print_byte
HALT

print_byte:
LDB R0, [R1]
SYSCALL 0
INC R1
RET

R0やR1は、数値を一時的に持つレジスタです。メモリは番号の付いた保存場所が並んだもので、その番号をアドレス、または番地と呼びます。MOVI R1, 0x500 はR1へ保存先の番号を入れ、STB [R1], R0 はその番号のメモリへR0の下位1バイトを書き込みます。角括弧の付いた [R1] は、R1そのものではなく、R1が指す保存場所です。

65と66は、それぞれAとBの文字コードです。文字コードは、文字を数値で表すための対応です。最初の7命令でAとBを隣り合う場所へ保存し、R1をAの位置へ戻しています。続く2個の CALLI print_byte が、同じ表示処理を呼びます。

呼び出される処理は print_byte: の次からです。LDBで1バイト読み、SYSCALL 0で文字と改行を表示します。INC R1で次の位置へ進み、RETで呼び出し元の続きへ戻ります。このように、呼び出して使い、終わったら戻る処理をサブルーチンと呼びます。1回目はA、2回目はBを読み、2回目から戻った後はHALTで停止します。

ラベルは、命令の位置に付ける名前

今回追加する print_byte: のような名前がラベルです。末尾のコロンは「ここで名前を定義する」という印です。CALLI print_byte のように使う側にはコロンを付けません。この使い方をラベルの参照と呼びます。

CALLI print_byte  ; 名前を参照する
HALT

print_byte:      ; この位置に名前を付ける
RET

この短い例では、print_byteの前にCALLIとHALTの2命令があります。このVMの命令は、どれも4バイトの固定長です。1バイトは8個のビットをまとめた単位で、メモリの1番地に入る量です。命令は0番地から詰めて置くため、最初の命令は0、次は4、その次は8番地になります。したがって、この短い例のprint_byteは8番地です。

ラベルの行自体は命令ではないので、4バイトを消費しません。空行やコメントも位置を進めません。ソースの行番号を4倍するのではなく、それまでに現れた命令の個数を4倍するのがポイントです。

AとBを表示する本来のサンプルでは、print_byteの前に10命令あります。そのため、10×4 = 40番地になります。16進数では 0x28 です。0x は16進数の印で、0x28は2×16+8を意味します。前回手で書いていた数値と、同じ値になります。

命令数    配置先       内容
0         0x00         MOVI R1, 0x500
...
7         0x1C         CALLI print_byte
8         0x20         CALLI print_byte
9         0x24         HALT
10        0x28         print_byte: LDB R0, [R1]
11        0x2C         SYSCALL 0
12        0x30         INC R1
13        0x34         RET

VMへ渡すファイルには、print_byteという名前やコロンは入りません。small-asmが名前を0x28へ置き換えてから数値を書き出します。VMが受け取るのは、これまでと同じ命令列です。このため、今回はVM本体の実行処理を変更しません。

名前の規則と、使える場所を小さく決める

実装の前に、manual/specs/038-small-asm-labels.md へ仕様カードを書きます。ラベル名は、ASCIIの英字かアンダースコアで始め、その後に英数字かアンダースコアを続けます。ASCIIとは、A〜Zなどを数値へ対応させる文字コードの規格です。ここでは日本語などを名前には使わず、loop、print_byte、_done2 のような名前に絞ります。長さは63文字までです。

命令名と同じように、ラベルも大文字・小文字を区別しません。loop と LOOP は同じ名前です。定義は最大256個で、同じ名前を2回定義するとエラーにします。違う名前なら、別の行で同じ位置へ付けることもできます。

entry:
start: MOVI R0, 65
       HALT

この例のentryとstartは両方とも0番地です。ラベルだけの行にも、ラベルの後に命令を続ける行にも対応します。ただし、1行に書ける定義は1個までとします。コロンの前後には空白を入れられます。

名前を参照できるのは、JUMP、JZ、JNZ、CALLIの宛先です。JUMPは無条件で移動し、JZとJNZは比較結果に応じて移動する命令です。CALLIは戻り先を保存して移動します。いずれも、以前からの数値指定も使えます。MOVIとSYSCALLは今回も数値だけを受け付けます。

JUMP loop
JZ done
JNZ loop
CALLI print_byte
CALLI 0x28

この5行は書き方の例です。実際に変換するファイルでは、使った名前をどこかで定義する必要があります。loop+4 のような計算式、文字列データ、配置先を飛ばす指示はまだ扱いません。まずは「命令数を数えるだけで位置が決まる」という条件で、名前の解決に集中します。

後ろに書いた名前を使うため、入力を2回読む

サンプルでは、CALLIが先に現れ、print_byteの定義は後ろにあります。このように、定義より前に名前を使うことを前方参照と呼びます。1行ずつ読んですぐ出力するだけでは、CALLIを読んだ時点で移動先が分かりません。そこで、入力を2回読みます。1回の読み取りをパスと呼ぶことがあり、今回は2パスの変換です。

1回目は、命令を数えながら、名前とアドレスの対応表を作ります。CALLIのところで未登録の名前が出ても、名前の書式を確認するだけにします。後ろのprint_byteへ到達すると、その時点の命令数が10なので、表へ40を登録できます。

1回目: 定義を集める
名前          アドレス
PRINT_BYTE    40（0x28）

2回目: 表を使って参照を解決する
CALLI print_byte → CALLI 0x28 → 0x69000028

2回目に先頭へ戻ると、すでに表が完成しています。今度はCALLIの参照先を表で調べて、本当の命令値へ変換できます。前方参照だけでなく、前の位置へ戻る後方参照にも同じ表を使います。入力を何度も書き直したり、VMが実行中に名前を探したりする必要はありません。

この仕組みは、すべての命令が4バイトだから小さく作れます。ラベルの値が後から決まっても、命令の長さは変わらないので、1回目で数えた位置を2回目にも使えます。変換中に入力ファイルを書き換えないこと、先頭へ戻せるファイルを入力にすることも前提にします。

Cの配列へ、名前とアドレスを保存する

実装は tools/small-asm.c に追加します。表の1行を表すLabelには、名前とアドレスをまとめます。Cの構造体は、このように関連する値をひとまとまりで扱うための型です。

#define MAX_LABEL_LENGTH 63
#define MAX_LABELS 256

typedef struct {
    char name[MAX_LABEL_LENGTH + 1];
    uint32_t address;
} Label;

static Label labels[MAX_LABELS];
static unsigned int label_count;

名前の配列を64個にしているのは、最大63文字に加えて、Cの文字列の終わりを表す0を保存するためです。addressは32ビットの符号なし整数です。labelsは最大256組を置く配列、label_countは今いくつ登録しているかを表します。今回の規模では、検索するときは先頭から名前を1つずつ比べるだけにします。

行の準備を担当する prepare_line は、まずセミコロンか#以降のコメントを取り除きます。コメント内のコロンを定義と間違えないためです。次に大文字へ揃え、コロンがあれば左側をラベル名として検査します。1回目に限って、まだ同じ名前がないことと上限を確認し、表へ登録します。

strcpy(labels[label_count].name, name);
labels[label_count++].address = address;

これは検査が済んだ後の登録部分です。strcpyで名前をコピーし、同じ要素へアドレスを入れてからlabel_countを1増やします。アドレスは呼び出し側が instruction_count * 4 で渡します。同じ行に命令が続く場合は、ラベルを登録した後に命令を数えるため、その命令の先頭位置を正しく指します。

数値と名前を、同じ宛先の値へ揃える

命令の後ろに書く値やレジスタなどの指定を、オペランドと呼びます。たとえば CALLI print_byte のオペランドはprint_byteです。今回、分岐とCALLIのオペランドを読むところに parse_target を使います。

static int parse_target(const char *text, uint32_t *value) {
    if (parse_imm20(text, value)) {
        return 1;
    }
    if (!valid_label(text)) {
        return 0;
    }
    if (current_pass == 1) {
        *value = 0; /* All definitions will be available on pass 2. */
        return 1;
    }
    if (!find_label(text, value)) {
        diagnostic = "undefined label";
        return 0;
    }
    return 1;
}

最初のparse_imm20は、従来からある数値の検査です。数値として読めれば、その値をそのまま使います。数値ではない場合は、valid_labelで名前の規則を確認します。名前としても不正なら変換失敗です。

1回目の *value = 0 は、実行先を0番地へ決める処理ではありません。命令の構文を確認するための仮の値です。1回目の命令値は出力しません。2回目になるとfind_labelで表を調べ、本当のアドレスをvalueへ入れます。定義がない場合は undefined label を診断として返します。

名前が数値へ変わった後は、以前と同じ命令値の作り方が使えます。CALLIは 0x69000000 に宛先を組み合わせます。0x28なら 0x69000028 です。ファイルには上位のバイトから順に 69 00 00 28 と書きます。この順番をbig-endianと呼びます。表を作る部分は増えましたが、VMへ渡す4バイトの形式は同じです。

重複と未定義を、入力した行で知らせる

名前を使うと、書き間違いの種類も増えます。同じ名前を2回定義すると、どちらへ移動すべきか決められません。これは1回目の登録で検出します。一方、名前の書式が正しくても、最後まで定義がない場合があります。こちらは全定義が集まった2回目に検出します。

loop: HALT
LOOP: RET

この入力は2行目が重複です。大小文字を区別しないため、別名にはなりません。診断には入力ファイルのパスと行番号が付きます。たとえばファイル名が /tmp/duplicate.asm なら、次の形式です。

/tmp/duplicate.asm:2: duplicate label

HALT
JUMP missing

この入力では、2行目で使うmissingが定義されていないため undefined label になります。実行時にHALTで止まるかどうかにかかわらず、small-asmはファイル全体を検査します。変換に失敗したときの終了コードは1、成功したときは0です。終了コードは、コマンドを呼んだ側が成功・失敗を判断するための数値です。

また、今回は2回目の変換結果をいったん一時ファイルへ書きます。全行の変換に成功してから指定された出力ファイルを開くため、後半で未定義の名前が見つかっても、以前作った.binを上書きしません。一時ファイルにはCの tmpfile を使います。ただし、最終出力への書き込み自体が失敗した場合まで元のファイルを保持する仕組みではありません。

アドレスの上限も確認します。分岐やCALLIの宛先に使える領域は20ビットで、0〜0xFFFFFです。4バイト境界の最後の命令先頭は0xFFFFCになります。262144命令の直後は0x100000なので、その位置のラベルはエラーにします。これは命令形式としての上限です。VMのメモリに収まるか、データや戻り先の保存領域に重ならないかまで、アセンブラが保証するわけではありません。

バイトの一致と、命令を挿入した後の動きを確かめる

まず、前回の数値版と今回のラベル版を比較します。プロジェクトのディレクトリで次を実行します。

make programs/asm-memory-call.bin programs/asm-label-call.bin
cmp programs/asm-memory-call.bin programs/asm-label-call.bin

cmpは2つのファイルの内容を比べるコマンドです。一致していれば何も表示せず、終了コード0になります。今回はどちらも14命令、56バイトです。表示だけでなくファイル全体が一致するので、名前の解決が従来の数値指定と同じ命令列になっていることを確認できます。

次に、配置が変わる例を考えます。ラベル版のHALTとprint_byteの間へ、次のように1命令を挿入します。

HALT
INC R7

print_byte:
LDB R0, [R1]

この位置のINC R7は、直前にHALTがあるので通常の流れでは実行されません。ただし、ファイル内では4バイトを占めます。そのため、print_byteの位置は0x28から0x2Cへ移動します。2個のCALLIは名前のままなので、再変換すれば両方とも 0x6900002C になります。数値版なら呼び出し側も手で直す必要があった箇所です。

この挿入版は自動テストの一時ファイル内で作ります。配布するサンプルは数値版と同じ56バイトのままです。テストでは、呼び出し先の数値が変わったことと、実際にVMでA・Bを表示することを別々に確かめます。

make test-small-asm test-small-asm-labels

自動テストにはPython 3が必要です。makeのコマンド表示などを除くと、結果は次のようになります。

small-asm: 57 cases passed
small-asm-labels: 44 cases passed

前回は59ケースでしたが、そのうち「ラベルだけの行」と「未定義のCALLI」の2件は、今回のラベル用テストへ移しています。ラベルだけの行は成功になり、未定義のCALLIは専用の診断になるためです。既存の命令値、不正なレジスタ、数値の範囲などの確認は続けています。

ラベル用テストでは、4種類の命令の前方・後方参照、数値との混在、コメント、空行、名前の63文字上限、256定義の上限、アドレスの上限を確認します。不正入力では、出力がまだない場合と、すでに出力がある場合の両方を試します。さらにJZとJNZで繰り返す小さなプログラムもVMへ渡し、参照を解決した後の実行まで確かめます。

次は、文字列もソースへ書くための準備へ

今回、small-asmは命令の位置へ名前を付け、前方参照を含めて数値のアドレスへ変換できるようになりました。命令を増減しても、呼び出す側は同じ名前を使えます。画面に表示されるAとBは同じですが、プログラムを変更するときに手で数え直す箇所が減りました。

一方、これまで作ったechoコマンドのプログラムには、プロンプトや比較語などの文字列も必要です。現在はCで書いた専用の生成プログラムで、それらのデータを配置しています。次は、文字列をアセンブリのソースへ書くための最小仕様を考えます。文字の長さ、終わりを示す0、次の命令を置く位置、MOVIでデータの場所を指定する方法を、小さな例から決めていきます。

続く第19回では、small-asmに .string と .align 4 を追加し、命令と表示する文字列を同じソースへ書けるようにします。文字列の長さに合わせて後ろの命令の位置を揃え、ラベルで指定した文字列を表示する流れを、命令と文字列を同じソースへ書くで確認していきましょう。