2017-12-12

12日目: [x86] 数値とバイナリエディタ

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

昨日はx86のアーキテクチャの概要を説明した。C言語をニーモニックに変換する手順も書いた。

今日は数値とバイナリエディタに関する注意点をまとめる。

バイナリエディタと聞くと「機械語をそのまま0と1で表示するやつ」とか「16進数で表示するやつ」などと思うかもしれない。そこに大きな罠がある。これは機械語をそのまま表示するのではなく、ひっくり返して表示するツールなのだ。

機械語ファイルをバイナリエディタで開く

誤解を避けるため、16進数表記の際、頭に0xをつけることにする。つまり0xFFは十進数の255と同じ数を表す。

さてバイナリエディタの使い方を説明したい。例として

// C言語
void hoge() {
  int a=0x12345678;
}

というC言語のコードを考える。これをgccで(所定のオプションをつけて)コンパイルすると、アセンブラのファイルが生成される。その中には以下のようなニーモニックが含まれる(多分)。

mov eax, 0x12345678

この1行だけからなるhoge.asmというファイルを作り、昨日の記事のjmp imm8のあたりの手順に沿ってアセンブルすると、機械語のhoge.binというファイルが得られる。これをバイナリエディタのxxdで見てみると

$ xxd -g 1 hoge.bin
00000000: b8 78 56 34 12   .xV4.

左端の00000000:は、hoge.binの行番号(アドレス番号)
中央のb8 ... 78の部分が、hoge.binの中身そのもの。
右端の.xV4..D3".は、hoge.binをむりやりアスキーコードで表示したもので深い意味はない。

なにやら数字の順番が変だが、そのへんは後で徹底的にやる。「16進表示はわからん」という人は、xxdコマンドの引数に-bオプションを追加すれば2進表示になる。

$ xxd -g 1 -b hoge.bin
00000000: 10111000 01111000 01010110 00110100 00010010           .xV4.

最初の10111000を考えると、左4桁の1011は16進数のbで、右四桁の1000は16進数の8なので、あわせると上のb8に一致している。

なぜ78 56 34 12になるのか

簡潔に答えると、x86はリトルエンディアンなので、バイナリエディタが1byte毎にbit順序を反転して表示しているからだ。

意味不明だと思うので図で説明する。

f:id:kaitou_ryaku:20171212022844p:plain:w600

画像中段の「バイナリファイル」の行には、hoge.binに含まれる0と1の列を、最初のbitから最後のbitまで順番通りに書いた。右端から見ていくと、0x12345678の2進表記が逆順で書かれていることが分かるだろう。ぜろぜろぜろいち(あ、1だ)、ぜろぜろいちぜろ(あ、2だ)と思って欲しい。

ここでバイナリファイルを最初のbitから最後のbitまで、4bit区切りで16進数に変換してみよう。左端の0001は0x1に、次の1110は0xEに、その次の0110は0x6に、その次の1010は0xAに、、といった具合になり、元の0x12345678という数字からかけ離れた見た目になってしまう。

そこでバイナリエディタは、1byte毎にbit順序を反転し、その後16進数に変換して表示している。赤と灰色の矢印がクロスしている箇所は、このbit順序の反転操作を表している。これなら元の0x12345678とよく似た0x78 0x56 0x34 0x12が表示される。

ちなみにさっきのmov eax, 0x12345678をバイナリエディタで表示すると0xb8 0x78 0x56 0x34 0x12となったが、b8の部分もビット順序が反転して表示されている。バイナリエディタはどこが数値でどこがmovに対応するのか一切気にせず、ひたすら8bitずつ反転して表示するツールなのだ。

最後に重要なコメントだが、以降の数値に関する説明は、0と1の列も含め、全てバイナリエディタ形式で表示したので注意して欲しい。

負の整数

バイナリエディタの説明を終えたので、ここからは数値に関する注意を書きまくる。まずはマイナスの数だ。

数学的には、マイナス1は「1と加算すると0になる数」として定義されている。そして4bit同士の加算を考えると、

0001 + 1111 = 0000 (桁溢れは無視)

0001は4bitで1を表す(のが自然)なので、1111にはマイナス1っぽい雰囲気が漂っている。この理屈を推し進めると

f:id:kaitou_ryaku:20171212022857p:plain

上段は符号無整数と呼ばれ、下段は符号付整数と呼ばれている。下段同士足したり引いたりする際に、常に4桁で計算し、5桁に溢れた数を無視する約束の下で、1111はマイナス1と等価になる。

ところで0から7については、符号付整数と符号無整数は同じになるが、その先で困ったことになる。 4bitの下で、CPUは9とマイナス7をどのように区別しているのだろうか。

結論を言うと、4bitCPUは9とマイナス7を区別できない。どちらも純粋に1001というビット列にすぎない。

f:id:kaitou_ryaku:20171212022905p:plain

これはC言語で書かれたソースコードをバイナリファイルに変換し、バイナリエディタで見た結果を表している。 5種類の代入文があるけど、CPUはこれらの命令を同一視する。生成されるバイナリファイルも、当然全て同じになる。

繰り返しになるが、重要な点はC言語のsingned整数型もunsigned整数型も、機械語レベルでは全く同じということだ。 CPUができるのは、32個並んだ01の列を二つもってきて、加算器や減算器に入れて、結果に応じてフラグを立てるだけ。 CPUが勝手にsigned型か判定して演算の種類を変える、なんてことはない。あくまでC言語側が、機械語命令の結果を符号付き/符号なし整数のつもりで解釈しているだけなのだ。

byte拡張

昨日の記事のジャンプ命令の辺りを読むと

jmp 0x12       ; 機械語は 0xeb 0x12
jmp 0x12345678 ; 機械語は 0xef 0x78 0x56 0x34 0x12

このように、jmp命令の即値は1byteと4byteの2種類があるのだった。

一方x86 (IA-32)のレジスタは全て32bit(4byte)なので、1byteの即値をレジスタに入れる際に4byteに変換する必要がある。

これを説明するために、例として1byteの0x02と-0x02=0xEFの2つの数を考える。これらを4byteに変換するには

f:id:kaitou_ryaku:20171212022912p:plain:w400

要するに

1 byte	4 byte
`0x02`	`0x02000000`
`-0x02`=`0xFE`	`-0x02000000`=`0xFEFFFFFF`

キャリーフラグ

「負の整数」のセクションで

「CPUができるのは、32個並んだ01の列を二つもってきて、加算器や減算器に入れて、結果に応じてフラグを立てるだけ」

と書いた。フラグは数種類あり、その中にキャリーフラグがある。これは CPU編で全加算器を作った時に一応説明した。

x86の場合は、32個並んだ0と1の列を二つもってきて、全加算器に入れて、33桁目に溢れたらキャリーフラグを立てれば良い。

分かりやすいように4bitのCPUの場合で説明すると

f:id:kaitou_ryaku:20171212022922p:plain:w400

要するに4bitのレジスタを符号なし整数だと考えて、計算の結果が0~15の範囲外にはみ出すと、キャリーフラグが立つ。

オーバーフローフラグ

これは初登場だ。

要するに4bitのレジスタを符号付き整数だと考えた場合に、計算の結果が-8~7の範囲外にはみ出すと、オーバーフローフラグが立つ。

f:id:kaitou_ryaku:20171212022933p:plain:w400

オーバーフローフラグが立つのは、計算結果の符号が予想とずれた場合だ

正の大きな数同士を足すと、マイナスになった！
負の大きな数から、さらに引くと、プラスになった！

逆に計算結果の符号が二つのオペランドの符号から予想できない場合、オーバーフローフラグは立たない。

正数から正数を引く
負数から負数を引く
正数と負数を足す

これらの計算結果が範囲内に収まるのは、ほぼ自明だろう。

比較条件

他にもいくつかフラグがある。表にまとめると

記号	正式名称	フラグが立つ条件
CF	キャリーフラグ	符号なし整数が範囲外にはみ出る
OF	オーバーフローフラグ	符号付き整数が範囲外にはみ出る
ZF	ゼロフラグ	計算結果が0になる
SF	サインフラグ	計算結果を符号付き整数と思うと負値になる
PF	パリティフラグ	計算結果の下位1byteに1が偶数個ある

最後にcmp a, b命令(a-bを計算したつもりでフラグを更新)と、その後の条件付きジャンプ命令の関係表を貼っておく。

機械語	オペコード	飛ぶ場合のフラグの条件	前回の`cmp a, b`の結果
70	`jo`	`OF == 1`	符号付き整数計算に失敗したとき
71	`jno`	`OF == 0`	符号付き整数計算に成功したとき
72	`jc`	`CF == 1`	`a < b` (符号なし整数)
73	`jnc`	`CF == 0`	`a >= b` (符号なし整数)\|
74	`jz`	`ZF == 1`	`a == b`
75	`jnz`	`ZF == 0`	`a != b`
76	`jbe`	`CF == 1 or ZF == 1`	`a <= b` (符号なし整数)
77	`ja`	`CF == 0 and ZF == 0`	`a > b` (符号なし整数)
78	`js`	`SF == 1`
79	`jns`	`SF == 0`
7a	`jp`	`PF == 1`	a-bの下1byteに1が偶数個あるとき
7b	`jnp`	`PF == 0`	a-bの下1byteに1が奇数個あるとき
7c	`jl`	`SF != OF`	`a < b` (符号付き整数)
7d	`jge`	`SF == OF`	`a >= b` (符号付き整数)
7e	`jle`	`SF != OF or ZF == 1`	`a <= b` (符号付き整数)
7f	`jg`	`SF == OF and ZF == 0`	`a > b` (符号付き整数)

特に重要なのは、下4段の符号付き整数の大小関係。

符号付き整数の大小関係

a < b

機械語の7cのところ。

ここではa < bとSF != OFが対応している。この説明をしておく。

a < bはa - b < 0と等価だ。ここで

a > 0, b > 0 ならば、引算結果の符号は予想できないのでOF=0。結果は範囲内なのでSF=1
a < 0, b > 0, OF=0ならば、結果は範囲内なのでSF=1
a < 0, b > 0, OF=1ならば、結果は範囲外なのでSF=0
a < 0, b < 0 ならば、引算結果の符号は予想できないのでOF=0。結果は範囲内なのでSF=1

これら全パターンでSF != OFが満たされている。

a >= b

機械語の7dのところ。

機械語の7c同様の考察を機械語のa >= bに対して行うと、SF == OFが得られる。

この結果から、a < bはSF != OFに対応し、a >= bはSF == OFに対応していることが分かる。

a \<= b

機械語の7eのところ。

既に求めたa < bに対する条件に、a == bに対応するフラグ条件ZF == 1をorで結合すればよい。

a > b

機械語の7fのところ。

