セキュリティキャンプ 2019 Y-II Cコンパイラを自作してみようゼミ成果報告 (公開版)

Author: hiromi_mi

セキュリティキャンプ2019 Y-II Cコンパイラを自作してみようゼミに参加し、Cサブセットコンパイラ github:hiromi-mi/hanando-fukui を書いています。従って、最終日に成果報告として報告したスライドを書き出し、些細な訂正を加えたものを掲載します。何かしらの参考になればと思います。

応募用紙のほうは hiromi_mi によるセキュリティキャンプ2019 Yトラック Y-II Cコンパイラ自作ゼミの応募用紙に別途掲載してあります。

Y-II Cコンパイラを自作してみようゼミ概要

Cソースコードからアセンブリコードを出力するコンパイラを資料低レイヤを知りたい人のためのCコンパイラ作成入門に従って書いていく。この資料ではインクリメンタルに開発するのが特徴。基本的に開発途上であっても何かしらのC のサブセットをコンパイルできる状態が維持される。

規格や ABI の必要な部分を参照しつつ、事前学習とセキュリティキャンプのうち2,3,4 日の3日間でひたすら開発を進める。

また、分からない箇所や取れないバグを講師に質問しつつ行なうことで、開発を素早く進めることができた。

(2018年度の記事ではあるが) 講師の一人である @rui314 さんによる Cコンパイラ制作の夏期集中コースが思っていた以上にうまくいった話および他の参加者の様子を調べるとよいかもしれない。

おやくそく

まず、既存の Borland C Compiler, gcc, clang などへの敬意を込め以下「Cサブセットコンパイラ」と表記します。

Cサブセットコンパイラ自作の流行とともに怖がられていたり、不愉快に思われているのに悲しい気持ちを持っています。ここは成果報告の場なのできちんと報告は行ないますし、インターネット上にも公開します。

しかし進捗の状況で他人を煽る意図は決してありませんし、筆者の振る舞いや公開情報で他人を不愉快にさせるのは何としても回避したく思います。

当日は他の参加者の進捗を数枚のスライドをもとに概観しました。同士の成果量を比べるのは避けてほしい気持ちです。

未実装

以下、一般的なコンパイラには備わっているが、筆者が実装しなかった内容を列挙する。"手抜き" あるいは "取捨選択"とも呼べるかもしれない。

(筆者の成果報告が過度に誇張されたり誤解されるのを防ぎ、読者を不愉快にさせるのを可能な限り避ける意図があります。)

ほとんどの型検査
private, public チェック (間に合わず)
double 型や unsigned などの修飾子
goto 文
仮想関数テーブルやクラスの継承, new, delete
for(;;)

事前学習

セルフホスト (3月下旬→5月1日)

セルフホストとは自分で自分自身を幾度もコンパイルできる状態であり、

gcc
→ hanando (./hanando)
→ hanando (./main)
→ hanando (./main2)

このような順序で main.c のコンパイルを試みたとき、これらが全て同一出力を出力する。

追記: なお、セルフホスト成立後の v.1.1.1 の時点でのソースコード行数を cloc にて調査すると、おおむね2100行程度。

[~/devel/hanando-fukui]$ cloc main.c main.h
       2 text files.
       2 unique files.
       0 files ignored.

