【低レイヤ入門】C言語で仮想マシン自作：命令追加とスタック操作、vm.c 整理まで進める | UNIX Cafe

前回は、小さな自作VMをCで作りながら、LDB命令を例に「アセンブリを書く人の目線」と「VMを作る人の目線」の違いを整理しました。

今回は、その続きです。

VMに命令を少しずつ追加して、メモリへの32bit書き込み、レジスタ操作、スタック操作まで進めました。最後に、命令が増えて長くなったnotes/vm.cを、少し読みやすい形に整理しました。

この記事で扱う命令は次の5日分です。

Day 11: STDI
Day 12: INC / DEC
Day 13: MOV
Day 14: PUSH
Day 15: POP

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

今回のゴール

前回までで、VMは次のようなことができるようになっていました。

即値をレジスタへ入れる
メモリから1 byte読む
メモリへ1 byte書く
メモリから4 byte読む
SYSCALLで1文字を表示する

ただ、これだけだとまだ「CPUらしい動き」としては少し物足りません。

例えば、レジスタの値を別のレジスタへコピーしたり、値を1つ増やしたり、スタックに一時退避したりすることができません。

そこで今回は、次の3つを増やします。

1. 4 byteをメモリへ書く
2. レジスタ同士、レジスタ単体の操作を増やす
3. スタックに値を積んで、あとで取り出す

この3つが入ると、VMの中で「値を置く」「値を動かす」「一時的に退避する」という基本動作がかなり見えてきます。

STDI で32bit値をメモリへ書く

まず追加したのはSTDIです。

STDIは、レジスタの32bit値を、命令の中に直接書かれたアドレスへ保存する命令です。

前回までに作ったLDDIは、即値アドレスから4 byteを読んでレジスタへ入れる命令でした。

LDDI: memory -> register
STDI: register -> memory

つまり、STDIはLDDIの逆向きです。

STDIの仕様

名前: STDI
分類: direct memory instruction
目的: レジスタの32bit値を、即値アドレスで指定したVM内メモリへ4 byteで書く
命令長: 4 byte
bit配置:
  bits 31..28: type = 5
  bits 27..24: op = 1
  bits 23..20: rd = source register
  bits 19..0 : imm = immediate address
読むレジスタ: rd
書くレジスタ: なし
読むメモリ: なし
書くメモリ: memory[imm] から memory[imm + 3] までの4 byte

ここで大事なのは、rdの意味です。

rdという名前は、destination registerの略として使うことが多いです。ただし、命令によって役割が少し変わることがあります。

STDIでは、レジスタへ書くのではなく、レジスタからメモリへ書きます。そのため、この命令ではrdを「書き込み元レジスタ」として使っています。

STDI R0, 0x10

このコードは、次のように読めます。

R0の32bit値を
memory[0x10] から4 byteで書く

32bit値を4 byteに分ける

このVMでは、命令fetchも、32bit値の読み書きも、big-endianでそろえています。

例えば、R0に次の値が入っているとします。

R0 = 0x12345678

これをメモリに4 byteで書くと、次の順番になります。

memory[0x10] = 0x12
memory[0x11] = 0x34
memory[0x12] = 0x56
memory[0x13] = 0x78

Cでは、次のように書きます。

memory[imm] = (regs[rd] >> 24) & 0xFF;
memory[imm + 1] = (regs[rd] >> 16) & 0xFF;
memory[imm + 2] = (regs[rd] >> 8) & 0xFF;
memory[imm + 3] = regs[rd] & 0xFF;

シフトして、必要な1 byteだけを取り出し、順番にmemoryへ入れています。

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

R0=0x12345678
memory[0x10..0x13]=12 34 56 78
STDI test passed.

INC / DEC でレジスタの値を1つ増減する

次に、レジスタの値を1つ増やすINCと、1つ減らすDECを追加しました。

ここまでの命令は、メモリを読んだり書いたりするものが中心でした。INCとDECは、レジスタの中身そのものを変更します。

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

INC: type=2, op=0 -> 0x20000000
DEC: type=2, op=1 -> 0x21100000

type=2を、レジスタの値を計算する命令の分類として使うことにしました。

テストする命令列

MOVI R0, 0x10
MOVI R1, 0x10
INC R0
DEC R1
HALT

最初にR0とR1へ同じ値を入れます。

そのあと、INC R0でR0を1増やし、DEC R1でR1を1減らします。

R0: 0x10 -> 0x11
R1: 0x10 -> 0x0F

Cコードとしては、とても短いです。

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

ここで使うfieldはrdだけです。rsやimmは使いません。

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

R0=0x00000011
R1=0x0000000F
INC/DEC test passed.

小さい命令ですが、これでVMの中でレジスタの値を変化させられるようになりました。

MOV でレジスタからレジスタへコピーする

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

MOVは、あるレジスタの値を、別のレジスタへコピーする命令です。

