From ff11dd42bb845ad4a979b8924c678addb8681801 Mon Sep 17 00:00:00 2001
From: Dibyendu Majumdar <mobile@majumdar.org.uk>
Date: Sat, 11 Nov 2023 23:17:22 +0000
Subject: Chapter 6: Peepholes for If

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>
---
 .../com/seaofnodes/simple/GraphVisualizer.java     |  21 +-
 src/main/java/com/seaofnodes/simple/Parser.java    |   3 +-
 .../java/com/seaofnodes/simple/node/AddNode.java   |  67 +++--
 .../java/com/seaofnodes/simple/node/BoolNode.java  |   6 +
 .../java/com/seaofnodes/simple/node/IfNode.java    |  20 +-
 .../java/com/seaofnodes/simple/node/MulNode.java   |   6 +
 src/main/java/com/seaofnodes/simple/node/Node.java |  31 ++-
 .../java/com/seaofnodes/simple/node/PhiNode.java   |  28 +-
 .../java/com/seaofnodes/simple/node/ProjNode.java  |   2 +
 .../com/seaofnodes/simple/node/RegionNode.java     |  50 +++-
 .../com/seaofnodes/simple/node/ReturnNode.java     |   6 +-
 .../java/com/seaofnodes/simple/node/ScopeNode.java |   4 +-
 .../java/com/seaofnodes/simple/node/StartNode.java |   5 +
 .../java/com/seaofnodes/simple/node/StopNode.java  |   5 +
 src/main/java/com/seaofnodes/simple/type/Type.java |  37 ++-
 .../com/seaofnodes/simple/type/TypeInteger.java    |   2 +-
 .../java/com/seaofnodes/simple/type/TypeTuple.java |   8 +-
 .../java/com/seaofnodes/simple/Chapter02Test.java  |   4 -
 .../java/com/seaofnodes/simple/Chapter03Test.java  |   4 +-
 .../java/com/seaofnodes/simple/Chapter04Test.java  |  20 +-
 .../java/com/seaofnodes/simple/Chapter05Test.java  |  18 +-
 .../java/com/seaofnodes/simple/Chapter06Test.java  | 294 +++++++++++++++++++++
 22 files changed, 559 insertions(+), 82 deletions(-)
 create mode 100644 src/test/java/com/seaofnodes/simple/Chapter06Test.java

(limited to 'src')

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});
+
 }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java
index 4085ed7e..47cee096 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java
@@ -14,8 +14,6 @@ public class Chapter02Test {
         Node._disablePeephole = true; // disable peephole so we can observe full graph
         StopNode ret = parser.parse();
         assertEquals("return (1+((2*3)+(-5)));", ret.print());
-        GraphVisualizer gv = new GraphVisualizer();
-        System.out.println(gv.generateDotOutput(parser));
         Node._disablePeephole = false;
     }
 
@@ -59,8 +57,6 @@ public class Chapter02Test {
         Parser parser = new Parser("return 1+2*3+-5;");
         StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
-        GraphVisualizer gv = new GraphVisualizer();
-        System.out.println(gv.generateDotOutput(parser));
     }
 
 }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
