From c201515eeb2e99cb6f0e820459662affc047c2ce Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 20 Nov 2026 15:26:44 -0800 Subject: Basic first implementation 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. --- chapter33/README.md | 87 ++- .../com/seaofnodes/simple/codegen/Allocation.java | 397 +++++++++++ .../com/seaofnodes/simple/codegen/CodeGen.java | 15 +- .../com/seaofnodes/simple/node/ConstantNode.java | 1 + .../java/com/seaofnodes/simple/node/FunNode.java | 2 + .../com/seaofnodes/simple/node/FunPtrNode.java | 1 + .../main/java/com/seaofnodes/simple/node/Node.java | 5 + .../java/com/seaofnodes/simple/node/ParmNode.java | 2 + .../java/com/seaofnodes/simple/node/StartNode.java | 2 + .../com/seaofnodes/simple/node/SummaryNode.java | 1 + .../java/com/seaofnodes/simple/Chapter33Test.java | 223 ++++++ .../test/java/com/seaofnodes/simple/PhaseTest.java | 2 +- docs/automatic-memory-management-survey.md | 777 ++++++++++++++++++++- docs/roadmap.md | 85 ++- skills/chapter25-codex-notes.md | 76 +- 15 files changed, 1652 insertions(+), 24 deletions(-) create mode 100644 chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java create mode 100644 chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java 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 _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> _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 _sites = new ArrayList<>(); + public final HashSet _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 _nodes = new ArrayList<>(); + // Just the Calls + private final ArrayList _calls = new ArrayList<>(); + // Pointer expression -> possible storage objects, in this function's vocabulary. + private final IdentityHashMap< Node,HashSet> _values = new IdentityHashMap<>(); + // Call -> returned storage after substituting actuals and importing effects once. + private final IdentityHashMap> _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 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 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 work=new ArrayDeque<>(sum._sites); + while( !work.isEmpty() ) { + Site src = work.pop(); + for( Set 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 set(Site site) { + HashSet set = new HashSet<>(); set.add(site); return set; + } + + private static void edge(Set dst, String field, Set 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 refs(Summary sum, Node n) { + if( !pointer(n) ) return new HashSet<>(); + HashSet old = sum._values.get(n); + if( old!=null ) return old; + HashSet 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 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 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 compose(Summary sum, CallNode call) { + HashSet 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> 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 dst=map.get(site); + if( dst==null ) continue; + for( var field : site._fields.entrySet() ) for( Site child : field.getValue() ) { + Set 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 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 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 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 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 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 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 _print1(ExprPrinter 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 allocations(Allocation.Summary sum, String type) { + sum.requireSupported(); + var sites = new ArrayList(); + 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(); + 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(); + 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 Complex from as } +{ (*Complex)[] as, (*Complex)[] bs -> Complex from (as | bs) } +``` + +The first signature permits returning an interior reference such as `&as[i]`. +The second permits either argument as the source; their lifetimes need not +be equal. The caller accounts for all possible sources unless it can establish +which source applies. Names in `from` must resolve to named parameters of that +signature; no separate declaration of lifetime variables is required. + +For a Complex containing only numeric coordinates, returning `*Complex` +copies the value and requires no borrowed-result relationship: + +```text +{ (*Complex)[], (*Complex)[] -> *Complex } +``` + +Copies of object values containing reference fields still preserve those +references' lifetime obligations. A written contract is checked against the +body, not trusted, and does not silently extend allocations to make it fit. +Visible bodies infer relationships when omitted; separately compiled metadata +preserves inferred contracts. This syntax is agreed but not implemented. + +For now, FFI functions may not directly return borrowed interior references +into Simple objects. Array-oriented native adapters can return an index or +range; Simple performs checked access and forms the reference, making its +origin visible to the compiler. Bindings returning interior field references +are deferred until a use case warrants revisiting the restriction. This limits +the available FFI contracts without introducing a separate lifetime system. + +### Still open + +The delete/recycling policy is largely settled above. Remaining language-design +questions concern the automatic lifetime system: + +Cliff wants to settle these language choices before designing the analysis. +"How are we tracking this?" is explicitly deferred: representation of lifetime +constraints, path-sensitive escape information, loop-exit winners, recursive +summaries, and reclamation checkpoints are not selected implementation designs. +First settle the programmer-visible ownership and lifetime rules below. + +- Allocation-destination analysis: implement the agreed inferred placement, + named lexical scopes, top-level regions, and destination forwarding through + factories. The source-level choice is settled; tracking it remains deferred. +- Apply the agreed growth threshold (unknown loop bound, bound greater than 10, + or recursion) to repeated allocation that accumulates in an inferred owner, + distinguishing temporary storage reclaimed each iteration or activation. + Specify stable bound analysis and how loop-exit winners retain storage without + retaining failed candidates. Apply the selected destination syntax through + factories without annotating every helper. + Errors should identify the accumulating allocation, retaining owner, and + repetition, then show the explicit destination choices. +- References across regions: allowed stores, returns, and retained views; + proving that reclamation leaves no accessible dangling storage, including + historical pointer values permitted after delete. The safety obligation is + settled; its enforcement remains part of the deferred analysis design. +- Remaining function-contract syntax and enforcement: returned-borrow `from` + syntax is settled above; retention, destination, and growth interface + spellings remain. Implement the agreed relationships + and borrowing default across direct calls, separate compilation, and indirect + calls, including the written FFI types for native functions. Define useful + diagnostics and rewrite paths when a proof fails. +- Array-layout details: spell selectable length widths and construction/append + for the combined struct-and-tail type. Fixed-buffer notation, embedded object + access, and scope-based finishing are settled below. Any shrinking or + reconstruction operations need explicit reference-validity rules; they are + not implied by append or whole-object assignment. + +Implementation obligations, rather than new permission to change semantics: + +- Audit optimizer freshness assumptions, historical reads, pointer equality, + and initialization tracking under aliasable construction. +- Implement real array bounds checks, eliminating them only with adequate + proofs. Cliff notes the current unchecked accesses; memory safety is an + intended guarantee, not a claim about the current compiler. +- Specify concrete syntax and runtime metadata for the agreed lifetime and + recycling rules after the remaining lifetime choices are settled. + +### Node-construction check — 2026-11-17 + +Cliff asked whether Simple's IR Nodes actually have recursive constructors, +rather than merely nested constructor expressions in argument lists. Inspection +of Chapter 33's Java sources found: + +- The ideal-IR constructors inspected do not construct other Nodes. The base + [Node constructor](../chapter33/src/main/java/com/seaofnodes/simple/node/Node.java) + creates its edge arrays and installs use edges. Constructor worklist additions + enqueue work rather than running peepholes recursively. +- Some machine constructors do construct other concrete Node classes. For example, + [NegFX86](../chapter33/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NegFX86.java) + creates a ConstantNode and FltX86 inside its constructor body. ExtendX86, + ExtendARM, and ExtendRISC create projection/parameter nodes in delegating + constructor arguments. No path back into the same concrete Node constructor + was found in this inspection; this is not a whole-program proof. +- `new AddNode(new MulNode(...), ...)` finishes constructing its argument before + entering AddNode's constructor. Reserving/protecting the outer pool slot after + argument evaluation avoids making that expression overlap pool construction. +- Cyclic graph topology is distinct from recursive construction. Completed + Nodes can be wired into cycles afterward; deleting cyclic graph nodes need + not be forbidden merely to simplify construction tracking. +- A Simple port has a separate publication issue: Node's base constructor calls + `n.addUse(this)` on its inputs before the concrete subclass finishes. + CallNode also registers itself in the global call list. If these containers + are deletable, they cannot retain the incomplete receiver under the base + rule. Moving reverse-edge wiring and registration after full construction + provides a straightforward rewrite, without banning graph cycles. + +A pool-wide busy bit cannot identify which slot is under construction. Ignoring +all deletions in that pool while busy would be a broader semantic policy than +the agreed per-slot rule. With at most one active construction per class-pool, +a nullable current-slot pointer suffices to identify that object. Reentrant +construction can instead use temporary constructor-frame records; delete can +search those records, with cost proportional to active construction depth. +Cliff accepted a short stack of construction pointers as the base approach; +the single-pointer case remains a possible optimization. + +## Original survey There are several approaches worth inspecting. For Simple, I would give the closest attention to inferred regions, Lobster-style ownership inference with an RC fallback, and ownership of whole object graphs. Goose is particularly useful because it shows how much cheaper memory management can become when the language constrains storage layout and lifetimes together. @@ -432,3 +792,416 @@ Without `delete` the rules are as-is. With delete some things change: nested iner-locking allocations. -------------------------------------------------------- + +## Follow-up: syntax choices — 2026-11-18 + +There are several choices, but most should appear only where inference needs +help. Here is the inventory, with illustrative spellings, not proposed final +grammar. + +### 1. Allocation destination + +Keep ordinary allocation unchanged: + +```text +new Thing(args) // inferred destination +new Thing(args) in pool // explicit destination +new Thing(args) in stack // explicitly accept default-stack retention +``` + +We need to decide whether destination selection attaches to one allocation, +a surrounding block, or both. A block default would avoid repeating +annotations, but must propagate sensibly through factory calls. Also, `stack` +must mean the appropriate owning frame, not necessarily the frame executing +`new`. + +### 2. Pool declaration and lifetime + +We need a way to declare a global or lexical pool and name it as a destination. +Separate choices include: + +- Whether a pool serves one class or multiple types. +- How to request a dedicated growth space. +- Whether lexical exit is sufficient initially, or we also expose explicit + early reclamation. + +These can largely be library operations, although the compiler must understand +their lifetime effects. + +### 3. Growing arrays and finishing + +We need to distinguish an in-place growing array from an ordinary fixed-length +array. For example: + +```text +val a = new Pixel[grow]; +a.push(pixel); +finish(a); +``` + +The choices are: + +- A type suffix versus a constructor or builder type. +- Whether append uses ordinary method syntax. +- Whether `finish(a)` is a statement, or returns a fixed-length view: + `val b = finish(a)`. + +I lean toward a finish operation usable without introducing another name. It +changes growth permission for the storage, including aliases; it does not make +elements read-only. Existing `~` access syntax should remain separate. + +Appending inline objects also needs a way to construct the new element directly +in its slot, without requiring an intermediate object and copy. + +### 4. Inline versus separately stored objects + +This is the biggest layout syntax choice. For illustration: + +```text +inline Complex position; // object occupies this field's storage +Complex other; // existing reference field +``` + +Should embedding be chosen per field/type use, declared as a default on +`Complex`, or both? Per-use choice seems necessary: the same type may be +embedded in one place and shared through a reference elsewhere. + +Arrays need the same distinction: + +```text +Complex[] // array of references, under existing conventions +(inline Complex)[] // array containing Complex objects +``` + +Those parentheses are illustrative. Whatever spelling we choose must clearly +distinguish embedding the elements from embedding the array descriptor or a +fixed-capacity array. + +### 5. Value access versus interior-reference access + +For embedded objects, we need to distinguish: + +```text +copy of a[i] +reference to a[i] +``` + +Whether those become `copy(a[i])`, `&a[i]`, an explicit reference type, or +contextual operations is undecided. We also need assignment rules: does +assigning an inline object copy its fields, and what happens to existing +interior references? + +Container-and-index handles can probably be ordinary library types. We should +not make the same syntax silently alternate between a direct reference and a +handle. + +### 6. Lifetime and growth contracts + +Most relationships should be inferred, but external functions and explicit +interfaces need spellings for: + +- Result borrows storage from an argument. +- Argument may be retained in another argument or pool. +- Fresh result uses the caller's destination. +- Function may grow an array, only access it, or finish it. + +These belong in function types or associated declarations. The existing `^` +already denotes incomplete references; I would keep that distinct from lifetime +relationships. + +### 7. Deletable classes + +We need a class qualifier and an operation: + +```text +deletable struct Thing { ... }; +delete(p); +``` + +The exact spelling is small compared with the rules already settled. It should +be apparent from the type that instances permit recycling. + +I would choose inline/reference/value syntax first. It determines field +declarations, array element types, construction, assignment, and function +signatures. Allocation destinations and finish syntax are comparatively +independent and can stay lightweight. + +## Agreed design: embedded objects, values, and references + +Proposed 2026-11-18; reviewed and accepted in full by Cliff on 2026-11-19, +including the fixed-buffer notation. This resolves syntax items (4) and (5) +and builds on the restored [struct-value notes](roadmap.md#struct-values). +None of this is implemented yet; the examples describe the accepted direction, +not programs accepted by the current parser. Array-length and trailing-array +extensions agreed on 2026-11-19 follow at the end of this section. + +### Objects have storage; references identify storage + +Keep `T` as the existing reference type for a struct. Use `*T`, pronounced +"contents of T", for its object value. A field of type `*T` embeds the object; +a local or argument of that type has value semantics. Registers and scalar +replacement remain implementation choices when an address is not observable. + +```text +struct Complex { f64 x, y; }; +struct Example { + Complex ref; // reference to separately owned storage + *Complex value; // two embedded coordinates +}; +``` + +Embedding is chosen at the type use, not forced on every use of the class. +An embedding cycle with no intervening reference is rejected: it would require +an infinitely sized object. Existing access and binding modifiers remain +independent of reference-versus-value representation. + +### Contents, addresses, and copying + +An addressable expression denotes a storage location. Reading that expression +in a value context obtains its value; assignment writes the destination +location; address-taking obtains a reference to the location. This distinction +lets field access avoid first copying the whole enclosing object. + +```text +Complex p = new Complex(args); // construct storage and obtain a reference +Complex q = p; // copy reference; same target +*Complex v = *p; // initialize a new object by copying contents +*Complex w = v; // another object copy +Complex r = &v; // borrow v's existing storage; no allocation +*p = v; // copy contents into p's existing target +``` + +`*p` denotes the target object; `&v` denotes its address. Taking an address +requires existing addressable storage, not an arbitrary temporary expression. +Give a temporary a named owner before borrowing it. Nullable references must +be proven non-null before dereferencing, following the existing safety rules. + +No implicit conversion changes a reference into an object copy or an object +into a reference. `p = v` and `v = p` are type errors. A value copy copies +embedded values recursively and copies reference fields as references; it +does not clone the reachable object graph. Those copied references retain +their original lifetime obligations. + +Field access and method syntax remain uniform: `p.x`, `v.x`, `p.len()`, and +`v.len()`. A method on an addressable object uses that object's storage as its +receiver; the call does not silently copy the receiver. Retaining that receiver +is governed by the ordinary function lifetime contract. + +Preserve the useful binding distinction from the roadmap: + +```text +holder.*c // contents of the reference field: *(holder.c) +(*holder).c // field c of the object referenced by holder +``` + +These are not the same operation. Ordinary prefix `*holder.c` binds as +`*(holder.c)`, with field selection preceding prefix dereference. The `.*` +form makes the field being dereferenced explicit. Dereferencing an already +inline value is an error. The old tentative alternative `ref.c = val.*c` +would therefore not be adopted: it cannot implicitly turn a reference +assignment into an object assignment. + +### Construction and assignment are separate + +Use `new *T(args)` for constructing an object value directly in its +destination, alongside `new T(args)` for constructing storage and returning +a reference. Value results may be constructed in caller-provided storage; +the language need not require a temporary allocation and copy. + +Copy initialization can initialize final fields. Assignment into an existing +object can write only fields permitted at that program point. Thus `*p = v` +is not a back door for changing final fields or writing through read-only +references. Initially reject whole-object assignment when it would overwrite +protected fields; do not silently skip them. + +Whole-object assignment preserves the destination's identity and addresses of +its embedded fields. Existing interior references observe the resulting normal +field updates. Semantically obtain the source value before writing the +destination so overlapping copies do not corrupt the source. Assignment does +not rerun constructors or perform user-defined copy callbacks. + +Ending an object's lifetime and reconstructing its storage is a separate +operation, not an alternative interpretation of assignment. In particular, +reusing a removed vector element's slot must not invalidate surviving interior +references or silently bypass final-field rules. General reconstruction syntax +is outside this proposal. + +### Arrays distinguish element layout from element access + +```text +Complex[] refs; // array of Complex references +(*Complex)[] objects; // array of embedded Complex objects +var a = new *Complex[N]; // allocate embedded element storage +``` + +Elements must still be completely initialized before exposure; the final line +is a layout sketch, not permission to omit required initialization. Array +initializers and append must support construction or copy initialization into +the element destination. Only initialized elements contribute to visible length. + +For an embedded-element array: + +```text +*Complex v = a[i]; // copy the element's value +Complex p = &a[i]; // borrow the element's fixed storage +a[i].x = 3; // update in place +a[i] = v; // whole-object assignment, subject to permissions +``` + +For `Complex[]`, `refs[i]` copies a reference, not a Complex. For `int[]`, +`a[i]` produces an integer value. Indexing itself therefore remains uniform; +the element type determines what is copied in a value context. Bounds checks +apply before access or address-taking. + +Use `&V` as the type of a reference to storage holding +a value of type V. `&(*Complex)` is the existing `Complex` reference type; +`&int` references an integer slot; `&Complex` references a slot that itself +holds a Complex reference. This permits primitive and reference-slot borrowing +without inventing wrapper objects. Nested references carry the corresponding +storage lifetime constraints at each level. + +### Interior references borrow the actual backing storage + +`&a[i]` has a lifetime bounded by that particular array, not by a container +that happens to point to it. `&owner.value` is bounded by the owner's storage. +Creating a reference does not transfer ownership, allocate a copy, or extend +the source lifetime. Several references may alias; no blanket exclusive-borrow +rule is proposed. Access permissions and memory-effect rules still apply. + +A function returning such a reference exposes that origin in its lifetime +contract. Functions can infer it; external declarations must state it. Exact +contract spelling remains item (6). Ordinary direct references need not carry +a runtime owner pointer merely because the checker tracks their origin. + +An array never moves. A vector may select a different backing array. A direct +reference returned into the old array continues to identify the old element; +replacement does not retarget it. The old storage cannot be reclaimed or +recycled while that reference remains usable. Such a reference is not a promise +to follow the vector's current logical element. + +An interface promising a stable reference to a current container element must +instead prevent conflicting relocation during the reference's usable lifetime, +or use a representation that preserves element storage. The implementer chooses +the contract; it must not depend on whether this particular append happened to +fit within capacity. Proven non-relocating operations can be allowed. + +A `(container, index)` handle is an ordinary library value with explicitly +different behavior: it resolves the current storage and checks the current +length on access. Removal or reordering may change which element it identifies; +it does not promise persistent element identity. + +### Embedded small vectors + +The descriptor is an embedded object. Its small fixed buffer also needs an +embedded layout. The accepted extension of the same type notation is: + +```text +T[4] // reference to an array with fixed extent 4 +*(T[4]) // the fixed array itself, embedded in its owner +(*T)[4] // reference to an array of four embedded T objects +``` + +The parentheses distinguish embedding the array from embedding its elements. +An embedded array followed by other storage needs a statically known extent; +a dynamic trailing array is the additional layout described below. The fixed +extent can make a stored length redundant. Bounds checks still apply. This +fixed-buffer spelling was accepted on 2026-11-19 and is not part of the older +recovered notes. + +A Node can then embed vector descriptors and small arrays of Node references. +Reading a small element needs no separately allocated descriptor or backing +array. Overflow uses a backing pointer. Initially the fixed buffer and overflow +pointer can coexist; sharing their bytes would require a safely discriminated +layout, which is not needed to obtain the main indirection savings. + +Reference-valued `get` returns the stored Node reference and does not borrow +the vector slot. Value-valued `get` copies the embedded element. Direct slot +borrowing should be a separately named library operation with an explicit +storage contract; current indexing syntax need not gain overloads to implement +the first vector library. + +### Interaction with delete + +An embedded object cannot be independently deleted: its storage belongs to its +owner, not to a separately recyclable slot. This must be checked from allocation +origin even if a borrowed reference has nominal type T and T permits deletion. +Deleting the containing object, when permitted, affects the whole slot. + +Consequently, an embedded child of a deletable owner inherits the possibility +of stale aliases and reconstruction, even if the child's nominal class is not +deletable. Its constructor cannot assume private memory merely from that class. +The prohibition on publishing incomplete references into deletable storage +also applies through embedded fields. Final-field reads through old interior +references follow the containing slot's post-delete rules. + +Likewise, recycling a vector's old backing storage requires proving that no +usable references remain, including references recoverable through permitted +historical fields of a deletable owner. Merely replacing its backing pointer +does not establish that proof. + +These are necessary consequences of embedding in recyclable storage, not a +proposal to weaken the existing type-safety or initialization guarantees. + +### Array length is separate from element storage + +Agreed addition, 2026-11-19: an embedded array's logical length and its element +data are separate layout components. Embedding must not force a four-byte +length header immediately before every buffer. A containing object can carry +the length separately from the inline elements. Fixed-buffer extent, a +container's used length, and any overflow capacity remain distinct quantities. + +For `*(T[4])`, the array extent is the constant four. Constant propagation can +fold uses of that extent. Eliminating the redundant physical length field is +future work (possibly dead-field elimination); it is not part of the current +implementation task. A vector using that buffer can still have a separate +changing used length between zero and four. + +Lengths need not occupy four bytes. A short-string representation can select +a one-byte unsigned length, for example. Each array representation has a known +maximum element count; an unsigned one-byte length supports a maximum of 255. +Allocation and growth must respect that maximum as well as any applicable +storage capacity. Preventing length wrap or truncation is a consequence of +enforcing the maximum, not a separate array rule. The length's storage width +is part of the layout contract, and access must use that representation. +The exact declaration spelling and conversions +between layouts remain to be specified; a universal four-byte header must not +be assumed by the design. + +### A uniform struct with an array tail + +Agreed addition, 2026-11-19: support a single object containing fixed named +fields followed by a variable-length array tail. The object supports named +field access and array access; no separately allocated backing array or wrapper +is required. The tail is physically last and may grow until finalized under +the same scope-based growth rules as other in-place growing arrays. + +The older roadmap's field notation is a useful syntax candidate, not a newly +settled spelling: + +```text +struct ShortText { + // Other fixed named fields may precede the tail. + u8 #; // compact logical length + u8 []; // trailing byte elements in this same object +}; +``` + +An unsigned one-byte length gives this representation a known maximum of 255 +elements; a wider length can support a larger maximum. An open tail has a +changing length up to that maximum, rather than a fixed declared element count. +Named fields retain their offsets while the tail extends. Newly +appended elements must be initialized before becoming accessible. Indexing is +checked against the current logical length. + +Finalization ends tail growth without moving the object or making its mutable +fields read-only. The resulting storage can survive the creating scope when +its inferred or explicit destination permits that lifetime. Interior references +remain tied to the same storage. The layout planner must preserve room for +physical growth; this type cannot silently relocate merely because a container +with replaceable backing storage could do so. + +This generalizes embedded arrays to a dynamic final field. It does not permit +arbitrary variable-sized fields followed by other fields, and it does not add +array deletion. How to spell construction and append for the combined type, +and whether any combined type may independently opt into class deletion, +remain explicit follow-up questions; neither follows just from the layout. diff --git a/docs/roadmap.md b/docs/roadmap.md index 075780ad..e012eae3 100644 --- a/docs/roadmap.md +++ b/docs/roadmap.md @@ -372,6 +372,12 @@ design candidate, independent of compact pointer storage. ### Structs with trailing arrays +Chapter 33 selected the combined struct-and-array layout on 2026-11-19: +fixed named fields followed by a tail that can grow until finalized. Length +and element storage are separate layout components, and length widths may be +smaller than four bytes. See the [accepted design](automatic-memory-management-survey.md#array-length-is-separate-from-element-storage). +The declarations below remain syntax sketches, not implemented features. + Allow named fields followed by an array length and inline element storage: ```simple @@ -392,10 +398,10 @@ overhead. Arrays with different length representations would be distinct types, with explicit conversions and capacity checks. The spelling and alignment rules remain to be decided. -Growing such an object requires a replacement allocation. An extra level of -indirection, as in a growable-buffer wrapper, instead preserves the wrapper's -identity. Specify ownership before treating a growing call as consuming or -freeing its receiver. +The selected in-place growth model preserves the object's address while its +tail grows, then fixes its extent at finalization. It requires suitable growth +space. A wrapper with replaceable backing storage remains a separate container +choice; it cannot silently replace an object's stable-storage promise. ### String libraries @@ -418,13 +424,66 @@ buffer helpers provide the basic builder and formatting operations. ### Struct values -Allow a struct to be stored inline in another object, array, or argument list -rather than always through a reference. A proposed `*Complex` or `inline` -spelling would place both coordinates of `struct Complex { f64 x,y; };` -directly in the containing value. +The original "Structs can be inlined" proposal below is restored from commit +`69e4a21f71aca4954469063387063434af35e679`, before the roadmap cleanup. +Its examples retain the original syntax and proposed pointer size. The current +Chapter 33 design allows interior references bounded by their storage's +lifetime, superseding the older address-taking restriction below. The placement +of `*` reflects what it binds to; the original spellings are preserved. + +Cliff accepted the expanded [object/value/reference design](automatic-memory-management-survey.md#agreed-design-embedded-objects-values-and-references) +on 2026-11-19, including `*(T[4])` for embedded fixed buffers. That design is +the current decision; the historical proposal below remains for its examples. + +Structs are normally by-reference, but can be converted to by-value by using +the `*` operator, pronounced "contents of" (this name might be changed to +e.g. `inline`). + +This is a name-space change only, you cannot take the address of the internal +struct without entirely consuming its lifetime. No "escaping". + +```java +// 2 64-bit words, no other overheads +struct Complex { f64 x,y; val len = { ->Math.sqrt(x*x+y*y); }; }; -Define whole-value copying, reference-to-value conversion, and assignment -through an existing reference. A value must not silently become a reference -or expose an interior address with an invalid lifetime. Decide how consuming -an enclosing object's lifetime could permit such an address. Keep method -syntax uniform and define the calling convention for by-value arguments. +// Current Simple rules: always by-reference +struct ByRef { + !Complex !c; // 4-byte pointer to a Complex +}; +print(new ByRef.c.y); // Lookup requires 1 extra memory load from ref to c + +// New behavior: by value (inlining a struct) +// The '*' syntax indicator can be something else, e.g. a keyword "inline" +// I am pronouncing '*' as "contents of" +struct ByValue { + *!Complex !c; // c is inlined, full 16 bytes into ByValue +}; +print(new ByValue.c.y); // x,y inlined into ByValue, no extra memory load + +// Mixing Refs and Struct Values. Basically, a ref can be converted +// to a value by taking the "contents of" the ref, and values cannot +// be *converted* to a ref, although they can be copied over a ref. +ref. c = val.c; // Error, mixing refs and values +ref.*c = val.c; // Allowed, whole structure copy. Does not allocate, requires ref.c not-null +val. c = ref.c; // Error, mixing refs and values +val. c = *ref.c; // Allowed, whole structure copy +ref. c = ref.c; // Allowed, pointer copy +val. c = val.c; // Allowed, whole structure copy. +val *c = val.c; // Error, cannot take "contents of" a value + +// Alternative syntax, to avoid the "contents of" being on LHS and field applying to being on RHS: +ref.c = val.*c; // Assign into ref.c the "contents of" val.c + +// Arrays of inlined structures +var ary = new *Complex[99]; // Array of 99 !Complex !objects, inlined + +// Calling methods has the same syntax +ref.c.len(); +val.c.len(); + +// Function arguments use the same typing, so can pass-by-value +val math.sin = { *Complex c -> ... }; // Passes a complex by value +math.sin(ref.*c); // Requires de-reference to pass by value +math.sin(val. c); // Pass by value + +``` diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index 5ba1943c..2c327292 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -37,9 +37,77 @@ callers promise no initialized fields. No new passes or backward demand walks. Cliff closed Chapter 32 and requested `ch32` rebased onto `main`, then a new complete snapshot on branch `ch33`. Continue in `chapter33/`. Cliff selected -automatic memory management as the next topic, with the design still open. -The latest request is cleanup and preparation for that task, not implementation. -Do not treat earlier roadmap sketches as a chosen lifetime mechanism. +automatic memory management as the next topic. On 2026-11-19 Cliff requested +the first analysis pass after Opto and before TypeCheck, few new classes, +ASCII debugging, conservative rejections, and 3-4 poster children. The agreed decisions and remaining +questions are in [the survey's base design](../docs/automatic-memory-management-survey.md#agreed-base-design--2026-11-17). +The initial implementation is `codegen/Allocation.java`, after FinalizeIR and +before TypeCheck. One call-DAG DFS composes symbolic summaries in postorder; +local reference-edge closure uses a worklist. Four poster children and boundary +checks live in Chapter33Test. The phase is analysis-only: existing allocation +lowering is unchanged. `simple.alloc.dump` prints ASCII, `simple.alloc.check` +requires all plans to be supported; otherwise unsupported summaries record a +rejection without blocking the existing allocator. Loops, SCCs, variable sizes, +opaque calls, raw addresses, and unresolved pointer-load origins are deferred. +No new language syntax or serialized lifetime summaries are implemented yet. +Update 2026-11-19: Cliff accepted the entire +[embedded-object design](../docs/automatic-memory-management-survey.md#agreed-design-embedded-objects-values-and-references), +including `*T` object values, `&` interior references, and `*(T[4])` embedded +fixed buffers. Length and element storage are separate layout components; +length widths may be smaller than four bytes. Each array representation has a +known maximum element count; preventing length wrap follows from enforcing +that maximum, rather than being the primary semantic rule. Removing constant length fields +is future work, not an implementation request. A uniform struct with fixed +named fields and a growing final array tail is also selected; exact tail and +length-width syntax remains open. The tail grows until scope-based finishing. +Placement uses `new(destination) T(args)`; `region` declarations are top-level +only and denote program-lifetime storage with no language-level size bound. +Labeled scopes supply lexical destinations. Free lists from delete are compiler +internals, not user-visible pools. These distinctions supersede older pool +terminology below. `new E[]` begins growth, `es += e` appends, and the creating +scope's end finishes growth without necessarily ending storage lifetime. +Obsolete backing arrays can be internally recycled only after proving no usable +references survive; arrays still have no user delete operation. +Classes opt into deletion/recycling; stale reads remain type-safe but can see +historical field values, including finals. Incomplete references cannot be +stored into deletable objects, including during construction. Arrays are never +deletable; do not reintroduce array delete/reuse free lists. Non-moving growable +arrays are a separate requested discussion topic. Deletable +constructors use ordinary aliasable memory from entry, while non-deletable +constructors retain private memory. Keep initialization obligations separate +from storage privacy; withholding TMP._one is a suggested implementation route +to audit, not a verified sufficient change. Preserve these decisions; older +discussion in the survey includes superseded assumptions. +Do not treat other roadmap sketches as chosen mechanisms. +Pools have global or shorter lexical lifetimes (2026-11-18 decision), rather +than transferred/object-owned lifetimes. Global pools retain their storage. +Pool reclamation requires proving all usable references gone, including stale +references after object delete and reachable historical pointer values. Object +delete never waives the region-lifetime proof. Analysis design remains deferred. +Function lifetime contracts infer borrowing, result origins/destinations, and +retention for ordinary definitions; opaque callback interfaces default to +borrowing arguments for the call, with retention explicit and implementations +checked. Result contracts remain necessary. Specializing functions by argument +treatment is an optional optimization, never a condition of language legality. +Native functions use the same external lifetime contracts: their written Simple +FFI type supplies trusted promises that the native implementation must honor. +No separate native lifetime mechanism is needed; mismatches are binding or +implementation bugs. +Returned-borrow syntax agreed 2026-11-19: function result `T from arg`, or +`T from (a | b)` for alternative origins. Only arguments mentioned in `from` +need names in the function type; other parameters may remain unnamed. `T` is +a struct reference, while `*T` is an object value. Bodies infer contracts or +are checked against written ones; annotations do not silently extend storage. +For now FFI cannot directly return borrowed interior references into Simple +objects. Native array adapters return indices/ranges and Simple constructs +checked interior references. Field-reference FFI returns are deferred. +Apparent unbounded growth under inferred lifetimes must be an error, never a +warning or merely a report. The user fixes it with a cheap explicit choice of +the default stack destination or an appropriate pool. Neither annotation waives +lifetime safety. Growth-check repetition means an unknown loop bound, a known +upper bound greater than 10, or recursion; small bounded loops are exempt on +that account. Support make-and-test loops retaining only the winner, where +failed candidates provably do not escape. Syntax and implementation remain open. Preserve Chapter 32's compiler and performance narrative. The test commands and invariants below also apply to Chapter 33. @@ -332,6 +400,8 @@ and a small game with graphics, keyboard input, and sound. ## Collaboration preferences +- Avoid Java streams; Cliff finds ordinary loops easier to read, including in tests. + - For densely keyed integer maps, use indexed `Ary` storage rather than `HashMap`. - Build with Make alone; Maven must never be required. Cliff prefers few tests: -- cgit v1.2.3