From 6e59fc1b71f2098c8baf90a6c54e5a33b7291e94 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 19 Sep 2026 22:31:42 -0700 Subject: Unify mixed-return checking and results Unify dominator caching. --- .../main/java/com/seaofnodes/simple/IterPeeps.java | 4 ++-- .../com/seaofnodes/simple/codegen/CodeGen.java | 24 +++++----------------- .../simple/codegen/GlobalCodeMotion.java | 6 +++--- .../java/com/seaofnodes/simple/node/CFGNode.java | 21 +++++++++++++------ .../java/com/seaofnodes/simple/node/FunNode.java | 5 +---- .../java/com/seaofnodes/simple/node/LoadNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 4 +--- .../com/seaofnodes/simple/node/RegionNode.java | 14 ++++++------- .../com/seaofnodes/simple/node/StartCUNode.java | 2 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 4 ++-- .../java/com/seaofnodes/simple/Chapter10Test.java | 15 ++++++++++++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 +++++++++++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 16 +++++++++++++++ .../seaofnodes/simple/node/PrintTestSupport.java | 9 ++++++++ 15 files changed, 92 insertions(+), 50 deletions(-) (limited to 'chapter25/src') diff --git a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java index fda5af65..145e0e03 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -212,7 +212,7 @@ public class IterPeeps { for( Node use : n._outputs ) { CFGNode ublk = useBlock(n,use); if( ublk != null ) - lca = ublk._idom(lca,null); + lca = ublk.domLCA(lca,null); } if( lca == null ) return null; if( !early.sameFun(lca) ) return null; @@ -231,7 +231,7 @@ public class IterPeeps { if( phi.in(i)==n ) { if( i >= phi.region().nIns() ) return null; - found = phi.region().cfg(i)._idom(found,null); + found = phi.region().cfg(i).domLCA(found,null); } return found; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 2fccb5f3..317fff71 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -339,26 +339,12 @@ public class CodeGen { public int rpc( String clz ) { return _rpcs.next(clz); } - // idepths are cached and valid until *inserting* CFG edges (deleting is - // OK). This happens with inlining, which bumps the version to bulk - // invalidate the idepth caches. - private static final int IDEPTH_STRIDE = 1_000_000; - private int _iDepthVersion = 0; + // Inlining can insert CFG edges and invalidate cached depth ordering. + private char _iDepthVersion; + public char iDepthVersion() { return _iDepthVersion; } public void invalidateIDepthCaches() { + assert _iDepthVersion < Character.MAX_VALUE : "Dominator cache version exceeds 65535"; ++_iDepthVersion; - assert _iDepthVersion < IDEPTH_STRIDE; // Wrapped; needs a major hack to fix - } - public boolean validIDepth(int idepth) { - if( idepth==0 ) return false; - if( _iDepthVersion==0 ) return true; - return (idepth%IDEPTH_STRIDE)==_iDepthVersion; - } - public int iDepthAt(int idepth) { - return IDEPTH_STRIDE*idepth+_iDepthVersion; - } - public int iDepthFrom(int idepth) { - assert idepth==0 || validIDepth(idepth); - return idepth+IDEPTH_STRIDE; } // Popular visit bitset, declared here, so it gets reused all over @@ -1117,7 +1103,7 @@ public class CodeGen { if( _cfg==null ) return "no CFG"; SB sb = new SB(); for( CFGNode cfg : _cfg ) { - sb.fix(8,""+cfg._idepth); + sb.fix(8,""+(int)cfg._idepth); IRPrinter.printLine( cfg, sb ); } return sb.toString(); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 71c08d18..a72dde97 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -285,7 +285,7 @@ public abstract class GlobalCodeMotion { CFGNode lca = null; for( Node use : n._outputs ) if( use != null ) - lca = use_block(n,use, late)._idom(lca,null); + lca = use_block(n,use, late).domLCA(lca,null); // Loads may need anti-dependencies, raising their LCA if( n instanceof MemOpNode load && load._isLoad ) @@ -314,7 +314,7 @@ public abstract class GlobalCodeMotion { CFGNode found=null; for( int i=1; i * See {@link ...} */ - public int _idepth; - public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); + public char _idepth; + public char _idepthVersion; + public int idepth() { return validIDepth() ? _idepth : cacheIDepth(idom().idepth()+1); } + // Zero depth means uncached. Check before narrowing so overflow cannot wrap. + final int cacheIDepth(int depth) { + assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; + _idepthVersion = CodeGen.CODE.iDepthVersion(); + return _idepth = (char)depth; } + final boolean validIDepth() { return _idepth!=0 && _idepthVersion==CodeGen.CODE.iDepthVersion(); } + + // Return the immediate dominator of this Node and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); if( comp >= 0 ) lhs = (dep==null ? lhs : dep.addDep(lhs)).idom(); if( comp <= 0 ) rhs = (dep==null ? rhs : dep.addDep(rhs)).idom(); - if( lhs==null || rhs==null ) return null; } return lhs; } 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 274cc146..ddd637c9 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -197,10 +197,7 @@ public class FunNode extends RegionNode { // Bypass Region idom, always assume depth == 1, one more than Start, // unless folding - @Override public int idepth() { - if( _folding ) return super.idepth(); - return CodeGen.CODE.iDepthAt(1); - } + @Override public int idepth() { return _folding ? super.idepth() : 1; } // Bypass Region idom, always assume idom is Start @Override public CFGNode idom(Node dep) { 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 f5b61048..fb93964a 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -141,7 +141,7 @@ public class LoadNode extends MemOpNode { for( Node memuse : mem._outputs ) // Find a prior load, has same mem,ptr,off but higher ctrl if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() && - cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() && // Higher control means load is legal earlier + cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() && // Higher control means load is legal earlier addDep(ld)._type.isa(_type) ) // and not rolling backwards return ld; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 42c76060..e8464353 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -25,9 +25,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); - } + @Override public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 81d0d6b9..32434850 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -148,22 +148,20 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { - if( CodeGen.CODE.validIDepth(_idepth) ) - return _idepth; - int d=0; + if( validIDepth() ) return _idepth; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,CodeGen.CODE.iDepthFrom(((CFGNode)n).idepth())); - return _idepth = d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // Walk the LHS & RHS idom trees in parallel until they match, or either fails. - // Because this does not cache, it can be linear in the size of the program. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i strs ) { Serialize.gather(strs,_fname); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java index 7d2b2773..dc21e5eb 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -80,7 +80,7 @@ public class StartNode extends LoopNode implements MultiNode { @Override public Node idealize() { return null; } // No immediate dominator, and idepth==0 - @Override public int idepth() { return CodeGen.CODE.iDepthAt(0); } + @Override public int idepth() { return 0; } @Override public CFGNode idom(Node dep) { return null; } @Override public boolean eq( Node n ) { return true; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java index 45f5519e..b0bf8343 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -88,13 +88,13 @@ public class StopNode extends CFGNode { } @Override public int idepth() { - if( _idepth!=0 ) return _idepth; + if( validIDepth() ) return _idepth; int d=0; for( Node ret : _inputs ) // All public results are hooked on the Stop, including data // values, so must check CFG if( ret instanceof CFGNode cfg ) d = Math.max(d,cfg.idepth()+1); - return _idepth=d; + return cacheIDepth(d); } } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java index a96da02c..029e28b8 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,21 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter10Test { + @Test public void testDeadReferenceReturn() { + for( String body : new String[] { + "return new S; return 0;", + "if(1) return new S; else return 0;" + } ) { + String src = "struct S { int x; }; " + body; + var code = new CodeGen(src).parse().opto().typeCheck(); + // This chapter also has constructor/class-init Returns in the CompUnit. + var entry = (com.seaofnodes.simple.node.FunNode)code._start.uctrl(); + org.junit.Assert.assertTrue(body, + entry.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + private static final String NULLABLE_POINT_SOURCE = """ struct Point { int x; new Point = { int v -> x = v; }; }; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 85317644..4b2d48d8 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -5,6 +5,20 @@ import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter12Test { + @Test public void testDeadNumericReturns() { + for( String[] test : new String[][] { + {"if(1) return 7; else return 2.5;", "7"}, + {"if(0) return 7; else return 2.5;", "2.5"}, + {"return 7; return 2.5;", "7"}, + {"return 2.5; return 7;", "2.5"} + } ) { + String src = test[0]; + var code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals(src,test[1],Eval2.eval(code,0)); + } + } + + @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java index d7fd12ff..4cf19746 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -11,6 +11,22 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testReachableMixedReturns() { + for( String[] test : new String[][] { + {"if(arg) return 7; else return 2.5;", "No common type amongst int and f64"}, + {"struct S { int x; }; if(arg) return new S; else return 0;", + "No common type amongst int and reference"} + } ) { + try { + new CodeGen(test[0]).parse().opto().typeCheck(); + fail("Expected incompatible return types: " + test[0]); + } catch( Parser.ParseException e ) { + assertEquals("Cannot return generic scalar",e.getMessage()); + } + } + } + + @Test public void testPrintingForwardReferenceScope() throws Exception { new CodeGen("return 0;").parse(); var declared = TypeMemPtr.make(TypeStruct.make("PrintForward",true,true)); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 70d9071a..ceea1de5 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -21,15 +21,24 @@ public class PrintTestSupport { var ins = new IdentityHashMap(); var outs = new IdentityHashMap(); var hashes = new IdentityHashMap(); + var versions = new IdentityHashMap(); var depths = new IdentityHashMap(); for( Node n : nodes ) { ins.put(n,n._inputs.toArray(new Node[0])); outs.put(n,n._outputs.toArray(new Node[0])); hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) { + depths.put(n,(int)cfg._idepth); + versions.put(n,(int)cfg._idepthVersion); + } } print.run(); for( Node n : nodes ) { assertEquals("hash of node "+n._nid,(int)hashes.get(n),hash.getInt(n)); + if( n instanceof CFGNode cfg ) { + assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + assertEquals("depth version of node "+n._nid,(int)versions.get(n),cfg._idepthVersion); + } assertEquals(ins.get(n).length,n.nIns()); assertEquals(outs.get(n).length,n.nOuts()); for( int i=0; i