Backport changes in Chapter 5 to previous chapters and update Chapter5 documentation (#34)

* Backport changes from chapter 5 to older chapters (#30)

* Fix wrong indent

* Backport to chapter 4

* Backport to chapter 3

* Backport to chapter 2

* Backport to chapter 1

* Add if statement to comment (#32)

* Update visuals for chapters 1,2 & 3.
Reenable drawing of edges from constants to Start for these chapters.

* Update visuals for chapters 4.
Revise text to explain the labeling of edges in graphs and that we omit edge from Constant to Start nodes from chapter 4.

* Add code snippets for if statement parsing and the duplication and merging of ScopeNodes.
Explain how scopeNodes are duplicated and merged.

* Add constant check to minus node (#31)

* Fix closing root block with } (#33)

* Backport fix closing root block with } to chapter 4 and 3 (#35)

* Show use-def edge from Phi to Region as dotted edge.
Add example of Phi peephole.
Update visuals.
Add more examples.

* Fix visuals in chapter 1 and README in chapter 4.

* Remove subheading

* Adjust spaces

---------

Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>

10 files changed, 126 insertions, 132 deletions

diff --git a/chapter01/README.md b/chapter01/README.md
index e09b61a3..f5f31f82 100644
--- a/chapter01/README.md
+++ b/chapter01/README.md
@@ -164,5 +164,7 @@ return 1;
 
 ![Sea of Nodes Visual](./docs/01-graph.svg)
 
-* Control nodes appear as square boxes
+* Control nodes appear as square boxes with yellow background
 * Control edges are in bold red
+* The edges from Constants to Start are shown in dotted lines as these are not true control edges
+* We label each edge with its position in the `_inputs` array, thus `0` means the edge is `_inputs[0]`.
diff --git a/chapter01/docs/01-graph.gv b/chapter01/docs/01-graph.gv
index 82d1b40a..df256f52 100644
--- a/chapter01/docs/01-graph.gv
+++ b/chapter01/docs/01-graph.gv
@@ -1,11 +1,17 @@
 digraph chapter01 {
+/*
+return 1;
+*/
 	rankdir=BT;
+	ordering="in";
+	concentrate="true";
 	subgraph cluster_Nodes {
 		Start1 [ shape=box style=filled fillcolor=yellow label="Start" ];
-		Con12 [ label="Con1" ];
+		Con_2 [ label="#1" ];
 		Return3 [ shape=box style=filled fillcolor=yellow label="Return" ];
 	}
-	Con12 -> Start1 [style=dotted];
-	Return3 -> Start1 [color=red];
-	Return3 -> Con12;
+	edge [ fontname=Helvetica, fontsize=8 ];
+	Con_2 -> Start1[taillabel=0 style=dotted];
+	Return3 -> Start1[taillabel=0 color=red];
+	Return3 -> Con_2[taillabel=1];
 }
diff --git a/chapter01/docs/01-graph.svg b/chapter01/docs/01-graph.svg
index 8e478f4d..7f511966 100644
--- a/chapter01/docs/01-graph.svg
+++ b/chapter01/docs/01-graph.svg
@@ -4,50 +4,53 @@
 <!-- Generated by graphviz version 2.43.0 (0)
  -->
 <!-- Title: chapter01 Pages: 1 -->
-<svg width="128pt" height="220pt"
- viewBox="0.00 0.00 128.00 220.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<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>chapter01</title>
-<polygon fill="white" stroke="transparent" points="-4,4 -4,-216 124,-216 124,4 -4,4"/>
+<polygon fill="white" 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="black" points="8,-8 8,-204 112,-204 112,-8 8,-8"/>
+<polygon fill="none" stroke="black" points="8,-8 8,-204 98,-204 98,-8 8,-8"/>
 </g>
 <!-- Start1 -->
 <g id="node1" class="node">
 <title>Start1</title>
-<polygon fill="yellow" stroke="black" points="83,-196 29,-196 29,-160 83,-160 83,-196"/>
-<text text-anchor="middle" x="56" y="-174.3" font-family="Times,serif" font-size="14.00">Start</text>
+<polygon fill="yellow" stroke="black" points="80,-196 26,-196 26,-160 80,-160 80,-196"/>
+<text text-anchor="middle" x="53" y="-174.3" font-family="Times,serif" font-size="14.00">Start</text>
 </g>
-<!-- Con12 -->
+<!-- Con_2 -->
 <g id="node2" class="node">
-<title>Con12</title>
-<ellipse fill="none" stroke="black" cx="70" cy="-106" rx="34.39" ry="18"/>
-<text text-anchor="middle" x="70" y="-102.3" font-family="Times,serif" font-size="14.00">Con1</text>
+<title>Con_2</title>
+<ellipse fill="none" stroke="black" cx="43" cy="-106" rx="27" ry="18"/>
+<text text-anchor="middle" x="43" y="-102.3" font-family="Times,serif" font-size="14.00">#1</text>
 </g>
-<!-- Con12&#45;&gt;Start1 -->
+<!-- Con_2&#45;&gt;Start1 -->
 <g id="edge1" class="edge">
-<title>Con12&#45;&gt;Start1</title>
-<path fill="none" stroke="black" stroke-dasharray="1,5" d="M66.61,-123.95C65.07,-131.65 63.21,-140.97 61.47,-149.64"/>
-<polygon fill="black" stroke="black" points="57.98,-149.23 59.46,-159.72 64.85,-150.61 57.98,-149.23"/>
+<title>Con_2&#45;&gt;Start1</title>
+<path fill="none" stroke="black" stroke-dasharray="1,5" d="M45.42,-123.95C46.52,-131.65 47.85,-140.97 49.09,-149.64"/>
+<polygon fill="black" stroke="black" points="45.65,-150.32 50.53,-159.72 52.58,-149.33 45.65,-150.32"/>
+<text text-anchor="middle" x="42.42" y="-126.55" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
 </g>
 <!-- Return3 -->
 <g id="node3" class="node">
 <title>Return3</title>
-<polygon fill="yellow" stroke="black" points="92,-52 26,-52 26,-16 92,-16 92,-52"/>
-<text text-anchor="middle" x="59" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text>
+<polygon fill="yellow" stroke="black" points="86,-52 20,-52 20,-16 86,-16 86,-52"/>
+<text text-anchor="middle" x="53" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text>
 </g>
 <!-- Return3&#45;&gt;Start1 -->
 <g id="edge2" class="edge">
 <title>Return3&#45;&gt;Start1</title>
-<path fill="none" stroke="red" d="M45.44,-52.03C38.44,-61.91 30.63,-74.95 27,-88 22.71,-103.41 23.04,-108.5 27,-124 29.38,-133.3 33.76,-142.73 38.42,-151"/>
-<polygon fill="red" stroke="red" points="35.54,-153.01 43.69,-159.78 41.54,-149.41 35.54,-153.01"/>
+<path fill="none" stroke="red" d="M64.05,-52.39C69.74,-62.38 76.08,-75.42 79,-88 82.62,-103.59 82.62,-108.41 79,-124 76.9,-133.04 73.03,-142.32 68.91,-150.53"/>
+<polygon fill="red" stroke="red" points="65.69,-149.14 64.05,-159.61 71.86,-152.45 65.69,-149.14"/>
+<text text-anchor="middle" x="61.05" y="-54.99" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
 </g>
-<!-- Return3&#45;&gt;Con12 -->
+<!-- Return3&#45;&gt;Con_2 -->
 <g id="edge3" class="edge">
-<title>Return3&#45;&gt;Con12</title>
-<path fill="none" stroke="black" d="M61.72,-52.3C62.93,-60.02 64.39,-69.29 65.74,-77.89"/>
-<polygon fill="black" stroke="black" points="62.3,-78.56 67.31,-87.9 69.22,-77.47 62.3,-78.56"/>
+<title>Return3&#45;&gt;Con_2</title>
+<path fill="none" stroke="black" d="M50.53,-52.3C49.43,-60.02 48.1,-69.29 46.87,-77.89"/>
+<polygon fill="black" stroke="black" points="43.39,-77.5 45.44,-87.9 50.32,-78.49 43.39,-77.5"/>
+<text text-anchor="middle" x="47.53" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
 </g>
 </g>
 </svg>
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
index a71def25..e2c1ca71 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
@@ -1,20 +1,16 @@
 package com.seaofnodes.simple;
 
-import com.seaofnodes.simple.node.ConstantNode;
-import com.seaofnodes.simple.node.Node;
-import com.seaofnodes.simple.node.ReturnNode;
-import com.seaofnodes.simple.node.StartNode;
+import com.seaofnodes.simple.node.*;
 
 /**
- * The Parser converts a Simple source program to the Sea of Nodes intermediate representation
- * directly in one pass. There is no intermediate Abstract Syntax Tree structure.
- *
+ * The Parser converts a Simple source program to the Sea of Nodes intermediate
+ * representation directly in one pass. There is no intermediate Abstract
+ * Syntax Tree structure.
+ * <p>
  * This is a simple recursive descent parser. All lexical analysis is done here as well.
  */
 public class Parser {
 
-    private final Lexer _lexer;
-
     /**
      * A Global Static, unique to each compilation.  This is a public, so we
      * can make constants everywhere without having to thread the StartNode
@@ -24,6 +20,10 @@ public class Parser {
      */
     public static StartNode START;
 
+    // The Lexer.  Thin wrapper over a byte[] buffer with a cursor.
+    private final Lexer _lexer;
+
+
     public Parser(String source) {
         _lexer = new Lexer(source);
         Node.reset();
@@ -31,21 +31,21 @@ public class Parser {
     }
 
     public ReturnNode parse() {
+        require("return");
         return parseReturn();
     }
 
     /**
-     * Parses return statement.
+     * Parses a return statement; "return" already parsed.
      *
      * <pre>
-     *     return expr ;
+     *     'return' expr ;
      * </pre>
+     * @return an expression {@link Node}, never {@code null}
      */
     private ReturnNode parseReturn() {
-        require("return");
-        var returnExpr = parseExpression();
-        require(";");
-        return new ReturnNode(START, returnExpr);
+        var expr = require(parseExpression(), ";");
+        return new ReturnNode(START, expr);
     }
 
     /**
@@ -54,6 +54,7 @@ public class Parser {
      * <pre>
      *     expr : primaryExpr
      * </pre>
+     * @return an expression {@link Node}, never {@code null}
      */
     private Node parseExpression() {
         return parsePrimary();
@@ -81,25 +82,28 @@ public class Parser {
      * </pre>
      */
     private ConstantNode parseIntegerLiteral() {
-        return new ConstantNode(_lexer.parseNumber(), START);
-    }
-
-    static RuntimeException error(String errorMessage) {
-        return new RuntimeException(errorMessage);
+        return new ConstantNode(_lexer.parseNumber());
     }
 
     //////////////////////////////////
     // Utilities for lexical analysis
 
     // Return true and skip if "syntax" is next in the stream.
-    private boolean match(String syntax) {
-        return _lexer.match(syntax);
-    }
+    private boolean match(String syntax) { return _lexer.match(syntax); }
 
     // Require an exact match
-    private void require(String syntax) {
-        if (match(syntax)) return;
-        throw error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken());
+    private void require(String syntax) { require(null, syntax); }
+    private Node require(Node n, String syntax) {
+        if (match(syntax)) return n;
+        throw errorSyntax(syntax);
+    }
+
+    RuntimeException errorSyntax(String syntax) {
+        return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken());
+    }
+
+    static RuntimeException error(String errorMessage) {
+        return new RuntimeException(errorMessage);
     }
 
     ////////////////////////////////////
@@ -152,8 +156,7 @@ public class Parser {
          * Return the next non-white-space character
          */
         private void skipWhiteSpace() {
-            while (isWhiteSpace())
-                _position++;
+            while (isWhiteSpace()) _position++;
         }
 
 
@@ -163,8 +166,7 @@ public class Parser {
         boolean match(String syntax) {
             skipWhiteSpace();
             int len = syntax.length();
-            if (_position + len > _input.length)
-                return false;
+            if (_position + len > _input.length) return false;
             for (int i = 0; i < len; i++)
                 if ((char) _input[_position + i] != syntax.charAt(i))
                     return false;
@@ -175,20 +177,13 @@ public class Parser {
         // Used for errors
         String getAnyNextToken() {
             if (isEOF()) return "";
-            if (isIdentifierStart(peek()))
-                return parseIdentifier();
-            if (isPunctuation(peek()))
-                return parsePunctuation();
+            if (isIdStart(peek())) return parseId();
+            if (isPunctuation(peek())) return parsePunctuation();
             return String.valueOf(peek());
         }
 
-        boolean isNumber() {
-            return isNumber(peek());
-        }
-
-        boolean isNumber(char ch) {
-            return Character.isDigit(ch);
-        }
+        boolean isNumber() {return isNumber(peek());}
+        boolean isNumber(char ch) {return Character.isDigit(ch);}
 
         private long parseNumber() {
             int start = _position;
@@ -200,18 +195,18 @@ public class Parser {
         }
 
         // First letter of an identifier 
-        private boolean isIdentifierStart(char ch) {
+        private boolean isIdStart(char ch) {
             return Character.isAlphabetic(ch) || ch == '_';
         }
 
         // All characters of an identifier, e.g. "_x123"
-        private boolean isIdentifierLetter(char ch) {
+        private boolean isIdLetter(char ch) {
             return Character.isLetterOrDigit(ch) || ch == '_';
         }
 
-        private String parseIdentifier() {
+        private String parseId() {
             int start = _position;
-            while (isIdentifierLetter(nextChar())) ;
+            while (isIdLetter(nextChar())) ;
             return new String(_input, start, --_position - start);
         }
 
@@ -222,8 +217,7 @@ public class Parser {
 
         private String parsePunctuation() {
             int start = _position;
-            if (isPunctuation(nextChar())) ;
-            return new String(_input, start, --_position - start);
+            return new String(_input, start, 1);
         }
     }
 
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 7644daf2..21f65084 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -1,5 +1,7 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Parser;
+
 /**
  * A Constant node represents a constant value.  At present, the only constants
  * that we allow are integer literals; therefore Constants contain an integer
@@ -16,8 +18,8 @@ public class ConstantNode extends Node {
 
     public final long _value;
 
-    public ConstantNode(long value, StartNode startNode) {
-        super(startNode);
+    public ConstantNode(long value) {
+        super(Parser.START);
         _value = value;
     }
 }
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java
deleted file mode 100644
index 48cf2b7a..00000000
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java
+++ /dev/null
@@ -1,9 +0,0 @@
-package com.seaofnodes.simple.node;
-
-
-/**
- * Control interface is a marker interface to be implemented
- * by Control nodes.
- */
-public interface Control {
-}
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
index b6ce3160..cf465e94 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
-import java.util.ArrayList;
-import java.util.Collections;
+import java.util.*;
 
 /**
  * All Nodes in the Sea of Nodes IR inherit from the Node class.
@@ -22,8 +21,7 @@ public abstract class Node {
      * <p>
      * Generally fixed length, ordered, nulls allowed, no unused trailing space.
      * Ordering is required because e.g. "a/b" is different from "b/a".
-     * The first input (offset 0) is often a Control node.
-     * @see Control
+     * The first input (offset 0) is often a {@link #isCFG} node.
      */
     public final ArrayList<Node> _inputs;
 
@@ -45,17 +43,16 @@ public abstract class Node {
      * */
     private static int UNIQUE_ID = 1;
 
-    protected Node(Node ...inputs) {
+    protected Node(Node... inputs) {
         _nid = UNIQUE_ID++; // allocate unique dense ID
         _inputs = new ArrayList<>();
         Collections.addAll(_inputs,inputs);
         _outputs = new ArrayList<>();
-        for( Node n : _inputs ) {
+        for( Node n : _inputs )
             if( n != null )
                 n._outputs.add( this );
-      }
     }
-
+    
     /**
      * Gets the ith input node
      * @param i Offset of the input node
@@ -65,23 +62,16 @@ public abstract class Node {
 
     public int nIns() { return _inputs.size(); }
 
-    /**
-     * Gets the ith output node
-     * @param i Offset of the output node
-     * @return Output node (not null)
-     */
-    public Node out(int i) { return _outputs.get(i); }
-
     public int nOuts() { return _outputs.size(); }
 
+    public boolean isUnused() { return nOuts() == 0; }
+
+    public boolean isCFG() { return false; }
+  
+
     /**
      * Used to allow repeating tests in the same JVM.  This just resets the
      * Node unique id generator, and is done as part of making a new Parser.
      */
-    public static void reset() {
-        UNIQUE_ID = 1;
-    }
-    /*
-     * hashCode and equals implementation to be added in later chapter.
-     */
+    public static void reset() { UNIQUE_ID = 1; }
 }
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index a2321e2b..5e083cf2 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -9,17 +9,15 @@ package com.seaofnodes.simple.node;
  * <p>
  * The Return's output is the value from the data node.
  */
-public class ReturnNode extends Node implements Control {
+public class ReturnNode extends Node {
 
     public ReturnNode(Node ctrl, Node data) {
         super(ctrl, data);
     }
 
-    public Node ctrl() {
-        return in(0);
-    }
+    public Node ctrl() { return in(0); }
+    public Node expr() { return in(1); }
 
-    public Node expr() {
-        return in(1);
-    }
+    @Override public boolean isCFG() { return true; }
+  
 }
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
index c29ba53c..04bd6bb4 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -5,9 +5,12 @@ package com.seaofnodes.simple.node;
  * yet accept parameters.  When we add parameters the value of Start will be a tuple, and will require Projections to extract the values.
  * We discuss this in detail in Chapter 9: Functions and Calls.
  */
-public class StartNode extends Node implements Control {
+public class StartNode extends Node {
 
     public StartNode(/*arguments go here*/) {
         super();
     }
+
+    @Override public boolean isCFG() { return true; }
+
 }
diff --git a/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java
index ce8c2822..cb5a8a69 100644
--- a/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java
+++ b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java
@@ -1,15 +1,11 @@
 package com.seaofnodes.simple;
 
-import com.seaofnodes.simple.node.ConstantNode;
-import com.seaofnodes.simple.node.Node;
-import com.seaofnodes.simple.node.ReturnNode;
-import com.seaofnodes.simple.node.StartNode;
+import com.seaofnodes.simple.node.*;
 import org.junit.Rule;
 import org.junit.Test;
 import org.junit.rules.ExpectedException;
 
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.fail;
+import static org.junit.Assert.*;
 
 public class Chapter01Test {
 
@@ -21,11 +17,11 @@ public class Chapter01Test {
         Parser parser = new Parser("return 1;");
         ReturnNode ret = parser.parse();
         StartNode start = Parser.START;
-
+        
         assertEquals(start, ret.ctrl());
         Node expr = ret.expr();
-        if (expr instanceof ConstantNode con) {
-            assertEquals(start, con.in(0));
+        if( expr instanceof ConstantNode con ) {
+            assertEquals(start,con.in(0));
             assertEquals(1, con._value);
         } else {
             fail();
@@ -44,16 +40,22 @@ public class Chapter01Test {
 
     @Test
     public void testBad1() {
-        exceptionRule.expect(RuntimeException.class);
-        exceptionRule.expectMessage("Syntax error, expected return: ret");
-        new Parser("ret").parse();
+        try { 
+            new Parser("ret").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error, expected return: ret",e.getMessage());
+        }
     }
 
     @Test
     public void testBad2() {
-        exceptionRule.expect(RuntimeException.class);
-        exceptionRule.expectMessage("Syntax error: integer values cannot start with '0'");
-        new Parser("return 0123;").parse();
+        try { 
+            new Parser("return 0123;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage());
+        }
     }
 
     @Test
@@ -65,9 +67,12 @@ public class Chapter01Test {
 
     @Test
     public void testBad4() {
-        exceptionRule.expect(RuntimeException.class);
-        exceptionRule.expectMessage("Syntax error, expected ;:");
-        new Parser("return 100").parse();
+        try { 
+            new Parser("return 100").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error, expected ;: ",e.getMessage());
+        }
     }
 
     // Negative numbers require unary operator support that is not in scope