debug printers no longer call self-optimizing accessors

15 files changed, 196 insertions, 15 deletions

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));
+        }
+    }
+}