summaryrefslogtreecommitdiff
path: root/chapter02
diff options
context:
space:
mode:
authorDibyendu Majumdar <dibyendumajumdar@users.noreply.github.com>2023-10-22 05:18:58 +0100
committerGitHub <noreply@github.com>2023-10-21 21:18:58 -0700
commit10ed01188f78e3fad4b257a0241f9a89e2fdb405 (patch)
treebcf72f66bf0db33cced9b48e2401428706b8eebe /chapter02
parentd1c5e6995f5e08df18069be49b1fe0ea193996a9 (diff)
downloadSimple-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
Diffstat (limited to 'chapter02')
-rw-r--r--chapter02/README.md12
-rw-r--r--chapter02/docs/02-post-peephole-ex1.gv19
-rw-r--r--chapter02/docs/02-post-peephole-ex1.svg92
-rw-r--r--chapter02/docs/02-pre-peephole-ex1.gv53
-rw-r--r--chapter02/docs/02-pre-peephole-ex1.svg299
-rw-r--r--chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java107
-rw-r--r--chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java6
7 files changed, 295 insertions, 293 deletions
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&#45;&gt;Con213 -->
- <g id="edge1" class="edge">
- <title>Start1&#45;&gt;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&#45;&gt;Return14 -->
- <g id="edge3" class="edge">
- <title>Start1&#45;&gt;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&#45;&gt;Return14 -->
- <g id="edge2" class="edge">
- <title>Con213&#45;&gt;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&#45;&gt;Start1 -->
+<g id="edge1" class="edge">
+<title>Con213&#45;&gt;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&#45;&gt;Start1 -->
+<g id="edge2" class="edge">
+<title>Return14&#45;&gt;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&#45;&gt;Con213 -->
+<g id="edge3" class="edge">
+<title>Return14&#45;&gt;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&#45;&gt;Con12 -->
- <g id="edge1" class="edge">
- <title>Start1&#45;&gt;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&#45;&gt;Con23 -->
- <g id="edge2" class="edge">
- <title>Start1&#45;&gt;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&#45;&gt;Con34 -->
- <g id="edge3" class="edge">
- <title>Start1&#45;&gt;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&#45;&gt;Con56 -->
- <g id="edge6" class="edge">
- <title>Start1&#45;&gt;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&#45;&gt;Return10 -->
- <g id="edge13" class="edge">
- <title>Start1&#45;&gt;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&#45;&gt;Add9 -->
- <g id="edge10" class="edge">
- <title>Con12&#45;&gt;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&#45;&gt;Mul5 -->
- <g id="edge4" class="edge">
- <title>Con23&#45;&gt;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&#45;&gt;Mul5 -->
- <g id="edge5" class="edge">
- <title>Con34&#45;&gt;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&#45;&gt;Add8 -->
- <g id="edge8" class="edge">
- <title>Mul5&#45;&gt;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&#45;&gt;Minus7 -->
- <g id="edge7" class="edge">
- <title>Con56&#45;&gt;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&#45;&gt;Add8 -->
- <g id="edge9" class="edge">
- <title>Minus7&#45;&gt;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&#45;&gt;Add9 -->
- <g id="edge11" class="edge">
- <title>Add8&#45;&gt;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&#45;&gt;Return10 -->
- <g id="edge12" class="edge">
- <title>Add9&#45;&gt;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&#45;&gt;Start1 -->
+<g id="edge1" class="edge">
+<title>Con12&#45;&gt;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&#45;&gt;Start1 -->
+<g id="edge2" class="edge">
+<title>Con23&#45;&gt;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&#45;&gt;Start1 -->
+<g id="edge3" class="edge">
+<title>Con34&#45;&gt;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&#45;&gt;Con23 -->
+<g id="edge4" class="edge">
+<title>Mul5&#45;&gt;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&#45;&gt;Con34 -->
+<g id="edge5" class="edge">
+<title>Mul5&#45;&gt;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&#45;&gt;Start1 -->
+<g id="edge6" class="edge">
+<title>Con56&#45;&gt;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&#45;&gt;Con56 -->
+<g id="edge7" class="edge">
+<title>Minus7&#45;&gt;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&#45;&gt;Mul5 -->
+<g id="edge8" class="edge">
+<title>Add8&#45;&gt;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&#45;&gt;Minus7 -->
+<g id="edge9" class="edge">
+<title>Add8&#45;&gt;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&#45;&gt;Con12 -->
+<g id="edge10" class="edge">
+<title>Add9&#45;&gt;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&#45;&gt;Add8 -->
+<g id="edge11" class="edge">
+<title>Add9&#45;&gt;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&#45;&gt;Start1 -->
+<g id="edge12" class="edge">
+<title>Return10&#45;&gt;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&#45;&gt;Add9 -->
+<g id="edge13" class="edge">
+<title>Return10&#45;&gt;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());