diff options
| author | Dibyendu Majumdar <dibyendumajumdar@users.noreply.github.com> | 2023-11-03 21:21:54 +0000 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-11-03 21:21:54 +0000 |
| commit | 736c658c274404084b15b450b2ab72d0e7569586 (patch) | |
| tree | 38f729d42ca6a82f32429dde774eba7666a57391 /chapter02 | |
| parent | 360f4d1f2b5b4a3cb8bd97f1a659e8f7a3d0669e (diff) | |
| download | Simple-736c658c274404084b15b450b2ab72d0e7569586.tar.gz Simple-736c658c274404084b15b450b2ab72d0e7569586.zip | |
Backport changes in Chapter 5 to previous chapters and update Chapter5 documentation (#34)
* Backport changes from chapter 5 to older chapters (#30)
* Fix wrong indent
* Backport to chapter 4
* Backport to chapter 3
* Backport to chapter 2
* Backport to chapter 1
* Add if statement to comment (#32)
* Update visuals for chapters 1,2 & 3.
Reenable drawing of edges from constants to Start for these chapters.
* Update visuals for chapters 4.
Revise text to explain the labeling of edges in graphs and that we omit edge from Constant to Start nodes from chapter 4.
* Add code snippets for if statement parsing and the duplication and merging of ScopeNodes.
Explain how scopeNodes are duplicated and merged.
* Add constant check to minus node (#31)
* Fix closing root block with } (#33)
* Backport fix closing root block with } to chapter 4 and 3 (#35)
* Show use-def edge from Phi to Region as dotted edge.
Add example of Phi peephole.
Update visuals.
Add more examples.
* Fix visuals in chapter 1 and README in chapter 4.
* Remove subheading
* Adjust spaces
---------
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Diffstat (limited to 'chapter02')
20 files changed, 400 insertions, 332 deletions
diff --git a/chapter02/README.md b/chapter02/README.md index b89a3059..e1ee19aa 100644 --- a/chapter02/README.md +++ b/chapter02/README.md @@ -117,9 +117,10 @@ The following visual shows how the graph looks like pre-peephole optimization:  -* Control nodes appear as square boxes +* Control nodes appear as square boxes with yellow background * Control edges are in bold red -* The edges from Start to Constants are shown in dotted lines as these are not true def-use edges +* The edges from Constants to Start are shown in dotted lines as these are not true control edges +* We label each edge with its position in the node's list of inputs. ## Post-peephole diff --git a/chapter02/docs/02-post-peephole-ex1.gv b/chapter02/docs/02-post-peephole-ex1.gv index 290a1178..6c2b23ae 100644 --- a/chapter02/docs/02-post-peephole-ex1.gv +++ b/chapter02/docs/02-post-peephole-ex1.gv @@ -1,11 +1,17 @@ digraph chapter02 { +/* +return 1+2*3+-5; +*/ rankdir=BT; + ordering="in"; + concentrate="true"; subgraph cluster_Nodes { Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; - Con213 [ label="Con2" ]; + Con_13 [ label="#2" ]; 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 + edge [ fontname=Helvetica, fontsize=8 ]; + Con_13 -> Start1[taillabel=0 style=dotted]; + Return14 -> Start1[taillabel=0 color=red]; + Return14 -> Con_13[taillabel=1]; +} diff --git a/chapter02/docs/02-post-peephole-ex1.svg b/chapter02/docs/02-post-peephole-ex1.svg index b3c42c7d..db27e30d 100644 --- a/chapter02/docs/02-post-peephole-ex1.svg +++ b/chapter02/docs/02-post-peephole-ex1.svg @@ -4,50 +4,53 @@ <!-- Generated by graphviz version 2.43.0 (0) --> <!-- Title: chapter02 Pages: 1 --> -<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"> +<svg width="114pt" height="220pt" + viewBox="0.00 0.00 114.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"/> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-216 110,-216 110,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"/> +<polygon fill="none" stroke="black" points="8,-8 8,-204 98,-204 98,-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> +<polygon fill="yellow" stroke="black" points="80,-196 26,-196 26,-160 80,-160 80,-196"/> +<text text-anchor="middle" x="53" y="-174.3" font-family="Times,serif" font-size="14.00">Start</text> </g> -<!-- Con213 --> +<!-- Con_13 --> <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> +<title>Con_13</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">#2</text> </g> -<!-- Con213->Start1 --> +<!-- Con_13->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"/> +<title>Con_13->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M45.42,-123.95C46.52,-131.65 47.85,-140.97 49.09,-149.64"/> +<polygon fill="black" stroke="black" points="45.65,-150.32 50.53,-159.72 52.58,-149.33 45.65,-150.32"/> +<text text-anchor="middle" x="42.42" y="-126.55" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </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> +<polygon fill="yellow" stroke="black" points="86,-52 20,-52 20,-16 86,-16 86,-52"/> +<text text-anchor="middle" x="53" 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"/> +<path fill="none" stroke="red" d="M64.05,-52.39C69.74,-62.38 76.08,-75.42 79,-88 82.62,-103.59 82.62,-108.41 79,-124 76.9,-133.04 73.03,-142.32 68.91,-150.53"/> +<polygon fill="red" stroke="red" points="65.69,-149.14 64.05,-159.61 71.86,-152.45 65.69,-149.14"/> +<text text-anchor="middle" x="61.05" y="-54.99" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Return14->Con213 --> +<!-- Return14->Con_13 --> <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"/> +<title>Return14->Con_13</title> +<path fill="none" stroke="black" d="M50.53,-52.3C49.43,-60.02 48.1,-69.29 46.87,-77.89"/> +<polygon fill="black" stroke="black" points="43.39,-77.5 45.44,-87.9 50.32,-78.49 43.39,-77.5"/> +<text text-anchor="middle" x="47.53" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </g> </g> </svg> diff --git a/chapter02/docs/02-pre-peephole-ex1.gv b/chapter02/docs/02-pre-peephole-ex1.gv index c2eab457..411de5ee 100644 --- a/chapter02/docs/02-pre-peephole-ex1.gv +++ b/chapter02/docs/02-pre-peephole-ex1.gv @@ -1,28 +1,34 @@ digraph chapter02 { +/* +return 1+2*3+-5; +*/ rankdir=BT; + ordering="in"; + concentrate="true"; 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" ]; + Con_2 [ label="#1" ]; + Con_3 [ label="#2" ]; + Con_4 [ label="#3" ]; + Mul5 [ label="*" ]; + Con_6 [ label="#5" ]; + Minus7 [ label="-" ]; + Add8 [ label="+" ]; + Add9 [ label="+" ]; 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 + edge [ fontname=Helvetica, fontsize=8 ]; + Con_2 -> Start1[taillabel=0 style=dotted]; + Con_3 -> Start1[taillabel=0 style=dotted]; + Con_4 -> Start1[taillabel=0 style=dotted]; + Mul5 -> Con_3[taillabel=1]; + Mul5 -> Con_4[taillabel=2]; + Con_6 -> Start1[taillabel=0 style=dotted]; + Minus7 -> Con_6[taillabel=1]; + Add8 -> Mul5[taillabel=1]; + Add8 -> Minus7[taillabel=2]; + Add9 -> Con_2[taillabel=1]; + Add9 -> Add8[taillabel=2]; + Return10 -> Start1[taillabel=0 color=red]; + Return10 -> Add9[taillabel=1]; +} diff --git a/chapter02/docs/02-pre-peephole-ex1.svg b/chapter02/docs/02-pre-peephole-ex1.svg index 8a1ef457..29c76bd8 100644 --- a/chapter02/docs/02-pre-peephole-ex1.svg +++ b/chapter02/docs/02-pre-peephole-ex1.svg @@ -4,152 +4,165 @@ <!-- Generated by graphviz version 2.43.0 (0) --> <!-- Title: chapter02 Pages: 1 --> -<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"> +<svg width="278pt" height="436pt" + viewBox="0.00 0.00 278.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"/> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-432 274,-432 274,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"/> +<polygon fill="none" stroke="black" points="8,-8 8,-420 262,-420 262,-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> +<polygon fill="yellow" stroke="black" points="162,-412 108,-412 108,-376 162,-376 162,-412"/> +<text text-anchor="middle" x="135" y="-390.3" font-family="Times,serif" font-size="14.00">Start</text> </g> -<!-- Con12 --> +<!-- Con_2 --> <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> +<title>Con_2</title> +<ellipse fill="none" stroke="black" cx="222" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="222" y="-174.3" font-family="Times,serif" font-size="14.00">#1</text> </g> -<!-- Con12->Start1 --> +<!-- Con_2->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"/> +<title>Con_2->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M230.65,-195.54C245.5,-226.47 271.62,-294.07 243,-340 227.56,-364.77 196.8,-378.29 172.04,-385.46"/> +<polygon fill="black" stroke="black" points="170.97,-382.13 162.2,-388.08 172.77,-388.89 170.97,-382.13"/> +<text text-anchor="middle" x="227.65" y="-198.14" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Con23 --> +<!-- Con_3 --> <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> +<title>Con_3</title> +<ellipse fill="none" stroke="black" cx="63" cy="-322" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-318.3" font-family="Times,serif" font-size="14.00">#2</text> </g> -<!-- Con23->Start1 --> +<!-- Con_3->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"/> +<title>Con_3->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M77.57,-337.17C86.92,-346.25 99.3,-358.29 110.17,-368.86"/> +<polygon fill="black" stroke="black" points="107.79,-371.43 117.4,-375.89 112.67,-366.41 107.79,-371.43"/> +<text text-anchor="middle" x="74.57" y="-339.77" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Con34 --> +<!-- Con_4 --> <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> +<title>Con_4</title> +<ellipse fill="none" stroke="black" cx="135" cy="-322" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-318.3" font-family="Times,serif" font-size="14.00">#3</text> </g> -<!-- Con34->Start1 --> +<!-- Con_4->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"/> +<title>Con_4->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M135,-340.3C135,-348.02 135,-357.29 135,-365.89"/> +<polygon fill="black" stroke="black" points="131.5,-365.9 135,-375.9 138.5,-365.9 131.5,-365.9"/> +<text text-anchor="middle" x="132" y="-342.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </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> +<ellipse fill="none" stroke="black" cx="135" cy="-250" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-246.3" font-family="Times,serif" font-size="14.00">*</text> </g> -<!-- Mul5->Con23 --> +<!-- Mul5->Con_3 --> <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"/> +<title>Mul5->Con_3</title> +<path fill="none" stroke="black" d="M120.43,-265.17C110.25,-275.06 96.48,-288.45 84.97,-299.64"/> +<polygon fill="black" stroke="black" points="82.53,-297.13 77.8,-306.62 87.41,-302.15 82.53,-297.13"/> +<text text-anchor="middle" x="117.43" y="-267.77" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </g> -<!-- Mul5->Con34 --> +<!-- Mul5->Con_4 --> <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"/> +<title>Mul5->Con_4</title> +<path fill="none" stroke="black" d="M135,-268.3C135,-276.02 135,-285.29 135,-293.89"/> +<polygon fill="black" stroke="black" points="131.5,-293.9 135,-303.9 138.5,-293.9 131.5,-293.9"/> +<text text-anchor="middle" x="132" y="-270.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> </g> -<!-- Con56 --> +<!-- Con_6 --> <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> +<title>Con_6</title> +<ellipse fill="none" stroke="black" cx="207" cy="-322" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-318.3" font-family="Times,serif" font-size="14.00">#5</text> </g> -<!-- Con56->Start1 --> +<!-- Con_6->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"/> +<title>Con_6->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M192.43,-337.17C183.08,-346.25 170.7,-358.29 159.83,-368.86"/> +<polygon fill="black" stroke="black" points="157.33,-366.41 152.6,-375.89 162.21,-371.43 157.33,-366.41"/> +<text text-anchor="middle" x="189.43" y="-339.77" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </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> +<ellipse fill="none" stroke="black" cx="207" cy="-250" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-246.3" font-family="Times,serif" font-size="14.00">-</text> </g> -<!-- Minus7->Con56 --> +<!-- Minus7->Con_6 --> <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"/> +<title>Minus7->Con_6</title> +<path fill="none" stroke="black" d="M207,-268.3C207,-276.02 207,-285.29 207,-293.89"/> +<polygon fill="black" stroke="black" points="203.5,-293.9 207,-303.9 210.5,-293.9 203.5,-293.9"/> +<text text-anchor="middle" x="204" y="-270.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </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> +<ellipse fill="none" stroke="black" cx="140" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="140" y="-174.3" font-family="Times,serif" font-size="14.00">+</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"/> +<path fill="none" stroke="black" d="M138.76,-196.3C138.21,-204.02 137.55,-213.29 136.94,-221.89"/> +<polygon fill="black" stroke="black" points="133.44,-221.67 136.22,-231.9 140.43,-222.17 133.44,-221.67"/> +<text text-anchor="middle" x="135.76" y="-198.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </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"/> +<path fill="none" stroke="black" d="M153.88,-193.5C163.14,-203.17 175.47,-216.06 185.93,-226.98"/> +<polygon fill="black" stroke="black" points="183.69,-229.71 193.14,-234.51 188.75,-224.87 183.69,-229.71"/> +<text text-anchor="middle" x="150.88" y="-196.1" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> </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> +<ellipse fill="none" stroke="black" cx="140" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="140" y="-102.3" font-family="Times,serif" font-size="14.00">+</text> </g> -<!-- Add9->Con12 --> +<!-- Add9->Con_2 --> <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"/> +<title>Add9->Con_2</title> +<path fill="none" stroke="black" d="M156.2,-120.83C168.18,-131.06 184.69,-145.15 198.18,-156.66"/> +<polygon fill="black" stroke="black" points="196.23,-159.61 206.11,-163.44 200.78,-154.28 196.23,-159.61"/> +<text text-anchor="middle" x="153.2" y="-123.43" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </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"/> +<path fill="none" stroke="black" d="M140,-124.3C140,-132.02 140,-141.29 140,-149.89"/> +<polygon fill="black" stroke="black" points="136.5,-149.9 140,-159.9 143.5,-149.9 136.5,-149.9"/> +<text text-anchor="middle" x="137" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> </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> +<polygon fill="yellow" stroke="black" points="125,-52 59,-52 59,-16 125,-16 125,-52"/> +<text text-anchor="middle" x="92" 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"/> +<path fill="none" stroke="red" d="M75.73,-52.27C53.67,-77.55 17,-127.09 17,-177 17,-177 17,-177 17,-251 17,-290.8 4.09,-307.45 27,-340 43.69,-363.72 74.05,-377.3 98.34,-384.76"/> +<polygon fill="red" stroke="red" points="97.41,-388.14 107.99,-387.51 99.33,-381.4 97.41,-388.14"/> +<text text-anchor="middle" x="72.73" y="-54.87" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </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"/> +<path fill="none" stroke="black" d="M103.87,-52.3C109.82,-60.98 117.12,-71.63 123.6,-81.08"/> +<polygon fill="black" stroke="black" points="120.71,-83.06 129.25,-89.33 126.49,-79.1 120.71,-83.06"/> +<text text-anchor="middle" x="100.87" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </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 1af19d80..df128674 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -1,9 +1,6 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.ConstantNode; -import com.seaofnodes.simple.node.Control; -import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.StartNode; +import com.seaofnodes.simple.node.*; import java.util.*; @@ -21,7 +18,10 @@ public class GraphVisualizer { Collection<Node> all = findAll(parser); StringBuilder sb = new StringBuilder(); sb.append("digraph chapter02 {\n"); - + sb.append("/*\n"); + sb.append(parser.src()); + sb.append("\n*/\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 @@ -29,12 +29,19 @@ public class GraphVisualizer { // still making the subgraphs DOT gets confused. sb.append("\trankdir=BT;\n"); // Force Nodes before Scopes + // Preserve node input order + sb.append("\tordering=\"in\";\n"); + + // Merge multiple edges hitting the same node. Makes common shared + // nodes much prettier to look at. + sb.append("\tconcentrate=\"true\";\n"); + // 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(); } @@ -43,13 +50,14 @@ public class GraphVisualizer { 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) { + for( Node n : all ) { sb.append("\t\t").append(n.uniqueName()).append(" [ "); + String lab = n.glabel(); // control nodes have box shape // other nodes are ellipses, i.e. default shape - if (n instanceof Control) + if( n.isCFG() ) sb.append("shape=box style=filled fillcolor=yellow "); - sb.append("label=\"").append(n.label()).append("\" "); + sb.append("label=\"").append(lab).append("\" "); sb.append("];\n"); } sb.append("\t}\n"); // End Node cluster @@ -58,25 +66,32 @@ public class GraphVisualizer { // 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"); + // All them edge labels + sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n"); + for( Node n : all ) { + // In this chapter we do display the Constant->Start edge; + int i=0; + for( Node def : n._inputs ) { + if( def != null ) { + // Most edges land here use->def + sb.append('\t').append(n.uniqueName()).append(" -> "); + sb.append(def.uniqueName()); + // Number edges, so we can see how they track + sb.append("[taillabel=").append(i); + if( n instanceof ConstantNode && def instanceof StartNode ) + sb.append(" style=dotted"); + // control edges are colored red + else if( def.isCFG() ) + sb.append(" color=red"); + sb.append("];\n"); + } + i++; + } } } - + /** - * 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. + * Finds all nodes in the graph. */ private Collection<Node> findAll(Parser parser) { final StartNode start = Parser.START; @@ -91,9 +106,12 @@ public class GraphVisualizer { */ 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); + all.put(n._nid, n); + for (Node c : n._inputs) + if (c != null) + walk(all, c); + for (Node c : n._outputs) + if (c != null) + walk(all, c); } } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/Parser.java b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java index 3ca13c3f..5422ea66 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java @@ -21,29 +21,34 @@ public class Parser { */ public static StartNode START; + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; - public Parser( String source ) { + + public Parser(String source) { _lexer = new Lexer(source); Node.reset(); START = new StartNode(); } + String src() { return new String( _lexer._input ); } + public ReturnNode parse() { require("return"); - return parseReturn(); + return (ReturnNode) parseReturn(); } /** - * Parses returnStatement; "return" already parsed + * Parses a return statement; "return" already parsed. * * <pre> * 'return' expr ; * </pre> + * @return an expression {@link Node}, never {@code null} */ - private ReturnNode parseReturn() { - var expr = require(parseExpression(),";"); - return new ReturnNode(START, expr); + private Node parseReturn() { + var expr = require(parseExpression(), ";"); + return new ReturnNode(START, expr).peephole(); } /** @@ -52,6 +57,7 @@ public class Parser { * <pre> * expr : additiveExpr * </pre> + * @return an expression {@link Node}, never {@code null} */ private Node parseExpression() { return parseAddition(); } @@ -61,11 +67,12 @@ public class Parser { * <pre> * additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)* * </pre> + * @return an add expression {@link Node}, never {@code null} */ private Node parseAddition() { var lhs = parseMultiplication(); - if( match("+") ) return new AddNode(lhs, parseAddition()).peephole(); - if( match("-") ) return new SubNode(lhs, parseAddition()).peephole(); + if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); + if (match("-")) return new SubNode(lhs, parseAddition()).peephole(); return lhs; } @@ -75,11 +82,12 @@ public class Parser { * <pre> * multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)* * </pre> + * @return a multiply expression {@link Node}, never {@code null} */ private Node parseMultiplication() { var lhs = parseUnary(); - if( match("*") ) return new MulNode(lhs, parseMultiplication()).peephole(); - if( match("/") ) return new DivNode(lhs, parseMultiplication()).peephole(); + if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole(); + if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole(); return lhs; } @@ -89,9 +97,10 @@ public class Parser { * <pre> * unaryExpr : ('-') unaryExpr | primaryExpr * </pre> + * @return a unary expression {@link Node}, never {@code null} */ private Node parseUnary() { - if( match("-") ) return new MinusNode(parseUnary()).peephole(); + if (match("-")) return new MinusNode(parseUnary()).peephole(); return parsePrimary(); } @@ -99,12 +108,13 @@ public class Parser { * Parse a primary expression: * * <pre> - * primaryExpr : integerLiteral + * primaryExpr : integerLiteral | Identifier | '(' expression ')' * </pre> + * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { if( _lexer.isNumber() ) return parseIntegerLiteral(); - if( match("(") ) return require(parseExpression(),")"); + if( match("(") ) return require(parseExpression(), ")"); throw errorSyntax("integer literal"); } @@ -116,7 +126,7 @@ public class Parser { * </pre> */ private ConstantNode parseIntegerLiteral() { - return (ConstantNode)new ConstantNode(_lexer.parseNumber()).peephole(); + return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); } ////////////////////////////////// @@ -126,7 +136,7 @@ public class Parser { private boolean match(String syntax) { return _lexer.match(syntax); } // Require an exact match - private void require(String syntax) { require(null,syntax); } + private void require(String syntax) { require(null, syntax); } private Node require(Node n, String syntax) { if (match(syntax)) return n; throw errorSyntax(syntax); @@ -135,7 +145,7 @@ public class Parser { RuntimeException errorSyntax(String syntax) { return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); } - + static RuntimeException error(String errorMessage) { return new RuntimeException(errorMessage); } @@ -167,9 +177,9 @@ public class Parser { // Very handy in the debugger, shows the unparsed program @Override public String toString() { - return new String(_input,_position,_input.length-_position); + return new String(_input, _position, _input.length - _position); } - + // True if at EOF private boolean isEOF() { return _position >= _input.length; @@ -203,12 +213,12 @@ public class Parser { // Return true, if we find "syntax" after skipping white space; also // then advance the cursor past syntax. // Return false otherwise, and do not advance the cursor. - boolean match( String syntax ) { + boolean match(String syntax) { skipWhiteSpace(); int len = syntax.length(); - if( _position + len > _input.length ) return false; - for( int i = 0; i < len; i++ ) - if( (char)_input[_position + i] != syntax.charAt(i) ) + if (_position + len > _input.length) return false; + for (int i = 0; i < len; i++) + if ((char) _input[_position + i] != syntax.charAt(i)) return false; _position += len; return true; @@ -216,14 +226,14 @@ public class Parser { // Used for errors String getAnyNextToken() { - if( isEOF() ) return ""; - if( isIdStart(peek()) ) return parseId(); - if( isPunctuation(peek()) ) return parsePunctuation(); + if (isEOF()) return ""; + if (isIdStart(peek())) return parseId(); + if (isPunctuation(peek())) return parsePunctuation(); return String.valueOf(peek()); } - boolean isNumber() { return isNumber(peek()); } - boolean isNumber(char ch) { return Character.isDigit(ch); } + boolean isNumber() {return isNumber(peek());} + boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { int start = _position; @@ -231,7 +241,7 @@ public class Parser { String snum = new String(_input, start, --_position - start); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); - return new TypeInteger(Long.parseLong(snum)); + return TypeInteger.constant(Long.parseLong(snum)); } // First letter of an identifier @@ -257,8 +267,7 @@ public class Parser { private String parsePunctuation() { int start = _position; - if (isPunctuation(nextChar())) ; - return new String(_input, start, --_position - start); + return new String(_input, start, 1); } } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java index 015779dc..6784ad60 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -3,17 +3,16 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.*; public class AddNode extends Node { - public AddNode(Node lhs, Node rhs) { - super(null, lhs, rhs); - } + public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } - @Override - public String label() { return "Add"; } + @Override public String label() { return "Add"; } + + @Override public String glabel() { return "+"; } @Override - StringBuilder _print(StringBuilder sb) { - in(1)._print(sb.append("(")); - in(2)._print(sb.append("+")); + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("+")); return sb.append(")"); } @@ -21,8 +20,9 @@ public class AddNode extends Node { @Override public Type compute() { if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) - return new TypeInteger(i0._con + i1._con); + in(2)._type instanceof TypeInteger i1 ) { + return TypeInteger.constant(i0.value()+i1.value()); + } return TypeBot.BOTTOM; } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 99ccf4b5..ec85bf1f 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -16,22 +16,25 @@ import com.seaofnodes.simple.type.Type; * The Constant's value is the value stored in it. */ public class ConstantNode extends Node { - + Type _con; public ConstantNode( Type type ) { super(Parser.START); - _type = type; + _con = type; } @Override - public String label() { return "Con" + _type; } + public String label() { return "#"+_con; } + + @Override + public String uniqueName() { return "Con_" + _nid; } @Override - StringBuilder _print(StringBuilder sb) { - return _type._print(sb); + StringBuilder _print1(StringBuilder sb) { + return _con._print(sb); } @Override - public Type compute() { return _type; } + public Type compute() { return _con; } @Override public Node idealize() { return null; } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter02/src/main/java/com/seaofnodes/simple/node/Control.java deleted file mode 100644 index 48cf2b7a..00000000 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/Control.java +++ /dev/null @@ -1,9 +0,0 @@ -package com.seaofnodes.simple.node; - - -/** - * Control interface is a marker interface to be implemented - * by Control nodes. - */ -public interface Control { -} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java index 0056c42d..ca7df79c 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -5,17 +5,16 @@ import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class DivNode extends Node { - public DivNode(Node lhs, Node rhs) { - super(null, lhs, rhs); - } + public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Div"; } + + @Override public String glabel() { return "//"; } @Override - public String label() { return "Div"; } - - @Override - StringBuilder _print(StringBuilder sb) { - in(1)._print(sb.append("(")); - in(2)._print(sb.append("/")); + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("/")); return sb.append(")"); } @@ -23,11 +22,9 @@ public class DivNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { - if (i0.isConstant() && i1.isConstant()) - return i1._con == 0 - ? TypeInteger.ZERO - : new TypeInteger(i0._con/i1._con); - return new TypeInteger(i0._con / i1._con); + return i1.value() == 0 + ? TypeInteger.ZERO + : TypeInteger.constant(i0.value()/i1.value()); } return TypeBot.BOTTOM; } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 7fab83b0..834f4c11 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -5,23 +5,22 @@ import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MinusNode extends Node { - public MinusNode(Node in) { - super(null, in); - } + public MinusNode(Node in) { super(null, in); } - @Override - public String label() { return "Minus"; } + @Override public String label() { return "Minus"; } + + @Override public String glabel() { return "-"; } @Override - StringBuilder _print(StringBuilder sb) { - in(1)._print(sb.append("(-")); + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(-")); return sb.append(")"); } @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0) - return new TypeInteger(-i0._con); + return TypeInteger.constant(-i0.value()); return TypeBot.BOTTOM; } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java index e1a26858..0fa54966 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -5,25 +5,25 @@ import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MulNode extends Node { - public MulNode(Node lhs, Node rhs) { - super(null, lhs, rhs); - } - - @Override - public String label() { return "Mul"; } + public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Mul"; } + @Override public String glabel() { return "*"; } + @Override - StringBuilder _print(StringBuilder sb) { - in(1)._print(sb.append("(")); - in(2)._print(sb.append("*")); + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("*")); return sb.append(")"); } - + @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) - return new TypeInteger(i0._con * i1._con); + in(2)._type instanceof TypeInteger i1) { + return TypeInteger.constant(i0.value()*i1.value()); + } return TypeBot.BOTTOM; } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java index 7c39083e..dbef984e 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java @@ -2,8 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import java.util.ArrayList; -import java.util.Collections; +import java.util.*; /** * All Nodes in the Sea of Nodes IR inherit from the Node class. @@ -24,8 +23,7 @@ public abstract class Node { * <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. - * @see Control + * The first input (offset 0) is often a {@link #isCFG} node. */ public final ArrayList<Node> _inputs; @@ -40,6 +38,13 @@ public abstract class Node { */ public final ArrayList<Node> _outputs; + + /** + * Current computed type for this Node. This value changes as the graph + * changes and more knowledge is gained about the program. + */ + public Type _type; + /** * A private Global Static mutable counter, for unique node id generation. * To make the compiler multi-threaded, this field will have to move into a TLS. @@ -47,7 +52,7 @@ public abstract class Node { * */ private static int UNIQUE_ID = 1; - protected Node(Node ...inputs) { + protected Node(Node... inputs) { _nid = UNIQUE_ID++; // allocate unique dense ID _inputs = new ArrayList<>(); Collections.addAll(_inputs,inputs); @@ -55,26 +60,39 @@ public abstract class Node { for( Node n : _inputs ) if( n != null ) n._outputs.add( this ); - // Do an initial type computation - _type = compute(); } + // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" public abstract String label(); + // Unique label for graph visualization, e.g. "Add12" or "Region30" or "EQ99" public String uniqueName() { return label() + _nid; } + // Graphical label, e.g. "+" or "Region" or "==" + public String glabel() { return label(); } + @Override public final String toString() { // TODO: This needs a lot of work - return uniqueName(); + return print(); } // This is a *deep* print. This version will fail on cycles, which we will - // correct later when we can parse programs with loops. + // correct later when we can parse programs with loops. We print with a + // tik-tok style; the common _print0 calls the per-Node _print1, which + // calls back to _print0; public final String print() { - return _print(new StringBuilder()).toString(); + return _print0(new StringBuilder()).toString(); + } + // This is the common print: check for DEAD and print "DEAD" else call the + // per-Node print1. + final StringBuilder _print0(StringBuilder sb) { + return isDead() + ? sb.append(uniqueName()).append(":DEAD") + : _print1(sb); } - abstract StringBuilder _print(StringBuilder sb); + // Every Node implements this. + abstract StringBuilder _print1(StringBuilder sb); /** @@ -86,25 +104,21 @@ public abstract class Node { public int nIns() { return _inputs.size(); } - /** - * Gets the ith output node - * @param i Offset of the output node - * @return Output node (not null) - */ - public Node out(int i) { return _outputs.get(i); } - public int nOuts() { return _outputs.size(); } + public boolean isUnused() { return nOuts() == 0; } + + public boolean isCFG() { return false; } + /** * We allow disabling peephole opt so that we can observe the * full graph, vs the optimized graph. */ public static boolean _disablePeephole = false; - /** * Try to peephole at this node and return a better replacement Node if - * possible. We check and replace: + * possible. We compute a {@link Type} and then check and replace: * <ul> * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> * <li>in a future chapter we will look for a @@ -114,19 +128,21 @@ public abstract class Node { * </ul> */ public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); + if (_disablePeephole) return this; // Peephole optimizations turned off // Replace constant computations from non-constants with a constant node - Type type = compute(); if (!(this instanceof ConstantNode) && type.isConstant()) { kill(); // Kill `this` because replacing with a Constant - return new ConstantNode(type); + return new ConstantNode(type).peephole(); } // Future chapter: Global Value Numbering goes here - // Ask each node for a replacement + // Ask each node for a better replacement Node n = idealize(); if( n != null ) return n; @@ -134,27 +150,17 @@ public abstract class Node { } /** - * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> - * to null. This may recursively kill more Nodes and is basically dead - * code elimination. This function is co-recursive with {@link #set_def}. - */ - void kill( ) { - assert nOuts()==0; // Has no uses, so it is dead - for( int i=0; i<nIns(); i++ ) - set_def(i,null); // Set all inputs to null, recursively killing unused Nodes - } - - /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing * the corresponding <em>use->def</em> edge. This may make the original * <em>def</em> go dead. This function is co-recursive with {@link #kill}. * * @param idx which def to set * @param new_def the new definition + * @return this for flow coding */ - void set_def(int idx, Node new_def ) { + Node set_def(int idx, Node new_def ) { Node old_def = in(idx); - if( old_def == new_def ) return; // No change + if( old_def == new_def ) return this; // No change // If new def is not null, add the corresponding def->use edge // This needs to happen before removing the old node's def->use edge as // the new_def might get killed if the old node kills it recursively. @@ -174,15 +180,26 @@ public abstract class Node { } // Set the new_def over the old (killed) edge _inputs.set(idx,new_def); + // Return self for easy flow-coding + return this; } - - /** - * Current computed type for this Node. This value changes as the graph - * changes and more knowledge is gained about the program. + * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> + * to null. This may recursively kill more Nodes and is basically dead + * code elimination. This function is co-recursive with {@link #set_def}. */ - public Type _type; - + public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + for( int i=0; i<nIns(); i++ ) + set_def(i,null); // Set all inputs to null, recursively killing unused Nodes + _inputs.clear(); + _type=null; // Flag as dead + assert isDead(); // Really dead now + } + + // Mostly used for asserts and printing. + boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + /** * This function needs to be * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> @@ -208,9 +225,4 @@ public abstract class Node { * Node unique id generator, and is done as part of making a new Parser. */ public static void reset() { UNIQUE_ID = 1; } - - /* - * hashCode and equals implementation to be added in later chapter. - */ - } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index c188ca79..18f5eed9 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.*; /** * The Return node has two inputs. The first input is a control node and the @@ -11,7 +11,7 @@ import com.seaofnodes.simple.type.TypeBot; * <p> * The Return's output is the value from the data node. */ -public class ReturnNode extends Node implements Control { +public class ReturnNode extends Node { public ReturnNode(Node ctrl, Node data) { super(ctrl, data); @@ -24,10 +24,11 @@ public class ReturnNode extends Node implements Control { public String label() { return "Return"; } @Override - StringBuilder _print(StringBuilder sb) { - return expr()._print(sb.append("return ")).append(";"); + StringBuilder _print1(StringBuilder sb) { + return expr()._print0(sb.append("return ")).append(";"); } + @Override public boolean isCFG() { return true; } @Override public TypeBot compute() { diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java index 8d8031bb..08b8333a 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,11 +3,13 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.TypeBot; /** - * 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. + * 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. */ -public class StartNode extends Node implements Control { +public class StartNode extends Node { public StartNode(/*arguments go here*/) { super(); @@ -17,10 +19,12 @@ public class StartNode extends Node implements Control { public String label() { return "Start"; } @Override - StringBuilder _print(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb) { return sb.append(label()); } - + + @Override public boolean isCFG() { return true; } + @Override public TypeBot compute() { return TypeBot.BOTTOM; diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java index 2d7db8d3..71d70fa6 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -5,25 +5,25 @@ import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class SubNode extends Node { - public SubNode(Node lhs, Node rhs) { - super(null, lhs, rhs); - } + public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); } - @Override - public String label() { return "Sub"; } + @Override public String label() { return "Sub"; } + + @Override public String glabel() { return "-"; } @Override - StringBuilder _print(StringBuilder sb) { - in(1)._print(sb.append("(")); - in(2)._print(sb.append("-")); + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("-")); return sb.append(")"); } @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) - return new TypeInteger(i0._con - i1._con); + in(2)._type instanceof TypeInteger i1) { + return TypeInteger.constant(i0.value()-i1.value()); + } return TypeBot.BOTTOM; } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java index 5284884a..bc191241 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java @@ -8,7 +8,7 @@ public class TypeBot extends Type { @Override public String toString() { return "Bottom"; } - - @Override + + @Override public StringBuilder _print(StringBuilder sb) { return sb.append(toString()); } } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 06cac15e..ff6e865b 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -14,6 +14,8 @@ public class TypeInteger extends Type { public TypeInteger(long con) { _con = con; } + public static TypeInteger constant(long con) { return new TypeInteger(con); } + @Override public String toString() { return _print(new StringBuilder()).toString(); @@ -25,7 +27,7 @@ public class TypeInteger extends Type { @Override public boolean isConstant() { return true; } - public long getConstant() { return _con; } + public long value() { return _con; } @Override public boolean equals( Object o ) { diff --git a/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 83cd7a0f..971b60ba 100644 --- a/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -1,16 +1,12 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.ConstantNode; -import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.ReturnNode; -import com.seaofnodes.simple.node.StartNode; +import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Rule; import org.junit.Test; import org.junit.rules.ExpectedException; -import static org.junit.Assert.assertEquals; -import static org.junit.Assert.fail; +import static org.junit.Assert.*; public class Chapter02Test { @@ -76,15 +72,13 @@ public class Chapter02Test { 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()); Node expr = ret.expr(); if( expr instanceof ConstantNode con ) { assertEquals(start,con.in(0)); - assertEquals(new TypeInteger(1), con._type); + assertEquals(TypeInteger.constant(1), con._type); } else { fail(); } @@ -97,21 +91,27 @@ public class Chapter02Test { StartNode start = Parser.START; for( Node use : start._outputs ) if( use instanceof ConstantNode con ) - assertEquals(new TypeInteger(0),con._type); + assertEquals(TypeInteger.constant(0),con._type); } @Test public void testBad1() { - exceptionRule.expect(RuntimeException.class); - exceptionRule.expectMessage("Syntax error, expected return: ret"); - new Parser("ret").parse(); + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected return: ret",e.getMessage()); + } } @Test public void testBad2() { - exceptionRule.expect(RuntimeException.class); - exceptionRule.expectMessage("Syntax error: integer values cannot start with '0'"); - new Parser("return 0123;").parse(); + try { + new Parser("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } } @Test @@ -122,9 +122,12 @@ public class Chapter02Test { @Test public void testBad4() { - exceptionRule.expect(RuntimeException.class); - exceptionRule.expectMessage("Syntax error, expected ;:"); - new Parser("return 100").parse(); + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } } @Test |
