Chapter 13: References

Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

30 files changed, 494 insertions, 196 deletions

diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index 4e0a31d5..8a96e69c 100644
--- a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -1,5 +1,6 @@
  package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.IterPeeps.WorkList;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 import java.util.*;
@@ -12,14 +13,14 @@ public abstract class GlobalCodeMotion {
     public static void buildCFG( StopNode stop ) {
         schedEarly();
         Parser.SCHEDULED = true;
-        schedLate(Parser.START);
+        schedLate( stop);
     }
 
     // ------------------------------------------------------------------------
     // Backwards walk on the CFG only, looking for unreachable code - which has
     // to be an infinite loop.  Insert a bogus never-taken exit to Stop, so the
     // loop becomes reachable.  Also, set loop nesting depth
-    static void fixLoops(StopNode stop) {
+    public static void fixLoops(StopNode stop) {
         // Backwards walk from Stop, looking for unreachable code
         BitSet visit = new BitSet();
         HashSet<CFGNode> unreach = new HashSet<>();
@@ -54,6 +55,10 @@ public abstract class GlobalCodeMotion {
     }
 
     // ------------------------------------------------------------------------
+    // Visit all nodes in CFG Reverse Post-Order, essentially defs before uses
+    // (except at loops).  Since defs are visited first - and hoisted as early
+    // as possible, when we come to a use we place it just after its deepest
+    // input.
     private static void schedEarly() {
         ArrayList<CFGNode> rpo = new ArrayList<>();
         BitSet visit = new BitSet();
@@ -110,38 +115,60 @@ public abstract class GlobalCodeMotion {
     }
 
     // ------------------------------------------------------------------------
-    private static void schedLate(StartNode start) {
+    private static void schedLate( StopNode stop) {
         CFGNode[] late = new CFGNode[Node.UID()];
         Node[] ns = new Node[Node.UID()];
-        _schedLate(start,ns,late);
+        // Breadth-first scheduling
+        breadth(stop,ns,late);
+
+        // Copy the best placement choice into the control slot
         for( int i=0; i<late.length; i++ )
             if( ns[i] != null )
                 ns[i].setDef(0,late[i]);
     }
 
-    // Forwards post-order pass.  Schedule all outputs first, then draw a
-    // idom-tree line from the LCA of uses to the early schedule.  Schedule is
-    // legal anywhere on this line; pick the most control-dependent (largest
-    // idepth) in the shallowest loop nest.
-    private static void _schedLate(Node n, Node[] ns, CFGNode[] late) {
-        if( late[n._nid]!=null ) return; // Been there, done that
-        // These I know the late schedule of, and need to set early for loops
-        if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0);
-        if( n instanceof PhiNode phi ) late[n._nid] = phi.region();
-
-        // Walk Stores before Loads, so we can get the anti-deps right
-        for( Node use : n._outputs )
-            if( isForwardsEdge(use,n) &&
-                use._type instanceof TypeMem )
-                _schedLate(use,ns,late);
-        // Walk everybody now
-        for( Node use : n._outputs )
-            if( isForwardsEdge(use,n) )
-                _schedLate(use,ns,late);
-        // Already implicitly scheduled
-        if( n.isPinned() ) return;
-        // Need to schedule n
+    private static void breadth(Node stop, Node[] ns, CFGNode[] late) {
+        // Things on the worklist have some (but perhaps not all) uses done.
+        WorkList<Node> work = new WorkList<>();
+        work.push(stop);
+        Node n;
+        outer:
+        while( (n = work.pop()) != null ) {
+            assert late[n._nid]==null; // No double visit
+            // These I know the late schedule of, and need to set early for loops
+            if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0);
+            else if( n instanceof PhiNode phi ) late[n._nid] = phi.region();
+            else if( n.isPinned() ) late[n._nid] = n.cfg0();
+            else {
+
+                // All uses done?
+                for( Node use : n._outputs )
+                    if( late[use._nid]==null )
+                        continue outer; // Nope, await all uses done
+
+                // Loads need their memory inputs' uses also done
+                if( n instanceof LoadNode ld )
+                    for( Node memuse : ld.mem()._outputs )
+                        if( memuse._type instanceof TypeMem && late[memuse._nid]==null )
+                            continue outer;
+
+                // All uses done, schedule
+                _doSchedLate(n,ns,late);
+            }
+
+            // Walk all inputs and put on worklist, as their last-use might now be done
+            for( Node def : n._inputs )
+                if( def!=null && late[def._nid]==null ) {
+                    work.push(def);
+                    // if the def has a load use, maybe the load can fire
+                    for( Node ld : def._outputs )
+                        if( ld instanceof LoadNode && late[ld._nid]==null )
+                            work.push(ld);
+                }
+        }
+    }
 
+    private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late) {
         // Walk uses, gathering the LCA (Least Common Ancestor) of uses
         CFGNode early = (CFGNode)n.in(0);
         assert early != null;
@@ -154,7 +181,7 @@ public abstract class GlobalCodeMotion {
             lca = find_anti_dep(lca,load,early,late);
 
         // Walk up from the LCA to the early, looking for best place.  This is
-        // lowest execution frequency, approximated by least loop depth and
+        // the lowest execution frequency, approximated by least loop depth and
         // deepest control flow.
         CFGNode best = lca;
         lca = lca.idom();       // Already found best for starting LCA
@@ -187,12 +214,6 @@ public abstract class GlobalCodeMotion {
                 (lca.idepth() > best.idepth() || best instanceof IfNode);
     }
 
-    // Skip iteration if a backedge
-    private static boolean isForwardsEdge(Node use, Node def) {
-        return use != null && def != null &&
-            !(use.nIns()>2 && use.in(2)==def && (use instanceof LoopNode || (use instanceof PhiNode phi && phi.region() instanceof LoopNode)));
-    }
-
     private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late) {
         // We could skip final-field loads here.
         // Walk LCA->early, flagging Load's block location choices
@@ -202,6 +223,7 @@ public abstract class GlobalCodeMotion {
         for( Node mem : load.mem()._outputs ) {
             switch( mem ) {
             case StoreNode st:
+                assert late[st._nid]!=null;
                 lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st);
                 break;
             case PhiNode phi:
diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java
index 121d0233..783fc4f1 100644
--- a/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -57,7 +57,7 @@ public abstract class IterPeeps {
     /**
      * Iterate peepholes to a fixed point
      */
-    public static StopNode iterate(StopNode stop, boolean show) {
+    public static StopNode iterate(StopNode stop) {
         assert progressOnList(stop);
         int cnt=0;
 
@@ -92,11 +92,6 @@ public abstract class IterPeeps {
                 n.kill();       // Just plain dead
         }
 
-        // Break infinite loops, forcing a Never-branch to exit
-        GlobalCodeMotion.fixLoops(stop);
-        if( show )
-            System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null));
-        GlobalCodeMotion.buildCFG(stop);
         return stop;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index 1a223726..71bd6d02 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -179,7 +179,7 @@ public class Parser {
      *     type IDENTIFIER ;
      * </pre>
      */
-    private Field parseField(String sname) {
+    private Field parseField() {
         Type t = type();
         if( t==null )
             throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'");
@@ -191,25 +191,26 @@ public class Parser {
      * Only allowed in top level scope.
      * Structs cannot be redefined.
      *
-     * @return The statement following the struct
+     * @return null
      */
     private Node parseStruct() {
         if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope");
         String typeName = requireId();
-        if ( TYPES.containsKey(typeName)) throw errorSyntax("struct '" + typeName + "' cannot be redefined");
+        Type t = TYPES.get(typeName);
+        if( t!=null && !(t instanceof TypeStruct ts && ts._fields==null) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined");
         ArrayList<Field> fields = new ArrayList<>();
         require("{");
         while (!peek('}') && !_lexer.isEOF()) {
-            Field field = parseField(typeName);
+            Field field = parseField();
             if (fields.contains(field)) throw errorSyntax("Field '" + field + "' already defined in struct '" + typeName + "'");
             fields.add(field);
         }
         require("}");
         // Build and install the TypeStruct
         TypeStruct ts = TypeStruct.make(typeName, fields);
-        TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names
+        TYPES.put(typeName, ts);
         START.addMemProj(ts, _scope); // Insert memory edges
-        return parseStatement();
+        return null;
     }
 
     /**
@@ -350,8 +351,8 @@ public class Parser {
         // Parse the false side
         _scope = fScope;        // Restore scope, then parse else block if any
         ctrl(ifF.unkeep());     // Ctrl token is now set to ifFalse projection
+        _scope.upcast(ifF,pred,true); // Up-cast predicate
         if (matchx("else")) {
-            _scope.upcast(ifF,pred,true); // Up-cast predicate
             parseStatement();
             fScope = _scope;
         }
@@ -433,24 +434,36 @@ public class Parser {
         // Auto-widen int to float
         if( expr._type instanceof TypeInteger && t instanceof TypeFloat )
             expr = new ToFloatNode(expr).peephole();
+        // Auto-deepen forward ref types
+        Type e = expr._type;
+        if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null )
+            e = tmp.make_from((TypeStruct)TYPES.get(tmp._obj._name));
         // Type is sane
-        if( !expr._type.isa(t) )
-            throw error("Type " + expr._type.str() + " is not of declared type " + t.str());
+        if( !e.isa(t) )
+            throw error("Type " + e.str() + " is not of declared type " + t.str());
         return _scope.update(name,expr);
     }
 
-    // Parse a type-or-null
+    // Parse a "type id" and return "type" (and re-parse "id" in caller) or
+    // return null.
     private Type type() {
         int old = _lexer._position;
         String tname = _lexer.matchId();
         if( tname==null ) return null;
+        boolean nullable = match("?");
         Type t = TYPES.get(tname);
+        // Assume a forward-reference type
         if( t == null ) {
-            // Not a type; unwind the parse
-            _lexer._position = old;
-            return null;
+            int old2 = _lexer._position;
+            String id = _lexer.matchId();
+            if( id==null ) {
+                _lexer._position = old;
+                return null;
+            }
+            TYPES.put(tname,t = TypeStruct.make(tname));
+            _lexer._position = old2; // Reparse ID in caller
         }
-        return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,match("?")) : t;
+        return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t;
     }
 
 
@@ -567,7 +580,8 @@ public class Parser {
         if( matchx("new") ) {
             String structName = requireId();
             Type t = TYPES.get(structName);
-            if( t == null || !(t instanceof TypeStruct obj) ) throw errorSyntax("Unknown struct type '" + structName + "'");
+            if( !(t instanceof TypeStruct obj) || obj._fields==null )
+                throw error("Unknown struct type '" + structName + "'");
             return newStruct(obj);
         }
         String name = _lexer.matchId();
@@ -584,7 +598,7 @@ public class Parser {
         Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep();
         int alias = START._aliasStarts.get(obj._name);
         for( Field field : obj._fields ) {
-            memAlias(alias, new StoreNode(field._fname, alias, ctrl(), memAlias(alias), n, ZERO).peephole());
+            memAlias(alias, new StoreNode(field._fname, alias, field._type, ctrl(), memAlias(alias), n, new ConstantNode(field._type.makeInit()).peephole(),true).peephole());
             alias++;
         }
         return n.unkeep();
@@ -614,7 +628,9 @@ public class Parser {
 
         String name = requireId().intern();
         if( expr._type == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null");
-        int idx = ptr._obj==null ? -1 : ptr._obj.find(name);
+        if( ptr._obj == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'");
+        TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name);
+        int idx = base==null ? -1 : base.find(name);
         if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'");
         int alias = START._aliasStarts.get(ptr._obj._name)+idx;
 
@@ -623,13 +639,14 @@ public class Parser {
             if( peek('=') ) _lexer._position--;
             else {
                 Node val = parseExpression();
-                memAlias(alias, new StoreNode(name, alias, ctrl(), memAlias(alias), expr, val).peephole());
+                Type glb = base._fields[idx]._type;
+                memAlias(alias, new StoreNode(name, alias,glb, ctrl(), memAlias(alias), expr, val, false).peephole());
                 return expr;        // "obj.a = expr" returns the expression while updating memory
             }
         }
 
-        Type declaredType = ptr._obj._fields[idx]._type;
-        return parsePostfix(new LoadNode(name, alias, declaredType, memAlias(alias), expr).peephole());
+        Type declaredType = base._fields[idx]._type;
+        return parsePostfix(new LoadNode(name, alias, declaredType.glb(), memAlias(alias), expr).peephole());
     }
 
     /**
@@ -637,7 +654,7 @@ public class Parser {
      *
      * <pre>
      *     integerLiteral: [1-9][0-9]* | [0]
-     *     floatLiteral: [1-9][0-9]* | [0]
+     *     floatLiteral: [digits].[digits]?[e [digits]]?
      * </pre>
      */
     private ConstantNode parseLiteral() {
diff --git a/src/main/java/com/seaofnodes/simple/node/CastNode.java b/src/main/java/com/seaofnodes/simple/node/CastNode.java
index fec540f7..fbf0e518 100644
--- a/src/main/java/com/seaofnodes/simple/node/CastNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/CastNode.java
@@ -22,6 +22,9 @@ public class CastNode extends Node {
     public String uniqueName() { return "Cast_" + _nid; }
 
     @Override
+    public boolean isPinned() { return true; }
+
+    @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
         return in(1)._print0(sb.append(label()), visited);
     }
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index cf1a76b0..016b0b9b 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -32,7 +32,7 @@ public class ConstantNode extends Node {
 
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
-        return _con._print(sb);
+        return _con.print(sb);
     }
 
     @Override public boolean isMultiTail() { return true; }
diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 244a0919..a033a7cf 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -2,7 +2,6 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.Field;
 
 import java.util.BitSet;
 
@@ -12,7 +11,6 @@ import java.util.BitSet;
  */
 public class LoadNode extends MemOpNode {
 
-    Type _declaredType;
     /**
      * Load a value from a ptr.field.
      *
@@ -21,15 +19,11 @@ public class LoadNode extends MemOpNode {
      * @param memPtr The ptr to the struct from where we load a field
      */
     public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) {
-        super(name, alias, null, memSlice, memPtr);
-        _declaredType = glb;
+        super(name, alias, glb, null, memSlice, memPtr);
     }
 
-    @Override
-    public String label() { return "Load"; }
-
-    @Override
-    public String glabel() { return "."+_name; }
+    @Override public String  label() { return     _name; }
+    @Override public String glabel() { return "."+_name; }
 
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); }
diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index 551d2aa9..95319c24 100644
--- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -11,11 +11,14 @@ public abstract class MemOpNode extends Node {
 
     public final String _name;
     public final int _alias;
+    public final Type _declaredType;
 
-    public MemOpNode(String name, int alias, Node... nodes) {
+
+    public MemOpNode(String name, int alias, Type glb, Node... nodes ) {
         super(nodes);
         _name  = name;
         _alias = alias;
+        _declaredType = glb;
     }
 
     public Node mem() { return in(1); }
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 52282737..d846fcef 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -137,7 +137,7 @@ public abstract class Node implements OutNode {
 
     public boolean isUnused() { return nOuts() == 0; }
 
-    public CFGNode cfg0() { return (CFGNode)in(0); }
+   public CFGNode cfg0() { return (CFGNode)in(0); }
 
     /**
      * Change a <em>def</em> into a Node.  Keeps the edges correct, by removing
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index ab567bae..0eacc1f4 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.GlobalCodeMotion;
+import com.seaofnodes.simple.GraphVisualizer;
 
 import java.util.BitSet;
 
@@ -67,13 +69,21 @@ public class StopNode extends CFGNode {
         return addDef(node);
     }
 
-    public StopNode iterate(            ) { return IterPeeps.iterate(this,false).typeCheck(); }
-    public StopNode iterate(boolean show) { return IterPeeps.iterate(this,show ).typeCheck(); }
+    public StopNode iterate(            ) { return IterPeeps.iterate(this).typeCheck().GCM(false); }
+    public StopNode iterate(boolean show) { return IterPeeps.iterate(this).typeCheck().GCM(show ); }
     StopNode typeCheck() {
         String err = walk( Node::err );
         if( err != null ) throw new RuntimeException(err);
         return this;
     }
+    StopNode GCM(boolean show) {
+        // Break infinite loops, forcing a Never-branch to exit
+        GlobalCodeMotion.fixLoops(this);
+        if( show )
+            System.out.println(new GraphVisualizer().generateDotOutput(this,null,null));
+        GlobalCodeMotion.buildCFG(this);
+        return this;
+    }
 
     @Override public Node getBlockStart() { return this; }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index db8e2ce6..57e8b3ad 100644
--- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -11,22 +11,23 @@ import java.util.BitSet;
  */
 public class StoreNode extends MemOpNode {
 
+    private final boolean _init; // Initializing writes are allowed to write null
+
     /**
      * @param name The struct field we are assigning to
      * @param memSlice The memory alias node - this is updated after a Store
      * @param memPtr The ptr to the struct where we will store a value
      * @param value Value to be stored
      */
-    public StoreNode(String name, int alias, Node ctrl, Node memSlice, Node memPtr, Node value) {
-        super(name, alias, ctrl, memSlice, memPtr, value);
+    public StoreNode(String name, int alias, Type glb, Node ctrl, Node memSlice, Node memPtr, Node value, boolean init) {
+        super(name, alias, glb, ctrl, memSlice, memPtr, value);
+        _init = init;
     }
 
-    @Override
-    public String label() { return "Store"; }
-    @Override
-    public String glabel() { return "."+_name+" ="; }
-    @Override
-    public boolean isMem() { return true; }
+    @Override public String  label() { return "." +_name+"="; }
+    @Override public String glabel() { return "." +_name+"="; }
+    @Override public boolean isMem() { return true; }
+
     public Node val() { return in(3); }
 
     @Override
@@ -67,4 +68,11 @@ public class StoreNode extends MemOpNode {
         return false;
     }
 
+    @Override
+    String err() {
+        String err = super.err();
+        if( err != null ) return err;
+        Type ptr = val()._type;
+        return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_name;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/src/main/java/com/seaofnodes/simple/node/SubFNode.java
index b591718d..682930e0 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubFNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubFNode.java
@@ -34,7 +34,7 @@ public class SubFNode extends Node {
         Node lhs = in(1);
         Type t2 = in(2)._type;
 
-        // Sub of 0.
+        // Sub of 1.
         if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 )
             return lhs;
 
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index f0c77743..81cc6076 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -37,6 +37,7 @@ public class SubNode extends Node {
 
     @Override
     public Node idealize() {
+
         // x - (-y) is x+y
         if( in(2) instanceof MinusNode minus )
             return new AddNode(in(1),minus.in(1));
diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java
index e1c337d4..b2c006dd 100644
--- a/src/main/java/com/seaofnodes/simple/type/Field.java
+++ b/src/main/java/com/seaofnodes/simple/type/Field.java
@@ -52,8 +52,8 @@ public class Field extends Type {
 
 
     @Override
-    public StringBuilder _print( StringBuilder sb ) {
-        return _type._print(sb.append(_fname).append(":"));
+    public StringBuilder print( StringBuilder sb ) {
+        return _type.print(sb.append(_fname).append(" :"));
     }
 
     @Override public String str() { return _fname; }
diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java
index f3152719..1f211430 100644
--- a/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -76,20 +76,22 @@ public class Type {
     /**
      * Display Type name in a format that's good for IR printer
      */
-    public StringBuilder typeName( StringBuilder sb) { return _print(sb); }
+    public StringBuilder typeName( StringBuilder sb) { return print(sb); }
 
     public Type makeInit() { return null; }
 
     // ----------------------------------------------------------
 
-    // Notes on Type interning.
-    // At the moment it is not easy to reset the interned types
-    // because we hold static references to several types and these are scattered
-    // around. This means the INTERN cache will retain all types from
-    // every run of the Parser. For this to work correctly types must be
-    // rigorous about defining when they are the same. Also types need to be
-    // immutable once defined.
-    // The rationale for interning is performance.
+    // Notes on Type interning: At the moment it is not easy to reset the
+    // interned types because we hold static references to several types and
+    // these are scattered around.  This means the INTERN cache will retain all
+    // types from every run of the Parser.  For this to work correctly types
+    // must be rigorous about defining when they are the same.  Also types need
+    // to be immutable once defined.  The rationale for interning is
+    // *correctness* with cyclic type definitions.  Simple structural recursive
+    // checks go exponential with merely sharing, but with cycles they will
+    // stack overflow and crash.  Intering means we do not need to have sharing
+    // checks with every type compare, only during interning.
 
     // Factory method which interns "this"
     public  <T extends Type> T intern() {
@@ -178,10 +180,10 @@ public class Type {
     // This is a more verbose dev-friendly print.
     @Override
     public final String toString() {
-        return _print(new StringBuilder()).toString();
+        return print(new StringBuilder()).toString();
     }
 
-    public StringBuilder _print(StringBuilder sb) { return is_simple() ? sb.append(STRS[_type]) : sb;}
+    public StringBuilder print(StringBuilder sb) { return is_simple() ? sb.append(STRS[_type]) : sb;}
 
     // This is used by error messages, and is a shorted print.
     public String str() { return STRS[_type]; }
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
index 36bc61f5..738aebc9 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
@@ -35,7 +35,7 @@ public class TypeFloat extends Type {
     // FIXME this display format is problematic
     // In visualizer '#' gets prepended if its a constant
     @Override
-    public StringBuilder _print(StringBuilder sb) {
+    public StringBuilder print(StringBuilder sb) {
         if( this==TOP ) return sb.append("FltTop");
         if( this==BOT ) return sb.append("FltBot");
         return sb.append(_con);
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index f2a93a3a..8c77672b 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -35,7 +35,7 @@ public class TypeInteger extends Type {
     // FIXME this display format is problematic
     // In visualizer '#' gets prepended if its a constant
     @Override
-    public StringBuilder _print(StringBuilder sb) {
+    public StringBuilder print(StringBuilder sb) {
         if( this==TOP ) return sb.append("IntTop");
         if( this==BOT ) return sb.append("IntBot");
         return sb.append(_con);
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java
index 198d49ee..b2d081f4 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java
@@ -15,7 +15,7 @@ public class TypeMem extends Type {
     //  0 means TOP, no slice.
     // -1 means BOT, all memory.
     //  N means slice#N.
-    private final int _alias;
+    public final int _alias;
 
     private TypeMem(int alias) { super(TMEM); _alias = alias; }
 
@@ -23,7 +23,6 @@ public class TypeMem extends Type {
     public static final TypeMem TOP = make( 0);
     public static final TypeMem BOT = make(-1);
 
-
     public static void gather(ArrayList<Type> ts) { ts.add(make(1)); ts.add(BOT); }
 
     @Override
@@ -40,7 +39,7 @@ public class TypeMem extends Type {
     }
 
     @Override
-    public Type glb() { return TypeMem.BOT; }
+    public Type glb() { return make(_alias); }
 
     @Override
     int hash() { return 9876543 + _alias; }
@@ -52,7 +51,7 @@ public class TypeMem extends Type {
     }
 
     @Override
-    public StringBuilder _print(StringBuilder sb) {
+    public StringBuilder print(StringBuilder sb) {
         return sb.append("MEM#").append( switch(_alias) {
             case  0 -> "TOP";
             case -1 -> "BOT";
@@ -60,5 +59,5 @@ public class TypeMem extends Type {
             });
     }
 
-    @Override public String str() { return _print(new StringBuilder()).toString(); }
+    @Override public String str() { return toString(); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
index 65352402..e671c584 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
@@ -13,21 +13,27 @@ import java.util.ArrayList;
  */
 public class TypeMemPtr extends Type {
     // A TypeMemPtr is pair (obj,nil)
-    // where obj is one of
-    //    (null,TypeStruct).
-    // where nil is one of
-    //    (true,false) meaning an explicit null is allowed or not
+    // where obj is a TypeStruct, possibly TypeStruct.BOT
+    // where nil is an explicit null is allowed or not
 
-    public final TypeStruct _obj; // null, a TypeStruct, or sentinel TypeStruct.MANY
+    // Examples:
+    // (Person,false) - a not-nil Person
+    // (Person,true ) - a Person or a nil
+    // (BOT   ,false) - a not-nil void* (unspecified struct)
+    // (TOP   ,true ) - a nil
+
+    public final TypeStruct _obj;
     public final boolean _nil;
 
     private TypeMemPtr(TypeStruct obj, boolean nil) {
         super(TMEMPTR);
+        assert obj!=null;
         _obj = obj;
         _nil = nil;
     }
     public static TypeMemPtr make(TypeStruct obj, boolean nil) { return new TypeMemPtr(obj, nil).intern(); }
-    public static TypeMemPtr make(TypeStruct obj) { return TypeMemPtr.make(obj, false); }
+    public static TypeMemPtr make(TypeStruct obj) { return make(obj, false); }
+    public TypeMemPtr make_from(TypeStruct obj) { return make(obj, _nil); }
 
     public static TypeMemPtr BOT = make(TypeStruct.BOT,true);
     public static TypeMemPtr TOP = BOT.dual();
@@ -43,17 +49,14 @@ public class TypeMemPtr extends Type {
     }
 
     @Override
-    public TypeMemPtr dual() { return TypeMemPtr.make(_obj==null ? null : _obj.dual(), !_nil); }
+    public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil); }
 
     @Override
-    public Type glb() {
-        if( _obj==null ) return BOT;
-        return make(_obj.glb(),true);
-    }
+    public Type glb() { return make(_obj.glb(),true); }
     @Override public TypeMemPtr makeInit() { return NULLPTR; }
 
     @Override
-    int hash() { return (_obj==null ? 0xDEADBEEF : _obj.hashCode()) ^ (_nil ? 1024 : 0); }
+    int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); }
 
     @Override
     boolean eq(Type t) {
@@ -63,10 +66,10 @@ public class TypeMemPtr extends Type {
 
     // [void,name,MANY]*[,?]
     @Override
-    public StringBuilder _print(StringBuilder sb) {
+    public StringBuilder print(StringBuilder sb) {
         if( this== NULLPTR) return sb.append("null");
         if( this== VOIDPTR) return sb.append("*void");
-        return _obj._print(sb.append("*")).append(_nil ? "?" : "");
+        return _obj.print(sb.append("*")).append(_nil ? "?" : "");
     }
 
     @Override public String str() {
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
index 29102675..e2489d6f 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
@@ -8,9 +8,14 @@ import java.util.ArrayList;
  */
 public class TypeStruct extends Type {
 
-    // For now in terms of the lattice
-    // a struct type just stays as is
-
+    // A Struct has a name and a set of fields; the fields themselves have
+    // names and types.  Briefly during parsing its allowed to have a
+    // forward-ref to a Struct; in this case the _fields array is null.
+    // Its illegal to attempt to load a field from a forward-ref struct.
+    //
+    // During the normal optimization run, struct types "bottom out" at further
+    // struct references, so we don't have to handle e.g.  cyclic types.  The
+    // "bottom out" is again the forward-ref struct.
     public final String _name;
     public final Field[] _fields;
 
@@ -20,13 +25,23 @@ public class TypeStruct extends Type {
         _fields = fields;
     }
 
+    // Forward-ref version
+    public static TypeStruct make(String name) { return new TypeStruct(name, null).intern(); }
+    // All fields directly listed
     public static TypeStruct make(String name, Field[] fields) { return new TypeStruct(name, fields).intern(); }
+    // Parser uses an ArrayList to gather the fields
     public static TypeStruct make(String name, ArrayList<Field> fields) { return make(name,fields.toArray(new Field[fields.size()])); }
 
     public static final TypeStruct TOP = make("$TOP",new Field [0]);
     public static final TypeStruct BOT = make("$BOT",new Field [0]);
     public static final TypeStruct TEST = make("test",new Field[]{Field.TEST});
-    public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); }
+
+    // A pair of self-cyclic types
+    private static final TypeStruct S1F = make("S1");
+    private static final TypeStruct S2F = make("S2");
+    public  static final TypeStruct S1  = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT), Field.make("s2",TypeMemPtr.make(S2F,false)) });
+    private static final TypeStruct S2  = make("S2", new Field[]{ Field.make("b", TypeFloat  .BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) });
+    public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); }
 
     public int find(String fname) {
         for( int i=0; i<_fields.length; i++ )
@@ -51,6 +66,8 @@ public class TypeStruct extends Type {
         // And the answer is: "don't ask".
         if( !_name.equals(that._name) )
             return BOT;         // It's a struct; that's about all we know
+        if( this._fields==null ) return this;
+        if( that._fields==null ) return that;
         // Now all fields should be the same, so just do field meets
         assert _fields.length == that._fields.length;
         Field[] flds = new Field[_fields.length];
@@ -63,6 +80,7 @@ public class TypeStruct extends Type {
     public TypeStruct dual() {
         if( this==TOP ) return BOT;
         if( this==BOT ) return TOP;
+        if( _fields == null ) return this;
         Field[] flds = new Field[_fields.length];
         for( int i=0; i<_fields.length; i++ )
             flds[i] = _fields[i].dual();
@@ -80,9 +98,10 @@ public class TypeStruct extends Type {
         return make(_name,flds);
     }
     private boolean _glb() {
-        for( Field f : _fields )
-            if( f.glb() != f )
-                return false;
+        if( _fields!=null )
+          for( Field f : _fields )
+              if( f.glb() != f )
+                 return false;
         return true;
     }
 
@@ -91,6 +110,7 @@ public class TypeStruct extends Type {
         TypeStruct ts = (TypeStruct)t; // Invariant
         if( !_name.equals(ts._name) )
             return false;
+        if( _fields == ts._fields ) return true;
         if( _fields.length!=ts._fields.length )
             return false;
         for( int i = 0; i < _fields.length; i++ )
@@ -102,17 +122,20 @@ public class TypeStruct extends Type {
     @Override
     int hash() {
         long hash = _name.hashCode();
-        for( Field f : _fields ) hash = Utils.rot(hash,13) ^ f.hashCode();
+        if( _fields != null )
+            for( Field f : _fields )
+                hash = Utils.rot(hash,13) ^ f.hashCode();
         return Utils.fold(hash);
     }
 
     @Override
-    public StringBuilder _print(StringBuilder sb) {
-        sb.append(_name).append(" {\n");
+    public StringBuilder print(StringBuilder sb) {
+        sb.append(_name);
+        if( _fields == null ) return sb; // Forward reference struct, just print the name
+        sb.append(" {\n");
         for( Field f : _fields ) {
-            sb.append("  ").append(f._fname).append(":");
-            f._type._print(sb);
-            sb.append(";\n");
+            sb.append("  ").append(f._fname).append(" :");
+            f._type.print(sb).append(";\n");
         }
         return sb.append("}");
     }
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index 01bcbe9f..783f3f60 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -37,17 +37,16 @@ public class TypeTuple extends Type {
         return make(ts);
     }
 
-    @Override
-    public StringBuilder _print(StringBuilder sb) {
-        sb.append("[");
+    @Override public StringBuilder print(StringBuilder sb) {
+        sb.append("[  ");
         for( Type t : _types )
-            t._print(sb).append(",");
-        sb.setLength(sb.length()-1);
+            t.print(sb).append(", ");
+        sb.setLength(sb.length()-2);
         sb.append("]");
         return sb;
     }
 
-    @Override public String str() { return _print(new StringBuilder()).toString(); }
+    @Override public String str() { return print(new StringBuilder()).toString(); }
 
     /**
      * Display Type name in a format that's good for IR printer
diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index 8d15493f..9d154413 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -37,7 +37,7 @@ if (arg == 1) {
 }
 return c;""", TypeInteger.BOT);
         StopNode ret = parser.parse().iterate();
-        assertEquals("return Phi(Region18,4,3);", ret.toString());
+        assertEquals("return Phi(Region19,4,3);", ret.toString());
     }
 
     @Test
@@ -116,7 +116,7 @@ if( arg==0 )
 return arg+a+b;
 """, TypeInteger.BOT);
         StopNode stop = parser.parse();
-        assertEquals("return ((arg+Phi(Region15,1,0))+Phi(Region30,2,0));", stop.toString());
+        assertEquals("return ((arg+Phi(Region17,1,0))+Phi(Region33,2,0));", stop.toString());
     }
 
     @Test
@@ -130,7 +130,7 @@ if( arg==1 )
 }
 return a;""");
         StopNode ret = parser.parse().iterate();
-        assertEquals("return (arg==Phi(Region18,3,2));", ret.toString());
+        assertEquals("return (arg==Phi(Region19,3,2));", ret.toString());
     }
 
     @Test
diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
index 7b11bc35..633b25e0 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -30,7 +30,7 @@ if (arg)
 return (arg < a) < 3;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return ((arg<Phi(Region14,2,1))<3);", stop.toString());
+        assertEquals("return ((arg<Phi(Region16,2,1))<3);", stop.toString());
     }
 
     @Test
@@ -200,7 +200,7 @@ if( arg ) {
 return a+b;
 """);
         StopNode ret = parser.parse().iterate();
-        assertEquals("return Phi(Region26,4,1);", ret.toString());
+        assertEquals("return Phi(Region28,4,1);", ret.toString());
     }
 
 
@@ -251,7 +251,7 @@ if( arg ) {
 return a+b+c;
 """);
         StopNode ret = parser.parse().iterate();
-        assertEquals("return (Phi(Region38,Phi(Region25,2,3),0)+Phi(Region,3,1));", ret.toString());
+        assertEquals("return (Phi(Region40,Phi(Region25,2,3),0)+Phi(Region,3,1));", ret.toString());
     }
 
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
index 6aa74125..7760ae09 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
@@ -23,7 +23,7 @@ while(arg < 10) {
 return arg;
                 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region36,Phi(Region26,Phi(Loop8,arg,(Phi_arg+1)),Add),Add);", stop.toString());
+        assertEquals("return Phi(Region37,Phi(Region26,Phi(Loop8,arg,(Phi_arg+1)),Add),Add);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof RegionNode);
         Assert.assertEquals(5L, Evaluator.evaluate(stop, 1));
         Assert.assertEquals(10L, Evaluator.evaluate(stop, 6));
@@ -46,7 +46,7 @@ while(arg < 10) {
 return a;
                 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop9,1,Phi(Region41,Phi_a,(Phi_a+1)));", stop.toString());
+        assertEquals("return Phi(Loop9,1,Phi(Region43,Phi_a,(Phi_a+1)));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof CProjNode);
     }
 
@@ -65,7 +65,7 @@ while(arg < 10) {
 return arg;
                 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region34,Phi(Loop8,arg,(Phi_arg+1)),Add);", stop.toString());
+        assertEquals("return Phi(Region35,Phi(Loop8,arg,(Phi_arg+1)),Add);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof RegionNode);
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index 4a9521b9..c9f695c9 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -1,12 +1,7 @@
 package com.seaofnodes.simple;
 
-import com.seaofnodes.simple.node.Node;
 import com.seaofnodes.simple.node.StopNode;
-import com.seaofnodes.simple.type.*;
 import org.junit.Test;
-
-import java.util.Arrays;
-
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
@@ -33,7 +28,7 @@ if( (arg/13)==0 ) {
 int r = g+h;
 return p-r;
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return 0;", stop.toString());
     }
 
@@ -108,7 +103,7 @@ while (arg) {
 return bar.a;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString());
+        assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString());
     }
 
     @Test
@@ -160,7 +155,7 @@ if( bar ) bar.a = 1;
 return bar;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region16,null,new Bar);", stop.toString());
+        assertEquals("return Phi(Region31,(*void)Phi(Region19,null,new Bar),null);", stop.toString());
     }
 
     @Test
@@ -176,7 +171,7 @@ else bar.a = 1;
 return rez;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region33,4,3);", stop.toString());
+        assertEquals("return Phi(Region37,4,3);", stop.toString());
     }
 
     @Test
@@ -230,7 +225,7 @@ while( i.x < i.len ) {
 return sum;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop15,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString());
+        assertEquals("return Phi(Loop17,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString());
     }
 
 
@@ -251,7 +246,7 @@ while(arg) {
 return ret;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop11,new s0,Phi(Region31,new s0,Phi_ret));", stop.toString());
+        assertEquals("return Phi(Loop12,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString());
     }
 
     @Test
@@ -264,11 +259,12 @@ while(arg) {
     v0.v0 = arg;
     arg = arg-1;
     if (arg==5) ret=v0;
+
 }
 return ret;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop13,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString());
+        assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString());
     }
 
 
@@ -285,7 +281,7 @@ while(arg < 10) {
 return ret;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop11,new s0,Phi(Region30,new s0,Phi_ret));", stop.toString());
+        assertEquals("return Phi(Loop12,new s0,Phi(Region33,new s0,Phi_ret));", stop.toString());
     }
 
     @Test
diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
index a8b09226..da0bc087 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
@@ -291,7 +291,7 @@ else {
         }
 }
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; ]", stop.toString());
     }
 
@@ -324,7 +324,7 @@ while( prime <= arg ) {
 return primeCount;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("Stop[ return 0; return Phi(Loop19,1,Phi(Region81,Phi_primeCount,Phi(Region76,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString());
+        assertEquals("Stop[ return 0; return Phi(Loop20,1,Phi(Region87,Phi_primeCount,Phi(Region81,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString());
         assertEquals(0L, Evaluator.evaluate(stop,  1)); // No primes 1 or below
         assertEquals(1L, Evaluator.evaluate(stop,  2)); // 2
         assertEquals(2L, Evaluator.evaluate(stop,  3)); // 2, 3
@@ -366,7 +366,7 @@ if (arg) {
 return i;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region31,.f,0);", stop.toString());
+        assertEquals("return Phi(Region34,.f,0);", stop.toString());
     }
 
     @Test
@@ -451,7 +451,7 @@ while (arg) {
 }
 return i;
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return .f;", stop.toString());
     }
 
@@ -471,8 +471,8 @@ while(arg) {
 }
 return arg;
 """);
-        StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop13,arg,Phi(Region35,.f,0));", stop.toString());
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return Phi(Loop15,arg,Phi(Region37,.f,0));", stop.toString());
     }
 
     @Test
@@ -489,7 +489,7 @@ if (arg) {
 }
 return v;
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return new S;", stop.toString());
     }
 
@@ -523,7 +523,7 @@ else if (arg == 1) s.f = 1;
 return s.f;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region35,1,Phi(Region33,1,0));", stop.toString());
+        assertEquals("return Phi(Region37,1,Phi(Region35,1,0));", stop.toString());
         assertEquals(1L, Evaluator.evaluate(stop,  0));
         assertEquals(1L, Evaluator.evaluate(stop,  1));
         assertEquals(0L, Evaluator.evaluate(stop,  2));
diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
index af8fdfe9..62dce12b 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
@@ -2,9 +2,8 @@ package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.evaluator.Evaluator;
 import com.seaofnodes.simple.node.StopNode;
+import org.junit.Ignore;
 import org.junit.Test;
-
-
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
@@ -15,7 +14,7 @@ public class Chapter12Test {
 """
 return 3.14;
 """);
-        StopNode stop = parser.parse(false).iterate(false);
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return 3.14;", stop.toString());
         assertEquals(3.14, Evaluator.evaluate(stop,  0));
     }
@@ -26,7 +25,7 @@ return 3.14;
 """
 return 3.14;
 """);
-        StopNode stop = parser.parse(false).iterate(false);
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return 3.14;", stop.toString());
         assertEquals(3.14, Evaluator.evaluate(stop,  0));
     }
@@ -43,7 +42,7 @@ while( 1 ) {
 }
 return guess;
 """);
-        StopNode stop = parser.parse(false).iterate(false);
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return Phi(Loop9,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString());
         assertEquals(3.0, Evaluator.evaluate(stop,  9));
         assertEquals(1.414213562373095, Evaluator.evaluate(stop,  2));
@@ -56,7 +55,7 @@ return guess;
 flt x = arg;
 return x+1==x;
 """);
-        StopNode stop = parser.parse(false).iterate(false);
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString());
         assertEquals(0L, Evaluator.evaluate(stop, 1));
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java
new file mode 100644
index 00000000..b425fd85
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java
@@ -0,0 +1,184 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.evaluator.Evaluator;
+import com.seaofnodes.simple.node.StopNode;
+import org.junit.Ignore;
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+public class Chapter13Test {
+    @Test
+    public void testJig() {
+        Parser parser = new Parser(
+"""
+return 3.14;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return 3.14;", stop.toString());
+        assertEquals(3.14, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testLinkedList0() {
+        Parser parser = new Parser(
+"""
+struct LLI { LLI? next; int i; }
+LLI? head = null;
+while( arg ) {
+    LLI x = new LLI;
+    x.next = head;
+    x.i = arg;
+    head = x;
+    arg = arg-1;
+}
+return head.next.i;
+""");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); }
+    }
+
+    @Test
+    public void testLinkedList1() {
+        Parser parser = new Parser(
+"""
+struct LLI { LLI? next; int i; }
+LLI? head = null;
+while( arg ) {
+    LLI x = new LLI;
+    x.next = head;
+    x.i = arg;
+    head = x;
+    arg = arg-1;
+}
+if( !head ) return 0;
+LLI? next = head.next;
+if( next==null ) return 1;
+return next.i;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString());
+        assertEquals(2L, Evaluator.evaluate(stop,  3));
+    }
+
+    @Test
+    public void testCoRecur() {
+        Parser parser = new Parser(
+"""
+struct int0 { int i; flt0? f; }
+struct flt0 { flt f; int0? i; }
+int0 i0 = new int0;
+i0.i = 17;
+flt0 f0 = new flt0;
+f0.f = 3.14;
+i0.f = f0;
+f0.i = i0;
+return f0.i.f.i.i;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return 17;", stop.toString());
+    }
+
+    @Test
+    public void testNullRef0() {
+        Parser parser = new Parser(
+"""
+struct N { N next; int i; }
+N n = new N;
+return n.next;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return null;", stop.toString());
+    }
+
+    @Test
+    public void testNullRef1() {
+        Parser parser = new Parser(
+"""
+struct N { N next; int i; }
+N n = new N;
+n.next = new N;
+return n.next;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return new N;", stop.toString());
+    }
+
+    @Test
+    public void testNullRef2() {
+        Parser parser = new Parser(
+"""
+struct N { N next; int i; }
+N n = new N;
+n.next = null;
+return n.next;
+""");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Cannot store null into field *N next",e.getMessage()); }
+    }
+
+    @Test
+    public void testNullRef3() {
+        Parser parser = new Parser(
+"""
+struct N { N next; int i; }
+N n = new N;
+n.i = 3.14;
+return n.i;
+""");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Cannot store 3.14 into field IntBot i",e.getMessage()); }
+    }
+
+    @Test
+    public void testEmpty() {
+        Parser parser = new Parser(
+"""
+struct S{};
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return 0;", stop.toString());
+        assertEquals(0L, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testForwardRef0() {
+        Parser parser = new Parser(
+"""
+struct S1 { S2 s; }
+return new S2;
+""");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); }
+    }
+
+    @Test
+    public void testForwardRef1() {
+        Parser parser = new Parser(
+"""
+struct S1 { S2? s; }
+struct S2 { int x; }
+return new S1.s=new S2;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return new S1;", stop.toString());
+    }
+
+    @Test
+    public void testcheckNull() {
+        Parser parser = new Parser(
+"""
+struct I {int i;}
+struct P {I pi;}
+P p1 = new P;
+P p2 = new P;
+p2.pi = new I;
+p2.pi.i = 2;
+if (arg) p1 = new P;
+return p1.pi.i + 1;
+""");
+        try { parser.parse(false).iterate();  fail(); }
+        catch( Exception e ) {  assertEquals("Might be null accessing 'i'",e.getMessage());  }
+    }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/src/test/java/com/seaofnodes/simple/SchedulerTest.java
index 5def2782..853999b1 100644
--- a/src/test/java/com/seaofnodes/simple/SchedulerTest.java
+++ b/src/test/java/com/seaofnodes/simple/SchedulerTest.java
@@ -31,7 +31,7 @@ if (arg) v.f=1;
 return i;
 """);
         StopNode._disablePeephole = true;
-        StopNode stop = parser.parse(true);//.iterate();
+        StopNode stop = parser.parse();//.iterate();
         var eval = new Evaluator(stop);
         assertEquals(2L, eval.evaluate(1, 10));
     }
diff --git a/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java
index f9c580cc..9e8a1418 100644
--- a/src/test/java/com/seaofnodes/simple/TypeTest.java
+++ b/src/test/java/com/seaofnodes/simple/TypeTest.java
@@ -2,8 +2,8 @@ package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.type.*;
 import org.junit.Assert;
+import org.junit.Ignore;
 import org.junit.Test;
-
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertSame;
 
@@ -36,9 +36,9 @@ public class TypeTest {
         Assert.assertEquals(TypeMem   .BOT, m2.meet(m3));
         Assert.assertEquals(TypeMem   .BOT, m3.meet(m4));
 
-        Assert.assertEquals(TypeMem.BOT, m1.glb());
-        Assert.assertEquals(m1, m1.dual());
-        Assert.assertEquals(TypeMem.TOP, m1.glb().dual());
+        Assert.assertEquals(m1, m1.glb());
+        Assert.assertEquals(TypeMem.make(1), m1.dual());
+        Assert.assertEquals(m1.dual(), m1.glb().dual());
 
         TypeMemPtr ptr1 = TypeMemPtr.make(s1);
         Assert.assertEquals(s1, ptr1._obj);
@@ -128,10 +128,13 @@ public class TypeTest {
     private static void check_symmetric( Type t0, Type t1 ) {
         if( t1==t0 ) return;
         Type mt = t0.meet(t1);
-        Type ta = mt.dual().meet(t1.dual());
-        Type tb = mt.dual().meet(t0.dual());
-        assertSame(ta,t1.dual());
-        assertSame(tb,t0.dual());
+        Type dm = mt.dual();
+        Type d0 = t0.dual();
+        Type d1 = t1.dual();
+        Type ta = dm.meet(d1);
+        Type tb = dm.meet(d0);
+        assertSame(ta,d1);
+        assertSame(tb,d0);
     }
 
     private static void assoc( Type t0, Type t1, Type t2 ) {
@@ -142,4 +145,13 @@ public class TypeTest {
         assertSame(t01_2,t0_12);
     }
 
+    // Test cyclic types and meets
+    @Test
+    public void testCyclic0() {
+        Type d0 = TypeStruct.S1.dual();
+        Type d1 = d0.dual();
+        assertSame(TypeStruct.S1,d1);
+    }
+
+
 }
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
index b8437b50..94929241 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
@@ -3,9 +3,7 @@ package com.seaofnodes.simple.fuzzer;
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.node.ScopeNode;
 
-import java.util.ArrayList;
-import java.util.HashSet;
-import java.util.Random;
+import java.util.*;
 import java.util.function.Predicate;
 
 /**
@@ -70,11 +68,10 @@ public class ScriptGenerator {
 
     private static class TypeStruct extends Type {
         record Field (String name, Type type, TypeStruct struct) {}
-        final Field[] fields;
+        Field[] fields;
         final TypeNullable nullable = new TypeNullable(this);
-        TypeStruct(String name, Field[] fields) {
+        TypeStruct(String name) {
             super(name);
-            this.fields = fields;
         }
         boolean isa(Type other) { return this == other || other == nullable; }
     }
@@ -159,6 +156,10 @@ public class ScriptGenerator {
      */
     private final ArrayList<TypeStruct> structs = new ArrayList<>();
     /**
+     * All forward declared structs
+     */
+    private final ArrayList<TypeStruct> forwardStructs = new ArrayList<>();
+    /**
      * Allow to declare structs.
      */
     private boolean allowStructs = true;
@@ -301,6 +302,7 @@ public class ScriptGenerator {
         for (var s:structs) {
             if (s.name.equals(name)) return s;
         }
+        for (var s:forwardStructs) if (s.name.equals(name)) return s;
         return null;
     }
 
@@ -333,12 +335,18 @@ public class ScriptGenerator {
         return v;
     }
 
+    private <T> T randFromList(List<T> list) {
+        return list.get(random.nextInt(list.size()));
+    }
+
     /**
      * Get a random structure name
      * @return A random structure name
      */
     private String getStructName() {
-        if (!structs.isEmpty() && generateInvalid()) return structs.get(random.nextInt(structs.size())).name;
+        if (!structs.isEmpty() && generateInvalid()) return randFromList(structs).name;
+        if (!forwardStructs.isEmpty() && generateInvalid()) return randFromList(forwardStructs).name;
+
         // Generate a new random struct name
         StringBuilder sb = getRandomName();
         var v = sb.toString();
@@ -357,16 +365,27 @@ public class ScriptGenerator {
      * Get a random type
      * @return A random type
      */
-    private Type getType() {
+    private Type getType(boolean allowForward) {
         int t = random.nextInt(10);
         if( t<5 || structs.isEmpty() ) return TYPE_INT;
         if( t<7 ) return TYPE_FLT;
-        var idx = random.nextInt(structs.size());
-        TypeStruct struct = structs.get(idx);
+        if (allowForward && random.nextInt(10)==0) {
+            int i=random.nextInt(forwardStructs.size()+1);
+            if (i>0) return forwardStructs.get(i-1).nullable;
+            var name = getStructName();
+            var struct = new TypeStruct(name);
+            forwardStructs.add(struct);
+            return struct.nullable;
+        }
+        TypeStruct struct = randFromList(structs);
         if (random.nextBoolean()) return struct.nullable;
         return struct;
     }
 
+    private Type getType() {
+        return getType(false);
+    }
+
     /**
      * Generates a program and writes it into the string builder supplied in the constructor.
      * @return If the program is allowed to be invalid returns if something potentially invalid was generated.
@@ -426,19 +445,28 @@ public class ScriptGenerator {
      * @return 0
      */
     public int genStruct() {
-        var name = getStructName();
+        int idx = random.nextInt(forwardStructs.size()+10);
+        TypeStruct struct;
+        if (idx < 10) {
+            var name = getStructName();
+            struct = new TypeStruct(name);
+            forwardStructs.add(struct);
+        } else {
+            struct = forwardStructs.get(idx-10);
+        }
         var fields = new TypeStruct.Field[generateInvalid() ? 0 : random.nextInt(10)];
-        var struct = new TypeStruct(name, fields);
-        sb.append("struct ").append(name).append(" {\n");
+        sb.append("struct ").append(struct.name).append(" {\n");
         indentation += INDENTATION;
         for (int i=0; i<fields.length; i++) {
             var fieldName = getRandomName();
-            var type = getType();
+            var type = getType(true);
             printIndentation().append(type.name).append(" ").append(fieldName).append(";\n");
             fields[i] = new TypeStruct.Field(fieldName.toString(), type, struct);
         }
         indentation -= INDENTATION;
         printIndentation().append("}");
+        struct.fields = fields;
+        forwardStructs.remove(struct);
         structs.add(struct);
         return 0;
     }
@@ -804,7 +832,7 @@ public class ScriptGenerator {
         } else if (type == TYPE_FLT) {
             sb.append(random.nextFloat());
         } else if (type instanceof TypeNullable n) {
-            if (random.nextBoolean()) {
+            if ((n.base instanceof TypeStruct s && s.fields == null) || random.nextBoolean()) {
                 sb.append("null");
             } else {
                 sb.append("new ").append(generateInvalid() ? getRandomName() : n.base.name);