Chapter 2: Arithmeticlinear-chapter02

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: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>

14 files changed, 691 insertions, 21 deletions

diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
new file mode 100644
index 00000000..4c625be1
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -0,0 +1,117 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+
+import java.util.*;
+
+/**
+ * Simple visualizer that outputs GraphViz dot format.
+ * The dot output must be saved to a file and run manually via dot to generate the SVG output.
+ * Currently, this is done manually.
+ */
+public class GraphVisualizer {
+
+    public String generateDotOutput(Parser parser) {
+
+        // Since the graph has cycles, we need to create a flat list of all the
+        // nodes in the graph.
+        Collection<Node> all = findAll(parser);
+        StringBuilder sb = new StringBuilder();
+        sb.append("digraph chapter02 {\n");
+        sb.append("/*\n");
+        sb.append(parser.src());
+        sb.append("\n*/\n");
+
+        // To keep the Scopes below the graph and pointing up into the graph we
+        // need to group the Nodes in a subgraph cluster, and the scopes into a
+        // different subgraph cluster.  THEN we can draw edges between the
+        // scopes and nodes.  If we try to cross subgraph cluster borders while
+        // still making the subgraphs DOT gets confused.
+        sb.append("\trankdir=BT;\n"); // Force Nodes before Scopes
+
+        // Preserve node input order
+        sb.append("\tordering=\"in\";\n");
+
+        // Merge multiple edges hitting the same node.  Makes common shared
+        // nodes much prettier to look at.
+        sb.append("\tconcentrate=\"true\";\n");
+
+        // Just the Nodes first, in a cluster no edges
+        nodes(sb, all);
+
+        // Walk the Node edges
+        nodeEdges(sb, all);
+
+        sb.append("}\n");
+        return sb.toString();
+    }
+
+
+    private void nodes(StringBuilder sb, Collection<Node> all) {
+        // 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 ) {
+            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("\" ");
+            sb.append("];\n");
+        }
+        sb.append("\t}\n");     // End Node cluster
+    }
+
+
+    // Walk the node edges
+    private void nodeEdges(StringBuilder sb, Collection<Node> all) {
+        // 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;
+            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());
+                    // 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() )
+                        sb.append(" color=red");
+                    sb.append("];\n");
+                }
+                i++;
+            }
+        }
+    }
+
+    /**
+     * 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 )
+            walk(all, n);
+        return all.values();
+    }
+
+    /**
+     * Walk a subgraph and populate distinct nodes in the all list.
+     */
+    private void walk(HashMap<Integer, Node> all, Node n) {
+        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);
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index 806c985d..72da8eeb 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
 
 /**
  * The Parser converts a Simple source program to the Sea of Nodes intermediate
@@ -30,6 +31,8 @@ public class Parser {
         START = new StartNode();
     }
 
+    String src() { return new String( _lexer._input ); }
+
     public ReturnNode parse() {
         var ret = (ReturnNode) parseStatement();
         if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
@@ -57,20 +60,61 @@ public class Parser {
      * </pre>
      * @return an expression {@link Node}, never {@code null}
      */
