Chapter 9: Global Value Numbering and Iterative Peepholes

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

38 files changed, 1310 insertions, 295 deletions

diff --git a/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java
index f5694a78..9fc51c8e 100644
--- a/src/main/java/com/seaofnodes/simple/GraphEvaluator.java
+++ b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java
@@ -167,7 +167,7 @@ public class GraphEvaluator {
 
     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");
+        if (res.type== ResultType.TIMEOUT) throw new RuntimeException("Timeout");
         return res.value;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index d75e5bea..b4d64d4c 100644
--- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -20,15 +20,16 @@ public class GraphVisualizer {
     public GraphVisualizer(boolean separateControlCluster) { this._separateControlCluster = separateControlCluster; }
     public GraphVisualizer() { this(false); }
 
-    public String generateDotOutput(Parser parser) {
+    public String generateDotOutput(Parser parse) { return generateDotOutput(parse.STOP,parse._scope,parse._xScopes); }
+    public String generateDotOutput(StopNode stop, Node scope, Stack<ScopeNode> xScopes) {
 
         // Since the graph has cycles, we need to create a flat list of all the
         // nodes in the graph.
-        Collection<Node> all = findAll(parser);
+        Collection<Node> all = findAll(stop, scope);
         StringBuilder sb = new StringBuilder();
-        sb.append("digraph chapter08 {\n");
+        sb.append("digraph chapter09 {\n");
         sb.append("/*\n");
-        sb.append(parser.src());
+        sb.append(stop._src);
         sb.append("\n*/\n");
 
         // To keep the Scopes below the graph and pointing up into the graph we
@@ -52,15 +53,19 @@ public class GraphVisualizer {
         nodes(sb, all);
 
         // Now the scopes, in a cluster no edges
-        for( ScopeNode scope : parser._xScopes )
-            scope( sb, scope );
+        if( xScopes != null )
+            for( ScopeNode xscope : xScopes )
+                if( !xscope.isDead() )
+                    scope( sb, xscope );
 
         // Walk the Node edges
         nodeEdges(sb, all);
 
         // Walk the active Scope edges
-        for( ScopeNode scope : parser._xScopes )
-            scopeEdges( sb, scope );
+        if( xScopes != null )
+            for( ScopeNode xscope : xScopes )
+                if( !xscope.isDead() )
+                    scopeEdges( sb, xscope );
 
         sb.append("}\n");
         return sb.toString();
@@ -232,12 +237,13 @@ public class GraphVisualizer {
     /**
      * Finds all nodes in the graph.
      */
-    private Collection<Node> findAll(Parser parser) {
+    private Collection<Node> findAll(Node stop, Node scope) {
         final HashMap<Integer, Node> all = new HashMap<>();
-        for( Node n : Parser.START._outputs )
-            walk(all, n);
-        for( Node n : parser._scope._inputs )
+        for( Node n : stop._inputs )
             walk(all, n);
+        if( scope != null )
+            for( Node n : scope._inputs )
+                walk(all, n);
         return all.values();
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java
index 2a6dbefd..c06ac9d0 100644
--- a/src/main/java/com/seaofnodes/simple/IRPrinter.java
+++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java
@@ -48,14 +48,15 @@ public class IRPrinter {
         // First walk the CFG, then everything
         if( n.isCFG() ) {
             for( Node use : n._outputs )
-                if( use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) )
+                if( use!=null && use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) )
                     postOrd(use, rpos,visit,bfs);
             for( Node use : n._outputs )
-                if( use.isCFG() )
+                if( use!=null && use.isCFG() )
                     postOrd(use,rpos,visit,bfs);
         }
         for( Node use : n._outputs )
-            postOrd(use, rpos,visit,bfs);
+            if( use != null )
+                postOrd(use, rpos,visit,bfs);
         // Post-order
         rpos.add(n);
     }
diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java
new file mode 100644
index 00000000..6dafd95f
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -0,0 +1,204 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.ConstantNode;
+import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.node.StopNode;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.Random;
+
+/**
+ * The IterOptim runs after parsing. It iterates the peepholes to a fixed point
+ * so that no more peepholes apply.  This should be linear because peepholes rarely
+ * (never?)  increase code size.  The graph should monotonically reduce in some
+ * dimension, which is usually size.  It might also reduce in e.g. number of
+ * MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper
+ * ones.
+ *
+ * The theoretical overall worklist is mindless just grabbing the next thing and
+ * doing it.  If the graph changes, put the neighbors on the worklist.  Lather,
+ * Rinse, Repeat until the worklist runs dry.
+ *
+ * The main issues we have to deal with:
+ *
+ * <ul>
+ * <li>Nodes have uses; replacing some set of Nodes with another requires more graph
+ *   reworking.  Not rocket science, but it can be fiddly.  Its helpful to have a
+ *   small set of graph munging utilities, and the strong invariant that the graph
+ *   is stable and correct between peepholes.  In our case `Node.subsume` does
+ *   most of the munging, building on our prior stable Node utilities.</li>
+ *
+ * <li>Changing a Node also changes the graph "neighborhood".  The neigbors need to
+ *   be checked to see if THEY can also peephole, and so on.  After any peephole
+ *   or graph update we put a Nodes uses and defs on the worklist.</li>
+ *
+ * <li>Our strong invariant is that for all Nodes, either they are on the worklist
+ *   OR no peephole applies.  This invariant is easy to check, although expensive.
+ *   Basically the normal "iterate peepholes to a fixed point" is linear, and this
+ *   check is linear at each peephole step... so quadratic overall.  Its a useful
+ *   assert, but one we can disable once the overall algorithm is stable - and
+ *   then turn it back on again when some new set of peepholes is misbehaving.
+ *   The code for this is turned on in `IterOptim.iterate` as `assert
+ *   progressOnList(stop);`</li>
+ * </ul>
+ */
+public abstract class IterPeeps {
+
+    private static final WorkList<Node> WORK = new WorkList<>();
+
+    public static <N extends Node> N add( N n ) {
+        return (N)WORK.push(n);
+    }
+
+    public static void addAll( ArrayList<Node> ary ) {
+        WORK.addAll(ary);
+    }
+
+    /**
+     * Iterate peepholes to a fixed point
+     */
+    public static StopNode iterate(StopNode stop, boolean show) {
+        assert progressOnList(stop);
+        int cnt=0;
+
+        Node n;
+        while( (n=WORK.pop()) != null ) {
+            if( n.isDead() )  continue;
+            cnt++;              // Useful for debugging, searching which peephole broke things
+            Node x = n.peepholeOpt();
+            if( x != null ) {
+                if( x.isDead() ) continue;
+                // peepholeOpt can return brand-new nodes, needing an initial type set
+                if( x._type==null ) x.setType(x.compute());
+                // Changes require neighbors onto the worklist
+                if( x != n || !(x instanceof ConstantNode) ) {
+                    // All outputs of n (changing node) not x (prior existing node).
+                    for( Node z : n._outputs ) WORK.push(z);
+                    // Everybody gets a free "go again" in case they didn't get
+                    // made in their final form.
+                    WORK.push(x);
+                    // If the result is not self, revisit all inputs (because
+                    // there's a new user), and replace in the graph.
+                    if( x != n ) {
+                        for( Node z : n. _inputs ) WORK.push(z);
+                        n.subsume(x);
+                    }
+                }
+                // If there are distant neighbors, move to worklist
+                n.moveDepsToWorklist();
+                assert progressOnList(stop); // Very expensive assert
+            }
+        }
+
+        if( show )
+            System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null));
+        return stop;
+    }
+
+    // Visit ALL nodes and confirm the invariant:
+    //   Either you are on the WORK worklist OR running `iter()` makes no progress.
+
+    // This invariant ensures that no progress is missed, i.e., when the
+    // worklist is empty we have indeed done all that can be done.  To help
+    // with debugging, the {@code assert} is broken out in a place where it is easy to
+    // stop if a change is found.
+
+    // Also, the normal usage of `iter()` may attempt peepholes with distance
+    // neighbors and these should fail, but will then try to add dependencies
+    // {@link #Node.addDep} which is a side effect in an assert.  The {@link
+    // #midAssert} is used to stop this side effect.
+    private static boolean MID_ASSERT;
+    public static boolean midAssert() { return MID_ASSERT; }
+    private static boolean progressOnList(Node stop) {
+        MID_ASSERT = true;
+        int old_cnt = Node.ITER_CNT, old_nop = Node.ITER_NOP_CNT;
+        Node changed = stop.walk( n -> {
+                if( WORK.on(n) ) return null;
+                Node m = n.peepholeOpt();
+                if( m==null ) return null;
+                System.err.println("BREAK HERE FOR BUG");
+                return m;
+            });
+        Node.ITER_CNT = old_cnt;  Node.ITER_NOP_CNT = old_nop;
+        MID_ASSERT = false;
+        return changed==null;
+    }
+
+    public static void reset() {
+        WORK.clear();
+    }
+
+    /**
+     * Classic WorkList, with a fast add/remove, dup removal, random pull.
+     * The Node's nid is used to check membership in the worklist.
+     */
+    public static class WorkList<E extends Node> {
+
+        private Node[] _es;
+        private int _len;
+        private final BitSet _on;   // Bit set if Node._nid is on WorkList
+        private final Random _R;    // For randomizing pull from the WorkList
+        private final long _seed;
+
+        /* Useful stat - how many nodes are processed in the post parse iterative opt */
+        private long _totalWork = 0;
+
+        WorkList() { this(123); }
+        WorkList(long seed) {
+            _es = new Node[1];
+            _len=0;
+            _on = new BitSet();
+            _seed = seed;
+            _R = new Random();
+            _R.setSeed(_seed);
+        }
+
+        /**
+         * Pushes a Node on the WorkList, ensuring no duplicates
+         * If Node is null it will not be added.
+         */
+        public E push( E x ) {
+            if( x==null ) return null;
+            int idx = x._nid;
+            if( !_on.get(idx) ) {
+                _on.set(idx);
+                if( _len==_es.length )
+                    _es = Arrays.copyOf(_es,_len<<1);
+                _es[_len++] = x;
+                _totalWork++;
+            }
+            return x;
+        }
+
+        public void addAll( ArrayList<E> ary ) {
+            for( E n : ary )
+                push(n);
+        }
+
+        /**
+         * True if Node is on the WorkList
+         */
+        boolean on( E x ) { return _on.get(x._nid); }
+
+        /**
+         * Removes a random Node from the WorkList; null if WorkList is empty
+         */
+        E pop() {
+            if( _len == 0 ) return null;
+            int idx = _R.nextInt(_len);
+            E x = (E)_es[idx];
+            _es[idx] = _es[--_len]; // Compress array
+            _on.clear(x._nid);
+            return x;
+        }
+
+        public void clear() {
+            _len = 0;
+            _on.clear();
+            _R.setSeed(_seed);
+            _totalWork = 0;
+        }
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index 69796828..aabdf63a 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -69,11 +69,12 @@ public class Parser {
 
     public Parser(String source, TypeInteger arg) {
         Node.reset();
+        IterPeeps.reset();
         _lexer = new Lexer(source);
         _scope = new ScopeNode();
         _continueScope = _breakScope = null;
         START = new StartNode(new Type[]{ Type.CONTROL, arg });
-        STOP = new StopNode();
+        STOP = new StopNode(source);
     }
 
     public Parser(String source) {
@@ -108,7 +109,6 @@ public class Parser {
         return STOP;
     }
 
-
     /**
      * Parses a block
      *
@@ -185,11 +185,10 @@ public class Parser {
         // Parse predicate
         var pred = require(parseExpression(), ")");
         // IfNode takes current control and predicate
-        IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole();
+        Node ifNode = new IfNode(ctrl(), pred).peephole();
         // Setup projection nodes
-        Node ifT = new ProjNode(ifNode, 0, "True" ).peephole();
-        ifNode.unkeep();
-        Node ifF = new ProjNode(ifNode, 1, "False").peephole();
+        Node ifT = new ProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
+        Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole();
 
         // 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
@@ -203,7 +202,7 @@ public class Parser {
 
         // Parse the true side, which corresponds to loop body
         // Our current scope is the body Scope
-        ctrl(ifT);              // set ctrl token to ifTrue projection
+        ctrl(ifT.unkeep());     // set ctrl token to ifTrue projection
         parseStatement();       // Parse loop body
 
         // Merge the loop bottom into other continue statements
@@ -247,7 +246,7 @@ public class Parser {
             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);
+        toScope.ctrl(toScope.mergeScopes(cur));
         return toScope;
     }
 
@@ -269,11 +268,10 @@ public class Parser {
         // Parse predicate
         var pred = require(parseExpression(), ")");
         // IfNode takes current control and predicate
-        IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).<IfNode>keep().peephole();
+        Node ifNode = new IfNode(ctrl(), pred).peephole();
         // Setup projection nodes
-        Node ifT = new ProjNode(ifNode, 0, "True" ).peephole();
-        ifNode.unkeep();
-        Node ifF = new ProjNode(ifNode, 1, "False").peephole();
+        Node ifT = new ProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
+        Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole().keep();
         // In if true branch, the ifT proj node becomes the ctrl
         // But first clone the scope and set it as current
         int ndefs = _scope.nIns();
@@ -281,13 +279,13 @@ public class Parser {
         _xScopes.push(fScope); // For graph visualization we need all scopes
 
         // Parse the true side
-        ctrl(ifT);              // set ctrl token to ifTrue projection
+        ctrl(ifT.unkeep());     // set ctrl token to ifTrue projection
         parseStatement();       // Parse true-side
         ScopeNode tScope = _scope;
 
         // Parse the false side
         _scope = fScope;        // Restore scope, then parse else block if any
-        ctrl(ifF);              // Ctrl token is now set to ifFalse projection
+        ctrl(ifF.unkeep());     // Ctrl token is now set to ifFalse projection
         if (matchx("else")) {
             parseStatement();
             fScope = _scope;
@@ -324,8 +322,8 @@ public class Parser {
      * Dumps out the node graph
      * @return {@code null}
      */
-    private Node showGraph() {
-        System.out.println(new GraphVisualizer().generateDotOutput(this));
+    Node showGraph() {
+        System.out.println(new GraphVisualizer().generateDotOutput(STOP,_scope,_xScopes));
         return null;
     }
 
@@ -384,12 +382,23 @@ public class Parser {
      */
     private Node parseComparison() {
         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.LE(lhs, parseComparison()).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();
+        while( true ) {
+            int idx=0;  boolean negate=false;
+            // Test for any local nodes made, and "keep" lhs during peepholes
+            if( false ) ;
+            else if( match("==") ) { idx=2;  lhs = new BoolNode.EQ(lhs, null); }
+            else if( match("!=") ) { idx=2;  lhs = new BoolNode.EQ(lhs, null); negate=true; }
+            else if( match("<=") ) { idx=2;  lhs = new BoolNode.LE(lhs, null); }
+            else if( match("<" ) ) { idx=2;  lhs = new BoolNode.LT(lhs, null); }
+            else if( match(">=") ) { idx=1;  lhs = new BoolNode.LE(null, lhs); }
+            else if( match(">" ) ) { idx=1;  lhs = new BoolNode.LT(null, lhs); }
+            else break;
+            // Peepholes can fire, but lhs is already "hooked", kept alive
+            lhs.setDef(idx,parseAddition());
+            lhs = lhs.peephole();
+            if( negate )        // Extra negate for !=
+                lhs = new NotNode(lhs).peephole();
+        }
         return lhs;
     }
 
@@ -402,9 +411,15 @@ public class Parser {
      * @return an add expression {@link Node}, never {@code null}
      */
     private Node parseAddition() {
-        var lhs = parseMultiplication();
-        if (match("+")) return new AddNode(lhs, parseAddition()).peephole();
-        if (match("-")) return new SubNode(lhs, parseAddition()).peephole();
+        Node lhs = parseMultiplication();
+        while( true ) {
+            if( false ) ;
+            else if( match("+") ) lhs = new AddNode(lhs,null);
+            else if( match("-") ) lhs = new SubNode(lhs,null);
+            else break;
+            lhs.setDef(2,parseMultiplication());
+            lhs = lhs.peephole();
+        }
         return lhs;
     }
 
@@ -418,8 +433,14 @@ public class Parser {
      */
     private Node parseMultiplication() {
         var lhs = parseUnary();
-        if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole();
-        if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole();
+        while( true ) {
+            if( false ) ;
+            else if( match("*") ) lhs = new MulNode(lhs,null);
+            else if( match("/") ) lhs = new DivNode(lhs,null);
+            else break;
+            lhs.setDef(2,parseUnary());
+            lhs = lhs.peephole();
+        }
         return lhs;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 84a368fd..4e30bb55 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -25,21 +25,16 @@ public class AddNode extends Node {
             in(2)._type instanceof TypeInteger i1 ) {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()+i1.value());
-            return i0.meet(i1);
         }
-        return Type.BOTTOM;
+        return in(1)._type.meet(in(2)._type);
     }
 
     @Override
     public Node idealize () {
         Node lhs = in(1);
         Node rhs = in(2);
-        Type t1 = lhs._type;
         Type t2 = rhs._type;
 
-        // Already handled by peephole constant folding
-        assert !(t1.isConstant() && t2.isConstant());
-
         // Add of 0.  We do not check for (0+x) because this will already
         // canonicalize to (x+0)
         if( t2 instanceof TypeInteger i && i.value()==0 )
@@ -55,6 +50,10 @@ public class AddNode extends Node {
         if( !(lhs instanceof AddNode) && rhs instanceof AddNode )
             return swap12();
 
+        // x+(-y) becomes x-y
+        if( rhs instanceof MinusNode minus )
+            return new SubNode(lhs,minus.in(1));
+
         // Now we might see (add add non) or (add non non) or (add add add) but never (add non add)
 
         // Do we have  x + (y + z) ?
@@ -66,7 +65,7 @@ public class AddNode extends Node {
         // Now we might see (add add non) or (add non non) but never (add non add) nor (add add add)
         if( !(lhs instanceof AddNode) )
             // Rotate; look for (add (phi cons) con/(phi cons))
-            return spline_cmp(lhs,rhs) ? swap12() : phiCon(this,true);
+            return spine_cmp(lhs,rhs,this) ? swap12() : phiCon(this,true);
 
         // Now we only see (add add non)
 
@@ -77,7 +76,11 @@ public class AddNode extends Node {
 
         // Do we have (x + con1) + con2?
         // Replace with (x + (con1+con2) which then fold the constants
-        if( lhs.in(2)._type.isConstant() && t2.isConstant() )
+        // lhs.in(2) is con1 here
+        // If lhs.in(2) is not a constant, we add ourselves as a dependency
+        // because if it later became a constant then we could make this
+        // transformation.
+        if( lhs.in(2).addDep(this)._type.isConstant() && rhs._type.isConstant() )
             return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole());
 
 
@@ -87,11 +90,11 @@ public class AddNode extends Node {
         Node phicon = phiCon(this,true);
         if( phicon!=null ) return phicon;
 
-        // Now we sort along the spline via rotates, to gather similar things together.
+        // Now we sort along the spine via rotates, to gather similar things together.
 
         // Do we rotate (x + y) + z
         // into         (x + z) + y ?
-        if( spline_cmp(lhs.in(2),rhs) )
+        if( spine_cmp(lhs.in(2),rhs,this) )
             return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2));
 
         return null;
@@ -104,16 +107,16 @@ public class AddNode extends Node {
         Node lhs = op.in(1);
         Node rhs = op.in(2);
         // LHS is either a Phi of constants, or another op with Phi of constants
-        PhiNode lphi = pcon(lhs);
+        PhiNode lphi = pcon(lhs,op);
         if( rotate && lphi==null && lhs.nIns() > 2 ) {
             // Only valid to rotate constants if both are same associative ops
             if( lhs.getClass() != op.getClass() ) return null;
-            lphi = pcon(lhs.in(2)); // Will rotate with the Phi push
+            lphi = pcon(lhs.in(2),op); // Will rotate with the Phi push
         }
         if( lphi==null ) return null;
 
         // RHS is a constant or a Phi of constants
-        if( !(rhs instanceof ConstantNode con) && pcon(rhs)==null )
+        if( !(rhs instanceof ConstantNode) && pcon(rhs,op)==null )
             return null;
 
         // If both are Phis, must be same Region
@@ -134,21 +137,31 @@ public class AddNode extends Node {
         return lhs==lphi ? phi : op.copy(lhs.in(1),phi);
     }
 
-    static PhiNode pcon(Node op) {
-        return op instanceof PhiNode phi && phi.allCons() ? phi : null;
+    /**
+     * Tests if the op is a phi and has all constant inputs.
+     * If not, returns null.
+     * If op is a phi, but its inputs are not all constants, then dep is added as
+     * a dependency to the phi's non-const input, because if later the input turn into a constant
+     * dep can make progress.
+     */
+    static PhiNode pcon(Node op, Node dep) {
+        return op instanceof PhiNode phi && phi.allCons(dep) ? phi : null;
     }
 
-    // Compare two off-spline nodes and decide what order they should be in.
+    // Compare two off-spine nodes and decide what order they should be in.
     // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ?
     // Generally constants always go right, then Phi-of-constants, then muls, then others.
     // Ties with in a category sort by node ID.
     // TRUE if swapping hi and lo.
-    static boolean spline_cmp( Node hi, Node lo ) {
+    static boolean spine_cmp( Node hi, Node lo, Node dep ) {
         if( lo._type.isConstant() ) return false;
         if( hi._type.isConstant() ) return true ;
 
-        if( lo instanceof PhiNode && lo.allCons() ) return false;
-        if( hi instanceof PhiNode && hi.allCons() ) return true ;
+        if( lo instanceof PhiNode lphi && lphi.region()._type==Type.XCONTROL ) return false;
+        if( hi instanceof PhiNode hphi && hphi.region()._type==Type.XCONTROL ) return false;
+
+        if( lo instanceof PhiNode && lo.allCons(dep) ) return false;
+        if( hi instanceof PhiNode && hi.allCons(dep) ) return true ;
 
         if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true;
         if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false;
diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index 0c32d50d..d3fcec95 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -32,9 +32,8 @@ abstract public class BoolNode extends Node {
             in(2)._type instanceof TypeInteger i1 ) {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0);
-            return i0.meet(i1);
         }
-        return Type.BOTTOM;
+        return in(1)._type.meet(in(2)._type);
     }
 
     abstract boolean doOp(long lhs, long rhs);
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 13006bfb..9e45198c 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -8,7 +8,7 @@ import java.util.BitSet;
 /**
  * A Constant node represents a constant value.  At present, the only constants
  * that we allow are integer literals; therefore Constants contain an integer
- * value. As we add other types of constants, we will refactor how we represent
+ * value.  As we add other types of constants, we will refactor how we represent
  * Constants.
  * <p>
  * Constants have no semantic inputs. However, we set Start as an input to
@@ -25,7 +25,7 @@ public class ConstantNode extends Node {
     }
 
     @Override
-    public String label() { return ""+_con; }
+    public String label() { return "#"+_con; }
 
     @Override
     public String uniqueName() { return "Con_" + _nid; }
@@ -42,4 +42,17 @@ public class ConstantNode extends Node {
 
     @Override
     public Node idealize() { return null; }
+
+    @Override
+    boolean eq(Node n) {
+        ConstantNode con = (ConstantNode)n; // Contract
+        return _con==con._con;
+    }
+
+    @Override
+    int hash() { return _con.hashCode(); }
+
+    // Dead control is its own idom root
+    Node idom() { return null; }
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java
index 7207fd48..08ce70b8 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -27,9 +27,8 @@ public class DivNode extends Node {
                 return i1.value() == 0
                     ? TypeInteger.ZERO
                     : TypeInteger.constant(i0.value()/i1.value());
-            return i0.meet(i1);
         }
-        return Type.BOTTOM;
+        return in(1)._type.meet(in(2)._type);
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 23a8fafc..460dce51 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -32,27 +32,30 @@ public class IfNode extends MultiNode {
         // If the If node is not reachable then neither is any following Proj
         if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM )
             return TypeTuple.IF_NEITHER;
+        Node pred = pred();
+        Type t = pred._type;
+        // High types mean NEITHER side is reachable.
+        // Wait until the type falls to decide which way to go.
+        if( t == Type.TOP || t == TypeInteger.TOP )
+            return TypeTuple.IF_NEITHER;
         // If constant is 0 then false branch is reachable
         // Else true branch is reachable
-        if (pred()._type instanceof TypeInteger ti && ti.isConstant()) {
-            if (ti.value() == 0)   return TypeTuple.IF_FALSE;
-            else                   return TypeTuple.IF_TRUE;
-        }
-
-        // Hunt up the immediate dominator tree.  If we find an identical if
-        // test on either the true or false branch, then this test matches.
-        for( Node dom = idom(), prior=this; dom!=null;  prior=dom, dom = dom.idom() )
-          if( dom instanceof IfNode iff && iff.pred()==pred() )
-            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)
-              : dom._type;      // Repeated test not dominated on one side
+        if (t instanceof TypeInteger ti && ti.isConstant())
+            return ti==TypeInteger.ZERO ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE;
 
         return TypeTuple.IF_BOTH;
     }
 
     @Override
     public Node idealize() {
+        // Hunt up the immediate dominator tree.  If we find an identical if
+        // test on either the true or false branch, that side wins.
+        if( !pred()._type.isHighOrConst() )
+            for( Node dom = idom(), prior=this; dom!=null;  prior = dom, dom = dom.idom() )
+                if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof ProjNode prj ) {
+                    setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole());
+                    return this;
+                }
         return null;
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index 3d944fd4..dd092c9e 100644
--- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -22,7 +22,7 @@ public class MinusNode extends Node {
     public Type compute() {
         if (in(1)._type instanceof TypeInteger i0)
             return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0;
-        return Type.BOTTOM;
+        return TypeInteger.TOP.meet(in(1)._type);
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 2e701a4e..7e9f88a2 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -25,9 +25,8 @@ public class MulNode extends Node {
             in(2)._type instanceof TypeInteger i1) {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()*i1.value());
-            return i0.meet(i1);
         }
-        return Type.BOTTOM;
+        return in(1)._type.meet(in(2)._type);
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index 7ba1aa19..2743bd19 100644
--- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -4,4 +4,11 @@ public abstract class MultiNode extends Node {
 
     public MultiNode(Node... inputs) { super(inputs); }
 
+    // Find a projection by index
+    ProjNode proj( int idx ) {
+        for( Node out : _outputs )
+            if( out instanceof ProjNode prj && prj._idx==idx )
+                return prj;
+        return null;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 2d6d5ad5..5eb9c076 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,10 +1,12 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.IRPrinter;
+import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
 import java.util.*;
+import java.util.function.Function;
 
 /**
  * All Nodes in the Sea of Nodes IR inherit from the Node class.
@@ -63,6 +65,7 @@ public abstract class Node {
      * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values.
      * */
     private static int UNIQUE_ID = 1;
+    public static int UID() { return UNIQUE_ID; }
 
     protected Node(Node... inputs) {
         _nid = UNIQUE_ID++; // allocate unique dense ID
@@ -105,7 +108,7 @@ public abstract class Node {
     // 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) {
-        if (visited.get(_nid))
+        if (visited.get(_nid) && !(this instanceof ConstantNode) )
             return sb.append(label());
         visited.set(_nid);
         return isDead()
@@ -131,7 +134,7 @@ public abstract class Node {
             sb.append("     ");
         sb.append(" [[  ");
         for( Node use : _outputs )
-            sb.append("%4d ".formatted(use._nid));
+            sb.append(use==null ? "____ " : "%4d ".formatted(use._nid));
         int lim = 5 - Math.max(_inputs.size(),3);
         for( int i = _outputs.size(); i<lim; i++ )
             sb.append("     ");
@@ -154,6 +157,7 @@ public abstract class Node {
      * @return Input node or null
      */
     public Node in(int i) { return _inputs.get(i); }
+    public Node out(int i) { return _outputs.get(i); }
 
     public int nIns() { return _inputs.size(); }
 
@@ -179,9 +183,10 @@ public abstract class Node {
      * @param new_def the new definition
      * @return new_def for flow coding
      */
-    Node setDef(int idx, Node new_def ) {
+    public Node setDef(int idx, Node new_def ) {
+        unlock();
         Node old_def = in(idx);
-        if( old_def == new_def ) return this; // No change
+        if( old_def == new_def ) return new_def; // No change
         // If new def is not null, add the corresponding def->use edge
         // This needs to happen before removing the old node's def->use edge as
         // the new_def might get killed if the old node kills it recursively.
@@ -198,13 +203,17 @@ public abstract class Node {
 
     // Remove the numbered input, compressing the inputs in-place.  This
     // shuffles the order deterministically - which is suitable for Region and
-    // Phi, but not for every Node.
-    void delDef(int idx) {
+    // Phi, but not for every Node.  If the def goes dead, it is recursively
+    // killed, which may include 'this' Node.
+    Node delDef(int idx) {
+        unlock();
         Node old_def = in(idx);
         if( old_def != null &&  // If the old def exists, remove a def->use edge
             old_def.delUse(this) ) // If we removed the last use, the old def is now dead
             old_def.kill();     // Kill old def
+        old_def.moveDepsToWorklist();
         Utils.del(_inputs, idx);
+        return this;
     }
 
     /**
@@ -215,6 +224,7 @@ public abstract class Node {
      * @return new_def for flow coding
      */
     Node addDef(Node new_def) {
+        unlock();
         // Add use->def edge
         _inputs.add(new_def);
         // If new def is not null, add the corresponding def->use edge
@@ -237,6 +247,7 @@ public abstract class Node {
     // Shortcut for "popping" n nodes.  A "pop" is basically a
     // setDef(last,null) followed by lowering the nIns() count.
     void popN(int n) {
+        unlock();
         for( int i=0; i<n; i++ ) {
             Node old_def = _inputs.removeLast();
             if( old_def != null &&     // If it exists and
@@ -247,18 +258,26 @@ public abstract class Node {
 
     /**
      * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em>
-     * to null.  This may recursively kill more Nodes and is basically dead
-     * code elimination.  This function is co-recursive with {@link #popN}.
+     * to null.  This may recursively kill more Nodes, and is basically dead
+     * code elimination.
      */
     public void kill( ) {
+        unlock();
         assert isUnused();      // Has no uses, so it is dead
-        popN(nIns());          // Set all inputs to null, recursively killing unused Nodes
         _type=null;             // Flag as dead
+        while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes
+            Node old_def = _inputs.removeLast();
+            if( old_def != null ) {
+                IterPeeps.add(old_def);// Revisit neighbor because removed use
+                if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead
+                    old_def.kill();        // Kill old def
+            }
+        }
         assert isDead();        // Really dead now
     }
 
     // Mostly used for asserts and printing.
-    boolean isDead() { return isUnused() && nIns()==0 && _type==null; }
+    public boolean isDead() { return isUnused() && nIns()==0 && _type==null; }
 
     // Shortcuts to stop DCE mid-parse
     // Add bogus null use to keep node alive
@@ -268,10 +287,11 @@ public abstract class Node {
 
 
     // Replace self with nnn in the graph, making 'this' go dead
-    void subsume( Node nnn ) {
+    public void subsume( Node nnn ) {
         assert nnn!=this;
         while( nOuts() > 0 ) {
             Node n = _outputs.removeLast();
+            n.unlock();
             int idx = Utils.find(n._inputs, this);
             n._inputs.set(idx,nnn);
             nnn.addUse(n);
@@ -289,6 +309,19 @@ public abstract class Node {
     public static boolean _disablePeephole = false;
 
     /**
+     * Try to peephole at this node and return a better replacement Node.
+     * Always returns some not-null Node (often this).
+     */
+    public final Node peephole( ) {
+        if (_disablePeephole) {
+            _type = compute();
+            return this;        // Peephole optimizations turned off
+        }
+        Node n = peepholeOpt();
+        return n==null ? this : deadCodeElim(n.peephole()); // Cannot return null for no-progress
+    }
+
+    /**
      * Try to peephole at this node and return a better replacement Node if
      * possible.  We compute a {@link Type} and then check and replace:
      * <ul>
@@ -301,29 +334,45 @@ public abstract class Node {
      * {@code (x+(1+2))}.  By canonicalizing expressions we fold common addressing
      * math constants, remove algebraic identities and generally simplify the
      * code. </li>
+     *
+     * Unlike peephole above, this explicitly returns null for no-change, or not-null
+     * for a better replacement (which can be this).
      * </ul>
      */
-    public final Node peephole( ) {
+    public final Node peepholeOpt( ) {
+        ITER_CNT++;
         // Compute initial or improved Type
-        Type type = _type = compute();
-
-        if (_disablePeephole)
-            return this;        // Peephole optimizations turned off
+        Type old = setType(compute());
 
         // Replace constant computations from non-constants with a constant node
-        if (!(this instanceof ConstantNode) && type.isConstant())
-            return deadCodeElim(new ConstantNode(type).peephole());
-
-        // Future chapter: Global Value Numbering goes here
+        if (!(this instanceof ConstantNode) && _type.isHighOrConst() )
+            return new ConstantNode(_type).peepholeOpt();
+
+        // Global Value Numbering
+        if( _hash==0 ) {
+            Node n = GVN.get(this); // Will set _hash as a side effect
+            if( n==null )
+                GVN.put(this,this);  // Put in table now
+            else {
+                // Because of random worklist ordering, the two equal nodes
+                // might have different types.  Because of monotonicity, both
+                // types are valid.  To preserve monotonicity, the resulting
+                // shared Node has to have the best of both types.
+                n.setType(n._type.join(_type));
+                _hash = 0; // Clear, since it never went in the table
+                return deadCodeElim(n);// Return previous; does Common Subexpression Elimination
+            }
+        }
 
         // Ask each node for a better replacement
         Node n = idealize();
         if( n != null )         // Something changed
-            // Recursively optimize
-            return deadCodeElim(n.peephole());
+            return n;           // Report progress
 
-        return this;            // No progress
+        if( old==_type ) ITER_NOP_CNT++;
+        return old==_type ? null : this; // Report progress
     }
+    public static int ITER_CNT, ITER_NOP_CNT;
 
     // m is the new Node, self is the old.
     // Return 'm', which may have zero uses but is alive nonetheless.
@@ -353,13 +402,26 @@ public abstract class Node {
      * theory.  Much later on, this will become important and allow us to do
      * many fancy complex optimizations trivially... because theory.
      * <p>
-     * compute() needs to be stand-alone, and cannot recursively call compute
-     * on its inputs programs are cyclic (have loops!) and this will just
+     * {@link #compute()} needs to be stand-alone, and cannot recursively call compute
+     * on its inputs, because programs are cyclic (have loops!) and this will just
      * infinitely recurse until stack overflow.  Instead, compute typically
      * computes a new type from the {@link #_type} field of its inputs.
      */
     public abstract Type compute();
 
+    // Set the type.  Assert monotonic progress.
+    // If changing, add users to worklist.
+    public Type setType(Type type) {
+        Type old = _type;
+        assert old==null || type.isa(old); // Since _type not set, can just re-run this in assert in the debugger
+        if( old == type ) return old;
+        _type = type;       // Set _type late for easier assert debugging
+        IterPeeps.addAll(_outputs);
+        moveDepsToWorklist();
+        return old;
+    }
+
+
     /**
      * This function rewrites the current Node into a more "idealized" form.
      * This is the bulk of our peephole rewrite rules, and we use this to
@@ -399,32 +461,127 @@ public abstract class Node {
      * call peephole.
      * <p>
      * Since idealize calls peephole and peephole calls idealize, you must be
-     * careful that all idealizations are <em>monotonic</em>: all transforms remove
-     * some feature, so that the set of available transforms always shrinks.
-     * If you don't, you risk an infinite peephole loop!
+     * careful that all idealizations are <em>monotonic</em>: all transforms
+     * remove some feature, so that the set of available transforms always
+     * shrinks.  If you don't, you risk an infinite peephole loop!
      *
      * @return Either a new or changed node, or null for no changes.
      */
     public abstract Node idealize();
 
 
+    // Some of the peephole rules get complex, and search further afield than
+    // just the nearest neighbor.  These peepholes can fail the pattern match
+    // on a node some distance away, and if that node ever changes we should
+    // retry the peephole.  Track a set of Nodes dependent on `this`, and
+    // revisit them if `this` changes.
+    ArrayList<Node> _deps;
+
+    /**
+     * Add a node to the list o dependencies. Only add it if its not
+     * an input or output of this node, that is, it is at least one step
+     * away. The node being added must benefit from this node being peepholed.
+     */
+    Node addDep( Node dep ) {
+        // Running peepholes during the big assert cannot have side effects
+        // like adding dependencies.
+        if( IterPeeps.midAssert() ) return this;
+        if( _deps==null ) _deps = new ArrayList<>();
+        if( Utils.find(_deps  ,dep) != -1 ) return this; // Already on list
+        if( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors
+        if( Utils.find(_outputs,dep)!= -1 ) return this;
+        _deps.add(dep);
+        return this;
+    }
+
+    // Move the dependents onto a worklist, and clear for future dependents.
+    public void moveDepsToWorklist( ) {
+        if( _deps==null ) return;
+        IterPeeps.addAll(_deps);
+        _deps.clear();
+    }
+
+
+    // Global Value Numbering.  Hash over opcode and inputs; hits in this table
+    // are structurally equal.
+    public static final HashMap<Node,Node> GVN = new HashMap<>();
+
+    // Two nodes are equal if they have the same inputs and the same "opcode"
+    // which means the same Java class, plus same internal parts.
+    @Override public final boolean equals( Object o ) {
+        if( o==this ) return true;
+        if( o.getClass() != getClass() ) return false;
+        Node n = (Node)o;
+        int len = _inputs.size();
+        if( len != n._inputs.size() ) return false;
+        for( int i=0; i<len; i++ )
+            if( in(i) != n.in(i) )
+                return false;
+        return eq(n);
+    }
+    // Subclasses add extra checks (such as ConstantNodes have same constant),
+    // and can assume "this!=n" and has the same Java class.
+    boolean eq( Node n ) { return true; }
+
+
+    // Cached hash.  If zero, then not computed AND this Node is NOT in the GVN
+    // table - and can have its edges hacked (which will change his hash
+    // anyway).  If Non-Zero then this Node is IN the GVN table, or is being
+    // probed to see if it can be inserted.  His edges are "locked", because
+    // hacking his edges will change his hash.
+    int _hash;
+
+    // If the _hash is set, then the Node is in the GVN table; remove it.
+    void unlock() {
+        if( _hash==0 ) return;
+        Node old = GVN.remove(this); // Pull from table
+        assert old==this;
+        _hash=0;                // Out of table now
+    }
+
+
+    // Hash of opcode and inputs
+    @Override public final int hashCode() {
+        if( _hash != 0 ) return _hash;
+        int hash = hash();
+        for( Node n : _inputs )
+            if( n != null )
+                hash = hash ^ (hash<<17) ^ (hash>>13) ^ n._nid;
+        if( hash==0 ) hash = 0xDEADBEEF; // Bad hash, so use some junky thing
+        return (_hash=hash);
+    }
+    // Subclasses add extra hash info (such as ConstantNodes constant)
+    int hash() { return 0; }
+
+
     // ------------------------------------------------------------------------
     // Peephole utilities
 
     // Swap inputs without letting either input go dead during the swap.
     Node swap12() {
+        unlock();               // Hash is order dependent
         Node tmp = in(1);
         _inputs.set(1,in(2));
         _inputs.set(2,tmp);
         return this;
     }
 
-    // does this node contain all constants?
-    // Ignores in(0), as is usually control.
-    boolean allCons() {
+    /**
+     * Does this node contain all constants?
+     * Ignores in(0), as is usually control.
+     * In an input is not a constant, we add dep as
+     * a dependency to it, because dep can make progress
+     * if the input becomes a constant later.
+     * It is sufficient for one of the non-const
+     * inputs to have the dependency so we don't bother
+     * checking the rest.
+     */
+    boolean allCons(Node dep) {
         for( int i=1; i<nIns(); i++ )
-            if( !(in(i)._type.isConstant()) )
+            if( !(in(i)._type.isConstant()) ) {
+                in(i).addDep(dep); // If in(i) becomes a constant later, will trigger some peephole
                 return false;
+            }
         return true;
     }
 
@@ -448,25 +605,35 @@ public abstract class Node {
     public static void reset() {
         UNIQUE_ID = 1;
         _disablePeephole=false;
+        GVN.clear();
+        ITER_CNT = ITER_NOP_CNT = 0;
+    }
+
+
+    // Utility to walk the entire graph applying a function; return the first
+    // not-null result.
+    private static final BitSet WVISIT = new BitSet();
+    final public <E> E walk( Function<Node,E> pred ) {
+        assert WVISIT.isEmpty();
+        E rez = _walk(pred);
+        WVISIT.clear();
+        return rez;
+    }
+
+    private <E> E _walk( Function<Node,E> pred ) {
+        if( WVISIT.get(_nid) ) return null; // Been there, done that
+        WVISIT.set(_nid);
+        E x = pred.apply(this);
+        if( x != null ) return x;
+        for( Node def : _inputs  )  if( def != null && (x = def._walk(pred)) != null ) return x;
+        for( Node use : _outputs )  if( use != null && (x = use._walk(pred)) != null ) return x;
+        return null;
     }
 
     /**
      * Debugging utility to find a Node by index
      */
-    public Node find(int nid) { return _find(new BitSet(),nid); }
-    private Node _find(BitSet visit, int nid) {
-        if( _nid==nid ) return this;
-        if( visit.get(_nid) ) return null;
-        visit.set(_nid);
-        for( Node def : _inputs )
-            if( def!=null ) {
-                Node rez = def._find(visit,nid);
-                if( rez != null ) return rez;
-            }
-        for( Node use : _outputs ) {
-            Node rez = use._find(visit,nid);
-            if( rez != null ) return rez;
-        }
-        return null;
+    public Node find(int nid) {
+        return walk( n -> n._nid==nid ? n : null );
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java
index 39df410d..7a520fec 100644
--- a/src/main/java/com/seaofnodes/simple/node/NotNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -22,7 +22,7 @@ public class NotNode extends Node {
     public Type compute() {
         if( in(1)._type instanceof TypeInteger i0 )
             return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
-        return Type.BOTTOM;
+        return TypeInteger.TOP.meet(in(1)._type);
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index c7b5b357..ec4c6ad3 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -16,7 +16,7 @@ public class PhiNode extends Node {
 
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
-        if( region().inProgress() )
+        if( !(region() instanceof RegionNode r) || r.inProgress() )
             sb.append("Z");
         sb.append("Phi(");
         for( Node in : _inputs ) {
@@ -29,23 +29,29 @@ public class PhiNode extends Node {
         return sb;
     }
 
-    RegionNode region() { return (RegionNode)in(0); }
+    Node region() { return in(0); }
     @Override public boolean isMultiTail() { return true; }
 
     @Override
     public Type compute() {
-        if( !(region() instanceof RegionNode r) || r.inProgress() )
-            return Type.BOTTOM;
+        if( !(region() instanceof RegionNode r) )
+            return region()._type==Type.XCONTROL ? Type.TOP : _type;
+        if( r.inProgress() ) return Type.BOTTOM;
         Type t = Type.TOP;
         for (int i = 1; i < nIns(); i++)
-            t = t.meet(in(i)._type);
+            // If the region's control input is live, add this as a dependency
+            // to the control because we can be peeped should it become dead.
+            if( r.in(i).addDep(this)._type != Type.XCONTROL && in(i) != this )
+                t = t.meet(in(i)._type);
         return t;
     }
 
     @Override
     public Node idealize() {
-        if( !(region() instanceof RegionNode r ) || r.inProgress() )
-            return null;
+        if( !(region() instanceof RegionNode r ) )
+            return in(1);       // Input has collapse to e.g. starting control.
+        if( r.inProgress() || r.nIns()<=1 )
+            return null;        // Input is in-progress
 
         // If we have only a single unique input, become it.
         Node live = singleUniqueInput();
@@ -84,11 +90,13 @@ public class PhiNode extends Node {
      * If only single unique input, return it
      */
     private Node singleUniqueInput() {
+        if( region() instanceof LoopNode loop && loop.entry()._type == Type.XCONTROL )
+            return null;    // Dead entry loops just ignore and let the loop collapse
         Node live = null;
         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 the region's control input is live, add this as a dependency
+            // to the control because we can be peeped should it become dead.
+            if( region().in(i).addDep(this)._type != Type.XCONTROL && in(i) != this )
                 if( live == null || live == in(i) ) live = in(i);
                 else return null;
         }
@@ -96,9 +104,22 @@ public class PhiNode extends Node {
     }
 
     @Override
-    boolean allCons() {
-        if( !(region() instanceof RegionNode r) || r.inProgress() )
-            return false;
-        return super.allCons();
+    boolean allCons(Node dep) {
+        if( !(region() instanceof RegionNode r) ) return false;
+        // When the region completes (is no longer in progress) the Phi can
+        // become a "all constants" Phi, and the "dep" might make progress.
+        addDep(dep);
+        if( r.inProgress() ) return false;
+        return super.allCons(dep);
+    }
+
+    // True if last input is null
+    public final boolean inProgress() {
+        return in(nIns()-1) == null;
+    }
+
+    // Never equal if inProgress
+    @Override boolean eq( Node n ) {
+        return !inProgress();
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 3c3f73b8..0ed9441d 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -7,7 +7,7 @@ import java.util.BitSet;
 
 public class ProjNode extends Node {
 
-    // Which slice of the incoming multi-part value
+    // Which slice of the incoming multipart value
     public final int _idx;
 
     // Debugging label
@@ -32,7 +32,7 @@ public class ProjNode extends Node {
 
     @Override
     public Type compute() {
-        Type t = ctrl()._type;
+        Type t = in(0)._type;
         return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM;
     }
 
@@ -42,4 +42,10 @@ public class ProjNode extends Node {
             return ctrl().in(0); // We become our input control
         return null;
     }
+
+    @Override
+    boolean eq( Node n ) { return _idx == ((ProjNode)n)._idx; }
+
+    @Override
+    int hash() { return _idx; }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index 453d028f..c949c2b2 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -1,9 +1,11 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
-import java.util.Collection;
+import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.BitSet;
 
 public class RegionNode extends Node {
@@ -34,22 +36,31 @@ public class RegionNode extends Node {
     public Node idealize() {
         if( inProgress() ) return null;
         int path = findDeadInput();
-        if( path != 0 ) {
-            for( Node phi : _outputs )
-                if( phi instanceof PhiNode )
-                    phi.delDef(path);
-            delDef(path);
-
-            // If down to a single input, become that input - but also make all
-            // Phis an identity on *their* single input.
-            if( nIns()==2 ) {
-                for( Node phi : _outputs )
-                    if( phi instanceof PhiNode )
-                        // Currently does not happen, because no loops
-                        throw Utils.TODO();
-                return in(1);
+        if( path != 0 &&
+            // Do not delete the entry path of a loop (ok to remove the back
+            // edge and make the loop a single-entry Region which folds away
+            // the Loop).  Folding the entry path confused the loop structure,
+            // moving the backedge to the entry point.
+            !(this instanceof LoopNode loop && loop.entry()==in(path)) ) {
+            // Cannot use the obvious output iterator here, because a Phi
+            // deleting an input might recursively delete *itself*.  This
+            // shuffles the output array, and we might miss iterating an
+            // unrelated Phi. So on rare occasions we repeat the loop to get
+            // all the Phis.
+            int nouts = 0;
+            while( nouts != nOuts() ) {
+                nouts = nOuts();
+                for( int i=0; i<nOuts(); i++ )
+                    if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() )
+                        phi.delDef(path);
             }
-            return this;
+            _idom = null;       // Clear idom cache
+            return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path);
+        }
+        // If down to a single input, become that input
+        if( nIns()==2 && !hasPhi() ) {
+            _idom = null;       // Clear idom cache
+            return in(1);       // Collapse if no Phis; 1-input Phis will collapse on their own
         }
         return null;
     }
@@ -61,11 +72,22 @@ public class RegionNode extends Node {
         return 0;               // All inputs alive
     }
 
+    private boolean hasPhi() {
+        for( Node phi : _outputs )
+            if( phi instanceof PhiNode )
+                return true;
+        return false;
+    }
+
     // Immediate dominator of Region is a little more complicated.
     private Node _idom;         // Immediate dominator cache
     @Override Node idom() {
-        if( _idom != null ) return _idom; // Return cached copy
-        if( nIns()!=3 ) return null;      // Fails for anything other than 2-inputs
+        if( _idom != null ) {
+            if( _idom.isDead() ) _idom=null;
+            else return _idom; // Return cached copy
+        }
+        if( nIns()==2 ) return in(1); // 1-input is that one input
+        if( nIns()!=3 ) return null;  // Fails for anything other than 2-inputs
         // Walk the LHS & RHS idom trees in parallel until they match, or either fails
         Node lhs = in(1).idom();
         Node rhs = in(2).idom();
@@ -77,11 +99,17 @@ public class RegionNode extends Node {
         }
         if( lhs==null ) return null;
         _idepth = lhs._idepth+1;
-        return (_idom=lhs);
+        if( !IterPeeps.midAssert() ) _idom=lhs;
+        return lhs;
     }
 
     // True if last input is null
     public final boolean inProgress() {
-        return in(nIns()-1) == null;
+        return nIns()>1 && in(nIns()-1) == null;
+    }
+
+    // Never equal if inProgress
+    @Override boolean eq( Node n ) {
+        return !inProgress();
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 312058b9..922a3649 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -34,7 +34,7 @@ public class ReturnNode extends Node {
 
     @Override
     public Type compute() {
-        return new TypeTuple(ctrl()._type,expr()._type);
+        return TypeTuple.make(ctrl()._type,expr()._type);
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index e5d03d93..3abea54d 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.type.Type;
 
 import java.util.*;
@@ -212,6 +213,8 @@ public class ScopeNode extends Node {
             if( in(i) instanceof PhiNode phi ) {
                 // Do an eager useless-phi removal
                 Node in = phi.peephole();
+                IterPeeps.addAll(phi._outputs);
+                phi.moveDepsToWorklist();
                 if( in != phi ) {
                     phi.subsume(in);
                     setDef(i,in); // Set the update back into Scope
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 01f1485a..e399138b 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -18,7 +18,7 @@ public class StartNode extends MultiNode {
 
     public StartNode(Type[] args) {
         super();
-        _args = new TypeTuple(args);
+        _args = TypeTuple.make(args);
         _type = _args;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 417790d9..602feffc 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -1,12 +1,17 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.IterPeeps;
 
 import java.util.BitSet;
 
 public class StopNode extends Node {
-    public StopNode(Node... inputs) {
-        super(inputs);
+
+    public final String _src;
+
+    public StopNode(String src) {
+        super();
+        _src = src;
     }
 
     @Override
@@ -50,4 +55,6 @@ public class StopNode extends Node {
         return addDef(node);
     }
 
+    public StopNode iterate(            ) { return IterPeeps.iterate(this,false); }
+    public StopNode iterate(boolean show) { return IterPeeps.iterate(this,show ); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index af66b950..f661be14 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -29,9 +29,8 @@ public class SubNode extends Node {
             in(2)._type instanceof TypeInteger i1) {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()-i1.value());
-            return i0.meet(i1);
         }
-        return Type.BOTTOM;
+        return in(1)._type.meet(in(2)._type);
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java
index 2f0e6171..d0265e83 100644
--- a/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -1,5 +1,8 @@
 package com.seaofnodes.simple.type;
 
+import com.seaofnodes.simple.Utils;
+
+import java.util.HashMap;
 
 /**
  * These types are part of a Monotone Analysis Framework,
@@ -18,6 +21,7 @@ package com.seaofnodes.simple.type;
  */
 
 public class Type {
+    static final HashMap<Type,Type> INTERN = new HashMap<>();
 
     // ----------------------------------------------------------
     // Simple types are implemented fully here.  "Simple" means: the code and
@@ -36,15 +40,53 @@ public class Type {
     private static final String[] STRS = new String[]{"Bot","Top","Ctrl","~Ctrl"};
     protected Type(byte type) { _type = type; }
 
-    public static final Type BOTTOM   = new Type( TBOT   ); // ALL
-    public static final Type TOP      = new Type( TTOP   ); // ANY
-    public static final Type CONTROL  = new Type( TCTRL  ); // Ctrl
-    public static final Type XCONTROL = new Type( TXCTRL ); // ~Ctrl
+    public static final Type BOTTOM   = new Type( TBOT   ).intern(); // ALL
+    public static final Type TOP      = new Type( TTOP   ).intern(); // ANY
+    public static final Type CONTROL  = new Type( TCTRL  ).intern(); // Ctrl
+    public static final Type XCONTROL = new Type( TXCTRL ).intern(); // ~Ctrl
+
+    // Is high or on the lattice centerline.
+    public boolean isHighOrConst() { return _type==TTOP || _type==TXCTRL; }
 
-    public boolean isConstant() { return _type == TTOP || _type == TXCTRL; }
+    // Strict constant values, things on the lattice centerline.
+    // Excludes both high and low values
+    public boolean isConstant() { return false; }
 
     public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
 
+    // ----------------------------------------------------------
+
+    // Factory method which interns "this"
+    protected <T extends Type> T intern() {
+        T nnn = (T)INTERN.get(this);
+        if( nnn==null )
+            INTERN.put(nnn=(T)this,this);
+        return nnn;
+    }
+
+    private int _hash;          // Hash cache; not-zero when set.
+    @Override
+    public final int hashCode() {
+        if( _hash!=0 ) return _hash;
+        _hash = hash();
+        if( _hash==0 ) _hash = 0xDEADBEEF; // Bad hash from subclass; use some junk thing
+        return _hash;
+    }
+    // Override in subclasses
+    int hash() { return _type; }
+
+    @Override
+    public final boolean equals( Object o ) {
+        if( o==this ) return true;
+        if( !(o instanceof Type t)) return false;
+        if( _type != t._type ) return false;
+        return eq(t);
+    }
+    // Overridden in subclasses; subclass can assume "this!=t" and java classes are same
+    boolean eq(Type t) { return true; }
+
+
+    // ----------------------------------------------------------
     public final Type meet(Type t) {
         // Shortcut for the self case
         if( t == this ) return this;
@@ -53,7 +95,7 @@ public class Type {
         // Reverse; xmeet 2nd arg is never "is_simple" and never equal to "this".
         if(   is_simple() ) return this.xmeet(t   );
         if( t.is_simple() ) return t   .xmeet(this);
-        return BOTTOM;        // Mixing 2 unrelated types
+        return xmeet(t);        // Mixing 2 unrelated types
     }
 
     // Compute meet right now.  Overridden in subclasses.
@@ -70,6 +112,28 @@ public class Type {
         return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL;
     }
 
+    // True if this "isa" t; e.g. 17 isa TypeInteger.BOT
+    public boolean isa( Type t ) { return meet(t)==t; }
+
+    // ----------------------------------------------------------
+    // Our lattice is defined with a MEET and a DUAL.
+    // JOIN is dual of meet of both duals.
+    public final Type join(Type t) {
+        if( this==t ) return this;
+        return dual().meet(t.dual()).dual();
+    }
+
+    public Type dual() {
+        return switch( _type ) {
+        case TBOT -> TOP;
+        case TTOP -> BOTTOM;
+        case TCTRL -> XCONTROL;
+        case TXCTRL -> CONTROL;
+        default -> throw Utils.TODO(); // Should not reach here
+        };
+    }
+
+    // ----------------------------------------------------------
     @Override
     public final String toString() {
         return _print(new StringBuilder()).toString();
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index b30e21d8..ba045603 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -5,59 +5,70 @@ package com.seaofnodes.simple.type;
  */
 public class TypeInteger extends Type {
 
-    public final static TypeInteger TOP = new TypeInteger(false, 0);
-    public final static TypeInteger BOT = new TypeInteger(false, 1);
-    public final static TypeInteger ZERO= new TypeInteger(true, 0);
+    public final static TypeInteger TOP = make(false, 0);
+    public final static TypeInteger BOT = make(false, 1);
+    public final static TypeInteger ZERO= make(true , 0);
 
-    private final boolean _is_con;
+    public final boolean _is_con;
 
     /**
      * The constant value or
-     * if not constant then 0=bottom, 1=top.
+     * if not constant then 1=bottom, 0=top.
      */
-    private final long _con;
+    public final long _con;
 
-    public TypeInteger(boolean is_con, long con) {
+    private TypeInteger(boolean is_con, long con) {
         super(TINT);
         _is_con = is_con;
         _con = con;
     }
+    public static TypeInteger make(boolean is_con, long con) {
+        return new TypeInteger(is_con,con).intern();
+    }
 
-    public static TypeInteger constant(long con) { return new TypeInteger(true, con); }
-
-    public boolean isTop() { return !_is_con && _con==0; }
-    public boolean isBot() { return !_is_con && _con==1; }
+    public static TypeInteger constant(long con) { return make(true, con); }
 
     @Override
     public StringBuilder _print(StringBuilder sb) {
-        if (isTop()) return sb.append("IntTop");
-        if (isBot()) return sb.append("IntBot");
+        if( this==TOP ) return sb.append("IntTop");
+        if( this==BOT ) return sb.append("IntBot");
         return sb.append(_con);
     }
 
     @Override
+    public boolean isHighOrConst() { return _is_con || _con==0; }
+
+    @Override
     public boolean isConstant() { return _is_con; }
 
     public long value() { return _con; }
 
     @Override
     public Type xmeet(Type other) {
-        if( this==other ) return this;
-        if (!(other instanceof TypeInteger i)) return super.meet(other);
+        // Invariant from caller: 'this' != 'other' and same class (TypeInteger)
+        TypeInteger i = (TypeInteger)other; // Contract
         // BOT wins
-        if (   isBot() ) return this;
-        if ( i.isBot() ) return i   ;
+        if ( this==BOT ) return this;
+        if ( i   ==BOT ) return i   ;
         // TOP loses
-        if ( i.isTop() ) return this;
-        if (   isTop() ) return i   ;
-        assert isConstant() && i.isConstant();
-        return _con==i._con ? this : TypeInteger.BOT;
+        if ( i   ==TOP ) return this;
+        if ( this==TOP ) return i   ;
+        // Since both are constants, and are never equals (contract) unequals
+        // constants fall to bottom
+        return BOT;
     }
 
     @Override
-    public boolean equals( Object o ) {
-        if( o==this ) return true;
-        if( !(o instanceof TypeInteger i) ) return false;
+    public Type dual() {
+        if( isConstant() ) return this; // Constants are a self-dual
+        return _con==0 ? BOT : TOP;
+    }
+
+    @Override
+    int hash() { return (int)(_con ^ (_is_con ? 0 : 0x4000)); }
+    @Override
+    public boolean eq( Type t ) {
+        TypeInteger i = (TypeInteger)t; // Contract
         return _con==i._con && _is_con==i._is_con;
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index 0f8b95bd..e82ea00b 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -4,14 +4,24 @@ public class TypeTuple extends Type {
 
     public final Type[] _types;
 
-    public TypeTuple(Type... _types) {
-        super(TTUPLE);
-        this._types = _types;
-    }
+    private TypeTuple(Type[] types) { super(TTUPLE); _types = types; }
+    public static TypeTuple make(Type... types) { return new TypeTuple(types).intern(); }
 
     @Override
     public Type xmeet(Type other) {
-        throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented");
+        TypeTuple tt = (TypeTuple)other;     // contract from xmeet
+        assert _types.length == tt._types.length;
+        Type[] ts = new Type[_types.length];
+        for( int i=0; i<_types.length; i++ )
+            ts[i] = _types[i].meet(tt._types[i]);
+        return make(ts);
+    }
+
+    @Override public Type dual() {
+        Type[] ts = new Type[_types.length];
+        for( int i=0; i<_types.length; i++ )
+            ts[i] = _types[i].dual();
+        return make(ts);
     }
 
     @Override
@@ -24,9 +34,27 @@ public class TypeTuple extends Type {
         return sb;
     }
 
-    public static final TypeTuple IF_BOTH    = new TypeTuple(new Type[]{Type.CONTROL, Type.CONTROL});
-    public static final TypeTuple IF_NEITHER = new TypeTuple(new Type[]{Type.XCONTROL,Type.XCONTROL});
-    public static final TypeTuple IF_TRUE    = new TypeTuple(new Type[]{Type.CONTROL, Type.XCONTROL});
-    public static final TypeTuple IF_FALSE   = new TypeTuple(new Type[]{Type.XCONTROL,Type.CONTROL});
+    public static final TypeTuple IF_BOTH    = make(new Type[]{Type. CONTROL,Type. CONTROL});
+    public static final TypeTuple IF_NEITHER = make(new Type[]{Type.XCONTROL,Type.XCONTROL});
+    public static final TypeTuple IF_TRUE    = make(new Type[]{Type. CONTROL,Type.XCONTROL});
+    public static final TypeTuple IF_FALSE   = make(new Type[]{Type.XCONTROL,Type. CONTROL});
+
+    @Override
+    int hash() {
+        int sum = 0;
+        for( Type type : _types ) sum ^= type.hashCode();
+        return sum;
+    }
+
+    @Override
+    boolean eq( Type t ) {
+        TypeTuple tt = (TypeTuple)t; // Contract
+        if( _types.length != tt._types.length ) return false;
+        for( int i=0; i<_types.length; i++ )
+            if( _types[i]!=tt._types[i] )
+                return false;
+        return true;
+    }
+
 
 }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java
index 47cee096..75ee0b70 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java
@@ -13,7 +13,7 @@ public class Chapter02Test {
         Parser parser = new Parser("return 1+2*3+-5;");
         Node._disablePeephole = true; // disable peephole so we can observe full graph
         StopNode ret = parser.parse();
-        assertEquals("return (1+((2*3)+(-5)));", ret.print());
+        assertEquals("return ((1+(2*3))+(-5));", ret.print());
         Node._disablePeephole = false;
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
index 64ff153e..2246b927 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -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());
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index 68d379a1..6ad3af15 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -21,7 +21,7 @@ else {
 }
 
 return a;""");
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString());
     }
 
@@ -36,7 +36,7 @@ if (arg == 1) {
     c = 4;
 }
 return c;""", TypeInteger.BOT);
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return Phi(Region16,4,3);", ret.toString());
     }
 
@@ -64,7 +64,7 @@ if( arg==1 )
 else
     b=a+1;
 return a+b;""");
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString());
     }
 
@@ -79,7 +79,7 @@ if( arg==1 )
 else
     a=b+1;
 return a+b;""");
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString());
     }
 
@@ -99,7 +99,7 @@ else
     a=5;
 return a;
 """, TypeInteger.BOT);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString());
     }
 
@@ -129,7 +129,7 @@ if( arg==1 )
     a=arg==3;
 }
 return a;""");
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return (arg==Phi(Region16,3,2));", ret.toString());
     }
 
@@ -169,6 +169,7 @@ return a;""");
         }
     }
 
+
     @Test
     public void testBadNum() {
         try {
diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
index b858b83e..054e96e8 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -15,7 +15,7 @@ public class Chapter06Test {
 if( true ) return 2;
 return 1;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return 2;", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -29,7 +29,7 @@ if (arg)
     a = 2;
 return (arg < a) < 3;
 """);
-        StopNode stop = parser.parse(false);
+        StopNode stop = parser.parse().iterate();
         assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString());
     }
 
@@ -44,7 +44,7 @@ else
   a=3;
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return 2;", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -64,7 +64,7 @@ if( a==2 )
 else
     b=5;
 return b;""", TypeInteger.BOT);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region32,42,5);", stop.toString());
     }
 
@@ -83,8 +83,8 @@ if( arg==2 )
 else
     b=5;
 return b;""", TypeInteger.BOT);
-        StopNode stop = parser.parse();
-        assertEquals("return Phi(Region28,2,5);", stop.toString());
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Region29,2,5);", stop.toString());
     }
 
     @Test
@@ -123,7 +123,7 @@ else
     a=5;
 return a;
 """, TypeInteger.constant(1));
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return 3;", stop.toString());
     }
 
@@ -143,8 +143,8 @@ else
     a=5;
 return a;
 """, TypeInteger.BOT);
-        StopNode stop = parser.parse();
-        assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString());
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Region37,3,Phi(Region35,4,5));", stop.toString());
     }
 
     @Test
@@ -163,7 +163,7 @@ else
     a=5;
 return a;
 """, TypeInteger.constant(1));
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return 3;", stop.toString());
     }
 
@@ -183,7 +183,7 @@ else
     a=5;
 return a;
 """, TypeInteger.constant(3));
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return 4;", stop.toString());
     }
 
@@ -199,8 +199,8 @@ if( arg ) {
 }
 return a+b;
 """);
-        StopNode ret = parser.parse();
-        assertEquals("return Phi(Region22,4,1);", ret.toString());
+        StopNode ret = parser.parse().iterate();
+        assertEquals("return Phi(Region24,4,1);", ret.toString());
     }
 
 
@@ -216,7 +216,7 @@ if( arg ) {
 }
 return a+b;
 """, TypeInteger.constant(1));
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return 4;", ret.toString());
     }
 
@@ -232,7 +232,7 @@ if( arg ) {
 }
 return a+b;
 """, TypeInteger.constant(0));
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return 1;", ret.toString());
     }
 
@@ -250,8 +250,8 @@ if( arg ) {
 }
 return a+b+c;
 """);
-        StopNode ret = parser.parse();
-        assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString());
+        StopNode ret = parser.parse().iterate();
+        assertEquals("return (Phi(Region35,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString());
     }
 
 
@@ -269,7 +269,7 @@ if( arg ) {
 }
 return a+b+c;
 """, TypeInteger.constant(1));
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return 6;", ret.toString());
     }
 
@@ -287,7 +287,7 @@ if( arg ) {
 }
 return a+b+c;
 """, TypeInteger.constant(2));
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return 5;", ret.toString());
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
index d691672e..adf10471 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
@@ -36,7 +36,7 @@ if(arg){}else{
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString());
     }
 
@@ -56,7 +56,7 @@ while(i < arg) {
 }
 return sum;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString());
     }
 
@@ -93,7 +93,7 @@ while(a < 10) {
 }
 return b;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -128,7 +128,7 @@ while(a < 10) {
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop7,1,(Phi_a+3));", 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(false);
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop7,1,2);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -190,7 +190,7 @@ while(a < 10) {
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -226,7 +226,7 @@ while(a < 10) {
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop8,1,(Phi_a+3));", 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
index 5d9d1545..cea6dd0f 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
@@ -4,22 +4,12 @@ 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(
                 """
@@ -32,7 +22,7 @@ while(arg < 10) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         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));
@@ -55,7 +45,7 @@ while(arg < 10) {
 }
 return a;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop7,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -74,7 +64,7 @@ while(arg < 10) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof RegionNode);
     }
@@ -90,7 +80,7 @@ while(arg < 10) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof RegionNode);
     }
@@ -109,7 +99,7 @@ while(arg < 10) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -126,7 +116,7 @@ while(arg < 10) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -142,15 +132,15 @@ while( arg < 10 ) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         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());
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return 0;", stop.toString());
     }
 
     @Test
@@ -177,7 +167,7 @@ while(arg < 10) {
 }
 return arg;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return arg;", stop.toString());
     }
 
@@ -194,7 +184,7 @@ while(arg < 10) {
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof RegionNode);
     }
@@ -210,9 +200,9 @@ while(1) {
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString());
-        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+        assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 );
     }
 
 }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java
new file mode 100644
index 00000000..5567299a
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java
@@ -0,0 +1,300 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.junit.Ignore;
+
+import static org.junit.Assert.*;
+
+public class Chapter09Test {
+
+    @Test
+    @Ignore
+    public void testJig() {
+        Parser parser = new Parser("""
+int v0=0;
+arg=0;
+while(v0) {
+        while(1) if(arg*arg*0==0) {}
+                while(0) {}
+    arg=1;
+}
+return 0;
+                """);
+        StopNode stop = parser.parse().iterate();
+    }
+
+    @Test
+    public void testGVN1() {
+        Parser parser = new Parser(
+                """
+int x = arg + arg;
+if(arg < 10) {
+    return arg + arg;
+}
+else {
+    x = x + 1;
+}
+return x;
+                """);
+        StopNode stop = parser.parse();
+        assertEquals("Stop[ return (arg*2); return (Mul+1); ]", stop.toString());
+        Assert.assertEquals(2, GraphEvaluator.evaluate(stop, 1));
+        Assert.assertEquals(23, GraphEvaluator.evaluate(stop, 11));
+    }
+
+    @Test
+    public void testGVN2() {
+        Parser parser = new Parser(
+                """
+return arg*arg-arg*arg;
+                """);
+        StopNode stop = parser.parse();
+        assertEquals("return 0;", stop.toString());
+        Assert.assertEquals(0, GraphEvaluator.evaluate(stop, 1));
+    }
+
+    @Test
+    public void testWorklist1() {
+        Parser parser = new Parser(
+                """
+int step = 1;
+while (arg < 10) {
+    arg = arg + step + 1;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop7,arg,(Phi_arg+2));", stop.toString());
+        Assert.assertEquals(11, GraphEvaluator.evaluate(stop, 1));
+    }
+
+    @Test
+    public void testWorklist2() {
+        Parser parser = new Parser(
+                """
+int cond = 0;
+int one = 1;
+while (arg < 10) {
+    if (cond) one = 2;
+    arg = arg + one*3 + 1;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop8,arg,(Phi_arg+4));", stop.toString());
+        Assert.assertEquals(13, GraphEvaluator.evaluate(stop, 1));
+    }
+
+    @Test
+    public void testWorklist3() {
+        Parser parser = new Parser(
+                """
+int v1 = 0;
+int v2 = 0;
+int v3 = 0;
+int v4 = 0;
+int v5 = 0;
+int v6 = 0;
+int v7 = 0;
+int v8 = 0;
+while (arg) {
+    if (v1) v2 = 1;
+    if (v2) v3 = 1;
+    if (v3) v4 = 1;
+    if (v4) v5 = 1;
+    if (v5) v6 = 1;
+    if (v6) v7 = 1;
+    if (v7) v8 = 1;
+    arg = arg + v8 + 1;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop14,arg,(Phi_arg+1));", stop.toString());
+    }
+
+    @Test
+    public void testRegionPeepBug() {
+        Parser parser = new Parser(
+                """
+int v0=0;
+int v1=0;
+while(v1+arg) {
+    arg=0;
+    int v2=v0;
+    while(arg+1) {}
+    v0=1;
+    v1=v2;
+}
+                """);
+        StopNode stop = parser.parse().iterate();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testWhile0() {
+        Parser parser = new Parser("while(0) continue; if(0) arg=0;");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testWhile1() {
+        Parser parser = new Parser("""
+if(0) while(0) {
+    int arg=arg;
+    while(0) {}
+}
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+
+    @Test
+    public void testPrecedence() {
+        Parser parser = new Parser("return 3-1+2;");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return 4;", stop.toString());
+    }
+
+    @Test
+    public void testSwap2() {
+        Parser parser = new Parser("return 1+(1+1);");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return 3;", stop.toString());
+    }
+
+
+    @Test
+    public void testFuzz0() {
+        Parser parser = new Parser("""
+int one = 1;
+int a = 0;
+int zero = 0;
+while(arg) {
+    a = -(one + a + 2);
+    arg = arg + 1;
+    one = one + zero;
+}
+return a;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop9,0,(-(Phi_a+3)));", stop.toString());
+    }
+
+    @Test
+    public void testFuzz1() {
+        Parser parser = new Parser("""
+while(1) {}
+while(arg) break;
+while(arg) arg=0;
+arg=0;
+int v0=0!=0<-0;
+return -0+0+0;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+
+    @Test
+    public void testFuzz2() {
+        Parser parser = new Parser("return 0+-0;");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return 0;", stop.toString());
+    }
+
+    @Test
+    public void testFuzz3() {
+        Parser parser = new Parser("int v0=0; while(0==69) while(v0) return 0;");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testFuzz4() {
+        Parser parser = new Parser("""
+while(1) {
+    arg=0<=0;
+    if(1<0) while(arg==-0) arg=arg-arg;
+}
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testFuzz5() {
+        Parser parser = new Parser("""
+{
+    int v0=0;
+    while(1)
+            int v1=0--0;
+    while(v0)
+        break;
+    while(-v0) {
+        while(0+0+v0) continue;
+        break;
+    }
+    if(-0!=-0+0+v0) while(0+0+0+0)
+                break;
+}
+return 0!=0;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testFuzz6() {
+        Parser parser = new Parser("""
+int v0=0;
+while(0==1) while(v0)
+        v0=1+v0;
+                                   """);
+        StopNode stop = parser.parse().iterate();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testFuzz7() {
+        Parser parser = new Parser("""
+while(1) {}
+int v0=0;
+while(v0)
+    {}
+int v1=0;
+while(1)
+        v1=1;
+return v1+v0;
+                                   """);
+        StopNode stop = parser.parse().iterate();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testFuzz8() {
+        Parser parser = new Parser("while(arg) arg = arg - 1;  return arg;");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop6,arg,(Phi_arg-1));", stop.toString());
+    }
+
+    @Test
+    public void testMeet() {
+        Type t1 = Type.TOP;
+        Type t2 = TypeInteger.TOP;
+        Assert.assertEquals(TypeInteger.TOP, t1.meet(t2));
+        Assert.assertEquals(TypeInteger.TOP, t2.meet(t1));
+        t1 = Type.BOTTOM;
+        t2 = TypeInteger.BOT;
+        Assert.assertEquals(Type.BOTTOM, t1.meet(t2));
+        Assert.assertEquals(Type.BOTTOM, t2.meet(t1));
+    }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
index 82a6a472..bb3bec1c 100644
--- a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
+++ b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
@@ -1,8 +1,8 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.fuzzer.Fuzzer;
-import org.junit.Ignore;
 import org.junit.Test;
+import org.junit.Ignore;
 
 
 import static org.junit.Assert.assertTrue;
@@ -18,9 +18,18 @@ public class FuzzerWrap {
     @Ignore
     public void fuzzPeeps() {
         var fuzzer = new Fuzzer();
-        for (int i=0; i<100000; i++)
+        for (int i=0; i<1000000; i++)
             fuzzer.fuzzPeeps(i);
         assertTrue(fuzzer.noExceptions());
     }
 
+
+    @Test
+    @Ignore
+    public void fuzzPeepTiming() {
+        var fuzzer = new Fuzzer();
+        int max_nid=0;
+        for (int i=0; i<1000000; i++)
+            max_nid = fuzzer.fuzzPeepTiming(i, max_nid);
+    }
 }
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
index 5fcd8764..936fb41e 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
@@ -1,6 +1,8 @@
 package com.seaofnodes.simple.fuzzer;
 
 import com.seaofnodes.simple.GraphEvaluator;
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.node.Node;
 import com.seaofnodes.simple.node.StopNode;
 
 import java.util.ArrayList;
@@ -108,6 +110,45 @@ public class Fuzzer {
     }
 
     /**
+     * Run one test with the given seed, and check for peephole counts.
+     * @param seed The seed to use for generating this test case
+     */
+    public int fuzzPeepTiming(long seed, int max_nids) {
+        var rand = new Random(seed);
+        var sb = new StringBuilder();
+        new ScriptGenerator(rand, sb, true).genProgram();
+        try {
+            var parser = new Parser(sb.toString());
+
+            var stop = parser.parse();
+            int parse_peeps= Node.ITER_CNT;
+            int parse_nops = Node.ITER_NOP_CNT;
+            double parse_nop_ratio = (double)parse_nops/parse_peeps;
+            int nids = Node.UID();
+            if( nids <= max_nids ) return max_nids;
+
+            double parse_peeps_per_node = (double)parse_peeps/nids;
+
+            stop.iterate();
+            int iter_peeps= Node.ITER_CNT;
+            int iter_nops = Node.ITER_NOP_CNT;
+            double iter_nop_ratio = (double)iter_nops/iter_peeps;
+            double iter_peeps_per_node = (double)iter_peeps/nids;
+
+            System.out.printf("%6d | Parsing: peeps: %5d, nops: %5d, ratio: %5.3f, last UID: %5d ps/node: %5.3f  | Iter: peeps: %6d, nops: %6d, ratio: %5.3f, ps/node: %5.3f\n",
+                              seed,
+                              parse_peeps,parse_nops,parse_nop_ratio,nids,parse_peeps_per_node,
+                              iter_peeps , iter_nops, iter_nop_ratio,      iter_peeps_per_node);
+            return nids;
+        } catch (Throwable e) {
+            // ignore exceptions, let the normal fullPeeps catch and reduce,
+            // we're interested in valid program optimizations
+        }
+        return max_nids;
+    }
+
+
+    /**
      * Run one test with the given seed.
      * @param seed The seed to use for generating this test case
      */
@@ -118,6 +159,7 @@ public class Fuzzer {
         check(sb.toString(), valid);
     }
 
+
     /**
      * Check that no exceptions happened.
      * @return true if no exception happened
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
index 37a57e11..f13a51e1 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
@@ -1,15 +1,79 @@
 package com.seaofnodes.simple.fuzzer;
 
+import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.node.Node;
 import com.seaofnodes.simple.node.StopNode;
 
+import java.io.OutputStream;
+import java.io.PrintStream;
+import java.lang.invoke.MethodHandle;
+import java.lang.invoke.MethodHandles;
+import java.lang.reflect.Field;
+import java.util.BitSet;
+
 /**
  * Some utilities for the fuzzer.
  */
 class FuzzerUtils {
 
     /**
+     * Get the value of a private field
+     */
+    @SuppressWarnings("unchecked")
+    public static <T> T getFieldValue(Object obj, String name) throws NoSuchFieldException, IllegalAccessException {
+        return (T) (obj instanceof Class<?> clz ? getField(clz, name).get(null) : getField(obj.getClass(), name).get(obj));
+    }
+
+    /**
+     * Get access to a private field
+     */
+    public static Field getField(Class<?> clz, String name) throws NoSuchFieldException {
+        var field = clz.getDeclaredField(name);
+        try {
+            field.setAccessible(true);
+        } catch (Throwable e) {
+            // Intentionally left empty
+        }
+        return field;
+    }
+
+    /**
+     * Try to rethrow an exception or create a runtime exception and throw it.
+     */
+    public static RuntimeException rethrow(Throwable e) {
+        if (e instanceof RuntimeException re) return re;
+        if (e instanceof Error er) throw er;
+        return new RuntimeException(e);
+    }
+
+    /**
+     * Copy of Node.WVISIST
+     * Used to clear as exceptions might happen in the walk and left this bitset not cleared
+     */
+    private static final BitSet NodeWalkVisit;
+
+    /**
+     * Write access to Iterate.MID_ASSERT
+     * Exception could happen mid assert and left this at true. Used to reset to false prior to parsing.
+     */
+    private static final MethodHandle set_MID_ASSERT;
+
+    /**
+     * Some problems might trigger debug output. Suppress this output with a null print stream during fuzzing.
+     */
+    public static final PrintStream NULL_PRINT_STREAM = new PrintStream(OutputStream.nullOutputStream());
+
+    static {
+        try {
+            NodeWalkVisit = getFieldValue(Node.class, "WVISIT");
+            set_MID_ASSERT = MethodHandles.lookup().unreflectSetter(getField( IterPeeps.class, "MID_ASSERT"));
+        } catch (Exception e) {
+            throw new ExceptionInInitializerError(e);
+        }
+    }
+
+    /**
      * Check that eiter one of the objects is null or that both are equal.
      */
     private static boolean equalOrNull(Object a, Object b) {
@@ -50,9 +114,25 @@ class FuzzerUtils {
      * 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();
+        var err = System.err;
+        var out = System.out;
+        try {
+            System.setErr(NULL_PRINT_STREAM);
+            System.setOut(NULL_PRINT_STREAM);
+            try {
+                set_MID_ASSERT.invokeExact(false);
+            } catch (Throwable e) {
+                throw rethrow(e);
+            }
+            var parser = new Parser(script);
+            Node._disablePeephole = !runPeeps;
+            var stop = parser.parse();
+            return runPeeps ? stop.iterate() : stop;
+        } finally {
+            NodeWalkVisit.clear();
+            System.setErr(err);
+            System.setOut(out);
+        }
     }
 
 }
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java
index b7fc18ec..2ef0a3fd 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java
@@ -32,8 +32,8 @@ public class Reducer {
             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("\\b(?:[^\\W0]|\\w\\w+)\\b"), "1"),
             new Replace(Pattern.compile("\\d+\\+"), ""),
             new Replace(Pattern.compile("\\+\\d+"), ""),
             new Replace(Pattern.compile("(?<=\\n|^)[^\\n]*(?=\\n|$)"), "\n"),
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
index 148c2319..ad98f7e2 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
@@ -16,20 +16,6 @@ import java.util.Random;
 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;
@@ -40,7 +26,15 @@ public class ScriptGenerator {
     /**
      * List of keywords not valid for identifiers.
      */
-    private static final HashSet<String> KEYWORDS = getKeywords();
+    private static final HashSet<String> KEYWORDS;
+
+    static {
+        try {
+            KEYWORDS = FuzzerUtils.getFieldValue(new Parser(""), "KEYWORDS");
+        } catch (Throwable e) {
+            throw new ExceptionInInitializerError(e);
+        }
+    }
 
     /**
      * Flag for a statement that it does not pass on control flow to the next statement.
@@ -83,11 +77,11 @@ public class ScriptGenerator {
     /**
      * The depth of blocks allowed.
      */
-    private int depth = 7;
+    private int depth = 20;
     /**
      * The depth of expressions allowed.
      */
-    private int exprDepth = 3;
+    private int exprDepth = 30;
     /**
      * Current variables in scope.
      */
@@ -141,7 +135,7 @@ public class ScriptGenerator {
      * @return The random name generated
      */
     private StringBuilder getRandomName() {
-        int len = random.nextInt(10) + 1;
+        int len = random.nextInt(30) + 1;
         StringBuilder sb = new StringBuilder(len);
         sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()-10)));
         for (int i=1; i<len; i++)
@@ -203,7 +197,7 @@ public class ScriptGenerator {
      * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the last statement generated
      */
     public int genStatements() {
-        var num = random.nextInt(10);
+        var num = random.nextInt(10); // (30);
         for (int i=0; i<num; i++) {
             printIndentation();
             var stop = genStatement();