summaryrefslogtreecommitdiff
path: root/chapter33/README.md
diff options
context:
space:
mode:
Diffstat (limited to 'chapter33/README.md')
-rw-r--r--chapter33/README.md210
1 files changed, 206 insertions, 4 deletions
diff --git a/chapter33/README.md b/chapter33/README.md
index 486f02d3..9e95054e 100644
--- a/chapter33/README.md
+++ b/chapter33/README.md
@@ -4,10 +4,212 @@ English | [日本語](README.ja.md)
[Previous: Chapter 32 — Compiler Internal Speedups](../chapter32/README.md)
-This chapter will explore automatic memory management. The design is still
-open; no memory-management changes have been implemented yet. It starts from
-the complete, runnable Chapter 32 compiler, libraries, examples, and tests.
-The speedup measurements remain in [Chapter 32](../chapter32/README.md).
+This chapter starts automatic memory management with an allocation-lifetime
+analysis. It runs after Opto, field-layout finalization, and LoopTree, before TypeCheck.
+It reports where storage must live; allocation and machine code still use the
+existing runtime. The [design survey](../docs/automatic-memory-management-survey.md)
+records the language decisions. Chapter 32's
+[speedup measurements](../chapter32/README.md) remain there.
+
+The [existing-program survey](docs/allocation-survey.md) records what this first
+analysis accepts and rejects across `sys` and the games, with small reductions
+that separate analysis limitations from storage decisions.
+The [growing-array survey](docs/growing-arrays-survey.md) identifies builders that
+can finish in one scope, persistent collections, and library API changes needed
+for grow-in-place storage.
+
+## First allocation plans
+
+Four small examples in [Chapter33Test](src/test/java/com/seaofnodes/simple/Chapter33Test.java)
+exercise the first cut:
+
+| Example | Allocation destination |
+|---|---|
+| Make a temporary and pass it to a reader | Current function frame |
+| Return a Box containing a Thing through two factories | Caller-supplied result storage for both objects |
+| Assign a newly allocated Thing to an argument's field | Storage that lives long enough for that argument |
+| Call one factory twice and store into different arguments | Separate destinations for the two calls |
+
+The analysis walks the call DAG once. It discovers callees on entry and builds
+each function's summary on exit. Within a body it follows control, memory, and
+references, skipping arithmetic and offset expressions. Control anchors expose
+allocations even when only scalar uses remain; reference uses expose raw-address
+conversions without walking the arithmetic that consumes them. Sorting is confined
+to the debug dump. Parameters name symbolic storage owners;
+returning or storing a fresh reference adds destination requirements. Composing
+a call substitutes its actual arguments and keeps its fresh allocations distinct
+from other calls to the same factory. Private callee scratch stays in the
+callee's summary.
+
+Within one summary, loads, stores, and call effects converge before a worklist
+propagates destination requirements. For example, returning a Box retains its
+Thing too. This local closure does not repeat the call-graph traversal. Stores
+are conservative weak updates: overwriting a field does not yet release the
+earlier value's lifetime constraint. Array elements share one field, regardless
+of index.
+
+Pointer-valued loads keep the child's origin separate from the holder:
+
+```text
+get(h) { return h.c; } // returns borrowed origin arg3.c
+fill(h) { h.c.d = new Thing; } // new Thing must outlive arg3.c
+```
+
+At a call, `arg3.c` resolves to the actual holder's possible field values. A
+function can build a temporary holder and return its child; only the child
+needs result storage. Copying a child between holders likewise retains the
+child without retaining its source holder. Call substitution also handles two
+arguments referring to the same object.
+
+The ASCII dump shows function summaries in call-graph reverse postorder (RPO):
+callers before callees, starting from the program entry. Other retained functions
+(such as constructor bodies whose calls were inlined) follow in a separate RPO
+section. Reachability here follows direct calls in the optimized graph. Nested
+loop frames stay under their parent, with siblings ordered by node ID. Analysis
+still builds summaries in postorder.
+
+```text
++-- forward_noInline
+| call#219 -> make_noInline
+| [result] call#219/new#352:Test.Thing (8 bytes)
+| [result] call#219/new#381:Test.Box (8 bytes)
+| .child --> call#219/new#352:Test.Thing
+`-- return -> {call#219/new#381:Test.Box}
+
++-- make_noInline
+| [result] new#352:Test.Thing (8 bytes)
+| [result] new#381:Test.Box (8 bytes)
+| .child --> new#352:Test.Thing
+`-- return -> {new#381:Test.Box}
+```
+
+`frame` means scratch for that function; `result` means the caller's result
+destination; `static` means program lifetime. `arg3` names storage associated
+with argument input 3 (ordinary class functions use input 2 for their hidden
+receiver). `arg3.c` names the storage referenced by that argument's `c` field,
+not storage inside the holder. `arg3 & arg4` requires a destination satisfying both owners; it does
+not arbitrarily pick one. Node numbers help correlate this output with the IR.
+These are ownership constraints, not assigned physical stack offsets.
+Return origins are a set of alternatives: `{arg3:a | arg4:b}` means the returned
+reference may point to either argument. `{}` means no tracked storage is returned.
+
+Run a poster child and print its plan:
+
+```sh
+make -j8 test CLASS=Chapter33Test METHOD=testAllocationFactoryGraph "TEST_JAVA_OPTS=-XX:ActiveProcessorCount=2 -Dsimple.alloc.dump=true"
+```
+
+## Iteration storage and winners
+
+Functions and loop iterations use the same `Summary` and cleanup rule. Each
+summary has incoming values, normal exit values, retention effects, and scratch
+storage. A loop also has continuation values: its backedge returns these as
+arguments to the next iteration. Both loop exits clean up the iteration frame.
+The backedge's conceptual pop/push can reuse the same fixed storage without code.
+
+A loop can have both a surviving result and unrelated scratch. One reference-flow
+calculation finds both; placement follows the summary interfaces. For example,
+`testAllocationLoopWinnerAndScratch` constructs a Scratch and a candidate Thing
+each iteration, tests the candidate, and breaks with the winner:
+
+```text
+| +-- loop#221 frame; parent find_noInline
+| | continue refs -> {}
+| | return refs -> {call#276/new#424:Test.Thing}
+| | [loop#221 iteration] new#484:Test.Scratch (8 bytes)
+| `-- cleanup on continue and return -> {new#484:Test.Scratch}
+| [result] call#276/new#424:Test.Thing (8 bytes); loop#221 winner
+`-- return -> {call#276/new#424:Test.Thing}
+```
+
+The Thing has fixed result space reserved before entering the loop. Failed
+candidates may reuse it because no earlier candidate remains reachable on the
+backedge. Scratch belongs to the iteration and can be reclaimed each turn.
+Storage prints inside its owning frame, including an inner loop's winner when
+the outer iteration owns it. Iteration storage and function `[frame]` storage
+are the same logical scratch-storage choice, with different cleanup boundaries.
+A winner's referenced objects survive with it. An inner loop's winner can still
+belong to the outer loop's iteration storage. Storage exported by a frame is
+promoted through enclosing frames until one can own it. Calls substitute
+arguments and fresh sites; nested loops already share their function's SSA
+vocabulary, so their composition preserves site identities. Private callee
+scratch stays in the callee.
+
+The abbreviated dump above omits the value ports. The full dump names entry,
+continuation, and exit values, including scalar and memory values. A scalar
+loaded from scratch can cross an exit without retaining the scratch object.
+Returning from nested loops exports through each intervening summary; each
+frame retains its own cleanup set. These logical storage frames are separate
+from machine return-address and spill slots.
+
+The continuation summary follows reference Phis and memory reaching each backedge,
+including helper-call retention. Borrowed references can continue to the next
+iteration. Keeping an earlier candidate in a variable, linking
+candidates together, or storing them into a pre-existing array rejects the plan.
+Publishing through an argument's field only on an exit arm is allowed. For now,
+even bounded retention and overwritten memory slots reject: weak updates do not
+prove that the old reference died. Collection destinations and more precise
+memory liveness remain future work. Floating scalar uses may finish before an
+iteration reset; uses constrained outside the loop retain their referenced storage.
+
+These are still plans: no stack reservations, slot reuse, or reclamation are
+emitted yet. Allocation uses each CFG node's tightest containing LoopTree and
+the tree's parent links. Simple produces reducible control flow; that is an
+asserted invariant, not an allocation rejection. The early LoopTree walk leaves
+the IR unchanged. Before scheduling, the tree is rebuilt to account for Lower's
+CFG changes, and loops with zero exits receive one synthetic exit. Delaying those
+exits preserves nonreturning-function summaries during type checking and serialization.
+
+That ordering is temporary. Before this chapter closes, the original LoopTree
+build must insert NeverExits, Allocation's zero-exit support must be removed,
+and Lower must maintain the tree with local edits instead of a full rebuild.
+The [roadmap](../docs/roadmap.md#phase-ordering-and-incremental-analysis) tracks
+this deferred work, including preserving nonreturning-function semantics.
+
+Native calls borrow their arguments until the call returns: they must not retain,
+hide, or publish those references. Converting an array pointer to an integer now
+adds a `KeepAlive(control, value)` at the converting scope's exits. Allocation
+traces that value through arithmetic and Phis to its storage. The integer can
+travel through memory and Simple wrappers without losing the original endpoint.
+The native ABI and pointer representation are unchanged.
+
+The marker keeps every conversion, including earlier values of reassigned locals.
+Returns, breaks, and continues end the scopes they leave; unbraced if/else arms
+and loop bodies also have their own borrowing scopes. Conditional expressions
+share their enclosing scope. Returning or storing the integer does not extend
+that scope: using the address afterwards can access reclaimed storage.
+
+Markers survive serialization and inlining, then disappear before scheduling;
+they require no registers or machine instructions. Zero/null, duplicate adjacent
+markers, and unused address expressions fold away. Placement still chooses whole
+function/iteration frames, so a lexical endpoint can conservatively retain storage
+in a larger frame. Actual stack lowering is still pending. Serialized IR is now
+format 3; older objects must be rebuilt to supply these lifetime endpoints.
+
+Native results that are Simple pointers also need an explicit origin/allocation
+contract; they are not assumed to be borrowed or freshly allocated.
+
+The first cut also rejects plans for recursive calls, unknown/opaque Simple calls,
+variable-size allocations, and reference origins that it cannot trace.
+Weak updates can also invent endlessly longer field paths in
+code such as `p.next = p.next.next`; the pass rejects these plans when paths
+exceed the body's reads plus the path depths supplied by its callees. Tracking
+memory order is future work. A rejected function is printed as `REJECT`, never
+as a usable partial plan. Scalar field reads and writes do not themselves
+introduce retained references.
+
+Normal compilation records those rejections and continues with the existing
+allocator. `-Dsimple.alloc.check=true` rejects compilation if any function lacks
+a supported plan; tests can also require an individual summary to be supported.
+The pass does not yet insert hidden destination arguments, stack reservations,
+or reclamation. The proposed inline-object and growing-array syntax is not
+implemented by this analysis experiment.
+
+[Allocation.java](src/main/java/com/seaofnodes/simple/codegen/Allocation.java)
+contains the walk, one summary class, and one storage-site class. Comments mark
+the next work: collection and SCC destinations, memory-ordered field updates, bin packing,
+free lists, and parallel growth areas. No new IR nodes or serialized contracts
+are introduced yet.
## Build and use this chapter