セルフホストCコンパイラaqcc 開発記

セキュリティキャンプ全国大会2018に行って、講師のRuiさんとhikaliumさんのご指導の下、セルフホスト可能なCコンパイラを作ってきました。

事前学習として7月頭から開発を始めたのですが、その際に日記を付けていたので、それを適当に編集して以下に公開します。

諸注意としては

  • 基本的に技術的なログなのでプログラミングを知らない人には(多分)何も面白くない。
  • C言語が読める人はaqccのコミットログと一緒に見ると楽しいかもしれない。
  • C言語が読めない人でも、適当に流し読みすると、C言語コンパイラってこうやって作るんだへーみたいな感想をいだけるかもしれない。
  • 分かりにくいところには適宜編注を入れましたが、基本的に個人的なメモなので読みにくいと思います。ゆるして。

ではどうぞ。西暦はどれも2018年/平成30年です。

7月11日

  • 同じグループのhsjoihsさんが diary.md をプッシュしていてなるほどと思ったので自分も書くことにした。真似師だ。坩堝に書いてもいいなぁと思ったけれどあそこに技術的な文章を載せるのは微妙に違う気がする。セキュキャンが終わった後に体験記的ななにかを坩堝にまとめて書くことにする。
  • 今日までに主要な二項演算子と代入式の実装が終わった。事前にanqoubc(編注:アセンブリが全く読めなくてやばかったので、Cコンパイラ開発を本格的に始める前に鮟鱇が趣味で作っていたコンパイラ型のbc。レポジトリはこのへん。)とかをやっていたのが功を奏して、ここまでは順調。セキュキャン応募が通った時点ではアセンブリ何も分からん状態だったのに思えば遠くに来たもんだ(来てない)。
  • この次は関数の実装をしたい。昨日Ruiさん・hikaliumさんとhangoutsをして、・引数のない関数。・引数の型をintに固定した関数で、引数の個数チェックをしない。みたいな雰囲気で組んでいくと良いということだった。今すぐにでも実装に取り掛かりたいが、残念ながら試験勉強をしないといけないのでつらい。
  • 金曜日くらいに注文したドラゴンブックが今日届いた。読みたいが時間がない。ちゅらい。 1000ページ近くあるしもはや辞書だ。頭から読むと途中で萎えそうだし、興味のあるところを適当につまみ食いするのが良いのかもしれない。
  • この日記をpushしようと思ったけどなんとなく嫌だったのでやめる。ローカルで書こう。
  • 死ぬほどどうでも良いけど、どことなくロビンソンクルーソーの日記に自然と似る。

7月12日

  • 0時をまたいでしまったので既に13日だけど気分は12日。
  • バイトに行かずに家に帰って、1時間だけ開発した後コンピネ(編注:コンピュータ・ネットワークの試験勉強)をやっていた。22時位からもう一度開発。
  • 引数を持つ関数の呼び出しができるようになった。引数を持たないやつは楽でよかったけど、引数を持つやつは結構手間取った。
    • int値を引数として渡す場合8 bytesで渡す必要がある。つまりpushを使わないといけない。
    • 結構ハマった。最終的にコードはきれいになったけど。
  • 次は関数定義ですねぇ。これをすればフィボナッチ数列とかを吐けるようになるので気分が良さそう。
  • 試験勉強しないといけないけど。
  • 実装の話。今の所変数をスタックに割り当てるのはコード生成のフェーズで行っている。でもこれだと、関数呼び出しと変数を本質的に区別できない。今のところは関数呼び出しっぽかったら変数名を関数名として読み替えているけど、関数ポインタが入ると破綻しそう。
  • 解決策としては、変数の情報収集をパーズの段階でやらないとだめのようだ。8ccの実装もそうなっていた。
  • こうなってくると環境(編注:スコープのこと)が欲しくなる。LISPを実装したときと同じようにやればいいのかしら。でもそうすると変数のための構造体が欲しくなるんだけど、8ccだと見たところそういうものは無いんだよな。コードリーディングをする必要がありそう。
  • まぁとりあえず関数定義までは全部グローバル変数扱いでいいんじゃないっすかね。多分。

7月14日

  • 昨日は書き忘れたが、戻り値intで引数なしの関数定義をできるようにした。あとreturn文を実装した。
  • 今日は引数がintの関数定義をできるようにして、条件演算子(三項演算sうわなにをするやめr)(このあたりの話は(編注:Cコンパイラゼミの)Slackでもちょっと話題になっていた)を実装して、フィボナッチ数列を計算するプログラムを通せるようにした。楽しくなってまいりました。
  • フィボナッチ数列を計算するワンライナーCプログラムはC++ではill-formedのようだ。C言語としては合法。
  • ドラゴンブックの初めのところをチラ見した感じ、今CodeEnvのvar_mapで持っているものは「記号表」と呼ぶらしい。やはりパーズのときに作るようなので、今の自分の実装とは異なっている。いまのままだとパーズ時に変数なのか関数呼び出しなのか区別がつかないので、そのうち変える必要がある。
  • assignment exprをパーズする際にconditional exprとどう見極めるかが難しい。いまのところ左辺にはtIDENTが一つしかこないからどうにかなるけれど、そのうち破綻するので方法を考えるなりドラゴンブックを読むなりしないといけない。
  • 明日はif文と!=を実装したい。!=を実装し忘れていたのは結構驚きだった。
  • 明日hangoutsが23時からある。SlackのJSTのよこにPSTが添えられていてなんじゃこりゃと思ったらどうやら太平洋標準時(Pacific Standard Time)のようだ。なるほど。わーるどわいどだ。
  • 今日は線形代数をやった。途中散髪にいったり祖父母家に行ったりしたのであんまりできなかったけど、とりあえずJordan標準形のお気持ちを理解した。やばい。この三連休でどうにかしないといけない。

