From 22df891893d30e9906d0b14fc3ae5d8e67d500b2 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 3 Oct 2026 14:03:48 -0700 Subject: Chapter renumber, and split ch 17 Renumber chapters 10a, 10b, 11, 12, 13, 14 -> 10, 11, 13, 12, [11,14]. Split ch 17 into a 17a and 17b; shuffle around im/mutable syntax to be consistent, and present it more slowly. THe new immutable syntax is pushed through all later chapters --- chapter10a/README.md | 424 --------------------------------------------------- 1 file changed, 424 deletions(-) delete mode 100644 chapter10a/README.md (limited to 'chapter10a/README.md') diff --git a/chapter10a/README.md b/chapter10a/README.md deleted file mode 100644 index e150c664..00000000 --- a/chapter10a/README.md +++ /dev/null @@ -1,424 +0,0 @@ -# Chapter 10a: Structs and Memory - -[Previous: Chapter 9](../chapter09/README.md) | -[Next: Chapter 10b](../chapter10b/README.md) - -This chapter adds user-defined structs, pointers, allocation, field loads and -stores, and null checking. It also introduces an evaluator that executes the -graph, including its memory effects. The [grammar](docs/10-grammar.md) is the -same in 10a and 10b; the next chapter improves the memory representation. - -## References - -Structs are a collection of named and typed fields; very classically similar to -C or Java. New structs are made with the `new` keyword; this allocates memory -and produces a reference. Freeing memory awaits a later chapter. Fields are -accessed with the `.` notation. The fields can hold any scalar value, -including reference other structs and be mutually recursive. Any reference -field can allow null or not, same as a normal variable. - -```java -struct Person { - String last; // Last name, must exist - String? middle; // Optional middle name - int age; -}; -``` - -Here we have fields `last`, a not-null final String, and `middle` a nullable -and final String, and an `int age`. Like all `int` declared fields, it is -mutable. Later chapters will allow both mutable reference fields and immutable -integer fields; for now this choice covers most of the common ground. - -You have to have a reference to get at the fields, static fields are added in a later chapter. - -All field references have to be against not-null pointers, and this is directly -checked in the type system. I.e., Simple disallows null-pointer-exceptions by -design. Some examples of null checking before using: - -```java -print(ptr.age); // ERROR! ptr might be null - -if( ptr ) print(ptr.age); // Test before use - -// Field use can be far removed, as long as the check dominates -if( ptr ) { - S1; // Other statements - while( other ) { ...ptr.age... } -}; -``` - -Allocation, as well as Stores, means we now have memory effects to deal with. - - -## One memory value - -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; } -Point p = new Point; -p.x = 3; -p.y = arg; -return p.x; -``` - -`NewNode` produces the pointer. The parser emits stores of zero for both fields, -then stores 3 into `x` and `arg` into `y`. The final load observes the memory -after the `y` store. We deliberately keep that dependency here, even though -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. -To focus on memory, these illustrations show only small, detached True/False -control projections gating Loads and Stores. These schematic gates indicate -the source branches; Chapter 11 chooses the actual scheduling inputs. Other -control-flow context, including the Regions that bind Phis, is omitted. -The layout shows dependencies, not an execution schedule. - -| 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, memory, result | Completion with all preceding effects retained | - -For nodes consuming or producing both control and memory, control occupies slot -0 and memory slot 1. Start's outputs are `{ctrl, $mem, arg}`; Return's inputs -are `{ctrl, $mem, result}`. - -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 object's 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. - -For an `if`, the two branches can finish with different memory values. An -ordinary Phi selects the memory from the branch that executed: - -```java -struct Point { int x; int y; } -Point p = new Point; -if( arg ) p.x = 3; else p.x = 4; -return p.x; -``` - -![Whole memory across a branch](docs/example2a.svg) - -Loops reuse Chapter 8's lazy Phi construction. Reading or updating `$mem` in a -loop creates an initially incomplete memory Phi. Closing the loop supplies its -backedge. `break`, `continue`, nested loops, and early returns use the same scope -mechanics as scalar variables. - -```java -struct Point { int x; int y; } -Point p = new Point; -while( arg ) { - p.x = arg; - arg = arg-1; -}; -return p.x; -``` - -![Whole memory around a loop](docs/example2b.svg) - -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. - -## Enhanced Type Lattice - -The Type Lattice for Simple has a major revision in this chapter. - -![Type lattice with six domains and parallel named struct alternatives](./docs/lattice.svg) - -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. Boxes -containing an ellipsis abbreviate further parallel alternatives; they are not -extra union types. Field and tuple-element type lattices are elided in the -diagram. Field types can be any scalar type (Integer or Pointer), Tuple types -can be *any* lattice type, including Control and Memory. - -Within the type lattice, we now have the following domains: - -* ![Control](docs/type-control.svg) represents control flow: unreachable control - at control top, and reachable control at control bottom. -* ![Integer](docs/type-integer.svg) has integer top, integer bottom, and parallel - constants between them. The ellipses stand for the other integer constants. -* ![Pointer](docs/type-pointer.svg) (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. - -* ![Struct](docs/type-struct.svg) (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. -* ![Memory](docs/type-memory.svg) (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. -* ![Tuple](docs/type-tuple.svg) represents a collection of results from one node, - 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: - -* **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 pointer fields will never contain integers -(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 the 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 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. - -* 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`; occurring - 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 it is a non-null - 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. We just wrote `arg` into `p.x`, so reading it back needs no -memory access: - -```java -struct Box { int x; } -Box p = new Box; -p.x = arg; -return p.x; // Can return arg directly. -``` - -| Before: read back the stored value | After: use the value directly | -|---|---| -| ![Before: Return reads Load p.x after Store p.x](docs/load-after-store-before.svg) | ![After: Return uses arg and still consumes the Store's memory](docs/load-after-store-after.svg) | - -Return's result input changes from the Load to `arg`, and the unused Load -disappears. Return still consumes the Store's memory, so the write is retained. - -A store immediately following another store to the same address can also -discard the earlier store when no other user needs it. That separate rewrite -can remove the zero-initialization store still shown above. 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 -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 -global code motion and scheduling as a separate topic. - -## Build and test - -From this directory, with JDK 21 or newer, Make, and a shell: - -```sh -make lib -make tests -make release -make view -``` - -Make builds this snapshot directly, without Maven. `make release` produces -`build/release/simple.jar`; `make view` launches the shared interactive graph -viewer. Maven and IDEA module descriptions are also supplied. Tests include all -earlier chapters, memory ordering, returned object contents, and nested loops. - -Next, [Chapter 10b](../chapter10b/README.md) keeps this one parser binding while -splitting the graph into independent memory slices. -- cgit v1.2.3