Chapter 10: Structs and Memorylinear-chapter10

Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: XmiliaH <xmilia.hermit@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

21 files changed, 584 insertions, 118 deletions

diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 4e30bb55..2cc0b465 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -132,7 +132,7 @@ public class AddNode extends Node {
         for( int i=1; i<ns.length; i++ )
             ns[i] = op.copy(lphi.in(i), rhs instanceof PhiNode ? rhs.in(i) : rhs).peephole();
         String label = lphi._label + (rhs instanceof PhiNode rphi ? rphi._label : "");
-        Node phi = new PhiNode(label,ns).peephole();
+        Node phi = new PhiNode(label,lphi._declaredType,ns).peephole();
         // Rotate needs another op, otherwise just the phi
         return lhs==lphi ? phi : op.copy(lhs.in(1),phi);
     }
diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index d3fcec95..9c15f01b 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -2,6 +2,7 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
+import com.seaofnodes.simple.type.TypeMemPtr;
 
 import java.util.BitSet;
 
@@ -44,10 +45,25 @@ abstract public class BoolNode extends Node {
         if( in(1)==in(2) )
             return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0));
 
+        // Equals pushes constant to the right; 5==X becomes X==5.
+        if( this instanceof EQ ) {
+            if( !(in(2) instanceof ConstantNode) ) {
+                // con==noncon becomes noncon==con
+                if( in(1) instanceof ConstantNode )
+                    return new EQ(in(2),in(1));
+                // Equals sorts by NID otherwise: non.high == non.low becomes non.low == non.high
+                else if( in(1)._nid > in(2)._nid )
+                    return new EQ(in(2),in(1));
+            }
+            // Equals X==0 becomes a !X
+            if( (in(2)._type == TypeInteger.ZERO || in(2)._type == TypeMemPtr.NULLPTR) )
+                return new NotNode(in(1));
+        }
+
         // Do we have ((x * (phi cons)) * con) ?
         // Do we have ((x * (phi cons)) * (phi cons)) ?
         // Push constant up through the phi: x * (phi con0*con0 con1*con1...)
-        Node phicon = AddNode.phiCon(this,false);
+        Node phicon = AddNode.phiCon(this,this instanceof EQ);
         if( phicon!=null ) return phicon;
 
         return null;