7月15日

  • 午前中勉強して、昼ご飯を食べてから1時間ちょっと開発した。
  • if文を追加した。!=はすでに実装されていたけどテストがなかったので追加した。
  • if文を追加する過程でcompound statementが文として捉えられていなかったので訂正した。
  • Cの仕様をちゃんと読んでいないけれど、compound statementで新しいスコープi.e.環境ができるという認識で正しいのかしら。それだと関数の仮引数はその環境の外にあるということになる。
  • if文みたいなのが出来てくると意外といろんなことができて楽しい。スコープが無いのは悲しいのでさっさと対応させたい。連日考えているようにやっぱりそれは記号表をパーズ時に作るのと同時にやりたい。
  • ところでparseってパースなんだろうかパーズなんだろうか。Ruiさんはパーズと読んでいたのでここでもパーズって書いているけど、自分はずっとパースと読んでいた。
  • びっくりするぐらい暑い。12時位からクーラーを付けた。やはり去年エアコンを家に設置しておいて正解だった。今年は強力なサーキュレータも買ったので設定温度28度で結構いい感じに涼しくなっている。この設定温度が高いのか低いのかよく分からんけど。そもそもこれは何の温度なんだ。
  • そういえば昨日hsjoihsさんからPRが来ていて焦った。しかも送られていたのは2日前だった。インクルードガードがまずっているという内容だった。特に問題なさそうだったのでmergeした。 hsjoihsさん人のレポジトリまでよく見ててすごいなぁという気持ちになった。
  • 23時からミーチング。もっと気軽に質問してほしいとのこと。質問ってどうしてもためらうんですよねぇ。このあたりはYahoo!知恵袋で叩かれた()若き頃の記憶のせいかも知れない。ドラゴンブックを読んでも分からなかった記号表のこととか聞いてみよう。以下議事録。
    • このあとは制御構造を増やすと良いとのこと。whileとかforとか。do-whileは避けていいらしい。あとgotoも避ける。
    • floatは避ける。まじか。anqoubcでさっさと実装したのはまずかったようだ。
    • 構造体を入れるといいらしい。あとポインタをいれる。配列とポインタらしい。構文的にも分かりやすいしコード生成も分かりやすいようだ。
    • 今はintしかないので型がない(Bみたいなもんか?知らんけど)。型的な何かを導入して、配列名がでてきたら配列の先頭ポインタとして読みかえる。コード生成はアドレスそのものをmovすればよい。間接参照をする場合は、スタックトップのアドレスをロードしてきて、それが指す値をロードする。mov二回。
    • 型はintかint*だけでいい。でも配列を足すと配列の配列が作れるようになるから、無限の長さのものを扱う必要がある。配列やポインタを扱うためにはポインタ型を使う。「ポインタ型」「配列型」だけを用意して、そこへのアドレスをもたせる。指して居る先を見ると何かが分かる。
    • とりあえず一段のpointerを実装すればよい、けれどintとかが今のままだと読めない。ので、変数の宣言を先に実装すると良い、かもしれない。
      1. intの次は変数名が来る。初期化式無し。
      2. intの次に*が来る。
    • Cの構文の面倒なことは、2-tokenから決まる型が面倒。long static longは合法らしい。へー。とりあえず今のところは1-tokenの型だけ読めばいい。long static long const int a;も合法らしい。へー。
    • long intは許さないでlongだけを許す。shortも同様。
    • compound stmtのスコープは普通に環境をLinked Listにすればいいらしい。まぁそうだよね。むしろlexerかparserのどちらで記号表を作ればいいとか聞けば良かったかな。 PCのファンから異音が出ているのでちょっと怖くなってそれはやめた。80度だ。
    • hikaliumさんのCコンパイラはレジスタマシンらしい。レジスタマシンってなんだ。
    • 今の所凄く楽しいし、コンパイラ作るのってそんなに難しくねーな?とか思い始めているけど、どう考えてもRuiさんのマイルストーンが上手いんだよな、などと気づいた。すごい。徒然草は正しかったんだなぁという話かも知れない。「先達はあらまほしきことなり」。
  • hangoutsおわり。今日は寝る。

7月16日

  • さて今日は型の構文かぁ、おじちゃんはりきっちゃうぞー(@ksuenagaさん風)などと思いながら Slackを開いたら、どうやら制御構造を先に足したほうが良さそうだったので、whileとbreakとcontinueを足した。 breakとcontinueは微妙に実装に迷ったけどとりあえずこれで。
  • CodeEnv内でラベルと記号表と管理しているわけだが、これでどこまで持つんだろうか。今の所実用的な問題は出てないんだよなぁ。
  • 昨日寝る前に8ccの実装などを見ながら記号表をパーズ時に作る算段を付けていた。一応できそうではあるが面倒。
  • 線形代数がとりあえず終わりに近づいている。今日は線形代数を終わらした後で確率論やらE1の中テスト(明日)対策やらをやらないといけない。忙しい。今の所Cコンパイラに関しては1日1コミットの目標を守れているので満足。

