1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
# 第21章: 命令エンコーディングと ELF
[English](README.md) | 日本語
この文書は [原文](README.md) の日本語訳です。
[前の章: 第20章](../chapter20/README.ja.md) |
[次の章: 第22章](../chapter22/README.ja.md)
この章では、スケジューリングとレジスタ割り当てを終えたグラフを実行可能な命令に変換します。各マシンノードがバイトを書き込み、コンパイラがブロックを配置し、局所参照を解決し、リンカ向けの ELF オブジェクトを出力します。これで生成コードを実行できるため、命令選択、レジスタ割り当て、呼び出し規約も一緒にテストできます。
直線的なリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter21) を読み、[第20章と比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter20...linear-chapter21) することもできます。
この章の[完全な言語文法](21-grammar.ja.md)はこちらです。
## マシンノードからバイトへ
命令選択は演算とレジスタ制約を選びます。レジスタ割り当ては物理レジスタとスタックスロットを割り当てます。その後、エンコーディングがオペコード、割り当て済みレジスタ、即値オペランドを命令バイトへ組み合わせます。この時点で命令は別のレジスタを選べません。周囲の命令が、すでに割り当て器の選択に依存しているためです。
[Encoding.java](../../src/main/java/com/seaofnodes/simple/codegen/Encoding.java) がバイトストリームを所有し、各ノードのオフセットとエンコード後の長さを記録します。ドライバは次を行います。
1. 基本ブロックを配置し、必要に応じて分岐を挿入または反転する。
2. スケジュール順に `MachNode.encoding(Encoding)` を呼ぶ。
3. 短い命令形式と長い命令形式を確定する。
4. このコンパイル内に対象がある参照を修正する。
補助関数 `add1`、`add2`、`add4`、`add8` は、リトルエンディアンの値を追加します。エンコーディング関数は `Encoding.reg` で割り当て済みレジスタを得ます。スタックオペランドは、保存レジスタや出力引数の領域も含む、関数のフレーム配置を使います。彩色成功だけでは呼び出し規約の正しさは証明できません。生成プログラムは呼び出し側の値も保存しなければなりません。
## 3つの命令セット
対象はこのドライバを共有します。マシンノードがコンパイラのオペランドを解決し、共有の [ISA エンコーダ](../../isa/README.md) を呼びます。
| 対象 | 主なエンコーディング上の課題 |
|---|---|
| RISC-V | 命令語内のレジスタと即値のフィールド。大きい定数とアドレスには複数命令が必要。 |
| AArch64 | レジスタ形式、制限された即値エンコーディング、複数命令による定数構築。 |
| x86-64 | 可変命令長、レジスタ接頭辞、アドレッシング形式、短い分岐と長い分岐。 |
たとえば小さな整数は命令に直接収まる一方、大きな整数には複数命令や定数プールからのロードが必要なことがあります。その結果、固定幅命令を持つ対象でも、マシンノードによって異なるバイト数を出力できます。
[エンコーディングリファレンス](encoding-reference.ja.md) は、詳細なビット配置、具体例、ISA リンクを保持しています。個々の命令実装ではそれらの詳細が重要ですが、ここで説明するコンパイラのパイプラインは変わりません。マシンノードの接続は [node/cpus](../../src/main/java/com/seaofnodes/simple/node/cpus) にあります。共有の [X86 エンコーダ](../../isa/src/main/java/com/seaofnodes/isa/X86.java) が x86 のバイト出力を所有し、[Arm64](../../isa/src/main/java/com/seaofnodes/isa/Arm64.java) と [RiscV](../../isa/src/main/java/com/seaofnodes/isa/RiscV.java) は命令語を詰めます。
たとえば `AddX86` はオペコード `0x03` を選びます。その基底 `RegX86` は割り当て済みの2レジスタを読み、`X86.reg(enc,opcode(),dst,src)` を呼びます。共有メソッドは REX.W、オペコード、ModRM を `Encoding` のバイトバッファへ直接書き込みます。`add r9,r10` のバイト列は `4d 03 ca` です。レジスタ制約と2アドレスの要求は、この章のマシンノードに残ります。これによって、ADD を使う判断と、命令の固定されたビット表現を分離します。
ロードも同じ境界を使います。この章は、型と割り当て済みオペランドから、幅、符号拡張、レジスタバンクを解決します。`X86.load` はそれらの情報と具体的なアドレスを受け取り、この章のグラフや型の束に依存しません。後の章はコンパイラが進化しても、これらのエンコーディングを再利用します。
ARM と RISC-V の実行テストも `isa/src/test-support` の評価器を再利用します。この章のテストハーネスがメモリイメージを準備してリンクし、評価器がそのバイト列を実行します。こうして命令の意味を1か所に保持しつつ、イメージ構築は各章のコンパイラに従います。評価器はテストとともにコンパイルします。Make のリリース jar は、引き続きコンパイラとテストハーネスの両方を同梱します。
## 再配置と ELF
前方分岐は、最初にバイトを書き込む時点では最終的な変位を知りません。対象のオフセットは、間にあるすべてのエンコーディングに依存します。別の分岐を短縮・拡張すると、対象が再び動く場合があります。配置走査が命令サイズを確定してから、局所再配置が最終的な変位を修正します。
外部参照には、後での修正が必要です。たとえばコンパイラは、リンカが `malloc` をどこへ配置するか知らなくても、その呼び出しを出力できます。オブジェクトファイルはシンボル、修正位置、再配置種別を記録します。種別は命令と一致しなければなりません。x86 の呼び出し変位と、分割された RISC-V のアドレスは別のフィールドを占めるので、同じ修正演算は使えません。
[ElfFile.java](../../src/main/java/com/seaofnodes/simple/codegen/ElfFile.java) は、オブジェクトのコード、データ、シンボル、再配置記録を書き込みます。大きな定数も外部呼び出しと同じ配置問題を生じます。最終的なアドレスを、それらをロードする命令に接続しなければなりません。局所再配置とオブジェクトファイル再配置は、参照を正しくするという同じ責務の2段階です。
## 結果の実行
第11章の遅延メモリ分割が、エンコーディングまで引き継がれます。パラメータ、呼び出し、戻りはメモリ全体を運び、`BulkMemPhi`、`MemPhi`、`MemMerge` が各関数内の正確なエイリアスを発見します。New は `{ctrl, $mem, size}` を消費し、`{ptr, $mem}` を生成します。そのメモリは割り当てた構造体のエイリアスを覆い、周囲のマージは無関係なエイリアスを保持します。非ゼロ初期化は依然として明示的な Store を使います。メモリノードと順序付け辺はレジスタを必要としません。
スケジューリングは集合体を通じてエイリアスをたどり、対応する Store、割り当て、呼び出しの前に読み取りを順序付けます。Call は順序付けオペランドを追加せず、引数リストを保持します。合成されたループ出口は、エイリアスごとに正確なメモリを集めます。
実行の回帰テストは、コンストラクタ、インライン化されない呼び出しと再帰呼び出し、インライン化、配列更新を、ネイティブ x86 と両エミュレータで検証します。整数が XMM にある場合もあるため、全幅の x86 ロードはエンコーディング選択時に割り当て済みのレジスタバンクを使います。ARM エミュレーションは、これらの確認で使う大きな定数に対する MOVZ/MOVK の半語構築を処理します。
`make tests` は、生成 x86 コードをリンクして実行する C ハーネスと、RISC-V/AArch64 エミュレータの確認を含みます。結果とスピル数の両方を比較します。ネイティブプロセスの失敗は完全な終了ステータスを保持します。エミュレータの確認は、自身の結果メモリを読まなければなりません。別の対象の結果と一致するだけでは不十分です。
`make spill-stats` を実行すると、アサーションを有効にして同じテストから割り当てを収集します。各テスト／CPU／ABI を報告してから、群の合計を表示します。スピルの期待値との不一致は、残りの対象や実行確認を省略せず記録します。そのような不一致が1つでもあればコマンドは失敗します。構造的な割り当て器の回帰テストはスピル合計から除外します。
## RegAlloc の改良: コピーの除去
分割は2つの生存区間間にコピーを挿入します。両方を安全に1区間へまとめられるなら、彩色前にコピーを除去できます。[Coalesce.java](../../src/main/java/com/seaofnodes/simple/codegen/Coalesce.java) は、区間が干渉しないことを確認し、許可レジスタマスクの共通部分を取り、隣接ノードをまとめます。結果の隣接ノード数が利用可能レジスタ数より小さいときだけ併合します。この単純で保守的な規則は、各隣接ノードが異なるレジスタを取っても、色の選択肢を残します。
併合は隣接するノードの隣接リストも更新し、削除したコピーへの代表参照を除去します。拒否された併合は元の隣接リストを復元します。マスクの互換性だけでは不十分です。同時に生存する2値は、両方が同じレジスタを許しているだけでは共有できません。
彩色後にも、直後の命令に1つだけ使用があるコピーは、そのオペランドがコピー元レジスタを受け入れ、2アドレスのオペランドでなければ除去できます。たとえば `mov rpc=s8; st1 [rpc+4],s1` は `st1 [s8+4],s1` になります。隣接していることで、間にコピー元を上書きするものがないと証明できます。Phi と制御フローの使用側は除外します。この局所整理はスピル選択を変更せず、別の CFG 解析をせずに併合を補完します。
互換性のある再実体化や、破壊を考慮するコピー再利用など、第20章の合法性と進捗の修正も引き継ぎます。第21章はネイティブフレームと ABI のサポートを保持します。より強い色バイアスと安いスピルの順位付けは第22章、多数の使用のグループ化は第23章、低頻度側を先にするループ分割は第24章、面積／コストの順位付けは第25章に残します。
以下は **この章のコンパイラ** を使い、最適化器の既定シード123で Windows x86-64 上で測定した合計です。分割はレジスタ移動を含む残存 `SplitNode` であり、必ずしもメモリスピルではありません。重み付き数は各分割に `8^loopDepth` を掛けます。
| プログラム群 | コンパイル数 | 残存する移動 | ループ重み付き移動 |
|---|---:|---:|---:|
| 第20章 | 39 | 380 | 576 |
| 第21章 | 52 | 467 | 1,076 |
| **合計** | **91** | **847** | **1,652** |
第20章の行は、BrainFuck と MergeSort を含む元の13入力すべてを、3つの SystemV 対象について固定しています。これらは `Chapter20Test` にあります。以前そのファイルにあった改訂済みソース／ABI ケースは `Chapter21AllocTest` に保持し、`Chapter21Test`、ネイティブ BrainFuck/MergeSort テストと合わせて第21章の行を構成します。その行には ARM/SystemV が17、RISC-V/SystemV が17、x86/SystemV が8、x86/Win64 が10コンパイルあります。ネイティブホスト ABI の変更はこの行に影響するため、同じホストと対象で比較してください。
隣接コピー転送の前、メモリ移植によって、群の構成と割り当て器のヒューリスティックを変えずに、以前の合計840／1,456が845／1,559になりました。変化した行は以下のすべてです。各項目は残存／ループ重み付き分割です。
| 群／プログラム | 対象／ABI | 変更前 | 遅延メモリ |
|---|---|---:|---:|
| 20 / MergeSort | ARM / SystemV | 44 / 44 | 41 / 41 |
| 20 / BrainFuck | RISC-V / SystemV | 35 / 42 | 37 / 58 |
| 20 / Alloc2 | x86 / SystemV | 3 / 3 | 4 / 4 |
| 20 / Alloc2 | ARM / SystemV | 10 / 10 | 9 / 9 |
| 20 / String | x86 / SystemV | 7 / 14 | 8 / 15 |
| 20 / String | RISC-V / SystemV | 14 / 14 | 10 / 10 |
| 20 / String | ARM / SystemV | 13 / 13 | 10 / 10 |
| 21 / Sieve | x86 / Win64 | 24 / 178 | 24 / 185 |
| 21 / Sieve | RISC-V / SystemV | 19 / 89 | 22 / 92 |
| 21 / Sieve | ARM / SystemV | 23 / 93 | 21 / 91 |
| 21 / BrainFuck | RISC-V / SystemV | 35 / 42 | 46 / 130 |
重み付き増加の大半は RISC-V BrainFuck によるものです。read-before-New の順序付けだけを省く診断実行では、その2行は35／42と37／58になります。これでコストの大半を説明できますが、コンパイラは順序制約を保持します。メモリ移植にヒューリスティックの調整は含めていません。
続く Load 検索の改良は、ループの N 方向メモリマージを通じて BrainFuck の固定プログラム長を畳み込みます。すべての後退辺の枝が畳み込めるか、同じポインタについて変更されていないメモリへ戻る必要があります。RISC-V の Hello World 実行で907回のヒープロードを除去し、スタックアクセスを1,006ロード／572ストアから15／15へ減らします。コピー転送前、その行は144移動／165重み付き移動で、91項目全体は943／1,594でした。隣接コピー転送は、それぞれ35／42と821／1,444へ減らします。RISC-V の Hello World 実行は、ヒープとスタックのアクセス数を変えずに、21,920ではなく21,787命令を実行します。これらはエミュレータの命令数で、ハードウェアの時間測定ではありません。現在のネイティブ BrainFuck テストと、すべての実行時アサーションは有効です。
その後 GCM の反依存関係の支配ノード走査を復元したことで、RISC-V BrainFuck の各行は35／42から48／146へ変わり、上の現在の表になりました。条件付き書き手は、後の Load 配置を支配するとは限らないため、書き手の正確なブロックだけを確認すると、必要な順序付けを見逃します。復元した走査は、条件付きストア前の読み取りプログラムが120でなく140を返していた問題を修正します。両方の BrainFuck 実行確認と、91項目全体のスピル監査が成功しています。移動数の増加は、割り当て器のヒューリスティックを変えずに記録しています。
次の併合比較は遅延メモリより前のものです。両側はその監査の同じコンパイラを使います。現在のグラフに対する新たな機能無効化比較ではありません。
| 以前の制御された比較、同じ91コンパイル | 分割 | ループ重み付き分割 |
|---|---:|---:|
| 併合を無効にした監査コンパイラ | 1,070 | 1,889 |
| 併合を有効にした監査コンパイラ | 840 | 1,456 |
制御実行は `graphColor` 内の `Coalesce.coalesce` だけを無効にします。両実行で、割り当て、レジスタ制約、実行時確認が成功します。無効化した実行は、スピル期待値の9件の変化を報告し、意図どおり失敗終了します。併合は230移動（21.5%）と433重み付き移動（22.9%）を減らします。局所的な増加は起きる場合があり、1例ではなく集計がトレードオフを判断します。
最終監査は x86/RISC-V の狭いストアマスクをバックポートし、ARM のレジスタバンク選択と浮動小数点メモリ演算を修正しました。バイトストアを合法なレジスタに制限すると、RISC-V BrainFuck は2つの群それぞれで211から42重み付き移動となり、以前の表から44の単純移動／338の重み付き移動が減ります。これらの正しさの修正は比較の両側に含まれます。より広いマスクで行った以前の測定は過去の記録で、現在の基準値ではありません。第20章の357重み付き移動も併合の基準値ではありません。第21章は機械命令への変換を変更し、ネイティブ ABI の責務を実装しているためです。
|
