Verilogでスタックマシンを作ってみた話

## 1. はじめに

プログラミング言語を作ると言えば東大のCPU実験ですよね。CPUを作ってそれ用のMinCamlを実装してコンパイルして動かすのは夢の１つでもあります。言語を作れたらCPUも自作してみたい。FPGAを使えばVerilogなどのハードウェア記述言語を使ってCPUやGPUが作れてしまうらしいです。

ずっと遠い世界の話だと思っていた訳ですが、FPGAを使う機会がありまして簡単なCPUのようなものを作ってみようと思い足し算と掛け算しかできない簡単なスタックマシンを手始めに作ってみました。

## 2. ハードウェア

対象となるハードウェアは Tang Nano 20k です。非常に小さいハードウェアでUSB-CとHDMIの端子があるだけのハードウェアにブレッドボードとコントーラ２つと接続端子２つついて1万円弱で購入しました。

## 3. 開発ソフトウェア構成

M3 Mac で開発するため Docker の実装である Orb Stack 上にUbuntuを構築しその中で Linux 用の gowin_sh を動かしてビルドし、 OpenFPGALoader で USB経由の UART で接続して送り込みます。USB経由でシリアル通信をして結果を受け取ります。シリアル通信は /dev/usb-serial* に screen コマンドや cu コマンドで受け取ることができます。また Python の pyserial を使うことで通信することができます。

HDMI出力はHDMI入力をUSB-Cで取り込む小型のキャプチャボードをMacにもう１つ繋ぎHTML上からWebカメラを使う要領でブラウザ上で確認しています。QuickTimeでも観たり録画もできますが若干遅れが生じるのが気になるところでした。

## 4. スタックマシンの仕様

Verilog上にバイト配列を用意してプログラムとします。最初の１バイトが命令で場合によって２バイト目以降がデータ部とします。スタックはスタックポインタとスタック用の配列を用意します。プログラムカウンタを用意してコード配列からコードを読み出しスタック操作を行い終了命令があれば値をUARTを用いてシリアル出力します。

```
0 N 整数Nをスタックに積みます。
1 スタックトップの２つの値を足してスタックに積みます。
2 スタックトップをUART経由で出力します。
```

簡単ですね。

## 5. 実装

### 5.1. スタックマシン

Verilogで実装したスタックマシンを以下に示します：

```verilog:StackMachine.v
module StackMachine(input clk, rst, output reg flg, reg [7:0] out);
  initial begin flg = 0; st = IDLE; end
  localparam IDLE = 0, INI = 1, RUN = 2, FIN = 3;
  reg [7:0] st, sp, s[7], pc, c[13] = '{0,1,0,2,0,3,0,4,1,1,1,2,0};
  always @(posedge clk)
    if (rst) st <= INI; else
    case(st)
    INI: begin pc <= 0; sp <= 0; flg <= 0; st <= RUN; end
    RUN: case (c[pc])
         0: begin s[sp] <= c[pc+1]; sp <= sp+1; pc <= pc+2; end
         1: begin sp = sp-1; s[sp-1] <= s[sp]+s[sp-1]; pc <= pc+1; end
         2: begin out = s[sp-1]; flg = 1; st <= FIN; end
         endcase
    FIN: begin flg = 0; st <= IDLE; end
    endcase
endmodule
```

自分はいつもは関数型言語や論理型言語でプログラムを書いているのですが今回はステートマシンになるのでちょっと手惑いました。

clkがクロックで、01010101と繰り返し信号が変わるブール値です。always@(posedge clk)で1になった瞬間に処理を行います。
rstはリセット信号です。rstが1ならステートを初期状態に戻します。
initial begin ... end は初期化をします。
localparamはローカルな定数を決めます。C言語のenumのような用途に使います。
reg がレジスタを色々と宣言してまして8bitの状態変数とスタックポインタ,サイズ７のスタックsとプログラムカウンタpc、cがプログラムコードの入ったプログラムですね。

