diff options
Diffstat (limited to 'chapter12')
3 files changed, 83 insertions, 5 deletions
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)); + } + } +} |