Chapter 2 (#4)

* Start on Chapter 2.

* Start on Chapter 2.

* Refactor

* Refactor

* Initial attempt at peephole opt for add operation

* cleanup unused import

* Start on graph visualizer

* Start on graph visualizer

* Rework chapter 2

Add a short discourse on the Types, and provide a Bottom type.

Make a final toString; require each Node to specify its special printing via label().

Add a recursing printer called print(); toString is used by default in the debugger and so cannot be recursive.

Make the peephole rules based on a proper Type and idealize calls.
Big comments about the Type computations.

Every node picks up a _print, compute and idealize() call.

Rename long arith ops Divide, UnaryMinus, Multiply, Subtract into shorter uniform-length names.  Cleans up the parser where he does the precedence op parsing.

Rework Parser:
- Drop Token class, its all Strings except in the one place we know a number is coming
- Embed the Lexer as a field in the Parser, instead of trying to pass it around everywhere in the Parser
- StartNode becomes a read-only global, so we don't have to pass it around everywhere in the Parser AND optimizer.
- Lexer matches on strings and returns strings.  Match and consume *at the moment* instead of carrying around a current token/string and forcing the next-token after consuming the current one.
- All parse subexpressions shrink by 1/2 after these changes.

* Initial writeup of Chapter 2

* Initial writeup of Chapter 2

* Initial writeup of Chapter 2

* Initial writeup of Chapter 2

* Remove range

* progress Chapter 2

Drop integer ranges.
Broader lattice pic.
Lots of prose changes in the readme.
Fixed title in gviz dot generation.
Fixed bug with peephole making redundant constants.

* Implement compute for all the arithmetic node types
Add a flag to switch off peephole so we can see the full graph
Add post peephole graph to writeup

* Implement compute for all the arithmetic node types
Add a flag to switch off peephole so we can see the full graph
Add post peephole graph to writeup

* Fix bad path to the svg

* Update pre-peephole diagram

* Add dead code elimination

...and a set_def to proper update graph edges.

* Update README.md

* Cleanup the GraphVisualizer a bit.
Update the graphs.
Update the chapter list as chapter 3 deleted, and chapter 4 is now chapter 3.

---------

Co-authored-by: Cliff Click <cliffc@acm.org>

1 files changed, 20 insertions, 17 deletions

diff --git a/README.md b/README.md
index bec41b81..ef698c69 100644
--- a/README.md
+++ b/README.md
@@ -28,20 +28,23 @@ 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: Simple binary arithmetic such as addition, subtraction, multiplication, division with constants. Peephole optimization / simple constant folding.
-* Chapter 3: Graphical Visualization of Sea of Nodes IR.
-* Chapter 4: Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant.
-* Chapter 5: Binary and Comparison operators involving constants and variables. Non-zero values will be truthy.
-* Chapter 6: `if` statement.  CFG construction, peephole optimization around dead control flow.
-* Chapter 7: `while` statement. 
-* Chapter 8: Global Value Numbering.
-* Chapter 9: Functions and calls.
-* Chapter 10: Boolean operators `&&`, `||` and `!` including short circuit.
-* Chapter 11: `float` type.
-* Chapter 12: Memory effects: general memory edges in SSA. Peephole optimization around load-after-store/store-after-store.
-* Chapter 13: Equivalence class aliasing, fine grained peephole optimizations. Free ptr-to analysis in SoN; but does not handle aliasing in arrays.
-* Chapter 14: One dimensional static length array type. Array load/store.
-* Chapter 15: Global Code Motion - unwind SoN to CFG. Scheduling.
-* Chapter 16: Instruction selection, BURS.
-* Chapter 17: Backend register allocation.
-* Chapter 18: Garbage Collection.
\ No newline at end of file
+* [Chapter 2](chapter02/README.md): Simple binary arithmetic such as addition, subtraction, multiplication, division
+  with constants. Peephole optimization / simple constant folding.
+* Chapter 3: Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a
+  constant.
+* Chapter 4: Binary and Comparison operators involving constants and variables. Non-zero values will be truthy.
+* Chapter 5: `if` statement. CFG construction, peephole optimization around dead control flow.
+* Chapter 6: `while` statement.
+* Chapter 7: Global Value Numbering.
+* Chapter 8: Functions and calls.
+* Chapter 9: Boolean operators `&&`, `||` and `!` including short circuit.
+* Chapter 10: `float` type.
+* Chapter 11: Memory effects: general memory edges in SSA. Peephole optimization around
+  load-after-store/store-after-store.
+* Chapter 12: Equivalence class aliasing, fine grained peephole optimizations. Free ptr-to analysis in SoN; but does not
+  handle aliasing in arrays.
+* Chapter 13: One dimensional static length array type. Array load/store.
+* Chapter 14: Global Code Motion - unwind SoN to CFG. Scheduling.
+* Chapter 15: Instruction selection, BURS.
+* Chapter 16: Backend register allocation.
+* Chapter 17: Garbage Collection.
\ No newline at end of file