Cコンパイラを作る
Rui Ueyamaさんの『低レイヤを知りたい人のためのCコンパイラ作成入門』と『chibicc』のリファレンス実装を読みながらCコンパイラをCで作っていきます。セルフホストできるところまで進めるのが当面の目標です。日記形式で書いていきます。
9/2 ～ 9/10
「ステップ14: 関数の呼び出しに対応する」まで進めた。
9/11
Commit aedbf56 では関数呼び出しの際RSPが16の倍数になるように条件分岐させている。僕の実装だと、mainのプロローグの際にRSPをローカル変数の分だけ引くことになるがそこを16の倍数になるようにしており、コード生成の際にはpushした分だけpopしてるはず。従ってこういうチェックをしなくても16の倍数に最初からなっている…はず。ここに関わらず僕の実装とchibiccの実装が異なっている箇所が色々ある。後々沼にハマることを考えるとなるべく同じロジックにしておきたい気もするがどうしようか？とりあえずこのコミットは無視して進めることにする。
引数なしの関数宣言を実装していく
↑foo(){return 1;}bar(){return 2;}main(){return foo()+bar();}みたいなときに正しく16の倍数になっていない気がする。のでやっぱりcall前の16の倍数になるような調整をいれる。
もともとgenはreturnしたときに1つスタックにpushされているつもりだったが、それも難しそうな気がしてきたのでその前提でpopしてあるコードは消した。(そこに気づかずにwihleのデバッグが長引いた)chibiccを眺めながらなんとか完了。関数ごとにローカル変数を持っているので、別の関数が同じ変数名を持てる。ブロックのスコープには対応していない。
6個までの引数を持つ関数の宣言に対応
入出力があれば簡単な競プロの問題が解けそうなコンパイラになってきた。ところでC言語って殆ど書いたことなかったけどC++に比べて全然機能がなくて驚かされる。
9/12,13
関数・仮引数・ローカル変数の宣言にintをつけるようにした
intやint*,int**,…が扱える型を導入する。 Type* は各Nodeに持たせるがVarには持たせていない。
int main(){ int **a; *a; }
のような場合にint **aの型は*の個数ですぐに分かるが’*a’の型をどう決めるのかに悩む Varに紐づけるべきな気がするな…
9/14
リファレンス実装を見ながらなんとか型の実装までやった。 ND_EXPR_STMTをリファレンス実装では随分前に導入していたがこのことに今日気づいた。 ND_EXPR_STMTのノードをコードにする際にはスタックにプッシュされた分RSPを戻す。 これにより実装がいくらか簡単になる。式の値を使わないような場合にこのノードを使う。 例えばfor(init;cond;inc)についてはcondは結果を用いるからND_EXPR_STMTは用いず、init,incは結果を用いないからND_EXPR_STMTを使う。peek関数を(リファレンス同様)実装した。これは次のトークンが与えられた文字列と一致するかどうかを返す関数だ。9cc/chibiccの特徴としてコードを最初に全部読み込んでメモリに載せること、トークナイズ・パース・コード生成を並列せずに順に行うということを著者が挙げていたと思うが、この関数が自然に実装できるのはこの特徴のおかげだと思う。
などの動画を見た。
9/15
配列を実装した。配列からポインタへの暗黙の型変換が難しい。
配列に対して
sizeofと単項&以外の演算子は定義されず暗黙のうちにポインタに変換される
ND_DEREF,ND_VARではコード生成の際、型が配列かどうかで挙動を変えている。配列でない場合、gen_addrでスタックにアドレスを積み、loadでアドレスをpopしてアドレスが指す値をpushする。配列の場合、例えばint a[2];について*a=1;のコード生成ではgen_addrに*aが渡される。ノードはND_DEREFだからgenにaが渡される。次にgen_addrにaが渡され、スタックにaのアドレスが積まれる。そしてaのアドレスに1が代入される。
分かるような分からないような？とりあえず進めていく。
sizeofを実装した。chibiccに沿って実装している。compilerbookとは違ってまずND_SIZEOFを設定しておき、add_typeの際にND_NUMの定数に置き換えを行っている。またintは8byteとしている。
グローバル変数に対応した。 よく言われることだけど、ローカル変数とグローバル変数が内部的にはかなり違う実装になっていて驚く。
9/16
char型を実装した。8byte以外のデータの最初の導入。
文字列リテラルを実装した。#include <stdio.h>をコンパイルしたオブジェクトファイルとリンクすることでprintfが使えるようになった。Cの文字列リテラルが変更できなくて、静的領域に置かれるというのを知ってびっくりした。
9/17
GNU拡張の式文を追加。エスケープ文字に対応。
9/19
コメントに対応した。
ブロック文・関数のスコープに対応した。対応するchibiccのコミットではブロック文の方だけ実装している。 この実装はかなり簡単で驚いた。現在のスコープに対応するVarList *scopeを持っておき、ブロックに入る際にその時点でのスコープを覚えておく。そしてブロック内でローカル変数の定義が現れるとスコープに追加し、ブロックから出る際には入る際のスコープに戻す。find_varはscopeを前から探索するが、このリストは前のほうが新しく定義された変数、つまり深いところで定義された変数なのでこの方法で正しい。関数をパースする際にはscopeはglobalsにしておいた。
テストをシェルスクリプトからCのコードに変えた。面倒だったのでテストコードはコピペ…。一瞬でテストが終わるようになった。printfを使いたいときは#include <stdio.h>だけを書いたファイルをGCCでコンパイルしておいて9ccでコンパイルしたアセンブリコードとリンクするようにしてたけど、そんなことしなくても勝手にlibcを見に行ってくれるらしい。というかstdio.hはただのヘッダファイルだからそもそも実装は書かれてないのか。競プロでは最終的に単一のコードに変換する関係で.hppファイルに実装を普段から書いていたけど、普通は宣言だけ書くんだよね。
TCFMを聞いていたがイランの核施設の遠心分離機をアメリカ側がUSB経由のマルウェアを使って物理的に破壊したという話が面白かった
9/20
structに対応した。C++では
1
2
3
struct Name {
/* ... */
};
という形でグローバルにしかほとんど使ったことがなかったので、ローカルにも定義できることや無名のstructが作れることを知らなかった。入れ子に定義するのはSplay木を書いたときに使ったことがあったな。ここでは
1
2
3
struct {
/* ... */
} x;
という形の無名のstructにしか対応していない。
9/21
アラインメントを調整した。リファレンス実装だと2つのcommitで1つの意味のある修正になっていると思う。
struct tagの追加
9/24
->opを追加した。構造体のタグを追加した。
9/28
コンパイラーブックの『Cの型の構文』の章を読んだ。signal関数の宣言なかなかやばい。
1
void (*signal(int, void (*)(int)))(int);
10/1
typedefを実装した テストには
1
2
typedef int t;
t t = 1;
というコードがある。このままだとgccやclangでコンパイルは通らないが
1
2
typedef int t;
{ t t = 1; }
のようにするとコンパイル出来てしまうらしい。
10/2
sizeof(int)を8から4にした。 short,longを追加した。