Unify mixed-return checking and results

Unify dominator caching.

5 files changed, 40 insertions, 28 deletions

diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index d270cb29..8fd955e9 100644
--- a/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -54,5 +54,6 @@ public class ConstantNode extends Node {
 
     // Dead control is its own idom root
     Node idom() { return null; }
+    @Override int idepth() { return 0; }
 
 }
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index c192bc20..fa9d871e 100644
--- a/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -25,5 +25,7 @@ public class LoopNode extends RegionNode {
         return inProgress() ? null : super.idealize();
     }
 
+    @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); }
+
     @Override Node idom() { return entry(); }
 }
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java
index 151cb6a7..3524ca81 100644
--- a/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -57,7 +57,7 @@ public abstract class Node {
      * <p>
      * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
      */
-    int _idepth;
+    char _idepth;
 
     /**
      * A private Global Static mutable counter, for unique node id generation.
@@ -586,13 +586,29 @@ public abstract class Node {
     }
 
     // Return the immediate dominator of this Node and compute dom tree depth.
-    Node idom() {
-        Node idom = in(0);
-        if( idom._idepth==0 ) idom.idom(); // Recursively set _idepth
-        if( _idepth==0 ) _idepth = idom._idepth+1;
-        return idom;
+    Node idom() { return in(0); }
+
+    // Find the lowest common ancestor in the current dominator tree.
+    Node domLCA(Node rhs) {
+        if( rhs==null ) return this;
+        Node lhs = this;
+        while( lhs != rhs ) {
+            if( lhs==null || rhs==null ) return null;
+            int comp = lhs.idepth() - rhs.idepth();
+            if( comp >= 0 ) lhs = lhs.idom();
+            if( comp <= 0 ) rhs = rhs.idom();
+        }
+        return lhs;
+    }
+
+    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;
     }
 
+
     // Make a shallow copy (same class) of this Node, with given inputs and
     // empty outputs and a new Node ID.  The original inputs are ignored.
     // Does not need to be implemented in isCFG() nodes.
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index c949c2b2..71bef275 100644
--- a/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -54,12 +54,10 @@ public class RegionNode extends Node {
                     if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() )
                         phi.delDef(path);
             }
-            _idom = null;       // Clear idom cache
             return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path);
         }
         // If down to a single input, become that input
         if( nIns()==2 && !hasPhi() ) {
-            _idom = null;       // Clear idom cache
             return in(1);       // Collapse if no Phis; 1-input Phis will collapse on their own
         }
         return null;
@@ -80,27 +78,21 @@ public class RegionNode extends Node {
     }
 
     // Immediate dominator of Region is a little more complicated.
-    private Node _idom;         // Immediate dominator cache
+    @Override int idepth() {
+        if( _idepth!=0 ) return _idepth;
+        int depth=0;
+        for( Node n : _inputs )
+            if( n!=null )
+                depth = Math.max(depth,n.idepth()+1);
+        return cacheIDepth(depth);
+    }
+
     @Override Node idom() {
-        if( _idom != null ) {
-            if( _idom.isDead() ) _idom=null;
-            else return _idom; // Return cached copy
-        }
-        if( nIns()==2 ) return in(1); // 1-input is that one input
-        if( nIns()!=3 ) return null;  // Fails for anything other than 2-inputs
-        // Walk the LHS & RHS idom trees in parallel until they match, or either fails
-        Node lhs = in(1).idom();
-        Node rhs = in(2).idom();
-        while( lhs != rhs ) {
-          if( lhs==null || rhs==null ) return null;
-          var comp = lhs._idepth - rhs._idepth;
-          if( comp >= 0 ) lhs = lhs.idom();
-          if( comp <= 0 ) rhs = rhs.idom();
-        }
-        if( lhs==null ) return null;
-        _idepth = lhs._idepth+1;
-        if( !IterPeeps.midAssert() ) _idom=lhs;
-        return lhs;
+        Node lca = null;
+        // Recompute from predecessors: CFG edits can change the dominator.
+        for( int i=1; i<nIns(); i++ )
+            lca = in(i).domLCA(lca);
+        return lca;
     }
 
     // True if last input is null
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java
index e399138b..1e3559ce 100644
--- a/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -42,5 +42,6 @@ public class StartNode extends MultiNode {
     // No immediate dominator, and idepth==0
     @Override
     Node idom() { return null; }
+    @Override int idepth() { return 0; }
 
 }