おわり(この記事の本文にはコンパイル/コンパイラという単語が、合計164回出現しました。)*1:関数sum中で変数の書き換えをしているので、正確には「C++14」のコンパイル時計算と書くべきかもしれない。コンパイル時計算といった場合には、constexprだけではなく、テンプレートメタプログラミング(TMP)のことも含む。TMPに関しては後のセクションで触れる。IR"という中間言語でかかれたプログラムである。詳しくは次セクションで。*3:Twitter上でコメントをくださった@hsjoihsさん、ありがとうございます。(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言語コンパイラがつくろうということになった。いうことで1から自作することにした。対象とした自作CPUは、今年最も早く完動した3班の2ndアーキテクチャであるGAIAにした。命令セットも独自のものを採用している。つくったコンパイラについて作成したコンパイラはこれ。github.comUCCという名前で開発した。OCamlで実装されており、ANSI-Cの大部分をサポートしている。ANSI-Cの主要な機能で非サポートなのは、ビットフィールドと構造体を返す関数くらい。どちらもOSのソースコード内でつかわれなかったので、実装コスト的にサポートするのをやめた。ANSI-C外の機能としては、独自のインラインアセンブラをつかえるようにした。libcについては、必要に応じて自分たちで実装していって、サブセットがつかえる。開発は、自分の班でのタスクが区切りがついた11月中頃から僕が開始し、その後wasabizとb-inaryが加わって3人で開発した。型つけ、定数畳み込みアセンブリ生成という順でおこなっている。プリプロセッサはclangのものをコンパイラを利用した。UCC本体にCのコードを渡す前に、clangのfsyntax-onlyオプションでの文法チェックをかませるようにしている。その後、木を2回トラバースして、自作アーキテクチャ向けアセンブリを生成する。シンプルでわかりやすい構成に実装できたとおもう。実装の際には最適化より、バグなく正しく動くものをできるだけ早くつくることを意識した。簡単のため、変数はすべてメモリ上に割りつけることにしている。proveコマンドを利用して簡単に一括テストできるようにし、機能を追加するごとにテストコードも追加していった。これにより、変更によって、以前つくった機能を壊してしまうようなことを防げた。xv6の移植作業を開始してから、特に大きなバグが見つかることもなく、安定して動作したので良かったと思う。動いたものとか最終的な目標はxv6の自作CPU上での動作であったが、それまでの間、コンパイラのバグ発見も兼ねて、いくつか、ある程度の大きさのプログラムをコンパイルをしてみたりした。そのことについて書く。picrinの移植向けサブセット。この頃はUCCが、まだ浮動小数点数の実装途中だったり、charを簡単のために32bitで扱っていたため(Cの規格的には一応これでもOKだけど、その後8bitに修正した)、benz側でも色々な対応をしてもらった。wasabizの記事が詳しい。wasabiz.hatenablog.combenzはlibc非依存なので、UCC側では最低限必要なアーキテクチャ依存部分である、setjmpとmallocを実装した。mallocはK&Rに載っている実装をもってきたのだが、今までmallocの実装なんて考えたことがなかったので、勉強になった。結果、schemeインタープリタが自作CPU上で動いた。それまでは、テスト用で書いたプログラムしか動いていなかったので、とても嬉しかった。min-rt.cCPU実験といえば、レイトレーシングというわけで、レイトレーシングプログラムであるmin-rtを実行したかったのだが、これはMinCamlで実装されている。いうわけで、min-rt.mlを自分でCに移植して、それを動かした。これには浮動小数点数まわりの実装のバグチェックという役目もあった。GitHub変数をレジスタに割り当てていない分、MinCamlを改造したコンパイラにくらべて、実行命令数は多くなったが、これも実機で完動した。min-rt.cは割と丁寧に移植したつもりだし、もし来年度以降とか、CPU実験でCコンパイラつくることがあったら、テストプログラムとして使えるとおもう。(追記:コメントとtwitterで教わったところ、min-rtのC実装はこことかここに既に存在していた。かかれたコメントをみると、オリジナルがかかれたのが30年以上前で、それからぐるぐる色んな言語で書き直されてきたらしい。)xv6リポジトリはこちら。GitHubこいつが本命だった。このためには、コンパイラの他にコアの対応(割り込みやMMUの実装、高速化)シミュレータ・アセンブラの強化xv6のソースコード理解とx86依存部分書き換えという仕事が必要であった。これらについては、コンパイラの開発と並行して、他の班員たちが分担しておこなっていた。完動までに具体的にどんなことを行ったかについては詳しいことは僕も把握できていない部分があるので、他の班員が記事かいてくれることに期待。3月1日にシミュレータ上で動作し、9日に実機で動作した。OS係もコア係も線表みたいなのをつくって、予定通りにそれを消化していって最終的に完動にもっていっていて、とても強かった。nullpo-head.hateblo.jp一応どんなことができるようになったかを書いておく。シミュレータ上でOSが起動して、シェルのプロンプトがでてくるはず。lsとやれば、実行可能なユーザープログラムがみれる。UCC自体のコンパイルのために、OCamlとかが必要。UbuntuとMacで動作確認済。シェルの設定によってはうまくいかないことがあるかも。id:nullpo_headがEmscriptenを使って、ブラウザ上でデモを動かせるようにしたので、手軽に試せるようになった。(強い)https://nullpo-head.github.io/emcc-gaia-simu/xv6.html追記ここまでユーザープログラムとしては、xv6に元からはいっているlsとかcatとかgrepの他に、slとか2048などをユーザープログラムをつくってくれたので、それらで遊べる。2048は色もついていて普通に楽しい。あと、viライクなスクリーンエディタもある。簡単なアセンブラも用意したので、OS上でアセンブリプログラミングもできるようになった。libcはxv6自前のものは貧弱だったので、自分たちで実装したものをつかった。そのため、FILE構造体とかつかえている。ちなみにfopenはK&Rに載っている実装をもってきたのだが、今までfopenの実装なんて考えたことがなかったので、勉強になった。(2回め)そして、CPU実験といえばレイトレというわけで、OS側からmin-rtを呼び出せるようにもした。min-rt.cはユーザープログラムとしては大きすぎたので、デバイスとしてカーネルに組み込んだ。その結果、OS上でレイトレーシングができるようになった。OS上で動作しているので、タイマー割り込みとかの処理も含まれるので、実行時間は生のCPU上で動かすのよりも自明に時間がかかるのだが、実機ではプログラムロードの時間を含めても2分以内に動作した。コアがとても優秀だった。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には大変お世話になった。(特に付録の章)あと全然関係ないが、これがこのブログの最初の記事である。記事かくのがこれっきりになってしまいそうな予感がしている。それはよくないので、今後もなんか書ければいいなぁ。ブログを報告する引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。