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>

1 files changed, 67 insertions, 0 deletions

diff --git a/chapter09/docs/09-graph4.svg b/chapter09/docs/09-graph4.svg
new file mode 100644
index 00000000..4eef5414
--- /dev/null
+++ b/chapter09/docs/09-graph4.svg
@@ -0,0 +1,67 @@
+<?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="178pt" height="248pt"
+ viewBox="0.00 0.00 178.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>chapter09</title>
+<polygon fill="white" stroke="transparent" points="-4,4 -4,-244 174,-244 174,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="black" points="8,-8 8,-232 162,-232 162,-8 8,-8"/>
+</g>
+<!-- Start2 -->
+<g id="node1" class="node">
+<title>Start2</title>
+<polygon fill="yellow" stroke="transparent" points="24,-195 24,-220 74,-220 74,-195 24,-195"/>
+<polygon fill="none" stroke="black" points="24,-195 24,-220 74,-220 74,-195 24,-195"/>
+<text text-anchor="start" x="30.5" y="-203.8" font-family="Times,serif" font-size="14.00">Start</text>
+<polygon fill="none" stroke="black" points="24,-164 24,-195 74,-195 74,-164 24,-164"/>
+<polygon fill="yellow" stroke="transparent" points="29,-169 29,-190 69,-190 69,-169 29,-169"/>
+<polygon fill="none" stroke="black" points="29,-169 29,-190 69,-190 69,-169 29,-169"/>
+<text text-anchor="start" x="32" y="-175.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="112,-52 58,-52 58,-16 112,-16 112,-52"/>
+<text text-anchor="middle" x="85" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text>
+</g>
+<!-- Return10 -->
+<g id="node4" class="node">
+<title>Return10</title>
+<polygon fill="yellow" stroke="black" points="118,-124 52,-124 52,-88 118,-88 118,-124"/>
+<text text-anchor="middle" x="85" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text>
+</g>
+<!-- Stop3&#45;&gt;Return10 -->
+<g id="edge1" class="edge">
+<title>Stop3&#45;&gt;Return10</title>
+<path fill="none" stroke="red" d="M85,-52.3C85,-60.02 85,-69.29 85,-77.89"/>
+<polygon fill="red" stroke="red" points="81.5,-77.9 85,-87.9 88.5,-77.9 81.5,-77.9"/>
+<text text-anchor="middle" x="82" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Con_9 -->
+<g id="node3" class="node">
+<title>Con_9</title>
+<ellipse fill="none" stroke="black" cx="127" cy="-192" rx="27" ry="18"/>
+<text text-anchor="middle" x="127" y="-188.3" font-family="Times,serif" font-size="14.00">#0</text>
+</g>
+<!-- Return10&#45;&gt;Start2 -->
+<g id="edge2" class="edge">
+<title>Return10&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="red" d="M68.26,-124.13C60.77,-133.26 52.99,-145.23 50.13,-158.06"/>
+<polygon fill="red" stroke="red" points="46.66,-157.67 49,-168 53.61,-158.46 46.66,-157.67"/>
+<text text-anchor="middle" x="65.26" y="-126.73" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Return10&#45;&gt;Con_9 -->
+<g id="edge3" class="edge">
+<title>Return10&#45;&gt;Con_9</title>
+<path fill="none" stroke="black" d="M93.7,-124.4C99.66,-136.31 107.65,-152.3 114.31,-165.62"/>
+<polygon fill="black" stroke="black" points="111.28,-167.38 118.88,-174.76 117.54,-164.25 111.28,-167.38"/>
+<text text-anchor="middle" x="90.7" y="-127" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+</g>
+</svg>