Chapter 9: Global Value Numbering and Iterative Peepholeslinear-chapter09

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.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>

18 files changed, 395 insertions, 131 deletions

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