From 2f779dd115acf1fc99c7b3b416273fdb66ad48cb Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 19 Sep 2026 18:50:22 -0700 Subject: debug printers no longer call self-optimizing accessors --- .../main/java/com/seaofnodes/simple/IRPrinter.java | 32 ++++++-- .../java/com/seaofnodes/simple/Chapter11Test.java | 15 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../main/java/com/seaofnodes/simple/IRPrinter.java | 32 ++++++-- .../java/com/seaofnodes/simple/Chapter11Test.java | 15 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../main/java/com/seaofnodes/simple/IRPrinter.java | 32 ++++++-- .../java/com/seaofnodes/simple/Chapter11Test.java | 15 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../main/java/com/seaofnodes/simple/IRPrinter.java | 32 ++++++-- .../java/com/seaofnodes/simple/Chapter11Test.java | 15 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../main/java/com/seaofnodes/simple/IRPrinter.java | 25 +++++- .../java/com/seaofnodes/simple/Chapter11Test.java | 15 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../main/java/com/seaofnodes/simple/IRPrinter.java | 25 +++++- .../java/com/seaofnodes/simple/Chapter11Test.java | 15 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../main/java/com/seaofnodes/simple/IRPrinter.java | 25 +++++- .../java/com/seaofnodes/simple/Chapter11Test.java | 15 ++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../main/java/com/seaofnodes/simple/IRPrinter.java | 25 +++++- .../src/main/java/com/seaofnodes/simple/Var.java | 2 + .../com/seaofnodes/simple/node/MemMergeNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 2 +- .../java/com/seaofnodes/simple/Chapter11Test.java | 15 ++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 35 +++++++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../main/java/com/seaofnodes/simple/IRPrinter.java | 25 +++++- .../src/main/java/com/seaofnodes/simple/Var.java | 2 + .../java/com/seaofnodes/simple/node/CallNode.java | 6 +- .../com/seaofnodes/simple/node/ConstantNode.java | 4 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 2 +- .../java/com/seaofnodes/simple/Chapter11Test.java | 15 ++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 35 +++++++++ .../java/com/seaofnodes/simple/Chapter19Test.java | 22 ++++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../src/main/java/com/seaofnodes/simple/Var.java | 2 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 12 ++- .../java/com/seaofnodes/simple/node/CallNode.java | 6 +- .../com/seaofnodes/simple/node/ConstantNode.java | 4 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 2 +- .../com/seaofnodes/simple/print/IRPrinter.java | 25 +++++- .../java/com/seaofnodes/simple/Chapter11Test.java | 18 ++++- .../java/com/seaofnodes/simple/Chapter18Test.java | 35 +++++++++ .../java/com/seaofnodes/simple/Chapter19Test.java | 22 ++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 5 ++ .../simple/codegen/PrintRegTestSupport.java | 26 +++++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../src/main/java/com/seaofnodes/simple/Var.java | 2 + .../com/seaofnodes/simple/codegen/Encoding.java | 2 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 12 ++- .../java/com/seaofnodes/simple/node/CallNode.java | 6 +- .../com/seaofnodes/simple/node/ConstantNode.java | 2 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 2 +- .../com/seaofnodes/simple/print/ASMPrinter.java | 11 +-- .../com/seaofnodes/simple/print/IRPrinter.java | 25 +++++- .../java/com/seaofnodes/simple/Chapter11Test.java | 18 ++++- .../java/com/seaofnodes/simple/Chapter18Test.java | 35 +++++++++ .../java/com/seaofnodes/simple/Chapter19Test.java | 22 ++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 5 ++ .../simple/codegen/PrintRegTestSupport.java | 26 +++++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../src/main/java/com/seaofnodes/simple/Var.java | 2 + .../com/seaofnodes/simple/codegen/Encoding.java | 4 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 12 ++- .../java/com/seaofnodes/simple/node/CallNode.java | 2 +- .../com/seaofnodes/simple/node/ConstantNode.java | 2 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 2 +- .../com/seaofnodes/simple/print/ASMPrinter.java | 13 ++-- .../com/seaofnodes/simple/print/IRPrinter.java | 25 +++++- .../java/com/seaofnodes/simple/Chapter11Test.java | 18 ++++- .../java/com/seaofnodes/simple/Chapter18Test.java | 35 +++++++++ .../java/com/seaofnodes/simple/Chapter19Test.java | 22 ++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 5 ++ .../simple/codegen/PrintRegTestSupport.java | 26 +++++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../src/main/java/com/seaofnodes/simple/Var.java | 2 + .../com/seaofnodes/simple/codegen/Encoding.java | 4 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 12 ++- .../java/com/seaofnodes/simple/node/CallNode.java | 2 +- .../com/seaofnodes/simple/node/ConstantNode.java | 2 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 2 +- .../com/seaofnodes/simple/print/ASMPrinter.java | 13 ++-- .../com/seaofnodes/simple/print/IRPrinter.java | 25 +++++- .../com/seaofnodes/simple/type/TypeFunPtr.java | 2 +- .../com/seaofnodes/simple/type/TypeInteger.java | 4 +- .../java/com/seaofnodes/simple/Chapter11Test.java | 18 ++++- .../java/com/seaofnodes/simple/Chapter18Test.java | 35 +++++++++ .../java/com/seaofnodes/simple/Chapter19Test.java | 22 ++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 5 ++ .../java/com/seaofnodes/simple/Chapter23Test.java | 20 +++++ .../simple/codegen/PrintRegTestSupport.java | 26 +++++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../src/main/java/com/seaofnodes/simple/Var.java | 2 + .../com/seaofnodes/simple/codegen/CodeGen.java | 5 +- .../com/seaofnodes/simple/codegen/Encoding.java | 4 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 12 ++- .../java/com/seaofnodes/simple/node/CallNode.java | 4 +- .../com/seaofnodes/simple/node/ConstantNode.java | 4 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 2 +- .../com/seaofnodes/simple/print/ASMPrinter.java | 13 ++-- .../com/seaofnodes/simple/print/IRPrinter.java | 25 +++++- .../com/seaofnodes/simple/type/TypeFunPtr.java | 2 +- .../com/seaofnodes/simple/type/TypeInteger.java | 4 +- .../java/com/seaofnodes/simple/Chapter11Test.java | 18 ++++- .../java/com/seaofnodes/simple/Chapter18Test.java | 35 +++++++++ .../java/com/seaofnodes/simple/Chapter19Test.java | 22 ++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 5 ++ .../java/com/seaofnodes/simple/Chapter23Test.java | 25 ++++++ .../java/com/seaofnodes/simple/Chapter24Test.java | 20 +++++ .../simple/codegen/PrintRegTestSupport.java | 26 +++++++ .../seaofnodes/simple/node/PrintTestSupport.java | 41 ++++++++++ .../com/seaofnodes/simple/codegen/CodeGen.java | 6 +- .../com/seaofnodes/simple/codegen/Encoding.java | 11 ++- .../java/com/seaofnodes/simple/codegen/Opto.java | 2 +- .../com/seaofnodes/simple/codegen/RegAlloc.java | 12 ++- .../java/com/seaofnodes/simple/node/CallNode.java | 4 +- .../com/seaofnodes/simple/node/ConstantNode.java | 6 +- .../com/seaofnodes/simple/node/FunPtrNode.java | 2 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 2 +- .../com/seaofnodes/simple/print/ASMPrinter.java | 13 ++-- .../com/seaofnodes/simple/type/TypeFunPtr.java | 2 +- .../com/seaofnodes/simple/type/TypeInteger.java | 4 +- .../java/com/seaofnodes/simple/Chapter11Test.java | 14 +++- .../java/com/seaofnodes/simple/Chapter18Test.java | 28 +++++++ .../java/com/seaofnodes/simple/Chapter19Test.java | 22 ++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 5 ++ .../java/com/seaofnodes/simple/Chapter23Test.java | 25 ++++++ .../java/com/seaofnodes/simple/Chapter24Test.java | 20 +++++ .../java/com/seaofnodes/simple/Chapter25Test.java | 4 + .../simple/codegen/PrintRegTestSupport.java | 76 +++++++++++++++++++ .../seaofnodes/simple/node/PrintTestSupport.java | 39 ++++++++++ docs/chapter-backports.md | 88 +++++++++++++++++++++- skills/chapter25-codex-notes.md | 30 ++++++++ 141 files changed, 2272 insertions(+), 144 deletions(-) create mode 100644 chapter11/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter12/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter13/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter14/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter15/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter16/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter18/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter19/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter20/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java create mode 100644 chapter20/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter22/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java create mode 100644 chapter22/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter23/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java create mode 100644 chapter23/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java diff --git a/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java index 43c6c9f7..909dd575 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -5,6 +5,7 @@ import java.lang.StringBuilder; import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; +import java.util.IdentityHashMap; public class IRPrinter { @@ -187,19 +188,40 @@ public class IRPrinter { } } + // Diagnostic block ordering from raw control edges. Do not call idepth(): + // it fills compiler caches (and can walk lazy dominator accessors). + private static int _idepth(CFGNode cfg, HashMap depths) { + if( cfg == null || cfg instanceof StartNode ) return 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available public static String prettyPrintScheduled( Node node, int depth, boolean llvmFormat ) { // Backwards DFS walk to depth. - HashMap ds = new HashMap<>(); + IdentityHashMap ds = new IdentityHashMap<>(); _walk(ds,node,depth); - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList bns = new ArrayList<>(); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ds.keySet() ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : (CFGNode)n.in(0); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } ds.remove(blk); @@ -239,7 +261,7 @@ public class IRPrinter { return sb.toString(); } - private static void _walk( HashMap ds, Node node, int d ) { + private static void _walk( IdentityHashMap ds, Node node, int d ) { Integer nd = ds.get(node); if( nd!=null && d <= nd ) return; // Been there, done that ds.put(node,d); @@ -257,7 +279,7 @@ public class IRPrinter { if( !blk.blockHead() ) blk = blk.cfg(0); sb.append( "%-9.9s ".formatted( label( blk ) ) ); } - static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList bns, int i, HashMap ds ) { + static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList bns, int i, IdentityHashMap ds ) { printLine( n, sb, llvmFormat ); Utils.del(bns,i); ds.remove(n); diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 02843c85..4d558bd8 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; @@ -8,6 +9,20 @@ import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var stop = new Parser("while(arg < 10) arg = arg + 1; return arg;").parse().iterate(); + GlobalCodeMotion.buildCFG(stop); + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter11/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter11/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter11/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i depths) { + if( cfg == null || cfg instanceof StartNode ) return 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available public static String prettyPrintScheduled( Node node, int depth, boolean llvmFormat ) { // Backwards DFS walk to depth. - HashMap ds = new HashMap<>(); + IdentityHashMap ds = new IdentityHashMap<>(); _walk(ds,node,depth); - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList bns = new ArrayList<>(); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ds.keySet() ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : (CFGNode)n.in(0); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } ds.remove(blk); @@ -239,7 +261,7 @@ public class IRPrinter { return sb.toString(); } - private static void _walk( HashMap ds, Node node, int d ) { + private static void _walk( IdentityHashMap ds, Node node, int d ) { Integer nd = ds.get(node); if( nd!=null && d <= nd ) return; // Been there, done that ds.put(node,d); @@ -257,7 +279,7 @@ public class IRPrinter { if( !blk.blockHead() ) blk = blk.cfg(0); sb.append( "%-9.9s ".formatted( label( blk ) ) ); } - static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList bns, int i, HashMap ds ) { + static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList bns, int i, IdentityHashMap ds ) { printLine( n, sb, llvmFormat ); Utils.del(bns,i); ds.remove(n); diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java index a8b09226..17df1e3b 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; @@ -8,6 +9,20 @@ import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var stop = new Parser("while(arg < 10) arg = arg + 1; return arg;").parse().iterate(); + GlobalCodeMotion.buildCFG(stop); + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter12/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter12/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter12/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i depths) { + if( cfg == null || cfg instanceof StartNode ) return 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available public static String prettyPrintScheduled( Node node, int depth, boolean llvmFormat ) { // Backwards DFS walk to depth. - HashMap ds = new HashMap<>(); + IdentityHashMap ds = new IdentityHashMap<>(); _walk(ds,node,depth); - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList bns = new ArrayList<>(); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ds.keySet() ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : (CFGNode)n.in(0); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } ds.remove(blk); @@ -239,7 +261,7 @@ public class IRPrinter { return sb.toString(); } - private static void _walk( HashMap ds, Node node, int d ) { + private static void _walk( IdentityHashMap ds, Node node, int d ) { Integer nd = ds.get(node); if( nd!=null && d <= nd ) return; // Been there, done that ds.put(node,d); @@ -257,7 +279,7 @@ public class IRPrinter { if( !blk.blockHead() ) blk = blk.cfg(0); sb.append( "%-9.9s ".formatted( label( blk ) ) ); } - static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList bns, int i, HashMap ds ) { + static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList bns, int i, IdentityHashMap ds ) { printLine( n, sb, llvmFormat ); Utils.del(bns,i); ds.remove(n); diff --git a/chapter13/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter13/src/test/java/com/seaofnodes/simple/Chapter11Test.java index da0bc087..bdcae399 100644 --- a/chapter13/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter13/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; @@ -8,6 +9,20 @@ import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var stop = new Parser("while(arg < 10) arg = arg + 1; return arg;").parse().iterate(); + GlobalCodeMotion.buildCFG(stop); + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter13/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter13/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter13/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i depths) { + if( cfg == null || cfg instanceof StartNode ) return 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available public static String prettyPrintScheduled( Node node, int depth, boolean llvmFormat ) { // Backwards DFS walk to depth. - HashMap ds = new HashMap<>(); + IdentityHashMap ds = new IdentityHashMap<>(); _walk(ds,node,depth); - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList bns = new ArrayList<>(); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ds.keySet() ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : (CFGNode)n.in(0); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } ds.remove(blk); @@ -239,7 +261,7 @@ public class IRPrinter { return sb.toString(); } - private static void _walk( HashMap ds, Node node, int d ) { + private static void _walk( IdentityHashMap ds, Node node, int d ) { Integer nd = ds.get(node); if( nd!=null && d <= nd ) return; // Been there, done that ds.put(node,d); @@ -257,7 +279,7 @@ public class IRPrinter { if( !blk.blockHead() ) blk = blk.cfg(0); sb.append( "%-9.9s ".formatted( label( blk ) ) ); } - static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList bns, int i, HashMap ds ) { + static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList bns, int i, IdentityHashMap ds ) { printLine( n, sb, llvmFormat ); Utils.del(bns,i); ds.remove(n); diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 63cd511a..4bfc25f4 100644 --- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; @@ -8,6 +9,20 @@ import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var stop = new Parser("while(arg < 10) arg = arg + 1; return arg;").parse().iterate(); + GlobalCodeMotion.buildCFG(stop); + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter14/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter14/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter14/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i depths) { + if( cfg == null || cfg instanceof StartNode ) return 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available public static String prettyPrintScheduled( Node node, int depth, boolean llvmFormat ) { // Backwards DFS walk to depth. @@ -200,14 +220,15 @@ public class IRPrinter { ds.remove(proj._nid); } } - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList bns = new ArrayList<>(); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ns ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } ds.remove(blk._nid); diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 5f9f9cac..432b174f 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; @@ -8,6 +9,20 @@ import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var stop = new Parser("while(arg < 10) arg = arg + 1; return arg;").parse().iterate(); + GlobalCodeMotion.buildCFG(stop); + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter15/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter15/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter15/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i depths) { + if( cfg == null || cfg instanceof StartNode ) return 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available public static String prettyPrintScheduled( Node node, int depth, boolean llvmFormat ) { // Backwards DFS walk to depth. @@ -200,14 +220,15 @@ public class IRPrinter { ds.remove(proj._nid); } } - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList bns = new ArrayList<>(); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ns ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } ds.remove(blk._nid); diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java index d6b7bb00..67e3b530 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; @@ -8,6 +9,20 @@ import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var stop = new Parser("while(arg < 10) arg = arg + 1; return arg;").parse().iterate(); + GlobalCodeMotion.buildCFG(stop); + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter16/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter16/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter16/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i depths) { + if( cfg == null || cfg instanceof StartNode ) return 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available public static String prettyPrintScheduled( Node node, int depth, boolean llvmFormat ) { // Backwards DFS walk to depth. @@ -200,14 +220,15 @@ public class IRPrinter { ds.remove(proj._nid); } } - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList bns = new ArrayList<>(); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ns ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } ds.remove(blk._nid); diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 613b979b..ff1045d0 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; @@ -8,6 +9,20 @@ import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var stop = new Parser("while(arg < 10) arg = arg + 1; return arg;").parse().iterate(); + GlobalCodeMotion.buildCFG(stop); + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter17/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i depths) { + if( cfg == null || cfg instanceof StartNode || cfg instanceof FunNode ) return cfg instanceof FunNode ? 1 : 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available private static String _prettyPrintScheduled( Node node, int depth ) { // Backwards DFS walk to depth. @@ -185,14 +205,15 @@ public class IRPrinter { ds.remove(proj._nid); } } - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); SB sb = new SB(); Ary bns = new Ary<>(Node.class); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ns ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); - if( blk==null || cfg.idepth() < blk.idepth() || (blk instanceof FunNode && !(cfg instanceof FunNode))) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) || (blk instanceof FunNode && !(cfg instanceof FunNode))) blk = cfg; } Integer d = ds.remove(blk._nid); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Var.java b/chapter18/src/main/java/com/seaofnodes/simple/Var.java index e71d7ef2..6e621875 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/Var.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/Var.java @@ -26,6 +26,8 @@ public class Var { _loc = loc; _fref = fref; } + // Raw declared type, without resolving a forward reference while printing. + public Type _type() { return _type; } public Type type() { if( !_type.isFRef() ) return _type; // Update self to no longer use the forward ref type diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 8a08853c..033f1331 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -39,7 +39,7 @@ public class MemMergeNode extends Node { Node n = in(j); while( n instanceof ScopeNode loop ) { sb.append("Lazy_"); - n = loop.mem(j); + n = loop.mem().alias(j); } if( n==null ) sb.append("___ "); else n._print0(sb, visited).append(" "); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 675cd197..e8b20c37 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -49,7 +49,7 @@ public class ScopeNode extends MemMergeNode { for( int i=0; i { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 60f9b847..f9be0e93 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.node.*; + import org.junit.Test; import static org.junit.Assert.*; @@ -6,6 +9,38 @@ import static org.junit.Assert.fail; import org.junit.Ignore; public class Chapter18Test { + @Test public void testPrintingForwardReferenceScope() throws Exception { + new CodeGen("return 0;").parse(); + var declared = TypeMemPtr.make(TypeStruct.makeFRef("PrintForward")); + var scope = new ScopeNode(); + scope.define("ptr",declared,false,new ConstantNode(TypeInteger.ZERO),null); + Parser.TYPES.put("PrintForward",TypeMemPtr.make(TypeStruct.make("PrintForward"))); + var field = Var.class.getDeclaredField("_type"); + field.setAccessible(true); + var v = scope._vars.get(0); + org.junit.Assert.assertSame(declared,field.get(v)); + scope.toString(); + org.junit.Assert.assertSame(declared,field.get(v)); + } + + @Test public void testPrintingLazyMemory() throws Exception { + var code = new CodeGen("return 0;").parse(); + var base = new ConstantNode(com.seaofnodes.simple.type.TypeMem.BOT); + var outer = new ScopeNode(); + var inner = new ScopeNode(); + var loop = new LoopNode(null,code._start); + loop._type = com.seaofnodes.simple.type.Type.CONTROL; + var outerMem = new MemMergeNode(true); + outerMem.addDef(null); outerMem.addDef(base); outerMem.addDef(base); + outer.addDef(loop); outer.addDef(outerMem); + var innerMem = new MemMergeNode(true); + innerMem.addDef(null); innerMem.addDef(outer); innerMem.addDef(outer); + inner.addDef(loop); inner.addDef(innerMem); + var mem = new MemMergeNode(true); + mem.addDef(null); mem.addDef(base); mem.addDef(inner); + PrintTestSupport.unchanged(mem, () -> org.junit.Assert.assertTrue(mem.toString().contains("Lazy_"))); + } + @Test public void testJig() { diff --git a/chapter18/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter18/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter18/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i depths) { + if( cfg == null || cfg instanceof StartNode || cfg instanceof FunNode ) return cfg instanceof FunNode ? 1 : 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available private static String _prettyPrintScheduled( Node node, int depth ) { // Backwards DFS walk to depth. @@ -183,14 +203,15 @@ public abstract class IRPrinter { ds.remove(proj._nid); } } - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); SB sb = new SB(); Ary bns = new Ary<>(Node.class); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ns ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } Integer d = ds.remove(blk._nid); diff --git a/chapter19/src/main/java/com/seaofnodes/simple/Var.java b/chapter19/src/main/java/com/seaofnodes/simple/Var.java index e71d7ef2..6e621875 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/Var.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/Var.java @@ -26,6 +26,8 @@ public class Var { _loc = loc; _fref = fref; } + // Raw declared type, without resolving a forward reference while printing. + public Type _type() { return _type; } public Type type() { if( !_type.isFRef() ) return _type; // Update self to no longer use the forward ref type diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/CallNode.java index 25f76a71..82cf6d28 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -33,8 +33,10 @@ public class CallNode extends CFGNode { return sb.append(")"); } public String name() { - if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() ) - return CodeGen.CODE.link(tfp)._name; + if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() && tfp.notNull() ) { + FunNode fun = CodeGen.CODE.link(tfp); + return fun==null ? null : fun._name; + } return null; } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index d788cff7..46561644 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -42,9 +42,9 @@ public class ConstantNode extends Node { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( _con instanceof TypeFunPtr tfp ) { + if( _con instanceof TypeFunPtr tfp && tfp.isConstant() && tfp.notNull() ) { FunNode fun = CodeGen.CODE.link(tfp); - if( fun._name != null ) + if( fun!=null && fun._name != null ) return sb.append("{ ").append(fun._name).append("}"); } return sb.append(_con.print(new SB())); diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 5363bb6f..a540e7ca 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -37,7 +37,7 @@ public class MemMergeNode extends Node { Node n = in(j); while( n instanceof ScopeNode loop ) { sb.append("Lazy_"); - n = loop.mem(j); + n = loop.mem().alias(j); } if( n==null ) sb.append("___ "); else n._print0(sb, visited).append(" "); diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 913c2669..e0d97f39 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -49,7 +49,7 @@ public class ScopeNode extends MemMergeNode { for( int i=0; i { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java index db970f60..31a4f82e 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.node.*; + import org.junit.Test; import static org.junit.Assert.*; @@ -6,6 +9,38 @@ import static org.junit.Assert.fail; import org.junit.Ignore; public class Chapter18Test { + @Test public void testPrintingForwardReferenceScope() throws Exception { + new CodeGen("return 0;").parse(); + var declared = TypeMemPtr.make(TypeStruct.makeFRef("PrintForward")); + var scope = new ScopeNode(); + scope.define("ptr",declared,false,new ConstantNode(TypeInteger.ZERO),null); + Parser.TYPES.put("PrintForward",TypeMemPtr.make(TypeStruct.make("PrintForward"))); + var field = Var.class.getDeclaredField("_type"); + field.setAccessible(true); + var v = scope._vars.get(0); + org.junit.Assert.assertSame(declared,field.get(v)); + scope.toString(); + org.junit.Assert.assertSame(declared,field.get(v)); + } + + @Test public void testPrintingLazyMemory() throws Exception { + var code = new CodeGen("return 0;").parse(); + var base = new ConstantNode(com.seaofnodes.simple.type.TypeMem.BOT); + var outer = new ScopeNode(); + var inner = new ScopeNode(); + var loop = new LoopNode(null,code._start); + loop._type = com.seaofnodes.simple.type.Type.CONTROL; + var outerMem = new MemMergeNode(true); + outerMem.addDef(null); outerMem.addDef(base); outerMem.addDef(base); + outer.addDef(loop); outer.addDef(outerMem); + var innerMem = new MemMergeNode(true); + innerMem.addDef(null); innerMem.addDef(outer); innerMem.addDef(outer); + inner.addDef(loop); inner.addDef(innerMem); + var mem = new MemMergeNode(true); + mem.addDef(null); mem.addDef(base); mem.addDef(inner); + PrintTestSupport.unchanged(mem, () -> org.junit.Assert.assertTrue(mem.toString().contains("Lazy_"))); + } + @Test public void testJig() { diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 990c4c32..eef9f460 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import org.junit.Test; import static org.junit.Assert.*; @@ -6,6 +9,25 @@ import static org.junit.Assert.fail; import org.junit.Ignore; public class Chapter19Test { + @Test public void testPrintingFunctionLookup() { + var code = new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.make((byte)2,TypeTuple.make(TypeInteger.constant(987654)),TypeInteger.constant(123456),1L<<30); + var con = new ConstantNode(tfp); + var call = new CallNode(null,code._start,con,con); + // Diagnostic lookup may construct/intern the return-erased linker key. + con.toString(); + org.junit.Assert.assertNull(call.name()); + + var fun = new FunNode(null,tfp); + fun._name = "printerTarget"; + fun.addDef(code._start); + code.link(fun); + var otherReturn = tfp.makeFrom(TypeInteger.constant(654321)); + org.junit.Assert.assertSame(fun,code.link(otherReturn)); + org.junit.Assert.assertTrue(con.toString().contains("printerTarget")); + assertEquals("printerTarget",call.name()); + } + @Test public void testJig() { diff --git a/chapter19/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter19/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter19/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i depths) { + if( cfg == null || cfg instanceof StartNode || cfg instanceof FunNode ) return cfg instanceof FunNode ? 1 : 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available private static String _prettyPrintScheduled( Node node, int depth ) { // Backwards DFS walk to depth. @@ -232,14 +252,15 @@ public abstract class IRPrinter { ds.remove(proj._nid); } } - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); SB sb = new SB(); Ary bns = new Ary<>(Node.class); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ns ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } Integer d = ds.remove(blk._nid); diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter11Test.java index c2b9a86d..67828135 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,10 +1,26 @@ package com.seaofnodes.simple; - import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.IRPrinter; + + import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var code = new CodeGen("while(arg < 10) arg = arg + 1; return arg;").parse().opto().typeCheck().GCM().localSched(); + var stop = code._stop; + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java index d0623d12..48b96588 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.node.*; + import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Ignore; @@ -7,6 +10,38 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testPrintingForwardReferenceScope() throws Exception { + new CodeGen("return 0;").parse(); + var declared = TypeMemPtr.make(TypeStruct.makeFRef("PrintForward")); + var scope = new ScopeNode(); + scope.define("ptr",declared,false,new ConstantNode(TypeInteger.ZERO),null); + Parser.TYPES.put("PrintForward",TypeMemPtr.make(TypeStruct.make("PrintForward"))); + var field = Var.class.getDeclaredField("_type"); + field.setAccessible(true); + var v = scope._vars.get(0); + org.junit.Assert.assertSame(declared,field.get(v)); + scope.toString(); + org.junit.Assert.assertSame(declared,field.get(v)); + } + + @Test public void testPrintingLazyMemory() throws Exception { + var code = new CodeGen("return 0;").parse(); + var base = new ConstantNode(com.seaofnodes.simple.type.TypeMem.BOT); + var outer = new ScopeNode(); + var inner = new ScopeNode(); + var loop = new LoopNode(null,code._start); + loop._type = com.seaofnodes.simple.type.Type.CONTROL; + var outerMem = new MemMergeNode(true); + outerMem.addDef(null); outerMem.addDef(base); outerMem.addDef(base); + outer.addDef(loop); outer.addDef(outerMem); + var innerMem = new MemMergeNode(true); + innerMem.addDef(null); innerMem.addDef(outer); innerMem.addDef(outer); + inner.addDef(loop); inner.addDef(innerMem); + var mem = new MemMergeNode(true); + mem.addDef(null); mem.addDef(base); mem.addDef(inner); + PrintTestSupport.unchanged(mem, () -> org.junit.Assert.assertTrue(mem.toString().contains("Lazy_"))); + } + @Test public void testJig() { diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java index bb7e8716..95fbe3f5 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Ignore; @@ -8,6 +11,25 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter19Test { + @Test public void testPrintingFunctionLookup() { + var code = new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.make((byte)2,TypeTuple.make(TypeInteger.constant(987654)),TypeInteger.constant(123456),1L<<30); + var con = new ConstantNode(tfp); + var call = new CallNode(null,code._start,con,con); + // Diagnostic lookup may construct/intern the return-erased linker key. + con.toString(); + org.junit.Assert.assertNull(call.name()); + + var fun = new FunNode(null,tfp); + fun._name = "printerTarget"; + fun.addDef(code._start); + code.link(fun); + var otherReturn = tfp.makeFrom(TypeInteger.constant(654321)); + org.junit.Assert.assertSame(fun,code.link(otherReturn)); + org.junit.Assert.assertTrue(con.toString().contains("printerTarget")); + assertEquals("printerTarget",call.name()); + } + @Test public void testJig() { diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 008f5e0c..0657e9ad 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.print.ASMPrinter; import org.junit.Assert; @@ -9,6 +10,10 @@ import static com.seaofnodes.simple.Main.PORTS; import static org.junit.Assert.*; public class Chapter20Test { + @Test public void testPrintingRegisters() throws Exception { + com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); + } + @Test public void testJig() { diff --git a/chapter20/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java b/chapter20/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java new file mode 100644 index 00000000..b9b49c9f --- /dev/null +++ b/chapter20/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple.codegen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; +public class PrintRegTestSupport { + public static void check() throws Exception { + var code = new CodeGen("return 0;").parse(); + var alloc = new RegAlloc(code); + var n = new ConstantNode(TypeInteger.ZERO); + var a = new LRG((short)1); + var b = new LRG((short)2); + var c = new LRG((short)3); + a._reg = -1; + c._leader = b; + b._leader = a; + var field = RegAlloc.class.getDeclaredField("_lrgs"); + field.setAccessible(true); + var map = (java.util.Map)field.get(alloc); + map.put(n,c); + assertEquals("V1",alloc.reg(n)); + assertEquals(-1,alloc.regnum(n)); + assertSame(c,map.get(n)); + assertSame(b,c._leader); + assertSame(a,b._leader); + } +} diff --git a/chapter20/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter20/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter20/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i _bigCons = new HashMap<>(); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index bd4cbf35..0c79ecb0 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -124,15 +124,23 @@ public class RegAlloc { } + // Diagnostic lookup: do not compress leaders or rewrite the node mapping. + private LRG _lrg(Node n) { + LRG lrg = _lrgs.get(n); + if( lrg != null ) + while( lrg._leader != null ) lrg = lrg._leader; + return lrg; + } + public short regnum( Node n ) { - LRG lrg = lrg(n); + LRG lrg = _lrg(n); return lrg==null ? -1 : lrg._reg; } // Printable register number for node n String reg( Node n ) { return reg(n,null); } String reg( Node n, FunNode fun ) { - LRG lrg = lrg(n); + LRG lrg = _lrg(n); if( lrg==null ) return null; // No register yet, use LRG if( lrg._reg == -1 ) return "V"+lrg._lrg; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CallNode.java index 78a0b153..ea84937b 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -32,8 +32,10 @@ public class CallNode extends CFGNode { return sb.append(")"); } public String name() { - if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() ) - return CodeGen.CODE.link(tfp)._name; + if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() && tfp.notNull() ) { + FunNode fun = CodeGen.CODE.link(tfp); + return fun==null ? null : fun._name; + } return null; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 79f301c1..3ffd430b 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -43,7 +43,7 @@ public class ConstantNode extends Node { @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( _con instanceof TypeFunPtr tfp && tfp.isConstant() ) { + if( _con instanceof TypeFunPtr tfp && tfp.isConstant() && tfp.notNull() ) { FunNode fun = CodeGen.CODE.link(tfp); if( fun!=null && fun._name != null ) return sb.append("{ ").append(fun._name).append("}"); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 32c25a8b..72e381ca 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -38,7 +38,7 @@ public class MemMergeNode extends Node { Node n = in(j); while( n instanceof ScopeNode loop ) { sb.append("Lazy_"); - n = loop.mem(j); + n = loop.mem().alias(j); } if( n==null ) sb.append("___ "); else n._print0(sb, visited).append(" "); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 38343648..298c5a5f 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -50,7 +50,7 @@ public class ScopeNode extends MemMergeNode { for( int i=0; i targets = new HashSet<>(); + Set targets = Collections.newSetFromMap(new IdentityHashMap<>()); sb.p("--- Constant Pool ------").nl(); // By log size for( int log = 3; log >= 0; log-- ) { - for( Node op : enc._bigCons.keySet() ) { - Encoding.Relo relo = enc._bigCons.get(op); + for( Encoding.Relo relo : enc._bigCons.values() ) { if( targets.contains(relo._t) ) continue; targets.add(relo._t); - if( relo._t.log_size()==log ) { + if( relo._align==log ) { sb.hex2(iadr).p(" "); if( relo._t instanceof TypeTuple tt ) { for( Type tx : tt._types ) { diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/IRPrinter.java b/chapter21/src/main/java/com/seaofnodes/simple/print/IRPrinter.java index c6e478c5..82090c78 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/print/IRPrinter.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/print/IRPrinter.java @@ -221,6 +221,26 @@ public abstract class IRPrinter { return sb.toString(); } + // Diagnostic block ordering from raw control edges. Do not call idepth(): + // it fills compiler caches (and can walk lazy dominator accessors). + private static int _idepth(CFGNode cfg, HashMap depths) { + if( cfg == null || cfg instanceof StartNode || cfg instanceof FunNode ) return cfg instanceof FunNode ? 1 : 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available private static String _prettyPrintScheduled( Node node, int depth ) { // Backwards DFS walk to depth. @@ -234,14 +254,15 @@ public abstract class IRPrinter { ds.remove(proj._nid); } } - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); SB sb = new SB(); Ary bns = new Ary<>(Node.class); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ns ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } Integer d = ds.remove(blk._nid); diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter11Test.java index f6539ac4..cab7b7ed 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,10 +1,26 @@ package com.seaofnodes.simple; - import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.IRPrinter; + + import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var code = new CodeGen("while(arg < 10) arg = arg + 1; return arg;").parse().opto().typeCheck().GCM().localSched(); + var stop = code._stop; + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java index c0e28412..b4f6c6ba 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.node.*; + import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; @@ -8,6 +11,38 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testPrintingForwardReferenceScope() throws Exception { + new CodeGen("return 0;").parse(); + var declared = TypeMemPtr.make(TypeStruct.makeFRef("PrintForward")); + var scope = new ScopeNode(); + scope.define("ptr",declared,false,new ConstantNode(TypeInteger.ZERO),null); + Parser.TYPES.put("PrintForward",TypeMemPtr.make(TypeStruct.make("PrintForward"))); + var field = Var.class.getDeclaredField("_type"); + field.setAccessible(true); + var v = scope._vars.get(0); + org.junit.Assert.assertSame(declared,field.get(v)); + scope.toString(); + org.junit.Assert.assertSame(declared,field.get(v)); + } + + @Test public void testPrintingLazyMemory() throws Exception { + var code = new CodeGen("return 0;").parse(); + var base = new ConstantNode(com.seaofnodes.simple.type.TypeMem.BOT); + var outer = new ScopeNode(); + var inner = new ScopeNode(); + var loop = new LoopNode(null,code._start); + loop._type = com.seaofnodes.simple.type.Type.CONTROL; + var outerMem = new MemMergeNode(true); + outerMem.addDef(null); outerMem.addDef(base); outerMem.addDef(base); + outer.addDef(loop); outer.addDef(outerMem); + var innerMem = new MemMergeNode(true); + innerMem.addDef(null); innerMem.addDef(outer); innerMem.addDef(outer); + inner.addDef(loop); inner.addDef(innerMem); + var mem = new MemMergeNode(true); + mem.addDef(null); mem.addDef(base); mem.addDef(inner); + PrintTestSupport.unchanged(mem, () -> org.junit.Assert.assertTrue(mem.toString().contains("Lazy_"))); + } + @Test public void testJig() { diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java index bce75c81..1c427d4f 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; @@ -9,6 +12,25 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter19Test { + @Test public void testPrintingFunctionLookup() { + var code = new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.make((byte)2,TypeTuple.make(TypeInteger.constant(987654)),TypeInteger.constant(123456),1L<<30); + var con = new ConstantNode(tfp); + var call = new CallNode(null,code._start,con,con); + // Diagnostic lookup may construct/intern the return-erased linker key. + con.toString(); + org.junit.Assert.assertNull(call.name()); + + var fun = new FunNode(null,tfp); + fun._name = "printerTarget"; + fun.addDef(code._start); + code.link(fun); + var otherReturn = tfp.makeFrom(TypeInteger.constant(654321)); + org.junit.Assert.assertSame(fun,code.link(otherReturn)); + org.junit.Assert.assertTrue(con.toString().contains("printerTarget")); + assertEquals("printerTarget",call.name()); + } + @Test public void testJig() { diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 5b33d1e7..21f096b9 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.print.ASMPrinter; import java.io.IOException; @@ -11,6 +12,10 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter20Test { + @Test public void testPrintingRegisters() throws Exception { + com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); + } + @Test public void testJig() { diff --git a/chapter21/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java b/chapter21/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java new file mode 100644 index 00000000..b9b49c9f --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple.codegen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; +public class PrintRegTestSupport { + public static void check() throws Exception { + var code = new CodeGen("return 0;").parse(); + var alloc = new RegAlloc(code); + var n = new ConstantNode(TypeInteger.ZERO); + var a = new LRG((short)1); + var b = new LRG((short)2); + var c = new LRG((short)3); + a._reg = -1; + c._leader = b; + b._leader = a; + var field = RegAlloc.class.getDeclaredField("_lrgs"); + field.setAccessible(true); + var map = (java.util.Map)field.get(alloc); + map.put(n,c); + assertEquals("V1",alloc.reg(n)); + assertEquals(-1,alloc.regnum(n)); + assertSame(c,map.get(n)); + assertSame(b,c._leader); + assertSame(a,b._leader); + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter21/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i _bigCons = new HashMap<>(); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 57d0d90c..835ca2a5 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -124,15 +124,23 @@ public class RegAlloc { } + // Diagnostic lookup: do not compress leaders or rewrite the node mapping. + private LRG _lrg(Node n) { + LRG lrg = _lrgs.get(n); + if( lrg != null ) + while( lrg._leader != null ) lrg = lrg._leader; + return lrg; + } + public short regnum( Node n ) { - LRG lrg = lrg(n); + LRG lrg = _lrg(n); return lrg==null ? -1 : lrg._reg; } // Printable register number for node n String reg( Node n ) { return reg(n,null); } String reg( Node n, FunNode fun ) { - LRG lrg = lrg(n); + LRG lrg = _lrg(n); if( lrg==null ) return null; // No register yet, use LRG if( lrg._reg == -1 ) return "V"+lrg._lrg; diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/CallNode.java index 8b243e87..94935e7c 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -32,7 +32,7 @@ public class CallNode extends CFGNode { return sb.append(")"); } public String name() { - if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { + if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() && tfp.notNull() ) { FunNode fun = CodeGen.CODE.link(tfp); if( fun !=null ) return fun._name; if( fptr() instanceof ExternNode ex ) return ex._extern; diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 79f301c1..3ffd430b 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -43,7 +43,7 @@ public class ConstantNode extends Node { @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( _con instanceof TypeFunPtr tfp && tfp.isConstant() ) { + if( _con instanceof TypeFunPtr tfp && tfp.isConstant() && tfp.notNull() ) { FunNode fun = CodeGen.CODE.link(tfp); if( fun!=null && fun._name != null ) return sb.append("{ ").append(fun._name).append("}"); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 9f2fdd16..087cc18e 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -38,7 +38,7 @@ public class MemMergeNode extends Node { Node n = in(j); while( n instanceof ScopeNode loop ) { sb.append("Lazy_"); - n = loop.mem(j); + n = loop.mem().alias(j); } if( n==null ) sb.append("___ "); else n._print0(sb, visited).append(" "); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 828fa4d6..804d9cdd 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -53,7 +53,7 @@ public class ScopeNode extends MemMergeNode { for( int i=0; i[] raligns = new Ary[5]; - for( Node op : enc._bigCons.keySet() ) { - Relo relo = enc._bigCons.get(op); - int align = relo._t.alignment(); + for( Relo relo : enc._bigCons.values() ) { + int align = relo._align; Ary relos = raligns[align]==null ? (raligns[align]=new Ary<>( Relo.class)) : raligns[align]; relos.add(relo); } - HashSet targets = new HashSet<>(); + Set targets = Collections.newSetFromMap(new IdentityHashMap<>()); sb.p("--- Constant Pool ------").nl(); // By alignment @@ -55,7 +56,7 @@ public abstract class ASMPrinter { } case TypeStruct ts -> { - int sz = ts.size(); + int sz = relo._structSize; int log = 1< depths) { + if( cfg == null || cfg instanceof StartNode || cfg instanceof FunNode ) return cfg instanceof FunNode ? 1 : 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available private static String _prettyPrintScheduled( Node node, int depth ) { // Backwards DFS walk to depth. @@ -234,14 +254,15 @@ public abstract class IRPrinter { ds.remove(proj._nid); } } - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); SB sb = new SB(); Ary bns = new Ary<>(Node.class); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ns ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } Integer d = ds.remove(blk._nid); diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter11Test.java index f6539ac4..cab7b7ed 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,10 +1,26 @@ package com.seaofnodes.simple; - import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.IRPrinter; + + import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var code = new CodeGen("while(arg < 10) arg = arg + 1; return arg;").parse().opto().typeCheck().GCM().localSched(); + var stop = code._stop; + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 00d41a23..9bdf8aac 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.node.*; + import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; @@ -8,6 +11,38 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testPrintingForwardReferenceScope() throws Exception { + new CodeGen("return 0;").parse(); + var declared = TypeMemPtr.make(TypeStruct.makeFRef("PrintForward")); + var scope = new ScopeNode(); + scope.define("ptr",declared,false,new ConstantNode(TypeInteger.ZERO),null); + Parser.TYPES.put("PrintForward",TypeMemPtr.make(TypeStruct.make("PrintForward"))); + var field = Var.class.getDeclaredField("_type"); + field.setAccessible(true); + var v = scope._vars.get(0); + org.junit.Assert.assertSame(declared,field.get(v)); + scope.toString(); + org.junit.Assert.assertSame(declared,field.get(v)); + } + + @Test public void testPrintingLazyMemory() throws Exception { + var code = new CodeGen("return 0;").parse(); + var base = new ConstantNode(com.seaofnodes.simple.type.TypeMem.BOT); + var outer = new ScopeNode(); + var inner = new ScopeNode(); + var loop = new LoopNode(null,code._start); + loop._type = com.seaofnodes.simple.type.Type.CONTROL; + var outerMem = new MemMergeNode(true); + outerMem.addDef(null); outerMem.addDef(base); outerMem.addDef(base); + outer.addDef(loop); outer.addDef(outerMem); + var innerMem = new MemMergeNode(true); + innerMem.addDef(null); innerMem.addDef(outer); innerMem.addDef(outer); + inner.addDef(loop); inner.addDef(innerMem); + var mem = new MemMergeNode(true); + mem.addDef(null); mem.addDef(base); mem.addDef(inner); + PrintTestSupport.unchanged(mem, () -> org.junit.Assert.assertTrue(mem.toString().contains("Lazy_"))); + } + @Test public void testJig() { diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java index b8ef22d7..007e50b4 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; @@ -9,6 +12,25 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter19Test { + @Test public void testPrintingFunctionLookup() { + var code = new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.make((byte)2,TypeTuple.make(TypeInteger.constant(987654)),TypeInteger.constant(123456),1L<<30); + var con = new ConstantNode(tfp); + var call = new CallNode(null,code._start,con,con); + // Diagnostic lookup may construct/intern the return-erased linker key. + con.toString(); + org.junit.Assert.assertNull(call.name()); + + var fun = new FunNode(null,tfp,"printerTarget"); + fun._name = "printerTarget"; + fun.addDef(code._start); + code.link(fun); + var otherReturn = tfp.makeFrom(TypeInteger.constant(654321)); + org.junit.Assert.assertSame(fun,code.link(otherReturn)); + org.junit.Assert.assertTrue(con.toString().contains("printerTarget")); + assertEquals("printerTarget",call.name()); + } + @Test public void testJig() { diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java index f442ae1a..f5bd52aa 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.print.ASMPrinter; import java.io.IOException; @@ -11,6 +12,10 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter20Test { + @Test public void testPrintingRegisters() throws Exception { + com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); + } + @Test public void testJig() { diff --git a/chapter22/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java b/chapter22/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java new file mode 100644 index 00000000..b9b49c9f --- /dev/null +++ b/chapter22/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple.codegen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; +public class PrintRegTestSupport { + public static void check() throws Exception { + var code = new CodeGen("return 0;").parse(); + var alloc = new RegAlloc(code); + var n = new ConstantNode(TypeInteger.ZERO); + var a = new LRG((short)1); + var b = new LRG((short)2); + var c = new LRG((short)3); + a._reg = -1; + c._leader = b; + b._leader = a; + var field = RegAlloc.class.getDeclaredField("_lrgs"); + field.setAccessible(true); + var map = (java.util.Map)field.get(alloc); + map.put(n,c); + assertEquals("V1",alloc.reg(n)); + assertEquals(-1,alloc.regnum(n)); + assertSame(c,map.get(n)); + assertSame(b,c._leader); + assertSame(a,b._leader); + } +} diff --git a/chapter22/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter22/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter22/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i _bigCons = new HashMap<>(); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index da521082..10297a9a 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -124,15 +124,23 @@ public class RegAlloc { } + // Diagnostic lookup: do not compress leaders or rewrite the node mapping. + private LRG _lrg(Node n) { + LRG lrg = _lrgs.get(n); + if( lrg != null ) + while( lrg._leader != null ) lrg = lrg._leader; + return lrg; + } + public short regnum( Node n ) { - LRG lrg = lrg(n); + LRG lrg = _lrg(n); return lrg==null ? -1 : lrg._reg; } // Printable register number for node n String reg( Node n ) { return reg(n,null); } String reg( Node n, FunNode fun ) { - LRG lrg = lrg(n); + LRG lrg = _lrg(n); if( lrg==null ) return null; // No register yet, use LRG if( lrg._reg == -1 ) return "V"+lrg._lrg; diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/CallNode.java index ba08c87a..633197fa 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -32,7 +32,7 @@ public class CallNode extends CFGNode { return sb.append(")"); } public String name() { - if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { + if( fptr()._type instanceof TypeFunPtr tfp && tfp._isConstant() && tfp.notNull() ) { FunNode fun = CodeGen.CODE.link(tfp); if( fun !=null ) return fun._name; if( fptr() instanceof ExternNode ex ) return ex._extern; diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 22bf03c4..15d98a67 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -36,7 +36,7 @@ public class ConstantNode extends Node { @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( _con instanceof TypeFunPtr tfp && tfp.isConstant() ) { + if( _con instanceof TypeFunPtr tfp && tfp._isConstant() && tfp.notNull() ) { FunNode fun = CodeGen.CODE.link(tfp); if( fun!=null && fun._name != null ) return sb.append("{ ").append(fun._name).append("}"); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 19acc5b9..20aeb454 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -38,7 +38,7 @@ public class MemMergeNode extends Node { Node n = in(j); while( n instanceof ScopeNode loop ) { sb.append("Lazy_"); - n = loop.mem(j); + n = loop.mem().alias(j); } if( n==null ) sb.append("___ "); else n._print0(sb, visited).append(" "); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index d8c07a92..04666956 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -65,7 +65,7 @@ public class ScopeNode extends MemMergeNode { for( int i=0; i[] raligns = new Ary[5]; - for( Node op : enc._bigCons.keySet() ) { - Relo relo = enc._bigCons.get(op); - int align = relo._t.alignment(); + for( Relo relo : enc._bigCons.values() ) { + int align = relo._align; Ary relos = raligns[align]==null ? (raligns[align]=new Ary<>( Relo.class)) : raligns[align]; relos.add(relo); } - HashSet targets = new HashSet<>(); + Set targets = Collections.newSetFromMap(new IdentityHashMap<>()); sb.p("--- Constant Pool ------").nl(); // By alignment @@ -55,7 +56,7 @@ public abstract class ASMPrinter { } case TypeStruct ts -> { - int sz = ts.size(); + int sz = relo._structSize; int log = 1< depths) { + if( cfg == null || cfg instanceof StartNode || cfg instanceof FunNode ) return cfg instanceof FunNode ? 1 : 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available private static String _prettyPrintScheduled( Node node, int depth ) { // Backwards DFS walk to depth. @@ -234,14 +254,15 @@ public abstract class IRPrinter { ds.remove(proj._nid); } } - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); SB sb = new SB(); Ary bns = new Ary<>(Node.class); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ns ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } Integer d = ds.remove(blk._nid); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index b21dd451..88ac35c5 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -135,7 +135,7 @@ public class TypeFunPtr extends TypeNil { @Override public boolean isHigh() { return _nil <= 1 || (_nil==2 && _fidxs==0); } - @Override boolean _isConstant() { return (_nil==2 && Long.bitCount(_fidxs)==1) || (_nil==3 && _fidxs==0); } + @Override public boolean _isConstant() { return (_nil==2 && Long.bitCount(_fidxs)==1) || (_nil==3 && _fidxs==0); } @Override boolean _isFinal() { return true; } @Override boolean _isGLB(boolean mem) { return true; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 99f237a9..1d398e3b 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -89,7 +89,7 @@ public class TypeInteger extends Type { if( this==I16 || this==U16 ) return 1; // 1<<1 == 2 bytes if( this==I32 || this==U32 ) return 2; // 1<<2 == 4 bytes if( this==BOT ) return 3; // 1<<3 == 8 bytes - if( isConstant() ) { // just const here + if( _isConstant() ) { // just const here if (-0xFF <= _min && _min <= 0xFF) return 0; else if (-0xFFFF <= _min && _min <= 0xFFFF) return 1; else if (-0xFFFFFFFFL <= _min && _min <= 0xFFFFFFFFL) return 2; @@ -98,7 +98,7 @@ public class TypeInteger extends Type { throw Utils.TODO(); } - public long value() { assert isConstant(); return _min; } + public long value() { assert _isConstant(); return _min; } // AND-mask of forced zeros. e.g. unsigned types will return their mask; // u8 will return 0xFF. But also a range of 16-18 (0x10-0x12) will return diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 4f70913d..4b8bee40 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,10 +1,26 @@ package com.seaofnodes.simple; - import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.IRPrinter; + + import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var code = new CodeGen("while(arg < 10) arg = arg + 1; return arg;").parse().opto().typeCheck().GCM().localSched(); + var stop = code._stop; + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 42f80d86..704ac120 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.node.*; + import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; @@ -8,6 +11,38 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testPrintingForwardReferenceScope() throws Exception { + new CodeGen("return 0;").parse(); + var declared = TypeMemPtr.make(TypeStruct.open("PrintForward")); + var scope = new ScopeNode(); + scope.define("ptr",declared,false,new ConstantNode(TypeInteger.ZERO),null); + Parser.TYPES.put("PrintForward",TypeMemPtr.make(TypeStruct.make("PrintForward",false))); + var field = Var.class.getDeclaredField("_type"); + field.setAccessible(true); + var v = scope.var(0); + org.junit.Assert.assertSame(declared,field.get(v)); + scope.toString(); + org.junit.Assert.assertSame(declared,field.get(v)); + } + + @Test public void testPrintingLazyMemory() throws Exception { + var code = new CodeGen("return 0;").parse(); + var base = new ConstantNode(com.seaofnodes.simple.type.TypeMem.BOT); + var outer = new ScopeNode(); + var inner = new ScopeNode(); + var loop = new LoopNode(null,code._start); + loop._type = com.seaofnodes.simple.type.Type.CONTROL; + var outerMem = new MemMergeNode(true); + outerMem.addDef(null); outerMem.addDef(base); outerMem.addDef(base); + outer.addDef(loop); outer.addDef(outerMem); + var innerMem = new MemMergeNode(true); + innerMem.addDef(null); innerMem.addDef(outer); innerMem.addDef(outer); + inner.addDef(loop); inner.addDef(innerMem); + var mem = new MemMergeNode(true); + mem.addDef(null); mem.addDef(base); mem.addDef(inner); + PrintTestSupport.unchanged(mem, () -> org.junit.Assert.assertTrue(mem.toString().contains("Lazy_"))); + } + @Test public void testJig() { diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java index e2a155ce..93f31e19 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; @@ -9,6 +12,25 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter19Test { + @Test public void testPrintingFunctionLookup() { + var code = new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.make((byte)2,false,new Type[]{TypeInteger.constant(987654)},TypeInteger.constant(123456),1L<<30); + var con = new ConstantNode(tfp); + var call = new CallNode(null,code._start,con,con); + // Diagnostic lookup may construct/intern the return-erased linker key. + con.toString(); + org.junit.Assert.assertNull(call.name()); + + var fun = new FunNode(null,tfp,"printerTarget"); + fun._name = "printerTarget"; + fun.addDef(code._start); + code.link(fun); + var otherReturn = tfp.makeFrom(TypeInteger.constant(654321)); + org.junit.Assert.assertSame(fun,code.link(otherReturn)); + org.junit.Assert.assertTrue(con.toString().contains("printerTarget")); + assertEquals("printerTarget",call.name()); + } + @Test public void testJig() { diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java index dcea5c87..3f9f4925 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.print.ASMPrinter; import java.io.IOException; @@ -11,6 +12,10 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter20Test { + @Test public void testPrintingRegisters() throws Exception { + com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); + } + @Test public void testJig() { diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 435b675c..45acc62a 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.riscv.riscv; @@ -11,6 +14,23 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter23Test { + @Test public void testDiagnosticTypeAccessors() throws Exception { + new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.TEST; + var field = Type.class.getDeclaredField("VISIT"); + field.setAccessible(true); + var visit = (java.util.Map)field.get(null); + var marker = new Object(); + visit.put(marker,Type.BOTTOM); + try { + assertEquals(0,TypeInteger.ZERO.alignment()); + assertEquals(0,TypeInteger.ZERO.value()); + org.junit.Assert.assertTrue(tfp._isConstant()); + org.junit.Assert.assertSame(Type.BOTTOM,visit.get(marker)); + assertEquals(1,visit.size()); + } finally { visit.clear(); } + } + @Test public void testOrRhsLoopLocal() throws IOException { diff --git a/chapter23/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java b/chapter23/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java new file mode 100644 index 00000000..b9b49c9f --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple.codegen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; +public class PrintRegTestSupport { + public static void check() throws Exception { + var code = new CodeGen("return 0;").parse(); + var alloc = new RegAlloc(code); + var n = new ConstantNode(TypeInteger.ZERO); + var a = new LRG((short)1); + var b = new LRG((short)2); + var c = new LRG((short)3); + a._reg = -1; + c._leader = b; + b._leader = a; + var field = RegAlloc.class.getDeclaredField("_lrgs"); + field.setAccessible(true); + var map = (java.util.Map)field.get(alloc); + map.put(n,c); + assertEquals("V1",alloc.reg(n)); + assertEquals(-1,alloc.regnum(n)); + assertSame(c,map.get(n)); + assertSame(b,c._leader); + assertSame(a,b._leader); + } +} diff --git a/chapter23/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter23/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i _bigCons = new HashMap<>(); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index da521082..10297a9a 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -124,15 +124,23 @@ public class RegAlloc { } + // Diagnostic lookup: do not compress leaders or rewrite the node mapping. + private LRG _lrg(Node n) { + LRG lrg = _lrgs.get(n); + if( lrg != null ) + while( lrg._leader != null ) lrg = lrg._leader; + return lrg; + } + public short regnum( Node n ) { - LRG lrg = lrg(n); + LRG lrg = _lrg(n); return lrg==null ? -1 : lrg._reg; } // Printable register number for node n String reg( Node n ) { return reg(n,null); } String reg( Node n, FunNode fun ) { - LRG lrg = lrg(n); + LRG lrg = _lrg(n); if( lrg==null ) return null; // No register yet, use LRG if( lrg._reg == -1 ) return "V"+lrg._lrg; diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/CallNode.java index 47dfdf19..965efd99 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -32,8 +32,8 @@ public class CallNode extends CFGNode { return sb.append(")"); } public String name() { - if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { - FunNode fun = CodeGen.CODE.link(tfp); + if( fptr()._type instanceof TypeFunPtr tfp && tfp._isConstant() && tfp.notNull() ) { + FunNode fun = CodeGen.CODE._link(tfp); if( fun !=null ) return fun._name; if( fptr() instanceof ExternNode ex ) return ex._extern; } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 22bf03c4..d5d70a0f 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -36,8 +36,8 @@ public class ConstantNode extends Node { @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( _con instanceof TypeFunPtr tfp && tfp.isConstant() ) { - FunNode fun = CodeGen.CODE.link(tfp); + if( _con instanceof TypeFunPtr tfp && tfp._isConstant() && tfp.notNull() ) { + FunNode fun = CodeGen.CODE._link(tfp); if( fun!=null && fun._name != null ) return sb.append("{ ").append(fun._name).append("}"); } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 9ab57714..2a399b97 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -38,7 +38,7 @@ public class MemMergeNode extends Node { Node n = in(j); while( n instanceof ScopeNode loop ) { sb.append("Lazy_"); - n = loop.mem(j); + n = loop.mem().alias(j); } if( n==null ) sb.append("___ "); else n._print0(sb, visited).append(" "); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index d8c07a92..04666956 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -65,7 +65,7 @@ public class ScopeNode extends MemMergeNode { for( int i=0; i[] raligns = new Ary[5]; - for( Node op : enc._bigCons.keySet() ) { - Relo relo = enc._bigCons.get(op); - int align = relo._t.alignment(); + for( Relo relo : enc._bigCons.values() ) { + int align = relo._align; Ary relos = raligns[align]==null ? (raligns[align]=new Ary<>( Relo.class)) : raligns[align]; relos.add(relo); } - HashSet targets = new HashSet<>(); + Set targets = Collections.newSetFromMap(new IdentityHashMap<>()); sb.p("--- Constant Pool ------").nl(); // By alignment @@ -55,7 +56,7 @@ public abstract class ASMPrinter { } case TypeStruct ts -> { - int sz = ts.size(); + int sz = relo._structSize; int log = 1< depths) { + if( cfg == null || cfg instanceof StartNode || cfg instanceof FunNode ) return cfg instanceof FunNode ? 1 : 0; + Integer old = depths.get(cfg._nid); + if( old != null ) return old; + depths.put(cfg._nid,0); // Break cycles in partially constructed graphs. + int d = 0; + if( cfg instanceof LoopNode ) { + d = _idepth((CFGNode)cfg.in(1),depths)+1; + } else if( cfg instanceof RegionNode || cfg instanceof StopNode ) { + for( Node n : cfg._inputs ) + if( n instanceof CFGNode pred ) d = Math.max(d,_idepth(pred,depths)+1); + } else if( cfg.in(0) instanceof CFGNode pred ) { + d = _idepth(pred,depths)+1; + } + depths.put(cfg._nid,d); + return d; + } + // Bulk pretty printer, knowing scheduling information is available private static String _prettyPrintScheduled( Node node, int depth ) { // Backwards DFS walk to depth. @@ -234,14 +254,15 @@ public abstract class IRPrinter { ds.remove(proj._nid); } } - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap depths = new HashMap<>(); SB sb = new SB(); Ary bns = new Ary<>(Node.class); while( !ds.isEmpty() ) { CFGNode blk = null; for( Node n : ns ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); - if( blk==null || cfg.idepth() < blk.idepth() ) + if( blk==null || _idepth(cfg,depths) < _idepth(blk,depths) ) blk = cfg; } Integer d = ds.remove(blk._nid); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index ddef9651..2e957005 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -135,7 +135,7 @@ public class TypeFunPtr extends TypeNil { @Override public boolean isHigh() { return _nil <= 1 || (_nil==2 && _fidxs==0); } - @Override boolean _isConstant() { return (_nil==2 && Long.bitCount(_fidxs)==1) || (_nil==3 && _fidxs==0); } + @Override public boolean _isConstant() { return (_nil==2 && Long.bitCount(_fidxs)==1) || (_nil==3 && _fidxs==0); } @Override boolean _isFinal() { return true; } @Override boolean _isGLB(boolean mem) { return true; } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 97c17a34..a0cb12cb 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -116,7 +116,7 @@ public class TypeInteger extends Type { if( this==I16 || this==U16 ) return 1; // 1<<1 == 2 bytes if( this==I32 || this==U32 ) return 2; // 1<<2 == 4 bytes if( this==BOT ) return 3; // 1<<3 == 8 bytes - if( isConstant() ) { // just const here + if( _isConstant() ) { // just const here if (-0xFF <= _min && _min <= 0xFF) return 0; else if (-0xFFFF <= _min && _min <= 0xFFFF) return 1; else if (-0xFFFFFFFFL <= _min && _min <= 0xFFFFFFFFL) return 2; @@ -126,7 +126,7 @@ public class TypeInteger extends Type { throw Utils.TODO(); } - public long value() { assert isConstant(); return _min; } + public long value() { assert _isConstant(); return _min; } // AND-mask of forced zeros. e.g. unsigned types will return their mask; // u8 will return 0xFF. But also a range of 16-18 (0x10-0x12) will return diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 99aa9579..0ff13744 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,10 +1,26 @@ package com.seaofnodes.simple; - import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.IRPrinter; + + import org.junit.Test; import static org.junit.Assert.assertEquals; public class Chapter11Test { + @Test public void testPrintingPreservesGraph() throws Exception { + var code = new CodeGen("while(arg < 10) arg = arg + 1; return arg;").parse().opto().typeCheck().GCM().localSched(); + var stop = code._stop; + var bfs = new IRPrinter.BFS(stop,99); + for( var n : bfs._bfs ) + if( n instanceof com.seaofnodes.simple.node.CFGNode cfg ) cfg._idepth = 0; + new com.seaofnodes.simple.node.ConstantNode(com.seaofnodes.simple.type.TypeInteger.constant(123456)); + com.seaofnodes.simple.node.PrintTestSupport.unchanged(stop, () -> { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + @Test public void testPrimes() { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 00b6292e..764356cf 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.node.*; + import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; @@ -8,6 +11,38 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testPrintingForwardReferenceScope() throws Exception { + new CodeGen("return 0;").parse(); + var declared = TypeMemPtr.make(TypeStruct.open("PrintForward")); + var scope = new ScopeNode(); + scope.define("ptr",declared,false,new ConstantNode(TypeInteger.ZERO),null); + Parser.TYPES.put("PrintForward",TypeMemPtr.make(TypeStruct.make("PrintForward",false))); + var field = Var.class.getDeclaredField("_type"); + field.setAccessible(true); + var v = scope.var(0); + org.junit.Assert.assertSame(declared,field.get(v)); + scope.toString(); + org.junit.Assert.assertSame(declared,field.get(v)); + } + + @Test public void testPrintingLazyMemory() throws Exception { + var code = new CodeGen("return 0;").parse(); + var base = new ConstantNode(com.seaofnodes.simple.type.TypeMem.BOT); + var outer = new ScopeNode(); + var inner = new ScopeNode(); + var loop = new LoopNode(null,code._start); + loop._type = com.seaofnodes.simple.type.Type.CONTROL; + var outerMem = new MemMergeNode(true); + outerMem.addDef(null); outerMem.addDef(base); outerMem.addDef(base); + outer.addDef(loop); outer.addDef(outerMem); + var innerMem = new MemMergeNode(true); + innerMem.addDef(null); innerMem.addDef(outer); innerMem.addDef(outer); + inner.addDef(loop); inner.addDef(innerMem); + var mem = new MemMergeNode(true); + mem.addDef(null); mem.addDef(base); mem.addDef(inner); + PrintTestSupport.unchanged(mem, () -> org.junit.Assert.assertTrue(mem.toString().contains("Lazy_"))); + } + @Test public void testJig() { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 6d751946..b9764607 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; @@ -9,6 +12,25 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter19Test { + @Test public void testPrintingFunctionLookup() { + var code = new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.make((byte)2,false,new Type[]{TypeInteger.constant(987654)},TypeInteger.constant(123456),1L<<30); + var con = new ConstantNode(tfp); + var call = new CallNode(null,code._start,con,con); + // Diagnostic lookup may construct/intern the return-erased linker key. + con.toString(); + org.junit.Assert.assertNull(call.name()); + + var fun = new FunNode(null,tfp,"printerTarget"); + fun._name = "printerTarget"; + fun.addDef(code._start); + code.link(fun); + var otherReturn = tfp.makeFrom(TypeInteger.constant(654321)); + org.junit.Assert.assertSame(fun,code._link(otherReturn)); + org.junit.Assert.assertTrue(con.toString().contains("printerTarget")); + assertEquals("printerTarget",call.name()); + } + @Test public void testJig() { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 02de57a2..c422ea07 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,11 +1,16 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.codegen.CodeGen; import java.io.IOException; import org.junit.Test; import static org.junit.Assert.*; public class Chapter20Test { + @Test public void testPrintingRegisters() throws Exception { + com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); + } + @Test public void testJig() { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 400f6b52..56a672aa 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.riscv.riscv; @@ -11,6 +14,28 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter23Test { + @Test public void testDiagnosticTypeAccessors() throws Exception { + new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.TEST; + var con = new ConstantNode(tfp); + var call = new CallNode(null,con,con,con); + var field = Type.class.getDeclaredField("VISIT"); + field.setAccessible(true); + var visit = (java.util.Map)field.get(null); + var marker = new Object(); + visit.put(marker,Type.BOTTOM); + try { + assertEquals(0,TypeInteger.ZERO.alignment()); + assertEquals(0,TypeInteger.ZERO.value()); + org.junit.Assert.assertTrue(tfp._isConstant()); + con.toString(); + call.name(); + con.p(1); + org.junit.Assert.assertSame(Type.BOTTOM,visit.get(marker)); + assertEquals(1,visit.size()); + } finally { visit.clear(); } + } + @Test public void testOrRhsLoopLocal() throws IOException { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java index 1d67949a..a4fb5829 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.riscv.riscv; @@ -7,6 +10,23 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter24Test { + @Test public void testPrintingDeadFunction() throws Exception { + var code = new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.TEST; + var fun = new FunNode(null,tfp,"deadPrinterTarget"); + org.junit.Assert.assertTrue(fun.isDead()); + code.link(fun); + var con = new ConstantNode(tfp); + var call = new CallNode(null,con,con,con); + con.toString(); + call.name(); + + org.junit.Assert.assertSame(fun,code._link(tfp)); + // Optimizer lookup still performs its usual lazy cleanup. + org.junit.Assert.assertNull(code.link(tfp)); + org.junit.Assert.assertNull(code._link(tfp)); + } + @Test public void testJig() throws IOException { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java b/chapter24/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java new file mode 100644 index 00000000..b9b49c9f --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple.codegen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; +public class PrintRegTestSupport { + public static void check() throws Exception { + var code = new CodeGen("return 0;").parse(); + var alloc = new RegAlloc(code); + var n = new ConstantNode(TypeInteger.ZERO); + var a = new LRG((short)1); + var b = new LRG((short)2); + var c = new LRG((short)3); + a._reg = -1; + c._leader = b; + b._leader = a; + var field = RegAlloc.class.getDeclaredField("_lrgs"); + field.setAccessible(true); + var map = (java.util.Map)field.get(alloc); + map.put(n,c); + assertEquals("V1",alloc.reg(n)); + assertEquals(-1,alloc.regnum(n)); + assertSame(c,map.get(n)); + assertSame(b,c._leader); + assertSame(a,b._leader); + } +} diff --git a/chapter24/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter24/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..01d471bf --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i CodeGen.Phase.Opto.ordinal() ) return raw(type); if( type instanceof TypeFunPtr tfp && tfp.isConstant() ) { - FunNode fun = CodeGen.CODE.lookupFun(tfp); + FunNode fun = CodeGen.CODE._link(tfp); if( fun != null ) return new FunPtrNode(tfp,CodeGen.CODE._start,fun.ret()).init(); // TODO: A singleton FIDX can also emerge after merging and @@ -74,8 +74,8 @@ public class ConstantNode extends TypeNode { @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( _con instanceof TypeFunPtr tfp && tfp.isConstant() ) { - FunNode fun = CodeGen.CODE.lookupFun(tfp); + if( _con instanceof TypeFunPtr tfp && tfp._isConstant() && tfp.notNull() ) { + FunNode fun = CodeGen.CODE._link(tfp); if( fun!=null && fun._name != null ) return sb.append("{ ").append(fun._name).append("}"); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java index ce53b073..7f0b2b7d 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java @@ -35,7 +35,7 @@ public class FunPtrNode extends TypeNode { @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { - FunNode fun = CodeGen.CODE.lookupFun(((TypeFunPtr)_con).fidx()); + FunNode fun = CodeGen.CODE._link(((TypeFunPtr)_con).fidx()); return fun!=null && fun._name!=null ? sb.append("{ ").append(fun._name).append("}") : sb.append(_con); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 87d982f1..e16eee9e 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -32,7 +32,7 @@ public class MemMergeNode extends Node { Node n = in(j); while( n instanceof ScopeNode loop ) { sb.append("Lazy_"); - n = loop.mem(j); + n = loop.mem(); } if( n==null ) sb.append("___ "); else n._print0(sb, visited).append(" "); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index 7f9f3ad9..ff3eada2 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -8,7 +8,9 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; import java.util.HashMap; -import java.util.HashSet; +import java.util.Collections; +import java.util.IdentityHashMap; +import java.util.Set; public abstract class ASMPrinter { @@ -43,16 +45,15 @@ public abstract class ASMPrinter { sb.p("--- ").p(msg).p(" ------").nl(); // radix sort the big constants by alignment Ary[] raligns = new Ary[5]; - for( Node op : bigCons.keySet() ) { - Relo relo = bigCons.get(op); + for( Relo relo : bigCons.values() ) { if( relo.readOnly() != ro ) continue; - int align = relo._t.alignment(); + int align = relo._align; Ary relos = raligns[align]==null ? (raligns[align]=new Ary<>( Relo.class)) : raligns[align]; relos.add(relo); } - HashSet targets = new HashSet<>(); + Set targets = Collections.newSetFromMap(new IdentityHashMap<>()); // By alignment int dadr=0; @@ -64,7 +65,7 @@ public abstract class ASMPrinter { targets.add(relo._t); sb.hex2(iadr+dadr).p(" "); if( relo._t instanceof TypeStruct ts ) { - int sz = ts.size(); + int sz = relo._structSize; int log = 1< { + String first = stop.p(99); + assertEquals(first,stop.p(99)); + stop.toString(); + }); + } + @Test public void testPrimes() { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java index dc29dafa..d7fd12ff 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.node.*; + import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; @@ -8,6 +11,31 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testPrintingForwardReferenceScope() throws Exception { + new CodeGen("return 0;").parse(); + var declared = TypeMemPtr.make(TypeStruct.make("PrintForward",true,true)); + var scope = new ScopeNode(); + scope.define("ptr",declared,false,new ConstantNode(TypeInteger.ZERO),null); + Parser.TYPES.put("PrintForward",TypeMemPtr.make(TypeStruct.make("PrintForward",false,false))); + var field = Var.class.getDeclaredField("_type"); + field.setAccessible(true); + var v = scope.var(0); + org.junit.Assert.assertSame(declared,field.get(v)); + scope.toString(); + org.junit.Assert.assertSame(declared,field.get(v)); + } + + @Test public void testPrintingLazyMemory() throws Exception { + var code = new CodeGen("return 0;").parse(); + var base = new ConstantNode(com.seaofnodes.simple.type.TypeMem.BOT); + var outer = new ScopeNode(); + var inner = new ScopeNode(); + outer.addDef(null); outer.addDef(base); + inner.addDef(null); inner.addDef(outer); + var mem = new MemMergeNode(null,base,inner); + PrintTestSupport.unchanged(mem, () -> org.junit.Assert.assertTrue(mem.toString().contains("Lazy_"))); + } + @Test public void testJig() { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 10c4690e..5ab7ba97 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; @@ -7,6 +10,25 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter19Test { + @Test public void testPrintingFunctionLookup() { + var code = new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.make1((byte)2,false,new Type[]{TypeInteger.constant(987654)},TypeInteger.constant(123456),30); + var con = ConstantNode.raw(tfp); + var call = new CallNode(null,code._start,con,con); + // Diagnostic lookup may construct/intern the return-erased linker key. + con.toString(); + org.junit.Assert.assertNull(call.name()); + + var fun = new FunNode(null,tfp,"printerTarget",null); + fun._name = "printerTarget"; + fun.addDef(code._start); + code.link(fun); + var otherReturn = tfp.makeFrom(TypeInteger.constant(654321)); + org.junit.Assert.assertSame(fun,code._link(otherReturn)); + org.junit.Assert.assertTrue(con.toString().contains("printerTarget")); + assertEquals("printerTarget",call.name()); + } + @Test public void testJig() { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java index e8a3a875..43112594 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,10 +1,15 @@ package com.seaofnodes.simple; + import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Test; import static org.junit.Assert.*; public class Chapter20Test { + @Test public void testPrintingRegisters() throws Exception { + com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); + } + @Test public void testJig() { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 3346aa51..0e6398ee 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.riscv.riscv; @@ -10,6 +13,28 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter23Test { + @Test public void testDiagnosticTypeAccessors() throws Exception { + new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.TEST; + var con = ConstantNode.raw(tfp); + var call = new CallNode(null,con,con,con); + var field = Type.class.getDeclaredField("VISIT"); + field.setAccessible(true); + var visit = (java.util.Map)field.get(null); + var marker = new Object(); + visit.put(marker,Type.BOTTOM); + try { + assertEquals(0,TypeInteger.ZERO.alignment()); + assertEquals(0,TypeInteger.ZERO.value()); + org.junit.Assert.assertTrue(tfp._isConstant()); + con.toString(); + call.name(); + con.p(1); + org.junit.Assert.assertSame(Type.BOTTOM,visit.get(marker)); + assertEquals(1,visit.size()); + } finally { visit.clear(); } + } + @Test @Ignore public void testJig() throws IOException { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java index eb89dbb3..1307d2ce 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -1,4 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.riscv.riscv; @@ -7,6 +10,23 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter24Test { + @Test public void testPrintingDeadFunction() throws Exception { + var code = new CodeGen("return 0;").parse(); + var tfp = TypeFunPtr.TEST; + var fun = new FunNode(null,tfp,"deadPrinterTarget",null); + org.junit.Assert.assertTrue(fun.isDead()); + code.link(fun); + var con = ConstantNode.raw(tfp); + var call = new CallNode(null,con,con,con); + con.toString(); + call.name(); + code.funcName(tfp.fidx()); + org.junit.Assert.assertSame(fun,code._link(tfp)); + // Optimizer lookup still performs its usual lazy cleanup. + org.junit.Assert.assertNull(code.link(tfp)); + org.junit.Assert.assertNull(code._link(tfp)); + } + @Test public void testJig() throws IOException { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java index d2357ef1..b96ae836 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -20,6 +20,10 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter25Test { + @Test public void testPrintingConstantPool() throws Exception { + com.seaofnodes.simple.codegen.PrintRegTestSupport.checkConstantPool(); + } + @Ignore @Test diff --git a/chapter25/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java b/chapter25/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java new file mode 100644 index 00000000..b255bcf7 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java @@ -0,0 +1,76 @@ +package com.seaofnodes.simple.codegen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; +public class PrintRegTestSupport { + public static void check() throws Exception { + var code = new CodeGen("return 0;").parse(); + var alloc = new RegAlloc(code); + var n = new ConstantNode(TypeInteger.ZERO); + var a = new LRG((short)1,null); + var b = new LRG((short)2,null); + var c = new LRG((short)3,null); + a._reg = -1; + c._leader = b; + b._leader = a; + var field = RegAlloc.class.getDeclaredField("_lrgs"); + field.setAccessible(true); + var map = (java.util.Map)field.get(alloc); + map.put(n,c); + assertEquals("V1",alloc.reg(n)); + assertEquals(-1,alloc.regnum(n)); + assertSame(c,map.get(n)); + assertSame(b,c._leader); + assertSame(a,b._leader); + } + public static void checkConstantPool() throws Exception { + var code = new CodeGen("return 0;").parse(); + code._phase = CodeGen.Phase.Encoding; + var enc = new Encoding(code); + var t = com.seaofnodes.simple.type.TypeStruct.make("PrintPool",false, + com.seaofnodes.simple.type.Field.make("x",TypeInteger.ZERO,2,true)); + var n = new ConstantNode(TypeInteger.ZERO); + enc.largeConstant(n,t,0,2); + int size = t.size(); // Encoding lays out data before printing the pool. + for( int i=0; i)field.get(null); + var marker = new Object(); + visit.put(marker,t); + var method = com.seaofnodes.simple.print.ASMPrinter.class.getDeclaredMethod( + "printConstantPool",int.class,com.seaofnodes.simple.util.SB.class, + com.seaofnodes.simple.util.BAOS.class,java.util.HashMap.class,boolean.class,String.class); + method.setAccessible(true); + try { + var sb = new com.seaofnodes.simple.util.SB(); + method.invoke(null,0,sb,enc._cpool,enc._bigCons,true,"Constant Pool"); + assertTrue(sb.toString().contains("PrintPool")); + assertTrue(sb.toString().contains("LayoutProbe")); + assertNull(offsets.get(t)); + assertSame(t,visit.get(marker)); + assertEquals(1,visit.size()); + } finally { visit.clear(); } + } +} diff --git a/chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java b/chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java new file mode 100644 index 00000000..70d9071a --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/node/PrintTestSupport.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple.node; +import java.util.*; +import static org.junit.Assert.*; + +// Inspect raw fields: the regression must not itself use lazy accessors. +public class PrintTestSupport { + public static void unchanged(Node root, Runnable print) throws Exception { + var hash = Node.class.getDeclaredField("_hash"); + hash.setAccessible(true); + var nodes = new ArrayList(); + var seen = new IdentityHashMap(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i(); + var outs = new IdentityHashMap(); + var hashes = new IdentityHashMap(); + var depths = new IdentityHashMap(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + } + print.run(); + for( Node n : nodes ) { + assertEquals("hash of node "+n._nid,(int)hashes.get(n),hash.getInt(n)); + assertEquals(ins.get(n).length,n.nIns()); + assertEquals(outs.get(n).length,n.nOuts()); + for( int i=0; i` reduces to returning the static object, with no remaining + I/O or public-memory effects, its runtime work can disappear. Initially it + is sufficient to emit a trivial `` and keep its calls. Omitting the + function or calls is a later optimization; mixed initializers retain their + remaining effects. Adapt this conceptual return to the existing class-memory + representation rather than assuming the current `` returns a pointer. +- Extend encoding's relocation information to describe addresses stored inside + data: functions, other class objects, and constant objects such as strings. + Emit the required data-section relocations, including their symbol, field + offset, width, and addend. Keep native linking and emulator linking consistent. +- Give the function and data distinct stable symbols, e.g. `A.B.` and + `A.B.$class`. The defining CompUnit owns the class object and emits its one + definition in its ELF. Other compilation units, including source currently + being compiled, reference those symbols without emitting another copy of the + class data. Unifying loaded Simple types/IR alone does not unify native data; + preserve ownership and identity across partial compiles and serialization. +- Target four-byte function **and data** pointers, with code and data addresses + restricted to the low 4 GB. Function pointers stay four bytes; data pointers + must be brought into agreement. Account for layout, loads/stores, relocations, + native runtime/FFI boundaries, and actual placement; do not silently truncate + an out-of-range address. This is a proposed representation constraint, not a + claim that the current runtime already satisfies it. +- Emit immutable, fully preinitialized objects in read-only storage. Objects + with mutable fields or remaining runtime initialization writes stay writable. + Retain the current writable-class-storage correction until those writes have + actually been eliminated. + +Acceptance should cover scalar and pointer fields, shared/cyclic object +references, preserved effects in mixed initializers, and serialization +round-trips. A diamond of separately compiled users must share one class-object +address and observe each other's mutations. Check ELF definitions/relocations, +address-range enforcement, native execution, emulator execution, and the full +Chapter 25 suite, including `make -j 4 tests`. + ## Larger or entangled changes: defer | Group | Eventual home | Why not in the small queue yet | @@ -80,6 +132,40 @@ 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`. +### B09: complete locally, 2026-09-19 + +Audited `Node.p(depth)`, recursive printing, labels, scope/graph viewers, and +assembly helpers. Corrections follow the first affected representation: + +- 11-24: scheduled IR display uses local `_idepth` state; 11-14 also use + identity maps to avoid setting Node hashes/GVN locks. +- 18-24: memory display reads raw lazy aliases instead of creating Phis; + scope display uses `Var._type` without resolving forward references. + 25's stale alias-based memory display reads its actual bulk-memory input. +- 19-23: printers use ordinary `link` and tolerate missing targets. Per Cliff's + review, type interning is allowed: the proposed non-interning linker scan and + `sameTarget` helper were removed. 24-25 use `CodeGen._link` to preserve dead + entries, including through 25's `funcName`; optimizing `link` still cleans up. +- 20-25: register display uses `_lrg` without compressing chains or rewriting + node mappings. Function predicates use the existing leaf `_isConstant` from + 23; integer size/value accessors also avoid entering shared recursion state. +- 21-25: pool display uses identity bookkeeping and recorded alignment, plus + recorded struct size from 22 and section choice in 25. Printers do not ask + Types for layouts, even when an answer might already be cached. Layout is + separate from type identity and may eventually move out of TypeStruct. + +Regressions cover graph caches/edges, lazy Phis, unresolved declarations, stale +linker entries, register chains, leaf type accessors, and forbidden layout queries. +Isolated original Chapter 18 classes fail the lazy-memory and forward-reference +tests; original printers also reproduce cache mutation, register compression, +shared-scratch assertions, and dead-linker pruning. Tests permit type interning. + +Every affected compiler snapshot (11-25) passed its full `make tests` target with +assertions enabled after the review adjustment, including 443 tests in 25. +The constant-pool regression rejects size/alignment queries even if they would +return cached answers. Log: `chapter25/build/b09-review/revised.log`. +Durable rules are in the skills notes. + ### B13 / issue #246: complete, 2026-09-19 Cliff reports the correction pushed. Nested negation in `p != null` / `!!p` diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index bb75ac56..ab16e8ee 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -214,6 +214,36 @@ Consequences: aligned with `modrm`; reversing it silently selects the wrong extended registers. The Chapter 25 Bubble Sort failure exposed this in `MulIX86`. +## Side-effect-free diagnostics: B09 lessons + +- Type construction and interning are allowed during printing. Do not add + alternate linker-key comparisons or other machinery merely to avoid interning; + canonical types and fast identity comparisons are normal type-system operations. +- Type layout queries are forbidden during printing, including queries that + currently return cached answers. Layout lives in TypeStruct for convenience, + but is separate from type identity and lattice operations. It may eventually + move elsewhere to support removing dead fields or packing fields with limited + states. Capture size, alignment, and section choice during encoding; printers + display that recorded layout instead of asking Types to compute one. +- Use the `_` prefix for no-side-effect variants of accessors: `CodeGen._link`, + `RegAlloc._lrg`, `Var._type`, and the existing leaf `_isConstant` predicates. + The printer's local `_idepth` does not populate compiler dominator caches. + Keep mutating compiler accessors available for their normal jobs. +- Audit the whole call chain from `Node.p(depth)`, `print`/`toString`, labels, + scope/graph viewers, and machine `asm` methods. `link` prunes dead functions + starting in Chapter 24; 19-23 can use ordinary `link`, including its interned + return-erased key. Scope memory reads can create lazy Phis, `Var.type()` can + resolve declarations, and register lookups can compress union-find links. +- Use identity bookkeeping for graph inspection: `Node.hashCode()` writes + `_hash`, which also controls GVN locking. Leaf diagnostic type accessors can + use their existing `_` implementations without entering shared Type.VISIT + recursion; this is separate from permission to intern types. +- Test cold caches, unresolved declarations, lazy memory, stale linker entries, + uncompressed register chains, and forbidden layout queries. Do not assert that + printing leaves the type intern table unchanged. B09 regressions start in + Chapter11Test/18Test/19Test/20Test/23Test/24Test and propagate to later snapshots; + Chapter25Test also covers constant-pool display. + ## Debugging workflow 1. Reduce the first semantic or invariant failure before changing architecture. -- cgit v1.2.3