しかくいさんかく

解答略のメモ

8日目: [CPU] 命令セットの策定

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の8日目の記事です。

今日はこれまでに出てきた機械語命令を振り返り、自作するCPUの仕様を決定する。

実際にFPGAでCPUを作るのは、明日明後日やる予定。

初日から一週間経った

昨日までの一週間を振り返ると、

という順序でCPUを育ててきた。 その過程でたくさんの機械語命令が誕生した。 これらを一度まとめておこう。

レジスタの種類

これまでに出現したレジスタをまとめて、ついでに名前もつける。

名前 種類 サイズ 用途 初出
a, b, c, d 計算用レジスタ 8bit 加減算と、スタックの出し入れ 4日前にレジスタを複数化したとき
sp スタックポインタ 8bit 次にデータを入れるメモリスタックのアドレスを保持 昨日のメモリに値を書き込むところ
ip ブログラムカウンタ 8bit 次の機械語のメモリアドレスを保持 昨日の上から二番目の画像
zf ゼロフラグ 1bit 計算結果がゼロだと1、ゼロでなければ0 初出

これらのレジスタは全てDフリップフロップを並べた素子だ。 超重要な話なので、意味がわからなければ4日前の1bit1レジスタのCPUを復習して欲しい。

命令セット

これまでに登場したCPUの命令を、復習を兼ねてまとめる。ついでに2進数の機械語も定めておく。

ニーモニック 機械語(2進数) 命令長 説明
mov x, y 0000 xx yy 8bit x = y
add x, y 0001 xx yy 8bit x = x + y
sub x, y 0010 xx yy 8bit x = x - y
cmp x, y 0011 xx yy 8bit x - y でフラグを更新
mov x, imm 0100 xx 00 imm 16bit x = imm
add x, imm 0101 xx 00 imm 16bit x = x + imm
sub x, imm 0110 xx 00 imm 16bit x = x - imm
cmp x, imm 0111 xx 00 imm 16bit x - imm でフラグ更新
push x 1000 xx 00 8bit スタックメモリにxを積む
pop x 1001 xx 00 8bit スタックメモリからxに値を引き出す
jmp imm 1100 00 00 imm 16bit プログラムカウンタipにimmを加算してジャンプ
jz imm 1101 00 00 imm 16bit zf=1ならipにimmを加算してジャンプ
jnz imm 1110 00 00 imm 16bit zf=0ならipにimmを加算してジャンプ
hlt 1111 00 00 8bit 停止

まずニーモニックの欄と機械語の欄をざっと見て欲しい。 movpushといった単語(オペコードという)が、機械語の最初4桁にほぼ対応している。

オペコードの後には、レジスタ名やimmが入っている。これをオペランドという。

オペコードを順番に見ていくと、最初の8個(mov, add, sub, cmp)は計算命令になっている。 オペランドのxとyは、それぞれa, b, c, dのいずれかを表している。 機械語の欄のxxとyyは、レジスタを2進数で指定している。その対応は

レジスタ名 (x) 2進数による指定 (xx)
a 00
b 01
c 10
d 11

cmp命令は初登場なので説明すると、引算したつもりでゼロフラグだけ更新し、元のレジスタの値は変更しない命令だ。 つまりcmp a, bの実行結果は、aとbが等しければzf=1になり、異なればzf=0になる。

5番目から8番目の命令にはimmが入っている。具体例で説明すると

mov a, 0x1234 ; a に 0x1234を代入

という命令の0x1234immだ。immは8bit (1byte)の数字になっている。 こうした数字のことを即値(immediate number)と言う。 即値はメモリから読み取る必要があるので、即値入りの命令は命令長が伸びることに注意してほしい。

残りの命令はメモリとのやりとりに関するものだ。これらは昨日説明したので、詳細を省く。

サンプルコード

ここまで、レジスタ機械語(01の列)を定めて、分かりやすいようにニーモニックも定義した。 命令は全部で12個しかなく、現実のCPUと比べると貧弱だ。 こんなのを作ったところで、意味のある計算は何もできない気がする。

しかし、それは大きな間違いだ。 実際は相当複雑な計算をこなすことができる。

このCPUが完成した暁にはどんな計算が可能か、ニーモニックの練習を兼ねて今から見ていく。

4かける5を計算し、aレジスタに入れる

今回のCPUには乗算命令がない。足す引くだけだ。 しかし少し工夫すれば整数の積が計算できる。 これは4*5=20のサンプルコードで、右側にC言語風の代替コードも書いておいた

mov a, 0           ; a = 0
mov b, 1           ; b = 1

                   ; do {
add a, 4           ; a = a + 4
add b, 1           ; b = b + 1
cmp b, 5           ;
jnz -8             ; } while (b != 5)

hlt

