diff options
| author | Cliff Click <cliffc@acm.org> | 2026-11-20 15:26:44 -0800 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-11-20 15:26:44 -0800 |
| commit | c201515eeb2e99cb6f0e820459662affc047c2ce (patch) | |
| tree | 28750086af8c788f4614d6a8b2a82df4a413e00a /chapter33 | |
| parent | 4f0cc22dafcdea877fe4ab137523a5944f754126 (diff) | |
| download | Simple-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')
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); |
