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 /chapter04 | |
| 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 'chapter04')
23 files changed, 485 insertions, 367 deletions
diff --git a/chapter04/README.md b/chapter04/README.md index 2700a6a9..350b08b5 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -15,12 +15,12 @@ Here is the [complete language grammar](docs/04-grammar.md) for this chapter. In this chapter we add some new nodes and revise some existing nodes. Following are revised or new nodes -| Node Name | Type | Description | Inputs | Value | -|-----------|------------------|------------------------------------------------|--------------------------------|-------------------------------------------------------------------------| -| MultiNode | Abstract class | A node that has a tuple result | | A tuple | -| Start | Control | Start of function, now a MultiNode | An input argument named `arg`. | A tuple with a ctrl token and an `arg` data node | -| Proj | ? | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | -| Bool | Data | Represents results of a comparison operator | Two data nodes | Result a comparison, represented as integer value where 1=true, 0=false | +| Node Name | Type | Description | Inputs | Value | +|-----------|----------------|------------------------------------------------|-----------------------|----------------------------------------------------------------------------| +| MultiNode | Abstract class | A node that has a tuple result | | A tuple | +| Start | Control | Start of function, now a MultiNode | | A tuple with a ctrl token and an `arg` data node | +| Proj | ? | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | +| Bool | Data | Represents results of a comparison operator | Two data nodes | Result is a comparison, represented as integer value where 1=true, 0=false | Below is our list of Nodes from [Chapter 3](../chapter03/README.md): @@ -116,13 +116,18 @@ In previous chapters, we had a hard coded control input edge from Start to Return. In this chapter we no longer have such a hard-wired edge. Instead, we track the current in-scope control node via the name `$ctrl`. This means that when we need to create an edge to the predecessor control node, we simply -lookup this name in the current scope. +look up this name in the current scope. -This introduces the idea that the control flow subgraph is a Petri net model [[1]](#1). +This introduces the idea that the control flow subgraph is a Petri net model.[^1] The control token moves virtually from node to node as execution proceeds. The initial control token is in Start, it then moves via the Proj node to Return. In later chapters we will see how the token moves across branches. +## Note Regarding Visualizations + +From this chapter onwards we omit the edges from Constants to Start node, mainly to reduce +clutter and help draw reader's attention to the more important aspects of the graph. + ## More Peephole Optimizations Now that we have non-constant integer values, we do additional optimizations, rearranging algebraic @@ -246,7 +251,5 @@ The reason this is done is that we know `m` is the new replacement and is alive, but since it is not yet part of the graph up the tree, it has no users yet. By adding a bogus user we prevent it being mistaken for dead and being killed. -## References -<a id="1">[1]</a> -Click, C. (1995). -Combining Analyses, Combining Optimizations, 131. +[^1]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 131. diff --git a/chapter04/docs/04-post-peephole.gv b/chapter04/docs/04-post-peephole.gv index 22f55468..51e176bc 100644 --- a/chapter04/docs/04-post-peephole.gv +++ b/chapter04/docs/04-post-peephole.gv @@ -3,8 +3,10 @@ digraph chapter04 { return 1+arg+2; #showGraph; */ rankdir=BT; + ordering="in"; + concentrate="true"; subgraph cluster_Nodes { - Start1 [ shape=plaintext label=< + Start2 [ shape=plaintext label=< <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> <TR><TD BGCOLOR="yellow">Start</TD></TR> <TR><TD> @@ -14,28 +16,28 @@ return 1+arg+2; #showGraph; </TD></TR> </TABLE>> ]; - Con_9 [ label="#3" ]; - Add10 [ label="Add" ]; - Return11 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_10 [ label="#3" ]; + Add11 [ label="+" ]; + Return12 [ 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="cyan">0</TD><TD PORT="scope0_$ctrl">$ctrl</TD><TD PORT="scope0_arg">arg</TD></TR> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$ctrl">$ctrl</TD><TD PORT="Scope1_0_arg">arg</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="cyan">1</TD></TR> </TABLE>>]; } } - Add10 -> Start1:p1; - Add10 -> Con_9; - Return11 -> Start1:p0 [color=red]; - Return11 -> Add10; + edge [ fontname=Helvetica, fontsize=8 ]; + Add11 -> Start2:p1[taillabel=1]; + Add11 -> Con_10[taillabel=2]; + Return12 -> Start2:p0[taillabel=0; color=red]; + Return12 -> Add11[taillabel=1]; edge [style=dashed color=cornflowerblue]; - scope0:"scope0_$ctrl" -> Start1:p0; - scope0:"scope0_arg" -> Start1:p1; + Scope1_0:"Scope1_0_arg" -> Start2:p1; }
\ No newline at end of file diff --git a/chapter04/docs/04-post-peephole.svg b/chapter04/docs/04-post-peephole.svg index 5a45722c..550c16ef 100644 --- a/chapter04/docs/04-post-peephole.svg +++ b/chapter04/docs/04-post-peephole.svg @@ -14,16 +14,16 @@ <polygon fill="none" stroke="black" points="8,-8 8,-232 193,-232 193,-8 8,-8"/> </g> <g id="clust2" class="cluster"> -<title>cluster_0</title> +<title>cluster_Scope1_0</title> <polygon fill="none" stroke="black" points="201,-72 201,-140 401,-140 401,-72 201,-72"/> </g> <g id="clust3" class="cluster"> -<title>cluster_1</title> +<title>cluster_Scope1_1</title> <polygon fill="none" stroke="black" points="323,-80 323,-132 393,-132 393,-80 323,-80"/> </g> -<!-- Start1 --> +<!-- Start2 --> <g id="node1" class="node"> -<title>Start1</title> +<title>Start2</title> <polygon fill="yellow" stroke="transparent" points="97,-195 97,-220 178,-220 178,-195 97,-195"/> <polygon fill="none" stroke="black" points="97,-195 97,-220 178,-220 178,-195 97,-195"/> <text text-anchor="start" x="119" y="-203.8" font-family="Times,serif" font-size="14.00">Start</text> @@ -34,51 +34,55 @@ <polygon fill="none" stroke="black" points="142,-169 142,-190 173,-190 173,-169 142,-169"/> <text text-anchor="start" x="145" y="-175.8" font-family="Times,serif" font-size="14.00">arg</text> </g> -<!-- Con_9 --> +<!-- Con_10 --> <g id="node2" class="node"> -<title>Con_9</title> +<title>Con_10</title> <ellipse fill="none" stroke="black" cx="43" cy="-192" rx="27" ry="18"/> <text text-anchor="middle" x="43" y="-188.3" font-family="Times,serif" font-size="14.00">#3</text> </g> -<!-- Add10 --> +<!-- Add11 --> <g id="node3" class="node"> -<title>Add10</title> -<ellipse fill="none" stroke="black" cx="156" cy="-106" rx="28.7" ry="18"/> -<text text-anchor="middle" x="156" y="-102.3" font-family="Times,serif" font-size="14.00">Add</text> +<title>Add11</title> +<ellipse fill="none" stroke="black" cx="158" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="158" y="-102.3" font-family="Times,serif" font-size="14.00">+</text> </g> -<!-- Add10->Start1 --> +<!-- Add11->Start2 --> <g id="edge1" class="edge"> -<title>Add10->Start1:p1</title> -<path fill="none" stroke="black" d="M156.86,-124.09C157.28,-133.54 157.73,-145.77 157.92,-157.68"/> -<polygon fill="black" stroke="black" points="154.42,-158.03 158,-168 161.42,-157.97 154.42,-158.03"/> +<title>Add11->Start2:p1</title> +<path fill="none" stroke="black" d="M158,-124.09C158,-133.55 158,-145.77 158,-157.69"/> +<polygon fill="black" stroke="black" points="154.5,-158 158,-168 161.5,-158 154.5,-158"/> +<text text-anchor="middle" x="155" y="-126.69" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </g> -<!-- Add10->Con_9 --> +<!-- Add11->Con_10 --> <g id="edge2" class="edge"> -<title>Add10->Con_9</title> -<path fill="none" stroke="black" d="M136.93,-119.61C121.35,-130.08 98.91,-145.53 80,-160 75.7,-163.29 71.22,-166.89 66.91,-170.44"/> -<polygon fill="black" stroke="black" points="64.38,-168 58.96,-177.1 68.87,-173.37 64.38,-168"/> +<title>Add11->Con_10</title> +<path fill="none" stroke="black" d="M139.03,-119.12C123,-129.54 99.59,-145.19 80,-160 75.68,-163.26 71.19,-166.85 66.88,-170.4"/> +<polygon fill="black" stroke="black" points="64.34,-167.96 58.92,-177.06 68.84,-173.32 64.34,-167.96"/> +<text text-anchor="middle" x="136.03" y="-121.72" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> </g> -<!-- Return11 --> +<!-- Return12 --> <g id="node4" class="node"> -<title>Return11</title> -<polygon fill="yellow" stroke="black" points="163,-52 97,-52 97,-16 163,-16 163,-52"/> -<text text-anchor="middle" x="130" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> +<title>Return12</title> +<polygon fill="yellow" stroke="black" points="165,-52 99,-52 99,-16 165,-16 165,-52"/> +<text text-anchor="middle" x="132" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> </g> -<!-- Return11->Start1 --> +<!-- Return12->Start2 --> <g id="edge3" class="edge"> -<title>Return11->Start1:p0</title> -<path fill="none" stroke="red" d="M123.24,-52.04C121.12,-58.23 119.05,-65.33 118,-72 113.28,-101.85 115.86,-109.85 118,-140 118.58,-148.23 120.12,-152.3 121.11,-157.68"/> -<polygon fill="red" stroke="red" points="117.66,-158.34 122,-168 124.63,-157.74 117.66,-158.34"/> +<title>Return12->Start2:p0</title> +<path fill="none" stroke="red" d="M126.36,-52.13C124.59,-58.32 122.88,-65.4 122,-72 116.87,-110.66 121.12,-123.21 121.89,-157.66"/> +<polygon fill="red" stroke="red" points="118.39,-158.04 122,-168 125.39,-157.96 118.39,-158.04"/> +<text text-anchor="middle" x="123.36" y="-54.73" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Return11->Add10 --> +<!-- Return12->Add11 --> <g id="edge4" class="edge"> -<title>Return11->Add10</title> -<path fill="none" stroke="black" d="M136.43,-52.3C139.4,-60.3 142.99,-69.98 146.29,-78.85"/> -<polygon fill="black" stroke="black" points="143.06,-80.22 149.83,-88.38 149.63,-77.78 143.06,-80.22"/> +<title>Return12->Add11</title> +<path fill="none" stroke="black" d="M138.43,-52.3C141.4,-60.3 144.99,-69.98 148.29,-78.85"/> +<polygon fill="black" stroke="black" points="145.06,-80.22 151.83,-88.38 151.63,-77.78 145.06,-80.22"/> +<text text-anchor="middle" x="135.43" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </g> -<!-- scope0 --> +<!-- Scope1_0 --> <g id="node5" class="node"> -<title>scope0</title> +<title>Scope1_0</title> <polygon fill="cyan" stroke="transparent" points="218,-95 218,-116 234,-116 234,-95 218,-95"/> <polygon fill="none" stroke="black" points="218,-95 218,-116 234,-116 234,-95 218,-95"/> <text text-anchor="start" x="221" y="-101.8" font-family="Times,serif" font-size="14.00">0</text> @@ -87,21 +91,15 @@ <polygon fill="none" stroke="black" points="274,-95 274,-116 305,-116 305,-95 274,-95"/> <text text-anchor="start" x="277" y="-101.8" font-family="Times,serif" font-size="14.00">arg</text> </g> -<!-- scope0->Start1 --> +<!-- Scope1_0->Start2 --> <g id="edge5" class="edge"> -<title>scope0:scope0_$ctrl->Start1:p0</title> -<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M254,-117C254,-176.09 137.5,-113.66 123.39,-158.03"/> -<polygon fill="cornflowerblue" stroke="cornflowerblue" points="119.92,-157.61 122,-168 126.85,-158.58 119.92,-157.61"/> -</g> -<!-- scope0->Start1 --> -<g id="edge6" class="edge"> -<title>scope0:scope0_arg->Start1:p1</title> +<title>Scope1_0:Scope1_0_arg->Start2:p1</title> <path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M290,-117C290,-172.03 239,-178.4 184.25,-178.95"/> <polygon fill="cornflowerblue" stroke="cornflowerblue" points="183.98,-175.45 174,-179 184.02,-182.45 183.98,-175.45"/> </g> -<!-- scope1 --> +<!-- Scope1_1 --> <g id="node6" class="node"> -<title>scope1</title> +<title>Scope1_1</title> <polygon fill="cyan" stroke="transparent" points="350,-95 350,-116 366,-116 366,-95 350,-95"/> <polygon fill="none" stroke="black" points="350,-95 350,-116 366,-116 366,-95 350,-95"/> <text text-anchor="start" x="353" y="-101.8" font-family="Times,serif" font-size="14.00">1</text> diff --git a/chapter04/docs/04-pre-peephole.gv b/chapter04/docs/04-pre-peephole.gv index e8016c87..b6fefc2d 100644 --- a/chapter04/docs/04-pre-peephole.gv +++ b/chapter04/docs/04-pre-peephole.gv @@ -3,8 +3,10 @@ digraph chapter04 { return 1+arg+2; #showGraph; */ rankdir=BT; + ordering="in"; + concentrate="true"; subgraph cluster_Nodes { - Start1 [ shape=plaintext label=< + Start2 [ shape=plaintext label=< <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> <TR><TD BGCOLOR="yellow">Start</TD></TR> <TR><TD> @@ -14,32 +16,32 @@ return 1+arg+2; #showGraph; </TD></TR> </TABLE>> ]; - Con_4 [ label="#1" ]; - Con_5 [ label="#2" ]; - Add6 [ label="Add" ]; - Add7 [ label="Add" ]; - Return8 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_5 [ label="#1" ]; + Con_6 [ label="#2" ]; + Add7 [ label="+" ]; + Add8 [ label="+" ]; + Return9 [ 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="cyan">0</TD><TD PORT="scope0_$ctrl">$ctrl</TD><TD PORT="scope0_arg">arg</TD></TR> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$ctrl">$ctrl</TD><TD PORT="Scope1_0_arg">arg</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="cyan">1</TD></TR> </TABLE>>]; } } - Add6 -> Start1:p1; - Add6 -> Con_5; - Add7 -> Con_4; - Add7 -> Add6; - Return8 -> Start1:p0 [color=red]; - Return8 -> Add7; + edge [ fontname=Helvetica, fontsize=8 ]; + Add7 -> Start2:p1[taillabel=1]; + Add7 -> Con_6[taillabel=2]; + Add8 -> Con_5[taillabel=1]; + Add8 -> Add7[taillabel=2]; + Return9 -> Start2:p0[taillabel=0; color=red]; + Return9 -> Add8[taillabel=1]; edge [style=dashed color=cornflowerblue]; - scope0:"scope0_$ctrl" -> Start1:p0; - scope0:"scope0_arg" -> Start1:p1; -} + Scope1_0:"Scope1_0_arg" -> Start2:p1; +}
\ No newline at end of file diff --git a/chapter04/docs/04-pre-peephole.svg b/chapter04/docs/04-pre-peephole.svg index b1ab4eee..9ec38d27 100644 --- a/chapter04/docs/04-pre-peephole.svg +++ b/chapter04/docs/04-pre-peephole.svg @@ -14,16 +14,16 @@ <polygon fill="none" stroke="black" points="8,-8 8,-304 193,-304 193,-8 8,-8"/> </g> <g id="clust2" class="cluster"> -<title>cluster_0</title> +<title>cluster_Scope1_0</title> <polygon fill="none" stroke="black" points="201,-144 201,-212 401,-212 401,-144 201,-144"/> </g> <g id="clust3" class="cluster"> -<title>cluster_1</title> +<title>cluster_Scope1_1</title> <polygon fill="none" stroke="black" points="323,-152 323,-204 393,-204 393,-152 323,-152"/> </g> -<!-- Start1 --> +<!-- Start2 --> <g id="node1" class="node"> -<title>Start1</title> +<title>Start2</title> <polygon fill="yellow" stroke="transparent" points="97,-267 97,-292 178,-292 178,-267 97,-267"/> <polygon fill="none" stroke="black" points="97,-267 97,-292 178,-292 178,-267 97,-267"/> <text text-anchor="start" x="119" y="-275.8" font-family="Times,serif" font-size="14.00">Start</text> @@ -34,75 +34,81 @@ <polygon fill="none" stroke="black" points="142,-241 142,-262 173,-262 173,-241 142,-241"/> <text text-anchor="start" x="145" y="-247.8" font-family="Times,serif" font-size="14.00">arg</text> </g> -<!-- Con_4 --> +<!-- Con_5 --> <g id="node2" class="node"> -<title>Con_4</title> -<ellipse fill="none" stroke="black" cx="119" cy="-178" rx="27" ry="18"/> -<text text-anchor="middle" x="119" y="-174.3" font-family="Times,serif" font-size="14.00">#1</text> +<title>Con_5</title> +<ellipse fill="none" stroke="black" cx="115" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-174.3" font-family="Times,serif" font-size="14.00">#1</text> </g> -<!-- Con_5 --> +<!-- Con_6 --> <g id="node3" class="node"> -<title>Con_5</title> +<title>Con_6</title> <ellipse fill="none" stroke="black" cx="43" cy="-264" rx="27" ry="18"/> <text text-anchor="middle" x="43" y="-260.3" font-family="Times,serif" font-size="14.00">#2</text> </g> -<!-- Add6 --> +<!-- Add7 --> <g id="node4" class="node"> -<title>Add6</title> -<ellipse fill="none" stroke="black" cx="45" cy="-178" rx="28.7" ry="18"/> -<text text-anchor="middle" x="45" y="-174.3" font-family="Times,serif" font-size="14.00">Add</text> +<title>Add7</title> +<ellipse fill="none" stroke="black" cx="43" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-174.3" font-family="Times,serif" font-size="14.00">+</text> </g> -<!-- Add6->Start1 --> +<!-- Add7->Start2 --> <g id="edge1" class="edge"> -<title>Add6->Start1:p1</title> -<path fill="none" stroke="black" d="M59.56,-193.83C66.26,-200.06 74.59,-207 83,-212 110.12,-228.12 148.12,-209.69 156.37,-230.12"/> -<polygon fill="black" stroke="black" points="152.92,-230.7 158,-240 159.83,-229.56 152.92,-230.7"/> +<title>Add7->Start2:p1</title> +<path fill="none" stroke="black" d="M56.63,-193.93C62.95,-200.18 70.86,-207.11 79,-212 107.43,-229.09 147.88,-208.4 156.39,-229.99"/> +<polygon fill="black" stroke="black" points="152.96,-230.68 158,-240 159.87,-229.57 152.96,-230.68"/> +<text text-anchor="middle" x="53.63" y="-196.53" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </g> -<!-- Add6->Con_5 --> +<!-- Add7->Con_6 --> <g id="edge2" class="edge"> -<title>Add6->Con_5</title> -<path fill="none" stroke="black" d="M44.6,-196C44.33,-207.31 43.97,-222.42 43.66,-235.43"/> -<polygon fill="black" stroke="black" points="40.15,-235.66 43.41,-245.74 47.15,-235.82 40.15,-235.66"/> +<title>Add7->Con_6</title> +<path fill="none" stroke="black" d="M43,-196.4C43,-207.74 43,-222.77 43,-235.68"/> +<polygon fill="black" stroke="black" points="39.5,-235.9 43,-245.9 46.5,-235.9 39.5,-235.9"/> +<text text-anchor="middle" x="40" y="-199" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> </g> -<!-- Add7 --> +<!-- Add8 --> <g id="node5" class="node"> -<title>Add7</title> -<ellipse fill="none" stroke="black" cx="117" cy="-106" rx="28.7" ry="18"/> -<text text-anchor="middle" x="117" y="-102.3" font-family="Times,serif" font-size="14.00">Add</text> +<title>Add8</title> +<ellipse fill="none" stroke="black" cx="115" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-102.3" font-family="Times,serif" font-size="14.00">+</text> </g> -<!-- Add7->Con_4 --> +<!-- Add8->Con_5 --> <g id="edge3" class="edge"> -<title>Add7->Con_4</title> -<path fill="none" stroke="black" d="M117.49,-124.3C117.71,-132.02 117.98,-141.29 118.23,-149.89"/> -<polygon fill="black" stroke="black" points="114.73,-150 118.51,-159.9 121.72,-149.8 114.73,-150"/> +<title>Add8->Con_5</title> +<path fill="none" stroke="black" d="M115,-124.3C115,-132.02 115,-141.29 115,-149.89"/> +<polygon fill="black" stroke="black" points="111.5,-149.9 115,-159.9 118.5,-149.9 111.5,-149.9"/> +<text text-anchor="middle" x="112" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> </g> -<!-- Add7->Add6 --> +<!-- Add8->Add7 --> <g id="edge4" class="edge"> -<title>Add7->Add6</title> -<path fill="none" stroke="black" d="M102.08,-121.5C92.04,-131.27 78.62,-144.31 67.32,-155.3"/> -<polygon fill="black" stroke="black" points="64.63,-153.03 59.9,-162.51 69.51,-158.05 64.63,-153.03"/> +<title>Add8->Add7</title> +<path fill="none" stroke="black" d="M100.43,-121.17C90.25,-131.06 76.48,-144.45 64.97,-155.64"/> +<polygon fill="black" stroke="black" points="62.53,-153.13 57.8,-162.62 67.41,-158.15 62.53,-153.13"/> +<text text-anchor="middle" x="97.43" y="-123.77" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> </g> -<!-- Return8 --> +<!-- Return9 --> <g id="node6" class="node"> -<title>Return8</title> -<polygon fill="yellow" stroke="black" points="167,-52 101,-52 101,-16 167,-16 167,-52"/> -<text text-anchor="middle" x="134" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> +<title>Return9</title> +<polygon fill="yellow" stroke="black" points="166,-52 100,-52 100,-16 166,-16 166,-52"/> +<text text-anchor="middle" x="133" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> </g> -<!-- Return8->Start1 --> +<!-- Return9->Start2 --> <g id="edge5" class="edge"> -<title>Return8->Start1:p0</title> -<path fill="none" stroke="red" d="M142.72,-52.17C147.37,-62.31 152.62,-75.56 155,-88 165.33,-142.13 178.15,-161.99 155,-212 148.81,-225.36 132.76,-223.4 125.57,-230.38"/> -<polygon fill="red" stroke="red" points="122.2,-229.41 122,-240 128.76,-231.84 122.2,-229.41"/> +<title>Return9->Start2:p0</title> +<path fill="none" stroke="red" d="M140.48,-52.3C144.47,-62.48 148.97,-75.73 151,-88 159.98,-142.37 172.54,-161.27 151,-212 145.75,-224.37 132.06,-223.86 125.55,-230.39"/> +<polygon fill="red" stroke="red" points="122.18,-229.41 122,-240 128.74,-231.83 122.18,-229.41"/> +<text text-anchor="middle" x="137.48" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> </g> -<!-- Return8->Add7 --> +<!-- Return9->Add8 --> <g id="edge6" class="edge"> -<title>Return8->Add7</title> -<path fill="none" stroke="black" d="M129.8,-52.3C127.9,-60.1 125.62,-69.49 123.52,-78.17"/> -<polygon fill="black" stroke="black" points="120.11,-77.35 121.15,-87.9 126.92,-79 120.11,-77.35"/> +<title>Return9->Add8</title> +<path fill="none" stroke="black" d="M128.55,-52.3C126.55,-60.1 124.13,-69.49 121.9,-78.17"/> +<polygon fill="black" stroke="black" points="118.5,-77.34 119.4,-87.9 125.28,-79.08 118.5,-77.34"/> +<text text-anchor="middle" x="125.55" 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> +<title>Scope1_0</title> <polygon fill="cyan" stroke="transparent" points="218,-167 218,-188 234,-188 234,-167 218,-167"/> <polygon fill="none" stroke="black" points="218,-167 218,-188 234,-188 234,-167 218,-167"/> <text text-anchor="start" x="221" y="-173.8" font-family="Times,serif" font-size="14.00">0</text> @@ -111,21 +117,15 @@ <polygon fill="none" stroke="black" points="274,-167 274,-188 305,-188 305,-167 274,-167"/> <text text-anchor="start" x="277" y="-173.8" font-family="Times,serif" font-size="14.00">arg</text> </g> -<!-- scope0->Start1 --> +<!-- Scope1_0->Start2 --> <g id="edge7" class="edge"> -<title>scope0:scope0_$ctrl->Start1:p0</title> -<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M254,-189C254,-248.09 137.5,-185.66 123.39,-230.03"/> -<polygon fill="cornflowerblue" stroke="cornflowerblue" points="119.92,-229.61 122,-240 126.85,-230.58 119.92,-229.61"/> -</g> -<!-- scope0->Start1 --> -<g id="edge8" class="edge"> -<title>scope0:scope0_arg->Start1:p1</title> +<title>Scope1_0:Scope1_0_arg->Start2:p1</title> <path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M290,-189C290,-244.03 239,-250.4 184.25,-250.95"/> <polygon fill="cornflowerblue" stroke="cornflowerblue" points="183.98,-247.45 174,-251 184.02,-254.45 183.98,-247.45"/> </g> -<!-- scope1 --> +<!-- Scope1_1 --> <g id="node8" class="node"> -<title>scope1</title> +<title>Scope1_1</title> <polygon fill="cyan" stroke="transparent" points="350,-167 350,-188 366,-188 366,-167 350,-167"/> <polygon fill="none" stroke="black" points="350,-167 350,-188 366,-188 366,-167 350,-167"/> <text text-anchor="start" x="353" y="-173.8" font-family="Times,serif" font-size="14.00">1</text> diff --git a/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index f73bfd3c..f624cbde 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.TypeControl; import java.util.*; @@ -29,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); @@ -51,10 +57,10 @@ 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 ProjNode ) - continue; // Do not emit, rolled into MultiNode already + if( n instanceof ProjNode || n instanceof ScopeNode ) + continue; // Do not emit, rolled into MultiNode or Scope cluster already sb.append("\t\t").append(n.uniqueName()).append(" [ "); - String lab = n.label(); + String lab = n.glabel(); if( n instanceof MultiNode ) { // Make a box with the MultiNode on top, and all the projections on the bottom sb.append("shape=plaintext label=<\n"); @@ -71,8 +77,8 @@ public class GraphVisualizer { sb.append("\t\t\t\t<TR>"); } sb.append("<TD PORT=\"p").append(proj._idx).append("\""); - if( proj._idx==0 ) sb.append(" BGCOLOR=\"yellow\""); - sb.append(">").append(proj.label()).append("</TD>"); + if( proj.isCFG() ) sb.append(" BGCOLOR=\"yellow\""); + sb.append(">").append(proj.glabel()).append("</TD>"); } } if (doProjTable) { @@ -86,7 +92,7 @@ public class GraphVisualizer { } else { // 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(lab).append("\" "); } @@ -99,8 +105,8 @@ 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 @@ -116,31 +122,38 @@ 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 makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } - private boolean isControlEdge(Node def) { - return def._type instanceof TypeControl; - } + 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) { + // All them edge labels + sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n"); for( Node n : all ) { - if( n instanceof ConstantNode || n instanceof ProjNode ) - continue; // Do not display the Constant->Start edge; ProjNodes handled by Multi - for( Node def : n._inputs ) + // Do not display the Constant->Start edge; + // ProjNodes handled by Multi; + // ScopeNodes are done separately + if( n instanceof ConstantNode || n instanceof ProjNode || 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(" -> "); if( def instanceof ProjNode proj ) { String mname = proj.ctrl().uniqueName(); sb.append(mname).append(":p").append(proj._idx); } else sb.append(def.uniqueName()); - // Control edges are colored red - if( isControlEdge(def) ) - sb.append(" [color=red]"); - sb.append(";\n"); + // Number edges, so we can see how they track + sb.append("[taillabel=").append(i); + // control edges are colored red + if( def.isCFG() ) + sb.append(" color=red"); + sb.append("];\n"); } + i++; + } } } @@ -149,7 +162,7 @@ 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); + String scopeName = makeScopeName(scopenode, level); for( String name : scope.keySet() ) { Node def = scopenode.in(scope.get(name)); if( def==null ) continue; diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java index 275a4ebd..b505c2c5 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java @@ -15,6 +15,12 @@ import java.util.*; public class Parser { /** + * The control is a name that binds to the currently active control + * node in the graph + */ + public static final String CTRL = "$ctrl"; + + /** * A Global Static, unique to each compilation. This is a public, so we * can make constants everywhere without having to thread the StartNode * through the entire parser and optimizer. @@ -23,6 +29,7 @@ public class Parser { */ public static StartNode START; + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; /** @@ -31,10 +38,19 @@ 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, TypeInteger arg) { _lexer = new Lexer(source); - _scope = new ScopeNode(); Node.reset(); + _scope = new ScopeNode(); START = new StartNode(new Type[]{ Type.CONTROL, arg }); START.peephole(); } @@ -45,17 +61,23 @@ public class Parser { String src() { return new String( _lexer._input ); } + private Node ctrl() { return _scope.ctrl(); } + private Node ctrl(Node n) { return _scope.ctrl(n); } - public ReturnNode parse() { + public ReturnNode parse() { return parse(false); } + public ReturnNode parse(boolean show) { _scope.push(); try { - _scope.define("$ctrl", new ProjNode(START, 0, "$ctrl").peephole()); - _scope.define("arg" , new ProjNode(START, 1, "arg" ).peephole()); - return (ReturnNode) parseBlock(false); + _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole()); + _scope.define("arg", new ProjNode(START, 1, "arg").peephole()); + var ret = (ReturnNode) parseBlock(); + if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + return ret; } finally { _scope.pop(); + if( show ) showGraph(); } } @@ -65,23 +87,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; @@ -93,12 +109,13 @@ 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(); } @@ -109,19 +126,20 @@ public class Parser { * <pre> * 'return' expr ; * </pre> + * @return an expression {@link Node}, never {@code null} */ private Node parseReturn() { var expr = require(parseExpression(), ";"); - Node ret = new ReturnNode(_scope.lookup("$ctrl"), expr); - _scope.update("$ctrl",null); + Node ret = new ReturnNode(ctrl(), expr).peephole(); + ctrl(null); // Kill control return ret; } /** * Dumps out the node graph + * @return {@code null} */ private Node showGraph() { - require(";"); System.out.println(new GraphVisualizer().generateDotOutput(this)); return null; } @@ -132,6 +150,7 @@ public class Parser { * <pre> * name '=' expression ';' * </pre> + * @return an expression {@link Node}, never {@code null} */ private Node parseExpressionStatement() { var name = requireId(); @@ -148,6 +167,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 @@ -163,11 +183,20 @@ public class Parser { * Parse an expression of the form: * * <pre> - * expr : additiveExpr + * expr : compareExpr * </pre> + * @return an expression {@link Node}, never {@code null} */ private Node parseExpression() { return parseComparison(); } + /** + * Parse an expression of the form: + * + * <pre> + * expr : additiveExpr op additiveExpr + * </pre> + * @return an comparator expression {@link Node}, never {@code null} + */ private Node parseComparison() { var lhs = parseAddition(); if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); @@ -185,6 +214,7 @@ public class Parser { * <pre> * additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)* * </pre> + * @return an add expression {@link Node}, never {@code null} */ private Node parseAddition() { var lhs = parseMultiplication(); @@ -199,6 +229,7 @@ public class Parser { * <pre> * multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)* * </pre> + * @return a multiply expression {@link Node}, never {@code null} */ private Node parseMultiplication() { var lhs = parseUnary(); @@ -213,6 +244,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(); @@ -225,15 +257,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.peephole(); + 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 + "'"); } /** @@ -251,13 +284,17 @@ 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 @@ -343,11 +380,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(); @@ -397,8 +447,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/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java index 8b157a9c..d4d15bef 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -3,12 +3,11 @@ 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 _print1(StringBuilder sb) { @@ -36,37 +35,64 @@ public class AddNode extends Node { Type t1 = lhs._type; Type t2 = rhs._type; + // Already handled by peephole constant folding + assert !(t1.isConstant() && t2.isConstant()); + // Add of 0. We do not check for (0+x) because this will already // canonicalize to (x+0) - if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 ) + if( t2 instanceof TypeInteger i && i.value()==0 ) return lhs; - - // Move constants to RHS: con+arg becomes arg+con - if ( t1.isConstant() && !t2.isConstant() ) { - Node tmp = in(1); // Swap inputs without letting either input go dead during the swap - _inputs.set(1,in(2)); - _inputs.set(2,tmp); - return this; - } - + + // Add of same to a multiply by 2 + if( lhs==rhs ) + return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); + // Goal: a left-spine set of adds, with constants on the rhs (which then fold). - // Do we have (x + con1) + con2 ? - // Rotate to x +(con1 + con2) - // The constants will fold on the next peephole. - if (t2.isConstant() && lhs instanceof AddNode && lhs.in(2)._type.isConstant() ) - return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + // Move non-adds to RHS + if( !(lhs instanceof AddNode) && rhs instanceof AddNode ) + return swap12(); - // Do we have x + (y + con) ? - // Swap to (x + y) + con - if (rhs instanceof AddNode add && add.in(2)._type.isConstant() ) - return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + // Now we might see (add add non) or (add non non) or (add add add) but never (add non add) - // Add of same to a multiply by 2 - if( lhs==rhs ) - return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); + // Do we have x + (y + z) ? + // Swap to (x + y) + z + // Rotate (add add add) to remove the add on RHS + if( rhs instanceof AddNode add ) + return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + + // Now we might see (add add non) or (add non non) but never (add non add) nor (add add add) + if( !(lhs instanceof AddNode) ) + return spline_cmp(lhs,rhs) ? swap12() : null; + + // Now we only see (add add non) + + // Do we have (x + con1) + con2? + // Replace with (x + (con1+con2) which then fold the constants + if( lhs.in(2)._type.isConstant() && t2.isConstant() ) + return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + + // Now we sort along the spline via rotates, to gather similar things together. + + // Do we rotate (x + y) + z + // into (x + z) + y ? + if( spline_cmp(lhs.in(2),rhs) ) + return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); return null; } + + // Compare two off-spline nodes and decide what order they should be in. + // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ? + // Generally constants always go right, then others. + // Ties with in a category sort by node ID. + // TRUE if swapping hi and lo. + static boolean spline_cmp( Node hi, Node lo ) { + if( lo._type.isConstant() ) return false; + if( hi._type.isConstant() ) return true ; + + // Same category of "others" + return lo._nid > hi._nid; + } } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java index b0e0bf42..02eb7ce9 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -13,7 +13,10 @@ abstract public class BoolNode extends Node { abstract String op(); // String opcode name @Override - public String label() { return op(); } + public String label() { return getClass().getSimpleName(); } + + @Override + public String glabel() { return op(); } @Override StringBuilder _print1(StringBuilder sb) { diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter04/src/main/java/com/seaofnodes/simple/node/Control.java deleted file mode 100644 index 48cf2b7a..00000000 --- a/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java index 1f562378..ae87deac 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -5,13 +5,12 @@ 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 _print1(StringBuilder sb) { in(1)._print0(sb.append("(")); diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 04084d0f..533155d9 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -5,12 +5,11 @@ 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 _print1(StringBuilder sb) { @@ -21,7 +20,7 @@ public class MinusNode extends Node { @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0) - return TypeInteger.constant(-i0.value()); + return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; return TypeBot.BOTTOM; } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java index e3e83b38..5f6c1ad8 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -5,12 +5,11 @@ 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); - } + public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } - @Override - public String label() { return "Mul"; } + @Override public String label() { return "Mul"; } + + @Override public String glabel() { return "*"; } @Override StringBuilder _print1(StringBuilder sb) { @@ -43,12 +42,8 @@ public class MulNode extends Node { return lhs; // Move constants to RHS: con*arg becomes arg*con - if ( t1.isConstant() && !t2.isConstant() ) { - Node tmp = in(1); // Swap inputs without letting either input go dead during the swap - _inputs.set(1,in(2)); - _inputs.set(2,tmp); - return this; - } + if ( t1.isConstant() && !t2.isConstant() ) + return swap12(); return null; } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java index e517c3d5..fe3fddf8 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -4,10 +4,6 @@ import com.seaofnodes.simple.type.Type; public abstract class MultiNode extends Node { - public MultiNode(Node... inputs) { - super(inputs); - } - - // Return the ProjNode with the idx - abstract ProjNode proj(int idx); + public MultiNode(Node... inputs) { super(inputs); } + } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java index 7cc9291c..804d30e0 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter04/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; @@ -61,13 +59,18 @@ public abstract class Node { _outputs = new ArrayList<>(); for( Node n : _inputs ) if( n != null ) - n._outputs.add( this ); + 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 @@ -101,24 +104,18 @@ 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 compute a {@link Type} and then check and replace: @@ -197,7 +194,7 @@ 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 @@ -219,11 +216,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); } @@ -266,7 +262,7 @@ public abstract class Node { // 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> @@ -332,14 +328,21 @@ public abstract class Node { */ public abstract Node idealize(); + + // ----------------------- + // Peephole utilities + + // Swap inputs without letting either input go dead during the swap. + Node swap12() { + Node tmp = in(1); + _inputs.set(1,in(2)); + _inputs.set(2,tmp); + return this; + } + /** * Used to allow repeating tests in the same JVM. This just resets the * 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/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java index be37c514..be0556ed 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -22,7 +22,9 @@ public class ProjNode extends Node { public String label() { return _label; } @Override - StringBuilder _print1(StringBuilder sb) { return sb.append("Proj_" +_nid); } + StringBuilder _print1(StringBuilder sb) { return sb.append(_label); } + + @Override public boolean isCFG() { return _idx==0; } public MultiNode ctrl() { return (MultiNode)in(0); } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index c94115bb..e20d01e5 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; -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 @@ -12,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); @@ -29,10 +28,11 @@ public class ReturnNode extends Node implements Control { return expr()._print0(sb.append("return ")).append(";"); } + @Override public boolean isCFG() { return true; } @Override public Type compute() { - return expr().compute(); + return new TypeTuple(TypeControl.CONTROL,expr()._type); } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 8bd81e82..45966791 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.TypeBot; import java.util.*; @@ -16,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 _print1(StringBuilder sb) { + sb.append(label()); for( HashMap<String,Integer> scope : _scopes ) { sb.append("["); boolean first=true; @@ -41,12 +45,11 @@ public class ScopeNode extends Node { @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. @@ -60,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); } @@ -72,7 +76,15 @@ public class ScopeNode extends Node { return null; } + public Node ctrl() { assert lookup(Parser.CTRL)==in(0); return in(0); } + + public Node ctrl(Node n) { + assert lookup(Parser.CTRL)==in(0); + set_def(0,n); + return n; + } + // 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--) { @@ -84,5 +96,4 @@ public class ScopeNode extends Node { return null; } - } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java index b59e3375..91573de8 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -11,7 +11,7 @@ import com.seaofnodes.simple.type.TypeTuple; * will require Projections to extract the values. We discuss this in detail * in Chapter 9: Functions and Calls. */ -public class StartNode extends MultiNode implements Control { +public class StartNode extends MultiNode { final TypeTuple _args; @@ -27,20 +27,12 @@ public class StartNode extends MultiNode implements Control { StringBuilder _print1(StringBuilder sb) { return sb.append(label()); } - + + @Override public boolean isCFG() { return true; } + @Override public TypeTuple compute() { return _args; } @Override public Node idealize() { return null; } - - - @Override - public ProjNode proj( int idx ) { - for( Node proj : _outputs ) - if( ((ProjNode)proj)._idx==idx ) - return (ProjNode)proj; - return null; - } - } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java index e5939e1b..42ddc1c1 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -5,12 +5,11 @@ 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 _print1(StringBuilder sb) { diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index b53b1b29..63c46035 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -26,7 +26,7 @@ public class TypeInteger extends Type { @Override public String toString() { - return _print(new StringBuilder()).toString(); + return _print(new StringBuilder()).toString(); } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index ef87a415..036147a2 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.type; public class TypeTuple extends Type { - + public final Type[] _types; - public TypeTuple(Type[] _types) { + public TypeTuple(Type... _types) { this._types = _types; } diff --git a/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java index ed999039..ebfe1399 100644 --- a/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -15,44 +15,44 @@ public class Chapter04Test { @Test public void testChapter4Peephole() { - Parser parser = new Parser("return 1+arg+2; #showGraph;", TypeInteger.BOT); + Parser parser = new Parser("return 1+arg+2; #showGraph;"); ReturnNode ret = parser.parse(); - assertEquals("return (Proj_3+3);", ret.print()); + assertEquals("return (arg+3);", ret.print()); } @Test public void testChapter4Peephole2() { - Parser parser = new Parser("return (1+arg)+2;", TypeInteger.BOT); + Parser parser = new Parser("return (1+arg)+2;"); ReturnNode ret = parser.parse(); - assertEquals("return (Proj_3+3);", ret.print()); + assertEquals("return (arg+3);", ret.print()); } @Test public void testChapter4Add0() { - Parser parser = new Parser("return 0+arg;", TypeInteger.BOT); + Parser parser = new Parser("return 0+arg;"); ReturnNode ret = parser.parse(); - assertEquals("return Proj_3;", ret.print()); + assertEquals("return arg;", ret.print()); } @Test public void testChapter4AddAddMul() { - Parser parser = new Parser("return arg+0+arg;", TypeInteger.BOT); + Parser parser = new Parser("return arg+0+arg;"); ReturnNode ret = parser.parse(); - assertEquals("return (Proj_3*2);", ret.print()); + assertEquals("return (arg*2);", ret.print()); } @Test public void testChapter4Peephole3() { - Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;", TypeInteger.BOT); + Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); ReturnNode ret = parser.parse(); - assertEquals("return ((Proj_3*2)+6);", ret.print()); + assertEquals("return ((arg*2)+6);", ret.print()); } @Test public void testChapter4Mul1() { - Parser parser = new Parser("return 1*arg;", TypeInteger.BOT); + Parser parser = new Parser("return 1*arg;"); ReturnNode ret = parser.parse(); - assertEquals("return Proj_3;", ret.print()); + assertEquals("return arg;", ret.print()); } @Test @@ -72,54 +72,64 @@ public class Chapter04Test { @Test public void testChapter4CompEq() { - Parser parser = new Parser("return 3==3; #showGraph;", TypeInteger.BOT); + Parser parser = new Parser("return 3==3; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testChapter4CompEq2() { - Parser parser = new Parser("return 3==4; #showGraph;", TypeInteger.BOT); + Parser parser = new Parser("return 3==4; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testChapter4CompNEq() { - Parser parser = new Parser("return 3!=3; #showGraph;", TypeInteger.BOT); + Parser parser = new Parser("return 3!=3; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testChapter4CompNEq2() { - Parser parser = new Parser("return 3!=4; #showGraph;", TypeInteger.BOT); + Parser parser = new Parser("return 3!=4; #showGraph;"); ReturnNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testChapter4Bug1() { - Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;", TypeInteger.BOT); + Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); ReturnNode ret = parser.parse(); - assertEquals("return (Proj_3+3);", ret.print()); + assertEquals("return (arg+3);", ret.print()); } @Test public void testChapter4Bug2() { - Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;", TypeInteger.BOT); + Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); ReturnNode ret = parser.parse(); - assertEquals("return (Proj_3+1);", ret.print()); + assertEquals("return (arg+1);", ret.print()); } @Test public void testChapter4Bug3() { - Parser parser = new Parser("int a=arg*2+1; a=a+-1; return a; #showGraph;", TypeInteger.BOT); - ReturnNode ret = parser.parse(); - assertEquals("return (Proj_3*2);", ret.print()); + try { + new Parser("inta=1; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'inta'",e.getMessage()); + } } @Test + public void testChapter4Bug4() { + Parser parser = new Parser("return -arg;"); + ReturnNode ret = parser.parse(); + assertEquals("return (-arg);", ret.print()); + } + + @Test public void testVarDecl() { Parser parser = new Parser("int a=1; return a;"); ReturnNode ret = parser.parse(); @@ -158,12 +168,14 @@ public class Chapter04Test { @Test public void testSelfAssign() { - exceptionRule.expect(RuntimeException.class); - exceptionRule.expectMessage("Undefined name 'a'"); - new Parser("int a=a; return a;").parse(); + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } } - @Test public void testChapter2ParseGrammar() { Node._disablePeephole = true; // disable peephole so we can observe full graph @@ -247,16 +259,22 @@ public class Chapter04Test { @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 @@ -267,9 +285,12 @@ public class Chapter04Test { @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 @@ -280,8 +301,22 @@ public class Chapter04Test { @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()); + } + } + } |
