Implement break and continue (#55)

* #52 Update chapter8 to align with chapter7

* #52 Update chapter8 to align with chapter7

* #52 Fix spacing

* #51 get started on break and continue

* #51 get started on break and continue

* #51 more on break and continue

* #51 more on break and continue

* #51 more on break and continue

* #51 more on break and continue

* #51 more on break and continue

* #51 more on break and continue

* break & continue scopes are made lazily, and merged into as discovered

Drop ContBreak.
Drop ScopeNode.addScope.
Add a simple mergeScopes.
Simplify Region.inProgress; drop from child classes, use in Region.
Add a ConstantNode.XCONTROL shortcut.

* Fix some regressions

* Error on dead code after break/continue

* A more robust dead-def check

* Fix for dead loop-back path

* Fix scope shadowing bug with continue/break

Turn on LAZY phis by default; fix minor golden test results

* Fix a case with both break & continue

* #51 more on break and continue

* #51 more on break and continue

* #51 more on break and continue

* #51 fix erroneous push of scope

* #51 fix import

* #51 update test expected results

* #51 Start Chapter8 writeup

* #51 Start Chapter8 writeup

* #51 _scope needs killing after continue

* Add graph evaluator (#56)

* #51 wip writeup

* #51 wip writeup

* #51 wip writeup

* #51 wip writeup

* #51 wip writeup

* #51 update code comments / add assertion

* #51 revert assertion

* #51 evaluate graph to verify test outcome

* #51 add code snippets

* #51 add examples

* Cleanup README

Comment for usefullness of true Loops.
Try to distiguish `PhiNode` as the programming construct from `phi` as the mathematically SSA notation.
Flow long lines.
Remove LAZY flag, set as `true`.  Fold up true tests.

* minor comment

* #51 Check _breakScope is not null when parsing break or continue to detect use outside of loop

* #51 in parseComparison we need to move the op= version above the op version, since at this time using <= and >= does not work since they are parsed as > and < with a preceeding = which causes an error

* #51 Update main README to link to chapter 8

* Remove useless test

---------

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>

6 files changed, 270 insertions, 73 deletions

diff --git a/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java
new file mode 100644
index 00000000..cbd6f1f9
--- /dev/null
+++ b/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java
@@ -0,0 +1,175 @@
+package com.seaofnodes.simple;

+

+import com.seaofnodes.simple.node.*;

+import com.seaofnodes.simple.type.TypeInteger;

+

+import java.util.Arrays;

+import java.util.BitSet;

+import java.util.HashMap;

+

+public class GraphEvaluator {

+

+    /**

+     * Find the start node from some node in the graph or null if there is no start node

+     */

+    private static StartNode findStart(BitSet visit, Node node) {

+        if (node == null) return null;

+        if (node instanceof StartNode start) return start;

+        if( visit.get(node._nid) ) return null;

+        visit.set(node._nid);

+        for( Node def : node._inputs ) {

+            var res = findStart(visit,def);

+            if( res != null ) return res;

+        }

+        for( Node use : node._outputs ) {

+            var res = findStart(visit,use);

+            if( res != null ) return res;

+        }

+        return null;

+    }

+

+    /**

+     * Find the control output from a control node

+     */

+    private static Node findControl(Node control) {

+        for( Node use : control._outputs ) {

+            if (use.isCFG()) return use;

+        }

+        return null;

+    }

+

+    /**

+     * Find the projection for a node

+     */

+    private static ProjNode findProjection(Node node, int idx) {

+        for( Node use : node._outputs ) {

+            if (use instanceof ProjNode proj && proj._idx == idx) return proj;

+        }

+        return null;

+    }

+

+    private static RuntimeException timeout() {

+        return new RuntimeException("Timeout");

+    }

+

+    /**

+     * Cache values for phi and parameter projection nodes.

+     */

+    private final HashMap<Node, Long> cacheValues = new HashMap<>();

+    /**

+     * Cache for loop phis as they can depend on itself or other loop phis

+     */

+    private long[] loopPhiCache = new long[16];

+

+    private GraphEvaluator() {

+    }

+

+    private long div(DivNode div) {

+        long in2 = getValue(div.in(2));

+        return in2 == 0 ? 0 : getValue(div.in(1)) / in2;

+    }

+

+    /**

+     * Calculate the value of a node

+     */

+    private long getValue(Node node) {

+        var cache = cacheValues.get(node);

+        if (cache != null) return cache;

+        return switch (node) {

+            case ConstantNode cons  -> ((TypeInteger)cons.compute()).value();

+            case AddNode      add   -> getValue(add.in(1)) + getValue(add.in(2));

+            case BoolNode.EQ  eq    -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0;

+            case BoolNode.LE  le    -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0;

+            case BoolNode.LT  lt    -> getValue(lt.in(1)) <  getValue(lt.in(2)) ? 1 : 0;

+            case DivNode      div   -> div(div);

+            case MinusNode    minus -> -getValue(minus.in(1));

+            case MulNode      mul   -> getValue(mul.in(1)) * getValue(mul.in(2));

+            case NotNode      not   -> getValue(not.in(1)) == 0 ? 1 : 0;

+            case SubNode      sub   -> getValue(sub.in(1)) - getValue(sub.in(2));

+            default                 -> throw Utils.TODO("Unexpected node " + node);

+        };

+    }

+

+    /**

+     * Special case of latchPhis when phis can depend on phis of the same region.

+     */

+    private void latchLoopPhis(RegionNode region, Node prev) {

+        int idx = Utils.find(region._inputs, prev);

+        assert idx > 0;

+        int i = 0;

+        for( Node use : region._outputs ) {

+            if (use instanceof PhiNode phi) {

+                var value = getValue(phi.in(idx));

+                if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2);

+                loopPhiCache[i++] = value;

+            }

+        }

+        i = 0;

+        for( Node use : region._outputs ) {

+            if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]);

+        }

+    }

