以前に8ccというCコンパイラをゼロからひとりで開発していたときのログです。40日でセルフコンパイルできるところまで到達しています。日付はすべて2012年です。コードとヒストリはすべてGitHubで見れます。
3月4日
というわけでコンパイラを作っているわけだけど、1000行くらい書いたらそれなりに動き始めてきた。こんなのも動くし：
int a = 1; a + 2; // => 3
こういうのも通る。
int a = 61; int *b = &a; *b; // => 61
文字列は文字の配列として扱っていて、配列をポインタに成り下げる振る舞いも実装しているので、こういうのも通る。関数呼び出しもある。
char *c= "ab" + 1; printf("%c", *c); // => b
前回もこのあたりはがんばって実装したからここまで作るのはわりと単純作業かも。二回目だから配列とかポインタの扱いとかがうまくなっている気がする。
3月11日
Cコンパイラの作業が進んで自分でもびっくりするくらいマトモに動くようになってきた。Nクイーン問題を解くこの程度のコードはコンパイルできてきちんと動かせられる。
実装は素朴なもので、変数をレジスタに割り当てたりといった難しいことはしておらず、マシンスタックを使ったスタックマシンにコンパイルしているだけ。何をするにもメモリアクセスが発生するけど当面はこれでいいでしょう。
最初は整数一つを読み込んでコンパイルするという20行程度の単純なコードから出発したんだけど、書き換え続けていまは2000行くらいある。Gitのログをみてみるとこういう順番で機能を追加していったぽい。
- +, -追加
- 構文木を作ってパーズとコード生成フェーズを分離
- *, /追加
- 変数をサポート（暗黙で全てint扱い）
- 関数呼び出しをサポート
- 文字型を追加
- トークナイザをパーザから分離
- 初歩的な型宣言をサポート
- ポインタ型を追加
- 配列型を追加
- 配列の初期化式をサポート
- if文を追加
- 関数定義をサポート
- forループを追加
- return文を追加
- ポインタ型への代入をサポート
- ==追加
- 配列演算と配列の添字をサポート
- ++, --, !追加
3月13日
構造体が実装できた。構造体は1ワードより大きいメモリ上にあるオブジェクトだからプリミティブな型より実装が複雑なんだけど、意外と早く実装できた気がする。
構造体をメンバに含む構造体なんかを作ってみても正しく動いているみたいだし、構造体へのポインタを取得してそれをデリファレンスしてアクセスしても正しい値が返ってきてるっぽい。配列を入れた構造体も構造体の配列も正しく動いてる。こう扱うのが正しいはず、と思って書いたコードが複雑なテストケースでもきちんと動くとなんかうれしい。
でもなぜ今のコードできちんと動くのかいまいち自分でも理解しきれていない気がする。
関数に構造体を渡したりするのはまだできない。x86の関数呼び出し規約だと構造体はたんにスタックに置いといてそこへのポインタを渡すだけなんだけど、x86-64だと構造体のメンバをレジスタ渡ししないといけない。ややこしいのでここらへんは後回し。
3月14日
Unionは全部のフィールドの開始位置が同じの構造体の変種みたいなものだから実装は簡単にできた。->演算子とかもちょろっとサポート。まあたやすい。
浮動小数点数をサポートしようとしてるんだけどこれはかなりややこしい。整数との暗黙の型変換や四則演算はたぶん動いてるはずなんだけど、関数に渡すのがうまくいかない。関数呼び出しでは、一度引数を全部スタックにプッシュしてから改めてx86-64の関数呼び出し規則に沿ってレジスタに引数を置き直しているんだけど、そこでなにかが間違っているらしくSEGVる。冗長なアセンブリを出力しているのでその中でエラーになるとデバグが辛い。一日でできるかと思ったがやっぱり無理か。
3月15日
スタックフレームが16バイト境界にアラインされていないといけないというx86-64のABIを忘れていて時間をちょっと無駄にしてしまった。
浮動小数点数を複数printfに渡すとなぜかSEGVるというので、再現条件を調べてみたら、call命令を呼ぶときのスタックポインタの位置が問題だということがわかって、それでABIのrequirementを思い出した。
いままではスタックフレームのアラインメントなんて気にしていなかったので8バイト境界にしかアラインされていなかったのだけど、整数しかprintfには渡していなくて、それだと偶然うまく動いていたぽい。まあこれはcall命令を呼ぶ前にスタックポインタを16の倍数になるように調整すればすむ話。しかしこういうのは事前に仕様を読んでおかないとわからないよなぁ。
3月16日
コンパイラのコードを2タブから4タブに変更しておいた。2タブが標準のGoogleにいると目が腐ってきてまったく違和感を感じなくなるんだけど、やっぱり2タブは変。4タブのほうが「きれいなコードのオープンソースソフトウェア」という雰囲気が出る（偏見）。
もうちょっと意味のある変更としては、シェルスクリプトで書いていたテストをCで書きなおしてみた。いままではテスト対象の関数一個を自前のコンパイラでコンパイルして、gccでコンパイルしたmain()とリンクして、シェルスクリプトからそれを実行していたんだけど、これだとテスト一つにいくつもプロセスが生成されるので遅かった。コンパイラの機能が貧弱だったときはテストコードをそれ自体で書けなかったのでしょうがなかったんだけど（比較演算子がないから期待している値と合っているかどうか比べられないとか）、もういまはテストコードをコンパイルできるレベルまで機能が増えた。なのでCで書きなおして高速化をはかってみた。
ほかはdouble、longという大きいサイズの型を足すなど。やろうと思っていたことがサクサク実装できて楽しい。
3月17日
一日でCプリプロセッサの実装作業がだいたい終わった。以前書いたやつからのポートだけど。
Cプリプロセッサの実装はかなり手間がかかる。
Cの一部だから仕様は一応ANSIで決まっていることにはなっているんだけど、仕様書に書いてある内容はあまりにも適当すぎて実装の役に立たない。例が挙がっていてこのマクロを展開するとこうなるはずとかいうことはわかるんだけど、展開アルゴリズムの説明はないし、それどころか細かい仕様はきちんと書かれてすらいない気がする。
僕の知る限りこのブログにあるPDFが、マクロエキスパンダのアルゴリズムについての最良かつ唯一の資料だと思う。このアルゴリズムの基本的な方針は、無限に展開をすることにならないように展開してでてきたトークン列では一回展開したマクロ識別子を展開しないようにしつつ、できるだけ再帰的にマクロ展開するという感じ。
ほかにもCのマクロには興味深い細かい点がいろいろあって面白い。つまり奥が深い。
3月18日
#includeも実装したし、いよいよシステムのヘッダファイルを読み込んでみるか！と読んでみたらコケまくる。#ifで使える式のオペレータとかあまり実装してなかったからなぁ。プリプロセッサも細かいところでいろいろバグっていたのでがんばって直した。
それにしてもヘッダファイルは大きくて複雑。enumとかtypedefとか新しいのが次々でてくるので、そのたびに一つづつ足していった（ただし実装はかなり手抜き）。stdio.hをテストに使っているんだけど、これを最後まで読めるのはいつになることやら。
いまはコードが4000行くらいあって、LCCというコンパクトなCコンパイラのコードが12000行らしく、それを目安にするとそろそろまともに動き始めてもよさそうな気がする。
今日は500行も書いたらしくちょっとびっくりした。12時間集中してコーディングとかは普通にできるんだけど疲れて効率が悪くなっている気もする。いずれにせよ僕の暇人さはやばい。
3月20日
もうなにを直したのか覚えてないけどstdio.hをインクルードできるようになった。これでstdio.hで宣言されている関数と変数が正しい型で扱えるようになったはず。これはかなりうれしい。
それにしてもいままではシンプルな俺言語を発展させていってCに近づけていくというアプローチでやってたので、自分にとって重要ではない部分はあいまいにしたままでよかった。作りたいところだけ作っていけたのでさくさく書けて楽しかった。
これがヘッダファイルみたいな外部のものを扱い始めると突然「正しいC」であることが要求されるようになってどうも調子が狂う。とにかく最後まで読めるようにしたい一心でヘッダファイルの特定の行をパーズできるようにするためにダーティーなハックを実装してしまうとか。"const"という識別子はとりあえず全部無視！みたいな。自分でもその場しのぎのコードばかり書いていることがわかるのでどうも面白くない。
じゃあきれいに実装すれば、というと、それもそれで楽しい話というわけではない。Cの型の宣言の構文とか無意味に複雑で（この世界には必要以上に複雑なものというものがたくさんあって、Cの型の構文はそのひとつだと思う）、これをきちんと実装していくのは別に興味深い作業ではない。
まあ仕方のないものというものはある。そろそろギアを変えてCの構文を端から全部きちんと実装していくべきなのかも。着手すれば完成に近づいていく楽しさがあるかもしれない。やりたいことをやるには結局たくさんコードを書かないといけないという話はそういう趣旨なわけだし。
3月21日
2日かけてもさっぱり宣言と定義の正しいパーザーが書けないんですケド。ポインタとか構造体とかは一日でそこそこきちんと動いてくれたのになぜここで！？ なめてかからずに最初にしっかり方針を立てて望んだほうがいいのかしら。
3月22日
こういうときは一か月前は実質この1ファイルだけだったことを思い出して進歩を噛みしめよう。実質数字をscanf()してprintf()するしてるだけだからなぁ。ていうかほんと一ヶ月ですごい進んだな。かなりすごい気がするな（さっそく自己満足）。
3月24日
型の宣言と定義の正しいパーザを書き終えた。いままでうまく書けなかったのは細部を詳細に書きすぎていたせいで前提が狂うと全部書き直しになっていたせいだと思って、擬似コード的なもので理解が正しいのを確認したあとに、それをコンパイルできるように書きなおしたら、うまくいった。
Cを書き始めて15年くらいは経つと思うけど初めて完全にCの型の文法を理解した気がする。最初はきちんとわかっていなかったんだからパーザが書けなかったのも無理はない。
それにしてもこの部分は自分で書いたコードが自分でも理解できるかどうかギリギリくらいで、Dennis Ritchie本人も自分の書いているコードの意味を完全に理解していたのかどうかちょっと疑問。僕のコードがまずいというわけではなくこの部分はLCCでもやっぱりわけのわからないコードになっていた。Dennis Ritchieは結論がわかっていて書いたというより、適当に方針を決めてコードを書く→動かしてみると思いもよらない複雑な文法になる→その振る舞いがANSIで標準ということになる、ということが起こっただけではないかなと思った。細部まで既存のなにかを真似なくていいという意味では俺言語を実装する方がずっと簡単。俺言語を後追いで実装するのは大変。
3月25日
Cコンパイラは演算子を淡々と実装したりコードをきれいに直してみたり。
今日はじめてコンパイラの一部のファイルのセルフコンパイルに成功した。GCCでコンパイルした残りのオブジェクトファイルとリンクしたらきちんと動いたし、それを使って再コンパイルした第二世代のバイナリもきちんと動いた。かなり形になってきたよ。
3月26日
今日はswitch-case、continue、break、gotoなどを実装。gotoのテストケースを書いていたら短いテストコードがたちまちのうちにスパゲティになってワロタ。gotoがconsidered harmfulというのはこういうコードのことだったんだな。
3月28日
va_start()、va_arg()、va_end()とか可変長引数まわりを実装した。ここらへんは頻繁に使うというわけではないけど、これがないとprintf()みたいな関数がコンパイルできないので必要に迫られて。
Cの可変長引数は仕様があんまりよくない。引数が全部スタック渡しならva_start()は簡単に実装できるかもしれないけど、現代のプロセッサでは関数呼び出しのオーバーヘッドを減らすために引数がレジスタ渡しなので、前提が当てはまってない。
AMDが策定したx86-64のABIでは、可変長引数の関数は呼び出された直後に引数のレジスタを全部スタックにダンプしておいてva_start()の呼び出しに備える、みたいな感じの仕様になってる。まあそうするしか仕方ないんだろうけど、Cの可変長引数はかなり無理やり感がある。
ほかのコンパイラではどう可変長引数を実装しているんだろう？と思ってTCCのヘッダファイルをみてみたら、va_listがx86-64のABIで規定されている構造に従ってないように見えた。もし違うデータ構造になっているとしたらvsnprintf()みたいなva_listを受け渡す関数同士で互換性がなくなるので困ると思うんだけど。僕が勘違いしているだけ？ Clangも謎のデータ構造を使っていたけどややこしそうで読む気がしないのでやめた。あんまり詳細に読み込むと同じような実装になりがちで面白くないし。
3月28日
細かいバグを直して文字リテラルのエスケープシーケンスを足したら（いままで'\0'とかがなかった）、もうひとつファイルがセルフコンパイルできるようになった。着々と進んでいる感じで、着手してから1ヶ月が経ったんだけど、なかなかよい成果を上げている気がする。
6つ以上の引数を持つ関数をサポートしようとしたら一日で終わらなかった。x86-64では整数型の引数は6つまではレジスタ渡しでそれ以上はスタック渡しと、やり方が違って、いまのところレジスタ渡ししかサポートしてないのよね。レジスタに載せきれない引数をスタックに置くのは単純なことのはずなんだけど、デバグが辛くて時間を使いすぎる。7つ以上引数がある関数はいまのところ書いてないと思うから、セルフコンパイルを目標にするなら後回しにするという選択はありかも。
3月29日
また3つファイルがセルフコンパイルできるようになった。ファイル数でいえば6/11。でも行数でいえばまだ1/10くらい。残っているのはコンパイラ本体の大物ファイル。
しかもこの大物ファイルではcompound literalやdesignated initializerみたいなCの新しめの機能を使ってしまっているのでセルフコンパイルが面倒くさくなってしまっている。しかしその機能を使わないようにコードを書きなおすのは完全に後ろ向きな作業だからここは前向きにコンパイラでその機能をサポートしていきたいところ。まあ面倒なんだけどね。
3月30日
デバッギングエイドについて。コンパイラはステージがいくつもある複雑なプログラムだから中で何が起こっているのかわからないとデバグがすごく辛いものになってしまう。僕の自作コンパイラでも内部状態のわかるデバッギングエイドがいくつかあって、かなり役立ってくれている。
まずレキサの機能でどのファイルの何行目の何文字目を読んでいるというのがわかるようにしてあって、エラーで死ぬときはそれを常に出力するようにしてる。これでコンパイラが受け付けない入力がどこにあるのかということはすぐにわかる。
入力がおかしい時はerror()というマクロを使ってその場でexit()するようにしているんだけど、__FILE__と__LINE__マクロを使ってどこの何行目でerror()が呼ばれたかわかるようにしているので、正しい入力がエラーになったときはどこがバグっているかはだいたいわかる。
コマンドラインオプションを指定すると抽象構文木をプリントする機能があるのでそれをみてパーザのエラーはだいたい見つけられる。抽象構文木をプリントするときはあえてCとは違う素直な文法で出力するようにしている。これはエラーを見つけやすくするため。入力と出力の両方がバグっているけど結果として出力は同じ、という状態だとバグ発見の役に立たないので。
コードジェネレーターはアセンブリの各行に関数名だけのコンパクトなスタックトレース的なものをコメントでつけるようにしていて、どういうパスでその行が出力されることになったのかわかるようになっている。実行結果がおかしい場合はアセンブリ出力を眺めて、間違っている行を特定できれば、バグっている関数を特定できる。
抽象構文木とかトークンとか内部のデータ構造を文字列化する関数を用意してあるので、なにかがおかしいときはそれを使ってprintfデバグができる。内部表現を文字列化する関数の助けがあればprintfデバグは相当役立つ。そのために独立したdebug.cというファイルが用意されている。
機能を追加するたびに必ずユニットテストを書いているので、それで既存の機能が壊れるのを防止してる。機能を作っている間にもコンパイル可能な状態でユニットテストを実行してなるべく早くエラーには気づくようしてる。ちょっとづつしか変更してないので動作がおかしくなればそれは新しいコードが原因のはず。ユニットテストは数秒で完了するように早さにも気をつけているので頻繁に実行しても苦にならない。
4月1日
配列／構造体のinitializerを書きなおしたのと、compound literalを実装してみた。Initializerはいまいちよくない実装だったので書きなおしてすっきり。最初からキレイに書けばいいのにというとそうなんだけど、とりあえず動くものを書いてみないとわからないこともあるから、二度手間は仕方がないという面もある。
セルフコンパイルに必要なまだ実装してない機能は構造体の代入だけだと思う。必要な機能がそろったらあまりデバグせずに全体がすんなり動いてくれるといいな。
4月2日
トークナイザの入ってる大きめのファイルがセルフコンパイルに通るようになったんだけど、それで作った第二世代のバイナリが正しいアセンブリを出力しないので困った。第一世代はテストにパスするアセンブリを生成できるのでどうも微妙なバグらしい。
しょうがないからprintfデバグだな、と思って要所要所にprintfを足したら、そのデバグ出力が第二世代をビルドしている間にも出力されて一瞬意外に思った（第二世代を「使っている」ときにデバグ出力が欲しかっただけだったから、第二世代を「作っている」ときにもそれが出てくるとは予期してなかった）。さらにいろいろやっていたらいまのバイナリがどのファイルを使った何世代目なのかもよくわからなくなってきた。
なんか映画のインセプションを思い出した。「このバグを再現させるにはもう一階層深くまで行くんだ」みたいな。セルフコンパイルのデバグというのは面白いものですな。
4月3日
レキサーをセルフコンパイルすると第二世代のバイナリがおかしくなる問題は直した。ときどき-1 > 0が真ということになっていたとか（符号拡張し忘れてる）とか構造体のレイアウトにバグがあったとかとか、そういう問題でした。3 files to go!
4月4日
コードジェネレータがセルフコンパイルできるようになった。残り2ファイル。もうちょっとだな、と思うけど、どんな罠が潜んでいるかわからないのであまり楽観的になるのは禁物だよなぁ。
初期に書いたアドホックなコードがいまになって悪さをしているケースが何度もあってちょっとうんざりした。
必要な機能は全部実装していたかと思ったらそうでもなかった。前置の++、--とかがなかったのは論外だけど、もっとマイナーな機能はそういうのを使って書くんじゃなかったと後悔。実際何箇所かはコンパイラフレンドリーに書きなおした。当初はセルフコンパイルにすぐこぎつけるとは思ってなかったので書きやすさ優先でコンパイルしやすさは考慮してなかった。
4月5日
つ・い・に！ 僕のCコンパイラでそれ自身を全部セルフコンパイルできるようになった。Yay!
ここまで40日程度。セルフホスティングなCコンパイラを書くのに要した時間としてはかなり短いんじゃないだろうか？ やっぱり小さく作って大きく育てるアプローチがうまくいったんだと思う。ともかくこれはうれしい。
自分のコードを見てみると、仕組みがわかっていても、これがそれ自身を入力として扱って正しいアセンブリに変換できることが不思議に感じる。
次にやるのはバグ修正と未実装の機能を実装することかな。そのあと出力するコードの質を改善してLCCやTCCのレベルまで追いつきたいところ。
ソースコードはこれ。今のクオリティではあんまり読んでもしょうがないと思うけど、5000行程度のコンパイラが扱うことが可能なCコードの例としてみるとそれなりに面白いかも。
4月6日
セルフコンパイルができるようになったので元の盆栽の枝を整えるような地味な作業に戻った。ちょっとずつ変更しては遠目に眺めてその出来栄えに満足する、みたいな。ちまちました作業は好きなんだよね。
2回セルフコンパイルしてみて第一世代と第二世代で同じバイナリができているのを確認するテストを入れてみたり。たしかGCCもそういうテストがあると聞いたことがある。
4月7日
コンパイラのソースには書いていないのにバイナリだけで代々伝わっていく情報というのがある。
たとえば僕のコンパイラでは、文字列を読む部分で、'' のあとに 'n' がきたら '\n' という文字（改行文字）を読んだことにする、という箇所がある。これはよく考えてみればトートロジーみたいなもので情報が足りていない。おかしいでしょう？ これでは '\n' という文字は 本当は どのASCIIコードなのか、ということがソースコードからわからない。ソースコードからわからないけど、コンパイラをコンパイルするコンパイラからその情報が受け継がれるので、できたバイナリは改行文字をきちんと出力できる。僕のコンパイラの改行文字は何度セルフコンパイルしても最初に使ったGCC起源ということになる。
改行文字の文字コードというレベルではなくもっと大きな情報をバイナリだけで受け継いでいくこともできる。
この話はKen Thompsonがチューリング賞を受賞したときに発表して世の中をちょっと驚かせたらしい。Ken Thompsonが初期のUnixのコンパイラに埋め込んだ情報は、loginプログラムをコンパイルしているときにあるパスワードを勝手に受け付けるようにする、というコードだった。なのでKen Thompsonは誰のUnixアカウントにもログインすることができた。さらに、コンパイラをコンパイルしているときには、loginに細工をするコード（とコンパイラに細工するコード）を埋め込むようにしたので、コンパイラのソースコードには存在しないバックドアが何度セルフコンパイルしても受け継がれるようになっていた。すごいね。
4月7日
式の解析には演算子優先順位パーザを書いて使っていたのだけどそれを再帰下降パーザで書きなおした。演算子優先順位パーザの利点は単純で速いことだと思うんだけど、Cの式の文法は演算子優先順位文法というにはいろいろ付随するものが多すぎて（配列の添え字とかいろんな単項演算子とか）、演算子優先順位パーザだとごちゃごちゃする。再帰下降パーザで書きなおしたら細かい関数に分割できてすっきり。今後エラーチェックとかをきちんと書いていくときにもこっちのほうがやりやすくていい。
構文解析のいろんなテクニックはいままで何度も役に立ってくれた。覚えてといてよかった。
しかし再帰下降パーザで書きなおそうとCのスペックを見ていたら、左再帰になっている文法がところどころあって、これは無限再帰にならずにどうやって再帰下降法でパーザを書くんだっけ？ としばらく考えてしまった。左再帰の除去って非常に教科書的な話題だよなぁ。うーむ。でもやっぱ構文解析の基本的なこともしばらくたつと忘れてしまう。
4月8日
文字列 → トークン列 → マクロ展開されたトークン列 → 抽象構文木 → アセンブリコード、という流れでやってるんだけど、一番最後のパスが過負荷気味でコードが怪しい。暗黙の型変換とかラベルの解決とかをアセンブリを出力しながらアドホックにやっていてバグが潜んでいそうな雰囲気が漂う。セオリーからいうと抽象構文木とアセンブリの間に中間言語を作るべきかな、と。
ドラゴンブックのそのあたりを読みなおしてみたらなんだかわかったようなわからないような。説明が微妙に抽象的でわかりにくいんだよね。
とりあえず適当な三番地コードに落として三番地コードの変数を全部スタックに割り当ててしまうかなぁ。現状スタックにテンポラリな結果をpush/popしているのから効率は改善しないけど（というか悪くなるかも）、中間言語導入の最初のステップとして。
いまのコード、セルフコンパイルにかかる時間を測ってみたらGCCの2倍だった。思ったより悪くなかった。恐ろしくナイーブなコードでも桁違いには遅くないものなんだな。
4月9日
ふと思い立ってgcovをかけてみたらユニットテストで通っていないパスがちらほらあって、そこをテストしてみたら何個もバグが見つかった。コードカバレッジツールというのも意外とあなどれないものですね。
4月11日
コンパイラはちょっとネタ切れ感が。コード生成とか最適化をうまくやるのはやっぱ難しいのね。特に今回勉強しなくてもここまではさくさく書けたけど、これ以上は自分のよく知らない領域という感じ。困った。
4月14日
暗黙の型変換を暗黙のうちにコードジェネレータでやっていたのをやめて、型変換を陽に抽象構文木で扱うことにしたら、なにをやっているか明白になってすっきり。そのほかにも各所に手を入れていろいろ改善。ほとんど完成した気分になっていたけど実際は未実装の機能とバグがまだまだあるのでした。
もう少し知識を仕入れようとドラゴンブックを読んだら理解が結構進んだ。さらにもうちょっと理解が進んだら次の開発ステップに進めるかも。
4月17日
3日探していたバグをやっと見つけた。CALL命令を呼ぶ前後でスタックポインタのアドレスをプラスマイナス16すると、第2世代のコンパイラが正しい入力に対してコンパイルエラーのメッセージを出力するという謎の現象。素直にSEGVってくれればいいんだけど、中途半端に動作するこの手の問題は追跡しにくい。
スタックフレームのアラインメントの問題かなと思ったけど、16バイト境界に揃っていればいいのでそういう問題ではなかった。アセンブリを手で編集して簡単にしてみても、どう考えても正しいコードで同じエラーになる。
GCCで全体をコンパイルして一部だけを自作のコンパイラでコンパイルしてみたら、問題のファイルを一つに特定できた。さらに指定された関数だけでスタックポインタを変更するようにした上でスクリプトを回してどの関数が問題なのかも特定できた。それでもまだその関数がどう間違っているのかわからない。そもそもその関数でエラーになっているのではなくて、そこからずっと離れた関数がコンパイルエラーを出力してる。
というわけでそこからさらにたどっていったら、リテラルの構造体を別の構造体に代入しているというコードがあった。コンパウンドリテラルも構造体の代入も比較的稀な、つまりあまり信用できなさそうな機能。これを普通の構造体で書き換えてみたらバグが発現しなくなった。
結局原因は、リテラルの構造体で指定されていないフィールドを0で初期化するのを忘れていたということだった。イニシャライザがある場合、初期値の与えられていないフィールドは0で埋めなければいけないんだけど、それをしていなかったので、構造体がスタック上のゴミで初期化されていて、それがヒープにコピーされたあとシンボルテーブルに保存されて後で問題を引き起こしていたのだった。どのゴミを拾うかというのがスタックの位置によって変わってくるので微妙なバグになっていた。
0で初期化していないのは問題だからあとで直そうと思っていたような記憶がかすかにある。あの時直していればよかった。探索三日、修正一行。こういうバグ追跡もうちょっと簡単にならないかなぁ。
4月18日
見つけにくいバグをまた一つ潰した。GCCと自作コンパイラを混ぜてセルフコンパイルすると、できたコンパイラが正しいコードに対してシンタックスエラーを報告するという問題。この手の問題はエラーを出しているコードがバグっているのではなくて、ABI互換性の問題のはずだから、構造体のレイアウトか関数の引数の渡し方のどちらかかがおかしいのだろうと見当をつけてみたけど、アセンブリをみてもどちらも特に間違っているようには見えなかった。
仕方がないので問題のファイルを2つに分割して、片方をGCCで、残りを自作コンパイラでコンパイルして、二分探索で問題を絞り込んでいくことにした。関数がひとつに特定できたらそれをさらに細かい関数に分割してGCCのほうにコードを移していって、最終的に数行のコードにまで絞り込んだ。そのコードをGCCでコンパイルしてアセンブリ出力を比較してみた。
それでわかったのが、僕のコードではbool型の関数の返り値をレジスタ全体が0かどうかで真偽値として扱っているのに対して、GCCでは下8ビットだけしか見ていないということ。手でアセンブリをGCCに合わせて修正するとたしかに問題が消えてなくなる。どうもこの非互換性のせいで、GCCでコンパイルしたboolを返す関数で終了判定をしているループが、僕のコンパイラの真偽値判定ではすぐに終了してしまって、プリプロセッサのマクロがひとつも定義されていないかのような動作になっていたらしい。その結果シンタックスエラー。原因から結果がちょっと遠かったがまあ突き止めたぞ。
x86-64のABIのドキュメントを確認したらboolの返り値は下8ビットだけが意味を持つと数行でさらっと書いてあった。最初は含意を理解できず読み飛ばすけど後からみたら勘違いしようがないくらいはっきり書いてあるというこういうパターンってよくある気がする。トホホとしか言いようがない。
4月21日
ビットフィールドを実装してみた。
ビットフィールドはとにかくぴっちり隙間なく詰め込めばいいというわけではないらしい。GCCの出力したコードを見てみるとビットフィールドの配置はこういう感じになっているっぽかった（適当に調べただけなので間違ってるかも）。
- 連続するビットフィールドの最初のフィールドは、指定された型のアラインメントに従う。例えばint x:5とか書かれていたら4バイト境界からビットフィールドが始まる。char x:5なら次のバイトから始まる。
- 指定された型の自然な境界をまたがるようには配置しない。例えばint x:10と書かれていたら、前のビットフィールドの残りが4バイト境界に対して9ビット以下なら、それは使わずに次の4バイト境界から始める。
あっているかどうかよくわからないけど、とにかくこの理解に基づいてそれを実装してみた。CPUにはビット単位でメモリにアクセスする命令はないから、ビットフィールドを読むときはそれを含むメモリ領域をレジスタにコピーしてきて自前でシフト&マスクしないといけない。書き込むときはメモリからまず読んできて、それをマスクした上で新しい値をシフトしてORするということになる。若干面倒だけどすることは単純。一応いまのコードできちんと動いていると思う。
ビットフィールドは本当にビットを詰めて配置しないといけない理由がない限り使わないほうがいいということがよくわかった気がする。ビットフィールドほとんど使ったことがない。
4月21日
言語開発者にはお馴染みのcomputed gotoを実装してみた。Computed gotoはポインタを受け取ってそこに飛ぶという機能で、普通のgotoがラベルの位置にしか飛べないのに対して、computed gotoはどのアドレスにも飛べるというのがメリット。Cの標準機能ではなくGCC拡張だけど、VMを書くときはよくこれでジャンプテーブルを作ったりする。switch-caseベースの命令ディスパッチよりcomputed gotoでジャンプしたほうが速いので。
Computed gotoは単なる間接ジャンプなのでアセンブリで説明したほうがむしろわかりやすいと思う。僕のコンパイラはアセンブリを出力しているので実装は簡単だった。
4月22日
C11の_Genericを使いたくなったので実装してみたんだけど、実装したあとにコンパイラのソースで実際に_Genericを使ってみたら、GCCでエラーになってしまった。手元のGCC 4.6.1は_Genericをサポートしてないぽい。このオチは予想していなかったけどこれでは結局使えない。
ついでにGCC拡張のtypeof()もサポートしておいた。当面両方とも使い道がないけど短いコードで実装できたからまあいいかなと。
4月23日
C99のダイグラフを実装してみた。ダイグラフは一部の記号を直接入力できないマイナーな環境のためのすごく変な機能で、たとえば"["の代わりに"<:"と書いてよいなどということが決まっている。
ダイグラフはトークナイズの際に変換すればいいだけなので、意義はないけど別に害もない。
C89のトライグラフという機能もあって、こちらは明らかに有害といわざるをえない。トライグラフは三文字からなるシーケンスなんだけど、ソースコード上の どこに あらわれても無条件に置換が行われると決まっているので、printf("huh??!") が"huh|"を出力するとかいうことになってしまう。??!は縦棒のトライグラフ。役に立つ場面が皆無なのに問題を引き起こすことは容易に想像できそうな困った機能。
GCCではトライグラフは実装されているけど、デフォルトで無効になってる。この選択は妥当だよねー。僕のコンパイラではトライグラフはサポートするつもりはない。
4月23日
+shinichiro hamajiさんのIOCCCのコードが動かないなぁとぼやいたらHamajiさんがパッチを送ってくれたのでマージ。ありがたやありがたや。おかげでこれが動くように。
4月27日
TCCのテストを通そうとしているんだけど、未実装の機能とバグっている箇所があってなかなかテストに通らない。
TCCは2～3万行くらいで実装されたCコンパイラ（一つのアーキテクチャに絞ると1～2万行くらい）で、そのコンパクトさであれだけの機能をサポートしているのはすごいと思う。Cコンパイラだけではなくアセンブラとリンカが実装されていてそのサイズは驚異的。作者のFabrice Bellardさんは真のスーパーハカーとしか言いようがない。
TCCのソースコードはなんども読もうとしてみたんだけど、いまいち全体像がつかめないまま。コンパイラというのは複雑なプログラムだから、普通は複雑さを分割統治して制御できるようにいろいろ工夫するものだけど、TCCは複雑なものをそのままの複雑さで実装して、きちんと動いてしまっている感じがする。こんなすごいコードは少なくとも今の僕には書けない。真似したいコードかというとちょっと違うかもしれないけど、こういうコードを書くことができる人がいるんだという意味でちょっと感動させられる。
5月7日
TCCのテストコードを通そうとしてしばらくがんばってみたけどいまだにこれを通すには至らず。これを通せるようになったらTCCと同等レベルに到達できたといえるだろうから難しくて当然なんだけど。
飽きてきたのでまずTCC本体をコンパイルできるようにするほうに方針を転換することにした。
ほかのコンパイラのテストコードはバグ出しの役に立つけど、その性質上わりとどうでもよい重箱の隅を満遍なくつつきまくるものなので、そればっかり相手にしていると正直飽きる。なかなか進まないし。
というかコンパイラを作って一つ学んだことは相当バグってるコンパイラでも素直なコードは意外なほど問題なくコンパイルできてしまう、ということかも。そうなると重箱の隅つつきテストコードは「実際はこんなのあんまり問題じゃないだろうし・・」とか思ってしまうという。