コンパイル中にコンパイルする「コンパイル時Cコンパイラ」をつくった話
僕は先日、「コンパイル時Cコンパイラ」なるプログラムをつくって、公開した。
「コンパイル時Cコンパイラ」とは、コンパイルするとC言語プログラムのコンパイルが行われるというようなC++プログラムである。
C++のコンパイル中に C言語プログラムのコンパイルを行う、
— うどん (@kw_udon_) 2016年11月18日
"コンパイル時Cコンパイラ"をつくりました #ELVMhttps://t.co/kKiLU3rLFX
自分で書いておいてなんだが、「なんのこっちゃ」という感じではある。(ちゃんと記事中で説明する。)
実際、変なプログラムではあるのだが、とても嬉しいことに多くの人に面白がっていただき、予想だにしなかった大きな反響をいただいた。 Hacker Newsで1位になったり、LLVMの公式ブログで紹介されたり、果てはC++の作者であるBjarne Stroustrupにも言及されるに至った。
今回はその「コンパイル時Cコンパイラ」について書こうと思う。
まずはそもそも「コンパイル時Cコンパイラ」とは一体何なのかということを説明をする。 次にそれをどうやってつくったかについて、そして最後に「もうひとつの」コンパイル時Cコンパイラについて、書こうと思う。
お付き合いいただけたら、幸いである。
この記事はC++ Advent Calendar 2016の3日目の記事として書かれました。
2日目の記事はC++ ヘッダとソースでファイルを分ける 応用編 - Qiita でした。4日目の記事は VS2017の新機能 · GitHub です。
そもそも、コンパイル時Cコンパイラとは？
コンパイル時Cコンパイラと聞くと、「コンパイルする時を、"コンパイル時"というのだから、コンパイル時コンパイラって当たり前なのでは？」と思う人もいるかもしれない。
だが、そういうことではない。 コンパイル時Cコンパイラは、「コンパイル時計算として、C言語コンパイルを行う」C++プログラムである。 C++er向けに書くと、「C++14のconstexpr関数として実装されたCコンパイラ」のことである。
ということで、まず、コンパイル時計算についての説明からはじめる。
C++のコンパイル時計算
コンパイル時計算とは、ざっくりいってしまうと、実行時の状態に依存しない計算を、前もってコンパイルの際にやってしまうことである。 それによって、その部分は実行時には定数として扱うことができるのである。
例として、以下のC++プログラムを考える。これは、実行時に「0〜100の合計を計算し、それを出力する」普通のプログラムである。
#include<cstdio> int sum(int n) { int x = 0; for (int i = 0; i <= n; ++i) { x += i; } return x; } int main () { int x = sum(100); printf("%d\n", x); }
このプログラムをコンパイルし、実行すると、"5050" が出力される。
さて、このプログラムは入力に依存したり、乱数を使ったりしていない。
そのため、出力される変数xの値は、常に"5050"である。
よって、もし、int x = sum(100); の部分を、 int x = 5050; としても、プログラムを実行する側にとっては、何も問題ない。
むしろ、実行の際に、ループを回して計算する必要がないので、こっちの方が実行時間は短くて済むので嬉しい。
ただ、この"5050" という値を別途計算して、手でソースコードに埋め込むというのは、全くプログラマ的ではない。 では、どうするか。 ここで出てくるのが、コンパイル時計算である。
先ほどのプログラムに、次のように constexpr キーワードを追加する。
#include<cstdio> constexpr int sum(int n) { // constexprを追加 int x = 0; for (int i = 0; i <= n; ++i) { x += i; } return x; } int main () { constexpr int x = sum(100); // constexprを追加 printf("%d\n", x); }
この constexpr は、"constant expression"(定数式)の略であり、コンパイル時に値が決定する定数やコンパイル時に実行される関数につけるキーワードである。
(詳しくはリファレンス)
よって、このプログラムをコンパイルすると、sum(100) の計算がコンパイル中に 行われるようになる。
その結果、コンパイルが終わった時には、"5050" という値は既に求まっており、実行ファイルに定数 として埋め込まれている。
そして、その実行ファイルは定数"5050"を出力するだけのものである。
constexpr内でかける処理に関しては制約はあるし、そもそも入力に依存する計算はコンパイル時にはできないので、コンパイル時計算は万能ではないが、実行時のパフォーマンスの向上のための有効な手段の一つである。
コンパイル時Cコンパイラ
さて、「0〜100の和の計算」を例にコンパイル時計算を説明してきたが、和を計算するだけじゃ、コンパイル時計算の力を引き出しきれているとは言い切れない。 もっと複雑な計算だって、コンパイル時にできるはずである。
そう。たとえば、コンパイルだってできるかもしれない。
コンパイラだって、言ってしまえばただのプログラムである。 そのため、コンパイル時計算としてコンパイルができても何も不思議ではない。
というわけで、コンパイル時計算として Cプログラムのコンパイルを行うのが、「コンパイル時Cコンパイラ」である。
これは、8cc というCコンパイラの、C++の定数式への移植とみることもできる。
「0〜100の和」の例との対比で、挙動を説明をしてみる。 先ほどのコンパイル時に和を求めるプログラムをC++のコンパイラ(たとえばg++)を使ってコンパイルし、実行すると、次のようになる:
- コンパイル中に「0〜100の和の計算」が行われ、
- "5050"という値が定数として、実行ファイルに埋め込まれ、
- 実行時に、定数である5050が出力される
これに対し、コンパイル時コンパイラをg++でコンパイルすると次のようになる:
ちなみに、入力に関してだが、constexpr関数は入力をとれないので、文字列化したCプログラムを、プリプロセッサでソースコードに埋め込むということをやっている。
ちなみに"Hello World"のコンパイルは、3分くらいかかるもののちゃんとできる。 メモリ8GBのラップトップで動作を確認している。 g++ 6.2が入っていれば、簡単に試せるので、よかったら試してみて欲しい。
何の役に立つの？
もし万が一、「コンパイル時Cコンパイラ、なんか便利そう!」と思ってここまで読んでくださった方がいらっしゃったとしたら、本当に申し訳ない。 僕の文章力不足だ。コンパイル時Cコンパイラは基本的に役に立たない。 コンパイル時CコンパイラでCプログラムをコンパイルするには、GCCが必要になるが、手元にGCCがあるなら、直接GCCでコンパイルすればよいのである。
コンパイル時Cコンパイラは、言ってしまえば、ジョークプログラムなので、 「名前の響きが面白い」とか、「C++のコンパイル時計算はこんなことまでできるのか」とか、そういうことを感じてもらえればありがたい。
コンパイル時Cコンパイラのつくりかた
さて、コンパイル時Cコンパイラとは一体何かということを説明したところで、じゃあ、どうやって作ったのか、という話に移る。
ただ、つくったとは言ったが、僕はコンパイラを自分の手で実装したわけではない。 ELVMという機構を利用し、C言語で実装された8ccをconstexprへ翻訳したのである。 それについて、書く。 これ以降、若干テクニカルな話になる。
8ccとは？
8ccはrui314さん作のCで実装されたセルフホストされたCコンパイラである。 C11をサポートしているのに1万行程度とコンパクトで、しかもわかりやすい綺麗なコードで書かれていて、非常にクール。 今回は、この8ccをELVMでconstexprへ変換するということをした。
ELVMとは？
ELVMとは、EsoLang Virtual Machineの略で、C言語プログラムから他の言語への変換を行うためのコンパイラ基盤である。 これを使うと、C言語プログラムをBrainF*ckプログラムに変換したりできる。
詳しくは作者のid:shinichiro_hさんのスライドがわかりやすい。 構造を軽く説明するとELVMは、
からできている。
このELVMをつかうと、例えば、
「フロントエンドでCコンパイラをIRに変換し、バックエンドでIR→BrainF*ckの変換を行うことで、BrainF*ckで実装されたCコンパイラを得る」
というようなことができる。 現在、ELVMのバックエンドはEsoLang(難解言語)を中心に、20個以上のターゲット言語に対応している。(README参照) それによって、色々な人の手によって、世界に変な言語によるCコンパイラ達が誕生した。
僕もこの流れに乗って、ELVMを利用した。 つまり、僕は実際にやったことは、ELVMのconstexprバックエンドを実装ということになる。
ELVMのconstexprバックエンド
さて、ELVMのconstexprバックエンドであるが、僕ははC言語バックエンドをベースに改造することで実装した。
Cバックエンドはこんな感じの、ELVM IRの実行をシミュレートするようなCプログラムが出力する。
ELVMのCバックエンド・constexprバックエンドの出力例 · GitHub
レジスタとメモリに対応するグローバル変数を用意して、プログラムカウンタpcの値によって、対応する処理を実行するというようなプログラムである。
ELVM IRとの対応も取りやすいとおもう。
僕が作ったconstexprバックエンドもこれと似たようなプログラムを出力する。 C++14でconstexpr関数内での制限が緩和されたおかげで(参考)、プログラムの構造はほとんど同じである。 とはいえ、まだ制約はあり、主に次の3点について工夫が必要だった:
- 入出力
- グローバル変数
- 関数間の状態共有
順に説明する。
1. 入出力
C言語バックエンドでは、getcとputcに対応して、それぞれ getchar, putchar を吐くようになっていたが、残念ながらこれらの関数は実行時にしか使えないので、工夫が必要であった。
これに関しては、id:bolerosさんの コンパイル時BrainF*ckコンパイラを参考にした。
具体的には、入力はプリプロセス時に文字列として埋め込むようにした。
そして、getc のたびにカーソルを文字列の先頭から動かしていき、値を取得する。
一方、出力はバッファに溜め、実行時にそれを出力するという形をとった。
2. グローバル変数
Cのバックエンドが吐くプログラムでは、メモリやレジスタをグローバル変数で管理していた。 しかし、C++14のconstexprでは、副作用は関数内にとどめる必要があり、グローバル変数へのアクセスはできない。 では、どうしたか。単純に、グローバル変数ではなく、関数内で定義するようにした。
3. 関数間の状態共有
これは2.に関連する。 C言語バックエンドが生成したプログラムはグローバル変数を使って、関数間で状態の共有を行っていたが、2 でそれができなくなった。 複数の関数で変数の状態を共有するには、いちいち値をコピーして引数として渡さなければならない。 それは計算コストがかかるので嫌だ。 では、どうしたか。関数間で状態を共有しないですむように、全部の処理を一つの関数内で完結するようにした。 つまり、処理を全部巨大constexpr関数内でやる感じ。力技である。
大体こんな感じだったので、あまり技術的困難さは感じなかった。
そうしてできたconstexprバックエンドをつかって、8ccを変換してできたのが、8cc.hppである。
約150000行・2.8MBの巨大ファイルである。
eight_cc というconstexpr関数が本体なのだが、こいつはcaseの数が8300個以上の巨大switch文をもっているといった感じだ。
まぁ、人間が読むものではない。
constexpr-8ccを試すには、cloneしてきて、
$ g++-6 -D'EIGHT_CC_INPUT_FILE="./test/putchar.c.txt"' ./8cc.cpp
としてみればよい。
ファイル"./test/putchar.c.txt" の中身は、文字列化されたCプログラムである。これがプリプロセッサによって、ソースコードに埋め込まれる。
そして、それを入力とみなして、コンパイルが行われるのである。
ちなみに、これはg++6.2必須である。
Clangだと、constexprによるコンパイル時計算のステップ数に上限があり、それに引っかかってしまう。(GCCには上限がなさそうだが、未調査。)
また、g++ 5系で動かそうとすると、index_tuple のinstantiationの深さが上限を超えたというエラーで動かない。（5系と6系にどんな違いがあるのかは調査してないので、理由は不明）
こうして、ELVMのconstexprバックエンドができたわけであるが、これを使えば、色んな「コンパイル時〇〇」が簡単にできる。
「〇〇」をするプログラムをC言語で実装して、ELVMで変換かければ、あっという間に「コンパイル時〇〇」をするプログラムができるのである。 これはもう、なんでもコンパイル時にできてしまう時代の幕開けかもしれない。（これは冗談で、流石にそんなことはない）
余談: 反響について
冒頭にも書いたが、ありがたいことに、constexpr-8ccは色々な人に面白がっていただいた。 本当に嬉しかった。(嬉しさからエゴサしまくったのは恥ずかしいので内緒)
どうも、Hacker Newsで1位になったのがきっかけだったのかとおもう。 C++14でconstexprの制約を緩和してくださった方にも届いたようである。 また、ELVMはLLVMのパロディであるが、それが公式であるところのLLVMに言及されたのも面白かった。LLVM Weeklyという公式のブログ中にもコメントがある。
そして、その後、C++の作者であるBjarne Stroustrupにまで言及されるに至った。 偶然にもちょうどMeeting C++というカンファレンスが行われていたタイミングだったようだ。
btw, Bjarnes comment on the constexpr C++14 C compiler during #meetingcpp was, "its only a C compiler if it handles pointers and unions".
— Meeting C++ (@meetingcpp) 2016年11月20日
インターネットすごい。本当にびっくりした。
ちなみにこのコメント、はじめ読んだ時、"handles" の主語の it が何を指しているか掴めず、意味がわからなかったが、 pointerとunionが扱えないということから、この"it"は"constexpr"なのではないかと思われる。*3
ひとつ目のitはコンパイル時コンパイラだと思うので、訳してみると、
「もしconstexprでポインタと共用体が扱えるようになったら、コンパイル時コンパイラはただの(実行時)Cコンパイラになるだろう」
みたいな感じだろうか。 constexprの自由度が高まってきており、もう少しで、コンパイル時と実行時でできることに差異がなくなりそう、みたいな意味かと思う。
文中のconstexprでポインタが扱えないというのは、mallocのような動的なメモリ確保ができないことかとおもう。 また、共用体が扱えないというのは、次のようなコードの話だと思われる。
union Uni { float f; int i; }; constexpr int f() { Uni u = {1.0f}; // 初期化したのは'f'なので、 return u.i; // 'i'にはアクセスできない } int main() { constexpr int x = f(); // なので、コンパイルエラー return 0; }
ちなみに"handles" の主語の itを「コンパイル時コンパイラ」としても
「もしコンパイル時コンパイラがポインタと共用体を扱える(サポートしている)なら、単なるCコンパイラである」
となって意味は通るのだが、なぜわざわざ「ポインタと共用体」がでてきたのかということがわからなくなる。 8ccはもちろんポインタと共用体を使ったプログラムもコンパイルできる。 また、Cコンパイラにおける共用体のサポートは、構造体をサポートしていれば容易にできるはずである。 そのため構造体より使用頻度の低い(はず)の共用体をわざわざ名指しするのには違和感がある。
ただ、なんか勘違いをしてるかもしれないので、指摘・ツッコミがあればよろしくおねがいします。
「もうひとつの」コンパイル時Cコンパイラ
さて、ここで記事を終わりにしてもよかったのだが、せっかくなので、「もうひとつ」のコンパイル時Cコンパイラの話も書こうと思う。
C++のコンパイル時計算はconstexprの他に「もうひとつ」ある。
そう、テンプレートメタプログラミング(TMP) である。
というわけで テンプレートメタプログラミングによる コンパイル時Cコンパイラがこちらである。
だが、このコンパイラの実行、すなわちGCCでのコンパイルは絶対にやってはいけない!! GCCがメモリを喰らい尽くしてしまうからだ。
というわけで、カッコつけて「もうひとつの」なんて書いてしまったが、このTMP-8ccは、動かすことのできない、失敗作の 観賞用のコンパイル時Cコンパイラである。
constexpr版コンパイラができたので、こちらはお蔵入りにする予定だったが、せっかくなので(蛇足かもしれないが)その話も書くことにした。
経緯
時系列的にいうと、TMP版を作り始めたのはconstexpr版よりも前の話である。 まず、TwitterでELVMを知った時に思い出したのが @akabeさん作のEvil ML である。 Evil MLはMLのプログラムをC++テンプレートに変換するコンパイラである。 じゃあ、これみたいな感じで、ELVMのC++テンプレートバックエンドを書いたら面白いのではないかというように着想を得た。
ELVMのTMPバックエンド
テンプレートメタプログラミング(TMP)は、C++のテンプレートを純粋関数型言語とみなしてプログラミングを行うものである。 そのため、ELVMバックエンドを実装するにあたって問題になるのは、環境の破壊的変更をいかにシミュレートするかということである。 ここでいう環境とは、VMのレジスタ・メモリの状態・入出力バッファである。例えばメモリへの書き込みなどが破壊的変更にあたる。
この問題にはStore-passing Styleというテクニックを使えばよい。 これは状態(あるいは環境)を関数間で引数・返り値として、持ち回すというものである。
別に難しい話ではなく、
引数 → 返値 という副作用ありの関数のかわりに、
(引数、環境) → (返値、新しい環境) というような副作用なしの関数を書くというイメージである。
このテクニックは、関数型プログラミングで副作用を扱えない・扱いたくないときによくつかわれる。
というわけで、ELVMのTMPバックエンドをつくるにあたって、まず、ELVMの各命令に対応する処理をテンプレートで実装したライブラリ的なものをつくった。 それがこれである。 見てもらえばわかるが、movやstoreなど各命令に対応する処理がかかれている。 また、メモリを2分木として実装するなどしている。
そして、ELVMでのバックエンドが吐くプログラムはこれらの処理を呼ぶようにした。
そうして、できたTMPバックエンドはforkしてきたレポジトリで別ブランチとして公開している。
$ CPP_TEMPL=1 make cpp_templ とすると、いくつかテストが走る。(が、最後までは動かないので、適度なところでkillしてやる必要がある。)
Gistに出力例をおいておく。 ELVMの変換例: EIR, C++Template, C, constexprの比較 · GitHub
イメージがつきやすいように抜粋すると、
mov B, 77 store B, 300 load A, 300
というような命令は、
typedef mov_imm <r0, b, 77> r1; typedef store_imm<r1, m0, b, 300> m1; typedef load_imm <r1, m1, a, 300> r2;
というように変換される。
r0, r1はレジスタの状態に対応する型、m0,m1はメモリの状態に対応する型である。
一行目は、今のレジスタの状態r0 と レジスタ名 b、値77を引数として、mov_immという関数に渡すと、レジスタbの値が77に書き換えられた新しいレジスタの状態r1が得られるというような感じで読める。
ちなみにこの記事を書いている最中に、id:iroriさんによるELVMのUnlambdaバックエンドの記事が公開された。(前編、後編) Unlambdaは難解言語の一種で、純粋関数型言語である。そのため、僕のTMPバックエンドの実装方針と一部似ている部分がある。 しかし、Unlambdaのほうがずっと制約もきつく、より面白いことをやっているように思える。
ただ、このTMPバックエンド、できたはいいものの、生成されるコードはまともに動かない。 手でかかれたELVM IRから生成したコードはある程度動くが、Cから生成されたものになると全然だめである。
具体的にどれくらい動かないかというと、FizzBuzzで10まで表示させるプログラムの計算に約10分 かかり、メモリを82.5GB程度使う。たまたまAWSの無料クレジットをもっていたのでRAMが100GB以上のインスタンスを借りて、なんとか動かすことができたというレベルだ。
しかも、この使用するメモリの量は実行ステップ数が増えるにつれて、ガンガン増えていく。 (計測は十分ではないが、一応FizzBuzzで5までの場合は約1分半、使用メモリは16GB程度だったので、メモリ使用量増加のオーダーはステップ数の線形では済まないっぽい。)
注意してほしいのは、これはFizzBuzzプログラムのコンパイルではない。0, 1, 2, Fizz, ... と出力するだけである。
FizzBuzzの実行ステップ数とCプログラムのコンパイルの実行ステップ数は比べ物にならないはずなので、TMPバックエンドによるTMPコンパイル時Cコンパイラの実行は絶望的である。
TMP-8ccが動かない理由
さて、どうして、そんなにメモリを食うのだろうか。 Unlambdaの方が実装上の制約はきついのに、(1日以上かかるらしいが)動いているのだから、TMPの方も動いてもよいのではないか。
UnlambdaCコンパイラが動いて、TMP Cコンパイラが動かない原因は、端的にいうと処理系におけるメモリ解放の有無だと考えられる。
Unlambdaでは、新たな環境が作成されたら、古い環境はもう不要なので、インタプリタ上のGCによって解放される。
一方で、TMPでは不要になった古い環境も保持される。というのも、「環境」といっても実のところ、C++における型情報だからである。 C++コンパイラの気持ちになれば、判明した型情報を最後まで保持しておくのは、当然である。
これはつまり、TMPバックエンドが吐いたプログラムは、今までの環境の履歴を全てメモリ上に保持し続けながら計算が進んでいくということを意味する。 例えば、storeが行われるたびに、メモリの全コピーをすることになるが、そのとき、コピー前のメモリの状態も全てメモリ上に残るのである。 こんなの、現実のマシンでまともに動くわけがない。
TMP-8ccを動かすには、要らなくなった型情報をガンガン捨てていくTMP専用C++コンパイラをつくる必要がある気がする。(そんなことができるのかはよくわからず、適当書いている)
ちなみにTMPバックエンドで生成したプログラムがまともに動かないことに気づいた頃に、shinhさんがELVM公開直後にしていたこんなツイートを見つけた。
「TMPのアイディア自体は既出で、まともに動かないことまで予期されていたのか」と少し悔しくなった。ELVMで8ccをC++ templateに変換してC++くらいになるとコンパイルタイムにコンパイラが動くぜ？てネタをやろうかと思ったけど現実的な時間で動く気がしない。D compile-timeだと自明だろうしなあ
— shinichiro hamaji (@shinh) 2016年10月18日
ただ、個人的にはTMPは今回のためにはじめて触ったこともあり、やってみなければ無理だということもわからなかったので、やってよかったと思う。 それに、shinhさんはconstexprバックエンドまでは考えていなかったっぽい。 個人的には最終的にconstexprという良い着地点が見つかって、コンパイル時Cコンパイラを実現できたので、満足であった。
Related Work
最後に、関連する他プロジェクトについてまとめておく。
Cプログラムから、他言語への変換ができることは言われてみればそれはそうだが、実際に実装し、しかも現実に動くものをつくってしまうのはすごい。 また、バックエンドも書きやすいように設計されており、とてもありがたかった。
今回僕はコンパイラをつくったといっても、実質変換器を書いただけであったが、以前、Cコンパイラを実装したこともある。 8ccを知ったのはその頃だ。とてもわかりやすくかかれているので、「Cコンパイラって案外自分でもかけるかも」という気持ちにさせられた。 また当時、作者のruiさんの8ccを開発したときの日記も読んで、奮い立たされたのを覚えている。 そのようなこともあり、今回、ruiさんにも面白がってもらえたのは、個人的にかなり嬉しかった。
- ELVMで作られた他のコンパイラ達
昨日・今日で各アドベントカレンダーの記事として、ELVMの色々なバックエンドに関する記事が公開された。 バックエンド言語ごとの工夫があって、楽しい。
- Unlambda UnlambdaでVMを実装する（前編） - iroriの日記, UnlambdaでVMを実装する（後編） - iroriの日記
- Vim Script ELVM で C コンパイラをポーティングしてみよう（Vim script 編） - はやくプログラムになりたい
- TeX ELVMにTeXバックエンドを足した話 - hak7a3が書き残す何か
MLから、C++テンプレートへ変換するコンパイラ。TMP-8cc のセクションでも触れたとおり、ELVMのバックエンドとして、C++のテンプレートをやってみようという発想は、これに影響された。
C++14のconstexprで実装された、Brainf*ckコンパイラ。
僕のは世界初のconstexprで書かれたコンパイル時Cコンパイラのはずだが、単にconstexprで書かれたコンパイル時コンパイラ」としてなら、こっちが世界初だと思われる。
入力を#include で埋め込むといったアイディアなどはここからいただいた。
また、作者の中３女子さんはconstexprに関してライブラリや多くの資料を公開されており、それらも実装の際に参考にさせていただいた。
- 手書きのC++11 TMPによる"ちゃんと動く"コンパイル時Cコンパイラ (2018年追記)
本文中ではTMPによるコンパイル時Cコンパイラを動かすことを諦めたと書いたが，本記事公開から約1年後の2017年12月に現実のマシンで実行できるTMPによるコンパイル時Cコンパイラが登場した． それがltmpcである． これは自動生成ではなく，手で実装されており，TMPの色々なテクニックをつかって，メモリ消費量の問題に立ち向かっている． 本当に凄い． Qiitaにある解説も詳しい．
以上が、「コンパイル時Cコンパイラ」をつくった話である。 ELVMをいじって、コンパイル時Cコンパイラをつくるのはめちゃくちゃ楽しかった。 ELVM作者のshinhさんと、8cc作者のrui314さんには感謝したい。 みなさんも、ELVMで遊んでみてはいかがでしょうか？
ちなみに、shihさんは、今、TensorFlowバックエンドを実装しているようである。 意味がわからない。面白すぎる。
おわり
自作CPU向けCコンパイラをつくってOS動かした話 (CPU実験まとめ)
僕の学科では伝統的に3年の後期に半年かけてCPU実験というものをおこなう。 班で自作のアーキテクチャを設計・実装し、FPGA基板上でMinCaml(OCamlのサブセット)でかかれた課題用レイトレーシングプログラムが動けば単位がもらえるというものである。
レイトレ完動後には、その高速化にはげむもよし、余興としてゲームをつくるもよしで、自作CPU上で色々あそんだりする。
今年は有志で班を結成し、自作CPU上でxv6というOSを動かした。 僕はその班にCコンパイラ係として参加したので、そのことについてかく。 あと、OS移植班全体の成果についても触れる。
わりと長くなってしまったので、結局なにができたんだっていう人は、とりあえず先にこっちに飛んでほしい。
動機
期間は4ヶ月程度、配布されたFPGA基板のうえで動かしたいという制約のもとで移植するOSはxv6を選択した。 このOSはシンプルであるが、十分な機能をもっている上に、MITで教育用として講義でつかわれているようで、資料が豊富という利点がある。
ただ、このOSはC言語でかかれているという問題があった。
OSがCでかかれている事自体は普通のことであるが、CPU実験の課題プログラムはMinCamlでかかれているため、CPU実験に関してコンパイラというと、MinCamlを改造したものを指すのが一般的である。 そのため、MLコンパイラは用意できるのだが、xv6をすべてMinCamlで書き直すのはさすがに厳しい。
というわけで、OSの移植のまえに、自分たちのCPU向けにC言語コンパイラがつくろうということになった。
既存のCコンパイラを自分たちのアーキテクチャ向けに移植するという手もあったが、せっかくだしフルスクラッチで実装した方が面白そうだよね ということで１から自作することにした。
対象とした自作CPUは、今年最も早く完動した3班の2ndアーキテクチャであるGAIAにした。 命令セットも独自のものを採用している。
つくったコンパイラについて
作成したコンパイラはこれ。
UCCという名前で開発した。OCamlで実装されており、ANSI-Cの大部分をサポートしている。
ANSI-Cの主要な機能で非サポートなのは、ビットフィールドと構造体を返す関数くらい。
どちらもOSのソースコード内でつかわれなかったので、実装コスト的にサポートするのをやめた。
ANSI-C外の機能としては、独自のインラインアセンブラをつかえるようにした。
libcについては、必要に応じて自分たちで実装していって、サブセットがつかえる。
開発は、自分の班でのタスクが区切りがついた11月中頃から僕が開始し、その後wasabizとb-inaryが加わって3人で開発した。 （wasabizはCPUの実装、b-inaryはシミュレータ・アセンブラの実装も兼任）
という順でおこなっている。
プリプロセッサはclangのものをコンパイラを利用した。
また、UCC本体にCのコードを渡す前に、clangのfsyntax-onlyオプションでの文法チェックをかませるようにしている。
UCC本体では、 ocamlyaccで生成したパーサで抽象構文木を作成し、 その後、木を２回トラバースして、自作アーキテクチャ向けアセンブリを生成する。
割とシンプルでわかりやすい構成に実装できたとおもう。
実装の際には最適化より、バグなく正しく動くものをできるだけ早くつくることを意識した。
たとえば、簡単のため、変数はすべてメモリ上に割りつけることにしている。
また、テストを重視した。
proveコマンドを利用して簡単に一括テストできるようにし、機能を追加するごとにテストコードも追加していった。これにより、変更によって、以前つくった機能を壊してしまうようなことを防げた。
xv6の移植作業を開始してから、特に大きなバグが見つかることもなく、安定して動作したので良かったと思う。
動いたものとか
最終的な目標はxv6の自作CPU上での動作であったが、それまでの間、コンパイラのバグ発見も兼ねて、いくつか、ある程度の大きさのプログラムをコンパイルをしてみたりした。 そのことについて書く。
benz
これはwasabizのつくっているscheme処理系である picrinの移植向けサブセット。
この頃はUCCが、まだ浮動小数点数の実装途中だったり、charを簡単のために32bitで扱っていたため(Cの規格的には一応これでもOKだけど、その後8bitに修正した)、benz側でも色々な対応をしてもらった。 wasabizの記事が詳しい。
benzはlibc非依存なので、UCC側では最低限必要なアーキテクチャ依存部分である、setjmpとmallocを実装した。 mallocはK&Rに載っている実装をもってきたのだが、今までmallocの実装なんて考えたことがなかったので、勉強になった。K&Rは偉大。
結果、schemeインタープリタが自作CPU上で動いた。ちゃんとGCとかもしている。 それまでは、テスト用で書いたプログラムしか動いていなかったので、とても嬉しかった。
min-rt.c
CPU実験といえば、レイトレーシングというわけで、レイトレーシングプログラムであるmin-rtを実行したかったのだが、これはMinCamlで実装されている。 というわけで、min-rt.mlを自分でCに移植して、それを動かした。 これには浮動小数点数まわりの実装のバグチェックという役目もあった。
変数をレジスタに割り当てていない分、MinCamlを改造したコンパイラにくらべて、実行命令数は多くなったが、これも実機で完動した。
min-rt.cは割と丁寧に移植したつもりだし、もし来年度以降とか、CPU実験でCコンパイラつくることがあったら、テストプログラムとして使えるとおもう。
（追記：コメントとtwitterで教わったところ、min-rtのC実装はこことかここに既に存在していた。 かかれたコメントをみると、オリジナルがかかれたのが30年以上前で、それからぐるぐる色んな言語で書き直されてきたらしい。歴史を感じる。）
xv6
リポジトリはこちら。
こいつが本命だった。
このためには、コンパイラの他に
という仕事が必要であった。
これらについては、コンパイラの開発と並行して、他の班員たちが分担しておこなっていた。 完動までに具体的にどんなことを行ったかについては詳しいことは僕も把握できていない部分があるので、他の班員が記事かいてくれることに期待。
3月1日にシミュレータ上で動作し、9日に実機で動作した。 OS係もコア係も線表みたいなのをつくって、予定通りにそれを消化していって最終的に完動にもっていっていて、とても強かった。
追記 : OS移植班(X班)の他の班員の記事
- コア係 (UCC係も兼任)
- OS係
一応どんなことができるようになったかを書いておく。
（僕はリーダーとかでもなく、一人の班員としてコンパイラをつくっただけなので、僕が成果として書くのは気が引けるけど、誰もかかないのはよくないので）
とりあえず、デモとしては、このMakefileで
make runとやれば、
uccとシミュレータとアセンブラとxv6本体がクローンされてきて、UCCでOSがコンパイルされ、
シミュレータ上でOSが起動して、シェルのプロンプトがでてくるはず。
lsとやれば、実行可能なユーザープログラムがみれる。
UCC自体のコンパイルのために、OCamlとかが必要。
UbuntuとMacで動作確認済。シェルの設定によってはうまくいかないことがあるかも。
（追記：Macではシミュレータ内のtermiosの設定の問題で入力ができないっぽい）
追記(7/1) id:nullpo_headがEmscriptenを使って、ブラウザ上でデモを動かせるようにしたので、手軽に試せるようになった。（強い）
https://nullpo-head.github.io/emcc-gaia-simu/xv6.html
追記ここまで
ユーザープログラムとしては、xv6に元からはいっているlsとかcatとかgrepの他に、slとか2048などをユーザープログラムをつくってくれたので、それらで遊べる。2048は色もついていて普通に楽しい。 あと、viライクなスクリーンエディタもある。 OS係すごい。
簡単なアセンブラも用意したので、OS上でアセンブリプログラミングもできるようになった。
libcはxv6自前のものは貧弱だったので、自分たちで実装したものをつかった。そのため、FILE構造体とかつかえている。 ちなみにfopenはK&Rに載っている実装をもってきたのだが、今までfopenの実装なんて考えたことがなかったので、勉強になった。K&Rは偉大。（２回め）
そして、CPU実験といえばレイトレというわけで、OS側からmin-rtを呼び出せるようにもした。 min-rt.cはユーザープログラムとしては大きすぎたので、デバイスとしてカーネルに組み込んだ。 その結果、OS上でレイトレーシングができるようになった。
OS上で動作しているので、タイマー割り込みとかの処理も含まれるので、実行時間は生のCPU上で動かすのよりも自明に時間がかかるのだが、実機ではプログラムロードの時間を含めても2分以内に動作した。コアがとても優秀だった。
レイトレ on OS on FPGAは、序盤のうちからの夢であったが、正直実現するとは思っていなかった。 しかも、実際にこれができたのは最終発表会の数時間前だったので、本当に嬉しかった。
やり残し
もし、期間がもっとあったら、やりたかったことについて書く。
libcの強化
UCCで何ができるか考える過程で、Luaなどの言語処理系のコンパイルしてみたのだが、文法はUCCのサポートしているもので十分であったようだが、libcに依存していたため、断念した。 既存のlibcを移植するという手もあったが、アーキテクチャ依存の部分もあり、時間がかかりそうだったので、諦めた。 libcをサポートすれば、もっといろんなことができただろう。
セルフコンパイル
UCCはOCamlでかかれたCコンパイラなので、セルフコンパイルはできない。 でももし、コンパイラ自身がCで実装されていて、セルフコンパイルができれば、OS上でC言語プログラミングができるはずである。
OCamlは言語処理系を作る言語としては優れていると思うし、UCCをOCamlで実装したのは悪い選択ではなかったと思う。 本質的でないところで悩んだりバグを埋め込んだりすることは少なかったし、実装量も少なくて済んだ。 でももし、時間が十分にあったら、二代目のコンパイラをCで実装していたかもしれない。
linuxの移植
これはUCCのというより、OS移植班全体の野望。 今回移植したxv6は教育用OSということで、コンパクトであった。 それに比べて大きいlinuxを自作CPU上で動かせたら嬉しいよねという感じ。
ちなみに最終発表はおわったけど、FPGA基板はまだ借りられているから、CPU実験延長戦ってことでこれらはやるかもしれない。
感想
CPU実験は、つらくなったこともあったが、全体としてかなり楽しめた。 学科に入った当初は、情報科学のうち、アルゴリズムとデータ構造とかの、コンピュータをどう使うかというもっと上のレイヤーの部分にしか興味がなかったが、興味の幅が広がった。
OS移植班は全員で8人くらいだったが、割とうまくチームとして機能していたように思える。
コアも、OSの移植作業も、シミュレータ・アセンブラのどれが欠けても動かなかったわけなので、みんなすごいなぁ。
こんなに本格的な共同開発の経験ははじめてだったので、とても良い経験になった。
特に、UCCを一緒に開発した他の二人は、とても強い人たちで、色んなことを教わったし、本当にありがたかった。
ガンガン進捗うまれたし、良い環境であったなぁ。
また、C言語についても、とても理解が深まった。
コンパイラ実装始めるときは、C言語ははじめて覚えたプログラミング言語で、もう2年半くらいつかってるし、わかってるつもりだったけど、全くそんなことはなく知らないことばっかりだった。
K&Rには大変お世話になった。（特に付録の章）
あと全然関係ないが、これがこのブログの最初の記事である。 正直、記事かくのがこれっきりになってしまいそうな予感がしている。 それはよくないので、今後もなんか書ければいいなぁ。
おわり
