Permalink
Fetching contributors…
Cannot retrieve contributors at this time
1430 lines (734 sloc) 79.3 KB

C(のサブセット)コンパイラ開発日記

2018年7月8日 (Day 1)

  • VirtualBoxにUbuntuを入れるのに失敗した。しかたがないのでmacOSで開発する。まあ関数呼び出しとか実装するようになるのはもっと後の話だろうし。

  • 課題1(標準入力で数値を受け取り、その数値をreturnする関数のコードを吐く)。やるだけ。入力に乱数を入れたくて、ググったとおりに適当にやったが、なんか上手く行かなかった。macOSのbashの仕様が違うのかもしれないし、私がbashを理解していないのかもしれない。両方か。

  • +- だけがあるlexerを実装。

  • 課題2。とりあえずCPUをスタックマシンにするために頑張ろう。Compiler Explorerのコードを見て、見よう見まねでpushとか演算とかが実装できるようになった。チラ見した他の人のコードには普通に push みたいなニーモニックが書いてあったが、まあとりあえず動けばよかろうなのだ。

  • lexerとスタックマシンができたのだから、あとは中置をRPNにするだけ。再帰下降パーサーを書けばいいのだが、何を思ったかshunting-yardを実装(しかもまだvectorが無いので有限長の配列)。どうせどこかで挫折するんだろうなぁ

  • 無事動いた。やったぜ。

  • vectorが欲しいけど、つらくかなしい void* よりはメタプログラミングの方がまだマシでは。

  • vectorを無事shunting-yardに組み込むことに成功。これにて今日は終わり。

2018年7月9日 (Day 2)

  • 8日の日記を書いた後に、コードをきれいにして、さらに掛け算を実装。

  • 用事とか誕生日とかがあったのでそんなに組めていない。まあ今日はこんなもんでいいや。

  • 新機能としては、掛け算が増え、一般に複数の優先順位にだいたい対応できたということぐらいである。どちらかというとコード美化をした一日だった。

2018年7月10日

  • まったりしていたので進捗なし。たまにはこういう日もある。

2018年7月11日 (Day 3)

  • まったりしていたらみなさんがとても進捗を出しているの図。

  • とりあえず、パーサー拡充して演算子だけでも処理するか。演算子は大量にあるけれど代入とかを除けばだいたい同じだし。

  • 除算・剰余・カンマを実装。じゃあ次は比較演算子を実装して2文字の演算子について考えることとするか

  • 比較演算子( < <= > >= == != ) と ビット演算子( & | << >> ) を実装する途中で、スペースも処理するようにした。

  • 単項演算子( ! ~ )を実装したところで、そろそろ変数とかの方に移っていこうか。

2018年7月12日 (Day 4)

連想配列の実装

  • 寝て起きたので日が変わっている。えーと連想配列組まなきゃなんだよな。

  • (char *, int)というペアの配列で実装しろとのことなので、vectorテンプレートを使う。オレオレテンプレート、やはり便利。

  • 実装できたと思う。テストも書いた。

ローカル変数の実装

  • ローカル変数を処理できるようにしよう。%rbpはローカル変数の処理に使うべきで、固定しておくべきっぽいので、いままで%rbpを上下させて実装していたスタックマシンを、%rspを上下させるような仕様に変更。

  • 領域を確保するコードを正しく実装できた。さて次はlexerを変数に対応させよう。

  • 変数に対応させようとしたら、なんか16進数と8進数が実装されていた。変数に対応させよう。

  • とりあえずパーサーが変数を読めるようにした。

リポジトリ美化

  • テストファイルの命名に一貫性がないこと、自動生成されている.sが.gitignoreされていないことに関して指摘を受けたので訂正。

ローカル変数の実装

  • さてさて。ローカル変数の実装だ。そろそろshunting-yardだと支障をきたし始める頃だろうか。知らんけど。

2018年7月13日 (Day 5)

ローカル変数の実装

  • アセンブリを書いてみたところ、まあ当然右辺値として使うかどうかによって文脈判断が要るので、再帰下降にするしかないことが確定。まあそれはそうだった。最初から再帰下降にしておけばよかったのに。

リポジトリ美化part2

  • 空白はトークンではないのでlexerから削除。

  • ヘッダファイルを合流させた。

  • テストをまとめたり減らしたりした。

    • 出力ファイルにデバッグ情報を埋め込むことで、わざわざテストをしなくてもデバッグしやすいようになった。
    • --lexer-debug オプションを実装することで、わざわざテストをしなくてもデバッグしやすいようになった。
    • それによって不要になったテストを削除。print_assembly_check009 はcheckではなくsandboxなので、そう改名。
  • clang-formatを使用。

  • 再帰下降で全部書き直すことに成功。

機能追加

  • 再帰下降にしたので単項+と単項-が実装できるように。よって実装。

  • 複文を実装。「最後の評価値を戻り値にする」をそのままやるのが面倒だったため、returnも追加した。returnの後に更に文が来たときの挙動は現状では未定義とする(実情としては、「評価されるが」返り値には影響を与えない、みたいな挙動になるはず)→ラベル足せばいいことに気づいたので足す。

  • 変数aと変数bを使って処理ができるように。

  • 任意の名前の変数を許容。

  • ^を実装、さらに条件演算子を実装。

2018年7月14日 (Day 6)

関数呼び出し

  • 関数呼び出しを実装。関数定義ができないので、常に87を返す組み込み関数always87()を実装することで凌ぐ。

  • 引数付きの関数呼び出しを実装。

2018年7月15日 (Day 7)

  • parse_compound_statement を足して、それで全体をparseするように。

  • 複数の関数定義(引数なし)をパースできるように。

  • 複数の関数定義(引数あり)をパースできるようになり、フィボナッチに成功。

  • && を実装。3 && 2 && 5とかでも通る。

  • || を実装。3 || 2 || 5とかでも通る。

  • += を実装。

  • -= *= /= %= <<= >>= &= ^= |= を実装。

  • if - else を実装。ちゃんと最も内側のifelseがくっつく。

  • 関数内に複数のルートができたということなので、同一関数内のreturnは必ず同じ場所に返るように修正。

2018年7月16日

  • 徹夜 → 15:00まで外出 → ( ˘ω˘)スヤァ

2018年7月17日 (Day 8)

  • do - while を実装。

  • while を実装。また、;とコンマ演算子はやっぱり挙動が異なるべきなので、修正。

  • break を実装。多分。二重ループでもちゃんと正しく動いてるっぽいのでOK。

  • continue を実装。

2018年7月18日 (Day 9)

  • バグが検出されたので直した。do-whileの末尾でスタックを余計に押し下げていて、ローカル変数の領域を破壊していたのが原因だった。

  • いい加減vectorをvoid *に統一しなければならないので、その移行の準備をした。

  • 前置・後置の++-- を実装。

  • 「lexerを2回実行して、1回目でトークン数を数えて2回目でその分をcallocする」とすれば vector_Token が不要になるので、そうした。

  • intmap以外でのvectorの使用を廃することに成功したので、vectorをintmapの中に放り込んで怒涛のinline化。そしてリポジトリからテンプレート機構を削除。

  • 第三式が無いfor文を実装。

  • 第三式があるときにもfor文を実装。(あれ、コメントアウトで書いているけど2重ループでマズいのでは)(←大丈夫。第三式自体にforが出なければよくて、forは文なので第三式には出てこない)

2018年7月19日 (Day 10)

  • ソースコードから配列を追放。これで多分すべての変数宣言が 型名 名前; と見なせる

  • 型名 名前; を構文解析

  • int_mapint じゃなくて void* を取るように。それに沿って map に改名。

  • 変数が宣言されていないとエラーになるようにした。

スコープ

  • ちゃんとスコープを見てやらねばなのである。ということで、現状の map での管理では限界があろう。ブロックの内外で変数名が衝突することもあるのだし。

  • 変数用の領域を確保する処理は割と現状のままでよくて(現状だと多めに取ることになるが、多い分には困らない)、名前解決を直さねば。

  • 現状では、関数に入る際に、それ以降に登場する全ての識別子を数え、それに offset を振っている。しかしこれだとスコープの内外で変数名が衝突したときに困るので、最初は全ての識別子を重複を含めて数え、 offset は振らないでおく。

  • まずデータ構造を考えよう。中から外を見なければいけないが、外からは中は見えなくて良い。ということで、外へ外へと伸びていくリンクリストにすればよさそうではある。

  • さてどう移行していこうか。とりあえず var_tableold_var_table にしよう。次に、 capacity の確保をする際には重複して数えるようにしよう。

  • とりあえず片方向リンクリストの型を入れておいた。まだリンクリストにはなっていないけど。

  • isDeclared を一旦捨てて、直に offsetvoid*にキャストする方針へ。これによりcallocを廃す。

  • 宣言されてから初めてinsertするようにした。動いた。

  • 多分リンクリストが実装できた。知らんけど。

  • スコープチェーンが動いていることを確認。