index 407fbe48..33e2e824 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -31,7 +31,7 @@ public class Chapter03Test {
 
     @Test
     public void testVarScopeNoPeephole() {
-        Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;");
+        Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;");
         Node._disablePeephole = true;
         StopNode ret = parser.parse();
         Node._disablePeephole = false;
@@ -40,7 +40,7 @@ public class Chapter03Test {
 
     @Test
     public void testVarDist() {
-        Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;");
+        Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);");
         StopNode ret = parser.parse();
         assertEquals("return 8;", ret.print());
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
index cde23324..2b6b5ae2 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
@@ -10,7 +10,7 @@ public class Chapter04Test {
 
     @Test
     public void testPeephole() {
-        Parser parser = new Parser("return 1+arg+2; #showGraph;");
+        Parser parser = new Parser("return 1+arg+2;");
         StopNode ret = parser.parse();
         assertEquals("return (arg+3);", ret.print());
     }
@@ -38,7 +38,7 @@ public class Chapter04Test {
 
     @Test
     public void testPeephole3() {
-        Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;");
+        Parser parser = new Parser("return 1+arg+2+arg+3;");
         StopNode ret = parser.parse();
         assertEquals("return ((arg*2)+6);", ret.print());
     }
@@ -52,7 +52,7 @@ public class Chapter04Test {
 
     @Test
     public void testVarArg() {
-        Parser parser = new Parser("return arg; #showGraph;");
+        Parser parser = new Parser("return arg;");
         StopNode stop = parser.parse();
         ReturnNode ret = stop.ret();
         assertTrue(ret.in(0) instanceof ProjNode);
@@ -61,49 +61,49 @@ public class Chapter04Test {
 
     @Test
     public void testConstantArg() {
-        Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2));
+        Parser parser = new Parser("return arg;", TypeInteger.constant(2));
         StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
     }
 
     @Test
     public void testCompEq() {
-        Parser parser = new Parser("return 3==3; #showGraph;");
+        Parser parser = new Parser("return 3==3;");
         StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testCompEq2() {
-        Parser parser = new Parser("return 3==4; #showGraph;");
+        Parser parser = new Parser("return 3==4;");
         StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testCompNEq() {
-        Parser parser = new Parser("return 3!=3; #showGraph;");
+        Parser parser = new Parser("return 3!=3;");
         StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testCompNEq2() {
-        Parser parser = new Parser("return 3!=4; #showGraph;");
+        Parser parser = new Parser("return 3!=4;");
         StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testBug1() {
-        Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;");
+        Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2;");
         StopNode ret = parser.parse();
         assertEquals("return (arg+3);", ret.print());
     }
 
     @Test
     public void testBug2() {
-        Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;");
+        Parser parser = new Parser("int a=arg+1; a=a; return a;");
         StopNode ret = parser.parse();
         assertEquals("return (arg+1);", ret.print());
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index b5fcbeaf..134a8be2 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -17,11 +17,9 @@ if (arg == 1)
     a = arg+2;
 else {
     a = arg-3;
-    #showGraph;
 }
-#showGraph;
 return a;""");
-        StopNode ret = parser.parse(true);
+        StopNode ret = parser.parse(false);
         assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString());
     }
 
@@ -36,7 +34,7 @@ if (arg == 1) {
     c = 4;
 }
 return c;""", TypeInteger.BOT);
-        StopNode ret = parser.parse(true);
+        StopNode ret = parser.parse(false);
         assertEquals("return Phi(Region16,4,3);", ret.toString());
     }
 
@@ -48,7 +46,7 @@ if( arg==1 )
     return 3;
 else
     return 4;
-#showGraph;""", TypeInteger.BOT);
+""", TypeInteger.BOT);
         StopNode stop = parser.parse();
         assertEquals("Stop[ return 3; return 4; ]", stop.toString());
     }
@@ -64,7 +62,7 @@ if( arg==1 )
 else
     b=a+1;
 return a+b;""");
-        StopNode ret = parser.parse(true);
+        StopNode ret = parser.parse(false);
         assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString());
     }
 
@@ -79,7 +77,7 @@ if( arg==1 )
 else
     a=b+1;
 return a+b;""");
-        StopNode ret = parser.parse(true);
+        StopNode ret = parser.parse(false);
         assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString());
     }
 
@@ -98,7 +96,7 @@ else if( arg==3 )
 else
     a=5;
 return a;
-#showGraph;""", TypeInteger.BOT);
+""", TypeInteger.BOT);
         StopNode stop = parser.parse();
         assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString());
     }
@@ -114,7 +112,7 @@ if( arg )
 if( arg==0 )
     b=2;
 return arg+a+b;
-#showGraph;""", TypeInteger.BOT);
+""", TypeInteger.BOT);
         StopNode stop = parser.parse();
         assertEquals("return ((arg+Phi(Region13,1,0))+Phi(Region22,2,0));", stop.toString());
     }
@@ -129,7 +127,7 @@ if( arg==1 )
     a=arg==3;
 }
 return a;""");
-        StopNode ret = parser.parse(true);
+        StopNode ret = parser.parse(false);
         assertEquals("return (arg==Phi(Region16,3,2));", ret.toString());
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
new file mode 100644
index 00000000..44b49d73
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -0,0 +1,294 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+
+public class Chapter06Test {
+
+    @Test
+    public void testPeepholeReturn() {
+        Parser parser = new Parser(
+"""
+if( true ) return 2;
+return 1;
+""");
+        StopNode stop = parser.parse(false);
+        assertEquals("return 2;", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+    @Test
+    public void testPeepholeRotate() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+if (arg)
+    a = 2;
+return (arg < a) < 3;
+""");
+        StopNode stop = parser.parse(false);
+        assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString());
+    }
+
+    @Test
+    public void testPeepholeCFG() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( true )
+  a=2;
+else
+  a=3;
+return a;
+""");
+        StopNode stop = parser.parse(false);
+        assertEquals("return 2;", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+    @Test
+    public void testIfIf() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg!=1 )
+    a=2;
+else
+    a=3;
+int b=4;
+if( a==2 )
+    b=42;
+else
+    b=5;
+return b;""", TypeInteger.BOT);
+        StopNode stop = parser.parse(false);
+        assertEquals("return Phi(Region32,42,5);", stop.toString());
+    }
+
+    @Test
+    public void testIfArgIf() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( 1==1 )
+    a=2;
+else
+    a=3;
+int b=4;
+if( arg==2 )
+    b=a;
+else
+    b=5;
+return b;""", TypeInteger.BOT);
+        StopNode stop = parser.parse(false);
+        assertEquals("return Phi(Region28,2,5);", stop.toString());
+    }
+
+    @Test
+    public void testMerge3With2() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( arg==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.constant(2));
+        StopNode stop = parser.parse();
+        assertEquals("return 5;", stop.toString());
+    }
+
+    @Test
+    public void testMerge3With1() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( arg==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.constant(1));
+        StopNode stop = parser.parse(false);
+        assertEquals("return 3;", stop.toString());
+    }
+
+    @Test
+    public void testMerge3Peephole() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( 1==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.BOT);
+        StopNode stop = parser.parse(false);
+        assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString());
+    }
+
+    @Test
+    public void testMerge3Peephole1() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( 1==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.constant(1));
+        StopNode stop = parser.parse(false);
+        assertEquals("return 3;", stop.toString());
+    }
+
+    @Test
+    public void testMerge3Peephole3() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( 1==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.constant(3));
+        StopNode stop = parser.parse(false);
+        assertEquals("return 4;", stop.toString());
+    }
+
+    @Test
+    public void testDemo1NonConst() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+if( arg ) {
+    a = 2;
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b;
+""");
+        StopNode ret = parser.parse(false);
+        assertEquals("return Phi(Region22,4,1);", ret.toString());
+    }
+
+
+    @Test
+    public void testDemo1True() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+if( arg ) {
+    a = 2;
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b;
+""", TypeInteger.constant(1));
+        StopNode ret = parser.parse(false);
+        assertEquals("return 4;", ret.toString());
+    }
+
+    @Test
+    public void testDemo1False() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+if( arg ) {
+    a = 2;
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b;
+""", TypeInteger.constant(0));
+        StopNode ret = parser.parse(false);
+        assertEquals("return 1;", ret.toString());
+    }
+
+    @Test
+    public void testDemo2NonConst() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+int c = 0;
+if( arg ) {
+    a = 1;
+    if( arg==2 ) { c=2; } else { c=3; }
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b+c;
+""");
+        StopNode ret = parser.parse(false);
+        assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region33,3,1));", ret.toString());
+    }
+
+
+    @Test
+    public void testDemo2True() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+int c = 0;
+if( arg ) {
+    a = 1;
+    if( arg==2 ) { c=2; } else { c=3; }
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b+c;
+""", TypeInteger.constant(1));
+        StopNode ret = parser.parse(false);
+        assertEquals("return 6;", ret.toString());
+    }
+
+    @Test
+    public void testDemo2arg2() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+int c = 0;
+if( arg ) {
+    a = 1;
+    if( arg==2 ) { c=2; } else { c=3; }
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b+c;
+""", TypeInteger.constant(2));
+        StopNode ret = parser.parse(false);
+        assertEquals("return 5;", ret.toString());
+    }
+
+}
-- 
cgit v1.2.3