diff options
Diffstat (limited to 'chapter09/src/main/java')
5 files changed, 40 insertions, 28 deletions
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 { * <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. @@ -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<nIns(); i++ ) + lca = in(i).domLCA(lca); + return lca; } // True if last input is null diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java index e399138b..1e3559ce 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter09/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; } } |