ch4 extend DCE

3 files changed, 265 insertions, 4 deletions

diff --git a/chapter04/README.md b/chapter04/README.md
index 8f44cdf5..e96457c8 100644
--- a/chapter04/README.md
+++ b/chapter04/README.md
@@ -353,12 +353,14 @@ The peephole method does following:
 `peephole()` calls `deadCodeElim()` which is shown below.
 
 ## Dead Code Elimination(DCE)
-Dead Code Elimination 
+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 idealize call).
 
-Both of the methods mentioned above delete the nodes recursively.
+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).
@@ -392,9 +394,93 @@ Both of the methods mentioned above delete the nodes recursively.
   _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 we add it to the `scope`'s inputs as
-  as the scope to the outputs of `a`.
+  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 output.
+```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 also get rid of `ConstantNode`(`this`) from the outputs of `Start`:
+``` 
+old_def.delUse(this) 
+```
+
+*A constant node pointing to "Start"(ignored by the graph visualizer) but still maintains a connection:*
+
+![Graph3](docs/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](docs/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 new deadCodeElim(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.
diff --git a/chapter04/docs/04-dce2.svg b/chapter04/docs/04-dce2.svg
new file mode 100644
index 00000000..e3719bcc
--- /dev/null
+++ b/chapter04/docs/04-dce2.svg
@@ -0,0 +1,59 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 2.40.1 (20161225.0304)
+ -->
+<!-- Title: chapter04 Pages: 1 -->
+<svg width="114pt" height="250pt" viewBox="0.00 0.00 114.00 250.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 246)">
+<title>chapter04</title>
+<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-246 110,-246 110,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="#000000" points="8,-8 8,-234 98,-234 98,-8 8,-8"/>
+</g>
+<!-- Start2 -->
+<g id="node1" class="node">
+<title>Start2</title>
+<polygon fill="#ffff00" stroke="transparent" points="33,-196 33,-222 74,-222 74,-196 33,-196"/>
+<polygon fill="none" stroke="#000000" points="33,-196 33,-222 74,-222 74,-196 33,-196"/>
+<text text-anchor="start" x="40.2805" y="-204.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text>
+<polygon fill="none" stroke="#000000" points="33,-164 33,-196 74,-196 74,-164 33,-164"/>
+<polygon fill="#ffff00" stroke="transparent" points="38,-169 38,-191 69,-191 69,-169 38,-169"/>
+<polygon fill="none" stroke="#000000" points="38,-169 38,-191 69,-191 69,-169 38,-169"/>
+<text text-anchor="start" x="40.6718" y="-175.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text>
+</g>
+<!-- Con_6 -->
+<g id="node2" class="node">
+<title>Con_6</title>
+<ellipse fill="none" stroke="#000000" cx="43" cy="-106" rx="27" ry="18"/>
+<text text-anchor="middle" x="43" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text>
+</g>
+<!-- Con_6&#45;&gt;Start2 -->
+<g id="edge1" class="edge">
+<title>Con_6-&gt;Start2</title>
+<path fill="none" stroke="#ff0000" d="M45.072,-124.0265C45.9366,-131.5481 46.9815,-140.6387 48.0249,-149.7167"/>
+<polygon fill="#ff0000" stroke="#ff0000" points="44.5736,-150.3415 49.1927,-159.8764 51.5278,-149.5421 44.5736,-150.3415"/>
+<text text-anchor="middle" x="42.8484" y="-126.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Return7 -->
+<g id="node3" class="node">
+<title>Return7</title>
+<polygon fill="#ffff00" stroke="#000000" points="80.1025,-52 25.8975,-52 25.8975,-16 80.1025,-16 80.1025,-52"/>
+<text text-anchor="middle" x="53" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text>
+</g>
+<!-- Return7&#45;&gt;Start2 -->
+<g id="edge2" class="edge">
+<title>Return7-&gt;Start2:p0</title>
+<path fill="none" stroke="#ff0000" d="M64.3196,-52.2322C69.9396,-62.3585 76.1294,-75.4211 79,-88 82.5597,-103.599 83.0135,-108.5115 79,-124 74.2474,-142.3411 60.2215,-145.475 55.5405,-159.004"/>
+<polygon fill="#ff0000" stroke="#ff0000" points="52.0641,-158.5835 54,-169 58.9824,-159.6498 52.0641,-158.5835"/>
+<text text-anchor="middle" x="62.096" y="-54.6322" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Return7&#45;&gt;Con_6 -->
+<g id="edge3" class="edge">
+<title>Return7-&gt;Con_6</title>
+<path fill="none" stroke="#000000" d="M50.4766,-52.1686C49.4071,-59.869 48.1353,-69.0257 46.9468,-77.5834"/>
+<polygon fill="#000000" stroke="#000000" points="43.4664,-77.2003 45.5574,-87.5867 50.3999,-78.1633 43.4664,-77.2003"/>
+<text text-anchor="middle" x="48.253" y="-54.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text>
+</g>
+</g>
+</svg>
\ No newline at end of file
diff --git a/chapter04/docs/04-dce3.svg b/chapter04/docs/04-dce3.svg
new file mode 100644
index 00000000..86fa6f0d
--- /dev/null
+++ b/chapter04/docs/04-dce3.svg
@@ -0,0 +1,116 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 2.40.1 (20161225.0304)
+ -->
+<!-- Title: chapter04 Pages: 1 -->
+<svg width="458pt" height="178pt" viewBox="0.00 0.00 458.00 178.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 174)">
+<title>chapter04</title>
+<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-174 454,-174 454,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="#000000" points="8,-8 8,-162 442,-162 442,-8 8,-8"/>
+</g>
+<!-- Start2 -->
+<g id="node1" class="node">
+<title>Start2</title>
+<polygon fill="#ffff00" stroke="transparent" points="25,-124 25,-150 66,-150 66,-124 25,-124"/>
+<polygon fill="none" stroke="#000000" points="25,-124 25,-150 66,-150 66,-124 25,-124"/>
+<text text-anchor="start" x="32.2805" y="-132.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text>
+<polygon fill="none" stroke="#000000" points="25,-92 25,-124 66,-124 66,-92 25,-92"/>
+<polygon fill="#ffff00" stroke="transparent" points="30,-97 30,-119 61,-119 61,-97 30,-97"/>
+<polygon fill="none" stroke="#000000" points="30,-97 30,-119 61,-119 61,-97 30,-97"/>
+<text text-anchor="start" x="32.6718" y="-103.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text>
+</g>
+<!-- Con_5 -->
+<g id="node2" class="node">
+<title>Con_5</title>
+<ellipse fill="none" stroke="#000000" cx="335" cy="-121" rx="27" ry="18"/>
+<text text-anchor="middle" x="335" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">2</text>
+</g>
+<!-- Con_6 -->
+<g id="node3" class="node">
+<title>Con_6</title>
+<ellipse fill="none" stroke="#000000" cx="407" cy="-121" rx="27" ry="18"/>
+<text text-anchor="middle" x="407" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text>
+</g>
+<!-- Add7 -->
+<g id="node4" class="node">
+<title>Add7</title>
+<ellipse fill="none" stroke="#000000" cx="371" cy="-34" rx="27" ry="18"/>
+<text text-anchor="middle" x="371" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text>
+</g>
+<!-- Add7&#45;&gt;Con_5 -->
+<g id="edge1" class="edge">
+<title>Add7-&gt;Con_5</title>
+<path fill="none" stroke="#000000" d="M363.7149,-51.6057C358.6889,-63.7518 351.9107,-80.1326 346.2018,-93.9289"/>
+<polygon fill="#000000" stroke="#000000" points="342.8638,-92.842 342.2743,-103.4204 349.3319,-95.5185 342.8638,-92.842"/>
+<text text-anchor="middle" x="361.4913" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text>
+</g>
+<!-- Add7&#45;&gt;Con_6 -->
+<g id="edge2" class="edge">
+<title>Add7-&gt;Con_6</title>
+<path fill="none" stroke="#000000" d="M378.2851,-51.6057C383.3111,-63.7518 390.0893,-80.1326 395.7982,-93.9289"/>
+<polygon fill="#000000" stroke="#000000" points="392.6681,-95.5185 399.7257,-103.4204 399.1362,-92.842 392.6681,-95.5185"/>
+<text text-anchor="middle" x="376.0615" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text>
+</g>
+<!-- Con_8 -->
+<g id="node5" class="node">
+<title>Con_8</title>
+<ellipse fill="none" stroke="#000000" cx="191" cy="-121" rx="27" ry="18"/>
+<text text-anchor="middle" x="191" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">3</text>
+</g>
+<!-- Con_9 -->
+<g id="node6" class="node">
+<title>Con_9</title>
+<ellipse fill="none" stroke="#000000" cx="263" cy="-121" rx="27" ry="18"/>
+<text text-anchor="middle" x="263" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">3</text>
+</g>
+<!-- Add10 -->
+<g id="node7" class="node">
+<title>Add10</title>
+<ellipse fill="none" stroke="#000000" cx="227" cy="-34" rx="27" ry="18"/>
+<text text-anchor="middle" x="227" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text>
+</g>
+<!-- Add10&#45;&gt;Con_8 -->
+<g id="edge3" class="edge">
+<title>Add10-&gt;Con_8</title>
+<path fill="none" stroke="#000000" d="M219.7149,-51.6057C214.6889,-63.7518 207.9107,-80.1326 202.2018,-93.9289"/>
+<polygon fill="#000000" stroke="#000000" points="198.8638,-92.842 198.2743,-103.4204 205.3319,-95.5185 198.8638,-92.842"/>
+<text text-anchor="middle" x="217.4913" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text>
+</g>
+<!-- Add10&#45;&gt;Con_9 -->
+<g id="edge4" class="edge">
+<title>Add10-&gt;Con_9</title>
+<path fill="none" stroke="#000000" d="M234.2851,-51.6057C239.3111,-63.7518 246.0893,-80.1326 251.7982,-93.9289"/>
+<polygon fill="#000000" stroke="#000000" points="248.6681,-95.5185 255.7257,-103.4204 255.1362,-92.842 248.6681,-95.5185"/>
+<text text-anchor="middle" x="232.0615" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text>
+</g>
+<!-- Con_11 -->
+<g id="node8" class="node">
+<title>Con_11</title>
+<ellipse fill="none" stroke="#000000" cx="119" cy="-121" rx="27" ry="18"/>
+<text text-anchor="middle" x="119" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">6</text>
+</g>
+<!-- Return12 -->
+<g id="node9" class="node">
+<title>Return12</title>
+<polygon fill="#ffff00" stroke="#000000" points="109.1025,-52 54.8975,-52 54.8975,-16 109.1025,-16 109.1025,-52"/>
+<text text-anchor="middle" x="82" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text>
+</g>
+<!-- Return12&#45;&gt;Start2 -->
+<g id="edge5" class="edge">
+<title>Return12-&gt;Start2:p0</title>
+<path fill="none" stroke="#ff0000" d="M65.0542,-52.052C57.6135,-61.4899 49.9318,-73.7894 47.1181,-86.8747"/>
+<polygon fill="#ff0000" stroke="#ff0000" points="43.6189,-86.6762 46,-97 50.5766,-87.4446 43.6189,-86.6762"/>
+<text text-anchor="middle" x="62.8306" y="-54.452" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Return12&#45;&gt;Con_11 -->
+<g id="edge6" class="edge">
+<title>Return12-&gt;Con_11</title>
+<path fill="none" stroke="#000000" d="M89.6664,-52.0265C94.8444,-64.2017 101.7707,-80.4878 107.5926,-94.1772"/>
+<polygon fill="#000000" stroke="#000000" points="104.4613,-95.7577 111.5959,-103.5903 110.903,-93.0181 104.4613,-95.7577"/>
+<text text-anchor="middle" x="87.4428" y="-54.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text>
+</g>
+</g>
+</svg>
\ No newline at end of file