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, 86 insertions, 0 deletions

diff --git a/chapter06/docs/06-graph3-nonconst.gv b/chapter06/docs/06-graph3-nonconst.gv
new file mode 100644
index 00000000..0746be85
--- /dev/null
+++ b/chapter06/docs/06-graph3-nonconst.gv
@@ -0,0 +1,86 @@
+digraph chapter06 {
+/*
+int a = 0;
+int b = 1;
+if( arg ) {
+    a = 2;
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b;
+
+*/
+	rankdir=BT;
+	ordering="in";
+	concentrate="true";
+	subgraph cluster_Nodes {
+		Start2 [ shape=plaintext label=<
+			<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
+			<TR><TD BGCOLOR="yellow">Start</TD></TR>
+			<TR><TD>
+				<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+				<TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR>
+				</TABLE>
+			</TD></TR>
+			</TABLE>>
+		];
+		Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ];
+		Con_6 [ label="#0" ];
+		Con_7 [ label="#1" ];
+		If8 [ shape=plaintext label=<
+			<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
+			<TR><TD BGCOLOR="yellow">If</TD></TR>
+			<TR><TD>
+				<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+				<TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR>
+				</TABLE>
+			</TD></TR>
+			</TABLE>>
+		];
+		Con_12 [ label="#2" ];
+		If13 [ shape=plaintext label=<
+			<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
+			<TR><TD BGCOLOR="yellow">If</TD></TR>
+			<TR><TD>
+				<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+				<TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR>
+				</TABLE>
+			</TD></TR>
+			</TABLE>>
+		];
+		Con_17 [ label="#2" ];
+		Con_18 [ label="#3" ];
+		Region19 [ shape=box style=filled fillcolor=yellow label="Region" ];
+		Phi_b20 [ style=filled fillcolor=lightyellow label="&phi;_b" ];
+		Region21 [ shape=box style=filled fillcolor=yellow label="Region" ];
+		Phi_a22 [ style=filled fillcolor=lightyellow label="&phi;_a" ];
+		Phi_b23 [ style=filled fillcolor=lightyellow label="&phi;_b" ];
+		Add24 [ label="+" ];
+		Return25 [ shape=box style=filled fillcolor=yellow label="Return" ];
+		{ rank=same; Region19;Phi_b20;}
+		{ rank=same; Region21;Phi_b23;Phi_a22;}
+	}
+	edge [ fontname=Helvetica, fontsize=8 ];
+	Stop3 -> Return25[taillabel=0 color=red];
+	If8 -> Start2:p0[taillabel=0 color=red];
+	If8 -> Start2:p1[taillabel=1];
+	If13 -> If8:p0[taillabel=0 color=red];
+	If13 -> Start2:p1[taillabel=1];
+	Region19 -> If13:p0[taillabel=1 color=red];
+	Region19 -> If13:p1[taillabel=2 color=red];
+	Phi_b20 -> Region19 [style=dotted taillabel=0];
+	Phi_b20 -> Con_17[taillabel=1];
+	Phi_b20 -> Con_18[taillabel=2];
+	Region21 -> Region19[taillabel=1 color=red];
+	Region21 -> If8:p1[taillabel=2 color=red];
+	Phi_a22 -> Region21 [style=dotted taillabel=0];
+	Phi_a22 -> Con_12[taillabel=1];
+	Phi_a22 -> Con_6[taillabel=2];
+	Phi_b23 -> Region21 [style=dotted taillabel=0];
+	Phi_b23 -> Phi_b20[taillabel=1];
+	Phi_b23 -> Con_7[taillabel=2];
+	Add24 -> Phi_b23[taillabel=1];
+	Add24 -> Phi_a22[taillabel=2];
+	Return25 -> Region21[taillabel=0 color=red];
+	Return25 -> Add24[taillabel=1];
+}
\ No newline at end of file