diff options
| author | Dibyendu Majumdar <mobile@majumdar.org.uk> | 2023-10-20 15:21:08 -0700 |
|---|---|---|
| committer | Dibyendu Majumdar <mobile@majumdar.org.uk> | 2024-10-23 17:51:09 -0700 |
| commit | 83fdf059150e37c335a86e3dd4547a76a1c588db (patch) | |
| tree | 7df24a5366647c8f9cf083ead43ca106f1d23430 /docs/chapter04 | |
| parent | 0e8916e1a4ae550357401b37df6fdca683c221f7 (diff) | |
| download | Simple-83fdf059150e37c335a86e3dd4547a76a1c588db.tar.gz Simple-83fdf059150e37c335a86e3dd4547a76a1c588db.zip | |
Chapter 4: External Argument and Comparisonslinear-chapter04
Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: Hels15 <helsgithub15@gmail.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Diffstat (limited to 'docs/chapter04')
| -rw-r--r-- | docs/chapter04/04-arg1.svg | 84 | ||||
| -rw-r--r-- | docs/chapter04/04-arg2.svg | 80 | ||||
| -rw-r--r-- | docs/chapter04/04-dce1.svg | 100 | ||||
| -rw-r--r-- | docs/chapter04/04-dce2.svg | 59 | ||||
| -rw-r--r-- | docs/chapter04/04-dce3.svg | 116 | ||||
| -rw-r--r-- | docs/chapter04/04-grammar.md | 76 | ||||
| -rw-r--r-- | docs/chapter04/04-post-peephole.gv | 43 | ||||
| -rw-r--r-- | docs/chapter04/04-post-peephole.svg | 108 | ||||
| -rw-r--r-- | docs/chapter04/04-pre-peephole.gv | 47 | ||||
| -rw-r--r-- | docs/chapter04/04-pre-peephole.svg | 134 | ||||
| -rw-r--r-- | docs/chapter04/Makefile | 12 | ||||
| -rw-r--r-- | docs/chapter04/README.md | 397 | ||||
| -rw-r--r-- | docs/chapter04/lattice.gv | 63 | ||||
| -rw-r--r-- | docs/chapter04/lattice.svg | 195 | ||||
| -rw-r--r-- | docs/chapter04/projnode.png | bin | 0 -> 6061 bytes |
15 files changed, 1514 insertions, 0 deletions
diff --git a/docs/chapter04/04-arg1.svg b/docs/chapter04/04-arg1.svg new file mode 100644 index 00000000..cf4599c5 --- /dev/null +++ b/docs/chapter04/04-arg1.svg @@ -0,0 +1,84 @@ +<?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: chapter04 Pages: 1 --> +<svg width="358pt" height="186pt" viewBox="0.00 0.00 358.00 186.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 182)"> +<title>chapter04</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-182 354,-182 354,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-16 8,-170 154,-170 154,-16 8,-16"/> +</g> +<g id="clust2" class="cluster"> +<title>cluster_Scope1_0</title> +<polygon fill="none" stroke="#000000" points="162,-8 162,-76 342,-76 342,-8 162,-8"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_Scope1_1</title> +<polygon fill="none" stroke="#000000" points="264,-16 264,-68 334,-68 334,-16 264,-16"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="25,-132 25,-158 66,-158 66,-132 25,-132"/> +<polygon fill="none" stroke="#000000" points="25,-132 25,-158 66,-158 66,-132 25,-132"/> +<text text-anchor="start" x="32.2805" y="-140.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="25,-100 25,-132 66,-132 66,-100 25,-100"/> +<polygon fill="#ffff00" stroke="transparent" points="30,-105 30,-127 61,-127 61,-105 30,-105"/> +<polygon fill="none" stroke="#000000" points="30,-105 30,-127 61,-127 61,-105 30,-105"/> +<text text-anchor="start" x="32.6718" y="-111.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +</g> +<!-- Con_5 --> +<g id="node2" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="#000000" cx="119" cy="-129" rx="27" ry="18"/> +<text text-anchor="middle" x="119" y="-124.8" font-family="Times,serif" font-size="14.00" fill="#000000">2</text> +</g> +<!-- Return6 --> +<g id="node3" class="node"> +<title>Return6</title> +<polygon fill="#ffff00" stroke="#000000" points="109.1025,-60 54.8975,-60 54.8975,-24 109.1025,-24 109.1025,-60"/> +<text text-anchor="middle" x="82" y="-37.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Return6->Start2 --> +<g id="edge1" class="edge"> +<title>Return6->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M65.0542,-60.052C57.6135,-69.4899 49.9318,-81.7894 47.1181,-94.8747"/> +<polygon fill="#ff0000" stroke="#ff0000" points="43.6189,-94.6762 46,-105 50.5766,-95.4446 43.6189,-94.6762"/> +<text text-anchor="middle" x="62.8306" y="-62.452" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return6->Con_5 --> +<g id="edge2" class="edge"> +<title>Return6->Con_5</title> +<path fill="none" stroke="#000000" d="M89.6664,-60.0265C94.8444,-72.2017 101.7707,-88.4878 107.5926,-102.1772"/> +<polygon fill="#000000" stroke="#000000" points="104.4613,-103.7577 111.5959,-111.5903 110.903,-101.0181 104.4613,-103.7577"/> +<text text-anchor="middle" x="87.4428" y="-62.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Scope1_0 --> +<g id="node4" class="node"> +<title>Scope1_0</title> +<polygon fill="#00ffff" stroke="transparent" points="179,-31 179,-53 192,-53 192,-31 179,-31"/> +<polygon fill="none" stroke="#000000" points="179,-31 179,-53 192,-53 192,-31 179,-31"/> +<text text-anchor="start" x="182" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">0</text> +<polygon fill="none" stroke="#000000" points="192,-31 192,-53 223,-53 223,-31 192,-31"/> +<text text-anchor="start" x="194.6718" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +<polygon fill="none" stroke="#000000" points="223,-31 223,-53 246,-53 246,-31 223,-31"/> +<text text-anchor="start" x="225.5624" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text> +</g> +<!-- Scope1_0->Con_5 --> +<g id="edge3" class="edge"> +<title>Scope1_0:Scope1_0_arg->Con_5</title> +<path fill="none" stroke="#6495ed" stroke-dasharray="5,2" d="M235,-53C235,-91.8959 188.8038,-111.9666 154.717,-121.4819"/> +<polygon fill="#6495ed" stroke="#6495ed" points="153.8305,-118.0959 145.0327,-123.9992 155.5916,-124.8708 153.8305,-118.0959"/> +</g> +<!-- Scope1_1 --> +<g id="node5" class="node"> +<title>Scope1_1</title> +<polygon fill="#00ffff" stroke="transparent" points="293,-31 293,-53 306,-53 306,-31 293,-31"/> +<polygon fill="none" stroke="#000000" points="293,-31 293,-53 306,-53 306,-31 293,-31"/> +<text text-anchor="start" x="296" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +</g> +</svg>
\ No newline at end of file diff --git a/docs/chapter04/04-arg2.svg b/docs/chapter04/04-arg2.svg new file mode 100644 index 00000000..2b3b47a3 --- /dev/null +++ b/docs/chapter04/04-arg2.svg @@ -0,0 +1,80 @@ +<?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: chapter04 Pages: 1 --> +<svg width="308pt" height="186pt" viewBox="0.00 0.00 308.00 186.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 182)"> +<title>chapter04</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-182 304,-182 304,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-16 8,-170 104,-170 104,-16 8,-16"/> +</g> +<g id="clust2" class="cluster"> +<title>cluster_Scope1_0</title> +<polygon fill="none" stroke="#000000" points="112,-8 112,-76 292,-76 292,-8 112,-8"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_Scope1_1</title> +<polygon fill="none" stroke="#000000" points="214,-16 214,-68 284,-68 284,-16 214,-16"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="24,-132 24,-158 88,-158 88,-132 24,-132"/> +<polygon fill="none" stroke="#000000" points="24,-132 24,-158 88,-158 88,-132 24,-132"/> +<text text-anchor="start" x="42.7805" y="-140.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="24,-100 24,-132 88,-132 88,-100 24,-100"/> +<polygon fill="#ffff00" stroke="transparent" points="29,-105 29,-127 60,-127 60,-105 29,-105"/> +<polygon fill="none" stroke="#000000" points="29,-105 29,-127 60,-127 60,-105 29,-105"/> +<text text-anchor="start" x="31.6718" y="-111.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +<polygon fill="none" stroke="#000000" points="60,-105 60,-127 83,-127 83,-105 60,-105"/> +<text text-anchor="start" x="62.5624" y="-111.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text> +</g> +<!-- Return5 --> +<g id="node2" class="node"> +<title>Return5</title> +<polygon fill="#ffff00" stroke="#000000" points="83.1025,-60 28.8975,-60 28.8975,-24 83.1025,-24 83.1025,-60"/> +<text text-anchor="middle" x="56" y="-37.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Return5->Start2 --> +<g id="edge1" class="edge"> +<title>Return5->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M50.7017,-60.0225C48.1903,-69.7926 45.5126,-82.3709 44.4612,-94.733"/> +<polygon fill="#ff0000" stroke="#ff0000" points="40.9524,-94.853 44,-105 47.9454,-95.1672 40.9524,-94.853"/> +<text text-anchor="middle" x="48.4781" y="-62.4225" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return5->Start2 --> +<g id="edge2" class="edge"> +<title>Return5->Start2:p1</title> +<path fill="none" stroke="#000000" d="M63.1576,-60.1614C66.4858,-69.8668 70.0107,-82.3387 71.3935,-94.7027"/> +<polygon fill="#000000" stroke="#000000" points="67.918,-95.2231 72,-105 74.9059,-94.8115 67.918,-95.2231"/> +<text text-anchor="middle" x="60.934" y="-62.5614" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Scope1_0 --> +<g id="node3" class="node"> +<title>Scope1_0</title> +<polygon fill="#00ffff" stroke="transparent" points="129,-31 129,-53 142,-53 142,-31 129,-31"/> +<polygon fill="none" stroke="#000000" points="129,-31 129,-53 142,-53 142,-31 129,-31"/> +<text text-anchor="start" x="132" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">0</text> +<polygon fill="none" stroke="#000000" points="142,-31 142,-53 173,-53 173,-31 142,-31"/> +<text text-anchor="start" x="144.6718" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +<polygon fill="none" stroke="#000000" points="173,-31 173,-53 196,-53 196,-31 173,-31"/> +<text text-anchor="start" x="175.5624" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text> +</g> +<!-- Scope1_0->Start2 --> +<g id="edge3" class="edge"> +<title>Scope1_0:Scope1_0_arg->Start2:p1</title> +<path fill="none" stroke="#6495ed" stroke-dasharray="5,2" d="M185,-53C185,-102.849 142.3608,-114.5665 93.2341,-115.8698"/> +<polygon fill="#6495ed" stroke="#6495ed" points="92.9546,-112.373 83,-116 93.0437,-119.3724 92.9546,-112.373"/> +</g> +<!-- Scope1_1 --> +<g id="node4" class="node"> +<title>Scope1_1</title> +<polygon fill="#00ffff" stroke="transparent" points="243,-31 243,-53 256,-53 256,-31 243,-31"/> +<polygon fill="none" stroke="#000000" points="243,-31 243,-53 256,-53 256,-31 243,-31"/> +<text text-anchor="start" x="246" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +</g> +</svg>
\ No newline at end of file diff --git a/docs/chapter04/04-dce1.svg b/docs/chapter04/04-dce1.svg new file mode 100644 index 00000000..c63a85f7 --- /dev/null +++ b/docs/chapter04/04-dce1.svg @@ -0,0 +1,100 @@ +<?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: chapter04 Pages: 1 --> +<svg width="204pt" height="258pt" viewBox="0.00 0.00 204.00 258.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 254)"> +<title>chapter04</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-254 200,-254 200,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="19,-88 19,-242 187,-242 187,-88 19,-88"/> +</g> +<g id="clust2" class="cluster"> +<title>cluster_Scope1_0</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-76 188,-76 188,-8 8,-8"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_Scope1_1</title> +<polygon fill="none" stroke="#000000" points="110,-16 110,-68 180,-68 180,-16 110,-16"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="35,-204 35,-230 99,-230 99,-204 35,-204"/> +<polygon fill="none" stroke="#000000" points="35,-204 35,-230 99,-230 99,-204 35,-204"/> +<text text-anchor="start" x="53.7805" y="-212.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="35,-172 35,-204 99,-204 99,-172 35,-172"/> +<polygon fill="#ffff00" stroke="transparent" points="40,-177 40,-199 71,-199 71,-177 40,-177"/> +<polygon fill="none" stroke="#000000" points="40,-177 40,-199 71,-199 71,-177 40,-177"/> +<text text-anchor="start" x="42.6718" y="-183.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +<polygon fill="none" stroke="#000000" points="71,-177 71,-199 94,-199 94,-177 71,-177"/> +<text text-anchor="start" x="73.5624" y="-183.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text> +</g> +<!-- Con_5 --> +<g id="node2" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="#000000" cx="152" cy="-114" rx="27" ry="18"/> +<text text-anchor="middle" x="152" y="-109.8" font-family="Times,serif" font-size="14.00" fill="#000000">12</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="#000000" cx="152" cy="-201" rx="27" ry="18"/> +<text text-anchor="middle" x="152" y="-196.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- Return7 --> +<g id="node4" class="node"> +<title>Return7</title> +<polygon fill="#ffff00" stroke="#000000" points="107.1025,-132 52.8975,-132 52.8975,-96 107.1025,-96 107.1025,-132"/> +<text text-anchor="middle" x="80" y="-109.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Return7->Start2 --> +<g id="edge1" class="edge"> +<title>Return7->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M68.6703,-132.0016C63.4509,-141.64 57.957,-154.1206 55.8715,-166.8193"/> +<polygon fill="#ff0000" stroke="#ff0000" points="52.3657,-166.7379 55,-177 59.3402,-167.335 52.3657,-166.7379"/> +<text text-anchor="middle" x="66.4467" y="-134.4016" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return7->Con_6 --> +<g id="edge2" class="edge"> +<title>Return7->Con_6</title> +<path fill="none" stroke="#000000" d="M94.9184,-132.0265C105.7302,-145.0906 120.4588,-162.8877 132.2466,-177.1313"/> +<polygon fill="#000000" stroke="#000000" points="129.7233,-179.572 138.7954,-185.0444 135.1161,-175.109 129.7233,-179.572"/> +<text text-anchor="middle" x="92.6948" y="-134.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Scope1_0 --> +<g id="node5" class="node"> +<title>Scope1_0</title> +<polygon fill="#00ffff" stroke="transparent" points="25,-31 25,-53 38,-53 38,-31 25,-31"/> +<polygon fill="none" stroke="#000000" points="25,-31 25,-53 38,-53 38,-31 25,-31"/> +<text text-anchor="start" x="28" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">0</text> +<polygon fill="none" stroke="#000000" points="38,-31 38,-53 69,-53 69,-31 38,-31"/> +<text text-anchor="start" x="40.6718" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +<polygon fill="none" stroke="#000000" points="69,-31 69,-53 92,-53 92,-31 69,-31"/> +<text text-anchor="start" x="71.5624" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text> +</g> +<!-- Scope1_0->Start2 --> +<g id="edge3" class="edge"> +<title>Scope1_0:Scope1_0_arg->Start2:p1</title> +<path fill="none" stroke="#6495ed" stroke-dasharray="5,2" d="M81,-53C81,-75.6361 52.952,-67.2092 44,-88 36.2663,-105.9613 37.1652,-113.6777 44,-132 51.8047,-152.9223 74.2036,-151.7329 81.0127,-166.7479"/> +<polygon fill="#6495ed" stroke="#6495ed" points="77.6609,-167.8488 83,-177 84.533,-166.5167 77.6609,-167.8488"/> +</g> +<!-- Scope1_1 --> +<g id="node6" class="node"> +<title>Scope1_1</title> +<polygon fill="#00ffff" stroke="transparent" points="133,-31 133,-53 146,-53 146,-31 133,-31"/> +<polygon fill="none" stroke="#000000" points="133,-31 133,-53 146,-53 146,-31 133,-31"/> +<text text-anchor="start" x="136" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +<polygon fill="none" stroke="#000000" points="146,-31 146,-53 158,-53 158,-31 146,-31"/> +<text text-anchor="start" x="148.8927" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">a</text> +</g> +<!-- Scope1_1->Con_5 --> +<g id="edge4" class="edge"> +<title>Scope1_1:Scope1_1_a->Con_5</title> +<path fill="none" stroke="#6495ed" stroke-dasharray="5,2" d="M152,-53C152,-63.6896 152,-75.4328 152,-85.737"/> +<polygon fill="#6495ed" stroke="#6495ed" points="148.5001,-85.8496 152,-95.8497 155.5001,-85.8497 148.5001,-85.8496"/> +</g> +</g> +</svg>
\ No newline at end of file diff --git a/docs/chapter04/04-dce2.svg b/docs/chapter04/04-dce2.svg new file mode 100644 index 00000000..e3719bcc --- /dev/null +++ b/docs/chapter04/04-dce2.svg @@ -0,0 +1,59 @@ +<?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: chapter04 Pages: 1 --> +<svg width="114pt" height="250pt" viewBox="0.00 0.00 114.00 250.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 246)"> +<title>chapter04</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-246 110,-246 110,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-234 98,-234 98,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="33,-196 33,-222 74,-222 74,-196 33,-196"/> +<polygon fill="none" stroke="#000000" points="33,-196 33,-222 74,-222 74,-196 33,-196"/> +<text text-anchor="start" x="40.2805" y="-204.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="33,-164 33,-196 74,-196 74,-164 33,-164"/> +<polygon fill="#ffff00" stroke="transparent" points="38,-169 38,-191 69,-191 69,-169 38,-169"/> +<polygon fill="none" stroke="#000000" points="38,-169 38,-191 69,-191 69,-169 38,-169"/> +<text text-anchor="start" x="40.6718" y="-175.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +</g> +<!-- Con_6 --> +<g id="node2" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="#000000" cx="43" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- Con_6->Start2 --> +<g id="edge1" class="edge"> +<title>Con_6->Start2</title> +<path fill="none" stroke="#ff0000" d="M45.072,-124.0265C45.9366,-131.5481 46.9815,-140.6387 48.0249,-149.7167"/> +<polygon fill="#ff0000" stroke="#ff0000" points="44.5736,-150.3415 49.1927,-159.8764 51.5278,-149.5421 44.5736,-150.3415"/> +<text text-anchor="middle" x="42.8484" y="-126.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return7 --> +<g id="node3" class="node"> +<title>Return7</title> +<polygon fill="#ffff00" stroke="#000000" points="80.1025,-52 25.8975,-52 25.8975,-16 80.1025,-16 80.1025,-52"/> +<text text-anchor="middle" x="53" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Return7->Start2 --> +<g id="edge2" class="edge"> +<title>Return7->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M64.3196,-52.2322C69.9396,-62.3585 76.1294,-75.4211 79,-88 82.5597,-103.599 83.0135,-108.5115 79,-124 74.2474,-142.3411 60.2215,-145.475 55.5405,-159.004"/> +<polygon fill="#ff0000" stroke="#ff0000" points="52.0641,-158.5835 54,-169 58.9824,-159.6498 52.0641,-158.5835"/> +<text text-anchor="middle" x="62.096" y="-54.6322" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return7->Con_6 --> +<g id="edge3" class="edge"> +<title>Return7->Con_6</title> +<path fill="none" stroke="#000000" d="M50.4766,-52.1686C49.4071,-59.869 48.1353,-69.0257 46.9468,-77.5834"/> +<polygon fill="#000000" stroke="#000000" points="43.4664,-77.2003 45.5574,-87.5867 50.3999,-78.1633 43.4664,-77.2003"/> +<text text-anchor="middle" x="48.253" y="-54.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +</g> +</svg>
\ No newline at end of file diff --git a/docs/chapter04/04-dce3.svg b/docs/chapter04/04-dce3.svg new file mode 100644 index 00000000..86fa6f0d --- /dev/null +++ b/docs/chapter04/04-dce3.svg @@ -0,0 +1,116 @@ +<?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: chapter04 Pages: 1 --> +<svg width="458pt" height="178pt" viewBox="0.00 0.00 458.00 178.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 174)"> +<title>chapter04</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-174 454,-174 454,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-162 442,-162 442,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="25,-124 25,-150 66,-150 66,-124 25,-124"/> +<polygon fill="none" stroke="#000000" points="25,-124 25,-150 66,-150 66,-124 25,-124"/> +<text text-anchor="start" x="32.2805" y="-132.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="25,-92 25,-124 66,-124 66,-92 25,-92"/> +<polygon fill="#ffff00" stroke="transparent" points="30,-97 30,-119 61,-119 61,-97 30,-97"/> +<polygon fill="none" stroke="#000000" points="30,-97 30,-119 61,-119 61,-97 30,-97"/> +<text text-anchor="start" x="32.6718" y="-103.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +</g> +<!-- Con_5 --> +<g id="node2" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="#000000" cx="335" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="335" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">2</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="#000000" cx="407" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="407" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- Add7 --> +<g id="node4" class="node"> +<title>Add7</title> +<ellipse fill="none" stroke="#000000" cx="371" cy="-34" rx="27" ry="18"/> +<text text-anchor="middle" x="371" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text> +</g> +<!-- Add7->Con_5 --> +<g id="edge1" class="edge"> +<title>Add7->Con_5</title> +<path fill="none" stroke="#000000" d="M363.7149,-51.6057C358.6889,-63.7518 351.9107,-80.1326 346.2018,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="342.8638,-92.842 342.2743,-103.4204 349.3319,-95.5185 342.8638,-92.842"/> +<text text-anchor="middle" x="361.4913" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Add7->Con_6 --> +<g id="edge2" class="edge"> +<title>Add7->Con_6</title> +<path fill="none" stroke="#000000" d="M378.2851,-51.6057C383.3111,-63.7518 390.0893,-80.1326 395.7982,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="392.6681,-95.5185 399.7257,-103.4204 399.1362,-92.842 392.6681,-95.5185"/> +<text text-anchor="middle" x="376.0615" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Con_8 --> +<g id="node5" class="node"> +<title>Con_8</title> +<ellipse fill="none" stroke="#000000" cx="191" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="191" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">3</text> +</g> +<!-- Con_9 --> +<g id="node6" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="#000000" cx="263" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="263" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">3</text> +</g> +<!-- Add10 --> +<g id="node7" class="node"> +<title>Add10</title> +<ellipse fill="none" stroke="#000000" cx="227" cy="-34" rx="27" ry="18"/> +<text text-anchor="middle" x="227" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text> +</g> +<!-- Add10->Con_8 --> +<g id="edge3" class="edge"> +<title>Add10->Con_8</title> +<path fill="none" stroke="#000000" d="M219.7149,-51.6057C214.6889,-63.7518 207.9107,-80.1326 202.2018,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="198.8638,-92.842 198.2743,-103.4204 205.3319,-95.5185 198.8638,-92.842"/> +<text text-anchor="middle" x="217.4913" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Add10->Con_9 --> +<g id="edge4" class="edge"> +<title>Add10->Con_9</title> +<path fill="none" stroke="#000000" d="M234.2851,-51.6057C239.3111,-63.7518 246.0893,-80.1326 251.7982,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="248.6681,-95.5185 255.7257,-103.4204 255.1362,-92.842 248.6681,-95.5185"/> +<text text-anchor="middle" x="232.0615" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Con_11 --> +<g id="node8" class="node"> +<title>Con_11</title> +<ellipse fill="none" stroke="#000000" cx="119" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="119" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">6</text> +</g> +<!-- Return12 --> +<g id="node9" class="node"> +<title>Return12</title> +<polygon fill="#ffff00" stroke="#000000" points="109.1025,-52 54.8975,-52 54.8975,-16 109.1025,-16 109.1025,-52"/> +<text text-anchor="middle" x="82" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Return12->Start2 --> +<g id="edge5" class="edge"> +<title>Return12->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M65.0542,-52.052C57.6135,-61.4899 49.9318,-73.7894 47.1181,-86.8747"/> +<polygon fill="#ff0000" stroke="#ff0000" points="43.6189,-86.6762 46,-97 50.5766,-87.4446 43.6189,-86.6762"/> +<text text-anchor="middle" x="62.8306" y="-54.452" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return12->Con_11 --> +<g id="edge6" class="edge"> +<title>Return12->Con_11</title> +<path fill="none" stroke="#000000" d="M89.6664,-52.0265C94.8444,-64.2017 101.7707,-80.4878 107.5926,-94.1772"/> +<polygon fill="#000000" stroke="#000000" points="104.4613,-95.7577 111.5959,-103.5903 110.903,-93.0181 104.4613,-95.7577"/> +<text text-anchor="middle" x="87.4428" y="-54.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +</g> +</svg>
\ No newline at end of file diff --git a/docs/chapter04/04-grammar.md b/docs/chapter04/04-grammar.md new file mode 100644 index 00000000..48facd4c --- /dev/null +++ b/docs/chapter04/04-grammar.md @@ -0,0 +1,76 @@ +# Grammar for Chapter 1 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | metaStatement + ; + +metaStatement + : '#showGraph' ';' + ; + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter04/04-post-peephole.gv b/docs/chapter04/04-post-peephole.gv new file mode 100644 index 00000000..0a9f8e93 --- /dev/null +++ b/docs/chapter04/04-post-peephole.gv @@ -0,0 +1,43 @@ +digraph chapter04 { +/* +return 1+arg+2; #showGraph; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ 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_10 [ label="#3" ]; + Add11 [ label="+" ]; + Return12 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$ctrl">$ctrl</TD><TD PORT="Scope1_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD></TR> + </TABLE>>]; + } + } + 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]; + Scope1_0:"Scope1_0_arg" -> Start2:p1; +} diff --git a/docs/chapter04/04-post-peephole.svg b/docs/chapter04/04-post-peephole.svg new file mode 100644 index 00000000..550c16ef --- /dev/null +++ b/docs/chapter04/04-post-peephole.svg @@ -0,0 +1,108 @@ +<?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: chapter04 Pages: 1 --> +<svg width="417pt" height="248pt" + viewBox="0.00 0.00 417.00 248.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 244)"> +<title>chapter04</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-244 413,-244 413,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-232 193,-232 193,-8 8,-8"/> +</g> +<g id="clust2" class="cluster"> +<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_Scope1_1</title> +<polygon fill="none" stroke="black" points="323,-80 323,-132 393,-132 393,-80 323,-80"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<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> +<polygon fill="none" stroke="black" points="97,-164 97,-195 178,-195 178,-164 97,-164"/> +<polygon fill="yellow" stroke="transparent" points="102,-169 102,-190 142,-190 142,-169 102,-169"/> +<polygon fill="none" stroke="black" points="102,-169 102,-190 142,-190 142,-169 102,-169"/> +<text text-anchor="start" x="105" y="-175.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<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_10 --> +<g id="node2" class="node"> +<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> +<!-- Add11 --> +<g id="node3" class="node"> +<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> +<!-- Add11->Start2 --> +<g id="edge1" class="edge"> +<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> +<!-- Add11->Con_10 --> +<g id="edge2" class="edge"> +<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> +<!-- Return12 --> +<g id="node4" class="node"> +<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> +<!-- Return12->Start2 --> +<g id="edge3" class="edge"> +<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> +<!-- Return12->Add11 --> +<g id="edge4" class="edge"> +<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> +<!-- Scope1_0 --> +<g id="node5" class="node"> +<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> +<polygon fill="none" stroke="black" points="234,-95 234,-116 274,-116 274,-95 234,-95"/> +<text text-anchor="start" x="237" y="-101.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<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> +<!-- Scope1_0->Start2 --> +<g id="edge5" class="edge"> +<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_1 --> +<g id="node6" class="node"> +<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> +</g> +</g> +</svg> diff --git a/docs/chapter04/04-pre-peephole.gv b/docs/chapter04/04-pre-peephole.gv new file mode 100644 index 00000000..aefd81c4 --- /dev/null +++ b/docs/chapter04/04-pre-peephole.gv @@ -0,0 +1,47 @@ +digraph chapter04 { +/* +return 1+arg+2; #showGraph; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ 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" ]; + Con_6 [ label="#2" ]; + Add7 [ label="+" ]; + Add8 [ label="+" ]; + Return9 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$ctrl">$ctrl</TD><TD PORT="Scope1_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD></TR> + </TABLE>>]; + } + } + 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]; + Scope1_0:"Scope1_0_arg" -> Start2:p1; +} diff --git a/docs/chapter04/04-pre-peephole.svg b/docs/chapter04/04-pre-peephole.svg new file mode 100644 index 00000000..9ec38d27 --- /dev/null +++ b/docs/chapter04/04-pre-peephole.svg @@ -0,0 +1,134 @@ +<?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: chapter04 Pages: 1 --> +<svg width="417pt" height="320pt" + viewBox="0.00 0.00 417.00 320.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 316)"> +<title>chapter04</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-316 413,-316 413,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-304 193,-304 193,-8 8,-8"/> +</g> +<g id="clust2" class="cluster"> +<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_Scope1_1</title> +<polygon fill="none" stroke="black" points="323,-152 323,-204 393,-204 393,-152 323,-152"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<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> +<polygon fill="none" stroke="black" points="97,-236 97,-267 178,-267 178,-236 97,-236"/> +<polygon fill="yellow" stroke="transparent" points="102,-241 102,-262 142,-262 142,-241 102,-241"/> +<polygon fill="none" stroke="black" points="102,-241 102,-262 142,-262 142,-241 102,-241"/> +<text text-anchor="start" x="105" y="-247.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<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_5 --> +<g id="node2" class="node"> +<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_6 --> +<g id="node3" class="node"> +<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> +<!-- Add7 --> +<g id="node4" class="node"> +<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> +<!-- Add7->Start2 --> +<g id="edge1" class="edge"> +<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> +<!-- Add7->Con_6 --> +<g id="edge2" class="edge"> +<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> +<!-- Add8 --> +<g id="node5" class="node"> +<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> +<!-- Add8->Con_5 --> +<g id="edge3" class="edge"> +<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> +<!-- Add8->Add7 --> +<g id="edge4" class="edge"> +<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> +<!-- Return9 --> +<g id="node6" class="node"> +<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> +<!-- Return9->Start2 --> +<g id="edge5" class="edge"> +<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> +<!-- Return9->Add8 --> +<g id="edge6" class="edge"> +<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> +<!-- Scope1_0 --> +<g id="node7" class="node"> +<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> +<polygon fill="none" stroke="black" points="234,-167 234,-188 274,-188 274,-167 234,-167"/> +<text text-anchor="start" x="237" y="-173.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<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> +<!-- Scope1_0->Start2 --> +<g id="edge7" class="edge"> +<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_1 --> +<g id="node8" class="node"> +<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> +</g> +</g> +</svg> diff --git a/docs/chapter04/Makefile b/docs/chapter04/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter04/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter04/README.md b/docs/chapter04/README.md new file mode 100644 index 00000000..bfb52487 --- /dev/null +++ b/docs/chapter04/README.md @@ -0,0 +1,397 @@ +# Chapter 4: External Argument and Comparisons + +In this chapter we extend the language grammar with following features: + +* The program receives a single argument named `arg` of integer type from external environment. +* Expressions support comparison operators. +* We introduce a scope sensitive name binding `$ctrl` for the current incoming + control node. Thus, our Return is no longer hard-wired to Start, instead it + tracks the in scope `$ctrl` binding. + +Here is the [complete language grammar](04-grammar.md) for this chapter. + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter04) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter03...linear-chapter04) it to the previous chapter. + +## Extensions to Intermediate Representation + +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 | | A tuple with a ctrl token and an `arg` data node | +| Proj | Data | 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 | +| Not | Data | Logical not | One data node | Result converts 0 to 1 and vice versa | + +Below is our list of Nodes from [Chapter 3](../chapter03/README.md): + +| Node Name | Type | Description | Inputs | Value | +|-----------|--------------|------------------------------------|------------------------------------------------------------------|------------------------------| +| Return | Control | End of function | Predecessor control node, Data node value | Return value of the function | +| Constant | Data | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | +| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | +| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | +| Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | +| Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | +| Minus | Data | Negate a value | One data node, value is negated | Result of the unary minus | +| Scope | Symbol Table | Represents scopes in the graph | All nodes that define variables | None | + +## Projection Nodes + +We add projection nodes that are used to extract a specific tuple member from a multi-valued node. +Each projection node contains an index of the field to extract from its input node. +Projection nodes allow us to maintain labeled use-def edges as simple Node references. + +In the visuals, projection nodes are shown as rectangular boxes inside the node to which they are attached. + +### Visualisation + + + +In the visual above, the projection nodes have been tagged by the names +associated with the outputs of the Start node. Both MultiNode that contain +Control and Control nodes are yellow. `$ctrl` and `arg` are outputs(users) of +StartNode(`START`) and have their MultiNode as their only input in slot 0. The +`label` has no semantics and is used during debug printing. + +```java +public ProjNode(MultiNode ctrl, int idx, String label) { + super(ctrl); +``` + +```java +_scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole()); +_scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); +``` + +These projection nodes are going to extract the types for `CTRL` and `ARG0` from the `START` MultiNode. +The MultiNode holds the types as a TypeTuple: + +```java +public StartNode(Type[] args) { + super(); + _args = new TypeTuple(args); +``` + +Extracting the types is based on the `_idx`: +```java +return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; +``` + +### Initial values + +An argument is always provided, and defaults to `TypeInteger.BOT`. Individual +tests can (and do) pass in other integer values by calling `new Parser` with +an argument: + +```java +Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); +``` + +The graph: + + + +- `$ctrl` and `arg` are both defined in the outermost symbol table, at lexical depth 0. +- There is an empty global-scope symbol table created at depth 1; in the future + global variables will be defined here. +- There is no line for the scope `$ctrl` because control is dead after the + return. It is manually set to null, which calls `setDef` to kill the node + (and killed nodes are not part of the program and not visualized). + +``` + ctrl(null); // Kill control +``` + +- The `arg` projection node is not included in the cluster because arg is a + constant. The `arg` was originally defined by a ProjNode; but when peephole + is called the computed type is a constant, and the ProjNode gets replaced + with a ConstantNode: + +```java +public final Node peephole( ) { + Type type = _type = compute(); + /* type = {TypeInteger@1527} "2" */ + + if (_disablePeephole) + return this; + + // ProjNode is not a constant unlike its type. + if (!(this instanceof ConstantNode) && type.isConstant()) + /* Create Constant(2) */ + return deadCodeElim(new ConstantNode(type).peephole()); + + /* won't get called */ + ... +``` + +If you don't pass an argument you get `TypeInteger.BOT` + +```java + Parser parser = new Parser("return arg; #showGraph;"); + ... + +public Parser(String source) { + this(source, TypeInteger.BOT); +} + +``` + +We clearly see this is not a constant: + +```java +public final static TypeInteger BOT = new TypeInteger(false, 1); + /* _is_con = false */ +``` + +So the `arg` projection node remains in the cluster: + + + + +#### When Is Control Not-Null? + +In later chapters, `$ctrl` will point to other control nodes, such as +`If` and `Region` (and `Loop`), but for now with no other control flow it always gets set to null after a `Return`. + +#### 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. + + + +## Changes to Type System + +In [Chapter 2](../chapter02/README.md) we introduced the Type System. + +We have annotated Nodes with Types and the Type annotation serves two purposes: + +* It defines the set of operations allowed on the Node, and +* it defines the set of values the Node takes on. + +We mentioned in [Chapter 2](../chapter02/README.md) that the set of values +associated with a Type at a specific Node can be conveniently represented as a +[lattice](https://en.wikipedia.org/wiki/Lattice_(order)). + +The type itself is identified by the Java class `Type` and subtypes. The type +implementation uses Java classes as convenient to deal with a Types' internal +structure - but the Java classes have no relation to a Type's place in the +lattice. + +In this chapter we extend the Type hierarchy as follows: + +``` +Type ++-- TypeControl (New - represents control token) ++-- TypeInteger (Enhanced - now has Top and Bottom types) ++-- TypeBot ++-- TypeTuple (New - represents multi-valued result) +``` + +Our enhanced Lattice looks like this: + + + + +In this chapter we introduce the possibility of a program input variable named +`arg`; all we know about this variable is that it is some integer value, but we do not know whether it is a constant or not. + +To support the requirements for non-constant integer values, we enhance `TypeInteger` to +allow it to represent `IntTop` and `IntBot` integer types in addition to the earlier constant value. + +Now that integer values may be constants or non-constants, we need to introduce the "meet" operator +in our lattice. The `meet` operator describes rules that define the resulting type when we combine +integer values. + +| | IntBot | Con1 | Con2 | IntTop | +|--------|--------|--------|--------|--------| +| IntBot | IntBot | IntBot | IntBot | IntBot | +| Con1 | IntBot | Con1 | IntBot | Con1 | +| IntTop | IntBot | Con1 | Con2 | IntTop | + +In the table above `Con1` and `Con2` represent two distinct integer values, and serve to explain the rules below. + +* The `meet` of `IntTop` with any integer constant is that constant. +* The `meet` of `IntBot` with any integer value is `IntBot`. +* The `meet` of any integer with itself is that integer. +* The `meet` of two unrelated integer constants is `IntBot`. + +Currently, all our integer valued nodes are either a constant or a `IntBot` integer type. +When we start optimizing loops, we will start seeing `IntTop` values. + + +## `$ctrl` name binding + +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 +look up this name in the current scope. + +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. + + +## More Peephole Optimizations + +Now that we have non-constant integer values, we can do additional +optimizations, rearranging algebraic expressions to enable constant +folding. For example: + +``` +return 1 + arg + 2; +``` + +We would expect the compiler to output `arg+3` here, but as it stands what we get is: + + + +We need to perform some algebraic simplifications to enable better outcome. For +example, we need to rearrange the expression as follows: + +``` +arg + (1 + 2) +``` + +This then enables constant folding and the final outcome is shown below. By +canonicalizing expressions we fold common addressing math constants, remove +algebraic identities and generally simplify the code. + + + +Here is a list of peepholes introduced in this Chapter, more will be introduced in later chapters: + +| Before | After | Description | +|-----------------------|-----------------------|------------------------------------------------| +| (arg + 0 ) | arg | Add of zero identity | +| (arg * 1 ) | arg | Multiple of one identity | +| (con + arg) | (arg + con) | Move constants to right, to encourage folding | +| (con * arg) | (arg * con) | Move constants to right, to encourage folding | +| (con1 + (arg + con2)) | (arg + (con1 + con2)) | Move constants to right, to encourage folding | +| ((arg1 + con) + arg2) | ((arg1 + arg2) + con) | Move constants to right, to encourage folding | +| (arg + arg) | (arg * 2) | Sum-of-products form | +| (arg - arg) | 0 | Sub of same is 0 +| (con / 1) | con | Division by one +| (arg == arg) | 1 | Compare of same +| (arg != arg) | 0 | Compare of same +| (arg < arg) | 0 | Compare of same +| (arg > arg) | 0 | Compare of same +| (arg <= arg) | 1 | Compare of same +| (arg >= arg) | 1 | Compare of same + + +## Peephole Walkthrough + +The peephole optimizations introduced in this chapter are local. They are triggered during parsing +as new nodes are created, before the newly created node has any uses. + +For example, when we parse a unary expression, and create a Node for the parsed expression, +`peephole()` is invoked on the newly created `MinusNode`: + +```java +private Node parseUnary() { + if (match("-")) return new MinusNode(parseUnary()).peephole(); + return parsePrimary(); +} +``` + +As another example, here is the parsing of comparison operators, also introduced in this chapter: + +```java +private Node parseComparison() { + var lhs = parseAddition(); + if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); + if (match("!=")) return new BoolNode.NENode(lhs, parseComparison()).peephole(); + if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole(); + if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole(); + if (match(">=")) return new BoolNode.GENode(lhs, parseComparison()).peephole(); + if (match(">" )) return new BoolNode.GTNode(lhs, parseComparison()).peephole(); + return lhs; +} +``` + +The implementation of `peephole()` is in the main `Node` class, and is thus shared +by all subclasses of `Node`. + +```java +public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); + + // Replace constant computations from non-constants with a constant node + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + return this; // No progress +} +``` + +The peephole method does following: + +- Compute a Type for the node. +- If the Type is a Constant and the node is not a ConstantNode, replace with a + ConstantNode, recursively invoking peephole on the new constant. +- Otherwise, ask the Node for a better replacement via a call to `idealize()`. + The "better replacement" is things like `(1+2)` becomes `3` and `1+(x+2))` + becomes `(x+(1+2))`. +- - Each Node subtype is responsible for deciding what the `idealize()` step + should do. If there is a better replacement then the node returns a non + `null` value. +- - If we see a non `null` value, something changed, so we invoke `peephole()` + again and then also run dead code elimination on the (now dead and replaced) + `this` node. + +`peephole()` calls `deadCodeElim()` which is shown below. + + +## Dead Code Elimination(DCE) + +We call `kill` every time a Node makes the 1-user-to-0-users transition during +graph editing. This commonly happens when replacing via peeps and exiting +scopes. This recursive `kill` amounts to Dead Code Elimination in many other +compilers; here we call it in a very fine-grained way. Many Nodes will be +created by the parser, only to be killed before the very next lexeme is parsed. + +For more information please read the [appendix section](appendix/dce.md#appendix) on dead code elimination. + +The suggestively called `deadCodeElim` function is a thin wrapper over `kill` +used by `peepholeOpt` to avoid prematurely killing a Node which only briefly +makes the 1->0 users transition. + +```java +// m is the new Node, self is the old. +// Return 'm', which may have zero uses but is alive nonetheless. +// If self has zero uses (and is not 'm'), {@link #kill} self. +private Node deadCodeElim(Node m) { + // If self is going dead and not being returned here (Nodes returned + // from peephole commonly have no uses (yet)), then kill self. + if( m != this && isUnused() ) { + // Killing self - and since self recursively kills self's inputs we + // might end up killing 'm', which we are returning as a live Node. + // So we add a bogus extra null output edge to stop kill(). + m.addUse(null); // Add bogus null use to keep m alive + kill(); // Kill self because replacing with 'm' + m.delUse(null); // Remove bogus null. + } + return m; +} +``` + +Note the temporary add of a bogus user to the Node `m`. The reason this is +done is that we know `m` is the new replacement and is alive, but since it is +not yet hooked into the graph, it has no users yet. By adding a bogus user we +prevent it being mistaken for dead and being killed. + +[^1]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 131. diff --git a/docs/chapter04/lattice.gv b/docs/chapter04/lattice.gv new file mode 100644 index 00000000..1f286530 --- /dev/null +++ b/docs/chapter04/lattice.gv @@ -0,0 +1,63 @@ +digraph Lattice { + // Define nodes + splines=false; + node [shape=circle, style=filled, fillcolor=lightblue]; + nodesep=0.6; + + TOP [label="⊤"]; + BOT [label="⊥"]; + + CTRL [label="Ctrl"]; + + INT_TOP [label="IntTop"]; + INT_BOT [label="IntBot"]; + + INT_MIN [label="-n"]; + INT_MINDOTS [label="..." shape=none style=none]; + INT_MINUS [label="-1"]; + INT_ZERO [label="0"]; + INT_PLUS [label="1"]; + INT_MAXDOTS [label="..." shape=none style=none]; + INT_MAX [label="+n"]; + + TUPLE [label="TUPLE"]; + + // Define edges + edge [arrowhead=none]; + + TOP -> INT_TOP; + INT_TOP -> INT_MIN; + INT_TOP -> INT_MINDOTS; + INT_TOP -> INT_MINUS; + INT_TOP -> INT_ZERO; + INT_TOP -> INT_PLUS; + INT_TOP -> INT_MAXDOTS; + INT_TOP -> INT_MAX; + INT_MIN -> INT_BOT; + INT_MINDOTS -> INT_BOT; + INT_MINUS -> INT_BOT; + INT_ZERO -> INT_BOT; + INT_PLUS -> INT_BOT; + INT_MAXDOTS -> INT_BOT; + INT_MAX -> INT_BOT; + INT_BOT -> BOT; + + INT_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + TOP -> TUPLE; + TUPLE -> BOT; + + TOP -> CTRL; + CTRL -> BOT; + + + // Additional customization + {rank=same; TOP} + {rank=same; INT_TOP} + {rank=same; CTRL; INT_MIN; INT_MINDOTS; + INT_MINUS; INT_ZERO; + INT_PLUS; INT_MAXDOTS; + INT_MAX; TUPLE} + {rank=same; INT_BOT} + {rank=same; BOT;} +} diff --git a/docs/chapter04/lattice.svg b/docs/chapter04/lattice.svg new file mode 100644 index 00000000..0d403c20 --- /dev/null +++ b/docs/chapter04/lattice.svg @@ -0,0 +1,195 @@ +<?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: Lattice Pages: 1 --> +<svg width="802pt" height="478pt" + viewBox="0.00 0.00 802.14 478.27" 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 474.27)"> +<title>Lattice</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-474.27 798.14,-474.27 798.14,4 -4,4"/> +<!-- TOP --> +<g id="node1" class="node"> +<title>TOP</title> +<ellipse fill="lightblue" stroke="black" cx="377.6" cy="-450.77" rx="19.5" ry="19.5"/> +<text text-anchor="middle" x="377.6" y="-447.07" font-family="Times,serif" font-size="14.00">⊤</text> +</g> +<!-- CTRL --> +<g id="node3" class="node"> +<title>CTRL</title> +<ellipse fill="lightblue" stroke="black" cx="28.6" cy="-235.14" rx="28.7" ry="28.7"/> +<text text-anchor="middle" x="28.6" y="-231.44" font-family="Times,serif" font-size="14.00">Ctrl</text> +</g> +<!-- TOP->CTRL --> +<g id="edge25" class="edge"> +<title>TOP->CTRL</title> +<path fill="none" stroke="black" d="M360.76,-440.37C304.12,-405.37 120.24,-291.76 53.28,-250.38"/> +</g> +<!-- INT_TOP --> +<g id="node4" class="node"> +<title>INT_TOP</title> +<ellipse fill="lightblue" stroke="black" cx="377.6" cy="-354.98" rx="40.09" ry="40.09"/> +<text text-anchor="middle" x="377.6" y="-351.28" font-family="Times,serif" font-size="14.00">IntTop</text> +</g> +<!-- TOP->INT_TOP --> +<g id="edge1" class="edge"> +<title>TOP->INT_TOP</title> +<path fill="none" stroke="black" d="M377.6,-431.24C377.6,-420.99 377.6,-407.84 377.6,-395.42"/> +</g> +<!-- TUPLE --> +<g id="node13" class="node"> +<title>TUPLE</title> +<ellipse fill="lightblue" stroke="black" cx="750.6" cy="-235.14" rx="43.59" ry="43.59"/> +<text text-anchor="middle" x="750.6" y="-231.44" font-family="Times,serif" font-size="14.00">TUPLE</text> +</g> +<!-- TOP->TUPLE --> +<g id="edge23" class="edge"> +<title>TOP->TUPLE</title> +<path fill="none" stroke="black" d="M394.59,-440.95C451.03,-408.32 633.13,-303.05 712.75,-257.02"/> +</g> +<!-- BOT --> +<g id="node2" class="node"> +<title>BOT</title> +<ellipse fill="lightblue" stroke="black" cx="377.6" cy="-19.5" rx="19.5" ry="19.5"/> +<text text-anchor="middle" x="377.6" y="-15.8" font-family="Times,serif" font-size="14.00">⊥</text> +</g> +<!-- CTRL->BOT --> +<g id="edge26" class="edge"> +<title>CTRL->BOT</title> +<path fill="none" stroke="black" d="M53.14,-219.97C120.01,-178.65 304.22,-64.84 360.83,-29.86"/> +</g> +<!-- INT_MIN --> +<g id="node6" class="node"> +<title>INT_MIN</title> +<ellipse fill="lightblue" stroke="black" cx="119.6" cy="-235.14" rx="19.5" ry="19.5"/> +<text text-anchor="middle" x="119.6" y="-231.44" font-family="Times,serif" font-size="14.00">-n</text> +</g> +<!-- INT_TOP->INT_MIN --> +<g id="edge2" class="edge"> +<title>INT_TOP->INT_MIN</title> +<path fill="none" stroke="black" d="M341.18,-337.34C284.92,-311.65 179.02,-263.28 137.21,-244.18"/> +</g> +<!-- INT_MINDOTS --> +<g id="node7" class="node"> +<title>INT_MINDOTS</title> +<text text-anchor="middle" x="208.6" y="-231.44" font-family="Times,serif" font-size="14.00">...</text> +</g> +<!-- INT_TOP->INT_MINDOTS --> +<g id="edge3" class="edge"> +<title>INT_TOP->INT_MINDOTS</title> +<path fill="none" stroke="black" d="M345.01,-331.26C312.3,-308.45 262.65,-273.83 233.14,-253.25"/> +</g> +<!-- INT_MINUS --> +<g id="node8" class="node"> +<title>INT_MINUS</title> +<ellipse fill="lightblue" stroke="black" cx="297.6" cy="-235.14" rx="19.5" ry="19.5"/> +<text text-anchor="middle" x="297.6" y="-231.44" font-family="Times,serif" font-size="14.00">-1</text> +</g> +<!-- INT_TOP->INT_MINUS --> +<g id="edge4" class="edge"> +<title>INT_TOP->INT_MINUS</title> +<path fill="none" stroke="black" d="M355.31,-321.15C339.96,-298.54 320.25,-269.51 308.29,-251.89"/> +</g> +<!-- INT_ZERO --> +<g id="node9" class="node"> +<title>INT_ZERO</title> +<ellipse fill="lightblue" stroke="black" cx="377.6" cy="-235.14" rx="18" ry="18"/> +<text text-anchor="middle" x="377.6" y="-231.44" font-family="Times,serif" font-size="14.00">0</text> +</g> +<!-- INT_TOP->INT_ZERO --> +<g id="edge5" class="edge"> +<title>INT_TOP->INT_ZERO</title> +<path fill="none" stroke="black" d="M377.6,-314.41C377.6,-293.68 377.6,-269.36 377.6,-253.39"/> +</g> +<!-- INT_PLUS --> +<g id="node10" class="node"> +<title>INT_PLUS</title> +<ellipse fill="lightblue" stroke="black" cx="456.6" cy="-235.14" rx="18" ry="18"/> +<text text-anchor="middle" x="456.6" y="-231.44" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- INT_TOP->INT_PLUS --> +<g id="edge6" class="edge"> +<title>INT_TOP->INT_PLUS</title> +<path fill="none" stroke="black" d="M399.6,-321.15C415.13,-298 435.17,-268.1 446.88,-250.63"/> +</g> +<!-- INT_MAXDOTS --> +<g id="node11" class="node"> +<title>INT_MAXDOTS</title> +<text text-anchor="middle" x="544.6" y="-231.44" font-family="Times,serif" font-size="14.00">...</text> +</g> +<!-- INT_TOP->INT_MAXDOTS --> +<g id="edge7" class="edge"> +<title>INT_TOP->INT_MAXDOTS</title> +<path fill="none" stroke="black" d="M410.19,-330.98C442.56,-308.14 491.43,-273.65 520.47,-253.16"/> +</g> +<!-- INT_MAX --> +<g id="node12" class="node"> +<title>INT_MAX</title> +<ellipse fill="lightblue" stroke="black" cx="639.6" cy="-235.14" rx="24.9" ry="24.9"/> +<text text-anchor="middle" x="639.6" y="-231.44" font-family="Times,serif" font-size="14.00">+n</text> +</g> +<!-- INT_TOP->INT_MAX --> +<g id="edge8" class="edge"> +<title>INT_TOP->INT_MAX</title> +<path fill="none" stroke="black" d="M414.03,-337.59C469.15,-312.8 572.09,-266.5 617.32,-246.16"/> +</g> +<!-- INT_BOT --> +<g id="node5" class="node"> +<title>INT_BOT</title> +<ellipse fill="lightblue" stroke="black" cx="377.6" cy="-115.29" rx="40.09" ry="40.09"/> +<text text-anchor="middle" x="377.6" y="-111.59" font-family="Times,serif" font-size="14.00">IntBot</text> +</g> +<!-- INT_BOT->BOT --> +<g id="edge16" class="edge"> +<title>INT_BOT->BOT</title> +<path fill="none" stroke="black" d="M377.6,-74.79C377.6,-62.37 377.6,-49.25 377.6,-39.01"/> +</g> +<!-- INT_MIN->INT_BOT --> +<g id="edge9" class="edge"> +<title>INT_MIN->INT_BOT</title> +<path fill="none" stroke="black" d="M137.33,-226.04C179.23,-206.9 285.02,-158.58 341.21,-132.91"/> +</g> +<!-- INT_MIN->INT_MINDOTS --> +<!-- INT_MINDOTS->INT_BOT --> +<g id="edge10" class="edge"> +<title>INT_MINDOTS->INT_BOT</title> +<path fill="none" stroke="black" d="M233.17,-217C262.65,-196.45 312.17,-161.91 344.87,-139.11"/> +</g> +<!-- INT_MINDOTS->INT_MINUS --> +<!-- INT_MINUS->INT_BOT --> +<g id="edge11" class="edge"> +<title>INT_MINUS->INT_BOT</title> +<path fill="none" stroke="black" d="M308.39,-218.24C320.33,-200.65 339.91,-171.81 355.2,-149.29"/> +</g> +<!-- INT_MINUS->INT_ZERO --> +<!-- INT_ZERO->INT_BOT --> +<g id="edge12" class="edge"> +<title>INT_ZERO->INT_BOT</title> +<path fill="none" stroke="black" d="M377.6,-217C377.6,-201.04 377.6,-176.66 377.6,-155.88"/> +</g> +<!-- INT_ZERO->INT_PLUS --> +<!-- INT_PLUS->INT_BOT --> +<g id="edge13" class="edge"> +<title>INT_PLUS->INT_BOT</title> +<path fill="none" stroke="black" d="M446.91,-219.69C435.21,-202.23 415.16,-172.33 399.63,-149.16"/> +</g> +<!-- INT_PLUS->INT_MAXDOTS --> +<!-- INT_MAXDOTS->INT_BOT --> +<g id="edge14" class="edge"> +<title>INT_MAXDOTS->INT_BOT</title> +<path fill="none" stroke="black" d="M520.31,-217C491.28,-196.51 442.55,-162.13 410.24,-139.33"/> +</g> +<!-- INT_MAXDOTS->INT_MAX --> +<!-- INT_MAX->INT_BOT --> +<g id="edge15" class="edge"> +<title>INT_MAX->INT_BOT</title> +<path fill="none" stroke="black" d="M617.26,-224.09C572.09,-203.77 469.52,-157.64 414.35,-132.82"/> +</g> +<!-- TUPLE->BOT --> +<g id="edge24" class="edge"> +<title>TUPLE->BOT</title> +<path fill="none" stroke="black" d="M712.78,-213.27C633.14,-167.23 450.85,-61.85 394.51,-29.27"/> +</g> +</g> +</svg> diff --git a/docs/chapter04/projnode.png b/docs/chapter04/projnode.png Binary files differnew file mode 100644 index 00000000..bf7493f2 --- /dev/null +++ b/docs/chapter04/projnode.png |
