Chapter 6: Peepholes for If

Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.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: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

18 files changed, 254 insertions, 46 deletions

diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index 359d0175..b9fbf26f 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -161,6 +161,7 @@ public class Parser {
         IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).<IfNode>keep().peephole();
         // Setup projection nodes
         Node ifT = new ProjNode(ifNode, 0, "True" ).peephole();
+        ifNode.unkeep();
         Node ifF = new ProjNode(ifNode, 1, "False").peephole();
         // In if true branch, the ifT proj node becomes the ctrl
         // But first clone the scope and set it as current
@@ -204,7 +205,7 @@ public class Parser {
     private Node parseReturn() {
         var expr = require(parseExpression(), ";");
         Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr).peephole());
-        ctrl(null);             // Kill control
+        ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill control
         return ret;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 367cb2c0..22c36746 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -57,7 +57,8 @@ 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) )
-            return spine_cmp(lhs,rhs) ? swap12() : null;
+            // Rotate; look for (add (phi cons) con/(phi cons))
+            return spine_cmp(lhs,rhs) ? swap12() : phiCon(this,true);
 
         // Now we only see (add add non)
 
@@ -66,23 +67,12 @@ public class AddNode extends Node {
         if( lhs.in(2)._type.isConstant() && t2.isConstant() )
             return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole());
 
-        if( lhs.in(2) instanceof PhiNode phi && phi.allCons() &&
-            // Do we have ((x + (phi cons)) + con) ?
-            // Do we have ((x + (phi cons)) + (phi cons)) ?
-            // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
-
-            // Note that this is the exact reverse of Phi pulling a common op
-            // down to reduce total op-count.  We don't get in an endless push-
-            // up push-down peephole cycle because the constants all fold first.
-            (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.allCons()) ) ) {
-            Node[] ns = new Node[phi.nIns()];
-            ns[0] = phi.in(0);
-            // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
-            for( int i=1; i<ns.length; i++ )
-                ns[i] = new AddNode(phi.in(i),t2.isConstant() ? rhs : rhs.in(i)).peephole();
-            String label = phi._label + (rhs instanceof PhiNode rphi ? rphi._label : "");
-            return new AddNode(lhs.in(1),new PhiNode(label,ns).peephole());
-        }
+
+        // Do we have ((x + (phi cons)) + con) ?
+        // Do we have ((x + (phi cons)) + (phi cons)) ?
+        // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
+        Node phicon = phiCon(this,true);
+        if( phicon!=null ) return phicon;
 
         // Now we sort along the spine via rotates, to gather similar things together.
 
@@ -94,6 +84,47 @@ public class AddNode extends Node {
         return null;
     }
 
+    // Rotation is only valid for associative ops, e.g. Add, Mul, And, Or.
+    // Do we have ((phi cons)|(x + (phi cons)) + con|(phi cons)) ?
+    // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
+    static Node phiCon(Node op, boolean rotate) {
+        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);
+        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
+        }
+        if( lphi==null ) return null;
+
+        // RHS is a constant or a Phi of constants
+        if( !(rhs instanceof ConstantNode con) && pcon(rhs)==null )
+            return null;
+
+        // If both are Phis, must be same Region
+        if( rhs instanceof PhiNode && lphi.in(0) != rhs.in(0) )
+            return null;
+
+        // Note that this is the exact reverse of Phi pulling a common op down
+        // to reduce total op-count.  We don't get in an endless push-up
+        // push-down peephole cycle because the constants all fold first.
+        Node[] ns = new Node[lphi.nIns()];
+        ns[0] = lphi.in(0);
+        // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
+        for( int i=1; i<ns.length; i++ )
+            ns[i] = op.copy(lphi.in(i), rhs instanceof PhiNode ? rhs.in(i) : rhs).peephole();
+        String label = lphi._label + (rhs instanceof PhiNode rphi ? rphi._label : "");
+        Node phi = new PhiNode(label,ns).peephole();
+        // Rotate needs another op, otherwise just the phi
+        return lhs==lphi ? phi : op.copy(lhs.in(1),phi);
+    }
+
+    static PhiNode pcon(Node op) {
+        return op instanceof PhiNode phi && phi.allCons() ? phi : null;
+    }
+
     // 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.
diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index aaf261d5..3a5e1a8f 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -39,6 +39,13 @@ abstract public class BoolNode extends Node {
         if( in(1)==in(2) )
             return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0));
 
+        // Do we have ((phi cons) cmp con) ?
+        // Do we have ((phi cons) cmp (phi cons)) ?
+        // Push the compare up through the phi: (phi con0 cmp con, con1 cmp con...)
+        // No rotate: compares are not associative.
+        Node phicon = AddNode.phiCon(this,false);
+        if( phicon!=null ) return phicon;
+
         return null;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 3b644bec..05c1c844 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -23,7 +23,25 @@ public class IfNode extends MultiNode {
 
     @Override
     public Type compute() {
-        return TypeTuple.IF;
+        // If the If node is not reachable then neither is any following Proj
+        if (ctrl()._type != Type.CONTROL) 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)
+              : null;           // Repeated test not dominated on one side
+
+        return TypeTuple.IF_BOTH;
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index a881bd96..d7c65b26 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -38,6 +38,12 @@ public class MulNode extends Node {
         if ( t1.isConstant() && !t2.isConstant() )
             return swap12();
 
+        // Do we have ((x * (phi cons)) * con) ?
+        // Do we have ((x * (phi cons)) * (phi cons)) ?
+        // Push constant up through the phi: x * (phi con0*con0 con1*con1...)
+        Node phicon = AddNode.phiCon(this,true);
+        if( phicon!=null ) return phicon;
+
         return null;
     }
     @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); }
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 72469ad2..23f15ebe 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -3,8 +3,10 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.print.BaseNode;
 
 import com.seaofnodes.simple.Parser;
+
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
+
 import java.util.*;
 
 /**
@@ -41,8 +43,17 @@ public abstract class Node extends BaseNode<Node> {
     public Type _type;
 
     /**
+     * Immediate dominator tree depth, used to approximate a real IDOM during
+     * parsing where we do not have the whole program, and also peepholes
+     * change the CFG incrementally.
+     * <p>
+     * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
+     */
+    char _idepth;
+
+    /**
      * A private Global Static mutable counter, for unique node id generation.
-     * To make the compiler multi-threaded, this field will have to move into a TLS.
+     * To make the compiler multithreaded, this field will have to move into a TLS.
      * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values.
      * */
     private static int UNIQUE_ID = 1;
@@ -110,6 +121,17 @@ public abstract class Node extends BaseNode<Node> {
         return new_def;
     }
 
