Bring forward the lazy mem alias

Integrate with ch15 NewNode creating aliases

14 files changed, 526 insertions, 128 deletions

diff --git a/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index a270f026..78a0dcde 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -149,7 +149,7 @@ public abstract class GlobalCodeMotion {
                 // 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 )
+                        if( antiUse(ld,memuse) && late[memuse._nid]==null )
                             continue outer;
 
                 // All uses done, schedule
@@ -219,6 +219,17 @@ public abstract class GlobalCodeMotion {
             best instanceof IfNode;
     }
 
+    // Only a store or memory Phi covering this alias can constrain a load.
+    // MemMerge packages slices without overwriting them.
+    private static boolean antiUse(LoadNode load, Node use) {
+        return switch( use ) {
+        case StoreNode st -> st._alias==load._alias;
+        case MemPhiNode phi -> phi._alias==load._alias;
+        case BulkMemPhiNode phi -> !phi.isSplit(load._alias);
+        default -> false;
+        };
+    }
+
     private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late, int[] anti) {
         // We could skip final-field loads here.
         // Walk LCA->early, flagging Load's block location choices
@@ -226,6 +237,7 @@ public abstract class GlobalCodeMotion {
             anti[cfg._nid] = load._nid;
         // Walk load->mem uses, looking for Stores causing an anti-dep
         for( Node mem : load.mem()._outputs ) {
+            if( !antiUse(load,mem) ) continue;
             switch( mem ) {
             case StoreNode st:
                 assert late[st._nid]!=null;
@@ -238,9 +250,6 @@ public abstract class GlobalCodeMotion {
                     if( phi.in(i)==load.mem() )
                         lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti);
                 break;
-            case LoadNode ld: break; // Loads do not cause anti-deps on other loads
-            case ReturnNode ret: break; // Load must already be ahead of Return
-            case NeverNode never: break;
             default: throw Utils.TODO();
             }
         }
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/Parser.java b/chapter14/src/main/java/com/seaofnodes/simple/Parser.java
index 34fac183..bce192c2 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/Parser.java
@@ -36,6 +36,10 @@ public class Parser {
 
     public StopNode STOP;
 
+    // Field identities are independent of the memory graph and Start's tuple.
+    private final HashMap<String,Integer> _aliases = new HashMap<>();
+    private int _alias = 2;
+
     // Debugger Printing.
     public static boolean SCHEDULED; // True if debug printer can use schedule info
 
@@ -123,7 +127,7 @@ public class Parser {
         _lexer = new Lexer(source);
         _scope = new ScopeNode();
         _continueScope = _breakScope = null;
-        START = new StartNode(new Type[]{ Type.CONTROL, arg });
+        START = new StartNode(new Type[]{ Type.CONTROL, TypeMem.BOT, arg });
         STOP = new StopNode(source);
         ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep();
         XCTRL= new XCtrlNode().peephole().keep();
@@ -150,7 +154,8 @@ public class Parser {
         // Enter a new scope for the initial control and arguments
         _scope.push();
         _scope.define(ScopeNode.CTRL, Type.CONTROL   , new CProjNode(START, 0, ScopeNode.CTRL).peephole());
-        _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new  ProjNode(START, 1, ScopeNode.ARG0).peephole());
+        _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new  ProjNode(START, 2, ScopeNode.ARG0).peephole());
+        _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole());
         parseBlock();
         if( ctrl()._type==Type.CONTROL )
             STOP.addReturn(new ReturnNode(ctrl(), new ConstantNode(TypeInteger.constant(0)).peephole(), _scope).peephole());
@@ -238,8 +243,9 @@ public class Parser {
         require("}");
         // Build and install the TypeStruct
         TypeStruct ts = TypeStruct.make(typeName, fields);
-        TYPES.put(typeName, ts);
-        START.addMemProj(ts, _scope); // Insert memory edges
+        TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names
+        _aliases.put(typeName,_alias);
+        _alias += ts._fields.length;
         return parseStatement();
     }
 
@@ -666,21 +672,24 @@ public class Parser {
      */
     private Node newStruct(TypeStruct obj) {
         Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep();
-        int alias = START._aliasStarts.get(obj._name);
+        int alias = _aliases.get(obj._name);
         for( Field field : obj._fields ) {
-            memAlias(alias, new StoreNode(field._fname, alias, field._type, ctrl(), memAlias(alias), n, new ConstantNode(field._type.makeInit()).peephole(),true).peephole());
+            store(field._fname,alias,field._type,n,new ConstantNode(field._type.makeInit()).peephole(),true);
             alias++;
         }
         return n.unkeep();
     }
 
-    // We set up memory aliases by inserting special vars in the scope these
-    // variables are prefixed by $ so they cannot be referenced in Simple code.
-    // Using vars has the benefit that all the existing machinery of scoping
-    // and phis work as expected
-    private Node memAlias(int alias         ) { return _scope.lookup(memName(alias)    ); }
-    private Node memAlias(int alias, Node st) { return _scope.update(memName(alias), st); }
-    public static String memName(int alias) { return ("$"+alias).intern(); }
+    // Memory is one hidden SSA variable, including across branches and loops.
+    private Node mem() { return _scope.lookup("$mem"); }
+    private Node mem(Node n) { return _scope.update("$mem",n); }
+
+    private void store(String name, int alias, Type glb, Node ptr, Node val, boolean init) {
+        Node prior = mem().keep();
+        Node st = new StoreNode(name,alias,glb,ctrl(),prior,ptr,val,init).peephole();
+        mem(new MemMergeNode(prior,alias,st).peephole());
+        prior.unkeep();
+    }
 
     /**
      * Parse postfix expression. For now this is just a field
@@ -702,7 +711,7 @@ public class Parser {
         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;
+        int alias = _aliases.get(ptr._obj._name)+idx;
 
         if( match("=") ) {
             // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment
@@ -712,13 +721,13 @@ public class Parser {
                 Type glb = base._fields[idx]._type;
                 // Auto-truncate when storing to narrow fields
                 val = zsMask(val,glb);
-                memAlias(alias, new StoreNode(name, alias,glb, ctrl(), memAlias(alias), expr, val, false).peephole());
+                store(name,alias,glb,expr,val,false);
                 return expr;        // "obj.a = expr" returns the expression while updating memory
             }
         }
 
         Type declaredType = base._fields[idx]._type;
-        return parsePostfix(new LoadNode(name, alias, declaredType.glb(), memAlias(alias), expr).peephole());
+        return parsePostfix(new LoadNode(name, alias, declaredType.glb(), mem(), expr).peephole());
     }
 
     // zero/sign extend.  "i" is limited to either classic unsigned (min==0) or
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
new file mode 100644
index 00000000..8d512f21
--- /dev/null
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
@@ -0,0 +1,237 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMem;
+import java.util.BitSet;
+
+/**
+ * A Phi for bulk memory.  It covers all aliases except {@link #_aliases};
+ * those aliases must be represented by parallel precise MemPhis at the same
+ * program slice.
+ */
+public class BulkMemPhiNode extends PhiNode {
+
+    private static final BitSet EMPTY = new BitSet();
+
+    // Excluded Aliases; empty means NO exclusions.
+    // Each split clones the exclusions; published sets are never mutated.
+    public final BitSet _aliases;
+
+    public BulkMemPhiNode(String label, Node... inputs) {
+        this(label,EMPTY,inputs);
+    }
+
+    private BulkMemPhiNode(String label, BitSet aliases, Node... inputs) {
+        super(label,TypeMem.BOT,inputs);
+        _aliases = aliases;
+    }
+
+    public boolean isSplit(int alias) { return _aliases.get(alias); }
+
+    @Override public String label() { return "BulkPhi"+_aliases; }
+
+    @Override
+    public Type compute() {
+        Type t = super.compute();
+        return t instanceof TypeMem mem ? mem :
+            t==Type.BOTTOM ? TypeMem.BOT :
+            TypeMem.TOP;
+    }
+
+    @Override
+    public Node idealize() {
+        Node progress = super.idealize();
+        if( progress != null ) return progress;
+        if( ((RegionNode)region()).inProgress() || region().nIns()<=1 )
+            return null;        // Input is in-progress
+
+        // "Peek through" a MemMerge that covers this alias set on its default
+        for( int i=1; i<nIns(); i++ )
+            if( in(i) instanceof MemMergeNode mmm && canPeek(mmm) ) {
+                setDef(i,IterPeeps.add(mmm.in(1)));
+                return this;
+            }
+
+        // If any input or output uses or defines a specific alias we cover,
+        // make a private MemPhi for it, and add it to the excluded list.
+        for( int i=1; i<nIns(); i++ ) {
+            int alias = inputAlias(in(i));
+            if( alias!=0 )
+                return slice(alias);
+        }
+
+        for( int i=0; i<_outputs.size(); i++ ) {
+            int alias = outputAlias(_outputs.get(i));
+            if( alias!=0 )
+                return slice(alias);
+        }
+
+        return null;
+    }
+
+    static public boolean checkMem(Node n, int alias) {
+        for( Node m : n._inputs )
+            // Bulk memory supplies this alias
+            if( m instanceof BulkMemPhiNode bulk ) {
+                if( bulk._aliases.get(alias) )
+                    return false;
+            } else if( m instanceof MemMergeNode mmm &&
+                       mmm.in(1) instanceof BulkMemPhiNode bulk &&
+                       bulk._aliases.get(alias) &&
+                       (alias >= mmm.nIns() || mmm.in(alias)==null) )
+                return false;
+        return true;
+    }
+
+
+    // True if the MemMerge has no precise slice still covered by this Phi.
+    private boolean canPeek(MemMergeNode mmm) {
+        return missingAlias(mmm,false)==0;
+    }
+
+    // Return an alias required by an input but still covered by this Phi, or 0.
+    private int inputAlias(Node n) {
+        return switch(n) {
+        case ProjNode proj -> 0;
+        case ConstantNode con -> 0;
+        case MemMergeNode mmm -> missingAlias(mmm,false);
+        case MemOpNode mem -> unsplit(mem._alias);
+        case BulkMemPhiNode bulk -> missingAlias(bulk);
+        default -> throw new AssertionError("Unexpected memory input "+n);
+        };
+    }
+
+    // Return an alias required by a user but still covered by this Phi, or 0.
+    private int outputAlias(Node use) {
+        // This decision depends backwards on an immediate user's alias/set.
+        // Normal graph-neighbor enqueueing flows from defs to uses, so retain
+        // an explicit forward dependency to revisit this Phi when the user
+        // sharpens.
+        use.addDepForwards(this);
+        return switch(use) {
+        case ScopeNode scope -> 0;
+        case MemMergeNode mmm -> missingAlias(mmm,true);
+        case BulkMemPhiNode bulk -> missingAlias(bulk);
+        case MemOpNode mem -> unsplit(mem._alias);
+        case MemPhiNode phi -> unsplit(phi._alias);
+        default -> {
+            assert use instanceof ReturnNode
+                : "Unexpected bulk-memory user "+use;
+            yield 0;
+        }
+        };
+    }
+
+    // Alias zero/one is bulk, and an already excluded precise alias cannot
+    // trigger another split of this Phi.
+    private int unsplit(int alias) {
+        if( alias <= 1 ) return 0;
+        assert !_aliases.get(alias);
+        return alias;
+    }
+
+    // First alias excluded by the neighboring bulk Phi but not by this one.
+    private int missingAlias(BulkMemPhiNode bulk) {
+        for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) )
+            if( !_aliases.get(alias) )
+                return alias;
+        return 0;
+    }
+
+    // First precise MemMerge slice still covered by this Phi.  When inspecting
+    // a user, ignore slots which point back to this Phi.
+    private int missingAlias(MemMergeNode mmm, boolean user) {
+        for( int alias=2; alias<mmm.nIns(); alias++ )
+            if( mmm.in(alias)!=null &&
+                mmm.alias(alias)!=mmm.in(1) &&
+                !_aliases.get(alias) )
+                { assert (!user || mmm.in(alias)!=this); return alias; }
+        return 0;
+    }
+
+    // Slice out given alias
+    private MemMergeNode slice( int alias ) {
+        assert !_aliases.get(alias);
+        // Inputs are the same; MemPhi will sharpen his own inputs.  If a
+        // parallel precise Phi already exists, reuse it instead of building a
+        // duplicate for the same Region/alias pair.
+        Node mem = precisePhi(alias);
+
+        BitSet aliases = ((BitSet)_aliases.clone());
+        aliases.set(alias);
+        BulkMemPhiNode bphi = new BulkMemPhiNode(_label,aliases);
+        for( int i=0; i<nIns(); i++ )
+            bphi.addDef(in(i));
+        // Installing bphi creates a new bulk user with a different exclusion
+        // set.  Queue the original memory inputs before bphi itself can peep
+        // away and hide those neighbor relationships.
+        for( int i=1; i<bphi.nIns(); i++ )
+            IterPeeps.add(bphi.in(i));
+        // Do not peephole bphi here, as BulkMemPhi can recursively start a
+        // second bulk rewrite before this one has finished.  Let the worklist
+        // discover any further splits
+        bphi.setType(TypeMem.BOT);
+        Node bulk = bphi;
+        IterPeeps.add(bulk);
+        IterPeeps.add(mem);
+        return aggregate(bulk,alias,mem);
+    }
+
+    // Build aggregate memory over a bulk Phi, preserving every precise slice
+    // which the bulk has already excluded.  The named alias is newly supplied
+    // (or replaces its old slice).
+    MemMergeNode aggregate(Node bulk, int alias, Node precise) {
+        MemMergeNode mmm = new MemMergeNode(bulk);
+        for( int old = _aliases.nextSetBit(0); old >= 0; old = _aliases.nextSetBit(old+1) )
+            { assert old != alias; mmm.alias(old,precisePhi(old));}
+        mmm.alias(alias,precise);
+        assert checkMerge(mmm);
+        return mmm;
+    }
+
+    // Find or make the precise Phi parallel to this bulk Phi at the same merge.
+    private Node precisePhi(int alias) {
+        MemPhiNode mphi = _findPhi(alias);
+        if( mphi!=null ) return mphi;
+
+        mphi = new MemPhiNode("$"+alias,alias);
+        mphi.addDef(region());
+        // Due to cycles, must set before calling peephole
+        mphi.setType(TypeMem.make(alias));
+        for( int i=1; i<nIns(); i++ )
+            mphi.addDef(IterPeeps.add(preciseInput(in(i),alias)));
+        return IterPeeps.add(mphi);
+    }
+
+    MemPhiNode _findPhi(int alias) {
+        for( Node use : region()._outputs )
+            if( use instanceof MemPhiNode mphi && mphi._alias==alias )
+                return mphi;
+        return null;
+    }
+
+    // Select an alias already split out of a predecessor's bulk memory.
+    private Node preciseInput(Node mem, int alias) {
+        if( mem instanceof MemMergeNode mmm )
+            return mmm.alias(alias);
+        if( mem instanceof BulkMemPhiNode bulk && bulk.isSplit(alias) )
+            return bulk.precisePhi(alias);
+        return mem;
+    }
+
+    // Every alias excluded by a bulk default must be supplied explicitly.
+    static boolean checkMerge(MemMergeNode mmm) {
+        if( !(mmm.in(1) instanceof BulkMemPhiNode bulk) ) return true;
+        for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) )
+            if( alias >= mmm.nIns() || mmm.in(alias)==null )
+                return false;
+        return true;
+    }
+
+    @Override public boolean eq(Node n) {
+        return _aliases.equals(((BulkMemPhiNode)n)._aliases) && super.eq(n);
+    }
+
+    @Override int hash() { return _aliases.hashCode(); }
+}
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 2db5e469..5cd39a33 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.type.Type;
 
 import java.util.BitSet;
