学部３年の課題でOCaml言語で書かれたプログラムをRISC-Vアセンブリに変換するコンパイラを作成しました。
ゴールは、授業で配布されたレイトレーシングのプログラムをできるだけ早く動かすことです。
コア、コンパイラ、メモリ/FPU、シミュレーターの4つの役割に分かれてグループで一つのCPUを作ります。
コンパイラ係としての目標は、OCaml言語で書かれたプログラムの最適化をできるだけ行って生成されるアセンブリの命令数を減らすことです。
今回のコンパイラは、90億だった命令数を最終的には17億まで減らしました。
実際には、min-camlをもとに以下の内容を追加で実装しています。
- コアで独自に定義されている命令に対応
- RISC-Vへの対応（既存のものは、SPARCやx86）
- 最適化
- 共通部分式削除
- グラフ彩色
全体の構成
動作例
変換前(OCaml)
変換後(RISC-V)
実装
コアで独自に定義されている命令に対応
ocamllexとocamlyaccという機能を使います。
まず、読み込みたい言葉（token）をlexer.mllに定義。
ここでは「fhalf」や「fsqr」を独自命令として追加する例を見ていきます。
次に、parser.mlyでどのような構文になるかを定義（後ろに何が来るかなど）
同時に、syntax.mlで型を定義。
ここで定義した型に基づいて処理をしていきます。
最終的には、アセンブリとして出力
RISC-Vへの対応
最終的にファイルに書き込む文字列を変更。
x86の場合（現在はx86に対応していないので赤線が出ている）
RISC-Vの場合
最適化
共通部分式削除
変数yが「y = e1」として定義された後に、別の変数xが「x = e1」として定義されていた場合、変数xを変数yで置き換える。
式eに出現する変数xを変数yで置き換える関数。
グラフ彩色
レジスタ割当を最適化するためにグラフ彩色によるレジスタ割当を行った。
同時に存在してほしい変数には別のレジスタを割り当てることで、レジスタを効率的に使うことができます。
もし、賢くないレジスタ割り当てをした場合、スピルが多く発生し、メモリにロードしたりストアしたりする時間が余分にかかっていまいます。
「Modern Compiler Implementation in ML」という本に書かれているアルゴリズムに従って以下のように実装しました。
- データフロー解析から、各命令ノードごとに、live-inとlive-out（命令に⼊るときに⽣きている変数と命令から出るときに⽣きている変数）を解析。
- それをもとに変数同⼠の⼲渉グラフを作成。
- ⼲渉グラフを、simplify→coalesce→freeze→selectのアルゴリズムで彩⾊。
最終発表で使ったスライドを紹介します。
