From b1e1045173c4bc2525ffe9366c90549f5a325933 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 12 Sep 2026 16:10:33 -0700 Subject: 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 --- .../main/java/com/seaofnodes/simple/IterPeeps.java | 78 +++++++++++++++++++++- .../main/java/com/seaofnodes/simple/Parser.java | 10 +-- .../java/com/seaofnodes/simple/node/CFGNode.java | 65 ++++++++++++++++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 41 ++++++++---- .../java/com/seaofnodes/simple/node/ScopeNode.java | 77 ++++++++++++++++++--- 5 files changed, 242 insertions(+), 29 deletions(-) (limited to 'chapter25/src/main') 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 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.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 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 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 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