ChiselでBF処理系を作る(1)

BFに対する理解とアーキテクチャについて

前回まででChiselを使った開発フローについて理解したが、実際になにか作ってみることにする。

今回はBrainf**kという言語(以後BFと略する)の処理系をChiselを使って実装してみようと思う。

お題の理由としては以下となる。

• (当初考えていた)オレオレCPUを作るなら、Chiselの理解度が高い状態で臨みたい
• 命令数が少なく、また単純なので難易度設定として適切
• BF処理系を作るのは楽しい

完成物

kamiyaowl/arty-chisel-brainfxxk - Github

参照ドキュメント

今回の開発にあたって、以下ページを何度も読み返している。特に英語ができない私にとっては日本語情報は本当にありがたかった。改めて感謝を。

• Github Chisel3 wiki
• FPGA開発日記
• ハードウェアの気になるあれこれ

BFについて

まずはBF言語について簡単に説明しておく。

構成

BFプログラムと、現在実行している命令のポインタ、30000個の要素を持つuint8_tの配列、配列のどのデータを操作するかを示すポインタの4要素である。

命令セット

以下の8種類のみ使用できる

• + 現在参照しているデータをインクリメント
• - 現在参照しているデータをデクリメント
• > データ参照ポインタをインクリメント
• < データ参照ポインタをデクリメント
• , 外部入力を現在参照しているデータに上書き
• . 現在参照しているデータを外部出力
• [ 現在参照しているデータが0なら、対応する]に命令ポインタを移動
• ] 対応する[に命令ポインタを移動

コード例

これを利用するとHello world!は以下のようなプログラムになる

">+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++."

一見複雑そうに見えるがからくりはこうである。例えば最初のHを出力する箇所を確認する。

>+++++++++[<++++++++>-]<.

• >+++++++++ → mem[1] += 9
• [<++++++++>-] → mem[0] += 8, mem[1] -= 1 (mem[1] > 0の間繰り返し)
• <. → put(mem[0])

となっている。c言語に書き下すならこうだ

int mem[30000];
int ptr = 0;

ptr++;
mem[ptr] = 9; // ptr == 1

while(mem[ptr]) { // ptr == 1

    ptr--;
    mem[ptr] += 8; // ptr == 0

    ptr++
}
ptr--;
put(mem[ptr]); // ptr == 0, mem[0] == 72('H')

処理系実装

上記の例にもあるようにかなり簡単に実装できるので、まずは理解を深めるためにも自分の得意な言語で処理系を実装することを推奨する。 最初からHDL実装をしようとすると、意外と理論から実装に落とすフェーズに勘違いがあったりして躓くことがしばしあるからだ。

参考までにc++で実装したので、以下に貼っておく。 brainfxxk.cpp - Gist

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <stdint.h>

using namespace std;

int main() {
	vector<uint8_t> mem(30000,0);
	stack<int> branchStack;
	string src;

	cin >> src;

	int ptr = 0;
	int pc = 0;
	for(pc = 0; pc < src.length() ; ++pc) {
		switch(src[pc]) {
			case '+':
				mem[ptr]++;
				break;
			case '-':
				mem[ptr]--;
				break;
			case '>':
				ptr++;
				break;
			case '<':
				ptr--;
				break;
			case ',':
				cin >> mem[ptr];
				break;
			case '.':
				cout << (char)mem[ptr];
				break;
			case '[':
				if (mem[ptr]) {
					branchStack.push(pc - 1);
				} else {
					for(int nest = 1 ; nest > 0 && pc < src.length() - 1 ; ++pc) {
						switch(src[pc + 1]) {
							case '[':
								nest++;
								break;
							case ']':
								nest--;
								break;
						}
					}
				}
				break;
			case ']':
				pc = branchStack.top();
				branchStack.pop();
				break;
		}
	}
	return 0;
}

方式検討

ここまででBFの実装については理解できたと思うので、いよいよHDLに起こすことを検討する。 今回は手元にArty A7があったので、これにポーティングできることをとりあえず目標とする。

構成

お風呂に入りながら考えたが、stdin/outがあるのが面倒なので途中にFIFOをもたせるようなインターフェースがいいだろうと考えた。

簡単に説明しておく

• PCとのやり取りはすべてUartを経由する
• ProcessorをUartと直結してしまうと（当然だが）Uartの転送が終わるまで動けなくなるのでFIFOを設ける
• BFのプログラムを格納するメモリはBF_Processor内部に持たせる(結構悩んだ)
• プログラム転送モードと実行モードの切替は、オンボードのスライドスイッチを使う
• スライドスイッチ入力はチャタリング対策を施す
• クロックはシステムクロック１つのみとし非同期パスは作らない
• 周波数は目標100MHzとする

まとめ

記事のきりが良いのでここで区切るが、次回からは実装が簡単だった順番に紹介しようと思う。実際はProcessorから作っていったが…。

次回 - ChiselでBF処理系を作る(2)