ELVM Compiler Infrastructure について

はじめに

言語実装 Advent Calendar 2016 用です。

ELVMは、コンパイラをフロントエンドと中間言語とバックエンドにわけて、多言語多CPUに対応しよう……というようなLLVMの考え方を、パロディと言っていいレベルにまで単純化したものです。結果として実用性は全くないが、C言語から他言語へのトランスレータを極めて簡単に書け、 Brainfuck などのような難しい言語のコードもC言語を書くだけで生成できる、というようなことを主目的としています。

本当は ELVM のバックエンドを一つ足して、 Brainfuck とかのような難しいターゲットでなければ、こういう感じで手軽に足せますよーということを書こうかと思っていました。しかし、ありがたいことにそういう趣旨だったり、あるいはもっと難しいターゲットについても、既にあれこれと書いていただいたのでした。例えば

など。上のリストは、おおざっぱに、上の方に簡単な雰囲気をつかむのに向いてそうな記事、下の方に謎テクニックを楽しむのに向いてそうな記事を並べてみました。いずれにせよ、こういう記事は中身をよく把握してる私自身より、試行錯誤していただいた他の人達が書いた方がわかりやすいでしょう……ということでなんか違うことを書いてみます。

具体的にはどういうふうに作業を進めたりした…てことを雑に書いていこうかと。技術的な概要は一つ前のこのポストとそこからリンクされてるスライドに書いたので、そっちを参照してください。

http://shinh.hatenablog.com/entry/2016/10/18/095437

sedlisp, beflisp, makelisp, bflisp

色々あって、Esolangですごく簡単なLisp処理系を書く、というのがマイブームになったことがありました。 GNU sed と GNU make は完全手書きでした。sedlisp を書いた時から、 @rui314 さんは「手書きじゃなくて中間層を介して変換した方が良いのではないか」と言っていたのですが、 sed や make だと、計算モデルが違いすぎるので直接書く方がラクかなということと、結果できたものが遅くなりすぎそうだったので、直接書きました。

ですが、 Befunge の時はなにか中間に入れないとキツいと感じたので、 LLVM bitcode から雑に変換する、という方法でやりました。といっても、 LLVM bitcode は任意のものを許すわけではなく、変換器がサポートしてる命令しか吐かないように注意深く書かれた lisp.c を LLVM bitcode にして、そこから Befunge に変換する、というようなやり方でした。

で、 Brainfuck もやってみるかなぁと思った時に、これは自明に Befunge 以上に大変なわけで、まあなんかから変換するしか無いわけです。でも LLVM bitcode て以外に命令セットでかいということは Befunge の時に感じてたので、あまりつきあいたくなかった。じゃあなんかオレオレ中間コードを作るのが良いかな、と考えました。

bfs

で、 bfs という中間形式をデッチ上げました。これは今の ELVM の EIR と同じなんですけど、最初は Brainfuck だけが想定ターゲットだったので、 Brainfuck Assembly 的な理由でこういう名前になっていました。ややこしいんで今後 EIR で統一します。中間形式をでっち上げるのは、まあ適当に決めるだけなので簡単です。

で形式が決まるとCコンパイラをいじることになります。 main しか無いような簡単なコードを書いてみて、x86-64のコードを出力してる部分を順に EIR を吐くように変換して、うまくいったらreturn 42;とか1+2;とか、命令を足しては出てきたx86-64のコードを等価な EIR のコードに変換していく感じでした。

すごく短いプログラムをコンパイルできるようになったら、 EIR のシミュレータを書いたかと思います。命令数が少ないので、 Brainfuck のインタプリタを書く程度プラスアルファくらいの手間でできます。途中、ああ命令だけじゃなくてデータも書けないといけないな、ということで.dataセクションを足したりもしました。

この段階で重要だったのは、C言語で書いたコードをx86-64に変換して実行した結果と、EIRにコンパイルしてシミュレータで動かした結果が同じ、ということをきちんとテストすることでした。なにかまだサポートできてないCの機能を見つけるたびに、C言語でテストを書いて、makeと叩けばx86-64で実行した結果とシミュレータの結果が同じであることをチェックできるようにしてたと思います。

