Bring forward the lazy mem alias

Integrate with ch15 NewNode creating aliases

7 files changed, 183 insertions, 29 deletions

diff --git a/chapter10a/README.md b/chapter10a/README.md
index 47fd5ad6..80a1f46c 100644
--- a/chapter10a/README.md
+++ b/chapter10a/README.md
@@ -98,6 +98,25 @@ A load can also move through a memory Phi when doing so exposes a useful
 load-after-store fold. On a loop, the backedge must fold, preventing this rewrite
 from repeatedly moving the load around the cycle.
 
+The reverse direction can save an operation: a Phi of matching Loads or Stores
+can become one operation after the join. For example, these two writes:
+
+```java
+if (arg) s.x = arg+1;
+else     s.x = arg+2;
+```
+
+can become `s.x = Phi(arg+1,arg+2)`. The general rewrite creates a separate,
+correctly typed Phi for each differing operand, including memory and pointers;
+identical operands need no Phi. An exact-class copy preserves the operation's
+attributes. The proposed result must not widen the original Phi's type.
+
+Every arm must match the operation and field and have no control input. A Store
+must have no other users, so moving it removes the original effect. A Load must
+have no possible conflicting write or memory merge among its memory's users;
+otherwise delaying the read could change its value. The check happens during
+optimization, before any scheduler can supply explicit anti-dependency edges.
+
 The single chain is conservative. A store to `y` can prevent forwarding an
 earlier store to `x`, even when the objects are identical. This is a missed
 optimization, not a correctness problem; it motivates the next chapter.
diff --git a/chapter10a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter10a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 54689283..001f4bf6 100644
--- a/chapter10a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter10a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -23,6 +23,23 @@ 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);
+    }
+
+    // A Store directly clobbers this memory. A Phi might lead to a clobber
+    // through a cycle; conservatively stop rather than searching beyond it.
+    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 ) return true;
+        }
+        return false;
+    }
+
     @Override
     public String label() { return "Load"; }
 
diff --git a/chapter10a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter10a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index d811e71a..138f8fa5 100644
--- a/chapter10a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/chapter10a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -18,6 +18,15 @@ 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);
+        if( !_name.equals(other._name) || err()!=null ) return false;
+        return !(ptr()._type instanceof TypeMemPtr p &&
+                 other.ptr()._type instanceof TypeMemPtr q && p._obj!=q._obj);
+    }
+
     @Override
     boolean eq(Node n) {
         MemOpNode mem = (MemOpNode)n; // Invariant
diff --git a/chapter10a/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10a/src/main/java/com/seaofnodes/simple/node/Node.java
index eb6c1697..6a4d6334 100644
--- a/chapter10a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter10a/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();
     }
 
@@ -449,7 +450,9 @@ public abstract class Node {
      * 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 ) {
+    Node addDep(Node dep) { return addDep(dep,false); }
+    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;
@@ -457,8 +460,8 @@ public abstract class Node {
         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; // No need for deps on immediate neighbors
+        if( !forwards && Utils.find(_outputs,dep)!= -1 ) return this;
         _deps.add(dep);
         return this;
     }
@@ -590,6 +593,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/chapter10a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter10a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index bdf50847..c52fad49 100644
--- a/chapter10a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter10a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -66,23 +66,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, _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 ) {
@@ -112,12 +98,59 @@ 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 ) 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 = new PhiNode(_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/chapter10a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter10a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index f7a56503..a6b8d834 100644
--- a/chapter10a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter10a/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/chapter10a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter10a/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index 26bbb62a..f39b1e78 100644
--- a/chapter10a/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/chapter10a/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;
@@ -165,7 +169,7 @@ while (arg) {
 return bar.a;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop10,0,(Phi_a+2));", stop.toString());
+        assertEquals("return Phi(Loop10,0,(Phi_$mem+2));", stop.toString());
     }
 
     @Test
@@ -519,4 +523,59 @@ return 0;
             org.junit.Assert.assertArrayEquals(arg==0 ? new Object[]{3L,17L,7L} : new Object[]{11L,5L,13L}, obj.fields());
         }
     }
+
+    @Test public void testDropLoads() {
+        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();
+        assertEquals(1,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();
+        assertEquals(1,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;
+    }
 }