Chapter 9: Global Value Numbering and Iterative Peepholes

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

26 files changed, 805 insertions, 203 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/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java
new file mode 100644
index 00000000..41fc6916
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -0,0 +1,208 @@
+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) {
+        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
+            var obs = Parser.PARSER == null ? null : Parser.PARSER._obs;
+            if( obs != null ) obs.before(n);
+            Node x = n.peepholeOpt();
+            if( x != null ) {
+                if( x.isDead() ) {
+                    if( obs != null ) obs.after(n, x, true);
+                    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( obs != null ) obs.after(n, x, true);
+        }
+
+        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 d7055f48..3c1eab96 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -78,11 +78,12 @@ public class Parser {
     public Parser(String source, TypeInteger arg) {
         PARSER = this;
         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) {
@@ -115,7 +116,6 @@ public class Parser {
         return STOP;
     }
 
-
     /**
      * Parses a block
      *
@@ -191,11 +191,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
@@ -209,7 +208,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
@@ -253,7 +252,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;
     }
 
@@ -275,11 +274,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();
@@ -288,12 +286,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
+        ifF.unkeep();           // fScope already owns the false control
         if (matchx("else")) {
             parseStatement();
             fScope = _scope;
@@ -383,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;
     }
 
@@ -401,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;
     }
 
@@ -417,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 4a587953..c299e805 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -14,11 +14,14 @@ public class AddNode extends Node {
 
     @Override
     public Type compute() {
-        if( in(1)._type instanceof TypeInteger i0 &&
-            in(2)._type instanceof TypeInteger i1 ) {
+        Type t1 = in(1)._type, t2 = in(2)._type;
+        if( t1==Type.TOP || t1==TypeInteger.TOP ||
+            t2==Type.TOP || t2==TypeInteger.TOP )
+            return TypeInteger.TOP;
+        if( t1 instanceof TypeInteger i0 &&
+            t2 instanceof TypeInteger i1 ) {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()+i1.value());
-            return i0.meet(i1);
         }
         return TypeInteger.BOT;
     }
@@ -27,12 +30,8 @@ public class AddNode extends Node {
     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 )
@@ -48,6 +47,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) ?
@@ -59,7 +62,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 spine_cmp(lhs,rhs) ? swap12() : phiCon(this,true);
+            return spine_cmp(lhs,rhs,this) ? swap12() : phiCon(this,true);
 
         // Now we only see (add add non)
 
@@ -70,7 +73,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());
 
 
@@ -84,7 +91,7 @@ public class AddNode extends Node {
 
         // Do we rotate (x + y) + z
         // into         (x + z) + y ?
-        if( spine_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;
@@ -97,16 +104,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
@@ -127,8 +134,15 @@ 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-spine nodes and decide what order they should be in.
@@ -136,12 +150,15 @@ public class AddNode extends Node {
     // 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 spine_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 e363bf75..a6b8bfc7 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -23,11 +23,14 @@ abstract public class BoolNode extends Node {
 
     @Override
     public Type compute() {
-        if( in(1)._type instanceof TypeInteger i0 &&
-            in(2)._type instanceof TypeInteger i1 ) {
+        Type t1 = in(1)._type, t2 = in(2)._type;
+        if( t1==Type.TOP || t1==TypeInteger.TOP ||
+            t2==Type.TOP || t2==TypeInteger.TOP )
+            return TypeInteger.TOP;
+        if( t1 instanceof TypeInteger i0 &&
+            t2 instanceof TypeInteger i1 ) {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0);
-            return i0.meet(i1);
         }
         return TypeInteger.BOT;
     }
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 19166ec6..cf2465e3 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -9,7 +9,7 @@ import com.seaofnodes.simple.type.Type;
 /**
  * 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
@@ -44,4 +44,18 @@ 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; }
+    @Override int idepth() { return 0; }
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java
index 4c3c2feb..d7244ace 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -14,13 +14,16 @@ public class DivNode extends Node {
 
     @Override
     public Type compute() {
-        if (in(1)._type instanceof TypeInteger i0 &&
-            in(2)._type instanceof TypeInteger i1) {
+        Type t1 = in(1)._type, t2 = in(2)._type;
+        if( t1==Type.TOP || t1==TypeInteger.TOP ||
+            t2==Type.TOP || t2==TypeInteger.TOP )
+            return TypeInteger.TOP;
+        if (t1 instanceof TypeInteger i0 &&
+            t2 instanceof TypeInteger i1) {
             if (i0.isConstant() && i1.isConstant())
                 return i1.value() == 0
                     ? TypeInteger.ZERO
                     : TypeInteger.constant(i0.value()/i1.value());
-            return i0.meet(i1);
         }
         return TypeInteger.BOT;
     }
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 41b5ffd7..1c3d2c85 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -28,27 +28,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 fb51777e..0934c37f 100644
--- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -16,7 +16,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 TypeInteger.BOT;
+        return in(1)._type==Type.TOP ? TypeInteger.TOP : TypeInteger.BOT;
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 2d0fa95b..5592c52d 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -14,11 +14,14 @@ public class MulNode extends Node {
 
     @Override
     public Type compute() {
-        if (in(1)._type instanceof TypeInteger i0 &&
-            in(2)._type instanceof TypeInteger i1) {
+        Type t1 = in(1)._type, t2 = in(2)._type;
+        if( t1==Type.TOP || t1==TypeInteger.TOP ||
+            t2==Type.TOP || t2==TypeInteger.TOP )
+            return TypeInteger.TOP;
+        if (t1 instanceof TypeInteger i0 &&
+            t2 instanceof TypeInteger i1) {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()*i1.value());
-            return i0.meet(i1);
         }
         return TypeInteger.BOT;
     }
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 46d5b843..3c1ed0ab 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -5,10 +5,12 @@ import com.seaofnodes.print.BaseNode;
 import com.seaofnodes.simple.Parser;
 
 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.
@@ -58,6 +60,7 @@ public abstract class Node extends BaseNode<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) {
         super(UNIQUE_ID++); // allocate unique dense ID
@@ -88,11 +91,10 @@ public abstract class Node extends BaseNode<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(); }
 
-    public Node out(int i) { return _outputs.get(i); }
-
     public int nOuts() { return _outputs.size(); }
 
     public boolean isUnused() { return nOuts() == 0; }
@@ -113,9 +115,10 @@ public abstract class Node extends BaseNode<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.
@@ -132,13 +135,17 @@ public abstract class Node extends BaseNode<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;
     }
 
     /**
@@ -149,6 +156,7 @@ public abstract class Node extends BaseNode<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
@@ -171,6 +179,7 @@ public abstract class Node extends BaseNode<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
@@ -181,13 +190,21 @@ public abstract class Node extends BaseNode<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
     }
 
@@ -201,10 +218,11 @@ public abstract class Node extends BaseNode<Node> {
     public <N extends Node> N unkeep() { delUse(null); return (N)this; }
 
     // 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);
@@ -216,6 +234,19 @@ public abstract class Node extends BaseNode<Node> {
     // Graph-based optimizations
 
     /**
+     * Try to peephole at this node and return a better replacement Node.
+     * Always returns some not-null Node (often this).
+     */
+    public final Node peephole() {
+        var obs = IterPeeps.midAssert() ? null : Parser.PARSER == null ? null : Parser.PARSER._obs;
+        if( obs != null ) obs.before(this);
+        Node n = peepholeOpt();
+        Node rez = n == null ? this : deadCodeElim(n.peephole());
+        if( obs != null ) obs.after(this, n == null ? null : rez, false);
+        return rez;
+    }
+
+    /**
      * 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>
@@ -228,36 +259,45 @@ public abstract class Node extends BaseNode<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() {
-        var obs = Parser.PARSER == null ? null : Parser.PARSER._obs;
-        if( obs != null ) obs.before(this);
-        Type old = _type;
-        Node n = peepholeOpt();
-        Node rez = n == null ? this : n;
-        if( obs != null ) obs.after(this, n == null && old == _type ? null : rez, false);
-        return rez;
-    }
-
-    private Node peepholeOpt() {
+    public final Node peepholeOpt( ) {
+        ITER_CNT++;
         // Compute initial or improved Type
-        Type type = _type = compute();
+        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 null;            // 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.
@@ -287,13 +327,25 @@ public abstract class Node extends BaseNode<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
@@ -333,31 +385,126 @@ public abstract class Node extends BaseNode<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;
+    public int nDeps() { return _deps == null ? 0 : _deps.size(); }
+    public Node dep(int idx) { return _deps.get(idx); }
+
+    /**
+     * 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;
+        var obs = IterPeeps.midAssert() ? null : Parser.PARSER == null ? null : Parser.PARSER._obs;
+        if( obs != null ) obs.dep(this, dep);
+        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;
     }
 
@@ -395,25 +542,34 @@ public abstract class Node extends BaseNode<Node> {
      */
     public static void reset() {
         UNIQUE_ID = 1;
+        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 538016bd..8077f108 100644
--- a/src/main/java/com/seaofnodes/simple/node/NotNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -16,7 +16,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 TypeInteger.BOT;
+        return in(1)._type==Type.TOP ? TypeInteger.TOP : TypeInteger.BOT;
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 14622140..fe6231fa 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -15,30 +15,36 @@ public class PhiNode extends Node {
 
     @Override
     protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
-        if( region().inProgress() )
+        if( !(region() instanceof RegionNode r) || r.inProgress() )
             p.p("Z");
         p.p("Phi(");
         for( Node in : _inputs ) p.n(in).p(",");
         return p.unchar(',').close();
     }
 
-    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();
@@ -77,11 +83,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;
         }
@@ -89,9 +97,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 605c73bd..a794dfcc 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -8,7 +8,7 @@ import com.seaofnodes.simple.type.TypeTuple;
 
 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
@@ -33,7 +33,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;
     }
 
@@ -43,4 +43,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 b4dc3f58..315fcf0e 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -2,10 +2,12 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.print.ExprPrinter;
 
+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;
 
 public class RegionNode extends Node {
 
@@ -34,22 +36,29 @@ 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;
+            return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path);
+        }
+        // If down to a single input, become that input
+        if( nIns()==2 && !hasPhi() ) {
+            return in(1);       // Collapse if no Phis; 1-input Phis will collapse on their own
         }
         return null;
     }
@@ -61,6 +70,13 @@ 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.
     @Override int idepth() {
         if( _idepth!=0 ) return _idepth;
@@ -81,6 +97,11 @@ public class RegionNode extends Node {
 
     // 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 9f4cad7a..bc09c623 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -35,7 +35,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 31585ef4..f34d78e1 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -2,6 +2,7 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.print.ExprPrinter;
 
+import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.type.Type;
 
 import java.util.*;
@@ -213,6 +214,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 56689503..c2fcaba5 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -19,7 +19,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 aa655f63..d79194d8 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -3,11 +3,16 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.print.ExprPrinter;
 
 import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.IterPeeps;
 
 
 public class StopNode extends Node {
-    public StopNode(Node... inputs) {
-        super(inputs);
+
+    public final String _src;
+
+    public StopNode(String src) {
+        super();
+        _src = src;
     }
 
     @Override
@@ -51,4 +56,5 @@ public class StopNode extends Node {
         return addDef(node);
     }
 
+    public StopNode iterate() { return IterPeeps.iterate(this); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index bf938504..6fa87a07 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -14,15 +14,18 @@ public class SubNode extends Node {
 
     @Override
     public Type compute() {
+        Type t1 = in(1)._type, t2 = in(2)._type;
+        if( t1==Type.TOP || t1==TypeInteger.TOP ||
+            t2==Type.TOP || t2==TypeInteger.TOP )
+            return TypeInteger.TOP;
         // Sub of same is 0
         if( in(1)==in(2) )
             return TypeInteger.ZERO;
 
-        if (in(1)._type instanceof TypeInteger i0 &&
-            in(2)._type instanceof TypeInteger i1) {
+        if (t1 instanceof TypeInteger i0 &&
+            t2 instanceof TypeInteger i1) {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()-i1.value());
-            return i0.meet(i1);
         }
         return TypeInteger.BOT;
     }
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
index a9acba10..64b78766 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
@@ -5,7 +5,7 @@ import com.seaofnodes.graph.GraphSnapshot.*;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.node.Node;
 
-/** Chapter 8's view of the IR; browser, transport and layout are shared. */
+/** Chapter 9's view of the IR; browser, transport and layout are shared. */
 public class SimpleGraphAdapter extends GraphAdapter<Node> {
 
     @Override protected String[] edgeNames(Node n) {
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
index 0c3f4ce8..2c6c90ca 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
@@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node;
 import java.util.ArrayList;
 import java.io.IOException;
 
-/** Chapter 8's compilation context; capture and event bookkeeping are shared. */
+/** Chapter 9's compilation context; capture and event bookkeeping are shared. */
 public class SimpleGraphObserver extends GraphCapture<Node> {
     private Parser _parser;
     private Node _ret;
@@ -22,6 +22,9 @@ public class SimpleGraphObserver extends GraphCapture<Node> {
         _phase = "Parse";
         _ret = _parser.parse();
         phase(_phase);
+        _phase = "Iter";
+        com.seaofnodes.simple.IterPeeps.iterate(_parser.STOP);
+        phase(_phase);
     }
     @Override protected String phase() { return _phase; }
     @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; }
diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java
index d66fb3e7..daaa8af6 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 a9f6ee1c..ab9dbcff 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 39d8f72b..a2a6a095 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;
+    }
+
 
 }