Do BulkMemPhi splits one by one

3 files changed, 41 insertions, 113 deletions

diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
index d261a2b5..cabf7d69 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
@@ -197,17 +197,11 @@ public class BulkMemPhiNode extends PhiNode {
     // Slice out given alias
     private MemMergeNode slice( int alias ) {
         assert !_aliases.get(alias);
-        assert !hasDup(alias);
-        // Inputs are the same; MemPhi will sharpen his own inputs
-        MemPhiNode mphi = new MemPhiNode("$"+alias,alias);
-        for( int i=0; i<nIns(); i++ ) mphi.addDef(in(i));
-        Node mem = mphi.peephole();
+        // 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);
         assert ((TypeMem)mem._type)._alias==alias;
-        // The precise Phi is a new alias-sensitive user of every memory
-        // input.  Revisit those defs: a predecessor BulkMemPhi may now need
-        // to split this alias even though none of its inputs or types changed.
-        for( int i=1; i<mphi.nIns(); i++ )
-            CodeGen.CODE.add(mphi.in(i));
 
         BitSet aliases = ((BitSet)_aliases.clone());
         aliases.set(alias);
@@ -219,9 +213,12 @@ public class BulkMemPhiNode extends PhiNode {
         // away and hide those neighbor relationships.
         for( int i=1; i<bphi.nIns(); i++ )
             CodeGen.CODE.add(bphi.in(i));
-        Node bulk = bphi.peephole();
+        // 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
+        Node bulk = bphi.init();
         CodeGen.CODE.add(bulk);
-        CodeGen.CODE.add(mphi);
+        CodeGen.CODE.add(mem);
         return aggregate(bulk,alias,mem);
     }
 
@@ -245,47 +242,33 @@ public class BulkMemPhiNode extends PhiNode {
         return mmm;
     }
 
-    // Find the precise Phi parallel to this bulk Phi at the same merge.
+    // Find or make the precise Phi parallel to this bulk Phi at the same merge.
     private Node precisePhi(int alias) {
-        Node found = null;
+        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.BOT.makeFrom(alias));
+        for( int i=1; i<nIns(); i++ )
+            mphi.addDef(CodeGen.CODE.add(preciseInput(in(i),alias)));
+        return (MemPhiNode)mphi.peephole();
+    }
+
+    MemPhiNode _findPhi(int alias) {
         for( Node use : region().outs() )
-            if( use instanceof MemPhiNode mphi && mphi._alias==alias ) {
-                assert found==null;
-                found = mphi;
-            }
-        // The parallel Phi may already have collapsed to a common input.  Do
-        // not recover it from downstream MemMerges: they are distinct program
-        // points and can legitimately carry different values for this alias.
-        // Reconstruct from this Phi's merge inputs instead.  MemPhi selects
-        // the alias from each input MemMerge and collapses when, for example,
-        // the alias is loop-invariant here.
-        if( found==null ) {
-            MemPhiNode mphi = new MemPhiNode("$"+alias,alias);
-            mphi.addDef(region());
-            // Publishing the Phi on the Region makes it visible to recursive
-            // precisePhi lookups before all loop inputs have been installed.
-            // Give that recursion a valid lattice value until peephole computes
-            // the completed precise-memory Phi.
-            mphi.setType(TypeMem.BOT.makeFrom(alias));
-            for( int i=1; i<nIns(); i++ )
-                mphi.addDef(preciseInput(in(i),alias));
-            found = mphi.peephole();
-            // A newly reconstructed precise Phi also creates new users of
-            // its memory inputs.  In particular, a BulkMemPhi input may now
-            // need to split this alias, a backwards (user-to-def) change not
-            // covered by processing the new Phi itself.
-            for( int i=1; i<mphi.nIns(); i++ )
-                CodeGen.CODE.add(mphi.in(i));
-            CodeGen.CODE.add(found);
-        }
-        return found;
+            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);
-        assert !(mem instanceof BulkMemPhiNode bulk) || !bulk.isSplit(alias);
+        if( mem instanceof BulkMemPhiNode bulk && bulk.isSplit(alias) )
+            return bulk.precisePhi(alias);
         return mem;
     }
 
