Chapter 4: External Argument and Comparisons

Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: Hels15 <helsgithub15@gmail.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 <noreply@anthropic.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>

2 files changed, 353 insertions, 0 deletions

diff --git a/docs/chapter04/appendix/dce.ja.md b/docs/chapter04/appendix/dce.ja.md
new file mode 100644
index 00000000..ab22b00e
--- /dev/null
+++ b/docs/chapter04/appendix/dce.ja.md
@@ -0,0 +1,185 @@
+# 付録
+
+[English](dce.md) | 日本語
+
+この文書は [原文](dce.md) の日本語訳です。
+
+## デッドコード除去（DCE）
+
+デッドコード除去は、死んだ（使われていない）ノードを取り除く処理です。
+
+この章には、2種類のデッドコード除去があります。
+
+* スコープをポップするときに、使われていないノードを削除する。
+* よりよい置き換えを見つけた後（`idealize()` の呼び出し後）に、古いノードを削除する。
+
+どちらの方法もノードを再帰的に削除します。ただし、最初のケースは `peephole` を呼ぶかどうかにかかわらず発生します。
+
+### スコープをポップするときに使われていないノードを削除する
+
+出力（利用側）のないノードは、使われていません。
+
+### 例1
+
+  ``` 
+  int a = 12; // the only output it has is the scope itself
+  return 1;
+  ```
+
+`a` が使われていないことは明らかです。これから得られる、DCE なしのグラフは次のとおりです。
+
+![グラフ2](../04-dce1.svg)
+
+`a` を削除するため、スコープのポップ時に次の方法を導入します。
+
+  ```java
+  var ret = (ReturnNode) parseBlock();
+  _scope.pop();
+  ```
+
+現時点ではプログラムの終わりは return に固定されており、解析を終えたらスコープをポップします。ポップ前のスコープの状態は次のとおりです。
+
+  ```
+  _scope = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]"
+  1 = {ProjNode@1528} "arg"
+  2 = {ConstantNode@1529} "12"
+  _inputs = {ArrayList@1523}  size = 3
+  ```
+
+`a` の出力:
+
+  ```
+  _outputs = {ArrayList@1544}  size = 1
+  0 = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]"
+  ```
+
+`a` の唯一の出力はスコープ自身であることに注目してください。`a` を導入するとき、スコープの入力に追加するとともに、スコープを `a` の出力に追加します（使用・定義の連鎖を思い出してください）。
+
+`a` は戻り値ではないため、使われておらず、削除できます。
+
+`_scope.pop`:
+
+```java
+public void pop() { popN(_scopes.pop().size());  }
+```
+
+`_scope.popN`（使われていないノードを *再帰的に* 削除する処理）:
+
+```java 
+void popN(int n) {
+    for (int i = 0; i < n; i++) {
+        Node old_def = _inputs.removeLast(); // start from the back
+        if (old_def != null &&        // If it exists and
+            old_def.delUse(this)) {   // If we removed the last use, the old def is now dead
+            old_def.kill();           // Kill the old def
+        }
+    }
+}
+```
+
+まず、スコープの入力をループでたどります（スコープもほかと同じノードであり、スコープのシンボルが入力であることを *思い出してください*）。`removeLast` が返すノードが null でなく、`old_def` の唯一の利用側が現在のノードなら、削除できます。
+
+`old_def.delUse(this)` は、`old_def` の出力から *this* を削除します。
+
+```java
+protected boolean delUse( Node use ) {
+  Utils.del(_outputs, Utils.find(_outputs, use));
+  return _outputs.isEmpty();
+                                     }
+```
+
+`use` の削除後に `_outputs` が空になれば true を返します。`old_def.kill()` は再帰的な削除処理を開始します。
+
+`old_def.kill()`:
+
+```java 
+public void kill( ) {
+      assert isUnused();      // Has no uses, so it is dead
+      popN(nIns());           // Set all inputs to null, recursively killing unused Nodes
+      _type=null;             // Flag as dead
+      assert isDead();        // Really dead now
+    }
+```
+
+再び `popN` を呼びます。目的は、`a` を解放した結果、同様に削除できるノードを探すことです。`a` の唯一の入力は、値12の定数ノードです。ほかのノードと同様に、`ConstantNode` も最初の入力として制御ノード（`Start`）を取ります。`ConstantNode` の入力から `Start` ノードを取り除いたら、
+
+``` 
+Node old_def = _inputs.removeLast();
+```
+
+`Start` の出力から `ConstantNode`（`this`）も取り除けます。
+
+``` 
+old_def.delUse(this) 
+```
+
+### 例2
+
+```
+int a = 12; 
+int b = a + 1; 
+return 1; 
+```
+
+* 現在のスコープで `popN` を呼びます。
+* `b = a + 1;` に利用側がないとわかるので、削除できます。
+* kill 関数では再び `popN` を呼べますが、今回は `b = a + 1;` の入力を対象にします（再帰的な削除を始めます）。
+* 末尾から削除処理を始め、まず「1」を調べます。これには `AddNode` 以外の出力がありません。`this = AddNode` なので、`delUse` を呼ぶと「1」が死んだ状態になります。
+* 「1」を削除し、1つの入力（制御ノード）に対して `popN` を呼べます。
+* 次に「a」を調べます。この時点ではスコープと `AddNode` の2つの利用側があります。`this = AddNode` なので、出力から `AddNode` を取り除きますが、まだスコープが利用側として残るため、ここでは削除できません。
+* `a = 12` に進みます。「a」の利用側は1つ（スコープ）だけで、`this = scope` なので、容易に削除できます。
+* 前と同じように「a」の入力をたどり、制御ノードの出力からそれらを削除します。
+
+![グラフ3](../04-dce2.svg)
+
+## よりよい置き換えを見つけた後に古いノードを削除する
+
+次のコードを考えます。
+
+```
+return (2+1)+3; 
+```
+
+`idealize` の呼び出し後に DCE を行わなければ、次のようになります。
+
+![グラフ3](../04-dce3.svg)
+
+式 (2 + 1) + 3 に対して、より最適な置き換え値（6）を見つけた後、その値を保持する定数ノードを作りました。しかし、元の式を取り除かなかったため、構造内に不要なノードが残っています。
+
+これを直すため、使われていないノードを削除する `deadCodeElim` の呼び出しを追加します。
+
+```java
+public final Node peephole( ) {
+    ...
+    if (!(this instanceof ConstantNode) && type.isConstant())
+        return deadCodeElim(new ConstantNode(type).peephole());
+
+    ...
+  
+    Node n = idealize();
+    if( n != null )         // Something changed
+        // Recursively optimize
+        return deadCodeElim(n.peephole());
+   
+   ...
+}
+``` 
+
+```java
+// m is the new Node, self is the old.
+// Return 'm', which may have zero uses but is alive nonetheless.
+// If self has zero uses (and is not 'm'), {@link #kill} self.
+private Node deadCodeElim(Node m) {
+    // If self is going dead and not being returned here (Nodes returned
+    // from peephole commonly have no uses (yet)), then kill self.
+    if( m != this && isUnused() ) {
+        // Killing self - and since self recursively kills self's inputs we
+        // might end up killing 'm', which we are returning as a live Node.
+        // So we add a bogus extra null output edge to stop kill().
+        m.addUse(null); // Add bogus null use to keep m alive
+        kill();            // Kill self because replacing with 'm'
+        m.delUse(null);    // Remove bogus null.
+    }
+    return m;
+}
+```
diff --git a/docs/chapter04/appendix/dce.md b/docs/chapter04/appendix/dce.md
new file mode 100644
index 00000000..2f55e792
--- /dev/null
+++ b/docs/chapter04/appendix/dce.md
@@ -0,0 +1,168 @@
+# Appendix
+
+English | [日本語](dce.ja.md)
+## Dead Code Elimination(DCE)
+Dead Code Elimination is the process or removing nodes that are dead(unused).
+
+There are two kinds of dead code eliminations present in this chapter.
+- Delete unused nodes when popping the scope.
+- Delete old nodes after finding a better replacement (after calling `idealize()`).
+
+Both of the methods mentioned above delete the nodes recursively.  However, the
+first case happens regardless of whether `peephole` is called or not.
+
+### Delete unused nodes when popping the scope
+
+A node is unused if it has no outputs(users).
+
+### Example 1:
+  ``` 
+  int a = 12; // the only output it has is the scope itself
+  return 1;
+  ```
+We clearly see `a` is unused.
+This gives us the following graph(without DCE):
+
+![Graph2](../04-dce1.svg)
+
+To remove `a` we introduce the following technique when popping the scope.
+
+  ```java
+  var ret = (ReturnNode) parseBlock();
+  _scope.pop();
+  ```
+As of now the end of the program is hard-wired to return, after finishing parsing we pop the scope.
+The state of the scope before popping it:
+  ```
+  _scope = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]"
+  1 = {ProjNode@1528} "arg"
+  2 = {ConstantNode@1529} "12"
+  _inputs = {ArrayList@1523}  size = 3
+  ```
+The output(s) of `a`
+  ```
+  _outputs = {ArrayList@1544}  size = 1
+  0 = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]"
+  ```
+Notice how the only output of `a`is the scope itself. When `a` is introduced, it is added to the
+inputs of the scope, and the scope is added to the outputs of `a`(recall use-def chains).
+
+Since `a` is not being returned - it is unused and can be killed.
+
+`_scope.pop`:
+```java
+public void pop() { popN(_scopes.pop().size());  }
+```
+`_scope.popN`(responsible for killing the unused nodes *recursively*):
+```java 
+void popN(int n) {
+    for (int i = 0; i < n; i++) {
+        Node old_def = _inputs.removeLast(); // start from the back
+        if (old_def != null &&        // If it exists and
+            old_def.delUse(this)) {   // If we removed the last use, the old def is now dead
+            old_def.kill();           // Kill the old def
+        }
+    }
+}
+```
+First, we start off by looping through the inputs of the scope(*remember*: scope is just a node like any other, the symbols of the scope are the inputs).
+If the node returned by `removeLast` is not null, and if the only user of `old_def` is the current Node then we can delete it.
+
+`old_def.delUse(this)` - delete *this* from `old_def`'s outputs.
+```java
+protected boolean delUse( Node use ) {
+  Utils.del(_outputs, Utils.find(_outputs, use));
+  return _outputs.isEmpty();
+                                     }
+```
+Returns true if `_outputs` becomes empty after deleting `use`.
+`old_def.kill()` starts the killing process recursively.
+
+`old_def.kill()`
+```java 
+public void kill( ) {
+      assert isUnused();      // Has no uses, so it is dead
+      popN(nIns());           // Set all inputs to null, recursively killing unused Nodes
+      _type=null;             // Flag as dead
+      assert isDead();        // Really dead now
+    }
+```
+`popN` is called again, our goal is to look for nodes that might also get deleted once `a` is freed.
+The only input `a` has is the constant node with value 12. As every other node a `ConstantNode` takes in the control node first(`Start`), once we
+drop the `Start` node from the inputs of `ConstantNode`:
+``` 
+Node old_def = _inputs.removeLast();
+```
+we can also get rid of `ConstantNode`(`this`) from the outputs of `Start`:
+``` 
+old_def.delUse(this) 
+```
+### Example 2:
+```
+int a = 12; 
+int b = a + 1; 
+return 1; 
+```
+- Call `popN` on current scope.
+- Realize that `b = a + 1;` has no uses - so we can kill it.
+- In the kill function we can call `popN` but this time with the inputs of `b = a + 1;`(start killing them recursively)
+- We start the killing process from the back and examine "1" first. This has no output other than the `AddNode`. Since `this = AddNode` calling `delUse` will mark "1" as dead.
+- We now can kill "1" and call the `popN` function with one input(the control node).
+- Now we examine "a" which has 2 uses at this point, the scope and `AddNode`. Since `this = AddNode` we will remove `AddNode` from its outputs, it will still have the scope as a user - so we can't delete it just yet.
+- We move onto`a = 12`, since "a" has only one user left(the scope) and `this = scope` it can get killed easily.
+- Same as before, we go through the inputs of "a" and will delete them from the outputs of the control node.
+
+![Graph3](../04-dce2.svg)
+
+## Delete old nodes after finding a better replacement
+
+Consider the following code:
+```
+return (2+1)+3; 
+```
+Without DCE after the `idealize` call we would end up with:
+![Graph3](../04-dce3.svg)
+
+After identifying a more optimal replacement value (6) for the expression (2 + 1) + 3,
+we created a constant node to store this value.
+However, we did not remove the original expression,
+resulting in dangling nodes in our structure.
+
+To fix this, we introduce an extra `deadCodeElim` call that is responsible for deleting unused nodes.
+
+
+```java
+public final Node peephole( ) {
+    ...
+    if (!(this instanceof ConstantNode) && type.isConstant())
+        return deadCodeElim(new ConstantNode(type).peephole());
+
+    ...
+  
+    Node n = idealize();
+    if( n != null )         // Something changed
+        // Recursively optimize
+        return deadCodeElim(n.peephole());
+   
+   ...
+}
+``` 
+
+```java
+// m is the new Node, self is the old.
+// Return 'm', which may have zero uses but is alive nonetheless.
+// If self has zero uses (and is not 'm'), {@link #kill} self.
+private Node deadCodeElim(Node m) {
+    // If self is going dead and not being returned here (Nodes returned
+    // from peephole commonly have no uses (yet)), then kill self.
+    if( m != this && isUnused() ) {
+        // Killing self - and since self recursively kills self's inputs we
+        // might end up killing 'm', which we are returning as a live Node.
+        // So we add a bogus extra null output edge to stop kill().
+        m.addUse(null); // Add bogus null use to keep m alive
+        kill();            // Kill self because replacing with 'm'
+        m.delUse(null);    // Remove bogus null.
+    }
+    return m;
+}
+```
\ No newline at end of file