Chapter 8: Lazy Phis, Break, Continue, and Evaluator

Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Co-authored-by: Darrick Wiebe <darrickw@untether.ai>

22 files changed, 1371 insertions, 62 deletions

diff --git a/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java
new file mode 100644
index 00000000..f5694a78
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java
@@ -0,0 +1,181 @@
+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 {
+
+    public enum ResultType { VALUE, FALLTHROUGH, TIMEOUT }
+
+    public record Result(ResultType type, long value) {}
+
+    /**
+     * 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;
+    }
+
+    /**
+     * 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 Result 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) return new Result(ResultType.TIMEOUT, 0);
+                        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 new Result(ResultType.VALUE, getValue(ret.in(1)));
+                }
+                case ProjNode ignored -> next = findControl(control);
+                default -> throw Utils.TODO("Unexpected control node " + control);
+            }
+            prev = control;
+            control = next;
+        }
+        return new Result(ResultType.FALLTHROUGH, 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 res = evaluateWithResult(graph, parameter, loops);
+        if (res.type==ResultType.TIMEOUT) throw new RuntimeException("Timeout");
+        return res.value;
+    }
+
+    public static Result evaluateWithResult(Node graph, long parameter, int loops) {
+        var start = findStart(new BitSet(), graph);
+        if (start == null) return new Result(ResultType.TIMEOUT, 0);
+        var evaluator = new GraphEvaluator();
+        return evaluator.evaluate(start, parameter, loops);
+    }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index 07f1af21..d75e5bea 100644
--- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -26,7 +26,7 @@ public class GraphVisualizer {
         // nodes in the graph.
         Collection<Node> all = findAll(parser);
         StringBuilder sb = new StringBuilder();
-        sb.append("digraph chapter07 {\n");
+        sb.append("digraph chapter08 {\n");
         sb.append("/*\n");
         sb.append(parser.src());
         sb.append("\n*/\n");
@@ -212,6 +212,8 @@ public class GraphVisualizer {
             for( String name : syms.keySet() ) {
                 int idx = syms.get(name);
                 Node def = scope.in(idx);
+                while( def instanceof ScopeNode lazy )
+                    def = lazy.in(idx);
                 if( def==null ) continue;
                 sb.append("\t")
                   .append(scopeName).append(":")
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index cfb4deb4..69796828 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -46,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");
@@ -62,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();
     }
@@ -136,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 if (matchx(";")) return null; // Empty statement
         else return parseExpressionStatement();
@@ -150,6 +158,10 @@ 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
@@ -179,36 +191,71 @@ public class Parser {
         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
      *
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 8f3e5a98..84a368fd 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -70,6 +70,11 @@ public class AddNode extends Node {
 
         // Now we only see (add add non)
 
+        // Dead data cycle; comes about from dead infinite loops.  Do nothing,
+        // the loop will peep as dead after a bit.
+        if( lhs.in(1) == lhs )
+            return null;
+
         // Do we have (x + con1) + con2?
         // Replace with (x + (con1+con2) which then fold the constants
         if( lhs.in(2)._type.isConstant() && t2.isConstant() )
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 0f414c08..23a8fafc 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -46,7 +46,7 @@ public class IfNode extends MultiNode {
             return prior instanceof ProjNode proj
               // Repeated test, dominated on one side.  Test result is the same.
               ? (proj._idx==0 ? TypeTuple.IF_TRUE : TypeTuple.IF_FALSE)
-              : null;           // Repeated test not dominated on one side
+              : dom._type;      // Repeated test not dominated on one side
 
         return TypeTuple.IF_BOTH;
     }
diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index 81f707ec..c192bc20 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -16,7 +16,8 @@ public class LoopNode extends RegionNode {
 
     @Override
     public Type compute() {
-        return inProgress() ? Type.CONTROL : super.compute();
+        if( inProgress() ) return Type.CONTROL;
+        return entry()._type;
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 5759a065..234930b4 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.IRPrinter;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
@@ -100,6 +101,7 @@ public abstract class Node {
     public final String print() {
         return _print0(new StringBuilder(), new BitSet()).toString();
     }
+
     // This is the common print: check for repeats, check for DEAD and print
     // "DEAD" else call the per-Node print1.
     final StringBuilder _print0(StringBuilder sb, BitSet visited) {
@@ -138,6 +140,8 @@ public abstract class Node {
         sb.append("\n");
     }
 
+    public String p(int depth) { return IRPrinter.prettyPrint(this,depth); }
+
     public boolean isMultiHead() { return false; }
     public boolean isMultiTail() { return false; }
 
@@ -153,8 +157,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; }
@@ -443,7 +445,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/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 2a4ff52a..c7b5b357 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -85,10 +85,13 @@ public class PhiNode extends Node {
      */
     private Node singleUniqueInput() {
         Node live = null;
-        for( int i=1; i<nIns(); i++ )
+        for( int i=1; i<nIns(); i++ ) {
+            if( region() instanceof LoopNode loop && loop.entry()._type == Type.XCONTROL )
+                return null;    // Dead entry loops just ignore and let the loop collapse
             if( region().in(i)._type != Type.XCONTROL && in(i) != this )
                 if( live == null || live == in(i) ) live = in(i);
                 else return null;
+        }
         return live;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index acaadaf1..453d028f 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -3,6 +3,7 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
+import java.util.Collection;
 import java.util.BitSet;
 
 public class RegionNode extends Node {
diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index a4fcbe65..e5d03d93 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -39,6 +39,10 @@ public class ScopeNode extends Node {
         for( int j=0; j<nIns(); j++ ) {
             sb.append(names[j]).append(":");
             Node n = in(j);
+            while( n instanceof ScopeNode loop ) {
+                sb.append("Lazy_");
+                n = loop.in(j);
+            }
             n._print0(sb, visited).append(" ");
         }
         sb.setLength(sb.length()-1);
@@ -107,8 +111,18 @@ public class ScopeNode extends Node {
         var idx = syms.get(name);
         if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope
         Node old = in(idx);
-        // If n is null we are looking up rather than updating, hence return existing value
-        return n==null ? old : setDef(idx,n);
+        if( old instanceof ScopeNode loop ) {
+            // Lazy Phi!
+            old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region()
+                // Loop already has a real Phi, use it
+                ? loop.in(idx)
+                // Set real Phi in the loop head
+                // The phi takes its one input (no backedge yet) from a recursive
+                // lookup, which might have insert a Phi in every loop nest.
+                : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole());
+            setDef(idx,old);
+        }
+        return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer
     }
 
     public Node ctrl() { return in(0); }
@@ -131,6 +145,11 @@ public class ScopeNode extends Node {
      * tables), nor deep (would dup the Scope, the HashMap tables, but then
      * also the program Nodes).
      * <p>
+     * If the {@code loop} flag is set, the edges are filled in as the original
+     * Scope, as a indication of Lazy Phis at loop heads.  The goal here is to
+     * not make Phis at loop heads for variables which are never touched in the
+     * loop body.
+     * <p>
      * The new Scope is a full-fledged Node with proper use<->def edges.
      */
     public ScopeNode dup() { return dup(false); }
@@ -144,17 +163,10 @@ 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 {
-                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;
     }
 
@@ -172,7 +184,9 @@ public class ScopeNode extends Node {
         // 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
-                setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole());
+                // If we are in lazy phi mode we need to a lookup
+                // 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();
     }
@@ -184,14 +198,26 @@ public class ScopeNode extends Node {
         assert ctrl instanceof LoopNode loop && loop.inProgress();
         ctrl.setDef(2,back.ctrl());
         for( int i=1; i<nIns(); i++ ) {
-            PhiNode phi = (PhiNode)in(i);
-            assert phi.region()==ctrl && phi.in(2)==null;
-            phi.setDef(2,back.in(i));
-            // Do an eager useless-phi removal
-            Node in = phi.peephole();
-            if( in != phi )
-                phi.subsume(in);
+            if( back.in(i) != this ) {
+                PhiNode phi = (PhiNode)in(i);
+                assert phi.region()==ctrl && phi.in(2)==null;
+                phi.setDef(2,back.in(i));
+            }
+            if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also
+                exit.setDef(i,in(i));
         }
         back.kill();            // Loop backedge is dead
+        // Now one-time do a useless-phi removal
+        for( int i=1; i<nIns(); i++ ) {
+            if( in(i) instanceof PhiNode phi ) {
+                // Do an eager useless-phi removal
+                Node in = phi.peephole();
+                if( in != phi ) {
+                    phi.subsume(in);
+                    setDef(i,in); // Set the update back into Scope
+                }
+            }
+        }
+
     }
 }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java
index 547c36f8..13b42f96 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java
@@ -31,7 +31,7 @@ public class Chapter01Test {
         parser.parse();
         StartNode start = Parser.START;
         for( Node use : start._outputs )
-            if( use instanceof ConstantNode con )
+            if( use instanceof ConstantNode con && con._type instanceof TypeInteger )
                 assertEquals(TypeInteger.constant(0),con._type);
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
index 1e67cef5..64ff153e 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -31,7 +31,7 @@ public class Chapter03Test {
 
     @Test
     public void testVarScopeNoPeephole() {
-        Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;");
+        Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;  } return c; ");
         Node._disablePeephole = true;
         StopNode ret = parser.parse();
         Node._disablePeephole = false;
@@ -40,7 +40,7 @@ public class Chapter03Test {
 
     @Test
     public void testVarDist() {
-        Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);");
+        Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); ");
         StopNode ret = parser.parse();
         assertEquals("return 8;", ret.print());
     }
@@ -54,7 +54,7 @@ public class Chapter03Test {
             assertEquals("Undefined name 'a'",e.getMessage());
         }
     }
-    
+
     @Test
     public void testRedeclareVar() {
         try {
diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
index 98878ca6..2e2abb25 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
@@ -10,7 +10,7 @@ public class Chapter04Test {
 
     @Test
     public void testPeephole() {
-        Parser parser = new Parser("return 1+arg+2;");
+        Parser parser = new Parser("return 1+arg+2; ");
         StopNode ret = parser.parse();
         assertEquals("return (arg+3);", ret.print());
     }
@@ -38,7 +38,7 @@ public class Chapter04Test {
 
     @Test
     public void testPeephole3() {
-        Parser parser = new Parser("return 1+arg+2+arg+3;");
+        Parser parser = new Parser("return 1+arg+2+arg+3; ");
         StopNode ret = parser.parse();
         assertEquals("return ((arg*2)+6);", ret.print());
     }
@@ -52,7 +52,7 @@ public class Chapter04Test {
 
     @Test
     public void testVarArg() {
-        Parser parser = new Parser("return arg;");
+        Parser parser = new Parser("return arg; ");
         StopNode stop = parser.parse();
         ReturnNode ret = stop.ret();
         assertTrue(ret.in(0) instanceof ProjNode);
@@ -61,49 +61,49 @@ public class Chapter04Test {
 
     @Test
     public void testConstantArg() {
-        Parser parser = new Parser("return arg;", TypeInteger.constant(2));
+        Parser parser = new Parser("return arg; ", TypeInteger.constant(2));
         StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
     }
 
     @Test
     public void testCompEq() {
-        Parser parser = new Parser("return 3==3;");
+        Parser parser = new Parser("return 3==3; ");
         StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testCompEq2() {
-        Parser parser = new Parser("return 3==4;");
+        Parser parser = new Parser("return 3==4; ");
         StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testCompNEq() {
-        Parser parser = new Parser("return 3!=3;");
+        Parser parser = new Parser("return 3!=3; ");
         StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testCompNEq2() {
-        Parser parser = new Parser("return 3!=4;");
+        Parser parser = new Parser("return 3!=4; ");
         StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testBug1() {
-        Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2;");
+        Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; ");
         StopNode ret = parser.parse();
         assertEquals("return (arg+3);", ret.print());
     }
 
     @Test
     public void testBug2() {
-        Parser parser = new Parser("int a=arg+1; a=a; return a;");
+        Parser parser = new Parser("int a=arg+1; a=a; return a; ");
         StopNode ret = parser.parse();
         assertEquals("return (arg+1);", ret.print());
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index 5bb67817..68d379a1 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -17,7 +17,9 @@ if (arg == 1)
     a = arg+2;
 else {
     a = arg-3;
+
 }
+
 return a;""");
         StopNode ret = parser.parse();
         assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString());
diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
index 00d725bc..b858b83e 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -29,7 +29,7 @@ if (arg)
     a = 2;
 return (arg < a) < 3;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse(false);
         assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString());
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
index 189fcf66..d691672e 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
@@ -37,7 +37,7 @@ if(arg){}else{
 return a;
 """);
         StopNode stop = parser.parse();
-        assertEquals("return Phi(Region23,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString());
+        assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString());
     }
 
     @Test
@@ -57,7 +57,7 @@ while(i < arg) {
 return sum;
 """);
         StopNode stop = parser.parse();
-        assertEquals("return Phi(Loop8,0,Phi(Loop21,Phi_sum,(Phi(Loop,0,(Phi_j+1))+Phi_sum)));", stop.toString());
+        assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString());
     }
 
     @Test
@@ -74,7 +74,7 @@ return b;
 """);
         Node._disablePeephole = true;
         StopNode stop = parser.parse();
-        assertEquals("return Phi(Loop8,2,Phi(Region27,Phi_b,4));", stop.toString());
+        assertEquals("return Phi(Loop8,2,Phi(Region26,Phi_b,4));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
         Node._disablePeephole = false;
     }
@@ -94,7 +94,7 @@ while(a < 10) {
 return b;
 """);
         StopNode stop = parser.parse();
-        assertEquals("return Phi(Loop8,2,(Phi(Region27,Phi_b,4)+1));", stop.toString());
+        assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
 
@@ -156,7 +156,7 @@ int a = 1;
 while(arg) a = 2;
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse(false);
         assertEquals("return Phi(Loop7,1,2);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
new file mode 100644
index 00000000..5d9d1545
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
@@ -0,0 +1,218 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.Ignore;
+
+import static org.junit.Assert.*;
+
+public class Chapter08Test {
+
+    @Test
+    @Ignore
+    public void testJig() {
+        Parser parser = new Parser("""
+// Insert test case here
+""");
+        StopNode stop = parser.parse();
+    }
+
+    @Test
+    public void testEx6() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        break;
+    if (arg == 6)
+        break;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse();
+        assertEquals("return Phi(Region36,Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add),Add);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+        Assert.assertEquals(5, GraphEvaluator.evaluate(stop, 1));
+        Assert.assertEquals(10, GraphEvaluator.evaluate(stop, 6));
+    }
+
+
+    @Test
+    public void testEx5() {
+        Parser parser = new Parser(
+                """
+int a = 1;
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        continue;
+    if (arg == 7)
+        continue;
+    a = a + 1;
+}
+return a;
+                """);
+        StopNode stop = parser.parse();
+        assertEquals("return Phi(Loop7,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+
+    @Test
+    public void testEx4() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        continue;
+    if (arg == 6)
+        break;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse();
+        assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+    }
+
+    @Test
+    public void testEx3() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 6)
+        break;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse();
+        assertEquals("return Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+    }
+
+
+    @Test
+    public void testEx2() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        continue;
+    if (arg == 6)
+        continue;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse();
+        assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+
+    @Test
+    public void testEx1() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        continue;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse();
+        assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+    @Test
+    public void testRegress1() {
+        Parser parser = new Parser(
+                """
+while( arg < 10 ) {
+    int a = arg+2;
+    if( a > 4 )
+        break;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse();
+        assertEquals("return arg;", stop.toString());
+    }
+
+    @Test
+    public void testRegress2() {
+        Parser parser = new Parser("if(1) return 0;  else while(arg>--arg) arg=arg+1; return 0;");
+        StopNode stop = parser.parse();
+        assertEquals("Stop[ return 0; return 0; ]", stop.toString());
+    }
+
+    @Test
+    public void testBreakOutsideLoop() {
+        try {
+            new Parser("""
+if(arg <= 10) {
+    break;
+    arg = arg + 1;
+}
+return arg;
+""").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("No active loop for a break or continue",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testRegress3() {
+        Parser parser = new Parser("""
+while(arg < 10) {
+    break;
+}
+return arg;
+""");
+        StopNode stop = parser.parse();
+        assertEquals("return arg;", stop.toString());
+    }
+
+    @Test
+    public void testRegress4() {
+        Parser parser = new Parser("""
+int a = 1;
+while(arg < 10) {
+    a = a + 1;
+    if (arg > 2) {
+        int a = 17;
+        break;
+    }
+}
+return a;
+""");
+        StopNode stop = parser.parse();
+        assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+    }
+
+    @Test
+    public void testRegress5() {
+        Parser parser = new Parser("""
+int a = 1;
+while(1) {
+    a = a + 1;
+    if (a<10) continue;
+    break;
+}
+return a;
+""");
+        StopNode stop = parser.parse();
+        assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+    }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
new file mode 100644
index 00000000..82a6a472
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
@@ -0,0 +1,26 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.fuzzer.Fuzzer;
+import org.junit.Ignore;
+import org.junit.Test;
+
+
+import static org.junit.Assert.assertTrue;
+
+/**
+ * To use the fuzzer run the <code>fuzzPeeps</code> methods.
+ * This can be done from IntelliJ Gui or remove the `@Ignore` annotation and start the test case from the command line
+ * via <code>mvn clean test -Dtest=com.seaofnodes.simple.FuzzerWrap#fuzzPeeps</code>
+ */
+public class FuzzerWrap {
+
+    @Test
+    @Ignore
+    public void fuzzPeeps() {
+        var fuzzer = new Fuzzer();
+        for (int i=0; i<100000; i++)
+            fuzzer.fuzzPeeps(i);
+        assertTrue(fuzzer.noExceptions());
+    }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
new file mode 100644
index 00000000..5fcd8764
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
@@ -0,0 +1,128 @@
+package com.seaofnodes.simple.fuzzer;
+
+import com.seaofnodes.simple.GraphEvaluator;
+import com.seaofnodes.simple.node.StopNode;
+
+import java.util.ArrayList;
+import java.util.Random;
+import java.util.function.Consumer;
+
+/**
+ * Implementation of the fuzzer.
+ * Random testcases are generated using the ScriptGenerator.
+ * This will generate a script similar to how the parser parses it but instead of parsing it will
+ * randomly choose a variation the parser would parse and generate it.
+ * These scripts are the parsed by the parser and all exceptions are caught and filtered
+ * to only show one occurrence of one problem. This includes script which generate different
+ * results when the compiled graph with and without peeps is executed.
+ * To aid debugging scripts that cause errors are then reduced by applying rules and checking
+ * that the same issue persists.
+ */
+public class Fuzzer {
+
+    private static final int EVAL_TIMEOUT = 1000;
+
+    /**
+     * List of exceptions already encountered.
+     * This is used to filter new exceptions and discard them if they are already found.
+     */
+    private final ArrayList<Throwable> exceptions = new ArrayList<>();
+
+    /**
+     * Filter and record an exception in a script.
+     * @param e The exception caused by the script
+     * @param script The script causing the exception
+     * @param reproducer Reproducer which should be used to reproduce the test case.
+     */
+    private void recordException(Throwable e, String script, Consumer<String> reproducer) {
+        for (var ex : exceptions) {
+            if (FuzzerUtils.isExceptionFromSameCause(ex, e)) return;
+        }
+        exceptions.add(e);
+        System.out.println("========== Stack ==========");
+        e.printStackTrace(System.out);
+        System.out.println("========== Code ===========");
+        System.out.println(script);
+        System.out.println("========= Reduced =========");
+        System.out.println(Reducer.reduce(script, e, reproducer));
+        System.out.println("===========================");
+        System.out.flush();
+    }
+
+    /**
+     * Check that two graphs result in the same output when supplied with a value
+     * @param stop1 Stop node of the first graph
+     * @param stop2 Stop node of the second graph
+     * @param in The input value to both graphs to test for an equal output
+     */
+    private static void checkGraphs(StopNode stop1, StopNode stop2, long in) {
+        var e1 = GraphEvaluator.evaluateWithResult(stop1, in, EVAL_TIMEOUT);
+        var e2 = GraphEvaluator.evaluateWithResult(stop2, in, EVAL_TIMEOUT);
+        if (e1.type() == GraphEvaluator.ResultType.TIMEOUT || e2.type() == GraphEvaluator.ResultType.TIMEOUT) return;
+        if (e1.type() != e2.type())
+            throw new RuntimeException("Different calculations types " + e1.type() + " vs " + e2.type());
+        if (e1.value() != e2.value())
+            throw new RuntimeException("Different calculations values " + e1.value() + " vs " + e2.value());
+    }
+
+    /**
+     * Run checks for script. Compile the script with peeps enabled and disabled.
+     * Check that exceptions raised in the parser by both methods are the same and only happens if the script may be invalid.
+     * If the script was successfully parsed check that both version behave the same.
+     * @param script The script to test
+     * @param valid If the script is definitely valid. If not some exceptions may be suppressed.
+     */
+    private static void runCheck(String script, boolean valid) {
+        StopNode stop1;
+        try {
+            stop1 = FuzzerUtils.parse(script, false);
+        } catch (RuntimeException e1) {
+            try {
+                FuzzerUtils.parse(script, true);
+            } catch (RuntimeException e2) {
+                if (FuzzerUtils.isExceptionFromSameCause(e1, e2)) {
+                    if (!valid || e1.getClass() == RuntimeException.class) return;
+                } else {
+                    e1.addSuppressed(e2);
+                }
+            }
+            throw e1;
+        }
+        var stop2 = FuzzerUtils.parse(script, true);
+        checkGraphs(stop1, stop2, 0);
+        checkGraphs(stop1, stop2, 1);
+        checkGraphs(stop1, stop2, 10);
+    }
+
+    /**
+     * Check that the script does not result in exceptions.
+     * @param script The script to test.
+     * @param valid If the script is valid or if it might contain syntax errors.
+     */
+    private void check(String script, boolean valid) {
+        try {
+            runCheck(script, valid);
+        } catch (Throwable e) {
+            recordException(e, script, s->runCheck(s, valid));
+        }
+    }
+
+    /**
+     * Run one test with the given seed.
+     * @param seed The seed to use for generating this test case
+     */
+    public void fuzzPeeps(long seed) {
+        var rand = new Random(seed);
+        var sb = new StringBuilder();
+        var valid = new ScriptGenerator(rand, sb, false).genProgram();
+        check(sb.toString(), valid);
+    }
+
+    /**
+     * Check that no exceptions happened.
+     * @return true if no exception happened
+     */
+    public boolean noExceptions() {
+        return exceptions.isEmpty();
+    }
+}
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
new file mode 100644
index 00000000..37a57e11
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
@@ -0,0 +1,58 @@
+package com.seaofnodes.simple.fuzzer;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.node.StopNode;
+
+/**
+ * Some utilities for the fuzzer.
+ */
+class FuzzerUtils {
+
+    /**
+     * Check that eiter one of the objects is null or that both are equal.
+     */
+    private static boolean equalOrNull(Object a, Object b) {
+        if (a == null || b == null) return true;
+        return a.equals(b);
+    }
+
+    /**
+     * Check if both stack traces have the same first entry. Empty stack traces can happen with NPE optimization
+     * and allow the other to be any stack trace.
+     */
+    private static boolean sameStackTraceOrigin(StackTraceElement[] a, StackTraceElement[] b) {
+        if (a == null || a.length == 0 || b == null || b.length == 0) return true; // One or both stack traces are missing.
+        return a[0].equals(b[0]);
+    }
+
+    /**
+     * Checks if two exceptions are caused by the same problem.
+     */
+    public static boolean isExceptionFromSameCause(Throwable a, Throwable b) {
+        if (a == null || b == null) return a == b; // Handle the null case
+        if (a.getClass() != b.getClass()) return false; // Different classes
+        if (!equalOrNull(a.getMessage(), b.getMessage())) return false; // Different messages. Null is allowed as wildcard
+        var s1 = a.getStackTrace();
+        var s2 = b.getStackTrace();
+        if (!sameStackTraceOrigin(s1, s2)) return false; // Different stack trace origins
+        if (!isExceptionFromSameCause(a.getCause(), b.getCause())) return false; // Different causes
+        var o1 = a.getSuppressed();
+        var o2 = b.getSuppressed();
+        if (o1 == null || o2 == null || o1.length != o2.length) return o1 == o2; // Different suppression
+        for (int i=0; i<o1.length; i++) {
+            if (!isExceptionFromSameCause(o1[i], o2[i])) return false; // Different suppression
+        }
+        return true;
+    }
+
+    /**
+     * Parse script with peepholes enabled or disabled
+     */
+    public static StopNode parse(String script, boolean runPeeps) {
+        var parser = new Parser(script);
+        Node._disablePeephole = !runPeeps;
+        return parser.parse();
+    }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java
new file mode 100644
index 00000000..b7fc18ec
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java
@@ -0,0 +1,144 @@
+package com.seaofnodes.simple.fuzzer;
+
+import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.regex.Pattern;
+
+/**
+ * This class is used to reduce test cases created by the fuzzer.
+ * It applies rewrite rules to the test case and checks that the
+ * test still produces the same exception.
+ * This is done in a fixpoint iteration until every rewrite produces
+ * no or a different exception.
+ */
+public class Reducer {
+
+    /**
+     * Holder for the rewrite rules
+     */
+    private record Replace(Pattern p, String r) {}
+
+    /**
+     * List of rewrite rules.
+     */
+    private static final Replace[] REPLACEMENTS = {
+            new Replace(Pattern.compile("(?<=[+\\-*/<>=(])--"), ""),
+            new Replace(Pattern.compile("\\b--"), "+"),
+            new Replace(Pattern.compile("\\b\\+-"), "-"),
+            new Replace(Pattern.compile("\\bfalse\\b"), "0"),
+            new Replace(Pattern.compile("\\btrue\\b"), "1"),
+            new Replace(Pattern.compile("-"), ""),
+            new Replace(Pattern.compile("(?<![+\\-*/<>=])(?:-|\\*|/|>=|<=|>|<|!=|==)(?![+\\-*/<>=])"), "+"),
+            new Replace(Pattern.compile("\\{(?:[^{}]|\\{})+}"), "{}"),
+            new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)}"), "$1"),
+            new Replace(Pattern.compile("\\(([^()]+)\\)"), "$1"),
+            new Replace(Pattern.compile("\\b\\w+\\b"), "1"),
+            new Replace(Pattern.compile("\\b\\w+\\b"), "0"),
+            new Replace(Pattern.compile("\\d+\\+"), ""),
+            new Replace(Pattern.compile("\\+\\d+"), ""),
+            new Replace(Pattern.compile("(?<=\\n|^)[^\\n]*(?=\\n|$)"), "\n"),
+            new Replace(Pattern.compile("\\n+"), "\n"),
+            new Replace(Pattern.compile("^\\n+|\\n+$"), ""),
+            new Replace(Pattern.compile("else *"), ""),
+            new Replace(Pattern.compile("\\bif\\([^()]+\\) *"), ""),
+            new Replace(Pattern.compile("\\bwhile\\([^()]+\\) *"), ""),
+    };
+
+    /**
+     * Predicate to test if the reduced script generates the same error.
+     */
+    private final Predicate<String> tester;
+
+    /**
+     * Create a reducer with a test function.
+     * @param tester Test function which returns true when the same issue is found in the script.
+     */
+    private Reducer(Predicate<String> tester) {
+        this.tester = tester;
+    }
+
+    /**
+     * Rewrites the script with one rewrite rule.
+     */
+    private String doReplacement(String script, Pattern pattern, String with) {
+        var matcher = pattern.matcher(script);
+        var sb = new StringBuilder();
+        int last = 0;
+        while (matcher.find()) {
+            var pos = sb.length();
+            matcher.appendReplacement(sb, with);
+            var tail = sb.length();
+            matcher.appendTail(sb);
+            if (tester.test(sb.toString())) {
+                sb.setLength(tail);
+            } else {
+                sb.setLength(pos);
+                sb.append(script, last, matcher.end());
+            }
+            last = matcher.end();
+        }
+        matcher.appendTail(sb);
+        return sb.toString();
+    }
+
+    /**
+     * Clean up variable names from the random ones generated by the fuzzer.
+     */
+    private String cleanVariables(String script) {
+        var matcher = Pattern.compile("\\bint ([0-9a-zA-Z_]+)").matcher(script);
+        int num = 0;
+        while (matcher.find()) {
+            var var = matcher.group(1);
+            if (var.matches("v\\d+")) continue;
+            while (script.contains("v"+num)) num++;
+            var n = script.replaceAll("\\b"+var+"\\b", "v" + num);
+            if (tester.test(n)) {
+                script = n;
+            }
+        }
+        return script;
+    }
+
+    /**
+     * Run all rewrite rules once.
+     */
+    private String doAllReplacements(String script) {
+        for (var replace: REPLACEMENTS) {
+            script = doReplacement(script, replace.p, replace.r);
+        }
+        return script;
+    }
+
+    /**
+     * Reduce the script to a minimal version which produces the same problem with a test function.
+     * @param tester Test function which returns true when the same issue is found in the script.
+     */
+    public static String reduce(String script, Predicate<String> tester) {
+        var reducer = new Reducer(tester);
+        String old;
+        do {
+            old = script;
+            script = reducer.doAllReplacements(script);
+            script = reducer.cleanVariables(script);
+        } while (!script.equals(old));
+        return script;
+    }
+
+    /**
+     * Reduce the script to a minimal version which produces the same problem with a reproducer.
+     * @param ex The exception originally caused by the script
+     * @param reproducer Test function which throws an exception which will be checked against ex.
+     */
+    public static String reduce(String script, Throwable ex, Consumer<String> reproducer) {
+        return reduce(script, s->{
+            Throwable nex = null;
+            try {
+                reproducer.accept(s);
+            } catch (Throwable e) {
+                nex = e;
+            }
+            return FuzzerUtils.isExceptionFromSameCause(nex, ex);
+        });
+    }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
new file mode 100644
index 00000000..148c2319
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
@@ -0,0 +1,462 @@
+package com.seaofnodes.simple.fuzzer;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.node.ScopeNode;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Random;
+
+/**
+ * Generate a pseudo random script.
+ * This generator will generate the same script for two random number generators initialized with the same seed.
+ * To generate valid code it implements the parser but instead of parsing it emits the statements and expressions.
+ * It is guaranteed to terminate.
+ */
+public class ScriptGenerator {
+
+    /**
+     * Get the list of keywords from the parser.
+     */
+    @SuppressWarnings("unchecked")
+    private static HashSet<String> getKeywords() {
+        try {
+            var field = Parser.class.getDeclaredField("KEYWORDS");
+            field.setAccessible(true);
+            return (HashSet<String>) field.get(new Parser(""));
+        } catch (Throwable e) {
+            throw new ExceptionInInitializerError(e);
+        }
+    }
+
+    /**
+     * Number of spaces per indentation
+     */
+    private static final int INDENTATION = 4;
+    /**
+     * Valid characters for identifiers. The last 10 are not valid for the first character.
+     */
+    private static final String VAR_CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_0123456789";
+    /**
+     * List of keywords not valid for identifiers.
+     */
+    private static final HashSet<String> KEYWORDS = getKeywords();
+
+    /**
+     * Flag for a statement that it does not pass on control flow to the next statement.
+     */
+    private static final int FLAG_STOP = 0x01;
+    /**
+     * Flag for a statement that it contains a final if statement without an else branch.
+     */
+    private static final int FLAG_IF_WITHOUT_ELSE = 0x02;
+    /**
+     * Binary operators.
+     */
+    private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/"};
+    /**
+     * Unary operators.
+     */
+    private static final String[] UNARY_OP = {"-"};
+
+
+    /**
+     * The random number generator used for random decisions.
+     */
+    private final Random random;
+    /**
+     * Indentation depth.
+     */
+    private int indentation = 0;
+    /**
+     * Output string builder
+     */
+    private final StringBuilder sb;
+    /**
+     * Number of nested loops
+     */
+    private int loopDepth = 0;
+    /**
+     * Current scope start in the variables list.
+     */
+    private int currScopeStart = 0;
+    /**
+     * The depth of blocks allowed.
+     */
+    private int depth = 7;
+    /**
+     * The depth of expressions allowed.
+     */
+    private int exprDepth = 3;
+    /**
+     * Current variables in scope.
+     */
+    private final ArrayList<String> variables = new ArrayList<>();
+    /**
+     * If this needs to generate valid scripts or is also allowed to generate invalid ones.
+     */
+    private final boolean generateValid;
+    /**
+     * If this script might be invalid.
+     */
+    private boolean maybeInvalid = false;
+
+    /**
+     *
+     * @param random the random number generator.
+     * @param sb the script will be written to this string builder.
+     * @param generateValid if the script should be guaranteed valid or if it is allowed to contain bugs.
+     */
+    public ScriptGenerator(Random random, StringBuilder sb, boolean generateValid) {
+        this.random = random;
+        this.sb = sb;
+        this.generateValid = generateValid;
+    }
+
+    /**
+     * Random number with log distribution
+     * @param max The maximum value
+     * @return A random number in the range [0, max) with higher numbers being more uncommon.
+     */
+    private int randLog(int max) {
+        max--;
+        int n = 1<<max;
+        var num = random.nextInt(n);
+        for (int i=max-1; i>=0; i--) {
+            if ((num & (1<<i))!=0) return max-i-1;
+        }
+        return max;
+    }
+
+    /**
+     * Helper function to print indentation.
+     * @return sb for chaining
+     */
+    private StringBuilder printIndentation() {
+        return sb.repeat(' ', indentation);
+    }
+
+    /**
+     * Generate a random name for variables. This might be invalid when it is a keyword.
+     * @return The random name generated
+     */
+    private StringBuilder getRandomName() {
+        int len = random.nextInt(10) + 1;
+        StringBuilder sb = new StringBuilder(len);
+        sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()-10)));
+        for (int i=1; i<len; i++)
+            sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length())));
+        return sb;
+    }
+
+    /**
+     * Generate a variable name. This might be new random name or a name from an outer scope.
+     * If the program is allowed to be invalid this can return keywords and already used variable names in the current scope.
+     * @return The variable name.
+     */
+    private String getVarName() {
+        if (currScopeStart > 0 && random.nextInt(10) > 7) {
+            // Use a variable outside the current scope.
+            var v = variables.get(random.nextInt(currScopeStart));
+            if (variables.lastIndexOf(v) < currScopeStart) return v;
+            if (!generateValid) {
+                maybeInvalid = true;
+                return v;
+            }
+        }
+        // Generate a new random variable name
+        StringBuilder sb = getRandomName();
+        var v = sb.toString();
+        if (!generateValid && (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart)) {
+            maybeInvalid = true;
+            return v;
+        }
+        while (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart) {
+            sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length())));
+            v = sb.toString();
+        }
+        return v;
+    }
+
+
+
+    /**
+     * Generates a program and writes it into the string builder supplied in the constructor.
+     * @return If the program is allowed to be invalid returns if something potentially invalid was generated.
+     */
+    public boolean genProgram() {
+        this.maybeInvalid = false;
+        variables.add(ScopeNode.ARG0);
+        currScopeStart = variables.size();
+        if ((genStatements() & FLAG_STOP) == 0) {
+            if (generateValid || random.nextInt(10)<7) {
+                genReturn();
+            } else {
+                this.maybeInvalid = true;
+            }
+        }
+        return !this.maybeInvalid;
+    }
+
+    /**
+     * Generate a list of statements.
+     * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the last statement generated
+     */
+    public int genStatements() {
+        var num = random.nextInt(10);
+        for (int i=0; i<num; i++) {
+            printIndentation();
+            var stop = genStatement();
+            sb.append("\n");
+            if ((stop & FLAG_STOP) != 0) return stop;
+        }
+        return 0;
+    }
+
+    /**
+     * Generate a single statement
+     * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement
+     */
+    public int genStatement() {
+        return switch (random.nextInt(10)) {
+            case 1 -> genBlock();
+            case 2 -> genIf();
+            case 3 -> genWhile();
+            case 4, 5 -> genDecl();
+            case 6, 7, 8 -> genAssignment();
+            default -> genExit();
+        };
+    }
+
+    /**
+     * Generate a statement for if, else and while blocks.
+     * This is special since it disallows declarations and prefers to generate blocks.
+     * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement
+     */
+    public int genStatementBlock() {
+        indentation += INDENTATION;
+        int res;
+        if (depth == 0) {
+            res = random.nextBoolean() ? genAssignment() : genExit();
+        } else {
+            depth--;
+            res = switch (random.nextInt(10)) {
+                case 1, 2, 3, 4, 5 -> {
+                    depth++;
+                    indentation -= INDENTATION;
+                    var ret = genBlock();
+                    indentation += INDENTATION;
+                    depth--;
+                    yield ret;
+                }
+                case 6 -> genIf();
+                case 7 -> genWhile();
+                case 8 -> genAssignment();
+                default -> genExit();
+            };
+            depth++;
+        }
+        indentation -= INDENTATION;
+        return res;
+    }
+
+    /**
+     * Generate an exit. This can be return or break and continue when in a loop.
+     * @return FLAG_STOP
+     */
+    public int genExit() {
+        if (loopDepth == 0 && generateValid) return genReturn();
+        return switch (random.nextInt(7)) {
+            case 0,1,2 -> {
+                if (loopDepth == 0) maybeInvalid = true;
+                sb.append("continue;");
+                yield FLAG_STOP;
+            }
+            case 3,4,5 -> {
+                if (loopDepth == 0) maybeInvalid = true;
+                sb.append("break;");
+                yield FLAG_STOP;
+            }
+            default -> genReturn();
+        };
+    }
+
+    /**
+     * Generate a block statement. After a certain depth only empty blocks are generated to ensure termination of the generator.
+     * @return flag FLAG_STOP for the generated statement
+     */
+    public int genBlock() {
+        if (depth == 0) {
+            sb.append("{}");
+            return 0;
+        }
+        depth--;
+        int oldCSS = currScopeStart;
+        currScopeStart = variables.size();
+        sb.append("{\n");
+        indentation += INDENTATION;
+        var stop = genStatements();
+        indentation -= INDENTATION;
+        printIndentation().append("}");
+        while (variables.size() > currScopeStart)
+            variables.removeLast();
+        currScopeStart = oldCSS;
+        depth++;
+        return stop & ~FLAG_IF_WITHOUT_ELSE;
+    }
+
+    /**
+     * Generate an if statement with an optional else block.
+     * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement
+     */
+    public int genIf() {
+        sb.append("if(");
+        genExpression();
+        sb.append(") ");
+        var stop = genStatementBlock();
+        if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) {
+            sb.append("\n");
+            printIndentation().append("else ");
+            stop &= genStatementBlock();
+        } else {
+            stop = FLAG_IF_WITHOUT_ELSE;
+        }
+        return stop;
+    }
+
+    /**
+     * Generate a while loop.
+     * @return 0
+     */
+    public int genWhile() {
+        sb.append("while(");
+        genExpression();
+        sb.append(") ");
+        loopDepth++;
+        genStatementBlock();
+        loopDepth--;
+        return 0;
+    }
+
+    /**
+     * Generate a declaration statement.
+     * @return 0
+     */
+    public int genDecl() {
+        String name = getVarName();
+        sb.append("int ").append(name).append("=");
+        genExpression();
+        sb.append(";");
+        variables.add(name);
+        return 0;
+    }
+
+    /**
+     * Generate an assignment statement.
+     * @return 0
+     */
+    public int genAssignment() {
+        if (variables.isEmpty()) return genDecl();
+        genVariable();
+        sb.append("=");
+        genExpression();
+        sb.append(";");
+        return 0;
+    }
+
+    /**
+     * Generate a return statement.
+     * @return FLAG_STOP
+     */
+    public int genReturn() {
+        sb.append("return ");
+        genExpression();
+        sb.append(";");
+        return FLAG_STOP;
+    }
+
+
+    /**
+     * Generate a binary expression.
+     * This method does not care about operator precedence.
+     */
+    public void genExpression() {
+        var num = randLog(10);
+        while(num-->0) {
+            genUnary();
+            sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]);
+        }
+        genUnary();
+    }
+
+    /**
+     * Generate a unary expression.
+     */
+    public void genUnary() {
+        var num = randLog(6);
+        while(num-->0) {
+            sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]);
+        }
+        genPrimary();
+    }
+
+    /**
+     * Generate a primary expression.
+     */
+    public void genPrimary() {
+        switch (random.nextInt(10)) {
+            case 0:
+                sb.append("true");
+                break;
+            case 1:
+                sb.append("false");
+                break;
+            case 2:
+                if (exprDepth == 0) {
+                    // Ensure termination of the generator.
+                    if (random.nextBoolean()) {
+                        genNumber();
+                    } else {
+                        genVariable();
+                    }
+                } else {
+                    sb.append("(");
+                    exprDepth--;
+                    genExpression();
+                    exprDepth++;
+                    sb.append(")");
+                }
+                break;
+            case 3, 4, 5, 6:
+                genNumber();
+                break;
+            default:
+                genVariable();
+        }
+    }
+
+    /**
+     * Generate a number.
+     */
+    public void genNumber() {
+        sb.append(random.nextInt(100));
+    }
+
+    /**
+     * Generate a variable. If there are none generate a number instead.
+     * If the program is allowed to be invalid a random name can be generated in some cases.
+     */
+    public void genVariable() {
+        if (!generateValid && random.nextInt(100)>97) {
+            sb.append(getRandomName());
+            maybeInvalid = true;
+            return;
+        }
+        if (variables.isEmpty()) {
+            genNumber();
+        } else {
+            sb.append(variables.get(random.nextInt(variables.size())));
+        }
+    }
+
+}