Brainf*ckを計算機アーキテクチャとして実装する

# はじめに

[Brain*uckを計算機と見立てて実装する - Qiita](http://qiita.com/quwahara/items/db57b02e9528cfaa0d6e)
を読みました。
前半は興味深いことが書かれていたのですが、最終的にできたものは命令を読み取ってそれに合わせた処理を行う、どこにでもあるようなBrainf*ckインタプリタでした。
(逆に実際のCPU、例えば[8086のインタプリタ](https://github.com/mikecat/8086interpreter)も「命令を読み取ってそれに合わせた処理を行う」ものになってしまうことがあるのですが…)
そこで、Verilogを用いて実装してみました。

# 成果物

実装したものを[GitHub](https://github.com/mikecat/brainfuck_verilog)に上げました。
この記事ではこのコードの一部を紹介します。

# とりあえず実装する

## メモリ

メモリ(RAM)はアドレス幅とデータ幅を指定して作成できます。今回使用するメモリのモデルでは、クロックの立ち上がりで指定したアドレスのデータが読み出され、`WE`がHIGHならば指定されたデータが指定されたアドレスに書き込まれます。読み出されるデータは書き込まれる前のものとなります。

```verilog
module ram(clk, data_read, data_write, addr, we);
	parameter ADDR_WIDTH = 15;
	parameter DATA_WIDTH = 8;

	input clk;
	output [DATA_WIDTH-1:0] data_read;
	input [DATA_WIDTH-1:0] data_write;
	input [ADDR_WIDTH-1:0] addr;
	input we;

	reg [DATA_WIDTH-1:0] data_read;
	reg [DATA_WIDTH-1:0] mem[0:(1<<ADDR_WIDTH)-1];

	always @(posedge clk) begin
		data_read <= mem[addr];
		if (we) mem[addr] <= data_write;
	end
endmodule
```

## CPU

今回実装するCPUにおいては、

* 命令フェッチ(IF)
* 命令実行(EX)
* 実行結果の書き込み(WB)

の3ステージを考えます。
また、起動直後にデータメモリの内容を0に初期化します。

### 命令フェッチ

メモリから命令データを読み込み、レジスタに格納します。そして、次の読み込みに備えてプログラムカウンタを進めます。

```verilog
data_we <= 0;
input_read <= 0;
output_write <= 0;
if (pc < prog_size) begin
	inst <= inst_load_data;
	jumpptr <= jumpptr_load_data;
	pc <= pc + 1;
	phase <= `CPU_PHASE_EX;
end else begin
	inst <= 0;
	halted <= 1;
end
```

### 命令実行

読み込んだ命令データに応じた処理を実行します。
メモリへの書き込みが必要な場合は、この時点で書き込み指示を発行し、次のクロックで書き込ませます。
また、ジャンプをする場合はフェッチするアドレスをここで書き換えておかないと、次のフェッチに間に合いません。
また、入出力の準備ができていない場合は、できるまで待機します。

```verilog
case (inst)
`CPU_INST_RIGHT: begin
	data_ptr <= data_ptr + 1;
	phase <= `CPU_PHASE_WB;
end
`CPU_INST_LEFT: begin
	data_ptr <= data_ptr - 1;
	phase <= `CPU_PHASE_WB;
end
`CPU_INST_INC: begin
	data_store_data <= data_load_data + 1;
	data_we <= 1;
	phase <= `CPU_PHASE_WB;
end
`CPU_INST_DEC: begin
	data_store_data <= data_load_data - 1;
	data_we <= 1;
	phase <= `CPU_PHASE_WB;
end
`CPU_INST_WHILE: begin
	if (data_load_data == 0) begin
		pc <= jumpptr;
	end
	phase <= `CPU_PHASE_WB;
end
`CPU_INST_WEND: begin
	if (data_load_data != 0) begin
		pc <= jumpptr;
	end
	phase <= `CPU_PHASE_WB;
end
`CPU_INST_IN: begin
	if (input_valid) begin
		data_store_data <= input_data;
		data_we <= 1;
		input_read <= 1;
		phase <= `CPU_PHASE_WB;
	end
end
`CPU_INST_OUT: begin
	if (~output_busy) begin
		output_data <= data_load_data;
		output_write <= 1;
		phase <= `CPU_PHASE_WB;
	end
end
default: begin
	phase <= `CPU_PHASE_WB;
end
endcase
```

### 実行結果の書き込み

メモリや出力ポートに書き込む指示を出した後、書き込まれるのを待ちつつ、書き込む指示を解除します。
また、今回のメモリの仕様ではメモリに書き込む指示を出した後書き込んだデータを読み出せるまでには2クロックかかるので、次の命令実行をその後にする役割もあります。

```verilog
case (inst)
`CPU_INST_RIGHT: begin
	phase <= `CPU_PHASE_IF;
end
`CPU_INST_LEFT: begin
	phase <= `CPU_PHASE_IF;
end
`CPU_INST_INC: begin
	data_we <= 0;
	phase <= `CPU_PHASE_IF;
end
`CPU_INST_DEC: begin
	data_we <= 0;
	phase <= `CPU_PHASE_IF;
end
`CPU_INST_WHILE: begin
	phase <= `CPU_PHASE_IF;
end
`CPU_INST_WEND: begin
	phase <= `CPU_PHASE_IF;
end
`CPU_INST_IN: begin
	data_we <= 0;
	input_read <= 0;
	phase <= `CPU_PHASE_IF;
end
`CPU_INST_OUT: begin
	output_write <= 0;
	phase <= `CPU_PHASE_IF;
end
default: begin
	phase <= `CPU_PHASE_IF;
end
endcase
```

# CPUを改良する

上のCPUの実装でも動作しますが、1命令の実行に必ず3クロックかかっています。
これでは効率が悪いので、もう少し速くしましょう。
前の命令の実行が完了する前に次の命令の実行を開始する、パイプライン処理のようなものを実装します。

## 時系列順にやるべき処理を追ってみる

やるべき処理を時系列に沿ってテーブルにしてみると、それぞれの状況で何をするべきかがわかりやすくなります。

|時刻|プログラムカウンタ|データポインタ|フェッチした命令|実行した命令|結果を書き込んだ命令|データ読み書きのアドレス|読み込まれるデータ|書き込むデータ|データを書き込むか|メモ|
|---|---|---|---|---|---|---|---|---|---|---|
|0|0|0|0|0|0|0|0|*|0|実行開始|
|1|1|0|+|0|0|0|0|*|0|NOPを実行|
|2|2|0|&gt;|+|0|0|0|1|1|+を実行|
|3|3|1|+|&gt;|+|1|0|*|0|&gt;を実行|
|4|3|1|+|&gt;|+|1|0|*|0|データ読み込みのためストール|
|5|4|1|+|+|&gt;|1|0|1|1|+を実行|
|6|5|1|&gt;|+|+|1|0|2|1|+を実行、フォワーディング|
|7|6|2|[|&gt;|+|2|1|*|0|&gt;を実行|
|8|6|2|[|&gt;|+|2|0|*|0|データ読み込みのためストール|
|9|10|2|0|[|&gt;|2|0|*|0|[を実行、ジャンプを行う|
|10|11|2|]|0|0|2|0|*|0|NOPを実行|
|11|12|2|&gt;|]|0|2|0|*|0|]を実行、ジャンプを行わない|
|12|13|3|IN|&gt;|]|3|0|*|0|&gt;を実行|
|13|14|3|IN|IN|&gt;|3|0|30(入力データ)|1|INを実行|
|14|14|3|IN|IN|&gt;|3|0|*|0|INを実行(強制待機)|
|15|14|3|IN|IN|&gt;|3|0|*|0|INを実行(入力ポート待機)|
|16|15|3|+|IN|IN|3|0|40(入力データ)|1|INを実行|
|17|16|3|OUT|+|IN|3|0|41|1|+を実行、フォワーディング|
|18|17|3|OUT|OUT|+|3|40|*|0|OUTを実行、フォワーディング|
|19|17|3|OUT|OUT|+|3|41|*|0|OUTを実行(強制待機)|
|20|17|3|OUT|OUT|+|3|41|*|0|OUTを実行(出力ポート待機)|
|21|18|3|&gt;|OUT|+|3|41|*|0|OUTを実行|
|22|19|4|&gt;|&gt;|OUT|4|41|*|0|&gt;を実行|
|23|20|5|OUT|&gt;|&gt;|5|0|*|0|&gt;を実行|
|24|20|5|OUT|&gt;|&gt;|5|0|*|0|データ読み込みのためストール|
|25|20|5|OUT|&gt;|&gt;|5|0|*|0|OUTを実行(出力ポート待機)|
|26|21|5|IN|OUT|&gt;|5|0|*|0|OUTを実行|
|27|22|5|0|IN|OUT|5|0|0|1|INを実行|
|28|22|5|0|0|IN|5|0|*|0|halt|
|29|22|5|0|0|0|5|0|*|0|halt|

基本的に前に実行した命令に応じて実行を補正しつつ、フェッチした命令を実行すればいいことがわかります。

## 命令フェッチ

基本的に`pc`(プログラムカウンタ)が指すアドレスのメモリのデータを読み込むのですが、
今回の実装では`pc`が変化してからメモリから読み出されるデータが変化するまでには1クロックの遅延があるので、
この遅延をごまかすためにメモリに1クロック後の`pc`の値を渡してあげます。

さらに、ジャンプを行った直後はプログラムカウンタの変化にメモリが追いつかないので、
命令をフェッチせずにダミーの命令を渡してあげます。

また、プログラムの最後に到達したらフェッチを停止し、ダミーの命令を格納します。

```verilog
assign next_pc = (~rst_i || ~ready) ? 0 :
	(do_stall || io_wait) ? pc :
	do_jump ? jumpptr :
	(pc < prog_size) ? pc + 1 :
	pc;

// 命令フェッチ
if (do_jump) begin
	// ジャンプ
	inst_if <= 0;
	pc <= jumpptr;
end else if (pc < prog_size) begin
	// 命令フェッチ
	inst_if <= inst_load_data;
	jumpptr <= jumpptr_load_data;
	pc <= pc + 1;
end else begin
	// 実行終了
	inst_if <= 0;
	halted <= 1;
end
```

## データのフォワーディング

メモリの値を書き換える指示を出した直後は、まだその値がメモリから出て来ません。
しかし、書き換える指示を出したということは出てくるはずの値はCPUが持っているので、その値を使うことで処理ができます。
書き込み指示を出してから実際に書き込まれるまでの間は2クロックなので、その間指示を出した値を使わせます。

```verilog
// 直前またはその前に実行した命令がメモリに書き込む命令のとき、フォワーディングする
wire do_forwarding = (forwarding_count > 0);
// フォワーディングを反映したメモリの値
wire [7:0] load_data = do_forwarding ? data_store_data : data_load_data;

// 次に実行するのがメモリに書き込む命令か
wire inst_if_mem = (inst_if == `CPU_INST_INC || inst_if == `CPU_INST_DEC || inst_if == `CPU_INST_IN);

forwarding_count <= inst_if_mem ? 2 :
	(forwarding_count > 0) ? forwarding_count - 1 : 0;
```

## ストール

データポインタを変更した直後はメモリから変更前のアドレスの値が出ており、しかもその値をCPUが持っていないので、メモリの値を使いたい場合はメモリから変更後のアドレスの値が出てくるまで1クロック待つ必要があります。
また、入力または出力が連続する場合も、ポート操作によってポートの状態(次の入力データがあるか、次の出力を受け入れることができるか)が変化することが考えられるが、操作した直後はこの変化が反映されないことが考えられるので、反映されるまで1クロック待機します。

```verilog
// 直前に実行した命令がデータポインタの変更で、
// 実行する命令がメモリを使用する命令のとき、ストールする (新しい位置のデータを読み込むため)
wire do_stall_mem = (
	inst_ex == `CPU_INST_RIGHT || inst_ex == `CPU_INST_LEFT
) && (
	inst_if == `CPU_INST_INC || inst_if == `CPU_INST_DEC ||
	inst_if == `CPU_INST_WHILE || inst_if == `CPU_INST_WEND ||
	inst_if == `CPU_INST_OUT
);
// 入力または出力が連続するとき、ストールする (入出力ポートの状態が更新されるのを待つため)
wire do_stall_io = (inst_if == `CPU_INST_IN && inst_ex == `CPU_INST_IN) ||
	(inst_if == `CPU_INST_OUT && inst_ex == `CPU_INST_OUT);

wire do_stall = (do_stall_mem | do_stall_io) & ~stalled;
```


## 命令実行

命令とデータに応じて、次のメモリの状態やデータポインタの値、入出力ポートへの指示を変更します。

```verilog
// 命令実行
data_ptr <= (inst_if == `CPU_INST_RIGHT) ? data_ptr + 1 :
	(inst_if == `CPU_INST_LEFT) ? data_ptr - 1 :
	data_ptr;
data_store_data <= (inst_if == `CPU_INST_INC) ? load_data + 1 :
	(inst_if == `CPU_INST_DEC) ? load_data - 1 :
	(inst_if == `CPU_INST_IN) ? input_data :
	data_store_data;
data_we <= inst_if_mem;
forwarding_count <= inst_if_mem ? 2 :
	(forwarding_count > 0) ? forwarding_count - 1 : 0;
input_read <= inst_if == `CPU_INST_IN;
output_write <= inst_if == `CPU_INST_OUT;
output_data <= load_data;
```

# CPUの比較

"hello, world"を出力するプログラムを実行して結果を比較してみました。

```bf:hello_world.bf
++++++++[>+++++++++++++<-]>.---.+++++++..+++.<++++++[>-----------<-]>-.<
+++[>----<-]>.<+++++++[>++++++++++++<-]>+++.--------.+++.------.--------.
>++++++++++.
```

## 最初のCPU

初期化完了から実行終了まで1459クロックかかりました。
規則正しく1命令を3クロックで実行しています。
![最初のCPUのシミュレーション結果](https://qiita-image-store.s3.amazonaws.com/0/99656/032aa415-0f46-b365-5d9f-06f83d5efe67.png)

## 改良したCPU

初期化完了から実行終了まで563クロックかかり、最初のCPUに比べてこのプログラムの場合は約2.59倍速くなりました。
ストールやジャンプなどの例外を除いて、1命令あたり1クロックで実行できています。
![改良したCPUのシミュレーション結果](https://qiita-image-store.s3.amazonaws.com/0/99656/c754a4ff-de6e-a3ee-2c57-4fedd7495c67.png)


# まとめ

Verilogを用いてBrainf*ckのインタプリタ(Brainf*ckを命令セットとするCPU)を実装することができました。
また、前の命令の実行が完了する前に次の命令の実行を始めることで、プログラムの実行にかかるクロック数を減らすことができました。