From 1e2ebb397cbbca1a7d2fd35052c3b90a47bb5733 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 2 Oct 2026 14:27:49 -0700 Subject: README updates thru ch10a --- chapter01/README.md | 69 ++++++----- chapter02/README.md | 46 ++++---- chapter03/README.md | 25 ++-- chapter04/README.md | 24 +--- chapter04/appendix/dce.md | 10 +- chapter05/README.md | 89 +++++++++----- chapter08/README.md | 25 ++-- chapter09/README.md | 97 +++++++-------- chapter10a/README.md | 101 ++++++++++------ chapter10a/docs/Makefile | 15 +-- chapter10a/docs/example1.json | 24 ++++ chapter10a/docs/example1.svg | 195 +++++++++++++++++++------------ chapter10a/docs/example2a.json | 31 +++++ chapter10a/docs/example2a.svg | 232 ++++++++++++++++++++++-------------- chapter10a/docs/example2b.json | 31 +++++ chapter10a/docs/example2b.svg | 222 +++++++++++++++++++++++------------ chapter10a/docs/example2c.json | 22 ++++ chapter10a/docs/example2c.svg | 163 ++++++++++++++++++-------- chapter10a/docs/lattice.gv | 25 +++- chapter10a/docs/lattice.svg | 260 ++++++++++++++++++++++------------------- graph/README.md | 2 +- 21 files changed, 1076 insertions(+), 632 deletions(-) create mode 100644 chapter10a/docs/example1.json create mode 100644 chapter10a/docs/example2a.json create mode 100644 chapter10a/docs/example2b.json create mode 100644 chapter10a/docs/example2c.json diff --git a/chapter01/README.md b/chapter01/README.md index ebe2811e..b0950913 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -47,44 +47,39 @@ If necessary the reader can consult a standard compiler textbook. ## Architecture -We construct the intermediate Sea of Nodes (SoN) representation directly as we parse the language. There is no Abstract Syntax Tree representation. The reason for this is to demonstrate a key benefit of the SoN IR: -a number of pessimistic peephole optimizations can be performed while parsing a language. This aspect is more fully explored from [Chapter 2](../chapter02/README.md) onwards. - -## Data Structures - -Our data structures are based upon the descriptions provided in the following papers: - -* [From Quads to Graphs: An Intermediate Representation's Journey](http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR93366-S.pdf) -* [Combining Analyses, Combining Optimizations](https://dl.acm.org/doi/pdf/10.1145/201059.201061) -* [A Simple Graph-Based Intermediate Representation](https://www.oracle.com/technetwork/java/javase/tech/c2-ir95-150110.pdf) -* [Global Code Motion Global Value Numbering](https://courses.cs.washington.edu/courses/cse501/06wi/reading/click-pldi95.pdf) -* [EasySSA](https://www.dropbox.com/scl/fi/0ww4sgl3ynep9hhe3i4xn/EasySSA.pdf?rlkey=2cp78hzxke62flkmyneiebzoz&dl=0) -* [SeaOfNodes](https://www.dropbox.com/scl/fi/cxykfvlzsmlcatyg6rlbt/SeaOfNodes.pdf?rlkey=z6o7y3rwr6atrejilcze6r8x0&e=1&dl=0) - -Following the lead from above, we represent our intermediate representation using an object oriented data model. Details of the -representation follow. +We construct the intermediate Sea of Nodes (SoN) representation directly as we +parse the language. There is no Abstract Syntax Tree representation. The reason +for this is to demonstrate a key benefit of the SoN IR: a number of pessimistic +peephole optimizations can be performed while parsing a language. This aspect +is more fully explored from [Chapter 2](../chapter02/README.md) onwards, and +eventually leads to a full-fledged program typing without needing any +type-analysis passes. ### Intermediate Representation as a Graph of Nodes The intermediate representation is a graph of Node objects. The `Node` class is the base type for objects in the IR graph. The `Node` class provides common capabilities that are inherited by all subtypes. -Each subtype implements semantics relevant to that subtype. +Subtypes implements semantics relevant to that subtype, e.g. AddNodes add and MulNodes multiply. Each `Node` represents an "instruction" as it may appear in traditional IRs. ### Nodes are in a Graph -The key idea of the Sea of Nodes IR is that each Node is linked to other Nodes by def-use dependencies. -As this is such an important and fundamental aspect of the IR, it is important to understand how we implement this, and depict this in graph visuals. +The key idea of the Sea of Nodes IR is that each Node is linked to other Nodes +by def-use dependencies. As this is such an important and fundamental aspect +of the IR, it is important to understand how we implement this, and depict this +in graph visuals. -The base `Node` class maintains a list of Nodes that are inputs to it. An input is an edge from a "def" to a "use". What this means is that if `B` is a definition, and `A` uses `B`, -then there is a def-use edge from `B` to `A`. +The base `Node` class maintains a list of Nodes that are inputs to it. An +input is an edge from a "use" to a "def". What this means is that if `B` is a +definition, and `A` uses `B`, then `B` has a def->use edge from `B` to `A` and +correspondingly A has an input use->def edge from `A` to `B`. Visually we show an arrow from the "use" to the "def". Here is an example: ![Use Def](./docs/01-use-def.svg) -From an implementation point of view, our `Node` type also maintains a reverse link. +From an implementation point of view, our `Node` type also maintains a both links. This means that in the above scenario: * Since `A` is a "use" of `B`, then `B` will appear in `A`'s list of inputs. @@ -122,7 +117,7 @@ public abstract class Node { There are two categories of Nodes in the intermediate representation. -* **Control Nodes** - these represent the control flow subgraph (CFG) of the compiled program +* **Control Nodes** - these represent the Control Flow Graph (CFG) of the compiled program * **Data Nodes** - these capture the data semantics The following control and data nodes appear in this chapter. @@ -133,9 +128,12 @@ The following control and data nodes appear in this chapter. | Return | Control | Represents the termination of a function | Predecessor control node, Data node value | Return value of the function | | Constant | Data | Represents constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | -Within a traditional basic block, instructions are executed in sequence. In the Sea of Nodes model, the correct sequence of instructions is determined by a scheduling -algorithm that depends only on dependencies between nodes (including control dependencies) that are explicit as edges in the graph. This enables a number of optimizations -at very little cost (nearly always small constant time) because all dependencies are always available. +Within a traditional basic block, instructions are executed in sequence. In the +Sea of Nodes model, the correct sequence of instructions is determined by a +scheduling algorithm that depends only on dependencies between nodes (including +control dependencies) that are explicit as edges in the graph. This enables a +number of optimizations at very little cost (nearly always small constant time) +because all dependencies are always available. ### Unique Node ID @@ -168,7 +166,7 @@ The Constant's value is the value stored in it. The Return node has two inputs. The first input is a control node and the second is the data node that supplies the return value. -In this presentation, Return functions as a Stop node, since multiple `return` statements are not possible. +In this presentation, Return ends the program, since multiple `return` statements are not possible. The Stop node will be introduced in [Chapter 5](../chapter05/README.md) when we implement `if` statements. The Return's output is the value from the data node. @@ -187,3 +185,20 @@ return 1; * Control edges are red and thicker than data edges * The edges from Constants to Start are shown as dashed gray lines as these are not true control edges * We label each edge with its position in the `_inputs` array, thus `0` means the edge is `_inputs[0]`. + + + +## Reading Material + +Our data structures are based upon the descriptions provided in the following papers: + +* [From Quads to Graphs: An Intermediate Representation's Journey](http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR93366-S.pdf) +* [Combining Analyses, Combining Optimizations](https://dl.acm.org/doi/pdf/10.1145/201059.201061) +* [A Simple Graph-Based Intermediate Representation](https://www.oracle.com/technetwork/java/javase/tech/c2-ir95-150110.pdf) +* [Global Code Motion Global Value Numbering](https://courses.cs.washington.edu/courses/cse501/06wi/reading/click-pldi95.pdf) +* [EasySSA](https://www.dropbox.com/scl/fi/0ww4sgl3ynep9hhe3i4xn/EasySSA.pdf?rlkey=2cp78hzxke62flkmyneiebzoz&dl=0) +* [SeaOfNodes](https://www.dropbox.com/scl/fi/cxykfvlzsmlcatyg6rlbt/SeaOfNodes.pdf?rlkey=z6o7y3rwr6atrejilcze6r8x0&e=1&dl=0) + +Following the lead from above, we represent our intermediate representation using an object oriented data model. Details of the +representation follow. + diff --git a/chapter02/README.md b/chapter02/README.md index 9b6d3651..86b7aac0 100644 --- a/chapter02/README.md +++ b/chapter02/README.md @@ -27,15 +27,7 @@ Here is the [complete language grammar](docs/02-grammar.md) for this chapter. ## Extensions to Intermediate Representation -In [Chapter 1](../chapter01/README.md) we introduced the following nodes. - -| Node Name | Type | Description | Inputs | Value | -|-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| -| Start | Control | Start of function | None | None for now as we do not have function arguments yet | -| 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 | - -We extend the set of nodes by adding the following additional node types. +We extend the set of nodes by adding the following additional node types: | Node Name | Type | Description | Inputs | Value | |-----------|------|-------------------------------|------------------------------------------------------------|-----------------------------| @@ -46,15 +38,7 @@ We extend the set of nodes by adding the following additional node types. | Minus | Data | Negate a value | One data node, value is negated | Result of the unary minus | -## *Value* equality vs *Reference* equality - -In much of Simple, Nodes are looked up (`find()` calls) via *reference* -equality. This is by far the most common case. In [Chapter -9](../chapter09/README.md) we introduce *value* equality for the first time. -In both cases the choice of value-vs-reference equality is intentional: it is -*never* correct to "just pick one or the other kind of equality". When in -doubt check the context: only *Global Value Numbering* uses value equality; -everywhere else we mean reference equality. +We keep from [Chapter 1](../chapter01/README.md) the following nodes: Start, Return, Constant. ## Peephole Optimizations @@ -65,7 +49,7 @@ locally rewrite the graph. During parsing, these peephole optimizations are particularly easy to check and apply: there are no uses (yet) of a just-created Node from a just-parsed piece -of syntax, so there's no effort to the "rewrite" part of the problem. We just +of syntax, so there's no effort to the "rewrite" part of the program. We just replace in-place before installing Nodes into the graph. This replacement might allow us to *kill* the unused inputs from the replaced @@ -135,14 +119,14 @@ Our lattice elements can be one of three types: An invariant of peephole optimizations is that the type of a Node always moves *up* the lattice (towards "top"); peepholes are *pessimistic* 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 +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. 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 +`Type`. We need the 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)). @@ -162,10 +146,14 @@ There are other important properties of the Lattice that we discuss in [Chapter The following schematic shows the operations before peephole folding. The parser optimizes each node as it is built; it does not retain this entire intermediate graph: +```java +return 1 + 2 * 3 + -5; +``` + ![Example Visual](./docs/02-pre-peephole-ex1.svg) * Control nodes appear as rectangular boxes with pale yellow backgrounds -* Control edges are red and thicker than data edges +* Control edges are in red * The edges from Constants to Start are shown as dashed gray lines as these are not true control edges * We label each edge with its position in the node's list of inputs. @@ -226,6 +214,7 @@ This can be captured by: ```java // Replace constant computations from non-constants with a constant node if (!(this instanceof ConstantNode) && type.isConstant()) { + .... } ``` Note how we return a constant type when doing constant folding @@ -284,3 +273,16 @@ _type=null; We finally end up with this: ![Example Visual](./docs/02-demonstration-peephole.svg) + + +## Implementation Notes + +### *Value* equality vs *Reference* equality + +In much of Simple, Nodes are looked up (`find()` calls) via *reference* +equality. This is by far the most common case. In [Chapter +9](../chapter09/README.md) we introduce *value* equality for the first time. +In both cases the choice of value-vs-reference equality is intentional: it is +*never* correct to "just pick one or the other kind of equality". When in +doubt check the context: only *Global Value Numbering* uses value equality; +everywhere else we mean reference equality. diff --git a/chapter03/README.md b/chapter03/README.md index 5998efad..ce5901ce 100644 --- a/chapter03/README.md +++ b/chapter03/README.md @@ -31,25 +31,13 @@ Here is the [complete language grammar](docs/03-grammar.md) for this chapter. ## Extensions to Intermediate Representation -To recap, our list of Nodes is: - -| Node Name | Type | Description | Inputs | Value | -|-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| -| Start | Control | Start of function | None | None for now as we do not have function arguments yet | -| 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 | - In this chapter we introduce: | Node Name | Type | Description | Inputs | Value | |-----------|--------------|--------------------------------|---------------------------------|-------| | Scope | Symbol Table | Represents scopes in the graph | All nodes that define variables | None | +and keep all nodes from prior chapters. ## Symbol Tables @@ -69,10 +57,13 @@ the stack of symbol tables, in lexical order. A ScopeNode encapsulates the stack of symbol tables that are used to implement lexical scopes. -* The nodes referenced by the names in a lexical scope become inputs to the ScopeNode; this makes ScopeNode a user of these values, thus keeping them alive while a particular lexical scope is alive. - When the lexical scope ends, those inputs are removed. This is crucial because peepholes will remove dead Nodes and every new Node is effectively dead at the instant of creation without such a reference. +* The nodes referenced by the names in a lexical scope become inputs to the + ScopeNode; this makes ScopeNode a user of these values, thus keeping them + alive while a particular lexical scope is alive. When the lexical scope + ends, those inputs are removed. This is crucial because peepholes will remove + dead Nodes and every new Node is effectively dead at the instant of creation. * In [Chapter 5](../chapter05/README.md) when we implement branches, the ScopeNode gets duplicated at a branch point and then gets merged when the branch joins. This allows - the names to evolve in each branch independently. At the merge point names that have diverged require a Phi node. + the names to evolve in each branch independently. At the merge point, names that have diverged require a Phi node. * In [Chapter 7](../chapter07/README.md) additional logic is deployed for handling Phis from back edges. * The ScopeNode is used to track some other values such as the Control token starting from [Chapter 4](../chapter04/README.md), and whole memory starting from [Chapter 10a](../chapter10a/README.md). Special name bindings are used for these, and each name is tracked across branches and then merged at merge points. @@ -90,7 +81,7 @@ that uses the variable) this is when the expression dies: int a=1; { int b=a*a*a; - } // When this scope closes & ends, b (and the cube of a) dies + } // When this scope closes and ends, b (and the cube of a) dies return a; ``` diff --git a/chapter04/README.md b/chapter04/README.md index e7ae71d2..f9a2dd36 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -49,18 +49,8 @@ Following are revised or new nodes > A `Proj` is a control node when it projects the control slot: `Proj#0` off `Start`. > Every other projection is a data node. See `ProjNode.isCFG()`. -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 | Symbol Table | Represents scopes in the graph | All nodes that define variables | None | +We keep all other nodes from prior chapters. + ## Projection Nodes @@ -267,11 +257,6 @@ 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. -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 -initial control token is in Start, it then moves via the Proj node to Return. -In later chapters we will see how the token moves across branches. - ## More Peephole Optimizations @@ -327,7 +312,7 @@ Here is a list of peepholes introduced in this Chapter, more will be introduced ## Peephole Walkthrough -The peephole optimizations introduced in this chapter are local. They are triggered during parsing +The peephole optimizations introduced in this chapter are all local. They are triggered during parsing as new nodes are created, before the newly created node has any uses. For example, when we parse a unary expression, and create a Node for the parsed expression, @@ -432,6 +417,3 @@ Note the temporary add of a bogus user to the Node `m`. The reason this is done is that we know `m` is the new replacement and is alive, but since it is not yet hooked into the graph, it has no users yet. By adding a bogus user we prevent it being mistaken for dead and being killed. - -[^1]: Click, C. (1995). - Combining Analyses, Combining Optimizations, 131. diff --git a/chapter04/appendix/dce.md b/chapter04/appendix/dce.md index ad5be2d0..1f9dfa7a 100644 --- a/chapter04/appendix/dce.md +++ b/chapter04/appendix/dce.md @@ -4,12 +4,13 @@ Dead Code Elimination is the process or removing nodes that are dead(unused). There are two kinds of dead code eliminations present in this chapter. - Delete unused nodes when popping the scope. -- Delete old nodes after finding a better replacement(after idealize call). +- Delete old nodes after finding a better replacement (after calling `idealize()`). -Both of the methods mentioned above delete the nodes recursively. However, the first case happens -regardless of whether `peephole` is called or not. +Both of the methods mentioned above delete the nodes recursively. However, the +first case happens regardless of whether `peephole` is called or not. ### Delete unused nodes when popping the scope + A node is unused if it has no outputs(users). ### Example 1: @@ -109,11 +110,10 @@ return 1; - We move onto`a = 12`, since "a" has only one user left(the scope) and `this = scope` it can get killed easily. - Same as before, we go through the inputs of "a" and will delete them from the outputs of the control node. -*A constant node pointing to "Start"(ignored by the graph visualizer) but still maintains a connection:* - ![Graph3](../docs/04-dce2.svg) ## Delete old nodes after finding a better replacement + Consider the following code: ``` return (2+1)+3; diff --git a/chapter05/README.md b/chapter05/README.md index f7ff382c..c507df07 100644 --- a/chapter05/README.md +++ b/chapter05/README.md @@ -22,7 +22,8 @@ 15. [Finally](#finally) 16. [Example 2](#example-2) 17. [Example 3](#example-3) -18. [More Examples](#more-examples) +18. [Pushing addition up through a Phi](#pushing-addition-up-through-a-phi) +19. [More Examples](#more-examples) You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter05) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter04...linear-chapter05) it to the previous chapter. @@ -34,30 +35,6 @@ In this chapter we extend the language grammar with the following features: Here is the [complete language grammar](docs/05-grammar.md) for this chapter. -## Recap - -Here is a recap of the nodes introduced in previous chapters: - -| Node Name | Type | Chapter | Description | Inputs | Value | -|-----------|----------------|---------|------------------------------------------------|-------------------------------------------------------------------------------|----------------------------------------------------------------------------| -| Multi | Abstract class | 4 | A node that has a tuple result | | A tuple | -| Start | Control | 1 | Start of function, now a MultiNode | | A tuple with a ctrl token and an `arg` data node | -| Proj | Data / Control | 4 | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | -| Bool | Data | 4 | Represents results of a comparison operator | Two data nodes | Result is a comparison, represented as integer value where 1=true, 0=false | -| Not | Data | 4 | Logical not | One data node | Result converts 0 to 1 and vice versa | -| Return | Control | 1 | End of function | Predecessor control node and a data node for the return value of the function | Return value of the function | -| Constant | Data | 1 | Represents constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | -| Add | Data | 2 | Add two values | Two data nodes without restrictions on the order | Result of the add operation | -| Sub | Data | 2 | Subtract a value from another | Two data nodes, the first one is subtracted by the second one | Result of the subtraction | -| Mul | Data | 2 | Multiply two values | Two data nodes without restrictions on the order | Result of the multiplication | -| Div | Data | 2 | Divide a value by another | Two data nodes, the first one is divided by the second one | Result of the division | -| Minus | Data | 2 | Negate a value | One data node that value is negated | Result of the negation | -| Scope | Symbol Table | 3 | Represents scopes in the graph | Nodes that represent the current value of variables | None | - -> A `Proj` is a control node when it projects a control slot: `Proj#0` off `Start`, -> and both projections off an `If`. Every other projection is a data node. -> See `ProjNode.isCFG()`. - ## New Nodes The following new nodes are introduced in this chapter: @@ -69,6 +46,8 @@ The following new nodes are introduced in this chapter: | Phi | Data | 5 | A phi function picks a value based on control flow | A Region, and data nodes for each control path | Depends on control flow path taken | | Stop | Control | 5 | Termination of the program | All return nodes of the function | None | +and keep all nodes from prior chapters. + #### `IfNode` `If` node takes in both control and data (predicate expression) and routes the @@ -113,7 +92,7 @@ exists in a “sea” of Nodes, with little control structure. The “sea” of Nodes is useful for optimization, but does not represent any traditional intermediate representation such as a CFG. We need a way to serialize the graph and get back the control dependences. We do this with a -simple global code motion algorithm.[^3] +simple Global Code Motion [^3] algorithm in [Chapter 11](../chapter11/README.md). #### `Stop` Nodes `StopNode`s only have `ReturnNode` inputs. They mark the program termination. @@ -174,7 +153,7 @@ At the merge point we merge two ScopeNodes. The goals are: 1) Merge names whose bindings have changed between the two nodes. For each such name, a Phi node is created, referencing the two original data nodes. 2) A new Region node is created representing the merged control flow. The phis have this region node as the first input. -3) After the merge is completed, the duplicate is discarded, and its use of each of the nodes is also deleted. +3) After the merge is completed, the duplicate `ScopeNode` is discarded along with its edges. The merging logic takes advantage of the fact that the two ScopeNodes have the bound nodes in the same order in the list of inputs. This was ensured during duplicating the ScopeNode. Although only the innermost occurrence of a name can have its binding changed, we scan all the nodes in our input list, and simply ignore ones where the binding has not changed. @@ -212,8 +191,11 @@ Below is the graph after we created a `Region` node and merged the two definitio ![Graph2](./docs/05-graph2.svg) The duplicate `ScopeNode` has been discarded and was merged into the other one. -Since `a` had two different definitions in both scopes a `Phi` node was created and is now referenced from `a`. -The `Phi` node's inputs are the `Region` node and the `Add` node from the `True` branch, and `Sub` node from the `False` branch. +Since `a` had two different definitions in both scopes a `Phi` node was created +and is now referenced from `a`. The `Phi` node's inputs are the `Region` node +and the `Add` node from the `True` branch, and `Sub` node from the `False` +branch. The `arg` variable did not get assigned; both scopes agree on the +value so `arg` does not get a `Phi`. ### Finally @@ -326,7 +308,54 @@ Post-peephole: The common operator was pulled out and the Phi node only got applied to the operands. Notice how only the second operand of the `==` changes, the first one stays the same (`arg`). The implementation is in -[`PhiNode.idealize()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java#L31-L71) +[`PhiNode.idealize()`](src/main/java/com/seaofnodes/simple/node/PhiNode.java). + +In graph notation, with `r` denoting the same Region throughout: + +```text +Phi(r, a+b, c+d) -> Phi(r, a, c) + Phi(r, b, d) +``` + +We call this **pulling the operation down** through the Phi: the common +operation moves from the incoming paths to after their merge. Each new Phi +selects the corresponding operand from the same path. If an operand is shared, +as `arg` is above, its Phi collapses to that operand. + + +## Pushing addition up through a Phi + +The opposite direction can expose constant folding. For example: + +```java +int x = 1; +if( arg ) x = 2; +return (arg+x)+3; +``` + +The merge gives `x` a Phi of constants. Although `x` itself is not constant, +adding 3 to each possible value is a compile-time calculation. The addition +peephole reassociates the expression and **pushes the addition up** onto the +incoming paths: + +```text +(arg + Phi(r, 2, 1)) + 3 + -> arg + Phi(r, 2+3, 1+3) + -> arg + Phi(r, 5, 4) +``` + +The implementation first appears here in +[`AddNode.idealize()`](src/main/java/com/seaofnodes/simple/node/AddNode.java), +for the shape `(x + Phi(constants)) + constant`. The final operand can also +be another Phi of constants, but both Phis must use the **same Region** so +their corresponding arms describe the same path. + +Why not push every operation through a Phi? That would duplicate work across +the incoming paths, and the pull-down peephole could immediately undo it. +Repeatedly applying the two rewrites would never finish. Here every new +addition folds to a constant **before** we build the result Phi. There are no +new additions left for that Phi to pull back down, and one runtime addition +has disappeared. The folding requirement supplies both the benefit and the +reason this pair of opposing rewrites terminates. ## More examples diff --git a/chapter08/README.md b/chapter08/README.md index 46e4eeca..f412fd36 100644 --- a/chapter08/README.md +++ b/chapter08/README.md @@ -131,12 +131,10 @@ We have several ways of implementing these backedges. Phis that are stacked. In this chapter we adopt option 3 as it is the simplest implementation on top -of our basic `while` loop architecture. We also experimented with -option 2. For readers who would like to see this alternative solution, we -provide a separate branch with such an implementation. +of our basic `while` loop architecture.[^1] The implementation requires some careful handling of scopes. This is because -we would like to only generate `PhiNode/RegionNode`s for continues if necessary. +we would like to only generate `PhiNode/RegionNode`s for `continues` if necessary. In our [basic loop architecture](../chapter07/README.md), by the time we get to the loop backedge, we have already exited all nested blocks/scopes, we just @@ -299,9 +297,16 @@ while(arg < 10) { return t; ``` -In this code, the two statements within the loop may be evaluated in either order by the graph, so we must ensure that the new value `arg` is not cached before the value of `t` can be set to the previous value of `arg`. +In this code, the two statements within the loop may be evaluated in either +order by the graph, so we must ensure that the new value `arg` is not cached +before the value of `t` can be set to the previous value of `arg`. -This approach to evaluation is useful for testing because it allows a program to be executed without worrying about instruction selection, register allocation or code generation. It executes the graph produced with normal peephole optimization. In later chapters, the evaluator can compare graphs optimized with different worklist orders to detect inconsistent results. This chapter's fuzzer checks generated programs for compiler and evaluator failures. +This approach to evaluation is useful for testing because it allows a program +to be executed without worrying about instruction selection, register +allocation or code generation. It executes the graph produced with normal +peephole optimization. In later chapters, the evaluator can compare graphs +optimized with different worklist orders to detect inconsistent results. This +chapter's fuzzer checks generated programs for compiler and evaluator failures. ``` java arg=arg+arg; @@ -311,4 +316,10 @@ arg=arg+arg; return arg; ``` -On the other hand, this engine is not designed to be particularly fast! Because not all expressions are cached, it's possible to construct programs like the preceding one which have exponential runtime. +On the other hand, this engine is not designed to be particularly fast! Because +not all expressions are cached, it's possible to construct programs like the +preceding one which have exponential runtime. + + +[^1]: We also experimented with option 2. For readers who would like to see this +alternative solution, we provide a separate branch with such an implementation. \ No newline at end of file diff --git a/chapter09/README.md b/chapter09/README.md index 2a9abe4e..9c9eba07 100644 --- a/chapter09/README.md +++ b/chapter09/README.md @@ -182,54 +182,6 @@ Changes: dependents onto the worklist. -## Other Concerns - -There are more issues we will want to deal with in a later Chapter: - -* Blindly running peepholes in any order has some drawbacks: - - - Dead and dying stuff might get peepholes done... and then die. Wasted work. - - Dead infinite loops often lead to infinite peephole cycles... if only we - would get around to working on the "base" of the dead loop it would fold - up. - - Some peepholes naturally reduce the graph directly; while some keep its - size the same but reduce other things (e.g. swapping a Mul-by-2 with a - Shift), and we might end up with a few which try to grow the graph briefly - before collapsing. - -* All this means is there's some benefit to running peepholes that reduce the - graph directly (e.g. Dead Code Eliminate), before running peeps that reduce - other things, before running all other peeps. This implies a sorted - worklist, but the count of unique orders is really limited - a radix sort is - all that is needed. We'll have to break up the peepholes into some - categories like - - "strictly reducing" vs - - "same Nodes but swapping e.g. `Mul` for `Shift`, vs - - getting more freedom (edge bypass), vs - - "grow now because shrink later" (inlining lands in this camp). - -* Also there's a benefit to not always grabbing from either end of the list - - many peep patterns might go quadratic if approached from one end or another, - because they modify something then push it back onto the list where it - immediately gets pulled again. I.e., you end up spinning in a loop repeating - the same peeps while slowly migrating e.g. left-spine add-tree into a - right-spine add-tree. A pseudo-random pull uses randomization to defeat bad - peep patterns. - -* Why isn't `IterPeeps` just passing over all of the Nodes once or twice, - instead of using a worklist with the `addDeps` mechanism? We could even - visit them in a defs-before-uses order (e.g. Reverse Post Order). - - In the absence of loops exactly one such pass will find all local peepholes, - and indeed the Parser already does this. However, this will fail to find - opportunities at loops and farther remote cases - and to get those peepholes - around loops will require another visit. It is easy to construct a case - requiring O(N) passes, each of cost O(N) and the algorithm quickly goes - quadratic. - - The `addDeps` solution avoids this quadratic cost, in exchange for some more - costs in writing peepholes. - # Examples @@ -299,3 +251,52 @@ Enabling the post parse worklist based optimization yields below. Notice that no loop body: ![Graph6](./docs/09-graph6.svg) + + +## Future Work + +There are more issues we will want to deal with in a later Chapter: + +* Blindly running peepholes in any order has some drawbacks: + + - Dead and dying stuff might get peepholes done... and then die. Wasted work. + - Dead infinite loops often lead to infinite peephole cycles... if only we + would get around to working on the "base" of the dead loop it would fold + up. + - Some peepholes naturally reduce the graph directly; while some keep its + size the same but reduce other things (e.g. swapping a Mul-by-2 with a + Shift), and we might end up with a few which try to grow the graph briefly + before collapsing. + +* All this means is there's some benefit to running peepholes that reduce the + graph directly (e.g. Dead Code Eliminate), before running peeps that reduce + other things, before running all other peeps. This implies a sorted + worklist, but the count of unique orders is really limited - a radix sort is + all that is needed. We'll have to break up the peepholes into some + categories like + - "strictly reducing" vs + - "same Nodes but swapping e.g. `Mul` for `Shift`, vs + - getting more freedom (edge bypass), vs + - "grow now because shrink later" (inlining lands in this camp). + +* Also there's a benefit to not always grabbing from either end of the list - + many peep patterns might go quadratic if approached from one end or another, + because they modify something then push it back onto the list where it + immediately gets pulled again. I.e., you end up spinning in a loop repeating + the same peeps while slowly migrating e.g. left-spine add-tree into a + right-spine add-tree. A pseudo-random pull uses randomization to defeat bad + peep patterns. + +* Why isn't `IterPeeps` just passing over all of the Nodes once or twice, + instead of using a worklist with the `addDeps` mechanism? We could even + visit them in a defs-before-uses order (e.g. Reverse Post Order). + + In the absence of loops exactly one such pass will find all local peepholes, + and indeed the Parser already does this. However, this will fail to find + opportunities at loops and farther remote cases - and to get those peepholes + around loops will require another visit. It is easy to construct a case + requiring O(N) passes, each of cost O(N) and the algorithm quickly goes + quadratic. + + The `addDeps` solution avoids this quadratic cost, in exchange for some more + costs in writing peepholes. diff --git a/chapter10a/README.md b/chapter10a/README.md index b9ea258a..6f51df28 100644 --- a/chapter10a/README.md +++ b/chapter10a/README.md @@ -31,6 +31,9 @@ different fields are independent. Chapter 10b will remove it. ![One chain orders stores and loads](docs/example1.svg) +The graphs show dependencies before local folding. Definitions appear above +their uses, except for loop backedges; arrows point from use to definition. + | Node | Inputs | Result | |----------|---|---| | `New` | Control and a struct type | A fresh, non-null object pointer | @@ -86,41 +89,6 @@ Every Return consumes the current whole-memory value. This keeps stores alive even when the returned scalar does not depend on them, or when the program returns the modified object itself. -## Local memory optimizations - -A load immediately following a store to the **same pointer and field** can use -the stored value. A store immediately following another store to the same -address can discard the earlier store when no other user needs it. Both the -pointer and field checks matter: two different fields of one object are -different addresses, as are the same fields of two different objects. - -A load can also move through a memory Phi when doing so exposes a useful -load-after-store fold. On a loop, the backedge must fold, preventing this rewrite -from repeatedly moving the load around the cycle. - -The reverse direction can save an operation: a Phi of matching Loads or Stores -can become one operation after the join. For example, these two writes: - -```java -if (arg) s.x = arg+1; -else s.x = arg+2; -``` - -can become `s.x = Phi(arg+1,arg+2)`. The general rewrite creates a separate, -correctly typed Phi for each differing operand, including memory and pointers; -identical operands need no Phi. An exact-class copy preserves the operation's -attributes. The proposed result must not widen the original Phi's type. - -Every arm must match the operation and field and have no control input. A Store -must have no other users, so moving it removes the original effect. A Load must -have no possible conflicting write or memory merge among its memory's users; -otherwise delaying the read could change its value. The check happens during -optimization, before any scheduler can supply explicit anti-dependency edges. - -The single chain is conservative. A store to `y` can prevent forwarding an -earlier store to `x`, even when the objects are identical. This is a missed -optimization, not a correctness problem; it motivates the next chapter. - ## Enhanced Type Lattice The Type Lattice for Simple has a major revision in this chapter. @@ -182,8 +150,9 @@ Within the type lattice, we now have the following domains: Memory top and memory bottom are `TypeMem.TOP` and `TypeMem.BOT`. Neither records the values stored in individual fields. * ![Tuple](docs/type-tuple.svg) represents a collection of results from one node, - such as Start's control, memory, and argument. The displayed shapes abbreviate - tuples of different lengths and their element-type lattices. + such as Start's control, memory, and argument. The pink headers identify tuples + of different lengths; each vertically stacked black `type` cell stands for + the full type lattice again, including the possibility of another tuple. We use the following operations on the lattice: @@ -299,6 +268,59 @@ To enable this behaviour, we make the following enhancements. ptr value, we convert to `0`. See `NotNode.compute()`. +## Local memory optimizations + +A load immediately following a store to the **same pointer and field** can use +the stored value. A store immediately following another store to the same +address can discard the earlier store when no other user needs it. Both the +pointer and field checks matter: two different fields of one object are +different addresses, as are the same fields of two different objects. + +A load can also move up through a memory Phi. This extends +[Chapter 5's push-through-Phi optimization](../chapter05/README.md#pushing-addition-up-through-a-phi): +there, arithmetic folds on the incoming paths; here, a load can fold against +a matching store. In graph notation, keeping the same pointer and field: + +```text +Load(Phi(r, m0, m1), p.x) + -> Phi(r, Load(m0, p.x), Load(m1, p.x)) +``` + +The Phi of memory becomes a Phi of loaded values. This chapter handles two +incoming paths and requires a load-after-store fold on at least one of them. +On a loop, that path must be the **backedge**: folding only on entry would +leave a load that could be pushed around the cycle indefinitely. As with the +arithmetic rewrite, exposing a fold is part of deciding to transform the +graph, not just a hoped-for cleanup afterward. See +[`LoadNode.idealize()`](src/main/java/com/seaofnodes/simple/node/LoadNode.java). + +The reverse direction extends +[Chapter 5's common-operation pull-down](../chapter05/README.md#example-3): +a Phi of matching Loads or Stores can become one operation after the join. +For example, these two writes: + +```java +if (arg) s.x = arg+1; +else s.x = arg+2; +``` + +can become `s.x = Phi(arg+1,arg+2)`. The general rewrite creates a separate, +correctly typed Phi for each differing operand, including memory and pointers. +We must be more careful here with memory ops; it is possible to lose some +type precision, so we check for that as part of the profitability. + +Also, a Store must have no other users, so moving it removes the original +effect. A Load must have no possible conflicting writes or memory merges among +its memory's users; otherwise delaying the read could change its value. Much +later, we will be adding anti-dependences, but for now we do a conservative +check. + +### Missing an easy one + +The single memory chain is correct but conservative. A store to `y` can +prevent forwarding an earlier store to `x`, even when the objects are +identical. This is a missed optimization and it motivates the next chapter. + ## Executing the graph The evaluator includes a small late scheduler. A load must execute before a @@ -306,6 +328,11 @@ later store that consumes the same memory definition, even though there is no ordinary data edge from the load to that store. These load/store anti-dependencies supplement the explicit graph edges. +For example, after allocating `p`, `int old = p.x; p.x = arg; return old;` +reads the value before the final store. In the graph below, Load and Store +consume the same memory state. The scheduler must execute the Load first; +there is no ordinary data edge between them. + ![A load must precede a clobbering store](docs/example2c.svg) The scheduler is sufficient to execute this chapter. Chapter 11 develops diff --git a/chapter10a/docs/Makefile b/chapter10a/docs/Makefile index 055882b2..6fa0f057 100644 --- a/chapter10a/docs/Makefile +++ b/chapter10a/docs/Makefile @@ -1,14 +1 @@ -GV := $(wildcard *.gv) -SVG := $(patsubst %.gv,%.svg,$(GV)) -.DELETE_ON_ERROR: - -.PHONY: all -all: $(SVG) - -%.svg: %.gv - dot -Tsvg $< > $@ - @sed -i 's/\r$$//' $@ - -.PHONY: clean -clean: - @rm -f $(SVG) +include ../../graph/docs.mk diff --git a/chapter10a/docs/example1.json b/chapter10a/docs/example1.json new file mode 100644 index 00000000..1b556c04 --- /dev/null +++ b/chapter10a/docs/example1.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter10a/docs/example1.svg", + "step": 1, + "roots": [13], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}], "proj": {"par": 1, "idx": 0}}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 10, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "MEM", "label": null}, {"idx": 2, "def": 12, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10a/docs/example1.svg b/chapter10a/docs/example1.svg index fdb4864c..b50701b0 100644 --- a/chapter10a/docs/example1.svg +++ b/chapter10a/docs/example1.svg @@ -1,73 +1,122 @@ - - - - - - -Memory - - - -M0 - -Initial memory - - - -X - -Store p.x = 3 - - - -X->M0 - - - - - -Y - -Store p.y = arg - - - -Y->X - - - - - -L - -Load p.x - - - -L->Y - - - - - -Return - -Return - - - -Return->Y - - - - - -Return->L - - - - - +#5[0] → #2 · CTRL#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[0] → #1 · ASSOC#10[1] → #8 · MEM#10[2] → #5 · DATA#10[3] → #9 · DATA#11[1] → #10 · MEM#11[2] → #5 · DATA#11[3] → #4 · DATA#12[1] → #11 · MEM#12[2] → #5 · DATA#13[0] → #2 · CTRL#13[1] → #11 · MEM#13[2] → #12 · DATAStart  #1#1 Start +Type not computed + +$ctrl  #2/0#2 $ctrl +Projection 0 of #1 +Type not computed + +[0] → #1 CTRL$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → #2 CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123#3  #9#9 #3 +Type not computed + +[0] → #1 ASSOC0Store p.x  #10#10 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #9 DATA0123Store p.y  #11#11 Store p.y +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → #4 DATA0123Load p.x  #12#12 Load p.x +Type not computed + +[0] → — CTRL +[1] → #11 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #13#13 Return +Type not computed + +[0] → #2 CTRL +[1] → #11 MEM +[2] → #12 DATA012 diff --git a/chapter10a/docs/example2a.json b/chapter10a/docs/example2a.json new file mode 100644 index 00000000..2fa04643 --- /dev/null +++ b/chapter10a/docs/example2a.json @@ -0,0 +1,31 @@ +{ + "ver": 1, + "comp": "chapter10a/docs/example2a.svg", + "step": 1, + "roots": [19], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}], "proj": {"par": 1, "idx": 0}}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 0}}, + {"id": 11, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 1}}, + {"id": 12, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 13, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 12, "role": "DATA", "label": null}], "proj": null}, + {"id": 14, "label": "#4", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 15, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 14, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "CTRL", "label": null}, {"idx": 2, "def": 11, "role": "CTRL", "label": null}], "proj": null}, + {"id": 17, "label": "Phi $mem", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 16, "role": "ASSOC", "label": null}, {"idx": 1, "def": 13, "role": "MEM", "label": null}, {"idx": 2, "def": 15, "role": "MEM", "label": null}], "proj": null}, + {"id": 18, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "MEM", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 9, "par": 0, "nodes": [7, 8, 9, 10, 11, 13, 15, 16, 17]} + ] +} diff --git a/chapter10a/docs/example2a.svg b/chapter10a/docs/example2a.svg index f0bbf531..eb43548f 100644 --- a/chapter10a/docs/example2a.svg +++ b/chapter10a/docs/example2a.svg @@ -1,85 +1,147 @@ - - - - - - -Memory - - - -M - -Incoming memory - - - -A - -True: Store x - - - -A->M - - - - - -B - -False: Store x - - - -B->M - - - - - -P - -Phi(memory) - - - -P->A - - - - - -P->B - - - - - -Region - -Region - - - -P->Region - - - - - -Return - -Return - - - -Return->P - - - - - +#5[0] → #2 · CTRL#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[0] → #2 · CTRL#9[1] → #4 · DATA#12[0] → #1 · ASSOC#13[1] → #8 · MEM#13[2] → #5 · DATA#13[3] → #12 · DATA#14[0] → #1 · ASSOC#15[1] → #8 · MEM#15[2] → #5 · DATA#15[3] → #14 · DATA#16[1] → #10 · CTRL#16[2] → #11 · CTRL#17[1] → #13 · MEM#17[2] → #15 · MEM#18[1] → #17 · MEM#18[2] → #5 · DATA#19[0] → #16 · CTRL#19[1] → #17 · MEM#19[2] → #18 · DATAStart  #1#1 Start +Type not computed + +$ctrl  #2/0#2 $ctrl +Projection 0 of #1 +Type not computed + +[0] → #1 CTRL$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → #2 CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123If  #9#9 If +Type not computed + +[0] → #2 CTRL +[1] → #4 DATA01True  #10/0#10 True +Projection 0 of #9 +Type not computed + +[0] → #9 CTRLFalse  #11/1#11 False +Projection 1 of #9 +Type not computed + +[0] → #9 CTRL#3  #12#12 #3 +Type not computed + +[0] → #1 ASSOC0Store p.x  #13#13 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #12 DATA0123#4  #14#14 #4 +Type not computed + +[0] → #1 ASSOC0Store p.x  #15#15 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #14 DATA0123Region  #16#16 Region +Type not computed + +[0] → — ASSOC +[1] → #10 CTRL +[2] → #11 CTRL012Phi $mem  #17#17 Phi $mem +Type not computed + +[0] → #16 ASSOC +[1] → #13 MEM +[2] → #15 MEM[0] → #16012Load p.x  #18#18 Load p.x +Type not computed + +[0] → — CTRL +[1] → #17 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #19#19 Return +Type not computed + +[0] → #16 CTRL +[1] → #17 MEM +[2] → #18 DATA012If  #9If · 9 nodes−Fold region diff --git a/chapter10a/docs/example2b.json b/chapter10a/docs/example2b.json new file mode 100644 index 00000000..50fbfc74 --- /dev/null +++ b/chapter10a/docs/example2b.json @@ -0,0 +1,31 @@ +{ + "ver": 1, + "comp": "chapter10a/docs/example2b.svg", + "step": 1, + "roots": [19], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}], "proj": {"par": 1, "idx": 0}}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 2, "role": "CTRL", "label": null}, {"idx": 2, "def": 13, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": "Phi $mem", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 9, "role": "ASSOC", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 15, "role": "MEM", "label": null}], "proj": null}, + {"id": 11, "label": "Phi arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 9, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}], "proj": {"par": 12, "idx": 0}}, + {"id": 14, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}], "proj": {"par": 12, "idx": 1}}, + {"id": 15, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 17, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 18, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 14, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 9, "par": 0, "nodes": [7, 8, 9, 10, 11, 12, 13, 14, 15, 17]} + ] +} diff --git a/chapter10a/docs/example2b.svg b/chapter10a/docs/example2b.svg index 77ebec85..e5322a61 100644 --- a/chapter10a/docs/example2b.svg +++ b/chapter10a/docs/example2b.svg @@ -1,74 +1,148 @@ - - - - - - -Memory - - - -P - -Phi(memory) - - - -S - -Loop-body Store - - - -P->S - - - - - -Entry - -Entry - - - -P->Entry - - - - - -Loop - -Loop - - - -P->Loop - - - - - -S->P - - - - - -Return - -Return - - - -Return->P - - - - - - +#5[0] → #2 · CTRL#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[1] → #2 · CTRL#9[2] → #13 · CTRL#10[1] → #8 · MEM#10[2] → #15 · MEM#11[1] → #4 · DATA#11[2] → #17 · DATA#12[0] → #9 · CTRL#12[1] → #11 · DATA#15[1] → #10 · MEM#15[2] → #5 · DATA#15[3] → #11 · DATA#16[0] → #1 · ASSOC#17[1] → #11 · DATA#17[2] → #16 · DATA#18[1] → #10 · MEM#18[2] → #5 · DATA#19[0] → #14 · CTRL#19[1] → #10 · MEM#19[2] → #18 · DATAStart  #1#1 Start +Type not computed + +$ctrl  #2/0#2 $ctrl +Projection 0 of #1 +Type not computed + +[0] → #1 CTRL$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → #2 CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123Loop  #9#9 Loop +Type not computed + +[0] → — ASSOC +[1] → #2 CTRL +[2] → #13 CTRL012Phi $mem  #10#10 Phi $mem +Type not computed + +[0] → #9 ASSOC +[1] → #8 MEM +[2] → #15 MEM[0] → #9012Phi arg  #11#11 Phi arg +Type not computed + +[0] → #9 ASSOC +[1] → #4 DATA +[2] → #17 DATA[0] → #9012If  #12#12 If +Type not computed + +[0] → #9 CTRL +[1] → #11 DATA01True  #13/0#13 True +Projection 0 of #12 +Type not computed + +[0] → #12 CTRLFalse  #14/1#14 False +Projection 1 of #12 +Type not computed + +[0] → #12 CTRLStore p.x  #15#15 Store p.x +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → #11 DATA0123#1  #16#16 #1 +Type not computed + +[0] → #1 ASSOC0-  #17#17 - +Type not computed + +[0] → — CTRL +[1] → #11 DATA +[2] → #16 DATA012Load p.x  #18#18 Load p.x +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #19#19 Return +Type not computed + +[0] → #14 CTRL +[1] → #10 MEM +[2] → #18 DATA012Loop  #9Loop · 10 nodes−Fold region diff --git a/chapter10a/docs/example2c.json b/chapter10a/docs/example2c.json new file mode 100644 index 00000000..4e7e096b --- /dev/null +++ b/chapter10a/docs/example2c.json @@ -0,0 +1,22 @@ +{ + "ver": 1, + "comp": "chapter10a/docs/example2c.svg", + "step": 1, + "roots": [11], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}], "proj": {"par": 1, "idx": 0}}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10a/docs/example2c.svg b/chapter10a/docs/example2c.svg index 2aa8fa2d..eb8fad03 100644 --- a/chapter10a/docs/example2c.svg +++ b/chapter10a/docs/example2c.svg @@ -1,50 +1,113 @@ - - - - - - -Memory - - - -M - -Prior memory - - - -L - -Load p.x - - - -L->M - - - - - -S - -Store p.x - - - -S->M - - - - - -S->L - - -execute load first - - - +#5[0] → #2 · CTRL#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[1] → #8 · MEM#9[2] → #5 · DATA#10[1] → #8 · MEM#10[2] → #5 · DATA#10[3] → #4 · DATA#11[0] → #2 · CTRL#11[1] → #10 · MEM#11[2] → #9 · DATAStart  #1#1 Start +Type not computed + +$ctrl  #2/0#2 $ctrl +Projection 0 of #1 +Type not computed + +[0] → #1 CTRL$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → #2 CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123Load p.x  #9#9 Load p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → — DATA0123Store p.x  #10#10 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #4 DATA0123Return  #11#11 Return +Type not computed + +[0] → #2 CTRL +[1] → #10 MEM +[2] → #9 DATA012 diff --git a/chapter10a/docs/lattice.gv b/chapter10a/docs/lattice.gv index eb4d7fb1..b56a3073 100644 --- a/chapter10a/docs/lattice.gv +++ b/chapter10a/docs/lattice.gv @@ -91,9 +91,28 @@ digraph Lattice { node [fillcolor="#ffc0cb"]; TUPLE_TOP [label="⊤:tuple"]; TUPLE_BOT [label="⊥:tuple"]; - TUPLE1 [label="(type)", shape=box]; - TUPLE2 [label="(type, type)", shape=box]; - TUPLEN [label="(type, …)", shape=box]; + // Each black element stands for a recursively nested type lattice. + TUPLE1 [shape=plain, label=< + + + +
tuple
type
+ >]; + TUPLE2 [shape=plain, label=< + + + + +
tuple
type
type
+ >]; + TUPLEN [shape=plain, label=< + + + + + +
tuple
type
…
type
+ >]; {rank=same; TUPLE1; TUPLE2; TUPLEN;} TUPLE1 -> TUPLE2 -> TUPLEN [style=invis]; TUPLE_TOP -> {TUPLE1 TUPLE2 TUPLEN}; diff --git a/chapter10a/docs/lattice.svg b/chapter10a/docs/lattice.svg index c8bed535..006ab762 100644 --- a/chapter10a/docs/lattice.svg +++ b/chapter10a/docs/lattice.svg @@ -4,122 +4,122 @@ - - + + Lattice - + cluster_control - -Control + +Control cluster_integer - -Integer + +Integer cluster_pointer - -Pointer = nullability × struct type + +Pointer = nullability × struct type cluster_struct - -Struct -named collection of named scalar types + +Struct +named collection of named scalar types cluster_memory - -Memory + +Memory cluster_tuple - -Tuple -collection of types + +Tuple +collection of types TOP - -⊤ + +⊤ XCTRL - -⊤:ctrl + +⊤:ctrl TOP->XCTRL - - + + INT_TOP - -⊤:int + +⊤:int TOP->INT_TOP - - + + PTR_TOP - -⊤:ptr -[*⊤:struct] + +⊤:ptr +[*⊤:struct] TOP->PTR_TOP - - + + STRUCT_TOP - -⊤:struct -[struct top] + +⊤:struct +[struct top] TOP->STRUCT_TOP - - + + MEM_TOP - -⊤:mem + +⊤:mem TOP->MEM_TOP - - + + TUPLE_TOP - -⊤:tuple + +⊤:tuple TOP->TUPLE_TOP - - + + @@ -136,7 +136,7 @@ XCTRL->CTRL - + @@ -155,8 +155,8 @@ INT_TOP->INT_NEG - - + + @@ -167,8 +167,8 @@ INT_TOP->INT_ZERO - - + + @@ -179,8 +179,8 @@ INT_TOP->INT_POS - - + + @@ -218,50 +218,50 @@ PTR_NULL - -null + +null PTR_TOP->PTR_NULL - - + + PTR_PERSON - -*Person + +*Person PTR_TOP->PTR_PERSON - - + + PTR_S1 - -*s1 + +*s1 PTR_TOP->PTR_S1 - - + + PTR_MORE - -*s2, … + +*s2, … PTR_TOP->PTR_MORE - - + + @@ -286,8 +286,8 @@ PTR_NULL->PTR_PERSON_NIL - - + + @@ -298,8 +298,8 @@ PTR_NULL->PTR_S1_NIL - - + + @@ -310,8 +310,8 @@ PTR_NULL->PTR_MORE_NIL - - + + @@ -330,41 +330,41 @@ PTR_PERSON->PTR_ANY - - + + PTR_PERSON->PTR_PERSON_NIL - - + + PTR_S1->PTR_ANY - - + + PTR_S1->PTR_S1_NIL - - + + PTR_MORE->PTR_ANY - - + + PTR_MORE->PTR_MORE_NIL - - + + @@ -396,8 +396,8 @@ STRUCT_TOP->STRUCT_PERSON - - + + @@ -409,8 +409,8 @@ STRUCT_TOP->STRUCT_S1 - - + + @@ -422,8 +422,8 @@ STRUCT_TOP->STRUCT_S2 - - + + @@ -434,8 +434,8 @@ STRUCT_TOP->STRUCT_MORE - - + + @@ -487,7 +487,7 @@ MEM_TOP->MEM_BOT - + @@ -500,70 +500,94 @@ TUPLE1 - -(type) + + + +tuple + + +type TUPLE_TOP->TUPLE1 - - + + TUPLE2 - -(type, type) + + + +tuple + + +type + + +type TUPLE_TOP->TUPLE2 - - + + TUPLEN - -(type, …) + + + +tuple + + +type + + +… + + +type TUPLE_TOP->TUPLEN - - + + TUPLE_BOT - -⊥:tuple + +⊥:tuple TUPLE_BOT->BOT - - + + TUPLE1->TUPLE_BOT - - + + TUPLE2->TUPLE_BOT - - + + TUPLEN->TUPLE_BOT - - + + diff --git a/graph/README.md b/graph/README.md index 915746e9..7479aaf9 100644 --- a/graph/README.md +++ b/graph/README.md @@ -143,7 +143,7 @@ The chapter `docs/Makefile` rules select JSON before a same-named legacy DOT file. They accept `PYTHON` and `DOC_BROWSER` overrides, for example `make -C chapter01/docs PYTHON=python DOC_BROWSER=msedge` from the repository root. -The compact memory-dependency schematics in 10a/10b retain `.gv` sources to +The compact memory-dependency schematics in 10b retain `.gv` sources to preserve their deliberate horizontal layouts. They use the viewer palette and node shapes; definitions are left of uses horizontally and above uses vertically, with arrows from use to definition. Type lattices use their own domain colors -- cgit v1.2.3