既に求めたa >= bに対する条件に、a != bに対応するフラグ条件ZF != 1をandで結合すればよい。

全パターン求まった。証明完了！

2017-12-11

11日目: [x86] アーキテクチャとバイナリ解析最速マスター

アドベントカレンダー2017 低レイヤ x86

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

昨日まではCPUの回路実装の話だった。つまりトランジスタをいかに配置するか、という話だった。そういう回路視点でCPUを考えることをマイクロアーキテクチャという。

今日からは命令セットアーキテクチャの視点でCPUを考えていく。命令セットは全ニーモニックを集めた一覧表と思えば良い。つまりレジスタは何個で、ニーモニックはどんな感じで、どういう機械語に変換されるのかという視点で、これからCPUを考えていく。

CPUの種類が変われば命令セットも変わる。全てのCPUを解説することはできないので、今後はx86と呼ばれるCPUに特化する。

x86はintelが30年以上前に策定した命令セットで、今日までPCとサーバーのCPU市場を席巻してきた。日常で使用するCPUは今後もx86であり続けるだろう¹。手元のPCの仕組みを理解する上で、x86の命令セットは外せないと思う。

x86を知るメリットは山のようにある。

普段使うPCの実行可能ファイルが解析できるようになる (この記事の最後でやる)
普段使うPCで様々な言語をデバッグする際の最終兵器になる
普段使うPCでC言語のソース内にアセンブラを埋め込み、超カリカリに最適化できる
普段使うPCで動くOSを自作するにはx86の細かい知識がいる
普段使うPC用のコンパイラを作るのに必要
普段使うPC用のデバイスドライバも書けるらしい

適当に書き並べてみたが、まだまだあると思う。

つまるところ、日常用途の実行可能ファイルを解析する手段があると安心感が違う。他の命令セットをベースにすると、この安心感が得られない。「MIPSはキレイで学びやすい。初心者におすすめ」などと言ってx86を知らずに生きるのは、もったいなさすぎる。

そういう偏った信念に基づき、あと4日間かけてx86の機能(のごく一部)を説明し、最後にエミュレータを作ろうと思う。

レジスタの種類

x86 (IA-32)のレジスタ構成を見てみる。

名称	サイズ	タイプ	昨日のCPUの対応物	`mov`で値変更
eax	32bit	計算用	a	O
ecx	32bit	計算用	c	O
edx	32bit	計算用	d	O
ebx	32bit	計算用	b	O
esp	32bit	スタックポインタ	sp	O
ebp	32bit	関数呼出で使う	なし	O
esi	32bit	計算用	aかも	O
edi	32bit	計算用	cかも	O
eip	32bit	プログラムカウンタ	ip	X
eflags	32bit	フラグの集まり	zf	X

ebp以外は、昨日作ったしょぼいCPUに対応物がある。 ebpは「関数呼出で使う」などと難しそうに書かれているが、結局のところeaxと同じようなレジスタだ。恐れる必要はない。

eipとeflagsはmovで値が変更できないと書かれている。昨日作ったCPUでも、プログラムカウンタやゼロフラグは自動で値が変化するので、mov命令で恣意的に値を変える必要は無かった。

他にもレジスタはある²のだが、話をややこしくするだけなので無視する。参考用に昨日作ったCPUの仕様書へのリンクを貼っておく。是非見比べて欲しい。

命令セット表

これがx86(IA-32)の命令セットだ!

f:id:kaitou_ryaku:20171211195350p:plain

土日の間に頑張って作った。

jmp imm8

この表の使い方を説明するため、例として右下(e行b列)のjmp imm8を考える。これはジャンプ命令で、昨日作ったCPUに存在したニーモニックなので意味はわかると思う。

表の使い方だが、まずhoge.asmというファイルに

; hoge.asm

jmp 0x12 ; 0x12は8bitの即値、つまりimm8

と書いて、nasmコマンドで機械語に変換する

$ nasm hoge.asm -o hoge.o   # アセンブルするコマンド

これで機械語に変換された。 1byte(8bit)ずつ区切って16進表示すると

$ xxd -g 1 hoge.o   # バイナリを表示するコマンド
00000000: eb 12

つまりjmp 0x12をアセンブラで機械語に変換すると、eb 12になる。

jmp imm32

jmp imm8の左にはimm8をimm32に変えたやつがいる。この場合

jmp 0x12345678 ; 0x12345678は32bitの即値、つまりimm32
               ; 対応する機械語は e9 78 56 34 12

なんか12345678の順番が変なことになっているが、この理屈はややこしいので明日に回そう。

実は表の空欄の部分にも命令があるのだが、今回は無視した³。表に記載した命令は、後日解説予定のx86 エミュレータに実装されている。

命令セット毎に分割

各命令の詳細は明日以降に回すとして、さっきの表の全体を眺めると、おおむね4行毎に分割されている。また左右が対称的になっている。左側だけ上から順に見ていくと

0-3行:計算系

f:id:kaitou_ryaku:20171211195414p:plain:w400

最初の4行は計算演算で構成されている。

addは言うまでもなく加算
adcも加算なのだが、キャリーフラグが立ってる場合は結果にプラス1する
andはbid毎に論理積をとる演算
xorはbid毎に排他的論理和をとる演算

枠内に小文字で[M+imm]やRなどと書かれているが、これはModRMというややこしいやつなので、明後日解説する。

4-7行:`inc`, `push`, `jcc`

f:id:kaitou_ryaku:20171211195425p:plain:w400

一番目のincはレジスタの値を1増やす命令だ。

枠内には小文字でeaxやらediなどと書かれているが、これは

inc eax ; 対応する機械語は 40
inc edi ; 対応する機械語は 47

を意味している。

pushは昨日のCPUにも出てきたが、スタックに値を詰む命令だった。

最下段にはjoやらjnoやらたくさん書かれているが、これは昨日のCPUのjzとjnz命令に対応する。つまりフラグレジスタのeflagsの値を見て、ジャンプするかどうか決める命令だ。昨日のCPUはゼロフラグ(zf)しか無かったが、x86のeflagsは32bitなのでジャンプの条件が大量にある。これらの条件ジャンプ命令をまとめてjccと呼ぶのだが、詳細は明日に回そう。

8-b行:`mov`がメイン

f:id:kaitou_ryaku:20171211195449p:plain:w400

一番上のcalcだが、これはさっき出てきたaddやadcなどの演算をまとめたものだ。 ModRMが絡んできてややっこしいので説明は控える。

次のnopは、メモリやレジスタを一切変化させず、プログラムカウンタだけを進める命令。クロックが過ぎ去るのを何もせずに待つだけ。

右隣のxchgは、eaxレジスタと他のレジスタの値を交換する命令。つまりx86において、nop命令はxchg eax, eaxと考えられているのだ。

最後はmov命令だが、mov eax, [imm32]の場合は

mov eax, [0x12345678] ; メモリの0x12345678番地の値を、eaxにコピーしたい
                      ; 対応する機械語は
                      ; a1 78 56 34 12

ここで、0x12345678は32bitの即値なのでimm32と表記されている。またアセンブラには四角カッコでくくると、メモリを表すというルールがある。つまりこの命令は、eaxレジスタにメモリから値を読み込むという命令だ。

右隣のmov eax, [imm32]の場合はさっきと真逆で、eaxレジスタの値をメモリにコピーする命令になっている。

8-b行:関数呼び出し

f:id:kaitou_ryaku:20171211195502p:plain:w400

最初はret命令だが、これは重要な命令である。関数呼び出しに使用するのだが、昨日までのCPUには無かった命令なので説明しずらい。詳細は、他の関数呼び出し命令(leaveとcall)とあわせて後日書くことにする。

その右にmov命令がいるけど、またしても[M+imm], imm32のMがModRMなので、詳細は明後日に回す。

最後の命令は、CPUを停止するhltだ。これは昨日のCPUで実装したので説明不要だろう。

C言語の機械語を解析

駆け足だったが、x86の命令セットの概要(オペコードの種類)はおおむね掴めたと思う。残りの時間で、今知った命令セットの知識を応用してみる。

普段使うPC上で、a.outやa.exeなどの実行ファイルは馴染み深いと思うが、それらの機械語がどんな感じ科調べてみる。

やる内容を先にまとめると

f:id:kaitou_ryaku:20171211195645p:plain:w400

赤矢印を辿るのだが、詳細は

org.cを好きなように作る
$ gcc -m32 -O0 -c org.c -o fat.o でコンパイル
fat.oが得られる。このバイナリにはOSに関する余計な情報が入っている。
$ objdump -d -M i386,intel fat.o > org.txtで逆アセンブル。余計な情報は削がれるものの、出力形式がイマイチ
org.txtの出力形式を手で変更し、org.asmとして保存
$ nasm org.asm -o org.oでorg.asmをアセンブル
org.oのバイナリが得られる。これがorg.cに対応する機械語である

重要なのはorg.asmとorg.oの2つだ。これらは元のorg.cをアセンブリ言語に翻訳したものと、それを機械語に翻訳したファイルだ。

1 : C言語ソースファイル`org.c`の用意

こんな感じでいこう

org.cの中身

/* org.c */
int foo(int a, int b) {
  return a+b;
}

void bar(void) {
  int c;
  c = foo(2,3);
}

2,3 : コンパイル

$ gcc -m32 -O0 -c org.c -o fat.o

こうしてできたバイナリfat.oには、実はfat.c以外の情報が多数含まれている。その根本的な原因はOSにある。バイナリに書かれた機械語は直接CPUで実行されるのではなく、OSを介してCPUに渡される。今回作ったfat.oには、gcc氏の粋な計らいにより、OSに色々と指示を与えるための余分な情報が付与されてしまっている。我々の欲しいのはfat.cに対応する機械語だけなので、この余分な情報を削ぎ落とす必要がある。

ちなみにここまでC言語を使ったが、他の言語でも機械語形式のfat.oに対応するファイルが得られれば、以降の解析は全く同様に行うことができる。

4 : 機械語とニーモニックの対応表`org.txt`の取得

そこで以下のコマンドを叩く。これはOSへの指示部分を無視し、org.cの処理に対応する部分だけを逆アセンブルするコマンドだ。

$ objdump -d -M i386,intel fat.o > org.txt

これでorg.cに対応するニーモニックのファイルorg.txtが得られた。その中身は

00000000 <_foo>:
   0:   55                      push   ebp
   1:   89 e5                   mov    ebp,esp
   3:   8b 55 08                mov    edx,DWORD PTR [ebp+0x8]
   6:   8b 45 0c                mov    eax,DWORD PTR [ebp+0xc]
   9:   01 d0                   add    eax,edx
   b:   5d                      pop    ebp
   c:   c3                      ret

0000000d <_bar>:
   d:   55                      push   ebp
以下略

