Bring forward the lazy mem alias

Integrate with ch15 NewNode creating aliases

5 files changed, 111 insertions, 25 deletions

diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index d057e5c9..6d44c84a 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter11/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/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index 551d2aa9..5a57a8c8 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/chapter11/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/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java
index 69605607..c712a017 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -14,14 +14,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.
@@ -30,7 +30,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
@@ -41,7 +41,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();
     }
 
@@ -575,6 +576,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/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index bbd19795..886ef092 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -69,23 +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( !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 ) {
@@ -115,12 +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;
+        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/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index 060dfb45..8933ea74 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter11/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();