7月18日

  • 昨日書き忘れた。確かfor文を実装した。for文をwhileに書き換えることで実装しようとしたらcontinue文の処理で詰まってしまって出来なかったので、仕方なくfor文専用のコードを付けくわえた。 Ruiさんによるとそれでいいとのこと。下手に一般化しないほうが良いらしい。なるほど。多分ラベルとgotoのレベルまで抽象化(というより具体化?)すればfor, while, do-while, gotoあたりはまとめられると思うけど、まぁおいおい。
  • それでfor文の3つめの式にi++とか書きそうになったわけだけどインクリメントを実装していなかったので実装した。前置と後置の違いはinclとpushqの順番だけだった。興味深い。
  • 以上を昨日やって、今日はint a;といった変数宣言を読み込めるようにした。これが大変だった。同じ名前の変数が宣言できるとまずいし、宣言していない変数が使われるのもまずい。この処理は従来通りコード生成の部分で行うことも可能だったかもしれないけど、そうすると変数宣言をパーズする意味がなくなるし、後々、式に型を与えるのがつらくなりそうだったので、前々から思っていた「記号表をパーズ時に作る」ようにした。そうするとかなり大規模にコードを書き換える必要があったので大変だった。結局実験(編注:「計算機科学実験及び演習」という授業)の時間を全部とかして、しかも45分くらい延長してから帰宅した。後半はコンピネをやるつもりだったのになぁ。仕方がないから帰りの電車の中でやったけど、途中で寝た。
  • intを3時間位かけて読み込ませた後、スコープと言うか環境を作った。変数の情報を持つMapをトラバースする方法がなくてつらかったけれど、よく考えるとMapとVectorの両方を持たないといけないことに気づいた。すなわち、関数の環境と、スコープ(compound stmts)の環境は別だっていうこと。ということで少し情報が重複してダサい実装になっているけど仕方がない。本質的に8ccとこのあたりは同様。というかあれのコードを見て実装したので自然と似る。段々とaqccが8ccの劣化コピーになってきていていやだなぁと思っている。
  • 8ccはグローバル変数とstatic変数の使い方がうまい。C++とかを普段使っていると(?)グローバル変数は理由なく悪という気分になってくるし、実際現状のaqccはグローバル変数を使っていない。でも並列処理とかをするわけでもないんだから必要なところは適宜使ったほうが、結果的にコードが短くなるのかもしれない。8ccだと、グローバル変数にアクセスする関数を制限していて、見通しが良くなっている。
  • lccとかもちょっと見ようと思ったんだけど、かなり読みにくかった。Cコンパイラとして8ccはかなり読みやすいというのは事実のようだ。すごいなぁ。あとpccも見たかったんだけどDLする場所が見当たらなかった。
  • 帰ってから電電回路のレポーヨを作った。わくわく鮟鱇ランドで@rocoに助けてもらった。全然勉強してない。やばい。

7月19日

  • 行きの電車の中で関数定義の中にintを書けるようにした。つまりint fib(int n){...} みたいに書ける。

7月20日

  • 昨日はその後帰りの京阪が人身事故で止まっているスキにポインタを扱えるようにした。
  • *a=b; みたいなコードを通すのに苦労した。とりあえずunary-exprとして読んで、その次に=が来ているかどうかで分岐して、来ていなければunary-exprを読む前の状態に戻って、みたいな実装をした。しかしこれLLかね?
  • いつのまにかGoogle Doc(編注:Ruiさんのテキスト)がめっちゃ増えていた。読んだ。掲示板の方にも貼ったようだ。
  • で、今日は一日中微積やら確率論やらをやっていたため進捗は無し。来週いっぱいはこういう日が続きそうだ。
  • RuiさんとHangouts. 色々と実装上の指摘をいただいた。
    • エラー出力にトークンを出力。
    • test.cをtest.incにしてもいい。
    • aqcc.hには不完全定義しかかかないほうがいい。VectorやMapなど。
      • これはもともとtest.cとかのためにこういう実装にしたんだけど、今の状態だとそれでも動きそう。
    • #pragma once は特に必要ない。
      • #pragma once はAppleしか使ってないそうな。へー。
  • あんまり指摘がなかったので良かった(?)
  • みんなグローバル変数を使っていないらしい。グローバル変数は悪っていう風潮だかんねぇと思ったり思わなかったり。
  • 今後の実装の話。typeにバイト数をもたせる方がtype2byteとかいう謎の関数を呼ぶよりいいと思い候。構造体とかも楽に書けるし。多分。
  • TY_INTとかは一々newするのがアホらしいので、get_int_type()みたいな関数を作って、static変数のアドレスを返すようにするつもり。
    • この辺りも8ccの影響だかんねぇ。
  • エラー出力にトークンを合わせて出力するのは一筋縄では行かないのでとりあえず放置。 enum 周りに関して全部intで取り扱っているのはどうにかしたいと思っていたりする。でもCの列挙型対応って確か不十分なんだよね……。ちゃんと把握してないけど。
  • 文字列リテラルまでちゃんと実装した暁にはアレしたい。Sudoku Solver.

