Chapter 19: Instruction Selection and Portable Compilation

Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

1 files changed, 149 insertions, 0 deletions

diff --git a/docs/chapter19/README.ja.md b/docs/chapter19/README.ja.md
new file mode 100644
index 00000000..c52ff522
--- /dev/null
+++ b/docs/chapter19/README.ja.md
@@ -0,0 +1,149 @@
+# 第19章: 命令選択と移植可能なコンパイル
+
+[English](README.md) | 日本語
+
+この文書は [原文](README.md) の日本語訳です。
+
+[前の章: 第18章](../chapter18/README.ja.md) |
+[次の章: 第20章](../chapter20/README.ja.md)
+
+[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチ上の直線的な Git リビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter19) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter18...linear-chapter19) することもできます。
+
+文法は[第18章](../chapter18/18-grammar.ja.md)から変わりません。
+
+## 命令選択、レジスタ割り当て、命令エンコーディングにまつわる全体的な問題と開発上の問題
+
+命令選択の出力、すなわち理想化された Simple ノードからマシン固有のノードへの対応付けは、実行方法がないと大量にテストするのが困難です。命令選択、レジスタ割り当て、命令エンコーディングの3つすべてが完成するまでは、実行方法が得られません。そのため、エンコーディングの完成前後には、命令選択とレジスタ割り当てで多くのバグが見つかると予想しています。もちろん出力を手作業で調べて明らかな問題は修正しますが、実際にコードを動かせるようになるまで、多くのバグが残ります。
+
+つまり、この章で説明する作業に対する更新やバグ修正が、ほかの章に含まれています。
+
+## 移植可能なコンパイル
+
+CPU の移植先ごとに1つの、新しい抽象 `Machine` クラスを追加します。`Machine` は移植先の名前、すべてのレジスタ名、そして *理想* ノードからマシンノードを生成する方法を定義します。さらに、コード生成時にマシン非依存のコンパイラ部分が使う *split* 演算と *jump* の生成も可能にします。
+
+各種呼び出し規約を選択できるように、新しい CallingConv 列挙型を追加します。
+
+## 命令選択フェーズ
+
+*大域的コード移動* の前に、新しい *InstructionSelection* コンパイルフェーズを追加します。これは任意ですが、*理想* ノードをマシン固有の派生形に置き換えます。命令選択には対象 CPU 名を渡し、その時点で移植コードを検索して使用します。これによって、少なくとも Java 実装では CPU 移植先を遅延して追加できます。
+
+## マシン固有のノード
+
+`MachNode` インターフェースを実装する「マシン固有」のノードという概念を追加します。`MachNode` ノードは、各命令の入力・出力レジスタ、ビットエンコーディング、利用者向けの表現を定義します。後ほど、局所スケジュールを改善するための機能ユニット情報を追加します。
+
+## CodeGen コンパイルドライバの整理
+
+さらに多くの静的なグローバル状態を、すべての最上位ドライバ間で受け渡す CodeGen オブジェクトに移します。Node のコンストラクタには渡さないため、idealize() 呼び出しにも渡しません。静的なグローバル状態が必要なケースの大半は、依然としてこれらです。要するに、コンパイラはずっと関数型に近づき、並行コンパイルやマルチスレッドコンパイルに向けて大きく前進します。
+
+## 命令選択を通じたメモリの扱い
+
+パーサーは1つの `$mem` 束縛を保持します。BulkMemPhi は必要に応じてエイリアスを並列の MemPhi に分割し、MemMerge は既定のメモリと明示的なスライスをまとめます。両方のマシン選択器は、これらのノードクラスとエイリアス情報を保持します。メモリの Phi を通常の値の Phi には変換しません。
+
+この章では、コンストラクタの非ゼロ値を明示的な Store に変換し、割り当てそのものはゼロ初期化演算として維持します。New は `{ctrl, $mem, size}` を消費し、`{ptr, $mem}` を生成します。その入力は、割り当てる構造体のエイリアスをカバーする部分的な MemMerge です。単一のメモリ結果も、同じエイリアスをカバーします。パーサーは周囲の集合体に無関係なメモリを保持します。割り当てのサイズレジスタは入力2、ポインタ結果は出力0で、メモリにはレジスタがありません。
+
+選択されたメモリ演算は、x86 の算術命令や比較命令が Load を吸収しても、フィールドのエイリアスを保持します。そのため大域的スケジューリングは、共通の MemOpNode を通じ、MemMerge 内の該当スライスをたどって反依存関係を見つけます。メモリを結果とする命令は書き手で、ほかのメモリ演算は読み手です。書き手の末尾にある順序付け辺は、レジスタを要求しません。Phi の因数分解で使用する単純な1段階の Load ガードは変更しません。
+
+Call は依然としてメモリ全体を消費し、生成します。Call はブロックを終了するため、スケジューリングは引数リストに入力を追加せず、読み取りを Call の前に引き上げます。直接マシン呼び出しは定数の対象を埋め込み、制御、メモリ、引数の入力だけを保持します。
+
+## レジスタとレジスタマスク
+
+`Machines` はレジスタを小さな密な整数として定義します。レジスタ割り当て器は割り当て時にこれらの番号を使います。小さな整数からマシンレジスタへの対応は移植者に任されますが、通常は明らかな1対1の対応があります。X86 では RAX がレジスタ0、RCX がレジスタ1となり、16個の GPR まで続きます。XMM レジスタ番号は16から31です。レジスタ番号は一意でなければなりません。割り当て器はこれによってレジスタを追跡します。
+
+レジスタマスククラス `RegMask` は、許可されたレジスタのビット集合を保持します。大半のマシン演算は全レジスタの部分集合に制限され、許可集合を RegMask で記述します。大半の RegMask は、たとえば `Mul` 演算で許可されるレジスタ集合のように不変ですが、割り当て器は可変のレジスタ集合も広範囲に使います。
+
+呼び出し規約は多くの固定レジスタを指定し、実際には許可レジスタ集合をかなり「縛る」傾向があります。
+
+## SystemV または Win64 呼び出し規約を持つ X86_64_V2 移植
+
+`node/cpus/x86_64_v2` ディレクトリには、X86 64 V2 への移植 `x86_64_v2.java` があります。16個の64ビット GPR、16個の XMM レジスタ、X86 フラグをサポートします。理想化された Simple の Sea-of-Nodes から X86 演算を対応付けるパターンマッチャがあります。アドレッシングモードを除けば、理想ノードから X86 演算へほぼ1対1で対応付けます。
+
+### 通常の命令選択
+
+instSelect フェーズは理想グラフを走査し、理想演算からマシン演算への対応を保持します。先着順で最初に一致したものを採用する、貪欲なパターンマッチを行います。特別な動作のない演算は局所的な検索だけを行います。たとえば `Mul` は X86 の `MulX86` に直接対応します。大半のマッチの右辺は即値定数にでき、即値版（`MulIX86`）に対応します。
+
+### アドレッシングモード
+
+多くの X86 演算では、入力の1つが `Load` なら、メモリを入力にする派生形を使えます。X86 マッチャの専用の `address()` 呼び出しが各種アドレッシングモードを探し、メモリ専用の派生形を構築します。これらは個別に明示する必要がありますが、単純な1行のマッチと、メモリ版を割り当てる1行で済みます。
+
+### Compare と Jmp
+
+Simple の `BoolNode` は `0/1` の値を生成します。X86 では `Cmp/SetXX` という命令列で行います。X86 の `Jxx` は `0/1` ではなく `FLAGS` を受け取るので、`SetXX` を飛ばして直接 `Cmp` を使います。理想 `Bool` を直接使う場合は `SetXX` が必要です。つまり `return a==3` は `CmpX86 RAX,#3; SetEQ RAX; ret;` に対応し、`if( a==3 )` は `CmpX86 RAX,#3; jeq;` に対応します。
+
+## RISC-V 移植
+
+`node/cpus/riscv` ディレクトリには RISC-V への移植 `riscv.java` があります。32個の64ビット GPR と32個の浮動小数点レジスタをサポートします。理想化された Simple の Sea-of-Nodes から riscv 演算を対応付けるパターンマッチャがあります。現在の対象は `RVA23U64` です。
+
+### 通常の命令選択
+
+**X86_64_V2** と同様に動作します。riscv には *複雑な* アドレッシングモードがないため、ほとんどの場合は貪欲なパターンマッチを適用しません。特別な動作のない演算は、単純に検索します。
+
+### 制限された ISA
+
+RISC-V は単純なアドレッシングモードとオーバーロードを備える、制限された ISA です。たとえば `lea` はありません。
+
+### 分岐
+
+`x86_64_v2` の分岐は、フラグを設定する比較命令と、そのフラグを使うジャンプ命令を必要とします。一方 RISC-V は、必要なオペランドをすべて分岐命令そのものに含め、別の比較ステップを不要にします。
+
+例:
+
+```
+beq x10, x11, some_label
+```
+
+`CBranchRISC` がこの動作を実装します。
+
+### R フラグを持たない
+
+RISC-V には R フラグがありません。同様の機能を得るには、比較結果に応じてレジスタ値を明示的に設定できます。
+
+```
+xor     a0, a0, a1
+seqz    a0, a0
+```
+
+最初の `xor` の後、`a0` と `a1` が等しければ `a0` はゼロになります。`seqz` 命令は、前の演算で `a0` がゼロになっていれば `a0` を1に設定します。これは `nodes/cpus/riscv` 移植の `SetRISC` に対応します。
+
+### 固定長命令
+
+RISC-V の命令長は（ほとんどの場合）32ビット固定であり、エンコーディング側で変位を活用できます。
+
+例:
+
+```
+flw fa5, 0(a0)
+flw fa4, 12(a0)
+fadd.s fa0, fa5, fa4
+```
+
+（`flw` の前にロードは必要ありません。）
+
+### ABI 名（レジスタ）
+
+`RISC-V` の汎用レジスタ（`GPR`）は `x0` から `x31`、浮動小数点レジスタは `f0` から `f31` です。
+
+読みやすさを高め、呼び出し規約と整合させるため、RISC-V はレジスタの ABI 名を定義し、生の番号よりも直感的な別名を提供します。
+
+| レジスタ | 別名 | 用途 | 保存する側 |
+|----------|-------|------------------------------|----------|
+| x10 | a0 | 関数の引数／戻り値 | 呼び出し側 |
+| x11 | a1 | 関数の引数／戻り値 | 呼び出し側 |
+| x12 | a2 | 関数の引数 | 呼び出し側 |
+| x13 | a3 | 関数の引数 | 呼び出し側 |
+| x14 | a4 | 関数の引数 | 呼び出し側 |
+| x15 | a5 | 関数の引数 | 呼び出し側 |
+| x16 | a6 | 関数の引数 | 呼び出し側 |
+| x17 | a7 | 関数の引数 | 呼び出し側 |
+
+関数に引数を渡すとき、呼び出し側からの最初の8個の引数はレジスタ `a0` から `a7` で渡します。
+
+### 浮動小数点値のロード
+
+現在、浮動小数点定数は、浮動小数点レジスタに変換する前に、まず `integer GPR` にロードします。この処理は RA フェーズで次のように書き換えます。
+
+````
+lui a0, 262144
+fmv.w.x fa0, a0
+````
+
+非定数値には、GPR と FPR の両方をサポートする、より広いレジスタマスクを使います。この実装は `nodes/cpus/riscv/LoadRISC` にあります。