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 /chapter03 | |
| 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 'chapter03')
22 files changed, 577 insertions, 435 deletions
diff --git a/chapter03/docs/03-graph1.gv b/chapter03/docs/03-graph1.gv index 5983f622..2bdca351 100644 --- a/chapter03/docs/03-graph1.gv +++ b/chapter03/docs/03-graph1.gv @@ -1,33 +1,39 @@ digraph chapter03 { +/* +int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph; +*/ rankdir=BT; + ordering="in"; + concentrate="true"; subgraph cluster_Nodes { - Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; - Con_2 [ label="#1" ]; - Con_3 [ label="#2" ]; - Con_5 [ label="#3" ]; - Add6 [ label="Add" ]; + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_6 [ label="#3" ]; + Add7 [ label="+" ]; } node [shape=plaintext]; - subgraph cluster_0 { - scope0 [label=< + subgraph cluster_Scope1_0 { + Scope1_0 [label=< <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> - <TR><TD BGCOLOR="aqua">0</TD><TD PORT="scope0_a">a</TD><TD PORT="scope0_b">b</TD><TD PORT="scope0_c">c</TD></TR> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_a">a</TD><TD PORT="Scope1_0_b">b</TD><TD PORT="Scope1_0_c">c</TD></TR> </TABLE>>]; - subgraph cluster_1 { - scope1 [label=< + subgraph cluster_Scope1_1 { + Scope1_1 [label=< <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> - <TR><TD BGCOLOR="aqua">1</TD><TD PORT="scope1_b">b</TD></TR> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope1_1_b">b</TD></TR> </TABLE>>]; } } - Con_2 -> Start1 [style=dotted]; - Con_3 -> Start1 [style=dotted]; - Con_5 -> Start1 [style=dotted]; - Add6 -> Con_2; - Add6 -> Con_5; + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_6 -> Start2[taillabel=0 style=dotted]; + Add7 -> Con_3[taillabel=1]; + Add7 -> Con_6[taillabel=2]; edge [style=dashed color=cornflowerblue]; - scope0:scope0_a -> Con_2; - scope0:scope0_b -> Con_3; - scope0:scope0_c -> Add6; - scope1:scope1_b -> Con_5; + Scope1_0:"Scope1_0_a" -> Con_3; + Scope1_0:"Scope1_0_b" -> Con_4; + Scope1_0:"Scope1_0_c" -> Add7; + Scope1_1:"Scope1_1_b" -> Con_6; } diff --git a/chapter03/docs/03-graph1.svg b/chapter03/docs/03-graph1.svg index 364cd42c..ab6f9600 100644 --- a/chapter03/docs/03-graph1.svg +++ b/chapter03/docs/03-graph1.svg @@ -14,77 +14,82 @@ <polygon fill="none" stroke="black" points="8,-88 8,-284 222,-284 222,-88 8,-88"/> </g> <g id="clust2" class="cluster"> -<title>cluster_0</title> +<title>cluster_Scope1_0</title> <polygon fill="none" stroke="black" points="36,-8 36,-76 210,-76 210,-8 36,-8"/> </g> <g id="clust3" class="cluster"> -<title>cluster_1</title> +<title>cluster_Scope1_1</title> <polygon fill="none" stroke="black" points="132,-16 132,-68 202,-68 202,-16 132,-16"/> </g> -<!-- Start1 --> +<!-- Start2 --> <g id="node1" class="node"> -<title>Start1</title> +<title>Start2</title> <polygon fill="yellow" stroke="black" points="142,-276 88,-276 88,-240 142,-240 142,-276"/> <text text-anchor="middle" x="115" y="-254.3" font-family="Times,serif" font-size="14.00">Start</text> </g> -<!-- Con_2 --> +<!-- Con_3 --> <g id="node2" class="node"> -<title>Con_2</title> +<title>Con_3</title> <ellipse fill="none" stroke="black" cx="43" cy="-186" rx="27" ry="18"/> <text text-anchor="middle" x="43" y="-182.3" font-family="Times,serif" font-size="14.00">#1</text> </g> -<!-- Con_2->Start1 --> +<!-- Con_3->Start2 --> <g id="edge1" class="edge"> -<title>Con_2->Start1</title> +<title>Con_3->Start2</title> <path fill="none" stroke="black" stroke-dasharray="1,5" d="M57.57,-201.17C66.92,-210.25 79.3,-222.29 90.17,-232.86"/> <polygon fill="black" stroke="black" points="87.79,-235.43 97.4,-239.89 92.67,-230.41 87.79,-235.43"/> +<text text-anchor="middle" x="54.57" y="-203.77" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Con_3 --> +<!-- Con_4 --> <g id="node3" class="node"> -<title>Con_3</title> +<title>Con_4</title> <ellipse fill="none" stroke="black" cx="115" cy="-186" rx="27" ry="18"/> <text text-anchor="middle" x="115" y="-182.3" font-family="Times,serif" font-size="14.00">#2</text> </g> -<!-- Con_3->Start1 --> +<!-- Con_4->Start2 --> <g id="edge2" class="edge"> -<title>Con_3->Start1</title> +<title>Con_4->Start2</title> <path fill="none" stroke="black" stroke-dasharray="1,5" d="M115,-204.3C115,-212.02 115,-221.29 115,-229.89"/> <polygon fill="black" stroke="black" points="111.5,-229.9 115,-239.9 118.5,-229.9 111.5,-229.9"/> +<text text-anchor="middle" x="112" y="-206.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Con_5 --> +<!-- Con_6 --> <g id="node4" class="node"> -<title>Con_5</title> +<title>Con_6</title> <ellipse fill="none" stroke="black" cx="187" cy="-186" rx="27" ry="18"/> <text text-anchor="middle" x="187" y="-182.3" font-family="Times,serif" font-size="14.00">#3</text> </g> -<!-- Con_5->Start1 --> +<!-- Con_6->Start2 --> <g id="edge3" class="edge"> -<title>Con_5->Start1</title> +<title>Con_6->Start2</title> <path fill="none" stroke="black" stroke-dasharray="1,5" d="M172.43,-201.17C163.08,-210.25 150.7,-222.29 139.83,-232.86"/> <polygon fill="black" stroke="black" points="137.33,-230.41 132.6,-239.89 142.21,-235.43 137.33,-230.41"/> +<text text-anchor="middle" x="169.43" y="-203.77" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Add6 --> +<!-- Add7 --> <g id="node5" class="node"> -<title>Add6</title> -<ellipse fill="none" stroke="black" cx="138" cy="-114" rx="28.7" ry="18"/> -<text text-anchor="middle" x="138" y="-110.3" font-family="Times,serif" font-size="14.00">Add</text> +<title>Add7</title> +<ellipse fill="none" stroke="black" cx="136" cy="-114" rx="27" ry="18"/> +<text text-anchor="middle" x="136" y="-110.3" font-family="Times,serif" font-size="14.00">+</text> </g> -<!-- Add6->Con_2 --> +<!-- Add7->Con_3 --> <g id="edge4" class="edge"> -<title>Add6->Con_2</title> -<path fill="none" stroke="black" d="M120.13,-128.17C105.58,-138.89 84.84,-154.17 68.53,-166.18"/> -<polygon fill="black" stroke="black" points="66.44,-163.38 60.47,-172.13 70.59,-169.01 66.44,-163.38"/> +<title>Add7->Con_3</title> +<path fill="none" stroke="black" d="M118.51,-128.17C104.48,-138.73 84.58,-153.7 68.74,-165.63"/> +<polygon fill="black" stroke="black" points="66.3,-163.08 60.41,-171.89 70.51,-168.68 66.3,-163.08"/> +<text text-anchor="middle" x="115.51" y="-130.77" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </g> -<!-- Add6->Con_5 --> +<!-- Add7->Con_6 --> <g id="edge5" class="edge"> -<title>Add6->Con_5</title> -<path fill="none" stroke="black" d="M149.12,-130.88C155.32,-139.74 163.17,-150.96 170.12,-160.88"/> -<polygon fill="black" stroke="black" points="167.32,-162.99 175.93,-169.18 173.06,-158.98 167.32,-162.99"/> +<title>Add7->Con_6</title> +<path fill="none" stroke="black" d="M147.32,-130.54C153.92,-139.6 162.38,-151.21 169.8,-161.39"/> +<polygon fill="black" stroke="black" points="167,-163.49 175.71,-169.51 172.65,-159.36 167,-163.49"/> +<text text-anchor="middle" x="144.32" y="-133.14" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> </g> -<!-- scope0 --> +<!-- Scope1_0 --> <g id="node6" class="node"> -<title>scope0</title> -<polygon fill="aqua" stroke="transparent" points="53,-31 53,-52 69,-52 69,-31 53,-31"/> +<title>Scope1_0</title> +<polygon fill="cyan" stroke="transparent" points="53,-31 53,-52 69,-52 69,-31 53,-31"/> <polygon fill="none" stroke="black" points="53,-31 53,-52 69,-52 69,-31 53,-31"/> <text text-anchor="start" x="56" y="-37.8" font-family="Times,serif" font-size="14.00">0</text> <polygon fill="none" stroke="black" points="69,-31 69,-52 84,-52 84,-31 69,-31"/> @@ -94,36 +99,36 @@ <polygon fill="none" stroke="black" points="100,-31 100,-52 114,-52 114,-31 100,-31"/> <text text-anchor="start" x="103" y="-37.8" font-family="Times,serif" font-size="14.00">c</text> </g> -<!-- scope0->Con_2 --> +<!-- Scope1_0->Con_3 --> <g id="edge6" class="edge"> -<title>scope0:scope0_a->Con_2</title> +<title>Scope1_0:Scope1_0_a->Con_3</title> <path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M76,-53C76,-90.54 63.29,-132.33 53.64,-158.64"/> <polygon fill="cornflowerblue" stroke="cornflowerblue" points="50.27,-157.66 50,-168.25 56.81,-160.14 50.27,-157.66"/> </g> -<!-- scope0->Con_3 --> +<!-- Scope1_0->Con_4 --> <g id="edge7" class="edge"> -<title>scope0:scope0_b->Con_3</title> +<title>Scope1_0:Scope1_0_b->Con_4</title> <path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M92,-53C92,-88.29 93.39,-97.33 100,-132 101.65,-140.68 104.07,-150 106.48,-158.37"/> <polygon fill="cornflowerblue" stroke="cornflowerblue" points="103.14,-159.42 109.37,-168 109.85,-157.41 103.14,-159.42"/> </g> -<!-- scope0->Add6 --> +<!-- Scope1_0->Add7 --> <g id="edge8" class="edge"> -<title>scope0:scope0_c->Add6</title> -<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M107,-53C107,-65.88 112.71,-78.75 119.22,-89.25"/> -<polygon fill="cornflowerblue" stroke="cornflowerblue" points="116.52,-91.5 125.03,-97.81 122.31,-87.57 116.52,-91.5"/> +<title>Scope1_0:Scope1_0_c->Add7</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M107,-53C107,-65.71 112.34,-78.55 118.43,-89.08"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="115.57,-91.1 123.87,-97.68 121.48,-87.35 115.57,-91.1"/> </g> -<!-- scope1 --> +<!-- Scope1_1 --> <g id="node7" class="node"> -<title>scope1</title> -<polygon fill="aqua" stroke="transparent" points="151,-31 151,-52 167,-52 167,-31 151,-31"/> +<title>Scope1_1</title> +<polygon fill="cyan" stroke="transparent" points="151,-31 151,-52 167,-52 167,-31 151,-31"/> <polygon fill="none" stroke="black" points="151,-31 151,-52 167,-52 167,-31 151,-31"/> <text text-anchor="start" x="154" y="-37.8" font-family="Times,serif" font-size="14.00">1</text> <polygon fill="none" stroke="black" points="167,-31 167,-52 183,-52 183,-31 167,-31"/> <text text-anchor="start" x="170" y="-37.8" font-family="Times,serif" font-size="14.00">b</text> </g> -<!-- scope1->Con_5 --> +<!-- Scope1_1->Con_6 --> <g id="edge9" class="edge"> -<title>scope1:scope1_b->Con_5</title> +<title>Scope1_1:Scope1_1_b->Con_6</title> <path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M175,-53C175,-89.4 179.58,-131.23 183.08,-157.87"/> <polygon fill="cornflowerblue" stroke="cornflowerblue" points="179.64,-158.52 184.46,-167.96 186.58,-157.58 179.64,-158.52"/> </g> diff --git a/chapter03/docs/03-graph2.gv b/chapter03/docs/03-graph2.gv index c6c55028..f570b13e 100644 --- a/chapter03/docs/03-graph2.gv +++ b/chapter03/docs/03-graph2.gv @@ -1,29 +1,35 @@ digraph chapter03 { +/* +int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph; +*/ rankdir=BT; + ordering="in"; + concentrate="true"; subgraph cluster_Nodes { - Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; - Con_2 [ label="#1" ]; - Con_3 [ label="#2" ]; - Con_5 [ label="#3" ]; - Add6 [ label="Add" ]; - Return7 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_6 [ label="#3" ]; + Add7 [ label="+" ]; + Return8 [ shape=box style=filled fillcolor=yellow label="Return" ]; } node [shape=plaintext]; - subgraph cluster_0 { - scope0 [label=< + subgraph cluster_Scope1_0 { + Scope1_0 [label=< <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> - <TR><TD BGCOLOR="aqua">0</TD><TD PORT="scope0_a">a</TD><TD PORT="scope0_b">b</TD><TD PORT="scope0_c">c</TD></TR> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_a">a</TD><TD PORT="Scope1_0_b">b</TD><TD PORT="Scope1_0_c">c</TD></TR> </TABLE>>]; } - Con_2 -> Start1 [style=dotted]; - Con_3 -> Start1 [style=dotted]; - Con_5 -> Start1 [style=dotted]; - Add6 -> Con_2; - Add6 -> Con_5; - Return7 -> Start1 [color=red]; - Return7 -> Add6; + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_6 -> Start2[taillabel=0 style=dotted]; + Add7 -> Con_3[taillabel=1]; + Add7 -> Con_6[taillabel=2]; + Return8 -> Start2[taillabel=0 color=red]; + Return8 -> Add7[taillabel=1]; edge [style=dashed color=cornflowerblue]; - scope0:scope0_a -> Con_2; - scope0:scope0_b -> Con_3; - scope0:scope0_c -> Add6; -} + Scope1_0:"Scope1_0_a" -> Con_3; + Scope1_0:"Scope1_0_b" -> Con_4; + Scope1_0:"Scope1_0_c" -> Add7; +}
\ No newline at end of file diff --git a/chapter03/docs/03-graph2.svg b/chapter03/docs/03-graph2.svg index 4ab5a8b6..0a539c6a 100644 --- a/chapter03/docs/03-graph2.svg +++ b/chapter03/docs/03-graph2.svg @@ -14,91 +14,98 @@ <polygon fill="none" stroke="black" points="8,-8 8,-276 242,-276 242,-8 8,-8"/> </g> <g id="clust2" class="cluster"> -<title>cluster_0</title> +<title>cluster_Scope1_0</title> <polygon fill="none" stroke="black" points="250,-8 250,-60 344,-60 344,-8 250,-8"/> </g> -<!-- Start1 --> +<!-- Start2 --> <g id="node1" class="node"> -<title>Start1</title> +<title>Start2</title> <polygon fill="yellow" stroke="black" points="126,-268 72,-268 72,-232 126,-232 126,-268"/> <text text-anchor="middle" x="99" y="-246.3" font-family="Times,serif" font-size="14.00">Start</text> </g> -<!-- Con_2 --> +<!-- Con_3 --> <g id="node2" class="node"> -<title>Con_2</title> +<title>Con_3</title> <ellipse fill="none" stroke="black" cx="135" cy="-178" rx="27" ry="18"/> <text text-anchor="middle" x="135" y="-174.3" font-family="Times,serif" font-size="14.00">#1</text> </g> -<!-- Con_2->Start1 --> +<!-- Con_3->Start2 --> <g id="edge1" class="edge"> -<title>Con_2->Start1</title> +<title>Con_3->Start2</title> <path fill="none" stroke="black" stroke-dasharray="1,5" d="M126.65,-195.24C122.46,-203.39 117.27,-213.47 112.53,-222.69"/> <polygon fill="black" stroke="black" points="109.27,-221.38 107.81,-231.88 115.49,-224.58 109.27,-221.38"/> +<text text-anchor="middle" x="123.65" y="-197.84" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Con_3 --> +<!-- Con_4 --> <g id="node3" class="node"> -<title>Con_3</title> +<title>Con_4</title> <ellipse fill="none" stroke="black" cx="207" cy="-178" rx="27" ry="18"/> <text text-anchor="middle" x="207" y="-174.3" font-family="Times,serif" font-size="14.00">#2</text> </g> -<!-- Con_3->Start1 --> +<!-- Con_4->Start2 --> <g id="edge2" class="edge"> -<title>Con_3->Start1</title> +<title>Con_4->Start2</title> <path fill="none" stroke="black" stroke-dasharray="1,5" d="M188.19,-191.19C173.23,-200.89 151.89,-214.72 133.84,-226.42"/> <polygon fill="black" stroke="black" points="131.77,-223.59 125.28,-231.97 135.58,-229.46 131.77,-223.59"/> +<text text-anchor="middle" x="185.19" y="-193.79" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Con_5 --> +<!-- Con_6 --> <g id="node4" class="node"> -<title>Con_5</title> +<title>Con_6</title> <ellipse fill="none" stroke="black" cx="63" cy="-178" rx="27" ry="18"/> <text text-anchor="middle" x="63" y="-174.3" font-family="Times,serif" font-size="14.00">#3</text> </g> -<!-- Con_5->Start1 --> +<!-- Con_6->Start2 --> <g id="edge3" class="edge"> -<title>Con_5->Start1</title> +<title>Con_6->Start2</title> <path fill="none" stroke="black" stroke-dasharray="1,5" d="M71.35,-195.24C75.54,-203.39 80.73,-213.47 85.47,-222.69"/> <polygon fill="black" stroke="black" points="82.51,-224.58 90.19,-231.88 88.73,-221.38 82.51,-224.58"/> +<text text-anchor="middle" x="68.35" y="-197.84" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Add6 --> +<!-- Add7 --> <g id="node5" class="node"> -<title>Add6</title> -<ellipse fill="none" stroke="black" cx="89" cy="-106" rx="28.7" ry="18"/> -<text text-anchor="middle" x="89" y="-102.3" font-family="Times,serif" font-size="14.00">Add</text> +<title>Add7</title> +<ellipse fill="none" stroke="black" cx="71" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="71" y="-102.3" font-family="Times,serif" font-size="14.00">+</text> </g> -<!-- Add6->Con_2 --> +<!-- Add7->Con_3 --> <g id="edge4" class="edge"> -<title>Add6->Con_2</title> -<path fill="none" stroke="black" d="M99.44,-122.88C105.2,-131.66 112.48,-142.74 118.96,-152.58"/> -<polygon fill="black" stroke="black" points="116.19,-154.74 124.6,-161.18 122.04,-150.9 116.19,-154.74"/> +<title>Add7->Con_3</title> +<path fill="none" stroke="black" d="M84.57,-121.85C93.31,-131.4 104.83,-144.01 114.66,-154.75"/> +<polygon fill="black" stroke="black" points="112.12,-157.16 121.45,-162.18 117.28,-152.43 112.12,-157.16"/> +<text text-anchor="middle" x="81.57" y="-124.45" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </g> -<!-- Add6->Con_5 --> +<!-- Add7->Con_6 --> <g id="edge5" class="edge"> -<title>Add6->Con_5</title> -<path fill="none" stroke="black" d="M82.84,-123.59C79.84,-131.66 76.16,-141.57 72.79,-150.65"/> -<polygon fill="black" stroke="black" points="69.5,-149.45 69.3,-160.04 76.06,-151.89 69.5,-149.45"/> +<title>Add7->Con_6</title> +<path fill="none" stroke="black" d="M69.02,-124.3C68.14,-132.02 67.08,-141.29 66.1,-149.89"/> +<polygon fill="black" stroke="black" points="62.61,-149.56 64.95,-159.9 69.57,-150.36 62.61,-149.56"/> +<text text-anchor="middle" x="66.02" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> </g> -<!-- Return7 --> +<!-- Return8 --> <g id="node6" class="node"> -<title>Return7</title> -<polygon fill="yellow" stroke="black" points="96,-52 30,-52 30,-16 96,-16 96,-52"/> -<text text-anchor="middle" x="63" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> +<title>Return8</title> +<polygon fill="yellow" stroke="black" points="89,-52 23,-52 23,-16 89,-16 89,-52"/> +<text text-anchor="middle" x="56" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> </g> -<!-- Return7->Start1 --> +<!-- Return8->Start2 --> <g id="edge6" class="edge"> -<title>Return7->Start1</title> -<path fill="none" stroke="red" d="M51.87,-52.38C33.84,-82.96 2.57,-147.69 27,-196 34.7,-211.23 49.06,-223.15 62.94,-231.8"/> +<title>Return8->Start2</title> +<path fill="none" stroke="red" d="M46.1,-52.47C30.13,-83.17 2.78,-148.1 27,-196 34.7,-211.23 49.06,-223.15 62.94,-231.8"/> <polygon fill="red" stroke="red" points="61.52,-235.02 71.92,-237.01 65.03,-228.96 61.52,-235.02"/> +<text text-anchor="middle" x="43.1" y="-55.07" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Return7->Add6 --> +<!-- Return8->Add7 --> <g id="edge7" class="edge"> -<title>Return7->Add6</title> -<path fill="none" stroke="black" d="M69.43,-52.3C72.4,-60.3 75.99,-69.98 79.29,-78.85"/> -<polygon fill="black" stroke="black" points="76.06,-80.22 82.83,-88.38 82.63,-77.78 76.06,-80.22"/> +<title>Return8->Add7</title> +<path fill="none" stroke="black" d="M59.71,-52.3C61.36,-60.02 63.35,-69.29 65.19,-77.89"/> +<polygon fill="black" stroke="black" points="61.82,-78.85 67.33,-87.9 68.66,-77.38 61.82,-78.85"/> +<text text-anchor="middle" x="56.71" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </g> -<!-- scope0 --> +<!-- Scope1_0 --> <g id="node7" class="node"> -<title>scope0</title> -<polygon fill="aqua" stroke="transparent" points="267,-23 267,-44 283,-44 283,-23 267,-23"/> +<title>Scope1_0</title> +<polygon fill="cyan" stroke="transparent" points="267,-23 267,-44 283,-44 283,-23 267,-23"/> <polygon fill="none" stroke="black" points="267,-23 267,-44 283,-44 283,-23 267,-23"/> <text text-anchor="start" x="270" y="-29.8" font-family="Times,serif" font-size="14.00">0</text> <polygon fill="none" stroke="black" points="283,-23 283,-44 298,-44 298,-23 283,-23"/> @@ -108,23 +115,23 @@ <polygon fill="none" stroke="black" points="314,-23 314,-44 328,-44 328,-23 314,-23"/> <text text-anchor="start" x="317" y="-29.8" font-family="Times,serif" font-size="14.00">c</text> </g> -<!-- scope0->Con_2 --> +<!-- Scope1_0->Con_3 --> <g id="edge8" class="edge"> -<title>scope0:scope0_a->Con_2</title> +<title>Scope1_0:Scope1_0_a->Con_3</title> <path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M290,-45C290,-77.9 208.02,-132.76 163.3,-160.24"/> <polygon fill="cornflowerblue" stroke="cornflowerblue" points="161.36,-157.33 154.63,-165.51 164.99,-163.31 161.36,-157.33"/> </g> -<!-- scope0->Con_3 --> +<!-- Scope1_0->Con_4 --> <g id="edge9" class="edge"> -<title>scope0:scope0_b->Con_3</title> +<title>Scope1_0:Scope1_0_b->Con_4</title> <path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M306,-45C306,-93.23 263.17,-135.12 233.85,-158.15"/> <polygon fill="cornflowerblue" stroke="cornflowerblue" points="231.47,-155.56 225.62,-164.4 235.7,-161.14 231.47,-155.56"/> </g> -<!-- scope0->Add6 --> +<!-- Scope1_0->Add7 --> <g id="edge10" class="edge"> -<title>scope0:scope0_c->Add6</title> -<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M321,-45C321,-86.77 178.12,-76.36 138,-88 132.99,-89.45 127.75,-91.12 122.62,-92.82"/> -<polygon fill="cornflowerblue" stroke="cornflowerblue" points="121.34,-89.56 113.02,-96.11 123.61,-96.18 121.34,-89.56"/> +<title>Scope1_0:Scope1_0_c->Add7</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M321,-45C321,-86.77 178.58,-78.08 138,-88 127.51,-90.56 116.11,-93.43 105.75,-96.06"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="104.62,-92.74 95.79,-98.6 106.35,-99.52 104.62,-92.74"/> </g> </g> </svg> diff --git a/chapter03/docs/03-graph3.gv b/chapter03/docs/03-graph3.gv index 717024e3..50cb6d27 100644 --- a/chapter03/docs/03-graph3.gv +++ b/chapter03/docs/03-graph3.gv @@ -1,32 +1,37 @@ digraph chapter03 { +/* +int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph; +*/ rankdir=BT; + ordering="in"; + concentrate="true"; subgraph cluster_Nodes { - Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; - Con_2 [ label="#1" ]; - Con_3 [ label="#2" ]; - Con_19 [ label="#8" ]; - Con_4 [ label="#3" ]; - Return20 [ shape=box style=filled fillcolor=yellow label="Return" ]; - Con_5 [ label="#4" ]; + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_20 [ label="#8" ]; + Con_5 [ label="#3" ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_6 [ label="#4" ]; } node [shape=plaintext]; - subgraph cluster_0 { - scope0 [label=< + subgraph cluster_Scope1_0 { + Scope1_0 [label=< <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> - <TR><TD BGCOLOR="cyan">0</TD><TD PORT="scope0_y0">y0</TD><TD PORT="scope0_x0">x0</TD><TD PORT="scope0_y1">y1</TD><TD PORT="scope0_x1">x1</TD></TR> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_y0">y0</TD><TD PORT="Scope1_0_x0">x0</TD><TD PORT="Scope1_0_y1">y1</TD><TD PORT="Scope1_0_x1">x1</TD></TR> </TABLE>>]; } - Con_2 -> Start1 [style=dotted]; - Con_3 -> Start1 [style=dotted]; - Con_19 -> Start1 [style=dotted]; - Con_4 -> Start1 [style=dotted]; - Return20 -> Start1 [color=red]; - Return20 -> Con_19; - Con_5 -> Start1 [style=dotted]; + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_20 -> Start2[taillabel=0 style=dotted]; + Con_5 -> Start2[taillabel=0 style=dotted]; + Return21 -> Start2[taillabel=0 color=red]; + Return21 -> Con_20[taillabel=1]; + Con_6 -> Start2[taillabel=0 style=dotted]; edge [style=dashed color=cornflowerblue]; - scope0:scope0_y0 -> Con_3; - scope0:scope0_x0 -> Con_2; - scope0:scope0_y1 -> Con_5; - scope0:scope0_x1 -> Con_4; + Scope1_0:"Scope1_0_y0" -> Con_4; + Scope1_0:"Scope1_0_x0" -> Con_3; + Scope1_0:"Scope1_0_y1" -> Con_6; + Scope1_0:"Scope1_0_x1" -> Con_5; } - diff --git a/chapter03/docs/03-graph3.svg b/chapter03/docs/03-graph3.svg index 3b720323..623bd902 100644 --- a/chapter03/docs/03-graph3.svg +++ b/chapter03/docs/03-graph3.svg @@ -14,96 +14,103 @@ <polygon fill="none" stroke="black" points="8,-8 8,-204 386,-204 386,-8 8,-8"/> </g> <g id="clust2" class="cluster"> -<title>cluster_0</title> +<title>cluster_Scope1_0</title> <polygon fill="none" stroke="black" points="394,-8 394,-60 538,-60 538,-8 394,-8"/> </g> -<!-- Start1 --> +<!-- Start2 --> <g id="node1" class="node"> -<title>Start1</title> +<title>Start2</title> <polygon fill="yellow" stroke="black" points="198,-196 144,-196 144,-160 198,-160 198,-196"/> <text text-anchor="middle" x="171" y="-174.3" font-family="Times,serif" font-size="14.00">Start</text> </g> -<!-- Con_2 --> +<!-- Con_3 --> <g id="node2" class="node"> -<title>Con_2</title> +<title>Con_3</title> <ellipse fill="none" stroke="black" cx="207" cy="-106" rx="27" ry="18"/> <text text-anchor="middle" x="207" y="-102.3" font-family="Times,serif" font-size="14.00">#1</text> </g> -<!-- Con_2->Start1 --> +<!-- Con_3->Start2 --> <g id="edge1" class="edge"> -<title>Con_2->Start1</title> +<title>Con_3->Start2</title> <path fill="none" stroke="black" stroke-dasharray="1,5" d="M198.65,-123.24C194.46,-131.39 189.27,-141.47 184.53,-150.69"/> <polygon fill="black" stroke="black" points="181.27,-149.38 179.81,-159.88 187.49,-152.58 181.27,-149.38"/> +<text text-anchor="middle" x="195.65" y="-125.84" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Con_3 --> +<!-- Con_4 --> <g id="node3" class="node"> -<title>Con_3</title> +<title>Con_4</title> <ellipse fill="none" stroke="black" cx="135" cy="-106" rx="27" ry="18"/> <text text-anchor="middle" x="135" y="-102.3" font-family="Times,serif" font-size="14.00">#2</text> </g> -<!-- Con_3->Start1 --> +<!-- Con_4->Start2 --> <g id="edge2" class="edge"> -<title>Con_3->Start1</title> +<title>Con_4->Start2</title> <path fill="none" stroke="black" stroke-dasharray="1,5" d="M143.35,-123.24C147.54,-131.39 152.73,-141.47 157.47,-150.69"/> <polygon fill="black" stroke="black" points="154.51,-152.58 162.19,-159.88 160.73,-149.38 154.51,-152.58"/> +<text text-anchor="middle" x="140.35" y="-125.84" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Con_19 --> +<!-- Con_20 --> <g id="node4" class="node"> -<title>Con_19</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">#8</text> +<title>Con_20</title> +<ellipse fill="none" stroke="black" cx="63" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-102.3" font-family="Times,serif" font-size="14.00">#8</text> </g> -<!-- Con_19->Start1 --> +<!-- Con_20->Start2 --> <g id="edge3" class="edge"> -<title>Con_19->Start1</title> -<path fill="none" stroke="black" stroke-dasharray="1,5" d="M63.28,-118.09C82.45,-128.57 111.64,-144.54 134.8,-157.2"/> -<polygon fill="black" stroke="black" points="133.21,-160.32 143.67,-162.05 136.57,-154.18 133.21,-160.32"/> +<title>Con_20->Start2</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M81.81,-119.19C96.77,-128.89 118.11,-142.72 136.16,-154.42"/> +<polygon fill="black" stroke="black" points="134.42,-157.46 144.72,-159.97 138.23,-151.59 134.42,-157.46"/> +<text text-anchor="middle" x="78.81" y="-121.79" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Con_4 --> +<!-- Con_5 --> <g id="node5" class="node"> -<title>Con_4</title> +<title>Con_5</title> <ellipse fill="none" stroke="black" cx="351" cy="-106" rx="27" ry="18"/> <text text-anchor="middle" x="351" y="-102.3" font-family="Times,serif" font-size="14.00">#3</text> </g> -<!-- Con_4->Start1 --> +<!-- Con_5->Start2 --> <g id="edge4" class="edge"> -<title>Con_4->Start1</title> +<title>Con_5->Start2</title> <path fill="none" stroke="black" stroke-dasharray="1,5" d="M329.82,-117.38C324.99,-119.65 319.84,-121.97 315,-124 279.07,-139.06 237.19,-154.21 207.89,-164.43"/> <polygon fill="black" stroke="black" points="206.38,-161.25 198.08,-167.84 208.68,-167.87 206.38,-161.25"/> +<text text-anchor="middle" x="326.82" y="-119.98" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Return20 --> +<!-- Return21 --> <g id="node6" class="node"> -<title>Return20</title> -<polygon fill="yellow" stroke="black" points="102,-52 36,-52 36,-16 102,-16 102,-52"/> -<text text-anchor="middle" x="69" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> +<title>Return21</title> +<polygon fill="yellow" stroke="black" points="89,-52 23,-52 23,-16 89,-16 89,-52"/> +<text text-anchor="middle" x="56" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> </g> -<!-- Return20->Start1 --> +<!-- Return21->Start2 --> <g id="edge5" class="edge"> -<title>Return20->Start1</title> -<path fill="none" stroke="red" d="M71.6,-52.16C75.16,-71.21 83.04,-102.14 99,-124 108.52,-137.04 122.19,-148.23 135.06,-156.92"/> -<polygon fill="red" stroke="red" points="133.48,-160.07 143.79,-162.53 137.27,-154.18 133.48,-160.07"/> +<title>Return21->Start2</title> +<path fill="none" stroke="red" d="M42.04,-52.06C28.34,-71.02 11.57,-101.87 27,-124 50.89,-158.26 99.53,-170.43 133.64,-174.72"/> +<polygon fill="red" stroke="red" points="133.4,-178.22 143.72,-175.82 134.16,-171.26 133.4,-178.22"/> +<text text-anchor="middle" x="39.04" y="-54.66" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Return20->Con_19 --> +<!-- Return21->Con_20 --> <g id="edge6" class="edge"> -<title>Return20->Con_19</title> -<path fill="none" stroke="black" d="M62.57,-52.3C59.6,-60.3 56.01,-69.98 52.71,-78.85"/> -<polygon fill="black" stroke="black" points="49.37,-77.78 49.17,-88.38 55.94,-80.22 49.37,-77.78"/> +<title>Return21->Con_20</title> +<path fill="none" stroke="black" d="M57.73,-52.3C58.5,-60.02 59.43,-69.29 60.29,-77.89"/> +<polygon fill="black" stroke="black" points="56.81,-78.29 61.29,-87.9 63.78,-77.6 56.81,-78.29"/> +<text text-anchor="middle" x="54.73" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </g> -<!-- Con_5 --> +<!-- Con_6 --> <g id="node7" class="node"> -<title>Con_5</title> +<title>Con_6</title> <ellipse fill="none" stroke="black" cx="279" cy="-106" rx="27" ry="18"/> <text text-anchor="middle" x="279" y="-102.3" font-family="Times,serif" font-size="14.00">#4</text> </g> -<!-- Con_5->Start1 --> +<!-- Con_6->Start2 --> <g id="edge7" class="edge"> -<title>Con_5->Start1</title> +<title>Con_6->Start2</title> <path fill="none" stroke="black" stroke-dasharray="1,5" d="M260.19,-119.19C245.23,-128.89 223.89,-142.72 205.84,-154.42"/> <polygon fill="black" stroke="black" points="203.77,-151.59 197.28,-159.97 207.58,-157.46 203.77,-151.59"/> +<text text-anchor="middle" x="257.19" y="-121.79" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- scope0 --> +<!-- Scope1_0 --> <g id="node8" class="node"> -<title>scope0</title> +<title>Scope1_0</title> <polygon fill="cyan" stroke="transparent" points="410,-23 410,-44 426,-44 426,-23 410,-23"/> <polygon fill="none" stroke="black" points="410,-23 410,-44 426,-44 426,-23 410,-23"/> <text text-anchor="start" x="413" y="-29.8" font-family="Times,serif" font-size="14.00">0</text> @@ -116,27 +123,27 @@ <polygon fill="none" stroke="black" points="498,-23 498,-44 522,-44 522,-23 498,-23"/> <text text-anchor="start" x="501" y="-29.8" font-family="Times,serif" font-size="14.00">x1</text> </g> -<!-- scope0->Con_2 --> +<!-- Scope1_0->Con_3 --> <g id="edge9" class="edge"> -<title>scope0:scope0_x0->Con_2</title> +<title>Scope1_0:Scope1_0_x0->Con_3</title> <path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M462,-45C462,-94.6 290.16,-72.65 243,-88 241.08,-88.63 239.12,-89.33 237.17,-90.09"/> <polygon fill="cornflowerblue" stroke="cornflowerblue" points="235.39,-87.04 227.58,-94.19 238.15,-93.48 235.39,-87.04"/> </g> -<!-- scope0->Con_3 --> +<!-- Scope1_0->Con_4 --> <g id="edge8" class="edge"> -<title>scope0:scope0_y0->Con_3</title> +<title>Scope1_0:Scope1_0_y0->Con_4</title> <path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M438,-45C438,-67.35 411.84,-55.23 390,-60 294.13,-80.94 265.19,-60.49 171,-88 169.06,-88.57 167.09,-89.23 165.13,-89.95"/> <polygon fill="cornflowerblue" stroke="cornflowerblue" points="163.39,-86.88 155.5,-93.97 166.08,-93.34 163.39,-86.88"/> </g> -<!-- scope0->Con_4 --> +<!-- Scope1_0->Con_5 --> <g id="edge11" class="edge"> -<title>scope0:scope0_x1->Con_4</title> +<title>Scope1_0:Scope1_0_x1->Con_5</title> <path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M510,-45C510,-71.13 433.9,-89.82 387,-98.86"/> <polygon fill="cornflowerblue" stroke="cornflowerblue" points="386.09,-95.47 376.9,-100.75 387.37,-102.35 386.09,-95.47"/> </g> -<!-- scope0->Con_5 --> +<!-- Scope1_0->Con_6 --> <g id="edge10" class="edge"> -<title>scope0:scope0_y1->Con_5</title> +<title>Scope1_0:Scope1_0_y1->Con_6</title> <path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M486,-45C486,-123.37 388.78,-61.59 315,-88 313.15,-88.66 311.26,-89.39 309.37,-90.16"/> <polygon fill="cornflowerblue" stroke="cornflowerblue" points="307.8,-87.02 300.03,-94.23 310.6,-93.44 307.8,-87.02"/> </g> diff --git a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index dc5358f4..a85a670e 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -18,6 +18,9 @@ public class GraphVisualizer { Collection<Node> all = findAll(parser); StringBuilder sb = new StringBuilder(); sb.append("digraph chapter03 {\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 @@ -25,6 +28,13 @@ public class GraphVisualizer { // 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 + + // 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); @@ -47,12 +57,15 @@ public class GraphVisualizer { // 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 ) { + if( n instanceof ScopeNode ) + continue; // Do not emit, rolled into Scope cluster already 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 @@ -62,12 +75,12 @@ public class GraphVisualizer { sb.append("\tnode [shape=plaintext];\n"); int level=0; for( HashMap<String,Integer> scope : scopenode._scopes ) { - sb.append("\tsubgraph cluster_").append(level).append(" {\n"); // Magic "cluster_" in the subgraph name - String scopeName = makeScopeName(level); + String scopeName = makeScopeName(scopenode, level); + sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name sb.append("\t\t").append(scopeName).append(" [label=<\n"); sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n"); // Add the scope level - sb.append("\t\t\t<TR><TD BGCOLOR=\"aqua\">").append(level).append("</TD>"); + sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(level).append("</TD>"); for( String name : scope.keySet() ) sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>"); sb.append("</TR>\n"); @@ -79,23 +92,37 @@ public class GraphVisualizer { // We close them all at once here. sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters } - - private String makeScopeName(int level) { return "scope" + level; } + + private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; } private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } // 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; + // ScopeNodes are done separately + if( n instanceof ScopeNode ) + continue; + 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++; + } + } } // Walk the scope edges @@ -103,19 +130,23 @@ public class GraphVisualizer { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); int level=0; for( HashMap<String,Integer> scope : scopenode._scopes ) { - String scopeName = makeScopeName(level); - for( String name : scope.keySet() ) - sb.append("\t").append(scopeName).append(":").append(makePortName(scopeName, name)).append(" -> ").append(scopenode.in(scope.get(name)).uniqueName()).append(";\n"); + String scopeName = makeScopeName(scopenode, level); + for( String name : scope.keySet() ) { + Node def = scopenode.in(scope.get(name)); + if( def==null ) continue; + sb.append("\t") + .append(scopeName).append(":") + .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted + .append(" -> "); + sb.append(def.uniqueName()); + sb.append(";\n"); + } level++; } } /** - * 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; @@ -133,10 +164,14 @@ public class GraphVisualizer { * Walk a subgraph and populate distinct nodes in the all list. */ private void walk(HashMap<Integer, Node> all, Node n) { + if(n == null ) return; 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); + for (Node c : n._outputs) + if (c != null) + walk(all, c); } } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java index 3d06a9c3..c8195882 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java @@ -23,6 +23,7 @@ public class Parser { */ public static StartNode START; + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; /** @@ -31,17 +32,35 @@ public class Parser { */ public ScopeNode _scope; + /** + * List of keywords disallowed as identifiers + */ + private final HashSet<String> KEYWORDS = new HashSet<>(){{ + add("int"); + add("return"); + }}; + + public Parser(String source) { _lexer = new Lexer(source); - _scope = new ScopeNode(); Node.reset(); + _scope = new ScopeNode(); START = new StartNode(); } - public ReturnNode parse() { - return (ReturnNode) parseBlock(false); - } + String src() { return new String( _lexer._input ); } + public ReturnNode parse() { return parse(false); } + public ReturnNode parse(boolean show) { + try { + var ret = (ReturnNode) parseBlock(); + if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + return ret; + } + finally { + if( show ) showGraph(); + } + } /** * Parses a block @@ -49,23 +68,17 @@ public class Parser { * <pre> * '{' statements '}' * </pre> + * Does not parse the opening or closing '{}' + * @return a {@link Node} or {@code null} */ - private Node parseBlock(boolean requireClosingBracket) { + private Node parseBlock() { // Enter a new scope _scope.push(); Node n = null; - do { - if (match("}")) { - if (requireClosingBracket) break; - else throw error("unexpected '}' token"); - } else if (_lexer.isEOF()) { - if (requireClosingBracket) require("}"); - else break; - } - + while (!peek('}') && !_lexer.isEOF()) { Node n0 = parseStatement(); if (n0 != null) n = n0; // Allow null returns from eg showGraph - } while (true); + }; // Exit scope _scope.pop(); return n; @@ -77,32 +90,34 @@ public class Parser { * <pre> * returnStatement | declStatement | blockStatement | expressionStatement * </pre> + * @return a {@link Node} or {@code null} */ private Node parseStatement() { - if (match("return")) return parseReturn(); - else if (match("int")) return parseDecl(); - else if (match("{")) return parseBlock(true); - else if (match("#showGraph")) return showGraph(); + if (matchx("return") ) return parseReturn(); + else if (matchx("int")) return parseDecl(); + else if (match ("{" )) return require(parseBlock(),"}"); + else if (matchx("#showGraph")) return require(showGraph(),";"); else return parseExpressionStatement(); } /** - * 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 Node parseReturn() { var expr = require(parseExpression(), ";"); - return new ReturnNode(START, expr); + return new ReturnNode(START, expr).peephole(); } /** * Dumps out the node graph + * @return {@code null} */ private Node showGraph() { - require(";"); System.out.println(new GraphVisualizer().generateDotOutput(this)); return null; } @@ -113,6 +128,7 @@ public class Parser { * <pre> * name '=' expression ';' * </pre> + * @return an expression {@link Node}, never {@code null} */ private Node parseExpressionStatement() { var name = requireId(); @@ -129,6 +145,7 @@ public class Parser { * <pre> * 'int' name = expression ';' * </pre> + * @return an expression {@link Node}, never {@code null} */ private Node parseDecl() { // Type is 'int' for now @@ -146,8 +163,9 @@ public class Parser { * <pre> * expr : additiveExpr * </pre> + * @return an expression {@link Node}, never {@code null} */ - private Node parseExpression() {return parseAddition();} + private Node parseExpression() { return parseAddition(); } /** * Parse an additive expression @@ -155,6 +173,7 @@ public class Parser { * <pre> * additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)* * </pre> + * @return an add expression {@link Node}, never {@code null} */ private Node parseAddition() { var lhs = parseMultiplication(); @@ -169,6 +188,7 @@ public class Parser { * <pre> * multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)* * </pre> + * @return a multiply expression {@link Node}, never {@code null} */ private Node parseMultiplication() { var lhs = parseUnary(); @@ -183,6 +203,7 @@ 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(); @@ -195,15 +216,16 @@ public class Parser { * <pre> * 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(), ")"); - String name = requireId(); - Node id = _scope.lookup(name); - if( id==null ) - throw error("Undefined name '" + name + "'"); - return id; + if( _lexer.isNumber() ) return parseIntegerLiteral(); + if( match("(") ) return require(parseExpression(), ")"); + String name = _lexer.matchId(); + if( name == null) throw errorSyntax("an identifier or expression"); + Node n = _scope.lookup(name); + if( n!=null ) return n; + throw error("Undefined name '" + name + "'"); } /** @@ -221,17 +243,21 @@ public class Parser { // Utilities for lexical analysis // Return true and skip if "syntax" is next in the stream. - private boolean match(String syntax) {return _lexer.match(syntax);} + private boolean match (String syntax) { return _lexer.match (syntax); } + // Match must be "exact", not be followed by more id letters + private boolean matchx(String syntax) { return _lexer.matchx(syntax); } + // Return true and do NOT skip if 'ch' is next + private boolean peek(char ch) { return _lexer.peek(ch); } // Require and return an identifier private String requireId() { String id = _lexer.matchId(); - if (id != null) return id; - throw error("identifier"); + if (id != null && !KEYWORDS.contains(id) ) return id; + throw error("Expected an identifier, found '"+id+"'"); } // 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); @@ -313,11 +339,24 @@ public class Parser { 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)) return false; + if ((char) _input[_position + i] != syntax.charAt(i)) + return false; _position += len; return true; } + boolean matchx(String syntax) { + if( !match(syntax) ) return false; + if( !isIdLetter(peek()) ) return true; + _position -= syntax.length(); + return false; + } + + private boolean peek(char ch) { + skipWhiteSpace(); + return peek()==ch; + } + // Return an identifier or null String matchId() { skipWhiteSpace(); @@ -341,7 +380,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 @@ -367,8 +406,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/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java index 015779dc..6784ad60 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 798d40d5..ec85bf1f 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -16,25 +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 "#"+_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/chapter03/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Control.java deleted file mode 100644 index 48cf2b7a..00000000 --- a/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java index 0056c42d..ca7df79c 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 7fab83b0..834f4c11 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java index e1a26858..0fa54966 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java index 9c71c424..a778687d 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter03/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,34 +52,47 @@ 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); _outputs = new ArrayList<>(); for( Node n : _inputs ) if( n != null ) - n._outputs.add( this ); - // Do an initial type computation - _type = compute(); + n.addUse( this ); } + // 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,23 +150,13 @@ 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}. - */ - public 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 */ Node set_def(int idx, Node new_def ) { Node old_def = in(idx); @@ -159,10 +165,10 @@ public abstract class Node { // 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. if( new_def != null ) - new_def._outputs.add(this); + new_def.addUse(this); if( old_def != null && // If the old def exists, remove a def->use edge old_def.delUse(this) ) // If we removed the last use, the old def is now dead - old_def.kill(); // Kill old def + old_def.kill(); // Kill old def // Set the new_def over the old (killed) edge _inputs.set(idx,new_def); // Return self for easy flow-coding @@ -181,11 +187,10 @@ public abstract class Node { _inputs.add(new_def); // If new def is not null, add the corresponding def->use edge if( new_def != null ) - new_def._outputs.add(this); + new_def.addUse(this); return new_def; } - // Breaks the edge invariants, used temporarily private void addUse(Node n) { _outputs.add(n); } @@ -194,10 +199,10 @@ public abstract class Node { // Error is 'use' does not exist; ok for 'use' to be null. private boolean delUse( Node use ) { ArrayList<Node> outs = _outputs; - int lidx = outs.size()-1; // Last index + int lidx = outs.size()-1; // Last index // This 1-line hack compresses an element out of an ArrayList // without having to copy the contents. The last element is - // stuffed over the deleted element, and then the size is reduced. + // stuffed over the deleted element, and then the size is reduced. outs.set(outs.indexOf(use),outs.get(lidx)); outs.remove(lidx); // Reduce ArrayList size without copying anything return lidx==0; @@ -209,17 +214,26 @@ public abstract class Node { for( int i=0; i<n; i++ ) { Node old_def = _inputs.remove(_inputs.size()-1); if( old_def != null && // If it exists and - old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def } } /** - * 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 #pop_n}. */ - public Type _type; - + public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + pop_n(nIns()); // Set all inputs to null, recursively killing unused Nodes + _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> @@ -245,9 +259,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/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index c188ca79..18f5eed9 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index c7d6edb9..5f5d66a0 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,9 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.TypeBot; -import java.util.HashMap; -import java.util.Stack; +import java.util.*; /** * The Scope node is a purely parser helper - it tracks names to nodes with a @@ -17,12 +17,15 @@ public class ScopeNode extends Node { * The top of this stack represents current scope. */ public final Stack<HashMap<String, Integer>> _scopes = new Stack<>(); - - @Override - public String label() { return "Scope"; } - + + // Reverse lookup for nicer graph printing + private final ArrayList<String> _rlabels = new ArrayList<>(); + + @Override public String label() { return "Scope"; } + @Override - StringBuilder _print(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb) { + sb.append(label()); for( HashMap<String,Integer> scope : _scopes ) { sb.append("["); boolean first=true; @@ -32,22 +35,21 @@ public class ScopeNode extends Node { sb.append(name).append(":"); Node n = in(scope.get(name)); if( n==null ) sb.append("null"); - else n._print(sb); + else n._print0(sb); } sb.append("]"); } return sb; } - + @Override public TypeBot compute() { return TypeBot.BOTTOM; } - @Override - public Node idealize() { return null; } + @Override public Node idealize() { return null; } // Add an empty lexical scope - public void push() { - _scopes.push(new HashMap<>()); + public HashMap<String, Integer> push() { + return _scopes.push(new HashMap<>()); } // Remove the current lexical scope, killing all unused nodes. @@ -61,6 +63,7 @@ public class ScopeNode extends Node { HashMap<String,Integer> scope = _scopes.lastElement(); if( scope.put(name,nIns()) != null ) return null; // Double define + _rlabels.add(name); return add_def(n); } @@ -73,7 +76,7 @@ public class ScopeNode extends Node { return null; } - + // If the name is present in any scope, then redefine public Node update(String name, Node n) { for (int i = _scopes.size() - 1; i >= 0; i--) { @@ -85,5 +88,4 @@ public class ScopeNode extends Node { return null; } - } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java index 8d8031bb..08b8333a 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java index 2d7db8d3..71d70fa6 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java index 5284884a..bc191241 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 06cac15e..ff6e865b 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter03/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/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 21faacac..d86b978f 100644 --- a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.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 Chapter03Test { @@ -54,6 +50,15 @@ public class Chapter03Test { assertEquals("return 8;", ret.print()); } + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } @Test public void testChapter2ParseGrammar() { @@ -120,7 +125,7 @@ public class Chapter03Test { 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(); } @@ -133,21 +138,27 @@ public class Chapter03Test { 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 =: "); - new Parser("ret").parse(); + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: ",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 @@ -158,9 +169,12 @@ public class Chapter03Test { @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 @@ -171,8 +185,22 @@ public class Chapter03Test { @Test public void testBad6() { - exceptionRule.expect(RuntimeException.class); - exceptionRule.expectMessage("Syntax error, expected }:"); - new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } } + + @Test + public void testBad7() { + try { + new Parser("return 1;}").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, unexpected }",e.getMessage()); + } + } + } |
