diff options
| author | Cliff Click <cliffc@acm.org> | 2026-10-03 14:03:48 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-03 14:03:48 -0700 |
| commit | 22df891893d30e9906d0b14fc3ae5d8e67d500b2 (patch) | |
| tree | 2bda142f92febc8b26f1cabd4bb0c46d1864f34b /chapter10b/README.md | |
| parent | c3958e34c0de21df52e57e47e4f47ffe6464f138 (diff) | |
| download | Simple-22df891893d30e9906d0b14fc3ae5d8e67d500b2.tar.gz Simple-22df891893d30e9906d0b14fc3ae5d8e67d500b2.zip | |
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
Diffstat (limited to 'chapter10b/README.md')
| -rw-r--r-- | chapter10b/README.md | 218 |
1 files changed, 0 insertions, 218 deletions
diff --git a/chapter10b/README.md b/chapter10b/README.md deleted file mode 100644 index 7cb4cc75..00000000 --- a/chapter10b/README.md +++ /dev/null @@ -1,218 +0,0 @@ -# Chapter 10b: Splitting Memory - -[Previous: Chapter 10a](../chapter10a/README.md) | -[Next: Chapter 11](../chapter11/README.md) - -Chapter 10a made memory effects explicit with one SSA memory value. This -chapter keeps exactly that parser model and recovers independent memory chains -through graph rewrites. There is no new language syntax; the -[grammar](docs/10-grammar.md), pointer types, and null checks are unchanged. - -## Why split memory? - -```java -struct Point { int x; int y; } -Point p = new Point; -p.x = 42; -while (arg > 0) { - p.y = p.y + arg; - arg = arg - 1; -} -return p.x; -``` - -The loop changes `y`, so it cannot affect `x`. With one memory chain the load -of `x` follows the loop's stores. Splitting the fields lets ordinary -load-after-store forwarding turn the return value into 42. - - - -The graph shows the split chains before the final Load folds. Its memory input -goes straight to the Store of 42, bypassing the loop's `y` chain. As in 10a, -definitions appear above uses, apart from loop backedges, and arrows point -from use to definition. As in 10a, small, detached True/False projections -show the source branches gating Loads and Stores. Other control-flow context, -including Regions and their Phi bindings, is omitted. Chapter 11 chooses -the actual scheduling inputs; the vertical placement of independent chains -does not specify their execution order. - -## Equivalence-class aliasing - -Each struct field has an integer alias identity. Two different fields receive -different identities, even if they have the same spelling in different structs. -Two instances of the same struct share their field aliases. Thus different -classes never alias; accesses in the same class **may alias**. Same-class does -not mean same-address: forwarding still checks pointer identity. - -The parser assigns field identities at struct declarations, beginning at 2. -These identities are independent of Start's output indices. The default slot -of a memory aggregate is 1; precise slots are greater than 1. - -We do not allocate a Start projection, scope binding, or loop Phi for every -declared field. Start supplies one memory value, Scope holds one `$mem` binding, -and Return consumes `{ctrl, $mem, result}`. As with Start's outputs, control is -in slot 0 and memory in slot 1. The optimizer introduces slices -only where graph operations require them. - -## Three memory nodes - -| Node | Meaning | -|---|---| -| `MemMerge` | A complete memory state: a default plus precise alias overrides | -| `MemPhi` | One alias selected according to the incoming control path | -| `BulkMemPhi` | All aliases except an explicit exclusion set, selected by control | - -`MemMerge` combines independent pieces of memory at one program point. It is -not a control-flow merge. For example, after storing to alias `x`: - -```text -prior = current memory -store = Store_x(prior, pointer, value) -current memory = MemMerge(default=prior, x=store) -``` - -The Store selects its precise input from any incoming MemMerge. Loads and -precise memory Phis do the same. A missing precise entry falls back to the -default, provided that default still covers the requested alias. - -The explicit entries override the default: the semantic slices are disjoint, -and their union covers all memory. Flattening stacked aggregates preserves -entries that the outer aggregate has not replaced. This allows an `x` store -and a later `y` store to remain visible together at Return. - -The graph below shows `p.x = arg; p.y = 42; return p;` after redundant -initialization stores have been removed. MemMerge takes the default memory -in slot 1 and the `x` and `y` overrides in slots 2 and 3. - - - - -## Splitting a memory Phi - -Scope initially creates a BulkMemPhi wherever the ordinary SSA algorithm needs -to merge memory. It starts by covering all aliases and an empty exclusion set -while the merge point is finalized. Later, peeps will split out precise memory -slices from the bulk memory, lazily on demand. - -Precise single aliases can be split out from the bulk by this transformation: - -```text -BulkPhi(R, left, right) - becomes -MemMerge( - default = BulkPhi_except{x}(R, left, right), - x = MemPhi_x(R, slice(left,x), slice(right,x))) -``` - -The new precise Phi and the remaining bulk Phi share a Region (omitted from -the illustrations) and matching control-path indices. A loop uses the same -transformation, with the backedge among those inputs. Each further split preserves all previously extracted -slices (and peephole optimizations tidy up the stacked splits). - -Here the two branches store 3 or 4 into `p.x`, then return `p`. The graph shows -the partition immediately after extracting `x`, before further simplification -of the bulk Phi and its incoming aggregates. - - - -This transform is invasive, and is disallowed from being called recursively; -you can end up splitting around a loop (which is good) but then visiting a -1/2-split loop head (which is bad). The new nodes from the split are put -on the worklist and visited after the current split completes. - -Since bulk Phis merge a bunch of aliases, they have to take care when -peepholing vs MemMerges: there cannot be any overlap between the MemMerge -precise merges and the bulk Phi. - -Phi refactoring can combine matching Loads or Stores as in Chapter 10a (pushing -up or pulling down). The Phi new memory operands can use precise MemPhis for -the alias. This peep requires precise aliases, and is otherwise blocked by -BulkMems - and thus is a trigger for splitting a BulkMem. - -This also extends the worklist lesson from Chapter 9. A bulk Phi inspects its -users, so changes to a user's partition must wake the producer - job for -`addDep()`. Selecting a slice from an aggregate can expose a new bulk-Phi -user; that selected definition must be queued too. In short, any time we're -working with MemMerge, MemPhi or BulkMemPhi we can expect some non-local -dependencies. - -Memory splitting can increase node count - but Phis (Mem, Bulk or otherwise) -make no code. Progress comes from extracting an alias from a bulk Phi and -removing some Loads & Stores, rather than from requiring every rewrite -to shrink the graph. In other words, the total Load/Store count is going down -even if the MemPhi count is going up. - - - -## Types - -The type lattice retains Chapter 10a's six domains, colors, and notation: -`⊤` means top, `⊥` means bottom, and a suffix names the domain. The other five -domains are unchanged; memory now adds a flat element `MEM#N` for each precise -alias between memory top (`TypeMem.TOP`) and memory bottom (`TypeMem.BOT`). - - - -The parallel `MEM#2`, `MEM#3`, and further alias elements describe independent -field slices. For the first `Point` declaration above, these two aliases identify -`Point.x` and `Point.y`. Meeting different aliases gives memory bottom; joining -them gives memory top. Each precise alias is its own dual. (And the ellipsis stands -for more parallel aliases, not a type representing a set of aliases). - -Memory bottom covers all memory. The default aggregate slot numbered 1 is a -graph input position, not a precise field alias in this diagram. Types do not -track field values, private objects, or escape information. Bulk exclusion sets -and the default-plus-overrides structure of MemMerge belong to graph nodes, -not to an expanded type lattice. As in Chapter 10a, diagram edges show lattice -order, with top above bottom; field and tuple-element type lattices are elided. - - -## Evaluation and ordering - -MemMerge is a dependency node; it emits no heap operation. Its evaluator result -is a memory token, while Store mutates the object's fields. The scheduler must -distinguish aggregation from overwriting memory. A MemMerge is not a clobber, -and stores in different alias classes do not impose load/store anti-dependencies. - -In `int old = p.x; p.x = arg; p.y = arg; return old;`, the Load must precede -the later `x` Store; the `y` Store has an independent memory chain. The graph -retains the Load to show this scheduling requirement before local folding. - - - -Tests cover independent-field folding, parallel memory Phis, multiple field -updates surviving at Return, early returns, nested loops with break/continue, -and reads before subsequent stores through potentially aliased pointers. - -## What remains for later chapters? - -Chapter 10b knows every access's alias while parsing. What is lazy here is the -construction of memory partitions. Chapter 25 also allows an existing access's -alias to become known later, using the same representation. Its private -constructor memory, escape tracking, incomplete types, and module alias -remapping are separate extensions and are not needed here. - -Chapters 11-24 use this representation, including alias-specific load/store -anti-dependencies. Chapter 15 adds allocation with partial memory and typed -alias contents. Chapter 16 extends initialization to constructor values, and -Chapter 18 carries whole memory across function calls. - -## Build and test - -With JDK 21 or newer, from this directory: - -```sh -make lib -make tests -make release -make view -``` - -Make builds this complete snapshot without Maven. `make release` writes -`build/release/simple.jar`; `make view` launches the shared graph viewer. -Both the root Maven reactor and the supplied IDEA module descriptor include -the chapter. From the repository root, test both halves with: - -```sh -make tests CHAPTERS="chapter10a chapter10b" -``` |
