diff options
141 files changed, 2272 insertions, 144 deletions
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<Integer,Integer> 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<Node,Integer> ds = new HashMap<>(); + IdentityHashMap<Node,Integer> ds = new IdentityHashMap<>(); _walk(ds,node,depth); - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap<Integer,Integer> depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList<Node> 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<Node,Integer> ds, Node node, int d ) { + private static void _walk( IdentityHashMap<Node,Integer> 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<Node> bns, int i, HashMap<Node,Integer> ds ) { + static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList<Node> bns, int i, IdentityHashMap<Node,Integer> 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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter12/src/main/java/com/seaofnodes/simple/IRPrinter.java index 43c6c9f7..909dd575 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter12/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<Integer,Integer> 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<Node,Integer> ds = new HashMap<>(); + IdentityHashMap<Node,Integer> ds = new IdentityHashMap<>(); _walk(ds,node,depth); - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap<Integer,Integer> depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList<Node> 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<Node,Integer> ds, Node node, int d ) { + private static void _walk( IdentityHashMap<Node,Integer> 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<Node> bns, int i, HashMap<Node,Integer> ds ) { + static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList<Node> bns, int i, IdentityHashMap<Node,Integer> 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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter13/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter13/src/main/java/com/seaofnodes/simple/IRPrinter.java index 43c6c9f7..909dd575 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter13/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<Integer,Integer> 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<Node,Integer> ds = new HashMap<>(); + IdentityHashMap<Node,Integer> ds = new IdentityHashMap<>(); _walk(ds,node,depth); - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap<Integer,Integer> depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList<Node> 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<Node,Integer> ds, Node node, int d ) { + private static void _walk( IdentityHashMap<Node,Integer> 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<Node> bns, int i, HashMap<Node,Integer> ds ) { + static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList<Node> bns, int i, IdentityHashMap<Node,Integer> 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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter14/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter14/src/main/java/com/seaofnodes/simple/IRPrinter.java index 43c6c9f7..909dd575 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter14/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<Integer,Integer> 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<Node,Integer> ds = new HashMap<>(); + IdentityHashMap<Node,Integer> ds = new IdentityHashMap<>(); _walk(ds,node,depth); - // Print by block with least idepth + // Print by block with least diagnostic depth + HashMap<Integer,Integer> depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList<Node> 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<Node,Integer> ds, Node node, int d ) { + private static void _walk( IdentityHashMap<Node,Integer> 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<Node> bns, int i, HashMap<Node,Integer> ds ) { + static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList<Node> bns, int i, IdentityHashMap<Node,Integer> 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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter15/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter15/src/main/java/com/seaofnodes/simple/IRPrinter.java index 418cda29..2b4e7ec6 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -187,6 +187,26 @@ 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<Integer,Integer> 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<Integer,Integer> depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList<Node> 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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter16/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter16/src/main/java/com/seaofnodes/simple/IRPrinter.java index 418cda29..2b4e7ec6 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -187,6 +187,26 @@ 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<Integer,Integer> 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<Integer,Integer> depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList<Node> 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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter17/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter17/src/main/java/com/seaofnodes/simple/IRPrinter.java index 7ef55a3f..f8691931 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -187,6 +187,26 @@ 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<Integer,Integer> 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<Integer,Integer> depths = new HashMap<>(); StringBuilder sb = new StringBuilder(); ArrayList<Node> 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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java index aa498b16..d563e031 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -172,6 +172,26 @@ 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<Integer,Integer> 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<Integer,Integer> depths = new HashMap<>(); SB sb = new SB(); Ary<Node> 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<nIns(); i++ ) { if( j < _lexSize._len && i == _lexSize.at(j) ) { sb.append("| "); j++; } Var v = _vars.get(i); - sb.append(v.type().print(new SB())); + sb.append(v._type().print(new SB())); sb.append(" "); if( v._final ) sb.append("!"); sb.append(v._name); diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 0b24bd5d..fc9f117c 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,11 +1,26 @@ package com.seaofnodes.simple; + 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/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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter19/src/main/java/com/seaofnodes/simple/IRPrinter.java index 3cddacfd..957a9184 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -170,6 +170,26 @@ public abstract 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<Integer,Integer> 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<Integer,Integer> depths = new HashMap<>(); SB sb = new SB(); Ary<Node> 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<nIns(); i++ ) { if( j < _lexSize._len && i == _lexSize.at(j) ) { sb.append("| "); j++; } Var v = _vars.get(i); - sb.append(v.type().print(new SB())); + sb.append(v._type().print(new SB())); sb.append(" "); if( v._final ) sb.append("!"); sb.append(v._name); diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 0b24bd5d..fc9f117c 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,11 +1,26 @@ package com.seaofnodes.simple; + 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/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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter20/src/main/java/com/seaofnodes/simple/Var.java b/chapter20/src/main/java/com/seaofnodes/simple/Var.java index e71d7ef2..6e621875 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/Var.java +++ b/chapter20/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/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index badec740..335f4530 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -123,14 +123,22 @@ 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 ) { - LRG lrg = lrg(n); + LRG lrg = _lrg(n); if( lrg==null ) return null; if( lrg._reg == -1 ) return "V"+lrg._lrg; return _code._mach.reg(lrg._reg); diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/CallNode.java index c9bbcc52..a3f880b6 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter20/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/chapter20/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index f7ebc006..73ba94ce 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -43,9 +43,9 @@ public class ConstantNode extends Node { @Override 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._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/chapter20/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 1495a703..adf83aab 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter20/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/chapter20/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 3411756d..13ddc53a 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -50,7 +50,7 @@ public class ScopeNode extends MemMergeNode { for( int i=0; i<nIns(); i++ ) { if( j < _lexSize._len && i == _lexSize.at(j) ) { sb.append("| "); j++; } Var v = _vars.get(i); - sb.append(v.type().print(new SB())); + sb.append(v._type().print(new SB())); sb.append(" "); if( v._final ) sb.append("!"); sb.append(v._name); diff --git a/chapter20/src/main/java/com/seaofnodes/simple/print/IRPrinter.java b/chapter20/src/main/java/com/seaofnodes/simple/print/IRPrinter.java index c91f844b..a815e536 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/print/IRPrinter.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/print/IRPrinter.java @@ -219,6 +219,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<Integer,Integer> 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<Integer,Integer> depths = new HashMap<>(); SB sb = new SB(); Ary<Node> 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<Node,LRG>)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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter21/src/main/java/com/seaofnodes/simple/Var.java b/chapter21/src/main/java/com/seaofnodes/simple/Var.java index e71d7ef2..6e621875 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/Var.java +++ b/chapter21/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/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index c35ea6a4..2021c795 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -49,12 +49,14 @@ public class Encoding { public static class Relo { public final Node _op; public final Type _t; // Constant type + public final int _align; // Log alignment, captured for diagnostic display public final byte _off; // Offset from start of opcode public final byte _elf; // ELF relocation type, e.g. 2/PC32 public int _target; // Where constant is finally placede public int _opStart; // Opcode start Relo( Node op, Type t, byte off, byte elf ) { _op=op; _t=t; _off=off; _elf=elf; + _align = t.log_size(); } } public final HashMap<Node,Relo> _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<nIns(); i++ ) { if( j < _lexSize._len && i == _lexSize.at(j) ) { sb.append("| "); j++; } Var v = _vars.get(i); - sb.append(v.type().print(new SB())); + sb.append(v._type().print(new SB())); sb.append(" "); if( v._final ) sb.append("!"); sb.append(v._name); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index da269d31..0582be8c 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -6,7 +6,9 @@ import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import java.util.HashSet; +import java.util.Collections; +import java.util.IdentityHashMap; +import java.util.Set; public abstract class ASMPrinter { @@ -28,15 +30,14 @@ public abstract class ASMPrinter { Encoding enc = code._encoding; if( enc!=null && !enc._bigCons.isEmpty() ) { iadr = (iadr+15)&-16; // pad to 16 - HashSet<Type> targets = new HashSet<>(); + Set<Type> 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<Integer,Integer> 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<Integer,Integer> depths = new HashMap<>(); SB sb = new SB(); Ary<Node> 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<Node,LRG>)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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter22/src/main/java/com/seaofnodes/simple/Var.java b/chapter22/src/main/java/com/seaofnodes/simple/Var.java index cf549cd6..14295395 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/Var.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/Var.java @@ -28,6 +28,8 @@ public class Var { _fref = fref; _loc = loc; } + // 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/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index db799b98..162263d9 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -49,12 +49,16 @@ public class Encoding { public static class Relo { public final Node _op; public final Type _t; // Constant type + public final int _align; // Log alignment, captured for diagnostic display + public final int _structSize; // Capture layout during encoding, not printing public final byte _off; // Offset from start of opcode public final byte _elf; // ELF relocation type, e.g. 2/PC32 public int _target; // Where constant is finally placed public int _opStart; // Opcode start Relo( Node op, Type t, byte off, byte elf ) { _op=op; _t=t; _off=off; _elf=elf; + _align = t.alignment(); + _structSize = t instanceof TypeStruct ts ? ts.size() : 0; } } public final HashMap<Node,Relo> _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<nIns(); i++ ) { if( j < _lexSize._len && i == _lexSize.at(j) ) { sb.append("| "); j++; } Var v = _vars.at(i); - sb.append(v.type().print(new SB())); + sb.append(v._type().print(new SB())); sb.append(" "); if( v._final ) sb.append("!"); sb.append(v._name); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter22/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index 366ae376..c8082841 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -8,7 +8,9 @@ import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.codegen.Encoding.Relo; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import java.util.HashSet; +import java.util.Collections; +import java.util.IdentityHashMap; +import java.util.Set; public abstract class ASMPrinter { @@ -28,14 +30,13 @@ public abstract class ASMPrinter { if( enc!=null && !enc._bigCons.isEmpty() && iadr < enc._bits.size() ) { // radix sort the big constants by alignment Ary<Relo>[] 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<Relo> relos = raligns[align]==null ? (raligns[align]=new Ary<>( Relo.class)) : raligns[align]; relos.add(relo); } - HashSet<Type> targets = new HashSet<>(); + Set<Type> 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<<align; sz = (sz + (log -1)) & -log; // Round up final padding for( int i=0; i<sz; i++ ) diff --git a/chapter22/src/main/java/com/seaofnodes/simple/print/IRPrinter.java b/chapter22/src/main/java/com/seaofnodes/simple/print/IRPrinter.java index c6e478c5..82090c78 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/print/IRPrinter.java +++ b/chapter22/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<Integer,Integer> 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<Integer,Integer> depths = new HashMap<>(); SB sb = new SB(); Ary<Node> 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<Node,LRG>)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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter23/src/main/java/com/seaofnodes/simple/Var.java b/chapter23/src/main/java/com/seaofnodes/simple/Var.java index cf549cd6..14295395 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/Var.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/Var.java @@ -28,6 +28,8 @@ public class Var { _fref = fref; _loc = loc; } + // 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/chapter23/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 1065cd9f..6a16d56b 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -52,12 +52,16 @@ public class Encoding { public static class Relo { public final Node _op; public final Type _t; // Constant type + public final int _align; // Log alignment, captured for diagnostic display + public final int _structSize; // Capture layout during encoding, not printing public final byte _off; // Offset from start of opcode public final byte _elf; // ELF relocation type, e.g. 2/PC32 public int _target; // Where constant is finally placed public int _opStart; // Opcode start Relo( Node op, Type t, byte off, byte elf ) { _op=op; _t=t; _off=off; _elf=elf; + _align = t.alignment(); + _structSize = t instanceof TypeStruct ts ? ts.size() : 0; } } public final HashMap<Node,Relo> _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<nIns(); i++ ) { if( j < depth() && i == _kinds.at(j)._lexSize ) { sb.append("| "); j++; } Var v = _vars.at(i); - sb.append(v.type()); + sb.append(v._type()); sb.append(" "); if( v._final ) sb.append("!"); sb.append(v._name); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter23/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index a9f86ce8..9ee26039 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -8,7 +8,9 @@ import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; -import java.util.HashSet; +import java.util.Collections; +import java.util.IdentityHashMap; +import java.util.Set; public abstract class ASMPrinter { @@ -28,14 +30,13 @@ public abstract class ASMPrinter { if( enc!=null && !enc._bigCons.isEmpty() && iadr < enc._bits.size() ) { // radix sort the big constants by alignment Ary<Relo>[] 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<Relo> relos = raligns[align]==null ? (raligns[align]=new Ary<>( Relo.class)) : raligns[align]; relos.add(relo); } - HashSet<Type> targets = new HashSet<>(); + Set<Type> 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<<align; sz = (sz + (log -1)) & -log; // Round up final padding for( int i=0; i<sz; i++ ) diff --git a/chapter23/src/main/java/com/seaofnodes/simple/print/IRPrinter.java b/chapter23/src/main/java/com/seaofnodes/simple/print/IRPrinter.java index d1265bef..336cf500 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/print/IRPrinter.java +++ b/chapter23/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<Integer,Integer> 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<Integer,Integer> depths = new HashMap<>(); SB sb = new SB(); Ary<Node> 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<Object,Type>)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<Node,LRG>)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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter24/src/main/java/com/seaofnodes/simple/Var.java b/chapter24/src/main/java/com/seaofnodes/simple/Var.java index cf549cd6..14295395 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/Var.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/Var.java @@ -28,6 +28,8 @@ public class Var { _fref = fref; _loc = loc; } + // 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/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 3715d015..c0b8d68e 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -140,7 +140,10 @@ public class CodeGen { // Reverse from a constant function pointer to the IR function being called. // Error to call with a non-constant TFP public FunNode link( TypeFunPtr tfp ) { return link(tfp.fidx()); } - // Return the FunNode from a fidx + // Read-only diagnostic lookup; preserve stale entries. + public FunNode _link(TypeFunPtr tfp) { return _link(tfp.fidx()); } + public FunNode _link(int fidx) { return _linker.atX(fidx); } + // Return the FunNode from a fidx, cleaning up dead entries. public FunNode link( int fidx ) { FunNode fun =_linker.atX(fidx); if( fun!=null && fun.isDead() ) { diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index e3684445..4e7166fa 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -52,12 +52,16 @@ public class Encoding { public static class Relo { public final Node _op; public final Type _t; // Constant type + public final int _align; // Log alignment, captured for diagnostic display + public final int _structSize; // Capture layout during encoding, not printing public final byte _off; // Offset from start of opcode public final byte _elf; // ELF relocation type, e.g. 2/PC32 public int _target; // Where constant is finally placed public int _opStart; // Opcode start Relo( Node op, Type t, byte off, byte elf ) { _op=op; _t=t; _off=off; _elf=elf; + _align = t.alignment(); + _structSize = t instanceof TypeStruct ts ? ts.size() : 0; } } public final HashMap<Node,Relo> _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<nIns(); i++ ) { if( j < depth() && i == _kinds.at(j)._lexSize ) { sb.append("| "); j++; } Var v = _vars.at(i); - sb.append(v.type()); + sb.append(v._type()); sb.append(" "); if( v._final ) sb.append("!"); sb.append(v._name); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter24/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index a9f86ce8..9ee26039 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -8,7 +8,9 @@ import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; -import java.util.HashSet; +import java.util.Collections; +import java.util.IdentityHashMap; +import java.util.Set; public abstract class ASMPrinter { @@ -28,14 +30,13 @@ public abstract class ASMPrinter { if( enc!=null && !enc._bigCons.isEmpty() && iadr < enc._bits.size() ) { // radix sort the big constants by alignment Ary<Relo>[] 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<Relo> relos = raligns[align]==null ? (raligns[align]=new Ary<>( Relo.class)) : raligns[align]; relos.add(relo); } - HashSet<Type> targets = new HashSet<>(); + Set<Type> 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<<align; sz = (sz + (log -1)) & -log; // Round up final padding for( int i=0; i<sz; i++ ) diff --git a/chapter24/src/main/java/com/seaofnodes/simple/print/IRPrinter.java b/chapter24/src/main/java/com/seaofnodes/simple/print/IRPrinter.java index d1265bef..336cf500 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/print/IRPrinter.java +++ b/chapter24/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<Integer,Integer> 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<Integer,Integer> depths = new HashMap<>(); SB sb = new SB(); Ary<Node> 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<Object,Type>)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<Node,LRG>)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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + if( n instanceof CFGNode cfg ) depths.put(n,cfg._idepth); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index ca2cc955..2fccb5f3 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -378,8 +378,8 @@ public class CodeGen { public FunNode link( TypeFunPtr tfp ) { return link(tfp.fidx()); } // Read-only linker lookup, suitable for printers and debugger display. // In particular, do not lazily remove a partially dead function. - public FunNode lookupFun(int fidx) { return _linker.atX(fidx); } - public FunNode lookupFun(TypeFunPtr tfp) { return lookupFun(tfp.fidx()); } + public FunNode _link(int fidx) { return _linker.atX(fidx); } + public FunNode _link(TypeFunPtr tfp) { return _link(tfp.fidx()); } // Return the FunNode from a fidx public FunNode link( int fidx ) { FunNode fun =_linker.atX(fidx); @@ -409,7 +409,7 @@ public class CodeGen { public String externFunc(int fidx) { return _externFunc.get(fidx); } public String funcName(int fidx ) { - FunNode fun = link(fidx); + FunNode fun = _link(fidx); if( fun!=null ) return fun._name; return externFunc(fidx); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 48ca4335..618ec689 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -46,17 +46,24 @@ public class Encoding { public static class Relo { public final Node _op; public final Type _t; // Constant type + public final int _align; // Log alignment, captured for diagnostic display + public final int _structSize; // Capture layout during encoding, not printing public final byte _off; // Offset from start of opcode public final byte _elf; // ELF relocation type, e.g. 2/PC32 public int _target; // Where constant is finally placed public int _opStart; // Opcode start Relo( Node op, Type t, byte off, byte elf ) { _op=op; _t=t; _off=off; _elf=elf; + _align = t.alignment(); + _structSize = t instanceof TypeStruct ts ? ts.size() : 0; + _readOnly = readOnly(t); } - public boolean readOnly() { + public boolean readOnly() { return _readOnly; } + private final boolean _readOnly; + private static boolean readOnly(Type t) { // Class initializers still write their fields, even when every // final value is constant. Their storage must remain writable. - return !(_t instanceof TypeStruct ts) || + return !(t instanceof TypeStruct ts) || (!Parser.startsClzPrefix(ts._name) && ts.isConstant()); } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 7c14965c..132705aa 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -140,7 +140,7 @@ abstract public class Opto { // unlinkStart deliberately leaves uncalled functions in a // temporarily dead limbo. A newly discovered call revives them; // do not use the cleanup lookup which removes dead linker entries. - FunNode fun = code.lookupFun(fidx); + FunNode fun = code._link(fidx); // null here means an external function; i.e. this Call // calls to an outside library and all its arguments escape. if( fun != null && !call.linked(fun) ) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 6650b19c..f8c96ff2 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -130,14 +130,22 @@ 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 ) { - LRG lrg = lrg(n); + LRG lrg = _lrg(n); return lrg==null ? null : reg(lrg); } String reg( LRG lrg ) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java index 51d10702..c053f377 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -38,8 +38,8 @@ public class CallNode extends CFGNode { return sb.append(")"); } public String name() { - if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { - FunNode fun = CodeGen.CODE.lookupFun(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/chapter25/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index feed8c5c..df2dc27b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -45,7 +45,7 @@ public class ConstantNode extends TypeNode { CodeGen.CODE._phase.ordinal() > 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<Relo>[] 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<Relo> relos = raligns[align]==null ? (raligns[align]=new Ary<>( Relo.class)) : raligns[align]; relos.add(relo); } - HashSet<Type> targets = new HashSet<>(); + Set<Type> 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<<align; sz = (sz + (log -1)) & -log; // Round up final padding for( int i=0; i<sz; i++ ) diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 975bce3d..fdf7fe2f 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -180,7 +180,7 @@ public class TypeFunPtr extends TypeNil { @Override public boolean isHigh() { return _nil <= 1 || (_nil==2 && _fidxs== XInt.EMPTY); } - @Override boolean _isConstant() { return (_nil==2 && XInt.isConstant(_fidxs)) || (_nil==3 && _fidxs== XInt.EMPTY); } + @Override public boolean _isConstant() { return (_nil==2 && XInt.isConstant(_fidxs)) || (_nil==3 && _fidxs== XInt.EMPTY); } @Override boolean _isFinal() { return true; } @Override TypeFunPtr _makeStorage() { return this; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 405e64d0..1306a39a 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -118,7 +118,7 @@ public class TypeInteger extends TypeScalar { 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() ) return log(_min); // just const here + if( _isConstant() ) return log(_min); // just const here int lo = log(_min); int hi = log(_max); return Math.max(lo,hi); @@ -131,7 +131,7 @@ public class TypeInteger extends TypeScalar { return 3; } - 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/chapter25/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter11Test.java index ab730b45..60a31c40 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,10 +1,22 @@ package com.seaofnodes.simple; - import com.seaofnodes.simple.codegen.CodeGen; + + 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; + 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/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<Object,Type>)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<Node,LRG>)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<size; i++ ) enc._cpool.write(0); + // Layout queries are forbidden during printing, even if they would + // happen to return a cached answer without changing the type. + boolean[] printing = {false}; + var scalar = new com.seaofnodes.simple.type.Type(com.seaofnodes.simple.type.Type.BOTTOM._type) { + @Override public int alignment() { + assertFalse("alignment queried by printer",printing[0]); + return 0; + } + @Override public int size() { + assertFalse("size queried by printer",printing[0]); + return 1; + } + @Override public String str() { return "LayoutProbe"; } + }; + var scalarNode = new ConstantNode(TypeInteger.TRUE); + enc._bigCons.put(scalarNode,new Encoding.Relo(scalarNode,scalar,(byte)0,(byte)2)); + enc._cpool.write(0); + printing[0] = true; + var offsets = com.seaofnodes.simple.type.TypeStruct.class.getDeclaredField("_offs"); + offsets.setAccessible(true); + offsets.set(t,null); // Printer must not lazily rebuild the cached layout. + var field = com.seaofnodes.simple.type.Type.class.getDeclaredField("VISIT"); + field.setAccessible(true); + var visit = (java.util.Map<Object,Object>)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<Node>(); + var seen = new IdentityHashMap<Node,Boolean>(); + nodes.add(root); + seen.put(root,true); + for( int i=0; i<nodes.size(); i++ ) { + Node n = nodes.get(i); + for( Node def : n._inputs ) + if( def!=null && seen.put(def,true)==null ) nodes.add(def); + for( Node use : n._outputs ) + if( use!=null && seen.put(use,true)==null ) nodes.add(use); + } + var ins = new IdentityHashMap<Node,Node[]>(); + var outs = new IdentityHashMap<Node,Node[]>(); + var hashes = new IdentityHashMap<Node,Integer>(); + var depths = new IdentityHashMap<Node,Integer>(); + for( Node n : nodes ) { + ins.put(n,n._inputs.toArray(new Node[0])); + outs.put(n,n._outputs.toArray(new Node[0])); + hashes.put(n,hash.getInt(n)); + } + 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<n.nIns(); i++ ) assertSame(ins.get(n)[i],n.in(i)); + for( int i=0; i<n.nOuts(); i++ ) assertSame(outs.get(n)[i],n._outputs.get(i)); + } + } +} diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index 09f1a14e..7dc4cbc3 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -19,7 +19,6 @@ the correction into the chapter's representation, not the entire modern file. | ID | Change | Proposed destination | Scope and acceptance evidence | |---|---|---|---| -| B09 | Make diagnostic function lookup read-only | 18 onward; **audit** first mutating printer lookup | Separate `lookupFun` from cleanup-performing `link`. Verify printing preserves graph/linker state. Do not import FunPtrNode or compilation units for this fix. | | B10 | Preserve widening state in integer nonzero refinement | **Audit** first chapter with both widening and `nonZero`; no later than 24 | Chapter 25 `TypeInteger.nonZero` preserves `_widen`. Check lattice laws and loop refinement. Exclude TypeScalar, storage-type, and serialization changes. | | B11 | Diagnose return types using the optimized return expression | 18; 19 already has the correction | `ReturnNode.err()` uses `expr()._type` instead of the parse-time `mt` aggregate. Chapter 18 rejects `struct S { u8 x; }; return new S; return 0;` with a mixed integer/reference error; Chapter 19 accepts it. Also test genuinely reachable incompatible returns. This is a candidate, not yet an applied or isolated-patch-verified fix. | | B12 | Encode the actual destination register for two-address immediate multiply | 21 | `MulIX86` inherits `ImmX86.encoding`, whose ModRM.reg is fixed to zero and whose REX.R is clear. With source/destination both `rcx`, multiplying by 11 emits `48 6b c1 0b` (destination `rax`) instead of `48 6b c9 0b`. With both `r9`, it emits `49 6b c1 0b` instead of `4d 6b c9 0b`. Give multiply its proper register fields while preserving Chapter 21's two-address allocation contract; do not change the opcode-extension fields used by other `ImmX86` subclasses. Later chapters use a separate multiply encoder. | @@ -27,6 +26,59 @@ the correction into the chapter's representation, not the entire modern file. After the first two reviews, batch only corrections with established independence and regressions. Keep one logical correction per commit across affected chapters. +## AOT class initialization: larger independent work + +Proposed on 2026-09-19; deferred behind the smaller BXX cleanup above. This is +a substantial, self-contained Chapter 25 change, not an entangled backport. +Earlier chapter applicability has not been established. + +The goal is to pre-allocate AOT class objects in ELF data and pre-fill their +fields, letting ordinary graph optimization remove redundant initialization. +Lazy-loaded classes retain runtime initialization for now. + +- Represent static object creation with a dedicated node, or a ConstantNode + carrying a TypeStruct with the appropriate final field values. Preserve the + class's identity and canonical layout independently of its current field + values; equal contents must not merge distinct class objects. +- Use normal StoreNode peepholes to remove same-value-over-same-value stores. + If needed, add a peephole that folds initializing stores into the static + creator's type. Create a replacement ConstantNode/type; never mutate a shared + constant's type. Prove that folding preserves initialization ordering and + does not expose a final value prematurely through another reference. +- When `<clinit>` 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 `<clinit>` 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 `<clinit>` 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.<clinit>` 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. |