From 30aa804f95d47c60f42fd8bfd38fb2e947dc4fc7 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 20 Oct 2023 15:21:08 -0700 Subject: Chapter 4: External Argument and Comparisons MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Yichen Yan Co-authored-by: Thalia Archibald Co-authored-by: Tamas Hadhazy Co-authored-by: Hels15 Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: RobertObkircher --- .../com/seaofnodes/simple/GraphVisualizer.java | 65 +++++++--- src/main/java/com/seaofnodes/simple/Parser.java | 57 +++++++-- .../java/com/seaofnodes/simple/node/AddNode.java | 64 +++++++++- .../java/com/seaofnodes/simple/node/BoolNode.java | 52 ++++++++ .../com/seaofnodes/simple/node/ConstantNode.java | 3 +- .../java/com/seaofnodes/simple/node/DivNode.java | 8 +- .../java/com/seaofnodes/simple/node/MulNode.java | 19 ++- .../java/com/seaofnodes/simple/node/MultiNode.java | 7 ++ src/main/java/com/seaofnodes/simple/node/Node.java | 114 +++++++++++++++--- .../java/com/seaofnodes/simple/node/NotNode.java | 28 +++++ .../java/com/seaofnodes/simple/node/ProjNode.java | 40 +++++++ .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 18 ++- .../java/com/seaofnodes/simple/node/StartNode.java | 11 +- .../java/com/seaofnodes/simple/node/SubNode.java | 9 +- src/main/java/com/seaofnodes/simple/type/Type.java | 20 +++- .../com/seaofnodes/simple/type/TypeInteger.java | 44 +++++-- .../java/com/seaofnodes/simple/type/TypeTuple.java | 26 ++++ .../java/com/seaofnodes/simple/Chapter01Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 1 + .../java/com/seaofnodes/simple/Chapter04Test.java | 133 +++++++++++++++++++++ 21 files changed, 651 insertions(+), 72 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/node/BoolNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MultiNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/NotNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ProjNode.java create mode 100644 src/main/java/com/seaofnodes/simple/type/TypeTuple.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter04Test.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 9dfac52d..62b434f3 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 all = findAll(parser); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter03 {\n"); + sb.append("digraph chapter04 {\n"); sb.append("/*\n"); sb.append(parser.src()); sb.append("\n*/\n"); @@ -57,15 +57,45 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name for( Node n : all ) { - if( n instanceof ScopeNode ) - continue; // Do not emit, rolled into Scope cluster already + if( n instanceof ProjNode || n instanceof ScopeNode ) + continue; // Do not emit, rolled into MultiNode or Scope cluster already sb.append("\t\t").append(n.uniqueName()).append(" [ "); String lab = n.glabel(); - // control nodes have box shape - // other nodes are ellipses, i.e. default shape - if( n.isCFG() ) - sb.append("shape=box style=filled fillcolor=yellow "); - sb.append("label=\"").append(lab).append("\" "); + if( n instanceof MultiNode ) { + // Make a box with the MultiNode on top, and all the projections on the bottom + sb.append("shape=plaintext label=<\n"); + sb.append("\t\t\t\n"); + sb.append("\t\t\t\n"); + sb.append("\t\t\t"); + boolean doProjTable = false; + for( Node use : n._outputs ) { + if( use instanceof ProjNode proj ) { + if (!doProjTable) { + doProjTable = true; + sb.append(""); + } + sb.append("\n"); + sb.append("\t\t\t
").append(lab).append("
").append("\n"); + sb.append("\t\t\t\t").append("\n"); + sb.append("\t\t\t\t"); + } + sb.append(""); + } + } + if (doProjTable) { + sb.append("").append("\n"); + sb.append("\t\t\t\t
").append(proj.glabel()).append("
").append("\n"); + sb.append("\t\t\t
>\n\t\t"); + + } else { + // control nodes have box shape + // other nodes are ellipses, i.e. default shape + if( n.isCFG() ) + sb.append("shape=box style=filled fillcolor=yellow "); + sb.append("label=\"").append(lab).append("\" "); + } sb.append("];\n"); } sb.append("\t}\n"); // End Node cluster @@ -101,22 +131,24 @@ public class GraphVisualizer { // All them edge labels sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n"); for( Node n : all ) { - // In this chapter we do display the Constant->Start edge; + // Do not display the Constant->Start edge; + // ProjNodes handled by Multi; // ScopeNodes are done separately - if( n instanceof ScopeNode ) + if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof ScopeNode ) continue; int i=0; for( Node def : n._inputs ) { if( def != null ) { // Most edges land here use->def sb.append('\t').append(n.uniqueName()).append(" -> "); - sb.append(def.uniqueName()); + if( def instanceof ProjNode proj ) { + String mname = proj.ctrl().uniqueName(); + sb.append(mname).append(":p").append(proj._idx); + } else sb.append(def.uniqueName()); // Number edges, so we can see how they track sb.append("[taillabel=").append(i); - if( n instanceof ConstantNode && def instanceof StartNode ) - sb.append(" style=dotted"); // control edges are colored red - else if( def.isCFG() ) + if( def.isCFG() ) sb.append(" color=red"); sb.append("];\n"); } @@ -138,7 +170,10 @@ public class GraphVisualizer { .append(scopeName).append(":") .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted .append(" -> "); - sb.append(def.uniqueName()); + if( def instanceof ProjNode proj ) { + String mname = proj.ctrl().uniqueName(); + sb.append(mname).append(":p").append(proj._idx); + } else sb.append(def.uniqueName()); sb.append(";\n"); } level++; diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index fa1a852c..ff2c0504 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -14,6 +14,7 @@ import java.util.*; */ public class Parser { + /** * A Global Static, unique to each compilation. This is a public, so we * can make constants everywhere without having to thread the StartNode @@ -27,7 +28,7 @@ public class Parser { private final Lexer _lexer; /** - * Stack of lexical scopes, each scope is a symbol table that binds + * A ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds * variable names to Nodes. The top of this stack represents current scope. */ public ScopeNode _scope; @@ -41,18 +42,38 @@ public class Parser { }}; - public Parser(String source) { - _lexer = new Lexer(source); + public Parser(String source, TypeInteger arg) { Node.reset(); + _lexer = new Lexer(source); _scope = new ScopeNode(); - START = new StartNode(); + START = new StartNode(new Type[]{ Type.CONTROL, arg }); + START.peephole(); + } + + public Parser(String source) { + this(source, TypeInteger.BOT); } + @Override + public String toString() { return _lexer.toString(); } + String src() { return new String( _lexer._input ); } + // Debugging utility to find a Node by index + public static Node find(int nid) { return START.find(nid); } + + private Node ctrl() { return _scope.ctrl(); } + + private Node ctrl(Node n) { return _scope.ctrl(n); } + public ReturnNode parse() { return parse(false); } public ReturnNode parse(boolean show) { + // Enter a new scope for the initial control and arguments + _scope.push(); + _scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole()); + _scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); var ret = (ReturnNode) parseBlock(); + _scope.pop(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); if( show ) showGraph(); return ret; @@ -99,6 +120,7 @@ public class Parser { /** * Parses a return statement; "return" already parsed. + * The $ctrl edge is killed. * * 
      *     'return' expr ;
