Unify mixed-return checking and results

Unify dominator caching.

8 files changed, 50 insertions, 17 deletions

diff --git a/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index 9698abd9..8cfbe509 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -137,7 +137,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 LoadNode load )
@@ -216,7 +216,7 @@ public abstract class GlobalCodeMotion {
         for( ; stblk != defblk.idom(); stblk = stblk.idom() ) {
             // 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/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index 052ad8fc..8e063205 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -36,21 +36,28 @@ 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 _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; }
+    public char _idepth;
+    public int idepth() { return _idepth!=0 ? _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";
+        return _idepth = (char)depth;
+    }
+
 
     // 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( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom();
-            if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom();
+            if( lhs==null || rhs==null ) return null;
+            int comp = lhs.idepth() - rhs.idepth();
+            if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom();
+            if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom();
         }
         return lhs;
     }
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index ecda9c63..8fb6a4ce 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -28,7 +28,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 _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; }
+    @Override public int idepth() { return _idepth!=0 ? _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/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index fb39af17..59da86ff 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -92,19 +92,18 @@ public class RegionNode extends CFGNode {
     // Immediate dominator of Region is a little more complicated.
     @Override public int idepth() {
         if( _idepth!=0 ) return _idepth;
-        int d=0;
+        int depth=0;
         for( Node n : _inputs )
             if( n!=null )
-                d = Math.max(d,((CFGNode)n).idepth()+1);
-        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++ )
-            lca = cfg(i)._idom(lca,dep);
+            lca = cfg(i).domLCA(lca,dep);
         return lca;
     }
 
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 867225cb..59d38865 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -60,7 +60,7 @@ public class StopNode extends CFGNode {
         for( Node n : _inputs )
             if( n!=null )
                 d = Math.max(d,((CFGNode)n).idepth()+1);
-        return _idepth=d;
+        return cacheIDepth(d);
     }
     @Override public CFGNode idom(Node dep) { return null; }
 
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index d6f6bcd3..c5035381 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -7,6 +7,19 @@ 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 stop = new Parser(src).parse().iterate();
+            org.junit.Assert.assertTrue(body,
+                stop.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr);
+        }
+    }
+
+
 
     // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15.
     private static final String NULLABLE_POINT_SOURCE = """
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter12Test.java
index a70a5f33..e81f9845 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter12Test.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter12Test.java
@@ -8,6 +8,20 @@ import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
 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 stop = new Parser(src).parse().iterate();
+            assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString());
+        }
+    }
+
+
     @Test
     public void testJig() {
         Parser parser = new Parser(
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java
index 01d471bf..8ff33436 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java
@@ -26,7 +26,7 @@ public class PrintTestSupport {
             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,cfg._idepth);
+            if( n instanceof CFGNode cfg ) depths.put(n,(int)cfg._idepth);
         }
         print.run();
         for( Node n : nodes ) {