diff options
| author | Dibyendu Majumdar <dibyendumajumdar@users.noreply.github.com> | 2024-03-03 17:55:47 +0000 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2024-03-03 17:55:47 +0000 |
| commit | c3842e2a01522f52ae4690de3e9c90efa33f0f27 (patch) | |
| tree | bcedc8d459d74a57acc7ea3b1b968aa60db4a5e6 /chapter09/docs/09-graph6.svg | |
| parent | 29bc63423aeba9327b2e60959f8dbb2c8e718a29 (diff) | |
| download | Simple-c3842e2a01522f52ae4690de3e9c90efa33f0f27.tar.gz Simple-c3842e2a01522f52ae4690de3e9c90efa33f0f27.zip | |
Chapter 9 (#66)
* chapter9
* merge fixes to chapter8
* Ch 9 notes
* Ch 9 work
Add a Iterate phase, after parsing.
Add a Worklist with fast dup removal & rand pull.
Add a Node.iter() call which returns progress or null. Peephole calls it. Iter() also asserts that Types make monotonic progress.
Intern all types, so we can do a cheap/easy "isa" test.
* GVN
* rename temporarily
* Apply Cliff's worklist changes
* Apply Cliff's GVN changes
* Revert "GVN"
This reverts commit 9dc6db1cac7e40de4a58333cbc3c9c3e7c088e6f.
* Revert "Ch 9 work"
This reverts commit df5b74e6c017a4f237a5d1a550a83b40a7928876.
* Fix 3-1+2
Was computing as 3-(1+2) == 0, not 4 as expected.
Add tests.
Unlock in swap12.
* Missed some cut-n-paste changes
* Break up the test file per-chapter
* Fix keep-alive while looping expressions
Must "hook" LHS prior to calling peepholes
* Ch9 Region optimization
Bug fix, GVN hits 2 inProgress Loops
Bug fix lifetime tracking when parsing dead code
Bug fix debug find call
GraphViz post-iterate
* Readme overhaul
Progress on Ch 9 readme
* Fix bugs hashcode
Was relying on label() hashCode for Phi, Proj; since this is debug-only cannot be relied on. Proj relies on _idx field, Phi needs a !inProgress check.
* Constant nodes print "#" before con
* Add a farther neighbor check
Peeps that check more than the nearest neighbor register a dependency on the Node that failed them. Should that Node later change, the peep root is put back on the worklist and revisited.
* Fix addDeps assert
Unwind golden test print, print smarter.
Unlock edges in subsume
* Update README
* shuffle adddeps forward one
its needed again shortly in another test, so just cover it now
* Fix fuzzer bugs
Peep x+(-y) to x-y
Handle TOP inputs; didn't think it could happen before running an optimistic pass, but fuzzer proved me wrong.
Deleting an input can recursively delete the self-node.
When checking the compute() type assert, delay setting _type so the method can just be re-run in the debugger.
Missing addDep in Phi
Parser mis-handling stacked operators like "1+-2" or "1==!=<=<>=>2"
Make Work list deterministic between tests.
* Update fuzzer to run iterate (#62)
* Update fuzzer to run iterate
* Work seed is now reset by reset
* A few more fuzzer tests
Set _type in iter() even later, better debugging.
Handle dead active scopes in visiualizer.
Region ideal honors Loop invariants; finish Region ideal for single input; inProgress check is a little tighter.
Type.isConstant is true strictly for lattice centerline constants. Clean up TypeInteger.
ideaj warning removal
* Fix all fuzzer bugs
iter() does not call peep(), instead peep() is self-recursive. This allows Iterate() to call iter(), and not get into arbitrary recursive peep() changes that do not track on the worklist.
Div, Minus, If all monotonic.
Catch a bunch of progress issues.
Robustify IRPrinter and Iterate and Region ideal
* Reducer could run into an infinite loop (#63)
* Write up how the Evaluator works (#64)
* Write up how the Evaluator works
* Some small improvements and a slightly better wrap up.
* Series of fuzzer bugs.
Fix monotonicity for all data nodes.
Generic compute intercept for data nodes, check all inputs for TOP/BOTTOM, and again for IntDataNodes.
Fix general progress bug allow high Types as constants.
Fix progress Region 1-input has obvious idom.
Make shortcut for fuzzer; renames Fuzzer to not have "Test" in the class name.
Fix invert comment in TypeInteger
* All fuzzer tests pass
Turn off expensive assert accidentally turned on
CSE needs to join types.
Add a type join.
Missing dep in Phi
* More README
* Hacking alternative way to fix the type compute
* Node is no longer IntSupplier
Renamed Work to WorkList
Renamed Iterate to IterOptim
Renamed Node.iter() to Node.peepholeOpt()
WorkList expects elements to be of Node
* Add an example of GVN
* Rename the method depsClear to moveDepsToWorklist - to better capture what it actually does.
* Add a second example of GVN benefits
* Fix typo
* Add example of worklist opt
* Prepare to allow alternative post parse worklist opt
* Alternative WorkList opt that has following differences:
1. It does not require dependencies between nodes
2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step.
3. It is simple
* Alternative WorkList opt that has following differences:
1. It does not require dependencies between nodes
2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step.
3. It is simple
* The RPO list was incomplete as it only identified the subgraph accessible from the STOP node.
* Fix iter count
* Add test suggested by Xmilia
* Fix bug where after the region is peeped the phis get consistent number of inputs
* Fix bug where after the region is peeped the phis get consistent number of inputs
* Dump out stats on how many nodes we peepd during the post parse iterative opt.
* Make it easy to switch the IterOpt
* Use deps based worklist by default
* Sharper worklist add
* Copy across Cliff's changes
* Merge changes to Iterate
* Revert failing change
* Update readme
* Add comments / update docs to explain the patterns where we call addDep().
* As before, unconditionally made dep a dependent of region.
* Fix a lot of missing dep issues
Rename IterOptim -> IterPeeps
Some grammar changes in comments & readme
* Bump up fuzzer limits, more testing
Missing dep in idom calc in IfNode.
Missed idom cache clear on Region edit.
* Remove RPO based peeps
O(n^2) behavior
* Minor updates README
* fix compile bug
---------
Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Darrick Wiebe <darrickw@untether.ai>
Diffstat (limited to 'chapter09/docs/09-graph6.svg')
| -rw-r--r-- | chapter09/docs/09-graph6.svg | 184 |
1 files changed, 184 insertions, 0 deletions
diff --git a/chapter09/docs/09-graph6.svg b/chapter09/docs/09-graph6.svg new file mode 100644 index 00000000..36c70099 --- /dev/null +++ b/chapter09/docs/09-graph6.svg @@ -0,0 +1,184 @@ +<?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: chapter09 Pages: 1 --> +<svg width="338pt" height="492pt" + viewBox="0.00 0.00 338.00 492.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 488)"> +<title>chapter09</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-488 334,-488 334,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-476 322,-476 322,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="149,-439 149,-464 230,-464 230,-439 149,-439"/> +<polygon fill="none" stroke="black" points="149,-439 149,-464 230,-464 230,-439 149,-439"/> +<text text-anchor="start" x="171" y="-447.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="149,-408 149,-439 230,-439 230,-408 149,-408"/> +<polygon fill="yellow" stroke="transparent" points="154,-413 154,-434 194,-434 194,-413 154,-413"/> +<polygon fill="none" stroke="black" points="154,-413 154,-434 194,-434 194,-413 154,-413"/> +<text text-anchor="start" x="157" y="-419.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="194,-413 194,-434 225,-434 225,-413 194,-413"/> +<text text-anchor="start" x="197" y="-419.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="157,-52 103,-52 103,-16 157,-16 157,-52"/> +<text text-anchor="middle" x="130" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return21 --> +<g id="node8" class="node"> +<title>Return21</title> +<polygon fill="yellow" stroke="black" points="163,-124 97,-124 97,-88 163,-88 163,-124"/> +<text text-anchor="middle" x="130" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return21 --> +<g id="edge1" class="edge"> +<title>Stop3->Return21</title> +<path fill="none" stroke="red" d="M130,-52.3C130,-60.02 130,-69.29 130,-77.89"/> +<polygon fill="red" stroke="red" points="126.5,-77.9 130,-87.9 133.5,-77.9 126.5,-77.9"/> +<text text-anchor="middle" x="127" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Loop7 --> +<g id="node3" class="node"> +<title>Loop7</title> +<polygon fill="yellow" stroke="black" points="314,-368 260,-368 260,-332 314,-332 314,-368"/> +<text text-anchor="middle" x="287" y="-346.3" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop7->Start2 --> +<g id="edge2" class="edge"> +<title>Loop7->Start2:p0</title> +<path fill="none" stroke="red" d="M259.93,-364.13C234.34,-376.71 197.56,-395.24 181.73,-405.41"/> +<polygon fill="red" stroke="red" points="179.34,-402.85 174,-412 183.88,-408.18 179.34,-402.85"/> +<text text-anchor="middle" x="256.93" y="-357.73" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- If12 --> +<g id="node7" class="node"> +<title>If12</title> +<polygon fill="yellow" stroke="transparent" points="36,-195 36,-220 130,-220 130,-195 36,-195"/> +<polygon fill="none" stroke="black" points="36,-195 36,-220 130,-220 130,-195 36,-195"/> +<text text-anchor="start" x="77.5" y="-203.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="36,-164 36,-195 130,-195 130,-164 36,-164"/> +<polygon fill="yellow" stroke="transparent" points="41,-169 41,-190 81,-190 81,-169 41,-169"/> +<polygon fill="none" stroke="black" points="41,-169 41,-190 81,-190 81,-169 41,-169"/> +<text text-anchor="start" x="44" y="-175.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="81,-169 81,-190 125,-190 125,-169 81,-169"/> +<polygon fill="none" stroke="black" points="81,-169 81,-190 125,-190 125,-169 81,-169"/> +<text text-anchor="start" x="84" y="-175.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- Loop7->If12 --> +<g id="edge3" class="edge"> +<title>Loop7->If12:p0</title> +<path fill="none" stroke="red" d="M259.79,-335.23C256.86,-334.03 253.9,-332.92 251,-332 163.26,-304.1 109.06,-364.01 47,-296 22.33,-268.96 18.57,-203.69 31.46,-184.44"/> +<polygon fill="red" stroke="red" points="33.44,-187.32 40,-179 29.68,-181.42 33.44,-187.32"/> +<text text-anchor="middle" x="256.79" y="-328.83" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg9 --> +<g id="node4" class="node"> +<title>Phi_arg9</title> +<ellipse fill="lightyellow" stroke="black" cx="133" cy="-350" rx="37.09" ry="18"/> +<text text-anchor="middle" x="133" y="-346.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg9->Start2 --> +<g id="edge5" class="edge"> +<title>Phi_arg9->Start2:p1</title> +<path fill="none" stroke="black" d="M162.55,-360.93C181.21,-369 202.84,-382.27 208.56,-401.87"/> +<polygon fill="black" stroke="black" points="205.12,-402.59 210,-412 212.05,-401.61 205.12,-402.59"/> +<text text-anchor="middle" x="159.55" y="-363.53" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg9->Loop7 --> +<g id="edge4" class="edge"> +<title>Phi_arg9->Loop7</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M151.47,-334.01C161.54,-326.34 174.66,-317.98 188,-314 211,-307.14 219.35,-306.06 242,-314 249.14,-316.5 255.99,-320.67 262.09,-325.3"/> +<polygon fill="black" stroke="black" points="259.99,-328.1 269.92,-331.78 264.45,-322.71 259.99,-328.1"/> +<text text-anchor="middle" x="148.47" y="-327.61" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add25 --> +<g id="node10" class="node"> +<title>Add25</title> +<ellipse fill="none" stroke="black" cx="209" cy="-278" rx="27" ry="18"/> +<text text-anchor="middle" x="209" y="-274.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- LT10 --> +<g id="node5" class="node"> +<title>LT10</title> +<ellipse fill="none" stroke="black" cx="83" cy="-278" rx="27" ry="18"/> +<text text-anchor="middle" x="83" y="-274.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT10->Phi_arg9 --> +<g id="edge7" class="edge"> +<title>LT10->Phi_arg9</title> +<path fill="none" stroke="black" d="M94.1,-294.54C100.33,-303.26 108.25,-314.35 115.31,-324.24"/> +<polygon fill="black" stroke="black" points="112.58,-326.43 121.24,-332.53 118.27,-322.36 112.58,-326.43"/> +<text text-anchor="middle" x="91.1" y="-297.14" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_11 --> +<g id="node6" class="node"> +<title>Con_11</title> +<ellipse fill="none" stroke="black" cx="47" cy="-350" rx="30.59" ry="18"/> +<text text-anchor="middle" x="47" y="-346.3" font-family="Times,serif" font-size="14.00">#10</text> +</g> +<!-- LT10->Con_11 --> +<g id="edge8" class="edge"> +<title>LT10->Con_11</title> +<path fill="none" stroke="black" d="M74.65,-295.24C70.35,-303.6 65.01,-313.98 60.17,-323.39"/> +<polygon fill="black" stroke="black" points="57.02,-321.87 55.55,-332.37 63.24,-325.07 57.02,-321.87"/> +<text text-anchor="middle" x="71.65" y="-297.84" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If12->Loop7 --> +<g id="edge9" class="edge"> +<title>If12->Loop7</title> +<path fill="none" stroke="red" d="M138.19,-204.98C172.47,-214.83 215.47,-231.87 245,-260 262.62,-276.78 273.63,-302.43 279.94,-321.89"/> +<polygon fill="red" stroke="red" points="276.66,-323.13 282.89,-331.7 283.36,-321.11 276.66,-323.13"/> +<text text-anchor="middle" x="141.19" y="-198.58" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If12->LT10 --> +<g id="edge10" class="edge"> +<title>If12->LT10</title> +<path fill="none" stroke="black" d="M83,-224.28C83,-232.58 83,-241.48 83,-249.56"/> +<polygon fill="black" stroke="black" points="79.5,-249.6 83,-259.6 86.5,-249.6 79.5,-249.6"/> +<text text-anchor="middle" x="80" y="-226.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return21->Phi_arg9 --> +<g id="edge12" class="edge"> +<title>Return21->Phi_arg9</title> +<path fill="none" stroke="black" d="M137.07,-124.33C140.84,-134.53 145.09,-147.78 147,-160 155.96,-217.25 145.96,-285.18 138.86,-322"/> +<polygon fill="black" stroke="black" points="135.39,-321.46 136.86,-331.95 142.26,-322.84 135.39,-321.46"/> +<text text-anchor="middle" x="134.07" y="-126.93" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return21->If12 --> +<g id="edge11" class="edge"> +<title>Return21->If12:p1</title> +<path fill="none" stroke="red" d="M117.92,-124C112.25,-133.3 106.24,-145.44 103.95,-157.94"/> +<polygon fill="red" stroke="red" points="100.46,-157.71 103,-168 107.43,-158.38 100.46,-157.71"/> +<text text-anchor="middle" x="114.92" y="-126.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_24 --> +<g id="node9" class="node"> +<title>Con_24</title> +<ellipse fill="none" stroke="black" cx="215" cy="-350" rx="27" ry="18"/> +<text text-anchor="middle" x="215" y="-346.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Add25->Phi_arg9 --> +<g id="edge13" class="edge"> +<title>Add25->Phi_arg9</title> +<path fill="none" stroke="black" d="M185.95,-300.23C176.82,-308.64 166.31,-318.32 157.07,-326.83"/> +<polygon fill="black" stroke="black" points="188.64,-302.51 193.62,-293.17 183.89,-297.37 188.64,-302.51"/> +<polygon fill="black" stroke="black" points="154.66,-324.29 149.68,-333.64 159.4,-329.44 154.66,-324.29"/> +<text text-anchor="middle" x="190.62" y="-295.77" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add25->Con_24 --> +<g id="edge14" class="edge"> +<title>Add25->Con_24</title> +<path fill="none" stroke="black" d="M210.48,-296.3C211.14,-304.02 211.94,-313.29 212.68,-321.89"/> +<polygon fill="black" stroke="black" points="209.19,-322.23 213.53,-331.9 216.17,-321.63 209.19,-322.23"/> +<text text-anchor="middle" x="207.48" y="-298.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +</g> +</svg> |