7月21日

  • 朝から確率論をやっていて、今JFR(編注:情報符号理論)に移行した。思い出したので書き留めておく。今の関節参照の実装がまずい。 **a=b を正常にコンパイルできない。 *があるときの代入式のコード生成を変える必要がある。つまり、 ast->lhs のコードをダンプした後、それをpopして、そこのアドレスを使うようにすれば良い。簡単にできる変更だがまだやっていない。
  • 代わりに今日Slackで少し話題になっていた%rspが16バイト境界にないといけないというのを実装した。でも8バイトでも関数呼出しが出来ているのでよくわからない。
  • JFRやばい。やばいよー。たんいのおとぉ!
  • 上で書いたpopして云々はすでにやっていた。その代わりunary exprのパーズがまずっていたので訂正。**x=y; が動くようになった。
  • 今日はこれだけ。開発時間5分。

7月23日

  • 昨日の記憶はない。(編注:7月23日はJFRの試験日)
  • 帰りの電車の中で少し開発、というほどのこともしてないけど。int*が戻り値やら引数に渡せないので直したいが、そこまでの時間はない。
  • parse_parameter_list()がちゃんとparse_type_name()を呼ばないのでうまく動かない。直すにはFunctionDefinitionのときの ASTのparamに型情報をもたせる必要がある。今は名前しか持ってない。どうするのが一番スマァートかねぇ。
  • parse_parameter_list()の時点でAST_VARを作るという考え方もあるけど。それはまずいか?再帰ができないからまずいな。
  • となると適当なPairをもたせる以外に無いかもしれない。VectorにVector持たせてもいいけど。

7月26日

  • ここ3日の記憶はない。(編注:7月23日〜26日は試験日)Slackを見るたびにSinya Katoさんとhsjoihsさんがめっちゃ進捗を産んでいてつらかった。
  • まだ試験は残っているけれどとりあえず一段落。プログラムを書くぞ書くぞ。
  • 上の日記を見る限りでは int* とかを引数に渡していきたいようだ。なるほど。
  • int *を引数に渡せるようにした。Pairとかいう構造体を作ったりしたのでちょっとアドホックだけどまぁこれはこれで。
  • return *test(&x);と書きたかったが書けない。これを書くためには関数呼出しの型をちゃんと決めないといけない。そのためには関数のリストを探索する必要がある。つらいな?
  • これに対応させようと思ったら、外側にあるret0()とかで戻り値が分からずに死んでいる。んー。でもそれならエラーメッセージがほしいなぁ。
  • 適当にintに推論するようにして実装した。関数の戻り値の型が、関数を呼び出す式の型にちゃんと反映されるようになった。

7月27日

  • ポインタ演算を実装していく。Google Docにはめっちゃざっくりしか書いていなかったので、実装で悩む。とりあえずコード生成のときに型を見て適当にやる感じでいいかな。どうせ加算と減算しか無いし。
  • int*を返す外の関数を呼べるように関数宣言を作った。このあたり回避方法は死ぬほどあるけど、まぁそんなに実装的につらくなさそうだった。実際辛くなかった。
  • 帰ってきてから夜なべして(っていうほどでもない)ポインタ演算を実装した。結構汚くなってしまったけど、まぁこれはこれで。
  • コード生成に全てを押し付けているけど、ptr + int, int + ptr, int + intでASTを分けたほうがいいのかしら。微妙なところ。指摘されたら直そう。どのレベルでASTを作ればいいかという問題はなかなか奥が深い。
  • 明日は配列をやりたいけど、DBのおべんつよをやらないといけない。

7月28日

  • 全然おべんつよをやらずに配列型を実装した。多次元配列はやっぱり手間取ったけどとりあえず動くものが出来た。配列のポインタへの変換とかめっちゃ適当やけど、まぁそれはポインタ演算もそうなのでア。
  • [] による添字アクセスを実装。めっちゃ適当な実装だけど、実質24行の増加で実装できるのはとても興味深い。
  • 今日はここまで。明日はグローバル変数を作りたいけど、さすがに勉強しないといけない(n回目)。

7月29日

  • 昨日あのあとRuiさんから「構文解析のところわちゃわちゃしてるから型変換とか別のパスにしたほうがいいかも」って言われたのでそれを実装した。
  • 意味解析を分離っていう風に合言葉にしたけど正しいんだろうか。まぁいいや。
  • DBをやる。結局全然できてない。

7月31日

  • 昨日は+=とかを実装した。<<=の字句解析の実装で勘違いしてアワアワしたりした。
  • 今日は京阪電車の中で夏季投稿大会のお知らせを投げた。楽しい。どのくらいの人が参加するだろうか。自分の記事はセキュキャン周りにするつもり。このdiary.mdをちょっと改変して投げても良いかもしれない。

