diff options
| author | Dibyendu Majumdar <mobile@majumdar.org.uk> | 2023-09-26 17:43:36 +0100 |
|---|---|---|
| committer | Dibyendu Majumdar <mobile@majumdar.org.uk> | 2025-06-13 15:42:08 -0700 |
| commit | 0c1949a40dae7770045d64cb97036e6072b99dfd (patch) | |
| tree | 19e04b16eef9798045d17389ce4e280f7483d0bc /docs | |
| parent | 8e8dcf86abfdd8d90b11ede7db2e94666f4b7356 (diff) | |
| download | Simple-0c1949a40dae7770045d64cb97036e6072b99dfd.tar.gz Simple-0c1949a40dae7770045d64cb97036e6072b99dfd.zip | |
Chapter 2: Arithmetic
Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/chapter02/02-demonstration-peephole.svg | 54 | ||||
| -rw-r--r-- | docs/chapter02/02-demonstration-pre-peephole-nokill.svg | 100 | ||||
| -rw-r--r-- | docs/chapter02/02-demonstration-pre-peephole.svg | 87 | ||||
| -rw-r--r-- | docs/chapter02/02-grammar.md | 40 | ||||
| -rw-r--r-- | docs/chapter02/02-post-peephole-ex1.gv | 17 | ||||
| -rw-r--r-- | docs/chapter02/02-post-peephole-ex1.svg | 56 | ||||
| -rw-r--r-- | docs/chapter02/02-pre-peephole-ex1.gv | 34 | ||||
| -rw-r--r-- | docs/chapter02/02-pre-peephole-ex1.svg | 168 | ||||
| -rw-r--r-- | docs/chapter02/Makefile | 12 | ||||
| -rw-r--r-- | docs/chapter02/README.md | 282 | ||||
| -rw-r--r-- | docs/chapter02/lattice.gv | 40 | ||||
| -rw-r--r-- | docs/chapter02/lattice.svg | 159 |
12 files changed, 1049 insertions, 0 deletions
diff --git a/docs/chapter02/02-demonstration-peephole.svg b/docs/chapter02/02-demonstration-peephole.svg new file mode 100644 index 00000000..90ab6ca4 --- /dev/null +++ b/docs/chapter02/02-demonstration-peephole.svg @@ -0,0 +1,54 @@ +<?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: chapter02 Pages: 1 --> +<svg width="114pt" height="220pt" viewBox="0.00 0.00 114.00 220.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 216)"> +<title>chapter02</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-216 110,-216 110,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-204 98,-204 98,-8 8,-8"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="#ffff00" stroke="#000000" points="80,-196 26,-196 26,-160 80,-160 80,-196"/> +<text text-anchor="middle" x="53" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +</g> +<!-- Con_5 --> +<g id="node2" class="node"> +<title>Con_5</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">#3</text> +</g> +<!-- Con_5->Start1 --> +<g id="edge1" class="edge"> +<title>Con_5->Start1</title> +<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M45.5234,-124.1686C46.5929,-131.869 47.8647,-141.0257 49.0532,-149.5834"/> +<polygon fill="#000000" stroke="#000000" points="45.6001,-150.1633 50.4426,-159.5867 52.5336,-149.2003 45.6001,-150.1633"/> +<text text-anchor="middle" x="43.2998" y="-126.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return6 --> +<g id="node3" class="node"> +<title>Return6</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> +<!-- Return6->Start1 --> +<g id="edge2" class="edge"> +<title>Return6->Start1</title> +<path fill="none" stroke="#ff0000" d="M64.3196,-52.2322C69.9396,-62.3585 76.1294,-75.4211 79,-88 82.5597,-103.599 82.5597,-108.401 79,-124 76.9144,-133.1394 73.0765,-142.534 68.9781,-150.8724"/> +<polygon fill="#ff0000" stroke="#ff0000" points="65.8583,-149.2853 64.3196,-159.7678 72.0595,-152.5328 65.8583,-149.2853"/> +<text text-anchor="middle" x="62.096" y="-54.6322" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return6->Con_5 --> +<g id="edge3" class="edge"> +<title>Return6->Con_5</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/chapter02/02-demonstration-pre-peephole-nokill.svg b/docs/chapter02/02-demonstration-pre-peephole-nokill.svg new file mode 100644 index 00000000..3d4f53df --- /dev/null +++ b/docs/chapter02/02-demonstration-pre-peephole-nokill.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: chapter02 Pages: 1 --> +<svg width="258pt" height="220pt" viewBox="0.00 0.00 258.00 220.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 216)"> +<title>chapter02</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-216 254,-216 254,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-204 242,-204 242,-8 8,-8"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="#ffff00" stroke="#000000" points="165,-196 111,-196 111,-160 165,-160 165,-196"/> +<text text-anchor="middle" x="138" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +</g> +<!-- Con_2 --> +<g id="node2" class="node"> +<title>Con_2</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_2->Start1 --> +<g id="edge1" class="edge"> +<title>Con_2->Start1</title> +<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M60.8688,-119.5426C73.5668,-129.1664 90.9688,-142.3553 106.03,-153.7701"/> +<polygon fill="#000000" stroke="#000000" points="104.028,-156.6444 114.1118,-159.8953 108.2562,-151.0656 104.028,-156.6444"/> +<text text-anchor="middle" x="58.6452" y="-121.9426" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Con_3 --> +<g id="node3" class="node"> +<title>Con_3</title> +<ellipse fill="none" stroke="#000000" cx="115" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">#2</text> +</g> +<!-- Con_3->Start1 --> +<g id="edge2" class="edge"> +<title>Con_3->Start1</title> +<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M120.6854,-123.7978C123.237,-131.7854 126.3069,-141.3955 129.1486,-150.2913"/> +<polygon fill="#000000" stroke="#000000" points="125.8432,-151.4462 132.2203,-159.9069 132.5113,-149.316 125.8432,-151.4462"/> +<text text-anchor="middle" x="118.4618" y="-126.1978" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Add4 --> +<g id="node4" class="node"> +<title>Add4</title> +<ellipse fill="none" stroke="#000000" cx="89" cy="-34" rx="27" ry="18"/> +<text text-anchor="middle" x="89" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text> +</g> +<!-- Add4->Con_2 --> +<g id="edge3" class="edge"> +<title>Add4->Con_2</title> +<path fill="none" stroke="#000000" d="M78.3311,-50.6992C72.6414,-59.6048 65.5223,-70.7476 59.1684,-80.693"/> +<polygon fill="#000000" stroke="#000000" points="56.0456,-79.08 53.6111,-89.3913 61.9445,-82.8487 56.0456,-79.08"/> +<text text-anchor="middle" x="80.5547" y="-53.0992" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Add4->Con_3 --> +<g id="edge4" class="edge"> +<title>Add4->Con_3</title> +<path fill="none" stroke="#000000" d="M95.427,-51.7978C98.3866,-59.9936 101.963,-69.8976 105.2447,-78.9855"/> +<polygon fill="#000000" stroke="#000000" points="101.9585,-80.1902 108.647,-88.407 108.5424,-77.8126 101.9585,-80.1902"/> +<text text-anchor="middle" x="93.2034" y="-54.1978" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Con_5 --> +<g id="node5" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="#000000" cx="207" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">#3</text> +</g> +<!-- Con_5->Start1 --> +<g id="edge5" class="edge"> +<title>Con_5->Start1</title> +<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M192.3669,-121.2693C183.6447,-130.3708 172.3525,-142.1539 162.3214,-152.6212"/> +<polygon fill="#000000" stroke="#000000" points="159.6869,-150.3117 155.2947,-159.9533 164.7408,-155.1551 159.6869,-150.3117"/> +<text text-anchor="middle" x="194.5905" y="-123.6693" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return6 --> +<g id="node6" class="node"> +<title>Return6</title> +<polygon fill="#ffff00" stroke="#000000" points="211.1025,-52 156.8975,-52 156.8975,-16 211.1025,-16 211.1025,-52"/> +<text text-anchor="middle" x="184" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Return6->Start1 --> +<g id="edge6" class="edge"> +<title>Return6->Start1</title> +<path fill="none" stroke="#ff0000" d="M178.1741,-52.2377C170.2935,-76.9072 156.1635,-121.1402 146.9358,-150.0269"/> +<polygon fill="#ff0000" stroke="#ff0000" points="143.4876,-149.3195 143.7786,-159.9104 150.1557,-151.4497 143.4876,-149.3195"/> +<text text-anchor="middle" x="175.9505" y="-54.6377" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return6->Con_5 --> +<g id="edge7" class="edge"> +<title>Return6->Con_5</title> +<path fill="none" stroke="#000000" d="M189.8039,-52.1686C192.3565,-60.1594 195.41,-69.7181 198.2308,-78.5486"/> +<polygon fill="#000000" stroke="#000000" points="194.9006,-79.6259 201.2777,-88.0866 201.5687,-77.4957 194.9006,-79.6259"/> +<text text-anchor="middle" x="187.5803" 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/chapter02/02-demonstration-pre-peephole.svg b/docs/chapter02/02-demonstration-pre-peephole.svg new file mode 100644 index 00000000..49624652 --- /dev/null +++ b/docs/chapter02/02-demonstration-pre-peephole.svg @@ -0,0 +1,87 @@ +<?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: chapter02 Pages: 1 --> +<svg width="186pt" height="292pt" viewBox="0.00 0.00 186.00 292.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 288)"> +<title>chapter02</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-288 182,-288 182,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-276 170,-276 170,-8 8,-8"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="#ffff00" stroke="#000000" points="90,-268 36,-268 36,-232 90,-232 90,-268"/> +<text text-anchor="middle" x="63" y="-245.8" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +</g> +<!-- Con_2 --> +<g id="node2" class="node"> +<title>Con_2</title> +<ellipse fill="none" stroke="#000000" cx="63" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">#1</text> +</g> +<!-- Con_2->Start1 --> +<g id="edge1" class="edge"> +<title>Con_2->Start1</title> +<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M63,-196.1686C63,-203.869 63,-213.0257 63,-221.5834"/> +<polygon fill="#000000" stroke="#000000" points="59.5001,-221.5867 63,-231.5867 66.5001,-221.5868 59.5001,-221.5867"/> +<text text-anchor="middle" x="60.7764" y="-198.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Con_3 --> +<g id="node3" class="node"> +<title>Con_3</title> +<ellipse fill="none" stroke="#000000" cx="135" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">#2</text> +</g> +<!-- Con_3->Start1 --> +<g id="edge2" class="edge"> +<title>Con_3->Start1</title> +<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M119.7307,-193.2693C110.6292,-202.3708 98.8461,-214.1539 88.3788,-224.6212"/> +<polygon fill="#000000" stroke="#000000" points="85.6429,-222.4073 81.0467,-231.9533 90.5927,-227.3571 85.6429,-222.4073"/> +<text text-anchor="middle" x="117.5071" y="-195.6693" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Add4 --> +<g id="node4" class="node"> +<title>Add4</title> +<ellipse fill="none" stroke="#000000" cx="63" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text> +</g> +<!-- Add4->Con_2 --> +<g id="edge3" class="edge"> +<title>Add4->Con_2</title> +<path fill="none" stroke="#000000" d="M63,-124.1686C63,-131.869 63,-141.0257 63,-149.5834"/> +<polygon fill="#000000" stroke="#000000" points="59.5001,-149.5867 63,-159.5867 66.5001,-149.5868 59.5001,-149.5867"/> +<text text-anchor="middle" x="60.7764" y="-126.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Add4->Con_3 --> +<g id="edge4" class="edge"> +<title>Add4->Con_3</title> +<path fill="none" stroke="#000000" d="M78.2693,-121.2693C88.197,-131.197 101.3153,-144.3153 112.4363,-155.4363"/> +<polygon fill="#000000" stroke="#000000" points="110.2067,-158.1564 119.7527,-162.7527 115.1564,-153.2067 110.2067,-158.1564"/> +<text text-anchor="middle" x="80.4929" y="-123.6693" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Return5 --> +<g id="node5" class="node"> +<title>Return5</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> +<!-- Return5->Start1 --> +<g id="edge5" class="edge"> +<title>Return5->Start1</title> +<path fill="none" stroke="#ff0000" d="M41.6804,-52.2322C36.0604,-62.3585 29.8706,-75.4211 27,-88 16.3208,-134.7969 13.0904,-150.0596 27,-196 29.9564,-205.7645 35.3252,-215.3771 41.03,-223.7238"/> +<polygon fill="#ff0000" stroke="#ff0000" points="38.2871,-225.9027 47.0095,-231.9169 43.9414,-221.7761 38.2871,-225.9027"/> +<text text-anchor="middle" x="39.4568" y="-54.6322" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return5->Add4 --> +<g id="edge6" class="edge"> +<title>Return5->Add4</title> +<path fill="none" stroke="#000000" d="M55.5234,-52.1686C56.5929,-59.869 57.8647,-69.0257 59.0532,-77.5834"/> +<polygon fill="#000000" stroke="#000000" points="55.6001,-78.1633 60.4426,-87.5867 62.5336,-77.2003 55.6001,-78.1633"/> +<text text-anchor="middle" x="53.2998" 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/chapter02/02-grammar.md b/docs/chapter02/02-grammar.md new file mode 100644 index 00000000..ce875eda --- /dev/null +++ b/docs/chapter02/02-grammar.md @@ -0,0 +1,40 @@ +# Grammar for Chapter 1 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement EOF + ; + +statement + : 'return' expression ';' + ; + +expression + : additiveExpression + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : INTEGER_LITERAL + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; +``` diff --git a/docs/chapter02/02-post-peephole-ex1.gv b/docs/chapter02/02-post-peephole-ex1.gv new file mode 100644 index 00000000..6c2b23ae --- /dev/null +++ b/docs/chapter02/02-post-peephole-ex1.gv @@ -0,0 +1,17 @@ +digraph chapter02 { +/* +return 1+2*3+-5; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_13 [ label="#2" ]; + Return14 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_13 -> Start1[taillabel=0 style=dotted]; + Return14 -> Start1[taillabel=0 color=red]; + Return14 -> Con_13[taillabel=1]; +} diff --git a/docs/chapter02/02-post-peephole-ex1.svg b/docs/chapter02/02-post-peephole-ex1.svg new file mode 100644 index 00000000..db27e30d --- /dev/null +++ b/docs/chapter02/02-post-peephole-ex1.svg @@ -0,0 +1,56 @@ +<?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: chapter02 Pages: 1 --> +<svg width="114pt" height="220pt" + viewBox="0.00 0.00 114.00 220.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 216)"> +<title>chapter02</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-216 110,-216 110,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-204 98,-204 98,-8 8,-8"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="yellow" stroke="black" points="80,-196 26,-196 26,-160 80,-160 80,-196"/> +<text text-anchor="middle" x="53" y="-174.3" font-family="Times,serif" font-size="14.00">Start</text> +</g> +<!-- Con_13 --> +<g id="node2" class="node"> +<title>Con_13</title> +<ellipse fill="none" stroke="black" cx="43" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-102.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Con_13->Start1 --> +<g id="edge1" class="edge"> +<title>Con_13->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M45.42,-123.95C46.52,-131.65 47.85,-140.97 49.09,-149.64"/> +<polygon fill="black" stroke="black" points="45.65,-150.32 50.53,-159.72 52.58,-149.33 45.65,-150.32"/> +<text text-anchor="middle" x="42.42" y="-126.55" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return14 --> +<g id="node3" class="node"> +<title>Return14</title> +<polygon fill="yellow" stroke="black" points="86,-52 20,-52 20,-16 86,-16 86,-52"/> +<text text-anchor="middle" x="53" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Return14->Start1 --> +<g id="edge2" class="edge"> +<title>Return14->Start1</title> +<path fill="none" stroke="red" d="M64.05,-52.39C69.74,-62.38 76.08,-75.42 79,-88 82.62,-103.59 82.62,-108.41 79,-124 76.9,-133.04 73.03,-142.32 68.91,-150.53"/> +<polygon fill="red" stroke="red" points="65.69,-149.14 64.05,-159.61 71.86,-152.45 65.69,-149.14"/> +<text text-anchor="middle" x="61.05" y="-54.99" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return14->Con_13 --> +<g id="edge3" class="edge"> +<title>Return14->Con_13</title> +<path fill="none" stroke="black" d="M50.53,-52.3C49.43,-60.02 48.1,-69.29 46.87,-77.89"/> +<polygon fill="black" stroke="black" points="43.39,-77.5 45.44,-87.9 50.32,-78.49 43.39,-77.5"/> +<text text-anchor="middle" x="47.53" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter02/02-pre-peephole-ex1.gv b/docs/chapter02/02-pre-peephole-ex1.gv new file mode 100644 index 00000000..411de5ee --- /dev/null +++ b/docs/chapter02/02-pre-peephole-ex1.gv @@ -0,0 +1,34 @@ +digraph chapter02 { +/* +return 1+2*3+-5; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_2 [ label="#1" ]; + Con_3 [ label="#2" ]; + Con_4 [ label="#3" ]; + Mul5 [ label="*" ]; + Con_6 [ label="#5" ]; + Minus7 [ label="-" ]; + Add8 [ label="+" ]; + Add9 [ label="+" ]; + Return10 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_2 -> Start1[taillabel=0 style=dotted]; + Con_3 -> Start1[taillabel=0 style=dotted]; + Con_4 -> Start1[taillabel=0 style=dotted]; + Mul5 -> Con_3[taillabel=1]; + Mul5 -> Con_4[taillabel=2]; + Con_6 -> Start1[taillabel=0 style=dotted]; + Minus7 -> Con_6[taillabel=1]; + Add8 -> Mul5[taillabel=1]; + Add8 -> Minus7[taillabel=2]; + Add9 -> Con_2[taillabel=1]; + Add9 -> Add8[taillabel=2]; + Return10 -> Start1[taillabel=0 color=red]; + Return10 -> Add9[taillabel=1]; +} diff --git a/docs/chapter02/02-pre-peephole-ex1.svg b/docs/chapter02/02-pre-peephole-ex1.svg new file mode 100644 index 00000000..29c76bd8 --- /dev/null +++ b/docs/chapter02/02-pre-peephole-ex1.svg @@ -0,0 +1,168 @@ +<?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: chapter02 Pages: 1 --> +<svg width="278pt" height="436pt" + viewBox="0.00 0.00 278.00 436.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 432)"> +<title>chapter02</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-432 274,-432 274,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-420 262,-420 262,-8 8,-8"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="yellow" stroke="black" points="162,-412 108,-412 108,-376 162,-376 162,-412"/> +<text text-anchor="middle" x="135" y="-390.3" font-family="Times,serif" font-size="14.00">Start</text> +</g> +<!-- Con_2 --> +<g id="node2" class="node"> +<title>Con_2</title> +<ellipse fill="none" stroke="black" cx="222" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="222" y="-174.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- Con_2->Start1 --> +<g id="edge1" class="edge"> +<title>Con_2->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M230.65,-195.54C245.5,-226.47 271.62,-294.07 243,-340 227.56,-364.77 196.8,-378.29 172.04,-385.46"/> +<polygon fill="black" stroke="black" points="170.97,-382.13 162.2,-388.08 172.77,-388.89 170.97,-382.13"/> +<text text-anchor="middle" x="227.65" y="-198.14" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_3 --> +<g id="node3" class="node"> +<title>Con_3</title> +<ellipse fill="none" stroke="black" cx="63" cy="-322" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-318.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Con_3->Start1 --> +<g id="edge2" class="edge"> +<title>Con_3->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M77.57,-337.17C86.92,-346.25 99.3,-358.29 110.17,-368.86"/> +<polygon fill="black" stroke="black" points="107.79,-371.43 117.4,-375.89 112.67,-366.41 107.79,-371.43"/> +<text text-anchor="middle" x="74.57" y="-339.77" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_4 --> +<g id="node4" class="node"> +<title>Con_4</title> +<ellipse fill="none" stroke="black" cx="135" cy="-322" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-318.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Con_4->Start1 --> +<g id="edge3" class="edge"> +<title>Con_4->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M135,-340.3C135,-348.02 135,-357.29 135,-365.89"/> +<polygon fill="black" stroke="black" points="131.5,-365.9 135,-375.9 138.5,-365.9 131.5,-365.9"/> +<text text-anchor="middle" x="132" y="-342.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Mul5 --> +<g id="node5" class="node"> +<title>Mul5</title> +<ellipse fill="none" stroke="black" cx="135" cy="-250" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-246.3" font-family="Times,serif" font-size="14.00">*</text> +</g> +<!-- Mul5->Con_3 --> +<g id="edge4" class="edge"> +<title>Mul5->Con_3</title> +<path fill="none" stroke="black" d="M120.43,-265.17C110.25,-275.06 96.48,-288.45 84.97,-299.64"/> +<polygon fill="black" stroke="black" points="82.53,-297.13 77.8,-306.62 87.41,-302.15 82.53,-297.13"/> +<text text-anchor="middle" x="117.43" y="-267.77" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Mul5->Con_4 --> +<g id="edge5" class="edge"> +<title>Mul5->Con_4</title> +<path fill="none" stroke="black" d="M135,-268.3C135,-276.02 135,-285.29 135,-293.89"/> +<polygon fill="black" stroke="black" points="131.5,-293.9 135,-303.9 138.5,-293.9 131.5,-293.9"/> +<text text-anchor="middle" x="132" y="-270.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_6 --> +<g id="node6" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="black" cx="207" cy="-322" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-318.3" font-family="Times,serif" font-size="14.00">#5</text> +</g> +<!-- Con_6->Start1 --> +<g id="edge6" class="edge"> +<title>Con_6->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M192.43,-337.17C183.08,-346.25 170.7,-358.29 159.83,-368.86"/> +<polygon fill="black" stroke="black" points="157.33,-366.41 152.6,-375.89 162.21,-371.43 157.33,-366.41"/> +<text text-anchor="middle" x="189.43" y="-339.77" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Minus7 --> +<g id="node7" class="node"> +<title>Minus7</title> +<ellipse fill="none" stroke="black" cx="207" cy="-250" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-246.3" font-family="Times,serif" font-size="14.00">-</text> +</g> +<!-- Minus7->Con_6 --> +<g id="edge7" class="edge"> +<title>Minus7->Con_6</title> +<path fill="none" stroke="black" d="M207,-268.3C207,-276.02 207,-285.29 207,-293.89"/> +<polygon fill="black" stroke="black" points="203.5,-293.9 207,-303.9 210.5,-293.9 203.5,-293.9"/> +<text text-anchor="middle" x="204" y="-270.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add8 --> +<g id="node8" class="node"> +<title>Add8</title> +<ellipse fill="none" stroke="black" cx="140" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="140" y="-174.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Add8->Mul5 --> +<g id="edge8" class="edge"> +<title>Add8->Mul5</title> +<path fill="none" stroke="black" d="M138.76,-196.3C138.21,-204.02 137.55,-213.29 136.94,-221.89"/> +<polygon fill="black" stroke="black" points="133.44,-221.67 136.22,-231.9 140.43,-222.17 133.44,-221.67"/> +<text text-anchor="middle" x="135.76" y="-198.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add8->Minus7 --> +<g id="edge9" class="edge"> +<title>Add8->Minus7</title> +<path fill="none" stroke="black" d="M153.88,-193.5C163.14,-203.17 175.47,-216.06 185.93,-226.98"/> +<polygon fill="black" stroke="black" points="183.69,-229.71 193.14,-234.51 188.75,-224.87 183.69,-229.71"/> +<text text-anchor="middle" x="150.88" y="-196.1" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Add9 --> +<g id="node9" class="node"> +<title>Add9</title> +<ellipse fill="none" stroke="black" cx="140" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="140" y="-102.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Add9->Con_2 --> +<g id="edge10" class="edge"> +<title>Add9->Con_2</title> +<path fill="none" stroke="black" d="M156.2,-120.83C168.18,-131.06 184.69,-145.15 198.18,-156.66"/> +<polygon fill="black" stroke="black" points="196.23,-159.61 206.11,-163.44 200.78,-154.28 196.23,-159.61"/> +<text text-anchor="middle" x="153.2" y="-123.43" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add9->Add8 --> +<g id="edge11" class="edge"> +<title>Add9->Add8</title> +<path fill="none" stroke="black" d="M140,-124.3C140,-132.02 140,-141.29 140,-149.89"/> +<polygon fill="black" stroke="black" points="136.5,-149.9 140,-159.9 143.5,-149.9 136.5,-149.9"/> +<text text-anchor="middle" x="137" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Return10 --> +<g id="node10" class="node"> +<title>Return10</title> +<polygon fill="yellow" stroke="black" points="125,-52 59,-52 59,-16 125,-16 125,-52"/> +<text text-anchor="middle" x="92" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Return10->Start1 --> +<g id="edge12" class="edge"> +<title>Return10->Start1</title> +<path fill="none" stroke="red" d="M75.73,-52.27C53.67,-77.55 17,-127.09 17,-177 17,-177 17,-177 17,-251 17,-290.8 4.09,-307.45 27,-340 43.69,-363.72 74.05,-377.3 98.34,-384.76"/> +<polygon fill="red" stroke="red" points="97.41,-388.14 107.99,-387.51 99.33,-381.4 97.41,-388.14"/> +<text text-anchor="middle" x="72.73" y="-54.87" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return10->Add9 --> +<g id="edge13" class="edge"> +<title>Return10->Add9</title> +<path fill="none" stroke="black" d="M103.87,-52.3C109.82,-60.98 117.12,-71.63 123.6,-81.08"/> +<polygon fill="black" stroke="black" points="120.71,-83.06 129.25,-89.33 126.49,-79.1 120.71,-83.06"/> +<text text-anchor="middle" x="100.87" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter02/Makefile b/docs/chapter02/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter02/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/chapter02/README.md b/docs/chapter02/README.md new file mode 100644 index 00000000..0e3f2a8d --- /dev/null +++ b/docs/chapter02/README.md @@ -0,0 +1,282 @@ +# Chapter 2: Arithmetic + + +# Table of Contents + +1. [Extensions to Intermediate Representation](#extensions-to-intermediate-representation) +2. [Peephole Optimizations](#peephole-optimizations) +3. [Constant Folding and Constant Propagation](#constant-folding-and-constant-propagation) +4. [Nodes Pre Peephole Optimization](#nodes-pre-peephole-optimization) +5. [Post-peephole](#post-peephole) +6. [Demonstration](#demonstration) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter02) 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-chapter01...linear-chapter02) it to the previous chapter. + + +In this chapter we extend the language grammar to include arithmetic operations such as addition, subtraction, +multiplication, division, and unary minus. This allows us to write statements such as: + +``` +return 1 + 2 * 3 + -5; +``` + +Here is the [complete language grammar](02-grammar.md) for this chapter. + +## Extensions to Intermediate Representation + +In [Chapter 1](../chapter01/README.md) we introduced following nodes. + +| Node Name | Type | Description | Inputs | Value | +|-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| +| Start | Control | Start of function | None | None for now as we do not have function arguments yet | +| 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 | + +We extend the set of nodes by adding following additional node types. + +| Node Name | Type | Description | Inputs | Value | +|-----------|------|-------------------------------|------------------------------------------------------------|-----------------------------| +| 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 | + + +## *Value* equality vs *Reference* equality + +In much of Simple, Nodes are looked up (`find()` calls) via *reference* +equality. This is by far the most common case. In [Chapter +9](../chapter09/README.md) we introduce *value* equality for the first time. +In both cases the choice of value-vs-reference equality is intentional: it is +*never* correct to "just pick one or the other kind of equality". When in +doubt check the context: only *Global Value Numbering* uses value equality; +everywhere we mean reference equality. + + +## Peephole Optimizations + +Nodes in the graph can be peephole-optimized. The graph is viewed through a +"peephole", a small chunk of graph, and if a certain pattern is detected we +locally rewrite the graph. + +During parsing, these peephole optimizations are particularly easy to check and +apply: there are no uses (yet) of a just-created Node from a just-parsed piece +of syntax, so there's no effort to the "rewrite" part of the problem. We just +replace in-place before installing Nodes into the graph. + +This replacement might allow us to *kill* the unused inputs from the replaced +Node, basically doing a modest Dead Code Elimination during parsing. + +E.g. Suppose we already parsed out a constant `1`, and a constant `2`; then when we +parse an `Add(1,2)`, the peephole rule for constant math replaces the Add with a +constant `3`. At this point, we also *kill* the unused `Add`, which recursively +may *kill* the unused constants `1` and `2`. + + + +## Constant Folding and Constant Propagation + +In this chapter and next we focus on a particular peephole optimization: +constant folding and constant propagation. Since we do not have non-constant values +until [Chapter 4](../chapter04/README.md), the main feature we demonstrate now is constant folding. +However, we introduce some additional ideas into the compiler at this stage, to +set the scene for Chapter 4. + +It is useful for the compiler to know at various points of the program whether +a node's value is a constant. The compiler can use this knowledge to perform various +optimizations such as: + +* Evaluate expressions at compile time and replace an expression with a + constant. This idea can be extended in a number of ways and is called + [Partial Evaluation](https://en.wikipedia.org/wiki/Partial_evaluation). +* The compiler may be able to identify regions of code that are dead and no + longer needed, such as when a conditional branch always take one of the + branches ([Chapter 6](../chapter06/README.md)). +* Pointers may be known to be not-null, and a null check can be skipped ([Chapter 10](../chapter10/README.md)). +* Array indices may be known to be in-range, and a range check can be skipped. +* Many additional optimizations are possible when the compiler learns more + about the possible set of Node values. + +In order to achieve above, we need a way to talk about what kinds of values a Node can take +on at runtime - we call these Types, and we annotate Nodes with Types. + +The Type annotation serves two purposes: + +* it defines the set of operations allowed on the Node +* it defines the set of values the Node takes on + +The Type itself is represented as a Java class; the Java classes are used as +convenient to represent the Type's structure; all types are subtypes of the +class `Type`. For now, we only have the following hierarchy of types: + +``` +Type ++-- TypeInteger +``` + +It turns out that the set of values associated with a Type at a specific Node +can be conveniently represented as a *lattice* +[wiki/Lattice_(order)](https://en.wikipedia.org/wiki/Lattice_(order)). Our lattice has the following structure: + + + +Our lattice elements can be one of three types: + +* The highest element is "top", denoted by ⊤; assigning ⊤ means that the Node's + value may or may not be a compile time constant. +* All elements in the middle are constants. +* The lowest is "bottom", denoted by ⊥; assigning ⊥ means that we know that the + Node's value is **not** a compile time constant. + +An invariant of peephole optimizations is that the type of a Node always moves +*up* the lattice (towards "top"); peepholes are *pessmistic* assuming the worst +until they can prove better. A later *optimistic* optimization will start all +Nodes at *top* and move Types *down* the lattice as eager assumptions are +proven wrong. + +In later chapters we will explore extending this lattice, as it frequently +forms the heart of core optimizations we want our compiler to do. + +We add a `_type` field to every Node, to store its current computed best +`Type`. We need a field to keep the optimizer runtime linear, and later when +doing an optimistic version of constant propagation (called [Sparse Conditional +Constant Propagation](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation)). + +We add a `_type` field even to `Start` and `Return`, and later to all control +Nodes - because the Sea of Nodes does not distinguish between control and data. +Both nodes are equally peepholed and optimized, and this will be covered +starting in [Chapter 4](../chapter04/README.md) and [Chapter +5](../chapter05/README.md). + + +There are other important properties of the Lattice that we discuss in [Chapter +4](../chapter04/README.md) and [Chapter 10](../chapter10/README.md), such as the "meet" and "join" operators and their rules. + + +## Nodes Pre Peephole Optimization + +The following visual shows how the graph looks like pre-peephole optimization: + + + +* Control nodes appear as square boxes with yellow background +* Control edges are in bold red +* The edges from Constants to Start are shown in dotted lines as these are not true control edges +* We label each edge with its position in the node's list of inputs. + + +## Post-peephole + + + + +## Demonstration +To demonstrate how the optimisation works, let's consider the following code: +``` +return 1+2; +``` +This is parsed as: +```java + var lhs = parseMultiplication(); + if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); +``` +When the peephole is called on the AddNode node it first calls the compute function: +```java + public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); +``` +```java + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1 ) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()+i1.value()); + } + return Type.BOTTOM; + } +``` +In our case both of the operands(`1`, `2`) are constants, and instance of +`TypeInteger`. +Since `compute` returns a type, and we know that both of our operands are constants, we can do +constant propagation/folding where we compute the result of the expression so that instead of having `1+2` we can +have `3`. + +The 'TypeInteger' interface inherits from type but also has a field that stores the value observed for that type. +```java + private final long _con +``` + +AddNode has the layout: + + + +Since, we already know the value of both of the operands, we can just add them together and replace the +old node with a constant node that just holds the result of the expression. + +To do this - we have to recognize this happens when the type computed for the node is already a constant, but the node +is still not an instance of constant node. + +This can be captured by: +```java +// Replace constant computations from non-constants with a constant node +if (!(this instanceof ConstantNode) && type.isConstant()) { +} +``` +Note how we return a constant type when doing constant folding +```java +return TypeInteger.constant(i0.value()+i1.value()); +``` +We can create a constant node in the following way: +```java +return new ConstantNode(type).peephole(); +``` +This recursively calls the peephole algorithm. +Now, we end up with this: + + + +Notice, how we added the constant node holding a constant value of `3`. +The remaining add node is unused and can be killed. + +We can call the kill function before this way: +```java +// Replace constant computations from non-constants with a constant node +if (!(this instanceof ConstantNode) && type.isConstant()) { + kill(); // Kill `this` because replacing with a Constant + return new ConstantNode(type).peephole(); +``` +This is responsible for deleting the dangling add node. + +```java +public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + for( int i=0; i<nIns(); i++ ) + setDef(i,null); // Set all inputs to null, recursively killing unused Nodes + + _inputs.clear(); + _type=null; // Flag as dead + assert isDead(); // Really dead now +} +``` + +`isUnused` - This makes sure the current node has no outputs. +Ideally, in our case there would be one output as the return statement is +using the add expression. +However, the optimisation happens before even creating the return node, which means that at this point +there are no users of the add node. + +We can now freely go ahead and delete the node. + +```java +for(int i=0; i<nIns(); i++ ) + setDef(i,null); // Set all inputs to null, recursively killing unused Nodes + +_inputs.clear(); +_type=null; +``` + +We finally end up with this: + + diff --git a/docs/chapter02/lattice.gv b/docs/chapter02/lattice.gv new file mode 100644 index 00000000..fe8df136 --- /dev/null +++ b/docs/chapter02/lattice.gv @@ -0,0 +1,40 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=circle, style=filled]; + nodesep=0.6; + + // ---------------------- + // Integers + INT_TOP [label=<<B>⊤</B >:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<<B>⊥</B>:int>, fillcolor=lightblue, shape=oval]; + + INT_MIN [label="-n" , fillcolor=lightblue]; + INT_MINDOTS [label="...", fillcolor=lightblue shape=oval]; + INT_MINUS [label="-1" , fillcolor=lightblue]; + INT_ZERO [label="0" , fillcolor=lightblue]; + INT_PLUS [label="1" , fillcolor=lightblue]; + INT_MAXDOTS [label="...", fillcolor=lightblue, shape=oval]; + INT_MAX [label="+n" , fillcolor=lightblue]; + + 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_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + // Additional customization + {rank=same; INT_MIN; INT_MINDOTS; INT_MINUS; INT_ZERO; INT_PLUS; INT_MAXDOTS; INT_MAX; } +} diff --git a/docs/chapter02/lattice.svg b/docs/chapter02/lattice.svg new file mode 100644 index 00000000..b11d57aa --- /dev/null +++ b/docs/chapter02/lattice.svg @@ -0,0 +1,159 @@ +<?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 12.2.0 (20241103.1931)
+ -->
+<!-- Title: Lattice Pages: 1 -->
+<svg width="564pt" height="194pt"
+ viewBox="0.00 0.00 563.75 194.31" 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 190.31)">
+<title>Lattice</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-190.31 559.75,-190.31 559.75,4 -4,4"/>
+<!-- INT_TOP -->
+<g id="node1" class="node">
+<title>INT_TOP</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-168.31" rx="33.95" ry="18"/>
+<text text-anchor="start" x="259.72" y="-164.26" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="275.47" y="-164.26" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- INT_MIN -->
+<g id="node3" class="node">
+<title>INT_MIN</title>
+<ellipse fill="lightblue" stroke="black" cx="18.6" cy="-93.15" rx="18.6" ry="18.6"/>
+<text text-anchor="middle" x="18.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">-n</text>
+</g>
+<!-- INT_TOP->INT_MIN -->
+<g id="edge1" class="edge">
+<title>INT_TOP->INT_MIN</title>
+<path fill="none" stroke="black" d="M247,-158.92C197.13,-144.78 96.96,-116.37 47.53,-102.36"/>
+<polygon fill="black" stroke="black" points="48.71,-99.06 38.13,-99.69 46.8,-105.79 48.71,-99.06"/>
+</g>
+<!-- INT_MINDOTS -->
+<g id="node4" class="node">
+<title>INT_MINDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="107.6" cy="-93.15" rx="27" ry="18"/>
+<text text-anchor="middle" x="107.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP->INT_MINDOTS -->
+<g id="edge2" class="edge">
+<title>INT_TOP->INT_MINDOTS</title>
+<path fill="none" stroke="black" d="M250.93,-156.2C221.31,-143.38 172.55,-122.27 140.26,-108.29"/>
+<polygon fill="black" stroke="black" points="141.94,-105.21 131.38,-104.45 139.16,-111.63 141.94,-105.21"/>
+</g>
+<!-- INT_MINUS -->
+<g id="node5" class="node">
+<title>INT_MINUS</title>
+<ellipse fill="lightblue" stroke="black" cx="196.6" cy="-93.15" rx="18.6" ry="18.6"/>
+<text text-anchor="middle" x="196.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">-1</text>
+</g>
+<!-- INT_TOP->INT_MINUS -->
+<g id="edge3" class="edge">
+<title>INT_TOP->INT_MINUS</title>
+<path fill="none" stroke="black" d="M260.02,-152.15C247.97,-141.13 231.55,-126.11 218.43,-114.12"/>
+<polygon fill="black" stroke="black" points="220.83,-111.57 211.09,-107.41 216.11,-116.74 220.83,-111.57"/>
+</g>
+<!-- INT_ZERO -->
+<g id="node6" class="node">
+<title>INT_ZERO</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-93.15" rx="18" ry="18"/>
+<text text-anchor="middle" x="276.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">0</text>
+</g>
+<!-- INT_TOP->INT_ZERO -->
+<g id="edge4" class="edge">
+<title>INT_TOP->INT_ZERO</title>
+<path fill="none" stroke="black" d="M276.6,-149.97C276.6,-141.92 276.6,-132.14 276.6,-123.02"/>
+<polygon fill="black" stroke="black" points="280.1,-123.13 276.6,-113.13 273.1,-123.13 280.1,-123.13"/>
+</g>
+<!-- INT_PLUS -->
+<g id="node7" class="node">
+<title>INT_PLUS</title>
+<ellipse fill="lightblue" stroke="black" cx="355.6" cy="-93.15" rx="18" ry="18"/>
+<text text-anchor="middle" x="355.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">1</text>
+</g>
+<!-- INT_TOP->INT_PLUS -->
+<g id="edge5" class="edge">
+<title>INT_TOP->INT_PLUS</title>
+<path fill="none" stroke="black" d="M292.96,-152.15C305.01,-141 321.48,-125.74 334.51,-113.68"/>
+<polygon fill="black" stroke="black" points="336.82,-116.31 341.78,-106.95 332.06,-111.18 336.82,-116.31"/>
+</g>
+<!-- INT_MAXDOTS -->
+<g id="node8" class="node">
+<title>INT_MAXDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="443.6" cy="-93.15" rx="27" ry="18"/>
+<text text-anchor="middle" x="443.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP->INT_MAXDOTS -->
+<g id="edge6" class="edge">
+<title>INT_TOP->INT_MAXDOTS</title>
+<path fill="none" stroke="black" d="M302.32,-156.04C331.46,-143.28 379,-122.45 410.79,-108.53"/>
+<polygon fill="black" stroke="black" points="412.17,-111.74 419.93,-104.52 409.36,-105.33 412.17,-111.74"/>
+</g>
+<!-- INT_MAX -->
+<g id="node9" class="node">
+<title>INT_MAX</title>
+<ellipse fill="lightblue" stroke="black" cx="534.6" cy="-93.15" rx="21.15" ry="21.15"/>
+<text text-anchor="middle" x="534.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">+n</text>
+</g>
+<!-- INT_TOP->INT_MAX -->
+<g id="edge7" class="edge">
+<title>INT_TOP->INT_MAX</title>
+<path fill="none" stroke="black" d="M306.19,-158.92C355.31,-144.99 453.21,-117.23 503.38,-103.01"/>
+<polygon fill="black" stroke="black" points="504.07,-106.45 512.73,-100.35 502.16,-99.71 504.07,-106.45"/>
+</g>
+<!-- INT_BOT -->
+<g id="node2" class="node">
+<title>INT_BOT</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-18" rx="33.95" ry="18"/>
+<text text-anchor="start" x="259.72" y="-13.95" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="275.47" y="-13.95" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- INT_MIN->INT_BOT -->
+<g id="edge8" class="edge">
+<title>INT_MIN->INT_BOT</title>
+<path fill="none" stroke="black" d="M36.33,-87.13C77.31,-75.51 179.45,-46.55 236.48,-30.38"/>
+<polygon fill="black" stroke="black" points="237.13,-33.83 245.79,-27.73 235.22,-27.09 237.13,-33.83"/>
+</g>
+<!-- INT_MIN->INT_MINDOTS -->
+<!-- INT_MINDOTS->INT_BOT -->
+<g id="edge9" class="edge">
+<title>INT_MINDOTS->INT_BOT</title>
+<path fill="none" stroke="black" d="M129.69,-82.59C157.87,-70.39 206.96,-49.14 240.58,-34.59"/>
+<polygon fill="black" stroke="black" points="241.73,-37.91 249.51,-30.72 238.95,-31.48 241.73,-37.91"/>
+</g>
+<!-- INT_MINDOTS->INT_MINUS -->
+<!-- INT_MINUS->INT_BOT -->
+<g id="edge10" class="edge">
+<title>INT_MINUS->INT_BOT</title>
+<path fill="none" stroke="black" d="M210.17,-79.75C221.61,-69.28 238.28,-54.04 252.06,-41.44"/>
+<polygon fill="black" stroke="black" points="254.05,-44.36 259.07,-35.03 249.33,-39.19 254.05,-44.36"/>
+</g>
+<!-- INT_MINUS->INT_ZERO -->
+<!-- INT_ZERO->INT_BOT -->
+<g id="edge11" class="edge">
+<title>INT_ZERO->INT_BOT</title>
+<path fill="none" stroke="black" d="M276.6,-74.82C276.6,-66.77 276.6,-56.98 276.6,-47.86"/>
+<polygon fill="black" stroke="black" points="280.1,-47.98 276.6,-37.98 273.1,-47.98 280.1,-47.98"/>
+</g>
+<!-- INT_ZERO->INT_PLUS -->
+<!-- INT_PLUS->INT_BOT -->
+<g id="edge12" class="edge">
+<title>INT_PLUS->INT_BOT</title>
+<path fill="none" stroke="black" d="M342.55,-80.07C331.3,-69.66 314.75,-54.33 301.04,-41.64"/>
+<polygon fill="black" stroke="black" points="303.78,-39.4 294.06,-35.17 299.02,-44.53 303.78,-39.4"/>
+</g>
+<!-- INT_PLUS->INT_MAXDOTS -->
+<!-- INT_MAXDOTS->INT_BOT -->
+<g id="edge13" class="edge">
+<title>INT_MAXDOTS->INT_BOT</title>
+<path fill="none" stroke="black" d="M421.42,-82.44C393.56,-70.24 345.4,-49.14 312.32,-34.65"/>
+<polygon fill="black" stroke="black" points="314.1,-31.61 303.54,-30.8 311.29,-38.02 314.1,-31.61"/>
+</g>
+<!-- INT_MAXDOTS->INT_MAX -->
+<!-- INT_MAX->INT_BOT -->
+<g id="edge14" class="edge">
+<title>INT_MAX->INT_BOT</title>
+<path fill="none" stroke="black" d="M514.35,-86.41C471.9,-74.38 372.87,-46.3 316.93,-30.44"/>
+<polygon fill="black" stroke="black" points="318.05,-27.12 307.47,-27.76 316.14,-33.85 318.05,-27.12"/>
+</g>
+</g>
+</svg>
|
