DQNEO日記

今日も明日も上昇気流

Goコンパイラを自作して93日でセルフホストを達成した(2回目)

Goコンパイラをゼロから書いてセルフホストを達成しました。(1年ぶり2回目) https://github.com/DQNEO/babygo

(ちなみに 前回の話はこちら 「Goコンパイラをゼロから作って147日でセルフホストを達成した」 )

主な特徴

  • 全部手書き。標準ライブラリも自作。system call 呼び出しも自作。libc非依存。
  • コンパイルするとアセンブリを吐きます。これをビルドすると単一静的バイナリになります。
  • 設計は、go/parser + chibicicc + α

かかった期間

2020/3/29に開始、2020/7/28にセルフホスト達成。

コミットした日 (Author date)を数えたら93日でした。

$ git log --pretty=format:%ad --date=short | sort | uniq | wc -l
93

平均1日2-3時間としてざっくり240 時間 ほど。 前回は500時間かかってるので、今回は半分の期間で達成できたことになります。

なんでまたやろうと思ったの？

実は前作 minogo を作ったあと完全に燃え尽きて、コンパイラ自作からしばらく離れていました。

しかし一方で「違うやり方で作ればもっと簡単にセルフホストできたのでは？」という疑念がずっとありました。

2019年秋のGoConference Tokyoで 自作Goコンパイラの発表をしたとき、

聴衆「今後の目標は何ですか？」

私「疲れたのでしばらく休みたい。もしやるとしたらもう一回最初からやりたい」

というやりとりがあり、それに対する会場の反応が微妙だったのを覚えています。冗談と思われたのかもしれません。 しかし本気だったのです。

それと、自作GoコンパイラネタでアメリカGophercon2020に登壇予定だったのがコロナで延期になってしまって、どうせ登壇するならもう1個Goコンパイラを作って全米をあっと言わせたい、みたいな野心もありました。

全米は言いすぎた。

前作の反省点

前作 minigo では、Lexer/Parserはうまく書けたものの、コード生成部が異常に複雑になってしまい、超絶難度のSegmentation Fault に苦しみました。 原因は明白で、どのようにアセンブリコードを吐くべきかに関して筋の通った設計哲学がなかったことです。

スタックマシンと左辺値

前作は 一応 8cc 流のスタックマシンぽい設計ではあったものの、そもそもスタックマシンを全く理解していないまま作ったので、かなりひどいものでした。 特に代入のおける左辺値の扱いがひどく、様々な種類の左辺値と右辺値の組み合わせに対して全ケース個別に実装を書く羽目になりました。

左辺値の扱いについては TCFM 第30回 でも話題にのぼっています。rui さんいわく

「 8ccでは代入の扱いが混乱していた。次のコンパイラ(9cc)ではそこがうまく扱えるようになった」

とのこと。

実際 chibicc のコード生成部を見てみると、劇的にシンプルになっていて目からウロコでした。 具体的に言うと、下記のような代入があった場合、

structA.field[2] = structB.field[3]

8cc や 前作 minigo では左辺と右辺は全く違うコードになります。 一方 chibicc流のスタックマシンでは左辺と右辺を同じコードで扱うことができ(実行時アドレス計算)、劇的なコード削減につながります。また、あらゆる式が統一的なインターフェースを通して値をメモリにロード・ストアするので、少ないテストコードで多くのケースをカバーすることができ、バグが起きにくくなります。 (JVMのようなスタックマシンを知ってる人にとっては当たり前に聞こえるかもしれませんが、VMではない生のCPUとアセンブリ言語でスタックマシンを実装する方法はそれほど自明ではない気がします)

視野を広く持つ、自前主義を捨てる

前作では 「8ccで学んだ知識だけで Goコンパイラを作ってみたらどうなるのか？」が開発の主要命題でした。なので、あまり他のものを見ないように気をつけていました。 「他にもっとよい書き方があるはず、なんてことを考えていたらいつまでたっても先に進めない」(tcfmより) この言葉を強く意識して、意図的に視野を狭くしていました。 この方針は結果的にうまく行ったと思います。あれこれ他のコンパイラやら書籍やらを眺めだしたら、手が止まって何も完成しなかったでしょう。

一方で、コンパイラを書き終わったあとも 自分の知識が 8cc ベースのままとどまってしまっていたのも事実です。 そこで今回は、「他のものを積極的に見る。新しい視野を獲得する」というのを意識して取り組みました。 具体的には、

  • フロントエンド (字句解析、構文解析、AST) は Go標準パッケージを真似る
  • コード生成は chibicc を真似る
  • 公式Goが吐くアセンブリを見て、なるべく真似る (特にABI)

