diff options
Diffstat (limited to 'chapter10/src/main/java/com')
3 files changed, 31 insertions, 20 deletions
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java index ea1489c4..a0ba973e 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -26,6 +26,6 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use entry in(1) instead of in(0) - @Override int idepth() { return _idepth(1); } + @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } @Override Node idom() { return entry(); } } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java index c4889231..718b930d 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java @@ -565,9 +565,28 @@ public abstract class Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - public int _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit - final int _idepth(int idx) { return _idepth==0 ? (_idepth=in(idx).idepth()+1) : _idepth; } - int idepth() { return _idepth(0); } + public char _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit + + // 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; + } + // Return the immediate dominator of this Node. Node idom() { return in(0); } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 42501118..f7a56503 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -91,27 +91,19 @@ public class RegionNode extends Node { // Immediate dominator of Region is a little more complicated. @Override int idepth() { if( _idepth!=0 ) return _idepth; - int d=0; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,n.idepth()); - return _idepth=d; + depth = Math.max(depth,n.idepth()+1); + return cacheIDepth(depth); } @Override Node idom() { - 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. - // Because this does not cache, it can be linear in the size of the program. - Node lhs = in(1); - Node rhs = in(2); - 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(); - } - 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 |