From 6e59fc1b71f2098c8baf90a6c54e5a33b7291e94 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 19 Sep 2026 22:31:42 -0700 Subject: Unify mixed-return checking and results Unify dominator caching. --- .../com/seaofnodes/simple/node/ConstantNode.java | 1 + .../java/com/seaofnodes/simple/node/LoopNode.java | 2 ++ .../main/java/com/seaofnodes/simple/node/Node.java | 28 +++++++++++++---- .../com/seaofnodes/simple/node/RegionNode.java | 36 +++++++++------------- .../java/com/seaofnodes/simple/node/StartNode.java | 1 + 5 files changed, 40 insertions(+), 28 deletions(-) (limited to 'chapter09/src/main/java/com') 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 { *

* See {@link ...} */ - 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