の3点です。 この試みはうまく行きました。

あとは、同じタイミングで rui さんが「Cコンパイラ作成集中講座」というオンラインコミュニティを開設されたのでそこにも参加して積極的に質問しました。 講師・参加者ともに熱量があり、とてもよいコミュニティです。同じ目的に向かってる仲間がいるとモチベーションを保ちやすいです。

がんばりすぎない

前作では とにかく全力で突進して、method, map, interface, などの難易度の高い機能も強引に実装しました。ただ、これらの機能はやはり難易度が高く Segementation Fault の温床になってしまったのは事実です。

そこで今回は、極力少ない機能でセルフホストまで行くことを意識しました。

  • method の代わりに普通の関数で代用
  • map の代わりに slice の線形探索で代用
  • interface の代わりに 構造体ポインタで代用

その結果、上に述べた chibicc ベースの設計の利点とあいまって、コードベースを小さくすることに成功しました。 新作 babygo コンパイラはたった3ファイルでできており、コード行数は4,924行です。(前作の半分！)

$ wc -l main.go runtime.go runtime.s
  4630 main.go
   218 runtime.go
    76 runtime.s
  4924 total

作る順番を工夫

前作で、第2世代コンパイラのデバグに死ぬほど苦しんだ経験から、今回は前回とはかなり違う順番で作ってみることにしました。 具体的には、

  • 初期実装(第1世代コンパイラ)では “go/parser “ をそのまま利用し、コード生成部のみ自分で書く
  • 第1世代コンパイラである程度の文法をカバーしたら、その範囲内の文法のみを使って第2世代コンパイラをゼロから書き始める
    • Lexer, Parser, ASTに関してはそれぞれ go/scanner, go/parser, go/ast をロジックまる写し
      • ただし、少ない文法で書かないといけない(前述したように map, method, interface等が使えない)ので、工夫は必要
    • コード生成に関しては 第1世代コンパイラで書いたものを流用
  • 第2世代コンパイラが、第1世代コンパイラ用のテストをすべてパスするまで機能を足していく
  • 第2世代コンパイラで自分自身をコンパイルさせて、出てきたバグを潰す
  • 第2世代コンパイラで自分自身をコンパイルさせて得られたものが、自分自身と一致すれば完成 (第3世代コンパイラ == 第2世代コンパイラ)

この試みは2つの点でうまく行ったと思います。

1点目は、「chibicc のスタックマシン設計が Go言語で通用するのか？」を早めの段階で検証できたことです。 コード生成はコンパイラの中でも一番難易度が高いものです。また、 ある設計が通用するかどうかは実際にコードを書いてみないとわからないということもあります。上記のような方法で開発すれば、「コード生成部のみ作る」ということが可能になり、コード生成の設計の良し悪しを検証しやすくなります。

2点目は、「第1世代コンパイラがサポートする文法のみを使って第2世代を書く」ことで、サポートしてない文法をうっかり使ってしまうことを防げることです。 例えば、第2世代コンパイラのパーサでうっかり(サポートする予定のない)型推論を使ってしまったとすると、

x :=  parseExpr()

このコードを 第1世代コンパイラに食わせると文法エラーになるので、書いた瞬間に気づくことができます。 この効果は絶大でした。 「新規で書いたところにバグがある」というのは直すのがとても簡単なのです。 今回は第2世代コンパイラのセルフホスト中のバグ発生を極めて少なく抑えることに成功しました。

また全体の過程で、出たバグの大半はprintデバグで解決できました。gdbを起動してデバグをしないといけない場面もあるにはありましたが、前回のような超絶難易度の高いバグは起きませんでした。

例えると、前回は歯を食いしばって悲壮な顔をして断崖絶壁をよじ登る感じだったのが、今回はピクニック気分で坂をてくてく歩いていたらやがて頂上に着いた、そのくらい難易度が違いました。

終わりに

あらためて、Go言語およびGo標準パッケージを作られた方々、および 8cc/chibicc/compilerbook を作られた rui さん、ありがとうございました。 Goコンパイラ babygo はこれらの巨人の肩にのって作られました。

私の事例を見て Goコンパイラ自作に挑戦する人が増えたらいいなと思います。

Goコンパイラ作ろう！

カテゴリ: go compiler