From f4d0e1583b9ae0237422640d8ee7eea5ce8aad6f Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 3 Dec 2023 23:23:04 +0000 Subject: Chapter 7: While Statement MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Thalia Archibald Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Claude Opus 5 Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki --- docs/chapter07/README.ja.md | 229 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 229 insertions(+) create mode 100644 docs/chapter07/README.ja.md (limited to 'docs/chapter07/README.ja.md') diff --git a/docs/chapter07/README.ja.md b/docs/chapter07/README.ja.md new file mode 100644 index 00000000..67d59c1b --- /dev/null +++ b/docs/chapter07/README.ja.md @@ -0,0 +1,229 @@ +# 第7章: While 文 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第6章](../chapter06/README.ja.md) | +[次の章: 第8章](../chapter08/README.ja.md) + +# 目次 + +1. [バックエッジの扱い](#バックエッジの扱い) +2. [新しいノード型](#新しいノード型) +3. [詳細な手順](#詳細な手順) +4. [可視化](#可視化) +5. [入れ子のループ](#入れ子のループ) +6. [If を内包するループ](#if-を内包するループ) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git のリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter07) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter06...linear-chapter07) することもできます。 + +この章では `while` 文を導入します。 + +この章の [完全な言語文法](07-grammar.ja.md) はこちらです。 + +## バックエッジの扱い + +ループ構造によって生じる難しさは、反復時に変数がループ本体へ戻ってくることです。たとえば、次のコードです。 + +```java +while(arg < 10) { + arg = arg + 1; +} +return arg; +``` + +変数 `arg` にはループ本体内で新しい値が代入され、その値がループ本体へ戻ります。 + +一般に、ループ構造を次のように書き換えます。 + +```java +loop_head: +if( !(arg < 10) ) + goto loop_exit; +arg = arg + 1; +goto loop_head; + +loop_exit: +``` + +これは説明のためのもので、この言語にはラベルや `goto` 文はありません。 + +SSA[^1] の観点では、`arg` が戻ってくるため、先頭に `phi` ノードが必要です。概念的には、次のような結果にしたいのです。 + +```java +// arg1 represents incoming arg +// +loop_head: +arg2 = phi(arg1, arg3); +if( !(arg2 < 10) ) + goto loop_exit; +arg3 = arg2 + 1; +goto loop_head; + +loop_exit: +``` + +`arg2` の phi が `arg3` を参照することに注目してください。`while` ループの条件を解析する時点では、`arg3` はまだわかりません。常に SSA 形式である Sea of Nodes グラフを正しく構築するために解決すべき問題の核心は、ここにあります。 + +[第5章](../chapter05/README.ja.md) を思い出してください。`if` 文の解析では、`if` の条件を過ぎるときにシンボルテーブルを複製します。後で2組のシンボルテーブルを `Region` でマージし、`if` 文の2つの分岐内で定義が変わったすべての名前に phi を作ります。`if` 文の場合、マージする定義がすでにわかっているマージ地点で phi を作ります。 + +ループ構造に対する基本的な考えは、ループ本体内でどの名前が再定義されるかわからないため、ループの `if` 条件に入る *前に*、シンボルテーブル内のすべての名前に対して積極的に phi を作ることです。ループが終わると、さかのぼって不要な phi を削除します。これを「eager phi（先行生成する phi）」方式と呼びます。[^2] + +[第8章](../chapter08/README.ja.md) では、名前の再定義に遭遇したときだけ phi を作る「lazy phi（遅延生成する phi）」方式を実装します。 + +## 新しいノード型 + +ノードの一覧は [第5章](../chapter05/README.ja.md) と同じですが、必要な追加ロジックの一部をより適切にカプセル化するため、`Region` のサブタイプ `Loop` を作ります。Loop と Phi のピープホール最適化では、バックエッジが必要な書き換えを、ループ本体の解析が完了するまで延期します。ほかのノードは通常どおり最適化を続けます。 + +## 詳細な手順 + +1. まず、`Region` の新しいサブクラス `Loop` を作ります。`Loop` は2つの制御入力を取ります。最初は入口、すなわち `$ctrl` の現在の束縛です。2つ目（`null`）は、ループ解析後に設定するバックエッジのためのプレースホルダーです。バックエッジの欠如は、Loop と対応する Phi が未完成であることを示します。そのため、それらのピープホール最適化は、各書き換えに必要な入力がそろうまで待ちます。 + + ```java + ctrl(new LoopNode(ctrl(),null).peephole()); + ``` + + 新しく作った Region が現在の制御になります。 + +2. 現在の Scope ノードを複製します。スコープ内のすべての階層のシンボルを複製し、`$ctrl` の束縛を除くすべてのシンボルに phi を作ります。 + + ```java + // Make a new Scope for the body. + _scope = _scope.dup(true); + ``` + + `dup` の呼び出しに引数 `true` を渡すことに注目してください。これが phi の作成を引き起こします。`dup()` メソッドで phi を作るコードを次に示します。 + + ```java + // boolean loop=true if this is a loop region + + String[] names = reverseNames(); // Get the variable names + dup.add_def(ctrl()); // Control input is just copied + for( int i=1; ikeep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + ifNode.unkeep(); + Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + ``` + +4. 現在のスコープをもう一度複製します。これはループ終了後に生き続ける出口スコープなので、出口スコープの `$ctrl` を `False` 射影に設定します。出口スコープは、ループの条件式の副作用も取り込みます。 + + ```java + // The exit scope, accounting for any side effects in the predicate + var exit = _scope.dup(); + exit.ctrl(ifF); + ``` + +5. 制御を `True` 射影に設定し、ループ本体を解析します。 + + ```java + // Parse the true side, which corresponds to loop body + ctrl(ifT); // set ctrl token to ifTrue projection + parseStatement(); // Parse loop body + ``` + +6. ループ本体の解析後、先ほど作ったすべての phi に戻って処理します。 + + ```java + // The true branch loops back, so whatever is current control gets + // added to head loop as input + head.endLoop(_scope, exit); + ``` + + `endLoop` メソッドは、ループ Region の2つ目の制御をバックエッジの制御に設定します。続いてすべての phi をたどり、それぞれの2つ目のデータ入力をループ本体の対応する項目に設定します。使われなかった phi はピープホール最適化され、元の入力に置き換わります。 + + ```java + Node ctrl = ctrl(); + ctrl.set_def(2,back.ctrl()); + for( int i=1; i