雑多

  • ついでに、関数名の前に型を要求。これで supplement.c を自力でコンパイルできるように。

  • 誤ったCに対してエラーを吐く方に関してはテストをしていなかったので、テストをしようとしたところ、continue_label_nameの初期化忘れというバグを検出。修復した。

型とoffsetとアラインメント

  • 言われたとおり、 Type 型を追加。ついでに幅を取得するsize_ofを追加。
struct Type {
	enum { INT_, PTR_ } type;
	struct Type *pointer_of;
};
  • ポインタ型の宣言を構文解析。

  • ポインタ型の値を後々入れていくことも考え、offsetを一律8に。

2018年7月20日 (Day 11)

  • &* を実装していきたい。とりあえずアセンブリで実験を重ねる。

  • ↓をアセンブリでどう吐くかが分かってきた。

int main()
{
    int x; x = 86;
    int *y; y = &x;
    int **z; z = &y;
    return (*y) + (**z) + 2;
 }
  • 変数に型情報が必要なので、 struct VarInfo を復活させた。といっても、かつてのとは異なり isDeclared が滅びているわけだが。そして変数の型情報をinsert。

2018年7月21日 (Day 12)

  • 型のsizeが8バイトであるときは8バイトをロードするように。

  • とりあえず & を足すだけ足した。

  • 型チェックをするには型の等価性を判定しなくてはいけない。ということで type.c を分離してそこに書いていくことにする。

  • んー、コンパイラの中にも「型のスタックマシン」を積んで、それを操作して型情報を取得するしかないな。普通なら抽象構文木をちゃんと作って処理するべきなんだろうけど、いまさら足すのもなぁという思いがあるので。

  • 現状の gen_ 系の関数を全てラップするか。んでコンパイラではそっちを呼び出す感じで。

これ以降日記の更新が途絶えており、1ヶ月経った今(2018年8月21日)ログを見て書いていっている

  • 言語学オリンピックの集まりに行った後、radare2のコミッターとかSecHack365経験者とかとのオフ会に行く。上記の「型のスタックマシン」のアイデアをもとに午前中12コミットほどするも、午後6時台に(時間を潰すべく座る場所を求めて行った)ゲーセンで2コミットしたタイミングでこの方針の愚かさに気づき、急遽午前9:38の4ade413に戻すこととした。

  • なお、戒めのためにそのブランチをdesertedという名前でpushしておく。

  • コミッターと合流した後もコードを書いていく。とりあえず、desertedブランチのなかでも使い物になりそうなコミット(本筋と関係のなかったコード美化のたぐい)を採用してから、implement_typecheckブランチを立ててやっていった。

型チェックの実装

  • とりあえず、(理想に反して)まだ構文木が無いので、parse_なんとか_expression系の関数(なんとparseといいながらここで意味解析もコード生成もしているんよな)がvoidではなく式の型(とあとは「ローカル変数かどうか」「ローカル変数だったときそのオフセットはどれほどか」)を含む構造体ExprInfoを返すようにしていった。

  • 一気にやるとバグらせるので、一時的にFIXMEという値をExprInfoとして許容し、1関数ずつExprInfoを足していきながら情報が足りないときにはFIXMEで埋める、という方針をとった。この方法は今後も何回か出てくる。

  • この日のうちにはFIXMEを消し去るところまで行かなかった。21:00頃に二次会(radare2のコミッターがTwitterで人を追加で呼び急遽開催)が発生し、その後帰って寝たからである。なお、ログ曰く進捗も出さずに午前2時までTwitterをしていたそうな。

2018年7月22日 (Day 13)

  • ログ曰く、起きたのは13時とかのようだ。コードは15時から書き始めている。16時あたりに「通るはずの型チェックが通らない」という現象が起きたらしく、それを特定すべくexpect_typeの第三引数にマジックナンバーを埋め込んでデバッグ、2項&が単項&と衝突するらしいのでとりあえずコメントアウトして4e311d8としてコミット。(おかしいなー再帰下降してるんだから衝突なんて起こるはずないのになー)原因は関数のパラメータに関して型の情報を記録していなかったというだけだったのだが、埋め込まれたマジックナンバーはその後も残り続け、後にコードレビューで指摘されることとなる。

  • FIXMEを全て取り除いた。この段階でテストを走らせると089だけが通らない。仕方がないので089をコメントアウトしてコミット。

  • アドレス演算子のパーサーでポインタを進め忘れていたというだけの話だった。「通るはずの型チェックが通らない」という現象が起きていたのは、このせいで2項演算子の&の方の処理も通っていたためのようだ。なるほどなぁ。これにより、「パーサー中で変なところを通っていたら、トークンの消費し忘れ=ポインタの進め忘れを疑え」という知見を得た。これは地味に後々のデバッグで役立つのであった。

  • ということで無事実装できたので、implement_typecheckブランチをmasterにマージ。

間接参照演算子・複雑な左辺を持つ代入文の実装

  • 型チェッカーができたので、「右辺値としての」 * の実装は楽である。ポインタ型であるかどうかを確認して(←これを書くために型チェッカーが必要だったのだなぁ)、PTR_ノードを型から取り除いて、アドレスから値を得ればOK。テストも通る。

  • さて、問題は左辺値である。自分でもあまり分かっていなかった印象があったので、恒例のごとくとりあえずgccが吐いたアセンブリを読んで式変形していこう。

2018年7月23日 (Day 14)

  • 複合代入演算子も考えておいたほうがいいよなぁ。これまたアセンブリを読んでいこう。ふむふむ、先に右辺値として処理する際に、*される前のアドレスを隠しローカル変数に退避しておけば、「実は左辺値でしたー」となったときも対応できるな。さらに、複合代入演算子の場合は右辺値としての値と左辺値としての値が両方必要になるわけだ。ますますこの方法が適しているだろう。

(編注:当然であるが、構文木さえ作っていれば、こんなトリック使わずとも「右辺値と左辺値のコード生成を分離する」だけで十分なのである。)

  • 寝て起きた。ということで、ローカル変数の領域を増やしてアドレスをバックアップしよう。(編注:なぜか44e2c5dのコミットメッセージはback up the register とか書いてある。addressの間違いに決まっているんだよなぁ。)

  • Cの構文規則では、assignment-expressionはこう定義されている。

assignment-expression:
                 conditional-expression
                 unary-expression assignment-operator assignment-expression
  • ということは、「試しにunary-expressionを読んでみて、その直後にassignment-operatorが来ていなかった場合はその情報を破棄し、conditional-expressionとして読む」と実装しなければならない。しかし、現状ではparseしたら同時にコード生成もしてしまう。

  • コード生成のオンオフを切り替える機能を実装することも一瞬考えたが、あまりに面倒である。かといって、ネストする可能性があるのでfor文のときと違ってコメントで処理はできない。

  • …そうだ、ジャンプですっ飛ばせば事実上のコメントアウトではないか!

(編注:当然であるが、構文木さえ作っていれば、こんなトリックは一切不要なのである。)

  • とまあそんな迷案を思いついてしまったので実装。ついでにfor文の第三式もコメントではなくこの方法で処理するように。

  • *ident とかがlvalueとして使えるようになった。

  • assignment-expressionがネストする際、バックアップ領域が上書きされてしまうのを防ぐために、バックアップをさらにスタックに積み直すように。これにより a = b = 5; が動く。

(編注:当然であるが、構文木さえ【以下略】)

alloc4 のための準備

  • さて、資料に従ってポインタ演算のテストをするには、「intの値を4つ引数に与えるとその引数を要素数4の配列に突っ込んでくれる」という関数alloc4を作ってgccでコンパイルし、リンクする必要がある。そのためには関数にポインタを渡したり、関数からポインタを返したりする必要がある。関数呼び出し周りが4byteの引数しか対応していないので、修正が必要だ。

  • アセンブリを眺め、「あっこれ movq にしないとダメだな」とかを検出しつつ、コード片を print_x86_64.c に送っていく。

  • ポインタを関数に渡したりとかをできるようにすべく、そのための8バイト用コード片とかを足した。

  • ParserState が関数の戻り値の型をメモるようにしたので、戻り値の型チェックができるようになった。