bflisp

C言語→EIRが一通りうまくいってるぽくなってくると、次は EIR を Brainfuck に変換する部分です。これはまあ……大変です。定数ロードとかをかけ算でやるとかは大変だし遅いBF処理系では全く通用しないので、8bitセルのBFで複数セルを使って1byte (当時は1byte==16bit) の情報を扱います。つまり単なる加減命令とかでも、繰上がり下がりの計算がはさまることになって……めんどくさいです。がまあ加減くらいは序の口で。

一番キツかったのは比較命令だったかと思います。上位セルが大きかったら下位は無視してーとか、0と比較する時だけおかしいとか、下位が0の時だけおかしいとか、そういう謎の現象が起きまくりました。load/storeも結構大変だったのですが、比較の後だったから慣れていたというのと、あまりコーナーケースが多くなかったこともあって、どっちかというとどういうレイアウトにするか、っていうデザインが大変だったような気がします。

こういうわけわからない有象無象をデバッグするために、EIRのシミュレータと、EIRからBrainfuckを出力した時のコードに、トレース出力をつけました。具体的には1命令ごとにレジスタの状態を出力する感じです。これでできた巨大なトレース出力を diff していると、喰い違いが出てくる部分がでてきて、そこを見ればバグの原因がわかるので、小さいテストを書いて修正する……というのを繰り返しました。これはオモチャ CPU 作った時にも使ったアプローチで、CPUの時はエミュレータに実行トレースをつけたものと、iverilogでトレースを出してたものを比較してました。でまぁ、なんかうまくいきました。

あとは、C言語→EIRの時に使ったテストケースを、順にEIR→Brainfuckの変換でも正しく動くかをテストしていった感じでした。そんなこんなで lisp.c が Brainfuck の上で動きました。

8cc.bf

さて、lispが動くならCコンパイラ自体もBrainfuckで動かしたいな、ということで色々試しはじめます。まずわかったのは16bitのメモリ空間では、命令もデータも足りない、ということでした。命令の方は、「実際のCPUじゃないんだから、1命令ごとにPCひとつ使う必要ないよね」ってことで、 basic block ごとに PC が変わることになりました。 VLIW と考えても良いかもしれないです。いや良くないでしょうけど。

データの方はちょこざいなこともできなくて足りないので、素直に24bitに拡張しました。命令も拡張しても良かったんでしょうけど、前述の basic block ごとに命令をまとめる作戦は、単純に実行速度の向上にも貢献するのでいずれにせよやって良かったと思います。

あとは少しバグをつぶしたらEIR→Brainfuck側はだいたいできました。足りない libc 関数の用意と、 8cc 側の EIR としてサポートできない記述の修正です。 libc は ARC やオモチャ CPU のために書いたコードや、 Bionic から必要なものをひっこ抜いてきたり自分で書いたりして準備しました。 8cc 側の困った記述というのは、 signed が無いので value >= 0 とかが常に true とか、あとはビットシフトと浮動小数の撤去でした。

そんな感じで 8cc が Brainfuck 上で動きました。5時間ほどかかってセルフホストができて、おおーと思いました。

ELVM

このへんでだいたい満足してたのですが、2点ほど思っていることがありました。

id:irori さんが Unlambda への変換を実現させて、 8cc.unl を作ってくれたのですが、こういう感じでもっとターゲットを増やすと面白いのではないか
EIR→Brainfuckの変換はRubyで行なっていたので、完全なセルフホストではなかった。これでは人類からBrainfuck インタプリタ以外が失われた時に対応できない

でまあ、一番大変な 8cc.bf というのはすでに動いてたので、だるいなーと思ってたのです。がまあある日、2つとも一気に解決しよう、で ELVM とかいう景気のいい名前をつけよう、とか思い立ちました。名前とか決まるとやる気出ますね。

でまあ、まずはEIR→ターゲットの部分をCにしつつ、ちゃんとフレームワークぽい感じにしました。実装量はあったけどまあやるだけ。