8月1日

  • ついに7月が終わってしまった。はやいねぇ。テストも明日で終わり。まだ何の勉強もしてない。
  • 昨日はあの後グヨーバユ変数を実装した。テキストのコードがそのままでは動かなかったので難儀した。結局.data.textを適宜入れていなかったことが問題だったようだ。GCCとかだと.commというよくわからんものでグローバル変数を実現している。Ruiさんから説明されたけどいまいちよくわからんかった。このあたりは自分で手を動かして確かめるしか無いようだ。ネットにもそういう記事があったので、機会があればちゃんと調べたいなぁ……今がその機会かもしれない。
  • 今日はchar型を実装した。正確に言えば昨日から実装は初めたのだけど、上手く実装する方法が思いつかなくて今日になった。 charというのは1つの独立した型なのだけど、実際にCのなかで扱われるときはほとんどintと変わりがない。 1バイトを頑張って読み込んだり書き込んだりさえすれば、あとはintとして扱っても問題ないようだ。それを実現するのにAST_VARのところでchar2intをかまそうとしたんだけど、よく考えたらAST_ASSIGNの左辺に変数があるばあいでもAST_VARが呼ばれるので、それだと「左辺値じゃないよ」エラーが出て怒られる。つらかったが必要なところ全てにchar2intをかますことでどうにかした。実際sizeof(ch)みたいな式を評価することを考えてもこっちのほうが良いとは思う。
  • movsblを使って読み込まないとだめだよーと書いてあったので素直にそうしたんだけど、でもいまいち問題がどこにあるのかよくわかっていない。intを介さないような実装であればmovbだけでもどうにかなるんじゃないのかなぁ。分からん。あとmovsblのインターフェースが個人的に謎だった。byteを移動させてるはずなのに32bitで受け取るとはこれいかに。
  • そういえばドメイン移管の手続きが途中で止まっているとさくらインターネットからメールが来ていた。返信が必要なメールなんて初めてだ。さっさとやらないといけない。
  • あとCDがArchLinuxでマウントできなくて死んだ。なんぞこれは。
  • さて計数(編注:計算機科学のための数学演習)をやろう。

8月2日

  • 試験終わり! 計数の最後の問題が解けなかったことに心残りはあるけどまぁいいや。
  • AT&TからIntelにスイッチする?みたいな話がSlackで行われていたが、結局AT&Tのままになった。みんなIntelのほうが好きで、AT&Tが好きな人は一人もいなかったことが面白かった。
  • さて今からsizeof演算子を実装してから文字列リテラルを実装する。8クイーン問題までもう少しだ。
  • sizeof演算子を実装。AST_NOPが役立った。
  • 文字列リテラルを実装。printfとかを呼ぼうとするとよくわからないリンクエラーが出る。以前のanqoubcを思い出して、リンク時に-no-pieをくっつけるとちゃんと動いた。が、釈然としないのでSlackに投げようとしたら、先にShinya Katoさんが投げていた。
  • 結局-no-pieをつけるか@PLTをつけるかだった。ほーん。

8月3日

  • 朝から文字列リテラルの実装を変更した。グローバル変数として文字列リテラルを持つことでいい感じになった。
  • 23時から個人ミーティング。hikaliumさんに「我々の仕事がない」などと言われながらも色々と指摘をうけた。こういう経験殆ど無いので新鮮。
    • エスケープシーケンスはsizeofでバグるのでちゃんと数えよう。
    • 何かサンプルのソースを書く
      • 電卓、はテストとしては不適?
    • 文字リテラルはint. 実装は楽。
    • 行とカラムをトークンに足す。それをエラー出力として利用する。
      • token -> strの関数を作って、トークンの種類と行とカラムを出力する。
      • 文字列全部読み込んで文字列にしたほうが楽。StringBuilderを利用。
    • forをwhileで実装する
    • 変数にアクセスする場合は全てそのアドレスを基底にすると、構造体とかでいい感じになる。
    • アセンブリコメントを出力すると見やすくなる。
    • 次は構造体
      • 親のオフセットに子のオフセットを足す。
    • アロー演算子はパーザで置き換え。(*a).b
    • enumはint
    • switchはif-else if
      • Spectreの脆弱性があるよ!
    • cast
      • 型を読み替えるだけでいいはず。
    • va_args
      • ABIを見よう!
    • コメントを実装。
      • 1トークン先読みでできるはず。
  • 個人ミーティング終了。sizeofをAST_INTに書き換えるやつだけやって寝る。

8月4日

  • 昨日指摘された点を修正。unexpected errorを吐く時にソースファイルの行数と列数を出すようにしたり、エスケープシーケンスを自前で処理することでsizeofに対して正しく返すようにしたりした。
    • sizeof(“abc”)ってあんまり書かない(書く必要がない)けど、これが動くっていうのは、ちゃんと文字列リテラルがcharの配列になっているっていうことを如実に表していて面白い。
  • シングルクオートで文字を書けるやつを実装。integer character constantと言うらしい。仕様によると複数文字が入っている’abc’みたいなのの値は処理系依存だそうだ。へー。とりあえず一番始めの文字だけが効力を持つようにした。
  • シェルスクリプトで書いていたテストをCに移行! 死ぬほど実行が早くなった。やばい。書き換えるに当たってVimで置換して機械的に置き換えたら、かなりの数のテストが動かなくなり焦った。前のテストからそのまま続いて次のテストが実行されるため、スタックがクリアされるわけではない。それで新たにバグが明らかになったようだった。修正を入れたらちゃんと通るようになった。
  • 今日は落ち穂拾いの日だなぁ。
  • 昨日forをwhileで書き直す話が出たのだけど、よく考えたらwhileをforで書き直せばいいのではという話に思い当たったので実装。analyze_ast_detail()も戻り値でもとの値を置換することを徹底していなかったせいでバグが出た。まぁバグを潰せたのでよし。置換はうまく行った。次はswitchだ。
  • switchの実装が死ぬほど面倒。基本的にgotoに皮をかぶせたようなものっぽいので、手抜き実装をして、gotoを実装したあとに戻ってくるのが一番良さそうだ。
  • 手抜き実装ですら面倒なので諦めた。gotoをさっさと実装しよう。