今度は左側にアドレスと機械語、右側にニーモニックという形式で吐き出されてしまった。人間にとっては見やすいが、このままではアセンブルすることができない。

5 : アセンブラ言語のソースコード`org.asm`の作成

nasmの文法に対応させるためには

左側の行番号と機械語列
PTR
<...>

これらを削除する必要がある。 nasm文法ではPTR が使えず、またニーモニック中の 0 <_foo> は、アドレス0がラベル_fooだと説明しているだけなので消しても問題ない。これをorg.asmとして保存する。

org.asmの中身

;org.asm
push   ebp
mov    ebp,esp
mov    edx,DWORD [ebp+0x8]
mov    eax,DWORD [ebp+0xc]
add    eax,edx
pop    ebp
ret

push   ebp
; 以下略

6,7 : アセンブルとシンプルなバイナリファイル

org.asmをnasmでアセンブルする

$ nasm org.asm -o org.o

こうして得られたorg.oは、org.cをシンプルに機械語に変換したバイナリファイルである。つまりOSへの指示等の余分な情報は含まれていない。

全て揃った

以上の手続きでorg.cに対応するニーモニックのorg.asmと機械語のorg.oが得られた。

org.oを逆アセンブルすると、org.asmと同じ結果が得られるはずだ。試してみよう。

$ objdump -d -b binary -m i386 -M i386l,intel -D org.o

手順4で叩いたobjdumpコマンドとオプションが変わっている。今回はバイナリファイル全体を逆アセンブルするコマンドになっている。前回はバイナリファイルの中でOSへの指示部分は無視して、org.cの処理に対応する部分だけを逆アセンブルするオプションだった。

表示結果を見ると、たしかにorg.asmと対応している。

00000000 <.data>:
 0: 55                   push  ebp
 1: 89 e5                mov   ebp,esp
 3: 8b 55 08             mov   edx,DWORD PTR [ebp+0x8]
 6: 8b 45 0c             mov   eax,DWORD PTR [ebp+0xc]
 9: 01 d0                add   eax,edx
 b: 5d                   pop   ebp
 c: c3                   ret
 d: 55                   push  ebp
 e: 89 e5                mov   ebp,esp
10: 83 ec 18             sub   esp,0x18
13: c7 44 24 04 03 00 00 mov   DWORD PTR [esp+0x4],0x3
1a: 00
1b: c7 04 24 02 00 00 00 mov   DWORD PTR [esp],0x2
22: e8 d9 ff ff ff       call  0x0
27: 89 45 fc             mov   DWORD PTR [ebp-0x4],eax
2a: 90                   nop
2b: c9                   leave
2c: c3                   ret
2d: 90                   nop
2e: 90                   nop
2f: 90                   nop

DWORDとPTRについては無視して構わない。

ニーモニック観察

表示結果を眺めてみる。

1行目を見ると、機械語は55で、ニーモニックはpush ebpとなっている。命令セット表の55の場所を見ると、push ebpと書かれている。ちゃんと対応している。

2行目を見ると、機械語は89で、ニーモニックはmov ebp,espとなっている。命令セットの表の89の場所を見ると、mov [M+imm], Rと書かれている。この[M+imm], RはModRMで、未解説なので意味不明だと思うが、ebp,espに対応しそうな雰囲気だ。

オペコードの部分を縦に眺めてみると、push, mov, add, pop, ret, sub, call, nop, leave, retの10種類が存在している。どれも命令セット表に記載されている。あの表は空欄だらけだが、頻出の機械語命令はほぼ網羅されているのだ。

初日から今日まで丁寧に記事を読んでくださった方は、今感動してるんじゃないかな。ニーモニックを回路で実装する方法は昨日の記事を読めばイメージできると思う。 pushやmovが回路素子に見えれば、かなりいい感じだ。こうした回路素子で、あの抽象的なC言語の処理が実現するなんて！！という具合に感動して欲しい。

どうでもいい話

一口にx86と言っても、歴史が長く種類も多い。最初のバージョンは1985年製の80386というCPUに搭載されていた命令セットで、i386と呼ばれている。レジスタやアドレスバスは32bitだった。その後i486、i586、i686などの拡張版が作られた。これらをまとめてIA-32と呼ぶ。

その後レジスタやアドレスバスを64bitに拡張した命令セット(x64と呼ばれる)が作られた。重要なのは後方互換性で、IA-32の機械語は最新のx64でも動作する。なのでIA-32がわかれば、過去数十年間の全CPUに直接命令を下せるようになる。ような気がする。

スマホのCPUはx86じゃないけど↩
ディスクの読み込みに使うセグメントレジスタやら、起動時のモード切替に使うコントロールレジスタやら↩
割り込みのint命令を無視してるのは切腹モノだと思うが、許せ。↩

2017-12-10

10日目: [CPU] FPGAでCPUを自作 (完成)

アドベントカレンダー2017 低レイヤマイクロアーキテクチャ FPGA

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

昨日に引き続きFPGAでCPUを作成していく。

復習

昨日のメインは test.sv の解説だった。ここにはシミュレーション用のモジュールが書かれていた。

こいつを論理合成用に書き換えたのが top.sv だった。

これらはCPUの本体を構成するモジュールで

回路素子の宣言
外部から初期メモリの内容を読み込み
外部演算モジュールへの接続
レジスタとメモリの初期化
レジスタとメモリの更新
クロック生成
assertテスト

という機能をもっていた。

ここで昨日の記事のワイヤの更新のセクションを思い出してほしいのだが、 CPU本体のモジュールには演算回路が含まれず、外部の演算モジュールに繋いでいた。

この外部演算モジュールの入出力は

入出力	線の種類	4日目のコード(改変版)の対応素子
入力	メモリの出口のワイヤ	`a`の出口
入力	レジスタの出口のワイヤ	`a`の出口
出力	次回のクロック立ち上りでメモリを上書きするワイヤ	`b`の入口
出力	次回のクロック立ち上りでレジスタを上書きするワイヤ	`b`の入口

つまりワイヤをワイヤに変換する組み合わせ回路が、演算モジュールだった。

4日目のコードとの対応

基本(超重要)の4日目の記事に出てきたコードを改変すると

module cpu( input CLOCK); // 昨日作った
  logic a;      // レジスタaを用意
  logic next_a; // ワイヤnext_aを用意

  // 外部演算モジュールに繋いで、aからnext_aの電圧を作る
  make_next_a make_next_a_0(a, next_a);

  // レジスタaをワイヤnext_aで上書き
  always_ff @(posedge CLOCK)
    a <= next_a;
endmodule

module make_next_a( input a, output next_a); // 今日作る
  // always_comb中でnext_aに線を繋ぐのは無理(仕様)なので
  // ワイヤのb_endを作り、その出口をbの入口に繋ぐ
  logic end_a;
  assign next_a = end_a;

  always_comb   // aを使ってend_aを作る組み合わせ回路
    end_a = ~a; // aの出口を反転してend_aに繋いだ
endmodule

このコードを4日目のコード(改変版)と呼ぶことにする。

cpuモジュールは昨日作った test.sv に対応し、 make_next_aモジュールは今日作る make_next_reg に対応する。

make_next_aの内側では

まずend_aというワイヤを宣言
次にend_aの出口をnext_aの入口に繋ぐ
最後にレジスタaの出口電圧を反転し、end_aの入口に繋ぐ

ここまでの話が理解できれば、後の話は難しくない。

4日目のコードとの今日の回路の違いは

レジスタの種類が増えて、複数ビット化した
メモリ(レジスタとほぼ同じ)が追加された
演算の種類が大幅に増えた

極論すると、レジスタの数が増えただけだ。恐れる必要は全く無い。

準備が整ったので、本日のメインテーマの演算モジュール本体の解説に移ろう。

引数

まずこの部分に着目する。

これはモジュールの冒頭の引数部分だが

module make_next_reg(

  input    reg  [7:0] memory [`MEMSIZE-1:0]
  , output wire                write_flag
  , output wire [`MEMSIZE-1:0] write_addr
  , output wire [7:0]          write_value
  , input  reg  [7:0] a
  // (inputがたくさん。省略)
  , input  reg  [7:0] ip
  , input  reg        zf
  , output wire [7:0] next_a
  // (outputがたくさん。省略)
  , output wire       next_zf
);

要するにmemoryやa等のレジスタの出口電圧をもとに、いい感じの電圧を作り、write_flagやnext_a等のワイヤの入口に繋ぐ組み合わせ回路だ。 4日目のコード(改変版)に対応させると、next_a = ~aのような組み合わせ回路を作れば良い。

ちなみにwrite_***のワイヤはメモリの更新用だった。忘れた人は昨日の記事の「クロックの立ち上り」の辺りを読み直して欲しい。

ワイヤの宣言と接続

この部分に着目する。

4日目のコード(改変版)に

まずend_aというワイヤを宣言
次にend_aの出口をnext_aの入口に繋ぐ

という部分があった。この宣言と接続に対応するのが

// 出力をendのワイヤーに変換
logic [7:0] end_a;
// (宣言文たくさん。省略)
logic       end_zf;

assign next_a  = end_a;
// (assign文たくさん。省略)
assign next_zf = end_zf ;

