A few missing addDeps

IterPeeps cnt does not reset.
Faster schedulableIses, reuses ID Map.
Test in Iter work if not GVN table
ScheduableUses peeks through folding/dead Call/Fun

12 files changed, 160 insertions, 75 deletions

diff --git a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java
index d2611b32..d4b84828 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -52,6 +52,7 @@ public class IterPeeps {
 
     public final WorkList<Node> _work;
     final WorkList<CallEndNode> _workInline;
+    private int _cnt;
 
     public IterPeeps( long seed ) {
         _work       = new WorkList<>(seed);
@@ -98,13 +99,12 @@ public class IterPeeps {
 
     // Run all the code-reduction and type-lifting peeps as possible
     private void iteratePeeps( CodeGen code ) {
-        assert !CodeGen.expensiveAssert(1) || (progressOnList(code, _work) && schedulableUses(code));
-        int cnt=0;
+        assert !CodeGen.expensiveAssert(0) || (progressOnList(code, _work) && schedulableUses(code));
 
         Node n;
         while( (n=_work.pop()) != null ) {
             if( n.isDead() )  continue;
-            cnt++;              // Useful for debugging, searching which peephole broke things
+            _cnt++;              // Useful for debugging, searching which peephole broke things
             Node x = n.peepholeOpt();
             if( n instanceof CallEndNode cend )
                 _workInline.push(cend);
@@ -135,7 +135,7 @@ public class IterPeeps {
                 n.moveDepsToWorklist();
                 JSViewer.show(); // Show again
                 // Very expensive assert.
-                assert !CodeGen.expensiveAssert(cnt) || (progressOnList(code, _work) && schedulableUses(code));
+                assert !CodeGen.expensiveAssert(_cnt) || (progressOnList(code, _work) && schedulableUses(code));
             }
             if( n.isUnused() ) {
                 assert !(n instanceof StopNode); // StopNodes can die if all code in the compunit dies
@@ -162,13 +162,11 @@ public class IterPeeps {
     public static boolean progressOnList(CodeGen code, WorkList<Node> list ) {
         code._midAssert = true;
         Node changed = code._stop.walk( n -> {
-            Node m = n;
-            Type nval = n.compute();
             // Ignore most in-progress things
             if( n.iskeep() ) return null;
-
             // Types must be forwards, even if on the worklist.
-            assert nval.isa(n._type) : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+m;
+            Type nval = n.compute();
+            assert nval.isa(n._type) : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+n;
             if( list.on(n) )
                 return null;    // On worklist is ok!
             if( n instanceof CallEndNode cend ) {
@@ -176,9 +174,10 @@ public class IterPeeps {
                     return null; // On inline worklist is ok!
                 assert cend.maybeInline() <= 0 : "Inline fired and not on worklist, CallEndNode#"+cend._nid;
             }
-
+            // Off list: must be live, in GVN table, and no peeps.
             assert n.nOuts() > 0 : "Unused live node: "+n;
-            m = n.peepholeOpt();
+            assert code._gvn.get(n)==n : "Not in GVN table: "+n;
+            Node m = n.peepholeOpt();
             assert m==null : "Peep fired and not on worklist, "+n.getClass().getSimpleName()+"#"+n._nid+" -> "+m;
             return m;
         });
@@ -197,25 +196,26 @@ public class IterPeeps {
     // and no later than the LCA of its uses.  Catch graphs where a use escapes
     // above an input-defined branch before the later scheduling pass walks off
     // the top of the idom tree.
+    private static final IdentityHashMap<Node,CFGNode> earlyCache = new IdentityHashMap<>();
+    private static final BitSet VISIT = new BitSet();
     public static boolean schedulableUses(CodeGen code) {
-        IdentityHashMap<Node,CFGNode> earlyCache = new IdentityHashMap<>();
+        earlyCache.clear();
         Node bad = code._stop.walk( n -> {
             if( n.iskeep() || n.isDead() || n.isConst() ||
                 n instanceof CFGNode || n instanceof PhiNode || n instanceof ProjNode )
                 return null;
-            CFGNode early = CFGNode.earlyCFG(n,code._start,earlyCache,new BitSet());
-            if( early == null || early == code._start )
-                return null;
+            assert VISIT.isEmpty();
+            CFGNode early = CFGNode.earlyCFG(n,earlyCache,VISIT);
+            VISIT.clear();
+            if( early == null ) return null;
             CFGNode lca = null;
             for( Node use : n._outputs ) {
                 CFGNode ublk = useBlock(n,use);
                 if( ublk != null )
                     lca = ublk._idom(lca,null);
             }
-            if( lca == null )
-                return null;
-            if( !early.sameFun(lca) )
-                return null;
+            if( lca == null ) return null;
+            if( !early.sameFun(lca) )  return null;
             assert early.dominates(lca) : badSchedule(n,early,lca);
             return null;
         });
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index c5ceda41..cde88ffa 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -94,7 +94,18 @@ public abstract class CFGNode extends Node {
 
     // Safe read of the control input of a data node.
     public static CFGNode safeCFG(Node n) {
-        return n != null && n.in(0) instanceof CFGNode cfg ? cfg : null;
+        if( n==null ) return null;
+        if( !(n.in(0) instanceof CFGNode cfg) ) return null;
+        return cfg._safeCFG();
+    }
+    private CFGNode _safeCFG() {
+        return switch(this) {
+        case CallNode call when call.cend()._folding -> call.cfg0()._safeCFG();
+        case CallEndNode cend when cend._folding -> cend.cfg(1)._safeCFG();
+        case FunNode fun when fun._folding -> fun.cfg(1)._safeCFG();
+        case ReturnNode ret when ret.fun()._folding -> ret.cfg0()._safeCFG();
+        default -> this;
+        };
     }
 
     // True when this node dominates `sub` in the current idom tree.
@@ -105,56 +116,44 @@ public abstract class CFGNode extends Node {
         return false;
     }
 
-    public boolean sameFun(CFGNode that) {
-        FunNode fun = fun();
-        return fun != null && fun == that.fun();
-    }
-
-    public static boolean sameFun(CFGNode a, CFGNode b) {
-        return a != null && b != null && a.sameFun(b);
-    }
-
     public static CFGNode deepest(CFGNode a, CFGNode b) {
         if( a == null ) return b;
         if( b == null ) return a;
         return b.idepth() > a.idepth() ? b : a;
     }
 
-    public static CFGNode earlyCFG(Node n, CFGNode start) {
-        return earlyCFG(n,start,new IdentityHashMap<>(),new BitSet());
+    public static CFGNode earlyCFG(Node n) {
+        return earlyCFG(n,new IdentityHashMap<>(),new BitSet());
     }
 
-    public static CFGNode earlyCFG(Node n, CFGNode start, IdentityHashMap<Node,CFGNode> cache, BitSet active) {
-        if( n == null )
-            return null;
+    public static CFGNode earlyCFG(Node n, IdentityHashMap<Node,CFGNode> cache, BitSet active) {
+        if( n == null ) return null;
         CFGNode cached = cache.get(n);
-        if( cached != null )
-            return cached;
+        if( cached != null ) return cached;
         if( active.get(n._nid) )
             return safeCFG(n);
         active.set(n._nid);
-        CFGNode early = start;
-        if( n.in(0) instanceof CFGNode cfg )
-            early = cfg;
-        for( int i=1; i<n.nIns(); i++ )
-            early = deepest(early,defCFG(n.in(i),start,cache,active));
+        CFGNode early = null;
+        for( Node x : n._inputs )
+            early = deepest(early,defCFG(x,cache,active));
         active.clear(n._nid);
         cache.put(n,early);
         return early;
     }
 
-    private static CFGNode defCFG(Node n, CFGNode start, IdentityHashMap<Node,CFGNode> cache, BitSet active) {
-        if( n == null )
-            return null;
-        if( n instanceof PhiNode phi )
-            return phi.region();
-        if( n instanceof CFGNode cfg )
-            return cfg;
-        if( n instanceof ProjNode )
-            return safeCFG(n);
-        if( n.isConst() )
-            return start;
-        return earlyCFG(n,start,cache,active);
+    private static CFGNode defCFG(Node n, IdentityHashMap<Node,CFGNode> cache, BitSet active) {
+        if( n == null || n.isConst() )  return null; // no impact on early cfg
+        return switch( n ) {
+        case PhiNode phi -> phi.region();
+        case CFGNode cfg -> cfg;
+        case ProjNode projNode -> safeCFG( n );
+        default -> earlyCFG( n, cache, active );
+        };
+    }
+
+    public boolean sameFun(CFGNode that) {
+        FunNode fun = fun();
+        return fun != null && fun == that.fun();
     }
 
     // Anti-dependence field support
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java
index 9ce97ac6..51d10702 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java
@@ -128,11 +128,11 @@ public class CallNode extends CFGNode {
     // Link so this calls fun
     public Node link( FunNode fun ) {
         assert !linked(fun);
-        fun.addDef(this);
+        CodeGen.CODE.add(fun).addDef(this);
         for( Node use : fun._outputs )
             if( use instanceof ParmNode parm ) {
                 Node def = parm._idx==0 ? ConstantNode.seed(cend()._rpc).peephole() : arg(parm._idx);
-                parm.addDef(def);
+                CodeGen.CODE.add(parm).addDef(def);
                 // Linking can happen during post-SCCP inlining.  Keep an RPC
                 // Parm's cached finite set synchronized with its newly added
                 // input instead of waiting for the next worklist visit.
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java
index d1ff3f65..5be4d3e8 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java
@@ -90,7 +90,8 @@ public class EscapeNode extends TypeNode {
         }
         // New allocation is dead
         if( self()._type.isHigh() )
-            return pub();
+            if( pub()._type.isa(_type) ) return pub();
+            else addDep(pub());
         return null;
     }
 
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java
index d9d3e451..274cc146 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java
@@ -94,8 +94,8 @@ public class FunNode extends RegionNode {
                 for( Node use : ret().outs() )
                     if( use instanceof CallEndNode || use instanceof FunPtrNode )
                         CODE.add(use);
-            _sig = sig;
             unlock();
+            _sig = sig;
         }
     }
 
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java
index e3c6f0e2..16b83f22 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java
@@ -39,6 +39,12 @@ public class GuardNode extends Node {
     }
 
     @Override public Type compute() {
+        // Guard is a pinned, path-local fact.  If its control path is not
+        // executable, the fact is not executable either, regardless of how the
+        // value input sharpens later.
+        Type c = in(0)._type;
+        if( c != Type.CONTROL && c != Type.BOTTOM )
+            return Type.TOP;
         Type t = in(1)._type;
         if( t==Type.BOTTOM || t==Type.TOP ) return t;
         // The scalar envelope does not identify a value family.  Preserve it
@@ -50,6 +56,8 @@ public class GuardNode extends Node {
     }
 
     @Override public Node idealize() {
+        if( in(0)._type != Type.CONTROL && in(0)._type != Type.BOTTOM )
+            return null;
         if( in(1)._type==Type.BOTTOM || in(1)._type==Type.TOP ) return null;
         if( _type.isHighOrConst() && in(1)._type.isa(_type) )
             return in(1);
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 3c144b6e..d625b898 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -269,10 +269,7 @@ public class LoadNode extends MemOpNode {
         Node px = memphi.in(idx);
         if( px==null ) return false;
         assert !(px._type instanceof TypeMem mem && mem._t.isHighOrConst() );
-        //// To avoid cyclic pushing a Load up then down, getting here means
-        //// the load *must* replace with the high/constant.
-        //return true;
-        if( px instanceof StoreNode st1 && ptr()==addDep(st1.nnptr() ) && off()==st1.off() && st1.val()._type.isa(_type) )
+        if( px instanceof StoreNode st1 && ptr()==addDep(st1.nnptr() ) && off()==st1.off() && addDep(st1.val())._type.isa(_type) )
             // To avoid cyclic pushing a Load up then down, getting here means
             // the load *must* match against the Store
             return true;
@@ -304,6 +301,4 @@ public class LoadNode extends MemOpNode {
         Node shl = new ShlNode(null,val,shf.keep()).peephole();
         return new SarNode(null,shl,shf.unkeep());
     }
-
-    //@Override public int log_size() { return declaredType().log_size(); }
 }
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 1ad9d7a2..4112a977 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -149,7 +149,7 @@ public class PhiNode extends Node {
             n = guard.in(1);
             throw Utils.TODO("test and remove TODO");
         }
-        CFGNode early = CFGNode.earlyCFG(n,null);
+        CFGNode early = CFGNode.earlyCFG(n);
         return iff.pred()==cast.in(1) && (early==null || early.dominates(r)) ? n : null;
     }
 
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 36765981..57dcd66b 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -535,7 +535,7 @@ public class ScopeNode extends MemMergeNode {
     private void _addGuards( CFGNode ctrl, Node pred, boolean invert ) {
         if( pred==null || pred.isDead() )
             return;
-        CFGNode early = CFGNode.earlyCFG(pred,null);
+        CFGNode early = CFGNode.earlyCFG(pred);
         if( early != null && !early.dominates(ctrl) )
             return;
         // Short-circuit logic is represented by a Phi.  For `a || b` being
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index f140f28f..faa3d17b 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -146,7 +146,7 @@ public class StoreNode extends MemOpNode {
                 if( useAlias(use)==fld._alias ) {
                     int idx = use._inputs.find(this);
                     assert idx != -1;
-                    use.setDef(idx,st);
+                    CodeGen.CODE.add(use).setDef(idx,st);
                     i--;        // setDef removed use from this Store's outputs
                 }
             }
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java
index 2677de5e..a393a623 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java
+++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java
@@ -21,9 +21,70 @@ public class Chapter25Test {
     @Ignore
     @Test
     public void testJig() {
-        String src = "struct _Oan {};  return --arg; arg=++arg;";
+        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;
+    }
+}
+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("1",Eval2.eval(code,0));
+        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 d67b2065..d7293da1 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
+++ b/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
@@ -13,22 +13,42 @@ import static org.junit.Assert.assertTrue;
  */
 public class FuzzerWrap {
 
-    @Ignore
+    private static final long[] REGRESSION_SEEDS = {
+        375135762521757909L,   // bad LCA
+        -148471672577312953L,  // bulk mem
+        -5037182906211190034L, // dead Guard control
+        -6359653295501938199L, // monotonicity, escape is dead
+    };
+
+    private static final long[] OPEN_FAILING_SEEDS = {
+    };
+
+
+    @Test         public void fuzzPeepsRegression  () { fuzzPeepsSeeds(  REGRESSION_SEEDS); }
+    @Test @Ignore public void fuzzPeepsOpenFailures() { fuzzPeepsSeeds(OPEN_FAILING_SEEDS); }
+
+    private static void fuzzPeepsSeeds(long... seeds) {
+        var fuzzer = new Fuzzer();
+        for (long seed : seeds)
+            fuzzer.fuzzPeepsRegression(seed);
+    }
+
     @Test
-    public void fuzzPeeps() {
+    public void fuzzPeepsRandom() {
+        Random R = new Random(System.currentTimeMillis());
         var fuzzer = new Fuzzer();
-        for (int i=0; i<1000000; i++)
-            fuzzer.fuzzPeeps(i);
+        for (int i=0; i<100; i++)
+            fuzzer.fuzzPeeps(R.nextLong());
         assertTrue(fuzzer.noExceptions());
     }
 
 
+    @Ignore
     @Test
-    public void fuzzPeepsSmall() {
-        Random R = new Random(System.currentTimeMillis());
+    public void fuzzPeepsLarge() {
         var fuzzer = new Fuzzer();
-        for (int i=0; i<100; i++)
-            fuzzer.fuzzPeeps( R.nextLong());
+        for (int i=0; i<1000000; i++)
+            fuzzer.fuzzPeeps(i);
         assertTrue(fuzzer.noExceptions());
     }
 
@@ -40,4 +60,5 @@ public class FuzzerWrap {
         for (int i=0; i<1000000; i++)
             max_nid = fuzzer.fuzzPeepTiming(i, max_nid);
     }
+
 }