【低レイヤ入門】C言語で自作VMに計算・比較・分岐・CALL/RETを追加する | UNIX Cafe

前回は、小さな自作VMにSTDI、INC、DEC、MOV、PUSH、POPを追加しました。

値をメモリへ書く、レジスタ同士でコピーする、スタックへ退避する、というところまで進みました。

ただし、この段階のVMは、まだ基本的には上から順番に命令を実行するだけです。

今回はそこから一歩進めて、計算、比較、分岐、サブルーチン呼び出しを追加します。

Day 16: ADD / SUB
Day 17: CMP
Day 18: JUMP / JZ
Day 19: JNZ
Day 20: CALLI / RET

最後に、統合VMのnotes/vm.cへSYSCALL 1も入れて、メモリ上の0終端文字列を表示できるようにします。

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

今回のゴール

今回のゴールは、VMに次の4つの力を足すことです。

1. レジスタ同士で計算する
2. レジスタ同士を比較する
3. 条件によってPCを書き換える
4. サブルーチンを呼んで戻る

ここまで入ると、VMの中で「処理の流れ」を作れるようになります。

JUMPで別の場所へ移動し、CMPの結果を使ってJZやJNZで分岐し、CALLIとRETで呼び出し元へ戻ります。

ADD / SUB でレジスタ同士を計算する

まず追加したのは、足し算のADDと引き算のSUBです。

命令番号は次のようにしました。

ADD: type=2, op=2
SUB: type=2, op=3

type=2は、レジスタの値を計算する命令の分類として使っています。前回追加したINCとDECも、このtype=2に入れていました。

ADD / SUB の仕様

名前: ADD / SUB
分類: register arithmetic instruction
目的: レジスタ同士で足し算、引き算をする
命令長: 4 byte
bit配置:
  bits 31..28: type = 2
  bits 27..24: op = 2 または 3
  bits 23..20: rd
  bits 19..16: rs
読むレジスタ: rd, rs
書くレジスタ: rd
読むメモリ: なし
書くメモリ: なし
PCの変化: fetch時に +4
条件フラグの変化: なし

ADD R0, R1は、R0とR1を足して、結果をR0へ戻します。

ADD R0, R1
-> R0 = R0 + R1

SUB R2, R3も同じ形です。R2からR3を引いて、結果をR2へ戻します。

SUB R2, R3
-> R2 = R2 - R3

ここで、rdは読むレジスタでもあり、書くレジスタでもあります。rsは読むだけです。

テストする命令列

MOVI R0, 10
MOVI R1, 3
ADD R0, R1

MOVI R2, 10
MOVI R3, 3
SUB R2, R3
HALT

期待する結果は、R0 = 13とR2 = 7です。

R0: 10 + 3 = 13 = 0x0000000D
R2: 10 - 3 = 7  = 0x00000007

Cコードでは、次の処理になります。

regs[rd] += regs[rs];
regs[rd] -= regs[rs];

今回のADD R0, R1なら、decodeした結果は次のようになります。

rd = 0
rs = 1

したがって、Cコードへ当てはめるとこうなります。

regs[0] += regs[1];

テスト結果はこうなりました。

R0=0x0000000D
R2=0x00000007
ADD/SUB test passed.

これでVMの中で、レジスタ同士の基本的な計算ができるようになりました。

CMP と zero_flag で比較結果を残す

次に追加したのはCMPです。

CMPは、2つのレジスタを比較する命令です。ただし、比較した結果をレジスタへ書き込みません。代わりに、VMの状態として持っているzero_flagを書き換えます。

CMP: type=2, op=4

VMの状態には、次のfieldを追加します。

bool zero_flag;

CMP の仕様

名前: CMP
分類: register compare instruction
目的: 2つのレジスタを比較し、等しければzero_flagをtrueにする
命令長: 4 byte
bit配置:
  bits 31..28: type = 2
  bits 27..24: op = 4
  bits 23..20: rd
  bits 19..16: rs
読むレジスタ: rd, rs
書くレジスタ: なし
読むメモリ: なし
書くメモリ: なし
PCの変化: fetch時に +4
条件フラグの変化: regs[rd] == regs[rs] なら zero_flag = true

CMPのCコードは、次の1行が中心です。

vm->zero_flag = vm->regs[inst.rd] == vm->regs[inst.rs];

ここで大事なのは、CMPがレジスタの値を変えないことです。

R0 = 10
R1 = 10
CMP R0, R1

R0は10のまま
R1は10のまま
zero_flag = true

比較結果だけをzero_flagへ残します。この結果を、次に追加するJZやJNZが使います。

テスト結果

テストでは、同じ値の比較と、違う値の比較を両方確認しました。

MOVI R0, 10
MOVI R1, 10
CMP R0, R1

MOVI R2, 10
MOVI R3, 3
CMP R2, R3
HALT

