LoginSignup
732
385

More than 3 years have passed since last update.

@DQNEO(DQNEO)inMercari

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

Last updated at Posted at 2019-05-20

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

本家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コンパイラを書いてセルフホスト達成というのは前例を聞いたことがないので、達成したこと自体がよかったなと思います。

最初のコミット

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

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

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

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

なんで作ろうと思ったの

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

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

Rebuild: 153: Connecting The Dots (rui314)

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

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

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

大まかな進行

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

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

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

前半戦

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

1日目: 足し算が動いた

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

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

5日目: hello_world.go が動いた

1ヶ月: FizzBuzzが動いた

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

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

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

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

識別子解決問題

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

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

package main

func main() {
    println(i)
}

var i int = 123

これは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ローカル の掛け算が組み合わせ爆発になってしまい、それぞれのケースに対してコードを書かなければならない事態に陥りました。

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

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

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

後半戦

つらかった

"Segmentation Fault"の嵐

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

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

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

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

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

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

自作malloc/appendのバグ

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

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

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

構造体のフィールド同士が干渉

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

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

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

Mapの要素を取得する際に

v, ok := mymap[x]

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

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

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

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

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

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

最終ステージ

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

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

記念すべきセルフホスト達成コミット → 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にまとめました。

謝辞

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

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

参考リンク

8cc

9cc

追記 1

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

追記 2

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

  1. トークナイザーとプリプロセッサがやや密結合していた ↩

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

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

732
385
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
732
385