8月5日

  • なんだかんだswitchとgotoを実装した。一度方針を決めて書き出せばそんなにはつらくなかった。ラベル生成を統一してもコードは汚いが、より良いものは思いつかないのでとりあえず放置。 gotoとlabelをASTレベルで作ればifとかforとかを消し飛ばせるのではと思ったけどそうでもない。まぁこれはこれでいいのかも知れない。
  • gotoの仕様がひどい。ラベルはローカル変数やら関数名やらとバッチングしても何の問題もない。つまりラベルをそのままアセンブリに吐き出すことは出来ない。仕方がないので適当なラベルに置換。そうすると、先にgotoが出てあとからラベルが定義されるソースに対応するのが面倒だった。関数内でしかラベルが使えないっていうのは実装を楽にするという意味でも妥当な制約だった。
  • さて次は何をしようか……。Shinya KatoさんがNクイーンを実装していて、Twitterでたくさんいいねがついていた。いいなぁ。
  • 構造体の実装に向けて、AST_LVAR/GVARをアドレスpushの命令とするように変更しようとしたが断念。かなり面倒。いま意味解析では変数が左辺値か右辺値かというのは全く考慮していないから。 30分ぐらい考えて、これを実装しなくても構造体の実装には問題無さそうに思えたのでとりあえずこのまま放置。さっさと構造体を実装しよう。
  • @hiromi_mitiによるとMinGWでaqccが動かないらしい。吐く_test.sがLinuxとMinGWで異なっているそうだ。謎。
  • castを実装しようかと思ったがまともなテストケースが書けないので断念。int*をintに変換しても情報が落ちるのだ。
  • 構造体を実装!!! sizeofに対して期待通りに動いている。嬉しい。パーズがくそ雑なのでどうにかしたいが、とりあえず動いている。
  • 演算子.やら->やらを実装した。つらかった。変数のアドレスを起点としてコードを生成するように書き換えるのがとてもつらかった。特にAST_INDIRとAST_ADDRの実装で悩んだ。が、その過程で面白い発見をした。 AST_INDIRとAST_ADDRは、コード生成としては、自分が持っているアドレスをそのまま出力するだけだ。こいつらの役目は主に意味解析にあって、AST_INDIRはrvalueをlvalueに変換し、AST_ADDRはlvalueをrvalueに変換する。上でバグらしていた主な原因は、既にlvalueになっているASTをAST_INDIRが持っている場合には、一度lvalue2rvalueをかましてからAST_INDIRしないといけないということだった。面白い。
  • ネスト構造体を実装。無名構造体 in 構造体とかがちゃんと動くようになった。楽しい。
  • Slackに投げたら「はやいねー」という感想をもらった。そら開発時間14時間越えてますからね今日。
  • 昼に実装が煩雑になりそうでやめたdeclaratorの実装が、実はそんなに煩雑でもないかもねという話になった。そうかもしれない。明日ヒマがあれば実装してみよう。
  • そういや今日の開発の途中でerrorが__FILE____LINE__を吐くのは無意味ではないかと思い始めた。どうせerrorでbreakpointを設定すれば全部辿れるのだ。あとASTにline, columnが無いのはつらいのでさっさと実装しよう。適当なトークンから引っ張ればいいはずだ。
    • いやそう単純でもないな。とくにanalyze. うーん。

8月6日

  • 朝からパーザを書き直す。Annex AのBNFに従って構文解析するように書き直した。これに5時間くらい溶けた。つらい。
    • ただこれのおかげで「ポインタの配列」が扱えるようになったり、カンマ区切りで変数宣言ができるようになった。
  • 細かいところを直す。構造体のポインタを返す関数に矢印をはやせるようになった。
  • N-queenをさっと書こうと思ったら、まずN-queenが書けなくて死んだ。やっとこさ書いたらこんどは動かない。論理否定演算子!を実装していなかったり、if文のcondにlvalue2rvalueをかましていなかったりした。直したら動いた。デクリメントが無いのは-=でどうにかした。
  • 日記を書きながらwhileとforにもかましていないことを思い出したのでかました。
  • 日記がここで400行。テストはさっきtest300を越えた。

8月8日

  • Ruiさんの指摘をもとに、テストをマクロで書くことで、期待されている値と実際の計算との距離を近くした。これの移行をする時にエスケープシーケンスの処理がまずっていたので訂正。isprint()にかけてfalseのやつだけを見ていたんだけど、これだとダブルクオーテーションをエスケープできないという問題があった。
  • コンマ演算子を追加。これでfor(i = 0, j = 0; …)とかが書ける。 AST_EXPR_LISTというASTを追加して、これで格納するようにした。
  • for文の節1に宣言を書けるようにした。これでfor(int i = 0;…)とかが書ける。これの実装に当たって、parse_declaration() の戻り地をAST *にした。もともとはVector *だったんだけどさすがにそれだと扱いにくかった。 AST_DECL_LISTを追加してこれで格納するようにした。すこし冗長だ。analyzeが一つのAST *を複数のAST *に変換できるように拡張すれば、コード生成で消し飛ばすことが出来る。要検討。
  • CodeEnvをグローバル変数に移行。大昔、まだコード生成で意味解析(変数の出現とか)を管理していた頃は、 codesをswapすることでいろいろやっていたので、そのときはCodeEnvを別のものにするという処理が必要だったのだけど、いやよく考えたら当時から要らなかったかも知れない。とにかく一つのCodeEnvインスタンスがあれば十分なのでグローバル変数にした。ついでにcodesなんて英語にないよ問題を解決。

