diff options
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 { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - int _idepth; + char _idepth; /** * A private Global Static mutable counter, for unique node id generation. @@ -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<nIns(); i++ ) + lca = in(i).domLCA(lca); + return lca; } } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java index c5a45876..6b98aed7 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -39,5 +39,6 @@ public class StartNode extends MultiNode { // No immediate dominator, and idepth==0 @Override Node idom() { return null; } + @Override int idepth() { return 0; } } diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 81f707ec..e4ef68a3 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -24,5 +24,7 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } + @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } + @Override Node idom() { return entry(); } } diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java index 941edaca..49c1e6a1 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java @@ -54,7 +54,7 @@ public abstract class Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - int _idepth; + char _idepth; /** * A private Global Static mutable counter, for unique node id generation. @@ -427,13 +427,29 @@ public abstract class Node { } // Return the immediate dominator of this Node and compute dom tree depth. - Node idom() { - Node idom = in(0); - if( idom._idepth==0 ) idom.idom(); // Recursively set _idepth - if( _idepth==0 ) _idepth = idom._idepth+1; - return idom; + Node idom() { return in(0); } + + // Find the lowest common ancestor in the current dominator tree. + Node domLCA(Node rhs) { + if( rhs==null ) return this; + Node lhs = this; + while( lhs != rhs ) { + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + return lhs; + } + + int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); } + // Zero depth means uncached. Check before narrowing so overflow cannot wrap. + final int cacheIDepth(int depth) { + assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; + return _idepth = (char)depth; } + // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. // Does not need to be implemented in isCFG() nodes. diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java index acaadaf1..e357796b 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -61,22 +61,21 @@ public class RegionNode extends Node { } // Immediate dominator of Region is a little more complicated. - private Node _idom; // Immediate dominator cache + @Override int idepth() { + if( _idepth!=0 ) return _idepth; + int depth=0; + for( Node n : _inputs ) + if( n!=null ) + depth = Math.max(depth,n.idepth()+1); + return cacheIDepth(depth); + } + @Override Node idom() { - if( _idom != null ) return _idom; // Return cached copy - if( nIns()!=3 ) return null; // Fails for anything other than 2-inputs - // Walk the LHS & RHS idom trees in parallel until they match, or either fails - Node lhs = in(1).idom(); - Node rhs = in(2).idom(); - while( lhs != rhs ) { - if( lhs==null || rhs==null ) return null; - var comp = lhs._idepth - rhs._idepth; - if( comp >= 0 ) lhs = lhs.idom(); - if( comp <= 0 ) rhs = rhs.idom(); - } - if( lhs==null ) return null; - _idepth = lhs._idepth+1; - return (_idom=lhs); + Node lca = null; + // Recompute from predecessors: CFG edits can change the dominator. + for( int i=1; i<nIns(); i++ ) + lca = in(i).domLCA(lca); + return lca; } // True if last input is null diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/StartNode.java index 01f1485a..bab0f18c 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -42,5 +42,6 @@ public class StartNode extends MultiNode { // No immediate dominator, and idepth==0 @Override Node idom() { return null; } + @Override int idepth() { return 0; } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java index c192bc20..fa9d871e 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -25,5 +25,7 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } + @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } + @Override Node idom() { return entry(); } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java index cffb41e4..ba64b059 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java @@ -55,7 +55,7 @@ public abstract class Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - int _idepth; + char _idepth; /** * A private Global Static mutable counter, for unique node id generation. @@ -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<nIns(); i++ ) + lca = in(i).domLCA(lca); + return lca; } // True if last input is null diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/StartNode.java index 01f1485a..bab0f18c 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -42,5 +42,6 @@ public class StartNode extends MultiNode { // No immediate dominator, and idepth==0 @Override Node idom() { return null; } + @Override int idepth() { return 0; } } diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index d270cb29..8fd955e9 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -54,5 +54,6 @@ public class ConstantNode extends Node { // Dead control is its own idom root Node idom() { return null; } + @Override int idepth() { return 0; } } diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java index c192bc20..fa9d871e 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -25,5 +25,7 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } + @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } + @Override Node idom() { return entry(); } } diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java index 151cb6a7..3524ca81 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java @@ -57,7 +57,7 @@ public abstract class Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - int _idepth; + char _idepth; /** * A private Global Static mutable counter, for unique node id generation. @@ -586,13 +586,29 @@ public abstract class Node { } // Return the immediate dominator of this Node and compute dom tree depth. - Node idom() { - Node idom = in(0); - if( idom._idepth==0 ) idom.idom(); // Recursively set _idepth - if( _idepth==0 ) _idepth = idom._idepth+1; - return idom; + Node idom() { return in(0); } + + // Find the lowest common ancestor in the current dominator tree. + Node domLCA(Node rhs) { + if( rhs==null ) return this; + Node lhs = this; + while( lhs != rhs ) { + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + return lhs; + } + + int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); } + // Zero depth means uncached. Check before narrowing so overflow cannot wrap. + final int cacheIDepth(int depth) { + assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; + return _idepth = (char)depth; } + // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. // Does not need to be implemented in isCFG() nodes. diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java index c949c2b2..71bef275 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -54,12 +54,10 @@ public class RegionNode extends Node { if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() ) phi.delDef(path); } - _idom = null; // Clear idom cache return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path); } // If down to a single input, become that input if( nIns()==2 && !hasPhi() ) { - _idom = null; // Clear idom cache return in(1); // Collapse if no Phis; 1-input Phis will collapse on their own } return null; @@ -80,27 +78,21 @@ public class RegionNode extends Node { } // Immediate dominator of Region is a little more complicated. - private Node _idom; // Immediate dominator cache + @Override int idepth() { + if( _idepth!=0 ) return _idepth; + int depth=0; + for( Node n : _inputs ) + if( n!=null ) + depth = Math.max(depth,n.idepth()+1); + return cacheIDepth(depth); + } + @Override Node idom() { - if( _idom != null ) { - if( _idom.isDead() ) _idom=null; - else return _idom; // Return cached copy - } - if( nIns()==2 ) return in(1); // 1-input is that one input - if( nIns()!=3 ) return null; // Fails for anything other than 2-inputs - // Walk the LHS & RHS idom trees in parallel until they match, or either fails - Node lhs = in(1).idom(); - Node rhs = in(2).idom(); - while( lhs != rhs ) { - if( lhs==null || rhs==null ) return null; - var comp = lhs._idepth - rhs._idepth; - if( comp >= 0 ) lhs = lhs.idom(); - if( comp <= 0 ) rhs = rhs.idom(); - } - if( lhs==null ) return null; - _idepth = lhs._idepth+1; - if( !IterPeeps.midAssert() ) _idom=lhs; - return lhs; + Node lca = null; + // Recompute from predecessors: CFG edits can change the dominator. + for( int i=1; i<nIns(); i++ ) + lca = in(i).domLCA(lca); + return lca; } // True if last input is null diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java index e399138b..1e3559ce 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -42,5 +42,6 @@ public class StartNode extends MultiNode { // No immediate dominator, and idepth==0 @Override Node idom() { return null; } + @Override int idepth() { return 0; } } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java index ea1489c4..a0ba973e 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -26,6 +26,6 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use entry in(1) instead of in(0) - @Override int idepth() { return _idepth(1); } + @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } @Override Node idom() { return entry(); } } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java index c4889231..718b930d 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java @@ -565,9 +565,28 @@ public abstract class Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - public int _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit - final int _idepth(int idx) { return _idepth==0 ? (_idepth=in(idx).idepth()+1) : _idepth; } - int idepth() { return _idepth(0); } + public char _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit + + // Find the lowest common ancestor in the current dominator tree. + Node domLCA(Node rhs) { + if( rhs==null ) return this; + Node lhs = this; + while( lhs != rhs ) { + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + return lhs; + } + + int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); } + // Zero depth means uncached. Check before narrowing so overflow cannot wrap. + final int cacheIDepth(int depth) { + assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; + return _idepth = (char)depth; + } + // Return the immediate dominator of this Node. Node idom() { return in(0); } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 42501118..f7a56503 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -91,27 +91,19 @@ public class RegionNode extends Node { // Immediate dominator of Region is a little more complicated. @Override int idepth() { if( _idepth!=0 ) return _idepth; - int d=0; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,n.idepth()); - return _idepth=d; + depth = Math.max(depth,n.idepth()+1); + return cacheIDepth(depth); } @Override Node idom() { - if( nIns()==2 ) return in(1); // 1-input is that one input - if( nIns()!=3 ) return null; // Fails for anything other than 2-inputs - // Walk the LHS & RHS idom trees in parallel until they match, or either fails. - // Because this does not cache, it can be linear in the size of the program. - Node lhs = in(1); - Node rhs = in(2); - while( lhs != rhs ) { - if( lhs==null || rhs==null ) return null; - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = lhs.idom(); - if( comp <= 0 ) rhs = rhs.idom(); - } - return lhs; + Node lca = null; + // Recompute from predecessors: CFG edits can change the dominator. + for( int i=1; i<nIns(); i++ ) + lca = in(i).domLCA(lca); + return lca; } // True if last input is null diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java index c39c19b3..527999c2 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -11,6 +11,19 @@ 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 stop = new Parser(src).parse().iterate(); + org.junit.Assert.assertTrue(body, + stop.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 14540d46..99f2f0ea 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -148,7 +148,7 @@ public abstract class GlobalCodeMotion { assert early != null; CFGNode lca = null; for( Node use : n._outputs ) - lca = use_block(n,use, late).idom(lca); + lca = use_block(n,use, late).domLCA(lca); // Loads may need anti-dependencies, raising their LCA if( n instanceof LoadNode load ) @@ -226,7 +226,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk.idom(lca); // Raise Loads LCA + lca = stblk.domLCA(lca); // Raise Loads LCA if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java index b605071b..e02dd1e1 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -48,18 +48,25 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i).idom(lca); + lca = cfg(i).domLCA(lca); return lca; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java index 94b2ad6d..2bef4f50 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -57,7 +57,7 @@ public class StopNode extends CFGNode { for( Node n : _inputs ) if( n!=null ) d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } @Override public CFGNode idom() { return null; } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 6969358d..3e97e8e7 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,19 @@ 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 stop = new Parser(src).parse().iterate(); + org.junit.Assert.assertTrue(body, + stop.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter11/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter11/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..8ff33436 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -26,7 +26,7 @@ public class PrintTestSupport { 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); } print.run(); for( Node n : nodes ) { diff --git a/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 4e0a31d5..c44503ae 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -147,7 +147,7 @@ public abstract class GlobalCodeMotion { assert early != null; CFGNode lca = null; for( Node use : n._outputs ) - 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 LoadNode load ) @@ -226,7 +226,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 07ba0fa4..07ff0b15 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -48,21 +48,28 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java index ab567bae..fe96bd2a 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -57,7 +57,7 @@ public class StopNode extends CFGNode { for( Node n : _inputs ) if( n!=null ) d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } @Override public CFGNode idom(Node dep) { return null; } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 6f8a6b3b..fae91067 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -11,6 +11,19 @@ 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 stop = new Parser(src).parse().iterate(); + org.junit.Assert.assertTrue(body, + stop.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java index af8fdfe9..00b2591c 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -9,6 +9,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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 stop = new Parser(src).parse().iterate(); + assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString()); + } + } + + @Test public void testJig() { Parser parser = new Parser( diff --git a/chapter12/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter12/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..8ff33436 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -26,7 +26,7 @@ public class PrintTestSupport { 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); } print.run(); for( Node n : nodes ) { diff --git a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 8a96e69c..865f7036 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -174,7 +174,7 @@ public abstract class GlobalCodeMotion { assert early != null; CFGNode lca = null; for( Node use : n._outputs ) - 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 LoadNode load ) @@ -248,7 +248,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 07ba0fa4..07ff0b15 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -48,21 +48,28 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/StopNode.java index 0eacc1f4..d5b00011 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -59,7 +59,7 @@ public class StopNode extends CFGNode { for( Node n : _inputs ) if( n!=null ) d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } @Override public CFGNode idom(Node dep) { return null; } diff --git a/chapter13/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter13/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 124cea6d..e790d34d 100644 --- a/chapter13/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter13/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,19 @@ 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 stop = new Parser(src).parse().iterate(); + org.junit.Assert.assertTrue(body, + stop.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter13/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter13/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 62dce12b..f9f3a5da 100644 --- a/chapter13/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter13/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -8,6 +8,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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 stop = new Parser(src).parse().iterate(); + assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString()); + } + } + + @Test public void testJig() { Parser parser = new Parser( diff --git a/chapter13/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter13/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..8ff33436 100644 --- a/chapter13/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter13/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -26,7 +26,7 @@ public class PrintTestSupport { 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); } print.run(); for( Node n : nodes ) { diff --git a/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 8a96e69c..865f7036 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -174,7 +174,7 @@ public abstract class GlobalCodeMotion { assert early != null; CFGNode lca = null; for( Node use : n._outputs ) - 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 LoadNode load ) @@ -248,7 +248,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 07ba0fa4..07ff0b15 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -48,21 +48,28 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/StopNode.java index 0eacc1f4..d5b00011 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -59,7 +59,7 @@ public class StopNode extends CFGNode { for( Node n : _inputs ) if( n!=null ) d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } @Override public CFGNode idom(Node dep) { return null; } diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter10Test.java index bfe3b1d3..31220334 100644 --- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,19 @@ 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 stop = new Parser(src).parse().iterate(); + org.junit.Assert.assertTrue(body, + stop.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 972118be..61b1f490 100644 --- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -8,6 +8,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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 stop = new Parser(src).parse().iterate(); + assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString()); + } + } + + @Test public void testJig() { Parser parser = new Parser( diff --git a/chapter14/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter14/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..8ff33436 100644 --- a/chapter14/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter14/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -26,7 +26,7 @@ public class PrintTestSupport { 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); } print.run(); for( Node n : nodes ) { diff --git a/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 2eac6ccc..27f69c42 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -170,7 +170,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 LoadNode load ) @@ -248,7 +248,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 9e9d6970..704dea8d 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -45,21 +45,28 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/StopNode.java index 0eacc1f4..d5b00011 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -59,7 +59,7 @@ public class StopNode extends CFGNode { for( Node n : _inputs ) if( n!=null ) d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } @Override public CFGNode idom(Node dep) { return null; } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java index cf817b28..b737762e 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,19 @@ 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 stop = new Parser(src).parse().iterate(); + org.junit.Assert.assertTrue(body, + stop.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 2a637ce6..c8802f4c 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -8,6 +8,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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 stop = new Parser(src).parse().iterate(); + assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString()); + } + } + + @Test public void testJig() { Parser parser = new Parser( diff --git a/chapter15/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter15/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..8ff33436 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -26,7 +26,7 @@ public class PrintTestSupport { 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); } print.run(); for( Node n : nodes ) { diff --git a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 29841266..6a4728c3 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -175,7 +175,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 LoadNode load ) @@ -254,7 +254,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk; stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( !(stblk instanceof IfNode) && stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 9e9d6970..704dea8d 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -45,21 +45,28 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/StopNode.java index 0eacc1f4..d5b00011 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -59,7 +59,7 @@ public class StopNode extends CFGNode { for( Node n : _inputs ) if( n!=null ) d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } @Override public CFGNode idom(Node dep) { return null; } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java index ccc09dcb..a40dbe90 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -7,6 +7,19 @@ 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 stop = new Parser(src).parse().iterate(); + org.junit.Assert.assertTrue(body, + stop.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter12Test.java index c0f6266a..4db27407 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -8,6 +8,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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 stop = new Parser(src).parse().iterate(); + assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString()); + } + } + + @Test public void testJig() { Parser parser = new Parser( diff --git a/chapter16/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter16/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..8ff33436 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -26,7 +26,7 @@ public class PrintTestSupport { 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); } print.run(); for( Node n : nodes ) { diff --git a/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 9698abd9..8cfbe509 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -137,7 +137,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 LoadNode load ) @@ -216,7 +216,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 052ad8fc..8e063205 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -36,21 +36,28 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java index 867225cb..59d38865 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -60,7 +60,7 @@ public class StopNode extends CFGNode { for( Node n : _inputs ) if( n!=null ) d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } @Override public CFGNode idom(Node dep) { return null; } diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java index d6f6bcd3..c5035381 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -7,6 +7,19 @@ 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 stop = new Parser(src).parse().iterate(); + org.junit.Assert.assertTrue(body, + stop.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter12Test.java index a70a5f33..e81f9845 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -8,6 +8,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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 stop = new Parser(src).parse().iterate(); + assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString()); + } + } + + @Test public void testJig() { Parser parser = new Parser( diff --git a/chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..8ff33436 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -26,7 +26,7 @@ public class PrintTestSupport { 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); } print.run(); for( Node n : nodes ) { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java index 47616b51..1586b3c5 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java @@ -6,6 +6,16 @@ import java.util.HashMap; public class CodeGen { + // 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; + } + + + public enum Phase { Parse, Opto, TypeCheck, Schedule, LocalSched, RegAlloc; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index d3ee62c3..f68043c4 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -140,7 +140,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 LoadNode load ) @@ -167,7 +167,7 @@ public abstract class GlobalCodeMotion { CFGNode found=null; for( int i=1; i<phi.nIns(); i++ ) if( phi.in(i)==n ) - found = phi.region().cfg(i)._idom(found,null); + found = phi.region().cfg(i).domLCA(found,null); assert found!=null; return found; @@ -220,7 +220,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java index b051b3ce..dc486549 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.Utils; @@ -47,21 +48,32 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index e543f9ea..e516859b 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -77,8 +77,7 @@ public class ReturnNode extends CFGNode { return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress(); } - // Gather parse-time return types for error reporting - private Type mt = Type.TOP; + // Remember parsed type kinds for diagnostics; the optimized expression decides validity. private boolean ti=false, tf=false, tp=false, tn=false; // Add a return exit to the current parsing function @@ -87,7 +86,6 @@ public class ReturnNode extends CFGNode { // Gather parse-time return types for error reporting Type t = expr._type; - mt = mt.meet(t); ti |= t instanceof TypeInteger x; tf |= t instanceof TypeFloat x; tp |= t instanceof TypeMemPtr x; @@ -113,7 +111,7 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { - return mt==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; + return expr()._type==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; } static Parser.ParseException mixerr( boolean ti, boolean tf, boolean tp, boolean tn, Parser.Lexer loc ) { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java index feb8347f..cabb7393 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -54,10 +54,10 @@ 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 ) d = Math.max(d,((ReturnNode)ret).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 42684416..378e4f40 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -5,6 +5,19 @@ 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(); + org.junit.Assert.assertTrue(body, + code.expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 21df8205..43345809 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -8,6 +8,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java index f9be0e93..e4a9e409 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -9,6 +9,22 @@ import static org.junit.Assert.fail; import org.junit.Ignore; 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(test[1],e.getMessage()); + } + } + } + + @Test public void testPrintingForwardReferenceScope() throws Exception { new CodeGen("return 0;").parse(); var declared = TypeMemPtr.make(TypeStruct.makeFRef("PrintForward")); diff --git a/chapter18/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter18/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..ceea1de5 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -21,17 +21,24 @@ public class PrintTestSupport { var ins = new IdentityHashMap<Node,Node[]>(); var outs = new IdentityHashMap<Node,Node[]>(); var hashes = new IdentityHashMap<Node,Integer>(); + var versions = new IdentityHashMap<Node,Integer>(); var depths = new IdentityHashMap<Node,Integer>(); 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); diff --git a/chapter19/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter19/src/main/java/com/seaofnodes/simple/CodeGen.java index eb8dd4aa..e966200c 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/CodeGen.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/CodeGen.java @@ -8,6 +8,16 @@ import java.util.HashMap; import java.util.IdentityHashMap; public class CodeGen { + + // 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; + } + + // Last created CodeGen as a global; used all over to avoid passing about a // "context". public static CodeGen CODE; diff --git a/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 12dd9243..1ad7d29b 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -149,7 +149,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 LoadNode load ) @@ -176,7 +176,7 @@ public abstract class GlobalCodeMotion { CFGNode found=null; for( int i=1; i<phi.nIns(); i++ ) if( phi.in(i)==n ) - found = phi.region().cfg(i)._idom(found,null); + found = phi.region().cfg(i).domLCA(found,null); assert found!=null; return found; @@ -229,7 +229,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 174725f5..d2e70cd7 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; @@ -25,6 +26,7 @@ public abstract class CFGNode extends Node { public CFGNode(CFGNode cfg) { super(cfg); _idepth = cfg._idepth; + _idepthVersion = cfg._idepthVersion; _ltree = cfg._ltree; _pre = cfg._pre; } @@ -53,21 +55,32 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 20b6c7b9..4ca8131a 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -78,8 +78,7 @@ public class ReturnNode extends CFGNode { return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress(); } - // Gather parse-time return types for error reporting - private Type mt = Type.TOP; + // Remember parsed type kinds for diagnostics; the optimized expression decides validity. private boolean ti=false, tf=false, tp=false, tn=false; // Add a return exit to the current parsing function @@ -88,7 +87,6 @@ public class ReturnNode extends CFGNode { // Gather parse-time return types for error reporting Type t = expr._type; - mt = mt.meet(t); ti |= t instanceof TypeInteger x; tf |= t instanceof TypeFloat x; tp |= t instanceof TypeMemPtr x; @@ -114,7 +112,7 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { - return expr()._type/*mt*/==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; + return expr()._type==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; } static Parser.ParseException mixerr( boolean ti, boolean tf, boolean tp, boolean tn, Parser.Lexer loc ) { diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/StopNode.java index 6aaba3b3..0992c4de 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -55,10 +55,10 @@ 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 ) d = Math.max(d,((ReturnNode)ret).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } } diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 42684416..378e4f40 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -5,6 +5,19 @@ 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(); + org.junit.Assert.assertTrue(body, + code.expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 21df8205..43345809 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -8,6 +8,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 31a4f82e..05364d49 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -9,6 +9,22 @@ import static org.junit.Assert.fail; import org.junit.Ignore; 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(test[1],e.getMessage()); + } + } + } + + @Test public void testPrintingForwardReferenceScope() throws Exception { new CodeGen("return 0;").parse(); var declared = TypeMemPtr.make(TypeStruct.makeFRef("PrintForward")); diff --git a/chapter19/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter19/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..ceea1de5 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -21,17 +21,24 @@ public class PrintTestSupport { var ins = new IdentityHashMap<Node,Node[]>(); var outs = new IdentityHashMap<Node,Node[]>(); var hashes = new IdentityHashMap<Node,Integer>(); + var versions = new IdentityHashMap<Node,Integer>(); var depths = new IdentityHashMap<Node,Integer>(); 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index a1294890..b6efcf42 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -9,6 +9,16 @@ import java.util.HashMap; import java.util.IdentityHashMap; public class CodeGen { + + // 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; + } + + // Last created CodeGen as a global; used all over to avoid passing about a // "context". public static CodeGen CODE; diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 11c2b061..02f40974 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -189,7 +189,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 LoadNode load ) @@ -216,7 +216,7 @@ public abstract class GlobalCodeMotion { CFGNode found=null; for( int i=1; i<phi.nIns(); i++ ) if( phi.in(i)==n ) - found = phi.region().cfg(i)._idom(found,null); + found = phi.region().cfg(i).domLCA(found,null); assert found!=null; return found; @@ -269,7 +269,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 37d08fb0..8638d581 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.codegen.CodeGen; + import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; @@ -35,6 +37,7 @@ public abstract class CFGNode extends Node { super(cfg); if( cfg != null ) { _idepth = cfg._idepth; + _idepthVersion = cfg._idepthVersion; _ltree = cfg._ltree; _pre = cfg._pre; } @@ -64,21 +67,32 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 809dd1e1..0220b571 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -79,8 +79,7 @@ public class ReturnNode extends CFGNode { return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress(); } - // Gather parse-time return types for error reporting - private Type mt = Type.TOP; + // Remember parsed type kinds for diagnostics; the optimized expression decides validity. private boolean ti=false, tf=false, tp=false, tn=false; // Add a return exit to the current parsing function @@ -89,7 +88,6 @@ public class ReturnNode extends CFGNode { // Gather parse-time return types for error reporting Type t = expr._type; - mt = mt.meet(t); ti |= t instanceof TypeInteger x; tf |= t instanceof TypeFloat x; tp |= t instanceof TypeMemPtr x; @@ -115,7 +113,7 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { - return expr()._type/*mt*/==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; + return expr()._type==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; } static Parser.ParseException mixerr( boolean ti, boolean tf, boolean tp, boolean tn, Parser.Lexer loc ) { diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/StopNode.java index b4cb002b..80c911ca 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -55,10 +55,10 @@ 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 ) d = Math.max(d,((ReturnNode)ret).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java index e2cbf331..58ca9f5a 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,19 @@ 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(); + org.junit.Assert.assertTrue(body, + code.expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 8069ddaa..21759b78 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -7,6 +7,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 48b96588..8d612ae3 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -10,6 +10,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(test[1],e.getMessage()); + } + } + } + + @Test public void testPrintingForwardReferenceScope() throws Exception { new CodeGen("return 0;").parse(); var declared = TypeMemPtr.make(TypeStruct.makeFRef("PrintForward")); diff --git a/chapter20/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter20/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..ceea1de5 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -21,17 +21,24 @@ public class PrintTestSupport { var ins = new IdentityHashMap<Node,Node[]>(); var outs = new IdentityHashMap<Node,Node[]>(); var hashes = new IdentityHashMap<Node,Integer>(); + var versions = new IdentityHashMap<Node,Integer>(); var depths = new IdentityHashMap<Node,Integer>(); 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 9ec3bc7b..029e149b 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -87,22 +87,12 @@ public class CodeGen { public int getALIAS() { return _alias++; } - // 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 int _iDepthVersion = 0; - public void invalidateIDepthCaches() { _iDepthVersion++; } - public boolean validIDepth(int idepth) { - if( idepth==0 ) return false; - if( _iDepthVersion==0 ) return true; - return (idepth%100)==_iDepthVersion; - } - public int iDepthAt(int idepth) { - return 100*idepth+_iDepthVersion; - } - public int iDepthFrom(int idepth) { - assert idepth==0 || validIDepth(idepth); - return idepth+100; + // 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; } // Popular visit bitset, declared here, so it gets reused all over diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 40f827ec..da045925 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -196,7 +196,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 ) @@ -250,7 +250,7 @@ public abstract class GlobalCodeMotion { CFGNode found=null; for( int i=1; i<phi.nIns(); i++ ) if( phi.in(i)==n ) - found = phi.region().cfg(i)._idom(found,null); + found = phi.region().cfg(i).domLCA(found,null); assert found!=null; return found; @@ -304,7 +304,7 @@ public abstract class GlobalCodeMotion { private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 7877f93a..6f533ae0 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -36,6 +36,7 @@ public abstract class CFGNode extends Node { super(cfg); if( cfg != null ) { _idepth = cfg._idepth; + _idepthVersion = cfg._idepthVersion; _ltree = cfg._ltree; _pre = cfg._pre; } @@ -72,21 +73,30 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 317f4ce8..929deefd 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -82,8 +82,7 @@ public class ReturnNode extends CFGNode { return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress(); } - // Gather parse-time return types for error reporting - private Type mt = Type.TOP; + // Remember parsed type kinds for diagnostics; the optimized expression decides validity. private boolean ti=false, tf=false, tp=false, tn=false; // Add a return exit to the current parsing function @@ -92,7 +91,6 @@ public class ReturnNode extends CFGNode { // Gather parse-time return types for error reporting Type t = expr._type; - mt = mt.meet(t); ti |= t instanceof TypeInteger x; tf |= t instanceof TypeFloat x; tp |= t instanceof TypeMemPtr x; @@ -118,7 +116,7 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { - return expr()._type/*mt*/==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; + return expr()._type==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; } static Parser.ParseException mixerr( boolean ti, boolean tf, boolean tp, boolean tn, Parser.Lexer loc ) { diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java index f40203b4..4bd76f50 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -51,7 +51,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; } } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/StopNode.java index 9be08ad9..d381e716 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -56,10 +56,10 @@ 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 ) d = Math.max(d,((ReturnNode)ret).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java index e2cbf331..58ca9f5a 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,19 @@ 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(); + org.junit.Assert.assertTrue(body, + code.expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 8069ddaa..21759b78 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -7,6 +7,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java index b4f6c6ba..d5d5c2ef 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter21/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(test[1],e.getMessage()); + } + } + } + + @Test public void testPrintingForwardReferenceScope() throws Exception { new CodeGen("return 0;").parse(); var declared = TypeMemPtr.make(TypeStruct.makeFRef("PrintForward")); diff --git a/chapter21/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter21/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..ceea1de5 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -21,17 +21,24 @@ public class PrintTestSupport { var ins = new IdentityHashMap<Node,Node[]>(); var outs = new IdentityHashMap<Node,Node[]>(); var hashes = new IdentityHashMap<Node,Integer>(); + var versions = new IdentityHashMap<Node,Integer>(); var depths = new IdentityHashMap<Node,Integer>(); 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index adb71413..1726695f 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -89,22 +89,12 @@ public class CodeGen { public int getALIAS() { return _alias++; } - // 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 int _iDepthVersion = 0; - public void invalidateIDepthCaches() { _iDepthVersion++; } - public boolean validIDepth(int idepth) { - if( idepth==0 ) return false; - if( _iDepthVersion==0 ) return true; - return (idepth%100)==_iDepthVersion; - } - public int iDepthAt(int idepth) { - return 100*idepth+_iDepthVersion; - } - public int iDepthFrom(int idepth) { - assert idepth==0 || validIDepth(idepth); - return idepth+100; + // 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; } // Popular visit bitset, declared here, so it gets reused all over @@ -462,7 +452,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/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 04a119c2..1542c04d 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -203,7 +203,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 ) @@ -257,7 +257,7 @@ public abstract class GlobalCodeMotion { CFGNode found=null; for( int i=1; i<phi.nIns(); i++ ) if( phi.in(i)==n ) - found = phi.region().cfg(i)._idom(found,null); + found = phi.region().cfg(i).domLCA(found,null); assert found!=null; return found; @@ -311,7 +311,7 @@ public abstract class GlobalCodeMotion { private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 1dddc171..cad3b5e2 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -36,6 +36,7 @@ public abstract class CFGNode extends Node { super(cfg); if( cfg != null ) { _idepth = cfg._idepth; + _idepthVersion = cfg._idepthVersion; _ltree = cfg._ltree; _pre = cfg._pre; } @@ -72,21 +73,30 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index b4173871..618c8afa 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -81,8 +81,7 @@ public class ReturnNode extends CFGNode { return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress(); } - // Gather parse-time return types for error reporting - private Type mt = Type.TOP; + // Remember parsed type kinds for diagnostics; the optimized expression decides validity. private boolean ti=false, tf=false, tp=false, tn=false; // Add a return exit to the current parsing function @@ -91,7 +90,6 @@ public class ReturnNode extends CFGNode { // Gather parse-time return types for error reporting Type t = expr._type; - mt = mt.meet(t); ti |= t instanceof TypeInteger x; tf |= t instanceof TypeFloat x; tp |= t instanceof TypeMemPtr x; @@ -117,7 +115,7 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { - return expr()._type/*mt*/==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; + return expr()._type==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; } static Parser.ParseException mixerr( boolean ti, boolean tf, boolean tp, boolean tn, Parser.Lexer loc ) { diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/StartNode.java index f40203b4..4bd76f50 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -51,7 +51,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; } } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/StopNode.java index b65535f1..2363db2c 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -66,10 +66,10 @@ 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 ) d = Math.max(d,((ReturnNode)ret).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 743d5d85..9b5d5da6 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,19 @@ 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(); + org.junit.Assert.assertTrue(body, + code.expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 8069ddaa..21759b78 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -7,6 +7,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 9bdf8aac..c8a613a1 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter22/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(test[1],e.getMessage()); + } + } + } + + @Test public void testPrintingForwardReferenceScope() throws Exception { new CodeGen("return 0;").parse(); var declared = TypeMemPtr.make(TypeStruct.makeFRef("PrintForward")); diff --git a/chapter22/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter22/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..ceea1de5 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -21,17 +21,24 @@ public class PrintTestSupport { var ins = new IdentityHashMap<Node,Node[]>(); var outs = new IdentityHashMap<Node,Node[]>(); var hashes = new IdentityHashMap<Node,Integer>(); + var versions = new IdentityHashMap<Node,Integer>(); var depths = new IdentityHashMap<Node,Integer>(); 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 6c958f32..02ade2c1 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -94,22 +94,12 @@ public class CodeGen { public int getALIAS() { return _alias++; } - // 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 int _iDepthVersion = 0; - public void invalidateIDepthCaches() { _iDepthVersion++; } - public boolean validIDepth(int idepth) { - if( idepth==0 ) return false; - if( _iDepthVersion==0 ) return true; - return (idepth%100)==_iDepthVersion; - } - public int iDepthAt(int idepth) { - return 100*idepth+_iDepthVersion; - } - public int iDepthFrom(int idepth) { - assert idepth==0 || validIDepth(idepth); - return idepth+100; + // 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; } // Popular visit bitset, declared here, so it gets reused all over @@ -484,7 +474,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/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index d9c7a6ad..144a9f8e 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -203,7 +203,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 ) @@ -257,7 +257,7 @@ public abstract class GlobalCodeMotion { CFGNode found=null; for( int i=1; i<phi.nIns(); i++ ) if( phi.in(i)==n ) - found = phi.region().cfg(i)._idom(found,null); + found = phi.region().cfg(i).domLCA(found,null); assert found!=null; return found; @@ -311,7 +311,7 @@ public abstract class GlobalCodeMotion { private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java index b9c70e5f..d9452b6d 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -36,6 +36,7 @@ public abstract class CFGNode extends Node { super(cfg); if( cfg != null ) { _idepth = cfg._idepth; + _idepthVersion = cfg._idepthVersion; _ltree = cfg._ltree; _pre = cfg._pre; } @@ -72,24 +73,32 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 7971733a..95303994 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -80,8 +80,7 @@ public class ReturnNode extends CFGNode { return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress(); } - // Gather parse-time return types for error reporting - private Type mt = Type.TOP; + // Remember parsed type kinds for diagnostics; the optimized expression decides validity. private boolean ti=false, tf=false, tp=false, tn=false; // Add a return exit to the current parsing function @@ -90,7 +89,6 @@ public class ReturnNode extends CFGNode { // Gather parse-time return types for error reporting Type t = expr._type; - mt = mt.meet(t); ti |= t instanceof TypeInteger x; tf |= t instanceof TypeFloat x; tp |= t instanceof TypeMemPtr x; @@ -116,7 +114,7 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { - return expr()._type/*mt*/==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; + return expr()._type==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; } static Parser.ParseException mixerr( boolean ti, boolean tf, boolean tp, boolean tn, Parser.Lexer loc ) { diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/StartNode.java index e3806de7..6ed2acd3 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -50,7 +50,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; } } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/StopNode.java index 4b03bf4e..98a8d4c3 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -66,10 +66,10 @@ 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 ) d = Math.max(d,((ReturnNode)ret).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java index c1b5e3a8..d7a74f18 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,19 @@ 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(); + org.junit.Assert.assertTrue(body, + code.expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 8069ddaa..21759b78 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -7,6 +7,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 704ac120..41b7d139 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter23/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(test[1],e.getMessage()); + } + } + } + + @Test public void testPrintingForwardReferenceScope() throws Exception { new CodeGen("return 0;").parse(); var declared = TypeMemPtr.make(TypeStruct.open("PrintForward")); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter23/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..ceea1de5 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -21,17 +21,24 @@ public class PrintTestSupport { var ins = new IdentityHashMap<Node,Node[]>(); var outs = new IdentityHashMap<Node,Node[]>(); var hashes = new IdentityHashMap<Node,Integer>(); + var versions = new IdentityHashMap<Node,Integer>(); var depths = new IdentityHashMap<Node,Integer>(); 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index c0b8d68e..3c6e825d 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -94,22 +94,12 @@ public class CodeGen { public int getALIAS() { return _alias++; } - // 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 int _iDepthVersion = 0; - public void invalidateIDepthCaches() { _iDepthVersion++; } - public boolean validIDepth(int idepth) { - if( idepth==0 ) return false; - if( _iDepthVersion==0 ) return true; - return (idepth%100)==_iDepthVersion; - } - public int iDepthAt(int idepth) { - return 100*idepth+_iDepthVersion; - } - public int iDepthFrom(int idepth) { - assert idepth==0 || validIDepth(idepth); - return idepth+100; + // 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; } // Popular visit bitset, declared here, so it gets reused all over @@ -452,7 +442,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/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index d9c7a6ad..144a9f8e 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -203,7 +203,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 ) @@ -257,7 +257,7 @@ public abstract class GlobalCodeMotion { CFGNode found=null; for( int i=1; i<phi.nIns(); i++ ) if( phi.in(i)==n ) - found = phi.region().cfg(i)._idom(found,null); + found = phi.region().cfg(i).domLCA(found,null); assert found!=null; return found; @@ -311,7 +311,7 @@ public abstract class GlobalCodeMotion { private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java index b9c70e5f..d9452b6d 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -36,6 +36,7 @@ public abstract class CFGNode extends Node { super(cfg); if( cfg != null ) { _idepth = cfg._idepth; + _idepthVersion = cfg._idepthVersion; _ltree = cfg._ltree; _pre = cfg._pre; } @@ -72,24 +73,32 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) if( !cfg(i)._type.isHigh() ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 0aa70214..80b3fe4f 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -80,8 +80,7 @@ public class ReturnNode extends CFGNode { return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress(); } - // Gather parse-time return types for error reporting - private Type mt = Type.TOP; + // Remember parsed type kinds for diagnostics; the optimized expression decides validity. private boolean ti=false, tf=false, tp=false, tn=false; // Add a return exit to the current parsing function @@ -90,7 +89,6 @@ public class ReturnNode extends CFGNode { // Gather parse-time return types for error reporting Type t = expr._type; - mt = mt.meet(t); ti |= t instanceof TypeInteger x; tf |= t instanceof TypeFloat x; tp |= t instanceof TypeMemPtr x; diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/StartNode.java index e3806de7..6ed2acd3 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -50,7 +50,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; } } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/StopNode.java index 4b03bf4e..98a8d4c3 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -66,10 +66,10 @@ 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 ) d = Math.max(d,((ReturnNode)ret).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java index c1b5e3a8..d7a74f18 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,19 @@ 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(); + org.junit.Assert.assertTrue(body, + code.expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + } + } + + // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 8069ddaa..21759b78 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -7,6 +7,20 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; 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/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 764356cf..5dbbf0f1 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter24/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(test[1],e.getMessage()); + } + } + } + + @Test public void testPrintingForwardReferenceScope() throws Exception { new CodeGen("return 0;").parse(); var declared = TypeMemPtr.make(TypeStruct.open("PrintForward")); diff --git a/chapter24/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter24/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java index 01d471bf..ceea1de5 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -21,17 +21,24 @@ public class PrintTestSupport { var ins = new IdentityHashMap<Node,Node[]>(); var outs = new IdentityHashMap<Node,Node[]>(); var hashes = new IdentityHashMap<Node,Integer>(); + var versions = new IdentityHashMap<Node,Integer>(); var depths = new IdentityHashMap<Node,Integer>(); 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java index fda5af65..145e0e03 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -212,7 +212,7 @@ public class IterPeeps { for( Node use : n._outputs ) { CFGNode ublk = useBlock(n,use); if( ublk != null ) - lca = ublk._idom(lca,null); + lca = ublk.domLCA(lca,null); } if( lca == null ) return null; if( !early.sameFun(lca) ) return null; @@ -231,7 +231,7 @@ public class IterPeeps { if( phi.in(i)==n ) { if( 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<phi.nIns(); i++ ) if( phi.in(i)==n ) - found = phi.region().cfg(i)._idom(found,null); + found = phi.region().cfg(i).domLCA(found,null); assert found!=null; return found; @@ -372,7 +372,7 @@ public abstract class GlobalCodeMotion { private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 0ff74a2b..b40f4204 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -34,6 +34,7 @@ public abstract class CFGNode extends Node { super(cfg); if( cfg != null ) { _idepth = cfg._idepth; + _idepthVersion = cfg._idepthVersion; _ltree = cfg._ltree; _pre = cfg._pre; } @@ -70,24 +71,32 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - 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<nIns(); i++ ) if( !cfg(i)._type.isHigh() ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StartCUNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StartCUNode.java index d828c5f1..cd51f603 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StartCUNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StartCUNode.java @@ -25,7 +25,7 @@ public class StartCUNode extends StartNode { @Override public CFGNode cfg0() { return (CFGNode)in(0); } // IDom is cfg0() and depth is always Start+1 which is 0+1 or 1 - @Override public int idepth() { return CodeGen.CODE.iDepthAt(1); } + @Override public int idepth() { return 1; } @Override public CFGNode idom(Node dep) { return cfg0(); } @Override public void gather( HashMap<String,Integer> 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<Node,Node[]>(); var outs = new IdentityHashMap<Node,Node[]>(); var hashes = new IdentityHashMap<Node,Integer>(); + var versions = new IdentityHashMap<Node,Integer>(); var depths = new IdentityHashMap<Node,Integer>(); 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index 9714f697..a6fe5a76 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -9,21 +9,9 @@ For now, keep building SSA with incomplete types in Chapter 25. Moving that architecture earlier, or splitting Chapter 25, is deferred while small changes establish the review workflow. No renumbering is committed. -## Small changes - Keep each correction's reduced failure, smallest patch, and test results together for review. -An **audit** item needs an old-chapter reproducer before it is scheduled. Copy -the correction into the chapter's representation, not the entire modern file. - -| ID | Change | Proposed destination | Scope and acceptance evidence | -|---|---|---|---| -| B11 | Diagnose return types using the optimized return expression | 18; 19 already has the correction | `ReturnNode.err()` uses `expr()._type` instead of the parse-time `mt` aggregate. Chapter 18 rejects `struct S { u8 x; }; return new S; return 0;` with a mixed integer/reference error; Chapter 19 accepts it. Also test genuinely reachable incompatible returns. This is a candidate, not yet an applied or isolated-patch-verified fix. | - -After the first two reviews, batch only corrections with established independence -and regressions. Keep one logical correction per commit across affected chapters. - ## AOT class initialization: larger independent work Proposed on 2026-09-19; deferred behind the smaller BXX cleanup above. This is @@ -81,7 +69,7 @@ Chapter 25 suite, including `make -j 4 tests`. | Group | Eventual home | Why not in the small queue yet | |---|---|---| -| Dominator caches, scheduling, global constant cloning | 11 / 18 / 19 as applicable | Current changes mix inlining, scheduling, and compilation-unit ownership. Need a reduced old-IR failure. | +| Scheduling and global constant cloning | 11 / 19 as applicable | Separate scheduling and compilation-unit ownership changes; need reduced old-IR failures. | | Register allocation and spilling | 20 onward | Need constrained-register/spill regressions; changed golden spill counts are insufficient evidence. | | Conditional Store and array Load control | Memory/arrays chapters | Reproduce under the earlier alias model before extracting fixes from the new memory implementation. | | SCCP dependencies, function revival, reachability | 24; some foundations may fit 18 | Separate old-IR corrections from new Guard/Escape/BulkMemPhi and external-caller machinery. | @@ -89,6 +77,7 @@ Chapter 25 suite, including `make -j 4 tests`. | TypeScalar, numeric modes, guards, symbolic fields, open/forward types | Revisit earlier homes later | A connected incomplete-types architecture, including phase ordering and errors. | | BulkMemPhi/MemPhi, private constructor memory, allocation helpers | Revisit memory / constructors / methods | Move invariants and regressions together. | | Serialization, global identity remapping, module escape summaries | Separate compilation | Remain with modules. | +| Remove CFGNode._anti | move the field into a temp array during GCM | ## Review and test protocol @@ -130,6 +119,69 @@ Historical results below are dated evidence, not a substitute for a fresh baseline. Logs live in ignored build directories and may no longer exist. Reusable implementation lessons are in `skills/chapter25-codex-notes.md`. +### Dominator caches: unified locally, 2026-09-19 + +Real dominator searches begin in 6. The original Region pointer cache in 6-9 +returned the old, still-live dominator after its predecessors were rewired. +Regions now recompute through the shared depth-based `domLCA` walk in 6-25, +including one, two, or more predecessors. Existing dependency direction and +24-25's dead-predecessor filtering are preserved. + +Per review, 6-17 use a char depth with no version. Chapters 18-25 use separate +char depth/version fields, checked before depth narrowing and global version +increments. Added the invalidation hook to 18-20's inlining; 21-25 already had +it. Region, Loop and Stop all validate their caches, and folding functions use +their caller-side depth. CFG copy constructors preserve both fields, as do +ordinary clones. Packed versions in 21-24 failed after 100 invalidations; +25's packed depth overflowed at 2148. Both limits are now 65535, with explicit +overflow assertions. + +Development checks covered rewiring, depth overflow, actual inlining with warmed +caches, repeated invalidation, copy preservation, and version overflow. At +Cliff's request, the dedicated dominator helpers/tests and their Makefile +accommodations were subsequently removed as unnecessary for this bookkeeping. +Existing printer regressions still check that both cache fields stay unchanged. + +Baseline full targets passed in 6-24. After full Java rebuilds, all affected +snapshot suites passed with assertions enabled. Chapter 25 initially passed +`make tests` and `make -j 4 tests` in a scratch copy with a pre-existing stray +`v` removed from Node.java. After Cliff authorized removing that typo from the +live tree, its Java sources and system object rebuilt and `make -j 4 tests` +passed there too (451 tests, exit status zero). + +Logs: `chapter25/build/dominator-review/{baseline,fixed,later,final18-24,chapter25-scratch,chapter25-final,chapter25-live}.log`. +Reusable cache rules are in the skills notes. + +### B11: optimized return-type checking backported locally, 2026-09-19 + +The false mixed-return rejection begins in Chapter 18, where function returns +first merge through one Return/return-value Phi. `ReturnNode.err()` now checks +`expr()._type`, as in Chapter 19. The parse-time `mt` meet could retain a type +from an unreachable return forever. Removed that aggregate from 18-24; it was +already unused in 19-24 and absent in 25. Parsed kind flags remain only for +formatting diagnostics. Chapter 24's additional TOP check is preserved. + +Earlier snapshots were checked with reduced syntax. Struct/reference returns +appear in 10; floating-point returns in 12. Chapters 10-17 already accept the +dead reference/int examples, and 12-17 accept the dead float/int examples. +They retain separate Return nodes and do not require one common type across +reachable returns. The B11 false rejection therefore has no earlier compiler +patch; introducing common-return-type checking there would be separate work. + +`Chapter10Test.testDeadReferenceReturn` starts in 10 and is copied through 25; +`Chapter12Test.testDeadNumericReturns` starts in 12 and is copied through 25. +They cover both constant If arms and unreachable returns after an unconditional +return; numeric cases also verify execution results. Both tests failed in 18 +before the correction with `No common type amongst ...`. +`Chapter18Test.testReachableMixedReturns` in 18-25 still rejects reachable +int/float and int/reference alternatives, using each chapter's diagnostic. + +Unmodified baseline targets passed in 9-25. Final full `make tests` targets +passed with assertions enabled in every changed snapshot, 10-25; Chapter 25 +passed 448 tests. Its reference test selects the entry function explicitly, +because constructors add other Returns to the same compilation unit. +Logs: `chapter25/build/b11-review/{probe,probe-later,baseline,red,fixed,chapter25-fixed}.log`. + ### B12: immediate multiply destination corrected locally, 2026-09-19 The x86 backend has distinct integer register (`MulX86`, 0F AF), integer diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index 0bb324ac..ea794c8b 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -50,6 +50,32 @@ lessons rather than duplicating that history. files. The B13 `chapter25/tmp` probes were removed at Cliff's request after he reviewed and pushed the fix; future sessions must not rely on those files. +## Dominator caches and searches + +- Real dominator searches start in Chapter 6 (If and Region), before CFGNode + appears in 11. Regions recompute their dominator from current predecessors + using the shared `domLCA` walk; do not cache a dominator pointer just because + the old node is still alive. Rewiring a merge can change its dominator. +- Chapters 6-17 cache a `char` depth with zero meaning unset. From 18, inlining + requires a separate `char` cache version and a checked global version bump. + Keep depth/version as separate fields rather than packing arithmetic into an + int. Assert before narrowing a depth or incrementing the version: 65535 is + the largest representable value, and wrapping must fail clearly. +- Copy both cache fields when copying a CFG node. Ordinary `Node.copy()` clones + already preserve them; CFG copy constructors must do so explicitly. Inlining + invalidates afterward, but future local CFG transforms may preserve valid + caches outside their edit region. +- Every cached depth override, including Region, Loop and Stop, participates in + version validation. Start has fixed depth zero; an unfolded function is a + root, while a folding function uses its new caller-side depth. Preserve the + chapter's dependency direction and dead-predecessor rules when sharing walks. +- Cliff requested removing the dedicated dominator bookkeeping tests/helpers; + do not restore them without a substantive failure to cover. Keep existing + printer cache snapshots checking both fields; cast char depths to int for + numeric display. +- Keep single-return accessors and overrides compact on one line, including + `idepth()` and `validIDepth()`. + ## Null guards: B13 / issue #246 lessons - Null refinement starts in Chapter 10; arrays in 15; scoped expression guards @@ -178,6 +204,12 @@ Consequences: ## Functions and escape analysis +- Unified function returns start in Chapter 18. Check return compatibility from + the optimized return expression, not a parse-time meet that includes dead + exits. Parse-time type-kind flags may describe an error, but must not decide + whether an error exists. Earlier snapshots keep separate Return nodes; they + already accept dead mixed-type exits and do not enforce one common return type. + - A constant Simple function address must be a `FunPtrNode`, not an ordinary `ConstantNode`, so the pointer retains an edge to the function Return. - Before Opto, a live FunPtr keeps its function callable even if no Call is |