2018年7月24日 (Day 15)

  • 他の関数の戻り値の型を func_ret_type_map というmapに入れておいて、呼ぶ方も型チェックをするように。ん、となると、資料に書いてある alloc4 を実現するにはプロトタイプ宣言を足さないといけないな。

(編注:当時の資料のalloc4は確保した配列をポインタで返していた。int以外の値を返しているこのような関数を書くにはプロトタイプ宣言が必要ではないかと指摘し、今では「alloc4の第一引数にint **を渡し、そこ経由でポインタを入手する」ように書き換わっている。)

  • 8バイト用コード片を足したのでポインタを関数から返せるようになった。

  • 前述の理由によりプロトタイプ宣言を追加。

ポインタ演算

  • ポインタ演算を実装すべくgccの吐いたアセンブリで実験。 cltq という命令について学ぶ。

2018年7月25日 (Day 16)

  • ポインタ演算(pointer + int)を実装。ちなみにこの段階でalloc4の呼び出しが16バイトアラインメント制約に抵触しており、手動で変数を足してアラインメントをアドホックに揃えている。

  • 16バイトアラインメントを必ず満たすようにする方法を考える。思いついたのは以下の方法。

    • まずスタックを8バイト伸ばす。
    • rspと15でbitandし、rspを16で割ったときの余りを得る。
    • その余りの分だけスタックを伸ばし、余りをスタックのトップに格納してからcallする
    • 戻ってきたら、スタックのトップに書いてある値の分だけスタックを縮める。
    • スタックのトップに戻り値を書き込む。
  • こうすれば、最初に伸ばした8バイトのところに必ず戻り値が書き込まれ、かつcallの直前には必ず16バイトにアラインされている。

2018年7月26日 (Day 17)

  • pointer - intとかint + pointerとかも実装。

  • ポインタ演算のために掛け算するsizeofは1, 2, 4, 8だけ考えていればいいと思い込んでいたが、よく考えると配列へのポインタに関してはその限りではない。ということで任意のサイズを許すように。

2018年7月27日

  • ログを見る限り、徹夜してTwitterをして東大に行ってオフ会をしている。昼頃に人と会い、15:46頃に人が漢詩を作っている(押韻と平仄に苦しんでいた)のを見たりして、19:00あたりまで寝て、一人と会って帰っている。Cコンパイラの進捗は皆無である。

2018年7月28日 (Day 18)

配列

  • 配列を実装することを考え始める。まずは構造体Typeで配列を扱えるようにするのが先決だ。

  • 現状の関数定義のパーサー(もちろんコード生成と混じっている)は ret_type func_name(arg_list){} の形にしか対応していない。これを読んでいる人の中には「えっ、Cの関数定義の構文ってそうじゃないの?」と思っている人もいるかもしれないが、そうではない。例えば、 int a[3][5]; で定義される2次元配列 a を関数に渡し、関数では渡された a をそのまま返しているとしよう。その場合、その関数の定義は

int (*func(int (*a)[5]))[5]
{
    return a;
}

または

int (*func(int a[3][5]))[5]
{
    return a;
}

となる。

  • 今までは int *foo() というのを「型名 int *を読んで、識別子を読んで、カッコを読む」としていたが、配列が入ってくるとこれは破綻する。

  • ここまで複雑な例でなくても、「配列へのポインタ」を書きたいだけでも int (*a)[5]; と書かねばならない。配列の構文をサポートしろと書いてあるのだから、こういうケースもちゃんとサポートしてやらねばならない。

(編注:後になって分かることだが、この理解は 誤り であった。資料には「 int a[10]; のような変数定義を読み込めるようにしてください。」としか書いておらず、配列へのポインタだったりそれを返す関数だったりの構文解析をしろとはどこにも書いていない。)

  • なら、いっそのこと型関連の純粋なパーサーを新規に書き下してやろう。そうすれば現状の「パーサーとコード生成が混じっている」という現状を改善する取っ掛かりにもなるだろう。

  • int *a; とかを読んでいた箇所では、今までは int *a 箇所を「型名 + 識別子」として読んでいた。しかし、この解釈は誤りであるので、この箇所を parse_var_declarator という名前で抜き出し、構文規則に合ったコードで再解釈していくことを目標とする。

2018年7月29日 (Day 19)

ローカル変数の容量

  • 「スコープ」のところに「現状では、関数に入る際に、それ以降に登場する全ての識別子を数え、それに offset を振っている。しかしこれだとスコープの内外で変数名が衝突したときに困るので、最初は全ての識別子を重複を含めて数え、 offset は振らないでおく。」などというすごいことが書かれている。これは、「構文解析とコード生成を同時に行っている以上、関数が要求するローカル変数用の領域の大きさが関数の最後までわからない」という本質的な課題から逃げるための一時しのぎである。

  • しかし、配列が入ってくると、識別子の数を数えたところで十分な領域が確保できるとは限らなくなってしまう。ということは、関数を末尾まで読んで初めてローカル変数の容量が確定する。しかしローカル変数用の領域は関数の先頭で確保される。さてどうしよう。

(編注:当然であるが、構【以下略】)

  • そうだ、領域を確保するコードは関数の末尾に書いて、関数の先頭にはそこに飛ぶラベルを書けばいいんだ。(←は????)汚いけど動くからセーフ。うんうん。

(編注:アウト。いやまあfor文の第三式をコメントアウトで処理し始めた時点で既にだいぶアウトだった感は否めないが)

  • ローカル変数のsizeに応じてスタックを確保するようにした。前は最高が8だったので識別子が出るたびに8だけ確保していたが。

型の構文

  • 「さて、配列とポインタの入り混じった型宣言を構文解析するコードを書かねばならない」とかツイートしている。結論から言えば、しなくてよかったんですけどね。

  • 「型名 + 識別子」は嘘なので、 parse_type_name とかいう関数をinlineして parse_var_declarator として処理していくように。アスタリスクは識別子の方にくっつくのだということを parse_var_declarator に教えていきたい。

  • parse_var_declaratorptr_ps も コード生成も含まない純粋なパーサーなので、 type.c に送る。

  • K&Rを参考にして、 parse_var_declarator から parse_dcl*a を処理)を分離したり、アスタリスクは先に数えるだけ数えて後で型を構成したりするようにした。

  • parse_dcl から parse_dirdcl を分離。

  • parse_dirdcl にカッコを許容。( int *(*p); とかが書けるように。)

  • そういえばlexerにまだ角括弧を教えていなかったので追加。

2018年7月30日 (Day 20)

  • 日付は変わって7月30日。もう7月も終わる頃か。

  • 配列型のパースをバグらせた(pushしていないのでGitHubからは見えないはず)ので、typeparse_check.cを追加してチェックしながら慎重にやっていこう。

  • K&Rでは、型の構成要素が決まるたびにprintfしていっていた。つまり、vectorを用意してやって、K&Rがprintfしている箇所でvectorにプッシュしてやれば正しく動くはずだ。(ちなみにこれに気づくまでにさらに1回バグらせている。もちろんpushしていない。)

  • 三度目の正直で、配列を正しく読めるように。

構文解析とコード生成の分離(part0: 型)

  • 配列が読めたなら関数も同様に読める。じゃあ現状の関数定義のパーサー(もちろんコード生成と混じっている)もこれで処理するようにしてやれば、そのうちグローバル変数を実装した際にも対応できる。まずは int *foo(){} で生き残っていた parse_type_name とかいう関数を滅ぼし、後にグローバル変数に使うことも考えて parse_function_definitionparse_toplevel_definition に改名。

  • 関数型を追加して、純粋なパーサーで関数定義部分を読み取るように。parse_toplevel_definition の先頭での処理を純粋なパーサーに置き換えてやることで、可読性が上がりながらパーサーの「「「正しさ」」」も上がった。よきかな。

  • 前は parse_parameter_declaration でパースとコード生成を両方やっていたが、パースは純粋な方がやることになったのでコード生成のみの関数を生むことができた

  • きれいに「パーサーが読む、コード生成箇所が吐く」を(少なくともこの関数定義の冒頭に関してだけは)行うことができ、パーサーとコード生成を分離していくことに対する良い前例が生まれた。「パーサーが読んだ型が関数型以外であればグローバル変数宣言である」なので、今後グローバル変数を足していく際にもきれいに足せる。

  • 今回の件で、構文解析とコード生成が分離していることが如何に素晴らしいかだんだん分かるようになってきた。ということで、今まで parse_ で始まっていた関数の内、コード生成もしているものに関しては parseprint_ という接頭辞にしてやることで、「いつかは分離してやるぞ」という思いを表すことにした。

  • もともと変数の処理しか考えていなかったので parse_var_declarator と名付けたが、関数も対応した今となっては parse_declarator のほうがいいだろう。

