From 5ea32e69433d0c850d02bbc1e6c4a260bc095fec Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 1 Oct 2026 12:01:57 -0700 Subject: Move debug printing into shared space Same as the graph viewer, moves a lot of code out of all Nodes --- print/Makefile | 14 + print/README.md | 112 ++++++++ print/print.iml | 16 ++ print/print.mk | 4 + .../main/java/com/seaofnodes/print/ASMPrinter.java | 157 +++++++++++ .../java/com/seaofnodes/print/AssemblyAdapter.java | 26 ++ .../main/java/com/seaofnodes/print/BaseNode.java | 37 +++ .../java/com/seaofnodes/print/ExprPrinter.java | 56 ++++ .../main/java/com/seaofnodes/print/IRAdapter.java | 34 +++ .../main/java/com/seaofnodes/print/IRPrinter.java | 293 +++++++++++++++++++++ .../java/com/seaofnodes/print/PrinterTest.java | 153 +++++++++++ 11 files changed, 902 insertions(+) create mode 100644 print/Makefile create mode 100644 print/README.md create mode 100644 print/print.iml create mode 100644 print/print.mk create mode 100644 print/src/main/java/com/seaofnodes/print/ASMPrinter.java create mode 100644 print/src/main/java/com/seaofnodes/print/AssemblyAdapter.java create mode 100644 print/src/main/java/com/seaofnodes/print/BaseNode.java create mode 100644 print/src/main/java/com/seaofnodes/print/ExprPrinter.java create mode 100644 print/src/main/java/com/seaofnodes/print/IRAdapter.java create mode 100644 print/src/main/java/com/seaofnodes/print/IRPrinter.java create mode 100644 print/src/test/java/com/seaofnodes/print/PrinterTest.java (limited to 'print') diff --git a/print/Makefile b/print/Makefile new file mode 100644 index 00000000..9518b2d1 --- /dev/null +++ b/print/Makefile @@ -0,0 +1,14 @@ +SHELL := /bin/bash +.DEFAULT_GOAL := tests +.DELETE_ON_ERROR: +main_javas := $(wildcard src/main/java/com/seaofnodes/print/*.java) +test_javas := $(wildcard src/test/java/com/seaofnodes/print/*.java) + +.PHONY: tests +tests: build/classes/.tag + java -ea -cp build/classes com.seaofnodes.print.PrinterTest + +build/classes/.tag: $(main_javas) $(test_javas) + @mkdir -p build/classes + javac -d build/classes $(main_javas) $(test_javas) + @touch $@ diff --git a/print/README.md b/print/README.md new file mode 100644 index 00000000..76243bc0 --- /dev/null +++ b/print/README.md @@ -0,0 +1,112 @@ +# Shared debug printers + +Chapters share printing algorithms here while retaining the small hooks that +describe their own nodes. This module imports no compiler classes and requires +only the JDK. `make -C print tests` runs its independent contracts; the root +`make tests` also runs them. + +## BaseNode: the common node view + +Each chapter's `Node` extends `BaseNode`. The base provides the node ID +field, naming, `print()`/`toString()`, and the expression hook. The compiler +allocates IDs as before, passing one to `super(...)`; cloning still assigns a +fresh ID from the compiler's allocator. Graph storage and rewrites remain local. + +The common read-only contract is `in(i)`, `nIns()`, `out(i)`, and `nOuts()`. +Optional dependency access defaults to an empty set. Existing `label()` and +`isDead()` methods fit directly; `typeName()` exposes the chapter's available +type text. Both printers and the viewer use this contract, so their adapters +need no ID, edge, dead-node, or dependency forwarding methods. + +## Expressions: format strings or fluent hooks + +Chapter 2's arithmetic nodes need just one line: + +```java +@Override protected String format() { return "(%1+%2)"; } +``` + +`%1` means input slot 1, `%10` means slot 10, and `%%` prints a literal `%`. +Null or unattached inputs print `____`. A missing `format()` uses the node's +label. All expression prints track repeats; constants whose type text fits in +32 characters expand every time. Larger constants use their unique name on +repeat. Naming defaults to `label()+_nid`, with no separate constant/cast/guard +prefix protocol; constants use the label `Con` and print their value normally. + +Variable-length or conditional output uses the protected hook: + +```java +@Override protected ExprPrinter _print1(ExprPrinter p) { + p.p("Phi("); + for( Node in : _inputs ) p.n(in).p(","); + return p.unchar(',').close(); +} +``` + +`p()` appends text, `n()` prints a node in the same context, and `open()`/`close()` +append parentheses. `p.prt(this,"(%1+%2)")` also works inside a custom hook. +An outside-package subclass can override either hook without exposing it as a +public compiler API. Calling an operand's `toString()` starts a separate +context; use `n()` or a format slot to retain repeat tracking. + +`unchar(',')` and `unchar(", ")` remove only a matching trailing separator. +`unchar()` and `unchar(n)` remove one or several characters unconditionally. +All return the context for chaining. + +## IR dumps + +From Chapter 8, a chapter's `IRPrinter` is an `IRAdapter` plus the familiar +debugger entry points. The common node view supplies raw edges, identity, and +labels; the adapter adds node kinds and chapter-specific type spelling. Features +have defaults so early chapters need not implement functions, modules, or memory +annotations. + +The supported paths are `Node.toString()`/`print()` for compact expressions, +`Node.p(depth)` from Chapter 8 for a bounded IR dump, and `CodeGen.toString()` +from Chapter 18 for a whole-program dump. Chapters 20-24 use the recorded +schedule after scheduling. `IRPrinter.printLine(Node, SB)` remains for evaluator +traces and compiler diagnostics; there is no separate `Node._printLine` entry +point. The viewer captures `BaseNode` facts through `SimpleGraphObserver` and +`SimpleGraphAdapter`, independently of the text printers. + +The shared IR printer owns row formatting, bounded backward slices, CFG reverse +postorder, Phi and projection grouping, and diagnostic data placement. It walks +control before data, keeping a loop's closing merge below its body. Function +dumps stop at call-graph boundaries. Chapter 25 supplies compilation-unit roots +and function ownership; the shared code does not know its module representation. +Scheduled whole-program dumps retain the compiler's existing block order. + +Printer state is private. Never compute dominators, schedule code, reorder use +lists, resolve aliases, or compute a type's layout to produce a dump. The code +must tolerate missing inputs during graph construction. Print callbacks must +obey the same read-only rule. + +## Assembly listings + +`CodeGen.asm()` is the assembly debugger entry point from Chapter 19 onward; +inside `RegAlloc`, use `_code.asm()`. It calls the chapter's `ASMPrinter` +adapter and then the shared assembly printer. Keep this path even when it has +no ordinary source callers: it is an intentional debugger API. + +Register spelling comes from `CodeGen.reg(...)`: `N` before a live +range exists, `V` while that range has no chosen register, then the +selected register or stack location. Diagnostic LRG lookup follows leaders +without compressing them or changing the node mapping. After encoding, the +same entry point includes recorded instruction bytes and constant-pool dumps +(and static data where supported). + +From Chapter 19, `AssemblyAdapter` supplies machine-specific instruction +spelling, register names, visibility, and scheduled blocks. Machine nodes retain +their `asm` hooks. Encoding chapters additionally expose recorded instruction +offsets, lengths, bytes, and constant-pool metadata. The shared implementation +owns traversal, columns, Phi rows, byte order, multiline instructions, and data +sections. Type sizes and alignment come from encoding metadata, never fresh +layout queries. + +## Build integration + +`print.mk` adds the shared sources to each chapter's Make build, just as the +viewer adds its sources through `graph.mk`. Maven source paths and IDEA module +dependencies include `print/` too. The graph module depends on `print/` for +`BaseNode`; Make does not require Maven. Linearized +checkouts carry the shared directory and find it at their repository root. diff --git a/print/print.iml b/print/print.iml new file mode 100644 index 00000000..c6c0d587 --- /dev/null +++ b/print/print.iml @@ -0,0 +1,16 @@ + + + + + + + + + + + + + + + + diff --git a/print/print.mk b/print/print.mk new file mode 100644 index 00000000..2e41db68 --- /dev/null +++ b/print/print.mk @@ -0,0 +1,4 @@ +# Shared printing sources, also usable in a linearized chapter checkout. +PRINT_DIR := $(patsubst %/,%,$(dir $(lastword $(MAKEFILE_LIST)))) +print_javas := $(wildcard $(PRINT_DIR)/src/main/java/com/seaofnodes/print/*.java) +main_javas += $(print_javas) diff --git a/print/src/main/java/com/seaofnodes/print/ASMPrinter.java b/print/src/main/java/com/seaofnodes/print/ASMPrinter.java new file mode 100644 index 00000000..89c64b2c --- /dev/null +++ b/print/src/main/java/com/seaofnodes/print/ASMPrinter.java @@ -0,0 +1,157 @@ +package com.seaofnodes.print; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.IdentityHashMap; +import static com.seaofnodes.print.IRAdapter.Kind; + +/** Assembly listing layout shared by every chapter with instruction selection. */ +public final class ASMPrinter> { + private final AssemblyAdapter _a; + private final IRAdapter _ir; + private final StringBuilder _text=new StringBuilder(); + private final IdentityHashMap _seen=new IdentityHashMap<>(); + private int _address; + public ASMPrinter(AssemblyAdapter adapter) { _a=adapter; _ir=adapter.ir; } + + public String print() { + _text.setLength(0); + _seen.clear(); + _address=0; + ArrayList blocks=_a.blocks(); + if( blocks.isEmpty() ) return "No scheduled code"; + for( int i=0; i blocks, int idx) { + if( _a.labelBlock(bb) ) _text.append(label(bb)).append(":\n"); + if( _ir.kind(bb)==Kind.CALL ) return; + boolean packed=false; + for( int i=0; i<_ir.nOuts(bb); i++ ) { + N n=_ir.out(bb,i); + if( !_ir.phi(n) || _a.hidden(n) || _seen.put(n,Boolean.TRUE)!=null ) continue; + if( _a.postAlloc() ) { + if( !packed ) { indent(); packed=true; } + _text.append(_a.phiName(n)).append(':').append(_a.register(n)).append(','); + } else { + indent(); field(_a.phiName(n),5); _text.append(' ').append(_a.register(n)); + if( _ir.kind(n)!=Kind.PARM ) { + _text.append(" = phi( "); + for( int j=1; j<_ir.nIns(n); j++ ) { + if( j>1 ) _text.append(','); + N def=_ir.in(n,j); + _text.append(def==null ? "___" : "N"+_ir.id(def)); + } + _text.append(" )"); + } + _text.append('\n'); + } + } + if( packed ) { _text.setLength(_text.length()-1); _text.append('\n'); } + for( int i=0; i<_ir.nOuts(bb); i++ ) { + N n=_ir.out(bb,i); + if( n!=null && !_ir.phi(n) ) instruction(n,blocks,idx); + } + } + + private void instruction(N n, ArrayList blocks, int idx) { + if( n==null || _a.hidden(n) || _ir.kind(n)==Kind.CPROJ ) return; + if( _ir.region(n) && _ir.kind(n)!=Kind.FUN ) { + if( _a.encoded() ) return; + // A successor may be reached by falling through empty blocks. + for( int j=idx+1; j1 ) break; + } + address(_address++); field("??",_a.defaultSize()*2); + _text.append(" "); field("JMP",5); _text.append(' ').append(label(n)).append('\n'); + return; + } + if( _seen.put(n,Boolean.TRUE)!=null ) return; + if( _ir.kind(n)==Kind.PROJ ) { + if( _a.encoded() ) return; + indent(); _text.append(" "); field(_a.register(n),5); + _text.append(" // ").append(_ir.label(n)).append('\n'); + return; + } + int offset=_a.offset(n), size=Math.max(0,_a.size(n)), width=_a.defaultSize(); + if( offset>=0 ) _address=offset; + String args=_a.operands(n); + String[] lines=(args.startsWith("\n") ? args.substring(1) : args).split("\n",-1); + int done=0; + for( int row=0; row0 && done>=size && row==lines.length-1 && lines[row].isEmpty() ) break; + address(_address); + int count=_a.bytes()==null ? 0 : Math.min(width,size-done); + bytes(_address,count,_a.littleEndian()); + field("",(width-count)*2); _text.append(" "); + if( row==0 ) { field(_a.op(n),5); _text.append(' '); } + if( row=lines.length-1 ) break; + } + if( !_ir.control(n) ) + for( int i=0; i<_ir.nOuts(n); i++ ) { + N proj=_ir.out(n,i); + if( proj!=null && _ir.kind(proj)==Kind.PROJ && _ir.input0(proj)==n ) instruction(proj,blocks,idx); + } + } + private void indent() { field("",7+_a.defaultSize()*2); } + private void field(String text, int width) { + _text.append(text); + if( width>text.length() ) _text.append(" ".repeat(width-text.length())); + } + private void address(int address) { _text.append("%04x ".formatted(address)); } + private void bytes(int offset, int count, boolean little) { + byte[] bytes=_a.bytes(); + for( int i=0; i=bytes.length ) _text.append("??"); + else _text.append("%02x".formatted(bytes[idx]&255)); + } + } + + /** Metadata captured during encoding; printing never computes a type's layout. */ + public record Data(Object identity, String type, int alignment, int size) {} + public record Pool(String name, byte[] bytes, int offset, int address, ArrayList entries) {} + + public static String pool(Pool pool) { + StringBuilder sb=new StringBuilder("--- "+pool.name()+" ------\n"); + ArrayList entries=new ArrayList<>(pool.entries()); + entries.sort(Comparator.comparingInt(Data::alignment).reversed()); + IdentityHashMap seen=new IdentityHashMap<>(); + int offset=pool.offset(), address=pool.address(); + for( Data entry : entries ) { + if( seen.put(entry.identity(),Boolean.TRUE)!=null ) continue; + sb.append("%04x ".formatted(address)); + for( int i=0; i> { + public final IRAdapter ir; + protected AssemblyAdapter(IRAdapter ir) { this.ir=ir; } + public abstract ArrayList blocks(); + public abstract String op(N n); + public abstract String operands(N n); + public abstract String register(N n); + public String comment(N n) { return null; } + public String phiName(N n) { return ir.label(n); } + public boolean hidden(N n) { return false; } + public boolean labelBlock(N n) { return true; } + public boolean postAlloc() { return false; } + public boolean encoded() { return false; } + public boolean prologue(N fun) { return false; } + public int defaultSize() { return 4; } + public boolean littleEndian() { return true; } + public int offset(N n) { return -1; } + public int size(N n) { return 1; } + public byte[] bytes() { return null; } + public ArrayList pools(int codeEnd) { return new ArrayList<>(); } +} diff --git a/print/src/main/java/com/seaofnodes/print/BaseNode.java b/print/src/main/java/com/seaofnodes/print/BaseNode.java new file mode 100644 index 00000000..cc196b8c --- /dev/null +++ b/print/src/main/java/com/seaofnodes/print/BaseNode.java @@ -0,0 +1,37 @@ +package com.seaofnodes.print; + +/** Common read-only node view for debug printing and graph capture. */ +public abstract class BaseNode> { + // Allocated by the compiler. Copies receive a new ID from that same allocator. + public int _nid; + protected BaseNode(int nid) { _nid=nid; } + + public abstract N in(int i); + public abstract int nIns(); + public abstract N out(int i); + public abstract int nOuts(); + public int nDeps() { return 0; } + public N dep(int i) { throw new IndexOutOfBoundsException(i); } + + public String label() { return getClass().getSimpleName(); } + public String typeName() { return null; } + public boolean isDead() { return false; } + public boolean isCFG() { return false; } + public String glabel() { return label(); } + public String comment() { return null; } + public final String uniqueName() { return label()+_nid; } + + // %0, %1, ... name input slots; %% prints a literal percent sign. + protected String format() { return null; } + protected ExprPrinter _print1(ExprPrinter p) { + String fmt=format(); + return fmt==null ? p.p(label()) : p.prt(self(),fmt); + } + // Short constants return null to expand their value on each appearance. + protected String repeatName() { return label(); } + + @SuppressWarnings("unchecked") + private N self() { return (N)this; } + public final String print() { return ExprPrinter.print(self()); } + @Override public final String toString() { return print(); } +} diff --git a/print/src/main/java/com/seaofnodes/print/ExprPrinter.java b/print/src/main/java/com/seaofnodes/print/ExprPrinter.java new file mode 100644 index 00000000..129be470 --- /dev/null +++ b/print/src/main/java/com/seaofnodes/print/ExprPrinter.java @@ -0,0 +1,56 @@ +package com.seaofnodes.print; + +import java.util.IdentityHashMap; + +/** One expression's buffer and repeat tracking, shared by recursive node hooks. */ +public final class ExprPrinter> { + private final StringBuilder _text=new StringBuilder(); + private final IdentityHashMap _seen=new IdentityHashMap<>(); + private ExprPrinter() {} + + public static > String print(N node) { + return new ExprPrinter().n(node).toString(); + } + + public ExprPrinter n(N node) { + if( node==null ) return p("____"); + if( node.isDead() ) return p(node.uniqueName()).p(":DEAD"); + if( _seen.put(node,Boolean.TRUE)!=null ) { + String ref=node.repeatName(); + if( ref!=null ) return p(ref); + } + node._print1(this); + return this; + } + + /** Input slots are decimal numbers. Missing inputs print like null inputs. */ + public ExprPrinter prt(N node, String fmt) { + for( int i=0; i='0' && fmt.charAt(i)<='9' ) i++; + if( start==i ) throw new IllegalArgumentException("Expected input slot in "+fmt); + int slot=Integer.parseInt(fmt.substring(start,i--)); + n(node==null || slot>=node.nIns() ? null : node.in(slot)); + } + return this; + } + + public ExprPrinter p(Object text) { _text.append(text); return this; } + public ExprPrinter open() { return p('('); } + public ExprPrinter close() { return p(')'); } + public ExprPrinter unchar() { return unchar(1); } + public ExprPrinter unchar(int n) { _text.setLength(_text.length()-n); return this; } + /** Remove a trailing separator only when it matches. */ + public ExprPrinter unchar(char c) { + return _text.length()>0 && _text.charAt(_text.length()-1)==c ? unchar() : this; + } + public ExprPrinter unchar(String suffix) { + int start=_text.length()-suffix.length(); + return start>=0 && _text.indexOf(suffix,start)==start ? unchar(suffix.length()) : this; + } + @Override public String toString() { return _text.toString(); } +} diff --git a/print/src/main/java/com/seaofnodes/print/IRAdapter.java b/print/src/main/java/com/seaofnodes/print/IRAdapter.java new file mode 100644 index 00000000..06b169b0 --- /dev/null +++ b/print/src/main/java/com/seaofnodes/print/IRAdapter.java @@ -0,0 +1,34 @@ +package com.seaofnodes.print; + +/** Read-only facts about a chapter's graph. Needed only for structured IR dumps. */ +public abstract class IRAdapter> { + public enum Kind { DATA, CONSTANT, CTRL, START, STOP, REGION, LOOP, PHI, PARM, + MULTI, PROJ, CPROJ, FUN, RETURN, CALL, CALL_END, UNIT } + public int id(N n) { return n._nid; } + public String label(N n) { return n.label(); } + public int nIns(N n) { return n.nIns(); } + public N in(N n, int i) { return n.in(i); } + public int nOuts(N n) { return n.nOuts(); } + public N out(N n, int i) { return n.out(i); } + public abstract Kind kind(N n); + public boolean dead(N n) { return n.isDead(); } + public String type(N n) { String t=n.typeName(); return t==null ? "" : t; } + public int index(N n) { return id(n); } + public String signature(N fun) { return label(fun); } + public String functionName(N fun) { return label(fun); } + public String inputMark(N n, N def) { return " "; } + public boolean global(N n) { return kind(n)==Kind.CONSTANT; } + public int inputColumns() { return 4; } + + public final N input0(N n) { return n == null || nIns(n) == 0 ? null : in(n,0); } + public final boolean control(N n) { + if( n == null ) return false; + return switch(kind(n)) { + case CTRL, START, STOP, REGION, LOOP, CPROJ, FUN, RETURN, CALL, CALL_END, UNIT -> true; + default -> false; + }; + } + public final boolean phi(N n) { return n != null && (kind(n) == Kind.PHI || kind(n) == Kind.PARM); } + public final boolean projection(N n) { return n != null && (kind(n) == Kind.PROJ || kind(n) == Kind.CPROJ); } + public final boolean region(N n) { return n != null && (kind(n) == Kind.REGION || kind(n) == Kind.LOOP || kind(n) == Kind.FUN); } +} diff --git a/print/src/main/java/com/seaofnodes/print/IRPrinter.java b/print/src/main/java/com/seaofnodes/print/IRPrinter.java new file mode 100644 index 00000000..bfe1cb05 --- /dev/null +++ b/print/src/main/java/com/seaofnodes/print/IRPrinter.java @@ -0,0 +1,293 @@ +package com.seaofnodes.print; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.IdentityHashMap; +import static com.seaofnodes.print.IRAdapter.Kind; + +/** Shared diagnostic traversal. All ownership, ordering and visited state is local. */ +public final class IRPrinter> { + private final IRAdapter _a; + public IRPrinter(IRAdapter adapter) { _a = adapter; } + + public record Unit(String name, N start, N stop, ArrayList functions) {} + + public String program(N start, N stop, ArrayList> units) { + StringBuilder sb=new StringBuilder(line(start)); + ArrayList constants=new ArrayList<>(); + IdentityHashMap graph=new IdentityHashMap<>(), global=new IdentityHashMap<>(); + globals(start,graph,constants); + for( N n : constants ) global.put(n,Boolean.TRUE); + // GVN can share a floating expression of constants between functions. + for( N n : sorted(graph) ) + if( !_a.global(n) && floatingGlobal(n,global) ) constants.add(n); + constants.sort(Comparator.comparingInt(_a::id)); + for( N n : constants ) sb.append(line(n)); + ArrayList> ordered=new ArrayList<>(units); + ordered.sort(Comparator.comparing(u -> u.name()==null ? "" : u.name())); + for( Unit unit : ordered ) { + if( unit.start()!=null ) { + if( _a.dead(unit.start()) ) continue; + sb.append("\n=== ").append(unit.name()).append(" ===\n").append(line(unit.start())); + ArrayList ps=new ArrayList<>(); + for( int i=0; i<_a.nOuts(unit.start()); i++ ) { + N p=_a.out(unit.start(),i); + if( _a.projection(p) ) ps.add(p); + } + ps.sort(Comparator.comparingInt(_a::index)); + for( N p : ps ) sb.append(line(p)); + } + ArrayList funs=new ArrayList<>(unit.functions()); + funs.sort(Comparator.comparingInt(_a::id)); + for( N fun : funs ) if( !_a.dead(fun) ) sb.append(function(fun,global)); + sb.append(line(unit.stop())); + } + return sb.append(line(stop)).toString(); + } + + // Function-pointer constants can be attached to Returns rather than Start. + private void globals(N n, IdentityHashMap seen, ArrayList constants) { + if( n==null || seen.put(n,Boolean.TRUE)!=null ) return; + if( _a.global(n) && !_a.dead(n) ) constants.add(n); + for( int i=0; i<_a.nIns(n); i++ ) globals(_a.in(n,i),seen,constants); + for( int i=0; i<_a.nOuts(n); i++ ) globals(_a.out(n,i),seen,constants); + } + + private boolean floatingGlobal(N n, IdentityHashMap global) { + if( n==null ) return true; + Boolean old=global.get(n); + if( old!=null ) return old; + global.put(n,Boolean.FALSE); // Stop incomplete data cycles. + if( _a.dead(n) || _a.kind(n)!=Kind.DATA || _a.input0(n)!=null || _a.nIns(n)==0 ) return false; + for( int i=1; i<_a.nIns(n); i++ ) + if( !floatingGlobal(_a.in(n,i),global) ) return false; + global.put(n,Boolean.TRUE); + return true; + } + + public String line(N n) { + if( n == null ) return ""; + StringBuilder sb = new StringBuilder(); + sb.append("%4d %-7.7s ".formatted(_a.id(n),_a.label(n))); + if( _a.dead(n) ) return sb.append("DEAD\n").toString(); + for( int i=0; i<_a.nIns(n); i++ ) { + N def = _a.in(n,i); + sb.append(def == null ? "____" : "%4d".formatted(_a.id(def))).append(_a.inputMark(n,def)); + } + int cols = _a.inputColumns(); + for( int i=_a.nIns(n); i nodes = new IdentityHashMap<>(); + ArrayDeque todo = new ArrayDeque<>(); + if( root != null ) { nodes.put(root,Boolean.TRUE); todo.add(root); } + for( int d=0; d0 ) { + N n=todo.remove(); + for( int i=0; i<_a.nIns(n); i++ ) { + N def=_a.in(n,i); + if( def != null && nodes.put(def,Boolean.TRUE)==null ) todo.add(def); + } + } + } + for( N n : new ArrayList<>(nodes.keySet()) ) + if( _a.phi(n) || _a.projection(n) ) { + N head=_a.input0(n); + if( head != null ) nodes.put(head,Boolean.TRUE); + } + return render(nodes); + } + + /** Dump one function without traversing the caller/callee linkage. */ + public String function(N fun) { + return function(fun,new IdentityHashMap<>()); + } + + private String function(N fun, IdentityHashMap global) { + IdentityHashMap nodes = new IdentityHashMap<>(); + collect(fun,fun,nodes); + nodes.keySet().removeIf(n -> Boolean.TRUE.equals(global.get(n))); + // Floating expressions of constants need not have a forward path from + // the function header. Include their definitions from the owned uses. + for( N n : new ArrayList<>(nodes.keySet()) ) + // Parm alternatives are arguments in the callers, not local defs. + if( _a.kind(n)!=Kind.PARM ) + for( int i=0; i<_a.nIns(n); i++ ) collectData(_a.in(n,i),nodes,global); + return "\n--- "+_a.signature(fun)+"----------------------\n"+ + render(nodes)+"--- "+_a.functionName(fun)+" ----------------------\n"; + } + + private void collect(N n, N owner, IdentityHashMap seen) { + if( n == null || _a.dead(n) || seen.containsKey(n) || _a.global(n) ) return; + Kind k=_a.kind(n); + if( (k==Kind.FUN && n!=owner) || (k==Kind.PARM && _a.input0(n)!=owner) ) return; + if( k==Kind.START || k==Kind.STOP || k==Kind.UNIT ) return; + if( k==Kind.CALL_END && !seen.containsKey(_a.input0(n)) ) return; + seen.put(n,Boolean.TRUE); + if( k!=Kind.RETURN ) + for( int i=0; i<_a.nOuts(n); i++ ) collect(_a.out(n,i),owner,seen); + } + + private void collectData(N n, IdentityHashMap seen, IdentityHashMap global) { + if( n==null || seen.containsKey(n) || _a.dead(n) || _a.global(n) || _a.control(n) || + Boolean.TRUE.equals(global.get(n)) ) return; + N head=_a.input0(n); + if( _a.control(head) && !seen.containsKey(head) ) return; + seen.put(n,Boolean.TRUE); + for( int i=0; i<_a.nIns(n); i++ ) collectData(_a.in(n,i),seen,global); + } + + private ArrayList sorted(IdentityHashMap nodes) { + ArrayList ns = new ArrayList<>(nodes.keySet()); + ns.sort(Comparator.comparingInt(_a::id)); + return ns; + } + + /** Finish CFG RPO before placing data; data backedges cannot reorder blocks. */ + private String render(IdentityHashMap nodes) { + ArrayList ns=sorted(nodes), post=new ArrayList<>(); + IdentityHashMap seen=new IdentityHashMap<>(); + // Start from CFG roots, then cover disconnected/partially built components. + for( N n : ns ) + if( _a.control(n) && !hasPred(n,nodes) ) controlPost(n,nodes,seen,post); + for( N n : ns ) + if( _a.control(n) ) controlPost(n,nodes,seen,post); + Collections.reverse(post); + IdentityHashMap blocks=new IdentityHashMap<>(); + ArrayList> body=new ArrayList<>(); + for( int i=0; i()); } + if( body.isEmpty() ) body.add(new ArrayList<>()); + for( N n : ns ) + if( !_a.control(n) ) body.get(block(n,nodes,blocks)).add(n); + StringBuilder sb=new StringBuilder(); + IdentityHashMap emitted=new IdentityHashMap<>(); + for( int i=0; i nodes) { + for( int i=0; i<_a.nIns(n); i++ ) { + N def=_a.in(n,i); + // The loop entry determines its root status, not its backedge. + if( _a.kind(n)==Kind.LOOP && i>1 ) break; + if( def!=null && nodes.containsKey(def) && _a.control(def) && edge(def,n) ) return true; + } + return false; + } + private void controlPost(N n, IdentityHashMap nodes, + IdentityHashMap seen, ArrayList post) { + if( seen.put(n,Boolean.TRUE)!=null ) return; + ArrayList uses=new ArrayList<>(); + for( int i=0; i<_a.nOuts(n); i++ ) { + N use=_a.out(n,i); + if( use!=null && nodes.containsKey(use) && edge(n,use) ) uses.add(use); + } + uses.sort(Comparator.comparingInt(_a::id)); + for( N use : uses ) controlPost(use,nodes,seen,post); + post.add(n); + } + private int block(N n, IdentityHashMap nodes, IdentityHashMap blocks) { + Integer old=blocks.get(n); + if( old!=null ) return old; + if( n==null || !nodes.containsKey(n) || _a.kind(n)==Kind.CONSTANT ) return 0; + blocks.put(n,0); + int b=0; + N head=_a.input0(n); + if( _a.control(head) || _a.projection(n) ) b=block(head,nodes,blocks); + else for( int i=0; i<_a.nIns(n); i++ ) b=Math.max(b,block(_a.in(n,i),nodes,blocks)); + blocks.put(n,b); + return b; + } + private void emitDefs(N n, IdentityHashMap nodes, IdentityHashMap emitted, + StringBuilder sb) { + for( int i=0; i<_a.nIns(n); i++ ) emit(_a.in(n,i),nodes,emitted,sb); + } + private void emit(N n, IdentityHashMap nodes, IdentityHashMap emitted, + StringBuilder sb) { + if( n==null || emitted.containsKey(n) || !nodes.containsKey(n) || _a.control(n) || _a.phi(n) ) return; + if( _a.projection(n) && nodes.containsKey(_a.input0(n)) ) { + N head=_a.input0(n); + if( !emitted.containsKey(head) ) emit(head,nodes,emitted,sb); + if( emitted.containsKey(n) ) return; + } + emitted.put(n,Boolean.TRUE); + emitDefs(n,nodes,emitted,sb); + sb.append(line(n)); + projections(n,nodes,emitted,sb); + } + private void emitLine(N n, IdentityHashMap emitted, StringBuilder sb) { + if( emitted.put(n,Boolean.TRUE)==null ) sb.append(line(n)); + } + private void projections(N n, IdentityHashMap nodes, IdentityHashMap emitted, + StringBuilder sb) { + ArrayList ps=new ArrayList<>(); + for( int i=0; i<_a.nOuts(n); i++ ) { + N p=_a.out(n,i); + if( p!=null && nodes.containsKey(p) && _a.kind(p)==Kind.PROJ && _a.input0(p)==n ) ps.add(p); + } + ps.sort(Comparator.comparingInt(_a::index)); + for( N p : ps ) emitLine(p,emitted,sb); + } + + /** Scheduling already determines order; inspect it without sorting compiler arrays. */ + public String scheduled(ArrayList blocks) { + StringBuilder sb=new StringBuilder(); + IdentityHashMap emitted=new IdentityHashMap<>(); + for( N block : blocks ) { + if( block==null ) continue; + sb.append('\n'); + emitLine(block,emitted,sb); + for( int i=0; i<_a.nOuts(block); i++ ) { + N use=_a.out(block,i); + if( _a.phi(use) ) emitLine(use,emitted,sb); + } + for( int i=0; i<_a.nOuts(block); i++ ) { + N use=_a.out(block,i); + if( use!=null && !_a.control(use) ) { + emitLine(use,emitted,sb); + ArrayList ps=new ArrayList<>(); + for( int j=0; j<_a.nOuts(use); j++ ) { + N p=_a.out(use,j); + if( p!=null && _a.kind(p)==Kind.PROJ && _a.input0(p)==use ) ps.add(p); + } + ps.sort(Comparator.comparingInt(_a::index)); + for( N p : ps ) emitLine(p,emitted,sb); + } + } + } + return sb.toString(); + } +} diff --git a/print/src/test/java/com/seaofnodes/print/PrinterTest.java b/print/src/test/java/com/seaofnodes/print/PrinterTest.java new file mode 100644 index 00000000..d63cc6cb --- /dev/null +++ b/print/src/test/java/com/seaofnodes/print/PrinterTest.java @@ -0,0 +1,153 @@ +package com.seaofnodes.print; + +import java.util.ArrayList; +import java.util.Arrays; +import static com.seaofnodes.print.IRAdapter.Kind; + +/** Small independent contracts for the shared printers. Run with assertions enabled. */ +public class PrinterTest { + static class N extends BaseNode { + final String name; + final Kind kind; + final ArrayList ins=new ArrayList<>(), outs=new ArrayList<>(); + N(int id, String name, Kind kind, N... defs) { + super(id); + this.name=name; this.kind=kind; + for( N def : defs ) add(def); + } + @Override public N in(int i) { return ins.get(i); } + @Override public int nIns() { return ins.size(); } + @Override public N out(int i) { return outs.get(i); } + @Override public int nOuts() { return outs.size(); } + @Override public String label() { return name; } + @Override protected String repeatName() { return kind==Kind.CONSTANT ? null : name; } + @Override protected String format() { return ins.isEmpty() ? null : "(%0+%1)"; } + void add(N def) { ins.add(def); if( def!=null ) def.outs.add(this); } + } + static class Adapter extends IRAdapter { + @Override public Kind kind(N n) { return n.kind; } + } + + public static void main(String[] args) { + expression(); loop(); functions(); assembly(); + System.out.println("Shared printer contracts passed"); + } + static void expression() { + N one=new N(1,"1",Kind.CONSTANT), add=new N(2,"Add",Kind.DATA,one,one); + assert add.print().equals("(1+1)"); + add.ins.set(1,add); + assert add.print().equals("(1+Add)"); + // A failed callback must not leave another print's repeat state behind. + N bad=new N(3,"Bad",Kind.DATA) { + @Override protected ExprPrinter _print1(ExprPrinter p) { throw new IllegalStateException(); } + }; + try { bad.print(); } catch( IllegalStateException expected ) {} + assert add.print().equals("(1+Add)"); + N fmt=new N(4,"Format",Kind.DATA) { + @Override protected ExprPrinter _print1(ExprPrinter p) { return p.prt(this,"%10 %% %0 %12"); } + }; + for( int i=0; i<11; i++ ) fmt.add(one); + assert fmt.print().equals("1 % 1 ____") : fmt.print(); + N empty=new N(5,"Empty",Kind.DATA) { + @Override protected ExprPrinter _print1(ExprPrinter p) { return p.open().unchar(',').unchar(", ").close(); } + }; + assert empty.print().equals("()"); + } + static void loop() { + N fun=new N(1,"Fun",Kind.FUN); + N loop=new N(2,"Loop",Kind.LOOP,null,fun); + N phi=new N(3,"Phi",Kind.PHI,loop,null); + N branch=new N(4,"If",Kind.CTRL,loop,phi); + N yes=new N(5,"True",Kind.CPROJ,branch), no=new N(6,"False",Kind.CPROJ,branch); + N left=new N(7,"Left",Kind.CTRL,yes), right=new N(8,"Right",Kind.CTRL,no); + N merge=new N(9,"Merge",Kind.REGION,null,left,right); + N value=new N(10,"Add",Kind.DATA,null,phi); + phi.add(value); loop.add(merge); + N exit=new N(11,"Return",Kind.RETURN,merge,value); + // A call linkage must not bring another function's body into this dump. + N foreign=new N(12,"Other",Kind.FUN,exit); + new N(13,"Foreign",Kind.RETURN,foreign); + var nodes=new ArrayList<>(Arrays.asList(fun,loop,phi,branch,yes,no,left,right,merge,value,exit)); + var inputs=new ArrayList>(); var outputs=new ArrayList>(); + for( N n : nodes ) { inputs.add(new ArrayList<>(n.ins)); outputs.add(new ArrayList<>(n.outs)); } + IRPrinter printer=new IRPrinter<>(new Adapter()); + String text=printer.function(fun); + assert text.equals(printer.function(fun)); + assert !text.contains("Foreign"); + int li=row(text,"Loop"), pi=row(text,"Phi"), le=row(text,"Left"), ri=row(text,"Right"), mi=row(text,"Merge"); + assert li>=0 && pi>li && le>pi && ri>pi && mi>le && mi>ri : text; + String[] lines=text.split("\n"); + for( int i=0; i printer=new IRPrinter<>(new Adapter()); + var funs=new ArrayList<>(Arrays.asList(caller,callee)); + var units=new ArrayList>(); + units.add(new IRPrinter.Unit<>("",null,null,funs)); + String text=printer.program(start,stop,units); + for( N n : Arrays.asList(start,stop,one,sum,caller,callee,arg,load,parm,ret1,ret2) ) { + long count=text.lines().filter(line -> line.matches("\\s*"+n._nid+" .*" )).count(); + assert count==1 : n.name+" appears "+count+" times\n"+text; + } + assert row(text,"Sum")(Arrays.asList(caller,ret1))); + assert row(scheduled,"Ptr")>row(scheduled,"New") : scheduled; + } + + static void assembly() { + N fun=new N(1,"Fun",Kind.FUN), op=new N(2,"op",Kind.DATA,fun); + N ret=new N(3,"Return",Kind.RETURN,fun,op); + boolean[] encoded={true}; + var adapter=new AssemblyAdapter(new Adapter()) { + @Override public ArrayList blocks() { return new ArrayList<>(Arrays.asList(fun,ret)); } + @Override public String op(N n) { return n.name; } + @Override public String operands(N n) { return n==op ? "\nfirst\nsecond" : ""; } + @Override public String register(N n) { return "r0"; } + @Override public boolean hidden(N n) { return n==ret; } + @Override public boolean encoded() { return encoded[0]; } + @Override public int defaultSize() { return 2; } + @Override public int size(N n) { return 4; } + @Override public int offset(N n) { return 0; } + @Override public byte[] bytes() { return encoded[0] ? new byte[]{1,2,3,4} : null; } + @Override public boolean littleEndian() { return false; } + }; + ASMPrinter printer=new ASMPrinter<>(adapter); + String asm=printer.print(); + assert asm.equals(printer.print()); + assert asm.contains("0201") && asm.contains("0403") && asm.contains("second") : asm; + encoded[0]=false; + asm=new ASMPrinter<>(adapter).print(); + assert asm.contains("first") && asm.contains("second") : asm; + Object type=new Object(); + var entries=new ArrayList(); + entries.add(new ASMPrinter.Data(type,"Pair",1,2)); + entries.add(new ASMPrinter.Data(type,"Pair",1,2)); + String pool=ASMPrinter.pool(new ASMPrinter.Pool("Constants",new byte[]{5,6},0,16,entries)); + assert pool.indexOf("Pair")==pool.lastIndexOf("Pair") : pool; + assert pool.contains("0010 0506") : pool; + } +} -- cgit v1.2.3