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, 1 insertions, 2 deletions

diff --git a/README.md b/README.md
index d8f99553..59a342b1 100644
--- a/README.md
+++ b/README.md
@@ -26,7 +26,6 @@ Sea Of Nodes intermediate representation.
 
 The simple language will be a small subset of C. 
 
-* [Language](language/README.md): Simple language grammar.
 * [Chapter 1](chapter01/README.md): Script that returns an integer literal, i.e., an empty function that takes no arguments and returns a single integer value. The `return` statement.
 * [Chapter 2](chapter02/README.md): Simple binary arithmetic such as addition, subtraction, multiplication, division
   with constants. Peephole optimization / simple constant folding.
@@ -34,7 +33,7 @@ The simple language will be a small subset of C.
   constant.
 * [Chapter 4](chapter04/README.md): A non-constant external variable input named `arg`. Binary and Comparison operators involving constants and `arg`. Non-zero values will be truthy. Peephole optimizations involving algebraic simplifications. 
 * [Chapter 5](chapter05/README.md): `if` statement. CFG construction.
-* Chapter 6: Peephole optimization around dead control flow. 
+* [Chapter 6](chapter06/README.md): Peephole optimization around dead control flow. 
 * Chapter 7: `while` statement.
 * Chapter 8: Global Value Numbering.
 * Chapter 9: Functions and calls.