From 0caf37adc5f8c1600f13d80aaf77361f407c9694 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Thu, 2 May 2024 22:08:06 +0100 Subject: Documentation updates (#76) * More clearly explain why we do not have an AST in the implementation * Improve the description of type lattice. Cross reference to future chapters. * Minor update * Add lattice visual Revise the text describing meet. * minor update * Add a lattice visual to the text * Update the lattice visual. Add description of the new edges in the SoN graph --- chapter04/README.md | 69 +++++++-------- chapter04/docs/build-graphs.sh | 2 + chapter04/docs/lattice.gv | 63 +++++++++++++ chapter04/docs/lattice.svg | 195 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 293 insertions(+), 36 deletions(-) create mode 100644 chapter04/docs/build-graphs.sh create mode 100644 chapter04/docs/lattice.gv create mode 100644 chapter04/docs/lattice.svg (limited to 'chapter04') diff --git a/chapter04/README.md b/chapter04/README.md index f938f468..4ae4d432 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -19,22 +19,22 @@ Following are revised or new nodes |-----------|----------------|------------------------------------------------|-----------------------|----------------------------------------------------------------------------| | MultiNode | Abstract class | A node that has a tuple result | | A tuple | | Start | Control | Start of function, now a MultiNode | | A tuple with a ctrl token and an `arg` data node | -| Proj | ? | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | +| Proj | Data | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | | Bool | Data | Represents results of a comparison operator | Two data nodes | Result is a comparison, represented as integer value where 1=true, 0=false | | Not | Data | Logical not | One data node | Result converts 0 to 1 and vice versa | Below is our list of Nodes from [Chapter 3](../chapter03/README.md): -| Node Name | Type | Description | Inputs | Value | -|-----------|---------|------------------------------------|------------------------------------------------------------------|------------------------------| -| 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 | -| 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 | -| Minus | Data | Negate a value | One data node, value is negated | Result of the unary minus | -| Scope | ? | Represents scopes in the graph | All nodes that define variables | None | +| Node Name | Type | Description | Inputs | Value | +|-----------|--------------|------------------------------------|------------------------------------------------------------------|------------------------------| +| 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 | +| 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 | +| Minus | Data | Negate a value | One data node, value is negated | Result of the unary minus | +| Scope | Symbol Table | Represents scopes in the graph | All nodes that define variables | None | ## Projection Nodes @@ -51,13 +51,13 @@ Start node. ## Changes to Type System -In [Chapter 2](../chapter02/README.md) we introduced the Type System. Here is a summary of key points: +In [Chapter 2](../chapter02/README.md) we introduced the Type System. We annotate Nodes with Types. The Type annotation serves two purposes: -* it defines the set of operations allowed on the Node, and +* It defines the set of operations allowed on the Node, and * it defines the set of values the Node takes on. The type itself is identified by the Java class sub-typing relationship; all @@ -76,40 +76,37 @@ Type We mentioned in [Chapter 2](../chapter02/README.md) that the set of values associated with a Type at a specific Node can be conveniently represented as a "lattice". -Our lattice elements can be one of three types: +Our enhanced Lattice looks like this. -* the highest element is "top", denoted by T. -* The lowest is bottom, denoted by ⊥, -* All elements in the middle are constants. +![Lattice](./docs/lattice.svg) -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 this chapter we introduce the possibility of a program input variable named -`arg`; this variable is usually unknown so ⊥ . +`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 `Top` and `Bot` integer types in addition to the earlier constant value. +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 +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. -| | ⊥ | Con1 | Con2 | T | -|------|---|------|------|------| -| ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | -| Con1 | ⊥ | Con1 | ⊥ | Con1 | -| T | ⊥ | Con1 | Con2 | T | +| | IntBot | Con1 | Con2 | IntTop | +|--------|--------|--------|--------|--------| +| IntBot | IntBot | IntBot | IntBot | IntBot | +| Con1 | IntBot | Con1 | IntBot | Con1 | +| IntTop | IntBot | Con1 | Con2 | IntTop | +In the table above `Con1` and `Con2` represent two distinct integer values, and serve to explain the rules below. + +* The `meet` of `IntTop` with any integer constant is that constant. +* The `meet` of `IntBot` with any integer value is `IntBot`. +* The `meet` of any integer with itself is that integer. +* The `meet` of two unrelated integer constants is `IntBot`. + +Currently, all our integer valued nodes are either a constant or a `IntBot` integer type. +When we start optimizing loops, we will start seeing `IntTop` values. -The `meet` of `Top` with anything is that thing. -The `meet` of `Bot` with anything is `Bot`. -The `meet` of anything with itself is that thing. -The `meet` of two unrelated constants is `Bot`. -Currently, all our integer valued nodes are either a constant or a Bottom integer type. -When we start optimizing loops, we will start seeing Top values. ## `$ctrl` name binding diff --git a/chapter04/docs/build-graphs.sh b/chapter04/docs/build-graphs.sh new file mode 100644 index 00000000..d8038602 --- /dev/null +++ b/chapter04/docs/build-graphs.sh @@ -0,0 +1,2 @@ +dot -Tsvg lattice.gv > lattice.svg + diff --git a/chapter04/docs/lattice.gv b/chapter04/docs/lattice.gv new file mode 100644 index 00000000..2644448e --- /dev/null +++ b/chapter04/docs/lattice.gv @@ -0,0 +1,63 @@ +digraph Lattice { + // Define nodes + splines=false; + node [shape=circle, style=filled, fillcolor=lightblue]; + nodesep=0.6; + + TOP [label="⊤"]; + BOT [label="⊥"]; + + CTRL [label="Ctrl"]; + + INT_TOP [label="IntTop"]; + INT_BOT [label="IntBot"]; + + 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"]; + + TUPLE [label="TUPLE"]; + + // Define edges + edge [arrowhead=none]; + + TOP -> INT_TOP; + 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_BOT -> BOT; + + INT_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + TOP -> TUPLE; + TUPLE -> BOT; + + TOP -> CTRL; + CTRL -> BOT; + + + // Additional customization + {rank=same; TOP} + {rank=same; INT_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; BOT;} +} \ No newline at end of file diff --git a/chapter04/docs/lattice.svg b/chapter04/docs/lattice.svg new file mode 100644 index 00000000..0d403c20 --- /dev/null +++ b/chapter04/docs/lattice.svg @@ -0,0 +1,195 @@ + + + + + + +Lattice + + + +TOP + +⊤ + + + +CTRL + +Ctrl + + + +TOP->CTRL + + + + +INT_TOP + +IntTop + + + +TOP->INT_TOP + + + + +TUPLE + +TUPLE + + + +TOP->TUPLE + + + + +BOT + +⊥ + + + +CTRL->BOT + + + + +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 + +IntBot + + + +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 + + + + -- cgit v1.2.3