summaryrefslogtreecommitdiff
path: root/chapter33/README.md
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-11-20 15:26:44 -0800
committerCliff Click <cliffc@acm.org>2026-11-20 15:26:44 -0800
commitc201515eeb2e99cb6f0e820459662affc047c2ce (patch)
tree28750086af8c788f4614d6a8b2a82df4a413e00a /chapter33/README.md
parent4f0cc22dafcdea877fe4ab137523a5944f754126 (diff)
downloadSimple-c201515eeb2e99cb6f0e820459662affc047c2ce.tar.gz
Simple-c201515eeb2e99cb6f0e820459662affc047c2ce.zip
Basic first implementationch33
Walk a Call Graph DAG. Find allocation sites; find uses for those objects; move the allocation to the common shared call point. Limited in all sorts of ways.
Diffstat (limited to 'chapter33/README.md')
-rw-r--r--chapter33/README.md87
1 files changed, 83 insertions, 4 deletions
diff --git a/chapter33/README.md b/chapter33/README.md
index 486f02d3..e3a19026 100644
--- a/chapter33/README.md
+++ b/chapter33/README.md
@@ -4,10 +4,89 @@ 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 and field-layout finalization, 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.
+
+## 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, a worklist propagates requirements through object fields.
+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.
+
+The ASCII dump shows callees first, then their callers:
+
+```text
++-- 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
+
++-- 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
+```
+
+`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 & 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.
+
+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"
+```
+
+The first cut rejects plans for loops, recursive calls, opaque/indirect calls,
+variable-size allocations, raw address conversions, and reference origins that
+it cannot trace, including pointer-valued field loads. 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: loop and SCC destinations, field-path origins, bin packing,
+free lists, and parallel growth areas. No new IR nodes or serialized contracts
+are introduced yet.
## Build and use this chapter