読者です 読者をやめる 読者になる 読者になる

コンパイル中にコンパイルする「コンパイル時Cコンパイラ」をつくった話

僕は先日、「コンパイル時Cコンパイラ」なるプログラムをつくって、公開した。

「コンパイル時Cコンパイラ」とは、コンパイルするとC言語プログラムのコンパイルが行われるというようなC++プログラムである。

自分で書いておいてなんだが、「なんのこっちゃ」という感じではある。(ちゃんと記事中で説明する。)

実際、変なプログラムではあるのだが、とても嬉しいことに多くの人に面白がっていただき、予想だにしなかった大きな反響をいただいた。 Hacker Newsで1位になったり、LLVMの公式ブログで紹介されたり、果てはC++の作者であるBjarne Stroustrupにも言及されるに至った。

今回はその「コンパイル時Cコンパイラ」について書こうと思う。

まずはそもそも「コンパイル時Cコンパイラ」とは一体何なのかということを説明をする。 次にそれをどうやってつくったかについて、そして最後に「もうひとつの」コンパイル時Cコンパイラについて、書こうと思う。

お付き合いいただけたら、幸いである。

(この記事はC++ Advent Calendar 2016の3日目の記事として書かれました。)

そもそも、コンパイル時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"を出力するだけのものである。

これがC++におけるコンパイル時計算*1の例である。

constexpr内でかける処理に関しては制約はあるし、そもそも入力に依存する計算はコンパイル時にはできないので、コンパイル時計算は万能ではないが、実行時のパフォーマンスの向上のための有効な手段の一つである。

コンパイル時Cコンパイラ

さて、「0〜100の和の計算」を例にコンパイル時計算を説明してきたが、和を計算するだけじゃ、コンパイル時計算の力を引き出しきれているとは言い切れない。 もっと複雑な計算だって、コンパイル時にできるはずである。

そう。たとえば、コンパイルだってできるかもしれない。

コンパイラだって、言ってしまえばただのプログラムである。 そのため、コンパイル時計算としてコンパイルができても何も不思議ではない。

というわけで、コンパイル時計算として Cプログラムのコンパイルを行うのが、「コンパイル時Cコンパイラ」である。

github.com

これは、8cc というCコンパイラの、C++の定数式への移植とみることもできる。

「0〜100の和」の例との対比で、挙動を説明をしてみる。 先ほどのコンパイル時に和を求めるプログラムをC++のコンパイラ(たとえばg++)を使ってコンパイルし、実行すると、次のようになる:

  • コンパイル中に「0〜100の和の計算」が行われ、
  • "5050"という値が定数として、実行ファイルに埋め込まれ、
  • 実行時に、定数である5050が出力される

これに対し、コンパイル時コンパイラをg++でコンパイルすると次のようになる:

ちなみに、入力に関してだが、constexpr関数は入力をとれないので、文字列化したCプログラムを、プリプロセッサでソースコードに埋め込むということをやっている。

これが、コンパイル時Cコンパイラである。

ちなみに"Hello World"のコンパイルは、3分くらいかかる。

何の役に立つの？

もし万が一、「コンパイル時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. 入出力
  2. グローバル変数
  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++というカンファレンスが行われていたタイミングだったようだ。

インターネットすごい。本当にびっくりした。

ちなみにこのコメント、はじめ読んだ時、"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コンパイラがこちらである。

github.com

だが、このコンパイラの実行、すなわち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バックエンドの記事が公開された。(前編、後編) Unlamdaは難解言語の一種で、純粋関数型言語である。そのため、実装の方針は僕の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が動かない理由

さて、どうして、そんなにメモリを食うのだろうか。 Unlamdaの方が実装上の制約はきついのに、(1日以上かかるらしいが)動いているのだから、TMPの方も動いてもよいのではないか。

Unlambdaが動いて、TMPが動かない原因は、端的にいうと処理系におけるメモリ解放の有無だと考えられる。

Unlambdaでは、新たな環境が作成されたら、古い環境はもう不要なので、インタプリタ上のGCによってメモリ領域はGCによって、解放される。

