Chapter 6: Peepholes for Iflinear-chapter06

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

17 files changed, 245 insertions, 56 deletions

diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index c35a4e32..b30dd450 100644
--- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -17,7 +17,7 @@ public class GraphVisualizer {
         // nodes in the graph.
         Collection<Node> all = findAll(parser);
         StringBuilder sb = new StringBuilder();
-        sb.append("digraph chapter05 {\n");
+        sb.append("digraph chapter06 {\n");
         sb.append("/*\n");
         sb.append(parser.src());
         sb.append("\n*/\n");
@@ -207,29 +207,24 @@ public class GraphVisualizer {
      * Finds all nodes in the graph.
      */
     private Collection<Node> findAll(Parser parser) {
-        final StartNode start = Parser.START;
         final HashMap<Integer, Node> all = new HashMap<>();
-        for( Node n : start._outputs )
+        for( Node n : Parser.START._outputs )
+            walk(all, n);
+        for( Node n : parser._scope._inputs )
             walk(all, n);
-        // Scan symbol tables
-        for( HashMap<String,Integer> scope : parser._scope._scopes )
-            for (Integer i : scope.values())
-                walk(all, parser._scope.in(i));
         return all.values();
     }
 
     /**
      * Walk a subgraph and populate distinct nodes in the all list.
      */
-    private void walk(HashMap<Integer, Node> all, Node n) {
+    private void walk(HashMap<Integer,Node> all, Node n) {
         if(n == null ) return;
         if (all.get(n._nid) != null) return; // Been there, done that
         all.put(n._nid, n);
         for (Node c : n._inputs)
-            if (c != null)
-                walk(all, c);
-        for (Node c : n._outputs)
-            if (c != null)
-                walk(all, c);
+            walk(all, c);
+        for( Node c : n._outputs )
+            walk(all, c);
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index 80674d59..1a15efa3 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -155,6 +155,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
@@ -198,7 +199,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 081c9276..b37785f6 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -63,7 +63,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 spline_cmp(lhs,rhs) ? swap12() : null;
+            // Rotate; look for (add (phi cons) con/(phi cons))
+            return spline_cmp(lhs,rhs) ? swap12() : phiCon(this,true);
 
         // Now we only see (add add non)
 
@@ -72,23 +73,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 spline via rotates, to gather similar things together.
 
@@ -100,6 +90,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-spline 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 7a4a087e..a9ec6838 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -43,6 +43,12 @@ abstract public class BoolNode extends Node {
         if( in(1)==in(2) )
             return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0));
 
+        // 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,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 6124b893..34846e99 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -26,7 +26,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 2dbdd695..0380c079 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -44,6 +44,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 5412108b..97ba68ab 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -46,9 +46,19 @@ public abstract class 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>}
+     */
+    int _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;
@@ -151,6 +161,17 @@ public abstract class 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.
@@ -358,6 +379,14 @@ public abstract class Node {
         return true;
     }
 
+    // Return the immediate dominator of this Node and compute dom tree depth.
+    Node idom() {
+        Node idom = in(0);
+        if( idom._idepth==0 ) idom.idom(); // Recursively set _idepth
+        if( _idepth==0 ) _idepth = idom._idepth+1;
+        return idom;
+    }
+
     // 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 374e1183..15088e08 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -26,14 +26,18 @@ public class PhiNode extends Node {
 
     @Override
     public Type compute() {
-        return Type.BOTTOM;
+        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.
@@ -63,11 +67,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 2826d192..85f28037 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -35,6 +35,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 5d520d65..bb7998a3 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
 public class RegionNode extends Node {
@@ -17,11 +18,58 @@ 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.
+    private Node _idom;         // Immediate dominator cache
+    @Override Node idom() {
+        if( _idom != null ) return _idom; // Return cached copy
+        if( nIns()!=3 ) return null;      // Fails for anything other than 2-inputs
+        // Walk the LHS & RHS idom trees in parallel until they match, or either fails
+        Node lhs = in(1).idom();
+        Node rhs = in(2).idom();
+        while( lhs != rhs ) {
+          if( lhs==null || rhs==null ) return null;
+          var comp = lhs._idepth - rhs._idepth;
+          if( comp >= 0 ) lhs = lhs.idom();
+          if( comp <= 0 ) rhs = rhs.idom();
+        }
+        if( lhs==null ) return null;
+        _idepth = lhs._idepth+1;
+        return (_idom=lhs);
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index c9d6c9c8..6130d050 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -36,5 +36,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 32045fbc..a7a04a42 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -162,14 +162,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 022e276d..c5a45876 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -35,4 +35,9 @@ public class StartNode extends MultiNode {
 
     @Override
     public Node idealize() { return null; }
+
+    // No immediate dominator, and idepth==0
+    @Override
+    Node idom() { return null; }
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index a30256f9..01574dc7 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -36,6 +36,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/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java
index d0916312..2f0e6171 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 9fb4b853..b30e21d8 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 33417eb2..0f8b95bd 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});
+
 }