@@ -22,6 +23,24 @@ public class LoadNode extends MemOpNode {
         super(name, alias, glb, null, memSlice, memPtr);
     }
 
+    @Override boolean canDrop(MemOpNode other, Node dep) {
+        return super.canDrop(other,dep) && !clobbered(dep);
+    }
+
+    // Check only immediate memory users. Stores clobber memory; Phis and
+    // aggregates might lead to a clobber, so stop rather than search further.
+    private boolean clobbered(Node dep) {
+        Node mem = mem();
+        mem.addDepForwards(dep);
+        for( Node use : mem._outputs ) {
+            if( use==null ) continue;
+            use.addDepForwards(dep);
+            if( use instanceof StoreNode || use instanceof PhiNode ||
+                use instanceof MemMergeNode ) return true;
+        }
+        return false;
+    }
+
     @Override public String  label() { return     _name; }
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); }
@@ -33,10 +52,15 @@ public class LoadNode extends MemOpNode {
 
     @Override
     public Node idealize() {
+        if( mem() instanceof MemMergeNode merge ) {
+            setDef(1,IterPeeps.add(merge.alias(_alias)));
+            return this;
+        }
+
 
         // Simple Load-after-Store on same address.
         if( mem() instanceof StoreNode st &&
-            ptr() == st.ptr() ) { // Must check same object
+            ptr() == st.ptr() && _alias==st._alias ) { // Must check same object
             assert _name.equals(st._name); // Equiv class aliasing is perfect
             return st.val();
         }
@@ -48,7 +72,7 @@ public class LoadNode extends MemOpNode {
         //   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 ) {
+        if( mem() instanceof MemPhiNode 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.
@@ -69,7 +93,7 @@ public class LoadNode extends MemOpNode {
     // 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();
+        return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _alias==st1._alias;
     }
 
     Node copy(Node mem, Node ptr) {
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
new file mode 100644
index 00000000..d7fed402
--- /dev/null
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
@@ -0,0 +1,60 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMem;
+import java.util.BitSet;
+
+/** All memory: a default slice and explicit overrides for individual aliases. */
+public class MemMergeNode extends Node {
+    public MemMergeNode(Node bulk) { super(null,bulk); _type = TypeMem.BOT; }
+    public MemMergeNode(Node bulk, int alias, Node precise) {
+        this(bulk);
+        alias(alias,precise);
+    }
+
+    public Node alias(int alias) {
+        Node n = alias < nIns() ? in(alias) : null;
+        assert n!=null || !(in(1) instanceof BulkMemPhiNode bulk) || !bulk.isSplit(alias);
+        return n==null ? in(1) : n;
+    }
+
+    public void alias(int alias, Node mem) {
+        assert alias > 1;
+        while( nIns()<=alias ) addDef(null);
+        setDef(alias,mem);
+    }
+
+    @Override public String label() { return "MemMerge"; }
+    @Override public boolean isMem() { return true; }
+    @Override public Type compute() { return TypeMem.BOT; }
+    @Override StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        sb.append("MEM[");
+        for( int i=1; i<nIns(); i++ )
+            if( in(i)!=null ) {
+                sb.append(i==1 ? "default:" : i+":");
+                in(i)._print0(sb,visited).append(" ");
+            }
+        return sb.append("]");
+    }
+
+    @Override public Node idealize() {
+        boolean progress=false, allDefault=true;
+        for( int i=2; i<nIns(); i++ ) {
+            if( in(i)==in(1) ) { setDef(i,null); progress=true; }
+            if( in(i)!=null ) allDefault=false;
+        }
+        if( allDefault ) return in(1);
+
+        if( in(1) instanceof MemMergeNode mem ) {
+            for( int i=2; i<mem.nIns(); i++ )
+                if( mem.in(i)!=null && (i>=nIns() || in(i)==null) )
+                    alias(i,mem.in(i));
+            IterPeeps.add(mem.in(1));
+            setDef(1,mem.in(1));
+            return this;
+        }
+        assert BulkMemPhiNode.checkMerge(this);
+        return progress ? this : null;
+    }
+}
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index 76564db0..29d302cb 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -24,6 +24,13 @@ public abstract class MemOpNode extends Node {
     public Node mem() { return in(1); }
     public Node ptr() { return in(2); }
 
+    // Extra conditions for factoring matching memory operations through a Phi.
+    // The caller has already checked the opcode, input shape and control.
+    boolean canDrop(MemOpNode other, Node dep) {
+        ptr().addDep(dep);
+        return _alias==other._alias && _declaredType==other._declaredType && err()==null;
+    }
+
     @Override
     boolean eq(Node n) {
         MemOpNode mem = (MemOpNode)n; // Invariant
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java
new file mode 100644
index 00000000..c806bede
--- /dev/null
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java
@@ -0,0 +1,36 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMem;
+
+/** A Phi for one field alias, parallel to a bulk Phi at the same Region. */
+public class MemPhiNode extends PhiNode {
+    public final int _alias;
+
+    public MemPhiNode(String label, int alias, Node... inputs) {
+        super(label,TypeMem.make(alias),inputs);
+        assert alias > 1;
+        _alias = alias;
+    }
+
+    @Override public String label() { return "MemPhi_"+_alias; }
+
+    @Override public Type compute() {
+        assert BulkMemPhiNode.checkMem(this,_alias);
+        Type t = super.compute();
+        return t==Type.TOP || t==TypeMem.TOP ? TypeMem.TOP : TypeMem.make(_alias);
+    }
+
+    @Override public Node idealize() {
+        for( int i=1; i<nIns(); i++ )
+            if( in(i) instanceof MemMergeNode mem ) {
+                setDef(i,IterPeeps.add(mem.alias(_alias)));
+                return this;
+            }
+        return super.idealize();
+    }
+
+    @Override boolean eq(Node n) { return _alias==((MemPhiNode)n)._alias && super.eq(n); }
+    @Override int hash() { return _alias; }
+}
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java
index af59cb0d..469badc4 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -16,14 +16,14 @@ import java.util.function.Function;
  * The Node class provides common functionality used by all subtypes.
  * Subtypes of Node specialize by overriding methods.
  */
-public abstract class Node implements OutNode {
+public abstract class Node implements OutNode, Cloneable {
 
     /**
      * Each node has a unique dense Node ID within a compilation context
      * The ID is useful for debugging, for using as an offset in a bitvector,
      * as well as for computing equality of nodes (to be implemented later).
      */
-    public final int _nid;
+    public int _nid;
 
     /**
      * Inputs to the node. These are use-def references to Nodes.
@@ -32,7 +32,7 @@ public abstract class Node implements OutNode {
      * Ordering is required because e.g. "a/b" is different from "b/a".
      * The first input (offset 0) is often a {@link #isCFG} node.
      */
-    public final ArrayList<Node> _inputs;
+    public ArrayList<Node> _inputs;
 
     /**
      * Outputs reference Nodes that are not null and have this Node as an
@@ -43,7 +43,7 @@ public abstract class Node implements OutNode {
      * walked in either direction.  These outputs are typically used for
      * efficient optimizations but otherwise have no semantics meaning.
      */
-    public final ArrayList<Node> _outputs;
+    public ArrayList<Node> _outputs;
 
 
     /**
@@ -208,6 +208,7 @@ public abstract class Node implements OutNode {
     // Error is 'use' does not exist; ok for 'use' to be null.
     protected boolean delUse( Node use ) {
         Utils.del(_outputs, Utils.find(_outputs, use));
+        moveDepsToWorklist(); // User-count and anti-dependence queries can now change.
         return _outputs.isEmpty();
     }
 
@@ -449,6 +450,14 @@ public abstract class Node implements OutNode {
      * being added must benefit from this node being peepholed.
      */
     Node addDep( Node dep ) {
+        return addDep(dep,false);
+    }
+
+    // A bulk Phi inspects its users' partitions. Def-to-use propagation does
+    // not revisit that producer when an immediate user's partition changes.
+    Node addDepForwards(Node dep) { return addDep(dep,true); }
+
+    private Node addDep(Node dep, boolean forwards) {
         // Running peepholes during the big assert cannot have side effects
         // like adding dependencies.
         if( IterPeeps.midAssert() ) return this;
@@ -456,8 +465,8 @@ public abstract class Node implements OutNode {
         if( obs != null ) obs.dep(this, dep);
         if( _deps==null ) _deps = new ArrayList<>();
         if( Utils.find(_deps  ,dep) != -1 ) return this; // Already on list
-        if( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors
-        if( Utils.find(_outputs,dep)!= -1 ) return this;
+        if( !forwards && Utils.find(_inputs,dep) != -1 ) return this;
+        if( !forwards && Utils.find(_outputs,dep)!= -1 ) return this;
         _deps.add(dep);
         return this;
     }
@@ -589,6 +598,20 @@ public abstract class Node implements OutNode {
     // Does not need to be implemented in isCFG() nodes.
     Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); }
 
+    // Exact-class copy preserving operation attributes, with fresh identity
+    // and no edges, dependencies, or GVN membership.
+    public final Node copyEmpty() {
+        Node n;
+        try { n = (Node)clone(); }
+        catch( CloneNotSupportedException e ) { throw new AssertionError(e); }
+        n._nid = UNIQUE_ID++;
+        n._inputs = new ArrayList<>();
+        n._outputs = new ArrayList<>();
+        n._deps = null;
+        n._hash = 0;
+        return n;
+    }
+
     // Report any post-optimize errors
     String err() { return null; }
 
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 1d4b3fba..0f8b06f5 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -16,6 +16,10 @@ public class PhiNode extends Node {
 
     public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label;  assert declaredType!=null; _declaredType = declaredType; }
 
+    public static PhiNode make(String label, Type type, Node... inputs) {
+        return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,type,inputs);
+    }
+
     @Override public String label() { return "Phi_"+_label; }
 
     @Override
@@ -65,30 +69,9 @@ public class PhiNode extends Node {
         if (live != null)
             return live;
 
-        // Pull "down" a common data op.  One less op in the world.  One more
-        // Phi, but Phis do not make code.
-        //   Phi(op(A,B),op(Q,R),op(X,Y)) becomes
-        //     op(Phi(A,Q,X), Phi(B,R,Y)).
-        Node op = in(1);
-        if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) {
-            Node[] lhss = new Node[nIns()];
-            Node[] rhss = new Node[nIns()];
-            lhss[0] = rhss[0] = in(0); // Set Region
-            for( int i=1; i<nIns(); i++ ) {
-                lhss[i] = in(i).in(1);
-                rhss[i] = in(i).in(2);
-            }
-            Node phi_lhs = new PhiNode(_label, in(1).in(1)._type.glb(),lhss).peephole();
-            Node phi_rhs = new PhiNode(_label, in(1).in(2)._type.glb(),rhss).peephole();
-            Node phi_op = op.copy(phi_lhs,phi_rhs);
-            phi_op.setType(phi_op.compute());
-            // If losing precision, don't do it
-            if( !phi_op._type.isa(_type) ) {
-                phi_op.kill();
-                return null;
-            }
-            return phi_op;
-        }
+        // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...).
+        Node down;
+        if( same_op() && (down=drop_same_op())!=null ) return down;
 
         // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove.
         if( nIns()==3 ) {
@@ -118,16 +101,72 @@ public class PhiNode extends Node {
     }
 
     private boolean same_op() {
-        for( int i=2; i<nIns(); i++ ) {
-            if( in(1).getClass() != in(i).getClass() )   return false;
-            if( in(1).in(1)._type.glb() != in(i).in(1)._type.glb() ) return false;
-            if( in(1).in(2)._type.glb() != in(i).in(2)._type.glb() ) return false;
+        Node op = in(1);
+        if( op.isCFG() || op instanceof ConstantNode || op instanceof PhiNode ||
+            op instanceof ProjNode || op instanceof NewNode || op instanceof ScopeNode || op instanceof MemMergeNode ) return false;
+        // A bulk Phi must split its aliases before factoring precise Stores.
+        if( this instanceof BulkMemPhiNode ) return false;
+        // Bulk splitting currently identifies parallel slices by Region/alias.
+        // Factoring can introduce another slice at a different memory point;
+        // wait until that Region's bulk partitioning has finished.
+        if( op instanceof MemOpNode )
+            for( Node use : region()._outputs )
+                if( use instanceof BulkMemPhiNode ) {
+                    use.addDepForwards(this);
+                    return false;
+                }
+        Node busy = null;
+        for( int i=1; i<nIns(); i++ ) {
+            Node n = in(i);
+            if( region().in(i).addDep(this)._type==Type.XCONTROL ||
+                op.getClass()!=n.getClass() || n.nIns()!=op.nIns() || n.in(0)!=null || !op.eq(n) ) return false;
+            if( n instanceof MemOpNode mem && !mem.canDrop((MemOpNode)op,this) ) return false;
+            // Moving a Store must remove the old effect, not duplicate it.
+            // Allow one shared arm: the other arms disappear into the single
+            // factored operation, usually reducing the total operation count.
+            n.addDepForwards(this);
+            if( n.nOuts()>1 ) {
+                for( Node use : n._outputs )
+                    if( use!=null && use!=this ) use.addDepForwards(this);
+                if( n instanceof StoreNode || busy!=null ) return false;
+                busy=n;
+            }
+            for( int j=1; j<n.nIns(); j++ )
+                if( n.in(j) instanceof ScopeNode || ((n.in(j)==null) != (op.in(j)==null)) ) return false;
         }
-        // Load merging needs an anti-dep check.
-        if( in(1) instanceof MemOpNode ) return false;
         return true;
     }
 
+    private Node drop_same_op() {
+        Node op = in(1), cp = op.copyEmpty();
+        cp._type = null;
+        cp.addDef(null);
+        for( int j=1; j<op.nIns(); j++ ) {
+            Node x = op.in(j);
+            boolean different = false;
+            for( int i=2; i<nIns(); i++ )
+                if( in(i).in(j)!=x ) different=true;
+            if( different ) {
+                Node[] ins = new Node[nIns()];
+                ins[0] = region();
+                Type t = Type.TOP;
+                for( int i=1; i<nIns(); i++ ) {
+                    ins[i] = in(i).in(j);
+                    t = t.meet(ins[i]._type);
+                }
+                PhiNode phi = j==1 && op instanceof MemOpNode mem
+                    ? new MemPhiNode(_label,mem._alias,ins)
+                    : PhiNode.make(_label,t.glb(),ins);
+                x = phi.peephole();
+            }
+            cp.addDef(x);
+        }
+        // Factoring must not widen the result (e.g. correlated And operands).
+        if( cp.compute().isa(compute()) ) return cp;
+        cp.kill();
+        return null;
+    }
+
     /**
      * If only single unique input, return it
      */
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index fb934511..d7e934d7 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -68,7 +68,7 @@ public class RegionNode extends CFGNode {
         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.addDepForwards(this).in(0)==p2.addDepForwards(this).in(0) &&
             p1.in(0) instanceof IfNode iff )
             return iff.ctrl();
 
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 444b76a8..725c704f 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -4,32 +4,17 @@ import com.seaofnodes.simple.type.*;
 
 import java.util.BitSet;
 
-/**
- * The Return node has two inputs.  The first input is a control node and the
- * second is the data node that supplies the return value.
- * <p>
- * In this presentation, Return functions as a Stop node, since multiple <code>return</code> statements are not possible.
- * The Stop node will be introduced in Chapter 6 when we implement <code>if</code> statements.
- * <p>
- * The Return's output is the value from the data node.
- */
+/** Keeps all preceding memory effects and the return value alive: {ctrl, $mem, value}. */
 public class ReturnNode extends CFGNode {
 
     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
-        if( scope != null ) {
-            String[] names = scope.reverseNames();
-            for (String name: names) {
-                if (!name.equals("$ctrl") && name.startsWith("$"))
-                    addDef(scope.lookup(name));
-            }
-        }
+        // A synthetic never-taken loop exit has no source scope.
+        super(ctrl, scope == null ? null : scope.lookup("$mem"), data);
     }
 
     public Node ctrl() { return in(0); }
-    public Node expr() { return in(1); }
+    public Node mem () { return in(1); }
+    public Node expr() { return in(2); }
 
     @Override
     public String label() { return "Return"; }
@@ -43,7 +28,8 @@ public class ReturnNode extends CFGNode {
 
     @Override
     public Type compute() {
-        return TypeTuple.make(ctrl()._type,expr()._type);
+        // Return exposes the complete memory state.
+        return TypeTuple.make(ctrl()._type,TypeMem.BOT,expr()._type);
     }
 
     @Override
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 455f4b3a..b931e862 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -129,7 +129,7 @@ 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, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole());
+                : loop.setDef(idx,PhiNode.make(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
@@ -207,7 +207,7 @@ 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], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole());
+                setDef(i, PhiNode.make(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();
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 5f205ffd..2cedf0f6 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -1,59 +1,17 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.*;
-import java.util.Arrays;
 import java.util.BitSet;
-import java.util.HashMap;
 import java.util.HashSet;
 
-/**
- * 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.
- */
+/** Start supplies control, whole memory, and the argument, in that order. */
 public class StartNode extends CFGNode implements MultiNode {
 
-    // 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;
-
+    private final TypeTuple _args;
 
     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
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index 142aebc3..031240ce 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.type.*;
 
 import java.util.BitSet;
@@ -24,6 +25,10 @@ public class StoreNode extends MemOpNode {
         _init = init;
     }
 
+    @Override boolean canDrop(MemOpNode other, Node dep) {
+        return super.canDrop(other,dep) && _init==((StoreNode)other)._init;
+    }
+
     @Override public String  label() { return "." +_name+"="; }
     @Override public boolean isMem() { return true; }
 
@@ -39,11 +44,16 @@ public class StoreNode extends MemOpNode {
 
     @Override
     public Node idealize() {
+        if( mem() instanceof MemMergeNode merge ) {
+            setDef(1,IterPeeps.add(merge.alias(_alias)));
+            return this;
+        }
+
 
         // 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()==st.ptr() && _alias==st._alias &&  // 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.