Brainfuck CPUをマイクロプログラム方式で実装したお話

1.概要

論理回路シミュレータのlogisimを使って，Brainfuckのコードをそのまま(?)実行可能なCPUをマイクロプログラム方式で作ってみました．

この記事ではその成果，作り方，仕様を簡単に説明しますが，僕はCPUの勉強を始めたところなので，細かい内容については保証できません．

作ったlogisimのファイルとか，命令セットとかを書いた秘伝のエクセルシートとかはここに投げておきます．

2.とりあえず成果

興味本位で見に来たという方がほとんどだと思うので，説明はともかくとりあえず動作している様子はこんな感じです．

左上にあるのがROMで，Brainfuckの命令を書き込みます．その下にあるやつがマイクロプログラムが書き込まれたROMです．

デコーダ上ではBrainfuckの命令とマイクロコードを読み取っていい感じにBrainfuckのプログラムを実行しています．

今回はlogisimに搭載されているキーボードやディスプレイを使えるようにしているので，入出力がちゃんとできるようになっています．上のGIFではどっかから引っ張ってきたHello Worldのコードを実行していますが右下のディスプレイにちゃんと「Hello World!」が表示されています．

3.実装方法(マイクロコード編)

このCPUのキモはBrainfuckのコードが～という下りよりも，CPUの命令の制御にマイクロプログラムを用いているという点です．この制御方式はマイクロプログラム方式とよばれていて，1つの命令をより単純な命令群に置き換えるというものです．

マイクロプログラム方式の詳しい話はWikipediaをみるか，CPU関係で有名な本である『コンピュータの構成と設計　第二版　上』を読むといいと思います(最新版では省略されているかもしれないです)．

先に少し触れましたが，マイクロプログラム方式ではCPUの命令をより単純な命令群で置き換えるというものです．

まもな高級言語がなくアセンブラ言語でガリガリ書いていた時代では，より高度な命令をCPUに組み込ませるという考え方(CISC)が流行っていたようで，その考えのもとで作られたCPUではマイクロプログラム方式がよく用いられてきたようです．

今ではあまり使われていない方式のようですが，この方式を用いれば複雑な命令を実行できるので，Brainfuckを実行するCPUを作るのはお茶の子さいさいというわけです．

このCPUではBrainfuckの命令(+-,.><[])それぞれを次のようなマイクロプログラムで動かしています．エクセルシートもあげてありますので気になる方はそっちを見てください．

一番面倒なループ命令（"""["""と"""]""")は，Cレジスタで括弧の数を数えることで対応する括弧のところまでジャンプしています．それ以外はわりと単純な命令なのでほとんどそのままとなっています．

このマイクロプログラムからデコーダが適切な信号を出力します．

4.デコーダ

デコーダは割りと雑な感じになっていますがこんな感じです．雑に説明を入れておきました（あとで僕が見る用なので）

まだ数回しかCPUを作ってないですがデコーダだけはなんともなんないですね……ただ今回はCPUの勉強をある程度進めたお陰で割りとすんなり作れました．ちなみにこのCPUを作るのに6時間かかっているか，いないかぐらいです．

先程見せたマイクロプログラムの命令（マイクロ命令）から，適切な信号を出力するような回路となっているはずです．
マイクロ命令から出力される信号はこんな感じです．

XXXXという命令は，Brainfuckの命令から対応するマイクロプログラムの番地へジャンプする命令です．それ以外のマイクロ命令は大体普通のCPUとおんなじ感じになってます．

5.コンパイラ

コンパイラと言っても対応する数字を出力するだけのプログラムです．余分なincludeとかありますが無視してください．出力されたファイルはlogisimでROMデータに書き込むことができます．

	#include <iostream>
	#include <queue>
	#include <vector>
	#include <algorithm>
	#include <map>
	#include <string>
	#include <cstdio>
	#include <cstdlib>
	#include <ctime>
	#ifndef _USEFUL_MACROS_
	#define _USEFUL_MACROS_
	#define INF 99999999
	#define FOR(i,a,b) for (int i=(a);i<(b);i++)
	#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
	#define REP(i,n) for (int i=0;i<(n);i++)
	#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
	#endif
	using namespace std;
	int main(int argv,char *argc[]){
	FILE *src;
	FILE *output;
	char c;
	if( argv <= 2 ){
	cout << "Error: no input file." << endl;
	cout << "usage: ./bfc code.txt out.txt" << endl;
	return 0;
	}
	src = fopen(argc[1],"r");
	if( src == NULL ){
	cout << "File \"" << argc[1] << "\" not foud." << endl;
	return 0;
	}
	output = fopen(argc[2],"w");
	if( output == NULL ){
	cout << "File \"" << argc[2] << "\" not foud." << endl;
	return 0;
	}
	fprintf(output,"v2.0 raw\n");
	while( (c=fgetc(src)) != EOF ){
	int n = -1;
	char codes[9] = "><+-.,[]";
	REP(i,8)
	if( codes[i] == c )
	n = i;
	if( n != -1 ){
	fprintf(output,"%d ",n);
	}
	}
	fclose(src);
	fclose(output);
	return 0;
	}

view raw bfcpu_compiler.cpp hosted with ❤ by GitHub

logisimではROMにデータを書き込むときにはｋのよくわからないファイルフォーマットのファイルからデータを読み取れるようになっているのでそれを使うとハンドアセンブルしなくて済みます．

6.感想とか

この間『コンピュータの構成と設計　第二版　上』を読了しまして，その時にないがしろになっていた桁上げ先見加算器とマイクロプログラム方式について一応手を動かして作ってみた感じです．

もともと大学のレポートで自由課題として提出する用に作っていたのですが，Brainfuckの方は間に合わなかったのでブログに書いて供養させた感じです．

なるべく早く下巻を読み終えてパイプライン処理のmipsを実装したらFPGAに手を出していきたい所存です……