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 --- chapter04/README.md | 41 ++++--- chapter04/docs/lattice.gv | 81 +++++++++----- chapter04/docs/lattice.svg | 260 ++++++++++++++++++++++++++++++++------------- 3 files changed, 270 insertions(+), 112 deletions(-) (limited to 'chapter04') diff --git a/chapter04/README.md b/chapter04/README.md index 299d5da9..1b14bf0a 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -184,11 +184,9 @@ lattice. In this chapter we extend the Type hierarchy as follows: ``` -Type -+-- TypeControl (New - represents control token) -+-- TypeInteger (Enhanced - now has Top and Bottom types) -+-- TypeBot -+-- TypeTuple (New - represents multi-valued result) +Type (Enhanced - now has Control, and a global Top and Bottom) ++-- TypeInteger (Enhanced - now has Top and Bottom types) ++-- TypeTuple (New - represents multi-valued result) ``` Our enhanced Lattice looks like this: @@ -197,14 +195,18 @@ Our enhanced Lattice looks like this: In this chapter we introduce the possibility of a program input variable named -`arg`; all we know about this variable is that it is some integer value, but we do not know whether it is a constant or not. +`arg`; all we know about this variable is that it is some integer value, but we +do not know whether it is a constant or not. -To support the requirements for non-constant integer values, we enhance `TypeInteger` to -allow it to represent `IntTop` and `IntBot` integer types in addition to the earlier constant value. +To support the requirements for non-constant integer values, we enhance +`TypeInteger` to allow it to represent `IntTop` and `IntBot` integer types in +addition to the earlier constant value. -Now that integer values may be constants or non-constants, we need to introduce the "meet" operator -in our lattice. The `meet` operator describes rules that define the resulting type when we combine -integer values. +Now that integer values may be constants or non-constants, we need to introduce +the *meet* operator over our lattice. The `meet` operator describes rules that +define the resulting type when we combine integer values. In the lattice +diagram you can start from the two elements being `meet` and follow the +two arrows down the graph to the first point they meet. | | IntBot | Con1 | Con2 | IntTop | |--------|--------|--------|--------|--------| @@ -223,13 +225,26 @@ Currently, all our integer valued nodes are either a constant or a `IntBot` inte When we start optimizing loops, we will start seeing `IntTop` values. +### Tuple Types + +Tuple types need a little more explaination: they are a fixed-size grouping of +types; literally a `Type[]`. Tuples represent a collection of otherwise +unrelated types, and come from `MultiNode`s. `ProjNode`s will take the +appropriate `Type` array element out of a Tuple. The `StartNode` now produces +a 2-element `TypeTuple` with control and the type of `arg`: `[ctrl, TypeInteger.INTBOT]` + +The lattice `meet` operator on Tuples is done element by element; each array +element recursively calls `meet`. Tuples of mixed sizes are a internal +compiler error, and the `meet` uses Bottom for them. + + ## `$ctrl` name binding In previous chapters, we had a hard coded control input edge from Start to Return. In this chapter we no longer have such a hard-wired edge. Instead, we track the current in-scope control node via the name `$ctrl`. This means that -when we need to create an edge to the predecessor control node, we simply -look up this name in the current scope. +when we need to create an edge to the predecessor control node, we simply look +up this name in the current scope. This introduces the idea that the control flow subgraph is a Petri net model.[^1] The control token moves virtually from node to node as execution proceeds. The diff --git a/chapter04/docs/lattice.gv b/chapter04/docs/lattice.gv index 29a53b0a..6efef107 100644 --- a/chapter04/docs/lattice.gv +++ b/chapter04/docs/lattice.gv @@ -1,29 +1,32 @@ digraph Lattice { + compound = true; // Define nodes splines=false; - node [shape=circle, style=filled, fillcolor=lightblue]; + node [shape=circle, style=filled]; nodesep=0.6; - TOP [label="⊤" , fillcolor=black, fontcolor=white]; - BOT [label="⊥", fillcolor=black, fontcolor=white]; + TOP [label=<⊤>, fillcolor=black, fontcolor=white]; + BOT [label=<⊥>, fillcolor=black, fontcolor=white]; - CTRL [label="Ctrl", fillcolor=yellow]; + // ---------------------- + // Control + CTRL [label="ctrl", fillcolor=yellow, shape=oval]; - INT_TOP [label="⊤ :Int"]; - INT_BOT [label="⊥ :Int"]; - - INT_MIN [label="-n"]; - INT_MINDOTS [label="..." shape=none style=none]; - INT_MINUS [label="-1"]; - INT_ZERO [label="0"]; - INT_PLUS [label="1"]; - INT_MAXDOTS [label="..." shape=none style=none]; - INT_MAX [label="+n"]; + TOP -> CTRL; + CTRL -> BOT; - TUPLE [label="TUPLE", fillcolor=pink]; + // ---------------------- + // Integers + INT_TOP [label=<⊤:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<⊥:int>, fillcolor=lightblue, shape=oval]; - // Define edges - edge [arrowhead=none]; + 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]; TOP -> INT_TOP; INT_TOP -> INT_MIN; @@ -43,22 +46,52 @@ digraph Lattice { INT_BOT -> BOT; INT_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + // ---------------------- + // Tuples - TOP -> TUPLE; - TUPLE -> BOT; + TUPLE_TOP [label=<⊤:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<⊥:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + + + +
tuple
type
+ >]; + TUPLE2 [shape=none, fillcolor=none, label=< + + + + +
tuple
type
type
+ >]; + TUPLEN [shape=none, fillcolor=none, label=< + + + + + +
tuple
type
...
type
+ >]; - TOP -> CTRL; - CTRL -> BOT; + TOP -> TUPLE_TOP; + TUPLE_TOP -> TUPLE1; + TUPLE_TOP -> TUPLE2; + TUPLE_TOP -> TUPLEN; + TUPLE1 -> TUPLE_BOT; + TUPLE2 -> TUPLE_BOT; + TUPLEN -> TUPLE_BOT; + TUPLE_BOT -> BOT; // Additional customization {rank=same; TOP} - {rank=same; INT_TOP} + {rank=same; INT_TOP; TUPLE_TOP} {rank=same; CTRL; INT_MIN; INT_MINDOTS; INT_MINUS; INT_ZERO; INT_PLUS; INT_MAXDOTS; INT_MAX; - TUPLE } - {rank=same; INT_BOT} + {rank=same; INT_BOT, TUPLE_BOT} {rank=same; BOT;} } diff --git a/chapter04/docs/lattice.svg b/chapter04/docs/lattice.svg index 1cab7681..35cb9296 100644 --- a/chapter04/docs/lattice.svg +++ b/chapter04/docs/lattice.svg @@ -4,192 +4,302 @@ - - + + Lattice - + TOP - -⊤ + +⊤ CTRL - -Ctrl + +ctrl - + TOP->CTRL - + + INT_TOP - -⊤ :Int + +⊤ +:int - + TOP->INT_TOP - + + - + -TUPLE - -TUPLE +TUPLE_TOP + +⊤ +:tuple - - -TOP->TUPLE - + + +TOP->TUPLE_TOP + + BOT - -⊥ + +⊥ - + CTRL->BOT - + + INT_MIN - --n + +-n - + INT_TOP->INT_MIN - + + INT_MINDOTS -... + +... - + INT_TOP->INT_MINDOTS - + + INT_MINUS - --1 + +-1 - + INT_TOP->INT_MINUS - + + INT_ZERO - -0 + +0 - + INT_TOP->INT_ZERO - + + INT_PLUS - -1 + +1 - + INT_TOP->INT_PLUS - + + INT_MAXDOTS -... + +... - + INT_TOP->INT_MAXDOTS - + + INT_MAX - -+n + ++n - + INT_TOP->INT_MAX - + + INT_BOT - -⊥ :Int + +⊥ +:int - + INT_BOT->BOT - + + - + 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 - - - - -TUPLE->BOT - + + + + + +TUPLE1 + + + +tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +tuple + + +type + + +... + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥ +:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + +TUPLE2->TUPLE_BOT + + + + + +TUPLEN->TUPLE_BOT + + -- cgit v1.2.3