2018年7月31日 (Day 21)

  • parse_var_declarator は変数専用にしよう。ローカル変数の確保とか。(関数内部にもプロトタイプ宣言は書けるけど、ローカル変数の「定義」と違って領域を確保しないので、こういうのは parse_var_declarator にして、関数内にプロトタイプ宣言書くのは現状では禁止しておこう)

  • 他に変数専用なのは…ああ関数の引数とかか。関数の引数は関数ポインタであって関数ではないもんな。(仕様を見る)えっ?関数型を渡すのは合法で、勝手に関数ポインタになってくれるの?知らなかった。あ、ついでに「引数が配列型なら勝手にポインタに読み替えられる」を足しておこう。

(編注:史実としては、この仕様を知ったのは前日である。)

  • #pragma onceを消した。

グローバル変数

  • 資料に従うと、次に足したいのはグローバル変数なので、VarとなっているやつをとりあえずLocalVarとしておこう。あと、グローバル変数がどうコンパイルされるのかも実験せねば。

2018年8月1日 (Day 22)

  • gen_write_to_global_8byte, gen_write_to_global_4byte などのスニペットを定義。

  • ヘッダファイルはなるべく一つにまとめるよう言われているが、 print_x86_64.c に関しては「長い」「コンパイラの他のコードと完全に独立している(構造体の定義を要求しないなど)」「print_x86_64.cで定義されている関数を要求する.cファイルが限られる」という理由から、分離することを確定。

  • グローバル変数の定義・グローバル変数の名前解決を実装。

  • Rustに触発され unimplemented 関数を追加。fprintfしてexitするだけ。

  • 右辺値としてのグローバル変数・左辺値としてのグローバル変数を実装。

2018年8月2日 (Day 23)

構文解析とコード生成の分離(part1.1: 式のパーサー純化)

  • 式に関して純粋なパーサーを書き始めるようにする。まず、parseprint_expression.c をコピペしてコード生成にまつわる部分を全てコメントアウトし、 parse_expression.c を作る。

  • 式パーサーの中でもparse_expression.cではなくcompiler.cに置いてあるやつに関しても複製。

  • for文の第三式は、今回作った「コード生成しないパーサー」を使うことでジャンプコメントを回避。最初からこうしておけ。また、これにより(多分きっとおそらく)コード生成箇所が抜かり無くコメントアウトできていることを確認。

  • 代入文のところもジャンプコメントを回避するようにしたところバグった。検証してみると、やっぱりコメントアウト忘れが発覚したので直す。

  • まずXOR式をASTにしていって、そこから順次ASTにしていく。前回と同様、未実装のところはUNKNOWNで埋める。ビット積→等号→比較→シフトまでやって、問題は次の加減算である。

  • 式のカテゴリにPOINTER_PLUSORMINUS_INTを足した。意味解析が構文解析側に融合している現状では、パーサーを通したらいきなりコード生成となるので、式のカテゴリとして処理してやる必要がある。POINTER_MINUS_POINTERも要りますわな。

  • あとは乗除→ビットOR→論理AND→論理OR→条件演算子。論理AND・論理OR・条件演算子は今までラベル生成があったのでparse_expression.cから外されていたが、純化により分ける必要がなくなった。

  • さて、残るは関数の引数(パーサー上はassignment_expressionであり、あとで統合される)とか、変数や数値リテラルといったprimary_expressionとか。

  • 代入演算子。ローカル変数への代入・グローバル変数への代入を実装。

  • 単項演算子→後置演算子→関数の引数リスト→関数呼び出し。これでUNKNOWNの廃止に成功。

  • parse_expressionは2項演算子のみを処理しているので、parse_binary_expressionに改名。その他の純粋パーサーはparser.cとしてcompiler2.cから分離。

  • 引数の長さを数え間違えていたバグを修正。

  • parseprint_expressionをいずれはprint_expressionにすべく、print_expressionを部分的に実装。print_expressionを使ってパースせずにコード生成することが可能かどうか判定するis_parse_implementedも作る。これにより、段階的移行が可能になる。

構文解析とコード生成の分離(part1.2: 式のコード生成純化)

  • とまあ、65コミットを要する大改造を経て純粋なパーサーを作ることができた。最初から分けておけばよかったのに。

  • さて、まだ終わっていなくて、parseprintから純粋なprintを作ってやらねば分離したことにはならない。

  • parseprint_expressionでのトークンの消費をするのにparse_expressionを使うように。少なくともトークンを正しく消費できていることは確認ができる。

  • primary_expressionで数値リテラルを読む際、INT_VALUEカテゴリを付け忘れていたバグを修正。

  • print_expressionを少しずつ実装できているので段階的に移行。テストは常に通るべきなので、「完全分離でできている」は緑、「できていない」は赤でメッセージを吐きながら、赤を減らしていく方針。

  • 単項演算子を足したので021まで完全分離。

2018年8月3日 (Day 24)

  • print_expressionに機能を足していくごとに、026まで→036→038→073→088→089→104と、どんどん分離できるようになっていく。

  • もはや「分離できている」が当たり前になってきたので、ここらで緑メッセージを削除。

  • ポインタ演算のコード生成も実装し、完全分離に成功。さて怒涛の削除の時間だ

美化・微調整

  • 大量にコードを削除したり、Expressionの中で使う演算子用のenumを分離したり、コードを美化したり。徹夜をしているのでロジックとかは書くべきではなく、単純な式変形として実装できるタイプのリファクタリングに限るべきである。

  • 加減算の処理は複雑だが、多くの演算子に絡む。ということでcombine_by_add_or_subという関数として分離。

  • 配列を左辺値として使えないように。

配列からポインタへの暗黙の変換

  • アセンブリで実験し、ローカル変数の場合での実装に成功。

  • 次は「配列へのポインタ」を間接参照してできる配列。これまたgccのアセンブリで実験だ

  • MACOSフラグをソースコードではなくコンパイラオプションとして渡すように。調べたらMakefileで自動判別できるっぽいので採用する。

  • VirtualBoxの導入になんか成功したので、このリポジトリをUbuntuに持っていったところ動かない。どうやら、アセンブラの仕様が違うらしく行途中のコメントに対応していないようだ。あと+8(%rsp)と書けないらしい。

グローバル変数のアドレス

  • gen_global_declarationで出てくる_はMacだけなので、PREFIXマクロに置き換え。

  • グローバル変数のアドレスを得るには、MacだとGOTPCRELとかいうものを使わないといけないらしい。Ubuntuはleaqでいいので気楽である。ということでgen_push_address_of_globalを書いて両方の環境でテストした。

  • 徹夜が堪えてここで仮眠。

  • アドレス演算子をグローバル変数に対応させた。

  • グローバルな配列がポインタにすり替わるように。

左辺値

  • 「配列へのポインタ」を間接参照してできる配列が、これまたポインタにすり替わるように。

  • せっかくコード生成と構文解析が分離したのだから、print_expressionと分離したprint_expression_as_lvalueを実装すべきだという気持ちになった。とりあえずprint_expressionのサブセットを作るところから始める。

  • 例の一時しのぎ「「「アドレスのバックアップ」」」の処理が必要なのはprint_expression_as_lvalueの場合だけであるので、そちらにその処理を送る。これにより左辺値と右辺値のコード生成が別物になった。

  • 13コミットぐらいひたすらアセンブリを式変形し、gen_assignという共通処理をくくりだすことに成功。

  • 諸々リファクタリング。「=はコンマ演算子による複合代入演算子」と解して処理のさらなる共通化に成功したこととか。

2018年8月4日 (Day 25)

  • LOCAL_VAR_AS_LVALUEがprint_expressionに到達しないことを確認。AS_LVALUEとAS_RVALUEを合流させても問題なさそうだ。

  • 三種の左辺値(ローカル・グローバル・間接参照されたアドレス)の処理を一体化。

  • 「「「アドレスのバックアップ」」」を完全に消去。

2018年8月5日 (Day 26)

