From 10ed01188f78e3fad4b257a0241f9a89e2fdb405 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sun, 22 Oct 2023 05:18:58 +0100 Subject: Revision of docs (#10) * Port updates back to chapter 2 * Update older visuals to match new format * Update older visuals to match new format * update docs --- chapter01/README.md | 59 +++- chapter01/docs/01-graph.gv | 20 +- chapter01/docs/01-graph.svg | 64 +++-- chapter01/docs/01-use-def.gv | 7 + chapter01/docs/01-use-def.svg | 35 +++ chapter02/README.md | 12 +- chapter02/docs/02-post-peephole-ex1.gv | 19 +- chapter02/docs/02-post-peephole-ex1.svg | 92 +++---- chapter02/docs/02-pre-peephole-ex1.gv | 53 ++-- chapter02/docs/02-pre-peephole-ex1.svg | 299 ++++++++++----------- .../com/seaofnodes/simple/GraphVisualizer.java | 107 ++++---- .../java/com/seaofnodes/simple/Chapter02Test.java | 6 +- chapter04/README.md | 8 +- 13 files changed, 443 insertions(+), 338 deletions(-) create mode 100644 chapter01/docs/01-use-def.gv create mode 100644 chapter01/docs/01-use-def.svg diff --git a/chapter01/README.md b/chapter01/README.md index 57caa801..e09b61a3 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -29,8 +29,7 @@ We design our parser and compiler to illustrate some key aspects of the Sea of N Intermediate Representation: * We construct the intermediate Sea of Nodes representation directly as we parse the language. There is no Abstract Syntax Tree representation. - -* The compiler will perform a few basic local optimizations as we build the IR; this is a key benefit of the Sea of Nodes IR. This aspect is more fully explored from Chapter 2 onwards. +* The compiler will perform a few basic local optimizations as we build the IR; this is a key benefit of the Sea of Nodes IR. This aspect is more fully explored from [Chapter 2](../chapter02/README.md) onwards. ## Data Structures @@ -50,7 +49,57 @@ The intermediate representation is a graph of Node objects. The `Node` class is The `Node` class provides common capabilities that are inherited by all subtypes. Each subtype implements semantics relevant to that subtype. -There are two types of Nodes in the representation. +Each `Node` represents an "instruction" as it may appear in traditional IRs. + +### Nodes are in a Graph + +The key idea of the Sea of Nodes IR is that each Node is linked to other Nodes by def-use dependencies. +As this is such an important and fundamental aspect of the IR, it is important to understand how we implement this, and depict in graph visuals. + +The base `Node` class maintains a list of Nodes that are inputs to it. An input is an edge from a "def" to a "use". What this means is that if `B` is definition, and `A` uses `B`, +then there is a def-use edge from `B` to `A`. + +Visually we show an arrow from the "use" to the "def". Here is an example: + +![Use Def](./docs/01-use-def.svg) + +From an implementation point of view, our `Node` type also maintains a reverse link. +This means that in the above scenario: + +* Since `A` is a "use" of `B`, then `B` will appear in `A`'s list of inputs. +* Conversely, `B` maintains a list of outputs, and `A` will appear in this list. +* A key invariant is that these edges must be in sync at all times. + +Here is how this looks in the `Node` class: + +```java +public abstract class Node { + + /** + * Inputs to the node. These are use-def references to Nodes. + *

+ * Generally fixed length, ordered, nulls allowed, no unused trailing space. + * Ordering is required because e.g. "a/b" is different from "b/a". + * The first input (offset 0) is often a Control node. + */ + public final ArrayList _inputs; + + /** + * Outputs reference Nodes that are not null and have this Node as an + * input. These nodes are users of this node, thus these are def-use + * references to Nodes. + *

+ * Outputs directly match inputs, making a directed graph that can be + * walked in either direction. These outputs are typically used for + * efficient optimizations but otherwise have no semantics meaning. + */ + public final ArrayList _outputs; +} +``` + +### Types of Nodes + +There are two categories of Nodes in the intermediate representation. * **Control Nodes** - these represent the control flow subgraph (CFG) of the compiled program * **Data Nodes** - these capture the data semantics @@ -80,7 +129,7 @@ graph. We discuss Node equality in Chapter 8 Global Value Numbering. The Start node represents the start of the function. For now, we do not have any inputs to Start because our function does not yet accept parameters. When we add parameters the value of Start will be a tuple, and will require Projections to extract the values. -We discuss this in detail in Chapter 9: Functions and Calls. +We discuss this in detail in [Chapter 4](../chapter04/README.md). ### Constant Node @@ -101,7 +150,7 @@ The Return node has two inputs. The first input is a control node and the second is the data node that supplies the return value. In this presentation, Return functions as a Stop node, since multiple `return` statements are not possible. -The Stop node will be introduced in Chapter 6 when we implement `if` statements. +The Stop node will be introduced in Chapter 5 when we implement `if` statements. The Return's output is the value from the data node. diff --git a/chapter01/docs/01-graph.gv b/chapter01/docs/01-graph.gv index 40181544..82d1b40a 100644 --- a/chapter01/docs/01-graph.gv +++ b/chapter01/docs/01-graph.gv @@ -1,9 +1,11 @@ -digraph chapter01 -{ - start [shape=box, label="Start"]; - constant [label="Constant 1"]; - return [shape=box, label="Return"]; - constant -> return; - edge [color=red]; - start -> return [style=bold]; -} \ No newline at end of file +digraph chapter01 { + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con12 [ label="Con1" ]; + Return3 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + Con12 -> Start1 [style=dotted]; + Return3 -> Start1 [color=red]; + Return3 -> Con12; +} diff --git a/chapter01/docs/01-graph.svg b/chapter01/docs/01-graph.svg index fbf92d7d..8e478f4d 100644 --- a/chapter01/docs/01-graph.svg +++ b/chapter01/docs/01-graph.svg @@ -4,40 +4,50 @@ - - + + chapter01 - - + + +cluster_Nodes + + + -start - -Start +Start1 + +Start + + + +Con12 + +Con1 + + + +Con12->Start1 + + - + -return - -Return +Return3 + +Return - + -start->return - - - - - -constant - -Constant 1 +Return3->Start1 + + - - -constant->return - - + + +Return3->Con12 + + diff --git a/chapter01/docs/01-use-def.gv b/chapter01/docs/01-use-def.gv new file mode 100644 index 00000000..d0e84ecb --- /dev/null +++ b/chapter01/docs/01-use-def.gv @@ -0,0 +1,7 @@ +digraph chapter01 { + rankdir=BT; + subgraph cluster_Nodes { + A, B; + } + A -> B; +} diff --git a/chapter01/docs/01-use-def.svg b/chapter01/docs/01-use-def.svg new file mode 100644 index 00000000..644ab5a2 --- /dev/null +++ b/chapter01/docs/01-use-def.svg @@ -0,0 +1,35 @@ + + + + + + +chapter01 + + +cluster_Nodes + + + + +A + +A + + + +B + +B + + + +A->B + + + + + diff --git a/chapter02/README.md b/chapter02/README.md index 5b4c4958..b89a3059 100644 --- a/chapter02/README.md +++ b/chapter02/README.md @@ -11,7 +11,7 @@ Here is the [complete language grammar](docs/02-grammar.md) for this chapter. ## Extensions to Intermediate Representation -In chapter 1 we introduced following nodes. +In [Chapter 1](../chapter01/README.md) we introduced following nodes. | Node Name | Type | Description | Inputs | Value | |-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| @@ -53,10 +53,10 @@ may *kill* the unused constants `1` and `2`. ## Constant Folding and Constant Propagation In this chapter and next we focus on a particular peephole optimization: -constant folding and constant propagation. Since we do not have variables -until Chapter 3, the main feature we demonstrate now is constant folding. +constant folding and constant propagation. Since we do not have non-constant values +until [Chapter 4](../chapter04/README.md), the main feature we demonstrate now is constant folding. However, we introduce some additional ideas into the compiler at this stage, to -set the scene for Chapter 3. +set the scene for Chapter 4. It is useful for the compiler to know at various points of the program whether a node's value is a constant. The compiler can use this knowledge to perform various @@ -107,8 +107,8 @@ some constant to ⊥. In later chapters we will explore extending this lattice, as it frequently forms the heart of core optimizations we want our compiler to do. -There are other important properties of the Lattice that we discuss in Chapter -3, such as the "meet" operator and its rules. +There are other important properties of the Lattice that we discuss in [Chapter +4](../chapter04/README.md), such as the "meet" operator and its rules. ## Nodes Pre Peephole Optimization diff --git a/chapter02/docs/02-post-peephole-ex1.gv b/chapter02/docs/02-post-peephole-ex1.gv index a39d602b..290a1178 100644 --- a/chapter02/docs/02-post-peephole-ex1.gv +++ b/chapter02/docs/02-post-peephole-ex1.gv @@ -1,10 +1,11 @@ -digraph chapter02 -{ - Start1 [shape=box, label="Start"]; - Con213 [ label="Con2"]; - Start1 -> Con213 [style=dotted]; - Return14 [shape=box, label="Return"]; - Con213 -> Return14; - edge [color=red]; - Start1 -> Return14; +digraph chapter02 { + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con213 [ label="Con2" ]; + Return14 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + Con213 -> Start1 [style=dotted]; + Return14 -> Start1 [color=red]; + Return14 -> Con213; } \ No newline at end of file diff --git a/chapter02/docs/02-post-peephole-ex1.svg b/chapter02/docs/02-post-peephole-ex1.svg index 33aa5a95..b3c42c7d 100644 --- a/chapter02/docs/02-post-peephole-ex1.svg +++ b/chapter02/docs/02-post-peephole-ex1.svg @@ -1,51 +1,53 @@ + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> - - - chapter02 - - - - Start1 - - Start - - - - Con213 - - Con2 - - - - Start1->Con213 - - - - - - Return14 - - Return - - - - Start1->Return14 - - - - - - Con213->Return14 - - - - + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con213 + +Con2 + + + +Con213->Start1 + + + + + +Return14 + +Return + + + +Return14->Start1 + + + + + +Return14->Con213 + + + + diff --git a/chapter02/docs/02-pre-peephole-ex1.gv b/chapter02/docs/02-pre-peephole-ex1.gv index d5a16616..c2eab457 100644 --- a/chapter02/docs/02-pre-peephole-ex1.gv +++ b/chapter02/docs/02-pre-peephole-ex1.gv @@ -1,27 +1,28 @@ -digraph chapter02 -{ - Start1 [shape=box, label="Start"]; - Con12 [ label="Con1"]; - Start1 -> Con12 [style=dotted]; - Con23 [ label="Con2"]; - Start1 -> Con23 [style=dotted]; - Con34 [ label="Con3"]; - Start1 -> Con34 [style=dotted]; - Mul5 [ label="Mul"]; - Con23 -> Mul5; - Con34 -> Mul5; - Con56 [ label="Con5"]; - Start1 -> Con56 [style=dotted]; - Minus7 [ label="Minus"]; - Con56 -> Minus7; - Add8 [ label="Add"]; - Mul5 -> Add8; - Minus7 -> Add8; - Add9 [ label="Add"]; - Con12 -> Add9; - Add8 -> Add9; - Return10 [shape=box, label="Return"]; - Add9 -> Return10; - edge [color=red]; - Start1 -> Return10; +digraph chapter02 { + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con12 [ label="Con1" ]; + Con23 [ label="Con2" ]; + Con34 [ label="Con3" ]; + Mul5 [ label="Mul" ]; + Con56 [ label="Con5" ]; + Minus7 [ label="Minus" ]; + Add8 [ label="Add" ]; + Add9 [ label="Add" ]; + Return10 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + Con12 -> Start1 [style=dotted]; + Con23 -> Start1 [style=dotted]; + Con34 -> Start1 [style=dotted]; + Mul5 -> Con23; + Mul5 -> Con34; + Con56 -> Start1 [style=dotted]; + Minus7 -> Con56; + Add8 -> Mul5; + Add8 -> Minus7; + Add9 -> Con12; + Add9 -> Add8; + Return10 -> Start1 [color=red]; + Return10 -> Add9; } \ No newline at end of file diff --git a/chapter02/docs/02-pre-peephole-ex1.svg b/chapter02/docs/02-pre-peephole-ex1.svg index dc33c7f5..8a1ef457 100644 --- a/chapter02/docs/02-pre-peephole-ex1.svg +++ b/chapter02/docs/02-pre-peephole-ex1.svg @@ -1,156 +1,155 @@ + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> - - - chapter02 - - - - Start1 - - Start - - - - Con12 - - Con1 - - - - Start1->Con12 - - - - - - Con23 - - Con2 - - - - Start1->Con23 - - - - - - Con34 - - Con3 - - - - Start1->Con34 - - - - - - Con56 - - Con5 - - - - Start1->Con56 - - - - - - Return10 - - Return - - - - Start1->Return10 - - - - - - Add9 - - Add - - - - Con12->Add9 - - - - - - Mul5 - - Mul - - - - Con23->Mul5 - - - - - - Con34->Mul5 - - - - - - Add8 - - Add - - - - Mul5->Add8 - - - - - - Minus7 - - Minus - - - - Con56->Minus7 - - - - - - Minus7->Add8 - - - - - - Add8->Add9 - - - - - - Add9->Return10 - - - - + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con12 + +Con1 + + + +Con12->Start1 + + + + + +Con23 + +Con2 + + + +Con23->Start1 + + + + + +Con34 + +Con3 + + + +Con34->Start1 + + + + + +Mul5 + +Mul + + + +Mul5->Con23 + + + + + +Mul5->Con34 + + + + + +Con56 + +Con5 + + + +Con56->Start1 + + + + + +Minus7 + +Minus + + + +Minus7->Con56 + + + + + +Add8 + +Add + + + +Add8->Mul5 + + + + + +Add8->Minus7 + + + + + +Add9 + +Add + + + +Add9->Con12 + + + + + +Add9->Add8 + + + + + +Return10 + +Return + + + +Return10->Start1 + + + + + +Return10->Add9 + + + + diff --git a/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index d2aa8179..1af19d80 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -5,9 +5,7 @@ import com.seaofnodes.simple.node.Control; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StartNode; -import java.util.Collection; -import java.util.HashMap; -import java.util.Map; +import java.util.*; /** * Simple visualizer that outputs GraphViz dot format. @@ -16,59 +14,59 @@ import java.util.Map; */ public class GraphVisualizer { - public String generateDotOutput(StartNode start) { + public String generateDotOutput(Parser parser) { + // Since the graph has cycles, we need to create a flat list of all the // nodes in the graph. - Collection all = findAll(start); + Collection all = findAll(parser); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter02\n" + - "{\n"); + sb.append("digraph chapter02 {\n"); + + // To keep the Scopes below the graph and pointing up into the graph we + // need to group the Nodes in a subgraph cluster, and the scopes into a + // different subgraph cluster. THEN we can draw edges between the + // scopes and nodes. If we try to cross subgraph cluster borders while + // still making the subgraphs DOT gets confused. + sb.append("\trankdir=BT;\n"); // Force Nodes before Scopes + + // Just the Nodes first, in a cluster no edges + nodes(sb, all); + + // Walk the Node edges + nodeEdges(sb, all); + + sb.append("}\n"); + return sb.toString(); + } + + + private void nodes(StringBuilder sb, Collection all) { + // Just the Nodes first, in a cluster no edges + sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name for (Node n : all) { - sb.append('\t').append(n.uniqueName()); + sb.append("\t\t").append(n.uniqueName()).append(" [ "); // control nodes have box shape // other nodes are ellipses, i.e. default shape if (n instanceof Control) - sb.append(" [shape=box, "); - else - sb.append(" ["); - sb.append(" label=\"") - .append(n.label()) - .append("\"];\n"); - // Output the non control edges - walkIns(sb, n, false); + sb.append("shape=box style=filled fillcolor=yellow "); + sb.append("label=\"").append(n.label()).append("\" "); + sb.append("];\n"); } - // Now output the control edges which must be in red - sb.append("\tedge [color=red];\n"); - for (Node n : all) { - walkIns(sb, n, true); - } - sb.append("}\n"); - return sb.toString(); + sb.append("\t}\n"); // End Node cluster } - /** - * Outputs edges. If doControlEdges is true then - * edges between control nodes are output. Else other edges - * output. - */ - private void walkIns(StringBuilder sb, Node in, boolean doControlEdges) { - for (int i = 0; i < in.nIns(); i++) { - Node out = in.in(i); - if (out == null) - continue; - boolean isControlEdge = (out instanceof Control) && (in instanceof Control); - if (doControlEdges && !isControlEdge) - continue; - if (!doControlEdges && isControlEdge) - continue; - sb.append('\t') - .append(out.uniqueName()) - .append(" -> ") - .append(in.uniqueName()); - // the edge from start node to constants is just for convenience so - // show it differently - if ((out instanceof StartNode) && (in instanceof ConstantNode)) + + // Walk the node edges + private void nodeEdges(StringBuilder sb, Collection all) { + for( Node n : all ) + for( Node out : n._inputs ) + if( out != null ) { + sb.append('\t').append(n.uniqueName()).append(" -> ").append(out.uniqueName()); + // Control edges are colored red + if( n instanceof ConstantNode && out instanceof StartNode ) sb.append(" [style=dotted]"); + else if( n instanceof Control && out instanceof Control ) + sb.append(" [color=red]"); sb.append(";\n"); } } @@ -77,26 +75,25 @@ public class GraphVisualizer { * Walks the whole graph, starting from Start. * Since Start is the input to all constants - we look at the outputs for * Start, but for then subsequently we look at the inputs of each node. + * During graph construction not all nodes are reachable this way, so we + * also scan the symbol tables. */ - private Collection findAll(StartNode start) { - Map all = new HashMap<>(); - for (int i = 0; i < start.nOuts(); i++) { - Node n = start.out(i); + private Collection findAll(Parser parser) { + final StartNode start = Parser.START; + final HashMap all = new HashMap<>(); + for( Node n : start._outputs ) walk(all, n); - } return all.values(); } /** - * Walk a subgraph and populate distinct nodes in the _all list. + * Walk a subgraph and populate distinct nodes in the all list. */ - private void walk(Map all, Node n) { - if (all.get(n._nid) == null) { - // Not yet seen + private void walk(HashMap all, Node n) { + if (all.get(n._nid) != null) return; // Been there, done that all.put(n._nid, n); for (Node c : n._inputs) if (c != null) walk(all, c); - } } } diff --git a/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 846aff58..83cd7a0f 100644 --- a/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -24,7 +24,7 @@ public class Chapter02Test { ReturnNode ret = parser.parse(); assertEquals("return (1+((2*3)+(-5)));", ret.print()); GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(Parser.START)); + System.out.println(gv.generateDotOutput(parser)); Node._disablePeephole = false; } @@ -69,13 +69,15 @@ public class Chapter02Test { ReturnNode ret = parser.parse(); assertEquals("return 2;", ret.print()); GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(Parser.START)); + System.out.println(gv.generateDotOutput(parser)); } @Test public void testSimpleProgram() { Parser parser = new Parser("return 1;"); ReturnNode ret = parser.parse(); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); StartNode start = Parser.START; assertEquals(start, ret.ctrl()); diff --git a/chapter04/README.md b/chapter04/README.md index da8781d4..03bfe58b 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -22,7 +22,7 @@ Following are revised or new nodes | Proj | ? | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | | Bool | Data | Represents results of a comparison operator | Two data nodes | Result a comparison, represented as integer value where 1=true, 0=false | -Below is our list of Nodes from chapter 3: +Below is our list of Nodes from [Chapter 3](../chapter03/README.md): | Node Name | Type | Description | Inputs | Value | |------------|---------|------------------------------------|------------------------------------------------------------------|------------------------------| @@ -36,7 +36,7 @@ Below is our list of Nodes from chapter 3: ## Changes to Type System -In Chapter 2 we introduced the Type System. Here is a summary of key points: +In [Chapter 2](../chapter02/README.md) we introduced the Type System. Here is a summary of key points: We annotate Nodes with Types. @@ -58,7 +58,7 @@ Type +-- TypeTuple (New - represents multi-valued result) ``` -We mentioned in Chapter 2 that the set of values associated with a Type at a specific Node +We mentioned in [Chapter 2](../chapter02/README.md) that the set of values associated with a Type at a specific Node can be conveniently represented as a "lattice". Our lattice elements can be one of three types: @@ -151,7 +151,7 @@ The peephole optimizations introduced in this chapter are local. They are trigge as new nodes are created, before the newly created node has any uses. For example, when we parse a unary expression, and create a Node for the parsed expression, -`peephole()` is invoked on the newky created `MinusNode`: +`peephole()` is invoked on the newly created `MinusNode`: ```java private Node parseUnary() { -- cgit v1.2.3