8月9日

  • 朝から開発。今日は一日aqccをやる予定。
  • typedefを実装したいが、そのためには不完全型の実装を、あれ、Cに前方宣言とかあったっけ?という気分になったのでとりあえず実験。結論としてCに前方宣言はない。宣言していない型でも、とにかくポインタにしておけば使える。そしてこの挙動はすでに実装済みだった! 結構びっくり。テスト書いたら動くのだもの。そんな実装した覚えがないのに。種明かしとしては、ポインタ型の場合はanalyze_type()の本チャンルーチンがそもそも起動しない。で、->なりなんなりでポインタが外れたときにだけルーチンに入るが、そのときには構造体はすでに定義されているという寸法。よく考えられてるもんだ。
  • typedefを実装。長く辛い戦いだった。Ruiさんがtypedefは簡単だっていうから気軽に実装を始めたら3時間半くらいかかった。ただそのおかげでクリティカルなバグをいくつかつぶすことができた。
      • いままでanalyze_type()は構造体だけを相手にしていたが、それだとtypedefで「構造体の配列」みたいなのを持ち込まれた時に対応できなかった。それで全ての型について適当な処理をするようにし、再帰的に処理するようにした。
      • AST_EXPR_LISTのパーズで手抜きをしたために、すべての式はEXPR_LISTみたいなことになっていたが、これだとlvalue/rvalueまわりでバグった。具体的にはEXPR_LISTはかならず全ての式にlvalue2rvalue()を施すため、(*b).aみたいな式が動かなくなっていた。これがいままで動いていたのはgen_movにバグが合って、nbytes == -1でエラーになるのではなくコードが生成されない(!)ためだった。 gen_movにassertを入れて、全てをEXPR_LISTにするのではないようにした。でもよく考えたらこれが本質的な問題じゃないな……。謎。
      • 途中でとてもつらくなったし、自分がどんなコードを書いたか憶えていない。つらい。
      • これを書きながら確認したらやっぱりバグっていた。次のようなコードが通らない。直さないといけないがどうなおしたらいいかなぁ。
        int test323()
        {
            struct A { int a; };
            struct A a;
            struct A *b = &a;
            (1, *b).a;
        }
  • そうか、AST_EXPR_LISTの最後のexprだけlvalue2rvalueを書けなければいいのか。本当に?
  • 昼ご飯を食べながら考えよう。答えはある。
  • lvalue2rvalueをかましているのがそもそも間違いな気がしてきた。
  • EXPR_LISTがlvalueとして認識されるべきかどうかを決めないといけない。
  • 何かがおかしいと思ったら、EXPR_LISTがlvalueかどうかは一番最後のEXPRが決めるっていうことだ。そういうふうにis_lvalueを書き直したら動いた。ばんばんざい。
  • ご飯を食べてから前置後置デクリメントを実装。まだ実装してなかったのだ。
  • いまの実装だと(1, a)++が通ってしまうが、これは規格的にはダメ。EXPR_LISTに対してis_lvalueで対応しているのがまずいので、これを.演算子のほうにうつす。 a.bのaは規格的にはrvalueなのだろう多分。実装上はlvalueの方が便利だけど。
  • デクリメントとfor文始めの宣言を実装したのでこの前書いたNQueenがもう少し簡潔に書けるようになった。そのままexamples/nqueenに突っ込んでcommitした。
  • ここでなんとなく日記を見返した。楽しい。
  • 前から気になっていた部分をいくつか修正。
    • utility.cに入っていても、一つのファイルからしか使っていないやつは移した。正直このファイルわけというのは面倒で、どこに何を置けばいいかよく分からん。
    • ついにerror()の__FILE__を消し飛ばした。前にも書いたかも知れないけど、どうせ error()からbacktraceすれば全部見える。error()のファイル名と行番号だけは吐くようにした。
    • 構造体メンバのアラインメントを求めるアルゴリズムを変更。めっちゃ指摘が厳しいけどめっちゃ詳しいサイトを読んでもよく分からなかったので、GCCに実際に突っ込んで見ながらアルゴリズムを特定した。構造体のネスト三段階に配列を組み合わせたものに対して正しいsizeofが帰ってくるので、多分合っているだろう。

