インプットログ: 低レイヤを知りたい人のためのCコンパイラ作成入門
Mitsuaki Wada
低レイヤ強くなりたい。
役に立ちそうなリンク集
- C Playground
- C lang -> アセンブリ言語
Mitsuaki Wadaはじめに
- インクリメンタルに開発していく。常に完成形の状態。
- コンパイラ作りは楽しい。どこかのタイミングでコンパイラが出力するアセンブラがぱっと見で理解できなくなる。コンパイラが自分の知性を超える喜びがある。
Mitsuaki Wada機械語とアセンブラ
- この章の目的
-
コンピュータを構成するコンポーネントと、我々が作成するCコンパイラからどのようなコードを出力すればよいのかということについて、大雑把なイメージをつかむこと
-
- CPUからみるとメモリはランダムアクセス可能な巨大なバイトの配列。
- CPUが実行するプログラムと読み書きするデータはどちらもメモリに入っている。
- CPUは現在実行中の命令のアドレスをCPU内部に保持している。そして次の命令を読み出して実行するという流れでプログラムを実行している。
- 現在実行中の命令のアドレスがプログラミングカウンタ（PC）あるいはインストラクションポインタ（IP）という。
- CPUが実行するプログラムの形式そのものを機械語という。
- CPUは少数のデータ保存領域を持っている。AMDのプロセッサには64ビット整数が保持できる領域が16個ある。これをレジスタと呼ぶ。レジスタへのアクセスは、メモリへのアクセスと比べてとても高速。
- 多くの機械語のフォーマットは、2つのレジスタから値を読み出して演算しその結果をレジスタに書き戻す、というもの
- 特定の機械語の総称を命令セットアーキテクチャ（Instruction Set Architecture, ISA）あるいは命令セットという。
- Intel, AMD: x86-64
- iPhone, Android: ARM
- x86-64命令セットは、AMD64だったりIntel 64、x64などと呼ばれる。それぞれの名前は政治的なもの。本書ではx86-64を使う。
- アセンブリは人間のための言語。ネイティブなバイナリを出力するコンパイラはアセンブリを出力することが目標。よくある構成だとアセンブリを出力した後にアセンブラを起動する。
- 本書の目標もアセンブリを出力すること
- 逆アセンブル: 機械語からアセンブリへの変換
- アセンブリは、機械語1語につき1行という構成になってる。
- 関数呼び出しの場合、呼び出し後に呼び出し元に戻る必要がある。それはリターンアドレスと呼ばれ、メモリ上に保存される。関数はいくらでも深くできるので戻り先をレジスタに保存することはしない。CPUはただメモリ上のスタックへのアドレスを保持する。その領域をスタックポインタという。
- スタックポインタは常にスタックの先頭のアドレスを指す。なのでcallが呼ばれたときにスタックにpushされ、スタックポインタもインクリメントされる。また関数からretしたときはpopされ、スタックポインタはデクリメントされる。
- アセンブリ言語での開発は16個のグローバル変数をつかってプログラミングするようなものなのかな。大変そう。
Mitsuaki Wada電卓レベルの言語の計算
この章ではこの式をコンパイルできるようにする。再帰下降構文解析法を使って構文解析する。これはC/C++コンパイラでも使われている。
20 + (4 - 2) * -5
ステップ1：整数1個をコンパイルする言語の作成
- 本章では整数1個を受け取るコンパイラを作る。このアセンブリの出力を目指す
.intel_syntax noprefix
.globl main
main:
mov rax, 42
ret
ステップ2：加減算のできるコンパイラの作成
たとえば5+20-4を計算するアセンブリは以下
.intel_syntax noprefix
.globl main
main:
mov rax, 5
add rax, 20
sub rax, 4
ret
ステップ3：トークナイザを導入
式を読む前にトークン分けのフェーズを導入する。
- 実装した。いい感じ。if let気持ちいい。
Mitsuaki Wadaステップ4：エラーメッセージを改良
こんな感じでエラーを表示できるようにする。
$ ./9cc "1+3++" > tmp.s
1+3++
^ 数ではありません
$ ./9cc "1 + foo + 5" > tmp.s
1 + foo + 5
^ トークナイズできません
- 実装した。複数行のコードでもいい感じにエラー報告できるようにした
Mitsuaki Wada文法の記述方法と再帰下降構文解析
- どの演算子が最初にくっつくのか、というルールを「演算子の優先順位」という。
- 左から計算しなければならない演算子を「左結合」、右は右結合という。Cは代入の=以外はほぼ左結合。
- コンパイルの流れは、トークン列を構文解析し抽象構文木を構築し、そしてその構文木をアセンブリに変換する。
- チョムスキーが生成文法というアイデアを思いついた。彼の仮説によると、人間が言語を話せる理由は生成規則を獲得する専用の回路が脳に存在するため。
- 生成規則を表す記法がBNF
- 再帰下降構文解析法
- 戦略: EBNFの終端記号一つ一つをそのまま関数一つ一つにマップする。なので以下の四則演算EBNFを実装する場合、パーサーはexpr, mul, primaryという3つの関数を持つことになる。
expr = mul ("+" mul | "-" mul)*
mul = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"
ステップ5：四則演算のできる言語の作成
実装した: https://github.com/mi-wada/kanic/commit/468a8b38c714fd5954ba0e90a08970c60e8ab03e
楽しい。アセンブリをコード内できれいにフォーマットする方法を模索している。
Mitsuaki Wadaステップ6：単項プラスと単項マイナス
実装した: https://github.com/mi-wada/kanic/commit/fba77d012f095e7aed523cc9ffe9deadd9b500d0
-1 を 0 - 1として表現すればいままでのコードを再利用できる。賢い。
単項+演算子は何もしない。いらないな。
Mitsuaki WadaMitsuaki Wada分割コンパイルとリンク
すでにファイル分割しているのであまり関係なさそう。
Cの言語仕様では、コンパイラがファイル全体を読み込むことをせずに、関数1つ1つを先頭から順にコンパイルしていけるようになっています。したがって、どの関数も、その関数がファイル中で出現するところまでに書かれた情報だけでコンパイルできるようになっていなければいけません。従って、ファイルの後ろで定義されている関数を使いたい場合、事前にその関数の宣言を書いておく必要があります。そういった宣言のことを「前方宣言」（forward declaration）といいます。
へー
Mitsuaki Wada関数とローカル変数
この章では以下を実行可能にする。
// mからnまでを足す
sum(m, n) {
acc = 0;
for (i = m; i <= n; i = i + 1)
acc = acc + i;
return acc;
}
main() {
return sum(1, 10); // 55を返す
}
ステップ9：1文字のローカル変数
以下を実行可能にする
a = 3;
b = 5 * 6 - 8;
a + b / 2;
ローカル変数の実装面白いな、、、後で何度か参照することになりそう。
ローカル変数はスタックで管理されていて、そのスコープのベース（rbp）から何番目か、という指定でアクセスする。rbpはそのスコープ内で変えてはいけない。スコープ内のプロローグでrbpを適切にセットし、エピローグでリセットする。
スタックが下方向に成長するのは、メモリの下位アドレスあたりにコードが配置されることが多いため。そのコードのメモリとかぶらないように、上位アドレスから順にスタックを使っている。
実装した: https://github.com/mi-wada/kanic/commit/ac441f595722e28406d505058707ed9be374d45b
Mitsuaki Wadaステップ10：複数文字のローカル変数
parser内で各ローカル変数の場所を決定する。特に難しい点は無い。
実装した: https://github.com/mi-wada/kanic/commit/6af9355a3749b87960e3ed27ec4dd5113e4d1f8e
Mitsuaki Wadaステップ11：return文
以下をコンパイル可能にする。
a = 3;
b = 5 * 6 - 8;
return a + b / 2;
実装した: https://github.com/mi-wada/kanic/commit/7046eed8276783f0bed2e463c9d72853f2fc9423
Mitsuaki Wada1973年のCコンパイラ
Rob Pikeのルール刺さるな〜
コラム: Rob Pikeのプログラミングの5つのルール
9ccはRob Pikeのプログラミングに対する考え方の影響を受けています。Rob Pikeは、Cの作者Dennis Ritchieの元同僚で、Go言語の作者であり、Unixの作者Ken Thompsonと一緒にUnicodeのUTF-8を開発した人物です。
Rob Pikeの「プログラミングの5つのルール」（Rob Pike's 5 Rules of Programming）を引用します。
プログラムのどの部分が時間を使うのか予測することはできない。ボトルネックは驚くような場所で生じるので、それがどこにあるかわかるまで、むやみにボトルネックの場所を予測してパフォーマンスハックを加えたりしないこと。
計測せよ。計測する前に最適化しようとしてはいけない。また、計測したとしても、コードの極端に遅い場所以外は最適化しようとしないこと。
凝ったアルゴリズムはnが小さい時に遅く、nは通常小さい。凝ったアルゴリズムは定数部分が大きい。nが通常大きいということを知っているのでない限り、凝らないようにすること。（仮にnが大きいとしても、まずはルール2を適用せよ。）
凝ったアルゴリズムは簡単なものよりバグりやすく実装するのも難しい。シンプルなアルゴリズムとデータ構造を使うべき。
データこそが重要。正しいデータ構造を選んで、データをうまく表すことができれば、アルゴリズムはほぼ常に自明になる。アルゴリズムではなくデータ構造こそがプログラミングの中心となる存在である。
Mitsuaki Wadaステップ12: 制御構文を足す
これ以降は執筆中とのこと。未完成な部分があるので補完しながら読むことを想定している。
この章ではif, while, forを実装する。インクリメンタルにすすめる。
ifの実装
以下を実行できるようにする。if, elseは一つのstmtしか持たないことにする。
a = 10; b = 20; if (a > b) return a; else return b;
実装した: https://github.com/mi-wada/kanic/commit/c869a7905968393d09f33e61bec45cd9c12ab7f6
whileの実装
以下を実行できるようにする。whileは一つのstmtしか持たない。
a = 0;
while (a < 10)
a = a + 1;
return a;
# => 10
実装した: https://github.com/mi-wada/kanic/commit/e73a007c68ad5a21359d3ac2b6767bebb31c9079
forの実装
以下を実行できるようにする。forは一つのstmtしか持たない。
a = 0;
for (b = 0; b < 10; b = b + 1)
a = a + 1;
return a;
# => 10
実装した: https://github.com/mi-wada/kanic/commit/eab1889f63d45a728843a1368d1247c5c7b8e03a
Mitsuaki Wadaステップ13: ブロック