diff options
| -rw-r--r-- | chapter04/Makefile | 9 | ||||
| -rw-r--r-- | chapter04/pom.xml | 3 | ||||
| -rw-r--r-- | chapter04/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java | 38 | ||||
| -rw-r--r-- | chapter25/Makefile | 7 | ||||
| -rw-r--r-- | chapter25/pom.xml | 3 | ||||
| -rw-r--r-- | chapter25/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java | 74 | ||||
| -rw-r--r-- | graph/README.md | 99 | ||||
| -rw-r--r-- | graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java | 67 | ||||
| -rw-r--r-- | graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java | 38 | ||||
| -rw-r--r-- | pom.xml | 17 |
10 files changed, 345 insertions, 10 deletions
diff --git a/chapter04/Makefile b/chapter04/Makefile index 7f55b343..e6c8f275 100644 --- a/chapter04/Makefile +++ b/chapter04/Makefile @@ -36,6 +36,10 @@ CLZDIR:= build/classes main_javas := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java) test_javas := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java) main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas)) +# Compile the common adapter into this chapter without copying its sources. +GRAPH_DIR := $(firstword $(wildcard ../graph graph)) +graph_javas := $(wildcard $(GRAPH_DIR)/src/main/java/com/seaofnodes/graph/*.java) +main_javas += $(graph_javas) test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas)) test_cp := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java)) classes = $(main_classes) $(test_classes) @@ -52,8 +56,11 @@ endif default: $(default_targets) +.PHONY: build +build: $(main_classes) + # Compile just the out-of-date files -$(main_classes): build/classes/main/%class: $(SRC)/%java +$(main_classes): $(CLZDIR)/main/%class: $(SRC)/%java $(graph_javas) @echo "compiling " $@ " because " $? @[ -d $(CLZDIR)/main ] || mkdir -p $(CLZDIR)/main @javac $(JAVAC_ARGS) -cp "$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(SRC) -d $(CLZDIR)/main $(main_javas) diff --git a/chapter04/pom.xml b/chapter04/pom.xml index 0fdebb14..5b9c7c6e 100644 --- a/chapter04/pom.xml +++ b/chapter04/pom.xml @@ -11,4 +11,7 @@ <artifactId>chapter04</artifactId> <packaging>jar</packaging> <name>Chapter 4</name> + <properties> + <simple.graph.directory>${project.basedir}/../graph</simple.graph.directory> + </properties> </project> diff --git a/chapter04/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter04/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java new file mode 100644 index 00000000..0755613b --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -0,0 +1,38 @@ +package com.seaofnodes.simple.print; + +import com.seaofnodes.graph.GraphAdapter; +import com.seaofnodes.graph.GraphSnapshot; +import com.seaofnodes.graph.GraphSnapshot.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.Node; +import java.util.ArrayList; + +/** Chapter 4's view of the IR; no knowledge of browser, transport or layout. */ +public class SimpleGraphAdapter extends GraphAdapter<Node> { + @Override protected int id(Node n) { return n._nid; } + @Override protected int nIns(Node n) { return n.nIns(); } + @Override protected Node in(Node n, int idx) { return n.in(idx); } + @Override protected int nOuts(Node n) { return n.nOuts(); } + @Override protected Node out(Node n, int idx) { return n.out(idx); } + + private ArrayList<Edge> edges(Node n) { + String[] names = n instanceof ScopeNode scope ? scope.reverseNames() : null; + var edges = new ArrayList<Edge>(); + for( int i = 0; i < n.nIns(); i++ ) { + Role role = n instanceof ScopeNode || n instanceof ConstantNode ? Role.ASSOC + : n instanceof ProjNode ? (n.isCFG() ? Role.CTRL : Role.DATA) + : i == 0 ? Role.CTRL : Role.DATA; + edges.add(new Edge(i, ref(n.in(i)), role, names == null ? null : names[i])); + } + return edges; + } + + @Override protected GraphSnapshot.Node desc(Node n) { + Projection proj = n instanceof ProjNode p + ? new Projection(n.nIns() == 0 ? 0 : ref(n.in(0)), p._idx) : null; + Kind kind = n instanceof ScopeNode ? Kind.SCOPE : n.isCFG() ? Kind.CTRL : Kind.DATA; + String label = n.label(); + return new GraphSnapshot.Node(n._nid, label == null ? n.getClass().getSimpleName() : label, + n._type == null ? null : n._type.toString(), kind, edges(n), proj); + } +} diff --git a/chapter25/Makefile b/chapter25/Makefile index 08b7ce56..886354d3 100644 --- a/chapter25/Makefile +++ b/chapter25/Makefile @@ -65,6 +65,10 @@ main_javas := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java $(SRC test_javas := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java) simple_driver := $(TST)/$(SIMPLE)/Simple.java main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas)) +# Compile the common adapter into this chapter without copying its sources. +GRAPH_DIR := $(firstword $(wildcard ../graph graph)) +graph_javas := $(wildcard $(GRAPH_DIR)/src/main/java/com/seaofnodes/graph/*.java) +main_javas += $(graph_javas) test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas)) # These tests do not rely on the stdlib test_alone := com.seaofnodes.simple.BrainFuckTest com.seaofnodes.simple.MergeSortTest com.seaofnodes.simple.TypeTest @@ -100,6 +104,9 @@ endif default: $(default_targets) +.PHONY: build +build: $(CLZDIR)/main/.mtag + ####################################################### # Compile Java as a whole source set. javac tracks Java dependencies # internally, so compiling only the directly out-of-date .java files can leave diff --git a/chapter25/pom.xml b/chapter25/pom.xml index 6a59188f..7a2b2b78 100644 --- a/chapter25/pom.xml +++ b/chapter25/pom.xml @@ -11,4 +11,7 @@ <artifactId>chapter23</artifactId> <packaging>jar</packaging> <name>Chapter 23</name> + <properties> + <simple.graph.directory>${project.basedir}/../graph</simple.graph.directory> + </properties> </project> diff --git a/chapter25/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter25/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java new file mode 100644 index 00000000..592abb5c --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -0,0 +1,74 @@ +package com.seaofnodes.simple.print; + +import com.seaofnodes.graph.GraphAdapter; +import com.seaofnodes.graph.GraphSnapshot; +import com.seaofnodes.graph.GraphSnapshot.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeMem; +import java.util.ArrayList; + +/** Chapter 25's view of the IR, including partially constructed parse-time graphs. */ +public class SimpleGraphAdapter extends GraphAdapter<Node> { + @Override protected int id(Node n) { return n._nid; } + @Override protected int nIns(Node n) { return n.nIns(); } + @Override protected Node in(Node n, int idx) { return n.in(idx); } + @Override protected int nOuts(Node n) { return n.nOuts(); } + @Override protected Node out(Node n, int idx) { return n.out(idx); } + + private ArrayList<Edge> edges(Node n) { + var edges = new ArrayList<Edge>(); + for( int i = 0; i < n.nIns(); i++ ) { + String name = n instanceof ScopeNode scope && i < scope._vars.size() + ? scope.var(i)._name : null; + edges.add(new Edge(i, ref(n.in(i)), role(n, i), name)); + } + return edges; + } + + @Override protected GraphSnapshot.Node desc(Node n) { + Projection proj = n instanceof Proj p + ? new Projection(n.nIns() == 0 ? 0 : ref(n.in(0)), p.idx()) : null; + String label = n.label(); + return new GraphSnapshot.Node(n._nid, label == null ? n.getClass().getSimpleName() : label, + n._type == null ? null : n._type.toString(), kind(n), edges(n), proj); + } + + private Kind kind(Node n) { + if( n instanceof ScopeNode ) return Kind.SCOPE; + if( n instanceof StartCUNode || n instanceof StopCUNode ) return Kind.UNIT; + if( n instanceof FunNode ) return Kind.FUN; + // Start inherits Loop for whole-program analysis, but is not a source loop. + if( n instanceof StartNode ) return Kind.CTRL; + if( n instanceof LoopNode ) return Kind.LOOP; + if( n instanceof RegionNode ) return Kind.REGION; + if( n instanceof PhiNode ) return Kind.PHI; + if( n instanceof CFGNode ) return Kind.CTRL; + return isMem(n) ? Kind.MEM : Kind.DATA; + } + + private Role role(Node n, int i) { + if( n instanceof ScopeNode || n instanceof ConstantNode || n instanceof FunPtrNode || + n instanceof CtrlNode || n instanceof XCtrlNode ) + return Role.ASSOC; + if( n instanceof PhiNode ) + return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA; + if( n instanceof Proj ) + return n instanceof CFGNode ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; + if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; + // Preserve known slot roles even when an input is not attached/typed yet. + if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; + if( n instanceof MemMergeNode || + i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode || n instanceof CallNode) || + n instanceof EscapeNode && i >= 2 ) return Role.MEM; + Node def = n.in(i); + if( def instanceof CFGNode ) return Role.CTRL; + if( def != null && isMem(def) ) return Role.MEM; + return Role.DATA; + } + + private boolean isMem(Node n) { + // These Phi subclasses are memory even before their first type computation. + return n instanceof MemPhiNode || n instanceof BulkMemPhiNode || n.isMem() || n._type instanceof TypeMem; + } +} diff --git a/graph/README.md b/graph/README.md index d428b2c7..caf18f70 100644 --- a/graph/README.md +++ b/graph/README.md @@ -48,8 +48,8 @@ for Firefox testing. Test logs/screenshots are written under `build/graph-browse Each chapter currently retains its Java graph exporter, compiler hooks, and WebSocket transport. The browser code has no dependency on a chapter's Java -classes. Moving the transport into a shared Java library is a separate step; -the frontend extraction does not add dependencies to the compiler builds. +classes. The adapters below share snapshot capture; moving the transport into +the shared Java code is a separate step. The legacy protocol is: @@ -65,15 +65,96 @@ The legacy protocol is: DOT frames may contain a `// POS:` comment identifying the parser position. The browser owns frame history and backward/forward playback. -The next layout implementation belongs here. Its chapter interface should use -versioned snapshots with stable IDs, node labels/roles, indexed inputs, edge -roles, and optional source/grouping metadata. Keep compiler-specific traversal -in chapter adapters, and layout, routing, animation, and interaction here. -Full snapshots are a useful first interface; deltas can follow if needed. +The next layout implementation belongs here. The compiler-side adapter below +is its first building block; the running viewer still consumes DOT. The linearization workflow includes this directory as a shared root resource. -The compiler remains self-contained in each chapter; the optional interactive -viewer additionally needs this directory from the same checkout. +Chapters 4 and 25 compile the shared Java sources from this directory; the +interactive viewer also loads the web assets from this checkout. + +## Chapter adapters + +The shared Java code is in `src/main/java/com/seaofnodes/graph/`: + +- `GraphAdapter<N>` is an abstract base with hooks for `id`, `desc`, and indexed + edge access (`nIns`/`in`, `nOuts`/`out`). Its final `snap` method walks definitions and + uses iteratively, handles cycles, and sorts the copied records by ID. +- `GraphSnapshot` is detached data: compilation key, step, roots, and nodes. + Each node has an ID, plain-text label/type, kind, edges to its defs, and optional + projection metadata. It contains no chapter classes or layout coordinates. + Node and edge lists are concrete `ArrayList`s, treated as read-only after capture. + +Root IDs use `int[]`. Capture uses a node table indexed by ID for visitation and +root deduplication; no boxed integer lists, sets or map keys are needed. +Indexed edge access reads each chapter's native storage without copying it into +a different collection type. + +Both chapters implement `com.seaofnodes.simple.print.SimpleGraphAdapter`, +extending `GraphAdapter<Node>`. No changes to `Node` or its subclasses are +needed. The chapter owns classification and extraction; the base owns traversal +and snapshot assembly. No new Java interface is involved. + +For chapter 4: + +```java +var parser = new Parser("return 1+arg+2;"); +var ret = parser.parse(); +var adapter = new SimpleGraphAdapter(); +var frame = adapter.snap("compile-1", 0, ret, parser._scope); +``` + +For chapter 25: + +```java +var code = new CodeGen("while(arg < 10) arg = arg + 1; return arg;").parse(); +var adapter = new SimpleGraphAdapter(); +var frame = adapter.snap("compile-1", 0, code._stop); +``` + +During a peephole, pass the current node and any unattached replacement as +additional roots. Null roots are ignored. Capture runs on the compiler thread +at a point where the graph is not changing; consumers can retain the returned +records after compilation resumes. The adapter does not compute types, invoke +peepholes, schedule nodes, or rearrange use lists. + +Node IDs are the chapter's `_nid`, scoped by the caller's compilation key. Use +a new key whenever a parser/compiler resets IDs. A snapshot rejects two distinct +nodes sharing one ID. Each edge belongs to its use node and names the referenced +`def` ID and the input slot `idx` on that use: `use.in(idx) == def`. The adapter +derives these edges from the compiler's `_inputs`; `_outputs` only speeds up +traversal. Repeated definitions produce distinct edges with different slot +indices. Each input slot has an `Edge` record, including holes with `def == 0`. +Edges remain in input-slot order under their use node. +Projection nodes retain their own IDs and identify their parent and tuple +index, allowing the renderer to fold them into ports later. A missing parent +has `par == 0`; real node IDs are never zero. + +Chapter 4 adds control/data roles and scope binding names. Chapter 25 adds +memory roles and node kinds for Phis, Regions, Loops, +Functions and compilation-unit boundaries. These are existing IR facts, not +computed region membership or a SESE hierarchy. Scope bindings and constant +lifetime edges are associations, so they need not constrain CFG layout. +Types may be absent on newly constructed nodes. Source locations, grouping, +observer events, serialization and delta encoding remain follow-up work. + +Make compiles these shared sources directly into each participating chapter's +classes using `javac`. From the repository root: + +```sh +make -C chapter04 build +make -C chapter25 build +``` + +`build` compiles the compiler and adapter without running tests or opening a +browser. Shared source changes trigger recompilation. No Maven executable, +Maven-built artifacts, generated source copies or separately installed graph +JARs are needed. Existing `make tests`, `make release` and chapter 25's +`make view` also include the shared sources through their normal prerequisites. + +For the existing Maven/CI build path, `build-helper:add-source` describes the +same source directory. The two chapter POMs select `../graph`, while the root +POM defaults to `graph` for linearized checkouts. These entries are independent +of the Make build. ## Peephole hook investigation diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java b/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java new file mode 100644 index 00000000..77672c45 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java @@ -0,0 +1,67 @@ +package com.seaofnodes.graph; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Comparator; + +/** + * Subclass once per chapter. Only the subclass knows that chapter's IR. + * Capture on the compiler thread, while the graph is not being modified. + * Hooks must only read the IR: no computing types, peepholes or scheduling. + */ +public abstract class GraphAdapter<N> { + protected abstract int id(N node); + protected abstract int nIns(N node); + protected abstract N in(N node, int idx); + protected abstract int nOuts(N node); + protected abstract N out(N node, int idx); + protected abstract GraphSnapshot.Node desc(N node); + + protected final int ref(N node) { return node == null ? 0 : id(node); } + + /** + * Follow both definitions and uses from the roots, including cycles. + * Supply current/replacement nodes as extra roots while a peep is in flight; + * they need not be attached to the program yet. Null roots/uses are ignored. + * The caller supplies a new compilation key whenever node IDs reset. + */ + @SafeVarargs + public final GraphSnapshot snap(String comp, long step, N... roots) { + // Node IDs are dense; index directly without boxed keys or map entries. + var seen = new ArrayList<N>(); + var todo = new ArrayDeque<N>(); + var rids = new int[roots.length]; + int len = 0; + for( N root : roots ) + if( enq(root, seen, todo) ) rids[len++] = id(root); + var nodes = new ArrayList<GraphSnapshot.Node>(); + while( !todo.isEmpty() ) { + N node = todo.removeFirst(); + nodes.add(desc(node)); + for( int i = 0; i < nIns(node); i++ ) enq(in(node, i), seen, todo); + // Uses are a traversal shortcut, never the source of edge semantics. + for( int i = 0; i < nOuts(node); i++ ) enq(out(node, i), seen, todo); + } + // Determinism without reordering the compiler's use lists. + nodes.sort(Comparator.comparingInt(GraphSnapshot.Node::id)); + return new GraphSnapshot(GraphSnapshot.VER, comp, step, + Arrays.copyOf(rids, len), nodes); + } + + private boolean enq(N node, ArrayList<N> seen, ArrayDeque<N> todo) { + if( node == null ) return false; + int nid = id(node); + while( seen.size() <= nid ) seen.add(null); + N old = seen.get(nid); + if( old == null ) { + seen.set(nid, node); + todo.addLast(node); + return true; + } + if( old != node ) + throw new IllegalArgumentException("Different nodes share ID " + nid + + "; mixed compilations?"); + return false; + } +} diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java new file mode 100644 index 00000000..18926726 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java @@ -0,0 +1,38 @@ +package com.seaofnodes.graph; + +import java.util.ArrayList; + +/** A detached graph. Treat its lists as read-only after capture. */ +public record GraphSnapshot(int ver, String comp, long step, + int[] roots, ArrayList<Node> nodes) { + public static final int VER = 1; + + public GraphSnapshot { + roots = roots.clone(); + nodes = new ArrayList<>(nodes); + } + + @Override public int[] roots() { return roots.clone(); } + + public enum Kind { DATA, CTRL, MEM, SCOPE, PHI, REGION, LOOP, FUN, UNIT } + public enum Role { DATA, CTRL, MEM, ASSOC } + + /** IDs are stable within one compilation. Labels and types are plain text. */ + public record Node(int id, String label, String type, Kind kind, + ArrayList<Edge> edges, Projection proj) { + public Node { + edges = new ArrayList<>(edges); + } + } + + /** + * The containing Node is the use; def is the referenced node ID. + * idx is the input slot on that use: use.in(idx) == def. + * Each slot has a record, including holes (def == 0). + * label is an optional binding name, not markup. + */ + public record Edge(int idx, int def, Role role, String label) { } + + /** Projections remain real nodes; par == 0 means no parent is attached. */ + public record Projection(int par, int idx) { } +} @@ -50,6 +50,8 @@ <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> <maven.compiler.source>21</maven.compiler.source> <maven.compiler.target>21</maven.compiler.target> + <!-- Also works at the root of a linearized chapter checkout. --> + <simple.graph.directory>${project.basedir}/graph</simple.graph.directory> </properties> <dependencies> @@ -64,6 +66,21 @@ <build> <plugins> <plugin> + <groupId>org.codehaus.mojo</groupId> + <artifactId>build-helper-maven-plugin</artifactId> + <version>3.4.0</version> + <executions> + <execution> + <id>shared-graph-sources</id> + <phase>generate-sources</phase> + <goals><goal>add-source</goal></goals> + <configuration> + <sources><source>${simple.graph.directory}/src/main/java</source></sources> + </configuration> + </execution> + </executions> + </plugin> + <plugin> <groupId>org.apache.maven.plugins</groupId> <artifactId>maven-surefire-plugin</artifactId> <version>3.1.2</version> |