logic                 end_write_flag ;
logic [`MEMSIZE-1:0]  end_write_addr ;
logic [7:0]           end_write_value;

assign write_flag   = end_write_flag ;
assign write_addr   = end_write_addr ;
assign write_value  = end_write_value;

まずレジスタ用のワイヤend_aを宣言して、モジュールの出力ワイヤnext_a接続している。

次にメモリ用のワイヤend_write_***を宣言して、モジュールの出力ワイヤwrite_***に接続している。

メモリからオペコード類をフェッチ

この部分に着目する。

4日目のコード(改変版)では、ワイヤの宣言と接続を行った直後に、always_combでend_aを作成していた。

今回はメモリが存在している。そこに書かれた機械語命令や即値、スタックの値を使って、end_aを作ることになる。従ってalways_combの前にこれらの電圧値を準備する必要がある。

logic [7:0] ope     // 機械語命令のワイヤを準備
assign ope [7:0] = memory[ip];

logic [7:0] imm;    // 即値のワイヤを準備
assign imm [7:0] = memory[ip+1];

logic  [7:0] stack; // スタックのワイヤを準備
assign stack     = memory[sp];

実はこの辺の処理、かなりヤバい問題を抱えている。記事の最後で言及しよう。

オペランドのワイヤーの宣言

この部分に着目する。

機械語命令の中には

add x, y

のようにレジスタでレジスタを上書きする処理があるけど、このyレジスタに対応するワイヤをあらかじめ準備しておく。

// オペランドのワイヤ
logic [7:0] y;

さっき機械語命令や即値を準備した時と違ってassign文がない。

ここでは、機械語命令に応じて

機械語の下2桁	ワイヤ`y`の接続先
00	`a`の出口
01	`b`の出口
10	`c`の出口
11	`d`の出口

このように接続(assign)したいのだが、System Verilogの言語仕様上、alwaysの外側ではcase文やif文を使うことができないのだ¹。あとでalwaysが出たとき、レジスタの出口をyにつなごう。

`end_a`ワイヤーの電圧を作成

この部分に着目する。

いよいよ最後の処理だ。4日目のコード(改変版)でいうと

always_comb   // aを使ってend_aを作る
  end_a = ~a; // aの出口を反転してend_aに繋いだ

の部分にあたる。

今回はレジスタの数と演算の数が大幅に増えたので、always_combの中身が350行ぐらいに膨らんでしまった。処理ごとに分割して説明しよう。

オペランドのワイヤの作成

この部分に着目する。

オペランドを表すyのワイヤは、まだレジスタに繋がってなかった。現在はalwaysの中なのでcase文が使える。さっそく繋ごう。

// yをあらかじめ定義
case (ope[1:0])
  2'b00: y = a;
  2'b01: y = b;
  2'b10: y = c;
  2'b11: y = d;
endcase

計算命令とメモリ関連命令の分離

このcase文に着目する。

機械語命令を実際に処理する部分に入った。

2日前に決めた命令セット表を再掲すると

計算命令	機械語(2進数)	メモリ関連命令	機械語(2進数)
mov x, y	0000 xx yy	push x	1000 xx 00
add x, y	0001 xx yy	pop x	1001 xx 00
sub x, y	0010 xx yy	jmp imm	1010 00 00 imm
cmp x, y	0011 xx yy	jz imm	1100 00 00 imm
mov x, imm	0100 xx 00 imm	jnz imm	1101 00 00 imm
add x, imm	0101 xx 00 imm	hlt	1111 00 00
sub x, imm	0110 xx 00 imm
cmp x, imm	0111 xx 00 imm

機械語の左端が0なら計算命令で、1ならメモリ関連の命令になっている。 HDLの言葉に直すと、ope[7:0]の左端、ope[7]のbitで分岐すればよい。

case (ope[7])
  1'b0: begin
  // 計算関連命令
  end

  1'b1: begin
  // メモリ関連の命令
  end
endcase

計算とメモリ操作に分離できた。この後も同じ感じで分離操作を繰り返していく。

計算命令全体

計算命令の全範囲でメモリやスタックの更新がないので、最初に一括して

end_sp          = sp;
end_write_flag  = 0;
end_write_addr  = 0;
end_write_value = 0;

としている。メモリの書き込みフラグを0にしたので、次回のクロック立ち上がりでメモリの値は変更されない。

残された作業は、計算レジスタend_a等とプログラムカウンタend_ipの電圧値を作成するだけだ。

残りの部分は

case (ope[6])

  1'b0: begin
    end_ip = ip + 1;
    case (ope[5:4])
      2'b00: // mov  x, y の処理
      2'b01: // add  x, y の処理
      2'b10: // sub  x, y の処理
      2'b11: // cmp  x, y の処理

  1'b1: begin
    end_ip = ip + 2;
    case (ope[5:4])
      2'b00: // mov  x, imm の処理
      2'b01: // add  x, imm の処理
      2'b10: // sub  x, imm の処理
      2'b11: // cmp  x, imm の処理

endcase

重要なのはend_ipをつくるところ。次回クロックでフェッチする機械語のアドレスをend_ipに入れたいので、即値(imm)が含まれるかどうかでプログラムカウンタ(ip)の増分を変える必要がある。

以下では各機械語命令の実装を順に見ていく。

mov x, y (0000 xx yy)

この部分に着目する。

まずmov x, yに着目すると

end_zf = zf;
case (ope[3:2])
  2'b00: begin // mov a, y
    end_a = y;
    end_b = b;
    end_c = c;
    end_d = d;
  end

  2'b01: begin // mov b, y
    end_a = a;
    end_b = y;
    end_c = c;
    end_d = d;
  end

  2'b10: begin // mov c, y
    end_a = a;
    end_b = b;
    end_c = y;
    end_d = d;
  end

  2'b11: begin // mov d, y
    end_a = a;
    end_b = b;
    end_c = c;
    end_d = y;
  end

まず初めに、mov命令ではゼロフラグが変わらないのでend_zfを現在値と同じにしている。

次のcase (ope[3:2])の分岐でmov x, yのxを特定している。この辺の処理は5日目のマルチプレクサの辺りを読めば、回路実装がわかると思う。

mov x, yのyについては、あらかじめワイヤを準備していたので、ここで分岐する必要はない。

cmp x, y (0011 xx yy)

add x, yとsub x, yは今説明したmovとほぼ同じ²なので、毛色の違うcmp命令を見てみる。この部分に着目する。

cmp x, yの処理は

end_a = a;
end_b = b;
end_c = c;
end_d = d;
case (ope[3:2])
  2'b00: end_zf = a-y ? 0 : 1; // cmp a, y
  2'b01: end_zf = b-y ? 0 : 1; // cmp b, y
  2'b10: end_zf = c-y ? 0 : 1; // cmp c, y
  2'b11: end_zf = d-y ? 0 : 1; // cmp d, y
endcase

この命令はフラグだけを更新し、他のレジスタは変更しないので、最初にend_aからend_dに前回の値を繋いでいる。

その次のcase (ope[3:2])はcmp x, yのxを特定するための分岐だ。

その次の三項演算子はif文の省略形で

// 例
end_zf = a-y ? 0 : 1; // cmp a, y

// これは以下のif文と等価
if (a-y) end_zf = 0;  // if (a-y) は if(a-y != 0) の意味
else     end_zf = 1;

つまりa == yならフラグが立つわけだ。

ope x, imm (01?? xx 00 imm)

ここまでope x, y型の命令を見てきた。最後にope x, imm型の命令を見てもよいのだが、これは今まで y だったところを imm に変更するだけだ。ほぼ同じなので説明は略す。

メモリ関連の命令

メモリ関連命令の全範囲でゼロフラグの更新がないので、最初に一括して

end_zf = zf;

としている。

続いて

case (ope[6:4])
  3'b000:  // push x   の処理
  3'b001:  // pop  x   の処理
  3'b010:  // jmp  imm の処理
  3'b100:  // jz   imm の処理
  3'b101:  // jnz  imm の処理
  default: // hlt      の処理

これらの命令を順に見ていく。

push x (1000 xx 00)

この部分に着目すると

end_a  = a;
end_b  = b;
end_c  = c;
end_d  = d;
end_ip = ip + 1;
end_sp = sp - 1;
end_write_flag = 1;
end_write_addr = sp-1;

case (ope[3:2])
  2'b00: end_write_value = a; // push a
  2'b01: end_write_value = b; // push b
  2'b10: end_write_value = c; // push c
  2'b11: end_write_value = d; // push d
endcase

まず初めに計算用レジスタ更新用のワイヤを、現在のレジスタの出口に繋いでいる。

次に、この命令は即値を含まないので、end_ip は普通に1つ増やしている。

スタックポインタ(sp)については、スタックが変化するので値を変える必要がある。スタックはメモリの最後尾から最前列に向かって伸びているので、pushする度にspの値が1つ減る。

続いて、スタックメモリに値を書き込むのでend_write_flagを立てている。

書き込むアドレスはend_write_addrで指定しているが、spは最新のスタックが詰まったアドレスを指すので、ここで書き込むべきアドレスはsp-1としなければならない。

続いてcase (ope[3:2])でpush xのxを特定し、メモリに書き込むためend_write_valueに繋いでいる。

pop x (1001 xx 00)

この部分に着目する。

push命令の逆をやればよい。

end_ip = ip + 1;
end_sp = sp + 1;
end_write_flag = 0;
end_write_addr = 0;

case (ope[3:2])
  2'b00: begin
    end_a = stack; // pop a
    end_b = b;
    end_c = c;
    end_d = d;
  end
  2'b01: begin
    end_a = a;
    end_b = stack; // pop b
    end_c = c;
    end_d = d;
  end
  2'b10: begin
    end_a = a;
    end_b = b;
    end_c = stack; // pop c
    end_d = d;
  end
  2'b11: begin
    end_a = a;
    end_b = b;
    end_c = c;
    end_d = stack; // pop d
  end

スタックから1つ値を取り出すので、end_spに1加えている。

なおpop操作はメモリの論理削除であり、メモリをゼロで埋める物理削除はしない。そういう「必要かどうかわからない操作」は、ハードウェアで自動実行すべきではなく、ソフトウェア(つまりメモリに載った機械語)に判断を仰ぐべきである。無意味なメモリアクセスはすべきではない。

最後にcase (ope[3:2])でpop xのxを特定している。分からなければ、mov命令の説明を読み直して欲しい。

jmp imm (1010 00 00 imm)

この部分に着目すると

end_a  = a;
end_b  = b;
end_c  = c;
end_d  = d;
end_sp = sp;
end_ip = (ip + 2) + imm;
end_write_flag  = 0;
end_write_addr  = 0;
end_write_value = 0;

要するにジャンプ操作とはプログラムカウンタの書き換えであり、他のレジスタにはタッチしなかった。従って次回の機械語をフェッチするメモリアドレスを指定する、end_ipだけに着目すればよい。

ややこしいので表にまとめると

値	意味
`ip`	さっき読んだ機械語のアドレス
`ip+2`	ジャンプ命令でなかった場合に、次回読む機械語のアドレス
`imm`	ジャンプ命令でなかった場合に、次回読むはずだったアドレスからの差分
`ip+2+imm`	ジャンプし、次回読む機械語のアドレス

なお条件付きジャンプ命令は、jmp命令のend_ipを以下のように変更すれば作れる。

命令	`end_ip`の右辺値
`jz imm`	`zf ? ip+2+imm : ip+2`
`jnz imm`	`zf ? ip+2 : ip+2+imm`

三項演算子を使ってジャンプの有無を判断している。

hlt (1111 00 00)

この部分に着目する。

この命令が来たらプログラムを停止する。これを簡単に実装するには、

end_a  = a;
end_b  = b;
end_c  = c;
end_d  = d;
end_sp = sp;
end_ip = ip;
end_write_flag  = 0;
end_write_addr  = 0;
end_write_value = 0;

つまり全レジスタとメモリを前回と同じ値にすればよい。特にプログラムカウンタを前回と同じ値にするのがミソだ。こうすることで、CPUは延々とhlt命令を実行し続けることになる。

なお本物のhlt命令を実装するにはメモリへのアクセスを停止しなければならない。面倒くさいので安直に実装した。

以上で、 make_next_reg.sv の全部分を説明し終えた。ここまで読んでくださった方、誰もいないと思いますが、どうもありがとうございました。

このCPUのよくないところ

最後に注意を述べる。

今回作ったCPUは、ひとつだけ猛烈にヤバい処理をしている。どこかわかるだろうか?

答えはメモリからオペコード類をフェッチするところだ。あんな処理は現実のCPUだとありえないと思う。

あそこではクロックの立ち上がり毎に、ip, ip+1, spで指定されるメモリアドレスの3つの値を一斉にフェッチしていた。これを実現するには、データバスとアドレスバスを3倍に増やすなど、いろいろ気持ち悪いことをしなければならない。今回は話を簡単にして1クロックで処理を終了させたかったので、ズルをしたのだ。

もっと言うと、演算モジュールの引数にメモリ全体が入ってるのが強烈にヤバい。これではクロック立ち上がり毎に、全てのメモリの値をCPUにフェッチすることになる。データバスもアドレスバスもあったもんじゃない。

この辺をちゃんとやりたければ、

全機械語命令を、即値使用、スタック使用、オペコードのみ使用、の3つに分類
各々の命令に対しステートマシンを描く
1クロックでメモリを8bitだけ演算モジュールに渡すように、cpuモジュールを改変

という作業が必要になる。

まぁでもいいじゃん。FPGAでフィボナッチ動いたんだし。初日に書いたように、「とりあえず動く」「作り込まない」をモットーにしているので、多少のズルは許してもらおう。

どうでもいい話

今日で回路から見たCPUの話は一旦終了だ。お疲れ様でした。

ところで読者の中には「x86のCPUをFPGAで作るんちゃうんか？？ああん？？」と怒ってる方がいらっしゃると思いますが、それはx86の命令セットを解説し、エミュレータを作った後で取り組もうと思います。物事には順序ってものがある。

でもなぁ。日数が厳しいんだよな。予想外に回路パートに時間を取られてしまった。 x86をFPGAで作ると、クリスマスまでにコンパイラ編を終えるのが不可能になってしまう。どうしたものか。

三項演算子のcond ? a : bならalwaysの外で使用可能。↩
addとsubの結果で、zfは更新しないことにした。つまりcmp命令のみzfを書き換える。実装が面倒くさかったから。。↩

2017-12-09

9日目: [CPU] FPGAでCPUを自作 (前半)

アドベントカレンダー2017 低レイヤマイクロアーキテクチャ FPGA

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

今日から2日かけて、FPGA上に昨日の命令セットのCPUを実装する。言語はSystem Verilogを用いる。完成品のリポジトリはこれ。こいつでフィボナッチ数を計算すると

2進数で、1, 2, 3, 5, 8, 13, 21, 34, 55 を計算しているのが分かるだろう。

全体の流れ

FPGAで回路を組む手順をすべて書くと

FPGAを買う
買ったやつにあわせて制約ファイルを書く
シミュレーション用のモジュールを書く(HDLでコーディング)
そこにassertテストコードを追加
シミュレーションして、各レジスタの電圧波形を見る。テストを走らせる
テストが通る
論理合成用のモジュールを書く
論理合成する
論理合成結果をインプリメントする
ビット列に変換する
FPGA本体にビット列を書き込む
動作する。LEDがチカチカ光る

今日と明日解説するのは、工程3, 4, 7のモジュールを書くところだ。テキストエディタでSystem Verilogを書くことになる。

その他の工程ではIDEを使う。僕はVivadoというやつを使っている。 Vivadoはインストールがクソゲボみたいに難しいのだが、慣れると使いやすい。

今日はまず工程3, 4のシミュレーション用モジュール test.sv を全行解説する。その後、工程7の論理合成モジュール top.sv を説明する。

シミュレーション用モジュールの全容

この続きを読む前に4日目の記事を読み直して欲しい。あそこに書いたHDLコードが十分に理解できてないと、この先は意味不明だと思う。

今から test.sv を見ていくのだが、全部で130行ほどのコードだ。処理内容をざっと書くと

順番	処理の概要	注意点	4日目のコードの対応箇所
1	シミュ用の外部素子を宣言	クロック、リセットボタン、出力の3つを用意する	`module cpu( input CLOCK);`
2	メモリとレジスタの宣言	メモリはDフリップフロップ的な記憶素子がたくさん並んだものと考える	`logic a;`
3	更新用ワイヤの宣言	次回のクロック立ち上がりでレジスタとメモリに入れるやつ	`logic b;`
4	ワイヤの更新	外部の`make_next_reg`モジュールを呼び出す。詳細は明日	`always_comb b = ~a;`
5	クロック立上がりで更新	リセットがOFFの場合に更新	`always_ff @(posedge CLOCK) a <= b;`
6	クロック立上がりで初期化	リセットがONの場合に初期化	なし
7	シミュ用クロック作成	論理合成の際は消去する	なし
8	assertテスト	論理合成の際は消去する	なし

参考用に4日目のHDLコードを再掲しておくと

module cpu( input CLOCK);

  logic a;    // 素子aを用意
  logic b;    // 素子bを用意

  always_comb // 電圧変化が即座に伝わる繋ぎを書く
    b = ~a;   // bの入口に、aの出口を反転して繋いだ
              // bの出口は即座に電圧が変わる。
              // つまりbはワイヤーだ

  always_ff @(posedge CLOCK) // 電圧変化がクロック立上りの瞬間だけ伝わる繋ぎを書く
    a <= b;   // aの入口に、bの出口を繋いだ
              // aの出口はクロック立上りの瞬間だけ電圧が変わる。
              // つまりaはDフリップフロップだ

endmodule

以下では、ファイルの上から順にコードを説明していく。

外部素子を宣言

まずファイルの冒頭。から説明する。

cpuモジュールの一番最初に

logic CLOCK;
logic RESET;
logic [7:0] OUT;

としてクロックとリセット(ボタンのつもり)とアウトプット(LEDのつもり)が宣言されている。

クロックは、ファイルの最後の方でシミュレーションの設定を書く時に使う。
リセットボタンは、0(推されてない)なら普通にレジスタとメモリを更新し、1(押されている)ならレジスタとメモリを初期化する。詳細はalways_ffのところで説明する。
アウトプットは、とりあえずaレジスタの値を表示するのに使っている。深い意味はない。

メモリとレジスタの宣言

着目してる場所はここ。

外部素子の次は、CPU内のレジスタと、CPU外部(のつもり)のメモリを宣言している。 4日目のコードのlogic a;にあたる部分だ。これらは全てDフリップフロップの集合だとみなせる。

// メモリの宣言
logic [7:0] memory [`MEMSIZE-1:0];