一方で、TMPでは不要になった古い環境も保持される。というのも、「環境」といっても実のところ、C++における型情報だからである。 C++コンパイラの気持ちになれば、判明した型情報を最後まで保持しておくのは、当然である。

これはつまり、TMPバックエンドが吐いたプログラムは、今までの環境の履歴を全てメモリ上に保持し続けながら計算が進んでいくということを意味する。 例えば、storeが行われるたびに、メモリの全コピーをすることになるのが、コピー前のメモリの状態も全てメモリ上に残るのである。 こんなの、現実のマシンでまともに動くわけがない。

TMP-8ccを動かすには、要らなくなった型情報をガンガン捨てていくTMP専用C++コンパイラをつくる必要がある気がする。(そんなことができるのかはよくわからず、適当にかいてる)

ちなみにTMPバックエンドで生成したプログラムがまともに動かないことに気づいた頃に、shinhさんがELVM公開直後にしていたこんなツイートを見つけた。

「アイディア自体既出で、しかも できないことも予期されていたか」と悔しくなった。

ただ、個人的にはTMPは今回のためにはじめて触ったこともあり、やってみなければできないこともわからなかったので、やってよかったと思う。 それに、constexprは予測されていなかったっぽい。 constexprという良い着地点が見つかって、コンパイル時Cコンパイラを実現できたので、満足ではある。

Related Work

最後に、本文中でも触れた他プロジェクトについてまとめておく。

Cプログラムから、他言語への変換ができることは言われてみればそれはそうだが、実際に実装し、しかも現実に動くものをつくってしまうのはすごい。 また、バックエンドも書きやすいように設計されており、とてもありがたかった。

今回僕はコンパイラをつくったといっても、実質変換器を書いただけであったが、以前、Cコンパイラを実装したこともある。 8ccを知ったのはその頃だ。とてもわかりやすくかかれているので、「Cコンパイラって案外自分でもかけるかも」という気持ちにさせられた。 また当時、作者のruiさんの8ccを開発したときの日記も読んで、奮い立たされたのを覚えている。 ということもあり、今回、ruiさんにも面白がってもらえたのは、個人的にかなり嬉しかった。

昨日・今日で各アドベントカレンダーの記事として、ELVMの色々なバックエンドに関する記事が公開された。 バックエンド言語ごとの工夫があって、楽しい。

MLから、C++テンプレートへ変換するコンパイラ。TMP-8cc のセクションでも触れたとおり、ELVMのバックエンドとして、C++のテンプレートをやってみようという発想は、これに影響された。

C++14のconstexprで実装された、Brainf*ckコンパイラ。 僕のは世界初のconstexprで書かれたコンパイル時Cコンパイラのはずだが、C++の「コンパイル時コンパイラ」としてなら、こっちが世界初だと思われる。 入力を#include で埋め込むといったアイディアなどはここからいただいた。 また、作者の中３女子さんはconstexprに関してライブラリや多くの資料を公開されており、それらも実装の際に参考にさせていただいた。

以上が、「コンパイル時Cコンパイラ」をつくった話である。 ELVMをいじって、コンパイル時Cコンパイラをつくるのはめちゃくちゃ楽しかった。 ELVM作者のshinhさんと、8cc作者のrui314さんには感謝したい。 みなさんも、ELVMで遊んでみてはいかがでしょうか？

ちなみに、shihさんは、今、TensorFlowバックエンドを実装しているようである。 意味がわからない。面白すぎる。

おわり

(この記事の本文にはコンパイル/コンパイラという単語が、合計86回出現しました。)

*1:関数sum中で変数の書き換えをしているので、正確には「C++14」のコンパイル時計算と書くべきかもしれない。また、コンパイル時計算といった場合には、constexprだけではなく、テンプレートメタプログラミング(TMP)のことも含む。TMPに関しては後のセクションで触れる。

*2:ここでいう「コンパイル結果」は"ELVM IR"という中間言語でかかれたプログラムである。詳しくは次セクションで。

*3:Twitter上でコメントをくださった@hsjoihsさん、ありがとうございます。