これは何

自作コンパイラ基盤(以下面倒なのでcilk) の内部構造の解説を，気が向いた時に書いていく．

ざっくり

1. まず，IRがある
   1. IRに対して色々最適化したりもする．mem2regとかね．今は省略

2. DAG(Directed Acyclic Graph)形式に変換する

   • なぜDAGにするの? → 木構造のほうが命令パターンマッチしやすい
   1. Combine: 命令同士を合併したりする．LLVMなら，cmpとbrをbrcondにしたり．
   2. Legalize: アーキテクチャが対応していない(命令|型)を，対応している(命令|型)に変換したりする．例えば，cilkでは，ここでアドレス同士の足し算をLEA(x86ならね)に変換したりする．
   3. Instruction Selection: 名前の示す通り，適切なマシン命令を選択する．cilkでは，Rustのマクロで簡潔に命令パターンマッチを記述できるよう目指している．

3. マシンアセンブリ向け形式(以下MachineInst)に変換する

   • ここからはアーキテクチャごとにやることが大きく違うと思う
   • ここでは，cilkがある程度まともに対応しているx86を例にとる
   1. Phi Elimination: cilkのIRはSSAだからphiが存在する．ここではphiを取り除く
   2. Two Address Conversion: a = ADD b, cのような命令を，a = COPY b と a = ADD a, c に変換する．
   3. Register Allocation: 無限個の仮想レジスタに有限個の物理レジスタを割り当てる．cilkでは，普通レジスタ割当にはグラフ彩色を利用するところだけれど，Linear Scanのような何かを利用している．何かというのは，色々いじっている間にLinear ScanなのにSpill Weightのことを考えていたりして，正直よくわからなくなっているから．
   4. Prologue&Epilogue Insertion: 関数のプロローグ・エピローグを挿入する．push rbpとか．
   5. あとは細々したことをやったりする．浮動小数点数の即値をメモリ上に配置したり．

4. MachineInstを実際のアセンブリに変換する

完成