@@ -298,13 +281,6 @@ public class BulkMemPhiNode extends PhiNode {
         return true;
     }
 
-    private boolean hasDup( int alias ) {
-        for( Node use : region().outs() )
-            if( use instanceof MemPhiNode mphi && mphi._alias==alias )
-                return true;
-        return false;
-    }
-
     @Override public boolean eq(Node n) {
         return _aliases.equals(((BulkMemPhiNode)n)._aliases) && super.eq(n);
     }
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java
index a393a623..2966ec04 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java
+++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java
@@ -21,68 +21,16 @@ public class Chapter25Test {
     @Ignore
     @Test
     public void testJig() {
-        String src =
-"""
-if(3) arg=arg^arg;
-else return arg;
-u8 v0=arg^--arg;
-if(v0<=1) return 37;
-else {
-    arg=arg;
-    while(3) {
-        arg=v0==++arg;
-        arg=v0;
-        break;
+        String src =" while(1?!0:arg++) {";
+        String src2 = """
+int v0=0^0;
+    while(1) {
+        arg=v0++&0;
+            int v2=0;
+                    if(v0)
+                        if(v0) v2=0;
     }
-}
-arg=arg;
-struct IC95xuj {
-    bool v1;
-    u8 v2;
-    u8 He;
-};
-if(v0<new IC95xuj.He) while(new IC95xuj.He<!new IC95xuj.He) {
-        arg=new IC95xuj.He;
-        if(new IC95xuj.v1) while(new IC95xuj.v1) if(0&&new IC95xuj.v2) continue;
-                else v0=false?new IC95xuj.v2:new IC95xuj.v1&2;
-        else if(new IC95xuj.v2!=3>-++arg*arg) while(false + new IC95xuj.v2) arg=-arg;
-            else continue;
-        v0=new IC95xuj.v2;
-        arg=-new IC95xuj.He;
-        flt v3=-arg||---v0;
-        IC95xuj !v0=new IC95xuj;
-        v3=arg;
-    }
-else {
-    v0=-new IC95xuj.He;
-    v0=---v0/---v0+new IC95xuj.He;
-    return -new IC95xuj.v1|(++arg>arg?new IC95xuj.He:++v0);
-}
-while(-new IC95xuj.He*arg<=--v0||106) return new IC95xuj;
-while(new IC95xuj.v1<new IC95xuj.v2) {
-    if(new IC95xuj.v1||v0) break;
-    else {
-            int arg=new IC95xuj.v1;
-            while(arg<new IC95xuj.v1) {
-                arg=arg+0;
-                while(new IC95xuj.v2+!new IC95xuj.He)
-                    continue;
-                arg=0==new IC95xuj;
-            }
-        }
-        v0=1&new IC95xuj.He&new IC95xuj.He^arg;
-        v0=arg||--v0<--new IC95xuj.v2|3?new IC95xuj.v2&-new IC95xuj.v2:new IC95xuj.He;
-        v0=4;
-        break;
-}
-if(new IC95xuj.He) {
-    arg=0;
-    return v0;
-}
-else
-    return new IC95xuj;
-
-""";
+    """;
         CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck);
         assertEquals("2",Eval2.eval(code,0));
     }
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
index 51747fe4..a4532eb2 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
+++ b/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
@@ -19,9 +19,13 @@ public class FuzzerWrap {
         -5037182906211190034L, // dead Guard control
         -6359653295501938199L, // monotonicity, escape is dead
          6506797708065910879L, // missing ModeNode._mode is optimistic
+          650692970082394944L, // recursive bulk mem split
     };
 
     private static final long[] OPEN_FAILING_SEEDS = {
+        8335100609598232836L,
+        2520958273643234516L,
+        -3772838984504063325L,
     };