paiza.ioでコンパイラを作る

TL;DR

C++でBrainf**kのx64のELFコンパイラを作った．

ついでに下記3つのBrainfuckコンパイラも作った．

• x86のELFコンパイラ
• x64のexeコンパイラ
• x86のexeコンパイラ

GitHubにすべてまとめて置いてある．

元ネタ

ヤッター！paiza.ioでコンパイラできたよー！＼(^o^)／

元ネタの元ネタ

この記事

前置き

元ネタの記事ではRustを使用して，Brainf**kからRustに変換し，それをrustcに通すというコンパイラを作っていました．
なので，Brainf**kからx64のELFを直接吐くコンパイラを作ってみました．

ELFファイルを作るには，本体の機械語の前後に適当なヘッダやフッタをつける必要があり，ちょっと面倒なのですが，C言語またはC++においては <elf.h> というヘッダ等の構造体が定義されているヘッダファイルが利用できるので（gccとかじゃないとダメだけど），これを利用すれば簡単にELFファイルを作ることができるわけです．

作ったやつ

これです．

Brainfuckの仕様としてはオーソドックスなものである1セル1byte，65536セル（30000セルでいいけど，キリ良く65536にした）を採用しています．

解説

プログラム中のコメントがそのまま解説になっているので，必要はないですが，一応...．

生成するELFファイルはlibc等の標準ライブラリと一切リンクせず，IOと終了には全てシステムコールを使います（手抜き）．
Brainf**kのポインタとして使用しているレジスタは rsi にしています．
これはそのままwriteシステムコール，readの引数に用いることができるためです（後述）．

プログラムコード本体はBrainf**kの命令 ><+-.,[] また，開始部分と終了部分に応じて，次のアセンブリコードに応じた機械語を生成するだけです．

Brainf**k命令，箇所	アセンブリコード
>	inc rsi
<	dec rsi
+	inc byte ptr [rsi]
-	dec byte ptr [rsi]
.	mov eax, edx mov edi, edx syscall
,	xor eax, eax xor edi, edi syscall
[	cmp byte ptr [rsi], dh je {オフセット}
]	jmp {オフセット}
開始	movabs rsi, {.bssのアドレス} mov edx, 0x01
終了	mov eax, 0x3c xor edi, edi syscall

終了箇所でやっているのはexitシステムコールの呼出です．
これが無ければプログラムが終了せず，暴走します．
main関数が無いので，自分でexitシステムコールの呼出が必要になるわけですね．

開始位置で edx に 0x01 を代入しているのは，edxはシステムコールの第3引数に対応しており，この値をreadシステムコールとwriteシステムコールで共用できるためです．

このDレジスタに入った 0x01 という値を，そのまま . のコード生成，つまりwriteシステムコールの番号のセットと第一引数のセットに利用することと，下から2byte目が 0 であることを利用し，ジャンプ命令前の0比較部分で利用することによって，命令長を削減しています．

上記の表に加えて，連続する ><+- を加算，減算命令にまとめる，Brainf**kの頻出イディオムである [-] （[+]）をゼロ代入命令にすることで，それなりの高速化が図れます．

Brainf**k命令，箇所	アセンブリコード
>（2個以上連続）	add rsi, {連続数}
<（2個以上連続）	sub rsi, {連続数}
+（2個以上連続）	add byte ptr [rsi], {連続数 % 256}
-（2個以上連続）	sub byte ptr [rsi], {連続数 % 256}
[-]	mov byte ptr [rsi], dh

ただし，ジャンプのオフセットにしてもそうなんですが，加算減算には-128～127の値を加えるとき，オペランドが1byteの命令を利用することが可能です．
別にこれをやらず，常にオペランドが4byteの命令を使ったところで速度的に差が出ることは無いと思いますが，ファイルサイズを小さくすることができるという利点があります．
（実際のアセンブラにおいても，アセンブリコード上では同じ add rsi, {数値} であっても，{数値} の値によって生成する機械語が変わります）

こうしてできたプログラムコード本体に適当なヘッダとフッタを付けてやることで，実行可能なELFファイルが完成します．
libc等は一切使用していない実行ファイルであるため，ポータビリティは高いです（？）

参考：x64におけるread，write，exitシステムコール

x64におけるシステムコールでは，各レジスタが以下の役割を果たします．
今回利用するのは第三引数までなので，そこまでのみ示します．

レジスタ	役割
rax	システムコール番号
rdi	システムコールの第1引数
rsi	システムコールの第2引数
rdx	システムコールの第3引数

また，x64におけるread，write，exitシステムコールの番号，引数の数はそれぞれ以下の通りです．
（x86だとシステムコールの番号はまた異なっています）

システムコール	番号	番号（16進数）	引数の数
read	0	0x00	3
write	1	0x01	3
exit	60	0x3c	1

