From 9b3ad43f7aa2ec6d5f61fb9ff3c432101a5fba52 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 17 Sep 2026 19:18:46 -0700 Subject: Major overhaul debug printing --- .../com/seaofnodes/simple/codegen/CodeGen.java | 4 +- .../java/com/seaofnodes/simple/node/CallNode.java | 6 +- .../com/seaofnodes/simple/print/DebugSchedule.java | 375 ++++++++++++++++++++ .../com/seaofnodes/simple/print/IRPrinter.java | 385 +++++---------------- .../java/com/seaofnodes/simple/IRPrinterTest.java | 204 +++++++++++ 5 files changed, 663 insertions(+), 311 deletions(-) create mode 100644 chapter21/src/main/java/com/seaofnodes/simple/print/DebugSchedule.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/IRPrinterTest.java (limited to 'chapter21/src') diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 9ec3bc7b..fe449db0 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -430,9 +430,7 @@ public class CodeGen { // Debugging helper @Override public String toString() { - return _phase.ordinal() > Phase.Schedule.ordinal() - ? IRPrinter._prettyPrint( this ) - : _stop.p(9999); + return IRPrinter.prettyPrint(this); } // Debugging helper 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..d3c05b4c 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() ) { + FunNode fun = CodeGen.CODE.link(tfp); + if( fun!=null ) return fun._name; + } return null; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/DebugSchedule.java b/chapter21/src/main/java/com/seaofnodes/simple/print/DebugSchedule.java new file mode 100644 index 00000000..241ebbc9 --- /dev/null +++ b/chapter21/src/main/java/com/seaofnodes/simple/print/DebugSchedule.java @@ -0,0 +1,375 @@ +package com.seaofnodes.simple.print; + +import com.seaofnodes.simple.node.*; +import java.util.*; + +/** A debugger's ordering, independent of compiler scheduling and cached dominators. */ +final class DebugSchedule { + static Node input0(Node n) { + return n==null || n._inputs==null || n._inputs.isEmpty() ? null : n._inputs.get(0); + } + + static boolean head(Node n) { return n instanceof RegionNode || n instanceof MultiNode; } + + static boolean projection(Node n) { return n instanceof ProjNode || n instanceof CProjNode; } + + static boolean cfg(Node n) { return n instanceof CFGNode; } + + static boolean gap(Node n) { return cfg(n) && !projection(n); } + + static boolean child(Node n) { + Node h = input0(n); + return (n instanceof PhiNode && h instanceof RegionNode) || + (projection(n) && h instanceof MultiNode); + } + + private static Node group(Node n, IdentityHashMap selected) { + return child(n) && selected.containsKey(input0(n)) ? input0(n) : n; + } + + private static int order(Node n) { + if( n instanceof ProjNode proj ) return proj._idx; + if( n instanceof CProjNode proj ) return proj._idx; + return n._nid; + } + + // Use identity, not node equality (GVN), for all debugger bookkeeping. + static ArrayList schedule(Node base, int depth) { + ArrayList nodes = new ArrayList<>(); + IdentityHashMap distance = new IdentityHashMap<>(); + add(base,0,nodes,distance); + for( int i=0; i function(FunNode fun) { + ArrayList nodes = new ArrayList<>(); + IdentityHashMap seen = new IdentityHashMap<>(); + nodes.add(fun); + seen.put(fun,Boolean.TRUE); + for( int i=0; i orderNodes(ArrayList nodes) { + IdentityHashMap selected = new IdentityHashMap<>(); + for( Node n : nodes ) selected.put(n,Boolean.TRUE); + IdentityHashMap> members = new IdentityHashMap<>(); + ArrayList groups = new ArrayList<>(); + for( Node n : nodes ) { + Node g = group(n,selected); + if( !members.containsKey(g) ) { + members.put(g,new ArrayList<>()); + groups.add(g); + } + if( n!=g ) members.get(g).add(n); + } + // Reconstruct uses from inputs: incomplete reverse edges must not + // hide nodes. Ignore loop backedges for ordering, but still print them. + IdentityHashMap> uses = new IdentityHashMap<>(); + IdentityHashMap incoming = new IdentityHashMap<>(); + for( Node g : groups ) uses.put(g,new ArrayList<>()); + for( Node n : nodes ) { + if( n._inputs==null ) continue; + Node to = group(n,selected); + for( int i=0; i=2 && (n instanceof LoopNode || + n instanceof PhiNode && input0(n) instanceof LoopNode) ) continue; + if( n instanceof FunNode && def instanceof CallNode || + n instanceof CallEndNode && def instanceof ReturnNode || + n instanceof ParmNode && i>0 ) continue; + Node from = group(def,selected); + if( from!=to ) { + uses.get(from).add(to); + incoming.put(to,Boolean.TRUE); + } + } + } + Comparator cfgFirst = Comparator + .comparingInt((Node n) -> cfg(n) ? 0 : 1).thenComparingInt(n -> n._nid); + for( ArrayList us : uses.values() ) us.sort(cfgFirst); + groups.sort(Comparator.comparingInt(n -> n._nid)); + IdentityHashMap seen = new IdentityHashMap<>(); + ArrayList post = new ArrayList<>(); + for( Node g : groups ) + if( !incoming.containsKey(g) ) walk(g,uses,seen,post); + // A broken graph may consist entirely of cycles, with no roots. + for( Node g : groups ) walk(g,uses,seen,post); + Collections.reverse(post); + post=nestLoops(nodes,groups,selected,uses,post); + ArrayList result = new ArrayList<>(); + for( Node g : post ) { + result.add(g); + sortChildren(members.get(g)); + result.addAll(members.get(g)); + } + return result; + } + + // Projection lists are short. Select the next idx directly, including + // -1, sparse indices, and deterministic nid order for duplicate indices. + static void sortChildren(ArrayList children) { + for( int i=0; i children(Node head) { + ArrayList children = new ArrayList<>(); + Set seen = Collections.newSetFromMap(new IdentityHashMap<>()); + if( head!=null && head._outputs!=null ) for( Node use : head._outputs ) + if( child(use) && input0(use)==head && seen.add(use) ) children.add(use); + sortChildren(children); + return children; + } + + // Printer-local natural loops. Never ask idom()/loopDepth() to build or + // repair compiler metadata while inspecting a partly constructed graph. + private static final class Region { + final Node head; + final Set cfg = Collections.newSetFromMap(new IdentityHashMap<>()); + Region parent; + final ArrayList nodes = new ArrayList<>(); + ArrayList rpo; + Region(Node head) { this.head = head; } + } + + private record Use(Node node, int input) {} + + private static ArrayList predecessors(Node n) { + ArrayList preds = new ArrayList<>(); + if( !cfg(n) || n._inputs==null || (n instanceof StartNode || n instanceof StopNode || n instanceof FunNode) ) return preds; + if( n instanceof RegionNode ) { + for( int i=1; i path = Collections.newSetFromMap(new IdentityHashMap<>()); + for( Region r=a; r!=null; r=r.parent ) path.add(r); + for( Region r=b; r!=null; r=r.parent ) if( path.contains(r) ) return r; + throw new AssertionError("disjoint printer regions"); + } + + private static Region enclosing(Node cfg, ArrayList loops, Region root) { + Region best = root; + for( Region loop : loops ) + if( loop.cfg.contains(cfg) && (best==root || loop.cfg.size() owner) { + Region r = owner.get(n); + if( r==scope ) return n; + while( r!=null && r.parent!=scope ) r=r.parent; + return r==null ? null : r.head; + } + + private static ArrayList nestLoops(ArrayList nodes, ArrayList groups, + IdentityHashMap selected, + IdentityHashMap> uses, + ArrayList post) { + Region root = new Region(null); + ArrayList loops = new ArrayList<>(); + for( Node n : groups ) { + if( !(n instanceof LoopNode) || n instanceof StartNode ) continue; + Region loop = new Region(n); + loop.cfg.add(n); + ArrayList work = new ArrayList<>(); + Node back = n._inputs==null || n._inputs.size()<3 ? null : n._inputs.get(2); + Node entry = n._inputs==null || n._inputs.size()<2 ? null : n._inputs.get(1); + if( cfg(back) && selected.containsKey(back) && loop.cfg.add(back) ) work.add(back); + boolean closed = back==n; + for( int i=0; i> cfgUses = new IdentityHashMap<>(); + for( Node n : nodes ) if( cfg(n) ) cfgUses.put(n,new ArrayList<>()); + for( Node n : nodes ) if( cfg(n) ) + for( Node pred : predecessors(n) ) + if( cfgUses.containsKey(pred) ) cfgUses.get(pred).add(n); + for( Node n : groups ) if( n instanceof FunNode ) { + Region fun = new Region(n); + ArrayList work = new ArrayList<>(); + fun.cfg.add(n); + work.add(n); + for( int i=0; iloop.cfg.size() && outer.cfg.containsAll(loop.cfg) && + (loop.parent==root || outer.cfg.size() owner = new IdentityHashMap<>(); + IdentityHashMap> users = new IdentityHashMap<>(); + for( Node g : groups ) { + users.put(g,new ArrayList<>()); + if( cfg(g) ) owner.put(g,enclosing(g,loops,root)); + else if( cfg(input0(g)) ) owner.put(g,enclosing(input0(g),loops,root)); + else if( g instanceof ConstantNode ) owner.put(g,root); + } + for( Node use : nodes ) if( use._inputs!=null ) + for( int i=0; i0 ) continue; // Caller linkage, not callee data. + if( def!=null && selected.containsKey(def) && group(def,selected)!=group(use,selected) ) + users.get(group(def,selected)).add(new Use(use,i)); + } + // Floating definitions follow the common enclosing region of their + // uses. A loop Phi's entry value belongs outside that loop; its + // backedge value belongs inside. Pinned nodes keep their actual control. + boolean progress; + do { + progress=false; + for( int i=post.size()-1; i>=0; i-- ) { + Node g = post.get(i); + if( owner.containsKey(g) ) continue; + Region place=null; + boolean ready=true; + for( Use use : users.get(g) ) { + Region r=owner.get(group(use.node(),selected)); + if( r==null ) { ready=false; break; } + if( use.node() instanceof PhiNode && input0(use.node()) instanceof LoopNode && + r.head==input0(use.node()) && use.input()==1 ) r=r.parent; + place=place==null ? r : common(place,r); + } + if( ready ) { owner.put(g,place==null ? root : place); progress=true; } + } + } while( progress ); + // Unresolved data cycles do not prevent the rest of the graph printing. + for( Node g : groups ) owner.putIfAbsent(g,root); + for( Region loop : loops ) owner.put(loop.head,loop); + for( Node g : groups ) owner.get(g).nodes.add(g); + for( Region loop : loops ) loop.parent.nodes.add(loop.head); + + ArrayList regions = new ArrayList<>(loops); + regions.add(root); + for( Region scope : regions ) { + IdentityHashMap> edges = new IdentityHashMap<>(); + IdentityHashMap incoming = new IdentityHashMap<>(); + for( Node n : scope.nodes ) edges.put(n,new ArrayList<>()); + for( Node from : groups ) { + Node a=unit(from,scope,owner); + if( a==null ) continue; + for( Node to : uses.get(from) ) { + Node b=unit(to,scope,owner); + if( b!=null && a!=b ) { edges.get(a).add(b); incoming.put(b,Boolean.TRUE); } + } + } + scope.nodes.sort(Comparator.comparingInt(n -> n._nid)); + for( ArrayList es : edges.values() ) + es.sort(Comparator.comparingInt((Node n) -> cfg(n) ? 0 : 1).thenComparingInt(n -> n._nid)); + IdentityHashMap seen = new IdentityHashMap<>(); + scope.rpo = new ArrayList<>(); + if( scope.head!=null ) walk(scope.head,edges,seen,scope.rpo); + for( Node n : scope.nodes ) if( !incoming.containsKey(n) ) walk(n,edges,seen,scope.rpo); + for( Node n : scope.nodes ) walk(n,edges,seen,scope.rpo); + Collections.reverse(scope.rpo); + // Disconnected floating definitions still follow the loop header. + if( scope.head!=null ) { + scope.rpo.removeIf(n -> n==scope.head); + scope.rpo.add(0,scope.head); + } + } + // Expand nested loop vertices without recursive Java calls. + IdentityHashMap byHead = new IdentityHashMap<>(); + for( Region loop : loops ) byHead.put(loop.head,loop); + ArrayList result = new ArrayList<>(); + ArrayDeque scopes = new ArrayDeque<>(); + ArrayDeque> positions = new ArrayDeque<>(); + scopes.push(root); + positions.push(root.rpo.iterator()); + while( !scopes.isEmpty() ) { + if( !positions.peek().hasNext() ) { scopes.pop(); positions.pop(); continue; } + Node n=positions.peek().next(); + Region nested=byHead.get(n); + if( nested!=null && nested.parent==scopes.peek() ) { + scopes.push(nested); + positions.push(nested.rpo.iterator()); + } else result.add(n); + } + return result; + } + + private static void add(Node n, int d, ArrayList nodes, + IdentityHashMap distance) { + if( n!=null && !distance.containsKey(n) ) { + distance.put(n,d); + nodes.add(n); + } + } + + // An explicit DFS stack handles long chains as well as malformed cycles. + private static void walk(Node root, IdentityHashMap> uses, + IdentityHashMap seen, ArrayList post) { + if( seen.put(root,Boolean.TRUE)!=null ) return; + ArrayDeque stack = new ArrayDeque<>(); + ArrayDeque> edges = new ArrayDeque<>(); + stack.push(root); + edges.push(uses.get(root).iterator()); + while( !stack.isEmpty() ) { + if( edges.peek().hasNext() ) { + Node use = edges.peek().next(); + if( seen.put(use,Boolean.TRUE)==null ) { + stack.push(use); + edges.push(uses.get(use).iterator()); + } + } else { + post.add(stack.pop()); + edges.pop(); + } + } + } +} 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..70069539 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/print/IRPrinter.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/print/IRPrinter.java @@ -1,331 +1,104 @@ package com.seaofnodes.simple.print; -import com.seaofnodes.simple.Ary; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.TypeFunPtr; -import java.util.ArrayList; -import java.util.BitSet; -import java.util.HashMap; +import java.util.*; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.SB; -public abstract class IRPrinter { +public class IRPrinter { - // Print a node on 1 line, columnar aligned, as: - // NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE - // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt - public static SB printLine( Node n, SB sb ) { - if( n==null ) return sb; - sb.p("%4d %-7.7s ".formatted(n._nid,n.label())); - if( n._inputs==null ) - return sb.p("DEAD\n"); - for( Node def : n._inputs ) - sb.p(def==null ? "____" : "%4d".formatted(def._nid)) - // Lazy Phi indicator - .p(n instanceof MemMergeNode && def instanceof MemMergeNode ? "^" : " "); - for( int i = n._inputs.size(); i<4; i++ ) - sb.p(" "); - sb.p(" [[ "); - for( Node use : n._outputs ) - sb.p(use==null ? "____ " : "%4d ".formatted(use._nid)); - int lim = 6 - Math.max(n._inputs.size(),4); - for( int i = n._outputs.size(); i CodeGen.Phase.Schedule.ordinal() - ? _prettyPrintScheduled( node, depth ) - : _prettyPrint( node, depth ); + private static String type(Node n) { + if( n._type==null ) return ""; + try { return n._type.str(); } + catch( RuntimeException | AssertionError ex ) { return ""; } } - // 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 - 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(" "),false).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(" "),false); - sb.p("----------------------\n"); - } - if( !(n instanceof CallNode) ) { - sb.p("\n"); // Blank after multitail - gap = true; - } - } else { - printLine( n, sb ); - gap = false; - } - } - return sb.toString(); + private static String signature(FunNode fun) { + try { return fun.sig()==null ? "" : fun.sig().toString(); } + catch( RuntimeException | AssertionError ex ) { return ""; } } - 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); + public static void _printLine(Node n, StringBuilder sb) { + if( n==null ) return; + sb.append("%4d %-7.7s ".formatted(n._nid,label(n))); + if( n._inputs==null ) { sb.append("DEAD\n"); return; } + for( Node def : n._inputs ) + sb.append(def==null ? "____" : "%4d".formatted(def._nid)) + .append(n instanceof MemMergeNode && def instanceof MemMergeNode ? '^' : ' '); + for( int i=n._inputs.size(); i<4; i++ ) sb.append(" "); + sb.append(" [[ "); + if( n._outputs!=null ) for( Node use : n._outputs ) + sb.append(use==null ? "____ " : "%4d ".formatted(use._nid)); + sb.append(" ]] ").append(type(n)).append('\n'); } - // 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; - } + public static SB printLine(Node n, SB sb) { + StringBuilder line = new StringBuilder(); + _printLine(n,line); + return sb.p(line.toString()); } - 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 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 nodes = new ArrayList<>(); + IdentityHashMap seen = new IdentityHashMap<>(); + nodes.add(code._start); + seen.put(code._start,Boolean.TRUE); + if( code._stop!=null && seen.put(code._stop,Boolean.TRUE)==null ) nodes.add(code._stop); + ArrayList funs = new ArrayList<>(); + for( int i=0; i globals = new ArrayList<>(); + for( Node n : nodes ) + if( DebugSchedule.input0(n)==code._start && + n instanceof ConstantNode ) globals.add(n); + globals.sort(Comparator.comparingInt(n -> n._nid)); + for( Node n : globals ) _printLine(n,sb); + funs.sort(Comparator.comparingInt(n -> n._nid)); + for( FunNode fun : funs ) { + sb.append("\n--- ").append(label(fun)).append(' ').append(signature(fun)).append(" ----------------------\n"); + for( Node n : DebugSchedule.function(fun) ) { + if( DebugSchedule.gap(n) ) sb.append('\n'); + _printLine(n,sb); } - // 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); - } - - 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); - } - } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/IRPrinterTest.java b/chapter21/src/test/java/com/seaofnodes/simple/IRPrinterTest.java new file mode 100644 index 00000000..be9c67d1 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/IRPrinterTest.java @@ -0,0 +1,204 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.IRPrinter; +import java.util.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class IRPrinterTest { + private static final String SOURCE = """ + int sum=0; + int i=0; + while(i nodes = inputs(stop); + IdentityHashMap> defs = new IdentityHashMap<>(); + IdentityHashMap> uses = new IdentityHashMap<>(); + IdentityHashMap types = new IdentityHashMap<>(); + for( Node n : nodes ) { + defs.put(n,copy(n._inputs)); + uses.put(n,copy(n._outputs)); + types.put(n,n._type); + } + String printed = IRPrinter.prettyPrint(stop,999); + assertEquals(printed,IRPrinter.prettyPrint(stop,999)); + String program = code.toString(); + assertEquals(program,code.toString()); + List programIds = ids(program); + assertEquals(programIds.size(),new HashSet<>(programIds).size()); + List ids = ids(printed); + assertEquals(ids.size(),new HashSet<>(ids).size()); + int loops = 0; + for( Node n : nodes ) { + assertTrue("missing node " + n._nid,ids.contains(n._nid)); + assertEquals(defs.get(n),copy(n._inputs)); + assertEquals(uses.get(n),copy(n._outputs)); + assertSame(types.get(n),n._type); + if( !(n instanceof LoopNode) || n instanceof FunNode ) continue; + loops++; + ArrayList phis = new ArrayList<>(); + for( Node use : n._outputs ) + if( use instanceof PhiNode && use._inputs.get(0)==n ) phis.add(use); + phis.sort(Comparator.comparingInt(p -> p._nid)); + int idx = ids.indexOf(n._nid); + for( Node phi : phis ) assertEquals(Integer.valueOf(phi._nid),ids.get(++idx)); + idx = programIds.indexOf(n._nid); + assertTrue("missing loop " + n._nid,idx>=0); + for( Node phi : phis ) assertEquals(Integer.valueOf(phi._nid),programIds.get(++idx)); + } + assertTrue("nested source loops must remain",loops>=2); + // Printing must not call idepth() merely because the phase advanced. + CodeGen.Phase phase = code._phase; + code._phase = CodeGen.Phase.LocalSched; + try { assertEquals(printed,IRPrinter.prettyPrint(stop,999)); } + finally { code._phase = phase; } + } + + @Test(timeout=5000) public void testBrokenGraphs() { + CodeGen code = new CodeGen(SOURCE).parse(); + Node stop = code._stop; + // No entry control or backedge yet, and no reverse edge for the Phi. + LoopNode loop = new LoopNode(null,null); + PhiNode phi = new PhiNode("x",TypeInteger.BOT,loop,null,null); + loop._outputs.clear(); + List header = ids(IRPrinter.prettyPrint(phi,0)); + assertEquals(Arrays.asList(loop._nid,phi._nid),header); + // An orphan projection's label may itself dereference missing inputs. + ProjNode proj = new ProjNode(null,0,"broken"); + assertTrue(ids(IRPrinter.prettyPrint(proj,0)).contains(proj._nid)); + // A data cycle with no roots must terminate and print both nodes once. + AddNode a = new AddNode(null,null); + AddNode b = new AddNode(a,null); + a._inputs.set(1,b); + a._outputs.add(null); // keep edge + List cycle = ids(IRPrinter.prettyPrint(a,999)); + assertEquals(2,cycle.size()); + assertTrue(cycle.contains(a._nid)); + assertTrue(cycle.contains(b._nid)); + a._inputs=null; + assertTrue(IRPrinter.prettyPrint(a,999).contains("DEAD")); + assertEquals("",IRPrinter.prettyPrint(null,999)); + } + + @Test public void testProjectionOrderAndSpacing() { + new CodeGen("return 0;").parse(); + IfNode multi = new IfNode(null,null); + ProjNode p2 = new ProjNode(multi,2,"two"); + ProjNode pm = new ProjNode(multi,-1,"minus"); + CProjNode p1 = new CProjNode(multi,1,"one"); + ProjNode p0 = new ProjNode(multi,0,"zero"); + String printed = IRPrinter.prettyPrint(p2,0); + assertEquals(Arrays.asList(multi._nid,pm._nid,p0._nid,p1._nid,p2._nid),ids(printed)); + String[] lines = printed.split("\n"); + int first = line(lines,multi); + assertTrue(first>0 && lines[first-1].isBlank()); + assertEquals(first+1,line(lines,pm)); + assertEquals(first+2,line(lines,p0)); + assertEquals(first+3,line(lines,p1)); + assertEquals(first+4,line(lines,p2)); + } + + @Test public void testNestedLoopRpo() { + new CodeGen("return 0;").parse(); + LoopNode outer = new LoopNode(null,null); + LoopNode inner = new LoopNode(null,outer); + PhiNode op = new PhiNode("outer",TypeInteger.BOT,outer,null,null); + PhiNode ip = new PhiNode("inner",TypeInteger.BOT,inner,null,null); + AddNode innerValue = new AddNode(ip,null); + AddNode outerValue = new AddNode(ip,op); + ip._inputs.set(2,innerValue); + op._inputs.set(2,outerValue); + IfNode branch = new IfNode(inner,ip); + CProjNode left = new CProjNode(branch,0,"left"); + CProjNode right = new CProjNode(branch,1,"right"); + RegionNode join = new RegionNode((Parser.Lexer)null,null,left,right); + IfNode innerLatch = new IfNode(join,ip); + CProjNode innerBack = new CProjNode(innerLatch,0,"innerBack"); + CProjNode innerExit = new CProjNode(innerLatch,1,"innerExit"); + inner._inputs.set(2,innerBack); + IfNode outerLatch = new IfNode(innerExit,op); + CProjNode outerBack = new CProjNode(outerLatch,0,"outerBack"); + CProjNode outerExit = new CProjNode(outerLatch,1,"outerExit"); + outer._inputs.set(2,outerBack); + IfNode after = new IfNode(outerExit,op); + + // Raw input edits deliberately leave incomplete reverse edges. + String printed = IRPrinter.prettyPrint(after,999); + List ids = ids(printed); + assertEquals(ids.size(),new HashSet<>(ids).size()); + before(ids,outer,inner); + before(ids,inner,branch); + before(ids,branch,join); + before(ids,join,innerLatch); + before(ids,innerLatch,outerLatch); + before(ids,innerValue,outerValue); + before(ids,innerLatch,outerValue); + before(ids,outerValue,outerLatch); + before(ids,outerLatch,after); + assertEquals(Integer.valueOf(ip._nid),ids.get(ids.indexOf(inner._nid)+1)); + assertEquals(Integer.valueOf(op._nid),ids.get(ids.indexOf(outer._nid)+1)); + String[] lines = printed.split("\n"); + for( Node cfg : new Node[]{outer,inner,branch,join,innerLatch,outerLatch,after} ) { + int idx=line(lines,cfg); + assertTrue("blank before CFG " + cfg._nid,idx>0 && lines[idx-1].isBlank()); + } + assertEquals(line(lines,branch)+1,line(lines,left)); + assertEquals(line(lines,branch)+2,line(lines,right)); + } + + private static void before(List ids, Node a, Node b) { + assertTrue("missing " + a._nid,ids.contains(a._nid)); + assertTrue("missing " + b._nid,ids.contains(b._nid)); + assertTrue(a._nid + " before " + b._nid,ids.indexOf(a._nid) ids(String text) { + ArrayList ids = new ArrayList<>(); + for( String line : text.split("\n") ) { + String s = line.trim(); + if( !s.isEmpty() && Character.isDigit(s.charAt(0)) ) + ids.add(Integer.valueOf(s.split("\\s+",2)[0])); + } + return ids; + } + + private static ArrayList inputs(Node root) { + ArrayList nodes = new ArrayList<>(); + IdentityHashMap seen = new IdentityHashMap<>(); + nodes.add(root); + seen.put(root,Boolean.TRUE); + for( int i=0; i copy(Iterable edges) { + ArrayList copy = new ArrayList<>(); + if( edges!=null ) for( Node n : edges ) copy.add(n); + return copy; + } +} -- cgit v1.2.3