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. --- .../main/java/com/seaofnodes/simple/node/Node.java | 28 ++++++-- .../com/seaofnodes/simple/node/RegionNode.java | 29 ++++---- .../java/com/seaofnodes/simple/node/StartNode.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 | 29 ++++---- .../java/com/seaofnodes/simple/node/StartNode.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 | 29 ++++---- .../java/com/seaofnodes/simple/node/StartNode.java | 1 + .../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 + .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../main/java/com/seaofnodes/simple/node/Node.java | 25 ++++++- .../com/seaofnodes/simple/node/RegionNode.java | 24 +++---- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../com/seaofnodes/simple/GlobalCodeMotion.java | 4 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 15 +++-- .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 11 ++- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 2 +- .../com/seaofnodes/simple/GlobalCodeMotion.java | 4 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 19 ++++-- .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 11 ++- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 2 +- .../com/seaofnodes/simple/GlobalCodeMotion.java | 4 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 19 ++++-- .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 11 ++- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 2 +- .../com/seaofnodes/simple/GlobalCodeMotion.java | 4 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 19 ++++-- .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 11 ++- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 2 +- .../com/seaofnodes/simple/GlobalCodeMotion.java | 4 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 19 ++++-- .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 11 ++- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 2 +- .../com/seaofnodes/simple/GlobalCodeMotion.java | 4 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 19 ++++-- .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 11 ++- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 2 +- .../com/seaofnodes/simple/GlobalCodeMotion.java | 4 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 19 ++++-- .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 11 ++- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 2 +- .../main/java/com/seaofnodes/simple/CodeGen.java | 10 +++ .../com/seaofnodes/simple/GlobalCodeMotion.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 24 +++++-- .../com/seaofnodes/simple/node/CallEndNode.java | 2 + .../java/com/seaofnodes/simple/node/FunNode.java | 4 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 13 ++-- .../com/seaofnodes/simple/node/ReturnNode.java | 6 +- .../java/com/seaofnodes/simple/node/StopNode.java | 4 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 16 +++++ .../seaofnodes/simple/node/PrintTestSupport.java | 11 ++- .../main/java/com/seaofnodes/simple/CodeGen.java | 10 +++ .../com/seaofnodes/simple/GlobalCodeMotion.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 25 +++++-- .../com/seaofnodes/simple/node/CallEndNode.java | 1 + .../java/com/seaofnodes/simple/node/FunNode.java | 4 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 13 ++-- .../com/seaofnodes/simple/node/ReturnNode.java | 6 +- .../java/com/seaofnodes/simple/node/StopNode.java | 4 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 16 +++++ .../seaofnodes/simple/node/PrintTestSupport.java | 11 ++- .../com/seaofnodes/simple/codegen/CodeGen.java | 10 +++ .../simple/codegen/GlobalCodeMotion.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 26 ++++++-- .../com/seaofnodes/simple/node/CallEndNode.java | 1 + .../java/com/seaofnodes/simple/node/FunNode.java | 4 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 13 ++-- .../com/seaofnodes/simple/node/ReturnNode.java | 6 +- .../java/com/seaofnodes/simple/node/StopNode.java | 4 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 16 +++++ .../seaofnodes/simple/node/PrintTestSupport.java | 11 ++- .../com/seaofnodes/simple/codegen/CodeGen.java | 22 ++---- .../simple/codegen/GlobalCodeMotion.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 20 ++++-- .../java/com/seaofnodes/simple/node/FunNode.java | 4 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 4 +- .../com/seaofnodes/simple/node/RegionNode.java | 14 ++-- .../com/seaofnodes/simple/node/ReturnNode.java | 6 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 4 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 16 +++++ .../seaofnodes/simple/node/PrintTestSupport.java | 11 ++- .../com/seaofnodes/simple/codegen/CodeGen.java | 24 ++----- .../simple/codegen/GlobalCodeMotion.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 20 ++++-- .../java/com/seaofnodes/simple/node/FunNode.java | 4 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 4 +- .../com/seaofnodes/simple/node/RegionNode.java | 14 ++-- .../com/seaofnodes/simple/node/ReturnNode.java | 6 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 4 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 16 +++++ .../seaofnodes/simple/node/PrintTestSupport.java | 11 ++- .../com/seaofnodes/simple/codegen/CodeGen.java | 24 ++----- .../simple/codegen/GlobalCodeMotion.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 21 ++++-- .../java/com/seaofnodes/simple/node/FunNode.java | 4 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 4 +- .../com/seaofnodes/simple/node/RegionNode.java | 14 ++-- .../com/seaofnodes/simple/node/ReturnNode.java | 6 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 4 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 16 +++++ .../seaofnodes/simple/node/PrintTestSupport.java | 11 ++- .../com/seaofnodes/simple/codegen/CodeGen.java | 24 ++----- .../simple/codegen/GlobalCodeMotion.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 21 ++++-- .../java/com/seaofnodes/simple/node/FunNode.java | 4 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 4 +- .../com/seaofnodes/simple/node/RegionNode.java | 14 ++-- .../com/seaofnodes/simple/node/ReturnNode.java | 4 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 4 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 13 ++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 16 +++++ .../seaofnodes/simple/node/PrintTestSupport.java | 11 ++- .../main/java/com/seaofnodes/simple/IterPeeps.java | 4 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 24 ++----- .../simple/codegen/GlobalCodeMotion.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 21 ++++-- .../java/com/seaofnodes/simple/node/FunNode.java | 5 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 4 +- .../com/seaofnodes/simple/node/RegionNode.java | 14 ++-- .../com/seaofnodes/simple/node/StartCUNode.java | 2 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 4 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 15 +++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 14 ++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 16 +++++ .../seaofnodes/simple/node/PrintTestSupport.java | 9 +++ docs/chapter-backports.md | 78 ++++++++++++++++++---- skills/chapter25-codex-notes.md | 32 +++++++++ 189 files changed, 1381 insertions(+), 570 deletions(-) diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java index 39e8ff8d..44e8dfd2 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java @@ -54,7 +54,7 @@ public abstract class Node { *

* See {@link ...} */ - int _idepth; + char _idepth; /** * A private Global Static mutable counter, for unique node id generation. @@ -380,13 +380,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/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java index bb7998a3..9b51a277 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -55,21 +55,20 @@ 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 * See {@link ...} */ - 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 * See {@link ...} */ - 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 * 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 * See {@link ...} */ - 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 * See {@link ...} */ - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + public char _idepth; + public 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 and compute dom tree depth. public CFGNode idom() { return cfg(0); } // Return the LCA of two idoms - public CFGNode idom(CFGNode rhs) { + public CFGNode domLCA(CFGNode rhs) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); + 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(); } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java index c662dee6..45549f1d 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -28,7 +28,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + @Override public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom() { return entry(); } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java index dcc7ccef..060dfb45 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -92,19 +92,18 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { if( _idepth!=0 ) return _idepth; - int d=0; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom() { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i * See {@link ...} */ - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + public char _idepth; + public 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 and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom(); - if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); } return lhs; } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 22862cb9..a0e988dd 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -28,7 +28,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + @Override public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java index d5105614..fb934511 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -92,19 +92,18 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { if( _idepth!=0 ) return _idepth; - int d=0; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i * See {@link ...} */ - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + public char _idepth; + public 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 and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom(); - if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); } return lhs; } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 22862cb9..a0e988dd 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -28,7 +28,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + @Override public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/RegionNode.java index d5105614..fb934511 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -92,19 +92,18 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { if( _idepth!=0 ) return _idepth; - int d=0; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i * See {@link ...} */ - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + public char _idepth; + public 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 and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom(); - if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); } return lhs; } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 22862cb9..a0e988dd 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -28,7 +28,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + @Override public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java index d5105614..fb934511 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -92,19 +92,18 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { if( _idepth!=0 ) return _idepth; - int d=0; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i * See {@link ...} */ - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + public char _idepth; + public 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 and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom(); - if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); } return lhs; } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 22862cb9..a0e988dd 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -28,7 +28,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + @Override public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/RegionNode.java index bd05ce01..9e8b2611 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -147,19 +147,18 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { if( _idepth!=0 ) return _idepth; - int d=0; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i * See {@link ...} */ - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + public char _idepth; + public 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 and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom(); - if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); } return lhs; } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 22862cb9..a0e988dd 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -28,7 +28,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + @Override public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 941de76b..675d68ac 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -148,19 +148,18 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { if( _idepth!=0 ) return _idepth; - int d=0; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i * See {@link ...} */ - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + public char _idepth; + public 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 and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom(); - if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); } return lhs; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java index ecda9c63..8fb6a4ce 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -28,7 +28,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + @Override public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java index fb39af17..59da86ff 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -92,19 +92,18 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { if( _idepth!=0 ) return _idepth; - int d=0; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i * See {@link ...} */ - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + public char _idepth; + public char _idepthVersion; + public int idepth() { return validIDepth() ? _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"; + _idepthVersion = CodeGen.CODE.iDepthVersion(); + return _idepth = (char)depth; + } + + final boolean validIDepth() { return _idepth!=0 && _idepthVersion==CodeGen.CODE.iDepthVersion(); } + // Return the immediate dominator of this Node and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom(); - if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); } return lhs; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 07a2b5a3..6d7aa323 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; @@ -73,6 +74,7 @@ public class CallEndNode extends CFGNode implements MultiNode { fun.setDef(2,call.ctrl()); // Bypass the Call; fun.ret().setDef(3,null); // Return is folding also IterPeeps.addAll(fun._outputs); + CodeGen.CODE.invalidateIDepthCaches(); return this; } } else { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java index 1f0c76eb..5873f6b6 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -78,8 +78,8 @@ public class FunNode extends RegionNode { return progress; } - // Bypass Region idom, always assume depth == 1, one more than Start - @Override public int idepth() { return (_idepth=1); } + // Unfolded functions are roots; inlining reconnects their depth to the caller. + @Override public int idepth() { return _folding ? super.idepth() : 1; } // Bypass Region idom, always assume idom is Start @Override public CFGNode idom(Node dep) { return cfg(1); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java index f70a1012..097ddea7 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -24,7 +24,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + @Override public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java index ea053c02..9a076dea 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -100,20 +100,19 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { - if( _idepth!=0 ) return _idepth; - int d=0; + if( validIDepth() ) return _idepth; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i(); var outs = new IdentityHashMap(); var hashes = new IdentityHashMap(); + var versions = new IdentityHashMap(); var depths = new IdentityHashMap(); for( Node n : nodes ) { ins.put(n,n._inputs.toArray(new Node[0])); outs.put(n,n._outputs.toArray(new Node[0])); hashes.put(n,hash.getInt(n)); - if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + if( n instanceof CFGNode cfg ) { + depths.put(n,(int)cfg._idepth); + versions.put(n,(int)cfg._idepthVersion); + } } print.run(); for( Node n : nodes ) { assertEquals("hash of node "+n._nid,(int)hashes.get(n),hash.getInt(n)); - if( n instanceof CFGNode cfg ) assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + if( n instanceof CFGNode cfg ) { + assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + assertEquals("depth version of node "+n._nid,(int)versions.get(n),cfg._idepthVersion); + } assertEquals(ins.get(n).length,n.nIns()); assertEquals(outs.get(n).length,n.nOuts()); for( int i=0; i * See {@link ...} */ - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + public char _idepth; + public char _idepthVersion; + public int idepth() { return validIDepth() ? _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"; + _idepthVersion = CodeGen.CODE.iDepthVersion(); + return _idepth = (char)depth; + } + + final boolean validIDepth() { return _idepth!=0 && _idepthVersion==CodeGen.CODE.iDepthVersion(); } + // Return the immediate dominator of this Node and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom(); - if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); } return lhs; } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 46188ed5..e6aa9fe9 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -71,6 +71,7 @@ public class CallEndNode extends CFGNode implements MultiNode { fun.setDef(2,call.ctrl()); // Bypass the Call; fun.ret().setDef(3,null); // Return is folding also CodeGen.CODE.addAll(fun._outputs); + CodeGen.CODE.invalidateIDepthCaches(); return this; } } else { diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/FunNode.java index 506e7758..b514eba0 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -94,8 +94,8 @@ public class FunNode extends RegionNode { return null; } - // Bypass Region idom, always assume depth == 1, one more than Start - @Override public int idepth() { return (_idepth=1); } + // Unfolded functions are roots; inlining reconnects their depth to the caller. + @Override public int idepth() { return _folding ? super.idepth() : 1; } // Bypass Region idom, always assume idom is Start @Override public CFGNode idom(Node dep) { return cfg(1); } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 4004f87f..2978e0d0 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -65,7 +65,7 @@ public class LoadNode extends MemOpNode { for( Node memuse : mem._outputs ) // Find a prior load, has same mem,ptr,off but higher ctrl if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() && - cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier + cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier return ld; // Load-after-Store on same address, but bypassing provably unrelated diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/LoopNode.java index d2b0e36c..5482a737 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -25,7 +25,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + @Override public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 5d3db5c6..643b5f65 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -100,20 +100,19 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { - if( _idepth!=0 ) return _idepth; - int d=0; + if( validIDepth() ) return _idepth; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i(); var outs = new IdentityHashMap(); var hashes = new IdentityHashMap(); + var versions = new IdentityHashMap(); var depths = new IdentityHashMap(); for( Node n : nodes ) { ins.put(n,n._inputs.toArray(new Node[0])); outs.put(n,n._outputs.toArray(new Node[0])); hashes.put(n,hash.getInt(n)); - if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + if( n instanceof CFGNode cfg ) { + depths.put(n,(int)cfg._idepth); + versions.put(n,(int)cfg._idepthVersion); + } } print.run(); for( Node n : nodes ) { assertEquals("hash of node "+n._nid,(int)hashes.get(n),hash.getInt(n)); - if( n instanceof CFGNode cfg ) assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + if( n instanceof CFGNode cfg ) { + assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + assertEquals("depth version of node "+n._nid,(int)versions.get(n),cfg._idepthVersion); + } assertEquals(ins.get(n).length,n.nIns()); assertEquals(outs.get(n).length,n.nOuts()); for( int i=0; i * See {@link ...} */ - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + public char _idepth; + public char _idepthVersion; + public int idepth() { return validIDepth() ? _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"; + _idepthVersion = CodeGen.CODE.iDepthVersion(); + return _idepth = (char)depth; + } + + final boolean validIDepth() { return _idepth!=0 && _idepthVersion==CodeGen.CODE.iDepthVersion(); } + // Return the immediate dominator of this Node and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom(); - if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); } return lhs; } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 03a4462d..970045c5 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -81,6 +81,7 @@ public class CallEndNode extends CFGNode implements MultiNode { fun.setDef(2,call.ctrl()); // Bypass the Call; fun.ret().setDef(3,null); // Return is folding also CodeGen.CODE.addAll(fun._outputs); + CodeGen.CODE.invalidateIDepthCaches(); return this; } } else { diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/FunNode.java index 38aa83a0..99759bb0 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -109,8 +109,8 @@ public class FunNode extends RegionNode { return null; } - // Bypass Region idom, always assume depth == 1, one more than Start - @Override public int idepth() { return (_idepth=1); } + // Unfolded functions are roots; inlining reconnects their depth to the caller. + @Override public int idepth() { return _folding ? super.idepth() : 1; } // Bypass Region idom, always assume idom is Start @Override public CFGNode idom(Node dep) { return cfg(1); } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/LoadNode.java index b70a938d..b3263541 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -65,7 +65,7 @@ public class LoadNode extends MemOpNode { for( Node memuse : mem._outputs ) // Find a prior load, has same mem,ptr,off but higher ctrl if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() && - cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier + cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier return ld; // Load-after-Store on same address, but bypassing provably unrelated diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/LoopNode.java index d2b0e36c..5482a737 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -25,7 +25,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + @Override public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/RegionNode.java index fb6539ae..166ef4bf 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -100,20 +100,19 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { - if( _idepth!=0 ) return _idepth; - int d=0; + if( validIDepth() ) return _idepth; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i(); var outs = new IdentityHashMap(); var hashes = new IdentityHashMap(); + var versions = new IdentityHashMap(); var depths = new IdentityHashMap(); for( Node n : nodes ) { ins.put(n,n._inputs.toArray(new Node[0])); outs.put(n,n._outputs.toArray(new Node[0])); hashes.put(n,hash.getInt(n)); - if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + if( n instanceof CFGNode cfg ) { + depths.put(n,(int)cfg._idepth); + versions.put(n,(int)cfg._idepthVersion); + } } print.run(); for( Node n : nodes ) { assertEquals("hash of node "+n._nid,(int)hashes.get(n),hash.getInt(n)); - if( n instanceof CFGNode cfg ) assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + if( n instanceof CFGNode cfg ) { + assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + assertEquals("depth version of node "+n._nid,(int)versions.get(n),cfg._idepthVersion); + } assertEquals(ins.get(n).length,n.nIns()); assertEquals(outs.get(n).length,n.nOuts()); for( int i=0; i * See {@link ...} */ - public int _idepth; - public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); + public char _idepth; + public char _idepthVersion; + public int idepth() { return validIDepth() ? _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"; + _idepthVersion = CodeGen.CODE.iDepthVersion(); + return _idepth = (char)depth; } + final boolean validIDepth() { return _idepth!=0 && _idepthVersion==CodeGen.CODE.iDepthVersion(); } + + // Return the immediate dominator of this Node and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); if( comp >= 0 ) lhs = (dep==null ? lhs : dep.addDep(lhs)).idom(); if( comp <= 0 ) rhs = (dep==null ? rhs : dep.addDep(rhs)).idom(); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/FunNode.java index b41a7e54..384547fa 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -114,9 +114,7 @@ public class FunNode extends RegionNode { // Bypass Region idom, always assume depth == 1, one more than Start, // unless folding then just a ID on input#1 - @Override public int idepth() { - return _folding ? super.idepth() : CodeGen.CODE.iDepthAt(1); - } + @Override public int idepth() { return _folding ? super.idepth() : 1; } // Bypass Region idom, always assume idom is Start @Override public CFGNode idom(Node dep) { return cfg(1); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 6147de81..785ba62c 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -65,7 +65,7 @@ public class LoadNode extends MemOpNode { for( Node memuse : mem._outputs ) // Find a prior load, has same mem,ptr,off but higher ctrl if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() && - cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier + cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier return ld; // Load-after-Store on same address, but bypassing provably unrelated diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 2fa070bc..3d69b94d 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -26,9 +26,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); - } + public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 8f65d0e5..64747c63 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -141,21 +141,19 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { - if( CodeGen.CODE.validIDepth(_idepth) ) - return _idepth; - int d=0; + if( validIDepth() ) return _idepth; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,CodeGen.CODE.iDepthFrom(((CFGNode)n).idepth())); - return _idepth = d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i(); var outs = new IdentityHashMap(); var hashes = new IdentityHashMap(); + var versions = new IdentityHashMap(); var depths = new IdentityHashMap(); for( Node n : nodes ) { ins.put(n,n._inputs.toArray(new Node[0])); outs.put(n,n._outputs.toArray(new Node[0])); hashes.put(n,hash.getInt(n)); - if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + if( n instanceof CFGNode cfg ) { + depths.put(n,(int)cfg._idepth); + versions.put(n,(int)cfg._idepthVersion); + } } print.run(); for( Node n : nodes ) { assertEquals("hash of node "+n._nid,(int)hashes.get(n),hash.getInt(n)); - if( n instanceof CFGNode cfg ) assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + if( n instanceof CFGNode cfg ) { + assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + assertEquals("depth version of node "+n._nid,(int)versions.get(n),cfg._idepthVersion); + } assertEquals(ins.get(n).length,n.nIns()); assertEquals(outs.get(n).length,n.nOuts()); for( int i=0; i * See {@link ...} */ - public int _idepth; - public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); + public char _idepth; + public char _idepthVersion; + public int idepth() { return validIDepth() ? _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"; + _idepthVersion = CodeGen.CODE.iDepthVersion(); + return _idepth = (char)depth; } + final boolean validIDepth() { return _idepth!=0 && _idepthVersion==CodeGen.CODE.iDepthVersion(); } + + // Return the immediate dominator of this Node and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); if( comp >= 0 ) lhs = (dep==null ? lhs : dep.addDep(lhs)).idom(); if( comp <= 0 ) rhs = (dep==null ? rhs : dep.addDep(rhs)).idom(); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/FunNode.java index 81fa627a..c53807a6 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -121,9 +121,7 @@ public class FunNode extends RegionNode { // Bypass Region idom, always assume depth == 1, one more than Start, // unless folding then just a ID on input#1 - @Override public int idepth() { - return _folding ? super.idepth() : CodeGen.CODE.iDepthAt(1); - } + @Override public int idepth() { return _folding ? super.idepth() : 1; } // Bypass Region idom, always assume idom is Start @Override public CFGNode idom(Node dep) { return _folding && nIns()==3 ? cfg(2) : cfg(1); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java index eebe94a3..10de5e53 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -71,7 +71,7 @@ public class LoadNode extends MemOpNode { for( Node memuse : mem._outputs ) // Find a prior load, has same mem,ptr,off but higher ctrl if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() && - cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier + cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier return ld; // Load-after-Store on same address, but bypassing provably unrelated diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/LoopNode.java index ec9055dc..334ac686 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -26,9 +26,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); - } + @Override public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 8f65d0e5..64747c63 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -141,21 +141,19 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { - if( CodeGen.CODE.validIDepth(_idepth) ) - return _idepth; - int d=0; + if( validIDepth() ) return _idepth; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,CodeGen.CODE.iDepthFrom(((CFGNode)n).idepth())); - return _idepth = d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i(); var outs = new IdentityHashMap(); var hashes = new IdentityHashMap(); + var versions = new IdentityHashMap(); var depths = new IdentityHashMap(); for( Node n : nodes ) { ins.put(n,n._inputs.toArray(new Node[0])); outs.put(n,n._outputs.toArray(new Node[0])); hashes.put(n,hash.getInt(n)); - if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + if( n instanceof CFGNode cfg ) { + depths.put(n,(int)cfg._idepth); + versions.put(n,(int)cfg._idepthVersion); + } } print.run(); for( Node n : nodes ) { assertEquals("hash of node "+n._nid,(int)hashes.get(n),hash.getInt(n)); - if( n instanceof CFGNode cfg ) assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + if( n instanceof CFGNode cfg ) { + assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + assertEquals("depth version of node "+n._nid,(int)versions.get(n),cfg._idepthVersion); + } assertEquals(ins.get(n).length,n.nIns()); assertEquals(outs.get(n).length,n.nOuts()); for( int i=0; i * See {@link ...} */ - public int _idepth; - public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); + public char _idepth; + public char _idepthVersion; + public int idepth() { return validIDepth() ? _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"; + _idepthVersion = CodeGen.CODE.iDepthVersion(); + return _idepth = (char)depth; } + final boolean validIDepth() { return _idepth!=0 && _idepthVersion==CodeGen.CODE.iDepthVersion(); } + + // Return the immediate dominator of this Node and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); if( comp >= 0 ) lhs = (dep==null ? lhs : dep.addDep(lhs)).idom(); if( comp <= 0 ) rhs = (dep==null ? rhs : dep.addDep(rhs)).idom(); - if( lhs==null || rhs==null ) return null; } return lhs; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/FunNode.java index 4bd0fd97..3ef486f8 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -122,9 +122,7 @@ public class FunNode extends RegionNode { // Bypass Region idom, always assume depth == 1, one more than Start, // unless folding then just a ID on input#1 - @Override public int idepth() { - return _folding ? super.idepth() : CodeGen.CODE.iDepthAt(1); - } + @Override public int idepth() { return _folding ? super.idepth() : 1; } // Bypass Region idom, always assume idom is Start @Override public CFGNode idom(Node dep) { return _folding && nIns()==3 ? cfg(2) : (nIns()>1 ? cfg(1) : null); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java index b58ea498..ec6260c0 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -87,7 +87,7 @@ public class LoadNode extends MemOpNode { for( Node memuse : mem._outputs ) // Find a prior load, has same mem,ptr,off but higher ctrl if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() && - cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier + cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier return ld; // Load-after-Store on same address, but bypassing provably unrelated diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java index fc50e17f..6c69a56e 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -26,9 +26,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); - } + @Override public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 2b467a8c..42b23633 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -141,21 +141,19 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { - if( CodeGen.CODE.validIDepth(_idepth) ) - return _idepth; - int d=0; + if( validIDepth() ) return _idepth; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,CodeGen.CODE.iDepthFrom(((CFGNode)n).idepth())); - return _idepth = d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i(); var outs = new IdentityHashMap(); var hashes = new IdentityHashMap(); + var versions = new IdentityHashMap(); var depths = new IdentityHashMap(); for( Node n : nodes ) { ins.put(n,n._inputs.toArray(new Node[0])); outs.put(n,n._outputs.toArray(new Node[0])); hashes.put(n,hash.getInt(n)); - if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + if( n instanceof CFGNode cfg ) { + depths.put(n,(int)cfg._idepth); + versions.put(n,(int)cfg._idepthVersion); + } } print.run(); for( Node n : nodes ) { assertEquals("hash of node "+n._nid,(int)hashes.get(n),hash.getInt(n)); - if( n instanceof CFGNode cfg ) assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + if( n instanceof CFGNode cfg ) { + assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + assertEquals("depth version of node "+n._nid,(int)versions.get(n),cfg._idepthVersion); + } assertEquals(ins.get(n).length,n.nIns()); assertEquals(outs.get(n).length,n.nOuts()); for( int i=0; i * See {@link ...} */ - public int _idepth; - public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); + public char _idepth; + public char _idepthVersion; + public int idepth() { return validIDepth() ? _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"; + _idepthVersion = CodeGen.CODE.iDepthVersion(); + return _idepth = (char)depth; } + final boolean validIDepth() { return _idepth!=0 && _idepthVersion==CodeGen.CODE.iDepthVersion(); } + + // Return the immediate dominator of this Node and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); if( comp >= 0 ) lhs = (dep==null ? lhs : dep.addDep(lhs)).idom(); if( comp <= 0 ) rhs = (dep==null ? rhs : dep.addDep(rhs)).idom(); - if( lhs==null || rhs==null ) return null; } return lhs; } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/FunNode.java index 2931b9ea..a413689f 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -135,9 +135,7 @@ public class FunNode extends RegionNode { // Bypass Region idom, always assume depth == 1, one more than Start, // unless folding then just a ID on input#1 - @Override public int idepth() { - return _folding ? super.idepth() : CodeGen.CODE.iDepthAt(1); - } + @Override public int idepth() { return _folding ? super.idepth() : 1; } // Bypass Region idom, always assume idom is Start @Override public CFGNode idom(Node dep) { return _folding && nIns()==3 ? cfg(2) : (nIns()>1 ? cfg(1) : null); } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 58dbfc81..10fa9d43 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -99,7 +99,7 @@ public class LoadNode extends MemOpNode { for( Node memuse : mem._outputs ) // Find a prior load, has same mem,ptr,off but higher ctrl if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() && - cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier + cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier return ld; // Load-after-Store on same address, but bypassing provably unrelated diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/LoopNode.java index fc50e17f..6c69a56e 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -26,9 +26,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); - } + @Override public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/RegionNode.java index b115a260..e9c958ac 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -147,22 +147,20 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { - if( CodeGen.CODE.validIDepth(_idepth) ) - return _idepth; - int d=0; + if( validIDepth() ) return _idepth; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,CodeGen.CODE.iDepthFrom(((CFGNode)n).idepth())); - return _idepth = d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i(); var outs = new IdentityHashMap(); var hashes = new IdentityHashMap(); + var versions = new IdentityHashMap(); var depths = new IdentityHashMap(); for( Node n : nodes ) { ins.put(n,n._inputs.toArray(new Node[0])); outs.put(n,n._outputs.toArray(new Node[0])); hashes.put(n,hash.getInt(n)); - if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + if( n instanceof CFGNode cfg ) { + depths.put(n,(int)cfg._idepth); + versions.put(n,(int)cfg._idepthVersion); + } } print.run(); for( Node n : nodes ) { assertEquals("hash of node "+n._nid,(int)hashes.get(n),hash.getInt(n)); - if( n instanceof CFGNode cfg ) assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + if( n instanceof CFGNode cfg ) { + assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + assertEquals("depth version of node "+n._nid,(int)versions.get(n),cfg._idepthVersion); + } assertEquals(ins.get(n).length,n.nIns()); assertEquals(outs.get(n).length,n.nOuts()); for( int i=0; i= phi.region().nIns() ) return null; - found = phi.region().cfg(i)._idom(found,null); + found = phi.region().cfg(i).domLCA(found,null); } return found; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 2fccb5f3..317fff71 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -339,26 +339,12 @@ public class CodeGen { public int rpc( String clz ) { return _rpcs.next(clz); } - // idepths are cached and valid until *inserting* CFG edges (deleting is - // OK). This happens with inlining, which bumps the version to bulk - // invalidate the idepth caches. - private static final int IDEPTH_STRIDE = 1_000_000; - private int _iDepthVersion = 0; + // Inlining can insert CFG edges and invalidate cached depth ordering. + private char _iDepthVersion; + public char iDepthVersion() { return _iDepthVersion; } public void invalidateIDepthCaches() { + assert _iDepthVersion < Character.MAX_VALUE : "Dominator cache version exceeds 65535"; ++_iDepthVersion; - assert _iDepthVersion < IDEPTH_STRIDE; // Wrapped; needs a major hack to fix - } - public boolean validIDepth(int idepth) { - if( idepth==0 ) return false; - if( _iDepthVersion==0 ) return true; - return (idepth%IDEPTH_STRIDE)==_iDepthVersion; - } - public int iDepthAt(int idepth) { - return IDEPTH_STRIDE*idepth+_iDepthVersion; - } - public int iDepthFrom(int idepth) { - assert idepth==0 || validIDepth(idepth); - return idepth+IDEPTH_STRIDE; } // Popular visit bitset, declared here, so it gets reused all over @@ -1117,7 +1103,7 @@ public class CodeGen { if( _cfg==null ) return "no CFG"; SB sb = new SB(); for( CFGNode cfg : _cfg ) { - sb.fix(8,""+cfg._idepth); + sb.fix(8,""+(int)cfg._idepth); IRPrinter.printLine( cfg, sb ); } return sb.toString(); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 71c08d18..a72dde97 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -285,7 +285,7 @@ public abstract class GlobalCodeMotion { CFGNode lca = null; for( Node use : n._outputs ) if( use != null ) - lca = use_block(n,use, late)._idom(lca,null); + lca = use_block(n,use, late).domLCA(lca,null); // Loads may need anti-dependencies, raising their LCA if( n instanceof MemOpNode load && load._isLoad ) @@ -314,7 +314,7 @@ public abstract class GlobalCodeMotion { CFGNode found=null; for( int i=1; i * See {@link ...} */ - public int _idepth; - public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); + public char _idepth; + public char _idepthVersion; + public int idepth() { return validIDepth() ? _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"; + _idepthVersion = CodeGen.CODE.iDepthVersion(); + return _idepth = (char)depth; } + final boolean validIDepth() { return _idepth!=0 && _idepthVersion==CodeGen.CODE.iDepthVersion(); } + + // Return the immediate dominator of this Node and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); if( comp >= 0 ) lhs = (dep==null ? lhs : dep.addDep(lhs)).idom(); if( comp <= 0 ) rhs = (dep==null ? rhs : dep.addDep(rhs)).idom(); - if( lhs==null || rhs==null ) return null; } return lhs; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java index 274cc146..ddd637c9 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -197,10 +197,7 @@ public class FunNode extends RegionNode { // Bypass Region idom, always assume depth == 1, one more than Start, // unless folding - @Override public int idepth() { - if( _folding ) return super.idepth(); - return CodeGen.CODE.iDepthAt(1); - } + @Override public int idepth() { return _folding ? super.idepth() : 1; } // Bypass Region idom, always assume idom is Start @Override public CFGNode idom(Node dep) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java index f5b61048..fb93964a 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -141,7 +141,7 @@ public class LoadNode extends MemOpNode { for( Node memuse : mem._outputs ) // Find a prior load, has same mem,ptr,off but higher ctrl if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() && - cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() && // Higher control means load is legal earlier + cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() && // Higher control means load is legal earlier addDep(ld)._type.isa(_type) ) // and not rolling backwards return ld; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 42c76060..e8464353 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -25,9 +25,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); - } + @Override public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 81d0d6b9..32434850 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -148,22 +148,20 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { - if( CodeGen.CODE.validIDepth(_idepth) ) - return _idepth; - int d=0; + if( validIDepth() ) return _idepth; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,CodeGen.CODE.iDepthFrom(((CFGNode)n).idepth())); - return _idepth = d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // 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. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i strs ) { Serialize.gather(strs,_fname); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java index 7d2b2773..dc21e5eb 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -80,7 +80,7 @@ public class StartNode extends LoopNode implements MultiNode { @Override public Node idealize() { return null; } // No immediate dominator, and idepth==0 - @Override public int idepth() { return CodeGen.CODE.iDepthAt(0); } + @Override public int idepth() { return 0; } @Override public CFGNode idom(Node dep) { return null; } @Override public boolean eq( Node n ) { return true; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java index 45f5519e..b0bf8343 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -88,13 +88,13 @@ public class StopNode extends CFGNode { } @Override public int idepth() { - if( _idepth!=0 ) return _idepth; + if( validIDepth() ) return _idepth; int d=0; for( Node ret : _inputs ) // All public results are hooked on the Stop, including data // values, so must check CFG if( ret instanceof CFGNode cfg ) d = Math.max(d,cfg.idepth()+1); - return _idepth=d; + return cacheIDepth(d); } } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java index a96da02c..029e28b8 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,21 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter10Test { + @Test public void testDeadReferenceReturn() { + for( String body : new String[] { + "return new S; return 0;", + "if(1) return new S; else return 0;" + } ) { + String src = "struct S { int x; }; " + body; + var code = new CodeGen(src).parse().opto().typeCheck(); + // This chapter also has constructor/class-init Returns in the CompUnit. + var entry = (com.seaofnodes.simple.node.FunNode)code._start.uctrl(); + org.junit.Assert.assertTrue(body, + entry.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + private static final String NULLABLE_POINT_SOURCE = """ struct Point { int x; new Point = { int v -> x = v; }; }; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 85317644..4b2d48d8 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -5,6 +5,20 @@ import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter12Test { + @Test public void testDeadNumericReturns() { + for( String[] test : new String[][] { + {"if(1) return 7; else return 2.5;", "7"}, + {"if(0) return 7; else return 2.5;", "2.5"}, + {"return 7; return 2.5;", "7"}, + {"return 2.5; return 7;", "2.5"} + } ) { + String src = test[0]; + var code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals(src,test[1],Eval2.eval(code,0)); + } + } + + @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java index d7fd12ff..4cf19746 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -11,6 +11,22 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testReachableMixedReturns() { + for( String[] test : new String[][] { + {"if(arg) return 7; else return 2.5;", "No common type amongst int and f64"}, + {"struct S { int x; }; if(arg) return new S; else return 0;", + "No common type amongst int and reference"} + } ) { + try { + new CodeGen(test[0]).parse().opto().typeCheck(); + fail("Expected incompatible return types: " + test[0]); + } catch( Parser.ParseException e ) { + assertEquals("Cannot return generic scalar",e.getMessage()); + } + } + } + + @Test public void testPrintingForwardReferenceScope() throws Exception { new CodeGen("return 0;").parse(); var declared = TypeMemPtr.make(TypeStruct.make("PrintForward",true,true)); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 70d9071a..ceea1de5 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -21,15 +21,24 @@ public class PrintTestSupport { var ins = new IdentityHashMap(); var outs = new IdentityHashMap(); var hashes = new IdentityHashMap(); + var versions = new IdentityHashMap(); var depths = new IdentityHashMap(); for( Node n : nodes ) { ins.put(n,n._inputs.toArray(new Node[0])); outs.put(n,n._outputs.toArray(new Node[0])); hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) { + depths.put(n,(int)cfg._idepth); + versions.put(n,(int)cfg._idepthVersion); + } } print.run(); for( Node n : nodes ) { assertEquals("hash of node "+n._nid,(int)hashes.get(n),hash.getInt(n)); + if( n instanceof CFGNode cfg ) { + assertEquals("depth of node "+n._nid,(int)depths.get(n),cfg._idepth); + assertEquals("depth version of node "+n._nid,(int)versions.get(n),cfg._idepthVersion); + } assertEquals(ins.get(n).length,n.nIns()); assertEquals(outs.get(n).length,n.nOuts()); for( int i=0; i