diff options
Diffstat (limited to 'chapter19/src')
14 files changed, 99 insertions, 28 deletions
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)); |