MOV: type=1, op=0 -> 0x10200000
MOV R2, R0        -> 10 20 00 00

type=1は、レジスタ同士で値を動かす命令の分類として使うことにしました。

MOVは「移動」ではなくコピー

MOVという名前を見ると、元の場所から値が消えて、別の場所へ移動するように感じるかもしれません。

しかし、今回のMOVはコピーです。

MOVI R0, 0x12345
MOV R2, R0
HALT

この命令列では、まずR0に0x12345を入れます。そのあと、MOV R2, R0でR0の値をR2へコピーします。

Cではこうなります。

regs[rd] = regs[rs];

MOV R2, R0なら、decodeした結果は次のようになります。

rd = 2
rs = 0

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

regs[2] = regs[0];

regs[0]の値は消えません。同じ値がregs[2]にも入ります。

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

R0=0x00012345
R2=0x00012345
MOV test passed.

PUSH でスタックへ値を積む

ここから、スタックを使う命令に入ります。

まずはPUSHです。PUSHは、レジスタの32bit値をスタックへ積む命令です。

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

PUSH: type=7, op=0 -> 0x70000000
PUSH R0            -> 70 00 00 00

type=7は、スタックを扱う命令の分類として使います。

このVMのスタックは下方向に伸びる

このVMでは、SPの初期値を0x00100000にしています。

メモリサイズは1MBなので、有効なメモリアドレスは0x00000000から0x000FFFFFまでです。

SP = 0x00100000は、ちょうどメモリの末尾の1つ外側を指しています。ここを「空のスタック」として扱います。

スタックは下方向に伸びるので、PUSHするときは、先にSPを4減らします。

初期SP: 0x00100000
PUSH後: 0x000FFFFC

そのあと、memory[SP]から4 byteを書き込みます。

sp -= 4;
memory[sp] = (regs[rd] >> 24) & 0xFF;
memory[sp + 1] = (regs[rd] >> 16) & 0xFF;
memory[sp + 2] = (regs[rd] >> 8) & 0xFF;
memory[sp + 3] = regs[rd] & 0xFF;

ここでも、32bit値の書き込み順はbig-endianです。

0x12345678
-> 12 34 56 78

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

R0=0x12345678
SP=0x000FFFFC
memory[SP..SP+3]=12 34 56 78
PUSH test passed.

PUSHが動くと、レジスタの値を一時的にメモリの上のほうへ退避できるようになります。

POP でスタックから値を取り出す

PUSHを作ったら、次はPOPです。

POPは、スタックから32bit値を取り出して、レジスタへ入れる命令です。

POP: type=7, op=1 -> 0x71100000
POP R1            -> 71 10 00 00

PUSHがop=0、POPがop=1です。同じtype=7の中に、スタック操作の命令を並べています。

POPは読んでからSPを戻す

POPでは、まずSPが指している場所から4 byteを読みます。

そのあと、4 byte取り出したので、SPを4増やします。

POP前: SP = 0x000FFFFC
POP後: SP = 0x00100000

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

regs[rd] =
    ((uint32_t)memory[sp] << 24) |
    ((uint32_t)memory[sp + 1] << 16) |
    ((uint32_t)memory[sp + 2] << 8) |
    ((uint32_t)memory[sp + 3]);
sp += 4;

読み取り順はLDDIと同じくbig-endianです。

12 34 56 78
-> 0x12345678

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

R1=0x12345678
SP=0x00100000
POP test passed.

PUSHとPOPがそろうと、「一度値を退避して、あとで戻す」という動きが作れるようになります。

ここまでの命令一覧

Day 15までで、命令は次のようになりました。

それぞれの命令の詳しい説明は、GitHubの HANDWRITING_GUIDE.md 置いています。

こうして一覧にすると、typeごとに命令の分類が少し見えてきます。

type=3は、レジスタが指すメモリを読む・書く命令です。type=5は、命令の中に入っている即値アドレスを使ってメモリを読む・書く命令です。type=7は、スタックを扱う命令です。

最初はただの数字だったtypeとopが、だんだん命令表らしくなってきました。

命令が増えたので vm.c を整理した

ここまで命令を追加していくと、notes/vm.cのmain()がかなり長くなりました。

最初は、全部がmain()に入っていても気になりませんでした。小さいコードなら、上から順番に読めるからです。

しかし、命令が増えてくると、次の処理が混ざって分かりにくくなります。

memoryへの命令配置
fetch
decode
execute
エラーチェック
実行ループ

そこで、一度命令を増やすのを止めて、vm.cを整理しました。

VM状態を構造体にまとめる

まず、VMの状態をVM構造体にまとめました。

typedef struct {
    uint8_t memory[MEMORY_SIZE];
    uint32_t pc;
    uint32_t sp;
    uint32_t regs[REGISTER_COUNT];
    bool running;
} VM;

