Goコンパイラをゼロから作って147日でセルフホストを達成した

Go言語コンパイラをスクラッチから書いてセルフホストを達成しました。

https://github.com/DQNEO/minigo

本家Goコンパイラの実装はほとんど見ずに、ほぼ 8cc というCコンパイラから学んだ知識のみで作りました。


# 特徴
* コンパイルするとアセンブリを吐きます
* 字句解析・構文解析は手書きです。yacc/lex などのツールは使っていません
* 標準ライブラリも自作です

コード行数はテストをのぞくと 9,152行でした。

セルフホストに必要な機能しかないので、Go言語の全機能は網羅していません。
例えば以下の機能は未実装です。

* ガベージコレクション
* go routineとchannel
* 浮動小数点

# 設計

70%くらいは 8cc の設計をそのまま引き継いでいます。
残り25%(map,slice,interface,method,型推論等)が自分のオリジナル、残り5%が9cc、くらいな感じです。


# かかった期間

2018/10/7に着手して2019/5/17にセルフホスト達成。
仕事やプライベートが忙しくて中断してた時期もあったので、毎日やってたわけではないです。
コミットした日を数えたら147日でした。

```
$ git log --pretty=format:%cd --date=short | sort | uniq | wc -l                                                                       
147
```

1日あたり3-4時間くらいやってので、合計 500 時間くらい。

期間はあまり重要ではなくて、スクラッチからGoコンパイラを書いてセルフホスト達成というのは前例を聞いたことがないので、達成したこと自体がよかったなと思います。


# 最初のコミット

記念すべき最初のコミットはこれです。

https://github.com/DQNEO/minigo/commit/35252406a228a262e3b3b50b3c1b6b5fc6fb033c


```a.s
	.globl	main
main:
	movl	$0, %eax
	ret
```

もはやただのアセンブリコードで、コンパイラどころかGo言語の影も形もありません。ここから機能を付け足してGoコンパイラに育て上げました。

興味深いことに、7コミット目あたりですでにコンパイラ全体の骨格ができています。

https://github.com/DQNEO/minigo/commit/454fc2f4ad6669fc45c56e988599293e3f530976



# なんで作ろうと思ったの

もともとGoコンパイラを作るなどという発想は1㍉もなかったです。

当時、仕事でGoを触る機会はあったものの、週1-2回くらいしか触らないのでなかなか上達しないという焦りを抱えていまいた。
そんなとき Rebuildfm で ruiさんが8ccを作った話を聞いてすごく興味を持ちました。

