Major overhaul debug printing

4 files changed, 652 insertions, 257 deletions

diff --git a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
index 47616b51..4b8a7235 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
@@ -115,7 +115,7 @@ public class CodeGen {
 
     // Debugging helper
     @Override public String toString() {
-        return _stop.p(9999);
+        return IRPrinter.prettyPrint(this);
     }
 
     // Debugging helper
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/DebugSchedule.java b/chapter18/src/main/java/com/seaofnodes/simple/DebugSchedule.java
new file mode 100644
index 00000000..ba5986d6
--- /dev/null
+++ b/chapter18/src/main/java/com/seaofnodes/simple/DebugSchedule.java
@@ -0,0 +1,375 @@
+package com.seaofnodes.simple;
+
+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<Node,Boolean> 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<Node> schedule(Node base, int depth) {
+        ArrayList<Node> nodes = new ArrayList<>();
+        IdentityHashMap<Node,Integer> distance = new IdentityHashMap<>();
+        add(base,0,nodes,distance);
+        for( int i=0; i<nodes.size(); i++ ) {
+            Node n = nodes.get(i);
+            int d = distance.get(n);
+            if( n._inputs!=null && d<Math.max(0,depth) )
+                for( Node def : n._inputs ) add(def,d+1,nodes,distance);
+        }
+        // Complete block headers at the depth boundary, without pulling in
+        // another round of ordinary dependencies through sibling Phis.
+        for( int i=0; i<nodes.size(); i++ ) {
+            Node n = nodes.get(i);
+            if( child(n) ) add(input0(n),depth,nodes,distance);
+            if( head(n) && n._outputs!=null )
+                for( Node use : n._outputs )
+                    if( child(use) && input0(use)==n ) add(use,depth,nodes,distance);
+        }
+
+        return orderNodes(nodes);
+    }
+
+    // Function ownership follows raw uses, stopping at call/return linkages.
+    static ArrayList<Node> function(FunNode fun) {
+        ArrayList<Node> nodes = new ArrayList<>();
+        IdentityHashMap<Node,Boolean> seen = new IdentityHashMap<>();
+        nodes.add(fun);
+        seen.put(fun,Boolean.TRUE);
+        for( int i=0; i<nodes.size(); i++ ) {
+            Node n = nodes.get(i);
+            if( n instanceof ReturnNode || n._outputs==null ) continue;
+            for( Node use : n._outputs ) {
+                if( use==null || seen.containsKey(use) ) continue;
+                if( use instanceof FunNode other && other!=fun ) continue;
+                if( use instanceof ParmNode && input0(use)!=fun ) continue;
+                if( use instanceof StartNode || use instanceof StopNode ) continue;
+                if( use instanceof CallEndNode && input0(use)!=n ) continue;
+                seen.put(use,Boolean.TRUE);
+                nodes.add(use);
+            }
+        }
+        return orderNodes(nodes);
+    }
+
+    static ArrayList<Node> orderNodes(ArrayList<Node> nodes) {
+        IdentityHashMap<Node,Boolean> selected = new IdentityHashMap<>();
+        for( Node n : nodes ) selected.put(n,Boolean.TRUE);
+        IdentityHashMap<Node,ArrayList<Node>> members = new IdentityHashMap<>();
+        ArrayList<Node> 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<Node,ArrayList<Node>> uses = new IdentityHashMap<>();
+        IdentityHashMap<Node,Boolean> 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<n._inputs.size(); i++ ) {
+                Node def = n._inputs.get(i);
+                if( def==null || !selected.containsKey(def) ) continue;
+                if( 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<Node> cfgFirst = Comparator
+            .comparingInt((Node n) -> cfg(n) ? 0 : 1).thenComparingInt(n -> n._nid);
+        for( ArrayList<Node> us : uses.values() ) us.sort(cfgFirst);
+        groups.sort(Comparator.comparingInt(n -> n._nid));
+        IdentityHashMap<Node,Boolean> seen = new IdentityHashMap<>();
+        ArrayList<Node> 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<Node> 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<Node> children) {
+        for( int i=0; i<children.size(); i++ ) {
+            int best=i;
+            for( int j=i+1; j<children.size(); j++ ) {
+                Node a=children.get(j), b=children.get(best);
+                if( order(a)<order(b) || order(a)==order(b) && a._nid<b._nid ) best=j;
+            }
+            Collections.swap(children,i,best);
+        }
+    }
+
+    static ArrayList<Node> children(Node head) {
+        ArrayList<Node> children = new ArrayList<>();
+        Set<Node> 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<Node> cfg = Collections.newSetFromMap(new IdentityHashMap<>());
+        Region parent;
+        final ArrayList<Node> nodes = new ArrayList<>();
+        ArrayList<Node> rpo;
+        Region(Node head) { this.head = head; }
+    }
+
+    private record Use(Node node, int input) {}
+
+    private static ArrayList<Node> predecessors(Node n) {
+        ArrayList<Node> 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<n._inputs.size(); i++ )
+                if( cfg(n._inputs.get(i)) ) preds.add(n._inputs.get(i));
+        } else if( cfg(input0(n)) ) preds.add(input0(n));
+        return preds;
+    }
+
+    private static Region common(Region a, Region b) {
+        Set<Region> 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<Region> loops, Region root) {
+        Region best = root;
+        for( Region loop : loops )
+            if( loop.cfg.contains(cfg) && (best==root || loop.cfg.size()<best.cfg.size()) ) best=loop;
+        return best;
+    }
+
+    // A nested loop is one vertex in its parent's RPO.
+    private static Node unit(Node n, Region scope, IdentityHashMap<Node,Region> 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<Node> nestLoops(ArrayList<Node> nodes, ArrayList<Node> groups,
+                                            IdentityHashMap<Node,Boolean> selected,
+                                            IdentityHashMap<Node,ArrayList<Node>> uses,
+                                            ArrayList<Node> post) {
+        Region root = new Region(null);
+        ArrayList<Region> 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<Node> 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<work.size(); i++ )
+                for( Node pred : predecessors(work.get(i)) ) {
+                    if( pred==n ) closed=true;
+                    if( pred!=entry && selected.containsKey(pred) && loop.cfg.add(pred) ) work.add(pred);
+                }
+            // An incomplete or malformed backedge is still a printable header.
+            if( !closed ) { loop.cfg.clear(); loop.cfg.add(n); }
+            loops.add(loop);
+        }
+        // The same hierarchy applies to node/depth slices which contain
+        // several linked functions, as well as the whole-program view.
+        IdentityHashMap<Node,ArrayList<Node>> 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<Node> work = new ArrayList<>();
+            fun.cfg.add(n);
+            work.add(n);
+            for( int i=0; i<work.size(); i++ )
+                for( Node use : cfgUses.get(work.get(i)) )
+                    if( fun.cfg.add(use) ) work.add(use);
+            loops.add(fun);
+        }
+        if( loops.isEmpty() ) return post;
+        for( Region loop : loops ) {
+            loop.parent=root;
+            for( Region outer : loops )
+                if( outer.cfg.size()>loop.cfg.size() && outer.cfg.containsAll(loop.cfg) &&
+                    (loop.parent==root || outer.cfg.size()<loop.parent.cfg.size()) ) loop.parent=outer;
+        }
+
+        IdentityHashMap<Node,Region> owner = new IdentityHashMap<>();
+        IdentityHashMap<Node,ArrayList<Use>> 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; i<use._inputs.size(); i++ ) {
+                Node def = use._inputs.get(i);
+                if( use instanceof ParmNode && i>0 ) 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<Region> regions = new ArrayList<>(loops);
+        regions.add(root);
+        for( Region scope : regions ) {
+            IdentityHashMap<Node,ArrayList<Node>> edges = new IdentityHashMap<>();
+            IdentityHashMap<Node,Boolean> 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<Node> es : edges.values() )
+                es.sort(Comparator.comparingInt((Node n) -> cfg(n) ? 0 : 1).thenComparingInt(n -> n._nid));
+            IdentityHashMap<Node,Boolean> 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<Node,Region> byHead = new IdentityHashMap<>();
+        for( Region loop : loops ) byHead.put(loop.head,loop);
+        ArrayList<Node> result = new ArrayList<>();
+        ArrayDeque<Region> scopes = new ArrayDeque<>();
+        ArrayDeque<Iterator<Node>> 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<Node> nodes,
+                            IdentityHashMap<Node,Integer> 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<Node,ArrayList<Node>> uses,
+                             IdentityHashMap<Node,Boolean> seen, ArrayList<Node> post) {
+        if( seen.put(root,Boolean.TRUE)!=null ) return;
+        ArrayDeque<Node> stack = new ArrayDeque<>();
+        ArrayDeque<Iterator<Node>> 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/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java
index aa498b16..79f987fd 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java
@@ -1,280 +1,98 @@
 package com.seaofnodes.simple;
 
 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.*;
 
 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 ) {
-        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<lim; i++ )
-            sb.p("     ");
-        sb.p(" ]]  ");
-        if( n._type!= null ) sb.p(n._type.str());
-        return sb.p("\n");
+    // Inspect raw edges so a partly built/dead node is still useful to print.
+    private static String label(Node n) {
+        if( n._inputs==null ) return n.getClass().getSimpleName();
+        try { return n.label(); }
+        catch( RuntimeException | AssertionError ex ) { return n.getClass().getSimpleName(); }
     }
 
