diff options
Diffstat (limited to 'docs/chapter24/README.ja.md')
| -rw-r--r-- | docs/chapter24/README.ja.md | 262 |
1 files changed, 262 insertions, 0 deletions
diff --git a/docs/chapter24/README.ja.md b/docs/chapter24/README.ja.md new file mode 100644 index 00000000..bf412061 --- /dev/null +++ b/docs/chapter24/README.ja.md @@ -0,0 +1,262 @@ +# 第24章: 関係演算の連鎖と疎な条件付き定数伝播 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第23章](../chapter23/README.ja.md) | +[次の章: 第25章](../chapter25/README.ja.md) + +この章では、たとえば `(60 <= score < 90)` のような条件の *連鎖* を許し、中央の `score` を繰り返さずに済むようにします。 + +コンパイラの主な変更は、手続き間の疎な条件付き定数伝播（SCCP）です。呼び出しグラフの辺も発見する、楽観的な型の求解です。メモリは第11章の遅延分割に従います。BulkMemPhi はメモリ全体を表し、MemPhi は正確なエイリアスをマージし、割り当てはインスタンスフィールドの部分メモリを消費・生成します。SCCP 中、メモリ Phi は到達不能入力を無視し、割り当て結果は制御が到達するまで高いままです。第25章には、不完全な型のための大きな SSA 再設計、非公開のコンストラクタメモリ、分割コンパイルを残します。[バックポートのレビュー待ち一覧](../chapter-backports.md) を参照してください。 + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチ上の直線的な Git リビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter24) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter23...linear-chapter24) することもできます。 + +この章の[完全な言語文法](24-grammar.ja.md)はこちらです。 + +## 関係比較の連鎖 + +関係比較の連鎖により、同じ変数を繰り返さず、連続する比較をすっきりと読みやすく書けます。 + +```java +if (min <= x && x < max) +``` + +は、次になります。 + +```java +if (min <= x < max) +``` + +この構文は場所を節約し、数学で範囲検査を書く方法に似た、直感的な条件にします。たとえば: + +```java +int score = 75; +if (60 <= score < 90) { + sys.io.p("Pass"); +} +``` + +これは `score` を繰り返さず、60以上90未満かを検査します。 + +`<=` と `>=` の両方を使うなど、逆向きの比較を混ぜる式は、Simple の方向規則では許されません。 + +```java +if (a <= b >= c) +``` + +### 演算子の方向規則 + +重ねた比較は、すべての比較演算子が同じ方向を「向く」場合 *だけ* 有効です。 + +- `<` と `<` +- `<` と `<=` +- `>` と `>` +- `>` と `>=` + +等値演算子（`==` と `!=`）は通常どおり、より低い優先順位を持ちます。関係演算の連鎖をつなぐ要素ではありません。 + +1つの連鎖で方向を混ぜることはできません。 + +```java +if (a <= b >= c) // Invalid +``` + +真偽値を使えば、比較を数値の文脈に強制できます。次は有効ですが、珍しい書き方です。 + +```java +return (0 < arg) > 1; +``` + +`(0 < arg)` の結果に応じて、次のいずれかになります。 + +```java +return 0 > 1; +``` + +または + +```java +return 1 > 1; +``` + +等値演算子もこの形式で有効ですが、比較より優先順位が低いため、 + +```java +a < b == c +``` + +は次のように解析されます。 + +```java +(a < b) == c +``` + +これは意図した連鎖比較とは違うかもしれません。より明示的な代替は次です。 + +```java +a < b && b == c +``` + +比較は任意の長さで連鎖でき、同じ方向を向く限り、異なる比較演算子を自由に混ぜられます。中間の各オペランドは1回だけ評価します。後のオペランドは、前の比較が成功した場合だけ評価するため、連鎖内の呼び出しや更新は短絡評価されます。 + +例: + +``` +return 0 < arg < arg+1 < 4; +``` + +### 注意が必要な境界例 + +```java +return 0 != arg != 1; +``` + +これは連鎖した不等比較ではなく、標準の優先順位規則により次のように解析します。 + +```java +return ((0 != arg) != 1); +``` + +```java +return a == b == c; +``` + +同様に、これは次のように解析します。 + +```java +return ((a == b) == c); +``` + +## 疎な条件付き定数伝播 + +[SCCP](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation) は、これまで行ってきたピープホール最適化／定数畳み込みの、上から下へ進む版です。アルゴリズムの規則は文献でよく知られ、大学で一般に教えられています。[スライドの例](https://www.cse.psu.edu/~gxt29/teaching/cse522s23/slides/08monotoneFramework.pdf) があります。 + +- すでに束を持っています。 +- すでに SSA 形式を持っています。したがってアルゴリズムは *疎* です。 +- ノードから型への対応（`Node._type`）を持っています。 +- すでに伝達関数（`Node.compute`）を持っています。 + +すべての `_type` を、⊥ ではなく ⊤ に初期化し、すべてのノードをワークリストに置きます。そこからノードを取り、伝達関数 `node.compute()` を実行します。結果が `node._type` と変われば更新し、その出力側の隣接ノードをワークリストへ入れます。アサーションとデバッグ補助をすべて取り除いた簡略版は次のとおりです。 + +```java +while( (n = code._iter._work.pop()) != null ) { + Type nval = n.compute(); + if( n._type != nval ) { + assert n._type.isa(nval); // Types start high and always fall + n._type = nval; // Update type in Node + code._iter.addAll(n._outputs);// Neighbors might change, need to inspect + } +} +``` + +このアルゴリズムは必ず停止し、一般にはかなり速く、束と伝達関数の制限内での「最良の答え」である *不動点* に必ず到達します。得られる型はピープホール規則で見つけたものより単調に改善されます。その後、型が改善されたノードでピープホール規則を実行し、無関係なピープホール最適化が適用できるかを調べられます。たとえば新しく発見した定数が、計算を ConstantNode に置き換えます。 + +以下は SSA の擬似コードです。`phi` はマージを意味し、Simple の構文ではありません。 + +```text +int x0 = 1; // x0 = 1 +while( rand ) { + x1 = phi(x0,x2); // x1 = BOT = phi(1,BOT) + x2 = 2 - x1; // x2 = BOT = 2 - BOT +} +return x1 +``` + +SCCP がなければ、この小さなプログラムは `x` の計算を畳み込めません。見れば `x` は常に `1` とわかりますが、下から上へ進む悲観的手法は、x1 が BOT なので x2 が BOT、したがって x1 が BOT と判断します。行き詰まりを解くには楽観的手法が必要です。x1 が `1` と *仮定* すれば、x2 も `1` と発見できます。値の畳み込みは、ループ停止を証明したり、その条件と副作用を除去可能にしたりするものではありません。 + +アルゴリズムは左から右へ進み、変化がなくなったら停止します。 + +| 変数 | 初期 | x0=1 | x1=phi(1,T) | x2=2-x1 | x1=phi(1,1) | +|---|----|----|-----------|-------|-----------| +| x0 | T | 1 | 1 | 1 | 1 | +| x1 | T | T | 1 | 1 | 1 | +| x2 | T | T | T | 1 | 1 | + +### 条件付き + +制御フローがデータフローと同じグラフ内にあるため（これが Sea-of-Nodes の大きな要点です）、特別なことをする必要はなく、アルゴリズムはすでに *条件付き* です。ここでも例が役に立ちます。 + +再び SSA の擬似コードを使います。 + +```text +int x0 = 1; // x0 = 1 +while( rand ) { + x1 = phi(x0,x4); // x1 = BOT = phi(1,BOT) + if( x1 == 1 ) // Since x1 is BOT, both true and false arms are taken + x2 = 2 - x1; // x2 = BOT = 2 - BOT + else x3 = 99; // x3 = 99 + x4 = phi(x2,x3); // x4 = BOT = phi(BOT,99) +} +return x1 +``` + +再び左から右へ進みますが、今度はすべての経路が到達可能とは限りません。`if` の結果は Control 値の対で、経路が生きていれば `C`、そうでなければ `X` で示します。これは `x4 = phi(x2,x3)` の計算で使います。`PhiNode` は `if` の対応する制御入力 *も* 確認し、生きた経路だけをマージします。 + +| 変数 | 初期 | x0=1 | x1=phi(1,T) | 1 == 1? | x2=2-x1 | x3=99 | x4=phi(C/1,X/99) | x1=phi(1,1) | +|---|-----|----|-----------|---------|---------|---------|----------------|-----------| +| x0 | T | 1 | 1 | 1 | 1 | 1 | 1 | 1 | +| x1 | T | T | 1 | 1 | 1 | 1 | 1 | 1 | +| if | T | T | T | [C,X] | [C,X] | [C,X] | [C,X] | [C,X] | +| x2 | T | T | T | T | 1 | 1 | 1 | 1 | +| x3 | T | T | T | T | T | 99 | 99 | 99 | +| x4 | T | T | T | T | T | T | 1 | 1 | + +この種の条件付き定数伝播は、条件が真か偽と証明できると、最適化後のプログラムから検査と分岐を除去するので、非常に役立ちます。よくあるのが null 検査です。同じプログラムで、整数の代わりに null ポインタを使います。 + +```java +List head = notNullList(); +while( rand ) { + if( head ) head = new List(head,payload); + else { head = null; default_action(); } +} +``` + +`head` は非 null で始まるため、決して null にならず、`default_action` も起きません。ループは簡略化できます。 + +```java +List head = notNullList(); +while( rand ) { + head = new List(head,payload); +} +``` + +### 手続き間 + +**Simple** では、ここでもほぼ何もせず、SCCP を手続き間で実行します。`CallNode` は `FunNode` を呼び、`ReturnNode` は `CallEndNode` に戻り、まったく通常の方法で型情報を渡します。ただし問題が1つあります。`Call` と `Fun`、および `Return` と `CallEnd` の間に辺がありません。そのような辺が [呼び出しグラフ](https://en.wikipedia.org/wiki/Call_graph) を構成します。 + +通常の SCCP を拡張し、`Call` の関数ポインタ入力が変わり、新しい関数対象を得る時点を監視します。対象の数は有限なので、前の章で説明した *関数インデックス* で正確に表します。分割コンパイルでは、このコンパイル単位の外で呼ばれる無限の未知関数に対して、特別なインデックスを追加します。 + +`Call` で新しい *fidx* を見つけたら、`Call` と `Fun`、`Return` と `CallEnd` を *リンク* します。このリンクは、`Call` から `Fun`、そして `Call` の引数から `Fun` の `ParmNode` へ CFG 辺を追加したかのように動きます。`FunNode` は `RegionNode` を、`ParmNode` は `PhiNode` を拡張するため、同じ意味規則を使います。`Fun` は呼ばれると到達可能になり、`Parm` はすべての呼び出し引数をマージ（*meet*）します。同様に `CallEnd` は、すべての `Return` の *meet* を計算して、呼ばれたすべての関数の結果をマージします。 + +この *リンク* 段階はアルゴリズムの内部ループにいくつかの検査を加え、正確な呼び出しグラフも構築し、SCCP の手続き間実行を可能にします。進行中に新しい辺を少し発見する以外は、中核アルゴリズムは変わりません。不動点解で停止することが保証され、たとえば特定の呼び出しパラメータが、すべての呼び出し経路で定数、あるいは非 null と発見できることがあります。 + +## RegAlloc の改良: 低頻度側のループ分割を先に試す + +ループの Phi と後退辺は、ある命令で値が共存しなければならなくても、同じ生存区間に属する場合があります。この自己衝突は区間の分割を必要とします。第23章は Phi の定義と入力値をすぐに分割しました。この章では先に、高頻度の定義／後退辺をそのままにし、ループ外のコピーを試します。彩色が成功すれば各反復の移動を避けられます。2アドレス演算を含むほかの衝突は、既存の処理を保持します。 + +割り当て器は、どの Phi にこの機会を与えたかを記憶します。同じ Phi が再び自己衝突すると、次は通常の積極的な分割を使います。区間は各ラウンドで再構築するため、記録には Phi の同一性を使います。最初の試行でコピーを挿入しない、後退辺だけの衝突も対象です。その試行も、1回だけ許された遅延を消費しなければなりません。回帰テストは、安い最初の試行と、必須の代替処理の両方を確認します。 + +第21章の隣接コピー転送も引き継ぎます。彩色後、次の命令に唯一の使用がある場合、オペランドマスクが許し、2アドレスの結び付きを壊さなければコピー元レジスタを読めます。以下の表は、この整理と遅延メモリの前方移植を含みます。第22章の群には、以前の監査後に追加した移動0の C 戻り値 ABI 確認2件も含むようになりました（24ではなく26項目）。 + +`make spill-stats` を実行してください。全行は **第24章のコンパイラ**、最適化器のシード123、以前の群の表と同じソース／対象の組み合わせを使います。この Windows 結果は、x86 SystemV/Win64 と RISC-V/ARM SystemV を合わせ、遅延メモリの前方移植後に再測定したものです。 + +| プログラム群 | コンパイル数 | 残存する移動 | ループ重み付き移動 | +|---|---:|---:|---:| +| 第20章 | 39 | 320 | 439 | +| 第21章 | 52 | 420 | 952 | +| 第22章 | 26 | 67 | 67 | +| 第23章 | 30 | 78 | 225 | +| 第24章 | 67 | 422 | 1,325 | +| **合計** | **214** | **1,307** | **3,008** | + +`_spills` はレジスタ移動を含む残存 SplitNode を数えます。`_spillScaled` は `8^loopDepth` で重み付けするコスト推定で、測定されたメモリアクセスではありません。診断マシングラフはこの表の割り当てに寄与しません。報告器は、スピル期待値が異なっても、割り当ての合法性とネイティブ／エミュレーション結果を確認し、いずれの失敗でも失敗終了します。 + +後のコンパイラ修正より前の、元の2026-09-20割り当て器監査では、表の合計は1,332／2,956でした。低頻度側を先にする規則だけを無効にすると、同じコンパイラとプログラムは **1,338移動／2,962重み付き移動** でした。この規則は各6を減らします。RISC-V MergeSort の1ケースは1移動増えますが、ほかの MergeSort、Sieve、ARM ループの1ケースの改善が相殺します。集計測定はこの局所的な悪化を受け入れる根拠となります。ここでの改善は小さく、普遍的ではありません。 + +その監査で第20〜23章の群だけを見ると、第23章は933／1,745、第24章は900／1,614でした。それぞれの削減のうち、この割り当て器変更によるものは6だけです。残りは SCCP を含むほかのコンパイラ変更です。章だけの比較では、ヒューリスティックの効果を過大に見積もってしまいます。 + +以前の群は64ビット Person、ガード付き String、短いエミュレータ引数リストを保持します。改訂した Jig、BubbleSort、Newton、スタック引数入力は、既存のテストとともに第24章の群に属します。固定した String 処理対象は、インライン化の支配ノード走査で null 検査が欠けていたことも明らかにしました。その正しさの修正はヒューリスティック比較の両側に含めています。面積／コストのスピル順位付けは第25章に残します。 + +現在の関数ポインタ規則は、アドレスが直接呼び出し対象としてだけでなく、値として使われるたびに、未知の呼び出し側を保持します。これにより脱出解析なしで呼び出し可能な本体を保存しますが、Phi で選ばれた関数は一般的なパラメータ型を保持します。return のない String ケースは、今では未使用のハッシュ本体を除去し、分割を必要としません。ソース／対象の構成は変わりません。これらのグラフ変更は、上の低頻度側優先の割り当て器比較とは別です。 |