[Rebuild: 153: Connecting The Dots (rui314)](http://rebuild.fm/153/)

さっそく git clone して1コミット目から読んでみたら自分でもやりたくなって、
Go言語に移植してみようと思いました。

https://github.com/DQNEO/8cc.go

1コミット目から順番に、Cで写経してからGoに移植しました。
これがすごく面白くて6ヶ月ほどかけて93コミット目まで移植しました。
この過程でコンパイラ作りに必要な知識が身につきました。

8cc は自分のようなコンパイラ素人でもギリギリ理解できる程度にわかりやすかったです。ただ、トークンストリームの実装はやや複雑[^2]で、もうちょっとよい方法はないものかと思っていたところ、後継の 9cc が登場して、そのあたりがすごくきれいに設計されていたので、自分でもトークナイザーを書いてみたい衝動に駆られました。
それで試しにGoコンパイラを書いてみたらコアの部分があっさり動いたので、そのままGoコンパイラ開発に突入したという流れです。

[^2]: トークナイザーとプリプロセッサがやや密結合していた

# 大まかな進行

基本的には 8ccにならって、各ステージを少しずつ作り上げていくスタイルの開発をしました。
つまりある小さい機能を実装するたびに、テスト追加 → 字句解析 → 構文解析 → コード生成 と各コンポーネントを少しずつ育てていくやり方です。

ただ自分の場合、コンポーネントを頻繁にまたぐと脳のコンテキストスイッチの負担が大きいので、同じカテゴリのタスクはまとめてやる、つまり字句解析をやるときは字句解析ばっかり集中的にやる、構文解析をやるときは構文解析を一気に作る、というウォーターフォール的なやり方もとりいれました。

この戦略はわりとうまく行ったと思います。[^3]
字句解析はかなり早い段階でできあがり、構文解析もその後すぐ完成したので、後半はコード生成に集中することができました。

[^3]: 自分にとって2回目のコンパイラ作りだったから、というのもある。

## 前半戦

前半は自分でもびっくりするくらい順調でした。

### 1日目: 足し算が動いた

<blockquote class="twitter-tweet" data-lang="en"><p lang="ja" dir="ltr">GolanによるGo Compiler 作り始めてみました。150行くらい書いたら足し算が動くようになった。<a href="https://t.co/VLO2Gvnrw1">https://t.co/VLO2Gvnrw1</a><br>設計は8ccをほぼ踏襲しつつ、9ccの知見を一部取り込んでいます。</p>&mdash; ドキュネオ (@DQNEO) <a href="https://twitter.com/DQNEO/status/1048774803895672832?ref_src=twsrc%5Etfw">October 7, 2018</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

(しょっぱなでGolanなどとtypoしていますが正式名称は "The Go Programming Language" です)


### 2日目: 引き算・掛け算・関数呼び出し、hello world文が動いた

<blockquote class="twitter-tweet" data-lang="en"><p lang="ja" dir="ltr">早くも関数呼び出しができるようになった!<br>そして hello worldが動いた!!<br>たった1日でここまでいけるとは、自分でもびっくりw <a href="https://t.co/o45cBydtHn">pic.twitter.com/o45cBydtHn</a></p>&mdash; ドキュネオ (@DQNEO) <a href="https://twitter.com/DQNEO/status/1048968936610357248?ref_src=twsrc%5Etfw">October 7, 2018</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>


### 5日目: hello_world.go が動いた


<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="ja" dir="ltr">自作Goコンパイラで hello world 完全版うごいたー <a href="https://t.co/hUDcBNWbCS">pic.twitter.com/hUDcBNWbCS</a></p>&mdash; ドキュネオ (@DQNEO) <a href="https://twitter.com/DQNEO/status/1050039473222737921?ref_src=twsrc%5Etfw">October 10, 2018</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>


### 1ヶ月: FizzBuzzが動いた

<blockquote class="twitter-tweet" data-lang="en"><p lang="ja" dir="ltr">Goコンパイラを作り始めて1ヶ月で FizzBuzz がコンパイルできるようなりました <a href="https://t.co/vi6YXPnjw9">pic.twitter.com/vi6YXPnjw9</a></p>&mdash; ドキュネオ (@DQNEO) <a href="https://twitter.com/DQNEO/status/1060189760159764481?ref_src=twsrc%5Etfw">November 7, 2018</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

8ccの写経時に CでCコンパイラを書いてたのと比べると、4倍くらい速く進んだ気がします。
これには理由があって、


* Goをコンパイル対象としてみたとき、文法そのものがパーサに優しい仕様になっているので楽。(例：行頭の `func`,`type`,`var`等一単語を読んだだけで構文の種類が決まる)
* Goをコンパイラを書く道具としてみたとき、最初から slice,map, for rangeが使えるので楽。

対象が簡単＆道具が強力というのが掛け算で効いて、すごいスピードで進みました。
4倍高速に進捗すると、どんどん面白くなってやみつきになります。
当時、「GoでGoコンパイラを書くと4倍速で書ける。楽しすぎてヤバイ」と豪語していました。

(あとでこの自尊心はへし折られるわけですが)

### 識別子解決問題

最初のつまづき。
Cコンパイラ脳でGoコンパイラを書いていたので、識別子の解決がうまくいかないという問題にぶち当たりました。

Go言語では、下記のように下で宣言されたもの (この例では変数 `i` ) を上で使うということができます。

```go
package main

func main() {
	println(i)
}

var i int = 123
```

これはC言語と根本的に違うところです。
C言語ではこのようなコードはコンパイルエラーになります。

```c
#include <stdio.h>

int main() {
    printf("%d\n", i);
}

int i = 123;
```

```
 error: use of undeclared identifier 'i'
    printf("%d\n", i);
```

自分は当初Cコンパイラと同じ発想で上から読んでいって名前表を構築しつつ探索する方式をとっていたので 、このケースをパースできないことに気づきました。
また、そもそも `int` の正体が何であるかはパッケージ内の全ファイルをパースするまでは確定できないので、`var i int`の型宣言をパースした時点では型が確定できないという問題が起こります。


うんうん頭を捻りながら解決策を考えてみたものの、どうやって動くものが作れず、やむを得ずGo本体の実装を見たら、この問題がすごくエレガントに解決されていて感動しました。
ここはGo本体のロジックを借用して解決しました。

(余談ながら、Go本体のパーサの実装をはじめてみたとき、自分が今まで手書きしてきたパーサと似てる部分がたくさんあって感動しました)

### 組み合わせ爆発との戦い

Goにはいろいろな種類の式があり、右辺や左辺に登場します。

```
variable
array[3]
slice[1]
strct.field
obj.method()
```

そして式が返す型にもまた多数の種類(int,配列,スライス、構造体、ポインタ等)があります。
加えて、グローバル変数/ローカル変数という区分もあります。
自分のコンパイラの場合、この `式の種類` x `型の種類` x `グローバルorローカル` の掛け算が組み合わせ爆発になってしまい、それぞれのケースに対してコードを書かなければならない事態に陥りました。

たぶん設計に問題があったのだろうけど、組み合わせ爆発を回避する方法がわからなかったので組み合わせ爆発したまま力技で全ケース実装しました。

ここを乗り越えたら、自作コンパイラで自分自身をパーズできるようになりました。


<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="ja" dir="ltr">つ、ついに・・・！<br>自作Goコンパイラに自分自身を構文解析させてエラーなしで完走するとこまでできた！！<br>表面的な構文解析はこれで完成したことになる。<br>セルフホスト達成の夢が見えてきたー 😂<a href="https://twitter.com/hashtag/minigo?src=hash&amp;ref_src=twsrc%5Etfw">#minigo</a> <a href="https://t.co/dQdk5xwNgY">pic.twitter.com/dQdk5xwNgY</a></p>&mdash; ドキュネオ (@DQNEO) <a href="https://twitter.com/DQNEO/status/1082255334230581248?ref_src=twsrc%5Etfw">January 7, 2019</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>


ここまでで 3ヶ月くらい。

## 後半戦

つらかった

### "Segmentation Fault"の嵐

自作コンパイラで自分自身をコンパイルすると第二世代コンパイラが得られます。この中身は第一世代コンパイラが吐いた雑なアセンブリプログラムの塊なわけですが、これが動かしてみるとバグだらけ。
ひたすら Segmentation Fault で落ちる。

gdbを起動してステップ実行しながら原因特定して、修正して、実行すると別の"Segmentation Fault"で落ちる。

<blockquote class="twitter-tweet" data-lang="en"><p lang="ja" dir="ltr">次にmap setでもセグフォ起きてて、これもgdbの力で解決した。<br>セグフォ直後のレジスタの状態をこういう風に表示して、値をよーく見たら原因わかった。(この例ではr10をメモリアドレスとしてアクセスしようとしててセグフォ。)<br>gdbすごい！ <a href="https://t.co/ol8KaChBmc">pic.twitter.com/ol8KaChBmc</a></p>&mdash; ドキュネオ (@DQNEO) <a href="https://twitter.com/DQNEO/status/1089924260150169600?ref_src=twsrc%5Etfw">January 28, 2019</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>


毎日毎日 Segmentation Fault をつぶしていく地道な作業でした。

ほとんどの原因は、第一世代コンパイラで実装したはずの機能の実装漏れやテストもれです。
前半で雑につくっていた部分が一斉にこのフェーズで実行時エラーとなってあらわれる。

「第２世代コンパイラで発生する"Segmentation Fault"を治す方法」というのは、そんな書籍があるはずもなくWeb上にもほとんど事例が出てこない [^4] ので孤独な戦いでした。

[^4]: このへんに少し事例があります。 https://speakerdeck.com/anqou/seccamp2018deseruhuhosutockonpairawotukututa ,  http://0x19f.hatenablog.com/entry/2018/08/20/200432

毎日1-2個の"Segmentation Fault"を治すというのを2ヶ月くらいやりました。

### 自作malloc/appendのバグ
mallocやappendなどの動的メモリ確保が自作だったせいで、奇妙なバグに遭遇しました。

パーサがAST構造体を構築して、後でそれを使おうとしたときにはデータが壊れている。
しかもその構造体を全然触ってない処理の中でそれが起きる。
原因は、メモリ確保のアドレス計算が間違っていて、別々に確保した構造体のメモリ領域が一部オーバーラップしていたことでした。

mallocとappendのコードを捨てて書き直したらうまく行きました。

### 構造体のフィールド同士が干渉
ある構造体のフィールドAのメモリアドレスが、同じ構造体のフィールドBの途中を指しているというわけのわからないことが起きました。

どうやって原因を突き止めたかは忘れましたが、構造体ポインタのフィールドに代入する際のデリファレンスし忘れが原因だったようです。  (→ [修正コミット](https://github.com/DQNEO/minigo/commit/6118fd387b4fd35d0a06d2365fa14124c0fb1d6b) )

### 未実装であることに気づかない

Mapの要素を取得する際に

```
v, ok := mymap[x]
```
の okがtrueなのに vに値がセットされないという謎現象が起きました。
これは、単に`ok` の代入が未実装だったので、レジスタに残っているゴミ値が使われてたまたまok=trueになっていただけでした。

未実装なことを完全に失念していて、「自作mapが壊れている...全部書き直しか...」と暗澹たる気持ちになったのを覚えています。
この時期は絶望のどん底にいました。

### 第２世代コンパイラのデバグ中に第１世代コンパイラをバグらせる

第２世代コンパイラのバグ調査のためにコードをいじっていると第1世代コンパイラがバグる、ということがたまにあって、そうなると第２世代コンパイラが生成されなくなるので、そもそも治そうとしていたバグの発生源が消滅してしまい、自分は何と戦っているのかわからなくなる、ということが起きます。
こういう場合は調査用にいじった箇所を全部捨ててやり直すとうまくいきました。


そんな感じで普段のWebアプリケーション開発では絶対出会わない類のバグと何度も戦いました。

途中1,2回ほど 「もう自分には無理かもしれない」という思いが頭をよぎりました。

## 最終ステージ

<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="ja" dir="ltr">第二世代パーサーでコンパイラの全ファイルをパースできるようになった！🎉</p>&mdash; ドキュネオ (@DQNEO) <a href="https://twitter.com/DQNEO/status/1127110890753413120?ref_src=twsrc%5Etfw">May 11, 2019</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>



第２世代コンパイラのパーサが完走するようになったあたりで、これはいけるかもという気がしました。コードジェネレータが動き始めたあたりでそれが確信に変わりました。

<blockquote class="twitter-tweet" data-conversation="none" data-lang="en"><p lang="ja" dir="ltr">第二世代コンパイラがアセンブリコードを出力しはじめた...!  夢にまで見た風景が...!! <a href="https://t.co/elcUcbnNWs">pic.twitter.com/elcUcbnNWs</a></p>&mdash; ドキュネオ (@DQNEO) <a href="https://twitter.com/DQNEO/status/1127949711258734592?ref_src=twsrc%5Etfw">May 13, 2019</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>


そこから先はそれまでの苦労が嘘のようで、小さいバグをコツコツなおしていたら一気に進捗してセルフホスト達成できました。



記念すべきセルフホスト達成コミット → https://github.com/DQNEO/minigo/commit/18da74b1509f523de287fb3aa3f7cb1125ab4674

tcfm でよく語られる 「セルフホストは最後に一気に進む」というのは、最後の最後にはたしかに本当でした。

# なぜ本家Goコンパイラの実装を見なかったのか

一言でいうと「答え合わせの楽しみとしてとっておきたかった」からです。

他にも、

* `8cc` の知識でどこまでいけるか試してみたかった
* あれこれ目移りすると手が止まってしまう
* あまり見すぎると同じ設計になってしまう

あたりが理由です。

今は目標を達成したので本家Goコンパイラを読んでいるのですが、答え合わせ的な感じがめちゃくちゃ楽しいです。自作した後なので理解も速いです。

# 設計面での振り返り

sliceを設計したときに、「addr,len,capをもつ24バイトの構造体のような変数」という作りにしていて、map,interfaceも同様に24バイトの変数としたのですが、これは大きな間違いだったかもしれません。

int やpointerは8バイトなのに slice,map,interfaceは24バイト使うので、いたるところで条件分岐や複雑なコードが増えてしまい、例の組み合わせ爆発や後半戦の大量の実行時エラーの遠因になっていた気がします。

もし次挑戦するなら、slice,map,interfaceは8バイトのポインタとして扱う方がよいかも？

(追記: mapは実際に8バイトポイントになるように改造しました。sliceが24バイトになるのはしょうがないかも?)

あと、全体的にコード生成部分に負担が集中しているので、もう少しコンパイラバックエンド(中間表現、VMなど)の理論的な勉強をした方がよいかも。

# 実況中継のまとめ

ツイッターで進捗を毎日つぶやいていたので、Toggeterにまとめました。

https://togetter.com/li/1357678


# 謝辞

8cc, 9cc を公開してくださった rui さんに感謝します。
8ccがなければこんな奇跡は起きなかったでしょう。

セルフホストCコンパイルを達成されたセキュキャン参加者の方々の存在も、大きな励みになりました。
それから 僕の挑戦を応援してくださったTwitter上のみなさん、同僚のみなさん、
社内Slackで言語仕様に関するマニアックな質問に答えてくださった @tentennさん、どうもありがとうござました。

# 参考リンク
## 8cc
* https://github.com/rui314/8cc 
* [
Cコンパイラをスクラッチから開発してみた（日記）](https://qiita.com/ruiu/items/4d471216b71ab48d8b74)
* [Cコンパイラ8ccの1コミット目を読んでみよう](https://qiita.com/DQNEO/items/da15ce839b852a22cd51)

## 9cc
* https://github.com/rui314/9cc↩
* [低レイヤを知りたい人のためのCコンパイラ作成入門](https://www.sigbus.info/compilerbook)

# 追記 1
2020/02 libc依存から脱却しました。シングルスタティックバイナリを吐けるようになりました。

# 追記 2
2020/07 ２作目のGoコンパイラを作ってセルフホスト達成しました。 
http://dqn.sakusakutto.jp/2020/07/go-comiler-2nd.html