Ch10update (#75)

* Store-after-Store peep

* Load-after-Store peephole

* Fix graph viz mem edge color bug

* Scalar replace loop carried dependence

* #67 Dead Not node hanging around - if we add a Not in the upcast then add it to the IterPeeps worklist to ensure it gets cleaned up. We don't see the Not node in the parser hence we cannot do a peep on it there.

* #67 Update visuals. Add description of Store-Store and Store-Load peeps. Add examples.

* #67 Undo the change that wasn't supposed to be committed!

* #67 Update description of the Store-Store and Store-Load peepholes

---------

Co-authored-by: Cliff Click <cliffc@acm.org>

6 files changed, 61 insertions, 6 deletions

diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 26e57727..d37c6296 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.Field;
 
@@ -38,6 +39,27 @@ public class LoadNode extends MemOpNode {
 
     @Override
     public Node idealize() {
+
+        // Simple Load-after-Store on same address.
+        if( mem() instanceof StoreNode st &&
+            ptr() == st.ptr() ) { // Must check same object
+            assert _field==st._field; // 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.
+        //   BEFORE (2 Sts, 1 Ld):          AFTER (1 St):
+        //   if( pred ) ptr.x = e0;         val = pred ? e0
+        //   else       ptr.x = e1;                    : e1;
+        //   val = ptr.x;                   ptr.x = val;
+        if( mem() instanceof PhiNode phi && phi.nIns()== 3 &&
+            ((phi.in(1) instanceof StoreNode st1 && ptr()==st1.ptr()) ||
+             (phi.in(2) instanceof StoreNode st2 && ptr()==st2.ptr()) ) ) {
+            Node ld1 = new LoadNode(_field,phi.in(1),ptr()).peephole();
+            Node ld2 = new LoadNode(_field,phi.in(2),ptr()).peephole();
+            return new PhiNode(_field._fname,_type,phi.region(),ld1,ld2);
+        }
+
         return null;
     }
 }
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index 4376bb0f..dd68120c 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -18,7 +18,6 @@ abstract class MemOpNode extends Node {
 
     public Node mem() { return in(1); }
     public Node ptr() { return in(2); }
-    public Node val() { return nIns() > 3 ? in(3) : null; }
 
     @Override
     boolean eq(Node n) {
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java
index f96b88bd..6a32c092 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -178,6 +178,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;
     }
@@ -264,7 +265,11 @@ 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() {
+        assert Utils.find(_outputs, null) != -1;
+        delUse(null);
+        return (N)this;
+    }
 
 
     // Replace self with nnn in the graph, making 'this' go dead
@@ -459,9 +464,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
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 6261c446..08fe047c 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.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.Utils;
 
 import java.util.BitSet;
@@ -36,6 +37,8 @@ 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() {
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 44c1bab7..8a50eb56 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -255,7 +255,7 @@ public class ScopeNode extends Node {
         if( ctrl._type==Type.XCONTROL ) return null;
         // Invert the If conditional
         if( invert )
-            pred = pred instanceof NotNode not ? not.in(1) : new NotNode(pred).peephole();
+            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 ) {
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index 07e4e3f7..8faf6d4b 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -28,6 +28,7 @@ public class StoreNode extends MemOpNode {
     public String glabel() { return "."+_field._fname+" ="; }
     @Override
     public boolean isMem() { return true; }
+    public Node val() { return in(3); }
 
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
@@ -41,6 +42,31 @@ public class StoreNode extends MemOpNode {
 
     @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
+            // Must have exactly one use of "this" or you get weird
+            // non-serializable memory effects in the worse case.
+            st.checkNoUseBeyond(this) ) {
+            assert _field==st._field; // 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;
+    }
+
 }