自作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にした。 命令セットも独自のものを採用している。

つくったコンパイラについて

作成したコンパイラはこれ。

github.com

UCCという名前で開発した。OCamlで実装されており、ANSI-Cの大部分をサポートしている。
ANSI-Cの主要な機能で非サポートなのは、ビットフィールドと構造体を返す関数くらい。 どちらもOSのソースコード内でつかわれなかったので、実装コスト的にサポートするのをやめた。

ANSI-C外の機能としては、独自のインラインアセンブラをつかえるようにした。

libcについては、必要に応じて自分たちで実装していって、サブセットがつかえる。

開発は、自分の班でのタスクが区切りがついた11月中頃から僕が開始し、その後wasabizとb-inaryが加わって3人で開発した。 （wasabizはCPUの実装、b-inaryはシミュレータ・アセンブラの実装も兼任）

UCCではコンパイルを

1. clangによる、プリプロセス・文法チェック
2. 構文解析
3. 型つけ、定数畳み込み
4. アセンブリ生成

という順でおこなっている。

プリプロセッサはclangのものをコンパイラを利用した。
また、UCC本体にCのコードを渡す前に、clangのfsyntax-onlyオプションでの文法チェックをかませるようにしている。

UCC本体では、 ocamlyaccで生成したパーサで抽象構文木を作成し、 その後、木を２回トラバースして、自作アーキテクチャ向けアセンブリを生成する。

割とシンプルでわかりやすい構成に実装できたとおもう。

実装の際には最適化より、バグなく正しく動くものをできるだけ早くつくることを意識した。
たとえば、簡単のため、変数はすべてメモリ上に割りつけることにしている。

また、テストを重視した。
proveコマンドを利用して簡単に一括テストできるようにし、機能を追加するごとにテストコードも追加していった。これにより、変更によって、以前つくった機能を壊してしまうようなことを防げた。

xv6の移植作業を開始してから、特に大きなバグが見つかることもなく、安定して動作したので良かったと思う。

動いたものとか

最終的な目標はxv6の自作CPU上での動作であったが、それまでの間、コンパイラのバグ発見も兼ねて、いくつか、ある程度の大きさのプログラムをコンパイルをしてみたりした。 そのことについて書く。

benz

wasabiz/benz-gaia · GitHub

これはwasabizのつくっているscheme処理系である picrinの移植向けサブセット。

この頃はUCCが、まだ浮動小数点数の実装途中だったり、charを簡単のために32bitで扱っていたため(Cの規格的には一応これでもOKだけど、その後8bitに修正した)、benz側でも色々な対応をしてもらった。 wasabizの記事が詳しい。

wasabiz.hatenablog.com

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に移植して、それを動かした。 これには浮動小数点数まわりの実装のバグチェックという役目もあった。

kw-udon/min-rt-c · GitHub

変数をレジスタに割り当てていない分、MinCamlを改造したコンパイラにくらべて、実行命令数は多くなったが、これも実機で完動した。

min-rt.cは割と丁寧に移植したつもりだし、もし来年度以降とか、CPU実験でCコンパイラつくることがあったら、テストプログラムとして使えるとおもう。

（追記：コメントとtwitterで教わったところ、min-rtのC実装はこことかここに既に存在していた。 かかれたコメントをみると、オリジナルがかかれたのが30年以上前で、それからぐるぐる色んな言語で書き直されてきたらしい。歴史を感じる。）

xv6

リポジトリはこちら。

wasabiz/xv6 · GitHub

こいつが本命だった。

このためには、コンパイラの他に

• コアの対応(割り込みやMMUの実装、高速化)
• シミュレータ・アセンブラの強化
• xv6のソースコード理解とx86依存部分書き換え

という仕事が必要であった。

これらについては、コンパイラの開発と並行して、他の班員たちが分担しておこなっていた。 完動までに具体的にどんなことを行ったかについては詳しいことは僕も把握できていない部分があるので、他の班員が記事かいてくれることに期待。

3月1日にシミュレータ上で動作し、9日に実機で動作した。 OS係もコア係も線表みたいなのをつくって、予定通りにそれを消化していって最終的に完動にもっていっていて、とても強かった。

追記 : OS移植班(X班)の他の班員の記事

• コア係 (UCC係も兼任)

wasabiz.hatenablog.com

• OSä¿‚

nullpo-head.hateblo.jp

---

一応どんなことができるようになったかを書いておく。
（僕はリーダーとかでもなく、一人の班員としてコンパイラをつくっただけなので、僕が成果として書くのは気が引けるけど、誰もかかないのはよくないので）

とりあえず、デモとしては、この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には大変お世話になった。（特に付録の章）

あと全然関係ないが、これがこのブログの最初の記事である。 正直、記事かくのがこれっきりになってしまいそうな予感がしている。 それはよくないので、今後もなんか書ければいいなぁ。

おわり