first_cmp_zero=true
second_cmp_zero=false
R0=0x0000000A
R1=0x0000000A
R2=0x0000000A
R3=0x00000003
CMP test passed.

1回目の比較では10 == 10なのでtrueになり、2回目の比較では10 == 3ではないのでfalseになりました。

JUMP / JZ でPCを書き換える

次に、実行位置を変える命令を追加します。

今までのVMは、命令を1つ読むたびにPCが4ずつ進んでいました。

0x00 の命令を読む
-> PC = 0x04

0x04 の命令を読む
-> PC = 0x08

JUMPやJZは、このPCを命令側で書き換えます。

JUMP: type=6, op=8
JZ:   type=6, op=10

fetch後にPCを書き換える

このVMでは、fetchの時点でPCを+4します。

*inst = read_u32_be(vm->memory, vm->pc);
vm->pc += 4;

そのため、executeでJUMPを実行するときには、PCはすでに次の命令を指しています。

JUMPは、そのPCをジャンプ先アドレスで上書きします。

vm->pc = inst.imm;

JZは、zero_flagがtrueのときだけPCを書き換えます。

if (vm->zero_flag) {
    vm->pc = inst.imm;
}

ジャンプ先は、命令を4 byte読める範囲である必要があります。範囲外へ飛ぶと、次のfetchが壊れるからです。

static bool can_fetch(uint32_t address) {
    return address <= MEMORY_SIZE - 4;
}

JUMP / JZ のテスト

テストでは、最初にJUMPで途中の命令を飛ばします。

JUMP 0x10
MOVI R0, 99
HALT

MOVI R0, 1
MOVI R1, 1
CMP R0, R1
JZ 0x28
MOVI R2, 99
HALT

MOVI R2, 7
HALT

JUMP 0x10が効いていれば、MOVI R0, 99は実行されません。

そのあと、R0とR1に同じ値を入れてCMPします。zero_flagはtrueになるので、JZ 0x28でMOVI R2, 7へ飛びます。

R0=0x00000001
R1=0x00000001
R2=0x00000007
zero_flag=true
JUMP/JZ test passed.

R0が99ではなく1になり、R2も99ではなく7になっています。つまり、JUMPとJZの両方で実行位置を変えられています。

JNZ で「等しくないなら飛ぶ」を作る

JZの次は、逆向きの条件分岐としてJNZを追加しました。

JNZ: type=6, op=11

JZは、zero_flagが立っているときにジャンプします。JNZは、zero_flagが立っていないときにジャンプします。

JZ:
  同じだったら飛ぶ

JNZ:
  違っていたら飛ぶ

Cコードでは、条件が反対になるだけです。

if (!vm->zero_flag) {
    vm->pc = inst.imm;
}

JNZ のテスト

MOVI R0, 1
MOVI R1, 2
CMP R0, R1
JNZ 0x18
MOVI R2, 99
HALT

MOVI R2, 7
HALT

R0は1、R1は2なので、CMP R0, R1の結果はfalseです。

そのため、JNZ 0x18でジャンプし、MOVI R2, 99は実行されません。

R0=0x00000001
R1=0x00000002
R2=0x00000007
zero_flag=false
JNZ test passed.

CMP、JZ、JNZがそろうと、かなり小さい形ですが、if文に近い流れをVM上で作れるようになります。

CALLI / RET でサブルーチンを呼んで戻る

次に追加したのは、サブルーチン呼び出しのCALLIと、呼び出し元へ戻るRETです。

CALLI: type=6, op=9
RET:   inst == 0x02000000

CALLIは、JUMPに似ています。どちらもPCを別のアドレスへ変えます。

違いは、CALLIは戻り先を覚えることです。

JUMP:
  飛ぶだけ

CALLI:
  戻り先PCをスタックへ積んでから飛ぶ

CALLI の動き

CALLIでは、fetch後のPCを戻り先として使います。

0x00: CALLI 0x20
0x04: MOVI R1, 7

CALLIをfetchした直後のPC = 0x04
戻り先PC = 0x04

その戻り先PCをスタックへ積み、最後にPCを呼び出し先へ変更します。

1. fetch後のPCを戻り先として使う
2. SPを4減らす
3. memory[SP..SP+3] に戻り先PCを書く
4. PC = imm

Cコードではこうなります。

vm->sp -= 4;
write_u32_be(vm->memory, vm->sp, vm->pc);
vm->pc = inst.imm;

RET の動き

RETは、CALLIで積んだ戻り先PCをスタックから取り出します。

1. memory[SP..SP+3] から戻り先PCを読む
2. SPを4増やす
3. PC = return_address

Cコードではこうなります。

uint32_t return_address = read_u32_be(vm->memory, vm->sp);
vm->sp += 4;
vm->pc = return_address;

CALLIでSPを4減らし、RETでSPを4増やします。呼び出しと戻りが正しく対応していれば、最後のSPは元の値に戻ります。

