extend chapter 2 peephole section (#118)

* extend peephole section

* fix bad indentatitons

* Update README.md

4 files changed, 351 insertions, 1 deletions

diff --git a/chapter02/README.md b/chapter02/README.md
index 4bc72523..14eef8b2 100644
--- a/chapter02/README.md
+++ b/chapter02/README.md
@@ -127,7 +127,6 @@ starting in [Chapter 4](../chapter04/README.md) and [Chapter
 There are other important properties of the Lattice that we discuss in [Chapter
 4](../chapter04/README.md) and [Chapter 10](../chapter10/README.md), such as the "meet" and "join" operators and their rules.
 
-
 ## Nodes Pre Peephole Optimization
 
 The following visual shows how the graph looks like pre-peephole optimization:
@@ -142,3 +141,113 @@ The following visual shows how the graph looks like pre-peephole optimization:
 ## Post-peephole
 
 ![Example Visual](./docs/02-post-peephole-ex1.svg)
+
+## Demonstration
+To demonstrate how the optimisation works, let's consider the following code:
+```
+return 1+2;
+```
+This is parsed as: 
+```java
+        var lhs = parseMultiplication();
+        if (match("+")) return new AddNode(lhs, parseAddition()).peephole();
+```
+When the peephole is called on the AddNode node it first calls the compute function:
+```java
+    public final Node peephole( ) {
+        // Compute initial or improved Type
+        Type type = _type = compute();
+```
+```java
+    public Type compute() {
+        if( in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1 ) {
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(i0.value()+i1.value());
+        }
+        return Type.BOTTOM;
+    }
+```
+In our case both of the operands(`1`, `2`) are constants, and instance of 
+`TypeInteger`.
+Since `compute` returns a type, and we know that both of our operands are constants, we can do
+constant propagation/folding where we compute the result of the expression so that instead of having `1+2` we can 
+have `3`.
+
+The 'TypeInteger' interface inherits from type but also has a field that stores the value observed for that type.
+```java
+    private final long _con
+```
+
+AddNode has the layout:
+
+![Example Visual](./docs/02-demonstration-pre-peephole.svg)
+
+Since, we already know the value of both of the operands, we can just add them together and replace the
+old node with a constant node that just holds the result of the expression.
+
+To do this - we have to recognize this happens when the type computed for the node is already a constant, but the node
+is still not an instance of constant node.
+
+This can be captured by:
+```java
+// Replace constant computations from non-constants with a constant node
+if (!(this instanceof ConstantNode) && type.isConstant()) {
+}
+```
+Note how we return a constant type when doing constant folding
+```java
+return TypeInteger.constant(i0.value()+i1.value());
+```
+We can create a constant node in the following way: 
+```java
+return new ConstantNode(type).peephole();
+```
+This recursively calls the peephole algorithm. 
+Now, we end up with this:
+
+![Example Visual](./docs/02-demonstration-pre-peephole-nokill.svg)
+
+Notice, how we added the constant node holding a constant value of `3`.
+The remaining add node is unused and can be killed.
+
+We can call the kill function before this way:
+```java
+// Replace constant computations from non-constants with a constant node
+if (!(this instanceof ConstantNode) && type.isConstant()) {
+     kill();             // Kill `this` because replacing with a Constant
+     return new ConstantNode(type).peephole();
+```
+This is responsible for deleting the dangling add node.
+
+```java
+public void kill( ) {
+  assert isUnused();      // Has no uses, so it is dead
+  for( int i=0; i<nIns(); i++ )
+        setDef(i,null);  // Set all inputs to null, recursively killing unused Nodes
+
+  _inputs.clear();
+  _type=null;             // Flag as dead
+  assert isDead();        // Really dead now
+}
+```
+
+`isUnused` - This makes sure the current node has no outputs.
+Ideally, in our case there would be one output as the return statement is 
+using the add expression.
+However, the optimisation happens before even creating the return node, which means that at this point
+there are no users of the add node.
+
+We can now freely go ahead and delete the node. 
+
+```java
+for(int i=0; i<nIns(); i++ )
+    setDef(i,null);  // Set all inputs to null, recursively killing unused Nodes
+
+_inputs.clear();
+_type=null;        
+```
+
+We finally end up with this:
+
+![Example Visual](./docs/02-demonstration-peephole.svg)
diff --git a/chapter02/docs/02-demonstration-peephole.svg b/chapter02/docs/02-demonstration-peephole.svg
new file mode 100644
index 00000000..90ab6ca4
--- /dev/null
+++ b/chapter02/docs/02-demonstration-peephole.svg
@@ -0,0 +1,54 @@
+<?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: chapter02 Pages: 1 -->
+<svg width="114pt" height="220pt" viewBox="0.00 0.00 114.00 220.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 216)">
+<title>chapter02</title>
+<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-216 110,-216 110,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="#000000" points="8,-8 8,-204 98,-204 98,-8 8,-8"/>
+</g>
+<!-- Start1 -->
+<g id="node1" class="node">
+<title>Start1</title>
+<polygon fill="#ffff00" stroke="#000000" points="80,-196 26,-196 26,-160 80,-160 80,-196"/>
+<text text-anchor="middle" x="53" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text>
+</g>
+<!-- Con_5 -->
+<g id="node2" class="node">
+<title>Con_5</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">#3</text>
+</g>
+<!-- Con_5&#45;&gt;Start1 -->
+<g id="edge1" class="edge">
+<title>Con_5-&gt;Start1</title>
+<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M45.5234,-124.1686C46.5929,-131.869 47.8647,-141.0257 49.0532,-149.5834"/>
+<polygon fill="#000000" stroke="#000000" points="45.6001,-150.1633 50.4426,-159.5867 52.5336,-149.2003 45.6001,-150.1633"/>
+<text text-anchor="middle" x="43.2998" y="-126.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Return6 -->
+<g id="node3" class="node">
+<title>Return6</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>
+<!-- Return6&#45;&gt;Start1 -->
+<g id="edge2" class="edge">
+<title>Return6-&gt;Start1</title>
+<path fill="none" stroke="#ff0000" d="M64.3196,-52.2322C69.9396,-62.3585 76.1294,-75.4211 79,-88 82.5597,-103.599 82.5597,-108.401 79,-124 76.9144,-133.1394 73.0765,-142.534 68.9781,-150.8724"/>
+<polygon fill="#ff0000" stroke="#ff0000" points="65.8583,-149.2853 64.3196,-159.7678 72.0595,-152.5328 65.8583,-149.2853"/>
+<text text-anchor="middle" x="62.096" y="-54.6322" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Return6&#45;&gt;Con_5 -->
+<g id="edge3" class="edge">
+<title>Return6-&gt;Con_5</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/chapter02/docs/02-demonstration-pre-peephole-nokill.svg b/chapter02/docs/02-demonstration-pre-peephole-nokill.svg
new file mode 100644
index 00000000..3d4f53df
--- /dev/null
+++ b/chapter02/docs/02-demonstration-pre-peephole-nokill.svg
@@ -0,0 +1,100 @@
+<?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: chapter02 Pages: 1 -->
+<svg width="258pt" height="220pt" viewBox="0.00 0.00 258.00 220.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 216)">
+<title>chapter02</title>
+<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-216 254,-216 254,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="#000000" points="8,-8 8,-204 242,-204 242,-8 8,-8"/>
+</g>
+<!-- Start1 -->
+<g id="node1" class="node">
+<title>Start1</title>
+<polygon fill="#ffff00" stroke="#000000" points="165,-196 111,-196 111,-160 165,-160 165,-196"/>
+<text text-anchor="middle" x="138" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text>
+</g>
+<!-- Con_2 -->
+<g id="node2" class="node">
+<title>Con_2</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_2&#45;&gt;Start1 -->
+<g id="edge1" class="edge">
+<title>Con_2-&gt;Start1</title>
+<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M60.8688,-119.5426C73.5668,-129.1664 90.9688,-142.3553 106.03,-153.7701"/>
+<polygon fill="#000000" stroke="#000000" points="104.028,-156.6444 114.1118,-159.8953 108.2562,-151.0656 104.028,-156.6444"/>
+<text text-anchor="middle" x="58.6452" y="-121.9426" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Con_3 -->
+<g id="node3" class="node">
+<title>Con_3</title>
+<ellipse fill="none" stroke="#000000" cx="115" cy="-106" rx="27" ry="18"/>
+<text text-anchor="middle" x="115" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">#2</text>
+</g>
+<!-- Con_3&#45;&gt;Start1 -->
+<g id="edge2" class="edge">
+<title>Con_3-&gt;Start1</title>
+<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M120.6854,-123.7978C123.237,-131.7854 126.3069,-141.3955 129.1486,-150.2913"/>
+<polygon fill="#000000" stroke="#000000" points="125.8432,-151.4462 132.2203,-159.9069 132.5113,-149.316 125.8432,-151.4462"/>
+<text text-anchor="middle" x="118.4618" y="-126.1978" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Add4 -->
+<g id="node4" class="node">
+<title>Add4</title>
+<ellipse fill="none" stroke="#000000" cx="89" cy="-34" rx="27" ry="18"/>
+<text text-anchor="middle" x="89" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text>
+</g>
+<!-- Add4&#45;&gt;Con_2 -->
+<g id="edge3" class="edge">
+<title>Add4-&gt;Con_2</title>
+<path fill="none" stroke="#000000" d="M78.3311,-50.6992C72.6414,-59.6048 65.5223,-70.7476 59.1684,-80.693"/>
+<polygon fill="#000000" stroke="#000000" points="56.0456,-79.08 53.6111,-89.3913 61.9445,-82.8487 56.0456,-79.08"/>
+<text text-anchor="middle" x="80.5547" y="-53.0992" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text>
+</g>
+<!-- Add4&#45;&gt;Con_3 -->
+<g id="edge4" class="edge">
+<title>Add4-&gt;Con_3</title>
+<path fill="none" stroke="#000000" d="M95.427,-51.7978C98.3866,-59.9936 101.963,-69.8976 105.2447,-78.9855"/>
+<polygon fill="#000000" stroke="#000000" points="101.9585,-80.1902 108.647,-88.407 108.5424,-77.8126 101.9585,-80.1902"/>
+<text text-anchor="middle" x="93.2034" y="-54.1978" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text>
+</g>
+<!-- Con_5 -->
+<g id="node5" class="node">
+<title>Con_5</title>
+<ellipse fill="none" stroke="#000000" cx="207" cy="-106" rx="27" ry="18"/>
+<text text-anchor="middle" x="207" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">#3</text>
+</g>
+<!-- Con_5&#45;&gt;Start1 -->
+<g id="edge5" class="edge">
+<title>Con_5-&gt;Start1</title>
+<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M192.3669,-121.2693C183.6447,-130.3708 172.3525,-142.1539 162.3214,-152.6212"/>
+<polygon fill="#000000" stroke="#000000" points="159.6869,-150.3117 155.2947,-159.9533 164.7408,-155.1551 159.6869,-150.3117"/>
+<text text-anchor="middle" x="194.5905" y="-123.6693" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Return6 -->
+<g id="node6" class="node">
+<title>Return6</title>
+<polygon fill="#ffff00" stroke="#000000" points="211.1025,-52 156.8975,-52 156.8975,-16 211.1025,-16 211.1025,-52"/>
+<text text-anchor="middle" x="184" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text>
+</g>
+<!-- Return6&#45;&gt;Start1 -->
+<g id="edge6" class="edge">
+<title>Return6-&gt;Start1</title>
+<path fill="none" stroke="#ff0000" d="M178.1741,-52.2377C170.2935,-76.9072 156.1635,-121.1402 146.9358,-150.0269"/>
+<polygon fill="#ff0000" stroke="#ff0000" points="143.4876,-149.3195 143.7786,-159.9104 150.1557,-151.4497 143.4876,-149.3195"/>
+<text text-anchor="middle" x="175.9505" y="-54.6377" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Return6&#45;&gt;Con_5 -->
+<g id="edge7" class="edge">
+<title>Return6-&gt;Con_5</title>
+<path fill="none" stroke="#000000" d="M189.8039,-52.1686C192.3565,-60.1594 195.41,-69.7181 198.2308,-78.5486"/>
+<polygon fill="#000000" stroke="#000000" points="194.9006,-79.6259 201.2777,-88.0866 201.5687,-77.4957 194.9006,-79.6259"/>
+<text text-anchor="middle" x="187.5803" 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/chapter02/docs/02-demonstration-pre-peephole.svg b/chapter02/docs/02-demonstration-pre-peephole.svg
new file mode 100644
index 00000000..49624652
--- /dev/null
+++ b/chapter02/docs/02-demonstration-pre-peephole.svg
@@ -0,0 +1,87 @@
+<?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: chapter02 Pages: 1 -->
+<svg width="186pt" height="292pt" viewBox="0.00 0.00 186.00 292.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 288)">
+<title>chapter02</title>
+<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-288 182,-288 182,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="#000000" points="8,-8 8,-276 170,-276 170,-8 8,-8"/>
+</g>
+<!-- Start1 -->
+<g id="node1" class="node">
+<title>Start1</title>
+<polygon fill="#ffff00" stroke="#000000" points="90,-268 36,-268 36,-232 90,-232 90,-268"/>
+<text text-anchor="middle" x="63" y="-245.8" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text>
+</g>
+<!-- Con_2 -->
+<g id="node2" class="node">
+<title>Con_2</title>
+<ellipse fill="none" stroke="#000000" cx="63" cy="-178" rx="27" ry="18"/>
+<text text-anchor="middle" x="63" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">#1</text>
+</g>
+<!-- Con_2&#45;&gt;Start1 -->
+<g id="edge1" class="edge">
+<title>Con_2-&gt;Start1</title>
+<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M63,-196.1686C63,-203.869 63,-213.0257 63,-221.5834"/>
+<polygon fill="#000000" stroke="#000000" points="59.5001,-221.5867 63,-231.5867 66.5001,-221.5868 59.5001,-221.5867"/>
+<text text-anchor="middle" x="60.7764" y="-198.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Con_3 -->
+<g id="node3" class="node">
+<title>Con_3</title>
+<ellipse fill="none" stroke="#000000" cx="135" cy="-178" rx="27" ry="18"/>
+<text text-anchor="middle" x="135" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">#2</text>
+</g>
+<!-- Con_3&#45;&gt;Start1 -->
+<g id="edge2" class="edge">
+<title>Con_3-&gt;Start1</title>
+<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M119.7307,-193.2693C110.6292,-202.3708 98.8461,-214.1539 88.3788,-224.6212"/>
+<polygon fill="#000000" stroke="#000000" points="85.6429,-222.4073 81.0467,-231.9533 90.5927,-227.3571 85.6429,-222.4073"/>
+<text text-anchor="middle" x="117.5071" y="-195.6693" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Add4 -->
+<g id="node4" class="node">
+<title>Add4</title>
+<ellipse fill="none" stroke="#000000" cx="63" cy="-106" rx="27" ry="18"/>
+<text text-anchor="middle" x="63" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text>
+</g>
+<!-- Add4&#45;&gt;Con_2 -->
+<g id="edge3" class="edge">
+<title>Add4-&gt;Con_2</title>
+<path fill="none" stroke="#000000" d="M63,-124.1686C63,-131.869 63,-141.0257 63,-149.5834"/>
+<polygon fill="#000000" stroke="#000000" points="59.5001,-149.5867 63,-159.5867 66.5001,-149.5868 59.5001,-149.5867"/>
+<text text-anchor="middle" x="60.7764" y="-126.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text>
+</g>
+<!-- Add4&#45;&gt;Con_3 -->
+<g id="edge4" class="edge">
+<title>Add4-&gt;Con_3</title>
+<path fill="none" stroke="#000000" d="M78.2693,-121.2693C88.197,-131.197 101.3153,-144.3153 112.4363,-155.4363"/>
+<polygon fill="#000000" stroke="#000000" points="110.2067,-158.1564 119.7527,-162.7527 115.1564,-153.2067 110.2067,-158.1564"/>
+<text text-anchor="middle" x="80.4929" y="-123.6693" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text>
+</g>
+<!-- Return5 -->
+<g id="node5" class="node">
+<title>Return5</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>
+<!-- Return5&#45;&gt;Start1 -->
+<g id="edge5" class="edge">
+<title>Return5-&gt;Start1</title>
+<path fill="none" stroke="#ff0000" d="M41.6804,-52.2322C36.0604,-62.3585 29.8706,-75.4211 27,-88 16.3208,-134.7969 13.0904,-150.0596 27,-196 29.9564,-205.7645 35.3252,-215.3771 41.03,-223.7238"/>
+<polygon fill="#ff0000" stroke="#ff0000" points="38.2871,-225.9027 47.0095,-231.9169 43.9414,-221.7761 38.2871,-225.9027"/>
+<text text-anchor="middle" x="39.4568" y="-54.6322" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Return5&#45;&gt;Add4 -->
+<g id="edge6" class="edge">
+<title>Return5-&gt;Add4</title>
+<path fill="none" stroke="#000000" d="M55.5234,-52.1686C56.5929,-59.869 57.8647,-69.0257 59.0532,-77.5834"/>
+<polygon fill="#000000" stroke="#000000" points="55.6001,-78.1633 60.4426,-87.5867 62.5336,-77.2003 55.6001,-78.1633"/>
+<text text-anchor="middle" x="53.2998" 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