diff options
Diffstat (limited to 'chapter07/src/main/java/com')
4 files changed, 39 insertions, 21 deletions
diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 81f707ec..e4ef68a3 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -24,5 +24,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/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java index 941edaca..49c1e6a1 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter07/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. @@ -427,13 +427,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/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java index acaadaf1..e357796b 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -61,22 +61,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/chapter07/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/StartNode.java index 01f1485a..bab0f18c 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter07/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; } } |