-    private ReturnNode parseReturn() {
+    private Node parseReturn() {
         var expr = require(parseExpression(), ";");
-        return new ReturnNode(START, expr);
+        return new ReturnNode(START, expr).peephole();
     }
 
     /**
      * Parse an expression of the form:
      *
      * <pre>
-     *     expr : primaryExpr
+     *     expr : additiveExpr
      * </pre>
      * @return an expression {@link Node}, never {@code null}
      */
-    private Node parseExpression() {
+    private Node parseExpression() { return parseAddition(); }
+
+    /**
+     * Parse an additive expression
+     *
+     * <pre>
+     *     additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
+     * </pre>
+     * @return an add expression {@link Node}, never {@code null}
+     */
+    private Node parseAddition() {
+        var lhs = parseMultiplication();
+        if (match("+")) return new AddNode(lhs, parseAddition()).peephole();
+        if (match("-")) return new SubNode(lhs, parseAddition()).peephole();
+        return lhs;
+    }
+
+    /**
+     * Parse an multiplicativeExpr expression
+     *
+     * <pre>
+     *     multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
+     * </pre>
+     * @return a multiply expression {@link Node}, never {@code null}
+     */
+    private Node parseMultiplication() {
+        var lhs = parseUnary();
+        if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole();
+        if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole();
+        return lhs;
+    }
+
+    /**
+     * Parse a unary minus expression.
+     *
+     * <pre>
+     *     unaryExpr : ('-') unaryExpr | primaryExpr
+     * </pre>
+     * @return a unary expression {@link Node}, never {@code null}
+     */
+    private Node parseUnary() {
+        if (match("-")) return new MinusNode(parseUnary()).peephole();
         return parsePrimary();
     }
 
@@ -78,14 +122,14 @@ public class Parser {
      * Parse a primary expression:
      *
      * <pre>
-     *     primaryExpr : integerLiteral
+     *     primaryExpr : integerLiteral | Identifier | '(' expression ')'
      * </pre>
+     * @return a primary {@link Node}, never {@code null}
      */
     private Node parsePrimary() {
-        _lexer.skipWhiteSpace();
-        if (_lexer.isNumber())
-            return parseIntegerLiteral();
-        throw error("Syntax error, expected integer literal");
+        if( _lexer.isNumber() ) return parseIntegerLiteral();
+        if( match("(") ) return require(parseExpression(), ")");
+        throw errorSyntax("integer literal");
     }
 
     /**
@@ -96,7 +140,7 @@ public class Parser {
      * </pre>
      */
     private ConstantNode parseIntegerLiteral() {
-        return new ConstantNode(_lexer.parseNumber());
+        return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole();
     }
 
     //////////////////////////////////
@@ -146,6 +190,12 @@ public class Parser {
             _input = buf;
         }
 
+        // Very handy in the debugger, shows the unparsed program
+        @Override
+        public String toString() {
+            return new String(_input, _position, _input.length - _position);
+        }
+
         // True if at EOF
         private boolean isEOF() {
             return _position >= _input.length;
@@ -209,11 +259,11 @@ public class Parser {
         boolean isNumber() {return isNumber(peek());}
         boolean isNumber(char ch) {return Character.isDigit(ch);}
 
-        private long parseNumber() {
+        private Type parseNumber() {
             String snum = parseNumberString();
             if (snum.length() > 1 && snum.charAt(0) == '0')
                 throw error("Syntax error: integer values cannot start with '0'");
-            return Long.parseLong(snum);
+            return TypeInteger.constant(Long.parseLong(snum));
         }
         private String parseNumberString() {
             int start = _position;
@@ -246,5 +296,4 @@ public class Parser {
             return new String(_input, start, 1);
         }
     }
-
 }
diff --git a/src/main/java/com/seaofnodes/simple/Utils.java b/src/main/java/com/seaofnodes/simple/Utils.java
new file mode 100644
index 00000000..45f15327
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/Utils.java
@@ -0,0 +1,39 @@
+package com.seaofnodes.simple;
+
+import java.util.ArrayList;
+
+public class Utils {
+    public static RuntimeException TODO() { return TODO("Not yet implemented"); }
+    public static RuntimeException TODO(String msg) { return new RuntimeException(msg); }
+
+    /**
+     *  Fast, constant-time, element removal.  Does not preserve order
+     *
+     *  @param array ArrayList to modify
+     *  @param i element to be removed
+     *  @return element removed
+     */
+    public static <E> E del(ArrayList<E> array, int i) {
+        if ( i >= 0 && i < array.size() ) {
+            E tmp = array.get(i);
+            E last = array.removeLast();
+            if (i < array.size()) array.set(i, last);
+            return tmp;
+        }
+        return null;
+    }
+
+    /**
+     * Search a list for an element by reference
+     *
+     * @param ary List to search in
+     * @param x Object to be searched
+     * @return >= 0 on success, -1 on failure
+     */
+    public static <E> int find( ArrayList<E> ary, E x ) {
+        for( int i=0; i<ary.size(); i++ )
+            if( ary.get(i)==x )
+                return i;
+        return -1;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
new file mode 100644
index 00000000..7c1968c5
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -0,0 +1,36 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.*;
+
+public class AddNode extends Node {
+    public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Add"; }
+
+    @Override public String glabel() { return "+"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("+"));
+        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(i0.value()+i1.value());
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize () {
+        // TODO: add of 0, and many other peepholes added in Chaper04
+        return null;
+    }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 21f65084..e4d7f412 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
 
 /**
  * A Constant node represents a constant value.  At present, the only constants
@@ -15,11 +16,27 @@ import com.seaofnodes.simple.Parser;
  * The Constant's value is the value stored in it.
  */
 public class ConstantNode extends Node {
+    Type _con;
+    public ConstantNode( Type type ) {
+        super(Parser.START);
+        _con = type;
+    }
 
-    public final long _value;
+    @Override
+    public String label() { return "#"+_con; }
 
-    public ConstantNode(long value) {
-        super(Parser.START);
-        _value = value;
+    @Override
+    public String uniqueName() { return "Con_" + _nid; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return _con._print(sb);
     }
+
+    @Override
+    public Type compute() { return _con; }
+
+    @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
new file mode 100644
index 00000000..e3c3616a
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -0,0 +1,34 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class DivNode extends Node {
+    public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Div"; }
+
+    @Override public String glabel() { return "//"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("/"));
+        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 i1.value() == 0
+                    ? TypeInteger.ZERO
+                    : TypeInteger.constant(i0.value()/i1.value());
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
new file mode 100644
index 00000000..0d59ef25
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -0,0 +1,28 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class MinusNode extends Node {
+    public MinusNode(Node in) { super(null, in); }
+
+    @Override public String label() { return "Minus"; }
+
+    @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()) : i0;
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
new file mode 100644
index 00000000..26c28281
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -0,0 +1,32 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class MulNode extends Node {
+    public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Mul"; }
+
+    @Override public String glabel() { return "*"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("*"));
+        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(i0.value()*i1.value());
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 5d74e206..6f47f9eb 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,5 +1,8 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.type.Type;
+
 import java.util.*;
 
 /**
@@ -36,6 +39,13 @@ public abstract class Node {
      */
     public final ArrayList<Node> _outputs;
 
+
+    /**
+     * Current computed type for this Node.  This value changes as the graph
+     * changes and more knowledge is gained about the program.
+     */
+    public Type _type;
+
     /**
      * 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.
@@ -50,8 +60,53 @@ public abstract class Node {
         _outputs = new ArrayList<>();
         for( Node n : _inputs )
             if( n != null )
-                n._outputs.add( this );
+                n.addUse( this );
+    }
+
+    // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ"
+    public abstract String label();
+
+    // Unique label for graph visualization, e.g. "Add12" or "Region30" or "EQ99"
+    public String uniqueName() { return label() + _nid; }
+
+    // Graphical label, e.g. "+" or "Region" or "=="
+    public String glabel() { return label(); }
+
+
+    // ------------------------------------------------------------------------
+
+    // Debugger Printing.
+
+    // {@code toString} is what you get in the debugger.  It has to print 1
+    // 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();
+    }
+
+    // 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
+    // tik-tok style; the common _print0 calls the per-Node _print1, which
+    // calls back to _print0;
+    public final String print() {
+        return _print0(new StringBuilder()).toString();
     }
+    // This is the common print: check for DEAD and print "DEAD" else call the
+    // per-Node print1.
+    final StringBuilder _print0(StringBuilder sb) {
+        return isDead()
+            ? sb.append(uniqueName()).append(":DEAD")
+            : _print1(sb);
+    }
+    // Every Node implements this.
+    abstract StringBuilder _print1(StringBuilder sb);
+
 
     /**
      * Gets the ith input node
@@ -62,6 +117,8 @@ public abstract class Node {
 
     public int nIns() { return _inputs.size(); }
 
+    public Node out(int i) { return _outputs.get(i); }
+
     public int nOuts() { return _outputs.size(); }
 
     public boolean isUnused() { return nOuts() == 0; }
@@ -70,6 +127,119 @@ public abstract class Node {
 
 
     /**
+     * Change a <em>def</em> into a Node.  Keeps the edges correct, by removing
+     * the corresponding <em>use->def</em> edge.  This may make the original
+     * <em>def</em> go dead.  This function is co-recursive with {@link #kill}.
+     *
+     * @param idx which def to set
+     * @param new_def the new definition
+     * @return new_def for flow coding
+     */
+    Node setDef(int idx, Node new_def ) {
+        Node old_def = in(idx);
+        if( old_def == new_def ) return this; // No change
+        // If new def is not null, add the corresponding def->use edge
+        // This needs to happen before removing the old node's def->use edge as
+        // the new_def might get killed if the old node kills it recursively.
+        if( new_def != null )
+            new_def.addUse(this);
+        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
+        // Set the new_def over the old (killed) edge
+        _inputs.set(idx,new_def);
+        // Return self for easy flow-coding
+        return new_def;
+    }
+
+    // Breaks the edge invariants, used temporarily
+    protected <N extends Node> N addUse(Node n) { _outputs.add(n); return (N)this; }
+
+    // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place.
+    // Return true if the output list is empty afterward.
+    // 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;
+    }
+
+    /**
+     * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em>
+     * to null.  This may recursively kill more Nodes and is basically dead
+     * code elimination.  This function is co-recursive with {@link #setDef}.
+     */
+    public void kill( ) {
+        assert isUnused();      // Has no uses, so it is dead
+        for( int i=0; i<nIns(); i++ )
+            setDef(i,null);  // Set all inputs to null, recursively killing unused Nodes
+        _inputs.clear();
+        _type=null;             // Flag as dead
+        assert isDead();        // Really dead now
+    }
+
+    // Mostly used for asserts and printing.
+    boolean isDead() { return isUnused() && nIns()==0 && _type==null; }
+    /**
+     * We allow disabling peephole opt so that we can observe the
+     * full graph, vs the optimized graph.
+     */
+    public static boolean _disablePeephole = false;
+
+    /**
+     * Try to peephole at this node and return a better replacement Node if
+     * possible.  We compute a {@link Type} and then check and replace:
+     * <ul>
+     * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li>
+     * <li>in a future chapter we will look for a
+     * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a>
+     * to eliminate.</li>
+     * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li>
+     * </ul>
+     */
+    public final Node peephole( ) {
+        // Compute initial or improved Type
+        Type type = _type = compute();
+
+        if (_disablePeephole)
+            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();
+        }
+
+        // Future chapter: Global Value Numbering goes here
+
+        // Ask each node for a better replacement
+        Node n = idealize();
+        if( n != null ) return n;
+
+        return this;            // No progress
+    }
+
+
+    /**
+     * This function needs to be
+     * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a>
+     * as it is part of a Monotone Analysis Framework.
+     * <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">See for example this set of slides</a>.
+     * <p>
+     * For Chapter 2, all our Types are really integer constants, and so all
+     * the needed properties are trivially true, and we can ignore the high
+     * theory.  Much later on, this will become important and allow us to do
+     * many fancy complex optimizations trivially... because theory.
+     * <p>
+     * compute() needs to be stand-alone, and cannot recursively call compute
+     * on its inputs programs are cyclic (have loops!) and this will just
+     * infinitely recurse until stack overflow.  Instead, compute typically
+     * computes a new type from the {@link #_type} field of its inputs.
+     */
+    public abstract Type compute();
+
+    public abstract Node idealize();
+
+    /**
      * 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/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 85bbc83f..7fa470f8 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -1,5 +1,7 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.type.*;
+
 /**
  * The Return node has two inputs.  The first input is a control node and the
  * second is the data node that supplies the return value.
@@ -18,6 +20,21 @@ public class ReturnNode extends Node {
     public Node ctrl() { return in(0); }
     public Node expr() { return in(1); }
 
+    @Override
+    public String label() { return "Return"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return expr()._print0(sb.append("return ")).append(";");
+    }
+
     @Override public boolean isCFG() { return true; }
 
+    @Override
+    public Type compute() {
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 04bd6bb4..99e240ad 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -1,9 +1,13 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.type.Type;
+
 /**
- * The Start node represents the start of the function.  For now, we do not have any inputs to Start because our function does not
- * yet accept parameters.  When we add parameters the value of Start will be a tuple, and will require Projections to extract the values.
- * We discuss this in detail in Chapter 9: Functions and Calls.
+ * The Start node represents the start of the function.  For now, we do not
+ * have any inputs to Start because our function does not yet accept
+ * parameters.  When we add parameters the value of Start will be a tuple, and
+ * will require Projections to extract the values.  We discuss this in detail
+ * in Chapter 9: Functions and Calls.
  */
 public class StartNode extends Node {
 
@@ -11,6 +15,19 @@ public class StartNode extends Node {
         super();
     }
 
+    @Override
+    public String label() { return "Start"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+      return sb.append(label());
+    }
+
     @Override public boolean isCFG() { return true; }
 
+    @Override
+    public Type compute() { return Type.BOTTOM; }
+
+    @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
new file mode 100644
index 00000000..d2e32c61
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -0,0 +1,33 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class SubNode extends Node {
+    public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Sub"; }
+
+    @Override public String glabel() { return "-"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("-"));
+        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(i0.value()-i1.value());
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    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
new file mode 100644
index 00000000..89f6c715
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -0,0 +1,40 @@
+package com.seaofnodes.simple.type;
+
+
+/**
+ * These types are part of a Monotone Analysis Framework,
+ * @see <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">see for example this set of slides</a>.
+ * <p>
+ * The types form a lattice; @see <a href="https://en.wikipedia.org/wiki/Lattice_(order)">a symmetric complete bounded (ranked) lattice.</a>
+ * <p>
+ * This wild lattice theory will be needed later to allow us to easily beef up
+ * the analysis and optimization of the Simple compiler... but we don't need it
+ * now, just know that it is coming along in a later Chapter.
+ * <p>g
+ * One of the fun things here is that while the theory is deep and subtle, the
+ * actual implementation is darn near trivial and is generally really obvious
+ * what we're doing with it.  Right now, it's just simple integer math to do
+ * simple constant folding e.g. 1+2 == 3 stuff.
+ */
+
+public class Type {
+
+    // ----------------------------------------------------------
+    // Simple types are implemented fully here.  "Simple" means: the code and
+    // 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
+    public final byte _type;
+
+    public boolean is_simple() { return _type < TSIMPLE; }
+    private static final String[] STRS = new String[]{"Bot","Top"};
+    protected Type(byte type) { _type = type; }
+
+    public static final Type BOTTOM   = new Type( TBOT ); // ALL
+
+    public boolean isConstant() { return _type == TTOP; }
+
+    public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
+}
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
new file mode 100644
index 00000000..13f816bf
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -0,0 +1,41 @@
+package com.seaofnodes.simple.type;
+
+/**
+ * Integer Type
+ */
+public class TypeInteger extends Type {
+
+    public final static TypeInteger ZERO= new TypeInteger(0);
+
+    /**
+     * The constant value observed for this type
+     */
+    private final long _con;
+
+    public TypeInteger(long con) {
+        super(TINT);
+        _con = con;
+    }
+
+    public static TypeInteger constant(long con) { return new TypeInteger(con); }
+
+    @Override
+    public String toString() {
+      return _print(new StringBuilder()).toString();
+    }
+
+    @Override
+    public StringBuilder _print(StringBuilder sb) { return sb.append(_con); }
+
+    @Override
+    public boolean isConstant() { return true; }
+
+    public long value() { return _con; }
+
+    @Override
+    public boolean equals( Object o ) {
+        if( o==this ) return true;
+        if( !(o instanceof TypeInteger i) ) return false;
+        return _con==i._con;
+    }
+}