Unify mixed-return checking and results

Unify dominator caching.

4 files changed, 39 insertions, 21 deletions

diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index c192bc20..fa9d871e 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter08/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/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java
index cffb41e4..ba64b059 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -55,7 +55,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.
@@ -429,13 +429,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/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index 453d028f..756b4e24 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -62,22 +62,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 ) 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;
     }
 
     // True if last input is null
diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 01f1485a..bab0f18c 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter08/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; }
 
 }