diff --git a/src/main/java/com/seaofnodes/simple/node/CastNode.java b/src/main/java/com/seaofnodes/simple/node/CastNode.java
new file mode 100644
index 00000000..fec540f7
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/CastNode.java
@@ -0,0 +1,38 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+import com.seaofnodes.simple.IterPeeps;
+
+import java.util.BitSet;
+
+// Upcast (join) the input to a t.  Used after guard test to lift an input.
+// Can also be used to make a type-assertion if ctrl is null.
+public class CastNode extends Node {
+    private final Type _t;
+    public CastNode(Type t, Node ctrl, Node in) {
+        super(ctrl, in);
+        _t = t;
+        setType(compute());
+    }
+
+    @Override public String label() { return "("+_t.str()+")"; }
+
+    @Override
+    public String uniqueName() { return "Cast_" + _nid; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        return in(1)._print0(sb.append(label()), visited);
+    }
+
+    @Override
+    public Type compute() {
+        return in(1)._type.join(_t);
+    }
+
+    @Override
+    public Node idealize() {
+        return in(1)._type.isa(_t) ? in(1) : null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 9e45198c..ca42c2dc 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -51,8 +51,4 @@ public class ConstantNode extends Node {
 
     @Override
     int hash() { return _con.hashCode(); }
-
-    // Dead control is its own idom root
-    Node idom() { return null; }
-
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 460dce51..1cf4ddaf 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -1,15 +1,16 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 import com.seaofnodes.simple.type.TypeTuple;
-
 import java.util.BitSet;
 
 public class IfNode extends MultiNode {
 
     public IfNode(Node ctrl, Node pred) {
         super(ctrl, pred);
+        IterPeeps.add(this);    // Because idoms are complex, just add it
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
new file mode 100644
index 00000000..53ae1096
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -0,0 +1,78 @@
+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;
+
+/**
+ * Load represents extracting a value from inside a memory object,
+ * in chapter 10 this means Struct fields.
+ */
+public class LoadNode extends MemOpNode {
+
+    Type _declaredType;
+    /**
+     * Load a value from a ptr.field.
+     *
+     * @param name  The field we are loading
+     * @param memSlice The memory alias node - this is updated after a Store
+     * @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, memSlice, memPtr, null);
+        _declaredType = glb;
+    }
+
+    @Override
+    public String label() { return "Load"; }
+
+    @Override
+    public String glabel() { return "."+_name; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); }
+
+    @Override
+    public Type compute() {
+        return _declaredType;
+    }
+
+    @Override
+    public Node idealize() {
+
+        // Simple Load-after-Store on same address.
+        if( mem() instanceof StoreNode st &&
+            ptr() == st.ptr() ) { // Must check same object
+            assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect
+            return st.val();
+        }
+
+        // Push a Load up through a Phi, as long as it collapses on at least
+        // one arm.  If at a Loop, the backedge MUST collapse - else we risk
+        // spinning the same transform around the loop indefinitely.
+        //   BEFORE (2 Sts, 1 Ld):          AFTER (1 St, 0 Ld):
+        //   if( pred ) ptr.x = e0;         val = pred ? e0
+        //   else       ptr.x = e1;                    : e1;
+        //   val = ptr.x;                   ptr.x = val;
+        if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) {
+            // Profit on RHS/Loop backedge
+            if( profit(memphi,2) ||
+                // Else must not be a loop to count profit on LHS.
+                (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) {
+                Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole();
+                Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole();
+                return new PhiNode(_name,_type,memphi.region(),ld1,ld2);
+            }
+        }
+
+        return null;
+    }
+
+    // Profitable if we find a matching Store on this Phi arm.
+    private boolean profit(PhiNode phi, int idx) {
+        Node px = phi.in(idx);
+        return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr();
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index c192bc20..ea1489c4 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -25,5 +25,7 @@ public class LoopNode extends RegionNode {
         return inProgress() ? null : super.idealize();
     }
 
+    // Bypass Region idom, same as the default idom() using use entry in(1) instead of in(0)
+    @Override int idepth() { return _idepth(1); }
     @Override Node idom() { return entry(); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
new file mode 100644
index 00000000..08e08bbf
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -0,0 +1,40 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Field;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMemPtr;
+
+/**
+ * Convenience common base for Load and Store.
+ */
+public abstract class MemOpNode extends Node {
+
+    public final String _name;
+    public final int _alias;
+
+    public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) {
+        super(null, memSlice, memPtr, value);
+        _name  = name;
+        _alias = alias;
+    }
+
+    public Node mem() { return in(1); }
+    public Node ptr() { return in(2); }
+
+    @Override
+    boolean eq(Node n) {
+        MemOpNode mem = (MemOpNode)n; // Invariant
+        return _alias==mem._alias;    // When comparing types error to use "equals"; always use "=="
+    }
+
+    @Override
+    int hash() { return _alias; }
+
+    @Override
+    String err() {
+        Type ptr = ptr()._type;
+        return (ptr==Type.BOTTOM || (ptr instanceof TypeMemPtr tmp && tmp._nil) )
+            ? "Might be null accessing '" + _name + "'"
+            : null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index dd092c9e..9b687613 100644
--- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -26,5 +26,11 @@ public class MinusNode extends Node {
     }
 
     @Override
-    public Node idealize() { return null; }
+    public Node idealize() {
+        // -(-x) is x
+        if( in(1) instanceof MinusNode minus )
+            return minus.in(1);
+
+        return null;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java
new file mode 100644
index 00000000..352689b5
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java
@@ -0,0 +1,40 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMemPtr;
+
+import java.util.BitSet;
+
+public class NewNode extends Node {
+
+    TypeMemPtr _ptr;
+
+    public NewNode(TypeMemPtr ptr, Node ctrl) {
+        super(ctrl);
+        this._ptr = ptr;
+    }
+
+    @Override
+    public String label() { return "new"; }
+
+    @Override
+    public String glabel() { return "new " + _ptr._obj._name; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        sb.append("new ");
+        return sb.append(_ptr._obj.str());
+    }
+
+    @Override
+    public Type compute() { return _ptr; }
+
+    @Override
+    public Node idealize() { return null; }
+
+    @Override
+    boolean eq(Node n) { return this == n; }
+
+    @Override
+    int hash() { return _ptr.hashCode(); }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 5eb9c076..bb698860 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -51,15 +51,6 @@ public abstract class Node {
 
 
     /**
-     * Immediate dominator tree depth, used to approximate a real IDOM during
-     * parsing where we do not have the whole program, and also peepholes
-     * change the CFG incrementally.
-     * <p>
-     * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
-     */
-    int _idepth;
-
-    /**
      * A private Global Static mutable counter, for unique node id generation.
      * To make the compiler multithreaded, this field will have to move into a TLS.
      * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values.
@@ -81,7 +72,11 @@ public abstract class Node {
     public abstract String label();
 
     // Unique label for graph visualization, e.g. "Add12" or "Region30" or "EQ99"
-    public String uniqueName() { return label() + _nid; }
+    public String uniqueName() {
+        // Get rid of $ as graphviz doesn't like it
+        String label = label().replaceAll("\\$", "");
+        return label + _nid;
+    }
 
     // Graphical label, e.g. "+" or "Region" or "=="
     public String glabel() { return label(); }
@@ -118,31 +113,6 @@ public abstract class Node {
     // Every Node implements this; a partial-line recursive print
     abstract StringBuilder _print1(StringBuilder sb, BitSet visited);
 
-
-    // Print a node on 1 line, columnar aligned, as:
-    // NNID NNAME DDEF DDEF  [[  UUSE UUSE  ]]  TYPE
-    // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt
-    public void _printLine(StringBuilder sb ) {
-        sb.append("%4d %-7.7s ".formatted(_nid,label()));
-        if( _inputs==null ) {
-            sb.append("DEAD\n");
-            return;
-        }
-        for( Node def : _inputs )
-            sb.append(def==null ? "____ " : "%4d ".formatted(def._nid));
-        for( int i = _inputs.size(); i<3; i++ )
-            sb.append("     ");
-        sb.append(" [[  ");
-        for( Node use : _outputs )
-            sb.append(use==null ? "____ " : "%4d ".formatted(use._nid));
-        int lim = 5 - Math.max(_inputs.size(),3);
-        for( int i = _outputs.size(); i<lim; i++ )
-            sb.append("     ");
-        sb.append(" ]]  ");
-        if( _type!= null ) _type._print(sb);
-        sb.append("\n");
-    }
-
     public String p(int depth) { return IRPrinter.prettyPrint(this,depth); }
 
     public boolean isMultiHead() { return false; }
@@ -167,6 +137,8 @@ public abstract class Node {
 
     public boolean isCFG() { return false; }
 
+    public boolean isMem() { return false; }
+
     /**
      * Change a <em>def</em> into a Node.  Keeps the edges correct, by removing
      * the corresponding <em>use->def</em> edge.  This may make the original
@@ -197,6 +169,7 @@ public abstract class Node {
             old_def.kill();     // Kill old def
         // Set the new_def over the old (killed) edge
         _inputs.set(idx,new_def);
+        moveDepsToWorklist();
         // Return self for easy flow-coding
         return new_def;
     }
@@ -283,7 +256,12 @@ public abstract class Node {
     // Add bogus null use to keep node alive
     public <N extends Node> N keep() { return addUse(null); }
     // Remove bogus null.
-    public <N extends Node> N unkeep() { delUse(null); return (N)this; }
+    public <N extends Node> N unkeep() {
+        delUse(null);
+        return (N)this;
+    }
+    // Test "keep" status
+    public boolean iskeep() { return Utils.find(_outputs,null) != -1; }
 
 
     // Replace self with nnn in the graph, making 'this' go dead
@@ -345,7 +323,7 @@ public abstract class Node {
         Type old = setType(compute());
 
         // Replace constant computations from non-constants with a constant node
-        if (!(this instanceof ConstantNode) && _type.isHighOrConst() )
+        if( !(this instanceof ConstantNode) && _type.isHighOrConst() )
             return new ConstantNode(_type).peepholeOpt();
 
         // Global Value Numbering
@@ -380,7 +358,7 @@ public abstract class Node {
     private Node deadCodeElim(Node m) {
         // If self is going dead and not being returned here (Nodes returned
         // from peephole commonly have no uses (yet)), then kill self.
-        if( m != this && isUnused() ) {
+        if( m != this && isUnused() && !isDead() ) {
             // Killing self - and since self recursively kills self's inputs we
             // might end up killing 'm', which we are returning as a live Node.
             // So we add a bogus extra null output edge to stop kill().
@@ -478,9 +456,9 @@ public abstract class Node {
     ArrayList<Node> _deps;
 
     /**
-     * Add a node to the list o dependencies. Only add it if its not
-     * an input or output of this node, that is, it is at least one step
-     * away. The node being added must benefit from this node being peepholed.
+     * Add a node to the list of dependencies.  Only add it if its not an input
+     * or output of this node, that is, it is at least one step away.  The node
+     * being added must benefit from this node being peepholed.
      */
     Node addDep( Node dep ) {
         // Running peepholes during the big assert cannot have side effects
@@ -567,14 +545,11 @@ public abstract class Node {
     }
 
     /**
-     * Does this node contain all constants?
-     * Ignores in(0), as is usually control.
-     * In an input is not a constant, we add dep as
-     * a dependency to it, because dep can make progress
-     * if the input becomes a constant later.
-     * It is sufficient for one of the non-const
-     * inputs to have the dependency so we don't bother
-     * checking the rest.
+     * Does this node contain all constants?  Ignores in(0), as is usually
+     * control.  In an input is not a constant, we add dep as a dependency to
+     * it because dep can make progress if the input becomes a constant later.
+     * It is sufficient for one of the non-const inputs to have the dependency,
+     * so we don't bother checking the rest.
      */
     boolean allCons(Node dep) {
         for( int i=1; i<nIns(); i++ )
@@ -585,19 +560,29 @@ public abstract class Node {
         return true;
     }
 
-    // Return the immediate dominator of this Node and compute dom tree depth.
-    Node idom() {
-        Node idom = in(0);
-        if( idom._idepth==0 ) idom.idom(); // Recursively set _idepth
-        if( _idepth==0 ) _idepth = idom._idepth+1;
-        return idom;
-    }
+
+    /**
+     * Immediate dominator tree depth, used to approximate a real IDOM depth
+     * during parsing where we do not have the whole program, and also
+     * peepholes change the CFG incrementally.
+     * <p>
+     * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
+     */
+    public int _idepth;         // IDOM depth approx; Zero is unset; non-zero is cached legit
+    final int _idepth(int idx) { return _idepth==0 ? (_idepth=in(idx).idepth()+1) : _idepth; }
+    int idepth() { return _idepth(0); }
+
+    // Return the immediate dominator of this Node.
+    Node idom() { return in(0); }
 
     // Make a shallow copy (same class) of this Node, with given inputs and
     // empty outputs and a new Node ID.  The original inputs are ignored.
     // Does not need to be implemented in isCFG() nodes.
     Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); }
 
+    // Report any post-optimize errors
+    String err() { return null; }
+
     /**
      * Used to allow repeating tests in the same JVM.  This just resets the
      * Node unique id generator, and is done as part of making a new Parser.
diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java
index 7a520fec..05e44eb0 100644
--- a/src/main/java/com/seaofnodes/simple/node/NotNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -1,8 +1,7 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeInteger;
-
+import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.type.*;
 import java.util.BitSet;
 
 public class NotNode extends Node {
@@ -20,9 +19,24 @@ public class NotNode extends Node {
 
     @Override
     public Type compute() {
-        if( in(1)._type instanceof TypeInteger i0 )
+        Type t0 = in(1)._type;
+        switch( t0 ) {
+        case TypeInteger i0:
             return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
-        return TypeInteger.TOP.meet(in(1)._type);
+        case TypeMemPtr p0:
+            // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot
+            // If input in null then true
+            // If input is not null ptr then false
+            if( p0 == TypeMemPtr.TOP  )    return TypeInteger.TOP;
+            if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.constant(1);
+            if( !p0._nil )                 return TypeInteger.constant(0);
+            return TypeInteger.BOT;
+        case Type t:
+            if( t0.getClass() != Type.class )
+                // Only doing NOT on ints and ptrs
+                throw Utils.TODO();
+            return t0==Type.TOP ? Type.TOP : Type.BOTTOM;
+        }
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index ec4c6ad3..dd67bd06 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -1,6 +1,8 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMem;
+import com.seaofnodes.simple.Utils;
 
 import java.util.BitSet;
 
@@ -8,7 +10,11 @@ public class PhiNode extends Node {
 
     final String _label;
 
-    public PhiNode(String label, Node... inputs) { super(inputs); _label = label; }
+    // The Phi type we compute must stay within the domain of the Phi.
+    // Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem.
+    final Type _declaredType;
+
+    public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label;  assert declaredType!=null; _declaredType = declaredType; }
 
     @Override public String label() { return "Phi_"+_label; }
 
@@ -31,17 +37,21 @@ public class PhiNode extends Node {
 
     Node region() { return in(0); }
     @Override public boolean isMultiTail() { return true; }
+    @Override
+    public boolean isMem() { return _declaredType instanceof TypeMem; }
 
     @Override
     public Type compute() {
         if( !(region() instanceof RegionNode r) )
             return region()._type==Type.XCONTROL ? Type.TOP : _type;
-        if( r.inProgress() ) return Type.BOTTOM;
-        Type t = Type.TOP;
+        // During parsing Phis have to be computed type pessimistically.
+        if( r.inProgress() ) return _declaredType;
+        // Set type to local top of the starting type
+        Type t = _declaredType.glb().dual();
         for (int i = 1; i < nIns(); i++)
             // If the region's control input is live, add this as a dependency
             // to the control because we can be peeped should it become dead.
-            if( r.in(i).addDep(this)._type != Type.XCONTROL && in(i) != this )
+            if( r.in(i).addDep(this)._type != Type.XCONTROL )
                 t = t.meet(in(i)._type);
         return t;
     }
@@ -71,11 +81,35 @@ public class PhiNode extends Node {
                 lhss[i] = in(i).in(1);
                 rhss[i] = in(i).in(2);
             }
-            Node phi_lhs = new PhiNode(_label,lhss).peephole();
-            Node phi_rhs = new PhiNode(_label,rhss).peephole();
+            Node phi_lhs = new PhiNode(_label, _declaredType,lhss).peephole();
+            Node phi_rhs = new PhiNode(_label, _declaredType,rhss).peephole();
             return op.copy(phi_lhs,phi_rhs);
         }
 
+        // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove.
+        if( nIns()==3 ) {
+            if( in(1) instanceof CastNode cast && cast.in(1).addDep(this)==in(2) ) return in(2);
+            if( in(2) instanceof CastNode cast && cast.in(1).addDep(this)==in(1) ) return in(1);
+        }
+        // If merging a null-checked null and the checked value, just use the value.
+        // if( val ) ..; phi(Region,False=0/null,True=val);
+        // then replace with plain val.
+        if( nIns()==3 ) {
+            int nullx = -1;
+            if( in(1)._type == in(1)._type.makeInit() ) nullx = 1;
+            if( in(2)._type == in(2)._type.makeInit() ) nullx = 2;
+            if( nullx != -1 ) {
+                Node val = in(3-nullx);
+                if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) {
+                    // Must walk the idom on the null side to make sure we hit False.
+                    Node idom = region().in(nullx);
+                    while( idom.in(0) != iff ) idom = idom.idom();
+                    if( idom instanceof ProjNode proj && proj._idx==1 )
+                        return val;
+                }
+            }
+        }
+
         return null;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 0ed9441d..735fcdf3 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMem;
 import com.seaofnodes.simple.type.TypeTuple;
 
 import java.util.BitSet;
@@ -27,6 +28,7 @@ public class ProjNode extends Node {
 
     @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; }
     @Override public boolean isMultiTail() { return in(0).isMultiHead(); }
+    @Override public boolean isMem() { return _type instanceof TypeMem; }
 
     public MultiNode ctrl() { return (MultiNode)in(0); }
 
@@ -38,8 +40,14 @@ public class ProjNode extends Node {
 
     @Override
     public Node idealize() {
-        if( ctrl()._type instanceof TypeTuple tt && tt._types[1-_idx]==Type.XCONTROL ) // Only true for IfNodes
-            return ctrl().in(0); // We become our input control
+        if ( ctrl() instanceof IfNode iff ) {
+            if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL )
+                return iff.in(0); // We become our input control
+
+            // Flip a negating if-test, to remove the not
+            if( iff.pred().addDep(this) instanceof NotNode not )
+                return new ProjNode((MultiNode)new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True");
+        }
         return null;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index c949c2b2..42501118 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -35,6 +35,7 @@ public class RegionNode extends Node {
     @Override
     public Node idealize() {
         if( inProgress() ) return null;
+        // Delete dead paths into a Region
         int path = findDeadInput();
         if( path != 0 &&
             // Do not delete the entry path of a loop (ok to remove the back
@@ -51,17 +52,25 @@ public class RegionNode extends Node {
             while( nouts != nOuts() ) {
                 nouts = nOuts();
                 for( int i=0; i<nOuts(); i++ )
-                    if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() )
+                    if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() ) {
                         phi.delDef(path);
+                        IterPeeps.addAll(phi._outputs);
+                    }
             }
-            _idom = null;       // Clear idom cache
             return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path);
         }
         // If down to a single input, become that input
-        if( nIns()==2 && !hasPhi() ) {
-            _idom = null;       // Clear idom cache
+        if( nIns()==2 && !hasPhi() )
             return in(1);       // Collapse if no Phis; 1-input Phis will collapse on their own
-        }
+
+        // If a CFG diamond with no merging, delete: "if( pred ) {} else {};"
+        if( !hasPhi() &&       // No Phi users, just a control user
+            in(1) instanceof ProjNode p1 &&
+            in(2) instanceof ProjNode p2 &&
+            p1.in(0)==p2.in(0) &&
+            p1.in(0) instanceof IfNode iff )
+            return iff.ctrl();
+
         return null;
     }
 
@@ -80,26 +89,28 @@ public class RegionNode extends Node {
     }
 
     // Immediate dominator of Region is a little more complicated.
-    private Node _idom;         // Immediate dominator cache
+    @Override int idepth() {
+        if( _idepth!=0 ) return _idepth;
+        int d=0;
+        for( Node n : _inputs )
+            if( n!=null )
+                d = Math.max(d,n.idepth());
+        return _idepth=d;
+    }
+
     @Override Node idom() {
-        if( _idom != null ) {
-            if( _idom.isDead() ) _idom=null;
-            else return _idom; // Return cached copy
-        }
         if( nIns()==2 ) return in(1); // 1-input is that one input
         if( nIns()!=3 ) return null;  // Fails for anything other than 2-inputs
-        // Walk the LHS & RHS idom trees in parallel until they match, or either fails
-        Node lhs = in(1).idom();
-        Node rhs = in(2).idom();
+        // Walk the LHS & RHS idom trees in parallel until they match, or either fails.
+        // Because this does not cache, it can be linear in the size of the program.
+        Node lhs = in(1);
+        Node rhs = in(2);
         while( lhs != rhs ) {
           if( lhs==null || rhs==null ) return null;
-          var comp = lhs._idepth - rhs._idepth;
+          var comp = lhs.idepth() - rhs.idepth();
           if( comp >= 0 ) lhs = lhs.idom();
           if( comp <= 0 ) rhs = rhs.idom();
         }
-        if( lhs==null ) return null;
-        _idepth = lhs._idepth+1;
-        if( !IterPeeps.midAssert() ) _idom=lhs;
         return lhs;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 922a3649..92bda5bf 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -15,8 +15,15 @@ import java.util.BitSet;
  */
 public class ReturnNode extends Node {
 
-    public ReturnNode(Node ctrl, Node data) {
+    public ReturnNode(Node ctrl, Node data, ScopeNode scope) {
         super(ctrl, data);
+        // We lookup memory slices by the naming convention that they start with $
+        // We could also use implicit knowledge that all memory projects are at offset >= 2
+        String[] names = scope.reverseNames();
+        for (String name: names) {
+            if (!name.equals("$ctrl") && name.startsWith("$"))
+                addDef(scope.lookup(name));
+        }
     }
 
     public Node ctrl() { return in(0); }
@@ -27,7 +34,9 @@ public class ReturnNode extends Node {
 
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
-        return expr()._print0(sb.append("return "), visited).append(";");
+        sb.append("return ");
+        expr()._print0(sb, visited);
+        return sb.append(";");
     }
 
     @Override public boolean isCFG() { return true; }
diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 3abea54d..843ce733 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.type.TypeMemPtr;
 
 import java.util.*;
 
@@ -23,10 +25,16 @@ public class ScopeNode extends Node {
      */
     public final Stack<HashMap<String, Integer>> _scopes;
 
+    /**
+     * Tracks declared types for every name
+     */
+    public Stack<HashMap<String, Type>> _types;
+
 
     // A new ScopeNode
     public ScopeNode() {
         _scopes = new Stack<>();
+        _types  = new Stack<>();
         _type = Type.BOTTOM;
     }
 
@@ -69,14 +77,15 @@ public class ScopeNode extends Node {
 
     @Override public Node idealize() { return null; }
 
-    public void push() { _scopes.push(new HashMap<>());  }
-    public void pop() { popN(_scopes.pop().size());  }
+    public void push() { _scopes.push(new HashMap<>());  _types.push(new HashMap<>()); }
+    public void pop() { popN(_scopes.pop().size()); _types.pop(); }
 
     /**
      * Create a new name in the current scope
      */
-    public Node define( String name, Node n ) {
+    public Node define( String name, Type declaredType, Node n ) {
         HashMap<String,Integer> syms = _scopes.lastElement();
+        _types.lastElement().put(name,declaredType);
         if( syms.put(name,nIns()) != null )
             return null;        // Double define
         return addDef(n);
@@ -97,7 +106,7 @@ public class ScopeNode extends Node {
     public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); }
     /**
      * Both recursive lookup and update.
-     *
+     * <p>
      * A shared implementation allows us to create lazy phis both during
      * lookups and updates; the lazy phi creation is part of chapter 8.
      *
@@ -120,12 +129,21 @@ public class ScopeNode extends Node {
                 // Set real Phi in the loop head
                 // The phi takes its one input (no backedge yet) from a recursive
                 // lookup, which might have insert a Phi in every loop nest.
-                : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole());
+                : loop.setDef(idx,new PhiNode(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole());
             setDef(idx,old);
         }
         return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer
     }
 
+    // Return declared type
+    public Type lookupDeclaredType( String name ) {
+        for( int i=_types.size(); i>0; i-- ) {
+            Type t = _types.get(i-1).get(name);
+            if( t != null ) return t;
+        }
+        return null;
+    }
+
     public Node ctrl() { return in(0); }
 
     /**
@@ -162,8 +180,10 @@ public class ScopeNode extends Node {
         // 3) Ensure that the order of defs is the same to allow easy merging
         for( HashMap<String,Integer> syms : _scopes )
             dup._scopes.push(new HashMap<>(syms));
+        for( HashMap<String,Type> ts : _types )
+            dup._types.push(ts); // Types don't change, just keep stacks aligned
 
-        dup.addDef(ctrl());      // Control input is just copied
+        dup.addDef(ctrl());     // Control input is just copied
         for( int i=1; i<nIns(); i++ )
             // For lazy phis on loops we use a sentinel
             // that will trigger phi creation on update
@@ -187,8 +207,9 @@ public class ScopeNode extends Node {
             if( in(i) != that.in(i) ) // No need for redundant Phis
                 // If we are in lazy phi mode we need to a lookup
                 // by name as it will trigger a phi creation
-                setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole());
+                setDef(i, new PhiNode(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole());
         that.kill();            // Kill merged scope
+        IterPeeps.add(r);
         return r.unkeep().peephole();
     }
 
@@ -216,11 +237,61 @@ public class ScopeNode extends Node {
                 IterPeeps.addAll(phi._outputs);
                 phi.moveDepsToWorklist();
                 if( in != phi ) {
-                    phi.subsume(in);
+                    if( !phi.iskeep() ) // Keeping phi around for parser elsewhere
+                        phi.subsume(in);
                     setDef(i,in); // Set the update back into Scope
                 }
             }
         }
 
     }
+
+
+    // Up-casting: using the results of an If to improve a value.
+    // E.g. "if( ptr ) ptr.field;" is legal because ptr is known not-null.
+
+    // This Scope looks for direct variable uses, or certain simple
+    // combinations, and replaces the variable with the upcast variant.
+    public Node upcast( Node ctrl, Node pred, boolean invert ) {
+        if( ctrl._type==Type.XCONTROL ) return null;
+        // Invert the If conditional
+        if( invert )
+            pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole());
+
+        // Direct use of a value as predicate.  This is a zero/null test.
+        if( Utils.find(_inputs, pred) != -1 ) {
+            if( !(pred._type instanceof TypeMemPtr tmp) )
+                // Must be an `int`, since int and ptr are the only two value types
+                // being tested. No representation for a generic not-null int, so no upcast.
+                return null;
+            if( tmp.isa(TypeMemPtr.VOIDPTR) )
+                return null;    // Already not-null, no reason to upcast
+            // Upcast the ptr to not-null ptr, and replace in scope
+            return replace(pred,new CastNode(TypeMemPtr.VOIDPTR,ctrl,pred).peephole());
+        }
+
+        if( pred instanceof NotNode not ) {
+            // Direct use of a !value as predicate.  This is a zero/null test.
+            if( Utils.find(_inputs, not.in(1)) != -1 ) {
+                Type tinit = not.in(1)._type.makeInit();
+                if( not.in(1)._type.isa(tinit) ) return null; // Already zero/null, no reason to upcast
+                return replace(not.in(1), new ConstantNode(tinit).peephole());
+            }
+        }
+        // Apr/9/2024: Attempted to replace X with Y if guarded by a test of
+        // X==Y.  This didn't seem to help very much, or at least in the test
+        // cases seen so far was a very minor help.
+
+        // No upcast
+        return null;
+    }
+
+    private Node replace( Node old, Node cast ) {
+        assert old!=null && old!=cast;
+        for( int i=0; i<nIns(); i++ )
+            if( in(i)==old )
+                setDef(i,cast);
+        return cast;
+    }
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index e399138b..4b7e02a8 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -1,25 +1,58 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeTuple;
-
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.*;
+import java.util.Arrays;
 import java.util.BitSet;
+import java.util.HashMap;
 
 /**
- * The Start node represents the start of the function.  For now, we do not
- * have any inputs to Start because our function does not yet accept
- * parameters.  When we add parameters the value of Start will be a tuple, and
- * will require Projections to extract the values.  We discuss this in detail
- * in Chapter 9: Functions and Calls.
+ * The Start node represents the start of the function.
+ *
+ * Start initially has 1 input (arg) from outside and the initial control.
+ * In ch10 we also add mem aliases as structs get defined; each field in struct
+ * adds a distinct alias to Start's tuple.
  */
 public class StartNode extends MultiNode {
 
-    final TypeTuple _args;
+    // This field is NOT final, because the tuple expands as we add memory aliases
+    TypeTuple _args;
+
+    // The alias number of the first field in the struct.
+    //
+    public final HashMap<String,Integer> _aliasStarts;
+
 
     public StartNode(Type[] args) {
         super();
         _args = TypeTuple.make(args);
         _type = _args;
+        _aliasStarts = new HashMap<>();
+    }
+
+    /**
+     * Creates a projection for each of the struct's fields, using the field alias
+     * as the key.
+     */
+    public void addMemProj( TypeStruct ts, ScopeNode scope) {
+        int len = _args._types.length;
+        _aliasStarts.put(ts._name,len);
+
+        // resize the tuple's type array to include all fields of the struct
+        int max = len + ts._fields.length;
+        Type[] args = Arrays.copyOf(_args._types, max);
+
+        // The new members of the tuple get a mem type with an alias
+        for( int alias = len; alias < max; alias++ )
+            args[alias] = TypeMem.make(alias);
+        _type = _args = TypeTuple.make(args);
+        // For each of the fields we now add a mem projection.  Note that the
+        // alias matches the slot of the field in the tuple
+        for( int alias = len; alias < max; alias++ ) {
+            String name = Parser.memName(alias);
+            Node n = new ProjNode(this, alias, name).peephole();
+            scope.define(name, args[alias], n);
+        }
     }
 
     @Override
@@ -40,7 +73,6 @@ public class StartNode extends MultiNode {
     public Node idealize() { return null; }
 
     // No immediate dominator, and idepth==0
-    @Override
-    Node idom() { return null; }
-
+    @Override int idepth() { return 0; }
+    @Override Node idom() { return null; }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 602feffc..3b5a7ce3 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -51,10 +51,17 @@ public class StopNode extends Node {
         return null;
     }
 
+    @Override public Node idom() { return null; }
+
     public Node addReturn(Node node) {
         return addDef(node);
     }
 
-    public StopNode iterate(            ) { return IterPeeps.iterate(this,false); }
-    public StopNode iterate(boolean show) { return IterPeeps.iterate(this,show ); }
+    public StopNode iterate(            ) { return IterPeeps.iterate(this,false).typeCheck(); }
+    public StopNode iterate(boolean show) { return IterPeeps.iterate(this,show ).typeCheck(); }
+    StopNode typeCheck() {
+        String err = walk( Node::err );
+        if( err != null ) throw new RuntimeException(err);
+        return this;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
new file mode 100644
index 00000000..8d264601
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -0,0 +1,70 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.type.*;
+
+import java.util.BitSet;
+
+/**
+ * Store represents setting a value to a memory based object, in chapter 10
+ * this means a field inside a struct.
+ */
+public class StoreNode extends MemOpNode {
+
+    /**
+     * @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 memSlice, Node memPtr, Node value) {
+        super(name, alias, memSlice, memPtr, value);
+    }
+
+    @Override
+    public String label() { return "Store"; }
+    @Override
+    public String glabel() { return "."+_name+" ="; }
+    @Override
+    public boolean isMem() { return true; }
+    public Node val() { return in(3); }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        return sb.append(".").append(_name).append("=").append( val()).append(";");
+    }
+
+    @Override
+    public Type compute() { return TypeMem.make(_alias); }
+
+    @Override
+    public Node idealize() {
+
+        // Simple store-after-store on same address.  Should pick up the
+        // required init-store being stomped by a first user store.
+        if( mem() instanceof StoreNode st &&
+            ptr()==st.ptr() &&  // Must check same object
+            ptr()._type instanceof TypeMemPtr && // No bother if weird dead pointers
+            // Must have exactly one use of "this" or you get weird
+            // non-serializable memory effects in the worse case.
+            st.checkNoUseBeyond(this) ) {
+            assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect
+            setDef(1,st.mem());
+            return this;
+        }
+
+        return null;
+    }
+
+    // Check that `this` has no uses beyond `that`
+    private boolean checkNoUseBeyond(Node that) {
+        if( nOuts()==1 ) return true;
+        // Add deps on the other uses (can be e.g. ScopeNode mid-parse) so that
+        // when the other uses go away we can retry.
+        for( Node use : _outputs )
+            if( use != that )
+                use.addDep(that);
+        return false;
+    }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index f661be14..b87115cd 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -35,6 +35,14 @@ 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));
+
+        // (-x) - y is -(x+y)
+        if( in(1) instanceof MinusNode minus )
+            return new MinusNode(new AddNode(minus.in(1),in(2)).peephole());
+
         return null;
     }