2次元配列とNクイーン

  • なんか2次元配列で微妙にバグってるっぽい。添字0のときは問題ないので、sizeof絡みででもミスっているのだろうか。とりあえず恒例のごとくgccにアセンブリを吐かせて実験だ。

  • 「配列へのポインタ」を間接参照する際は、その値は変わらないということに気づいた。なるほどなぁ。さてこれで2次元配列もフルで動くようになった。

  • AS_LVALUEとAS_RVALUEを合流させた。

  • Nクイーンが解けるようになった。

2018年8月6日 (Day 27)

  • やはり毎回*(p+i)とか*(*(p+i)+j)とか書いているのはつらいので、添字演算子を足そう。combine_by_add_or_subは既にあるので、間接参照演算子用のderef_exprを作る。

  • p[i] を実装。

構文解析器の内部状態とコード生成部分の内部状態の分離

  • 構文解析時には、コード生成部分の内部状態は見えるべきではない。ということでPrinterStateという引数を生やしてコード生成部分の関数で持ち回り、ラベルとかの情報はそちらで持つようにしよう。

  • コード生成部分は構文解析器の内部状態を見るかもしれないが、変更はすべきでないだろう。constを足す。

  • 実はコード生成部分は構文解析器の内部状態を見る必要がなかったようだ。引数から削除。

char

  • 資料によれば、次はcharらしい。とりあえずgccのアセンブリをいじるいつもの作業。

  • 1byte用の関数を追加。

  • 末尾に4byteとついていなかった関数の多くに4byteとつけていく作業。

  • lexerと型パーサーにcharを足す

  • intとcharの間で代入ができるように、is_equalをis_compatibleとis_strictly_equalに分離。

2018年8月7日 (Day 28)

  • char *のderefとか、グローバルなcharとか、charの符号拡張とかを足す。

  • leave - ret するだけでいいことを知り、実践。

  • charが関数に渡せるようになったりする。

  • lexerに文字列リテラルを追加。

  • スタック上では少なくとも4バイト分は符号拡張されているようにした。

  • gen_strとgen_push_address_of_strをとりあえず足す。OSXでもUbuntuでも動くことを確認。

2018年8月8日 (Day 29)

  • 文字列リテラルをparse→コード生成したのでprintfを呼び出すコードが通る。

  • せっかくなので、Nクイーンでprintfを使うサンプルを追加。改行のためのエスケープシーケンスは無いので puts(""); で対応。

2018年8月9日 (Day 30)

ミーティング

  • ミーティングが行われた。指摘された箇所を直していったりしよう。

  • .gitkeepを使う→過去の遺物を削除→.hにclang-formatを掛ける→無駄なカッコの削除→未使用関数の削除

  • expect_typeの第三引数がマジックナンバーになっている(7月22日参照)のをデバッグメッセージに変更

  • ExprInfo.details.infoが重複した情報であり省けることが判明。削除。それに従い、remove_leftinessあたりの関数が消えた

  • int (*func(int (*a)[5]))[5] とかに対応する必要は全く無いとのことなので、それの処理をするコードを削除。故にtypeparse_check.cも不要に。

  • あと延々とリファクタリングが続くので、細かいものに関してはカット。

  • 特筆すべきこととしては、関数にstaticを付けることを避ける理由はないとのことだったので追加。

  • さらに、かつて滅ぼしたvectorを復活させた。あと型名は大文字で始まるように。

  • +- は取る型が違うので、combine_by_add_or_subcombine_by_addcombine_by_subに分割。

  • 複数行コメントに対応。

  • compiler2.c → codegen.h + main.c + codegen.c

  • 今まで入力をscanfで一行だけ読んでいたのを、複数行にも対応させる。

構文解析とコード生成の分離(part2: 文)

  • 文に関しても構文解析とコード生成を分離させていく。まずはparseprintの戻り値をvoidではなくstruct Statementにするところから。今回も恒例のごとくNOINFOというを足して再帰的に機能を追加。

  • NOINFO自体は8コミットぐらいで廃止できた。式ほど再帰が深くないのが助かる。

2018年8月10日 (Day 31)

  • newest_offsetはコード生成の内部状態にしていたが、構文解析(というか意味解析)の側に置いたほうが扱いやすいので移動。

  • これまたparseprintをコピペしてコード生成を削除することでparseを作る。

  • assertを入れ、消費するトークン数が同じであることを確認するのも恒例の通り。

  • parseprint_statementが引数として(自分自身が今returnしている)Statementを受け取るように。コピペしているのでこういうこともできる。

  • parseprint_statementが(パーサーの条件によってではなく)Statementの条件によって分岐するように。

  • parseprint_statementがvoidを返すように。

16進と8進の削除

  • 消せと言われたので消す。

構文解析とコード生成の分離(part2: 文)続き

  • codegen_expressionを作ってcodegen.hから分離する。

2018年8月11日 (Day 32)

  • 純粋なコード生成器print_statementが少しずつできてくる

  • 一時的にスコープチェーンのコピーを作る必要ができたので、これを機にMapに手を入れて内部構造を隠蔽する。

  • スコープチェーンのコピーをこっそりメモしておくことにより、parseprint_compound_statementでも「自分がparseして得たstatement」ではなく「純粋パーサーがparseして得たstatement」を使うことができた

  • parseprint_statementをparse_statementとprint_statementに分離することに成功

  • 分離してコードの順序を入れ替えた途端にスコープチェーンのバックアップが不要になった。

  • codegen.cからparse_statement.cを分離

  • parseprint_function_definitionもparseとprintに分離

  • parse_function_definitionをparse_toplevel_definitionとし、変数の場合も吸収。parse_definition.cとして分離

  • 全てのコード生成からParserStateの排除に成功

  • main.cでもparseとprintを分離。tokenizeしてparseしてgenerateする流れになった。

2018年8月12日 (Day 33)

美化

  • enumの型名を大文字で始める

  • GARBAGE_INTを取り除く

  • テストケースをシェルスクリプト送り

  • パーサー周りをparser.hに隔離

  • ParamInfosをVectorで代用する

2018年8月13日 (Day 34)

  • 予約語処理を別関数に分離

  • 指摘されたとおり、トークンが文字列の途中へのポインタを持っておくことで短いコード量でデバッグ出力をすることができるので修正。

  • ファイル名変更したり重複を削除したり。

2018年8月14日

  • セキュキャン1日目。人と話したり人の話を聞いたりしてたのでコードを書いていない。

2018年8月15日 (Day 35; Seccamp Day 2)

インクリメント周り

  • 左辺値の処理をまとめたりパーサーに手を入れたりすることで++*ptrとか((i))++とかp[i]++とかを許容。

バグ修正

  • バグ修正:レジスタに退避するタイミングを間違えていたことによって foo(i, j, bar(k))foo(k, j, bar(k))になってしまっていたバグを修正。

  • 条件演算子のオペランドが4バイトと仮定していたことによるバグを修正。

コード美化

  • ファイル名変更。parse_expressionとparse_binary_expressionを合流させたことによって関数に追加でstaticをつけられるように。

  • 構文解析と意味解析を分けるべきだということを明示すべく、parse_*_expressionparse_typecheck_*_expressionに改名。

機能追加

  • &*p, &(*p), &(q)を許容

構文解析と意味解析の分離

  • 一気に分離しようと11コミットぐらいしたらセグフォしたので、やはり段階的にやっていく。演算子の優先順位は多いので、ひたすら作業となる。

  • 純粋なパーサーがParserStateを見なくなった。じゃあこれ意味解析器の状態であってParserStateじゃないやん。

  • 純粋な意味解析器を作ろうと7コミットしたらまた詰まったので調査。parse_typecheckとtypecheckが果たして同じ木を吐くかどうか確認したところ、カテゴリにBINARY_EXPR付け忘れているだけだと判明。

  • しかしやはり木が一致しない。POINTER_PLUS_INTが左右入れ替えている可能性があるのをすっかり忘れていたので、それを無視して再実験。

  • とりあえず後置演算子周りが怪しいことが判明したので一旦寝よう

2018年8月16日 (Day 36; Seccamp Day 3)

  • 起きた。バグを直した。後置++と後置--に関して意味解析器でノード付け忘れていただけだった。

  • parse_typecheck系の関数の廃止に成功。

  • デバッグ用の木の比較コードとかを削除。