今までは、memory、pc、sp、regs、runningを、それぞれ別の変数として持っていました。

構造体にまとめると、関数に渡すときにVM *vmだけで済みます。

decode結果も構造体にする

次に、decodeした結果もDecodedInstにまとめました。

typedef struct {
    uint32_t raw;
    uint8_t type;
    uint8_t op;
    uint8_t rd;
    uint8_t rs;
    uint32_t imm;
} DecodedInst;

rawには、fetchした32bit命令そのものを入れます。

type、op、rd、rs、immには、命令を分解して取り出したfieldを入れます。

これで、execute()側では「decode済みの命令」として扱えます。

big-endianの読み書きを共通化する

今回のVMでは、32bit値を読むところ、書くところが何度も出てきます。

命令fetchでも4 byteを読みます。LDDIやPOPでも4 byteを読みます。STDIやPUSHでは4 byteを書きます。

毎回同じシフトとマスクを書くと、間違えやすくなります。そこで、read_u32_be()とwrite_u32_be()に分けました。

static uint32_t read_u32_be(const uint8_t *memory, uint32_t address) {
    return ((uint32_t)memory[address] << 24) |
           ((uint32_t)memory[address + 1] << 16) |
           ((uint32_t)memory[address + 2] << 8) |
           ((uint32_t)memory[address + 3]);
}

static void write_u32_be(uint8_t *memory, uint32_t address, uint32_t value) {
    memory[address] = (value >> 24) & 0xFF;
    memory[address + 1] = (value >> 16) & 0xFF;
    memory[address + 2] = (value >> 8) & 0xFF;
    memory[address + 3] = value & 0xFF;
}

これで、LDDIの実行はかなり短くなります。

vm->regs[inst.rd] = read_u32_be(vm->memory, inst.imm);

STDIも同じです。

write_u32_be(vm->memory, inst.imm, vm->regs[inst.rd]);

fetch / decode / execute / run に分ける

VMの実行は、基本的に次の繰り返しです。

fetch
decode
execute

そこで、この流れが見えるようにrun()を作りました。

static void run(VM *vm) {
    while (vm->running) {
        uint32_t inst;

        if (!fetch(vm, &inst)) {
            return;
        }

        execute(vm, decode(inst));
    }
}

この形にすると、main()はかなり短くなります。

int main(void) {
    VM vm = {0};

    vm.pc = 0x00000000;
    vm.sp = 0x00100000;
    vm.running = true;

    load_test_program(&vm);
    run(&vm);

    return 0;
}

main()だけを見ると、VMを初期化して、テストプログラムを読み込み、実行する、という流れが分かりやすくなりました。

命令の細かい処理はexecute()へ、命令の配置はload_test_program()へ移しています。

動作確認

整理したあとも、統合VMの実行結果は変えないようにしました。

cc vm.c -o vm
./vm

実行結果は次の通りです。

A
CPU halted.

警告つきのコンパイルも確認しました。

cc -Wall -Wextra -Werror vm.c -o vm

命令を増やしたあとにvm.cを整理すると、見た目は大きく変わります。こういうときは、実行結果が変わっていないことを確認しておくと安心です。

今回分かったこと

Day 11からDay 15までで、VMの命令はかなり増えました。

メモリを読む
メモリへ書く
レジスタを変更する
レジスタ間で値をコピーする
スタックへ積む
スタックから取り出す

最初はHALTで止まるだけだったVMが、少しずつCPUの命令セットらしくなってきました。

特にPUSHとPOPが入ったことで、SPが意味を持ち始めました。スタックは、関数呼び出しや一時退避を考えるときに避けて通れないので、ここで小さく動かせたのは大きいです。

一方で、まだ足りないものもあります。

足し算、引き算
比較
条件フラグ
ジャンプ
条件分岐

今のVMは、上から順番に命令を実行するだけなので、条件によって処理を変えたり、同じ場所へ戻ってループしたりすることはできません。

次に実装する命令は、ADD、SUB、CMP、JUMP、JZあたりが候補になります。

まとめ

今回は、Day 11からDay 15までの命令追加と、vm.cの整理を行いました。

• STDIで32bit値をメモリへ書けるようにしました
• INC / DECでレジスタの値を1つ増減できるようにしました
• MOVでレジスタ間コピーができるようにしました
• PUSH / POPでスタックへ値を積み、取り出せるようにしました
• 命令が増えたので、vm.cをfetch、decode、execute、runへ分けました

完成したVMから見ると、まだ本当に小さい一歩です。

ただ、命令を1つずつ仕様にし、テストし、Cコードに落とし込む流れは少しずつ見えてきました。

次に進むこと

次回は、VMを「上から順番に実行するだけ」から一歩進めて、ADD/SUBによる計算、CMPとzero_flagによる比較、JUMP/JZ/JNZによる分岐、CALLI/RETによるサブルーチン呼び出しを追加します。