Unify mixed-return checking and results

Unify dominator caching.

15 files changed, 92 insertions, 50 deletions

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<phi.nIns(); i++ )
             if( phi.in(i)==n )
-                found = phi.region().cfg(i)._idom(found,null);
+                found = phi.region().cfg(i).domLCA(found,null);
 
         assert found!=null;
         return found;
@@ -372,7 +372,7 @@ public abstract class GlobalCodeMotion {
     private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) {
         // Store and Load overlap, need anti-dependence
         if( stblk._anti==load._nid ) {
-            lca = stblk._idom(lca,null); // Raise Loads LCA
+            lca = stblk.domLCA(lca,null); // Raise Loads LCA
             if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved,
                 st.addDef(load); // Add anti-dep as well
             return lca;          // Cap this stores' anti-dep to here
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 0ff74a2b..b40f4204 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -34,6 +34,7 @@ public abstract class CFGNode extends Node {
         super(cfg);
         if( cfg != null ) {
             _idepth = cfg._idepth;
+            _idepthVersion = cfg._idepthVersion;
             _ltree = cfg._ltree;
             _pre = cfg._pre;
         }
@@ -70,24 +71,32 @@ public abstract class CFGNode extends Node {
      * <p>
      * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
      */
-    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<nIns(); i++ )
             if( !cfg(i)._type.isHigh() )
-                lca = cfg(i)._idom(lca,dep);
+                lca = cfg(i).domLCA(lca,dep);
         return lca;
     }
 
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StartCUNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StartCUNode.java
index d828c5f1..cd51f603 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/StartCUNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StartCUNode.java
@@ -25,7 +25,7 @@ public class StartCUNode extends StartNode {
     @Override public CFGNode cfg0() { return (CFGNode)in(0); }
 
     // IDom is cfg0() and depth is always Start+1 which is 0+1 or 1
-    @Override public int idepth() { return CodeGen.CODE.iDepthAt(1); }
+    @Override public int idepth() { return 1; }
     @Override public CFGNode idom(Node dep) { return cfg0(); }
     @Override public void gather( HashMap<String,Integer> 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<Node,Node[]>();
         var outs = new IdentityHashMap<Node,Node[]>();
         var hashes = new IdentityHashMap<Node,Integer>();
+        var versions = new IdentityHashMap<Node,Integer>();
         var depths = new IdentityHashMap<Node,Integer>();
         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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i));