struct

  • アラインメント、意外と案ずるより産むが易しだった。なるほどこういう仕組みだったのね

  • structのパースをするためにアドホックな実装をしていたら泥沼にはまったので、15コミットぐらい戻して6コミットを救出、ちゃんときれいに実装していく。

  • sizeofを求めるsize_of関数はコード生成時に今まで2通りに使われていて、一つは「コード生成時に何バイトの命令を用いるか」を求める用途(つまり1か4か8しかない)、もう一つはポインタ演算やグローバル変数確保(つまり任意のサイズがある)のためである。structが増えるとsize情報が動的に増えていくので、前者をsize_of_basic、後者のをsize_ofとすることで、後者にのみstruct情報を渡していけばいいと分かった。

  • structのsizeとalignが取れるようになり、structとかstructの配列とかがローカル変数として扱えるようになった。

  • まだsizeofがないので、char *にキャストしてポインタの差を取る関数をgccでコンパイルすることでテストとする。

  • sizeofが欲しくなったのでsizeofを足す

  • structの中でstructを使っても動くことを確認。

2018年8月17日 (Day 37; Seccamp Day 4)

  • パーサーに手を入れて f(a)[0]++ を許容。

  • パーサーにドット演算子とアローを追加。

  • なんかバグっていたと思ったら calloc(1, sizeof(struct TypeAndIdent *)) と書いていた。 calloc(1, sizeof(struct TypeAndIdent )) に修正。

  • structのメンバアクセスのコード生成に成功。

  • gccでコンパイルした構造体と互換性があることを確認するテストを追加することを提案されたので、追加。

  • なるほど、expect_typeとかが構造体に未対応か。ParserStateを追加して対応させよう。

ヌルポインタ

  • ヌルポインタ定数を追加。整数式0がポインタへの代入の文脈で出てくる際にヌルポインタ定数に変換。

  • 条件系統の演算子が全て4バイトを仮定していたので修正。これでヌルポインタでの条件分岐ができる。

三種のvoid

  • キーワードvoidを追加。まずは関数の空引数リストのvoidを実装。

  • void *を実装。

  • 返り値voidを実装。

  • 少々いじったvector.cのコンパイルに成功。やったぜ。

  • スライド を作った。

2018年8月18日 (Day 38; Seccamp Day 5)

switch-case

  • switch-caseを実装し始める。

  • ParserStateをAnalyzerStateに改名したりする

  • caseもdefaultもないswitchを実装(breakはある)。「それはswitchではない」とか言われた(それはそう)

焼肉

  • RuiさんがCコンパイラ班を連れて焼肉をおごってくださるとのことなので行った。

2018年8月19日 (Day 39)

switch-case

  • defaultを実装。

  • 定数式評価(整数リテラルのみ対応)を追加。

  • caseを実装、Duff's deviceが動く。Duff's deviceは0回のループでは誤作動を起こすことを知った。

_Alignof

  • 楽に実装できる_Alignofを追加。

2018年8月20日 (Day 40)

  • コメント足したりリファクタリングしたり。

  • 返り値がvoidな関数ではreturn;が省略できるように。

enum

  • enumを読む→intとcompatibleにする→名前解決をする→定数式として許す

条件分岐

  • スカラ型以外を条件式として使えないように。

2018年8月21日

日記

  • 日記を書く。

  • あ、ついでにテストケースにクワイン足した

2018年8月22日 (Day 41)

日記

  • とりあえず日記が執筆時刻に追いつく。

以上、長い長い回想終わり

to do

  • とりあえずぱっと思いつく段階でのto doを書いておいた。

switch補足

  • switch の外で casedefault が出てきたらエラーにするように。エラーにする仕組みのためのメンバーは用意していたのに、処理を入れていなかったという

nullable vectorの廃止

  • Vector.vectorはポインタなので、そこにヌルポインタを入れておくことでnullなVectorを表したりしていた。しかしそんな罠は避けたいし、関数を使わずVector.vectorに対して直に代入するなどもってのほかなので、それを廃止しようとしている。

  • structenum(不完全型かもしれない)と関数の引数(引数が空のプロトタイプ宣言であり、情報がないかもしれない)でこのdirty hackを使っていた。structenumについては難なく解決。

  • 関数の引数について。そもそも、古くからあるFuncInfoが情報量的にTypeのサブセットだったので、FuncInfoTypeに昇格。あと、かつてVectorでなかった名残があったのでそれを廃した。

  • そういえばExprもVectorもどきを使っているんだっけ。直さねば。とりあえずargsという単一要素としてまとめる。

  • Exprを真のVectorにした。

  • さて、関数の引数についてはどうしよう。なんかポインタにしたらバグったのよな。

  • フラグを立ててそこで見ることにした。

型とtype-nameの構文解析

  • やっぱり複雑な宣言が読めてこそCなので(編注:個人の感想です)、カッコの入った複雑な形宣言のパーサーを復活させた。さらに、キャストとかで使うtype-nameも再帰的な型に対応させた。

  • なぜこれをやったかというと、理由の一部としてはconstを足したかったからですね。ということで型の文脈でだけconstを読み飛ばすように。

  • 古いサンプルを復活させた。

2018年8月23日 (Day 42)

  • const足したしvectorももっとparseしやすくなったはず。…あれ、落ちる。なぜだろう。

  • なるほど、プロトタイプ宣言で引数リストがあると変なところで落ちるのか。明示しなきゃな。

  • とかやっていたら型の構文規則にさらに手を入れたくなってきた。引数リストってdeclarationとは微妙に違うのよな。

  • 初期化子の書けるinit-declaratorについても考えないといけないのでね

  • f(int)とか書けるようになった。

  • int *()が関数になっていないバグを直した。

  • 初期化子を書けるようになった。これではかどる

文字列

  • 文字列リテラルの結合を実装。

  • エスケープシーケンスを実装。

2018年8月24日 (Day 43)

セルフホストに向けて

  • セルフホストに向けてカスタムヘッダを作り始めた。

宣言するタイプのfor文

  • forの第一clauseで定義した変数、第二・第三・残りからは見えて外には見えないという性質を持つので、一旦ブロックにしてスコープとしてやる必要があったりしそうである。

  • とりあえずブロックスコープを足した。

  • for文の第一式が代入文だったら宣言と代入式に分けてやらねばだが、分けようとしたら盛大にバグった。(変数増やしただけで落ちる)

2018年8月25日 (Day 44)

デバッグ

  • デバッグをした。原因は単純にラベルvectorの初期化忘れだった。おしまい。

宣言するタイプのfor文

  • できたよ

2018年8月26日 (Day 45)

ポインタ演算

  • ポインタの ++ とか <= とかは未実装なので、出てきたら落とすようにしてみた。

  • ポインタの +=-= を実装。

  • ポインタの ++-- を実装。

  • ポインタの比較演算を実装。

プロトタイプ宣言と型チェック

  • 完全なプロトタイプ宣言を追加し、宣言・定義「どうしの」型チェックをするように(呼び出すときの実引数の型チェックはまだ)

フランケンコンパイル

  • _Noreturn を足したのでフランケンコンパイルに成功。

2018年8月26日 (Day 45)

diff

  • 先人が通ってきた「2代目と3代目が違う」というヤバを早期から検出すべく、もうテストに2代目と3代目のdiffを入れるようにした。これですぐに検出できる

ヌルポインタ

  • ヌルポインタとの比較をする際、0をポインタにキャストするのを忘れていた。キャストするようにした。

  • ポインタを返す関数でヌルポインタを返す場合もキャストが要るんだった。なるほどなぁ

2018年8月27日 (Day 46)

整理

  • Makefileを整理

  • 先人の轍を踏まぬよう、今の段階から2世代目(clangでコンパイルした初代自作コンパイラで、自作コンパイラの一部をコンパイルしてできたバイナリ)と3世代目(2代目の自作コンパイラで、自作コンパイラの一部をコンパイルしてできたバイナリ)のdiffを取るようにしておいた。

map.cのセルフコンパイル

  • やっていこう。

  • 無駄なラッパ構造体があったので、これを機に削除。

  • ヌルポインタとの比較・ヌルポインタのreturnでそれぞれ型エラーが起こるバグを修正。

  • 構造体の一括代入を使っていたが、それを避けた。

  • map.cのセルフコンパイルに成功。

2018年8月28日 (Day 47)

構造体

  • 構造体の一括代入を実装。

  • 構造体の一括代入を map.c で活用。

ヘッダ

  • <stdio.h> のサブセット "std_io.h" を制作。

