diff options
| -rw-r--r-- | chapter05/README.md | 36 | ||||
| -rw-r--r-- | chapter05/docs/05-graph1.gv | 85 | ||||
| -rw-r--r-- | chapter05/docs/05-graph1.svg | 220 | ||||
| -rw-r--r-- | chapter05/docs/05-graph2.gv | 77 | ||||
| -rw-r--r-- | chapter05/docs/05-graph2.svg | 228 | ||||
| -rw-r--r-- | chapter05/src/main/java/com/seaofnodes/simple/Parser.java | 1 |
6 files changed, 644 insertions, 3 deletions
diff --git a/chapter05/README.md b/chapter05/README.md index d0f475fa..c25e6aef 100644 --- a/chapter05/README.md +++ b/chapter05/README.md @@ -44,7 +44,7 @@ When we parse an `if` statement, the control flow splits at that point. We must This involves following: -* The `IfNode` is created with the current control token, i.e. the node mapped to `$ctrl` and the predicate expression as inputs. +* The `IfNode` is created with the current control token, i.e. the node mapped to `$ctrl`, and the predicate expression as inputs. * We add two `ProjNodes` - one for the `True` branch (call if `ifT`), and the other for the `False` branch (call it `ifF`) - these extract values from the tuple result of the `IfNode`. * We now create a duplicate of the current `ScopeNode`. The duplicated `ScopeNode` must have all the stack levels as the original, and moreover the new node must be a user of all the names that are currently bound. * The original `ScopeNode` is saved. @@ -54,11 +54,41 @@ This involves following: * We reset the original `ScopeNode` as current. * We set control token to the `False` projection node `ifF`. * If there is an `else` statement we parse it. -* At this point we have two `ScopeNode`s; the original one, potentially update by the `False` branch, and the duplicate one, potentially updated by the `True` branch. +* At this point we have two `ScopeNode`s; the original one, potentially updated by the `False` branch, and the duplicate one, potentially updated by the `True` branch. * We create a `Region` node to represent a merge point. -* We compare the two `ScopeNode`s. We create `Phi` nodes for any names whose bindings differ. The `Phi` nodes take the `Region` node as the control input and the two data nodes from each of the `ScopeNode`s. +* We compare the two `ScopeNode`s. We create `Phi` nodes for any names whose bindings differ. The `Phi` nodes take the `Region` node as the control input and the two data nodes from each of the `ScopeNode`s. The name binding is updated to point to the `Phi` node. * Finally, we set the `Region` node as the control token, and discard the duplicated `ScopeNode`. ## Example +We show the graph for the following code snippet: +```java +int a = 1; +if (arg == 1) + a = arg+2; +else + a = arg-3; +return a; +``` + +### Before merging + +Following shows the graph just before we merge the two branches of the `if` statement in a `Region` node. + + + +* Note the two `ScopeNode`s in the graph. +* One has its `$ctrl` pointing to the `True` projection, while the other has `$ctrl` pointing to `False` projection. +* Note that the binding of `a` is to the `Sub` node in the `False` branch, whereas `a` is bound to the `Add` node in the `True` branch. +* Thus `a` needs a `Phi` node. + +### After merging + +Below is the graph after we created a `Region` node and merged the two definitions of `a` in a `Phi` node. + + + +* Observe that the duplicate `ScopeNode` has been discarded. +* The binding of `a` is now bound to the `Phi` node. +* The `Phi` node's inputs are the `Region` node and the `Add` node from the `True` branch, and `Sub` node from the `False` branch. diff --git a/chapter05/docs/05-graph1.gv b/chapter05/docs/05-graph1.gv new file mode 100644 index 00000000..99993814 --- /dev/null +++ b/chapter05/docs/05-graph1.gv @@ -0,0 +1,85 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +return a; +#showGraph; + +*/ + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_5 [ label="#1" ]; + EQNode6 [ label="EQNode" ]; + If7 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_11 [ label="#2" ]; + Add12 [ label="Add" ]; + Con_13 [ label="#3" ]; + Sub14 [ label="Sub" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope20_0 { + Scope20_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope20_0_$ctrl">$ctrl</TD><TD PORT="Scope20_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope20_1 { + Scope20_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope20_1_a">a</TD></TR> + </TABLE>>]; + } + } + node [shape=plaintext]; + subgraph cluster_Scope21_0 { + Scope21_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope21_0_$ctrl">$ctrl</TD><TD PORT="Scope21_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope21_1 { + Scope21_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope21_1_a">a</TD></TR> + </TABLE>>]; + } + } + EQNode6 -> Start1:p1; + EQNode6 -> Con_5; + If7 -> Start1:p0 [color=red]; + If7 -> EQNode6; + Add12 -> Start1:p1; + Add12 -> Con_11; + Sub14 -> Start1:p1; + Sub14 -> Con_13; + edge [style=dashed color=cornflowerblue]; + Scope20_0:"Scope20_0_$ctrl" -> If7:p1; + Scope20_0:"Scope20_0_arg" -> Start1:p1; + Scope20_1:"Scope20_1_a" -> Sub14; + edge [style=dashed color=cornflowerblue]; + Scope21_0:"Scope21_0_$ctrl" -> If7:p0; + Scope21_0:"Scope21_0_arg" -> Start1:p1; + Scope21_1:"Scope21_1_a" -> Add12; +}
\ No newline at end of file diff --git a/chapter05/docs/05-graph1.svg b/chapter05/docs/05-graph1.svg new file mode 100644 index 00000000..488a71cb --- /dev/null +++ b/chapter05/docs/05-graph1.svg @@ -0,0 +1,220 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter05 Pages: 1 --> +<svg width="471pt" height="356pt" + viewBox="0.00 0.00 471.00 356.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 352)"> +<title>chapter05</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-352 467,-352 467,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="89,-88 89,-340 419,-340 419,-88 89,-88"/> +</g> +<g id="clust2" class="cluster"> +<title>cluster_Scope20_0</title> +<polygon fill="none" stroke="black" points="8,-8 8,-76 208,-76 208,-8 8,-8"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_Scope20_1</title> +<polygon fill="none" stroke="black" points="16,-16 16,-68 86,-68 86,-16 16,-16"/> +</g> +<g id="clust4" class="cluster"> +<title>cluster_Scope21_0</title> +<polygon fill="none" stroke="black" points="255,-8 255,-76 455,-76 455,-8 255,-8"/> +</g> +<g id="clust5" class="cluster"> +<title>cluster_Scope21_1</title> +<polygon fill="none" stroke="black" points="263,-16 263,-68 333,-68 333,-16 263,-16"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="yellow" stroke="transparent" points="178,-303 178,-328 259,-328 259,-303 178,-303"/> +<polygon fill="none" stroke="black" points="178,-303 178,-328 259,-328 259,-303 178,-303"/> +<text text-anchor="start" x="200" y="-311.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="178,-272 178,-303 259,-303 259,-272 178,-272"/> +<polygon fill="yellow" stroke="transparent" points="183,-277 183,-298 223,-298 223,-277 183,-277"/> +<polygon fill="none" stroke="black" points="183,-277 183,-298 223,-298 223,-277 183,-277"/> +<text text-anchor="start" x="186" y="-283.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="223,-277 223,-298 254,-298 254,-277 223,-277"/> +<text text-anchor="start" x="226" y="-283.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Con_5 --> +<g id="node2" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="black" cx="312" cy="-300" rx="27" ry="18"/> +<text text-anchor="middle" x="312" y="-296.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- EQNode6 --> +<g id="node3" class="node"> +<title>EQNode6</title> +<ellipse fill="none" stroke="black" cx="271" cy="-214" rx="49.29" ry="18"/> +<text text-anchor="middle" x="271" y="-210.3" font-family="Times,serif" font-size="14.00">EQNode</text> +</g> +<!-- EQNode6->Start1 --> +<g id="edge1" class="edge"> +<title>EQNode6->Start1:p1</title> +<path fill="none" stroke="black" d="M256.87,-231.41C250.04,-240.69 242.75,-253.02 240.07,-265.99"/> +<polygon fill="black" stroke="black" points="236.58,-265.69 239,-276 243.54,-266.43 236.58,-265.69"/> +</g> +<!-- EQNode6->Con_5 --> +<g id="edge2" class="edge"> +<title>EQNode6->Con_5</title> +<path fill="none" stroke="black" d="M279.3,-232C285.1,-243.88 292.94,-259.96 299.5,-273.39"/> +<polygon fill="black" stroke="black" points="296.46,-275.15 303.99,-282.6 302.75,-272.08 296.46,-275.15"/> +</g> +<!-- If7 --> +<g id="node4" class="node"> +<title>If7</title> +<polygon fill="yellow" stroke="transparent" points="181,-131 181,-156 275,-156 275,-131 181,-131"/> +<polygon fill="none" stroke="black" points="181,-131 181,-156 275,-156 275,-131 181,-131"/> +<text text-anchor="start" x="222.5" y="-139.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="181,-100 181,-131 275,-131 275,-100 181,-100"/> +<polygon fill="yellow" stroke="transparent" points="186,-105 186,-126 226,-126 226,-105 186,-105"/> +<polygon fill="none" stroke="black" points="186,-105 186,-126 226,-126 226,-105 186,-105"/> +<text text-anchor="start" x="189" y="-111.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="226,-105 226,-126 270,-126 270,-105 226,-105"/> +<polygon fill="none" stroke="black" points="226,-105 226,-126 270,-126 270,-105 226,-105"/> +<text text-anchor="start" x="229" y="-111.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If7->Start1 --> +<g id="edge3" class="edge"> +<title>If7->Start1:p0</title> +<path fill="none" stroke="red" d="M219.54,-160.28C212.88,-187.44 204.51,-228.22 203.18,-265.97"/> +<polygon fill="red" stroke="red" points="199.68,-265.94 203,-276 206.68,-266.06 199.68,-265.94"/> +</g> +<!-- If7->EQNode6 --> +<g id="edge4" class="edge"> +<title>If7->EQNode6</title> +<path fill="none" stroke="black" d="M244.01,-160.28C248.52,-169.09 253.38,-178.58 257.71,-187.04"/> +<polygon fill="black" stroke="black" points="254.66,-188.76 262.33,-196.07 260.89,-185.57 254.66,-188.76"/> +</g> +<!-- Con_11 --> +<g id="node5" class="node"> +<title>Con_11</title> +<ellipse fill="none" stroke="black" cx="384" cy="-300" rx="27" ry="18"/> +<text text-anchor="middle" x="384" y="-296.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Add12 --> +<g id="node6" class="node"> +<title>Add12</title> +<ellipse fill="none" stroke="black" cx="367" cy="-214" rx="28.7" ry="18"/> +<text text-anchor="middle" x="367" y="-210.3" font-family="Times,serif" font-size="14.00">Add</text> +</g> +<!-- Add12->Start1 --> +<g id="edge5" class="edge"> +<title>Add12->Start1:p1</title> +<path fill="none" stroke="black" d="M345.25,-226.01C326.31,-235.99 298.43,-251.6 276,-268 269.65,-272.64 267.95,-278.9 264.5,-282.95"/> +<polygon fill="black" stroke="black" points="262.82,-279.86 255,-287 265.57,-286.29 262.82,-279.86"/> +</g> +<!-- Add12->Con_11 --> +<g id="edge6" class="edge"> +<title>Add12->Con_11</title> +<path fill="none" stroke="black" d="M370.44,-232C372.77,-243.5 375.89,-258.93 378.55,-272.08"/> +<polygon fill="black" stroke="black" points="375.15,-272.92 380.56,-282.03 382.01,-271.53 375.15,-272.92"/> +</g> +<!-- Con_13 --> +<g id="node7" class="node"> +<title>Con_13</title> +<ellipse fill="none" stroke="black" cx="124" cy="-300" rx="27" ry="18"/> +<text text-anchor="middle" x="124" y="-296.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Sub14 --> +<g id="node8" class="node"> +<title>Sub14</title> +<ellipse fill="none" stroke="black" cx="155" cy="-214" rx="28.7" ry="18"/> +<text text-anchor="middle" x="155" y="-210.3" font-family="Times,serif" font-size="14.00">Sub</text> +</g> +<!-- Sub14->Start1 --> +<g id="edge7" class="edge"> +<title>Sub14->Start1:p1</title> +<path fill="none" stroke="black" d="M177.07,-225.84C197.1,-236.27 224.99,-252.48 235.13,-266.39"/> +<polygon fill="black" stroke="black" points="232.02,-268.03 239,-276 238.51,-265.42 232.02,-268.03"/> +</g> +<!-- Sub14->Con_13 --> +<g id="edge8" class="edge"> +<title>Sub14->Con_13</title> +<path fill="none" stroke="black" d="M148.88,-231.6C144.54,-243.33 138.65,-259.3 133.69,-272.76"/> +<polygon fill="black" stroke="black" points="130.29,-271.85 130.11,-282.44 136.86,-274.27 130.29,-271.85"/> +</g> +<!-- Scope20_0 --> +<g id="node9" class="node"> +<title>Scope20_0</title> +<polygon fill="cyan" stroke="transparent" points="105,-31 105,-52 121,-52 121,-31 105,-31"/> +<polygon fill="none" stroke="black" points="105,-31 105,-52 121,-52 121,-31 105,-31"/> +<text text-anchor="start" x="108" y="-37.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="121,-31 121,-52 161,-52 161,-31 121,-31"/> +<text text-anchor="start" x="124" y="-37.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="161,-31 161,-52 192,-52 192,-31 161,-31"/> +<text text-anchor="start" x="164" y="-37.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Scope20_0->Start1 --> +<g id="edge10" class="edge"> +<title>Scope20_0:Scope20_0_arg->Start1:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M177,-53C177,-61.62 118.7,-187.55 117,-196 113.84,-211.69 107.8,-218.91 117,-232 147.93,-276.04 227.44,-225.96 237.87,-266.02"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="234.39,-266.46 239,-276 241.35,-265.67 234.39,-266.46"/> +</g> +<!-- Scope20_0->If7 --> +<g id="edge9" class="edge"> +<title>Scope20_0:Scope20_0_$ctrl->If7:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M141,-53C141,-101.77 232.71,-58.8 246.32,-93.95"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="242.9,-94.71 248,-104 249.8,-93.56 242.9,-94.71"/> +</g> +<!-- Scope20_1 --> +<g id="node10" class="node"> +<title>Scope20_1</title> +<polygon fill="cyan" stroke="transparent" points="36,-31 36,-52 52,-52 52,-31 36,-31"/> +<polygon fill="none" stroke="black" points="36,-31 36,-52 52,-52 52,-31 36,-31"/> +<text text-anchor="start" x="39" y="-37.8" font-family="Times,serif" font-size="14.00">1</text> +<polygon fill="none" stroke="black" points="52,-31 52,-52 67,-52 67,-31 52,-31"/> +<text text-anchor="start" x="55" y="-37.8" font-family="Times,serif" font-size="14.00">a</text> +</g> +<!-- Scope20_1->Sub14 --> +<g id="edge11" class="edge"> +<title>Scope20_1:Scope20_1_a->Sub14</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M60,-53C60,-109.34 104.1,-163.18 132.2,-191.77"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="129.75,-194.27 139.31,-198.82 134.67,-189.29 129.75,-194.27"/> +</g> +<!-- Scope21_0 --> +<g id="node11" class="node"> +<title>Scope21_0</title> +<polygon fill="cyan" stroke="transparent" points="352,-31 352,-52 368,-52 368,-31 352,-31"/> +<polygon fill="none" stroke="black" points="352,-31 352,-52 368,-52 368,-31 352,-31"/> +<text text-anchor="start" x="355" y="-37.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="368,-31 368,-52 408,-52 408,-31 368,-31"/> +<text text-anchor="start" x="371" y="-37.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="408,-31 408,-52 439,-52 439,-31 408,-31"/> +<text text-anchor="start" x="411" y="-37.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Scope21_0->Start1 --> +<g id="edge13" class="edge"> +<title>Scope21_0:Scope21_0_arg->Start1:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M424,-53C424,-133 456.67,-170.92 405,-232 366.55,-277.44 328.13,-239.26 276,-268 269.11,-271.8 267.55,-278.27 264.27,-282.59"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="262.53,-279.54 255,-287 265.53,-285.86 262.53,-279.54"/> +</g> +<!-- Scope21_0->If7 --> +<g id="edge12" class="edge"> +<title>Scope21_0:Scope21_0_$ctrl->If7:p0</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M388,-53C388,-77.87 360.63,-68.25 337,-76 312.25,-84.12 230.52,-76.68 210.47,-94.63"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="207.15,-93.47 206,-104 213.46,-96.48 207.15,-93.47"/> +</g> +<!-- Scope21_1 --> +<g id="node12" class="node"> +<title>Scope21_1</title> +<polygon fill="cyan" stroke="transparent" points="283,-31 283,-52 299,-52 299,-31 283,-31"/> +<polygon fill="none" stroke="black" points="283,-31 283,-52 299,-52 299,-31 283,-31"/> +<text text-anchor="start" x="286" y="-37.8" font-family="Times,serif" font-size="14.00">1</text> +<polygon fill="none" stroke="black" points="299,-31 299,-52 314,-52 314,-31 299,-31"/> +<text text-anchor="start" x="302" y="-37.8" font-family="Times,serif" font-size="14.00">a</text> +</g> +<!-- Scope21_1->Add12 --> +<g id="edge14" class="edge"> +<title>Scope21_1:Scope21_1_a->Add12</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M307,-53C307,-103.54 333.58,-157.68 351.35,-188.24"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="348.42,-190.15 356.55,-196.94 354.42,-186.56 348.42,-190.15"/> +</g> +</g> +</svg> diff --git a/chapter05/docs/05-graph2.gv b/chapter05/docs/05-graph2.gv new file mode 100644 index 00000000..d2c819a8 --- /dev/null +++ b/chapter05/docs/05-graph2.gv @@ -0,0 +1,77 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +return a; +#showGraph; + +*/ + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_5 [ label="#1" ]; + EQNode6 [ label="EQNode" ]; + If7 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_11 [ label="#2" ]; + Add12 [ label="Add" ]; + Con_13 [ label="#3" ]; + Sub14 [ label="Sub" ]; + Region15 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi16 [ label="Phi" ]; + Return17 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope20_0 { + Scope20_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope20_0_$ctrl">$ctrl</TD><TD PORT="Scope20_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope20_1 { + Scope20_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope20_1_a">a</TD></TR> + </TABLE>>]; + } + } + EQNode6 -> Start1:p1; + EQNode6 -> Con_5; + If7 -> Start1:p0 [color=red]; + If7 -> EQNode6; + Add12 -> Start1:p1; + Add12 -> Con_11; + Sub14 -> Start1:p1; + Sub14 -> Con_13; + Region15 -> If7:p0 [color=red]; + Region15 -> If7:p1 [color=red]; + Phi16 -> Region15 [color=red]; + Phi16 -> Add12; + Phi16 -> Sub14; + Return17 -> Region15 [color=red]; + Return17 -> Phi16; + edge [style=dashed color=cornflowerblue]; + Scope20_0:"Scope20_0_arg" -> Start1:p1; + Scope20_1:"Scope20_1_a" -> Phi16; +}
\ No newline at end of file diff --git a/chapter05/docs/05-graph2.svg b/chapter05/docs/05-graph2.svg new file mode 100644 index 00000000..70d1a8c5 --- /dev/null +++ b/chapter05/docs/05-graph2.svg @@ -0,0 +1,228 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter05 Pages: 1 --> +<svg width="542pt" height="500pt" + viewBox="0.00 0.00 542.00 500.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 496)"> +<title>chapter05</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-496 538,-496 538,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-16 8,-484 318,-484 318,-16 8,-16"/> +</g> +<g id="clust2" class="cluster"> +<title>cluster_Scope20_0</title> +<polygon fill="none" stroke="black" points="326,-8 326,-76 526,-76 526,-8 326,-8"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_Scope20_1</title> +<polygon fill="none" stroke="black" points="334,-16 334,-68 404,-68 404,-16 334,-16"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="yellow" stroke="transparent" points="174,-447 174,-472 255,-472 255,-447 174,-447"/> +<polygon fill="none" stroke="black" points="174,-447 174,-472 255,-472 255,-447 174,-447"/> +<text text-anchor="start" x="196" y="-455.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="174,-416 174,-447 255,-447 255,-416 174,-416"/> +<polygon fill="yellow" stroke="transparent" points="179,-421 179,-442 219,-442 219,-421 179,-421"/> +<polygon fill="none" stroke="black" points="179,-421 179,-442 219,-442 219,-421 179,-421"/> +<text text-anchor="start" x="182" y="-427.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="219,-421 219,-442 250,-442 250,-421 219,-421"/> +<text text-anchor="start" x="222" y="-427.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Con_5 --> +<g id="node2" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="black" cx="120" cy="-444" rx="27" ry="18"/> +<text text-anchor="middle" x="120" y="-440.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- EQNode6 --> +<g id="node3" class="node"> +<title>EQNode6</title> +<ellipse fill="none" stroke="black" cx="139" cy="-358" rx="49.29" ry="18"/> +<text text-anchor="middle" x="139" y="-354.3" font-family="Times,serif" font-size="14.00">EQNode</text> +</g> +<!-- EQNode6->Start1 --> +<g id="edge1" class="edge"> +<title>EQNode6->Start1:p1</title> +<path fill="none" stroke="black" d="M179.99,-368.1C202.72,-375.5 227.59,-388.34 233.63,-409.86"/> +<polygon fill="black" stroke="black" points="230.19,-410.56 235,-420 237.13,-409.62 230.19,-410.56"/> +</g> +<!-- EQNode6->Con_5 --> +<g id="edge2" class="edge"> +<title>EQNode6->Con_5</title> +<path fill="none" stroke="black" d="M135.16,-376C132.55,-387.5 129.06,-402.93 126.09,-416.08"/> +<polygon fill="black" stroke="black" points="122.63,-415.5 123.84,-426.03 129.46,-417.05 122.63,-415.5"/> +</g> +<!-- If7 --> +<g id="node4" class="node"> +<title>If7</title> +<polygon fill="yellow" stroke="transparent" points="24,-275 24,-300 118,-300 118,-275 24,-275"/> +<polygon fill="none" stroke="black" points="24,-275 24,-300 118,-300 118,-275 24,-275"/> +<text text-anchor="start" x="65.5" y="-283.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="24,-244 24,-275 118,-275 118,-244 24,-244"/> +<polygon fill="yellow" stroke="transparent" points="29,-249 29,-270 69,-270 69,-249 29,-249"/> +<polygon fill="none" stroke="black" points="29,-249 29,-270 69,-270 69,-249 29,-249"/> +<text text-anchor="start" x="32" y="-255.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="69,-249 69,-270 113,-270 113,-249 69,-249"/> +<polygon fill="none" stroke="black" points="69,-249 69,-270 113,-270 113,-249 69,-249"/> +<text text-anchor="start" x="72" y="-255.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If7->Start1 --> +<g id="edge3" class="edge"> +<title>If7->Start1:p0</title> +<path fill="none" stroke="red" d="M66.46,-304.11C64.93,-326.1 66.49,-355.24 81,-376 102.18,-406.31 125.07,-391.74 156,-412 162.92,-416.54 164.7,-423.06 168.48,-427.16"/> +<polygon fill="red" stroke="red" points="167.42,-430.5 178,-431 170.04,-424.01 167.42,-430.5"/> +</g> +<!-- If7->EQNode6 --> +<g id="edge4" class="edge"> +<title>If7->EQNode6</title> +<path fill="none" stroke="black" d="M96.32,-304.28C103.88,-313.61 112.04,-323.7 119.19,-332.53"/> +<polygon fill="black" stroke="black" points="116.66,-334.97 125.68,-340.54 122.11,-330.57 116.66,-334.97"/> +</g> +<!-- Con_11 --> +<g id="node5" class="node"> +<title>Con_11</title> +<ellipse fill="none" stroke="black" cx="263" cy="-272" rx="27" ry="18"/> +<text text-anchor="middle" x="263" y="-268.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Add12 --> +<g id="node6" class="node"> +<title>Add12</title> +<ellipse fill="none" stroke="black" cx="263" cy="-186" rx="28.7" ry="18"/> +<text text-anchor="middle" x="263" y="-182.3" font-family="Times,serif" font-size="14.00">Add</text> +</g> +<!-- Add12->Start1 --> +<g id="edge5" class="edge"> +<title>Add12->Start1:p1</title> +<path fill="none" stroke="black" d="M276.75,-201.93C284.96,-211.9 294.62,-225.75 299,-240 323.67,-320.23 337.38,-422.23 261.26,-430.47"/> +<polygon fill="black" stroke="black" points="260.81,-426.99 251,-431 261.17,-433.98 260.81,-426.99"/> +</g> +<!-- Add12->Con_11 --> +<g id="edge6" class="edge"> +<title>Add12->Con_11</title> +<path fill="none" stroke="black" d="M263,-204.4C263,-215.74 263,-230.77 263,-243.68"/> +<polygon fill="black" stroke="black" points="259.5,-243.9 263,-253.9 266.5,-243.9 259.5,-243.9"/> +</g> +<!-- Con_13 --> +<g id="node7" class="node"> +<title>Con_13</title> +<ellipse fill="none" stroke="black" cx="171" cy="-272" rx="27" ry="18"/> +<text text-anchor="middle" x="171" y="-268.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Sub14 --> +<g id="node8" class="node"> +<title>Sub14</title> +<ellipse fill="none" stroke="black" cx="180" cy="-186" rx="28.7" ry="18"/> +<text text-anchor="middle" x="180" y="-182.3" font-family="Times,serif" font-size="14.00">Sub</text> +</g> +<!-- Sub14->Start1 --> +<g id="edge7" class="edge"> +<title>Sub14->Start1:p1</title> +<path fill="none" stroke="black" d="M189.92,-203.13C195.76,-213.34 202.81,-227.03 207,-240 230.84,-313.72 234.69,-337.05 234.98,-409.88"/> +<polygon fill="black" stroke="black" points="231.48,-410.01 235,-420 238.48,-409.99 231.48,-410.01"/> +</g> +<!-- Sub14->Con_13 --> +<g id="edge8" class="edge"> +<title>Sub14->Con_13</title> +<path fill="none" stroke="black" d="M178.18,-204C176.96,-215.38 175.33,-230.62 173.93,-243.69"/> +<polygon fill="black" stroke="black" points="170.4,-243.71 172.82,-254.03 177.36,-244.46 170.4,-243.71"/> +</g> +<!-- Region15 --> +<g id="node9" class="node"> +<title>Region15</title> +<polygon fill="yellow" stroke="black" points="128,-204 62,-204 62,-168 128,-168 128,-204"/> +<text text-anchor="middle" x="95" y="-182.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region15->If7 --> +<g id="edge9" class="edge"> +<title>Region15->If7:p0</title> +<path fill="none" stroke="red" d="M72.54,-204.25C63.23,-213.05 53.81,-224.66 50.37,-237.74"/> +<polygon fill="red" stroke="red" points="46.85,-237.63 49,-248 53.79,-238.55 46.85,-237.63"/> +</g> +<!-- Region15->If7 --> +<g id="edge10" class="edge"> +<title>Region15->If7:p1</title> +<path fill="none" stroke="red" d="M93.28,-204.07C92.44,-213.52 91.54,-225.74 91.17,-237.67"/> +<polygon fill="red" stroke="red" points="87.66,-237.94 91,-248 94.66,-238.06 87.66,-237.94"/> +</g> +<!-- Phi16 --> +<g id="node10" class="node"> +<title>Phi16</title> +<ellipse fill="none" stroke="black" cx="180" cy="-114" rx="27" ry="18"/> +<text text-anchor="middle" x="180" y="-110.3" font-family="Times,serif" font-size="14.00">Phi</text> +</g> +<!-- Phi16->Add12 --> +<g id="edge12" class="edge"> +<title>Phi16->Add12</title> +<path fill="none" stroke="black" d="M196.4,-128.83C208.45,-138.99 225.02,-152.97 238.62,-164.44"/> +<polygon fill="black" stroke="black" points="236.74,-167.43 246.64,-171.2 241.25,-162.08 236.74,-167.43"/> +</g> +<!-- Phi16->Sub14 --> +<g id="edge13" class="edge"> +<title>Phi16->Sub14</title> +<path fill="none" stroke="black" d="M180,-132.3C180,-140.02 180,-149.29 180,-157.89"/> +<polygon fill="black" stroke="black" points="176.5,-157.9 180,-167.9 183.5,-157.9 176.5,-157.9"/> +</g> +<!-- Phi16->Region15 --> +<g id="edge11" class="edge"> +<title>Phi16->Region15</title> +<path fill="none" stroke="red" d="M163.61,-128.5C152.35,-137.77 137.08,-150.34 123.81,-161.27"/> +<polygon fill="red" stroke="red" points="121.36,-158.76 115.86,-167.82 125.81,-164.16 121.36,-158.76"/> +</g> +<!-- Return17 --> +<g id="node11" class="node"> +<title>Return17</title> +<polygon fill="yellow" stroke="black" points="183,-60 117,-60 117,-24 183,-24 183,-60"/> +<text text-anchor="middle" x="150" y="-38.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Return17->Region15 --> +<g id="edge14" class="edge"> +<title>Return17->Region15</title> +<path fill="none" stroke="red" d="M143.37,-60.13C133.91,-84.54 116.47,-129.57 105.32,-158.36"/> +<polygon fill="red" stroke="red" points="102.01,-157.22 101.66,-167.81 108.53,-159.75 102.01,-157.22"/> +</g> +<!-- Return17->Phi16 --> +<g id="edge15" class="edge"> +<title>Return17->Phi16</title> +<path fill="none" stroke="black" d="M157.42,-60.3C160.88,-68.39 165.08,-78.19 168.91,-87.13"/> +<polygon fill="black" stroke="black" points="165.72,-88.56 172.88,-96.38 172.15,-85.81 165.72,-88.56"/> +</g> +<!-- Scope20_0 --> +<g id="node12" class="node"> +<title>Scope20_0</title> +<polygon fill="cyan" stroke="transparent" points="423,-31 423,-52 439,-52 439,-31 423,-31"/> +<polygon fill="none" stroke="black" points="423,-31 423,-52 439,-52 439,-31 423,-31"/> +<text text-anchor="start" x="426" y="-37.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="439,-31 439,-52 479,-52 479,-31 439,-31"/> +<text text-anchor="start" x="442" y="-37.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="479,-31 479,-52 510,-52 510,-31 479,-31"/> +<text text-anchor="start" x="482" y="-37.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Scope20_0->Start1 --> +<g id="edge16" class="edge"> +<title>Scope20_0:Scope20_0_arg->Start1:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M495,-53C495,-121.37 416,-116.63 416,-185 416,-185 416,-185 416,-273 416,-371.06 356.8,-427.09 261.28,-430.8"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="260.93,-427.31 251,-431 261.07,-434.31 260.93,-427.31"/> +</g> +<!-- Scope20_1 --> +<g id="node13" class="node"> +<title>Scope20_1</title> +<polygon fill="cyan" stroke="transparent" points="354,-31 354,-52 370,-52 370,-31 354,-31"/> +<polygon fill="none" stroke="black" points="354,-31 354,-52 370,-52 370,-31 354,-31"/> +<text text-anchor="start" x="357" y="-37.8" font-family="Times,serif" font-size="14.00">1</text> +<polygon fill="none" stroke="black" points="370,-31 370,-52 385,-52 385,-31 370,-31"/> +<text text-anchor="start" x="373" y="-37.8" font-family="Times,serif" font-size="14.00">a</text> +</g> +<!-- Scope20_1->Phi16 --> +<g id="edge17" class="edge"> +<title>Scope20_1:Scope20_1_a->Phi16</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M378,-53C378,-86.31 274.09,-102.84 216.82,-109.43"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="216.26,-105.97 206.7,-110.55 217.03,-112.93 216.26,-105.97"/> +</g> +</g> +</svg> diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index 2953ec26..b141d7ac 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -146,6 +146,7 @@ public class Parser { // Create region node and merge scopes // If a var is in both scopes and has different binding then we need to create PhiNode for it // After merge _scope remains, and ifScope is discarded + System.out.println(new GraphVisualizer().generateDotOutput(this)); RegionNode region = mergeScopes(ifT, ifScope, ifF, _scope); updateCtrlToken(region); // Now region becomes the ctrl token ifScope.clear(); // Clean up ifScope |
