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>

1 files changed, 67 insertions, 0 deletions

diff --git a/chapter06/docs/06-graph3-true.svg b/chapter06/docs/06-graph3-true.svg
new file mode 100644
index 00000000..7e573cc6
--- /dev/null
+++ b/chapter06/docs/06-graph3-true.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: chapter06 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>chapter06</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>
+<!-- Return29 -->
+<g id="node4" class="node">
+<title>Return29</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;Return29 -->
+<g id="edge1" class="edge">
+<title>Stop3&#45;&gt;Return29</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_28 -->
+<g id="node3" class="node">
+<title>Con_28</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">#4</text>
+</g>
+<!-- Return29&#45;&gt;Start2 -->
+<g id="edge2" class="edge">
+<title>Return29&#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>
+<!-- Return29&#45;&gt;Con_28 -->
+<g id="edge3" class="edge">
+<title>Return29&#45;&gt;Con_28</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>