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

diff --git a/chapter02/README.md b/chapter02/README.md
new file mode 100644
index 00000000..5b4c4958
--- /dev/null
+++ b/chapter02/README.md
@@ -0,0 +1,126 @@
+# Chapter 2
+
+In this chapter we extend the language grammar to include arithmetic operations such as addition, subtraction,
+multiplication, division, and unary minus. This allows us to write statements such as:
+
+```
+return 1 + 2 * 3 + -5;
+```
+
+Here is the [complete language grammar](docs/02-grammar.md) for this chapter. 
+
+## Extensions to Intermediate Representation
+
+In chapter 1 we introduced following nodes.
+
+| Node Name | Type    | Description                        | Inputs                                                           | Value                                                 |
+|-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------|
+| Start     | Control | Start of function                  | None                                                             | None for now as we do not have function arguments yet |
+| Return    | Control | End of function                    | Predecessor control node, Data node value                        | Return value of the function                          |
+| Constant  | Data    | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant                                 |
+
+We extend the set of nodes by adding following additional node types.
+
+| Node Name  | Type | Description                   | Inputs                                                     | Value                       |
+|------------|------|-------------------------------|------------------------------------------------------------|-----------------------------|
+| Add        | Data | Add two values                | Two data nodes, values are added, order not important      | Result of the add operation |
+| Sub        | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters       | Result of the subtract      |
+| Mul        | Data | Multiply two values           | Two data nodes, values are multiplied, order not important | Result of the multiply      |
+| Div        | Data | Divide a value by another     | Two data nodes, values are divided, order matters          | Result of the division      |
+| UnaryMinus | Data | Negate a value                | One data node, value is negated                            | Result of the unary minus   |
+
+## Peephole Optimizations
+
+Nodes in the graph can be peephole-optimized.  The graph is viewed through a
+"peephole", a small chunk of graph, and if a certain pattern is detected we
+locally rewrite the graph.
+
+During parsing, these peephole optimizations are particularly easy to check and
+apply: there are no uses (yet) of a just-created Node from a just-parsed piece
+of syntax, so there's no effort to the "rewrite" part of the problem. We just
+replace in-place before installing Nodes into the graph.
+
+This replacement might allow us to *kill* the unused inputs from the replaced
+Node, basically doing a modest Dead Code Elimination during parsing.
+
+E.g. Suppose we already parsed out a constant `1`, and a constant `2`; then when we
+parse an `Add(1,2)`, the peephole rule for constant math replaces the Add with a
+constant `3`.  At this point, we also *kill* the unused `Add`, which recursively
+may *kill* the unused constants `1` and `2`.
+
+
+
+## Constant Folding and Constant Propagation
+
+In this chapter and next we focus on a particular peephole optimization:
+constant folding and constant propagation.  Since we do not have variables
+until Chapter 3, the main feature we demonstrate now is constant folding.
+However, we introduce some additional ideas into the compiler at this stage, to
+set the scene for Chapter 3.
+
+It is useful for the compiler to know at various points of the program whether
+a node's value is a constant. The compiler can use this knowledge to perform various
+optimizations such as:
+
+* Evaluate expressions at compile time and replace an expression with a constant
+* The compiler may be able to identify regions of code that are dead and no
+  longer needed, such as when a conditional branch always take one of the
+  branches
+* Pointers may be known to be not-null, and a null check can be skipped.
+* Array indices may be known to be in-range, and a range check can be skipped
+* Many additional optimizations are possible when the compiler learns more
+  about the possible set of Node values
+
+In order to achieve above, we annotate Nodes with Types.
+
+The Type annotation serves two purposes:
+
+* it defines the set of operations allowed on the Node
+* it defines the set of values the Node takes on
+
+The type itself is identified by the Java class sub-typing relationship; all
+types are subtypes of the class `Type`.  For now, we only have the following
+hierarchy of types:
+
+```
+Type
++-- TypeInteger
+```
+
+It turns out that the set of values associated with a Type at a specific Node
+can be conveniently represented as a "lattice". Our lattice has the following
+structure:
+
+![Lattice](./docs/02-lattice.svg)
+
+Our lattice elements can be one of three types:
+
+* the highest element is "top", denoted by T.
+* The lowest is bottom, denoted by ⊥,
+* All elements in the middle are constants.
+
+Assigning ⊥ means that the Node's value is known to be not a compile time
+constant, whereas assigning T means that the Node's value may be some (as yet)
+undetermined constant.  The transition of the Node's type can occur from T to
+some constant to ⊥.
+
+In later chapters we will explore extending this lattice, as it frequently
+forms the heart of core optimizations we want our compiler to do.
+
+There are other important properties of the Lattice that we discuss in Chapter
+3, such as the "meet" operator and its rules.
+
+
+## Nodes Pre Peephole Optimization
+
+The following visual shows how the graph looks like pre-peephole optimization:
+
+![Example Visual](./docs/02-pre-peephole-ex1.svg)
+
+* Control nodes appear as square boxes
+* Control edges are in bold red
+* The edges from Start to Constants are shown in dotted lines as these are not true def-use edges
+
+## Post-peephole
+
+![Example Visual](./docs/02-post-peephole-ex1.svg)
\ No newline at end of file