# CPU 実験のコンパイラ係のメモ
- 2021年度のCPU実験でコンパイラ係をやったときのメモ
- 成果物提出段階では全班の中で実行命令数最小を達成した
- 実際のメモを清書・追記している
- あくまで「当時の」「自分達の班における」メモであり、**あまり信用しないでほしい**

- クソ雑なコンパイラ構成の図
- 説明の補助として記載するが、参考にはしないでほしい

- 班の ISA の基本方針として、ISA の工夫は最小限とし「RISC-V を単純化したもの + 専用命令」という構成にした
- 結果的に「コンパイラがやる最適化」と「ハードウェアがやる最適化」がほぼ完全に分離され、お互いの仕事に集中することは出来た
- ただし実行時間では ISA の工夫をちゃんとやった班に敗北している
- ちゃんと時間をとって 3rd ISA を考えたら違ったかもしれない (後悔)
- 2nd ISA としては良かったのかも

## コンパイラ開発でやってよかったこと
- シミュレーター係にデバッグ用の機能追加をお願いした
- 具体的には「特定のメモリアドレスにアクセスがあったときにブレークする機能」を実装してもらった
- グローバル変数 (後述) 周りのデバッグで非常に役立った
- ソースファイルとライブラリファイルを分けられるようにした
- 入力として渡された複数のソースファイルをコンパイル時に統合して処理するようにした
- 外部ライブラリの扱いが楽になった
- 「ファイルをパースした構文木」の型と「α変換 と型推論が終わった構文木」の型を分離した
- KNormal 周りのコードが単純化した
- Rust 言語で書き直した
- Rust が云々よりかは、自分が書き慣れていてライブラリが潤沢な言語で開発できると気持ちが楽
- 個人的に、OCaml はライブラリが貧弱だと感じた
- 副作用として、出来上がったコンパイラが高速化して min-caml のコンパイルがすぐ終わるようになったので開発のサイクルが回りやすくなった

## やって効果があった最適化
- **共通部分式削除** (CSE)
- コンパイラ実験の課題にもなっている
- 課題で指示された分だけ実装しても複合式が全然消えてくれないので、もうちょっと高級なものを実装した
- ちょっと高級なものを実装するとそれなりに効果が出た
- **グローバル変数**
- 最初の関数定義が現れるまでに定義された変数を全てグローバル変数とみなす
- レイトレだとクロージャの生成/呼出が消えて爆アド
- アドレス決定の方法周りでアセンブラ (リンカ？) と仕様の調整が必要
- **不要アセンブリ削除**
- 実行命令数は減らないがバイナリ長は案外減る
- バイナリ長が減るとレイトレのプログラムが BRAM に載って速くできるかも
- **インライン展開まわり**
- インライン展開はすればするほど速くなる
- レジスタの退避が不要になる
- 変数の間の関係が明らかになり、最適化がかかりやすくなる
- ただし展開しすぎるとバイナリ長が爆発する
- min-caml ではデフォルトで再帰関数もインライン展開してしまうようになっているが、これは阻止するべき
- 呼び出し箇所が一箇所しかない関数はサイズに依らずインライン展開したほうが良い

- **ループ検知**
- 末尾再帰関数をループに変換する
- レイトレでは再帰関数がほぼ残らなくなり、インライン展開が促進される

- **データフロー解析** (DFA)
- 配列内の要素がどこで読取・変更されるかを検知する
- これにより安全な配列読み取り除去が一部実装可能になる
- クロージャ呼び出しがあると DFA はほぼ無理。絶対に殺すべし
- **制御フローグラフ (CFG) への変換**
- 関数型言語としての最適化を終えたあと、中間言語に変換するときにプログラムを CFG の形式に変換
- 無駄なジャンプ命令の除去が非常に行いやすくなった
- 実はレイトレの実行命令数のうち結構な割合をジャンプ命令が占めている
- ジャンプ除去によるブロックの統合で、最適化が連鎖的に進む
- レジスタ割当は書き直すハメになる。Tiger Book に実装が載っているのでコピペする
- なんか本のコードに微妙にバグがあってデバッグが辛い
- 最適化がちゃんと出来てると、雑にやっても意外と spill しない
- **インラインアセンブリ**
- sin/cos や標準入出力などの外部ライブラリ関数を、インラインアセンブリを使って min-caml コードとして記述
- 外部関数呼び出しとして処理されていたものがインライン展開されるようになるのでそこそこ高速になる
- **if 式の最適化**
- min-caml のデフォルトでは if 式が非常に最適化しにくい形でパースされる
- これを変更して静的分岐予測ができるように
- if が一つ消えるだけでそこそこ最適化される
- **定数除算の置き換え**
- `print_int` の実装では「10 で割る」処理が欲しくなる
- 除算命令はコストが高いので入れたくないが「10 で割る」処理だけなら他の命令で代用可能である
- https://godbolt.org/z/z3z57MYGj
- これは高速化というよりかは Tips

## やってもあまり効果がなかった最適化
- **Lambda Lifting**
- コンパイラ実験の課題
- レイトレにはネストした定義がないので無意味
- 雑に実装すると x86 でのレジスタが不足するので意外と面倒
- **Do-All 型ループ検知**
- 案外活用がめんどい。安全にやるには DFA が必須
- ちゃんと使えば強いかも
- **配列の不要な初期化の除去**
- 案外めんどい割に効果が少ない
- **タプル平坦化**
- **配列に代入されない**タプルの平坦化は実装が楽だが、効果は限定的
- ただし配列に代入されうるタプルの平坦化は、**きちんと実装できれば**効果は高いと思われる。ただしきちんと実装するには高度な DFA が必須で死ぬほどムズそうだった
- コンパイラ実験の課題では事もなげに書いてあるが、あれは何かのミスではないか
- Rust みたいな所有権検査を最初に行うことで安全性の保証ができるかもしれない (未実装)
- 二次元配列の平坦化の安全な実装もおそらく地獄 (断念)
- レイトレ**では**正しく動く実装は比較的容易