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を追加した。
10/5
ネストされた型宣言に対応。 演算子の優先順位を確認した。 大まかに言って型の読み方としては pre (mid) sufという型宣言があった場合、Goの(理解しやすい)記法ではmid suf preの順となる。例えばint (*x)[3]の場合var x *[3]intとなる。すなわちxはポインタであり、そのベースは長さ3の配列であり、そのベースはintである。コードの並びとデータの並びが一致していないのでややこしい。chibiccでの実装の一部
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// declarator = "*"* ("(" declarator ")" | ident) type-suffix
Type *declarator(Type *ty, char **name) {
while (consume("*"))
ty = pointer_to(ty);
if (consume("(")) {
Type *placeholder = calloc(1, sizeof(Type));
Type *new_ty = declarator(placeholder, name);
expect(")");
*placeholder = *type_suffix(ty);
return new_ty;
}
*name = expect_ident();
return type_suffix(ty);
}
がぱっと見分からなかったが、例を考えるとなんとか理解できた。括弧の外側の情報を内側へ伝えるために引数を取っている。
10/17
しばらく開いてしまった。 関数の返り値に型を追加した。void型を追加した。chibiccではまだ関数の返り値の型としては使えないようだがこれも使えるようにしておいた。
10/19
_Boolを追加した。
10/23
sizeofに型を渡せるようにした。e.g. sizeof(int(*)[4])
unaryを渡すときと違って、こちらは括弧必須らしい。long型の数値リテラルに対応した。
10/24
型のキャストに対応した。chibiccではテストコード内にboolが現れるが、これは_Boolが正しい気がする。 コンパイラがboolを認識している様子がない気がするけどテスト通るのかな？ところでCはC23からboolを(ヘッダstdbool.hをインクルードせずに)使えるようになったらしい。
文字リテラルに対応した。
関数の返り値を型のサイズに正しく切り捨てるようにした。void型のサイズは取得できないようにしているので、voidの場合は何もしないように分岐させた。
関数宣言に対応した。
11/5
enumに対応した。enumって競プロだと赤黒木のRED,BLACKで使ってる実装くらいでしか見たことないな。
11/6
staticローカル変数に対応した。スコープについて少し考えていたが、staticがつくかつかないかでスコープは特に変わらないので必要なかった。グローバル変数にさえすれば良い。
for文の初期化式での変数宣言に対応
11/15
++,--演算子に対応した。
+=,-=,*=,/=に対応した。
!演算子に対応した。返り値はint型。C++だとbool型で返すらしい。
~演算子に対応した。返り値の型を元の型と同じにしているがこれが正しいのかはちゃんと調べてない。4byteより小さい型は4byteになっているような気がする。
11/16
ビット単位演算&,|,^に対応した。レファレンスに合わせてint型を返すようにしている。
論理演算&&,||に対応した。レファレンスではジャンプ命令を使っているが、ここではオペランドを0/1に変換してから単にand,or命令を使った。
11/19
関数の引数におけるarray-to-pointerの変換に対応した。これは
1
2
int f(int x[][2][3]);
int g(int x[1][2][3]);
のようなコードをコンパイラが
1
2
int f(int (*x)[2][3]);
int g(int (*x)[2][3]);
のように認識するというもの。引数にsizeofの結果が大きなものを渡したくないことを考えればこういう仕様があるのは理解できる気がする。
11/20
不完全な構造体の型に対応した。不完全というのは大きさを確定するための情報を欠いているという意味。struct tag *t;のようなコードがそれに当たる。tのサイズは決まっているがstruct tagのサイズはここでは決まらない。 次のコード
1
2
3
4
5
6
7
8
9
10
11
struct T {
int a;
};
{
struct T *t;
struct T {
int b;
};
t = calloc(1, sizeof(struct T));
t->a = 0;
}
でstruct T *t;の部分の解釈が最初の3行が有るか無いかで変わり、無かった場合tのメンバ変数はbになる。ここらへんややこしい。
11/24
break文に対応した。for/while文の終わりのラベルに飛ぶだけだが、ラベル名を知る必要があり対応する数を記憶するグローバル変数を用意している。 通常break文がどのループを抜けるのかは明らかだが、次の例では明らかではない。
1
2
3
4
while(1) {
while( ({break;1;}) ) {
}
}
外側のループを抜ける場合は通過するだけだが、内側のwhile文を抜ける場合無限ループになる。Clangでコンパイルすると
1
2
3
4
a.c:3:13: warning: 'break' is bound to current loop, GCC binds it to the enclosing loop [-Wgcc-compat]
3 | while( ({break;1;}) ) {
| ^
1 warning generated.
という警告が出る。Clangは内側のwhile文を抜け、GCCは外側のwhile文を抜けるようだ。ここではClangの挙動に合わせた。