セキュリティキャンプ2020 Y-3 Cコンパイラゼミを自作してみよう!ゼミに参加しました

 私はcoins20アドベントカレンダー2020に2回連続で遅刻しました。

 というわけでこの記事はcoins20アドベントカレンダーの12月6日の記事です。

adventar.org

 これは自分が参加したゼミ内での発表スライド azarashi2931.github.io

 以下の内容は半分位発表スライドと重複しています。

つくったもの

 作業ログの方にセキュキャン期間中自分がなにをやっていたか大体書いてある。
 作業の経過はそっちにあるので、ここでは感想を中心に書く。

 以下、作ったコンパイラをazccと呼ぶ。

Y-3 Cコンパイラゼミを自作してみよう!ゼミ

ゼミの紹介文から引用すると、

プログラミング言語の本格的なコンパイラを書いてみたいと思ったことがある人は多いのではないでしょうか? この講義では、簡単なプログラムが実際にコンパイルできるようなC言語コンパイラを、C言語を使って開発します。ひとまずの目標は、自作コンパイラを自作コンパイラ自身でコンパイルする(セルフホストする)ことですが、さらに最適化や異なるアーキテクチャへの対応を行いたいという方も大歓迎です。この講義を終えればコンピュータとプログラミング言語一般、そしてC言語についての深い理解が得られていることでしょう。実際に講師の私(植山)はセルフホスト可能なCコンパイラ8cc(https://github.com/rui314/8cc)をゼロから書いた経験がありますが、それはソフトウェアエンジニアとしての実力をぐっとアップさせるような、他には得難い貴重な体験でした。コンパイラ作成のような大きな目標を達成するためには、入念な事前準備が必要です。 プログラミング言語の理論や実装の基本的な構成などは事前に勉強していただく必要がありますが、それらはもちろん講師陣が手厚くサポートしていくので、心配する必要はありません。必要なものは、プログラミング言語に対する情熱です。多くの皆さんの応募をお待ちしています。

ということでC言語でCコンパイラを書くなどした。

 教材には講師の植山先生が公開している低レイヤを知りたい人のためのCコンパイラ作成入門を使用した。

www.sigbus.info

開発の際の自分ルール

  • エラー処理の関数などはcompilerbookからのコピペで済ませる一方で、トークナイザ、パーサ、コードジェネレータなどはなるべく参考実装を見ないで実装する。
  • セルフホストが重要なマイルストーンなので、Cコンパイラの実装はC言語で行う。

やった

式、文のパース

 intchar型のみをサポートし、それ以外はセルホストにいらないのでサポートしていない。
 式を1つ評価するとスタックに1つ値が積まれること、文を評価する前後でスタックは変化しないことに注意して実装したほうがよいということがわかってきた(n回スタックを破壊したので)。
 (実はこの記事を書いている途中にもスタック破壊を1つ見つけて修正した)

ローカル変数、グローバル変数の定義と初期化

 グローバル変数の初期化はint型のリテラルのみをサポートし、それ以外はサポートしていない。これはグローバル変数の初期化式が定数式でなければならないが、複雑な式を定数式であるか判定するのは面倒なので省略したため。あとでいいかんじの定数伝播を実装して複雑な定数式も受け取れるようにしたい。
 ローカル変数については実行時に値が決定すればよいので、azccでコンパイルできる任意の式を初期化式にできる。

関数の定義、宣言、6つ以上の引数をもつ関数を含む関数呼び出し

 コンパイラを実装するとき、関数の呼び出しや定義はコンパイラの成果物のターゲットの呼び出し規約*1にあわせて実装する必要がある。
 自分はABIを満たさない実装をした結果何度か破滅した。

構造体

 構造体のアライメントが難しいと聞いていたのでその辺に気をつけて実装した結果、割とすんなり実装できた。
 構造体を実装するときsizeof_Alignof*2があるとテストしやすいという話も聞いていたのでついでに実装した。
 構造体のアライメントに関する仕様はワンパスで実装できるような仕様であるはずだ、というところからエスパーするなどした。

_Bool

 どうしてそんな仕様にしましたか…?
 ちゃんとABIを見て実装した方がいい。自分は破滅した2。

やる

 スライドのこの項目に書いた内容は、実は翌日までにやってしまっているのである!

セルフホスト

 現状ではコードジェネレータ以外の部分は自分自身でコンパイルできているが、正常に動いているのはごく一部だけ。かなしい。
 コードジェネレータに関しては可変長引数関数の定義が含まれており、azccが可変長引数関数に未対応なのでコンパイルできていない。これはソースコードから可変長引数関数の定義を排除することで解決するつもりでいる。
 正常に動いていない部分に関しては、少なくとも関数呼び出し部分に問題があることがわかっているが、おそらくこれ以外にも多くのバグが埋まっている。書いてる間に解決した。やった~~。が、バグがたくさん埋まっているのは変わらず…
 機能追加はこれ以上必要ないと思うが、それでもセルフホストまでの道程は遠そう…

セルフホストしたらやりたい

  • 最適化パス
    • 自分のコンパイラが吐き出したものが速いと→うれしい!ので。
  • デバッグ情報の出力
    • 自分のコンパイラが吐いたバイナリに不具合があるときにどこが問題なのかわからず困っているため。

やる予定がない

ビット演算

 ビット演算を使わなくてもコンパイラは作れるので。

浮動小数点数

 同じくコンパイラにいらないので。

その他感想

  • オンラインでアバターを使って発表するための知見が得られてよかった。
  • せっかくセキュキャンに来たのに講師やチューターの方をあまり活用(?)できなかった感があり、もったいない。
  • チューターの方とクローズドな場所でセキュキャンに関するコミュニケーションをとって内容をゼミ内で共有してなかったのはあまり良くなかった。
  • 大学図書館ってやつがめちゃめちゃ便利で、良さげな文献がタダでシュッと出てくる。
  • 週に1回の講義という形態だったため、週初めに問題が起きて週末に質問するか~と思ったらその週のうちに解決してしまい質問がなくなる、などもあった。
  • compilerbookには「このステップができるとhogeのようなテストが通るはずです」のように書かれがちなので、テスト駆動開発っぽいことがやりやすかった。
  • だんだんとセルホスト最悪仕草*3が身についてきた。
  • 再帰下降構文解析アセンブラ、ABI、C言語の仕様に関する知識は大きな収穫だったし、C言語での開発経験(という程のものでもないかもしれないが)を積めたのは非常によかった。

さいごに

 年末までにセルフホストするぞするぞするぞするぞ。

*1:今回はSystem V AMD64 ABI

*2:自分はこのときはじめて_Alignofなるものを知った

*3:「UBなので何をやってもええんじゃ!」、「ま、コードの正しさはGCCが検証してくれるんで」など