+    // 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) {
+        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
+        Utils.del(_inputs, idx);
+    }
+
     /**
      * Add a new def to an existing Node.  Keep the edges correct by
      * adding the corresponding <em>def->use</em> edge.
@@ -317,6 +339,29 @@ public abstract class Node extends BaseNode<Node> {
         return true;
     }
 
+    // Return the immediate dominator of this Node and compute dom tree depth.
+    Node idom() { return in(0); }
+
+    // Find the lowest common ancestor in the current dominator tree.
+    Node domLCA(Node rhs) {
+        if( rhs==null ) return this;
+        Node lhs = this;
+        while( lhs != rhs ) {
+            if( lhs==null || rhs==null ) return null;
+            int comp = lhs.idepth() - rhs.idepth();
+            if( comp >= 0 ) lhs = lhs.idom();
+            if( comp <= 0 ) rhs = rhs.idom();
+        }
+        return lhs;
+    }
+
+    int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); }
+    // Zero depth means uncached. Check before narrowing so overflow cannot wrap.
+    final int cacheIDepth(int depth) {
+        assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535";
+        return _idepth = (char)depth;
+    }
+
     // Make a shallow copy (same class) of this Node, with given inputs and
     // empty outputs and a new Node ID.  The original inputs are ignored.
     // Does not need to be implemented in isCFG() nodes.
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index da3917c7..6acb5535 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -24,17 +24,18 @@ public class PhiNode extends Node {
 
     @Override
     public Type compute() {
-        Type t = in(1)._type;
-        for( int i=2; i<nIns(); i++ )
+        Type t = Type.TOP;
+        for (int i = 1; i < nIns(); i++)
             t = t.meet(in(i)._type);
         return t;
     }
 
     @Override
     public Node idealize() {
-        // Remove a "junk" Phi: Phi(x,x) is just x
-        if( same_inputs() )
-            return in(1);
+        // If we have only a single unique input, become it.
+        Node live = singleUniqueInput();
+        if (live != null)
+            return live;
 
         // Pull "down" a common data op.  One less op in the world.  One more
         // Phi, but Phis do not make code.
@@ -64,11 +65,17 @@ public class PhiNode extends Node {
         return true;
     }
 
-    private boolean same_inputs() {
-        for( int i=2; i<nIns(); i++ )
-            if( in(1) != in(i) )
-                return false;
-        return true;
+    /**
+     * If only single unique input, return it
+     */
+    private Node singleUniqueInput() {
+        Node live = null;
+        for( int i=1; i<nIns(); i++ )
+            if( region().in(i)._type != Type.XCONTROL && in(i) != this )
+                if( live == null || live == in(i) ) live = in(i);
+                else return null;
+        return live;
     }
 
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 8917fbd4..e313d31b 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -37,6 +37,8 @@ public class ProjNode extends Node {
 
     @Override
     public Node idealize() {
+        if( ctrl()._type instanceof TypeTuple tt && tt._types[1-_idx]==Type.XCONTROL ) // Only true for IfNodes
+            return ctrl().in(0); // We become our input control
         return null;
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index e29254ad..cbd51743 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -2,6 +2,7 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.print.ExprPrinter;
 
+import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
 public class RegionNode extends Node {
@@ -18,11 +19,57 @@ public class RegionNode extends Node {
 
     @Override
     public Type compute() {
-        return Type.CONTROL;
+        Type t = Type.XCONTROL;
+        for (int i = 1; i < nIns(); i++)
+            t = t.meet(in(i)._type);
+        return t;
     }
 
     @Override
     public Node idealize() {
+        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);
+            }
+            return this;
+        }
         return null;
     }
+
+    private int findDeadInput() {
+        for( int i=1; i<nIns(); i++ )
+            if( in(i)._type==Type.XCONTROL )
+                return i;
+        return 0;               // All inputs alive
+    }
+
+    // Immediate dominator of Region is a little more complicated.
+    @Override int idepth() {
+        if( _idepth!=0 ) return _idepth;
+        int depth=0;
+        for( Node n : _inputs )
+            if( n!=null )
+                depth = Math.max(depth,n.idepth()+1);
+        return cacheIDepth(depth);
+    }
+
+    @Override Node idom() {
+        Node lca = null;
+        // Recompute from predecessors: CFG edits can change the dominator.
+        for( int i=1; i<nIns(); i++ )
+            lca = in(i).domLCA(lca);
+        return lca;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index c5dc532d..b8bc8859 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -38,5 +38,9 @@ public class ReturnNode extends Node {
     }
 
     @Override
-    public Node idealize() { return null; }
+    public Node idealize() {
+        if( ctrl()._type==Type.XCONTROL )
+            return ctrl();
+        return null;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 90b97bae..86f4778e 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -164,14 +164,14 @@ public class ScopeNode extends Node {
      * @return A new node representing the merge point
      */
     public Node mergeScopes(ScopeNode that) {
-        RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole());
+        RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep());
         String[] ns = reverseNames();
         // Note that we skip i==0, which is bound to '$ctrl'
         for (int i = 1; i < nIns(); i++)
             if( in(i) != that.in(i) ) // No need for redundant Phis
                 setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole());
         that.kill();            // Kill merged scope
-        return r;
+        return r.unkeep().peephole();
     }
 
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index c9f53abd..199845fe 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -36,4 +36,10 @@ public class StartNode extends MultiNode {
 
     @Override
     public Node idealize() { return null; }
+
+    // No immediate dominator, and idepth==0
+    @Override
+    Node idom() { return null; }
+    @Override int idepth() { return 0; }
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 9ae0acb4..fe10b1ce 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -38,6 +38,11 @@ public class StopNode extends Node {
 
     @Override
     public Node idealize() {
+        int len = nIns();
+        for( int i=0; i<nIns(); i++ )
+            if( in(i)._type==Type.XCONTROL )
+                delDef(i--);
+        if( len != nIns() ) return this;
         return null;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
index 930d5376..24614ad4 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 5's view of the IR; browser, transport and layout are shared. */
+/** Chapter 6'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 a7604165..ea9a705e 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 5's compilation context; capture and event bookkeeping are shared. */
+/** Chapter 6's compilation context; capture and event bookkeeping are shared. */
 public class SimpleGraphObserver extends GraphCapture<Node> {
     private Parser _parser;
     private Node _ret;
diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java
index 6b9130ba..d66fb3e7 100644
--- a/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -25,25 +25,50 @@ public class Type {
     static final byte TBOT    = 0; // Bottom (ALL)
     static final byte TTOP    = 1; // Top    (ANY)
     static final byte TCTRL   = 2; // Ctrl flow bottom
-    static final byte TSIMPLE = 3; // End of the Simple Types
-    static final byte TINT    = 4; // All Integers; see TypeInteger
-    static final byte TTUPLE  = 5; // Tuples; finite collections of unrelated Types, kept in parallel
+    static final byte TXCTRL  = 3; // Ctrl flow top (mini-lattice: any-xctrl-ctrl-all)
+    static final byte TSIMPLE = 4; // End of the Simple Types
+    static final byte TINT    = 5; // All Integers; see TypeInteger
+    static final byte TTUPLE  = 6; // Tuples; finite collections of unrelated Types, kept in parallel
 
     public final byte _type;
 
     public boolean is_simple() { return _type < TSIMPLE; }
-    private static final String[] STRS = new String[]{"Bot","Top","Ctrl"};
+    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 boolean isConstant() { return _type == TTOP; }
+    public boolean isConstant() { return _type == TTOP || _type == TXCTRL; }
 
     public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
 
-    public Type meet(Type other) { return BOTTOM; }
+    public final Type meet(Type t) {
+        // Shortcut for the self case
+        if( t == this ) return this;
+        // Same-type is always safe in the subclasses
+        if( _type==t._type ) return xmeet(t);
+        // 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
+    }
+
+    // Compute meet right now.  Overridden in subclasses.
+    // Handle cases where 'this.is_simple()' and unequal to 't'.
+    // Subclassed xmeet calls can assert that '!t.is_simple()'.
+    protected Type xmeet(Type t) {
+        assert is_simple(); // Should be overridden in subclass
+        // ANY meet anything is thing; thing meet ALL is ALL
+        if( _type==TBOT || t._type==TTOP ) return this;
+        if( _type==TTOP || t._type==TBOT ) return    t;
+        // 'this' is {TCTRL,TXCTRL}
+        if( !t.is_simple() ) return BOTTOM;
+        // 't' is {TCTRL,TXCTRL}
+        return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL;
+    }
 
     @Override
     public final String toString() {
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index cbaff45f..a9f6ee1c 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -41,7 +41,7 @@ public class TypeInteger extends Type {
     public long value() { return _con; }
 
     @Override
-    public Type meet(Type other) {
+    public Type xmeet(Type other) {
         if( this==other ) return this;
         if (!(other instanceof TypeInteger i)) return super.meet(other);
         // BOT wins
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index da701865..39d8f72b 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -10,7 +10,7 @@ public class TypeTuple extends Type {
     }
 
     @Override
-    public Type meet(Type other) {
+    public Type xmeet(Type other) {
         throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented");
     }
 
@@ -24,5 +24,9 @@ public class TypeTuple extends Type {
         return sb;
     }
 
-    public static final TypeTuple IF = new TypeTuple(new Type[]{Type.CONTROL,Type.CONTROL});
+    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});
+
 }