From 863a6ed0ad723e06c76f392d4fb3a5f6bd22863c Mon Sep 17 00:00:00 2001 From: Jun Kawasaki Date: Tue, 6 Oct 2026 13:01:11 +0900 Subject: docs: add Japanese translations for all chapters --- chapter20/README.ja.md | 262 ++++++++++++++++++++++++++++++++++++++++ chapter20/README.md | 2 + chapter20/docs/18-grammar.ja.md | 138 +++++++++++++++++++++ chapter20/docs/18-grammar.md | 2 + 4 files changed, 404 insertions(+) create mode 100644 chapter20/README.ja.md create mode 100644 chapter20/docs/18-grammar.ja.md (limited to 'chapter20') diff --git a/chapter20/README.ja.md b/chapter20/README.ja.md new file mode 100644 index 00000000..c33630e2 --- /dev/null +++ b/chapter20/README.ja.md @@ -0,0 +1,262 @@ +# 第20章: グラフ彩色によるレジスタ割り当て + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第19章](../chapter19/README.ja.md) | +[次の章: 第21章](../chapter21/README.ja.md) + +## 参考資料 + +これは Briggs-Chaitin-Click 型の割り当て器であり、過去25年間にわたり大きな成功を収めてきた HotSpot の C2 割り当て器に非常によく似ています。 + +Wikipedia にはレジスタ割り当て全般のよい概説があります: https://en.wikipedia.org/wiki/Register_allocation + +Chaitin の原論文: https://en.wikipedia.org/wiki/Register_allocation#CITEREFChaitin1982 + +Briggs による追加: https://dl.acm.org/doi/10.1145/177492.177575 + +Briggs/Chaitin のよい講義スライド PDF: https://aktemur.github.io/cs544/lectures/chapter%2013%20registerAllocation.pdf + +Briggs や Chaitin を組み合わせて検索すると、ほかにも役立つリンクがいくつか見つかります。基本的に、この時代にはレジスタ割り当ての改良が相次ぎ、その多くが高性能な主流コンパイラに取り込まれました。 + +グラフ彩色割り当て器の高速化に関する非常に古い未発表論文 [Interference Graph Trimming](docs/ifg_trim.pdf) を同梱しました。 + +## 命令選択、レジスタ割り当て、命令エンコーディングにまつわる全体的な問題と開発上の問題 + +レジスタ割り当ての出力、すなわち演算に対するレジスタの割り当ては、実行方法がないと大量にテストするのが困難です。命令選択、レジスタ割り当て、命令エンコーディングの3つすべてが完成するまでは、実行方法が得られません。そのため、エンコーディングの完成前後には、命令選択とレジスタ割り当てで多くのバグが見つかると予想しています。もちろん出力を手作業で調べて明らかな問題は修正しますが、実際にコードを動かせるようになるまで、多くのバグが残ります。 + +つまり、この章で説明する作業に対する更新やバグ修正が、ほかの章に含まれています。 + +特にレジスタ割り当て器については、これからかなりの数の章にわたり、章ごとに徐々に改良を追加します。割り当て器は一般に最終的には多数のヒューリスティックを持ちますが、それらを少しずつ追加します。 + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチ上の直線的な Git リビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter20) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter19...linear-chapter20) することもできます。 + +## 基本理論 + +参考資料には基本概念の説明がいくつかありますが、重複を承知で、ここでも短く説明します。 + +読者はレジスタ割り当てが *なぜ* 必要かを知っていると仮定します。マシンレジスタは価値の高い有限資源であり、あらゆる有限資源と同様、適切に割り当てる必要があります。 + +グラフ彩色はそのような割り当て方法の1つです。マシンレジスタを色として扱い、各 *生存区間* が自身のレジスタ／色を必要とする *生存区間の干渉グラフ* を構築します。グラフを彩色することで、各生存区間が、特に別の生存区間と重なる、つまり *干渉する* 場合に、一意のレジスタを得ることを保証します。 + +彩色が成功すれば割り当ては終了し、いくらかの管理処理を経て、プログラムはたとえばコード出力の準備が整います。彩色が失敗したら、衝突する生存区間をスピルするか分割する必要があります。この割り当て器では、生存区間の *分割* を行います。分割により区間は短くなり、干渉するほかの区間が減るため、彩色しやすくなります。一般に、大きな関数は彩色可能になるまで数回の分割を必要とすることがあります。この問題は NP 完全なので保証はなく、最終的な割り当て品質は分割と彩色のヒューリスティックに大きく依存します。 + +したがって、彩色の中核アルゴリズムには多くの「高度な理論」を使いますが、実際の成功の多くは、多数のヒューリスティックに依存します。 + +### 彩色ラウンド + +彩色が得られるまで、次のラウンドを繰り返します。 + +- 生存区間を構築します。区間内のすべての命令は同じレジスタを必要とします。Phi 関数は無関係な定義／使用の辺を同じ生存区間に組み込み、衝突の多い大規模な相互接続区間を生み出すことがあります。一部のハードウェア演算は入力と出力に同じレジスタを要求し（X86 はこの点で悪名高い）、これも区間の数を減らして大きくします。互いに素な集合の Union-Find アルゴリズムを使い、プログラムを前向きに1回走査して高速に区間を構築します。 +- 干渉グラフを構築します。同時に生存する区間どうしは *干渉*、つまり衝突します。CFG を後ろ向きに走査する生存性解析で構築し、ループの入れ子深さに応じて複数回の走査が必要な場合があります。データ構造は通常2次元ビット集合で、三角形の部分だけを保持してサイズを半分にします。生存性解析の一部として、ブロックごとの到達定義集合も持ちます。 +- 干渉グラフを彩色します。グラフのノード（生存区間）のうち、次数が厳密に低いもの（隣接ノードより利用可能レジスタが多いもの）は、必ず色を得られます。衝突する隣接ノードが少ないのでレジスタ（色）を必ず得られるため、グラフから除去できます。この自明なノードの除去により、さらに多くのノードが自明になります。ノードが尽きて彩色が保証されるか、高次数のクリーク、すなわち相互に干渉し、どれも色を保証されない区間集合が見つかるまで繰り返します。後者では、彩色できないかもしれない「危険な」区間を1つ取り出します。グラフが空になったら、逆順に区間を戻しながら彩色します。自明な区間はすべて彩色できますが、危険な区間はできる場合もできない場合もあります。 +- すべての区間が色を得たら、レジスタ割り当ては終了です。そうでなければ分割ラウンドに入ります。彩色できなかった区間を、いくつかのヒューリスティックで多数の小さな区間に分割します。分割には相反する要求があります。多すぎるとスピルが増え、一般に割り当てが悪くなります。少なすぎると彩色不能のまま、割り当てに向けて前進しません。分割が終わったら、生存区間構築、干渉グラフ構築、彩色という新たなラウンドを始めます。 + +## レジスタとレジスタマスク + +レジスタこそ、レジスタ割り当ての対象です。0から始まる小さな密な整数で表し、番号は一般にハードウェアのエンコーディングに従います。X86_64 では RAX が0、RCX が1となり、16個の GPR まで続きます。XMM レジスタ番号は16から31です。番号は一意でなければなりません。割り当て器はこれによってレジスタを追跡します。 + +#### 単純な `long` ではなく RegMask クラスを使う理由 + +レジスタ集合はレジスタマスクに格納します。小さく単純なマシンなら i64 や i128（64または128ビット整数）で十分であり、すべての割り当てがこのビット数に収まるなら、この表現がはるかに優れています。割り当て器は、スタック経由のパラメータと、レジスタを得られない分割にもビットを必要とします。X86 のような32レジスタのマシンでは、フラグ用の1つを加えて33レジスタです。Java の `long` は64ビットなので、スピルとスタック渡しに31ビットが残ります。これはほぼすべての割り当てに十分で、最大級のものだけが使い切ります。しかし64レジスタのチップへ移ると、すぐに不足し、少なくとも128ビットのマスクが必要です。Java では128ビット値を直接 *返せない* ため、Simple は `RegMask` クラスのオブジェクトを使います。 + +#### スタックスロット + +Click による拡張の1つは「スタックスロット」を単なる別のレジスタとして扱う考え方です。ほかのレジスタと同様に彩色することで、スタックを非常に効率よく使えます。C2 は非常に小さいスタックフレームで知られています。もう1つの利点は、callee-save レジスタが優先して分割されることです。生存期間が非常に長く、入口での定義と出口での使用が1つずつしかないためです。その分割は最終的にスタックに彩色され、自然に呼び出しのプロローグとエピローグを構築します。この割り当て器は、それ以外にスタックフレーム管理のための特別な処理を行いません。結果として自然に得られます。 + +多くのレジスタマスクは不変です。たとえば特定のオペコードで許されるレジスタや、呼び出し規約を表すものです。一方、制約集合を蓄積する際に割り当て器が日常的にビットを落とす、可変のビット集合を表すマスクもあります。使い方を区別しやすくするため、`RegMask` クラスには可変版と不変版があります。 + +#### メモリ + +メモリ辺は順序を強制するために存在しますが、レジスタは得ません。割り当て器は基本的にそれらを無視します。 + +### Callee-save / Caller-save レジスタ + +この割り当て器は callee-save と caller-save のレジスタをほぼ特別扱いせず、保存・復元専用のプロローグやエピローグも構築しません。割り当て開始時に、各 `Return` と、各 `Fun` に由来する `CalleeSave` との間に SoN グラフ辺を追加します。通常の ABI が定義する callee-save 集合に固定するレジスタマスクを、これらの辺に与えます。 + +callee-save の生存区間は、関数先頭の `CalleeSave` という単一定義と、`Return` という単一使用を持ちます。安くスピルでき、広い範囲にわたってレジスタを解放するので、理想的なスピル候補です。レジスタを増やすために何かをスピルする必要があると、これらが最初にスピルされます。通常の生存区間分割の結果として、プロローグとエピローグが構築されます。 + +`Calls` は caller-save レジスタを破壊します（callee-save マスクを反転したものです）。これはレジスタを破壊するほかの演算と同様、通常の干渉グラフ構築で計算します。呼び出しで多数のレジスタを破壊すると、その時点で生存しているものから利用可能なレジスタがすべてなくなることが多く、スピルが強制されます。その結果、すぐに理想的な候補である callee-save レジスタがスピルされます。 + +## 生存区間 + +生存区間は、同じレジスタを得なければならないノードと辺の集合です。形状にほとんど制限のない、相互接続された網を形成します。また、すべての構成部分のレジスタ制約を集約します。 + +生存区間は `LRG` クラスのインスタンスとして保持します。そのフィールドの大半はスピルのヒューリスティック用ですが、LRG を定義する重要なフィールドもいくつかあります。`RegAlloc` には、Node から LRG への参照表、すなわち `Node` から `LRG` への対応を含む、LRG を扱う関数がいくつもあります。これは各 Node に専用の LRG フィールドを持つのと非常によく似ていますが、LRG は RegAlloc 中だけ使うので、それ以外ではフィールドが無駄な重荷になります。 + +LRG は自身の名前となる、一意で密な整数 `_lrg` 番号を持ちます。新しい番号は `RegAlloc._lrg_num` カウンタから得ます。LRG は結合できます。これが [Union-Find アルゴリズム](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) です。結合時には、小さい `_lrg` 番号が代表になります。結合は `BuildLRG` 中だけ行い、`Phi` がすべての入出力を同じレジスタに強制するか、2アドレス命令のために発生します。LRG には対応する `union`、`find` 呼び出しと、設定された `_leader` フィールドがあります。 + +割り当て後、`LRG._reg` は選択されたレジスタを保持します。割り当て中、`LRG._mask` は利用可能なレジスタ集合を保持します。通常はすべての既定値から各種の衝突を除いたものです。 + +`LRG._adj` は干渉グラフ全体の一部として隣接ノードのリストを保持し、彩色フェーズでだけ使います。[グラフについての詳細はこちらです。](https://en.wikipedia.org/wiki/Graph_(abstract_data_type)) これはグラフの「隣接リスト」表現で、IFG の2次元ビット集合（それ自体は `BitSet` の1次元リスト）から構築します。グラフ彩色によるレジスタ割り当ては、アルゴリズムの途中でデータ構造のレイアウトを変えることが有効な、数少ない場面の1つです。 + +残りのフィールドは、各種スピルのヒューリスティック専用です。 + +- `_machDef` `_machUse` `_uidx`: 代表となる定義と使用。 +- `_splitDef` `_splitUse`: この LRG に関係する代表的な分割。バイアス付き彩色はレジスタ選択を合わせて、これらを除去しようとします。 +- `_selfConflicts`: *自己衝突* ノードの部分集合。干渉グラフ構築時に検出し、積極的な分割を必要とします。 +- `_1regDefCnt` `_1regUseCnt`: 単一レジスタに固定された定義と使用の数。通常、レジスタ選択の自由を取り戻すため、使用の直前または定義の直後で強制分割を必要とします。 + +## 生存区間と衝突 + +生存区間の `_mask` が空になると、*ハード衝突* か *破壊* が起きた可能性があります。区間は自分自身とも干渉し、*自己衝突* を起こします。彩色中に、干渉区間の彩色不能なクリークが見つかり、*容量不足のスピル* に至ることもあります。このため区間内にはいくつかの衝突レベルがあり、それぞれに異なる対処のヒューリスティックを使います。 + +### ハード衝突 + +生存区間は、レジスタ要求が衝突し、有効な選択肢がなくなる *ハード衝突* を起こすことがあります。明らかな例は、入口のパラメータが `rdx` に固定されながら、出口の値として `rax` にも必要になる場合です。両方を同時に選べないので分割が必要です。生存区間構築フェーズでは、すべての定義と使用のレジスタ制約を AND します。`RegMask` は有効レジスタをすべて失うか、わずかな選択肢だけを残すことがあります。 + +ハード衝突は通常、生存区間構築時に見つかり、干渉グラフ構築や彩色の前に分割ラウンドを引き起こします。干渉グラフ構築中にも見つかる場合があり、一般に1レジスタの破壊が原因です。 + +### 干渉の回避 + +Briggs-Chaitin 割り当て器に対する Click の拡張の1つは、レジスタ制約を利用して干渉グラフの次数を下げることです。そうでなければ辺集合は O(n^2) になります。LR1 が、`rdx` を必要とする呼び出し引数などによって単一レジスタに制限され、より多くの選択肢を持つ LR2 と本来衝突する場合、LR2 の選択肢から `rdx` を除きます。`rdx` がなければ両者に共通レジスタがなくなり、衝突しません。その間の干渉グラフ辺を単に追加しないのです。呼び出し引数の制限は非常に一般的で、この辺除去は O(n^2) の辺集合を大きく縮小し、割り当てを大きな定数倍だけ高速化できます。 + +### 自己衝突 + +生存区間は、異なる2つの値が同時に生存しながら同じレジスタを要求する、*自己衝突* を起こせます。この区間は *必ず* 分割し、その結果としてコピーを得ます。単純な `fib` プログラムなどの、ループをまたぐ依存関係で起きます。 + +```java + int x=1, y=1; + while( true ) { + tmp = x + y; + y = x; + x = tmp; + }; + +``` + +SoN の SSA 形式では: + +```java + int x0 = 1, y0 = 1; + while( true ) { + x1 = phi(x0,x2); + y1 = phi(y0,x1); + x2 = x1 + y1; + } +``` + +変数 `x0,x1,x2,y0,y1` はすべて `Phi` で結合されるので、同じ生存区間の一部です。しかし `x1` と `y1` は `fib` の異なる反復に由来する別々の値を保持します。SSA 形式にはコピーがありませんが、レジスタ割り当て後の形式は、元のコードと同様にコピーを必要とします。 + +自己衝突は干渉グラフ構築中に見つかり、彩色フェーズを試す前に分割ラウンドを引き起こします。 + +## 彩色のヒューリスティック + +レジスタの彩色も分割もヒューリスティックが多数あり、その質が最終的な割り当て品質を大きく左右します。グラフ彩色は NP 完全であり、効率的な彩色アルゴリズムはありません。いずれにせよ、多くのプログラムは分割しなければ彩色できません。 + +### バイアス付き彩色 + +バイアス付き彩色は、Split を除去できるように「よりよい色を選ぶ」、あるいは「色の選択に偏りを付ける」ヒューリスティックです。Split は1つの生存区間を2つに分けますが、必要のない分割が挿入されることもあります。つまり、すでに過剰な分割が起きています。片側の区間が彩色済みで、もう片側も同じ色にできれば、その分割は除去できます。どちらも未彩色でも、片側が再帰的に彩色済み区間に接続されていれば、分割の連鎖がすべて同じ色になって除去されることを期待して、色に偏りを付けられます。 + +彩色処理が逆順に戻り、区間の色を選ぶとき、多くのレジスタ選択肢があることがよくあります。まず任意に、番号が最小のレジスタを選び、それからよりよい色を探します。バイアス付き彩色は代表的な定義を先に調べ（1つしかなければその唯一定義）、次に代表的な使用を調べます。分割の「反対側」が彩色済みかを確認し、そうであり、その色を使えれば採用します。分割があっても未彩色なら、その反対側で再帰的に繰り返します。2アドレス演算のもう1つの入力や、Phi ノードの入力の1つについても行います。 + +どの場合も、現在利用でき、将来この Split の反対側にも選べるかもしれない有効な色を選ぶのが目標です。それによって両側が同じ色になり、分割を除去できます。 + +### 危険な区間の選択 + +ここでは、大きなクリークを作る複数の *生存区間* から1つを選ばざるを得ません。相互の隣接ノードが多すぎて、どれも色を保証されません。ここには相反する要求があります。 + +「面積」が大きく、つまりプログラムの広い範囲を覆い、スピルの「コスト」が低い、つまり定義と使用が少なく、ループ外にある区間を選べば、大きな効果があります。プログラムの広い範囲でレジスタが空き、ほかの場所で彩色が成功できます。通常の ABI の callee-save レジスタは理想的です。入口で定義し出口でだけ使うため、プログラム全体を覆います。スピルも入口と出口で1回ずつ分割するだけです。このような区間のスピルは、基本的に古典的な関数のプロローグ／エピローグ列を構築します。ただし、この割り当て器は、たとえば高速経路の出口より外側でスピルすることも許されます。 + +``` + // No registers saved if the initial RDI is null + test rdi + jne BIG_AND_SLOW + xor rax,rax + ret // Fast path exit: null argument means null result +BIG_AND_SLOW: + add rsp,#12 + mov [rsp+0],rbx // begin spilling callee-save registers + mov [rsp+4],r12 // + // lots of code needing callee-save registers +``` + +もう一方の要求は、偶然によって彩色できそうな区間を選ぶことです。「ほとんど彩色可能」、たとえば利用可能なレジスタ／色より隣接ノードが1つだけ多い区間なら、偶然やバイアス付き彩色によって隣接ノードのいくつかが同じ色を使い、色が空いて、この危険な区間も結局彩色できるかもしれません。 + +## 分割 + +ここでは彩色に失敗したので、分割が必要です。特定の区間が彩色できず、分割方法を決めなければなりません。ここにも相反する要求があります。分割が多すぎると割り当てが悪くなり、少なすぎると進捗しないバグになり、任意の上限を超えるほど多くの分割ラウンドとして現れます。 + +まずスピルをソートして決定的にします。そうしないと HashMap の巡回順になります。それから各スピル対象の区間を順に調べ、分割戦略を決めます。 + +### 自己衝突の分割 + +自己衝突区間は「干渉グラフ構築」段階で発見します。この場合、自己衝突がある状態での彩色には意味がないので、彩色を試さず直接分割へ進みます。IFG 構築中に、この区間の衝突する定義の部分集合を収集しました。それらの定義位置を巡回し、スピルを挿入します。 + +- Phi のスロット #1 の前（ループ入口の Phi をループ本体から切り離す）と、Phi の後。 +- 2アドレス命令の前。演算の前後で区間を分断します。 +- 生存区間を延長する使用の前。 + +この分割集合はかなり積極的ですが、列挙した各位置で分割を必要とするテストを第20章に含めています。自己衝突がある間は彩色を試すことさえできないため、素早く区間を切り分けることが重要です。過剰分割になりがちなので、割り当て器はバイアス付き彩色と最終コピー整理に頼って余分なものを除去します。保守的な併合は後の章で導入します。 + +### ハード衝突の分割 + +直接の定義／使用の衝突（たとえば `rdi` で定義され、`rax` で使われる）は「生存区間構築」走査で発見します。「干渉グラフ構築」走査でも発見できます。たとえば、`rdi` で入る引数が後で使われるものの、`Call` に破壊される場合です。 + +単一定義と単一使用の単純なハード衝突では、正確な定義と使用を生存区間自身に保持しています。定義の後と使用の前で1回ずつ、レジスタが制限された側にだけ分割を行います。 + +より複雑な場合は、容量不足のスピル／ループ入れ子の手法を使います。複製可能な値は使用の近くで再生成できますが、その複製の出力レジスタクラスが使用を満たせる場合だけです。そうでなければ移動が必要です。固定レジスタの定数に柔軟な使用がある場合も、使用で分割しなければなりません。定義で何もしないと、同じハード衝突を永遠に繰り返します。 + +よく使われる定数（たとえば0）は、異なるレジスタを要求する多くの使用を持ちます。使用をレジスタクラスごとにまとめれば移動を減らせますが、このヒューリスティックは後の章まで延期します。 + +### ループの入れ子に沿った分割 + +ここでは通常、容量不足のスピルが起きています。単にもっとレジスタが必要です。`Call` が一時レジスタをすべて破壊し、値を呼び出しの先へ運ぶ必要があるときに起きやすいですが、大きな関数で多くのことが同時に起きる場合にも発生します。 + +ヒューリスティックは、頻繁に実行されるループ本体がスピルしないよう、利用可能レジスタを残すためにループの *周囲* で分割します。分割ラウンドが進むにつれ、区間をより深い入れ子へ分割します。最後には、最内周ループであっても各定義の後と各使用の前で分割します。 + +まず、すべての定義と使用の最小・最大ループ深さを求めます。それらが異なれば最外周ループの *周囲*、すなわち境界で分割し、外側からの制約を持たない内側の区間はそのまま保持します。それでも彩色できなければ、次のラウンドでは最外周ループが1段内側へ移り、次の内側の入れ子の周囲で分割します。最内周ループ内で分割するまで、この処理を繰り返します。 + +### 補助関数 + +RA は、比較的自己完結した一連の補助関数を使います。 + +- **findAllLRG**: 区間のすべての定義と使用を、O(N) ではなく O(|LRG|) 時間で見つけます。 +- **insertBefore** と **insertAfter**: 使用の前か定義の後に分割を挿入します。基本ブロック内の正しい順序に置く処理と、すべての辺の保守を含みます。 +- **makeSplit**: 分割を作ります。複製可能な定数を複製するか、`Machine` に移植先固有の `SplitNode` を要求します。 +- **ldepth**: `long` に詰めた最小・最大ループ深さを受け取り、指定ノード `n` に対する深さ範囲を拡張します。定義や使用がループ「内」にあるかを判定し、ループ周囲の分割に使います。 + +## 割り当て後 + +彩色成功後、両側が同じレジスタの分割を取り除きます。分割を素早く走査し、レジスタを確認して不要なものを除去します。残ったものは割り当ての「採点」用に追跡します。また、分割の後の分割の一部を迂回し、冗長なコピーを除去できることもあります。 + +レジスタは `RegAlloc` オブジェクトの `alloc.regnum( Node n )` から引き続き利用でき、次の命令エンコーディング走査で使います。 + +## RegAlloc の改良: 正しさと測定された基準値 + +この章は小さな割り当て器から始まります。ハード衝突は実際に断ち切らなければなりません。同じブロックに別のコピーがあるだけで分割を省略したり、衝突を復活させるような除去をしたりしてはいけません。ループの後退辺も、特に Phi が並列代入を表す場合には同じ注意が必要です。出力値のない命令にもレジスタ破壊は適用されます。最後に、冗長なコピーの除去には、間にある定義やレジスタ破壊を探す後ろ向き走査が必要です。これらはスピル品質とは独立した、正しさの規則です。 + +分割前に失敗した区間をソートし、同一性マップの順序の変化が割り当てを決めないようにします。割り当て器には null に安全な分割表示と、任意の関数内辺の診断もあります。テストはレジスタマスク、2アドレスのオペランド、Phi のレジスタ一致を確認します。小さなマシングラフが、最適化器の選択とは独立にハード衝突を検証します。ネイティブ実行は、第21章のエンコーディングとともに導入します。 + +### テスト全体で合計したスピル数 + +`make spill-stats` を実行すると、テストを実行し、各コンパイルの数、CPU/ABI ごとの小計、以下の合計を表示します。アサーションは有効なままで、テストが失敗すればコマンドも失敗します。最適化器の既定シードは123です。 + +第20章のプログラム群は `Chapter20Test` の11のソース例すべてと、`BrainFuckTest.testBrainfuck`、`MergeSortTest.testMergeSort` を、x86-64、RISC-V、ARM の SystemV でコンパイルしたものです。スピル0のケースを含む13プログラム、39コンパイルです。人工的な割り当て器の回帰グラフは正しさの確認であり、追加のプログラムベンチマークではありません。 + +| プログラムテスト群 | 割り当て器の章 | コンパイル数 | 分割による移動 | ループ重み付き移動 | +|---|---:|---:|---:|---:| +| 第20章 | 20 | 39 | 234 | 360 | + +`_spills` はレジスタ間コピーも含む、残存した分割移動を数えます。スタックへのストアだけではありません。`_spillScaled` は各移動を `8^loopDepth` で重み付けします。これは粗いコスト推定で、測定された実行頻度ではありません。重み付き小計は x86-64 が161、RISC-V が100、ARM が99です。 + +### 測定についてのコメント + +正しさの修正前、この群は235移動／354重み付き移動でした。遅延メモリ導入前の修正済み基準値は、両方が3増えました。そのうち2移動は、最終的な x86 ストアマスク制限のバックポートによるものです。整数のバイト／short ストアは XMM レジスタを消費できません。これは正しさのためのコストで、品質の向上ではありません。固定隣接ノードへの色バイアスの修正は、この群の数を変えません。 + +遅延メモリと選択済み読み取りの順序付けにより、同じ39コンパイルは導入前の238／357から、234移動／360重み付き移動になりました。すべての対象でレジスタの合法性が確認でき、割り当て器のヒューリスティックは変更していません。変化したプログラムは次のとおりです。 + +| プログラム | 対象 | 移動の前／後 | 重み付きの前／後 | +|---|---|---:|---:| +| 配列アクセス（`testAlloc2`） | x86-64 | 1 / 2 | 1 / 2 | +| 配列の累積和（`testArray1`） | x86-64 | 5 / 6 | 5 / 13 | +| 文字列ハッシュ | x86-64 | 7 / 5 | 21 / 19 | +| 文字列ハッシュ | RISC-V | 4 / 3 | 4 / 3 | +| 文字列ハッシュ | ARM | 5 / 3 | 5 / 3 | +| マージソート | ARM | 37 / 36 | 37 / 36 | + +累積和の追加のループ移動は、選択済み読み取りを、それを破壊する書き込みより前にスケジュールすることから生じます。その順序を省く診断ビルドでは5／5に戻りますが、有効な代替スケジュールではありません。これはフロントエンドとスケジューリングのグラフの変化であり、割り当て器のヒューリスティックの比較ではありません。新しいメモリ割り当ての回帰テストは合法性を確認しますが、この測定群に項目を追加しません。 + +後の章では、品質向上の手法を1つずつ追加し、このような表で締めくくります。第21章では自身の割り当て器で第20章と第21章のプログラム群を測定し、第25章では第20〜25章の群の行を持ちます。章をまたいで行を比較するときは、プログラム／対象の構成とシードを固定し、最適化器や命令選択の変化を割り当ての変化から分けてください。全体が改善するなら局所的な悪化に価値がある場合もありますが、割り当ての失敗や違法なレジスタ割り当てに価値はありません。 diff --git a/chapter20/README.md b/chapter20/README.md index f3c566e5..b4d4209f 100644 --- a/chapter20/README.md +++ b/chapter20/README.md @@ -1,5 +1,7 @@ # Chapter 20: Graph Coloring Register Allocation +English | [日本語](README.ja.md) + [Previous: Chapter 19](../chapter19/README.md) | [Next: Chapter 21](../chapter21/README.md) diff --git a/chapter20/docs/18-grammar.ja.md b/chapter20/docs/18-grammar.ja.md new file mode 100644 index 00000000..f0b12acb --- /dev/null +++ b/chapter20/docs/18-grammar.ja.md @@ -0,0 +1,138 @@ +# 第20章の文法 + +[English](18-grammar.md) | 日本語 + +この文書は [原文](18-grammar.md) の日本語訳です。 + +> 訳注: 原文の見出しは「Grammar for Chapter 16」です。この日本語版では、配置されている第20章に合わせた見出しにしています。 + +[第20章に戻る](../README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program : block EOF ; + +block : statement+ ; + + +statement + : '{' block '}' + | returnStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatement + | structDeclaration + | expressionStatement + ; + + +returnStatement : 'return' expression ';' ; + +ifStatement : 'if' '(' expression ')' statement ('else' statement)? ; + +whileStatement : 'while' '(' expression ')' statement ; + +breakStatement : 'break' ';' ; + +continueStatement : 'continue' ';' ; + + +structDeclaration : 'struct' IDENTIFIER '{' block '}' ; + +expressionStatement + : type IDENTIFIER ';' + | type IDENTIFIER '=' expression ';' + | IDENTIFIER '=' expression ';' + | expression + ; + +PRIMTYPE + : 'int' + | 'i8' + | 'i16' + | 'i32' + | 'i64' + | 'u8' + | 'u16' + | 'u32' + | 'flt' + | 'f32' + | 'f64' + | 'bool' + ; + +type + : PRIMTYPE + | typeName '?'? + | typeName nestedArray+ + ; + +nestedArray : '?'? '[]'* ; + +typeName : IDENTIFIER ; + + +expression : bitWiseExpression ; + +bitWiseExpression + : comparisonExpression ( '&' | '|' | '^' ) comparisonExpression)* + ; + +comparisonExpression + : shiftExpression (('==' | '!='| '>'| '<'| '>='| '<=') shiftExpression)* + ; + +shiftExpression + : additiveExpression ( '<<' | '>>>' | '>>' ) additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression postAssign + ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | '(' expression ')' + | 'true' + | 'false' + | 'null' + | newExpression + | IDENTIFIER + ; + +newExpression + : 'new' IDENTIFIER [ '{' block '}' ] + | 'new' IDENTIFIER '[' expression ']' + ; + +postAssign : postFix [ '=' expression ] | [ '#' ]; + +postFix + : '.' IDENTIFIER postFix + | '[' expression ']' postFix + ; + + +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; + +INTEGER_LITERAL + : [1-9]DIGIT* + | [0] + ; + +NON_DIGIT: [a-zA-Z_]; +DIGIT: [0-9]; +``` diff --git a/chapter20/docs/18-grammar.md b/chapter20/docs/18-grammar.md index 7da725e9..51539d0b 100644 --- a/chapter20/docs/18-grammar.md +++ b/chapter20/docs/18-grammar.md @@ -1,5 +1,7 @@ # Grammar for Chapter 16 +English | [日本語](18-grammar.ja.md) + ```antlrv4 grammar SimpleLanguage; -- cgit v1.2.3