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>

20 files changed, 215 insertions, 136 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