diff options
Diffstat (limited to 'chapter20')
13 files changed, 189 insertions, 11 deletions
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)); + } + } +} |