@@ -107,7 +129,9 @@ public class Parser {
      */
     private Node parseReturn() {
         var expr = require(parseExpression(), ";");
-        return new ReturnNode(START, expr).peephole();
+        Node ret = new ReturnNode(ctrl(), expr).peephole();
+        ctrl(null);             // Kill control
+        return ret;
     }
 
     /**
@@ -158,11 +182,30 @@ public class Parser {
      * Parse an expression of the form:
      *
      * 
-     *     expr : additiveExpr
+     *     expr : compareExpr
      * 

      * @return an expression {@link Node}, never {@code null}
      */
-    private Node parseExpression() { return parseAddition(); }
+    private Node parseExpression() { return parseComparison(); }
+
+    /**
+     * Parse an expression of the form:
+     *
+     * 
+     *     expr : additiveExpr op additiveExpr
+     * 

+     * @return an comparator expression {@link Node}, never {@code null}
+     */
+    private Node parseComparison() {
+        var lhs = parseAddition();
+        if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole();
+        if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole();
+        if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole();
+        if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole();
+        if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole();
+        if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole();
+        return lhs;
+    }
 
     /**
      * Parse an additive expression
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 7c1968c5..5720aca4 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -23,14 +23,76 @@ public class AddNode extends Node {
             in(2)._type instanceof TypeInteger i1 ) {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()+i1.value());
+            return i0.meet(i1);
         }
         return Type.BOTTOM;
     }
 
     @Override
     public Node idealize () {
-        // TODO: add of 0, and many other peepholes added in Chaper04
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t1 = lhs._type;
+        Type t2 = rhs._type;
+
+        // Already handled by peephole constant folding
+        assert !(t1.isConstant() && t2.isConstant());
+
+        // Add of 0.  We do not check for (0+x) because this will already
+        // canonicalize to (x+0)
+        if( t2 instanceof TypeInteger i && i.value()==0 )
+            return lhs;
+
+        // Add of same to a multiply by 2
+        if( lhs==rhs )
+            return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole());
+
+        // Goal: a left-spine set of adds, with constants on the rhs (which then fold).
+
+        // Move non-adds to RHS
+        if( !(lhs instanceof AddNode) && rhs instanceof AddNode )
+            return swap12();
+
+        // Now we might see (add add non) or (add non non) or (add add add) but never (add non add)
+
+        // Do we have  x + (y + z) ?
+        // Swap to    (x + y) + z
+        // Rotate (add add add) to remove the add on RHS
+        if( rhs instanceof AddNode add )
+            return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2));
+
+        // 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;
+
+        // Now we only see (add add non)
+
+        // Do we have (x + con1) + con2?
+        // Replace with (x + (con1+con2) which then fold the constants
+        if( lhs.in(2)._type.isConstant() && t2.isConstant() )
+            return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole());
+
+        // Now we sort along the spline via rotates, to gather similar things together.
+
+        // Do we rotate (x + y) + z
+        // into         (x + z) + y ?
+        if( spline_cmp(lhs.in(2),rhs) )
+            return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2));
+
         return 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 others.
+    // Ties with in a category sort by node ID.
+    // TRUE if swapping hi and lo.
+    static boolean spline_cmp( Node hi, Node lo ) {
+        if( lo._type.isConstant() ) return false;
+        if( hi._type.isConstant() ) return true ;
+
+        // Same category of "others"
+        return lo._nid > hi._nid;
+    }
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
new file mode 100644
index 00000000..05495790
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -0,0 +1,52 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+abstract public class BoolNode extends Node {
+
+    public BoolNode(Node lhs, Node rhs) {
+        super(null, lhs, rhs);
+    }
+
+    abstract String op();       // String opcode name
+
+    @Override
+    public String label() { return getClass().getSimpleName(); }
+
+    @Override
+    public String glabel() { return op(); }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append(op()));
+        return sb.append(")");
+    }
+
+    @Override
+    public Type compute() {
+        if( in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1 ) {
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0);
+            return i0.meet(i1);
+        }
+        return Type.BOTTOM;
+    }
+
+    abstract boolean doOp(long lhs, long rhs);
+
+    @Override
+    public Node idealize() {
+        // Compare of same
+        if( in(1)==in(2) )
+            return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0));
+
+        return null;
+    }
+
+    public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } }
+    public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs <  rhs; } }
+    public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 43a22426..85277d82 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -23,7 +23,7 @@ public class ConstantNode extends Node {
     }
 
     @Override
-    public String label() { return "#"+_con; }
+    public String label() { return ""+_con; }
 
     @Override
     public String uniqueName() { return "Con_" + _nid; }
@@ -38,5 +38,4 @@ public class ConstantNode extends Node {
 
     @Override
     public Node idealize() { return null; }
-
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java
index e3c3616a..3b3a4436 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -25,10 +25,16 @@ public class DivNode extends Node {
                 return i1.value() == 0
                     ? TypeInteger.ZERO
                     : TypeInteger.constant(i0.value()/i1.value());
+            return i0.meet(i1);
         }
         return Type.BOTTOM;
     }
 
     @Override
-    public Node idealize() { return null; }
+    public Node idealize() {
+        // Div of 1.
+        if( in(2)._type.isConstant() && in(2)._type instanceof TypeInteger i && i.value()==1 )
+            return in(1);
+        return null;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 26c28281..36d5eb3e 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -23,10 +23,27 @@ public class MulNode extends Node {
             in(2)._type instanceof TypeInteger i1) {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()*i1.value());
+            return i0.meet(i1);
         }
         return Type.BOTTOM;
     }
 
     @Override
-    public Node idealize() { return null; }
+    public Node idealize() {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t1 = lhs._type;
+        Type t2 = rhs._type;
+
+        // Mul of 1.  We do not check for (1*x) because this will already
+        // canonicalize to (x*1)
+        if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 )
+            return lhs;
+
+        // Move constants to RHS: con*arg becomes arg*con
+        if ( t1.isConstant() && !t2.isConstant() )
+            return swap12();
+
+        return null;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java
new file mode 100644
index 00000000..7ba1aa19
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -0,0 +1,7 @@
+package com.seaofnodes.simple.node;
+
+public abstract class MultiNode extends Node {
+
+    public MultiNode(Node... inputs) { super(inputs); }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 6e4617ff..2c0e3832 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -81,14 +81,7 @@ public abstract class Node {
     // line (because this is what a debugger typically displays by default) and
     // has to be robust with broken graph/nodes.
     @Override
-    public final String toString() {
-        // TODO: The print evolves in later chapters.  For now, a simple
-        // recursive print does well.  Later with control flow and later still
-        // with loops, we need some serious algorithm work to get a decent
-        // print.  So you should consider the "print" to always be a work-in-
-        // progress as we march through the chapters.
-        return print();
-    }
+    public final String toString() {  return print(); }
 
     // This is a *deep* print.  This version will fail on cycles, which we will
     // correct later when we can parse programs with loops.  We print with a
@@ -125,8 +118,6 @@ public abstract class Node {
 
     public boolean isCFG() { return false; }
 
-
-
     /**
      * Change a def into a Node.  Keeps the edges correct, by removing
      * the corresponding use->def edge.  This may make the original
@@ -184,11 +175,11 @@ public abstract class Node {
     // Error is 'use' does not exist; ok for 'use' to be null.
     protected boolean delUse( Node use ) {
         Utils.del(_outputs, Utils.find(_outputs, use));
-        return _outputs.size() == 0;
+        return _outputs.isEmpty();
     }
 
     // Shortcut for "popping" n nodes.  A "pop" is basically a
-    // set_def(last,null) followed by lowering the nIns() count.
+    // setDef(last,null) followed by lowering the nIns() count.
     void popN(int n) {
         for( int i=0; i N keep() { addUse(null); return (N)this; }
+    // Remove bogus null.
+    public  N unkeep() { delUse(null); return (N)this; }
+    // ------------------------------------------------------------------------
+    // Graph-based optimizations
+
     /**
      * We allow disabling peephole opt so that we can observe the
      * full graph, vs the optimized graph.
@@ -226,7 +226,11 @@ public abstract class Node {
      * 
  • in a future chapter we will look for a
      * Common Subexpression
      * to eliminate.
    • 
-     * 
  • we ask the Node for a better replacement (again, none enabled in this chapter)
    • 
+     * 
  • we ask the Node for a better replacement.  The "better replacement"
+     * is things like {@code (1+2)} becomes {@code 3} and {@code (1+(x+2))} becomes
+     * {@code (x+(1+2))}.  By canonicalizing expressions we fold common addressing
+     * math constants, remove algebraic identities and generally simplify the
+     * code. 
    • 
      * 
      */
     public final Node peephole( ) {
@@ -237,20 +241,37 @@ public abstract class Node {
             return this;        // Peephole optimizations turned off
 
         // Replace constant computations from non-constants with a constant node
-        if (!(this instanceof ConstantNode) && type.isConstant()) {
-            kill();             // Kill `this` because replacing with a Constant
-            return new ConstantNode(type).peephole();
-        }
+        if (!(this instanceof ConstantNode) && type.isConstant())
+            return deadCodeElim(new ConstantNode(type).peephole());
 
         // Future chapter: Global Value Numbering goes here
 
         // Ask each node for a better replacement
         Node n = idealize();
-        if( n != null ) return n;
+        if( n != null )         // Something changed
+            // Recursively optimize
+            return deadCodeElim(n.peephole());
 
         return this;            // No progress
     }
 
+    // m is the new Node, self is the old.
+    // Return 'm', which may have zero uses but is alive nonetheless.
+    // If self has zero uses (and is not 'm'), {@link #kill} self.
+    private Node deadCodeElim(Node m) {
+        // If self is going dead and not being returned here (Nodes returned
+        // from peephole commonly have no uses (yet)), then kill self.
+        if( m != this && isUnused() ) {
+            // Killing self - and since self recursively kills self's inputs we
+            // might end up killing 'm', which we are returning as a live Node.
+            // So we add a bogus extra null output edge to stop kill().
+            m.keep();      // Keep m alive
+            kill();        // Kill self because replacing with 'm'
+            m.unkeep();    // Okay to peephole m
+        }
+        return m;
+    }
+
     /**
      * This function needs to be
      * Monotonic
@@ -269,8 +290,65 @@ public abstract class Node {
      */
     public abstract Type compute();
 
+    /**
+     * This function rewrites the current Node into a more "idealized" form.
+     * This is the bulk of our peephole rewrite rules, and we use this to
+     * e.g. turn arbitrary collections of adds and multiplies with mixed
+     * constants into a normal form that's easy for hardware to implement.
+     * Example: An array addressing expression:
+     * 
       ary[idx+1]
    
+     * might turn into Sea-of-Nodes IR:
+     * 
       (ary+12)+((idx+1) * 4)
    
+     * This expression can then be idealized into:
+     * 
       ary + ((idx*4) + (12 + (1*4)))
    
+     * And more folding:
+     * 
       ary + ((idx<<2) + 16)
    
+     * And during code-gen:
+     * 
       MOV4 Rary,Ridx,16 // or some such hardware-specific notation 
    
+     * 
    
+     * {@link #idealize} has a very specific calling convention:
+     * 
      
+     * 
    • If NO change is made, return {@code null}
+     * 
    • If ANY change is made, return not-null; this can be {@code this}
+     * 
    • The returned Node does NOT call {@link #peephole} on itself; the {@link #peephole} call will recursively peephole it.
+     * 
    • Any NEW nodes that are not directly returned DO call {@link #peephole}.
+     * 
    
+     * 
    
+     * Examples:
+     * 
+     * 
+     * 
+     * 
+     * 
+     * 
        before              after     return comment  
    {@code (x+5)    }{@code   (x+5)  }{@code null  }No change
    {@code (5+x)    }{@code   (x+5)  }{@code this  }Swapped arguments
    {@code ((x+1)+2)}{@code (x+(1+2))}{@code (x+_) }Returns 2 new Nodes
    
+     *
+     * The last entry deserves more discussion.  The new Node {@code (1+2)}
+     * created in {@link #idealize} calls {@link #peephole} (which then folds
+     * into a constant).  The other new Node {@code (x+3)} does not call
+     * peephole, because it is returned and peephole itself will recursively
+     * call peephole.
+     * 
    
+     * Since idealize calls peephole and peephole calls idealize, you must be
+     * careful that all idealizations are monotonic: all transforms remove
+     * some feature, so that the set of available transforms always shrinks.
+     * If you don't, you risk an infinite peephole loop!
+     *
+     * @return Either a new or changed node, or null for no changes.
+     */
     public abstract Node idealize();
 
+
+    // ------------------------------------------------------------------------
+    // Peephole utilities
+
+    // Swap inputs without letting either input go dead during the swap.
+    Node swap12() {
+        Node tmp = in(1);
+        _inputs.set(1,in(2));
+        _inputs.set(2,tmp);
+        return this;
+    }
+
     /**
      * Used to allow repeating tests in the same JVM.  This just resets the
      * Node unique id generator, and is done as part of making a new Parser.
diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java
new file mode 100644
index 00000000..e3683646
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -0,0 +1,28 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class NotNode extends Node {
+    public NotNode(Node in) { super(null, in); }
+
+    @Override public String label() { return "Not"; }
+
+    @Override public String glabel() { return "!"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("(!"));
+        return sb.append(")");
+    }
+
+    @Override
+    public Type compute() {
+        if( in(1)._type instanceof TypeInteger i0 )
+            return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
new file mode 100644
index 00000000..2f49fe91
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -0,0 +1,40 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeTuple;
+
+public class ProjNode extends Node {
+
+    // Which slice of the incoming multi-part value
+    public final int _idx;
+
+    // Debugging label
+    public final String _label;
+
+    public ProjNode(MultiNode ctrl, int idx, String label) {
+        super(ctrl);
+        _idx = idx;
+        _label = label;
+    }
+
+    @Override
+    public String label() { return _label; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) { return sb.append(_label); }
+
+    @Override public boolean isCFG() { return _idx==0; }
+
+    public MultiNode ctrl() { return (MultiNode)in(0); }
+
+    @Override
+    public Type compute() {
+        Type t = ctrl()._type;
+        return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 7fa470f8..c9d6c9c8 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -32,7 +32,7 @@ public class ReturnNode extends Node {
 
     @Override
     public Type compute() {
-        return Type.BOTTOM;
+        return new TypeTuple(ctrl()._type,expr()._type);
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 379ef033..8ffeac64 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -7,12 +7,18 @@ import java.util.*;
 /**
  * The Scope node is purely a parser helper - it tracks names to nodes with a
  * stack of scopes.
- * @see chapter03/README.md
  */
 public class ScopeNode extends Node {
 
     /**
-     * A Stack of symbol tables; a symbol table is a map from names to node indices.
+     * The control is a name that binds to the currently active control
+     * node in the graph
+     */
+    public static final String CTRL = "$ctrl";
+    public static final String ARG0 = "arg";
+
+    /**
+     * Names for every input edge
      */
     public final Stack> _scopes;
 
@@ -49,7 +55,7 @@ public class ScopeNode extends Node {
      * Recover the names for all variable bindings.
      * The result is an array of names that is aligned with the
      * inputs to the Node.
-     * 
    
+     *
      * This is an expensive operation.
      */
     public String[] reverseNames() {
@@ -78,21 +84,21 @@ public class ScopeNode extends Node {
     }
     /**
      * Lookup a name in all scopes starting from most deeply nested.
-     * 
    
+     *
      * @param name Name to be looked up
      * @see #update(String, Node, int)
      */
     public Node lookup( String name ) { return update(name,null,_scopes.size()-1);  }
     /**
      * If the name is present in any scope, then redefine else null
-     * 
    
+     *
      * @param name Name being redefined
      * @param n    The node to bind to the name
      */
     public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); }
     /**
      * Both recursive lookup and update.
-     * 
    
+     *
      * A shared implementation allows us to create lazy phis both during
      * lookups and updates; the lazy phi creation is part of chapter 8.
      *
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 99e240ad..022e276d 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeTuple;
 
 /**
  * The Start node represents the start of the function.  For now, we do not
@@ -9,10 +10,14 @@ import com.seaofnodes.simple.type.Type;
  * will require Projections to extract the values.  We discuss this in detail
  * in Chapter 9: Functions and Calls.
  */
-public class StartNode extends Node {
+public class StartNode extends MultiNode {
 
-    public StartNode(/*arguments go here*/) {
+    final TypeTuple _args;
+
+    public StartNode(Type[] args) {
         super();
+        _args = new TypeTuple(args);
+        _type = _args;
     }
 
     @Override
@@ -26,7 +31,7 @@ public class StartNode extends Node {
     @Override public boolean isCFG() { return true; }
 
     @Override
-    public Type compute() { return Type.BOTTOM; }
+    public TypeTuple compute() { return _args; }
 
     @Override
     public Node idealize() { return null; }
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index d2e32c61..58d757ea 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -19,15 +19,22 @@ public class SubNode extends Node {
 
     @Override
     public Type compute() {
+        // Sub of same is 0
+        if( in(1)==in(2) )
+            return TypeInteger.ZERO;
+
         if (in(1)._type instanceof TypeInteger i0 &&
             in(2)._type instanceof TypeInteger i1) {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()-i1.value());
+            return i0.meet(i1);
         }
         return Type.BOTTOM;
     }
 
     @Override
-    public Node idealize() { return null; }
+    public Node idealize() {
+        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 7ea17bfb..1e50bdda 100644
--- a/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -24,17 +24,29 @@ public class Type {
     // type hierarchy are simple, not that the Type is conceptually simple.
     static final byte TBOT    = 0; // Bottom (ALL)
     static final byte TTOP    = 1; // Top    (ANY)
-    static final byte TSIMPLE = 2; // End of the Simple Types
-    static final byte TINT    = 3; // All Integers; see TypeInteger
+    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
+
     public final byte _type;
 
     public boolean is_simple() { return _type < TSIMPLE; }
-    private static final String[] STRS = new String[]{"Bot","Top"};
+    private static final String[] STRS = new String[]{"Bot","Top","Ctrl"};
     protected Type(byte type) { _type = type; }
 
-    public static final Type BOTTOM   = new Type( TBOT ); // ALL
+    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 boolean isConstant() { return _type == TTOP; }
 
     public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
+
+    public Type meet(Type other) { return Type.BOTTOM; }
+
+    @Override
+    public final String toString() {
+        return print(new StringBuilder()).toString();
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index e0324da5..cbaff45f 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -5,37 +5,59 @@ package com.seaofnodes.simple.type;
  */
 public class TypeInteger extends Type {
 
-    public final static TypeInteger ZERO= new TypeInteger(0);
+    public final static TypeInteger TOP = new TypeInteger(false, 0);
+    public final static TypeInteger BOT = new TypeInteger(false, 1);
+    public final static TypeInteger ZERO= new TypeInteger(true, 0);
+
+    private final boolean _is_con;
 
     /**
-     * The constant value observed for this type
+     * The constant value or
+     * if not constant then 0=bottom, 1=top.
      */
     private final long _con;
 
-    public TypeInteger(long con) {
+    public TypeInteger(boolean is_con, long con) {
         super(TINT);
+        _is_con = is_con;
         _con = con;
     }
 
-    public static TypeInteger constant(long con) { return new TypeInteger(con); }
+    public static TypeInteger constant(long con) { return new TypeInteger(true, con); }
 
-    @Override
-    public String toString() {
-      return print(new StringBuilder()).toString();
-    }
+    public boolean isTop() { return !_is_con && _con==0; }
+    public boolean isBot() { return !_is_con && _con==1; }
 
     @Override
-    public StringBuilder print(StringBuilder sb) { return sb.append(_con); }
+    public StringBuilder print(StringBuilder sb) {
+        if (isTop()) return sb.append("IntTop");
+        if (isBot()) return sb.append("IntBot");
+        return sb.append(_con);
+    }
 
     @Override
-    public boolean isConstant() { return true; }
+    public boolean isConstant() { return _is_con; }
 
     public long value() { return _con; }
 
+    @Override
+    public Type meet(Type other) {
+        if( this==other ) return this;
+        if (!(other instanceof TypeInteger i)) return super.meet(other);
+        // BOT wins
+        if (   isBot() ) return this;
+        if ( i.isBot() ) return i   ;
+        // TOP loses
+        if ( i.isTop() ) return this;
+        if (   isTop() ) return i   ;
+        assert isConstant() && i.isConstant();
+        return _con==i._con ? this : TypeInteger.BOT;
+    }
+
     @Override
     public boolean equals( Object o ) {
         if( o==this ) return true;
         if( !(o instanceof TypeInteger i) ) return false;
-        return _con==i._con;
+        return _con==i._con && _is_con==i._is_con;
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
new file mode 100644
index 00000000..52befa38
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -0,0 +1,26 @@
+package com.seaofnodes.simple.type;
+
+public class TypeTuple extends Type {
+
+    public final Type[] _types;
+
+    public TypeTuple(Type... _types) {
+        super(TTUPLE);
+        this._types = _types;
+    }
+
+    @Override
+    public Type meet(Type other) {
+        throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented");
+    }
+
+    @Override
+    public StringBuilder print(StringBuilder sb) {
+        sb.append("[ ");
+        for( Type t : _types )
+            t.print(sb).append(",");
+        sb.setLength(sb.length()-1);
+        sb.append("]");
+        return sb;
+    }
+}
diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java
index 311ca23b..3d568337 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java
@@ -14,7 +14,7 @@ public class Chapter01Test {
         ReturnNode ret = parser.parse();
         StartNode start = Parser.START;
 
-        assertEquals(start, ret.ctrl());
+        assertTrue(ret.ctrl() instanceof ProjNode);
         Node expr = ret.expr();
         if( expr instanceof ConstantNode con ) {
             assertEquals(start,con.in(0));
diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
index 3b8b3449..fc8e97b6 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
 import org.junit.Test;
 
 import static org.junit.Assert.*;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
new file mode 100644
index 00000000..faae0aee
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
@@ -0,0 +1,133 @@
+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 Chapter04Test {
+
+    @Test
+    public void testPeephole() {
+        Parser parser = new Parser("return 1+arg+2; #showGraph;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return (arg+3);", ret.print());
+    }
+
+    @Test
+    public void testPeephole2() {
+        Parser parser = new Parser("return (1+arg)+2;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return (arg+3);", ret.print());
+    }
+
+    @Test
+    public void testAdd0() {
+        Parser parser = new Parser("return 0+arg;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return arg;", ret.print());
+    }
+
+    @Test
+    public void testAddAddMul() {
+        Parser parser = new Parser("return arg+0+arg;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return (arg*2);", ret.print());
+    }
+
+    @Test
+    public void testPeephole3() {
+        Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return ((arg*2)+6);", ret.print());
+    }
+
+    @Test
+    public void testMul1() {
+        Parser parser = new Parser("return 1*arg;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return arg;", ret.print());
+    }
+
+    @Test
+    public void testVarArg() {
+        Parser parser = new Parser("return arg; #showGraph;", TypeInteger.BOT);
+        ReturnNode ret = parser.parse();
+        assertTrue(ret.in(0) instanceof ProjNode);
+        assertTrue(ret.in(1) instanceof ProjNode);
+    }
+
+    @Test
+    public void testConstantArg() {
+        Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2));
+        ReturnNode ret = parser.parse();
+        assertEquals("return 2;", ret.print());
+    }
+
+    @Test
+    public void testCompEq() {
+        Parser parser = new Parser("return 3==3; #showGraph;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 1;", ret.print());
+    }
+
+    @Test
+    public void testCompEq2() {
+        Parser parser = new Parser("return 3==4; #showGraph;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 0;", ret.print());
+    }
+
+    @Test
+    public void testCompNEq() {
+        Parser parser = new Parser("return 3!=3; #showGraph;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 0;", ret.print());
+    }
+
+    @Test
+    public void testCompNEq2() {
+        Parser parser = new Parser("return 3!=4; #showGraph;");
+        ReturnNode 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;");
+        ReturnNode 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;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return (arg+1);", ret.print());
+    }
+
+    @Test
+    public void testBug3() {
+        try {
+            new Parser("inta=1; return a;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Undefined name 'inta'",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testBug4() {
+        Parser parser = new Parser("return -arg;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return (-arg);", ret.print());
+    }
+
+    @Test
+    public void testBug5() {
+        Parser parser = new Parser("return arg--2;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return (arg--2);", ret.print());
+    }
+}
-- 
cgit v1.2.3