readシステムコール

read システムコールのC言語APIは以下の通りです．

ssize_t read(int fd, void *buf, size_t count)

引数	対応するレジスタ	役割	Brainf**kコンパイラ中で設定する値
fd	rdi	ファイルディスクリプタ	0 (stdin)
buf	rsi	入力先へのポインタ	Brainf**kのポインタそのまま
count	rdx	読込文字数	1 (getcharの代わりの1文字取得であるため)

writeシステムコール

write システムコールのC言語APIは以下の通りです．

ssize_t write(int fd, const void *buf, size_t count)

引数	対応するレジスタ	役割	Brainf**kコンパイラ中で設定する値
fd	rdi	ファイルディスクリプタ	1 (stdout)
buf	rsi	出力データへのポインタ	Brainf**kのポインタそのまま
count	rdx	出力文字数	1 (putcharの代わりの1文字出力であるため)

exitシステムコール

exit システムコールのC言語APIは以下の通りです．

void exit(int status)

引数	対応するレジスタ	役割	Brainf**kコンパイラ中で設定する値
status	rdi	終了ステータス	0 (正常終了)

最適化

Brainf**kを何かの言語にトランスパイルし，その言語のコンパイラの最適化に任せて実行ファイルを生成する形式ではなく，直接実行ファイルを生成しているので，生成した機械語がそのまま性能に影響します．
なので，最適化を行うことが重要になります．

面倒だったので，今回は連続する ><+- をまとめる， [-] （[+]）をゼロ代入にする以外の最適化は行っていません．

また，1文字出力の度にwriteシステムコールの呼び出しを行っているのでナンセンスです．
適切に出力バッファリングを行うようにするべきでしょう．

他にも，今回のようなシステムコールを利用した入出力を行うバイナリを吐くコンパイラならではになりますが，入力 , が無いBrainfuckプログラムは少なくない（例えばHello Worldのプログラムやマンデルブロ集合を描画するプログラム）のを踏まえ，, が無いBrainf**kプログラムの場合，プログラムの先頭で，rdiに 1 を入れておけば，write システムコールの呼び出しの度に，第一引数（rdi）をセットする必要が無くなります（システムコールの戻り値はraxに入りますが，1文字出力なので基本的には 1 のままであることが期待できるため，raxについても同様のことを行ってもよいかもしれません）．

本当にちゃんとしたBrainf**kのELFコンパイラを作るのであれば，実用Brainf*ckプログラミングに書かれている [>+<-] のような値の移動，[>+>+<<-]>>[<<+>>-] のような値のコピー， [>+++++,-] のような定数倍， [>[>+>+<<-]>>[<<+>>-]<<<-] のような掛け算をいい感じの命令に置き換える必要があると思います．

与太話

x86のELFコンパイラも32bit用のELFヘッダに置き換え，機械語をx86のものにすることで簡単に作成することができます．

また，Windowsのexeファイル（x86，x64両方とも）も同様に，適当なプログラム本体の機械語を生成し，適当なヘッダを付与することで作成することができます．
適当なヘッダ等の構造体（IMAGE_DOS_HEADER，IMAGE_OPTIONAL_HEADER32 / IMAGE_OPTIONAL_HEADER64，IMAGE_SECTION_HEADER，IMAGE_IMPORT_DESCRIPTOR，IMAGE_THUNK_DATA32 / IMAGE_THUNK_DATA64）は windows.h 内（でさらにインクルードしているヘッダファイル）で定義されているので，C言語，C++であれば簡単に実装することができるというわけです（MSVC，またはCygwin，MinGW，msys2におけるC++コンパイラに限りますが）．

Windowsでは，システムコールを直接的に使うことはできないので（多分），msvcrt.dll とリンクし，putchar，getchar，exit を呼び出すようにする必要があります．
また，ファイルサイズやプログラムコード本体位置のアラインメントに気を付ける必要があるなど，ELFファイルよりは作るのが面倒な感じです．

x86 exeのBrainf**kコンパイラの実装例が以下に記載されていますが，最近のWindowsだと終了時に ret 命令を実行するのではなく，exit 関数を呼び出すようにしないと，20秒ぐらい謎の終了までの待ち時間が発生することがあります．

• kbfc.cpp

おまけ

• x86のexeコンパイラ
• x64のexeコンパイラ

MSVCのコードを実行でき，かつファイル作成も可能なオンラインコンパイラサービスが見つからなかったので，とりあえずCompiler Explorerで紹介しています．
Windowsをお持ちの方はお手元の環境でコンパイルし，実行してみてください．

ただし，ウィルス対策ソフトやWindows Defenderによって，出力するexeファイルの実行がブロックされ，削除される可能性もあります．