diff options
| author | Dibyendu Majumdar <dibyendumajumdar@users.noreply.github.com> | 2023-11-11 23:17:22 +0000 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-11-11 23:17:22 +0000 |
| commit | 1a9cac97df063af82516ca35bde34fde62d24c56 (patch) | |
| tree | 7bab31bac1cf890466b3f0884a0f59c784cc0027 /chapter06/docs/06-graph1-pre.svg | |
| parent | 077b25007cf8af3c3673d017625ea255bda87620 (diff) | |
| download | Simple-1a9cac97df063af82516ca35bde34fde62d24c56.tar.gz Simple-1a9cac97df063af82516ca35bde34fde62d24c56.zip | |
Chapter 6 (#38)
* #37 Create chapter 6 skeleton
* #37 Revise type system - TOP, BOTTOM, CONTROL are now directly implemented in Type, XCONTROL is a new type and that's implemented directly too.
We have a _type field that is like an enum.
* #37 Revise Type.meet() - this is now final.
Subclasses can override xmeet() which is protected but
now handles simple types in Type itself.
* #37 Basic test for peephole of CFG
* #37 Revise compute of if
* #37 Revise compute of if
* #37 WIP peephole of If
* #37 WIP peephole of If
* #37 WIP peephole of If
* #37 WIP peephole of If
* #37 WIP peephole of If
* #37 WIP fix the chars inserted by IntelliJ
* #37 WIP Fix compute type in IfNode
* #37 WIP Null check region inputs
* #37 WIP Fix where we choose great grand parent instead of grand parent
Add new test
* #37 WIP More fixes and tests
* #37 WIP Some minor adjustments
* Cleanup folding dead IF tests
Remove isDeadCtrl & just test for the constant.
Remove DEAD_CTRL, doesn't properly reset between tests.
Move keep/unkeep to Node.
PhiNode has a proper compute() call.
ProjNode ideal is a lot simpler.
Region doesn't ever get a null.
Move the mergeScopes Region peep till after all Phis are added.
Type TOP and XCONTROL count as constants.
TypeTuple gets a toString
* #37 WIP Upate README
* #37 WIP Region node should check if one of its inputs is a region that needs to be peepholed
* #37 WIP If node should check if its ctrl input is a Region that has only 1 live input so can be peepholed
* #37 WIP Further update to README to make the peephole logic clearer. Also discuss the relationship between Region and Phi nodes
* Region removes dead input paths
Remove region-folding in Return, If.
Add a Makefile.
Reformat triple-quote lines to be emacs-friendly.
* StopNode idealize
Return type sharpens to include control input.
* Remove !=, >=, >; use Not and <, <=, ==
Fix bug mixing rotating different ops.
Generalize Add fold constants; apply to Mul, EQ.
Fix Div.copy
* Fix bug rotating e.g. < or <=
Peep is only valid for associative ops
* #37 WIP Doc updates
* Work over the Ch6 Readme
Major issue: Region inputs align 1-to-1 with Phi inputs, but a Region can have zero to many Phis. When we lose a Region input (dead path), we need to lose the same inputs to each Phi - but we don't lose the Phis themselves, unless we're folding away down to the last live input.
* Update chapter06/README.md
Co-authored-by: Yichen Yan <oraluben@outlook.com>
* Update chapter06/README.md
Co-authored-by: Yichen Yan <oraluben@outlook.com>
* #37 Backport type system changes to chapter 2
* #37 Backport type system changes to chapter 3
* #37 Backport type system changes to chapter 4
* #37 Backport type system changes to chapter 5
* #37 Merge chapter 5 updates from main.
Remove language grammar module as we describe the grammar incrementally in each chapter.
* #37 Chapter 6 doc updates - added visuals to show effects of CFG peephole
* #37 Sync some updates to chapter 2
* #37 Sync some updates to chapter 3
* #37 Sync some updates to chapter 4
---------
Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Diffstat (limited to 'chapter06/docs/06-graph1-pre.svg')
| -rw-r--r-- | chapter06/docs/06-graph1-pre.svg | 160 |
1 files changed, 160 insertions, 0 deletions
diff --git a/chapter06/docs/06-graph1-pre.svg b/chapter06/docs/06-graph1-pre.svg new file mode 100644 index 00000000..f80edcfc --- /dev/null +++ b/chapter06/docs/06-graph1-pre.svg @@ -0,0 +1,160 @@ +<?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: chapter06 Pages: 1 --> +<svg width="316pt" height="420pt" + viewBox="0.00 0.00 316.00 420.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 416)"> +<title>chapter06</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-416 312,-416 312,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-404 300,-404 300,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="35,-367 35,-392 85,-392 85,-367 35,-367"/> +<polygon fill="none" stroke="black" points="35,-367 35,-392 85,-392 85,-367 35,-367"/> +<text text-anchor="start" x="41.5" y="-375.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="35,-336 35,-367 85,-367 85,-336 35,-336"/> +<polygon fill="yellow" stroke="transparent" points="40,-341 40,-362 80,-362 80,-341 40,-341"/> +<polygon fill="none" stroke="black" points="40,-341 40,-362 80,-362 80,-341 40,-341"/> +<text text-anchor="start" x="43" y="-347.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="150,-52 96,-52 96,-16 150,-16 150,-52"/> +<text text-anchor="middle" x="123" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return12 --> +<g id="node6" class="node"> +<title>Return12</title> +<polygon fill="yellow" stroke="black" points="114,-124 48,-124 48,-88 114,-88 114,-124"/> +<text text-anchor="middle" x="81" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return12 --> +<g id="edge1" class="edge"> +<title>Stop3->Return12</title> +<path fill="none" stroke="red" d="M112.62,-52.3C107.74,-60.44 101.81,-70.31 96.42,-79.3"/> +<polygon fill="red" stroke="red" points="93.41,-77.52 91.26,-87.9 99.41,-81.12 93.41,-77.52"/> +<text text-anchor="middle" x="109.62" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return16 --> +<g id="node10" class="node"> +<title>Return16</title> +<polygon fill="yellow" stroke="black" points="198,-124 132,-124 132,-88 198,-88 198,-124"/> +<text text-anchor="middle" x="165" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return16 --> +<g id="edge2" class="edge"> +<title>Stop3->Return16</title> +<path fill="none" stroke="red" d="M133.38,-52.3C138.26,-60.44 144.19,-70.31 149.58,-79.3"/> +<polygon fill="red" stroke="red" points="146.59,-81.12 154.74,-87.9 152.59,-77.52 146.59,-81.12"/> +<text text-anchor="middle" x="130.38" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="black" cx="138" cy="-364" rx="27" ry="18"/> +<text text-anchor="middle" x="138" y="-360.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- If7 --> +<g id="node4" class="node"> +<title>If7</title> +<polygon fill="yellow" stroke="transparent" points="24,-267 24,-292 118,-292 118,-267 24,-267"/> +<polygon fill="none" stroke="black" points="24,-267 24,-292 118,-292 118,-267 24,-267"/> +<text text-anchor="start" x="65.5" y="-275.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="24,-236 24,-267 118,-267 118,-236 24,-236"/> +<polygon fill="yellow" stroke="transparent" points="29,-241 29,-262 69,-262 69,-241 29,-241"/> +<polygon fill="none" stroke="black" points="29,-241 29,-262 69,-262 69,-241 29,-241"/> +<text text-anchor="start" x="32" y="-247.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="69,-241 69,-262 113,-262 113,-241 69,-241"/> +<polygon fill="none" stroke="black" points="69,-241 69,-262 113,-262 113,-241 69,-241"/> +<text text-anchor="start" x="72" y="-247.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If7->Start2 --> +<g id="edge3" class="edge"> +<title>If7->Start2:p0</title> +<path fill="none" stroke="red" d="M64.35,-296.23C62.56,-306.6 60.93,-318.45 60.29,-329.99"/> +<polygon fill="red" stroke="red" points="56.79,-329.9 60,-340 63.79,-330.11 56.79,-329.9"/> +<text text-anchor="middle" x="61.35" y="-298.83" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If7->Con_6 --> +<g id="edge4" class="edge"> +<title>If7->Con_6</title> +<path fill="none" stroke="black" d="M92.2,-296.01C101.67,-309.86 112.66,-325.94 121.5,-338.87"/> +<polygon fill="black" stroke="black" points="118.7,-340.97 127.24,-347.25 124.48,-337.02 118.7,-340.97"/> +<text text-anchor="middle" x="89.2" y="-298.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_11 --> +<g id="node5" class="node"> +<title>Con_11</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">#2</text> +</g> +<!-- Return12->If7 --> +<g id="edge5" class="edge"> +<title>Return12->If7:p0</title> +<path fill="none" stroke="red" d="M83.45,-124.21C85.4,-142.49 86.7,-172.01 79,-196 73.01,-214.66 56.37,-216.36 50.82,-229.83"/> +<polygon fill="red" stroke="red" points="47.32,-229.54 49,-240 54.21,-230.77 47.32,-229.54"/> +<text text-anchor="middle" x="80.45" y="-126.81" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return12->Con_11 --> +<g id="edge6" class="edge"> +<title>Return12->Con_11</title> +<path fill="none" stroke="black" d="M71.61,-124.3C67.1,-132.6 61.63,-142.69 56.67,-151.81"/> +<polygon fill="black" stroke="black" points="53.46,-150.4 51.76,-160.86 59.61,-153.74 53.46,-150.4"/> +<text text-anchor="middle" x="68.61" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_13 --> +<g id="node7" class="node"> +<title>Con_13</title> +<ellipse fill="none" stroke="black" cx="218" cy="-264" rx="74.19" ry="18"/> +<text text-anchor="middle" x="218" y="-260.3" font-family="Times,serif" font-size="14.00">#~CONTROL</text> +</g> +<!-- Region14 --> +<g id="node8" class="node"> +<title>Region14</title> +<polygon fill="yellow" stroke="black" points="190,-196 124,-196 124,-160 190,-160 190,-196"/> +<text text-anchor="middle" x="157" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region14->If7 --> +<g id="edge8" class="edge"> +<title>Region14->If7:p1</title> +<path fill="none" stroke="red" d="M150.64,-196.06C144.08,-212.53 133.37,-236.39 122.96,-246.35"/> +<polygon fill="red" stroke="red" points="121.27,-243.29 114,-251 124.49,-249.5 121.27,-243.29"/> +<text text-anchor="middle" x="147.64" y="-198.66" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Region14->Con_13 --> +<g id="edge7" class="edge"> +<title>Region14->Con_13</title> +<path fill="none" stroke="black" d="M169.64,-196.4C178.34,-208.39 190.04,-224.5 199.75,-237.87"/> +<polygon fill="black" stroke="black" points="197.09,-240.16 205.79,-246.19 202.75,-236.04 197.09,-240.16"/> +<text text-anchor="middle" x="166.64" y="-199" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_15 --> +<g id="node9" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="235" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="235" y="-174.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- Return16->Region14 --> +<g id="edge9" class="edge"> +<title>Return16->Region14</title> +<path fill="none" stroke="red" d="M163.02,-124.3C162.14,-132.02 161.08,-141.29 160.1,-149.89"/> +<polygon fill="red" stroke="red" points="156.61,-149.56 158.95,-159.9 163.57,-150.36 156.61,-149.56"/> +<text text-anchor="middle" x="160.02" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return16->Con_15 --> +<g id="edge10" class="edge"> +<title>Return16->Con_15</title> +<path fill="none" stroke="black" d="M182.3,-124.3C191.72,-133.72 203.47,-145.47 213.47,-155.47"/> +<polygon fill="black" stroke="black" points="211.18,-158.12 220.72,-162.72 216.12,-153.18 211.18,-158.12"/> +<text text-anchor="middle" x="179.3" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> |