Unify mixed-return checking and results

Unify dominator caching.

9 files changed, 46 insertions, 25 deletions

diff --git a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
index 47616b51..1586b3c5 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
@@ -6,6 +6,16 @@ import java.util.HashMap;
 
 public class CodeGen {
 
+    // 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;
+    }
+
+
+
     public enum Phase {
         Parse, Opto, TypeCheck, Schedule, LocalSched, RegAlloc;
     }
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index d3ee62c3..f68043c4 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -140,7 +140,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 )
@@ -167,7 +167,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;
@@ -220,7 +220,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/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index b051b3ce..dc486549 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.CodeGen;
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.Utils;
@@ -47,21 +48,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 _idepth==0 ? (_idepth=idom().idepth()+1) : _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( 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/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
index 07a2b5a3..6d7aa323 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.CodeGen;
 import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.Utils;
@@ -73,6 +74,7 @@ public class CallEndNode extends CFGNode implements MultiNode {
                         fun.setDef(2,call.ctrl());  // Bypass the Call;
                         fun.ret().setDef(3,null);   // Return is folding also
                         IterPeeps.addAll(fun._outputs);
+                        CodeGen.CODE.invalidateIDepthCaches();
                         return this;
                     }
                 } else {
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java
index 1f0c76eb..5873f6b6 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java
@@ -78,8 +78,8 @@ public class FunNode extends RegionNode {
         return progress;
     }
 
-    // Bypass Region idom, always assume depth == 1, one more than Start
-    @Override public int idepth() { return (_idepth=1); }
+    // Unfolded functions are roots; inlining reconnects their depth to the caller.
+    @Override public int idepth() { return _folding ? super.idepth() : 1; }
     // Bypass Region idom, always assume idom is Start
     @Override public CFGNode idom(Node dep) { return cfg(1); }
 
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index f70a1012..097ddea7 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -24,7 +24,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 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/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index ea053c02..9a076dea 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -100,20 +100,19 @@ 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;
+        if( validIDepth() ) return _idepth;
+        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/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index e543f9ea..e516859b 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -77,8 +77,7 @@ public class ReturnNode extends CFGNode {
         return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress();
     }
 
-    // Gather parse-time return types for error reporting
-    private Type mt = Type.TOP;
+    // Remember parsed type kinds for diagnostics; the optimized expression decides validity.
     private boolean ti=false, tf=false, tp=false, tn=false;
 
     // Add a return exit to the current parsing function
@@ -87,7 +86,6 @@ public class ReturnNode extends CFGNode {
 
         // Gather parse-time return types for error reporting
         Type t = expr._type;
-        mt = mt.meet(t);
         ti |= t instanceof TypeInteger x;
         tf |= t instanceof TypeFloat   x;
         tp |= t instanceof TypeMemPtr  x;
@@ -113,7 +111,7 @@ public class ReturnNode extends CFGNode {
     }
 
     @Override public Parser.ParseException err() {
-        return mt==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null;
+        return expr()._type==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null;
     }
 
     static Parser.ParseException mixerr( boolean ti, boolean tf, boolean tp, boolean tn, Parser.Lexer loc ) {
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java
index feb8347f..cabb7393 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -54,10 +54,10 @@ 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 )
             d = Math.max(d,((ReturnNode)ret).idepth()+1);
-        return _idepth=d;
+        return cacheIDepth(d);
     }
 }