diff options
| -rw-r--r-- | chapter05/README.md | 76 | ||||
| -rw-r--r-- | chapter05/docs/05-graph9.svg | 174 |
2 files changed, 246 insertions, 4 deletions
diff --git a/chapter05/README.md b/chapter05/README.md index 4d36e40c..ef7f79da 100644 --- a/chapter05/README.md +++ b/chapter05/README.md @@ -144,10 +144,75 @@ Although only the innermost occurrence of a name can have its binding changed, w For implementation [see `ScopeNode.mergeScopes()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java#L164-L173) -## Example +## Demonstration +Consider the following code snippet: +```java +int b = 0; +int c = 0; +if (arg == 1) { + b = 2; + c = 1; +} +else { + b = 1; +} +return b; +``` +The value of `b` depends on which path the control flow took. +To resolve this, a Φ (Phi) function is inserted. +``` +b = Phi(2, 1); +c = Phi(1, 0); // dead +``` +`c` has no uses, after merging the scopes together it can be removed. +Before, we go ahead and parse down the if statement we duplicate the scope: +```java +ScopeNode fScope = _scope.dup(); +// Scope[$ctrl:$ctrl, arg:arg][b:0, c:0] +``` +We then will proceed and parse down the first branch of the if statement: +```java +// Parse the true side +ctrl(ifT); // set ctrl token to ifTrue projection +parseStatement(); // Parse true-side +ScopeNode tScope = _scope; -We show the graph for the following code snippet: +// Scope[$ctrl:True, arg:arg][b:2, c:1] +``` +Notice, this branch modified and set a new value for both symbols currently existing in the symbol table. +Now, we set the scope back to where we started(without the modifications that `ifT` made) +```java +_scope = fScope; +``` +We then will proceed and parse down the second branch of the if statement: +```java +if (matchx("else")) { + parseStatement(); + fScope = _scope; + + // Scope[$ctrl:False, arg:arg][b:1, c:0] + } + +``` +This branch only modified the value of `b`. +When merging these 2 scopes together, we know for sure that none of the branches introduced new symbols, this means that the +order of the name bindings stayed the same. +Excluding the first control node, we loop through and compare the nodes corresponding to the same name binding to see if the nodes are different, +if so we create a phi node representing this conflict: +```java +if( in(i) != that.in(i) ) // No need for redundant Phis + // in(i); 2 + // that.in(in); 1 + setDef(i, new PhiNode(ns[i], r, in(i), + that.in(i)).peephole()); +``` +`b` takes on different values depending on scope. (see above) +A Phi node is created with both values. + + +## Example +We show the graph for the following code snippet: ```java int a = 1; if (arg == 1) @@ -204,11 +269,12 @@ Pre-peephole we have: Post-peephole:  - +The common operator was pulled out and the Phi node only got applied to the operands. +Notice how only the second operand of the `==` changes, the first one stays the same(`arg`). The implementation is in [`PhiNode.idealize()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java#L31-L71) -## More examples +## More examples ```java int c = 3; int b = 2; @@ -250,6 +316,8 @@ return a;  +## `Stop` Nodes +Currently, they only have one input in the form of a `ReturnNode`. They mark the termination. [^1]: Click, C. (1995). diff --git a/chapter05/docs/05-graph9.svg b/chapter05/docs/05-graph9.svg new file mode 100644 index 00000000..dff4d63f --- /dev/null +++ b/chapter05/docs/05-graph9.svg @@ -0,0 +1,174 @@ +<?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.40.1 (20161225.0304) + --> +<!-- Title: chapter05 Pages: 1 --> +<svg width="277pt" height="496pt" viewBox="0.00 0.00 277.00 496.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 492)"> +<title>chapter05</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-492 273,-492 273,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-480 261,-480 261,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="109,-442 109,-468 173,-468 173,-442 109,-442"/> +<polygon fill="none" stroke="#000000" points="109,-442 109,-468 173,-468 173,-442 109,-442"/> +<text text-anchor="start" x="127.7805" y="-450.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="109,-410 109,-442 173,-442 173,-410 109,-410"/> +<polygon fill="#ffff00" stroke="transparent" points="114,-415 114,-437 145,-437 145,-415 114,-415"/> +<polygon fill="none" stroke="#000000" points="114,-415 114,-437 145,-437 145,-415 114,-415"/> +<text text-anchor="start" x="116.6718" y="-421.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +<polygon fill="none" stroke="#000000" points="145,-415 145,-437 168,-437 168,-415 145,-415"/> +<text text-anchor="start" x="147.5624" y="-421.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="#ffff00" stroke="#000000" points="179,-52 125,-52 125,-16 179,-16 179,-52"/> +<text text-anchor="middle" x="152" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Stop</text> +</g> +<!-- Return20 --> +<g id="node10" class="node"> +<title>Return20</title> +<polygon fill="#ffff00" stroke="#000000" points="179.1025,-124 124.8975,-124 124.8975,-88 179.1025,-88 179.1025,-124"/> +<text text-anchor="middle" x="152" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Stop3->Return20 --> +<g id="edge1" class="edge"> +<title>Stop3->Return20</title> +<path fill="none" stroke="#ff0000" d="M152,-52.1686C152,-59.869 152,-69.0257 152,-77.5834"/> +<polygon fill="#ff0000" stroke="#ff0000" points="148.5001,-77.5867 152,-87.5867 155.5001,-77.5868 148.5001,-77.5867"/> +<text text-anchor="middle" x="149.7764" y="-54.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Con_8 --> +<g id="node3" class="node"> +<title>Con_8</title> +<ellipse fill="none" stroke="#000000" cx="226" cy="-439" rx="27" ry="18"/> +<text text-anchor="middle" x="226" y="-434.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- EQ9 --> +<g id="node4" class="node"> +<title>EQ9</title> +<ellipse fill="none" stroke="#000000" cx="207" cy="-352" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-347.8" font-family="Times,serif" font-size="14.00" fill="#000000">==</text> +</g> +<!-- EQ9->Start2 --> +<g id="edge2" class="edge"> +<title>EQ9->Start2:p1</title> +<path fill="none" stroke="#000000" d="M188.0971,-364.9135C176.261,-374.4033 162.483,-388.4885 158.2807,-405.0084"/> +<polygon fill="#000000" stroke="#000000" points="154.7998,-404.6361 157,-415 161.743,-405.5261 154.7998,-404.6361"/> +<text text-anchor="middle" x="190.3207" y="-367.3135" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- EQ9->Con_8 --> +<g id="edge3" class="edge"> +<title>EQ9->Con_8</title> +<path fill="none" stroke="#000000" d="M210.9368,-370.0265C213.5098,-381.8082 216.9235,-397.4393 219.8505,-410.8419"/> +<polygon fill="#000000" stroke="#000000" points="216.5151,-411.9737 222.0682,-420.9966 223.3539,-410.4801 216.5151,-411.9737"/> +<text text-anchor="middle" x="208.7132" y="-372.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- If10 --> +<g id="node5" class="node"> +<title>If10</title> +<polygon fill="#ffff00" stroke="transparent" points="169,-268 169,-294 246,-294 246,-268 169,-268"/> +<polygon fill="none" stroke="#000000" points="169,-268 169,-294 246,-294 246,-268 169,-268"/> +<text text-anchor="start" x="202.8394" y="-276.4" font-family="Times,serif" font-size="14.00" fill="#000000">If</text> +<polygon fill="none" stroke="#000000" points="169,-236 169,-268 246,-268 246,-236 169,-236"/> +<polygon fill="#ffff00" stroke="transparent" points="174,-241 174,-263 206,-263 206,-241 174,-241"/> +<polygon fill="none" stroke="#000000" points="174,-241 174,-263 206,-263 206,-241 174,-241"/> +<text text-anchor="start" x="176.7861" y="-247.4" font-family="Times,serif" font-size="14.00" fill="#000000">True</text> +<polygon fill="#ffff00" stroke="transparent" points="206,-241 206,-263 241,-263 241,-241 206,-241"/> +<polygon fill="none" stroke="#000000" points="206,-241 206,-263 241,-263 241,-241 206,-241"/> +<text text-anchor="start" x="208.7265" y="-247.4" font-family="Times,serif" font-size="14.00" fill="#000000">False</text> +</g> +<!-- If10->Start2 --> +<g id="edge4" class="edge"> +<title>If10->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M177.9557,-298.2089C157.4684,-324.8446 133.0529,-364.3668 129.4523,-404.9472"/> +<polygon fill="#ff0000" stroke="#ff0000" points="125.9531,-404.8528 129,-415 132.946,-405.1674 125.9531,-404.8528"/> +<text text-anchor="middle" x="175.7321" y="-300.6089" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- If10->EQ9 --> +<g id="edge5" class="edge"> +<title>If10->EQ9</title> +<path fill="none" stroke="#000000" d="M207,-298.3877C207,-306.7839 207,-315.7123 207,-323.8253"/> +<polygon fill="#000000" stroke="#000000" points="203.5001,-323.9075 207,-333.9075 210.5001,-323.9075 203.5001,-323.9075"/> +<text text-anchor="middle" x="204.7764" y="-300.7877" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Con_14 --> +<g id="node6" class="node"> +<title>Con_14</title> +<ellipse fill="none" stroke="#000000" cx="43" cy="-265" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-260.8" font-family="Times,serif" font-size="14.00" fill="#000000">2</text> +</g> +<!-- Con_16 --> +<g id="node7" class="node"> +<title>Con_16</title> +<ellipse fill="none" stroke="#000000" cx="115" cy="-265" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-260.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- Region17 --> +<g id="node8" class="node"> +<title>Region17</title> +<polygon fill="#ffff00" stroke="#000000" points="217.4435,-196 160.5565,-196 160.5565,-160 217.4435,-160 217.4435,-196"/> +<text text-anchor="middle" x="189" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">Region</text> +</g> +<!-- Region17->If10 --> +<g id="edge6" class="edge"> +<title>Region17->If10:p0</title> +<path fill="none" stroke="#ff0000" d="M189.4415,-196.1943C189.6508,-206.0242 189.874,-218.6285 189.9616,-230.8706"/> +<polygon fill="#ff0000" stroke="#ff0000" points="186.462,-231.0134 190,-241 193.4619,-230.9868 186.462,-231.0134"/> +<text text-anchor="middle" x="187.2179" y="-198.5943" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Region17->If10 --> +<g id="edge7" class="edge"> +<title>Region17->If10:p1</title> +<path fill="none" stroke="#ff0000" d="M205.4751,-196.1305C212.7091,-205.5926 220.1774,-217.8998 222.9129,-230.93"/> +<polygon fill="#ff0000" stroke="#ff0000" points="219.4469,-231.4334 224,-241 226.4064,-230.6821 219.4469,-231.4334"/> +<text text-anchor="middle" x="203.2515" y="-198.5305" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Phi_b18 --> +<g id="node9" class="node"> +<title>Phi_b18</title> +<ellipse fill="#ffffe0" stroke="#000000" cx="115" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">φ_b</text> +</g> +<!-- Phi_b18->Con_14 --> +<g id="edge9" class="edge"> +<title>Phi_b18->Con_14</title> +<path fill="none" stroke="#000000" d="M101.7941,-193.9571C90.8328,-207.202 75.0821,-226.2341 62.6416,-241.2664"/> +<polygon fill="#000000" stroke="#000000" points="59.8015,-239.2086 56.1222,-249.144 65.1943,-243.6716 59.8015,-239.2086"/> +<text text-anchor="middle" x="99.5705" y="-196.3571" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Phi_b18->Con_16 --> +<g id="edge10" class="edge"> +<title>Phi_b18->Con_16</title> +<path fill="none" stroke="#000000" d="M115,-196.0265C115,-207.8082 115,-223.4393 115,-236.8419"/> +<polygon fill="#000000" stroke="#000000" points="111.5001,-236.9966 115,-246.9966 118.5001,-236.9967 111.5001,-236.9966"/> +<text text-anchor="middle" x="112.7764" y="-198.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Phi_b18->Region17 --> +<g id="edge8" class="edge"> +<title>Phi_b18->Region17</title> +<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M142.1719,-178C144.9348,-178 147.6977,-178 150.4605,-178"/> +<polygon fill="#000000" stroke="#000000" points="150.4641,-181.5001 160.4641,-178 150.4641,-174.5001 150.4641,-181.5001"/> +<text text-anchor="middle" x="144.3955" y="-170.8" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return20->Region17 --> +<g id="edge11" class="edge"> +<title>Return20->Region17</title> +<path fill="none" stroke="#ff0000" d="M161.3367,-124.1686C165.4243,-132.1229 170.3104,-141.631 174.8309,-150.4277"/> +<polygon fill="#ff0000" stroke="#ff0000" points="171.8539,-152.2922 179.5376,-159.5867 178.0799,-149.0926 171.8539,-152.2922"/> +<text text-anchor="middle" x="159.1131" y="-126.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return20->Phi_b18 --> +<g id="edge12" class="edge"> +<title>Return20->Phi_b18</title> +<path fill="none" stroke="#000000" d="M142.6633,-124.1686C138.4051,-132.4549 133.2804,-142.4273 128.6051,-151.5252"/> +<polygon fill="#000000" stroke="#000000" points="125.4085,-150.0882 123.9508,-160.5823 131.6345,-153.2877 125.4085,-150.0882"/> +<text text-anchor="middle" x="140.4397" y="-126.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +</g> +</svg>
\ No newline at end of file |