github.com/AlDanial/cloc v 1.82  T=0.04 s (48.8 files/s, 57830.9 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
C                                1            139            110           1954
C/C++ Header                     1             14             13            142
-------------------------------------------------------------------------------
SUM:                             2            153            123           2096
-------------------------------------------------------------------------------

さて、セルフホストを検証する。 make selfselftest を実行すると自身を幾度も自分自身でコンパイルし、結果出力されるアセンブリを diff -c を用い比較する。差分がないことがわかる。

[hanando-fukui]$ make selfselftest
./hanando -r -f main.c > main.s
gcc -g main.s -o main
./main -r -f main.c > main2.s
gcc -g main2.s -o main2
./main2 -r -f main.c > main3.s
gcc -g main3.s -o main3
diff -c main2.s main3.s
diff -c main.s main2.s
[hanando-fukui]$

レジスタマシンへの変更

資料はスタックマシンベースで書かれているが、次の理由からレジスタマシンへ移行させた。

ゆくゆく最適化しやすいように
レジスタはメモリ上にあるスタックと違い高速

一方、レジスタマシンの実装では一般にレジスタ割り付けなどを行なう必要がある。しかし、この際、凝ったことをせず必要になったらレジスタを retain_reg() にて確保、ノード評価終了後破棄するように実装した。

その結果、 v2.0 時点で、 main.c のコンパイル結果では (割り算などの特殊用途や関数引数を除き) 3レジスタ r10 r11 r12 しか必要ないことがわかり、そのことに驚いた。

セキュリティキャンプ期間中

期間中に実装したものは次の通り。

クラス機構のほんの一部
- スタティックな Hoge::fuga()など
- インスタンス化されたメソッドの呼出
- 問題点: this はない
最適化
- 定数畳み込み
- inline function expansion (デバッグ中)
関数ポインタ
デバッガによるステップ実行
組み込み型における静的ディスパッチ

このうちいくつかを取り上げて詳細を述べる。

クラス機構の一部

class 定義を実装し、その関連のスタティック関数の呼び出しやインスタンス関数を呼び出せるようにした。問題点として this キーワードが未導入であり、 private などのアクセス指定子が未実装などがある。

なお、次にあるソースコード例に Vim や Emacs とある。これは、名前マングリングが行なわれると関数のデバッグが行ないにくく、さてアセンブリコードを検索した際に見つけやすい名前にしようと考えた結果である。

// $ ./hanando -r -f -cpp test.cpp > test.s && clang -g test.s -o test && ./test

class Test {
   public:
   int a;
   char b;
   static int func();
   static int Vim(int c);
   int instancefunc();
   int Emacs();
};

int Test::Emacs() {
   printf("From Test::Emacs!\n");
   return 8;
}
static int Test::Vim(int c) {
   printf("From Test::Vim %d\n", c);
   return 1;
}

int main() {
   Test c;
   c.a = 9;
   Test::Vim(32);
   c.Emacs();
   return 0;
}

実行結果は次のようになる。正しく実行されていると分かる。

$ ./hanando -r -f -cpp cppsamples/test2.cpp > cppsamples/test2.s
$ gcc -g cppsamples/test2.s -o test2
$ ./cppsamples/test2
From Test::Vim 32
From Test::Emacs!

ステップ実行

hanando で出力した実行ファイルをデバッガ (GNU Debugger) で追うために、ステップ実行できるようにした。GNU Assembler の .loc や .file 疑似命令を用いた。

なお、変数の内容を確認するには、バイナリにデバッグ情報を埋め込む必要がある。その規格に DWARF, STUBS があり、DWARF は挫折し、STUBS は埋め込みバイナリがうまく gdbで検出されず挫折した。

以下の実例では、 ./main というセルフホストしたバイナリの main() 関数にブレークポイントを設定し、ステップ実行を行う。

[hanando-fukui]$ make self
./hanando -r -f main.c > main.s
gcc -g main.s -o main
[hanando-fukui]$ gdb -q --args ./hanando -r -f main.c
Reading symbols from ./hanando...
(gdb) b main
Breakpoint 1 at 0xd863: file main.c, line 4108.
(gdb) r
Starting program: /(パスは編集した)/hanando-fukui/hanando -r -f main.c

Breakpoint 1, main (argc=4, argv=0x7fffffffe4f8) at main.c:4108
4108       if (argc < 2) {
(gdb) n
4111       test_map();
(gdb) n
4113       tokens = new_vector();
(gdb) n
4114       int is_from_file = 0;
(gdb) n
4115       int is_register = 0;

静的ディスパッチ

いわゆる "テンプレート"のごく一部

2019/8/19 時点でクラスに対するディスパッチを実装しており、また実装方針が変更になることがあろうが、ひとまず現時点での実装は、関数呼出を構文解析する際にはじめて型が分かるので、そのときに実体化したアセンブリコードを出力するものである。

また、double は未実装であるから、以下の例では同じ T add(T, T) 関数を int とchar 型に対して実体化して、計算結果がオーバーフローするか否かで動作を検証した。

なお、現時点ではテンプレートの多重展開ができない、またクラスに対して適用できない問題点がある。

追記: 成果発表時には char や int などの組み込み型のみ対応だったが、そののち組み込みでない型にも対応した。

#include <stdio.h>
template<typename T> T add(T a, T b) {
   T c;
   c = a+b;
   return c;
}

int main() {
   printf("int: %d\n", add<int>(234, 123));
   printf("char: %d\n", add<char>(234, 123));
   return 0;
}

実行結果は次の通り。 char 型とint 型で異なる値を返していると分かる。

[hanando-fukui]$ ./cppsamples/test3
int: 357
char: 101
[hanando-fukui]$

その他

追記: 今日8月19日時点でのソースコード行数を cloc にて調査すると、次にあるようにおおむね3780行程度。

$ cloc main.c main.h
       2 text files.
classified 2 files
       2 unique files.
       0 files ignored.

github.com/AlDanial/cloc v 1.82  T=0.06 s (34.1 files/s, 75068.5 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
C                                1            306            285           3573
C/C++ Header                     1             17             15            207
-------------------------------------------------------------------------------
SUM:                             2            323            300           3780
-------------------------------------------------------------------------------

感想および今後

綺麗に実装しないとバグだらけで身動きがとれなくなる
規格はよくできている、先人は偉大
- これに関連して、規格の理解が曖昧なまま実装すべきではないと分かる。 (出来てない)
実装前に理解と実装方針を整理するのは有効
傲慢ではなく謙虚に、地味に地道にやっていく

追記: 今後 Map<T, U> や Vector<T> を実装し、コンパイラ内で使われている Vector や Map などのデータ構造を置き換えたい。

謝辞

Y-II ゼミの参加者チューター講師の方々ありがとうございました。
- 講師の @hikalium さん @rui314 さん
- 参加者の方々、とくに @takoeight0821 さん

そのほか、裏で支えておられる (取りやすいようペットボトルを三角形に並べるなど) スタッフや SCNOC の方々にも感謝します。

セキュリティキャンプ 2019 Y-II Cコンパイラを自作してみようゼミ 成果報告 (公開版)

Y-II Cコンパイラを自作してみようゼミ 概要