From 65454d77eba95d7f814336377f78d9f42c7455f9 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 27 Nov 2024 11:29:33 -0800 Subject: More lattice docs reworks --- chapter02/README.md | 13 ++-- chapter02/docs/02-lattice.gv | 35 ---------- chapter02/docs/02-lattice.svg | 143 ------------------------------------- chapter02/docs/lattice.gv | 40 +++++++++++ chapter02/docs/lattice.svg | 159 ++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 206 insertions(+), 184 deletions(-) delete mode 100644 chapter02/docs/02-lattice.gv delete mode 100644 chapter02/docs/02-lattice.svg create mode 100644 chapter02/docs/lattice.gv create mode 100644 chapter02/docs/lattice.svg (limited to 'chapter02') diff --git a/chapter02/README.md b/chapter02/README.md index db23796d..04e34eb9 100644 --- a/chapter02/README.md +++ b/chapter02/README.md @@ -93,17 +93,18 @@ 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: +can be conveniently represented as a *lattice* +[wiki/Lattice_(order)](https://en.wikipedia.org/wiki/Lattice_(order)). Our lattice has the following structure: -![Lattice](./docs/02-lattice.svg) +![Lattice](./docs/lattice.svg) Our lattice elements can be one of three types: -* The highest element is "top", denoted by T; assigning T means that the Node's value may or may not be a compile time constant. +* The highest element is "top", denoted by ⊤; assigning ⊤ means that the Node's + value may or may not be a compile time constant. * 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. +* 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 *up* the lattice (towards "top"); peepholes are *pessmistic* assuming the worst diff --git a/chapter02/docs/02-lattice.gv b/chapter02/docs/02-lattice.gv deleted file mode 100644 index 4faa0e11..00000000 --- a/chapter02/docs/02-lattice.gv +++ /dev/null @@ -1,35 +0,0 @@ -digraph Lattice { - // Define nodes - node [shape=circle, style=filled, fillcolor=lightblue]; - Top [label="⊤"]; - Bottom [label="⊥"]; - - A [label="MIN_INT"]; - B [label="..." shape=none style=none]; - C [label="-1"]; - D [label="0"]; - E [label="1"]; - F [label="..." shape=none style=none]; - G [label="MAX_INT"]; - - - // Define edges - Top -> A [arrowhead=none]; - Top -> B [arrowhead=none]; - Top -> C [arrowhead=none]; - Top -> D [arrowhead=none]; - Top -> E [arrowhead=none]; - Top -> F [arrowhead=none]; - Top -> G [arrowhead=none]; - A -> Bottom [arrowhead=none]; - B -> Bottom [arrowhead=none]; - C -> Bottom [arrowhead=none]; - D -> Bottom [arrowhead=none]; - E -> Bottom [arrowhead=none]; - F -> Bottom [arrowhead=none]; - G -> Bottom [arrowhead=none]; - - // Additional customization - {rank=same; A; B; C; D; E; F; G; } - {rank=same; Bottom;} -} diff --git a/chapter02/docs/02-lattice.svg b/chapter02/docs/02-lattice.svg deleted file mode 100644 index 218acc6a..00000000 --- a/chapter02/docs/02-lattice.svg +++ /dev/null @@ -1,143 +0,0 @@ - - - - - - - Lattice - - - - Top - - ⊤ - - - - A - - MIN_INT - - - - Top->A - - - - - B - ... - - - - Top->B - - - - - C - - -1 - - - - Top->C - - - - - D - - 0 - - - - Top->D - - - - - E - - 1 - - - - Top->E - - - - - F - ... - - - - Top->F - - - - - G - - MAX_INT - - - - Top->G - - - - - Bottom - - ⊥ - - - - A->Bottom - - - - - B->Bottom - - - - - C->Bottom - - - - - D->Bottom - - - - - E->Bottom - - - - - F->Bottom - - - - - G->Bottom - - - - diff --git a/chapter02/docs/lattice.gv b/chapter02/docs/lattice.gv new file mode 100644 index 00000000..fe8df136 --- /dev/null +++ b/chapter02/docs/lattice.gv @@ -0,0 +1,40 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=circle, style=filled]; + nodesep=0.6; + + // ---------------------- + // Integers + INT_TOP [label=<⊤:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<⊥:int>, fillcolor=lightblue, shape=oval]; + + INT_MIN [label="-n" , fillcolor=lightblue]; + INT_MINDOTS [label="...", fillcolor=lightblue shape=oval]; + INT_MINUS [label="-1" , fillcolor=lightblue]; + INT_ZERO [label="0" , fillcolor=lightblue]; + INT_PLUS [label="1" , fillcolor=lightblue]; + INT_MAXDOTS [label="...", fillcolor=lightblue, shape=oval]; + INT_MAX [label="+n" , fillcolor=lightblue]; + + INT_TOP -> INT_MIN; + INT_TOP -> INT_MINDOTS; + INT_TOP -> INT_MINUS; + INT_TOP -> INT_ZERO; + INT_TOP -> INT_PLUS; + INT_TOP -> INT_MAXDOTS; + INT_TOP -> INT_MAX; + INT_MIN -> INT_BOT; + INT_MINDOTS -> INT_BOT; + INT_MINUS -> INT_BOT; + INT_ZERO -> INT_BOT; + INT_PLUS -> INT_BOT; + INT_MAXDOTS -> INT_BOT; + INT_MAX -> INT_BOT; + + INT_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + // Additional customization + {rank=same; INT_MIN; INT_MINDOTS; INT_MINUS; INT_ZERO; INT_PLUS; INT_MAXDOTS; INT_MAX; } +} diff --git a/chapter02/docs/lattice.svg b/chapter02/docs/lattice.svg new file mode 100644 index 00000000..b11d57aa --- /dev/null +++ b/chapter02/docs/lattice.svg @@ -0,0 +1,159 @@ + + + + + + +Lattice + + + +INT_TOP + +⊤ +:int + + + +INT_MIN + +-n + + + +INT_TOP->INT_MIN + + + + + +INT_MINDOTS + +... + + + +INT_TOP->INT_MINDOTS + + + + + +INT_MINUS + +-1 + + + +INT_TOP->INT_MINUS + + + + + +INT_ZERO + +0 + + + +INT_TOP->INT_ZERO + + + + + +INT_PLUS + +1 + + + +INT_TOP->INT_PLUS + + + + + +INT_MAXDOTS + +... + + + +INT_TOP->INT_MAXDOTS + + + + + +INT_MAX + ++n + + + +INT_TOP->INT_MAX + + + + + +INT_BOT + +⊥ +:int + + + +INT_MIN->INT_BOT + + + + + + +INT_MINDOTS->INT_BOT + + + + + + +INT_MINUS->INT_BOT + + + + + + +INT_ZERO->INT_BOT + + + + + + +INT_PLUS->INT_BOT + + + + + + +INT_MAXDOTS->INT_BOT + + + + + + +INT_MAX->INT_BOT + + + + + -- cgit v1.2.3