```
{0,1,0,2,0,3,0,4,1,1,1,2,0}
```

スタックに1,2,3,4を積んで加算を3回して終了するプログラムです。[1,2,3,4,+,+,+] = 4+3+2+1のようなプログラムですね。答えは10になるはず。

ステートがINIが初期化状態で、RUNが実行状態、FINが終了状態でIDLEがウェイト状態です。

### 5.2 トップモジュール

こちらが動かすためのトップのモジュールです:

```verilog:top.v
module top(input clk, s1, output reg [5:0] led, output uart_txp);
  `define INCLUDE
  `include "UartTx.v"
  `undef INCLUDE
  assign print_clk = clk;
  `define ln {8'd13,"\n"}
  `define p(a,s) begin `print(a,STR);led[0]<=0; if(print_state==PRINT_IDLE_STATE) begin st<=PWAIT; pwait_st<=s; end end
  localparam FREQ=27_000_000;

  reg [3:0] st,pwait_st;
  initial begin st = INI; rst1 = 1; end
  localparam INI = 0, WAIT = 1, RUN = 2, OUT = 3, FIN = 4, IDLE=5,PWAIT=6;
  wire flg; wire [7:0] result; reg rst1; reg [32:0] cnt;
  StackMachine vm(clk,rst1,flg,result);
  always @(posedge clk) begin
    led[0] = ~s1;
    if (s1) begin st <= INI; led[3:1]<= ~0; end else
    case (st)
    INI: begin st <= WAIT; cnt <= 0; led[3:2]<= ~0; led[1] <= 0; `p({"initialize",`ln},WAIT) end
    WAIT:if (cnt >= FREQ/2) begin st <= RUN; rst1 <= 1; end
         else cnt <= cnt+1;
    RUN: begin rst1 <= 0; if (flg) st <= OUT; end
    OUT: begin led[2] <= 0; `p({"out[",hexf(result),"]",`ln},FIN) end
    FIN: begin led[3] <= 0; `p({"ok",`ln},IDLE) end
    PWAIT: st<=pwait_st;
    endcase
  end
endmodule
```

最初の数行はUART通信するためのおまじないです。
ステートがINI,WAIT,RUN,OUT,FIN,PWAITとあって初期化状態から始まりinitializeと出力した後にWAIT状態に移行します。WAIT状態で0.5秒経つとスタックマシンにリセットをかけてRUN状態に移行します。
RUN状態では計算が終わるflgを見て終わったらOUT状態に移行します。
OUT状態では結果を１６進数で出力しFIN状態に移行します。
FIN状態ではokと出力してIDLE状態に移行します。
PWAIT状態は`pマクロで出力が終わるのを待ち次の状態に移行するためのものです。

スタックマシン本体よりもこちらの方が大きくなってしまいました。

### 5.3 UartTxモジュール

以下にUartを用いて出力するモジュールを示します:

```verilog:UartTx.v
`ifndef INCLUDE
module UartTx(input clk, [7:0] din,input wr_en, output tx_busy, reg tx_p);
  initial begin tx_p = 1; cnt = 0; st = IDLE; end
  parameter clk_freq = 27000000, uart_freq = 115200;
  localparam TX_CLK_MAX = clk_freq / uart_freq - 1;
  localparam IDLE = 0, START = 1, DATA = 2, STOP = 3;
  reg [7:0] din1, din2; reg wr_en1; reg [2:0] p; reg [1:0] st;
  reg [$clog2(TX_CLK_MAX+1)+1:0] cnt;
  wire tx; assign tx = cnt == 0;
  assign tx_busy = st != IDLE;
  always @(posedge clk) begin
    din1 <= din; wr_en1 <= wr_en;
    cnt <= cnt>=TX_CLK_MAX ? 0 : cnt+1;
    case (st)
    IDLE: if (wr_en1) begin st <= START; din2 <= din1; p <= 0; end
    START:if (tx) begin tx_p <= 0; st <= DATA; end
    DATA: if (tx) begin tx_p <= din2[p];
                        if (p==7) st <= STOP; else p <= p+1; end
    STOP: if (tx) begin tx_p <= 1; st <= IDLE; end
    endcase
  end
endmodule
`else
	parameter STR = 0;
	parameter HEX = 1;

	wire print_clk;

	reg[7:0] print_seq[255:0];
	reg[7:0] seq_head=8'd0;
	reg[7:0] seq_tail=8'd0;

	reg[1023:0] print_buffer=1024'h0;
	reg[6:0] print_buffer_pointer = 7'd0;

	reg last_spin_state=0;
	reg spin_state=0;
	reg[6:0] print_length;
	reg print_type;

	parameter PRINT_IDLE_STATE = 0;
	parameter PRINT_WAIT_STATE = 1;
	parameter PRINT_WORK_STATE = 2;
	parameter PRINT_CONV_STATE = 3;
	reg[1:0] print_state=PRINT_IDLE_STATE;

	wire[7:0] hex_lib[15:0];
	assign hex_lib[4'h0] = 8'h30;
	assign hex_lib[4'h1] = 8'h31;
	assign hex_lib[4'h2] = 8'h32;
	assign hex_lib[4'h3] = 8'h33;
	assign hex_lib[4'h4] = 8'h34;
	assign hex_lib[4'h5] = 8'h35;
	assign hex_lib[4'h6] = 8'h36;
	assign hex_lib[4'h7] = 8'h37;
	assign hex_lib[4'h8] = 8'h38;
	assign hex_lib[4'h9] = 8'h39;
	assign hex_lib[4'hA] = 8'h61;
	assign hex_lib[4'hB] = 8'h62;
	assign hex_lib[4'hC] = 8'h63;
	assign hex_lib[4'hD] = 8'h64;
	assign hex_lib[4'hE] = 8'h65;
	assign hex_lib[4'hF] = 8'h66;

	//always block to handle the print task
	always@(posedge print_clk)begin
		last_spin_state<=spin_state;

		case(print_state)
			PRINT_IDLE_STATE:begin//IDLE, check if spin_state is changed
				if(spin_state!=last_spin_state)begin
					print_state<=PRINT_WAIT_STATE;
				end
			end
			PRINT_WAIT_STATE:begin//WAIT, wait 1 clk then start to fill print_seq
				print_state<=PRINT_WORK_STATE;
				if(print_type==STR)
					print_buffer_pointer<=7'd127;
				else
					print_buffer_pointer<=7'd127;
			end
			PRINT_WORK_STATE:begin//WORK, fill print_seq
				if(print_type==STR)begin//type is string, fill as it is
					if(print_buffer[
						print_buffer_pointer*8+7 -: 8
					]!=8'd0)begin
						print_seq[seq_tail]<=print_buffer[
							print_buffer_pointer*8+7 -: 8
						];
						seq_tail<=seq_tail+8'd1;
					end else begin
						print_state<=PRINT_IDLE_STATE;
					end

					print_buffer_pointer<=print_buffer_pointer-7'd1;

					if(print_buffer_pointer==7'd0)begin
						print_state<=PRINT_IDLE_STATE;
					end
				end else begin //type is data, fill as hex
					print_seq[seq_tail]<=hex_lib[print_buffer[
						print_buffer_pointer*8+7 -: 4
					]];
					seq_tail<=seq_tail+8'd1;

					//another convert clock cycle is needed
					print_state<=PRINT_CONV_STATE;
				end
			end
			PRINT_CONV_STATE:begin//CONV, convert data to hex
				print_seq[seq_tail]<=hex_lib[print_buffer[
					print_buffer_pointer*8+3 -: 4
				]];
				seq_tail<=seq_tail+8'd1;
				print_state<=PRINT_WORK_STATE;

				print_buffer_pointer<=print_buffer_pointer-7'd1;

				if(print_buffer_pointer==print_length)
					print_state<=PRINT_IDLE_STATE;
			end
		endcase
	end

	reg uart_en;
	wire uart_bz;
	wire uart_txp;
	UartTx tx(print_clk, print_seq[seq_head], uart_en, uart_bz, uart_txp);

	//always block to send the data via UART
	always@(posedge print_clk)begin
		uart_en<=1'b0;
		if(uart_en && uart_bz)
			seq_head<=seq_head+8'd1;
		if(seq_head!=seq_tail && !uart_bz)
			uart_en<=1'b1;
	end

	task int_print(
		input[1023:0] strin,//max 128 characters
		input[7:0] type_length //8bit width to show 128 characters
	);
	begin
		if(print_state==PRINT_IDLE_STATE)begin//print when busy will be ignored
			spin_state<=~spin_state;

			if(type_length==STR)begin
				print_type<=STR;
			end else begin
				print_type<=HEX;
				print_length<=8'd128-type_length;
			end

			print_buffer<=strin;
		end
	end

	`define print(a,b) int_print({>>{a}},b)
	endtask
	function [15:0] hexf ([7:0] data);
		hexf = {hex_lib[data[7:4]],hex_lib[data[3:0]]};
	endfunction
`endif
```

こちらは拾ってきたものを書き換えて使いやすくした感じです。一番大きいですね。

### 5.4 CSTファイル

ハードウェアのピンとtopモジュールを紐付けるのが .cstファイルです:

```text:top.cst
IO_LOC "clk" 4;
IO_PORT "clk" PULL_MODE=UP;
IO_LOC "s1" 88;
IO_PORT "s1" PULL_MODE=NONE;
IO_LOC "uart_txp" 69;
IO_PORT "uart_txp" IO_TYPE=LVCMOS33 PULL_MODE=NONE;
IO_LOC "led[5]" 20;
IO_PORT "led[5]" PULL_MODE=UP DRIVE=8 IO_TYPE=LVCMOS33;
IO_LOC "led[4]" 19;
IO_PORT "led[4]" PULL_MODE=UP DRIVE=8 IO_TYPE=LVCMOS33;
IO_LOC "led[3]" 18;
IO_PORT "led[3]" PULL_MODE=UP DRIVE=8 IO_TYPE=LVCMOS33;
IO_LOC "led[2]" 17;
IO_PORT "led[2]" PULL_MODE=UP DRIVE=8 IO_TYPE=LVCMOS33;
IO_LOC "led[1]" 16;
IO_PORT "led[1]" PULL_MODE=UP DRIVE=8 IO_TYPE=LVCMOS33;
IO_LOC "led[0]" 15;
IO_PORT "led[0]" PULL_MODE=UP DRIVE=8 IO_TYPE=LVCMOS33;
```

### 5.5 ビルドスクリプト

tclファイルでビルド設定を書きビルドします:

```tcl:build.tcl
add_file -type verilog "src/UartTx.v" "src/StackMachine.v" "src/top.v"
add_file -type cst "src/top.cst"

set_device GW2AR-LV18QN88C8/I7 -device_version C
set_option -verilog_std sysv2017
set_option -top_module top
run all
```

### 5.6 Makefile

makeを使うとビルドが楽になります。

```make:Makefile
all:
	docker run --rm --platform linux/amd64 -v ./../../:/usr/local/share/gowin -v .:/home/dev -it gowin-docker:latest gw_sh build.tcl
	cat impl/pnr/project.rpt.txt | grep LUT
	openFPGALoader -f impl/pnr/project.fs
	cat impl/pnr/project.rpt.txt | grep LUT
	make p
d:
	openFPGALoader -f impl/pnr/project.fs
	cat impl/pnr/project.rpt.txt | grep LUT
	make p
p:
	python inp.py
r:
	screen /dev/tty.usbserial-20230306211 115200
clean:
	rm -rf impl
```

### 5.7 通信用Pythonファイル

こちらが通信用のpythonファイルです。Makefileから呼び出されます:

```inp.py
import serial

readSer = serial.Serial('/dev/tty.usbserial-20230306211',115200, timeout=3)
while True:
    string = readSer.read()
    print(f"{string.decode()}",end="")

readSer.close()
```

このような構成で実行しますと、最終的に以下のように計算結果であるout[0a]つまり10が出力されます:

```
python inp.py
initialize
out[0a]
ok
```

以下にmake実行時のログを載せておきます:

```bash
% make
docker run --rm --platform linux/amd64 -v ./../../:/usr/local/share/gowin -v .:/home/dev -it gowin-docker:latest gw_sh build.tcl
*** GOWIN Tcl Command Line Console  *** 
add new file: "src/UartTx.v"
add new file: "src/top.v"
add new file: "src/top.cst"
current device: GW2AR-18C  GW2AR-LV18QN88C8/I7
GowinSynthesis start
Running parser ...
Analyzing Verilog file '/home/dev/src/UartTx.v'
Analyzing Verilog file '/home/dev/src/top.v'
Analyzing included file '/home/dev/src/UartTx.v'("/home/dev/src/top.v":3)
WARN  (EX3628) : Redeclaration of ANSI port 'uart_txp' is not allowed("/home/dev/src/UartTx.v":127)
Back to file '/home/dev/src/top.v'("/home/dev/src/top.v":3)
Compiling module 'top'("/home/dev/src/top.v":1)
Extracting RAM for identifier 'print_seq'("/home/dev/src/UartTx.v":29)
Compiling module 'UartTx'("/home/dev/src/UartTx.v":2)
WARN  (EX3791) : Expression size 11 truncated to fit in target size 10("/home/dev/src/UartTx.v":13)
WARN  (EX3791) : Expression size 4 truncated to fit in target size 3("/home/dev/src/UartTx.v":18)
Compiling module 'StackMachine'("/home/dev/src/top.v":30)
Extracting RAM for identifier 's'("/home/dev/src/top.v":33)
Extracting RAM for identifier 'c'("/home/dev/src/top.v":33)
WARN  (EX3791) : Expression size 9 truncated to fit in target size 8("/home/dev/src/top.v":39)
WARN  (EX3791) : Expression size 9 truncated to fit in target size 8("/home/dev/src/top.v":39)
WARN  (EX3791) : Expression size 32 truncated to fit in target size 8("/home/dev/src/top.v":40)
WARN  (EX3791) : Expression size 9 truncated to fit in target size 8("/home/dev/src/top.v":40)
WARN  (EX1998) : Net 'print_length[6]' does not have a driver("/home/dev/src/UartTx.v":38)
NOTE  (EX0101) : Current top module is "top"
WARN  (EX0211) : The output port "led[5]" of module "top" has no driver, assigning undriven bits to Z, simulation mismatch possible("/home/dev/src/top.v":1)
WARN  (EX0211) : The output port "led[4]" of module "top" has no driver, assigning undriven bits to Z, simulation mismatch possible("/home/dev/src/top.v":1)
[5%] Running netlist conversion ...
Running device independent optimization ...
[10%] Optimizing Phase 0 completed
[15%] Optimizing Phase 1 completed
[25%] Optimizing Phase 2 completed
Running inference ...
[30%] Inferring Phase 0 completed
[40%] Inferring Phase 1 completed
[50%] Inferring Phase 2 completed
[55%] Inferring Phase 3 completed
Running technical mapping ...
[60%] Tech-Mapping Phase 0 completed
[65%] Tech-Mapping Phase 1 completed
[75%] Tech-Mapping Phase 2 completed
[80%] Tech-Mapping Phase 3 completed
[90%] Tech-Mapping Phase 4 completed
[95%] Generate netlist file "/home/dev/impl/gwsynthesis/project.vg" completed
[100%] Generate report file "/home/dev/impl/gwsynthesis/project_syn.rpt.html" completed
GowinSynthesis finish
Reading netlist file: "/home/dev/impl/gwsynthesis/project.vg"
Parsing netlist file "/home/dev/impl/gwsynthesis/project.vg" completed
Processing netlist completed
Reading constraint file: "/home/dev/src/top.cst"
Physical Constraint parsed completed
Running placement......
[10%] Placement Phase 0 completed
[20%] Placement Phase 1 completed
[30%] Placement Phase 2 completed
[50%] Placement Phase 3 completed
Running routing......
[60%] Routing Phase 0 completed
[70%] Routing Phase 1 completed
[80%] Routing Phase 2 completed
WARN  (PR1014) : Generic routing resource will be used to clock signal 'clk_d' by the specified constraint. And then it may lead to the excessive delay or skew
[90%] Routing Phase 3 completed
Running timing analysis......
[95%] Timing analysis completed
Placement and routing completed
Bitstream generation in progress......
Bitstream generation completed
Running power analysis......
[100%] Power analysis completed
Generate file "/home/dev/impl/pnr/project.power.html" completed
Generate file "/home/dev/impl/pnr/project.pin.html" completed
Generate file "/home/dev/impl/pnr/project.rpt.html" completed
Generate file "/home/dev/impl/pnr/project.rpt.txt" completed
Generate file "/home/dev/impl/pnr/project.tr.html" completed
Tue Dec  3 14:20:55 2024

cat impl/pnr/project.rpt.txt | grep LUT
    --LUT,ALU,ROM16           | 321(276 LUT, 45 ALU, 0 ROM16)
openFPGALoader -f impl/pnr/project.fs
empty
write to flash
No cable or board specified: using direct ft2232 interface
Jtag frequency : requested 6.00MHz   -> real 6.00MHz  
Parse file Parse impl/pnr/project.fs: 
Done
DONE
after program flash: displayReadReg 00006020
        Memory Erase
        Done Final
        Security Final
Erase SRAM DONE
Jtag probe limited to %d MHz6000000
Jtag frequency : requested 10.00MHz  -> real 6.00MHz  
Detected: Winbond W25Q64 128 sectors size: 64Mb
Detected: Winbond W25Q64 128 sectors size: 64Mb
RDSR : 00
WIP  : 0
WEL  : 0
BP   : 0
TB   : 0
SRWD : 0
00000000 00000000 00000000 00
Erasing: [==================================================] 100.00%
Done
Writing: [==================================================] 100.00%
Done
cat impl/pnr/project.rpt.txt | grep LUT
    --LUT,ALU,ROM16           | 321(276 LUT, 45 ALU, 0 ROM16)
make p
python inp.py
initialize
out[0a]
ok
```

## 6. まとめ

FPGA上で作ったスタックマシンが動くことを確認できました！
スタックマシンですが、一応、CPUを作ったことになるのではないでしょうか？CPUを作ったどー！

FPGAでLチカをした後にプログラミング言語実装勢がやりたいのはCPU作りでしょう。
しかしどうやってデバッグしたらいいのかがわからないかもしれません。
シリアル通信の出力をして受け取れればわざわざ画面出力をしなくても確認できます。

スタックマシンを作るのは言語を作り慣れていれば簡単に作れますが、標準出力のようなものがないしCPUもないので通信手段を用意して使い受け取るというようなOSの仕事を作って実装しないといけないところが大変なポイントでした。printマクロのようなものを使えばそれなりに綺麗に書くことができるようになると思います。

FPGAがない場合でもおすすめなのが 8bitworkshop です。特に開発環境もなくてもverilogのプログラミングを試すことができます。
verilatorを用いればローカル環境でC++のプログラムとして実行してシミュレーションすることもできますので試してみるといいかもしれません。