+

+    /**

+     * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region.

+     */

+    private void latchPhis(RegionNode region, Node prev) {

+        int idx = Utils.find(region._inputs, prev);

+        assert idx > 0;

+        for( Node use : region._outputs ) {

+            if (use instanceof PhiNode phi) {

+                var value = getValue(phi.in(idx));

+                cacheValues.put(phi, value);

+            }

+        }

+    }

+

+    /**

+     * Run the graph until either a return is found or the number of loop iterations are done.

+     */

+    private long evaluate(StartNode start, long parameter, int loops) {

+        var parameter1 = findProjection(start, 1);

+        if (parameter1 != null) cacheValues.put(parameter1, parameter);

+        Node control = findProjection(start, 0);

+        Node prev = start;

+        while (control != null) {

+            Node next;

+            switch (control) {

+                case RegionNode region -> {

+                    if (region instanceof LoopNode && region.in(1) != prev) {

+                        if (loops--<=0) throw timeout();

+                        latchLoopPhis(region, prev);

+                    } else {

+                        latchPhis(region, prev);

+                    }

+                    next = findControl(region);

+                }

+                case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1);

+                case ReturnNode ret -> {

+                    return getValue(ret.in(1));

+                }

+                case ProjNode ignored -> next = findControl(control);

+                default -> throw Utils.TODO("Unexpected control node " + control);

+            }

+            prev = control;

+            control = next;

+        }

+        return 0;

+    }

+

+    public static long evaluate(Node graph) {

+        return evaluate(graph, 0);

+    }

+

+    public static long evaluate(Node graph, long parameter) {

+        return evaluate(graph, parameter, 1000);

+    }

+

+    public static long evaluate(Node graph, long parameter, int loops) {

+        var start = findStart(new BitSet(), graph);

+        if (start == null) throw timeout();

+        var evaluator = new GraphEvaluator();

+        return evaluator.evaluate(start, parameter, loops);

+    }

+

+}