セルフホストに向けて

  • キャストを実装する気がないので、ソースコードからキャストを除去。

  • " のエスケープシーケンスを実装する気がないので、 %c34 で処理。

  • extern を実装。

  • static を実装。

  • print_x86_64.c をセルフホスト。

構造体を値で返す

  • とりあえず system_v_abi_class_of という関数を実装。

2018年8月29日 (Day 48)

  • アセンブリ言語と格闘する

  • 十分大きい構造体の場合、 struct Foo f() というのは void f(struct Foo *) と同様に扱われるということを知る。

  • アラインメントが1の構造体を使っていないので、とりあえずそういうのは一時的に関数から返せないようにしておく。

  • gen_epilogue_returning_small_struct というのを実装する。RETURN_STATEMENT のコード生成時には構造体のアドレスをpushしておいて、エピローグでは、INTEGER_CLASSな構造体である場合はそこで間接参照してレジスタに詰めてからleave/retする。これにより INTEGER_CLASSな構造体は返せるようになった。

セルフホストに向けて

  • enumの初期化子をコメントアウトしたり、ネストした定義の構造体を分割したりして、header.hを整理したので alignment.c をセルフコンパイルできるようになった。

  • INTEGER_CLASSな構造体は返せるようになったので、init_vectorvector.c に戻した。

2018年8月30日 (Day 49)

落ち穂拾い

  • &配列 をサポート。使ってないけど。

2018年8月31日 (Day 50)

セルフホストに向けて

  • 構造体を関数に渡すのは放棄しよう。スタック使いたくないし。

  • ということで構造体を関数で渡している部分をポインタ渡しにするようにしたので、 codegen_expression.c をセルフコンパイルできた。

  • グローバル変数へのアクセスを全部GOTPCREL経由にしたところ、stderrがちゃんと使えるようになった。よって std.cerror.c をセルフコンパイル。

  • 「今構造体周りってどこまでできてたっけ?」と思ったので実験をしている。a.b.cとか普通にできるのか。

2018年9月1日 (Day 51)

  • 1回しか呼ばれていないstatic関数をインライン化したりしている。その結果関数が500行ぐらいになったりしているが、とはいえ分割しても見やすくならんのよな。単項と二項とそれ以外で分ける、ぐらいはしてもいいかもしれないが。

  • &&|| のオペランドに構造体が来るのを明示的に禁じた。今までもコンパイルエラーにはなっていたけど、根から断つ方針に。

  • arr[3].a がなんか動いたので一瞬驚いたが、よく考えると arr[3] は左辺値なので当たり前だった。

関数の返り値としての構造体

  • メンバアクセスされる他の存在と違って、関数の返り値はC言語の仕様上は右辺値である。とはいえ、アセンブリレベルで見るとどう考えても「ローカル変数の領域を確保し、そこを使う」(MEMORYだったらそこのポインタを第一引数として渡す、さもなくば%rax%rdxに入っているやつをローカル変数に入れる)という仕様なので、裏では @anon1 みたいな名前の変数だという設定にしておくしかなさそうである。

  • となると、「構造体を戻す関数呼び出し」の数を数えてローカル変数に計上してやらねばならないのか。なるほど。

2018年9月2日 (Day 52)

構造体をポインタ渡しにする作業

  • ひたすら関数の引数をポインタにしていくだけの作業。

  • 16コミットぐらい作業をしたところ、17コミット目で「第二世代でのみ」失敗。ふーむ。

  • 原因は単純に、ExprがVOID_EXPRであるとき、その型がなにであるか未定義だった。明示的にvoid型にした。

2018年9月3日 (Day 53)

関数の返り値としての構造体

  • 戻り値が構造体となる関数の関数呼び出しを作るところから考えていこう。とりあえず「構造体を戻す関数呼び出し」の数を数えてローカル変数に計上するのは書いた。

  • こいつに左辺値としてアクセスするときは、そのローカル変数のアドレスを使えばいいはずだ。

  • よし、INTEGER_CLASSについてはできた。

ポインタ論理否定

  • 「無いのでは?」「多分無い」

INTEGER_CLASS

  • さっそくcodegen.cをセルフコンパイルしようとしたら、バグった。具体的にいうと2代目のコンパイラでswitchでコード生成するときに落ちる。また、switchであるようなテストケースを除いても、clangが生んだ「1代目のコンパイラの.s」と、1代目のコンパイラが生んだ「2代目のコンパイラの.s」がswitchに関して大きく異なる挙動を示す。

  • 少なくとも、1代目のコンパイラがswitchを生成するときの処理が壊れているのは確実。で、多分それVector絡み。

  • mainでもバグる。しかし構造体は正しく返せている。なんだろう。

  • 原因判明。「構造体を返す関数を呼ぶ時、引数を積んでいない」。なるほどなぁ。

  • バグを直す。

  • ちゃんとmain.ccodegen_switch.cもコンパイルできるようになる

MEMORY_CLASS

  • 先にMEMORY_CLASSを返す関数の呼び出しを実装する。というのも、ローカル変数のアドレスを第一引数として入れるだけで動くので。

  • 次にMEMORY_CLASSを返す関数の定義を実装する。

  • よっしゃあとはセルフホストするだけだ

2018年9月4日 (Day 54)

セルフホストへ

  • lexer.cやろうと思ったら文字リテラルがない。むぅ。

  • parse_analyze_statement.cをコンパイルしようと思ったらstruct Map2 *struct Map2 *が違う型と言われる。なるほど、不完全型へのポインタは名前が一致すれば一致、としておかないとなのか。

  • parse_analyze_toplevel.cをセルフコンパイル。

  • parse_expression.cをセルフコンパイル。

  • parse_type.cをセルフコンパイル。

  • type.cをセルフコンパイル。

  • typecheck_expression.cをセルフコンパイルしようと思ったら不可解にarray is not an lvalueと出る。まあ多分ポインタ型の値のtrue_typeが未初期化なせいで偶然ARRAYに見えたりするんでしょうな。ということで全部初期化して回ったら動いた。

  • 文字リテラルを取り除いた。

  • セルフホスト達成ですありがとうございました

もうちょっとだけ続くんじゃ

  • 文字リテラルを実装。

  • 文字列リテラル内でのダブルクオートのエスケープを実装。

  • 巨大構造体のコピーをしている箇所をなるべく削減。

  • アセンブラを作っているプロかつ魚がいるが、当然16進数リテラルがあった。じゃあ私も16進数と8進数を復活させよう。

2018年9月7日 (Day 55)

  • セルフホスト達成したとたん開発速度が下がるというね。

  • カンマ演算子は左右に多彩な型を取れるので、少なくとも simple_binary_op ではないと判断、コンマ演算子をSIMPLEに分類しているコードを削除してリファクタリング。

  • 副次的な効果として、代入文と複合代入文が分離された。構造体とか考えると明確に違うので分けたほうがキレイ。

  • (構造体, スカラー) みたいなコンマ演算子の使い方ができるようになった。

  • 自明なリファクタリングしようと思ったらバグった。なるほど、true_typeが配列かどうか見ているところで、typeがポインタであることを確認しないと。

  • そこから自明なリファクタリングをさらにしたらまたバグった。バグっているときはDOT_EXPRが左辺に来ているそうだ。ふむふむ。はいやっぱりそこでtrue_typeが未初期化。なるほどね

  • (構造体 = 構造体).a が書けるようになった。

  • 結構リファクタリングをして、あまりにも深いネストは減らしていっている。

  • 構造体が第二オペランドである三項演算子を実装。

2018年9月8日 (Day 56)

プリプロセッサ

  • ネタ切れが著しいし、プリプロセッサでも書くかなぁ。

  • さてどう入れていこう。

  • …そうか、#includeを作ることを考えるとファイルを読むようにしていかないとなのか。

  • とりあえず、標準入力だけでなくファイルからも読めるようにした。

2018年9月19日 (Day 57)

  • 文字列リテラルを処理する関数を変えた。

2018年10月3日 (Day 58)

