Added PhiNode, RegionNode, IfNode, StopNode

No type compute yet
Initial parsing logic for If statements

10 files changed, 236 insertions, 15 deletions

diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
index 147515f6..331916fb 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
@@ -26,11 +26,21 @@ public class Parser {
     private final Lexer _lexer;
 
     /**
-     * Stack of lexical scopes, each scope is a symbol table that binds
+     * Current ScopeNode - ScopeNodes change as we parse code, but at any point of time
+     * there is one current ScopeNode. The reason the current ScopeNode can change is to do with how
+     * we handle branching. See {@link #parseIf()}.
+     *
+     * Each ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds
      * variable names to Nodes.  The top of this stack represents current scope.
+     *
+     * We keep a list of all ScopeNodes so that we can show them in graphs.
+     * @see #parseIf()
+     * @see #_allScopes
      */
     public ScopeNode _scope;
 
+    public List<ScopeNode> _allScopes = new ArrayList<>();
+
     public Parser(String source, TypeInteger arg) {
         _lexer = new Lexer(source);
         _scope = new ScopeNode();
@@ -90,10 +100,73 @@ public class Parser {
         if (match("return")) return parseReturn();
         else if (match("int")) return parseDecl();
         else if (match("{")) return parseBlock();
+        else if (match("if")) return parseIf();
         else if (match("#showGraph")) return showGraph();
         else return parseExpressionStatement();
     }
 
+    private Node parseIf() {
+        require("(");
+        // Parse predicate
+        var pred = require(parseExpression(), ")");
+        // IfNode takes current control and predicate
+        IfNode ifNode = new IfNode(_scope.lookup("$ctrl"), pred);
+        // Setup projection nodes
+        ProjNode ifT = new ProjNode(ifNode, 0, "ifT");
+        ProjNode ifF = new ProjNode(ifNode, 1, "ifF");
+        // In if true branch, the ifT proj node becomes the ctrl
+        // But first clone the scope and set it as current
+        ScopeNode savedScope = _scope;
+        ScopeNode ifScope = _scope.dup();  // Duplicate current scope
+        _allScopes.add(ifScope);           // For visualization we need all scopes
+        _scope = ifScope;                  // ifScope is current
+        _scope.define("$ctrl", ifT);
+        var thenStmt = parseStatement();
+        // restore scope
+        _scope = savedScope;
+        // Setup ifF as the ctrl
+        _scope.define("$ctrl", ifF);
+        Node elseStmt = null;
+        if (match("else")) elseStmt = parseStatement();
+        // Create region node and merge scopes
+        // If a var is in both scopes and different then we need to create PhiNode for it
+        // After merge _scope remains
+        RegionNode region = mergeScopes(ifT, ifScope, ifF, _scope);
+        _scope.update("$ctrl", region);
+        ifScope.clear();
+        _allScopes.remove(ifScope);
+        return region;
+    }
+
+    private RegionNode mergeScopes(ProjNode ifT, ScopeNode ifScope, ProjNode ifF, ScopeNode scope) {
+        RegionNode regionNode = new RegionNode(ifT, ifF);
+        Set<String> namesDone = new HashSet<>();
+        for (int level = ifScope._scopes.size()-1; level >= 0; level--) {
+            var tab = ifScope._scopes.get(level);
+            for (Map.Entry<String, Integer> e: tab.entrySet()) {
+                String name = e.getKey();
+                if (name.equals("$ctrl")) // ignore
+                    continue;
+                if (namesDone.contains(name)) // don't visit a name twice
+                    continue;
+                namesDone.add(name);
+                Integer idx = e.getValue();
+                Node ifTdef = ifScope.in(idx);
+                Node ifNdef = scope.lookup(name);
+                if (ifNdef == null)
+                    // The else scope didn't see this name
+                    scope.define(name, ifTdef); // Is this correct? Do we need same level as in ifScope?
+                else if (!ifTdef.equals(ifNdef)) {
+                    // Names are mapped to different nodes
+                    PhiNode phiNode = new PhiNode(regionNode, ifTdef, ifNdef);
+                    scope.update(name, phiNode);
+                }
+            }
+        }
+        return regionNode;
+    }
+
+
     /**
      * Parses a return statement; "return" already parsed.
      * The $ctrl edge is killed.
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java
new file mode 100644
index 00000000..460054ec
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -0,0 +1,31 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+
+public class IfNode extends MultiNode {
+
+    public IfNode(Node ctrl, Node pred) {
+        super(ctrl, pred);
+    }
+
+    @Override
+    public String label() {
+        return "If";
+    }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return sb;
+    }
+
+    @Override
+    public Type compute() {
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index e517c3d5..28d054a6 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -7,7 +7,5 @@ public abstract class MultiNode extends Node {
     public MultiNode(Node... inputs) {
         super(inputs);
     }
-    
-    // Return the ProjNode with the idx
-    abstract ProjNode proj(int idx);
+
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
index 8d698d1b..65ebef5b 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -4,6 +4,7 @@ import com.seaofnodes.simple.type.Type;
 
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.Objects;
 
 /**
  * All Nodes in the Sea of Nodes IR inherit from the Node class.
@@ -339,5 +340,17 @@ public abstract class Node {
     /*
      * hashCode and equals implementation to be added in later chapter.
      */
-  
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) return true;
+        if (o == null || getClass() != o.getClass()) return false;
+        Node node = (Node) o;
+        return _nid == node._nid && Objects.equals(_inputs, node._inputs) && Objects.equals(_type, node._type);
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(_nid, _inputs, _type);
+    }
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
new file mode 100644
index 00000000..25308724
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -0,0 +1,31 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+
+public class PhiNode extends Node {
+
+    public PhiNode(Node... inputs) {
+        super(inputs);
+    }
+
+    @Override
+    public String label() {
+        return "Phi";
+    }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return sb;
+    }
+
+    @Override
+    public Type compute() {
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java
new file mode 100644
index 00000000..96840ae5
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -0,0 +1,30 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+
+public class RegionNode extends Node implements Control {
+    public RegionNode(Node... inputs) {
+        super(inputs);
+    }
+
+    @Override
+    public String label() {
+        return "Region";
+    }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return sb;
+    }
+
+    @Override
+    public Type compute() {
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 8bd81e82..be5538a3 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -85,4 +85,22 @@ public class ScopeNode extends Node {
     }
 
 
+    public ScopeNode dup() {
+        ScopeNode sc = new ScopeNode();
+        for (HashMap<String, Integer> tab: _scopes) {
+            sc.push();
+            for (Map.Entry<String, Integer> e: tab.entrySet()) {
+                String name = e.getKey();
+                Integer idx = e.getValue();
+                Node n = in(idx);
+                sc.define(name, n);
+            }
+        }
+        return sc;
+    }
+
+    public void clear() {
+        while (!_scopes.empty())
+            pop();
+    }
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
index b59e3375..583cf054 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -33,14 +33,4 @@ public class StartNode extends MultiNode implements Control {
 
     @Override
     public Node idealize() { return null; }
-
-    
-    @Override 
-    public ProjNode proj( int idx ) {
-        for( Node proj : _outputs )
-            if( ((ProjNode)proj)._idx==idx )
-                return (ProjNode)proj;
-        return null;
-    }
-  
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
new file mode 100644
index 00000000..b710e160
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -0,0 +1,30 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+
+public class StopNode extends Node implements Control {
+    public StopNode(Node... inputs) {
+        super(inputs);
+    }
+
+    @Override
+    public String label() {
+        return "Stop";
+    }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return sb;
+    }
+
+    @Override
+    public Type compute() {
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+}
diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index 4106ef3b..858e2470 100644
--- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -14,6 +14,13 @@ public class Chapter05Test {
     public ExpectedException exceptionRule = ExpectedException.none();
 
     @Test
+    public void testChapter5IfStmt() {
+        Parser parser = new Parser("int a = 1; if (arg == 1) a = arg+2; else a = arg-3; return a;", TypeInteger.BOT);
+        ReturnNode ret = parser.parse();
+    }
+
+
+    @Test
     public void testChapter4Peephole() {
         Parser parser = new Parser("return 1+arg+2; #showGraph;", TypeInteger.BOT);
         ReturnNode ret = parser.parse();