From 28209703c72fb7e9955961dbdb84e24a0f871acd Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 25: Modules --- .../com/seaofnodes/simple/print/ASMPrinter.java | 192 +++++------ .../seaofnodes/simple/print/GraphVisualizer.java | 15 +- .../com/seaofnodes/simple/print/IRPrinter.java | 377 ++++++--------------- .../java/com/seaofnodes/simple/print/JSViewer.java | 11 +- 4 files changed, 216 insertions(+), 379 deletions(-) (limited to 'src/main/java/com/seaofnodes/simple/print') diff --git a/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index a9f86ce8..206983a0 100644 --- a/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -1,130 +1,126 @@ package com.seaofnodes.simple.print; +import com.seaofnodes.simple.codegen.CompUnit; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Encoding.Relo; import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.util.Ary; -import com.seaofnodes.simple.util.SB; -import com.seaofnodes.simple.util.Utils; +import com.seaofnodes.simple.util.*; +import java.util.HashMap; import java.util.HashSet; public abstract class ASMPrinter { - public static SB print(SB sb, CodeGen code) { - if( code._cfg==null ) - return sb.p("Need _cfg set, run after GCM"); + public static SB print(SB sb, CodeGen code ) { + Encoding enc = code._encoding; + if( enc == null ) return sb.p("No encoding for ").p(code._srcName); // instruction address int iadr = 0; - for( int i=0; i[] raligns = new Ary[5]; - for( Node op : enc._bigCons.keySet() ) { - Relo relo = enc._bigCons.get(op); - int align = relo._t.alignment(); - Ary relos = raligns[align]==null ? (raligns[align]=new Ary<>( Relo.class)) : raligns[align]; - relos.add(relo); - } + if( enc._cpool.size()>0 ) + iadr = printConstantPool(iadr, sb, enc._cpool,enc._bigCons,true ,"Constant Pool"); - HashSet targets = new HashSet<>(); - sb.p("--- Constant Pool ------").nl(); - - // By alignment - for( int align = 4; align >= 0; align-- ) { - Ary relos = raligns[align]; - if( relos == null ) continue; - for( Relo relo : relos ) { - if( targets.contains(relo._t) ) continue; - targets.add(relo._t); - sb.hex2(iadr).p(" "); - switch( relo._t ) { - case TypeTuple tt -> { - for( Type tx : tt._types ) { - pN(enc,sb,iadr,align).p(" "); - iadr += (1< { - int sz = ts.size(); - int log = 1<0 ) + iadr = printConstantPool(iadr, sb,enc._sdata,enc._bigCons,false, "Static Data" ); + return sb; + } + + + static int printConstantPool( int iadr, SB sb, BAOS bits, HashMap bigCons, boolean ro, String msg ) { + sb.p("--- ").p(msg).p(" ------").nl(); + // radix sort the big constants by alignment + Ary[] raligns = new Ary[5]; + for( Node op : bigCons.keySet() ) { + Relo relo = bigCons.get(op); + // non-constant structs in the r/w data, everything else in r/o data + if( (relo._t instanceof TypeStruct ts && !ts.isConstant()) == ro ) + continue; + int align = relo._t.alignment(); + Ary relos = raligns[align]==null ? (raligns[align]=new Ary<>( Relo.class)) : raligns[align]; + relos.add(relo); + } + + HashSet targets = new HashSet<>(); + + // By alignment + int dadr=0; + for( int align = 4; align >= 0; align-- ) { + Ary relos = raligns[align]; + if( relos == null ) continue; + for( Relo relo : relos ) { + if( targets.contains(relo._t) ) continue; + targets.add(relo._t); + sb.hex2(iadr+dadr).p(" "); + if( relo._t instanceof TypeStruct ts ) { + int sz = ts.size(); + int log = 1< { - pN(enc,sb,iadr,align).fix(9-(1< CodeGen.Phase.RegAlloc.ordinal(); final boolean postEncode= code._phase.ordinal() >=CodeGen.Phase.Encoding.ordinal(); + final boolean postAlloc = code._phase.ordinal() > CodeGen.Phase.RegAlloc.ordinal() || + (code._phase.ordinal() == CodeGen.Phase.RegAlloc.ordinal() && code._regAlloc.done()); boolean once=false; for( Node n : bb.outs() ) { @@ -133,10 +129,10 @@ public abstract class ASMPrinter { // Post-RegAlloc phi prints all on one line if( postAlloc ) { if( !once ) { once=true; sb.fix(4," ").p(" ").fix(encWidth,"").p(" "); } - sb.p(phi._label).p(':').p(code.reg(phi,fun)).p(','); + sb.p(phi._label).p(':').p(code.reg(phi)).p(','); } else { // Pre-RegAlloc phi prints one line per - sb.fix(4," ").p(" ").fix(encWidth,"").p(" ").fix(opWidth,phi._label).p(" ").p(code.reg(phi,fun)); + sb.fix(4," ").p(" ").fix(encWidth,"").p(" ").fix(opWidth,phi._label).p(" ").p(code.reg(phi)); if( phi.getClass() == PhiNode.class ) { sb.p(" = phi( "); for( int i=1; i1 ) break; // Has code in the block, need to jump around @@ -185,7 +182,9 @@ public abstract class ASMPrinter { // get indent slightly and just print their index & node# if( n instanceof ProjNode proj ) { if( proj._type instanceof TypeMem ) return iadr; // Nothing for the hidden ones - sb.fix(4," ").p(" ").fix(encWidth,"").p(" ").fix(opWidth,proj._label==null ? "---" : proj._label).p(" ").p(code.reg(n,fun)).nl(); + sb.fix(4," ").p(" ").fix(encWidth,"").p(" ").fix(opWidth,code.reg(n)).p(" // "); + if( proj._label != null ) sb.p(proj._label); + sb.nl(); return iadr; } @@ -195,15 +194,15 @@ public abstract class ASMPrinter { // Encoding int fatEncoding = 0; - if( code._encoding != null && code._encoding._opLen!=null ) { - int size = code._encoding._opLen[n._nid]; + if( enc != null ) { + int size = enc.opLen(n); if( code._asmLittle ) for( int i=0; i xScopes) { + public String generateDotOutput(Parser parse) { return generateDotOutput(parse._ref,parse._scope,parse._xScopes); } + public String generateDotOutput(CompUnit cu, Node scope, Stack xScopes) { // Since the graph has cycles, we need to create a flat list of all the // nodes in the graph. - Collection all = findAll(xScopes, stop, scope); + Collection all = findAll(xScopes, cu._stop, scope); StringBuilder sb = new StringBuilder(); sb.append("digraph chapter18 {\n"); sb.append("/*\n"); - sb.append(stop._src); + sb.append(cu._src); sb.append("\n*/\n"); // To keep the Scopes below the graph and pointing up into the graph we @@ -80,7 +81,7 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges sb.append(doCtrl ? "\tsubgraph cluster_Controls {\n" : "\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name for (Node n : all) { - if (n instanceof ProjNode || n instanceof CProjNode || n instanceof MemMergeNode || n==Parser.XCTRL) + if( n instanceof ProjNode || n instanceof CProjNode || n instanceof MemMergeNode || n instanceof XCtrlNode ) continue; // Do not emit, rolled into MultiNode or Scope cluster already if( _separateControlCluster && doCtrl && !(n instanceof CFGNode) ) continue; if( _separateControlCluster && !doCtrl && (n instanceof CFGNode) ) continue; @@ -162,7 +163,7 @@ public class GraphVisualizer { sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name // Special for memory ScopeMinNode if( level==0 ) { - MemMergeNode n = scope.mem(); + Node n = scope.mem(); sb.append("\t\t").append(n.uniqueName()).append(" [label=\"").append(n.glabel()).append("\"];\n"); } sb.append("\t\t").append(scopeName).append(" [label=<\n"); @@ -195,7 +196,7 @@ public class GraphVisualizer { // Do not display the Constant->Start edge; // ProjNodes handled by Multi; // ScopeNodes are done separately - if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeNode || n==Parser.XCTRL ) + if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeNode || n instanceof XCtrlNode ) continue; for( int i=0; i CodeGen.Phase.Schedule.ordinal() - ? _prettyPrintScheduled( node, depth ) - : _prettyPrint( node, depth ); - } - - // Another bulk pretty-printer. Makes more effort at basic-block grouping. - private static String _prettyPrint( Node node, int depth ) { - // First, a Breadth First Search at a fixed depth. - BFS bfs = new BFS(node,depth); - // Convert just that set to a post-order - ArrayList rpos = new ArrayList<>(); - BitSet visit = new BitSet(); - for( int i=bfs._lim; i< bfs._bfs.size(); i++ ) - postOrd( bfs._bfs.get(i), null, rpos, visit, bfs._bs); - // Reverse the post-order walk + // Bulk whole program pretty print + public static String prettyPrint( CodeGen code ) { + // Loop-tree for nodeOrder + CFGNode.LoopTree old = code._start._ltree; + if( old==null ) + code._start.buildLoopTree( code._linker, code._stop); + Ary nodes = Serialize.nodeOrder(code); + if( old == null ) + code._start._ltree = null; SB sb = new SB(); - boolean gap=false; - for( int i=rpos.size()-1; i>=0; i-- ) { - Node n = rpos.get(i); - if( n instanceof CFGNode || n instanceof MultiNode ) { - if( !gap ) sb.p("\n"); // Blank before multihead - if( n instanceof FunNode fun ) - fun.sig().print(sb.p("--- ").p(fun._name==null ? "" : fun._name).p(" ")).p("----------------------\n"); - printLine( n, sb ); // Print head - while( --i >= 0 ) { - Node t = rpos.get(i); - if( !(t.in(0) instanceof MultiNode) ) { i++; break; } - printLine( t, sb ); - } - if( n instanceof ReturnNode ret ) { - FunNode fun = ret.fun(); - sb.p("--- "); - if( fun != null ) - fun.sig().print(sb.p(fun._name==null ? "" : fun._name).p(" ")); - sb.p("----------------------\n"); - } - if( !(n instanceof CallNode) ) { - sb.p("\n"); // Blank after multitail - gap = true; - } - } else { - printLine( n, sb ); - gap = false; + Node prior=null; + for( Node n : nodes ) { + if( n instanceof FunNode fun ) { + sb.nl().p("--- "); + fun.sig().print(sb.p(fun._name==null ? "" : fun._name).p(" ")); + sb.p("----------------------\n"); } + if( n instanceof MultiNode || n instanceof RegionNode || n instanceof CallNode || + (isMultiChild(prior) && !isMultiChild(n)) ) + sb.nl(); + printLine(n,sb); + if( n instanceof ReturnNode ret ) + sb.p("--- ").p(ret._fun._name==null ? "" : ret._fun._name).p(" ----------------------\n"); + prior = n; } return sb.toString(); } - private static void postOrd(Node n, Node prior, ArrayList rpos, BitSet visit, BitSet bfs) { - if( !bfs.get(n._nid) ) - return; // Not in the BFS visit - if( n instanceof FunNode && !(prior instanceof StartNode) ) - return; // Only visit Fun from Start - if( visit.get(n._nid) ) return; // Already post-order walked - visit.set(n._nid); - // First walk the CFG, then everything - if( n instanceof CFGNode ) { - for( Node use : n._outputs ) - // Follow CFG, not across call/function borders, and not around backedges - if( use instanceof CFGNode && !(n instanceof CallNode && use instanceof FunNode) && - use.nOuts() >= 1 && !(use._outputs.get(0) instanceof LoopNode) ) - postOrd(use, n, rpos,visit,bfs); - for( Node use : n._outputs ) - // Follow CFG, not across call/function borders - if( use instanceof CFGNode && !(n instanceof CallNode && use instanceof FunNode) ) - postOrd(use,n,rpos,visit,bfs); - } - // Follow all outputs - for( Node use : n._outputs ) - if( use != null && - !(n instanceof CallNode && use instanceof FunNode) && - (n instanceof FunNode || !(use instanceof ParmNode)) ) - postOrd(use, n, rpos,visit,bfs); - // Post-order - rpos.add(n); + private static boolean isMultiHead(Node n) { + return n instanceof RegionNode || n instanceof MultiNode; } - // Breadth-first search, broken out in a class to keep in more independent. - // Maintains a root-set of Nodes at the limit (or past by 1 if MultiHead). - public static class BFS { - // A breadth first search, plus MultiHeads for any MultiTails - public final ArrayList _bfs; - public final BitSet _bs; // Visited members by node id - public final int _depth; // Depth limit - public final int _lim; // From here to _bfs._len can be roots for a reverse search - public BFS( Node base, int d ) { - _depth = d; - _bfs = new ArrayList<>(); - _bs = new BitSet(); - - add(base); // Prime the pump - int idx=0, lim=1; // Limit is where depth counter changes - while( idx < _bfs.size() ) { // Ran out of nodes below depth - Node n = _bfs.get(idx++); - for( Node def : n._inputs ) - if( def!=null && !_bs.get(def._nid) ) - add(def); - if( idx==lim ) { // Depth counter changes at limit - if( --d < 0 ) - break; // Ran out of depth - lim = _bfs.size(); // New depth limit - } - } - // Toss things past the limit except multi-heads - while( idx < _bfs.size() ) { - Node n = _bfs.get(idx); - if( n instanceof MultiNode ) idx++; - else del(idx); - } - // Root set is any node with no inputs in the visited set - lim = _bfs.size(); - for( int i=_bfs.size()-1; i>=0; i-- ) - if( !any_visited(_bfs.get(i)) ) - swap( i,--lim); - _lim = lim; - } - void swap( int x, int y ) { - if( x==y ) return; - Node tx = _bfs.get(x); - Node ty = _bfs.get(y); - _bfs.set(x,ty); - _bfs.set(y,tx); - } - void add(Node n) { - _bfs.add(n); - _bs.set(n._nid); - } - void del(int idx) { - _bs.clear(_bfs.get(idx)._nid); - Utils.del(_bfs, idx); - } - boolean any_visited( Node n ) { - for( Node def : n._inputs ) - if( def!=null && _bs.get(def._nid) ) - return true; - return false; - } + private static boolean isMultiChild(Node n) { + return n!=null && n.nIns() > 0 && n.in(0) != null && isMultiHead(n.in(0)); } - public static String _prettyPrint( CodeGen code ) { - SB sb = new SB(); - // Print the Start "block" - printLine(code._start,sb); - for( Node n : code._start._outputs ) - printLine(n,sb); - sb.nl(); - // Skip start, stop - for( int i=1; i post = new Ary<>(Node.class); + Ary rets = new Ary<>(Node.class); + var visit = new IdentityHashMap(); + assert depth < 5000; + postOrd( node, 0, depth, visit, post, rets); + // Function calls all print independent + while( rets.size()>0 ) + postOrd( rets.pop(), 0, depth, visit, post, rets ); - // Block contents - for( Node n : blk._outputs ) { - if( n instanceof CFGNode cfg ) continue; - printLine(n,sb); - if( !(n instanceof CFGNode) && n instanceof MultiNode ) - for( Node use : n._outputs ) - if( use instanceof ProjNode ) - printLine(use,sb); + + // Reverse the post-order walk + SB sb = new SB(); + for( int i=0; i0 && isMultiChild(post.at(i-1)) && !isMultiChild(n)) ) + sb.nl(); + if( n instanceof FunNode fun ) + fun.sig().print(sb.p("--- ").p(fun._name==null ? "" : fun._name).p(" ")).p("----------------------\n"); + printLine( n, sb ); // Print head + if( n instanceof ReturnNode ret ) { + FunNode fun = ret.fun(); + sb.p("--- ").p(fun==null ? "" : fun._name).p("----------------------\n"); } } - - printLine(code._stop,sb); return sb.toString(); } - // Bulk pretty printer, knowing scheduling information is available - private static String _prettyPrintScheduled( Node node, int depth ) { - // Backwards DFS walk to depth. - HashMap ds = new HashMap<>(); - Ary ns = new Ary<>(Node.class); - _walk(ds,ns,node,depth); - // Remove data projections, these are force-printed behind their multinode head - for( int i=0; i 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 = cfg; - } - Integer d = ds.remove(blk._nid); - ns.del(ns.find(blk)); - // Print block header - sb.p("%-13.13s".formatted(label(blk)+":")); - sb.p( " ".repeat(4) ).p(" [[ "); - if( blk instanceof StartNode ) ; - else if( blk instanceof RegionNode || blk instanceof StopNode ) - for( int i=(blk instanceof StopNode ? 3 : 1); i visit, Ary post, Ary rets ) { + if( n==null ) return; + if( d >= cutoff ) return; // Too deep + Integer depth = visit.get(n); + if( depth!=null ) return; // Been there, done that + + // Not a multi-child (Phi of a Region or Proj of a MultiNode) + if( !isMultiHead(n) && !isMultiChild(n) ) { + visit.put(n,d); // Visit node N and depth D + for( Node def : n._inputs ) // Children before visit + postOrd(def, d+1, cutoff, visit, post, rets); + post.add(n); // Post-order add + return; + } - // Collect block contents that are in the depth limit - bns.clear(); - int xd = Integer.MAX_VALUE; - for( Node use : blk._outputs ) { - Integer i = ds.get(use._nid); - if( i!=null && !(use instanceof CFGNode cfg && cfg.blockHead()) ) { - if( bns.find(use)==-1 ) - bns.add(use); - xd = Math.min(xd,i); + // Multi-child; print the parent and all children together + Node multi = isMultiHead(n) ? n : n.in(0); + // Multi + children are visited all at once + visit.put(multi,d+1); + for( Node out : multi.outs() ) + visit.put(out,d); + + // Order to visit all the children + Node[] outs = multi.outs().asAry(); + Arrays.sort(outs, Comparator.comparingInt( IRPrinter::sortOrder ) ); + + // Do not walk out of Functions, this makes functions stand-alone + // but otherwise unordered + if( !(multi instanceof FunNode fun && fun._folding) ) { + // Visit all children inputs all at once + for( Node out : outs ) { + // A FunNode is both a multi-head AND a multi-child from Start + if( !isMultiHead(out) && out != null ) { + for( Node def : out._inputs ) { + postOrd(def, d+1, cutoff, visit, post, rets); + } } } - // Print Phis up front, if any - for( int i=0; i ds, Ary ns, Node node, int d ) { - Integer nd = ds.get(node._nid); - if( nd!=null && d <= nd ) return; // Been there, done that - Integer old = ds.put(node._nid,d) ; - if( old == null ) - ns.add(node); - if( d == 0 ) return; // Depth cutoff - for( Node def : node._inputs ) - if( def != null && - !(node instanceof LoopNode loop && loop.back()==def) && - // Don't walk into or out of functions - !(node instanceof CallEndNode && def instanceof ReturnNode) && - !(node instanceof FunNode && def instanceof CallNode) && - !(node instanceof ParmNode && !(def instanceof FunNode)) - ) - _walk(ds,ns,def,d-1); + // Post visit the multi and all children + post.add(multi); + for( Node out : outs ) + if( !isMultiHead(out) ) + post.add(out); } - static String label( CFGNode blk ) { - if( blk instanceof StartNode ) return "START"; - return (blk instanceof LoopNode ? "LOOP" : "L")+blk._nid; - } - static void label( SB sb, CFGNode blk ) { - if( !blk.blockHead() ) blk = blk.cfg(0); - sb.p( "%-9.9s ".formatted( label( blk ) ) ); - } - static void printLine( Node n, SB sb, Ary bns, int i, HashMap ds, Ary ns ) { - printLine( n, sb ); - if( i != -1 ) bns.del(i); - ds.remove(n._nid); - int idx = ns.find(n); - if( idx!=-1 ) ns.del(idx); + static int sortOrder( Node n ) { + if( n instanceof ProjNode proj ) return proj._idx; + if( n instanceof PhiNode phi ) return phi._nid; + if( n == null ) return 0; + return n._nid+1000000; } } diff --git a/src/main/java/com/seaofnodes/simple/print/JSViewer.java b/src/main/java/com/seaofnodes/simple/print/JSViewer.java index 62ff0001..0f34af2e 100644 --- a/src/main/java/com/seaofnodes/simple/print/JSViewer.java +++ b/src/main/java/com/seaofnodes/simple/print/JSViewer.java @@ -202,11 +202,11 @@ public class JSViewer implements AutoCloseable { int lexStart = level==0 ? 0 : scope._kinds.at(level-1)._lexSize; // Special for memory ScopeMinNode - MemMergeNode n = scope.nIns()>1 ? scope.mem() : null; - if( level==0 && n!=null && n.nIns()>2 ) { + Node n = scope.nIns()>1 ? scope.mem() : null; + if( level==0 && n instanceof MemMergeNode merge && n.nIns()>2 ) { sb.i().p(""); for( int m=2; m\n"); // End scope level } @@ -346,7 +346,7 @@ public class JSViewer implements AutoCloseable { sb.i().p(scopeName).p(" -> ").p(n.uniqueName()).p(" [ style=dashed color=grey];\n"); } // Force functions above return - if( n instanceof ReturnNode ret && ret.inProgress() && !ret.fun().isDead() ) + if( n instanceof ReturnNode ret && !ret.fun().isDead() ) sb.i().p(ret.ctrl().uniqueName()).p(" -> ").p(ret.fun().uniqueName()).p("[style=invis]\n"); } } @@ -376,8 +376,7 @@ public class JSViewer implements AutoCloseable { } // Memory - if( scope.nIns()>1 ) { - MemMergeNode n = scope.mem(); + if( scope.nIns()>1 && scope.mem() instanceof MemMergeNode n ) { for( int i=2; i