Bring forward the lazy mem alias

Integrate with ch15 NewNode creating aliases

7 files changed, 189 insertions, 30 deletions

diff --git a/chapter10b/README.md b/chapter10b/README.md
index c033a850..dfdf74d5 100644
--- a/chapter10b/README.md
+++ b/chapter10b/README.md
@@ -123,8 +123,17 @@ not to an expanded type lattice. As in Chapter 10a, diagram edges show lattice
 order, with top above bottom; field and tuple-element type lattices are elided.
 
 Scalar Phis remain ordinary PhiNodes. The scope's Phi factory chooses a
-BulkMemPhi for whole memory; splitting constructs MemPhis explicitly. Generic
-arithmetic factoring through Phis must not factor a memory aggregate.
+BulkMemPhi for whole memory; splitting constructs MemPhis explicitly. Phi
+factoring can combine matching Loads or Stores as in Chapter 10a, but cannot
+factor MemMerge or BulkMemPhi. Its new memory operands use precise MemPhis for
+the operation's alias. Load safety checks only immediate memory users, rejecting
+Stores, Phis, and MemMerges. A Phi or aggregate might lead to a later write;
+we conservatively skip the rewrite instead of searching farther to save one Load.
+
+Factoring waits while a BulkMemPhi remains at the same Region. Bulk splitting
+identifies parallel slices by Region and alias, whereas factoring a Store can
+introduce a memory Phi *before* the Store at that same Region. Waiting avoids
+mistaking that earlier memory for the aggregate's completed slice.
 
 Memory splitting can increase node count. Progress comes from extracting an
 alias from a bulk Phi and simplifying its precise chain, rather than from
@@ -137,7 +146,9 @@ This also extends the worklist lesson from Chapter 9. A bulk Phi inspects its
 users, so changes to a user's partition must wake the producer. Selecting a
 slice from an aggregate can expose a new bulk-Phi user; that selected definition
 must be queued too. The optimizer's worklist completeness assertion remains
-enabled and checks these dependencies.
+enabled and checks these dependencies. Factoring also depends on user counts:
+removing a use wakes recorded dependents even when the definition's type stays
+unchanged.
 
 ## Evaluation and ordering
 
@@ -160,8 +171,9 @@ alias to become known later, using the same representation. Its private
 constructor memory, escape tracking, incomplete types, and module alias
 remapping are separate extensions and are not needed here.
 
-Chapter 11 schedules this representation, including alias-specific load/store
-anti-dependencies. Chapters 12-24 currently retain their older parser-managed
+Chapters 11-15 use this representation, including alias-specific load/store
+anti-dependencies. Chapter 15 adds allocation with partial memory and typed
+alias contents. Chapters 16-24 currently retain their older parser-managed
 memory chains; forwarding through those snapshots is tracked in the
 [backport queue](../docs/chapter-backports.md).
 
diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 55822722..5f096ef7 100644
--- a/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -26,6 +26,24 @@ public class LoadNode extends MemOpNode {
         _declaredType = glb;
     }
 
+    @Override boolean canDrop(MemOpNode other, Node dep) {
+        return super.canDrop(other,dep) && _declaredType==((LoadNode)other)._declaredType && !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 "Load"; }
 
diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index 08e08bbf..44304bcb 100644
--- a/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -21,6 +21,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 && err()==null;
+    }
+
     @Override
     boolean eq(Node n) {
         MemOpNode mem = (MemOpNode)n; // Invariant
diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java
index f4972f96..55fa6efd 100644
--- a/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -15,14 +15,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 {
+public abstract class Node implements 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.
@@ -31,7 +31,7 @@ public abstract class Node {
      * 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
@@ -42,7 +42,7 @@ public abstract class Node {
      * 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;
 
 
     /**
@@ -210,6 +210,7 @@ public abstract class Node {
     // 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();
     }
 
@@ -598,6 +599,20 @@ public abstract class Node {
     // 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/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 650edd6b..cdb4b7cc 100644
--- a/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -70,23 +70,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( !isMem() && 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, _declaredType,lhss).peephole();
-            Node phi_rhs = new PhiNode(_label, _declaredType,rhss).peephole();
-            return op.copy(phi_lhs,phi_rhs);
-        }
+        // 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 ) {
@@ -116,12 +102,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;
+        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;
+        }
         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/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index f7a56503..a6b8d834 100644
--- a/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -67,7 +67,7 @@ public class RegionNode extends Node {
         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/chapter10b/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter10b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index b59eee93..8bf1debe 100644
--- a/chapter10b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/chapter10b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -3,6 +3,10 @@ package com.seaofnodes.simple;
 import com.seaofnodes.simple.node.Node;
 import com.seaofnodes.simple.node.StopNode;
 import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.node.LoadNode;
+import com.seaofnodes.simple.node.StoreNode;
+import com.seaofnodes.simple.evaluator.Evaluator;
+import java.util.BitSet;
 import org.junit.Test;
 
 import java.util.Arrays;
@@ -519,4 +523,61 @@ return 0;
             org.junit.Assert.assertArrayEquals(arg==0 ? new Object[]{3L,17L,7L} : new Object[]{11L,5L,13L}, obj.fields());
         }
     }
+
+    @Test public void testKeepLoadsAtMerge() {
+        StopNode stop = new Parser("""
+            struct S { int x; }
+            S a = new S; S b = new S;
+            a.x = arg; b.x = arg+1;
+            S p = a; S q = b;
+            if (arg<0) { p=b; q=a; }
+            int v;
+            if (arg>1) v=p.x; else v=q.x;
+            return v;
+            """).parse().iterate();
+        // The one-step safety check stops at the memory aggregate.
+        assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet()));
+        assertEquals(-1L,Evaluator.evaluate(stop,-1));
+        assertEquals(1L,Evaluator.evaluate(stop,0));
+        assertEquals(3L,Evaluator.evaluate(stop,3));
+    }
+
+    @Test public void testDropStores() {
+        StopNode stop = new Parser("""
+            struct S { int x; }
+            S s = new S;
+            if (arg) s.x=arg+1; else s.x=arg+2;
+            return s;
+            """).parse().iterate();
+        // The initializing slice also remains live as the aggregate default.
+        assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet()));
+        assertEquals(2L,((Evaluator.Obj)Evaluator.evaluate(stop,0)).fields()[0]);
+        assertEquals(4L,((Evaluator.Obj)Evaluator.evaluate(stop,3)).fields()[0]);
+    }
+
+    @Test public void testKeepReadsBeforeWrites() {
+        StopNode stop = new Parser("""
+            struct S { int x; int y; }
+            S a = new S; S b = new S;
+            a.x=arg; b.x=arg+1;
+            S p=a; S q=b;
+            if (arg<0) { p=b; q=a; }
+            int v;
+            if (arg>1) { v=p.x; p.x=41; p.y=5; }
+            else       { v=q.x; q.x=42; }
+            return v;
+            """).parse().iterate();
+        assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet()));
+        assertEquals(-1L,Evaluator.evaluate(stop,-1));
+        assertEquals(1L,Evaluator.evaluate(stop,0));
+        assertEquals(3L,Evaluator.evaluate(stop,3));
+    }
+
+    private static int countMemoryNodes(Node n, Class<?> kind, BitSet seen) {
+        if (n==null || seen.get(n._nid)) return 0;
+        seen.set(n._nid);
+        int cnt=kind.isInstance(n) ? 1 : 0;
+        for (Node def : n._inputs) cnt+=countMemoryNodes(def,kind,seen);
+        return cnt;
+    }
 }