Ref types working

GCM uses a breadth-first pass for schedule-late instead of a post-order; the post-order walk depends on StoreNodes being pinned, which is true in C2 but not Simple.

Move GCM call out of IterPeeps.
Struct field init is "makeInit()" not integer zero.
Rename Type._print to print.
Store,Load prints include field name.

16 files changed, 169 insertions, 107 deletions

diff --git a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index 4e0a31d5..8a96e69c 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java
index 121d0233..783fc4f1 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/Parser.java b/chapter13/src/main/java/com/seaofnodes/simple/Parser.java
index 9182a74c..56c8e955 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter13/src/main/java/com/seaofnodes/simple/Parser.java
@@ -178,7 +178,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()+"'");
@@ -199,14 +199,14 @@ public class Parser {
         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();
     }
@@ -349,8 +349,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;
         }
@@ -432,24 +432,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;
     }
 
 
@@ -583,7 +595,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, memAlias(alias), n, ZERO).peephole());
+            memAlias(alias, new StoreNode(field._fname, alias, memAlias(alias), n, new ConstantNode(field._type.makeInit()).peephole()).peephole());
             alias++;
         }
         return n.unkeep();
@@ -613,7 +625,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;
 
@@ -627,7 +641,7 @@ public class Parser {
             }
         }
 
-        Type declaredType = ptr._obj._fields[idx]._type;
+        Type declaredType = base._fields[idx]._type;
         return parsePostfix(new LoadNode(name, alias, declaredType, memAlias(alias), expr).peephole());
     }
 
@@ -636,7 +650,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/chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java
index fec540f7..fbf0e518 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java
+++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index cf1a76b0..016b0b9b 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 95d49662..e235cc36 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter13/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;
 
@@ -26,10 +25,7 @@ public class LoadNode extends MemOpNode {
     }
 
     @Override
-    public String label() { return "Load"; }
-
-    @Override
-    public String glabel() { return "."+_name; }
+    public String label() { return "."+_name; }
 
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); }
diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/StopNode.java
index ab567bae..0eacc1f4 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index 7c41e767..2b4a46dd 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -22,9 +22,7 @@ public class StoreNode extends MemOpNode {
     }
 
     @Override
-    public String label() { return "Store"; }
-    @Override
-    public String glabel() { return "."+_name+" ="; }
+    public String label() { return "."+_name+"="; }
     @Override
     public boolean isMem() { return true; }
     public Node val() { return in(3); }
diff --git a/chapter13/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter13/src/main/java/com/seaofnodes/simple/type/Field.java
index e1c337d4..b2c006dd 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/type/Field.java
+++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter13/src/main/java/com/seaofnodes/simple/type/Type.java
index f3152719..1f211430 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
index 36bc61f5..738aebc9 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
+++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index f2a93a3a..8c77672b 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMem.java
index 198d49ee..b2d081f4 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMem.java
+++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
index 65352402..1ad65611 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
+++ b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
@@ -27,7 +27,8 @@ public class TypeMemPtr extends Type {
         _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();
@@ -63,10 +64,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/chapter13/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
index 29102675..e2489d6f 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
+++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index 01bcbe9f..783f3f60 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/chapter13/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