Unify mixed-return checking and results

Unify dominator caching.

3 files changed, 37 insertions, 21 deletions

diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java
index 39e8ff8d..44e8dfd2 100644
--- a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -54,7 +54,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.
@@ -380,13 +380,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/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index bb7998a3..9b51a277 100644
--- a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -55,21 +55,20 @@ 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 ) return _idom; // Return cached copy
-        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;
-        return (_idom=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;
     }
 }
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java
index c5a45876..6b98aed7 100644
--- a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -39,5 +39,6 @@ public class StartNode extends MultiNode {
     // No immediate dominator, and idepth==0
     @Override
     Node idom() { return null; }
+    @Override int idepth() { return 0; }
 
 }