他の部分は適当ですが、ターゲットを増やすのは割とやりやすくなってるのではないかと思います。なんか適当に周りの言語のコピペしてると、だいたいおかしいところが少しずつ見えてきて、インクリメンタルに作業できるんじゃないかと。特に Makefile がよく書けてると自負してまして、バックエンド書く人は少し Makefile に追記したら make hoge だけで hoge バックエンドに対するテストがたくさん走る感じになってます。

バックエンドを増殖させる

基本部分ができるとバックエンドを増殖させていきました。色々足していると、基盤部分にあった方がいい共通部品なんかが見えていったりしました。

Esoteric 方面の言語だと、 Befunge 、 sed 、 Piet 、 C-INTERCAL あたりはなかなか大変なバックエンドでした。特に経験が無かった C-INTERCAL と、あと Piet はなんか色々大変でした。

Piet はこう、 Befunge みたいな感じでできるかな…と思ってたのですが、コード変換と2次元レイアウトを同時にやるのが大変で、一旦 PietInst とかいう構造体の列にして、それからレイアウトを決めて色を配置する、みたいなことをやりました。つまりもう1つ中間言語を介してるわけです。

INTERCAL はこう、方言多すぎ、仕様多すぎですね。色々やってたのですが、結局 C-INTERCAL がまともに動きそう、ということでこれになりました。 add とか sub とか無いんで、このへんはパズルチックにプリミティブを作ってく感じでした。

反応など

当初は「ヘンなことやってるなあ」くらいに思われる程度だと思っていたのですが、予想以上に反応をいただいて、PRでバックエンドを足していただいたりして嬉しい誤算でした。現状28バックエンド中13バックエンドはPRでいただいた、というのはなかなかなもんだなと。最初の方に Unlambda, Vim, TeX バックエンドを書いてくだださった iroriさん rhysd さん hak7a3 さんには特に感謝する感じです。紹介記事書いていただいたのも後に続く人を増やしていただけたんでないかなと。

その後の展開としては、 C++ constexpr バックエンドのバズりっぷりがなかなか愉快でした。 @llvmweekly や Bjarne Stroustrup がコメントしたりと。あと、チューリングマシンバックエンドを書いていただいた、ND-CSE-30151というアカウントは、どうもこれノッテルダム大学の講義用のアカウントらしく、この講義のテーマにチューリング完全などがあるため、少なくとも授業で紹介くらいはしてくれるのでないかと思います。ジョークプロジェクトが大学の授業で紹介されるというのは、なかなか胸熱です。

あと、 id:irori さんの EsoLang vi のような方向性も面白いですね。改造 8cc が処理できる C 言語で書かれたソフトであれば、 Unlambda やら Brainfuck に変換できちゃうわけです。

まとめ

スライドにも書いたのですが、理論上できるに決まってることでも、実際動かしてみるのは大変だったりして、でも動いたりすると嬉しいもんだなと。どうも私は発見とかがしたいんじゃなくて、そんなのやってどうすんのってこととか、理屈はわかるけどそれ本当に現実的な話としてできるの、てことをやるのが好みなのかなぁと、最近思います。セクシーボイスアンドロボというマンガの主人公が、「私がしたいのは世界にちょっとしたドリームを与えるような、そういうこと」とか言ってたんですが、なんかたぶん、そういうことが目指すところな気がします

言語処理系、文法とかそういう表の部分に注目しがちですけど、バックエンドやそれ以降も面白いですよ、と。たとえば世の中の言語作者はもっとデバッガとかに興味持ってあげて欲しいと思ったりします。

あとはこう、なんか世の中にあるもののパロディーというか似たようなものを適当にでっちあげるというのは、なんかとりあえずやる、ってテーマとしては良いなと思ったりしました。なんか趣味コード書くかっていって、まぁいきなりデカいオープンソースに飛び込むとかすごい有用なもの作る、っていって手が動く人はいいんですけど…

PRは随時募集という感じなので、冬休みの暇潰しなどに、ぜひバックエンドを足してみてください