diff --git a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java
index 41803f24..45332396 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java
@@ -13,7 +13,6 @@ import java.util.*;
  * This is a simple recursive descent parser. All lexical analysis is done here as well.
  */
 public class Parser {
-    public static boolean LAZY = false;
   
     /**
      * A Global Static, unique to each compilation.  This is a public, so we
@@ -47,6 +46,8 @@ public class Parser {
      * List of keywords disallowed as identifiers
      */
     private final HashSet<String> KEYWORDS = new HashSet<>(){{
+            add("break");
+            add("continue");
             add("else");
             add("false");
             add("if");
@@ -63,10 +64,14 @@ public class Parser {
      */
     public final Stack<ScopeNode> _xScopes = new Stack<>();
 
+    ScopeNode _continueScope;
+    ScopeNode _breakScope;
+
     public Parser(String source, TypeInteger arg) {
         Node.reset();
         _lexer = new Lexer(source);
         _scope = new ScopeNode();
+        _continueScope = _breakScope = null;
         START = new StartNode(new Type[]{ Type.CONTROL, arg });
         STOP = new StopNode();
     }
@@ -137,6 +142,8 @@ public class Parser {
         else if (match ("{"  )) return require(parseBlock(),"}");
         else if (matchx("if" )) return parseIf();
         else if (matchx("while")) return parseWhile();
+        else if (matchx("break")) return parseBreak();
+        else if (matchx("continue")) return parseContinue();
         else if (matchx("#showGraph")) return require(showGraph(),";");
         else return parseExpressionStatement();
     }
@@ -150,65 +157,104 @@ public class Parser {
      * @return a {@link Node}, never {@code null}
      */
     private Node parseWhile() {
+
+        var savedContinueScope = _continueScope;
+        var savedBreakScope    = _breakScope;
+
         require("(");
 
         // Loop region has two control inputs, the first is the entry
         // point, and second is back edge that is set after loop is parsed
         // (see end_loop() call below).  Note that the absence of back edge is
         // used as an indicator to switch off peepholes of the region and
-        // associated phis.
+        // associated phis; see {@code inProgress()}.
 
-        ctrl(new LoopNode(ctrl(),null).peephole()); // Note we set back edge to null here
+        ctrl(new LoopNode(ctrl()).peephole()); // Note we set back edge to null here
 
         // At loop head, we clone the current Scope (this includes all
         // names in every nesting level within the Scope).
         // We create phis eagerly for all the names we find, see dup().
 
         // Save the current scope as the loop head
-        ScopeNode head = _xScopes.push(_scope).keep();
+        ScopeNode head = _scope.keep();
         // Clone the head Scope to create a new Scope for the body.
         // Create phis eagerly as part of cloning
-        _scope = _scope.dup(true); // The true argument triggers creating phis
+        _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis
 
         // Parse predicate
         var pred = require(parseExpression(), ")");
         // IfNode takes current control and predicate
-        IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).<IfNode>keep().peephole();
+        IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole();
         // Setup projection nodes
         Node ifT = new ProjNode(ifNode, 0, "True" ).peephole();
         ifNode.unkeep();
         Node ifF = new ProjNode(ifNode, 1, "False").peephole();
 
-        // Clone the body Scope to create the exit Scope
-        // which accounts for any side effects in the predicate
-        // The exit Scope will be the final scope after the loop,
-        // And its control input is the False branch of the loop predicate
-        // Note that body Scope is still our current scope
-        var exit = _scope.dup();
-        _xScopes.push(exit);
-        exit.ctrl(ifF);
+        // Clone the body Scope to create the break/exit Scope which accounts for any
+        // side effects in the predicate.  The break/exit Scope will be the final
+        // scope after the loop, and its control input is the False branch of
+        // the loop predicate.  Note that body Scope is still our current scope.
+        ctrl(ifF);
+        _xScopes.push(_breakScope = _scope.dup());
 
+        // No continues yet
+        _continueScope = null;
+        
         // Parse the true side, which corresponds to loop body
         // Our current scope is the body Scope
         ctrl(ifT);              // set ctrl token to ifTrue projection
         parseStatement();       // Parse loop body
 
-        // The true branch loops back, so whatever is current control (_scope.ctrl) gets
-        // added to head loop as input. endLoop() updates the head scope,
-        // and goes through all the phis that were created earlier. For each
-        // phi, it sets the second input to the corresponding input from the back edge.
-        // If the phi is redundant, it is replaced by its sole input.
+        // Merge the loop bottom into other continue statements
+        if (_continueScope != null) {
+            _continueScope = jumpTo(_continueScope);
+            _scope.kill();
+            _scope = _continueScope;
+        }
+
+        // The true branch loops back, so whatever is current _scope.ctrl gets
+        // added to head loop as input.  endLoop() updates the head scope, and
+        // goes through all the phis that were created earlier.  For each phi,
+        // it sets the second input to the corresponding input from the back
+        // edge.  If the phi is redundant, it is replaced by its sole input.
+        var exit = _breakScope;
         head.endLoop(_scope, exit);
         head.unkeep().kill();
 
         _xScopes.pop();       // Cleanup
         _xScopes.pop();       // Cleanup
 
+        _continueScope = savedContinueScope;
+        _breakScope = savedBreakScope;
+
         // At exit the false control is the current control, and
         // the scope is the exit scope after the exit test.
-        return (_scope = exit);
+        return _scope = exit;
     }
 
+    private ScopeNode jumpTo(ScopeNode toScope) {
+        ScopeNode cur = _scope.dup();
+        ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope
+        // Prune nested lexical scopes that have depth > than the loop head
+        // We use _breakScope as a proxy for the loop head scope to obtain the depth
+        while( cur._scopes.size() > _breakScope._scopes.size() )
+            cur.pop();
+        // If this is a continue then first time the target is null
+        // So we just use the pruned current scope as the base for the
+        // continue
+        if (toScope == null)
+            return cur;
+        // toScope is either the break scope, or a scope that was created here
+        assert toScope._scopes.size() <= _breakScope._scopes.size();
+        toScope.mergeScopes(cur);
+        return toScope;
+    }
+
+    private void checkLoopActive() { if (_breakScope == null) throw Parser.error("No active loop for a break or continue"); }
+
+    private Node parseBreak   () { checkLoopActive(); return (   _breakScope = require(jumpTo(    _breakScope ),";"));  }
+    private Node parseContinue() { checkLoopActive(); return (_continueScope = require(jumpTo( _continueScope ),";"));  }
+
     /**
      * Parses a statement
      *
@@ -339,10 +385,10 @@ public class Parser {
         var lhs = parseAddition();
         if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole();
         if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole();
-        if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole();
         if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole();
-        if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole();
+        if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole();
         if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole();
+        if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole();
         return lhs;
     }
 
@@ -439,7 +485,7 @@ public class Parser {
 
     // Require an exact match
     private void require(String syntax) { require(null, syntax); }
-    private Node require(Node n, String syntax) {
+    private <N extends Node> N require(N n, String syntax) {
         if (match(syntax)) return n;
         throw errorSyntax(syntax);
     }
@@ -448,7 +494,7 @@ public class Parser {
         return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken());
     }
 
-    static RuntimeException error(String errorMessage) {
+    public static RuntimeException error( String errorMessage ) {
         return new RuntimeException(errorMessage);
     }
 
diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index eaf19199..0ed32464 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -6,7 +6,7 @@ import java.util.BitSet;
 
 public class LoopNode extends RegionNode {
 
-    public LoopNode( Node entry, Node back) { super(null,entry,back); }
+    public LoopNode( Node entry ) { super(null,entry,null); }
 
     Node entry() { return in(1); }
     Node back () { return in(2); }
@@ -15,21 +15,9 @@ public class LoopNode extends RegionNode {
     public String label() { return "Loop"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb, BitSet visited) {
-        return sb.append("Loop").append(_nid);
-    }
-    
-    @Override
-    public Type compute() {
-        return inProgress() ? Type.CONTROL : super.compute();
-    }
-    
-    @Override
     public Node idealize() {
         return inProgress() ? null : super.idealize();
     }
 
-    @Override Node idom() { return entry(); }
-    
-    @Override public boolean inProgress() { return back()==null; }    
+    @Override Node idom() { return entry(); }    
 }
diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java
index 4cd1b3d2..52d4c1e4 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -153,8 +153,6 @@ public abstract class Node {
 
     public int nIns() { return _inputs.size(); }
 
-    public Node out(int i) { return _outputs.get(i); }
-
     public int nOuts() { return _outputs.size(); }
 
     public boolean isUnused() { return nOuts() == 0; }
@@ -229,11 +227,11 @@ public abstract class Node {
     // Error is 'use' does not exist; ok for 'use' to be null.
     protected boolean delUse( Node use ) {
         Utils.del(_outputs, Utils.find(_outputs, use));
-        return _outputs.size() == 0;
+        return _outputs.isEmpty();
     }
 
     // Shortcut for "popping" n nodes.  A "pop" is basically a
-    // set_def(last,null) followed by lowering the nIns() count.
+    // setDef(last,null) followed by lowering the nIns() count.
     void popN(int n) {
         for( int i=0; i<n; i++ ) {
             Node old_def = _inputs.removeLast();
@@ -443,7 +441,10 @@ public abstract class Node {
      * 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; _disablePeephole=false; }
+    public static void reset() {
+        UNIQUE_ID = 1;
+        _disablePeephole=false;
+    }
 
     /**
      * Debugging utility to find a Node by index
diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index 3b793758..00c010b2 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -7,8 +7,9 @@ import java.util.Collection;
 import java.util.BitSet;
 
 public class RegionNode extends Node {
-    public RegionNode(Node... inputs) { super(inputs); }
 
+    public RegionNode(Node... nodes) { super(nodes); }
+    
     @Override
     public String label() { return "Region"; }
 
@@ -22,6 +23,7 @@ public class RegionNode extends Node {
 
     @Override
     public Type compute() {
+        if( inProgress() ) return Type.CONTROL;
         Type t = Type.XCONTROL;
         for (int i = 1; i < nIns(); i++)
             t = t.meet(in(i)._type);
@@ -30,6 +32,7 @@ public class RegionNode extends Node {
 
     @Override
     public Node idealize() {
+        if( inProgress() ) return null;
         int path = findDeadInput();
         if( path != 0 ) {
             for( Node phi : _outputs )
@@ -77,5 +80,8 @@ public class RegionNode extends Node {
         return (_idom=lhs);
     }
 
-    public boolean inProgress() { return false; }
+    // True if last input is null
+    public final boolean inProgress() {
+        return in(nIns()-1) == null;
+    }
 }
diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 38dfe15d..dfd12253 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -164,25 +164,13 @@ public class ScopeNode extends Node {
             dup._scopes.push(new HashMap<>(syms));
 
         dup.addDef(ctrl());      // Control input is just copied
-        for( int i=1; i<nIns(); i++ ) {
-            if ( !loop ) { dup.addDef(in(i)); }
-            else if (Parser.LAZY) {
-                // For lazy phi we need to set a sentinel that will
-                // trigger phi creation on update
-                dup.addDef(this); // Add a sentinel which is self
-            }
-            else {
-                String[] names = reverseNames(); // Get the variable names
-                // Create a phi node with second input as null - to be filled in
-                // by endLoop() below
-                dup.addDef(new PhiNode(names[i], ctrl(), in(i), null).peephole());
-                // Ensure our node has the same phi in case we created one
-                setDef(i, dup.in(i));
-            }
-        }
+        for( int i=1; i<nIns(); i++ )
+            // For lazy phis on loops we use a sentinel
+            // that will trigger phi creation on update
+            dup.addDef(loop ? this : in(i));
         return dup;
     }
-    
+
     /**
      * Merges the names whose node bindings differ, by creating Phi node for such names
      * The names could occur at all stack levels, but a given name can only differ in the
@@ -195,18 +183,11 @@ public class ScopeNode extends Node {
         RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep());
         String[] ns = reverseNames();
         // Note that we skip i==0, which is bound to '$ctrl'
-        for (int i = 1; i < nIns(); i++) {
-            if( in(i) != that.in(i) ) { // No need for redundant Phis
+        for (int i = 1; i < nIns(); i++)
+            if( in(i) != that.in(i) ) // No need for redundant Phis
                 // If we are in lazy phi mode we need to a lookup
-                // by name as it will triger a phi creation
-                Node phi;
-                if (Parser.LAZY)
-                    phi = new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole();
-                else
-                   phi = new PhiNode(ns[i], r, in(i), that.in(i)).peephole();
-                setDef(i, phi);
-            }
-        }
+                // by name as it will trigger a phi creation
+                setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole());
         that.kill();            // Kill merged scope
         return r.unkeep().peephole();
     }