`ir_asm_virtual` : 仮想アセンブリ

mincaml-rsが導入する仮想アセンブリは，次の特徴を持つ中間表現です．rustcのmirに近い構造です．基本ブロックの表現はMLIRに似ています．

アーキテクチャ非依存
静的単一代入
制御フローグラフ
- 制御フローグラフへの変換
if式と引数を持つ基本ブロック
- phi node
- MLIRのブロック引数

名前は，文字列ソートしたときにアセンブリの近くに来てほしかったため後置修飾になっています．それ以外の理由はありません．

現在，この形式への変換のデバッグが不十分であり，構造の一部が変更される可能性があります．

アーキテクチャ非依存

この中間表現はアーキテクチャの情報を持ちません．ターゲットのマシンのレジスタの種類・個数，ターゲットの表現によって定まるポインタサイズ，それによって導かれる型のサイズの計算などは行いません．

もっとも，アーキテクチャのことを全く知らずにコンパイラを設計することはできず，アーキテクチャ非依存と言っておきながら，ターゲットがレジスタマシンであることやメモリの扱いができるなどといったことはある程度期待しています．

静的単一代入

どの変数もその変数への代入は高々1回であるような形式です．変数がイミュータブルなことと，名前解決（オリジナルではα変換）の手続きによりK正規形の時点では静的単一代入形式になっていますが，注意を払わなければこれは容易に崩れ去ります．

なお，対象言語は可変状態の機能を持ちますが，それは変数への代入とは異なります．第4回課題など，配列への代入を変数への代入として扱う場合はこの点に注意する必要があります．

制御フローグラフ

制御フローグラフ（Control flow graph, CFG）とは，制御構造に関心のあるグラフです．詳細は教科書やWikipediaを参照してください．コンパイラ実験の後半の講義でも（当然）登場します．

ここで扱う基本ブロックの命令は，関数呼び出しを含みません．関数呼び出しはブロックの末尾のterminatorにのみ現れることができます．

オリジナル版とは異なりこの形式を採用した理由として次のようなものがあります．

コンパイラ実験の第8,9,10回とのインテグレーション
LLVM, MLIR等でごく一般的に用いられる形式であること

制御フローグラフへの変換

クロージャ変換後の式から制御フローグラフへの変換は複雑です．

制御フローグラフの表現で，基本ブロックはインデックスにより管理するようにしています．terminatorは基本ブロックを参照するため，基本ブロック間の依存関係に対応してterminatorの構築順を変える必要があります．

オリジナル版も最終的にはアセンブリを出力するためこの問題に遭遇していますが，ラベルを解決する作業をアセンブラに任せることで回避しています．

mincaml-rsでもラベルのような機構により対応関係を考慮し，terminatorの構築をラベルへの参照をさせることにして遅延させています．

これらの実装の詳細はir_asm_virtual/src/lowering/expr.rsを参照してください．執筆時点で致命的なバグが含まれていることもあり，一部のコードが大規模に変更される可能性があります．

このように，実装面で多少の困難がありますが，この変換で最も重要なのはif式の変換の部分です．

`if`式と引数を持つ基本ブロック

知っている方向けの説明：if式の変換でphi nodeをMLIRライクな表現により用いています．

コンパイラの対象言語にはif式があります．結果を返さないif式は簡単で，then式とelse式に分岐して，それぞれで合流するだけです．

では，式としての値が変数に束縛されるif式はどうでしょうか？then式とelse式それぞれで異なる式としての評価結果の値が，今後その変数を介してアクセスされます．素朴な方法としては，この変換全体が式を代入に結びつけることをしていたのを思い出して，2つの式それぞれについて各々の末尾に代入文を作ればよいと考えるかもしれません．アセンブリに変換することを考えてもこの方法は自然です．しかし，この方法では直ちに静的単一代入形式を喪ってしまいます．

phi node

phi nodeは，静的単一代入形式を維持（または獲得）するための重要な機構です．ここでは，LLVMのphi命令とそれに類する機構をphi nodeと呼んでいます．

LLVMのphi命令とは，その基本ブロックに到達する直前の基本ブロックに基づいて値を決定する命令です．例えば，if式を次のように表現できます．

br i1 %cond, label %then, label %else

then:
  %x1 = 10
  br label %merge

else:
  %x2 = 20
  br label %merge

merge:
  %x = phi i32 [ %x1, %then ], [ %x2, %else ]

代入は一度しかできないが右辺の式は中間表現を設計する側が自由に定義できることを考えると，自然なアイデアです．

このコンパイラではif式の表現にのみこの表現力を利用していますが，ループやfor文などの言語機能による分岐の表現でも利用できます．

MLIRのブロック引数

phi nodeは仮想的な命令であり，実際にアセンブリに変換する際にはそれぞれの分岐命令に遡ってその前に設置されることになります．また，phi nodeは実装上ブロックの先頭にないと面倒です．

これらのことから，分岐命令が代入先の情報を持っていると便利ですし，phi nodeを命令から追い出して，さらに基本ブロックにphiにより定義される変数の情報を持たせると便利そうです．

MLIRの基本ブロックは引数を取ります．分岐命令が代入先の変数の情報を持ち，引数は命令とは異なる形式で扱えます．重要な注意として，ブロックの引数がその変数への唯一の代入であることを忘れないでください．生存解析やデータフロー解析で必ず意識することになります．

この代入の意味論は逐次ではなく並行代入であることにも注意してください．たとえば，この代入により多変数のswapが可能です．これはアセンブリに変換するときに問題になる可能性があります．

mincaml-rsではこの形式へ変換することを念頭に置いています．

mincaml-rs Documentation