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

## TL;DR

[C++でBrainf\*\*kのx64のELFコンパイラを作った](https://paiza.io/projects/eiLeDU9Gm7b-1qBS4FQ48A "Online PHP/Java/C++... editor and compiler | paiza.IO")．

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

- [x86のELFコンパイラ](https://paiza.io/projects/y93G2ZUw2S7U1ICcvT0Z4g "Online PHP/Java/C++... editor and compiler | paiza.IO")
- [x64のexeコンパイラ](https://godbolt.org/z/PN_GXq "Compiler Explorer")
- [x86のexeコンパイラ](https://godbolt.org/z/Jp4w2r "Compiler Explorer")

GitHubに[すべてまとめて置いてある](https://github.com/koturn/bfcompiler "koturn/bfcompiler")．


## 元ネタ

[ヤッター！paiza.ioでコンパイラできたよー！＼(^o^)／](https://qiita.com/kazatsuyu/items/bfbc78821699775aff9c "ヤッター！paiza.ioでコンパイラできたよー！＼(^o^)／")


## 元ネタの元ネタ

[この記事](https://megalodon.jp/2020-0526-1521-16/https://agency-star.co.jp:443/column/+compiler "【魚拓】コンパイラとは？構造や自作方法，おすすめのコンバイラの選び方を解説！インタプリタやアセンブラとの違いとは？ | A-STAR（エースター）")


## 前置き

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

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


## 作ったやつ

[これ](https://paiza.io/projects/eiLeDU9Gm7b-1qBS4FQ48A "Online PHP/Java/C++... editor and compiler | paiza.IO")です．

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` <br> `mov edi, edx` <br> `syscall`
`,`                   | `xor eax, eax` <br> `xor edi, edi` <br> `syscall`
`[`                   | `cmp byte ptr [rsi], dh` <br> `je {オフセット}`
`]`                   | `jmp {オフセット}`
開始                  | `movabs rsi, {.bssのアドレス}` <br> `mov edx, 0x01`
終了                  | `mov eax, 0x3c` <br> `xor edi, edi` <br> `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プログラミング](https://www.slideshare.net/KMC_JP/brainfck "実用Brainf*ckプログラミング")に書かれている `[>+<-]` のような値の移動，`[>+>+<<-]>>[<<+>>-]` のような値のコピー， `[>+++++,-]` のような定数倍， `[>[>+>+<<-]>>[<<+>>-]<<<-]` のような掛け算をいい感じの命令に置き換える必要があると思います．


## 与太話

x86のELFコンパイラも32bit用のELFヘッダに置き換え，機械語をx86のものにすることで[簡単に作成することができます](https://paiza.io/projects/y93G2ZUw2S7U1ICcvT0Z4g "Online PHP/Java/C++... editor and compiler | paiza.IO")．

また，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](https://gist.github.com/7shi/531154 "kbfc.cpp")


## おまけ

- [x86のexeコンパイラ](https://godbolt.org/z/Jp4w2r "Compiler Explorer")
- [x64のexeコンパイラ](https://godbolt.org/z/PN_GXq "Compiler Explorer")

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

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