summaryrefslogtreecommitdiff
path: root/chapter10b/README.md
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-10-03 14:03:48 -0700
committerCliff Click <cliffc@acm.org>2026-10-03 14:03:48 -0700
commit22df891893d30e9906d0b14fc3ae5d8e67d500b2 (patch)
tree2bda142f92febc8b26f1cabd4bb0c46d1864f34b /chapter10b/README.md
parentc3958e34c0de21df52e57e47e4f47ffe6464f138 (diff)
downloadSimple-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.md218
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.
-
-![Independent field dependencies](docs/example1.svg)
-
-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.
-
-![An aggregate preserves both updates](docs/example2a.svg)
-
-
-## 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.
-
-![Precise and bulk Phis share a control merge](docs/example2b.svg)
-
-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 type domains, including precise memory aliases](docs/lattice.svg)
-
-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.
-
-![Ordering applies within the affected alias](docs/example2c.svg)
-
-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"
-```