diff options
| author | Dibyendu Majumdar <dibyendumajumdar@users.noreply.github.com> | 2023-10-22 05:18:58 +0100 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-10-21 21:18:58 -0700 |
| commit | 10ed01188f78e3fad4b257a0241f9a89e2fdb405 (patch) | |
| tree | bcf72f66bf0db33cced9b48e2401428706b8eebe | |
| parent | d1c5e6995f5e08df18069be49b1fe0ea193996a9 (diff) | |
| download | Simple-10ed01188f78e3fad4b257a0241f9a89e2fdb405.tar.gz Simple-10ed01188f78e3fad4b257a0241f9a89e2fdb405.zip | |
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
| -rw-r--r-- | chapter01/README.md | 59 | ||||
| -rw-r--r-- | chapter01/docs/01-graph.gv | 20 | ||||
| -rw-r--r-- | chapter01/docs/01-graph.svg | 64 | ||||
| -rw-r--r-- | chapter01/docs/01-use-def.gv | 7 | ||||
| -rw-r--r-- | chapter01/docs/01-use-def.svg | 35 | ||||
| -rw-r--r-- | chapter02/README.md | 12 | ||||
| -rw-r--r-- | chapter02/docs/02-post-peephole-ex1.gv | 19 | ||||
| -rw-r--r-- | chapter02/docs/02-post-peephole-ex1.svg | 92 | ||||
| -rw-r--r-- | chapter02/docs/02-pre-peephole-ex1.gv | 53 | ||||
| -rw-r--r-- | chapter02/docs/02-pre-peephole-ex1.svg | 299 | ||||
| -rw-r--r-- | chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java | 107 | ||||
| -rw-r--r-- | chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java | 6 | ||||
| -rw-r--r-- | chapter04/README.md | 8 |
13 files changed, 443 insertions, 338 deletions
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: + + + +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. + * <p> + * 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<Node> _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. + * <p> + * 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<Node> _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 @@ <!-- Generated by graphviz version 2.43.0 (0) --> <!-- Title: chapter01 Pages: 1 --> -<svg width="204pt" height="116pt" - viewBox="0.00 0.00 203.74 116.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> -<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 112)"> +<svg width="128pt" height="220pt" + viewBox="0.00 0.00 128.00 220.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 216)"> <title>chapter01</title> -<polygon fill="white" stroke="transparent" points="-4,4 -4,-112 199.74,-112 199.74,4 -4,4"/> -<!-- start --> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-216 124,-216 124,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-204 112,-204 112,-8 8,-8"/> +</g> +<!-- Start1 --> <g id="node1" class="node"> -<title>start</title> -<polygon fill="none" stroke="black" points="54,-108 0,-108 0,-72 54,-72 54,-108"/> -<text text-anchor="middle" x="27" y="-86.3" font-family="Times,serif" font-size="14.00">Start</text> +<title>Start1</title> +<polygon fill="yellow" stroke="black" points="83,-196 29,-196 29,-160 83,-160 83,-196"/> +<text text-anchor="middle" x="56" y="-174.3" font-family="Times,serif" font-size="14.00">Start</text> +</g> +<!-- Con12 --> +<g id="node2" class="node"> +<title>Con12</title> +<ellipse fill="none" stroke="black" cx="70" cy="-106" rx="34.39" ry="18"/> +<text text-anchor="middle" x="70" y="-102.3" font-family="Times,serif" font-size="14.00">Con1</text> +</g> +<!-- Con12->Start1 --> +<g id="edge1" class="edge"> +<title>Con12->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M66.61,-123.95C65.07,-131.65 63.21,-140.97 61.47,-149.64"/> +<polygon fill="black" stroke="black" points="57.98,-149.23 59.46,-159.72 64.85,-150.61 57.98,-149.23"/> </g> -<!-- return --> +<!-- Return3 --> <g id="node3" class="node"> -<title>return</title> -<polygon fill="none" stroke="black" points="113,-36 47,-36 47,0 113,0 113,-36"/> -<text text-anchor="middle" x="80" y="-14.3" font-family="Times,serif" font-size="14.00">Return</text> +<title>Return3</title> +<polygon fill="yellow" stroke="black" points="92,-52 26,-52 26,-16 92,-16 92,-52"/> +<text text-anchor="middle" x="59" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> </g> -<!-- start->return --> +<!-- Return3->Start1 --> <g id="edge2" class="edge"> -<title>start->return</title> -<path fill="none" stroke="red" stroke-width="2" d="M40.1,-71.7C46.39,-63.39 54.05,-53.28 60.96,-44.14"/> -<polygon fill="red" stroke="red" stroke-width="2" points="63.8,-46.19 67.05,-36.1 58.22,-41.96 63.8,-46.19"/> -</g> -<!-- constant --> -<g id="node2" class="node"> -<title>constant</title> -<ellipse fill="none" stroke="black" cx="134" cy="-90" rx="61.99" ry="18"/> -<text text-anchor="middle" x="134" y="-86.3" font-family="Times,serif" font-size="14.00">Constant 1</text> +<title>Return3->Start1</title> +<path fill="none" stroke="red" d="M45.44,-52.03C38.44,-61.91 30.63,-74.95 27,-88 22.71,-103.41 23.04,-108.5 27,-124 29.38,-133.3 33.76,-142.73 38.42,-151"/> +<polygon fill="red" stroke="red" points="35.54,-153.01 43.69,-159.78 41.54,-149.41 35.54,-153.01"/> </g> -<!-- constant->return --> -<g id="edge1" class="edge"> -<title>constant->return</title> -<path fill="none" stroke="black" d="M120.93,-72.05C114.52,-63.75 106.68,-53.58 99.58,-44.38"/> -<polygon fill="black" stroke="black" points="102.21,-42.06 93.33,-36.28 96.66,-46.33 102.21,-42.06"/> +<!-- Return3->Con12 --> +<g id="edge3" class="edge"> +<title>Return3->Con12</title> +<path fill="none" stroke="black" d="M61.72,-52.3C62.93,-60.02 64.39,-69.29 65.74,-77.89"/> +<polygon fill="black" stroke="black" points="62.3,-78.56 67.31,-87.9 69.22,-77.47 62.3,-78.56"/> </g> </g> </svg> 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 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter01 Pages: 1 --> +<svg width="94pt" height="148pt" + viewBox="0.00 0.00 94.00 148.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 144)"> +<title>chapter01</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-144 90,-144 90,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-132 78,-132 78,-8 8,-8"/> +</g> +<!-- A --> +<g id="node1" class="node"> +<title>A</title> +<ellipse fill="none" stroke="black" cx="43" cy="-34" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-30.3" font-family="Times,serif" font-size="14.00">A</text> +</g> +<!-- B --> +<g id="node2" class="node"> +<title>B</title> +<ellipse fill="none" stroke="black" cx="43" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-102.3" font-family="Times,serif" font-size="14.00">B</text> +</g> +<!-- A->B --> +<g id="edge1" class="edge"> +<title>A->B</title> +<path fill="none" stroke="black" d="M43,-52.3C43,-60.02 43,-69.29 43,-77.89"/> +<polygon fill="black" stroke="black" points="39.5,-77.9 43,-87.9 46.5,-77.9 39.5,-77.9"/> +</g> +</g> +</svg> 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 @@ <?xml version="1.0" encoding="UTF-8" standalone="no"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" - "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> <!-- Generated by graphviz version 2.43.0 (0) --> <!-- Title: chapter02 Pages: 1 --> -<svg width="106pt" height="188pt" - viewBox="0.00 0.00 106.45 188.00" xmlns="http://www.w3.org/2000/svg"> - <g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 184)"> - <title>chapter02</title> - <polygon fill="white" stroke="transparent" points="-4,4 -4,-184 102.45,-184 102.45,4 -4,4"/> - <!-- Start1 --> - <g id="node1" class="node"> - <title>Start1</title> - <polygon fill="none" stroke="black" points="92.45,-180 38.45,-180 38.45,-144 92.45,-144 92.45,-180"/> - <text text-anchor="middle" x="65.45" y="-158.3" font-family="Times,serif" font-size="14.00">Start</text> - </g> - <!-- Con213 --> - <g id="node2" class="node"> - <title>Con213</title> - <ellipse fill="none" stroke="black" cx="34.45" cy="-90" rx="34.39" ry="18"/> - <text text-anchor="middle" x="34.45" y="-86.3" font-family="Times,serif" font-size="14.00">Con2</text> - </g> - <!-- Start1->Con213 --> - <g id="edge1" class="edge"> - <title>Start1->Con213</title> - <path fill="none" stroke="black" stroke-dasharray="1,5" - d="M57.78,-143.7C54.2,-135.61 49.86,-125.81 45.9,-116.87"/> - <polygon fill="black" stroke="black" points="49.06,-115.35 41.81,-107.62 42.66,-118.18 49.06,-115.35"/> - </g> - <!-- Return14 --> - <g id="node3" class="node"> - <title>Return14</title> - <polygon fill="none" stroke="black" points="98.45,-36 32.45,-36 32.45,0 98.45,0 98.45,-36"/> - <text text-anchor="middle" x="65.45" y="-14.3" font-family="Times,serif" font-size="14.00">Return</text> - </g> - <!-- Start1->Return14 --> - <g id="edge3" class="edge"> - <title>Start1->Return14</title> - <path fill="none" stroke="red" - d="M70.32,-143.98C73.01,-133.67 76.08,-120.19 77.45,-108 79.22,-92.1 79.22,-87.9 77.45,-72 76.49,-63.43 74.69,-54.22 72.76,-45.93"/> - <polygon fill="red" stroke="red" points="76.11,-44.89 70.32,-36.02 69.32,-46.57 76.11,-44.89"/> - </g> - <!-- Con213->Return14 --> - <g id="edge2" class="edge"> - <title>Con213->Return14</title> - <path fill="none" stroke="black" d="M41.79,-72.41C45.32,-64.45 49.63,-54.72 53.6,-45.76"/> - <polygon fill="black" stroke="black" points="56.87,-47.01 57.72,-36.45 50.47,-44.17 56.87,-47.01"/> - </g> - </g> +<svg width="128pt" height="220pt" + viewBox="0.00 0.00 128.00 220.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 216)"> +<title>chapter02</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-216 124,-216 124,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-204 112,-204 112,-8 8,-8"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="yellow" stroke="black" points="83,-196 29,-196 29,-160 83,-160 83,-196"/> +<text text-anchor="middle" x="56" y="-174.3" font-family="Times,serif" font-size="14.00">Start</text> +</g> +<!-- Con213 --> +<g id="node2" class="node"> +<title>Con213</title> +<ellipse fill="none" stroke="black" cx="70" cy="-106" rx="34.39" ry="18"/> +<text text-anchor="middle" x="70" y="-102.3" font-family="Times,serif" font-size="14.00">Con2</text> +</g> +<!-- Con213->Start1 --> +<g id="edge1" class="edge"> +<title>Con213->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M66.61,-123.95C65.07,-131.65 63.21,-140.97 61.47,-149.64"/> +<polygon fill="black" stroke="black" points="57.98,-149.23 59.46,-159.72 64.85,-150.61 57.98,-149.23"/> +</g> +<!-- Return14 --> +<g id="node3" class="node"> +<title>Return14</title> +<polygon fill="yellow" stroke="black" points="92,-52 26,-52 26,-16 92,-16 92,-52"/> +<text text-anchor="middle" x="59" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Return14->Start1 --> +<g id="edge2" class="edge"> +<title>Return14->Start1</title> +<path fill="none" stroke="red" d="M45.44,-52.03C38.44,-61.91 30.63,-74.95 27,-88 22.71,-103.41 23.04,-108.5 27,-124 29.38,-133.3 33.76,-142.73 38.42,-151"/> +<polygon fill="red" stroke="red" points="35.54,-153.01 43.69,-159.78 41.54,-149.41 35.54,-153.01"/> +</g> +<!-- Return14->Con213 --> +<g id="edge3" class="edge"> +<title>Return14->Con213</title> +<path fill="none" stroke="black" d="M61.72,-52.3C62.93,-60.02 64.39,-69.29 65.74,-77.89"/> +<polygon fill="black" stroke="black" points="62.3,-78.56 67.31,-87.9 69.22,-77.47 62.3,-78.56"/> +</g> +</g> </svg> 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 @@ <?xml version="1.0" encoding="UTF-8" standalone="no"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" - "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> <!-- Generated by graphviz version 2.43.0 (0) --> <!-- Title: chapter02 Pages: 1 --> -<svg width="301pt" height="404pt" - viewBox="0.00 0.00 301.08 404.00" xmlns="http://www.w3.org/2000/svg"> - <g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 400)"> - <title>chapter02</title> - <polygon fill="white" stroke="transparent" points="-4,4 -4,-400 297.08,-400 297.08,4 -4,4"/> - <!-- Start1 --> - <g id="node1" class="node"> - <title>Start1</title> - <polygon fill="none" stroke="black" points="169.34,-396 115.34,-396 115.34,-360 169.34,-360 169.34,-396"/> - <text text-anchor="middle" x="142.34" y="-374.3" font-family="Times,serif" font-size="14.00">Start</text> - </g> - <!-- Con12 --> - <g id="node2" class="node"> - <title>Con12</title> - <ellipse fill="none" stroke="black" cx="46.34" cy="-162" rx="34.39" ry="18"/> - <text text-anchor="middle" x="46.34" y="-158.3" font-family="Times,serif" font-size="14.00">Con1</text> - </g> - <!-- Start1->Con12 --> - <g id="edge1" class="edge"> - <title>Start1->Con12</title> - <path fill="none" stroke="black" stroke-dasharray="1,5" - d="M115.19,-374.6C84.32,-370.26 35.25,-358.08 12.34,-324 -15.78,-282.17 11,-221.54 30.37,-187.88"/> - <polygon fill="black" stroke="black" points="33.47,-189.52 35.59,-179.14 27.46,-185.93 33.47,-189.52"/> - </g> - <!-- Con23 --> - <g id="node3" class="node"> - <title>Con23</title> - <ellipse fill="none" stroke="black" cx="55.34" cy="-306" rx="34.39" ry="18"/> - <text text-anchor="middle" x="55.34" y="-302.3" font-family="Times,serif" font-size="14.00">Con2</text> - </g> - <!-- Start1->Con23 --> - <g id="edge2" class="edge"> - <title>Start1->Con23</title> - <path fill="none" stroke="black" stroke-dasharray="1,5" - d="M120.83,-359.7C108.86,-350.07 93.88,-338.01 81.26,-327.86"/> - <polygon fill="black" stroke="black" points="83.35,-325.05 73.37,-321.51 78.97,-330.5 83.35,-325.05"/> - </g> - <!-- Con34 --> - <g id="node4" class="node"> - <title>Con34</title> - <ellipse fill="none" stroke="black" cx="142.34" cy="-306" rx="34.39" ry="18"/> - <text text-anchor="middle" x="142.34" y="-302.3" font-family="Times,serif" font-size="14.00">Con3</text> - </g> - <!-- Start1->Con34 --> - <g id="edge3" class="edge"> - <title>Start1->Con34</title> - <path fill="none" stroke="black" stroke-dasharray="1,5" - d="M142.34,-359.7C142.34,-351.98 142.34,-342.71 142.34,-334.11"/> - <polygon fill="black" stroke="black" points="145.84,-334.1 142.34,-324.1 138.84,-334.1 145.84,-334.1"/> - </g> - <!-- Con56 --> - <g id="node6" class="node"> - <title>Con56</title> - <ellipse fill="none" stroke="black" cx="229.34" cy="-306" rx="34.39" ry="18"/> - <text text-anchor="middle" x="229.34" y="-302.3" font-family="Times,serif" font-size="14.00">Con5</text> - </g> - <!-- Start1->Con56 --> - <g id="edge6" class="edge"> - <title>Start1->Con56</title> - <path fill="none" stroke="black" stroke-dasharray="1,5" - d="M163.84,-359.7C175.81,-350.07 190.8,-338.01 203.41,-327.86"/> - <polygon fill="black" stroke="black" points="205.71,-330.5 211.31,-321.51 201.32,-325.05 205.71,-330.5"/> - </g> - <!-- Return10 --> - <g id="node10" class="node"> - <title>Return10</title> - <polygon fill="none" stroke="black" points="268.34,-36 202.34,-36 202.34,0 268.34,0 268.34,-36"/> - <text text-anchor="middle" x="235.34" y="-14.3" font-family="Times,serif" font-size="14.00">Return</text> - </g> - <!-- Start1->Return10 --> - <g id="edge13" class="edge"> - <title>Start1->Return10</title> - <path fill="none" stroke="red" - d="M169.34,-373.51C199.13,-368.18 246.29,-355.12 272.34,-324 298.3,-292.99 291.34,-275.45 291.34,-235 291.34,-235 291.34,-235 291.34,-161 291.34,-117.91 268.74,-72.26 252.26,-44.7"/> - <polygon fill="red" stroke="red" points="255.17,-42.75 246.94,-36.07 249.21,-46.42 255.17,-42.75"/> - </g> - <!-- Add9 --> - <g id="node9" class="node"> - <title>Add9</title> - <ellipse fill="none" stroke="black" cx="180.34" cy="-90" rx="28.7" ry="18"/> - <text text-anchor="middle" x="180.34" y="-86.3" font-family="Times,serif" font-size="14.00">Add</text> - </g> - <!-- Con12->Add9 --> - <g id="edge10" class="edge"> - <title>Con12->Add9</title> - <path fill="none" stroke="black" d="M69.99,-148.65C92.27,-137 125.77,-119.5 150.02,-106.84"/> - <polygon fill="black" stroke="black" points="151.89,-109.81 159.13,-102.08 148.65,-103.61 151.89,-109.81"/> - </g> - <!-- Mul5 --> - <g id="node5" class="node"> - <title>Mul5</title> - <ellipse fill="none" stroke="black" cx="137.34" cy="-234" rx="28.7" ry="18"/> - <text text-anchor="middle" x="137.34" y="-230.3" font-family="Times,serif" font-size="14.00">Mul</text> - </g> - <!-- Con23->Mul5 --> - <g id="edge4" class="edge"> - <title>Con23->Mul5</title> - <path fill="none" stroke="black" d="M72.73,-290.15C84.56,-280.05 100.38,-266.55 113.4,-255.43"/> - <polygon fill="black" stroke="black" points="115.76,-258.03 121.09,-248.87 111.21,-252.7 115.76,-258.03"/> - </g> - <!-- Con34->Mul5 --> - <g id="edge5" class="edge"> - <title>Con34->Mul5</title> - <path fill="none" stroke="black" d="M141.1,-287.7C140.55,-279.98 139.89,-270.71 139.27,-262.11"/> - <polygon fill="black" stroke="black" points="142.76,-261.83 138.56,-252.1 135.78,-262.33 142.76,-261.83"/> - </g> - <!-- Add8 --> - <g id="node8" class="node"> - <title>Add8</title> - <ellipse fill="none" stroke="black" cx="180.34" cy="-162" rx="28.7" ry="18"/> - <text text-anchor="middle" x="180.34" y="-158.3" font-family="Times,serif" font-size="14.00">Add</text> - </g> - <!-- Mul5->Add8 --> - <g id="edge8" class="edge"> - <title>Mul5->Add8</title> - <path fill="none" stroke="black" d="M147.31,-216.76C152.58,-208.19 159.15,-197.49 165.04,-187.9"/> - <polygon fill="black" stroke="black" points="168.17,-189.5 170.42,-179.15 162.2,-185.84 168.17,-189.5"/> - </g> - <!-- Minus7 --> - <g id="node7" class="node"> - <title>Minus7</title> - <ellipse fill="none" stroke="black" cx="223.34" cy="-234" rx="39.79" ry="18"/> - <text text-anchor="middle" x="223.34" y="-230.3" font-family="Times,serif" font-size="14.00">Minus</text> - </g> - <!-- Con56->Minus7 --> - <g id="edge7" class="edge"> - <title>Con56->Minus7</title> - <path fill="none" stroke="black" d="M227.85,-287.7C227.19,-279.98 226.4,-270.71 225.66,-262.11"/> - <polygon fill="black" stroke="black" points="229.15,-261.77 224.8,-252.1 222.17,-262.37 229.15,-261.77"/> - </g> - <!-- Minus7->Add8 --> - <g id="edge9" class="edge"> - <title>Minus7->Add8</title> - <path fill="none" stroke="black" d="M213.15,-216.41C207.88,-207.83 201.34,-197.19 195.49,-187.67"/> - <polygon fill="black" stroke="black" points="198.38,-185.68 190.16,-178.99 192.41,-189.34 198.38,-185.68"/> - </g> - <!-- Add8->Add9 --> - <g id="edge11" class="edge"> - <title>Add8->Add9</title> - <path fill="none" stroke="black" d="M180.34,-143.7C180.34,-135.98 180.34,-126.71 180.34,-118.11"/> - <polygon fill="black" stroke="black" points="183.84,-118.1 180.34,-108.1 176.84,-118.1 183.84,-118.1"/> - </g> - <!-- Add9->Return10 --> - <g id="edge12" class="edge"> - <title>Add9->Return10</title> - <path fill="none" stroke="black" d="M192.54,-73.46C199.2,-64.99 207.61,-54.29 215.21,-44.61"/> - <polygon fill="black" stroke="black" points="218.19,-46.49 221.62,-36.46 212.69,-42.16 218.19,-46.49"/> - </g> - </g> +<svg width="322pt" height="436pt" + viewBox="0.00 0.00 322.00 436.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 432)"> +<title>chapter02</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-432 318,-432 318,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-420 306,-420 306,-8 8,-8"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="yellow" stroke="black" points="117,-412 63,-412 63,-376 117,-376 117,-412"/> +<text text-anchor="middle" x="90" y="-390.3" font-family="Times,serif" font-size="14.00">Start</text> +</g> +<!-- Con12 --> +<g id="node2" class="node"> +<title>Con12</title> +<ellipse fill="none" stroke="black" cx="70" cy="-178" rx="34.39" ry="18"/> +<text text-anchor="middle" x="70" y="-174.3" font-family="Times,serif" font-size="14.00">Con1</text> +</g> +<!-- Con12->Start1 --> +<g id="edge1" class="edge"> +<title>Con12->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M62.43,-195.98C50.2,-225.92 29.16,-289.7 47,-340 50.66,-350.32 57.29,-360.1 64.26,-368.39"/> +<polygon fill="black" stroke="black" points="61.67,-370.74 70.96,-375.84 66.87,-366.06 61.67,-370.74"/> +</g> +<!-- Con23 --> +<g id="node3" class="node"> +<title>Con23</title> +<ellipse fill="none" stroke="black" cx="90" cy="-322" rx="34.39" ry="18"/> +<text text-anchor="middle" x="90" y="-318.3" font-family="Times,serif" font-size="14.00">Con2</text> +</g> +<!-- Con23->Start1 --> +<g id="edge2" class="edge"> +<title>Con23->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M90,-340.3C90,-348.02 90,-357.29 90,-365.89"/> +<polygon fill="black" stroke="black" points="86.5,-365.9 90,-375.9 93.5,-365.9 86.5,-365.9"/> +</g> +<!-- Con34 --> +<g id="node4" class="node"> +<title>Con34</title> +<ellipse fill="none" stroke="black" cx="177" cy="-322" rx="34.39" ry="18"/> +<text text-anchor="middle" x="177" y="-318.3" font-family="Times,serif" font-size="14.00">Con3</text> +</g> +<!-- Con34->Start1 --> +<g id="edge3" class="edge"> +<title>Con34->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M158.97,-337.5C147.52,-346.72 132.42,-358.87 119.27,-369.45"/> +<polygon fill="black" stroke="black" points="116.98,-366.8 111.38,-375.8 121.37,-372.25 116.98,-366.8"/> +</g> +<!-- Mul5 --> +<g id="node5" class="node"> +<title>Mul5</title> +<ellipse fill="none" stroke="black" cx="161" cy="-250" rx="28.7" ry="18"/> +<text text-anchor="middle" x="161" y="-246.3" font-family="Times,serif" font-size="14.00">Mul</text> +</g> +<!-- Mul5->Con23 --> +<g id="edge4" class="edge"> +<title>Mul5->Con23</title> +<path fill="none" stroke="black" d="M146.29,-265.5C136.65,-275 123.86,-287.62 112.91,-298.42"/> +<polygon fill="black" stroke="black" points="110.34,-296.03 105.68,-305.54 115.26,-301.02 110.34,-296.03"/> +</g> +<!-- Mul5->Con34 --> +<g id="edge5" class="edge"> +<title>Mul5->Con34</title> +<path fill="none" stroke="black" d="M164.87,-267.95C166.65,-275.74 168.81,-285.18 170.81,-293.92"/> +<polygon fill="black" stroke="black" points="167.41,-294.76 173.05,-303.72 174.24,-293.2 167.41,-294.76"/> +</g> +<!-- Con56 --> +<g id="node6" class="node"> +<title>Con56</title> +<ellipse fill="none" stroke="black" cx="264" cy="-322" rx="34.39" ry="18"/> +<text text-anchor="middle" x="264" y="-318.3" font-family="Times,serif" font-size="14.00">Con5</text> +</g> +<!-- Con56->Start1 --> +<g id="edge6" class="edge"> +<title>Con56->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M237.57,-333.63C207.98,-345.54 159.83,-364.91 126.62,-378.27"/> +<polygon fill="black" stroke="black" points="125.22,-375.06 117.25,-382.04 127.83,-381.55 125.22,-375.06"/> +</g> +<!-- Minus7 --> +<g id="node7" class="node"> +<title>Minus7</title> +<ellipse fill="none" stroke="black" cx="252" cy="-250" rx="39.79" ry="18"/> +<text text-anchor="middle" x="252" y="-246.3" font-family="Times,serif" font-size="14.00">Minus</text> +</g> +<!-- Minus7->Con56 --> +<g id="edge7" class="edge"> +<title>Minus7->Con56</title> +<path fill="none" stroke="black" d="M254.97,-268.3C256.29,-276.02 257.88,-285.29 259.35,-293.89"/> +<polygon fill="black" stroke="black" points="255.93,-294.63 261.07,-303.9 262.83,-293.45 255.93,-294.63"/> +</g> +<!-- Add8 --> +<g id="node8" class="node"> +<title>Add8</title> +<ellipse fill="none" stroke="black" cx="161" cy="-178" rx="28.7" ry="18"/> +<text text-anchor="middle" x="161" y="-174.3" font-family="Times,serif" font-size="14.00">Add</text> +</g> +<!-- Add8->Mul5 --> +<g id="edge8" class="edge"> +<title>Add8->Mul5</title> +<path fill="none" stroke="black" d="M161,-196.3C161,-204.02 161,-213.29 161,-221.89"/> +<polygon fill="black" stroke="black" points="157.5,-221.9 161,-231.9 164.5,-221.9 157.5,-221.9"/> +</g> +<!-- Add8->Minus7 --> +<g id="edge9" class="edge"> +<title>Add8->Minus7</title> +<path fill="none" stroke="black" d="M178.55,-192.5C191.62,-202.55 209.72,-216.48 224.68,-227.99"/> +<polygon fill="black" stroke="black" points="222.56,-230.77 232.62,-234.09 226.83,-225.22 222.56,-230.77"/> +</g> +<!-- Add9 --> +<g id="node9" class="node"> +<title>Add9</title> +<ellipse fill="none" stroke="black" cx="70" cy="-106" rx="28.7" ry="18"/> +<text text-anchor="middle" x="70" y="-102.3" font-family="Times,serif" font-size="14.00">Add</text> +</g> +<!-- Add9->Con12 --> +<g id="edge10" class="edge"> +<title>Add9->Con12</title> +<path fill="none" stroke="black" d="M70,-124.3C70,-132.02 70,-141.29 70,-149.89"/> +<polygon fill="black" stroke="black" points="66.5,-149.9 70,-159.9 73.5,-149.9 66.5,-149.9"/> +</g> +<!-- Add9->Add8 --> +<g id="edge11" class="edge"> +<title>Add9->Add8</title> +<path fill="none" stroke="black" d="M87.55,-120.5C101.14,-130.96 120.18,-145.6 135.46,-157.35"/> +<polygon fill="black" stroke="black" points="133.45,-160.22 143.51,-163.54 137.72,-154.67 133.45,-160.22"/> +</g> +<!-- Return10 --> +<g id="node10" class="node"> +<title>Return10</title> +<polygon fill="yellow" stroke="black" points="92,-52 26,-52 26,-16 92,-16 92,-52"/> +<text text-anchor="middle" x="59" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Return10->Start1 --> +<g id="edge12" class="edge"> +<title>Return10->Start1</title> +<path fill="none" stroke="red" d="M48.61,-52.09C42.9,-62.2 36.15,-75.45 32,-88 19.42,-126.09 17,-136.89 17,-177 17,-177 17,-177 17,-251 17,-291.54 17.45,-304.48 37,-340 42.87,-350.67 51.53,-360.62 60.16,-368.95"/> +<polygon fill="red" stroke="red" points="57.93,-371.65 67.66,-375.84 62.66,-366.5 57.93,-371.65"/> +</g> +<!-- Return10->Add9 --> +<g id="edge13" class="edge"> +<title>Return10->Add9</title> +<path fill="none" stroke="black" d="M61.72,-52.3C62.93,-60.02 64.39,-69.29 65.74,-77.89"/> +<polygon fill="black" stroke="black" points="62.3,-78.56 67.31,-87.9 69.22,-77.47 62.3,-78.56"/> +</g> +</g> </svg> 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<Node> all = findAll(start); + Collection<Node> 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<Node> 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<Node> 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<Node> findAll(StartNode start) { - Map<Integer, Node> all = new HashMap<>(); - for (int i = 0; i < start.nOuts(); i++) { - Node n = start.out(i); + private Collection<Node> findAll(Parser parser) { + final StartNode start = Parser.START; + final HashMap<Integer, Node> 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<Integer, Node> all, Node n) { - if (all.get(n._nid) == null) { - // Not yet seen + private void walk(HashMap<Integer, Node> 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() { |