-
-    public static String prettyPrint(Node node, int depth) {
-        return CodeGen.CODE._phase.ordinal() > 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 "<incomplete type>"; }
     }
 
-    // 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<Node> 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.isMultiHead() ) {
-                if( !gap ) sb.p("\n"); // Blank before multihead
-                if( n instanceof FunNode fun ) {
-                    TypeFunPtr sig = fun.sig();
-                    sig.print(sb.p("--- ").p(sig._name==null ? "" : sig._name).p(" "),false).p("----------------------\n");
-                }
-                printLine( n, sb );         // Print head
-                while( --i >= 0 ) {
-                    Node t = rpos.get(i);
-                    if( !t.isMultiTail() ) { i++; break; }
-                    printLine( t, sb );
-                }
-                if( n instanceof ReturnNode ret ) {
-                    TypeFunPtr sig = ret.fun().sig();
-                    sig.print(sb.p("--- ").p(sig._name==null ? "" : sig._name).p(" "),false).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 "<incomplete signature>"; }
     }
 
-    private static void postOrd(Node n, Node prior, ArrayList<Node> 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<Node> _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();
+    public static SB printLine(Node n, SB sb) {
+        StringBuilder line = new StringBuilder();
+        _printLine(n,line);
+        return sb.p(line.toString());
+    }
 
-            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.isMultiHead() ) 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 String prettyPrint(Node node, int depth) {
+        StringBuilder sb = new StringBuilder();
+        for( Node n : DebugSchedule.schedule(node,depth) ) {
+            if( DebugSchedule.gap(n) ) sb.append('\n');
+            if( n instanceof FunNode fun )
+                sb.append("--- ").append(label(fun)).append(' ').append(signature(fun)).append(" ----------------------\n");
+            _printLine(n,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<Integer,Integer> ds = new HashMap<>();
-        ArrayList<Node> ns = new ArrayList<>();
-        _walk(ds,ns,node,depth);
-        // Remove data projections, these are force-printed behind their multinode head
-        for( int i=0; i<ns.size(); i++ ) {
-            if( ns.get(i) instanceof ProjNode proj && !(proj.in(0) instanceof CFGNode) ) {
-                Utils.del(ns,i--);
-                ds.remove(proj._nid);
-            }
+    // Print complete functions separately, so linked callees/callers do not
+    // appear in the middle of one another's bodies.
+    public static String prettyPrint(CodeGen code) {
+        if( code._start==null ) return prettyPrint(code._stop,9999);
+        ArrayList<Node> nodes = new ArrayList<>();
+        IdentityHashMap<Node,Boolean> 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<FunNode> funs = new ArrayList<>();
+        for( int i=0; i<nodes.size(); i++ ) {
+            Node n = nodes.get(i);
+            if( n instanceof FunNode fun ) funs.add(fun);
+            if( n._inputs!=null ) for( Node def : n._inputs )
+                if( def!=null && seen.put(def,Boolean.TRUE)==null ) nodes.add(def);
+            if( n._outputs!=null ) for( Node use : n._outputs )
+                if( use!=null && seen.put(use,Boolean.TRUE)==null ) nodes.add(use);
         }
-        // Print by block with least idepth
-        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() || (blk instanceof FunNode && !(cfg instanceof FunNode)))
-                    blk = cfg;
+        StringBuilder sb = new StringBuilder();
+        sb.append('\n');
+        _printLine(code._start,sb);
+        for( Node proj : DebugSchedule.children(code._start) ) _printLine(proj,sb);
+        ArrayList<Node> 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);
             }
-            Integer d = ds.remove(blk._nid);
-            ns.remove(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<blk.nIns(); i++ )
-                    label(sb,blk.cfg(i));
-            else
-                label(sb,blk.cfg(0));
-            sb.p(" ]]  \n");
-            printLine(blk,sb);
-
-            // 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);
-                }
-            }
-            // Print Phis up front, if any
-            for( int i=0; i<bns.size(); i++ )
-                if( bns.get(i) instanceof PhiNode phi )
-                    printLine( phi, sb,bns,i--,ds,ns);
-
-            // Print block contents in depth order, bumping depth until whole block printed
-            for( ; !bns.isEmpty(); xd++ )
-                for( int i=0; i<bns.size(); i++ ) {
-                    Node n = bns.get(i);
-                    if( ds.get(n._nid)==xd ) {
-                        printLine( n, sb, bns, i--, ds,ns );
-                        if( n instanceof MultiNode && !(n instanceof CFGNode) ) {
-                            for( Node use : n._outputs ) {
-                                printLine(use,sb,bns,bns.indexOf(use),ds,ns);
-                            }
-                        }
-                    }
-                }
-            sb.p("\n");
+            sb.append("--- ").append(label(fun)).append(" ----------------------\n");
         }
