finished-reading-compilerbook.mkd

tags
プログラミング

"低レイヤを知りたい人のための Cコンパイラ作成入門" を読み終えた

先日，"低レイヤを知りたい人のためのCコンパイラ作成入門"を読み終えたので，ここに進捗と感想を残す． 前回からの実装内容は以下の通りだ．

• 比較演算子を実装
• ベクタ・マップを実装
• 2文字以上の識別子名のサポート
• 関数呼び出しを実装

実装内容

比較演算子を実装

等価演算子，不等価演算子を実装した． 等価演算子は，2つの値を比較し，同一の場合は1，そうでなければ0を返す．不等価演算子はその逆のことを行う．

コンパイラのコード生成器は，この演算子に対して以下のようなアセンブリを出力するようになっている．

pop rax
pop rdi
cmp rdi, rax
sete al
movzb rax, al

sete命令を使い，フラグレジスタからal レジスタに値をコピー，movzbでサイズを拡張することで， 比較演算の結果を rax へコピーすることができる．

ベクタ・マップを実装

今まで，トークンや文の列を格納するために固定長配列を使用していた． 本書の，そろそろ制限を直しても良い頃だ，という指示に従い，ベクタを実装し， いくつかの箇所で，固定長配列をベクタで置き換えた．

また，任意個数のローカル変数をサポートするためにマップが必要で，本書ではこのタイミングで修正するようになっている． しかし，関数呼び出しの実装を優先したためまだ実装できておらず，マップの実装のみがある状態だ． 近いうちに実装する．

実装したベクタ・マップの使い方は以下のようになっている．

Vector* vec = vector_new();
vec_push(vec, (void *)2);
int v_num = (int)vec->data[0]; // 2

Map* map = new_map();
map_put(map, "foo", (void *) 3);
int m_num = (int)map_get(map, "foo"); // 3

2文字以上の識別子名のサポート

後述する関数呼び出しの実装の都合上，2文字以上の識別子名をサポートした． これにより，num=0 のように，変数に2文字以上の名前が使える． しかし，今の実装は一時的なもので，変数名の1文字目で変数を判断している，というかなり致命的な制限がある． つまり， num=0; n = 1; のようなコードを書いた場合，num は上書きされてしまう． 前述したマップを使用した，任意個数のローカル変数のサポートをするタイミングで，この制限も修正する予定だ．

関数呼び出しを実装

先日，"Introduction to X86-64 Assembly for Compiler Writers"を読んだ という記事で x86-64での呼び出し規約について学ぶことができたので，関数呼び出しを実装することにした． なお，このコンパイラのサポートしているデータ型は整数のみなので，関数呼び出しで扱うことのできるデータ型も整数のみだ．

今回実装した関数呼び出しの構文は以下のようなものだ．

ident: "a" | "b" | "c"...
fncall: ident "(" arglist ")"
arglist: cmp arglist' | ε
arglist': "," cmp arglist' | ε

cmpは，今回実装した比較演算の構文だ．これは代入演算子が使えないことを除いて，代入演算子の右辺と同じだ．

また，出力されるアセンブリはx86-64の呼び出し規約に準拠しているが， 6つ以上の引数が渡された場合，それ以降の引数は無視する実装になっている． これの制限の理由は，x86-64の呼び出し規約に関係してくる．

先日書いた記事，"Introduction to X86-64 Assembly for Compiler Writers"を読んだ からx86-64の呼び出し規約を引用する．

• 整数の引数(ポインタを含む)は，%rdi， %rsi， %rdx， %rcx， %r8， と %r9，にこの順番に置かれる．
• 浮動小数点の引数は %xmm0-%xmm7のレジスタにこの順番で置かれる．
• 残りの引数はスタックにプッシュされる
• 関数が可変長の引数を取る場合，(printfのように)，%raxには浮動小数点引数の数がセットされなければならない
• 呼び出された関数は任意のレジスタを使用できるが，%rbx，%rbp，%rsp，と %r12-%r15を変更する場合，その値を復元しなければならない．
• 関数の返り値は %rax に置かれる

つまり，6つ目以降の引数はスタックに置かなければならない．実装を簡単にするため，今回はレジスタに収まる分の引数を受け付けるようにしている． とはいえ，32bitのマシンではすべてスタックに配置しなければならないので，この制限は近いうちに修正するだろう．(授業で使う実験機は32ビットだ)

関数呼び出しを実装したことで，制限はあるもののCの関数を呼び出せるようになった． 例えば，以下のようなコードを呼び出せる．

int add_int(int x, int y) {
  return x + y;
}

この関数を呼び出すには，以下のように書けば良い．

x = 2; y = 3; add_int(2, 3);

結果として，5 が返り値として得られる．

今後の実装予定

さて，今後の実装予定として，今のところは以下の3つを挙げたいと思う．

• 浮動小数点型への対応
• 関数定義を実装
• 構造体のサポート
• if・whileのサポート

この4つができれば，授業課題で使用する実行時ライブラリをコンパイルできるようになる． 授業課題というのは，「実数・虚数に対応した，三角関数，指数関数，対数関数を実装せよ」というもので， 実行時ライブラリはそれらの実装を含む関数群だ．

授業開始当初，目標として考えていたのが実行時ライブラリのコンパイルなので，達成できるようにしたい．

感想

本書を読む前はアセンブリを書いたことはなく，Cも授業で触った程度の経験だったが， 本書の流れに従うことでスムーズに開発を進めることが出来た．

本書を読むにあたって，主に授業前日の深夜を活用し，3~4週間ほどかかったので， 読み終えるまでに12~15時間ほどかかっただろうか．

また，自分でアセンブリ等についての他の資料と合わせて読むことで， Cコンパイラ開発の，最初の一歩を踏み出すための足がかりになったと思う．

授業後は，セルフホストを目標に開発を進めるか，あるいはOS自作をやってみるのもいいかもしれない．