// レジスタの宣言
logic [7:0] a;  // reg
logic [7:0] b;  // reg
logic [7:0] c;  // reg
logic [7:0] d;  // reg
logic [7:0] sp; // reg
logic [7:0] ip; // reg
logic zf;       // reg

memoryの配列を定義する際に、MEMSIZEはマクロを使っている。この値はファイルの先頭で64と定義した。 2次元配列の宣言がややキモいが、慣れるしかない。

zfは1bitのゼロフラグを表している。

更新用ワイヤの宣言

着目してる場所はここ。

CPUを一言でいうと、クロック毎にメモリやレジスタに値を代入する回路であった。この「代入する値」を格納するワイヤーをここで宣言する。 4日目のコードのlogic b;にあたる部分だ。

// メモリ直前のワイヤの宣言
logic                write_flag;
logic [`MEMSIZE-1:0] write_addr;
logic [7:0]          write_value;

// レジスタ直前のワイヤの宣言
logic [7:0] next_a;  // wire
logic [7:0] next_b;  // wire
logic [7:0] next_c;  // wire
logic [7:0] next_d;  // wire
logic [7:0] next_sp; // wire
logic [7:0] next_ip; // wire
logic next_zf;       // wire

メモリについては、全アドレスに毎クロック代入するのは筋が悪いので、変更すべき部分を指定して代入するようにしている。

write_flag : 0なら全メモリを保持、1なら1byte分のメモリを変更
write_addr : 変更するメモリのアドレス
write_value : 変更後のメモリの値

レジスタを変更するためのワイヤーは、説明いらないと思う。

ワイヤの更新

着目してる場所はここ。

現在のレジスタの出力を元に、今宣言したワイヤの値を作成しなければならない。要するに、現在のメモリの現在値を表すmemoryとレジスタの現在値を表すa等を元に、メモリ更新用ワイヤのwrite_flagやレジスタ更新用ワイヤのnext_a等に値を入れれば良い。

4日目のコードのalways_comb b = ~a;にあたる部分だが、今回は巨大な組み合わせ回路になる。この部分はややこしいので、別のモジュールに切り出した。

make_next_reg make_next_reg_0(
  memory, write_flag, write_addr, write_value
  ,      a,      b,      c,      d,      sp,      ip,      zf
  , next_a, next_b, next_c, next_d, next_sp, next_ip, next_zf
);

make_next_regがモジュール名(別ファイルで定義されている)で、 make_next_reg_0がインスタンス名(ここで適当につける)だ。

make_next_regモジュールの中身については、明日解説する予定。

クロックの立ち上り

着目してる場所はここ。

今作ったnext_aのワイヤの電圧値で、クロックの立ち上りの瞬間にaレジスタを上書きしたい。 4日目のコードのalways_ff @(posedge CLOCK) a <= b;にあたる部分だ。

always @(posedge CLOCK) begin
  case(RESET)
    // リセットOFFで通常更新
    1'b0: begin
      // メモリの更新
      case(write_flag)
        1'b1: begin
          memory[write_addr] <= write_value[7:0];
        end
        default:;
      endcase
      // レジスタの更新
      OUT <= next_a[7:0];
      a  <= next_a;
      b  <= next_b;
      c  <= next_c;
      d  <= next_d;
      sp <= next_sp;
      ip <= next_ip;
      zf <= next_zf;
    end

    // リセットONの場合
    1'b1: begin $display("RESET ON");
      // メモリの初期化
      $readmemb("test.txt", memory);
      // レジスタの初期化
      OUT <= 8'h00;
      a   <= 8'h00;
      b   <= 8'h00;
      c   <= 8'h00;
      d   <= 8'h00;
      sp  <= `MEMSIZE;
      ip  <= 8'h00;
      zf  <= 1'b0;
    end

    default: $display("Undefined Reset Button");
  endcase
end

コードをよく見ると、RESETの値で場合分けされている。 RESETが0、つまりリセットボタンが押されていなければ、メモリとレジスタはnext_***のワイヤーの値で更新される。 RESETが1の場合は、メモリとレジスタを初期化している。

特にメモリの初期化では外部ファイルの test.txt を読み込んでいる。 Vivadoの場合、このファイルはプロジェクトディレクトリ以下の ***.sim/sim_1/behav/test.txtに置けば良い。

ちなみに外部ファイルの読み込みはシミュレーションでしか使えない(多分)ので、論理合成する場合は

memory[0] <= 8'b10100000;
memory[1] <= 8'b11011000;
...

のように書かなければならない。

シミュレーション用のクロック生成

着目してる場所はここ。

ここから先は完全にシミュレーションの話だ。

まずクロックを5単位時間毎に反転させる。つまり、クロックの立ち上りは10単位時間毎にやってくる。

initial begin
  CLOCK = 1'b0;
  forever begin
    #5;
    CLOCK = ~ CLOCK;
  end
end

このようにinitialで指定されるブロックは、シミュレーションの開始とともに手続き的に実行され、論理合成の際には無視される。 #5;は5単位時間の経過を待つという意味で、foeverは無限ループ。

assertテスト

着目してる場所はここ。

クロックを作ったので、次はレジスタとメモリを初期化したい。そのためにはリセットボタンを押せば良かった。まず、シミュレーションの開始時点でリセットを1にしておく。しばらく経ったら0に切り替えて、レジスタとワイヤを通常更新するモードに移ろう。

initial begin

  RESET = 1'b1;
  # 6;
  RESET = 1'b0;

  #8;

  #10;$display("0100 00 00 00000001 // mov  a, imm -- a=01"); assert(a === 1);
  #10;$display("0101 00 00 00000001 // add  a, imm -- a=10"); assert(a === 2);
  // 略

  $stop;
end

CPUは10単位時間毎に新たな機械語命令をメモリからフェッチして実行し、レジスタの値が更新される。このレジスタの値が予想と整合するか、シミュレーション時にassertで調べている。 display関数はtclコンソールに結果が出力される。ちなみにメモリの内容は、リポジトリ内のtest.txtに用意した。

論理合成

以上でHDLのシミュレーションの説明は終了だ。これを論理合成してFPGAに書き込めば、実機で動作するわけだが、今解説したテストコードのままでは動かない。

テストコードを合成用コードに書き換える必要がある。

HDLの書き換え

論理合成するためには、まずテストコードを以下のように変更する

CLOCK, RESET, OUTをcpuモジュールの引数にする
メモリの初期化を、外部ファイル読込ではなくHDLコードに直書きする
initial構文の部分を全削除

クロックを間引く

これでも良いのだが、FPGAのクロックは100MHzぐらいなので、test.txtを実行するとマイクロ秒以下で終了してしまう。見栄えが良くないので、クロックを1Hzに変更しよう。そのためにはこのような処理が必要になる。

module top( input CLK100MHZ, input RESET, output reg [7:0] OUT);

  reg [26:0] counter;
  wire CLOCK;
  assign CLOCK = counter < 100_000_000 / 2;

  cpu cpu_0(CLOCK, RESET, OUT);

  always @(posedge CLK100MHZ) begin
    counter <= RESET | counter < 100_000_000 ? counter + 1 : 0;
  end

endmodule

まずtopモジュールの中でCLOCKというワイヤをつくり、1秒毎に反転させる。そして引数にCLOCKを入れて、cpuモジュールを呼び出している。

制約ファイル

最後に、topモジュールの引数をいかにして与えるか、という問題が残っている。合成後は

CLK100MHZ : FPGAに備え付けのクロック回路を使う
RESET : FPGAに備え付けのボタンを使う
OUT : FPGAに備え付けのLEDを使う

としたいわけだが、これは制約ファイル constrain.xdc を書くことで実現できる。 FPGAによって制約ファイルの中身は変わるわけだが、Xilinxのartyであれば

set_property -dict {PACKAGE_PIN E3 IOSTANDARD  LVCMOS33} [get_ports {CLK100MHZ}];
create_clock -period 10.0 -name sys_clk_pin -waveform {0.0 5.0} -add [get_ports {CLK100MHZ}];

set_property -dict {PACKAGE_PIN F6  IOSTANDARD LVCMOS33} [get_ports {OUT[0]}];
... 略 ...
set_property -dict {PACKAGE_PIN T10 IOSTANDARD LVCMOS33} [get_ports {OUT[7]}];

set_property -dict {PACKAGE_PIN D9  IOSTANDARD LVCMOS33} [get_ports {RESET}];

こんな感じになる。 FPGAのピンの正式名称はE3とかD9なのだが、それらにCLK100MHZやRESETのようなエイリアスを貼って、topモジュールの引数にしている。

ビット列ファイルの在処

必要なファイルは揃ったので、Vivadoで論理合成してインプリメントしてビット列を生成し、FPGAに書き込めば実機動作する。めでたい。ここで困るのがビット列ファイルの所在なのだが、Vivadoの場合はプロジェクト以下の simple_cpu.runs/impl_1/***.bitに生成される。

これをOpen Hardware ManagerからFPGAに書き込めば良い。

どうでもいい話

FPGAを使う際の一番高いハードル、Vivadoのインストールだと思う。次のハードルはVivadoの使い方を知ることだと思う。がんばれ～

明日は、今日飛ばしたmake_next_regモジュールの説明をします。

2017-12-08

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

アドベントカレンダー2017 低レイヤマイクロアーキテクチャ

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

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

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

初日から一週間経った

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

半導体からNANDゲートを作成
NANDゲートからDフリップフロップを作成
Dフリップフロップから1bitのCPUを作成
1bitのCPUのから複数レジスタ・複数bitのCPUを作成
mov命令、計算命令を追加
機械語フェッチ・メモリスタックを追加

という順序で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	停止

まずニーモニックの欄と機械語の欄をざっと見て欲しい。 movやpushといった単語(オペコードという)が、機械語の最初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を代入

という命令の0x1234がimmだ。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数ぐらいしかない。

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

2017-12-07

7日目: [CPU] メモリとプログラムカウンタ

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

昨日は計算の回路実装をやった。四則演算ができるようになった。

ところで昨日までは「どのレジスタにどの演算を実行するか」という、命令を与える方法について深く考えてこなかった。今日はその辺をやる。

メモリの必要性

昨日も一昨日も出てきたMOV命令だけのCPUだが

f:id:kaitou_ryaku:20171204032911p:plain:w400

今までは、図の下の方のSxやSyの電圧を人力で調整し、クロックのたびに演算が行うという体だった。今日はこの操作を自動化したい。つまりSxとSyへの信号を、どこかから自動で取得する仕組みが欲しい。

これを実現するには、メモリ上に機械語(つまりSxとSyの電圧値)をあらかじめ格納しておき、クロック立ち上り毎に値を持ってきて、SxとSyに繋げばよい。ここでメモリは電圧値を保存(セーブとロード)できるデバイスを意味している。

メモリの役割を果たす回路は色々あるのだが、たとえばDフリップフロップをたくさん並べた配列は、電圧値の保持と上書きが可能なのでメモリとして使うことができる¹。電気屋で売られている普通のメモリはDRAMと呼ばれるもので、Dフリップフロップより値段が安く、動作も遅い。メモリの実装にはあまり興味がないので、とりあえずDRAM素子(もしくはDフリップフロップ)がたくさん並んだやつがCPUにつながってるんだな、と思って欲しい。

機械語の読み込み

昨日と一昨日のMOV命令回路とメモリを連動させるには、クロックが立ち上がる度にメモリから情報を取得し、それに応じてSxとSyの値を変えればよかった。その回路を図示すると

f:id:kaitou_ryaku:20171207220420p:plain

まず左下を見ると、汎用レジスタがいる。こいつは最初の画像、つまりMOV命令のレジスタ転送回路を表している。汎用レジスタは計算用レジスタだと思って欲しい²。 [^1]スタックポインタなど、計算用以外の汎用レジスタもある。汎用レジスタの下から出ている線(4本束ねて書いてある)が、さっきのSxとSyに対応している。

この4本の線はデータバスを経由して仮想メモリの値(4bit)に繋がっている。ここにはCPUが実行すべき機械語が順番に詰まっている。バスという用語は初耳かもしれないが、ただのワイヤだ。

読むべきメモリのアドレスは、プログラムカウンタ(図のカウンタのところ)で指定されている。これはDフリップフロップ8個で構成されており、1クロック毎に加算器で+1されている。この8bitカウンタの電圧値は8本線の赤いアドレスバスを通り、デマルチプレクサに入る。そこで2^8=256本の線に分裂し、1本だけ電圧1、他の254本は電圧0になる。このようにして8bitのプログラムカウンタから256種のメモリアドレスが選出される。

このような仕組みで、CPUはクロックが変わるたびに新しい命令をメモリから取得してきている。ここで出てきたプログラムカウンタはレジスタだが、計算用ではなく機械語取得用であり、汎用レジスタではない。

他のデバイス

さっきの画像の右側を見ると、物理メモリ、HDD、ディスプレイ、キーボードがいる。 CPUはこれらのデバイスを仮想メモリという単一の記憶素子として見ている(ということにしてくれ)。

仮想メモリのアドレスの大半は物理メモリに由来している。物理メモリとは4GBや8GBの普通のDRAMメモリのことだ。 CPUが実行すべき機械語命令のレシピは、全てここに置かれている。

ディスプレイを光らせたい時は、仮想メモリのディスプレイに該当する箇所に値を書き込めばいい。キーボードの値を読む時は、仮想メモリのキーボードに該当する箇所の値を読めばいい[^2]。だいたいそんな感じでPCは動いている。

いちいち仮想メモリと書くのは煩わしいので、今後は単にメモリと書く。デバイスのことを深刻に考えない限り、メモリと言えば物理メモリを想像してもらって差し支えない。

メモリへの書き込み

さっきの回路図では

プログラムカウンタ -> アドレスバス -> メモリ
-> データバス -> 汎用レジスタ

という方向に電圧信号が伝わることで、CPUはクロック毎に新しい命令を受け取ることができていた。

次はメモリに値を書き込んでみたいのだが

汎用レジスタ -> アドレスバス & データバス -> メモリ

という方向に電圧信号を伝えることで、汎用レジスタの値をメモリに書き込むことができる。

では、メモリは読み込み命令と書き込み命令をどのようにして判別しているのだろうか。答えはコントロールバスだ。さっきの図では簡単のために省略したのだが、CPUメモリ間のバスをちゃんと描くと

名称	from	to
アドレスバス	CPU	メモリ
書き込み用データバス	CPU	メモリ
読み込み用データバス	メモリ	CPU
コントロールバス	CPU	メモリ

の4種類があると(多分)。コントロールバスは「メモリに値を書き込め」「読み込め」「何もするな」等の命令をCPUから送るためのものだ。

これらのバスをうまく操作し、CPUとメモリが協調しながら処理が進んでいく。

完全にマジでホントのCPU

メモリの読み書きを説明したので、ちょっと本格的なCPUをスケッチしてみる。具体的には

メモリから機械語命令を読む
ジャンプ命令
メモリからデータを読む (アドレスは汎用レジスタの値で指定)
汎用レジスタの値をメモリに書く
汎用レジスタの値を更新
停止

という命令が可能なCPUだ。一見高度なCPUに見えるが、実はさっきの回路にALUとデコーダを追加するだけで実現できる。今から詳しく見ていこう。

ちなみに、最新のPCに搭載されているCPUもこれと似たようなものだ。なんだ大した事ねーなと思ってほしい³。これから、各命令発動時のCPUの様子を図で説明していく。

メモリから機械語命令を読む

次回実行するための機械語命令を読み込む時の回路の様子は

f:id:kaitou_ryaku:20171207221231p:plain:w400

赤い部分だけを見ると、一つ上の画像とほとんど変わらない。プログラムカウンタがインクリメントされ、機械語がメモリからフェッチされている。

少し違うのはALUとデコーダが追加されたところだが、大したことはない。

ALUはArithmetic Logic Unit(算術論理演算装置)の略称で、昨日出てきた四則演算器を用いて汎用レジスタを更新するユニットを表している。

デコーダは機械語命令を読み込んで、CPUの動作を取り仕切るユニットだ。昨日MOVだけの回路に算術演算を組み込んだが、そこではTやSの電圧を変えることで演算の種類を変更することができた。デコーダは、フェッチした機械語をTやSにうまく差し込むための素子だと考えればよい。

デコーダの中身は、おおむねデマルチプレクサと思ってよい。処理手順をざっくり書くと

あらかじめ汎用レジスタ間の加減乗除を全パターン計算しておく
メモリから機械語命令(8bit)を読む
機械語命令がデコーダに入る
デマルチプレクサで256本に分岐し、そのうち1本の電圧が1、他は0になる
その結果とマルチプレクサを組み合わせて、加減乗除の結果を一つ選び、汎用レジスタを更新する

手順5の意味が分からない場合、昨日の記事の最初の方を読めばわかると思う。

ジャンプ命令

この命令は、要するにプログラムカウンタの上書きだ。

f:id:kaitou_ryaku:20171207220611p:plain:w400

デコーダから左に伸びた線がカウンタを上書きし、最終的にアドレスバスに到達している。つまり、次に読み込む機械語のアドレスをデコーダが上書きしたわけだ。さっきの命令ではメモリに並んだ機械語が順番に実行されていたが、カウンタが上書きされると、次回読み込まれるはずだった機械語がスキップされたり巻き戻されたりする。こうした命令をジャンプ命令という。

今の説明をニーモニックで忠実に書くと

mov プログラムカウンタのレジスタ, 値

となるのだが、この命令は使いにくい。むしろプログラムカウンタからの差分値でジャンプ先を指定するのが分かりやすいので

add プログラムカウンタのレジスタ, 差分

; プログラムカウンタ = プログラムカウンタ + 差分

という操作を行うことが多い。

ところでプログラムカウンタを「計算」するのは行儀が悪いとされている。昨日までに出てきた汎用レジスタ(計算用レジスタ)とは存在意義が異なるので、addのような計算まるだしの書き方は推奨されない。そこで

jmp 差分

と書くのが普通だ。要するに、差分で指定された数だけメモリ上の機械語をスキップしますよ、という命令だ。

蛇足だが、jmp命令をC言語に翻訳するとifやwhileといった分岐処理になる。

さらに蛇足だが、ジャンプ命令は昨日説明した計算フラグと関係が深い。例えばゼロフラグを見れば、直前のa-bの計算結果がゼロかどうか分かる。そこでゼロフラグが立っていればジャンプする jz 命令を用意すれば、 C言語のif (a==b) {...}のような処理が実現できる。

後日FPGAでCPUを作る際はjmpとjzを実装する予定。

メモリからデータを読む

「さっき計算結果をメモリに書き込んだのだが、それを取り出して使いたい」という要望を叶える命令だ。

f:id:kaitou_ryaku:20171207220627p:plain:w400

汎用レジスタの値がアドレスバスを経由してメモリに入っている。つまり、汎用レジスタに書かれた番地に行って、値をとってこいという命令が実行されている。

メモリからのデータの読み込みは、メモリ上にスタックを構築した際のpop命令の実装に必要となる。popの詳細は以下のpushのところにまとめておいた。

汎用レジスタの値をメモリに書く

アセンブラで書くと

mov [0x12], 汎用レジスタ

; [0x12]は0x12番地のメモリを表す

のような操作だ。

f:id:kaitou_ryaku:20171207220638p:plain:w400

アドレスバスに加え、メモリへの書き込み用のデータバスにも値が流れていることに注意して欲しい。汎用レジスタの値を用いて、書き込むべきアドレスと値のペアをメモリに送信しているわけだ。

ちなみに、メモリに計算結果を書き込んだり読み込んだりする場合はスタックポインタを用いるのが便利だ。その仕組みを解説すると、まずメモリの使用法として

機械語はメモリの最初(0x0000付近)に置くことにする
計算結果のデータはメモリの最後(0xFFFF付近)に置くことにする

このルールに基いてメモリを使うことにする。次に

次のデータ書き込むためのメモリアドレスを表す、espという汎用レジスタを用意しておく
つまりデータを一切書き込んでない状況では、espは0xFFFFという値になる
push操作: espの指すアドレスに値を書き込んで、espを-1する
pop操作: esp+1の値を読み込んで、espを+1する。この操作でメモリからデータが論理削除されたと考える

このようなスタック操作でメモリに値を出し入れするのが便利だ。これらの命令は、後日FPGAでCPUを作る時に実装する予定。

汎用レジスタの値を更新

さっきは値をメモリに書き込んだが、今回は汎用レジスタに書き込みたい。ニーモニックで書くと

add 汎用レジスタa, 汎用レジスタb

; 汎用レジスタa = 汎用レジスタa + 汎用レジスタb

これは昨日までに散々やった内容だし、メモリも絡んでないので説明を飛ばす。

停止

最後はメモリの読み込みをストップする操作だ。全処理が終わってCPUを停止(halt)する際には、メモリの読み込みを止める必要がある。

f:id:kaitou_ryaku:20171207220649p:plain:w400

後日FPGAでCPUを作るときには、メモリアクセスを停止する代わりにプログラムカウンタのインクリメントを止めて、CPUを停止させる予定。この方法はクロックの度に無駄にメモリにアクセスするのでよくないのだが、実装が簡単なので。。。。

処理終了以外のシチュエーションでも命令の読み込みを一時停止することがある。例えば浮動小数点の計算などの重い処理は、一回のクロックだと終了しないので、計算が終わるまで次の命令の読み込みを停止する必要がある。

ここまでで、メモリに関する話は一旦終了だ。やれやれだぜ。

どうでもいい話

この記事では、メモリは1クロックで値を返すことを暗に仮定していたが、実際のDRAMメモリでは遅延が生じる。百億近くのアドレスの中から特定のアドレスを見つける必要があるので、時間がかかって当然だろう。またCPUからメモリへの物理的な(センチメートル単位の)距離による遅延も無視できない。

あらためて読み返すと、初日に「概論は嫌い(キリッ」などと言っておきながら、今日の記事は概論臭がすごい。あーあ。

今日でカレンダー開始一週間か。毎日書くのはかなりキツイな。

実際のCPUのSRAM1次キャッシュはそんな感じだし、それほど間違った説明ではないと思う。↩
現実では割り込み処理があってややこしい。そのうえIO用の特殊なCPU命令があるかもしれない。↩
この記事のCPUと最新のCPUの違いは最適化にある。米Intelは毎年1兆円かけてCPUの回路を最適化しており、むちゃくちゃ機敏に動く。しかし機械語命令の実行結果は記事中のCPUとさほど変わらない。↩

2017-12-06

6日目: [CPU] bit拡張と数値演算

アドベントカレンダー2017 低レイヤマイクロアーキテクチャ

bit拡張と数値演算

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

昨日は変数(レジスタ)の数を4個に増やして、mov命令が実行できるCPUを設計した。しかしmov命令だけでは大したことができない。そこで今日は(浮動小数点を含む)四則演算ができるように回路を拡張する。

bit拡張

昨日はレジスタの種類を増やしたが、各レジスタの桁数は1bitのままだった。 2進数1桁の変数では計算もへったくれもない¹ので、まずはbitを拡張しよう。拡張方法は極めて簡単。例えばmov a, bを考えると、aの1の位はbの1の位で上書きされ、10の位は10の位で上書きされる。つまりmov命令は各桁毎に独立に実行される。

これを実現するには、昨日の回路と全く同じものを並べればいい。

f:id:kaitou_ryaku:20171204032844p:plain

当然だが、マルチプレクサに入る線Sx, Syは各桁の回路で共通化する。これでのmov命令CPUを4bitに拡張することができた。

ちなみに世間で32bitのCPUとか64bitのOSとか騒いでいるのは、このレジスタのbit数のことを指している。こうしてみると、Dのフリップフロップを単純にたくさん並べればbitが増やせるので、128bitでも256bitでも簡単に拡張できそうだ。

複数ビットを配列としてSystem Verilogで扱うには

logic [0:3] A;
assign A = 4'b0011; // 十進数と十六進数で3
// A[0] === 1'b0;
// A[1] === 1'b0;
// A[2] === 1'b1;
// A[3] === 1'b1;

logic [3:0] B;
assign B = 4'b0011; // 十進数と十六進数で3
// B[3] === 1'b0;
// B[2] === 1'b0;
// B[1] === 1'b1;
// B[0] === 1'b1;

logic [7:0] memory [0:63];       // 8bitのメモリが64個ある
assign memory[ 0] = 8'b00000011; // 十進数と十六進数で3
assign memory[ 1] = 8'b00000111; // 十進数と十六進数で7
assign memory[63] = 8'b00001000; // 十進数と十六進数で8

演算素子の追加

変数の桁が増えたので、次は計算命令をCPUに追加しよう。簡単のために、まずは昨日の1bitのCPUに演算の素子を追加してみる。

昨日の回路

f:id:kaitou_ryaku:20171204032911p:plain:w600

ここから赤い部分だけを取り出したのが下の左の図

f:id:kaitou_ryaku:20171204032921p:plain

取り出した部分に対し、右図のように演算の素子を追加する。こうすれば、人力でTの線に電圧を印加することで、レジスタ間の演算が行えるようになる。

1bitのCPUに演算を追加する方法は分かったが、次はこれを複数bitに拡張したい。

f:id:kaitou_ryaku:20171204032934p:plain:w400

やや抽象的な図で恐縮だが、要するに足す前に各桁の線を集めて、加算を実行し、結果を各桁に散らすという方法で複数bitの演算が実現できる。

この図のFull Adderの部分に減算器や乗算器などの組み合わせ回路を追加して、マルチプレクサで演算種別を選択できるようにすれば、様々な計算が実行可能なCPUになる。今日の残りの時間は、ここに入れる組み合わせ回路をひたすら説明していく。

整数の加算

まずは加算を実装したい。そのためにまず半加算器(Half Adder)を作り、それを使って全加算器(Full Adder)を作ればよい。

半加算器を一言でいうと、1bitのA,Bの加算を行う回路だ。

f:id:kaitou_ryaku:20171204032958g:plain:w400

真理値表は

A,B	S	C
0,0	0	0
0,1	1	0
1,0	1	0
1,1	0	1

つまりA+Bの1の位がSに入り、10の位がCに入る。

このままでは複数桁どうしの加算には使えないので、全加算器に拡張する。全加算器を一言でいうと、1bitのA,B,Xの加算を行う回路だ。

f:id:kaitou_ryaku:20171204033011g:plain:w400

真理値表は

X,A,B	S	C
0,0,0	0	0
0,0,1	1	0
0,1,0	1	0
0,1,1	0	1
1,0,0	1	0
1,0,1	0	1
1,1,0	0	1
1,1,1	1	1

要するにX+A+Bの1の位がSに、10の位がCに入る。

次に複数桁同士の加算を考える。

4桁同士の加算 A+B=C を計算するには、

A[0]+B[0]を半加算器で計算し、その繰り上がりをX[1]とする
A[1]+B[1]+X[1]を全加算器で計算し、その繰り上がりをX[2]とする
A[2]+B[2]+X[2]を全加算器で計算し、その繰り上がりをX[3]とする
A[3]+B[3]+X[3]を全加算器で計算し、その繰り上がりをX[4]とする
A[4]+B[4]+X[4]を全加算器で計算し、その繰り上がりをキャリーフラグとする

つまり小さい桁から1bit毎に足していけば、複数桁の加算結果が得られる。回路図で書くと

f:id:kaitou_ryaku:20171204033024p:plain

回路図は4bitのAとBを加算する回路を表している。

ちなみに最も大きな桁が繰り上がった場合、キャリーフラグが立ったという。図の右端のCはキャリーフラグを表している。

キャリーフラグは計算の破綻を意味しているように見えるが、必ずしもそうではない。今から説明する減算の際にはキャリーフラグが立ちまくる。

2の補数と整数の減算

加算の回路は構成できたので、次は減算だ。ところでA-BはA+(-B)なので、Bをマイナスにする方法が分かれば、さっきの加算器を使って減算が実現できる。

数学的に-Bは、Bと加算するとゼロになる数として定義されている。ここで

0001+1111=10000 -> 5bit目無視 -> 0000

という計算を考えると、4bitの範囲で-0001は1111っぽい雰囲気がある。ここで0001から1111を得る操作は

   0001のマイナスを計算したい
-> 1110 (ビット反転)
-> 1111 (1を足す)

このようにして得られる数を2の補数という。この辺の細かい話(符号付き整数の範囲は-4~3なのか-3~4なのか等)は後のx86のパートで詳しくやる予定なので、今はとりあえず2の補数とればマイナスになるんだなと思って欲しい。

ここまでの話をまとめると、A-Bを実現するには

Bをbit反転する
そこに1を加える
そこにAを加える

とすればよい。この回路は以下のようになる。

f:id:kaitou_ryaku:20171204033034p:plain

BバーはBのbit反転を表しており、Bの各桁をNOTゲートに入れれば作成できる。 2の補数を計算する際に1を加えるが、それは左端の全加算器(FA)に1を入力して対処している。

整数の乗除

加減算が完成したので、次は乗除だ。

2進数の乗除の筆算を考えると、桁をずらしながら加算と減算を実行していることが分かる。加算器と減算器は手元にある。従って、あとは桁のシフトさえできれば筆算のアルゴリズムが実装できる。

桁を1つシフトするのは簡単だ

f:id:kaitou_ryaku:20171204033044p:plain:w400

これを直列につなげれば、何桁でもシフトできる。あとは加算器や減算器とうまく組み合わせることで、乗算器や除算機を作ることができる。要するに「1桁ずつずらして足す」という操作を、レジスタのbit長と同じ回数だけ直列に実行する回路を作れば良い²。

浮動小数点

ここまでの話は整数の話だったが、せっかくなので小数の四則演算も説明する³。計算機上で小数を表現する際、いわゆるfloag型の浮動小数点方式がよく使われる。

float型は32bitのレジスタで表現されるのだが、

最初1bitが符号部
次の8bitが指数部 (桁を表す)
次の23bitが仮数部 (1以上10未満の数値を表す)

という3つの部分で構成されている。

例えば科学技術分野ではアボガドロ数を

+ 6.02214*10^23

という指数形式で表すけど、float型はこれを2進数でやっているだけだ。

ところでアボガドロ数について

  6.02214*10^23 - 6.02201*10^23
= 0.00013*10^23
= 1.3*10^19

という計算を考える。減算による桁落ちが発生し、指数が23から19に変わっている。この数式の2行目から3行目の処理を正規化という。

これと同じ現象がfloat型の演算でも発生する。つまり浮動小数点の計算を行うためには、電子回路で正規化を実装する必要がある。

正規化を行うためには、アボガドロ数の例で説明すると

0.00013を見て、「ゼロでない最大の桁」を発見する機能 ... Find First One
その桁の分だけ0.00013をbitシフトして、1.3にする機能 ... バレルシフタ

この2つの機能が要求される。これらの実装をまとめておく。

Find First One

まず準備として、最初の4桁に1が含まれるか調べたければ、以下のOR回路の組み合わせのif 1 in 4を使えば良い。

f:id:kaitou_ryaku:20171204033059p:plain:w400

これを拡張して、最初に1が現れる桁を発見する回路を作りたいのだが、それはif 1 in 4やif 1 in 8をマルチプレクサで繋げば得られる。

f:id:kaitou_ryaku:20171206202049p:plain

縦長の長方形は固定桁のbitシフタを表す。整数の乗除のところで1桁のbitシフタを導入したが、あれを直列に繋いだものだ。台形のMは頻出のマルチプレクサ。

実はこの回路図だとSのビットが反転しているので、入出力の例は以下のようになる。

input = 0001000011111110 (左から3個0が連続している)

--> [S3, S2, S1, S0] = [~0,~0,~1,~1]   (3は2進数で0011)
                     = [ 1, 1, 0, 0]

バレルシフタ

欲しいのは、入力データをinput、シフトする桁数をSとしたときに

* input = 0001000011111110
* S = 3 (3桁ずらしたい)
  [S3, S2, S1, S0] = [0,0,1,1]   (3は2進数で0011)

--> output = 1000011111110000

となるような組み合わせ回路だ。これは固定長bitシフタとマルチプレクサで構成できる。

f:id:kaitou_ryaku:20171204033119p:plain

以上でFind First Oneとバレルシフタの説明は終了だ。これらと加算器や減算器を組み合わせることで、浮動小数点の正規化ができるようになった。

これだけツールが揃えば、もはやなんでもできる。

2つの浮動小数点数A,Bに対する四則演算であれば

加減: バレルシフタを用いてA,Bのうち小さな方に指数部をあわせて、仮数部同士で加減算を行い、結果を正規化⁴
乗除: 仮数部同士、指数部同士で計算を行い、結果を正規化

他にも、剰余であれ三角関数であれ、今まで紹介した素子を組み合わせれば実装できる(と思う。多分)。

これで算術演算の基礎は一通り書き終えたと思う。

明日はメモリ周りをやる。本格的なCPUの形が見えてきた。

どうでもいい話

今日は計算を説明したが、加算器のところにキャリーフラグが出てきた。このような計算に伴うフラグは、他にもいくつかあって

符号付き整数の桁あふれを表すオーバーフローフラグ
計算結果がゼロかどうかを表すゼロフラグ
計算結果の符号を表すサインフラグ

詳細はx86のパートを待たれよ

いわゆるブール代数 ↩
レジスタのbitサイズが大きくなると、乗除の際の直列回路が長くなる。すると1クロック以内にDフリップフロップの入口に電圧が到達しない可能性がある。こういうクリティカルパスを短くするのが、高クロックなCPUを作成する際の重要ポイントらしい。↩
今回はハードウェアのFPUで小数点計算を説明した。しかし、FPUを使わず整数の計算だけからソフトウェア的に小数を実装するのもアリだと思う。↩
加減時のキャリーフラグを見て、うまいこと処理する必要がある↩

機械語ファイルをバイナリエディタで開く

なぜ78 56 34 12になるのか

負の整数

byte拡張

キャリーフラグ

オーバーフローフラグ

比較条件

符号付き整数の大小関係

a < b

a >= b

a \<= b

a > b

レジスタの種類

命令セット表

jmp imm8

jmp imm32

命令セット毎に分割

0-3行:計算系

4-7行:inc, push, jcc

8-b行:movがメイン

8-b行:関数呼び出し

C言語の機械語を解析

1 : C言語ソースファイルorg.cの用意

2,3 : コンパイル

4 : 機械語とニーモニックの対応表org.txtの取得

5 : アセンブラ言語のソースコードorg.asmの作成

6,7 : アセンブルとシンプルなバイナリファイル

全て揃った

ニーモニック観察

どうでもいい話

復習

4日目のコードとの対応

引数

ワイヤの宣言と接続

メモリからオペコード類をフェッチ

オペランドのワイヤーの宣言

end_aワイヤーの電圧を作成

オペランドのワイヤの作成

計算命令とメモリ関連命令の分離

計算命令全体

mov x, y (0000 xx yy)

cmp x, y (0011 xx yy)

ope x, imm (01?? xx 00 imm)

メモリ関連の命令

push x (1000 xx 00)

pop x (1001 xx 00)

jmp imm (1010 00 00 imm)

hlt (1111 00 00)

このCPUのよくないところ

どうでもいい話

全体の流れ

シミュレーション用モジュールの全容

外部素子を宣言

メモリとレジスタの宣言

更新用ワイヤの宣言

ワイヤの更新

クロックの立ち上り

シミュレーション用のクロック生成

assertテスト

論理合成

HDLの書き換え

クロックを間引く

制約ファイル

ビット列ファイルの在処

どうでもいい話

初日から一週間経った

レジスタの種類

命令セット

サンプルコード

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

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

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

どうでもいい話

メモリの必要性

機械語の読み込み

他のデバイス

メモリへの書き込み

完全にマジでホントのCPU

メモリから機械語命令を読む

ジャンプ命令

4-7行:`inc`, `push`, `jcc`

8-b行:`mov`がメイン

1 : C言語ソースファイル`org.c`の用意

4 : 機械語とニーモニックの対応表`org.txt`の取得

5 : アセンブラ言語のソースコード`org.asm`の作成

`end_a`ワイヤーの電圧を作成