Rust1.10でレジスタ割り付け

動機

• レジスタ割り付けの本格的なサンプルが欲しい
• Min-Camlにはレジスタ割り付けがある
• OCamlは文法が結構特殊なので慣れないと辛い
• C++に移植したけど、あまり美しくない
• C++のmoveセマンティックスは実行時エラーが起きて辛い
• Rustならきっと綺麗に書けるはず

---

Rustでのコンパイラ開発の問題

• Rustはまだ開発中では？
• GCがなくて不便では？
• パーサジェネレータはあるのか？
• immutableなグローバル変数は？

---

Rustはまだ開発中では？

• だいぶ安定してきました

GCがなくて不便では？

• GCがないけどインクリメンタルにメモリ管理する分高速なのでトレードオフです
• C++のunique_ptrで書くより楽です
• パターンマッチもあるし便利です

---

パーサジェネレータはあるのか？

• lalrpopというパーサジェネレータがあります
• インストール面倒くさいのでは?
  • cargoを使えば簡単にインストール可能です

---

lalrpop

• Rust製のパーサジェネレータ
• %% など見た目微妙な区切りはgrammer;と書く
• lexerも1ファイル内に一緒に書ける
• Rustの文法に近い文法で記述できる
• とてもいい感じ

---

immutableなグローバル変数は？

• コンパイラはIDを振りたいので、immutableなグローバル変数が欲しい
• 基本的には使わないでください
• じゃあどうしろと？
  • オブジェクト作ってメンバを書き換えてください

---

• なんで、こんなまどろっこしいの？
  • マルチスレッドで安全に高速に動作させるため
  • 横から書き換えられると困る
• Rustで安全に書けるの？
  • かけます
• どうやって？
  • たとえば、Cellを使えばできます

---

実装

---

構文木を書く

• ast.rsに、enumを使って書いた
• 非常に短く書けるし、deriveを使えばcloneも簡単

---

構文木を印字

• ast_print.rsに印字プログラムを作ってみる
• パターンマッチを使って書けばよい

---

アセンブラ出力部分を作成

• オブジェクトにコンテキストとして、fileやmap,vector,カウンタを持たせて書く
• Rustのお行儀さえわかれば書けた

---

自由変数の計算を書く

• レジスタ割り付けや、即値最適化には生きている変数の計算(fv)が必要なので移植した
• ツリーをトラバースする小さい例としてよかった

---

即値最適化を書いてみる

• メモリをコピラない方法も出来る
• だけど、パターンマッチすると所有権が移動してしまうので、何も変えてないのに再構成するのが面倒
• 借用ポインタをトラバースして全部コピーすることにした
• それなりのサイズの変換プログラムが書けた

---

レジスタ割り付け

• 一番長い処理で結構、気力が萎える
• 最初は関数の型だけ合わせる。適当にコメント内で移植を進める
• 例外を使っている箇所が問題
• Either的なResultを使うことにした。Ok,Errを使う
• C++版とOCaml版を参考にして効率的に移植

---

パーサを作る

• とりあえず、lalrpopを見つけた
• lalrpopのチュートリアルをやってみた
• cargo便利じゃん！
• lalrpopを自分なりに書き換えて使ってみた
• 最後に、プロジェクトに組み込み、OCaml版のものを移植した

---

グローバル変数の書き換え

• とりあえず、"tmp"を返すようなスタブを置いておいた
• 次にunsafeを使って動くようにした
• 最後にCellを使って安全にした
• オブジェクト内の生成部分も共通処理を使うようにした

---

完成！

• 目標だった、fibonattiのプログラムがコンパイルできたので完成！

---

TODO

• コマンドライン引数はまだ対応してないので対応する
• テストをきっちり書く
• レジスタ割り付けの説明を書く

---

まとめ

• Rustでコンパイラを開発してみた
• Rustは安定してる
• Rustのパーサジェネレータは実用的だった
• RustはC++より綺麗にGCレスで書けた
• 型合わせは苦労したけど、ほとんど実行時バグに悩まずに済んだ
• Rustいいよ！