extend opt and projnode docs

3 files changed, 286 insertions, 1 deletions

diff --git a/chapter04/README.md b/chapter04/README.md
index e1b28d3f..e180a88d 100644
--- a/chapter04/README.md
+++ b/chapter04/README.md
@@ -43,11 +43,123 @@ Each projection node contains an index of the field to extract from its input no
 Projection nodes allow us to maintain labeled use-def edges as simple Node references.
 
 In the visuals, projection nodes are shown as rectangular boxes inside the node to which they are attached.
+### Visualisation
 
 ![ProjNode](./docs/projnode.png)
 
 In the visual above, the projection nodes have been tagged by the names associated with the outputs of the
-Start node.
+Start node. Both MultiNode and Control nodes are yellow.
+
+`$ctrl` and `arg` are outputs(users) of StartNode(`START`):
+Since the projection nodes: `$ctrl`, `arg` are using `START` as their input.
+*Notice*: START is passed in as the control node(0th input) for the ProjNode.
+
+```java 
+    public ProjNode(MultiNode ctrl, int idx, String label) {
+    super(ctrl);
+```
+
+```java
+_scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole());
+_scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole());
+```
+These projection nodes are going to extract the types for `CTRL` and `ARG0` from the `START` MultiNode.
+The MultiNode holds the types as a TypeTuple:
+
+```java
+public StartNode(Type[] args) {
+    super();
+    _args = new TypeTuple(args);
+```
+
+Extracting the types:
+```java
+ return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM;
+```
+### Demonstration
+#### arg is provided:
+The arg from external environment can be provided in the following way:
+```java
+Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2));
+```
+The graph:
+
+![ProjNode](./docs/04-arg1.svg)
+ - The `arg` projection node is not included in the cluster(where `$ctrl` and `Start` are displayed)(0).
+ - `$ctrl` and `arg` are both defined in the outmost symbol table.
+ - Notice the extra symbol table created at index: 1(1).
+ - Notice how the dashed blue line is not drawn for `ctrl` and is not pointing to the `$ctrl node` in the cluster(2).
+
+`(0): ` Arg is a constant and gets stored in a constant node.
+When `peephole` called, and compute is executed, the type returned is the type at the provided index in the TypeTuple.
+It turns out - this returned type will be a `constant` TypeInteger with a `ProjNode`. 
+This can be replaced with a ConstantNode with the type passed in for `arg`.
+
+```java
+public final Node peephole( ) {
+      Type type = _type = compute(); 
+        /*
+             _type = {TypeInteger@1527} "2"
+            _is_con = true
+            _con = 2
+            _type = 4
+         */
+
+      if (_disablePeephole)
+          return this;        
+      
+      // ProjNode is not a constant unlike its type.
+      if (!(this instanceof ConstantNode) && type.isConstant())
+          // Create Constant(2)
+          return deadCodeElim(new ConstantNode(type).peephole());
+      
+      Node n = idealize(); // just null
+      if( n != null )
+          return deadCodeElim(n.peephole()); // won't get called
+
+      return this;  // won't get called       
+```
+
+`(1): ` We always create a symbol table when start parsing so that global symbols can be inserted.
+We had to create explicitly a symbol table containing `CTRL` and `ARG` at index 0. The symbol table for global symbols is at index 1(nested and currently empty).
+
+`(2): ` The control node is always set to null because there is no control after return.
+It is manually set to null here:
+```
+ctrl(null);             // Kill control
+```
+
+Which will call `setDef` to kill the node. If it does not exist we can't draw a line pointing to it.
+
+#### arg is not provided:
+Arg is not provided in this case:
+```java 
+      Parser parser = new Parser("return arg; #showGraph;", TypeInteger.BOT);
+```
+The graph:
+
+![ArgNode](./docs/04-arg2.svg)
+ - The `arg` projection node is included in the cluster.(0)
+
+`(0):` If the `arg` projection node is not explicitly defined, then we declare it this way:
+```java 
+public Parser(String source) {
+    this(source, TypeInteger.BOT);
+}
+```
+`TypeInteger.BOT:`
+```java
+public final static TypeInteger BOT = new TypeInteger(false, 1); 
+```
+``` 
+arg = {TypeInteger@1417} "IntBot"
+_type = 4
+_con = 1
+_is_con = false
+```
+We clearly see this is not a constant, so it can't get optimised out and will remain in the ProjNode cluster.
+
+#### ctrl is not null: Next chapter(ch5)
 
 ## Changes to Type System
 
