diff options
Diffstat (limited to 'chapter10a/README.md')
| -rw-r--r-- | chapter10a/README.md | 183 |
1 files changed, 100 insertions, 83 deletions
diff --git a/chapter10a/README.md b/chapter10a/README.md index 64600fa0..2f25f681 100644 --- a/chapter10a/README.md +++ b/chapter10a/README.md @@ -10,10 +10,11 @@ same in 10a and 10b; the next chapter improves the memory representation. ## One memory value -Arithmetic nodes depend on the values they use. A load also depends on when it -observes memory. In this chapter every store consumes the preceding memory -state and produces the next one. A load consumes memory without changing it. -This makes the source program's effect ordering explicit in the graph. +Arithmetic nodes depend on the values they use, similarly a load also depends +on when it observes memory. In this chapter every store consumes the preceding +memory state and produces the next one, and a load consumes memory without +changing it. This makes the source program's memory ordering explicit in the +graph. ```java struct Point { int x; int y; } @@ -30,27 +31,23 @@ different fields are independent. Chapter 10b will remove it.  -These diagrams are schematic dependency graphs: arrows run from uses to their -definitions. Pointer and value inputs are omitted where they do not explain ordering. - -| Node | Inputs | Result | -|---|---|---| -| `New` | Control and a struct type | A fresh, non-null object pointer | -| `Store` | Memory, pointer, field name, value | The updated whole-memory state | -| `Load` | Memory, pointer, field name | The value of the field | -| `Start` | External entry | Control, initial memory, and `arg` | +| Node | Inputs | Result | +|----------|---|---| +| `New` | Control and a struct type | A fresh, non-null object pointer | +| `Store` | Memory, pointer, field name, value | The updated whole-memory state | +| `Load` | Memory, pointer, field name | The value of the field | +| `Start` | External entry | Control, initial memory, and `arg` | | `Return` | Control, result, memory | Completion with all preceding effects retained | -The memory edge is a dependency token, not a copy of the heap. In the evaluator, -objects contain mutable field arrays; executing a Store changes an array entry. -The graph determines the legal execution order. +The memory edge is a dependency, not a copy of the heap. The graph determines +the legal execution order. In hardware, a Store updates physical memory +directly. In the evaluator, a Store updates an objects' attached memory array. ## Memory is an SSA variable The parser keeps one hidden binding named `$mem`. Source identifiers cannot contain `$`, so user code cannot name it. Reading and updating memory uses the -same `ScopeNode` lookup and update operations as a local variable. Start has a -fixed tuple: control at index 0, memory at index 1, and `arg` at index 2. +same `ScopeNode` lookup and update operations as a local variable. For an `if`, the two branches can finish with different memory values. An ordinary Phi selects the memory from the branch that executed: @@ -88,69 +85,88 @@ optimization, not a correctness problem; it motivates the next chapter. The Type Lattice for Simple has a major revision in this chapter. - - -Within the Type Lattice, we now have the following type domains: - -* <font style="background-color:yellow">Control type</font> - represents control flow -* <font style="background-color:lightblue">Integer type</font> - Integer values, with a Top, Bottom and constants -* <font style="background-color:green" color="white">Pointer type</font> (new) - Represents a pointer to a struct type - * We use the prefix `*` to mean pointer-to. Thus `*S1` means pointer to - `S1`, `*$TOP` means pointer to `$TOP`. - * `?` suffix represents the union of a pointer to some type and `null`. - * The pointer lattice has only 2 entries: null or not-null. In both cases a struct lattice element is - included, and can be any member of the struct lattice. - * `null` is a pointer to non-existent memory object, i.e. `*$TOP?`, and is a - nullable. Notice that the null part of the type is low in the lattice, - while the struct part is the highest struct. - * `*void` is a synonym for `*$BOT` - i.e. it represents a non-null pointer to - all possible struct types, akin to `void *` in C except not null. It is - the inverse or *dual* of `null`, and the null part is high in the pointer - lattice, while the struct part is the lowest struct. - * `null` pointer evaluates to False and non-null pointers evaluate to True, as in C. - -* <font style="background-color:lightgreen">Struct type</font> (new) - - Represents user defined struct types, a struct type is allowed to have - members of Integer type only in this chapter, later chapters will expand - this. - * `⊤:struct` represents local Top for struct type; all we know about the type - is that it is a struct but, we do not know if it is a specific struct, or - all possible structs. In the code, we use a struct with no fields named `$TOP`. - * `⊥:struct` represents local Bottom for struct type; we definitely know the - value can take all possible struct types. In the code, we uise a struct - with no fields named `$BOT`. -* <font style="background-color:blue" color="white">Memory type</font> (new) - Represents the whole-memory token - * `⊤:mem` is `TypeMem.TOP`, the high end of the memory domain. - * `⊥:mem` is `TypeMem.BOT`, our conservative type for the whole-memory state. - * Neither token describes the values stored in individual fields. -* <font style="background-color:pink">Tuple type</font> - when a Node results in a collection of values - -We make use of following operations on the lattice. - -* The `meet` operation takes two types and computes the greatest lower bound - type. While not true for all lattices, in the our lattice this can be - thought of as set union (ORing) of its input types (as sets). - * Example, meet of `*S1` and `*S2` results in `*void` - there is no lattice - element for exactly both `{*S1,*S2}`, so we drop down to the nearest - element containing both (and maybe more), which is `*void`. - * Meet of `*S1` and pointer `null` results in `*S1?` - * Meet of `*void` and `null` results in `*$BOT?`; bear in mind that `*void` is a synonym for `*$BOT`. - * Meet of `1` and `2` results in `Int Bot`. -* The `dual` operation is symmetric across the lattice centerline. Types directly on the centerline are their own dual. - * Find the corresponding node of the lattice after inverting the lattice. - * Thus, dual of `Top` is `Bot`. - * The dual of `*$TOP` is `*$BOT?`. - * For structs, the dual is obtained by computing the dual of each struct - member. Thus, dual of `*S1` is not `*S1?`, it is some `*S1?` with dualed - fields. - -* The `join` operation takes two types and computes the least upper bound type. - Similar to `meet` this can thought of as set intersection (ANDing) of its input types. - Because our lattice structure is symmetric and complete, we compute `join` with a well known identity: - `JOIN(x,y) === MEET(x.dual,y.dual).dual` - * Example, join of `*S1` and `*S2` results in `*$TOP`. - * Join of `1` and `2` results in `Int Top`. - * Join of `*void` and `Null` results in `*$TOP`. + + +The diagram uses `⊤` for **top** and `⊥` for **bottom**. A suffix names the +domain: `⊤:struct` is *struct top*, while the bare `⊤` is global top. In the +prose we use those words; in code examples we use the actual Java constants. +The implementation's `$TOP` and `$BOT` names need not appear in the diagram: + +| Diagram | Prose | Java constant | Internal struct name | +|---|---|---|---| +| `⊤:struct` | struct top | `TypeStruct.TOP` | `$TOP` | +| `⊥:struct` | struct bottom | `TypeStruct.BOT` | `$BOT` | + +Edges in this diagram show lattice order, with top above bottom. They are not +the use-to-definition edges of the program graphs elsewhere in the chapter. +Boxes containing an ellipsis abbreviate further parallel alternatives; they +are not extra union types. Field and tuple-element type lattices are elided. + +Within the type lattice, we now have the following domains: + +*  represents control flow: unreachable control + at control top, and reachable control at control bottom. +*  has integer top, integer bottom, and parallel + constants between them. The ellipses stand for the other integer constants. +*  (new) combines a struct type with nullability. + * The prefix `*` means pointer-to: `*Person` is a non-null pointer to a Person. + The suffix `?` includes null, so `*Person?` permits a Person pointer or null. + * The pointer domain contains the whole struct lattice twice, once without + null and once with it. The diagram expands named alternatives in both + copies. It is not just two individual pointer types. + * `null` combines struct top with the nullable flag: it has no non-null + object alternative. The diagram labels it `*⊤:struct?` as well as `null`. + * A pointer to struct bottom can point to any struct. The diagram shows the + non-null form as `*⊥:struct` and the nullable form as `*⊥:struct?`. + The latter is pointer bottom; pointer top is `*⊤:struct`. + * Null evaluates to false; non-null pointers evaluate to true. + + > C analogy: the non-null pointer to struct bottom is akin to `void *`, except + > that C's `void *` may also be null. Simple names this constant + > `TypeMemPtr.VOIDPTR` and prints it as `*void`. Struct bottom itself is the + > common lower bound of struct types, not C's `void` type. + +*  (new) represents user-defined named structs. + Fields have integer types in this chapter. + * Struct top lies above every named struct; struct bottom lies below every + named struct. Top is the high/empty struct alternative, while bottom + conservatively includes any struct name. + * `Person`, `s1`, `s2`, and further names are parallel alternatives. There is + no inheritance, so different named structs do not nest beneath one another, + even if they have identical fields. + * There is no fixed bound on the names a program can declare. The diagram's + ellipsis stands for more named alternatives, not a distinguished unnamed + struct. Each named box abbreviates its own field-type lattice. +*  (new) represents the whole-memory token. + Memory top and memory bottom are `TypeMem.TOP` and `TypeMem.BOT`. Neither + records the values stored in individual fields. +*  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. + +We use the following operations on the lattice: + +* **Meet** computes the greatest lower bound. For these examples, think of + combining the alternatives represented by its inputs. + * The meet of `Person` and `s1` is struct bottom. There is no separate type + representing exactly those two names. + * The meet of `*Person` and `*s1` is the non-null pointer to struct bottom. + * The meet of `*Person` and `null` is `*Person?`. + * The meet of the non-null pointer to struct bottom and `null` is pointer bottom. + * The meet of `1` and `2` is integer bottom. +* **Dual** reflects the lattice about its centerline: top and bottom exchange + places, and applying dual twice returns the original type. + * Struct top and struct bottom are duals. + * `null` and the non-null pointer to struct bottom are duals. + * A pointer's dual also duals its struct's fields and flips nullability. Thus + the dual of `*Person` is not generally the original `*Person?`: the field + types must be dualed too. Those field details are omitted in the diagram. +* **Join** computes the least upper bound. It is defined through meet and dual: + `JOIN(x,y) = MEET(x.dual(),y.dual()).dual()`. + * The join of `Person` and `s1` is struct top. + * The join of `*Person` and `*s1` is pointer top. + * The join of the non-null pointer to struct bottom and `null` is pointer top. + * The join of `1` and `2` is integer top. As we construct the Sea of Nodes graph, we ensure that values stay inside the domain they are created in - that is ptr fields will never contain ints @@ -221,8 +237,9 @@ To enable this behaviour, we make following enhancements. predicate is a ptr value. The up-cast removes the null possibility on the true branch making it legal to use the pointer. -* The up-cast is done using a `Cast` op with the type `*void`. This does a - lattice JOIN of the original type and `*void`. This JOIN operation preserves +* The up-cast uses a `Cast` with the non-null pointer to struct bottom + (`TypeMemPtr.VOIDPTR`). It joins the original pointer type with that type, + corresponding to `*⊥:struct` in the diagram. This JOIN operation preserves everything we already know about ptr, and also adds the new knowledge that the ptr is not-null. |