Major bugfix around unscheduable graphs

Robust assert about all data ops are schedulable.
Utiltiies for several places domionator-like stuff is used.
Removing a Phi with matching null/not-null values is now more robust; removes a major source if scheduling misalignment.
Big comments about what gets covered by a null check, or not.
Permanent list of fuzzer seeds that used to fail

5 files changed, 242 insertions, 29 deletions

diff --git a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java
index 760a03ab..d2611b32 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -9,6 +9,7 @@ import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.print.JSViewer;
 import java.util.Arrays;
 import java.util.BitSet;
+import java.util.IdentityHashMap;
 import java.util.Random;
 
 /**
@@ -97,7 +98,7 @@ 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);
+        assert !CodeGen.expensiveAssert(1) || (progressOnList(code, _work) && schedulableUses(code));
         int cnt=0;
 
         Node n;
@@ -134,13 +135,14 @@ public class IterPeeps {
                 n.moveDepsToWorklist();
                 JSViewer.show(); // Show again
                 // Very expensive assert.
-                assert !CodeGen.expensiveAssert(cnt) || progressOnList(code, _work);
+                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
                 n.kill();       // Just plain dead
             }
         }
+        assert !CodeGen.expensiveAssert(0) || schedulableUses(code);
 
     }
 
@@ -191,6 +193,78 @@ public class IterPeeps {
         return sb.append(']').toString();
     }
 
+    // GCM assumes every movable node can be placed no earlier than its inputs
+    // 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.
+    public static boolean schedulableUses(CodeGen code) {
+        IdentityHashMap<Node,CFGNode> earlyCache = new IdentityHashMap<>();
+        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;
+            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;
+            assert early.dominates(lca) : badSchedule(n,early,lca);
+            return null;
+        });
+        return bad == null;
+    }
+
+    private static CFGNode useBlock(Node n, Node use) {
+        if( use == null )
+            return null;
+        if( use instanceof PhiNode phi ) {
+            CFGNode found = null;
+            for( int i=1; i<phi.nIns(); i++ )
+                if( phi.in(i)==n ) {
+                    if( i >= phi.region().nIns() )
+                        return null;
+                    found = phi.region().cfg(i)._idom(found,null);
+                }
+            return found;
+        }
+        return CFGNode.safeCFG(use);
+    }
+
+    private static String badSchedule(Node n, CFGNode early, CFGNode lca) {
+        StringBuilder sb = new StringBuilder("Unschedulable data node ")
+            .append(n.getClass().getSimpleName()).append('#').append(n._nid)
+            .append(" early=").append(cfg(early))
+            .append(" use-lca=").append(cfg(lca))
+            .append(" node=").append(n).append("\ninputs:");
+        for( int i=0; i<n.nIns(); i++ ) {
+            Node in = n.in(i);
+            sb.append("\n  in").append(i).append(": ").append(node(in))
+              .append(" cfg=").append(cfg(CFGNode.safeCFG(in)));
+        }
+        sb.append("\noutputs:");
+        for( Node use : n._outputs )
+            if( use != null )
+                sb.append("\n  use ").append(node(use))
+                  .append(" block=").append(cfg(useBlock(n,use)));
+        return sb.toString();
+    }
+
+    private static String node(Node n) {
+        return n==null ? "null" : n.getClass().getSimpleName()+"#"+n._nid+" "+n;
+    }
+
+    private static String cfg(CFGNode cfg) {
+        return cfg==null ? "null" : cfg.getClass().getSimpleName()+"#"+cfg._nid+" "+cfg;
+    }
+
     /**
      * Classic WorkList, with a fast add/remove, dup removal, random pull.
      * The Node's nid is used to check membership in the worklist.
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java
index 37c43a7a..a9b7c84b 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java
@@ -630,8 +630,8 @@ public class Parser {
         // IfNode takes current control and predicate
         Node ifNode = new IfNode(ctrl(), pred.keep()).peephole();
         // Setup projection nodes
-        Node ifT = new CProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
-        Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole();
+        CFGNode ifT = new CProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
+        CFGNode ifF = (CFGNode)new CProjNode(ifNode.unkeep(), 1, "False").peephole();
 
         // for( ;;next ) body
         int nextPos = -1, nextEnd = -1;
@@ -734,7 +734,7 @@ public class Parser {
         // conditions here, not the union.
         _breakScope.removeGuards(_breakScope.ctrl());
         _breakScope = require(jumpTo(_breakScope ),";");
-        _breakScope.addGuards(_breakScope.ctrl(), null, false);
+        _breakScope.addGuards((CFGNode)_breakScope.ctrl(), null, false);
         return _code.ZERO;
     }
 
@@ -779,8 +779,8 @@ public class Parser {
         pred.keep();
         Node ifNode = new IfNode(ctrl(), pred).peephole();
         // Setup projection nodes
-        Node ifT = new CProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
-        Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole().keep();
+        CFGNode ifT = new CProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
+        CFGNode ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole().keep();
         // In if true branch, the ifT proj node becomes the ctrl
         // But first clone the scope and set it as current
         ScopeNode fScope = _scope.dup(); // Duplicate current scope
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 2b668da8..c5ceda41 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -92,6 +92,71 @@ public abstract class CFGNode extends Node {
         return lhs;
     }
 
+    // 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;
+    }
+
+    // True when this node dominates `sub` in the current idom tree.
+    public boolean dominates(CFGNode sub) {
+        for( CFGNode cfg=sub; cfg!=null; cfg=cfg.idom() )
+            if( cfg == this )
+                return true;
+        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, CFGNode start, IdentityHashMap<Node,CFGNode> cache, BitSet active) {
+        if( n == null )
+            return null;
+        CFGNode cached = cache.get(n);
+        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));
+        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);
+    }
+
     // Anti-dependence field support
     public int _anti;           // Per-CFG field to help find anti-deps
 
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 17868faf..1ad9d7a2 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -3,9 +3,7 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.*;
 import com.seaofnodes.simple.codegen.Serialize;
 import com.seaofnodes.simple.type.*;
-import com.seaofnodes.simple.util.BAOS;
-import com.seaofnodes.simple.util.SB;
-
+import com.seaofnodes.simple.util.*;
 import java.util.BitSet;
 import java.util.HashMap;
 import java.util.IdentityHashMap;
@@ -105,7 +103,8 @@ public class PhiNode extends Node {
 
     @Override
     public Node idealize() {
-        if( ((RegionNode)region()).inProgress() || nOuts()==0 )
+        RegionNode r = (RegionNode)region();
+        if( r.inProgress() || nOuts()==0 )
             return null;        // Input is in-progress
 
         // If we have only a single unique input, become it.
@@ -115,7 +114,7 @@ public class PhiNode extends Node {
 
         // No bother if region is going to fold dead paths soon
         for( int i=1; i<nIns(); i++ )
-            if( region().in(i)._type == Type.XCONTROL )
+            if( r.in(i)._type == Type.XCONTROL )
                 return null;
 
         // Generic "pull down op"
@@ -123,19 +122,35 @@ public class PhiNode extends Node {
         if( same_op() && (progress = drop_same_op()) != null )
             return progress;
 
-        // If merging Phi(ZERO, guardNZ(N)) - we are losing the cast JOIN effects, so just remove.
-        if( nIns()==3 ) {
-            if( in(1) instanceof GuardNode cast && cast._nonZero && in(2)._type.makeZero()==in(2)._type && cast.in(1)!=this )  return unguard(cast.in(1));
-            if( in(2) instanceof GuardNode cast && cast._nonZero && in(1)._type.makeZero()==in(1)._type && cast.in(1)!=this )  return unguard(cast.in(1));
-        }
+        // If merging Phi(ZERO, guardNZ(N)) at the matching `if(N)` join, the
+        // Phi is exactly N.  The guard arm proves N is non-zero, and the other
+        // arm contributes N's zero value.  This is only legal if N is already
+        // available at the Phi region; otherwise a return-scope/live-on-exit
+        // Phi can lose the zero arm and export a branch-local value upward.
+        Node unguard;
+        if( (unguard=matchingGuardMerge(r,1)) != null ) return unguard;
+        if( (unguard=matchingGuardMerge(r,2)) != null ) return unguard;
 
         return null;
     }
 
-    private static Node unguard(Node n) {
-        while( n instanceof GuardNode guard )
+    private Node matchingGuardMerge(RegionNode r, int nzIdx) {
+        Node zero = in(3-nzIdx);
+        if( !(in(nzIdx) instanceof GuardNode cast && cast._nonZero) ||
+            zero._type.makeZero()!=zero._type ||
+            cast.in(1)==this )
+            return null;
+        if( !(r.in(nzIdx) instanceof CProjNode nz && nz._idx==0 && nz.ctrl() instanceof IfNode iff) )
+            return null;
+        if( !(r.in(3-nzIdx) instanceof CProjNode z && z._idx==1 && z.ctrl()==iff) )
+            return null;
+        Node n = cast.in(1);
+        while( n instanceof GuardNode guard ) {
             n = guard.in(1);
-        return n;
+            throw Utils.TODO("test and remove TODO");
+        }
+        CFGNode early = CFGNode.earlyCFG(n,null);
+        return iff.pred()==cast.in(1) && (early==null || early.dominates(r)) ? n : null;
     }
 
     // Same op on all Phi paths; all ops have only the Phi as a use.
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 3eabac81..36765981 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -452,14 +452,71 @@ public class ScopeNode extends MemMergeNode {
     // Up-casting: using the results of an If to improve a value.
     // E.g. "if( ptr ) ptr.field;" is legal because ptr is known not-null.
     //
-    // This operation is lexical, not semantic, and thus its behavior changes
-    // the language spec.  Optimizations that hide the lexical structure
-    // (e.g. constant folding control flow) can hide what is guarded or how the
-    // guard is applied, making it somewhat fragile.  Several good use cases
-    // are covered here, but not everything you might like.
+    // This operation is lexical, not a full semantic theorem prover, and thus
+    // its behavior changes the language spec.  Optimizations that hide the
+    // lexical structure (e.g. constant folding control flow) can hide what is
+    // guarded or how the guard is applied, making it somewhat fragile.  Several
+    // good use cases are covered here, but not everything you might like.
+    //
+    // Simple lexical facts work well:
+    //
+    //  ```
+    //    if( ptr )
+    //        return ptr.field; // `ptr` is guarded non-null here.
+    //
+    //    if( a && a.ptr )
+    //        return a.ptr.x;   // `a` is guarded while parsing the RHS load,
+    //                          // and remains guarded on the true arm.
+    //  ```
+    //
+    // Short-circuit expressions are lowered as nested Phis.  We recursively
+    // decompose the recognized Phi shape, so chains such as:
+    //
+    //  ```
+    //    if( x && y && z )
+    //        use(x,y,z);
+    //  ```
+    //
+    // discover the nested `x && y` and then `x`, `y`, and `z`; this is not
+    // merely a one-level lookup.  Likewise, nested tests carry lexical guards
+    // inwards:
+    //
+    //  ```
+    //    if( x && y )
+    //        if( z && a )
+    //            if( x.ptr && z.ptr )
+    //                ...
+    //  ```
+    //
+    // Here `x` is already guarded while parsing the outer true arm, `z` while
+    // parsing the inner true arm, and both are available before the matching
+    // loads.  The later post-test decomposition is just a convenience for
+    // values still schedulable at the post-test control.
+    //
+    // The hard limit is that a semantic implication is not always a
+    // schedulable Node.  For `(x && y)`, the true side implies that `y` was
+    // true, but `y` might be a value computed only on the RHS control arm:
+    //
+    //  ```
+    //    val ptr = ...;
+    //    if( ptr && (ptr=fcn() ? 0 : arg ) {}
+    //  ```
+    //
+    // A Guard pinned after the Phi merge and using the branch-local `ptr`
+    // value would give that value a use above its defining arm.  GCM then has
+    // no legal block between the value's early control and the LCA of its
+    // uses.  Thus `_addGuards` first checks that the predicate's effective
+    // early CFG dominates the control where the Guard would be pinned.  If it
+    // does not, we skip that guard even if the fact is semantically true.
+    //
+    // A more complete answer would need a richer logical/proof node, or would
+    // need to rematerialize predicates on the guarded path instead of using
+    // branch-local nodes directly.  Plain GuardNodes are intentionally kept to
+    // facts represented by values already available at the guard control.
+    //
     // TODO: Make this more robust for shapes like:
     //  ```
-    //    if( !ary || !ary# ) exit();
+    //    if( !ary || !ary# ) exit(); // facts about ary are lost, despite the early exit
     //    for( ...; ary# ) ...;
     //  ```
     // Here the guard ends up guarding the whole expression (both ary and ary#
@@ -467,8 +524,7 @@ public class ScopeNode extends MemMergeNode {
     // a dedicated logical expression node, or some sort of gather-of-checked
     // values to Guard post-test.
 
-    public void addGuards( Node ctrl, Node pred, boolean invert ) {
-        assert ctrl instanceof CFGNode;
+    public void addGuards( CFGNode ctrl, Node pred, boolean invert ) {
         _guards.add(ctrl);      // Marker to distinguish 0,1,2 guards
         // add pred & its cast to the normal input list, with special Vars
         if( pred==null || pred.isDead() )
@@ -476,9 +532,12 @@ public class ScopeNode extends MemMergeNode {
         _addGuards(ctrl,pred,invert);
     }
 
-    private void _addGuards( Node ctrl, Node pred, boolean invert ) {
+    private void _addGuards( CFGNode ctrl, Node pred, boolean invert ) {
         if( pred==null || pred.isDead() )
             return;
+        CFGNode early = CFGNode.earlyCFG(pred,null);
+        if( early != null && !early.dominates(ctrl) )
+            return;
         // Short-circuit logic is represented by a Phi.  For `a || b` being
         // false, or `a && b` being true, both individual operands have the
         // same proven value as the whole expression.  The "skipped RHS" path