+        sb.append('\n');
+        _printLine(code._stop,sb);
         return sb.toString();
     }
-
-    private static void _walk( HashMap<Integer,Integer> ds, ArrayList<Node> 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<Node> bns, int i, HashMap<Integer,Integer> ds, ArrayList<Node> ns ) {
-        printLine( n, sb );
-        if( i != -1 ) bns.del(i);
-        ds.remove(n._nid);
-        ns.remove(n);
-    }
-
 }
diff --git a/chapter18/src/test/java/com/seaofnodes/simple/IRPrinterTest.java b/chapter18/src/test/java/com/seaofnodes/simple/IRPrinterTest.java
new file mode 100644
index 00000000..849aeebb
--- /dev/null
+++ b/chapter18/src/test/java/com/seaofnodes/simple/IRPrinterTest.java
@@ -0,0 +1,202 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+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<arg) {
+            int j=0;
+            while(j<i) { sum=sum+j; j=j+1; }
+            i=i+1;
+        }
+        return sum;
+        """;
+
+    // No exact whitespace/node-number golden: require a stable, complete
+    // listing and contiguous Loop/Phi headers, including nested loops.
+    @Test public void testLoopHeadersAndReadOnlyPrinting() {
+        CodeGen code = new CodeGen(SOURCE).parse();
+        Node stop = code._stop;
+        ArrayList<Node> nodes = inputs(stop);
+        IdentityHashMap<Node,List<Node>> defs = new IdentityHashMap<>();
+        IdentityHashMap<Node,List<Node>> uses = new IdentityHashMap<>();
+        IdentityHashMap<Node,Type> 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<Integer> programIds = ids(program);
+        assertEquals(programIds.size(),new HashSet<>(programIds).size());
+        List<Integer> 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<Node> 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<Integer> 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<Integer> cycle = ids(IRPrinter.prettyPrint(a,999));
+        assertEquals(2,cycle.size());
+        assertTrue(cycle.contains(a._nid));
+        assertTrue(cycle.contains(b._nid));
+        a._inputs.clear();
+        assertTrue(ids(IRPrinter.prettyPrint(a,999)).contains(a._nid));
+        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<Integer> 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<Integer> 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.indexOf(b._nid));
+    }
+
+    private static int line(String[] lines, Node n) {
+        for( int i=0; i<lines.length; i++ )
+            if( lines[i].trim().startsWith(n._nid+" ") ) return i;
+        fail("missing line " + n._nid);
+        return -1;
+    }
+
+    private static List<Integer> ids(String text) {
+        ArrayList<Integer> 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<Node> inputs(Node root) {
+        ArrayList<Node> nodes = new ArrayList<>();
+        IdentityHashMap<Node,Boolean> seen = new IdentityHashMap<>();
+        nodes.add(root);
+        seen.put(root,Boolean.TRUE);
+        for( int i=0; i<nodes.size(); i++ ) {
+            Node n = nodes.get(i);
+            if( n._inputs!=null ) for( Node def : n._inputs )
+                if( def!=null && seen.put(def,Boolean.TRUE)==null ) nodes.add(def);
+        }
+        return nodes;
+    }
+
+    private static List<Node> copy(Iterable<Node> edges) {
+        ArrayList<Node> copy = new ArrayList<>();
+        if( edges!=null ) for( Node n : edges ) copy.add(n);
+        return copy;
+    }
+}