8月10日

  • 昨日はあの後do-whileを実装し、キャストを実装し、 voidvoid * を実装し、unionを実装した、らしい。へー。
  • 今日は朝からスタバWifiで開発をした。いろいろ変えるとstring_builder.cがコンパイルできることがわかったので、いろいろ変えなくてもコンパイルできるように頑張った。まだできてないけど。
  • とりあえず全ての関数定義に.globalをつけるようにした。あと浮動小数点がないのでroundup()を改造。 Ruiさんがハッカーのたのしみから持ってきたコードがすごかった。よく分からんままコピペしたら動いたのでウォーっていう気分。結局よくわからんままだ。あとsize_tを使っていたところをintに変えたり、constを読み飛ばしたりした。
  • enumを追加。intに置き換えればええやろと思っていたが、それだと重複定義の場合などにちゃんとエラーが出せないので structやunionと同じ扱いにした。意外と面倒だった。
  • 関数引数に...を書けるようにした。今の所関数引数のチェックは虚無なので何をしても問題ないが、現状のコードを読むためには読み飛ばしでもいいから実装が必要だ。
  • あともう少しでaqcc.hが読めそう。これが読めれば make self としてセルフコンパイル(できるところを)するようにする。
  • これから個人ミーティング。多分これで最後だ。
  • 昨日Twitterに上げた「C++完全に理解した」名刺が生涯で一番のヒットをしていた。すごい。多少後悔もあるけど。
  • 以下議事録。
    • Noreturnは読み飛ばし。FILEはポインタとして使うから大丈夫。va_argsはやればできる。
    • va_argはパーズでビルトイン関数として読む。マクロがあれば別だけど。(int *)0みたいにして渡せる(?)
      • 関数呼び出しではレジスタをスタックに突っ込む。
      • va_startはそのポインタをどうにかこうにかする。
      • ABIを見よ。
      • 昔は関数だったんじゃないかな。
      • 関数プロローグでどうにかすればいい。
      • 意外と可変長引数関数呼び出しはコストが高い。
      • va_startも組み込み。
    • aqcc.h以外の方が早いのでは。そっちからコンパイルしてみたい。
    • 引数なしマクロは簡単なのでさっさと実装する。
      • トークナイザの改造だけでどうにかなる。
      • トークないず→ぷりプロセス→ぱーず
      • とーくないずではhashとnewline-characterを1つのトークンにする。
    • #includeだけを実装してみる。
    • 継続行はプログラム処理上のパスとしてまっさきにやる。
      • どんな処理よりも「強い」
      • 2つのポインタをもって、read/writeをやる。
      • 継続行はやばい。
    • _Boolはやばい。
      • 小さい整数型ではない。
    • make selfをする。
      • フランケンビルドをする。
      • gcc -c ... を使う。
      • 別のファイル名にすると良い。
      • self かつ test は適当に書く。
    • トライグラフは実用的に使っているのを見たことがない。
      • IBMのEBCDICぐらい? IBMのコンパイラ独自拡張にすればいいのに。
      • アンダーバーがない(代わりに左矢印がある)Zerox Altoで作られたSmalltalkはキャメルケース!?
    • ここまでで実質6200行くらいですねー。(編注:多分これは数え間違い。8月21日時点で6000行程度。この当時は4000行ぐらいだったのではないか。)
      • 大体6000行〜8000行くらいでセルフホストできるという印象。
    • 来週にはセキュキャンですねー。よろしくお願いします。

8月13日

  • 昨日も開発をしたが日記を書き忘れた。何やったっけ。
    • 引数なし#defineとか#include “…”とか継続行とかを実装したらしい。へー。
    • あとstaticなローカル変数を実装した。
  • 今日はexternを実装。
    • static共々、ポインタやら配列やらのときにちゃんと情報が伝播してなかったので修正したらtestが通らない。
    • 期待するアセンブリを吐いているのに挙動が期待したものとちがうというよく分からんことになってつらかった。
    • 結論としてはAST_LVAR_DECL_INITのgenでやっていたpopがまずかった。いままで必要以上にpopしてたのに動いていたのは謎だ。 ASSIGNがrhsに入っている場合のみpopするようにすれば治った。
  • これでaqcc.hが通るようになったので満を持してセルフコンパイル。
  • びっくりするぐらいうまく動いた。わけがわからない。aqccでまだ対応していない#ifを入れてエラーを吐くのを確認したり、 aqccとaqcc_selfの両方でtest.cを食わせて結果をdiffしたりしたがうまく動いている。やばい。
  • 結果7ファイルのセルフコンパイルに成功。短くて簡単なやつはだいたい出来たことになる。やばい。
  • わくわく鮟鱇ランドで「セキュキャン中なにするんや」と煽られた。それはそう。やばい。
    • まぁ引数付きマクロとかあるしね。
  • 明日はセキュキャンの準備等しないといけないのでアだが、今週中にはちゃんとセルフコンパイルできそうという希望を持った。

8月14日

  • 可変長引数の実装を初めたが、よく考えたら va_start()va_end() だけ実装したらいいことに気がついたので、実際のgccの出力やらABIやらをみながら実装した。バグらしたが割と楽だった。
  • 関数引数のparameterの配列→ポインタを実装。
  • 通らないところを書き直したりコメントアウトしたりしてセルフコンパイルできた! やったぜ。
  • 「セキュキャン0日目にセルフコンパイルしました!」とかって流そうかと思ったけどさすがにアだったので#seccampだけつけて流した。全然反応がないので悲しい。まぁいいや。寝よう。

余談

たのしみ。

追記

Twitterで少し指摘を受けたので。

  • aqccはRuiさんの作成されたセルフホストのCコンパイラ8ccの影響を大変受けています。
  • 7月11日の項にもあるように、この日記はhsjoihsさんの日記死ぬほど影響されて書き始めました。
  • そもそも私がCコンパイラを開発するということに興味を持ったきっかけは、Ruiさんが8ccを開発された際に書かれた日記に依るところがめちゃんこ大きいです。

ご参考まで。

諸悪の根元。サイト管理者。C++が好き。とんでもないアホ。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする