diff options
Diffstat (limited to 'print')
| -rw-r--r-- | print/Makefile | 14 | ||||
| -rw-r--r-- | print/README.md | 112 | ||||
| -rw-r--r-- | print/print.iml | 16 | ||||
| -rw-r--r-- | print/print.mk | 4 | ||||
| -rw-r--r-- | print/src/main/java/com/seaofnodes/print/ASMPrinter.java | 157 | ||||
| -rw-r--r-- | print/src/main/java/com/seaofnodes/print/AssemblyAdapter.java | 26 | ||||
| -rw-r--r-- | print/src/main/java/com/seaofnodes/print/BaseNode.java | 37 | ||||
| -rw-r--r-- | print/src/main/java/com/seaofnodes/print/ExprPrinter.java | 56 | ||||
| -rw-r--r-- | print/src/main/java/com/seaofnodes/print/IRAdapter.java | 34 | ||||
| -rw-r--r-- | print/src/main/java/com/seaofnodes/print/IRPrinter.java | 293 | ||||
| -rw-r--r-- | print/src/test/java/com/seaofnodes/print/PrinterTest.java | 153 |
11 files changed, 902 insertions, 0 deletions
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<Node>`. 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<Node> _print1(ExprPrinter<Node> 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<Node>` 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<node-id>` before a live +range exists, `V<LRG-id>` 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<Node>` 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 @@ +<?xml version="1.0" encoding="UTF-8"?> +<module type="JAVA_MODULE" version="4"> + <component name="NewModuleRootManager" inherit-compiler-output="false"> + <output url="file://$MODULE_DIR$/../build/idea/production/print" /> + <output-test url="file://$MODULE_DIR$/../build/idea/test/print" /> + <exclude-output /> + <content url="file://$MODULE_DIR$"> + <sourceFolder url="file://$MODULE_DIR$/src/main/java" isTestSource="false" /> + <sourceFolder url="file://$MODULE_DIR$/src/test/java" isTestSource="true" /> + <excludeFolder url="file://$MODULE_DIR$/build" /> + <excludeFolder url="file://$MODULE_DIR$/target" /> + </content> + <orderEntry type="inheritedJdk" /> + <orderEntry type="sourceFolder" forTests="false" /> + </component> +</module> 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<N extends BaseNode<N>> { + private final AssemblyAdapter<N> _a; + private final IRAdapter<N> _ir; + private final StringBuilder _text=new StringBuilder(); + private final IdentityHashMap<N,Boolean> _seen=new IdentityHashMap<>(); + private int _address; + public ASMPrinter(AssemblyAdapter<N> adapter) { _a=adapter; _ir=adapter.ir; } + + public String print() { + _text.setLength(0); + _seen.clear(); + _address=0; + ArrayList<N> blocks=_a.blocks(); + if( blocks.isEmpty() ) return "No scheduled code"; + for( int i=0; i<blocks.size(); i++ ) { + N fun=blocks.get(i); + if( _ir.kind(fun)!=Kind.FUN ) continue; + _text.append("\n--- ").append(_ir.signature(fun)).append("---------------------------\n"); + if( _a.encoded() ) _address=(_address+15)&-16; + if( _a.prologue(fun) ) instruction(fun,blocks,i); + for( ; i<blocks.size() && _ir.kind(blocks.get(i))!=Kind.RETURN; i++ ) + block(blocks.get(i),blocks,i); + _text.append("--- ").append(_ir.functionName(fun)).append("---------------------------\n"); + } + for( Pool pool : _a.pools(_address) ) _text.append(pool(pool)); + return _text.toString(); + } + + private String label(N n) { return (_ir.kind(n)==Kind.LOOP ? "LOOP" : "L")+_ir.id(n); } + private void block(N bb, ArrayList<N> 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<N> 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; j<blocks.size(); j++ ) { + N next=blocks.get(j); + if( next==n ) return; + if( _ir.nOuts(next)>1 ) 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; row<lines.length || done<size; row++ ) { + if( row>0 && 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 ) field(lines[row],row==0 ? 30 : 0); + if( row==0 ) { + String comment=_a.comment(n); + if( comment!=null ) _text.append(" // ").append(comment); + } + _text.append('\n'); + done+=count; _address+=count; + if( _a.bytes()==null ) { + // Before encoding, multiline machine expansions still show + // every instruction; byte lengths are not yet available. + if( row==0 ) { _address+=size; done=size; } + } + if( count==0 && 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<count; i++ ) { + int idx=offset+(little ? i : count-i-1); + if( idx<0 || idx>=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<Data> entries) {} + + public static String pool(Pool pool) { + StringBuilder sb=new StringBuilder("--- "+pool.name()+" ------\n"); + ArrayList<Data> entries=new ArrayList<>(pool.entries()); + entries.sort(Comparator.comparingInt(Data::alignment).reversed()); + IdentityHashMap<Object,Boolean> 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<entry.size(); i++ ) + sb.append(offset+i<pool.bytes().length ? "%02x".formatted(pool.bytes()[offset+i]&255) : "??"); + sb.append('\t').append(entry.type()).append('\n'); + offset+=entry.size(); address+=entry.size(); + } + return sb.toString(); + } +} diff --git a/print/src/main/java/com/seaofnodes/print/AssemblyAdapter.java b/print/src/main/java/com/seaofnodes/print/AssemblyAdapter.java new file mode 100644 index 00000000..a6aaf8d8 --- /dev/null +++ b/print/src/main/java/com/seaofnodes/print/AssemblyAdapter.java @@ -0,0 +1,26 @@ +package com.seaofnodes.print; + +import java.util.ArrayList; + +/** Machine facts for a listing, independent of traversal and column formatting. */ +public abstract class AssemblyAdapter<N extends BaseNode<N>> { + public final IRAdapter<N> ir; + protected AssemblyAdapter(IRAdapter<N> ir) { this.ir=ir; } + public abstract ArrayList<N> 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<ASMPrinter.Pool> 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<N extends BaseNode<N>> { + // 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<N> _print1(ExprPrinter<N> 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<N extends BaseNode<N>> { + private final StringBuilder _text=new StringBuilder(); + private final IdentityHashMap<N,Boolean> _seen=new IdentityHashMap<>(); + private ExprPrinter() {} + + public static <N extends BaseNode<N>> String print(N node) { + return new ExprPrinter<N>().n(node).toString(); + } + + public ExprPrinter<N> 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<N> prt(N node, String fmt) { + for( int i=0; i<fmt.length(); i++ ) { + char c=fmt.charAt(i); + if( c!='%' ) { p(c); continue; } + if( ++i==fmt.length() ) throw new IllegalArgumentException("Trailing % in "+fmt); + if( fmt.charAt(i)=='%' ) { p('%'); continue; } + int start=i; + while( i<fmt.length() && fmt.charAt(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<N> p(Object text) { _text.append(text); return this; } + public ExprPrinter<N> open() { return p('('); } + public ExprPrinter<N> close() { return p(')'); } + public ExprPrinter<N> unchar() { return unchar(1); } + public ExprPrinter<N> unchar(int n) { _text.setLength(_text.length()-n); return this; } + /** Remove a trailing separator only when it matches. */ + public ExprPrinter<N> unchar(char c) { + return _text.length()>0 && _text.charAt(_text.length()-1)==c ? unchar() : this; + } + public ExprPrinter<N> 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<N extends BaseNode<N>> { + 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<N extends BaseNode<N>> { + private final IRAdapter<N> _a; + public IRPrinter(IRAdapter<N> adapter) { _a = adapter; } + + public record Unit<N>(String name, N start, N stop, ArrayList<N> functions) {} + + public String program(N start, N stop, ArrayList<Unit<N>> units) { + StringBuilder sb=new StringBuilder(line(start)); + ArrayList<N> constants=new ArrayList<>(); + IdentityHashMap<N,Boolean> 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<Unit<N>> ordered=new ArrayList<>(units); + ordered.sort(Comparator.comparing(u -> u.name()==null ? "" : u.name())); + for( Unit<N> 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<N> 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<N> 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<N,Boolean> seen, ArrayList<N> 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<N,Boolean> 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<cols; i++ ) sb.append(" "); + sb.append(" [[ "); + for( int i=0; i<_a.nOuts(n); i++ ) { + N use = _a.out(n,i); + sb.append(use == null ? "____ " : "%4d ".formatted(_a.id(use))); + } + for( int i=_a.nOuts(n); i<cols+2-Math.max(_a.nIns(n),cols); i++ ) sb.append(" "); + return sb.append(" ]] ").append(_a.type(n)).append('\n').toString(); + } + + /** A bounded backward slice, including the headers of boundary projections/Phis. */ + public String prettyPrint(N root, int depth) { + IdentityHashMap<N,Boolean> nodes = new IdentityHashMap<>(); + ArrayDeque<N> todo = new ArrayDeque<>(); + if( root != null ) { nodes.put(root,Boolean.TRUE); todo.add(root); } + for( int d=0; d<depth && !todo.isEmpty(); d++ ) { + int count=todo.size(); + while( count-->0 ) { + 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<N,Boolean> global) { + IdentityHashMap<N,Boolean> 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<N,Boolean> 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<N,Boolean> seen, IdentityHashMap<N,Boolean> 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<N> sorted(IdentityHashMap<N,Boolean> nodes) { + ArrayList<N> 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<N,Boolean> nodes) { + ArrayList<N> ns=sorted(nodes), post=new ArrayList<>(); + IdentityHashMap<N,Boolean> 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<N,Integer> blocks=new IdentityHashMap<>(); + ArrayList<ArrayList<N>> body=new ArrayList<>(); + for( int i=0; i<post.size(); i++ ) { blocks.put(post.get(i),i); body.add(new ArrayList<>()); } + 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<N,Boolean> emitted=new IdentityHashMap<>(); + for( int i=0; i<body.size(); i++ ) { + if( i<post.size() ) { + N cfg=post.get(i); + sb.append('\n'); + emitDefs(cfg,nodes,emitted,sb); + emitLine(cfg,emitted,sb); + // A Phi's backedge belongs in the body, never ahead of the Phi. + for( N n : body.get(i) ) if( _a.phi(n) ) emitLine(n,emitted,sb); + } + for( N n : body.get(i) ) emit(n,nodes,emitted,sb); + } + // Include unanchored Phis and dead/incomplete nodes exactly once. + for( N n : ns ) emitLine(n,emitted,sb); + return sb.toString(); + } + + private boolean edge(N def, N use) { + if( !_a.control(use) || _a.kind(use)==Kind.FUN || _a.kind(def)==Kind.RETURN ) return false; + if( _a.region(use) || _a.kind(use)==Kind.STOP ) { + for( int i=_a.kind(use)==Kind.STOP ? 0 : 1; i<_a.nIns(use); i++ ) + if( _a.in(use,i)==def ) return true; + return false; + } + return _a.input0(use)==def; + } + private boolean hasPred(N n, IdentityHashMap<N,Boolean> 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<N,Boolean> nodes, + IdentityHashMap<N,Boolean> seen, ArrayList<N> post) { + if( seen.put(n,Boolean.TRUE)!=null ) return; + ArrayList<N> 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<N,Boolean> nodes, IdentityHashMap<N,Integer> 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<N,Boolean> nodes, IdentityHashMap<N,Boolean> 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<N,Boolean> nodes, IdentityHashMap<N,Boolean> 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<N,Boolean> emitted, StringBuilder sb) { + if( emitted.put(n,Boolean.TRUE)==null ) sb.append(line(n)); + } + private void projections(N n, IdentityHashMap<N,Boolean> nodes, IdentityHashMap<N,Boolean> emitted, + StringBuilder sb) { + ArrayList<N> 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<N> blocks) { + StringBuilder sb=new StringBuilder(); + IdentityHashMap<N,Boolean> 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<N> 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<N> { + final String name; + final Kind kind; + final ArrayList<N> 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<N> { + @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<N> _print1(ExprPrinter<N> 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<N> _print1(ExprPrinter<N> 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<N> _print1(ExprPrinter<N> 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<ArrayList<N>>(); var outputs=new ArrayList<ArrayList<N>>(); + for( N n : nodes ) { inputs.add(new ArrayList<>(n.ins)); outputs.add(new ArrayList<>(n.outs)); } + IRPrinter<N> 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<lines.length; i++ ) + if( lines[i].matches("\\s*2 Loop.*") ) assert lines[i+1].matches("\\s*3 Phi.*") : text; + for( int i=0; i<nodes.size(); i++ ) { + N n=nodes.get(i); + assert n.ins.equals(inputs.get(i)) && n.outs.equals(outputs.get(i)); + int count=0; + for( String line : lines ) if( line.matches("\\s*"+n._nid+" "+n.name+" .*")) count++; + assert count==1 : n.name+" appears "+count+" times\n"+text; + } + assert printer.prettyPrint(null,2).isEmpty(); + } + static int row(String text,String name) { return text.indexOf(" "+name+" "); } + + static void functions() { + N start=new N(1,"Start",Kind.START), stop=new N(2,"Stop",Kind.STOP); + N one=new N(3,"One",Kind.CONSTANT,start); + N sum=new N(4,"Sum",Kind.DATA,null,one,one); + N caller=new N(5,"Caller",Kind.FUN,start), callee=new N(6,"Callee",Kind.FUN,start); + N arg=new N(7,"Arg",Kind.PARM,caller); + N load=new N(8,"Load",Kind.DATA,caller,arg); + N parm=new N(9,"Parm",Kind.PARM,callee,load); + N ret1=new N(10,"Ret1",Kind.RETURN,caller,load,sum); + N ret2=new N(11,"Ret2",Kind.RETURN,callee,parm,sum); + stop.add(ret1); stop.add(ret2); + IRPrinter<N> printer=new IRPrinter<>(new Adapter()); + var funs=new ArrayList<>(Arrays.asList(caller,callee)); + var units=new ArrayList<IRPrinter.Unit<N>>(); + 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")<row(text,"Caller") : text; + assert !printer.function(callee).contains(" Load ") : text; + + N alloc=new N(12,"New",Kind.MULTI,caller), ptr=new N(13,"Ptr",Kind.PROJ,alloc); + String scheduled=printer.scheduled(new ArrayList<>(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<N>(new Adapter()) { + @Override public ArrayList<N> 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<N> 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<ASMPrinter.Data>(); + 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; + } +} |