diff options
Diffstat (limited to 'chapter23')
18 files changed, 219 insertions, 18 deletions
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)); + } + } +} |