summaryrefslogtreecommitdiff
path: root/chapter33
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
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')
-rw-r--r--chapter33/README.md87
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java397
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java15
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/ConstantNode.java1
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/FunNode.java2
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java1
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/Node.java5
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/ParmNode.java2
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/StartNode.java2
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/SummaryNode.java1
-rw-r--r--chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java223
-rw-r--r--chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java2
12 files changed, 732 insertions, 6 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
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java b/chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java
new file mode 100644
index 00000000..0c4feeee
--- /dev/null
+++ b/chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java
@@ -0,0 +1,397 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.util.SB;
+import java.util.*;
+
+/** First allocation-lifetime experiment. Builds plans, not machine allocations.
+ * One DFS of the call DAG: discover callees on entry, compose their symbolic
+ * summaries on exit. No call-tree expansion, caller rewalk, or IR mutation.
+ * Within a summary, reference edges propagate destination requirements with a
+ * small worklist. A rejected summary is never a usable allocation plan.
+ */
+public final class Allocation {
+ private final Summary[] _summaries;
+ private final ArrayList<Summary> _postorder = new ArrayList<>();
+
+ // Destination bits: result, static storage, then Call/Parm input indices.
+ private static final int RESULT=0, STATIC=1;
+
+ /** One abstract storage object. Imported allocations are distinct per call
+ * site; a parameter denotes borrowed storage, not an allocation to move. */
+ public static final class Site {
+ public final NewNode _allocation; // null for a formal or static storage
+ public final int _arg; // >=2: Parm index, -1: static, 0: fresh
+ public final String _name;
+ public final long _bytes; // snapshot before later IR rewrites
+ public final BitSet _owners = new BitSet();
+ public final HashMap<String,HashSet<Site>> _fields = new HashMap<>();
+
+ private Site(NewNode allocation, int arg, String name) {
+ _allocation=allocation; _arg=arg; _name=name;
+ _bytes=allocation!=null && allocation.size()._type instanceof TypeInteger size && size.isConstant()
+ ? size.value() : -1;
+ if( arg>=2 ) _owners.set(arg);
+ if( arg==-1 ) _owners.set(STATIC);
+ }
+
+ public String destination() {
+ if( _owners.isEmpty() ) return "frame";
+ SB sb = new SB();
+ for( int i=_owners.nextSetBit(0); i>=0; i=_owners.nextSetBit(i+1) )
+ sb.p(i==RESULT ? "result" : i==STATIC ? "static" : "arg"+i).p(" & ");
+ return sb.unchar(3).toString();
+ }
+ }
+
+ /** Symbolic summary, with separate destinations for separate arguments.
+ * Object fields are weak updates: all stored references remain possible.
+ * The first cut rejects pointer loads rather than guessing their origin. */
+
+ // Per-function summary; allocation sites; failure reasons
+ public static final class Summary {
+ public final FunNode _fun;
+ public final ArrayList<Site> _sites = new ArrayList<>();
+ public final HashSet<Site> _returns = new HashSet<>();
+ public String _reject;
+ private byte _state; // 0 pre/unseen, 1 mid/active DFS, 2 post/complete
+ // All allocation-interesting Nodes; Calls, Stores, News, Ptr ops
+ private final ArrayList<Node> _nodes = new ArrayList<>();
+ // Just the Calls
+ private final ArrayList<CallNode> _calls = new ArrayList<>();
+ // Pointer expression -> possible storage objects, in this function's vocabulary.
+ private final IdentityHashMap< Node,HashSet<Site>> _values = new IdentityHashMap<>();
+ // Call -> returned storage after substituting actuals and importing effects once.
+ private final IdentityHashMap<CallNode,HashSet<Site>> _results = new IdentityHashMap<>();
+ private final BitSet _resolving = new BitSet();
+ private final Site _static = new Site(null,-1,"static");
+
+ private Summary(FunNode fun) { _fun=fun; }
+ // Hit the end of summary findings with no errors.
+ public boolean supported() { return _state==2 && _reject==null; }
+ // Throw or return valid summary
+ public Summary requireSupported() {
+ if( !supported() ) throw new IllegalStateException("Allocation "+_fun.label()+": "+_reject);
+ return this;
+ }
+ // Collect first rejection
+ private void reject(String why) { if( _reject==null ) _reject=why; }
+ }
+
+ public Allocation(CodeGen code) {
+ _summaries = new Summary[code._linker._len];
+ for( FunNode fun : code._linker )
+ if( fun!=null && !fun.isDead() && !fun._type.isHigh() )
+ _summaries[fun.sig().fidx()] = new Summary(fun);
+ for( Summary sum : _summaries )
+ if( sum!=null )
+ visit(sum);
+ }
+
+ public Summary summary(String name) {
+ for( Summary sum : _summaries )
+ if( sum!=null && name.equals(sum._fun._name) ) return sum;
+ throw new IllegalArgumentException("No allocation summary for "+name);
+ }
+
+ public void requireSupported() {
+ for( Summary sum : _postorder )
+ sum.requireSupported();
+ }
+
+ private void visit(Summary sum) {
+ if( sum._state==2 ) return; // Post-order, done
+ // Mid-visit, so found a Call Graph cycle, i.e. recursion
+ if( sum._state==1 ) {
+ // Recursive SCC/mega-call work goes here; do not expand a call tree.
+ sum.reject("recursive call component");
+ return;
+ }
+ // Was pre-order, now mid-order
+ sum._state=1;
+ if( sum._fun._extern || sum._fun.summary()!=null ) {
+ sum.reject("opaque body: allocation contract unavailable");
+ } else {
+ // Collection interesting function body and call sites
+ collect(sum);
+ for( CallNode call : sum._calls ) {
+ Summary callee = target(call);
+ if( callee==null ) sum.reject("opaque or indirect call #"+call._nid);
+ else {
+ // Recursive walk Call Graph DAG
+ visit(callee);
+ // If some callee is rejected, so is this caller
+ if( callee._reject!=null )
+ sum.reject("call #"+call._nid+" -> "+callee._fun.label()+": "+callee._reject);
+ }
+ }
+ if( sum._reject==null )
+ build(sum);
+ }
+ // Postder
+ sum._state=2;
+ _postorder.add(sum);
+ }
+
+ private Summary target(CallNode call) {
+ if( !(call.fptr()._type instanceof TypeFunPtr fp) || !fp.isConstant() ) return null;
+ int idx=fp.fidx();
+ return idx>=0 && idx<_summaries.length ? _summaries[idx] : null;
+ }
+
+ // Follow control, memory, and references, not arithmetic/offset expressions.
+ // Find allocations at control anchors too: their only remaining use might
+ // be a scalar load or a raw address buried under arithmetic. Don't walk into
+ // other functions, so no following linked Calls or Parms.
+ private void collect(Summary sum) {
+ BitSet seen = new BitSet();
+ ArrayDeque<Node> work = new ArrayDeque<>();
+ // Start from the return
+ work.push(sum._fun.ret());
+ // Repeat until entire function is walked
+ while( !work.isEmpty() ) {
+ Node n = work.pop();
+ if( seen.get(n._nid) ) continue; // Been there, done that
+ seen.set(n._nid);
+ // Add to function body
+ sum._nodes.add(n);
+ if( n instanceof CFGNode )
+ for( Node use : n._outputs )
+ if( use instanceof NewNode alloc && alloc.ctrl()==n ||
+ use instanceof ParmNode parm && parm.fun()==sum._fun )
+ work.push(use);
+ // Reference uses stay within this function; Parm call links and
+ // constant/global anchors are boundaries. In particular, find raw
+ // conversions without following their scalar arithmetic users.
+ if( !n.isFunLeaf() || n instanceof ParmNode )
+ for( Node use : n._outputs )
+ if( use instanceof PtrToIntNode || pointer(use) && !use.isFunLeaf() )
+ work.push(use);
+ if( n.isFunLeaf() ) continue;
+ if( n instanceof CallNode call ) sum._calls.add(call);
+ // Iteration/winner destinations go here. Until then reject loops,
+ // even when a flow-insensitive union would appear to fit a frame.
+ if( n instanceof LoopNode ) sum.reject("loop destinations not implemented");
+ if( n instanceof PtrToIntNode ) sum.reject("raw address escapes lifetime tracking #"+n._nid);
+
+ // CLInit accesses static state, not caller parameters. Its body is
+ // analyzed separately; stores publishing local objects to static
+ // state already give those objects the static destination. Do not
+ // mistake an own-class initialization guard for recursive calling.
+ if( n instanceof CallEndNode cend ) { work.push(cend.call()); continue; }
+
+ // Walk selected edges. We can skip pure-data ops, but need to
+ // walk both control and memory at least.
+ for( Node in : n._inputs )
+ if( in!=null && (in instanceof CFGNode || in.isMem() ||
+ in._type instanceof TypeMem || pointer(in) || in instanceof NewNode) )
+ work.push(in);
+ }
+ }
+
+ // Post-order work during the Call Graph visit
+ private void build(Summary sum) {
+ for( Node n : sum._nodes ) {
+ // Gather allocation sites
+ if( n instanceof NewNode alloc ) {
+ if( !(alloc.size()._type instanceof TypeInteger size) || !size.isConstant() )
+ sum.reject("variable-size allocation #"+alloc._nid);
+ Site site = new Site(alloc,0,"new#"+alloc._nid+":"+alloc._ts._name);
+ if( TypeStruct.startsClzPrefix(alloc._ts._name) ) site._owners.set(STATIC);
+ sum._sites.add(site);
+ sum._values.put(alloc,set(site));
+ }
+ if( n instanceof ParmNode parm && pointer(parm) ) {
+ if( parm.fun()!=sum._fun ) sum.reject("foreign parameter #"+parm._nid);
+ Site site = new Site(null,parm._idx,"arg"+parm._idx+":"+parm.label());
+ sum._sites.add(site);
+ sum._values.put(parm,set(site));
+ }
+ }
+ for( CallNode call : sum._calls ) compose(sum,call);
+ for( Node n : sum._nodes ) {
+ if( n instanceof StoreNode store && pointer(store.val()) ) {
+ Set<Site> dst = refs(sum,store.ptr()), src=refs(sum,store.val());
+ edge(dst, store._name, src);
+ }
+ }
+ sum._returns.addAll(refs(sum,sum._fun.ret().expr()));
+ for( Site site : sum._returns ) site._owners.set(RESULT);
+ if( !sum._static._fields.isEmpty() ) sum._sites.add(sum._static);
+
+ // Local closure only: an object retained in a destination retains its
+ // referenced objects there too. Cyclic object graphs need no DAG rewalk.
+ ArrayDeque<Site> work=new ArrayDeque<>(sum._sites);
+ while( !work.isEmpty() ) {
+ Site src = work.pop();
+ for( Set<Site> values : src._fields.values() )
+ for( Site dst : values ) {
+ int before = dst._owners.cardinality();
+ dst._owners.or(src._owners); // Union owners set
+ if( dst._owners.cardinality() != before ) work.push(dst);
+ }
+ }
+ // Bin packing goes here: fixed destinations become caller landing zones.
+ // Free-list work goes here: only after checking remaining usable aliases.
+ // Parallel growing tips go here: one owner may need several storage areas.
+ }
+
+ // n has pointer type
+ private static boolean pointer(Node n) {
+ return n!=null && (n._type instanceof TypeMemPtr || n._type instanceof TypePtr);
+ }
+
+ // One element Set of Site
+ private static HashSet<Site> set(Site site) {
+ HashSet<Site> set = new HashSet<>(); set.add(site); return set;
+ }
+
+ private static void edge(Set<Site> dst, String field, Set<Site> src) {
+ if( src.isEmpty() ) return;
+ for( Site site : dst )
+ site._fields.computeIfAbsent(field,k -> new HashSet<>()).addAll(src);
+ }
+
+
+ // Which storage objects can this pointer expression denote? This resolves
+ // pointer VALUE flow, not the fields reachable through the pointer. A Phi
+ // unions possible targets; casts/views preserve targets; a call result uses
+ // compose's caller-side targets. New/Parm targets were seeded by build.
+ // Example: refs(cond ? a : b) = {site(a), site(b)}.
+ // build() uses these sets to add Store edges, then propagates owner requirements
+ // through that separate object graph. Object cycles are handled there;
+ // _resolving rejects cyclic SSA values (loop Phi support is future work).
+ private HashSet<Site> refs(Summary sum, Node n) {
+ if( !pointer(n) ) return new HashSet<>();
+ HashSet<Site> old = sum._values.get(n);
+ if( old!=null ) return old;
+ HashSet<Site> values = new HashSet<>();
+ if( sum._resolving.get(n._nid) ) {
+ sum.reject("cyclic reference value #"+n._nid);
+ return values;
+ }
+ sum._resolving.set(n._nid);
+ if( n instanceof ConstantNode ) {
+ // Zero/null carries no storage obligation. Other constant objects
+ // have static backing; references loaded from them are not guessed.
+ if( n._type!=Type.NIL && n._type!=TypeInteger.ZERO ) values.add(sum._static);
+ } else if( n instanceof ProjNode proj && proj.in(0) instanceof NewNode alloc && proj._idx==0 ) {
+ Set<Site> sites = sum._values.get(alloc);
+ if( sites==null ) sum.reject("foreign allocation #"+alloc._nid);
+ else values.addAll(sites);
+ } else if( n instanceof ProjNode proj && proj.in(0) instanceof CallEndNode end && proj._idx==2 ) {
+ values.addAll(compose(sum,end.call()));
+ } else if( n instanceof PhiNode phi && !(phi instanceof ParmNode) ) {
+ for( int i=1; i<n.nIns(); i++ )
+ if( !phi.region().in(i)._type.isHigh() ) values.addAll(refs(sum,n.in(i)));
+ } else if( n instanceof ReadOnlyNode || n instanceof GuardNode ||
+ n instanceof ConstructNode || n instanceof InitViewNode || n instanceof ConvertNode ) {
+ values.addAll(refs(sum,n.in(1)));
+ } else if( n instanceof ArrayInitNode ) {
+ values.addAll(refs(sum,n.in(2)));
+ } else {
+ // Field-path/array-element origins go here. A parameter's child may
+ // have a different owner; never silently substitute the base owner.
+ sum.reject("reference origin "+n.getClass().getSimpleName()+" #"+n._nid);
+ }
+ sum._resolving.clear(n._nid);
+ sum._values.put(n,values);
+ return values;
+ }
+
+ // Apply an already-built callee summary to this particular call. Translate
+ // callee Sites into caller Sites: formal -> refs(actual), static -> static,
+ // escaping allocation -> fresh Site tagged with this call. This copies
+ // analysis objects, not runtime objects or IR. Private callee scratch stays
+ // in the callee. A second call gets distinct Sites for its fresh allocations.
+ // Then translate field edges and returned targets through the same map.
+ // For helper(h) { h.c = new Thing; }, calling helper(a) adds a.c -> call/new.
+ // The map values are SETS because an actual may select several objects.
+ // Callee result/argument owner bits are relative to its signature; do not
+ // copy them into the caller. build's closure derives the caller's owners
+ // from the translated edges and uses of the result. Only static is absolute.
+ private HashSet<Site> compose(Summary sum, CallNode call) {
+ HashSet<Site> result=sum._results.get(call);
+ if( result!=null ) return result;
+ result=new HashSet<>();
+ sum._results.put(call,result);
+ Summary callee=target(call);
+ if( callee==null || !callee.supported() ) {
+ sum.reject("unavailable allocation summary at call #"+call._nid);
+ return result;
+ }
+ IdentityHashMap<Site,HashSet<Site>> map=new IdentityHashMap<>();
+ map.put(callee._static,set(sum._static));
+ // Establish all substitutions first, so forward/cyclic field edges can
+ // be copied without depending on Site visitation order.
+ for( Site site : callee._sites ) {
+ if( site._arg>=2 ) {
+ if( site._arg>=call.nIns()-1 ) {
+ sum.reject("missing argument at call #"+call._nid);
+ map.put(site,new HashSet<>());
+ } else map.put(site,refs(sum,call.arg(site._arg)));
+ } else if( site._allocation!=null && !site._owners.isEmpty() ) {
+ Site copy=new Site(site._allocation,0,"call#"+call._nid+"/"+site._name);
+ // Return/argument owners are substituted by edges in this caller.
+ if( site._owners.get(STATIC) ) copy._owners.set(STATIC);
+ sum._sites.add(copy);
+ map.put(site,set(copy));
+ }
+ }
+ // Retention effects exist even when the function returns a scalar.
+ for( Site site : callee._sites ) {
+ Set<Site> dst=map.get(site);
+ if( dst==null ) continue;
+ for( var field : site._fields.entrySet() ) for( Site child : field.getValue() ) {
+ Set<Site> src=map.get(child);
+ if( src==null ) sum.reject("unmapped retained storage at call #"+call._nid);
+ else edge(dst,field.getKey(),src);
+ }
+ }
+ for( Site site : callee._returns ) {
+ Set<Site> returned=map.get(site);
+ if( returned==null ) sum.reject("unmapped returned storage at call #"+call._nid);
+ else result.addAll(returned);
+ }
+ return result;
+ }
+
+ @Override public String toString() {
+ StringBuilder out = new StringBuilder("Allocation destinations (analysis only; no stack lowering)\n");
+ for( Summary sum : _postorder ) {
+ out.append("\n+-- ").append(sum._fun.label()).append("\n");
+ ArrayList<CallNode> calls=new ArrayList<>(sum._calls);
+ calls.sort(Comparator.comparingInt(n -> n._nid));
+ for( CallNode call : calls ) {
+ Summary callee=target(call);
+ out.append("| call#").append(call._nid).append(" -> ")
+ .append(callee==null ? "?" : callee._fun.label()).append("\n");
+ }
+ if( !sum.supported() ) {
+ out.append("`-- REJECT: ").append(sum._reject).append("\n");
+ continue; // Do not display a partial plan as a safe placement.
+ }
+ ArrayList<Site> sites=new ArrayList<>(sum._sites);
+ sites.sort(Comparator.comparing(s -> s._name));
+ for( Site site : sites ) {
+ out.append("| [").append(site.destination()).append("] ").append(site._name);
+ if( site._allocation!=null ) out.append(" (").append(site._bytes).append(" bytes)");
+ out.append("\n");
+ // Stable debugging order belongs here, not in the analysis maps.
+ ArrayList<String> edges=new ArrayList<>();
+ for( var field : site._fields.entrySet() ) for( Site child : field.getValue() )
+ edges.add("| ."+field.getKey()+" --> "+child._name+"\n");
+ Collections.sort(edges);
+ for( String edge : edges ) out.append(edge);
+ }
+ out.append("`-- return");
+ ArrayList<String> returns=new ArrayList<>();
+ for( Site site : sum._returns ) returns.add(site._name);
+ Collections.sort(returns);
+ for( String name : returns ) out.append(" -> ").append(name);
+ out.append("\n");
+ }
+ return out.toString();
+ }
+}
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index 51a6a197..f38305b2 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -27,6 +27,7 @@ public class CodeGen {
Opto, // SCCP, numeric modes, seed the peephole worklist
IterPostOpto, // Peepholes and inlining using SCCP results
FinalizeIR, // Field layout, offset cleanup, function/CU roots
+ Allocation, // Symbolic allocation destinations; analysis only
TypeCheck, // Last check for bad programs
Serialize, // Save ideal IR, including opaque class initialization
Lower, // Expand checked class initialization to ordinary IR
@@ -196,6 +197,7 @@ public class CodeGen {
step(target, Phase.IterPostOpto, this::iterPostOpto, dump);
// Field layouts; field symbols become constant offsets
step(target, Phase.FinalizeIR, this::finalizeIR, dump);
+ step(target, Phase.Allocation, this::allocation, dump);
// Final error check - bad programs fail here
step(target, Phase.TypeCheck, this::typeCheck, dump);
// Save reloadable ideal IR for a later seperate compilation
@@ -518,7 +520,18 @@ public class CodeGen {
// ---------------------------
// Last check for bad programs
- public CodeGen typeCheck() { return phase(Phase.TypeCheck, _phase==Phase.FinalizeIR, () -> TypeCheck.run(this)); }
+ public Allocation _allocation;
+ public CodeGen allocation() {
+ return phase(Phase.Allocation, _phase==Phase.FinalizeIR, () -> {
+ _allocation = new Allocation(this);
+ if( Boolean.getBoolean("simple.alloc.dump") ) System.out.print(_allocation);
+ if( Boolean.getBoolean("simple.alloc.check") ) _allocation.requireSupported();
+ });
+ }
+ public CodeGen typeCheck() {
+ if( _phase==Phase.FinalizeIR ) allocation();
+ return phase(Phase.TypeCheck, _phase==Phase.Allocation, () -> TypeCheck.run(this));
+ }
// ---------------------------
// TypeCheck queued surviving CLInits during its existing error walk.
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 0569f352..be22e68a 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -86,6 +86,7 @@ public class ConstantNode extends TypeNode {
}
@Override public boolean isConst() { return true; }
+ @Override public boolean isFunLeaf() { return true; }
@Override public Type compute() { return _con; }
@Override public Node idealize() { return null; }
}
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/FunNode.java
index 8b6b347e..632b5fb4 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/FunNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/FunNode.java
@@ -83,6 +83,8 @@ public class FunNode extends RegionNode {
}
public ParmNode rpc() { return parm(0); }
+ @Override public boolean isFunLeaf() { return true; }
+
// An unloaded body's Summary is constructed before every other user.
public SummaryNode summary() { return nOuts()>0 && out(0) instanceof SummaryNode summary ? summary : null; }
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java
index 82053fd8..5e803510 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java
@@ -41,6 +41,7 @@ public class FunPtrNode extends TypeNode {
}
@Override public boolean isConst() { return true; }
+ @Override public boolean isFunLeaf() { return true; }
@Override public Type compute() {
ReturnNode ret = ret();
if( ret == null ) return _con;
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter33/src/main/java/com/seaofnodes/simple/node/Node.java
index ad4f47e0..3688d6ea 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -154,6 +154,11 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
public boolean isConst() { return false; }
+ // Stop a backward, function-local input walk here. Entry/caller links,
+ // constant anchors, and opaque summaries are not part of the local body.
+ // This is not a CFG-exit or serialization-boundary predicate.
+ public boolean isFunLeaf() { return false; }
+
// ------------------------------------------------------------------------
// Graph Node & Edge manipulation
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/ParmNode.java
index aea402f6..c61d87b7 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/ParmNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/ParmNode.java
@@ -49,6 +49,8 @@ public class ParmNode extends PhiNode {
public FunNode fun() { return (FunNode)in(0); }
+ @Override public boolean isFunLeaf() { return true; }
+
// The hidden constructor receiver has private memory for checking reads.
// Only borrowed source parameters need an initially empty field promise.
private Type declaredBound() {
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 36583884..bfabbb92 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -35,6 +35,8 @@ public class StartNode extends LoopNode implements MultiNode {
@Override public Tag serialTag() { return Tag.Start; }
public Type arg() { return _arg; }
+ @Override public boolean isFunLeaf() { return true; }
+
@Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
return p.p(label());
}
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/SummaryNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/SummaryNode.java
index 5b945457..07e16eae 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/SummaryNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/SummaryNode.java
@@ -20,6 +20,7 @@ public class SummaryNode extends CFGNode implements MultiNode {
}
@Override public String label() { return "Summary"; }
+ @Override public boolean isFunLeaf() { return true; }
@Override public boolean blockHead() { return true; }
@Override public Type compute() {
if( in(0)._type.isHigh() ) return TypeTuple.STATE.dual();
diff --git a/chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java b/chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java
new file mode 100644
index 00000000..ff313c7e
--- /dev/null
+++ b/chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java
@@ -0,0 +1,223 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.*;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+/** Small allocation poster children. Keep calls visible: this tests summaries,
+ * not whether an inliner happens to put the allocations in the right function. */
+public class Chapter33Test {
+ private static final String THING = """
+ struct Thing {
+ i64 x;
+ new Thing = { i64 x -> self.x=x; };
+ };
+ val read_noInline = { Thing t -> t.x; };
+ """;
+
+ private static CodeGen compile(String source) {
+ return new CodeGen(source).driver(CodeGen.Phase.TypeCheck);
+ }
+
+ private static List<Allocation.Site> allocations(Allocation.Summary sum, String type) {
+ sum.requireSupported();
+ var sites = new ArrayList<Allocation.Site>();
+ for( var site : sum._sites )
+ if( site._allocation!=null && site._allocation._ts._name.endsWith("."+type) )
+ sites.add(site);
+ return sites;
+ }
+
+ // 1. A call borrows a temporary. The caller can reclaim it on return.
+ @Test public void testAllocationLocalFrame() {
+ CodeGen code = compile(THING+"""
+ val work_noInline = { i64 n ->
+ val t=new Thing(n);
+ return read_noInline(t);
+ };
+ return work_noInline(arg);
+ """);
+ var sites = allocations(code._allocation.summary("work_noInline"),"Thing");
+ assertEquals(1,sites.size());
+ assertEquals("frame",sites.get(0).destination());
+ assertEquals("17",Eval2.eval(code,17));
+ }
+
+ // 2. A factory returns a graph through another factory. Both objects need
+ // result destinations, but the final consuming caller owns them locally.
+ @Test public void testAllocationFactoryGraph() {
+ CodeGen code=compile(THING+"""
+ struct Box {
+ Thing child;
+ new Box = { Thing child -> self.child=child; };
+ };
+ val make_noInline = { i64 n -> new Box(new Thing(n)); };
+ val forward_noInline = { i64 n -> make_noInline(n); };
+ val use_noInline = { Box b -> b.child.x; };
+ val work_noInline = { i64 n -> use_noInline(forward_noInline(n)); };
+ return work_noInline(arg);
+ """);
+ for( String name : new String[]{"make_noInline","forward_noInline"} ) {
+ var sum = code._allocation.summary(name);
+ assertEquals("result",allocations(sum,"Box" ).get(0).destination());
+ assertEquals("result",allocations(sum,"Thing").get(0).destination());
+ }
+ var work = code._allocation.summary("work_noInline");
+ assertEquals("frame",allocations(work,"Box" ).get(0).destination());
+ assertEquals("frame",allocations(work,"Thing").get(0).destination());
+ assertEquals("23",Eval2.eval(code,23));
+ }
+
+ private static final String HOLDER = """
+ struct Holder { Thing !c = new Thing(0); };
+ """;
+
+ // 3. A fresh reference escapes through a parameter, not the return value.
+ @Test public void testAllocationStoreThroughArgument() {
+ CodeGen code=compile(THING+HOLDER+"""
+ val fill_noInline = { !Holder h, i64 n -> h.c = new Thing(n); return n; };
+ val work_noInline = { i64 n ->
+ val h = new Holder;
+ fill_noInline(h,n);
+ return h.c.x;
+ };
+ return work_noInline(arg);
+ """);
+ var fill = allocations(code._allocation.summary("fill_noInline"),"Thing");
+ assertEquals(1,fill.size());
+ assertEquals("arg3",fill.get(0).destination()); // arg2 is the class receiver
+ for( var site : allocations(code._allocation.summary("work_noInline"),"Thing") )
+ assertEquals("frame",site.destination());
+ assertEquals("31",Eval2.eval(code,31));
+ }
+
+ // 4. One shared factory, two call sites, two unrelated destinations.
+ @Test public void testAllocationSeparateDestinations() {
+ CodeGen code=compile(THING+HOLDER+"""
+ val make_noInline = { i64 n -> new Thing(n); };
+ val fill_noInline = { !Holder a, !Holder b, i64 n ->
+ a.c = make_noInline(n);
+ b.c = make_noInline(n+1);
+ return n;
+ };
+ val a = new Holder, b = new Holder;
+ fill_noInline(a,b,arg);
+ return a.c.x*10+b.c.x;
+ """);
+ var sites=allocations(code._allocation.summary("fill_noInline"),"Thing");
+ assertEquals(2,sites.size());
+ assertNotEquals(sites.get(0)._name,sites.get(1)._name);
+ var destinations=new ArrayList<String>();
+ for( var site : sites ) destinations.add(site.destination());
+ Collections.sort(destinations);
+ assertEquals(List.of("arg3","arg4"),destinations);
+ assertEquals("45",Eval2.eval(code,4));
+ String dump=code._allocation.toString();
+ assertTrue(dump.contains("[arg3]"));
+ assertTrue(dump.contains(".c -->"));
+ assertTrue(dump.indexOf("+-- make_noInline\n") < dump.indexOf("+-- fill_noInline\n"));
+ }
+
+ // A join requires BOTH possible owners; it must not pick whichever input
+ // happens to be visited first. Alias actual arguments at a call as well.
+ @Test public void testAllocationConditionalAndAliasedOwners() {
+ CodeGen code=compile(THING+HOLDER+"""
+ val fill_noInline = { !Holder a, !Holder b, i64 n ->
+ val h=n ? a : b;
+ h.c=new Thing(n);
+ return n;
+ };
+ val a=new Holder, b=new Holder;
+ fill_noInline(a,b,arg);
+ fill_noInline(a,a,arg+1);
+ return a.c.x;
+ """);
+ var sites=allocations(code._allocation.summary("fill_noInline"),"Thing");
+ assertEquals(1,sites.size());
+ assertEquals("arg3 & arg4",sites.get(0).destination());
+ assertEquals("8",Eval2.eval(code,7));
+ }
+
+ @Test public void testAllocationBorrowAndObjectCycle() {
+ CodeGen borrow=compile(THING+"""
+ val choose_noInline={ Thing a, Thing b, i64 n -> n ? a : b; };
+ return read_noInline(choose_noInline(new Thing(arg),new Thing(arg+1),arg));
+ """);
+ var choose=borrow._allocation.summary("choose_noInline").requireSupported();
+ assertEquals(2,choose._returns.size());
+ var destinations=new ArrayList<String>();
+ for( var site : choose._returns ) {
+ assertNull(site._allocation);
+ destinations.add(site.destination());
+ }
+ Collections.sort(destinations);
+ assertEquals(List.of("result & arg3","result & arg4"),destinations);
+ assertEquals("1",Eval2.eval(borrow,0));
+
+ CodeGen cycle=compile("""
+ struct Link { Link? !next; i64 x; new Link={ i64 n -> x=n; }; };
+ val cycle_noInline={ i64 n ->
+ val a=new Link(n), b=new Link(n+1);
+ a.next=b;
+ b.next=a;
+ return a;
+ };
+ return cycle_noInline(arg).x;
+ """);
+ var sites=allocations(cycle._allocation.summary("cycle_noInline"),"Link");
+ assertEquals(2,sites.size());
+ for( var site : sites ) assertEquals("result",site.destination());
+ assertEquals("9",Eval2.eval(cycle,9));
+ }
+
+ // Scalar results must not hide allocations when arithmetic is skipped.
+ @Test public void testAllocationScalarArrayUse() {
+ CodeGen code=compile("""
+ val work_noInline={ i64 n ->
+ val a=new i64[2];
+ a[0]=n;
+ return a[n&1]+n*n;
+ };
+ return work_noInline(arg);
+ """);
+ var sum=code._allocation.summary("work_noInline").requireSupported();
+ int arrays=0;
+ for( var site : sum._sites )
+ if( site._allocation!=null && site._allocation._ts.isAry() ) {
+ arrays++;
+ assertEquals("frame",site.destination());
+ }
+ assertEquals(1,arrays);
+ assertEquals("25",Eval2.eval(code,5));
+ assertEquals("20",Eval2.eval(code,4));
+ }
+
+ // Make unsupported plans explicit, without replacing existing TypeCheck
+ // diagnostics or changing the allocator used by older chapter tests.
+ @Test public void testAllocationRejectedPlans() {
+ String[] sources={
+ "val bad_noInline={ i64 n -> n ? bad_noInline(n-1) : 0; }; return bad_noInline(arg);",
+ "val bad_noInline={ i64 n -> i64 s=0; while(n>0) { s+=n; n--; } return s; }; return bad_noInline(arg);",
+ "val bad_noInline={ i64 n -> new int[n]; }; return bad_noInline(arg);",
+ THING+HOLDER+"val bad_noInline={ Holder h -> h.c; }; return bad_noInline(new Holder);",
+ "{ i64 -> i64 } native=\"C\"; val bad_noInline={ i64 n -> native(n); }; return bad_noInline(arg);",
+ "val bad_noInline={ -> val a=new int[2]; i64 raw=a; return raw+17; }; return bad_noInline();",
+ "val bad_noInline={ int[] a -> i64 raw=a; return raw+17; }; return bad_noInline(new int[2]);"
+ };
+ String[] reasons={"recursive", "loop destinations", "variable-size", "LoadNode", "opaque", "raw address", "raw address"};
+ for( int i=0; i<sources.length; i++ ) {
+ CodeGen code=compile(sources[i]);
+ var sum=code._allocation.summary("bad_noInline");
+ assertFalse(sum.supported());
+ assertTrue(sum._reject,sum._reject.contains(reasons[i]));
+ try { sum.requireSupported(); fail("Rejected plan was usable"); }
+ catch( IllegalStateException expected ) {
+ assertTrue(expected.getMessage().contains(reasons[i]));
+ }
+ assertTrue(code._allocation.toString().contains("REJECT:"));
+ }
+ }
+}
diff --git a/chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java b/chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java
index 6505009d..b94b4f2c 100644
--- a/chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java
+++ b/chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java
@@ -27,7 +27,7 @@ public class PhaseTest {
code.driver(Phase.TypeCheck); // A repeated request does not rerun anything.
assertEquals("45",Eval2.eval(code,10));
code.driver(Phase.LocalSched);
- assertEquals("Parse Iter Opto IterPostOpto FinalizeIR TypeCheck LoopTree Unlink Schedule LocalSched",
+ assertEquals("Parse Iter Opto IterPostOpto FinalizeIR Allocation TypeCheck LoopTree Unlink Schedule LocalSched",
String.join(" ",phases));
assertNull(code._serial);
assertNull(code._mach);