summaryrefslogtreecommitdiff
path: root/chapter02/README.md
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2024-08-04 13:53:26 -0700
committerGitHub <noreply@github.com>2024-08-04 13:53:26 -0700
commit09ecc9dd4ccf9ce636ae54f820d9c88adf5cce95 (patch)
tree232e04913ba4c437d9b912da9fc4b9397f91be85 /chapter02/README.md
parentd6442ce5d00b9bea52d366ff4d6ae8c03b84aabb (diff)
downloadSimple-09ecc9dd4ccf9ce636ae54f820d9c88adf5cce95.tar.gz
Simple-09ecc9dd4ccf9ce636ae54f820d9c88adf5cce95.zip
Update README.md (#93)
Diffstat (limited to 'chapter02/README.md')
-rw-r--r--chapter02/README.md18
1 files changed, 16 insertions, 2 deletions
diff --git a/chapter02/README.md b/chapter02/README.md
index 500e9ae8..eb908f06 100644
--- a/chapter02/README.md
+++ b/chapter02/README.md
@@ -88,8 +88,9 @@ Type
```
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:
+can be conveniently represented as a "lattice"
+(https://en.wikipedia.org/wiki/Lattice_(order).
+Our lattice has the following structure:
![Lattice](./docs/02-lattice.svg)
@@ -104,6 +105,19 @@ An invariant of peephole optimizations is that the type of a Node always moves d
In later chapters we will explore extending this lattice, as it frequently
forms the heart of core optimizations we want our compiler to do.
+We add a `_type` field to every Node, to store its current computed best
+`Type`. We need a field to keep the optimizer runtime linear, and later when
+doing an optimistic version of constant propagation (called Sparse Conditional
+Constant Propagation)
+(https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation).
+
+We add a `_type` field even to `Start` and `Return`, and later to all control
+Nodes - because the Sea of Nodes does not distinguish between control and data.
+Both nodes are equally peepholed and optimized, and this will be covered
+starting in [Chapter 4](../chapter04/README.md) and [Chapter
+5](../chapter05/README.md).
+
+
There are other important properties of the Lattice that we discuss in [Chapter
4](../chapter04/README.md) and [Chapter 10](../chapter10/README.md), such as the "meet" and "join" operators and their rules.