From c2b00feb2613e12ef4cafb2b6e022cb2831f68b8 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 23 Apr 2024 17:23:16 +0100 Subject: Chapter 10: Structs and Memory MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Thalia Archibald Co-authored-by: Dibyendu Majumdar Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: XmiliaH Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Robert Obkircher --- docs/chapter10/README.md | 359 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 359 insertions(+) create mode 100644 docs/chapter10/README.md (limited to 'docs/chapter10/README.md') diff --git a/docs/chapter10/README.md b/docs/chapter10/README.md new file mode 100644 index 00000000..32aec260 --- /dev/null +++ b/docs/chapter10/README.md @@ -0,0 +1,359 @@ +# Chapter 10: Structs and Memory + + +# Table of Contents + +1. [Memory](#memory) +2. [Alias Classes](#alias-classes) +3. [Implementation of Alias Classes](#implementation-of-alias-classes) +4. [Extensions to Intermediate Representation ](#extensions-to-intermediate-representation) +5. [Enhanced Type Lattice](#enhanced-type-lattice) +6. [Parser Enhancements](#parser-enhancements) +7. [Null Pointer Analysis](#null-pointer-analysis) +8. [Memory Operations Example](#memory-operations-example) +9. [Additional Peephole Optimizations](#additional-peephole-optimizations) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter10) 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-chapter09...linear-chapter10) it to the previous chapter. + +In this chapter: + +* We add user defined struct types in the Simple language. +* We introduce the concept of Memory, Memory Pointers and Aliasing. +* We add new nodes to represent operations on memory - such as creating new instance of a struct, storing and loading struct fields. + +Here is the [complete language grammar](10-grammar.md) for this chapter. + + +## Memory + +In previous chapters, we dealt with scalar values that fit into a single +machine register. We now introduce aggregate values of `struct` type; these +have reference semantics and thus do not behave like register values, even if +the struct would fit into a register. To support values of such a type, we +need the concept of `Memory`. + +The core ideas regarding `Memory` are: + +* The program starts and stops with a single `Memory` value that encapsulates + the whole of available memory; `Start` produces memory and `Return` consumes + memory. + +* Each `struct` and field carves up this memory into "alias classes", a unique + class for each combination of struct and field. + +* Memory in different alias classes *never* aliases; memory in the same alias + class *always* aliases. This is sometimes called "equivalence class" + aliasing. + +* Equivalence class aliasing can be directly represented in the Sea of Nodes, + as such we will not use any other side-structure for aliasing. This also + means with normal peepholes we can do alias-based optimizations such as + load/store bypassing or load forwarding without needing to consult any side + structure, or make alias tracking modifications when we alter the graph. + + +### Alias Classes + +Aliasing describes a situation in which a data location in memory can be +accessed through multiple symbolic names (variables) in the program. Modifying +the data through one name implicitly modifies the values associated with all +the aliased names. + +Data accesses to the same alias class (struct+field) are serialized as defined +by the source program; data in other classes is allowed to be accessed in +parallel. + +Simple, like Java, is a strongly typed language. Therefore, two variables that +have incompatible types cannot possibly be names to the same location in +memory. We can use type information to determine which symbols alias, +i.e., potentially reference the same location in memory. We +divide/slice all memory into disjoint alias classes. + +We implement the "alias class" as a unique integer ID assigned to each field in +a struct, where distinct struct types have their own set of ids. Thus, every +field in every struct type is a new alias class. In later chapters as we +implement arrays and subtyping, our strategy for assigning alias classes will +be enhanced. + +For background information and overview of type based alias analysis, please +refer to the paper `Type Based Alias Analysis`.[^1] Our approach is a form of +TBAA similar to the "FieldTypeDecl" algorithm described in the paper. We do +not track aliasing by instance of a Struct type. + + +### Implementation of Alias Classes + +For example, suppose we have declared two struct types like so: + +``` +struct Vec2D { int x; int y; } +struct Vec3D { int x; int y; int z; } +``` + +Then we can imagine assigning following alias class IDs + +| Struct type | Field | Alias | +| ----------- | ----- | ----- | +| Vec2D | x | 1 | +| Vec2D | y | 2 | +| Vec3D | x | 3 | +| Vec3D | y | 4 | +| Vec3D | z | 5 | + +So at this point we have sliced memory into 5 distinct alias classes. +Note that the `x` and `y` in `Vec2D` do not alias `x` and `y` in `Vec3D`. + +In this chapter we do not have inheritance or sub-typing. But if we had subtyping and `Vec3D` +was a subtype of `Vec2D` then `x` and `y` would alias and would be given the same alias class. + +## Extensions to Intermediate Representation + +We add following new Node types to support memory operations: + +| Node Name | Type | Description | Inputs | Value | +|-----------|------|----------------------------------|-----------------------------------------------------------|----------------------------------------| +| New | Mem | Create ptr to new object | Control, Struct type | Ptr value | +| Store | Mem | Stores a value in a struct field | Memory slice (aliased by struct+field), Ptr, Field, Value | Memory slice (aliased by struct+field) | +| Load | Mem | Loads a value from a field | Memory slice (aliased by struct+field), Ptr, Field | Value loaded | +| Cast | Data | Upcasts a value | Control, Data, type | Upcast value | + + +* New takes the current control as an input so that it is pinned correctly in + the control flow. Conceptually the control input is also a proxy for all + memory that originates from the Start node. + +* Above, "Ptr" refers to the base address of the allocated object. Ptrs can represent different values in loops. +* A "Memory Slice" represents a slice of memory where all stores and loads alias. Different slices do not alias. + +Additionally, the following Node types will be enhanced: + +| Node Name | Type | Changes | +|-----------|---------|------------------------------------------------------------------| +| Start | Control | Start will produce the initial Memory projections, one per slice | +| Return | Control | Will merge all memory slices | + + +## Enhanced Type Lattice + +The Type Lattice for Simple has a major revision in this chapter. + +![Graph1](./lattice.svg) + +Within the Type Lattice, we now have the following type domains: + +* Control type - represents control flow +* Integer type - Integer values, with a Top, Bottom and constants +* Pointer type (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. + +* Struct type (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`. +* Memory type (new) - Represents memory and memory slices + * `⊤:mem` - Nothing known about a slice; in the code we use `MEM#TOP`. + * `#n` - refers to a memory slice, and `n` is the alias class. + * `⊥:mem` - all of memory; in the code we use `MEM#BOT`. +* Tuple type - 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`. + * Meet of `#1` and `#2` results in `MEM#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`. + +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 +(obviously)... nor even the generic `TOP` and `BOT`. There are a couple of +nuances worth highlighting. + +* When Phis are created, the initial type of the Phi is based on the declared + type of its first input. This is a pessimistic type assignment because we do + not yet know what other types will be met. + +* When all the inputs of the Phi are known, we start with the local Top of the + declared type, and then compute a meet of all the input types. This + computation results in a more refined type for the Phi. + +## Parser Enhancements + +In previous chapters the only available type was Integer. Now, variables can +be of Integer type or pointer to Struct types. To support this, the Parser now +tracks the declared type of a variable (used to only be Integer!). The +declared type of a variable defines the set of values that can be legitimately +assigned to the variable. The Sea of Nodes graph also tracks the actual type +of values assigned to variables, these type transitions are defined by the Type +lattice described in the previous section. + +## Null Pointer Analysis + +The Simple language syntax allows a pointer variable to be specified as +null-able - and it prevents ever throwing a Null Pointer Exception. The +compiler decides if a null check is needed, and if needed and missing +the compiler rejects the program (asking the user to insert a null check). + +When the Parser encounters conditions that test the truthiness of a pointer variable, it uses this knowledge to refine the type information in the branches that follow. + +Here are two motivating examples: + +```java +struct Bar { int a; } +Bar? bar = new Bar; +if (arg) bar = null; +if( bar ) bar.a = 1; +``` + +If `bar` is not `null` above, then we would like to allow the assignment to +`bar.a`. If the final line lacked the null check, e.g. a plain `bar.a = 1;`, +then `Java` would compile this program but throw a NPE, and Simple rejects the +program pointing out a null check is required. + + +```java +struct Bar { int a; } +Bar? bar = new Bar; +if (arg) bar = null; +int rez = 3; +if( !bar ) rez=4; +else bar.a = 1; +``` + +If `bar` is `null` then we would like `!bar` to evaluate to `true`. In the else +branch we know `bar` is not null, hence the assignment to `bar.a` should be +allowed. + +To enable this behaviour, we make following enhancements. + +* We track the null-ness of a pointer in the Type system, and hence in every + Node that ptr type flows through. + +* We "wrap" the predicate of an `If` node with an up-cast when we see that the + 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 + everything we already know about ptr, and also adds the new knowledge that + the ptr is not-null. + +* The up-cast is represented by the `CastNode` op, and if applicable, we + replace all occurrences of the original predicate with the up-cast in the + current scope. The change is local to each branch of the `If`; occuring + separately for the true and the false branches of the `If` (and the false + branch inverts the predicate). + +* The up-cast peepholes normally; if its input's type is a super type of the + up-cast, then the `CastNode` can be removed. See `ScopeNode.upcast()` method, + and `CastNode`. + +* When computing a type for Not, we produce an Integer type when its input is a + ptr. When the input is a `null` we convert to `1` and when is a not `null` + ptr value, we convert to `0`. See `NotNode.compute()`. + +## Memory Operations Example + +This is a simple example illustrating how loads and stores are ordered based on aliasing. + +```java +struct Vec2D { int x; int y; } + +Vec2D v = new Vec2D; +v.x = 1; +if (arg) + v.y = 2; +else + v.y = 3; +return v; +``` + +The graph from above will have the shape: + +![Graph1](./example1.svg) + +The graph visual has the following enhancements: + +* The memory edges are shown in green and blue. +* The green edges occur on New nodes and anchor the ptr to a control flow node. +* The blue edges show the threading of a memory op via the equivalence aliasing. + +## Additional Peephole Optimizations + +The equivalence aliasing makes it possible to optimize following scenarios: + +* Store followed by another Store to the same field inside an object; the first Store is redundant if there are no other references to the first Store +* Load followed by a Store to a field inside an Object; the Load can be eliminated and the input value of the Store passed through. + +Both of these examples are illustrated in the example below: + +```java +struct Bar { + int a; + int b; +} +struct Foo { + int x; +} +Foo? foo = null; +Bar bar = new Bar; +bar.a = 1; +bar.a = 2; +return bar.a; +``` + +Before the peephole optimizations, we get: + +![Graph2a](./example2a.svg) + +After enabling Store-Store peephole we get: + +![Graph2b](./example2b.svg) + +After load-after-store elision: + +![Graph2c](./example2c.svg) + +Note that at this stage the `bar` object is dead therefore the allocation of bar can be dropped. + + +[^1]: Diwan A., McKinley K.S., Moss J.E.B. (1998). + Type Based Alias Analysis. -- cgit v1.2.3