@@ -162,6 +274,15 @@ Here is a (partial) list of peepholes introduced in this Chapter:
 | (con1 + (arg + con2)) | (arg + (con1 + con2)) | Move constants to right, to encourage folding  |
 | ((arg1 + con) + arg2) | ((arg1 + arg2) + con) | Move constants to right, to encourage folding  |
 | (arg + arg)           | (arg * 2)             | Sum-of-products form                           |
+| (arg - arg)           | 0                     | Sub of same is 0
+| (con / 1)             | con                   | Division by one
+| (con == con)          | 1                     | Compare of same
+| (con != con)          | 0                     | Compare of same
+| (con < con)           | 0                     | Compare of same
+| (con > con)           | 0                     | Compare of same
+| (con <= con)          | 1                     | Compare of same
+| (con >= con)          | 1                     | Compare of same
+
 
 ## Code Walkthrough
 
diff --git a/chapter04/docs/04-arg1.svg b/chapter04/docs/04-arg1.svg
new file mode 100644
index 00000000..cf4599c5
--- /dev/null
+++ b/chapter04/docs/04-arg1.svg
@@ -0,0 +1,84 @@
+<?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="358pt" height="186pt" viewBox="0.00 0.00 358.00 186.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 182)">
+<title>chapter04</title>
+<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-182 354,-182 354,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="#000000" points="8,-16 8,-170 154,-170 154,-16 8,-16"/>
+</g>
+<g id="clust2" class="cluster">
+<title>cluster_Scope1_0</title>
+<polygon fill="none" stroke="#000000" points="162,-8 162,-76 342,-76 342,-8 162,-8"/>
+</g>
+<g id="clust3" class="cluster">
+<title>cluster_Scope1_1</title>
+<polygon fill="none" stroke="#000000" points="264,-16 264,-68 334,-68 334,-16 264,-16"/>
+</g>
+<!-- Start2 -->
+<g id="node1" class="node">
+<title>Start2</title>
+<polygon fill="#ffff00" stroke="transparent" points="25,-132 25,-158 66,-158 66,-132 25,-132"/>
+<polygon fill="none" stroke="#000000" points="25,-132 25,-158 66,-158 66,-132 25,-132"/>
+<text text-anchor="start" x="32.2805" y="-140.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text>
+<polygon fill="none" stroke="#000000" points="25,-100 25,-132 66,-132 66,-100 25,-100"/>
+<polygon fill="#ffff00" stroke="transparent" points="30,-105 30,-127 61,-127 61,-105 30,-105"/>
+<polygon fill="none" stroke="#000000" points="30,-105 30,-127 61,-127 61,-105 30,-105"/>
+<text text-anchor="start" x="32.6718" y="-111.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="119" cy="-129" rx="27" ry="18"/>
+<text text-anchor="middle" x="119" y="-124.8" font-family="Times,serif" font-size="14.00" fill="#000000">2</text>
+</g>
+<!-- Return6 -->
+<g id="node3" class="node">
+<title>Return6</title>
+<polygon fill="#ffff00" stroke="#000000" points="109.1025,-60 54.8975,-60 54.8975,-24 109.1025,-24 109.1025,-60"/>
+<text text-anchor="middle" x="82" y="-37.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text>
+</g>
+<!-- Return6&#45;&gt;Start2 -->
+<g id="edge1" class="edge">
+<title>Return6-&gt;Start2:p0</title>
+<path fill="none" stroke="#ff0000" d="M65.0542,-60.052C57.6135,-69.4899 49.9318,-81.7894 47.1181,-94.8747"/>
+<polygon fill="#ff0000" stroke="#ff0000" points="43.6189,-94.6762 46,-105 50.5766,-95.4446 43.6189,-94.6762"/>
+<text text-anchor="middle" x="62.8306" y="-62.452" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Return6&#45;&gt;Con_5 -->
+<g id="edge2" class="edge">
+<title>Return6-&gt;Con_5</title>
+<path fill="none" stroke="#000000" d="M89.6664,-60.0265C94.8444,-72.2017 101.7707,-88.4878 107.5926,-102.1772"/>
+<polygon fill="#000000" stroke="#000000" points="104.4613,-103.7577 111.5959,-111.5903 110.903,-101.0181 104.4613,-103.7577"/>
+<text text-anchor="middle" x="87.4428" y="-62.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text>
+</g>
+<!-- Scope1_0 -->
+<g id="node4" class="node">
+<title>Scope1_0</title>
+<polygon fill="#00ffff" stroke="transparent" points="179,-31 179,-53 192,-53 192,-31 179,-31"/>
+<polygon fill="none" stroke="#000000" points="179,-31 179,-53 192,-53 192,-31 179,-31"/>
+<text text-anchor="start" x="182" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">0</text>
+<polygon fill="none" stroke="#000000" points="192,-31 192,-53 223,-53 223,-31 192,-31"/>
+<text text-anchor="start" x="194.6718" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text>
+<polygon fill="none" stroke="#000000" points="223,-31 223,-53 246,-53 246,-31 223,-31"/>
+<text text-anchor="start" x="225.5624" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text>
+</g>
+<!-- Scope1_0&#45;&gt;Con_5 -->
+<g id="edge3" class="edge">
+<title>Scope1_0:Scope1_0_arg-&gt;Con_5</title>
+<path fill="none" stroke="#6495ed" stroke-dasharray="5,2" d="M235,-53C235,-91.8959 188.8038,-111.9666 154.717,-121.4819"/>
+<polygon fill="#6495ed" stroke="#6495ed" points="153.8305,-118.0959 145.0327,-123.9992 155.5916,-124.8708 153.8305,-118.0959"/>
+</g>
+<!-- Scope1_1 -->
+<g id="node5" class="node">
+<title>Scope1_1</title>
+<polygon fill="#00ffff" stroke="transparent" points="293,-31 293,-53 306,-53 306,-31 293,-31"/>
+<polygon fill="none" stroke="#000000" points="293,-31 293,-53 306,-53 306,-31 293,-31"/>
+<text text-anchor="start" x="296" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">1</text>
+</g>
+</g>
+</svg>
\ No newline at end of file
diff --git a/chapter04/docs/04-arg2.svg b/chapter04/docs/04-arg2.svg
new file mode 100644
index 00000000..2b3b47a3
--- /dev/null
+++ b/chapter04/docs/04-arg2.svg
@@ -0,0 +1,80 @@
+<?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="308pt" height="186pt" viewBox="0.00 0.00 308.00 186.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 182)">
+<title>chapter04</title>
+<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-182 304,-182 304,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="#000000" points="8,-16 8,-170 104,-170 104,-16 8,-16"/>
+</g>
+<g id="clust2" class="cluster">
+<title>cluster_Scope1_0</title>
+<polygon fill="none" stroke="#000000" points="112,-8 112,-76 292,-76 292,-8 112,-8"/>
+</g>
+<g id="clust3" class="cluster">
+<title>cluster_Scope1_1</title>
+<polygon fill="none" stroke="#000000" points="214,-16 214,-68 284,-68 284,-16 214,-16"/>
+</g>
+<!-- Start2 -->
+<g id="node1" class="node">
+<title>Start2</title>
+<polygon fill="#ffff00" stroke="transparent" points="24,-132 24,-158 88,-158 88,-132 24,-132"/>
+<polygon fill="none" stroke="#000000" points="24,-132 24,-158 88,-158 88,-132 24,-132"/>
+<text text-anchor="start" x="42.7805" y="-140.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text>
+<polygon fill="none" stroke="#000000" points="24,-100 24,-132 88,-132 88,-100 24,-100"/>
+<polygon fill="#ffff00" stroke="transparent" points="29,-105 29,-127 60,-127 60,-105 29,-105"/>
+<polygon fill="none" stroke="#000000" points="29,-105 29,-127 60,-127 60,-105 29,-105"/>
+<text text-anchor="start" x="31.6718" y="-111.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text>
+<polygon fill="none" stroke="#000000" points="60,-105 60,-127 83,-127 83,-105 60,-105"/>
+<text text-anchor="start" x="62.5624" y="-111.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text>
+</g>
+<!-- Return5 -->
+<g id="node2" class="node">
+<title>Return5</title>
+<polygon fill="#ffff00" stroke="#000000" points="83.1025,-60 28.8975,-60 28.8975,-24 83.1025,-24 83.1025,-60"/>
+<text text-anchor="middle" x="56" y="-37.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text>
+</g>
+<!-- Return5&#45;&gt;Start2 -->
+<g id="edge1" class="edge">
+<title>Return5-&gt;Start2:p0</title>
+<path fill="none" stroke="#ff0000" d="M50.7017,-60.0225C48.1903,-69.7926 45.5126,-82.3709 44.4612,-94.733"/>
+<polygon fill="#ff0000" stroke="#ff0000" points="40.9524,-94.853 44,-105 47.9454,-95.1672 40.9524,-94.853"/>
+<text text-anchor="middle" x="48.4781" y="-62.4225" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text>
+</g>
+<!-- Return5&#45;&gt;Start2 -->
+<g id="edge2" class="edge">
+<title>Return5-&gt;Start2:p1</title>
+<path fill="none" stroke="#000000" d="M63.1576,-60.1614C66.4858,-69.8668 70.0107,-82.3387 71.3935,-94.7027"/>
+<polygon fill="#000000" stroke="#000000" points="67.918,-95.2231 72,-105 74.9059,-94.8115 67.918,-95.2231"/>
+<text text-anchor="middle" x="60.934" y="-62.5614" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text>
+</g>
+<!-- Scope1_0 -->
+<g id="node3" class="node">
+<title>Scope1_0</title>
+<polygon fill="#00ffff" stroke="transparent" points="129,-31 129,-53 142,-53 142,-31 129,-31"/>
+<polygon fill="none" stroke="#000000" points="129,-31 129,-53 142,-53 142,-31 129,-31"/>
+<text text-anchor="start" x="132" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">0</text>
+<polygon fill="none" stroke="#000000" points="142,-31 142,-53 173,-53 173,-31 142,-31"/>
+<text text-anchor="start" x="144.6718" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text>
+<polygon fill="none" stroke="#000000" points="173,-31 173,-53 196,-53 196,-31 173,-31"/>
+<text text-anchor="start" x="175.5624" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text>
+</g>
+<!-- Scope1_0&#45;&gt;Start2 -->
+<g id="edge3" class="edge">
+<title>Scope1_0:Scope1_0_arg-&gt;Start2:p1</title>
+<path fill="none" stroke="#6495ed" stroke-dasharray="5,2" d="M185,-53C185,-102.849 142.3608,-114.5665 93.2341,-115.8698"/>
+<polygon fill="#6495ed" stroke="#6495ed" points="92.9546,-112.373 83,-116 93.0437,-119.3724 92.9546,-112.373"/>
+</g>
+<!-- Scope1_1 -->
+<g id="node4" class="node">
+<title>Scope1_1</title>
+<polygon fill="#00ffff" stroke="transparent" points="243,-31 243,-53 256,-53 256,-31 243,-31"/>
+<polygon fill="none" stroke="#000000" points="243,-31 243,-53 256,-53 256,-31 243,-31"/>
+<text text-anchor="start" x="246" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">1</text>
+</g>
+</g>
+</svg>
\ No newline at end of file