summaryrefslogtreecommitdiff
path: root/chapter02/README.md
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2024-09-05 09:40:02 -0700
committerThalia Archibald <thalia@archibald.dev>2024-09-07 10:54:48 -0700
commitcb1adaabe4f78a30937a93abdcc2dfddd65e6f99 (patch)
tree5357422d77b8a2ddbd4137730530ecb406ad0770 /chapter02/README.md
parentec7f127c3b32e229ada9ee52def44d6f476c0a99 (diff)
downloadSimple-cb1adaabe4f78a30937a93abdcc2dfddd65e6f99.tar.gz
Simple-cb1adaabe4f78a30937a93abdcc2dfddd65e6f99.zip
Updates README
More on Types, pushed out Arrays one more chapter
Diffstat (limited to 'chapter02/README.md')
-rw-r--r--chapter02/README.md23
1 files changed, 15 insertions, 8 deletions
diff --git a/chapter02/README.md b/chapter02/README.md
index eb908f06..262a323f 100644
--- a/chapter02/README.md
+++ b/chapter02/README.md
@@ -62,7 +62,9 @@ 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.
+* Evaluate expressions at compile time and replace an expression with a
+ constant. This idea can be extended in a number of ways and is called
+ [Partial Evaluation](https://en.wikipedia.org/wiki/Partial_evaluation).
* 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 ([Chapter 6](../chapter06/README.md)).
@@ -71,16 +73,17 @@ optimizations such as:
* 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.
+In order to achieve above, we need a way to talk about what kinds of values a Node can take
+on at runtime - we call these Types, and 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:
+The Type itself is represented as a Java class; the Java classes are used as
+convenient to represent the Type's structure; all types are subtypes of the
+class `Type`. For now, we only have the following hierarchy of types:
```
Type
@@ -89,8 +92,8 @@ Type
It turns out that the set of values associated with a Type at a specific Node
can be conveniently represented as a "lattice"
-(https://en.wikipedia.org/wiki/Lattice_(order).
-Our lattice has the following structure:
+https://en.wikipedia.org/wiki/Lattice_(order)
+. Our lattice has the following structure:
![Lattice](./docs/02-lattice.svg)
@@ -100,7 +103,11 @@ Our lattice elements can be one of three types:
* All elements in the middle are constants.
* The lowest is "bottom", denoted by ⊥; assigning ⊥ means that we know that the Node's value is **not** a compile time constant.
-An invariant of peephole optimizations is that the type of a Node always moves down the lattice.
+An invariant of peephole optimizations is that the type of a Node always moves
+*up* the lattice (towards "top"); peepholes are *pessmistic* assuming the worst
+until they can prove better. A later *optimistic* optimization will start all
+Nodes at *top* and move Types *down* the lattice as eager assumptions are
+proven wrong.
In later chapters we will explore extending this lattice, as it frequently
forms the heart of core optimizations we want our compiler to do.