CALLI / RET のテスト

CALLI 0x20
MOVI R1, 7
HALT

; 0x20
MOVI R0, 42
RET

最初にCALLI 0x20で、0x20にあるサブルーチンへ飛びます。

サブルーチン側ではR0に42を入れて、RETで戻ります。戻ったあとは、CALLIの次にあるMOVI R1, 7を実行します。

R0=0x0000002A
R1=0x00000007
SP=0x00100000
CALLI/RET test passed.

R0にサブルーチン側の値が入り、R1に戻ったあとの値が入っています。さらにSPも初期値の0x00100000へ戻っています。

これで、VMの中に「呼び出して戻る」という流れを作れました。

統合VMに SYSCALL 1 を入れる

最後に、統合VMのnotes/vm.cへSYSCALL 1を入れました。

SYSCALL 0は、R0の下位1 byteを文字として表示する命令でした。

SYSCALL 0:
  R0の下位1 byteを文字として表示する

今回入れたSYSCALL 1は、R0をアドレスとして使います。そのアドレスから0終端までを文字列として表示します。

SYSCALL 1:
  R0が指す0終端文字列を表示する

文字列表示の関数は次のようにしました。

static void print_string(VM *vm, uint32_t address) {
    while (address < MEMORY_SIZE && vm->memory[address] != 0) {
        putchar(vm->memory[address]);
        address++;
    }
}

SYSCALLの実行側では、inst.immを見て処理を分けます。

if (inst.imm == 0) {
    putchar(vm->regs[0] & 0xFF);
    putchar('\n');
} else if (inst.imm == 1) {
    print_string(vm, vm->regs[0]);
}

ここで混同しやすいのは、PCとR0の役割です。

PC:
  次に読む命令の場所

R0:
  SYSCALL 1で表示したい文字列の場所

PCは命令を読むためのアドレスです。SYSCALL 1では、R0に入っている値をデータのアドレスとして使います。

統合VMの実行結果

notes/vm.cでは、0x100から次の文字列を置いています。

VM flow complete.\n\0

そして、R0へ0x100を入れてからSYSCALL 1を実行します。

MOVI R0, 0x100
SYSCALL 1
HALT

統合VMの実行結果はこうなりました。

A
VM flow complete.
CPU halted.

最初のAは、これまでのSYSCALL 0の確認です。そのあとにSYSCALL 1で、メモリ上の文字列VM flow complete.を表示しています。

ここまでの命令一覧

今回追加した命令を一覧にすると、次のようになります。

type=2には、レジスタの値を扱う計算・比較命令が増えました。

type=6には、SYSCALLに加えて、PCを変える命令が増えました。ここにJUMP、JZ、JNZ、CALLIが入っています。

今回分かったこと

今回の大きな変化は、VMが「上から順番に実行するだけ」ではなくなったことです。

ADD / SUB:
  レジスタ同士で計算する

CMP:
  比較結果をzero_flagへ残す

JUMP / JZ / JNZ:
  PCを書き換えて実行位置を変える

CALLI / RET:
  戻り先PCをスタックへ積んで、呼び出し元へ戻る

SYSCALL 1:
  メモリ上の0終端文字列を表示する

特にPCを書き換える命令が入ると、VMの見え方が変わります。

命令はメモリ上に順番に置かれています。しかし、実際に実行される順番は、必ずしもメモリ上の順番とは限りません。JUMPやCALLIがPCを変えると、次に読む命令も変わります。

また、CALLIとRETでは、前回作ったスタックが本格的に役割を持ち始めました。

PUSHとPOPの時点では、スタックは値の一時退避場所でした。今回のCALLIでは、戻り先PCを保存する場所として使っています。

まとめ

今回は、Day 16からDay 20までで、計算、比較、分岐、サブルーチン呼び出しを追加しました。

• ADD / SUBでレジスタ同士の計算ができるようにしました
• CMPで比較結果をzero_flagへ残せるようにしました
• JUMP / JZ / JNZでPCを書き換え、実行位置を変えられるようにしました
• CALLI / RETで、戻り先PCをスタックへ積んで呼び出し元へ戻れるようにしました
• SYSCALL 1で、メモリ上の0終端文字列を表示できるようにしました

まだ外部の.binを読み込むVMにはなっていません。今のnotes/vm.cは、内蔵テストプログラムを実行する統合VMです。

次は外部バイナリローダーを追加して、./vm program.binの形で小さなバイナリを実行できるようにします。まずはMOVI R0, 65、SYSCALL 0、HALTだけの最小プログラムを外から読み込むところまで進めます。

次に進むこと

前回作った分岐やCALL/RETの上に、今度は外部の .bin ファイルを読み込む仕組みを追加します。VM本体と実行するプログラムを分け、hello.bin の実行から最小アセンブラまで進めます。