要するに、aに4を5回足している。

jnzの後ろの-8が意味不明だと思うが、これは次回命令のhltから8個戻ったところの命令にジャンプするという意味だ。 即値も含めて-8からadd a, 4まで数えると、ちょうど8byteになることに注意。

しかし-8ではどこに飛ぶのかわかりにくいので、以下のようなラベルを使うことにする。

mov a, 0         ; a = 0
mov b, 1         ; b = 1

LOOPBEGIN :      ; do {
add a, 4         ;   a = a + 4
add b, 1         ;   b = b + 1
cmp b, 5         ;
jnz LOOPBEGIN    ; } while (b != 5)

hlt

つまり跳びたい場所にラベルを張り、jmp系命令の引数にしている。

1から10までの和を順番にスタックに入れる

スタックメモリに1,3,6,10,15,21,28,36,45,55という10個の値を積んでみる

mov a, 0          ; a = 0
mov b, 0          ; b = 0

LOOPBEGIN :       ; do {
add a, b          ;   a = a + b
push a            ;   mem.append(a)
add b, 0          ;   b = b + 1

cmp b 0xA         ;
jnz  LOOPBEGIN    ; } while (b != 10)

hlt

cmp命令のあとの0xAは、16進数でAになる数を示す表記法で、十進数の10にあたる。

CPUで実行すると

命令 a b sp stack zf
mov a, 0 0 -- FF -- --
mov b, 0 0 0 FF -- --
add a, b 1 0 FF -- --
push a 1 0 FE 1 --
add b, 1 1 1 FE 1 --
cmp b, 0xA 1 1 FE 1 0
jnz LOPBEGIN 1 1 FE 1 0
add a, b 2 1 FF 1 0
push a 2 1 FD 2,1 0
add b, 1 2 2 FD 2,1 0
cmp b, 0xA 2 2 FD 2,1 0
jnz LOPBEGIN 2 2 FD 2,1 0
add a, b 3 2 FD 2,1 0
push a 3 2 FC 3,2,1 0
add b, 1 3 3 FC 3,2,1 0
cmp b, 0xA 3 3 FC 3,2,1 0
jnz LOPBEGIN 3 3 FC 3,2,1 0
... ... ... ... ... ...
add a, b 55 9 F6 45,...2,1 0
push a 55 9 F5 45,...3,2,1 0
add b, 1 55 10 F5 45,...3,2,1 0
cmp b, 0xA 55 10 F5 55,45,...3,2,1 1
jnz LOPBEGIN 55 10 F5 55,45,...3,2,1 1
hlt 55 10 F5 55,45,...3,2,1 1

スタックメモリに値を積むと、spレジスタが1ずつ減るのを確認して欲しい。

10番目のフィボナッチ数を計算し、aレジスタに入れる

これは少しややこしい。aからdまでの全レジスタを使う

mov a, 1       ; a = 1
mov b, 1       ; b = 1
mov c, 0       ; c = 0

mov d, 1       ; d = 1
LOOPBEGIN:     ; do {
mov c, b       ; c = b
mov b, a       ; b = a
add a, c       ; a = a + c

add d, 1       ; d = d + 1
cmp d 0x9      ;
jnz  LOOPBEGIN ; } while (d != 9)

hlt

要するに前回と前々回のフィボナッチ数を記憶しておき、それらを足して新しいフィボナッチ数を作っている。

これはFPGA上のCPUで動かす予定なので、機械語も載せておこう

0100_00_00 00000001
0100_01_00 00000001
0100_10_00 00000000
0100_11_00 00000001
0000_10_01
0000_01_00
0001_00_10
0101_11_00 00000001
0111_11_00 00001001
1110_00_00 11110111
1111_00_00

見やすさのためにアンダースコアを入れたが、無視してほしい。 空白文字は改行だと思って欲しい。

シミュレータで実行すると

f:id:kaitou_ryaku:20171209182107p:plain

上から5番目のaの波形を見ると、最後に0x37(十進数で55)が入っている。 10番目のフィボナッチ数は55なので、正しく動きそうだ。

どうでもいい話

ここまで3種類の計算を見てきたが、アセンブラによる処理の雰囲気が伝われば良いな。

スタックを使いまくれば計算の自由度が大幅に増え、関数呼び出しや複雑な数式計算も可能になるのだが、コードが複雑になるので書かなかった。 そういうのは自作コンパイラのパートでやろう。

いずれx86の命令セットを紹介する予定だが、今回の命令セットと是非見比べてほしい。 想像以上に似ているはずだ。本質的な違いはレジスタのbit数ぐらいしかない。

そういえば、今日の記事には絵がなかった。 今までは回路図を書きまくってきたけど、こっから先はコードと表が増えると思う。華がなくなるけど、まぁしかたない。