デバッグ

  • 9月19日には実はこのあと「改行やスペースをトークンとして足す」というコミットをした。しかし、後述の理由によりこれはお蔵入りとなった。

  • 最新版を学校のUbuntuで動かすとセグフォる。自分の仮想環境で動かしてもセグフォる。デバッグの時間だ。

  • true_type バグが直った直後の版(bc61624)で実験。落ちるが、依存関係周りっぽい。

  • とりあえず、supplement.sが要求されているときに必ずしもsupplement.cがコンパイルされている保証がないことが分かったので直した。あと、clangでは要らないけどgccだと-no-pieというオプションを付けないと正しく動いてくれないらしい。

  • これでbc61624は動くようになった。あとは手動で二分探索。

  • 結局最新の7fa5d6e (2018/9/21) は落ちる。

  • 23個目のe019375を試す通る

  • -no-pieをつけたときのmacOSのwarningがうるさいので黙らせる

  • なんやかんやして「改行やスペースをトークンとして足す」というコミットが問題を起こしているっぽい。ということでなかったことにする。

2018年10月4日 (Day 59)

お導き

  • TLの迷えるCerである私「なんかセグフォる」「なるほど、ソースコードがめっちゃでかいと確保している領域を超えるので落ちるっぽい」
  • TLの迷えるC++erを救う神「サニタイザーとか使わないんです?」
  • 迷えるCer「オススメのサニタイザーあります?」
  • 神「clang」

使ってみた

  • ということで使ってみたらstableが落ちた。色々見て回った結果バグの原因が分かったので修正。というかspaceとnewlineで落ちたのも多分このバグのせいだな。コピペしてるし。

  • これを直したことにより最新の2つのコミットもバグ取り除いて反映することができた。

make

  • バージョン二分探索はmake test_mixed_compilerだけで行っていたが、せっかく安定化できたのでmake test_all_も安定化させたい。

  • 行った。clangに依存したりする細かいチェックはmake fで行い、make test_mixed_compilermake test_all_はMacでもUbuntuでも動くように書くものとする。

2018年10月5日 (Day 60)

プリプロセッサ

  • #define の何が面倒って、置換後に何個のトークンからなるトークン列に化けるのかが分からないところなんよね。ん?待てよ、2個以上のトークンになるケースって今回の私のCコンパイラにおいてはほぼ無いのでは?

  • ということで、「1個または0個のトークンになる」という前提で#defineを定義すればよい。それで良くなるように2トークンに展開されるマクロを変更。

  • まず空の指令(#のみの行)を処理。次にトークン列が空になる#defineを定義。

  • 最後に、1個のトークンに置き換わる#defineを定義。まあ実は無限再帰のケースを与えると無限再帰するんだけど気にしない。

2回数えている問題

  • lexer周りの各処理、終わる段階では個数が分かっているのにその情報がその次に渡らない。ということで、毎回数え直しているのだが、まあ無駄が多いので長さの情報も提供するようにした。

2018年10月6日 (Day 61)

#include

  • #include だと当然複数トークンになるやん。うーん。

  • #include外のマクロをちゃんと反映しつつ、#include内で獲得したマクロも外で反映しなければいけない。まあ普通にマクロのMapを渡すだけでいい。

  • 相対パスの処理は面倒なのでパス。パスだけに(←は?)

  • とりあえず一応組めた。とはいえプリプロセッサがでかくなってきたので、ファイル分割するべきだろうな

諸ディレクティブ

  • #defineの無限再帰問題を解決した。

  • #elseを実装するの面倒なのでソースコード中から取り除いた。

  • #ifdef #ifndefを実装し始める

  • #defineの後に無駄なスペースが入っていても許容。

  • #endifを実装。

  • 条件が真だったときの#ifdef #ifndefを実装。

  • ENDトークンを特殊扱いするのも面倒なので、必ずソースコードの最後に改行を追加するようにした。

2018年10月7日 (Day 62)

  • 条件が偽だったときの#ifdef #ifndefを実装。

  • コマンドラインオプションでマクロを定義できるようにした。ついでに--lexer-debugは一旦削除。

  • #endifの直後にディレクティブが来た時バグる問題を解決。

  • プリプロセッサ込でセルフホスト!

まだバグ

  • ファイル末に#endifがあって改行がないとバグる。それもlexerで。

  • なるほど。ファイルの最後に識別子があるとバグるけど、C言語の特性上今まで踏んでいなかっただけか。理解

  • 直した。

リファクタリング

  • 読めたもんじゃないので直していく。

2018年10月13日 (Day 63)

  • リファクタリングを続けていく。

  • ディレクティブを扱っている最中のところが「行のどこにいるか?」という情報を持っていて、しかもどいつもそれを書き換えないと来た。ということで二重ループにしてそっちに状態を閉じ込める。

2018年10月16日 (Day 64)

関数ポインタ(コード生成編)

  • 組んでいく。とりあえず型宣言のパースはできているので、ヌルポインタを代入したりすることは既にできている。

  • とりあえずMacでclangにアセンブリを作ってもらう。あとはそれをなるべく既存のgenで書いていく。

2018年10月17日 (Day 65)

  • gen_call_local_fp_and_push_ret_of_nbyte さえ足せば大丈夫そう。
  • codegen.cでvoid返す系の関数のときに面倒になってx64をそのままソースコードに書いていたのを思い出したので、修正。

supplement.c

  • supplement.c は元々、テストケースを扱う上でこっちのコンパイラに足りない機能をclang/gccにやってもらい、それとリンクすることで動作に互換性があるかどうかを確認する、という意図だった。とはいえ、これまで大量にテストを走らせていていて互換性も確保できていそうなので、とりあえずこっちでも読めるやつはセルフで解釈することにした。

2018年10月18日 (Day 66)

関数ポインタ(構文解析編)

  • とりあえず関数ポインタ呼び出しを検出するように。
  • 引数のパースを関数に分離。

2018年10月20日 (Day 67)

  • パーサーを関数ポインタ呼び出しに対応させる。

関数ポインタ(コード生成編part2)

  • 関数のアドレスはr11レジスタにでも入れておいて、それを呼び出すことにしよう。

関数ポインタ(意味解析編)

  • 関数か関数ポインタ以外を呼び出したら型エラー。

  • ここでついに仮引数と実引数間の型チェックを実装。やっとかよ。

  • 実装している最中に7個引数を渡してしまってセグフォしたので、検出するようにした。

  • 関数呼び出しを処理するコードを分離。

枝葉末節

  • 三項演算子の片方にヌルポインタが入ったときの自動変換が欠如していたことにコード書いてて気づいたので追加。

関数ポインタ(総集編)

  • とりあえず (p)(171) と書けば関数ポインタが呼び出せるようになった。

  • (*p)(171) とか (**********p)(171) でも関数ポインタが呼び出せるようになった。

  • 識別子の名前解決を別関数に分離、それを使って (fp)()だけでなくfp()でも関数ポインタが呼び出せるようになった。

2018年10月21日 (Day 68)

  • &関数名 で関数ポインタが取れるように。

  • *関数名 でも関数ポインタが取れるように。これで(******printf)("Hello, World!")をサポート。

  • 関数ポインタの配列も動くことを確認。

テストケース304

  • これだけがsupplement2.cになっているけど、もはやtest_cases.sh自体から切り離したほうがよさそう。

2018年10月22日 (Day 69)

  • シェルスクリプトいじって、

2018年10月23日 (Day 70)

  • ファイル名変更してtest_cases.shから追い出す。あとついでにcompile_filesも2回通すことにした。

2018年10月24日 (Day 71)

関数ポインタ(後日談)

  • 関数名を関数ポインタに格納できるようにした。

  • 「関数なら関数ポインタに変換する」というのを作る。

2018年10月25日 (Day 72)

API整理

  • 現状では、コード生成のところには直にx64を埋め込まず、gen_で始まる一連のAPIを通してアセンブリを書いている。(まあ実はレジスタ名は透けて見えているし、呼び出し規約のあたりがべったり依存しているが)そのAPIがごちゃごちゃしてきたので整理する。

  • ヘッダファイルを見てみたら20個以上はコード生成では直接は使っていない関数だった。ということでそいつらをヘッダファイルから消し、53個の関数になった。

  • gen_logical_OR_part2とかを他のAPIの組み合わせに変換。

  • 80分ぐらい掛けてひたすら関数を並べ替え、そこそこ関数も探しやすくなった。

  • 非公開APIは別ファイルに分離。

構造体と配列

  • 構造体は配列をメンバに持てる(sizeofも正常)けど、配列メンバにアクセスすると落ちることがわかった。まあだいたい原因は見えている。

  • ツイートした解決策がそのまま上手く行った。

  • オフセットが0なら足し算要らないことに気づいたので条件分岐。

  • ポインタ-ポインタ を計算する際にアドレス値をsizeof(T)で割る必要があり、今まで1, 2, 4, 8しか対応していなかったのを一般のsizeにも対応するようにした。