summaryrefslogtreecommitdiff
path: root/chapter33
diff options
context:
space:
mode:
Diffstat (limited to 'chapter33')
-rw-r--r--chapter33/README.md161
-rw-r--r--chapter33/docs/AllocationSurvey.java138
-rw-r--r--chapter33/docs/allocation-survey-functions.tsv262
-rw-r--r--chapter33/docs/allocation-survey.md256
-rw-r--r--chapter33/docs/growing-array-rewrites.md258
-rw-r--r--chapter33/docs/growing-arrays-survey.md222
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java661
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java28
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/codegen/Serialize.java7
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/codegen/Unlink.java1
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/CFGNode.java48
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/KeepAliveNode.java102
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/Node.java4
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/node/ScopeNode.java96
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java1
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/parser/ControlFlow.java4
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/parser/Conversions.java16
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/parser/Functions.java2
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/parser/Statements.java5
-rw-r--r--chapter33/src/main/java/com/seaofnodes/simple/type/Type.java7
-rw-r--r--chapter33/src/test/java/com/seaofnodes/simple/BrainFuckTest.java2
-rw-r--r--chapter33/src/test/java/com/seaofnodes/simple/Chapter18Test.java11
-rw-r--r--chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java799
-rw-r--r--chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java2
24 files changed, 2932 insertions, 161 deletions
diff --git a/chapter33/README.md b/chapter33/README.md
index e3a19026..9e95054e 100644
--- a/chapter33/README.md
+++ b/chapter33/README.md
@@ -5,12 +5,19 @@ English | [日本語](README.ja.md)
[Previous: Chapter 32 — Compiler Internal Speedups](../chapter32/README.md)
This chapter starts automatic memory management with an allocation-lifetime
-analysis. It runs after Opto and field-layout finalization, before TypeCheck.
+analysis. It runs after Opto, field-layout finalization, and LoopTree, before TypeCheck.
It reports where storage must live; allocation and machine code still use the
existing runtime. The [design survey](../docs/automatic-memory-management-survey.md)
records the language decisions. Chapter 32's
[speedup measurements](../chapter32/README.md) remain there.
+The [existing-program survey](docs/allocation-survey.md) records what this first
+analysis accepts and rejects across `sys` and the games, with small reductions
+that separate analysis limitations from storage decisions.
+The [growing-array survey](docs/growing-arrays-survey.md) identifies builders that
+can finish in one scope, persistent collections, and library API changes needed
+for grow-in-place storage.
+
## First allocation plans
Four small examples in [Chapter33Test](src/test/java/com/seaofnodes/simple/Chapter33Test.java)
@@ -34,34 +41,57 @@ 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.
+Within one summary, loads, stores, and call effects converge before a worklist
+propagates destination requirements. For example, returning a Box retains its
+Thing too. This local closure does not repeat the call-graph traversal. Stores
+are conservative weak updates: overwriting a field does not yet release the
+earlier value's lifetime constraint. Array elements share one field, regardless
+of index.
-The ASCII dump shows callees first, then their callers:
+Pointer-valued loads keep the child's origin separate from the holder:
```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
+get(h) { return h.c; } // returns borrowed origin arg3.c
+fill(h) { h.c.d = new Thing; } // new Thing must outlive arg3.c
+```
+
+At a call, `arg3.c` resolves to the actual holder's possible field values. A
+function can build a temporary holder and return its child; only the child
+needs result storage. Copying a child between holders likewise retains the
+child without retaining its source holder. Call substitution also handles two
+arguments referring to the same object.
+
+The ASCII dump shows function summaries in call-graph reverse postorder (RPO):
+callers before callees, starting from the program entry. Other retained functions
+(such as constructor bodies whose calls were inlined) follow in a separate RPO
+section. Reachability here follows direct calls in the optimized graph. Nested
+loop frames stay under their parent, with siblings ordered by node ID. Analysis
+still builds summaries in postorder.
+```text
+-- forward_noInline
| call#219 -> make_noInline
| [result] call#219/new#352:Test.Thing (8 bytes)
| [result] call#219/new#381:Test.Box (8 bytes)
| .child --> call#219/new#352:Test.Thing
-`-- return -> call#219/new#381:Test.Box
+`-- return -> {call#219/new#381:Test.Box}
+
++-- make_noInline
+| [result] new#352:Test.Thing (8 bytes)
+| [result] new#381:Test.Box (8 bytes)
+| .child --> new#352:Test.Thing
+`-- return -> {new#381:Test.Box}
```
`frame` means scratch for that function; `result` means the caller's result
destination; `static` means program lifetime. `arg3` names storage associated
with argument input 3 (ordinary class functions use input 2 for their hidden
-receiver). `arg3 & arg4` requires a destination satisfying both owners; it does
+receiver). `arg3.c` names the storage referenced by that argument's `c` field,
+not storage inside the holder. `arg3 & arg4` requires a destination satisfying both owners; it does
not arbitrarily pick one. Node numbers help correlate this output with the IR.
These are ownership constraints, not assigned physical stack offsets.
+Return origins are a set of alternatives: `{arg3:a | arg4:b}` means the returned
+reference may point to either argument. `{}` means no tracked storage is returned.
Run a poster child and print its plan:
@@ -69,11 +99,104 @@ Run a poster child and print its plan:
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.
+## Iteration storage and winners
+
+Functions and loop iterations use the same `Summary` and cleanup rule. Each
+summary has incoming values, normal exit values, retention effects, and scratch
+storage. A loop also has continuation values: its backedge returns these as
+arguments to the next iteration. Both loop exits clean up the iteration frame.
+The backedge's conceptual pop/push can reuse the same fixed storage without code.
+
+A loop can have both a surviving result and unrelated scratch. One reference-flow
+calculation finds both; placement follows the summary interfaces. For example,
+`testAllocationLoopWinnerAndScratch` constructs a Scratch and a candidate Thing
+each iteration, tests the candidate, and breaks with the winner:
+
+```text
+| +-- loop#221 frame; parent find_noInline
+| | continue refs -> {}
+| | return refs -> {call#276/new#424:Test.Thing}
+| | [loop#221 iteration] new#484:Test.Scratch (8 bytes)
+| `-- cleanup on continue and return -> {new#484:Test.Scratch}
+| [result] call#276/new#424:Test.Thing (8 bytes); loop#221 winner
+`-- return -> {call#276/new#424:Test.Thing}
+```
+
+The Thing has fixed result space reserved before entering the loop. Failed
+candidates may reuse it because no earlier candidate remains reachable on the
+backedge. Scratch belongs to the iteration and can be reclaimed each turn.
+Storage prints inside its owning frame, including an inner loop's winner when
+the outer iteration owns it. Iteration storage and function `[frame]` storage
+are the same logical scratch-storage choice, with different cleanup boundaries.
+A winner's referenced objects survive with it. An inner loop's winner can still
+belong to the outer loop's iteration storage. Storage exported by a frame is
+promoted through enclosing frames until one can own it. Calls substitute
+arguments and fresh sites; nested loops already share their function's SSA
+vocabulary, so their composition preserves site identities. Private callee
+scratch stays in the callee.
+
+The abbreviated dump above omits the value ports. The full dump names entry,
+continuation, and exit values, including scalar and memory values. A scalar
+loaded from scratch can cross an exit without retaining the scratch object.
+Returning from nested loops exports through each intervening summary; each
+frame retains its own cleanup set. These logical storage frames are separate
+from machine return-address and spill slots.
+
+The continuation summary follows reference Phis and memory reaching each backedge,
+including helper-call retention. Borrowed references can continue to the next
+iteration. Keeping an earlier candidate in a variable, linking
+candidates together, or storing them into a pre-existing array rejects the plan.
+Publishing through an argument's field only on an exit arm is allowed. For now,
+even bounded retention and overwritten memory slots reject: weak updates do not
+prove that the old reference died. Collection destinations and more precise
+memory liveness remain future work. Floating scalar uses may finish before an
+iteration reset; uses constrained outside the loop retain their referenced storage.
+
+These are still plans: no stack reservations, slot reuse, or reclamation are
+emitted yet. Allocation uses each CFG node's tightest containing LoopTree and
+the tree's parent links. Simple produces reducible control flow; that is an
+asserted invariant, not an allocation rejection. The early LoopTree walk leaves
+the IR unchanged. Before scheduling, the tree is rebuilt to account for Lower's
+CFG changes, and loops with zero exits receive one synthetic exit. Delaying those
+exits preserves nonreturning-function summaries during type checking and serialization.
+
+That ordering is temporary. Before this chapter closes, the original LoopTree
+build must insert NeverExits, Allocation's zero-exit support must be removed,
+and Lower must maintain the tree with local edits instead of a full rebuild.
+The [roadmap](../docs/roadmap.md#phase-ordering-and-incremental-analysis) tracks
+this deferred work, including preserving nonreturning-function semantics.
+
+Native calls borrow their arguments until the call returns: they must not retain,
+hide, or publish those references. Converting an array pointer to an integer now
+adds a `KeepAlive(control, value)` at the converting scope's exits. Allocation
+traces that value through arithmetic and Phis to its storage. The integer can
+travel through memory and Simple wrappers without losing the original endpoint.
+The native ABI and pointer representation are unchanged.
+
+The marker keeps every conversion, including earlier values of reassigned locals.
+Returns, breaks, and continues end the scopes they leave; unbraced if/else arms
+and loop bodies also have their own borrowing scopes. Conditional expressions
+share their enclosing scope. Returning or storing the integer does not extend
+that scope: using the address afterwards can access reclaimed storage.
+
+Markers survive serialization and inlining, then disappear before scheduling;
+they require no registers or machine instructions. Zero/null, duplicate adjacent
+markers, and unused address expressions fold away. Placement still chooses whole
+function/iteration frames, so a lexical endpoint can conservatively retain storage
+in a larger frame. Actual stack lowering is still pending. Serialized IR is now
+format 3; older objects must be rebuilt to supply these lifetime endpoints.
+
+Native results that are Simple pointers also need an explicit origin/allocation
+contract; they are not assumed to be borrowed or freshly allocated.
+
+The first cut also rejects plans for recursive calls, unknown/opaque Simple calls,
+variable-size allocations, and reference origins that it cannot trace.
+Weak updates can also invent endlessly longer field paths in
+code such as `p.next = p.next.next`; the pass rejects these plans when paths
+exceed the body's reads plus the path depths supplied by its callees. Tracking
+memory order is future work. A rejected function is printed as `REJECT`, never
+as a usable partial plan. Scalar field reads and writes do not themselves
+introduce retained references.
Normal compilation records those rejections and continues with the existing
allocator. `-Dsimple.alloc.check=true` rejects compilation if any function lacks
@@ -84,7 +207,7 @@ 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,
+the next work: collection and SCC destinations, memory-ordered field updates, bin packing,
free lists, and parallel growth areas. No new IR nodes or serialized contracts
are introduced yet.
diff --git a/chapter33/docs/AllocationSurvey.java b/chapter33/docs/AllocationSurvey.java
new file mode 100644
index 00000000..108cbfb3
--- /dev/null
+++ b/chapter33/docs/AllocationSurvey.java
@@ -0,0 +1,138 @@
+import com.seaofnodes.simple.codegen.*;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.util.Ary;
+import java.nio.file.*;
+import java.lang.reflect.Field;
+import java.util.*;
+
+// Standalone survey, not a test or a compiler option. Run from chapter33.
+public class AllocationSurvey {
+ static Object field(Object object, String name) throws Exception {
+ Field f=object.getClass().getDeclaredField(name);
+ f.setAccessible(true);
+ return f.get(object);
+ }
+ static String clean(Object s) { return s==null ? "" : s.toString().replace('\t',' ').replace('\n',' '); }
+ static String category(String reason) {
+ if( reason==null ) return "supported";
+ if( reason.contains("opaque body") ) return "opaque body";
+ if( reason.contains("opaque or indirect") ) return "indirect call";
+ if( reason.contains("recursive call") ) return "recursion";
+ if( reason.contains("raw address") ) return "raw address";
+ if( reason.contains("variable-size") ) return "variable size";
+ if( reason.contains("across its backedge") ) return "loop retention";
+ if( reason.contains("cyclic field-path") ) return "field paths";
+ if( reason.contains("reference origin") ) return "reference origin";
+ if( reason.contains("native result storage") ) return "native result";
+ return "other";
+ }
+ static String probe(String name) {
+ return switch(name) {
+ case "LocalArray" -> """
+ val work_noInline={ u32 n ->
+ val xs=new i64[n];
+ for( u32 i=0; i<n; i++ ) xs[i]=i;
+ return n ? xs[n-1] : 0;
+ };
+ u32 len=arg;
+ return work_noInline(len);
+ """;
+ case "ReturnedArray" -> """
+ val make_noInline={ u32 n -> new i64[n]; };
+ u32 len=arg;
+ return make_noInline(len)#;
+ """;
+ case "OverwrittenSlot" -> """
+ struct Thing { i64 !x; new Thing={i64 n -> x=n;}; };
+ struct Holder { Thing? !c=null; };
+ val work_noInline={i64 n ->
+ val h=new Holder;
+ while(n>0) { h.c=new Thing(n); n--; }
+ return h.c ? h.c.x : 0;
+ };
+ return work_noInline(arg);
+ """;
+ case "ReusedObject" -> """
+ struct Thing { i64 !x; new Thing={i64 n -> x=n;}; };
+ val read_noInline={Thing t -> t.x;};
+ val work_noInline={i64 n ->
+ val t=new Thing(0);
+ i64 sum=0;
+ while(n>0) { t.x=n; sum+=read_noInline(t); n--; }
+ return sum;
+ };
+ return work_noInline(arg);
+ """;
+ default -> throw new IllegalArgumentException(name);
+ };
+ }
+ @SuppressWarnings("unchecked")
+ public static void main(String[] args) throws Exception {
+ String name=args[0], mode=args.length>1 ? args[1] : "source";
+ Path out=Path.of("build/allocation-survey",name+"-"+mode);
+ Files.createDirectories(out);
+ for( String file : new String[]{"error.txt","dump.txt","functions.tsv","sites.tsv","allocations.tsv","calls.tsv"} )
+ Files.deleteIfExists(out.resolve(file));
+ String src=mode.equals("probe") ? probe(name) : name.equals("sys") ? null :
+ name.equals("RuntimeArgs") ? Files.readString(Path.of("src/main/smp/sys/rt/simple_args.smp")) :
+ Files.readString(Path.of("docs/examples",name+".smp"));
+ if( src!=null && !name.equals("RuntimeArgs") && mode.equals("source") ) src="val _survey_sys=sys;\n"+src;
+ String root=mode.equals("source") ? "src/main/smp" : "docs/examples";
+ Ary<String> libs=mode.equals("object") ? new Ary<>(new String[]{"build/release/x86_64_v2_win64"}) : null;
+ CodeGen code=new CodeGen(root,out.resolve("objects").toString(),libs,name,src,456,true,TypeInteger.BOT);
+ long start=System.nanoTime();
+ try { code.driver(CodeGen.Phase.TypeCheck); }
+ catch(Throwable t) {
+ StringBuilder error=new StringBuilder(t.toString()+"\nphase="+code._phase+"\n");
+ if( t instanceof com.seaofnodes.simple.parser.Parser.ParseException p ) error.append(p.diagnostic()).append('\n');
+ for( StackTraceElement frame : t.getStackTrace() ) error.append(frame).append('\n');
+ Files.writeString(out.resolve("error.txt"),error);
+ System.out.println(name+" "+mode+" ERROR "+t);
+ return;
+ }
+ Allocation.Summary[] summaries=(Allocation.Summary[])field(code._allocation,"_summaries");
+ Files.writeString(out.resolve("dump.txt"),code._allocation.toString());
+ StringBuilder rows=new StringBuilder("program\tmode\tunit\tfunction\tid\tstatus\tcategory\troot_function\troot_id\troot_unit\tnew_user\tnew_class\tvariable\tplaced_user\tplaced_class\tloops\treason\n");
+ StringBuilder sites=new StringBuilder("program\tmode\tunit\tfunction\tsite\ttype\tbytes\tdestination\n");
+ StringBuilder nodes=new StringBuilder("program\tmode\tunit\tfunction\tnode\tsize\ttype\n");
+ StringBuilder calls=new StringBuilder("program\tmode\tunit\tfunction\tnode\ttarget\tsignature\n");
+ int total=0,pass=0,allocated=0;
+ for( Allocation.Summary sum : summaries ) {
+ if( sum==null ) continue;
+ FunNode fun=sum._fun;
+ String unit=fun._compunit==null ? "" : fun._compunit._cname;
+ Allocation.Summary cause=sum;
+ HashSet<Allocation.Summary> seen=new HashSet<>();
+ while( cause._reject!=null && cause._reject.startsWith("call #") && seen.add(cause) ) {
+ int id=Integer.parseInt(cause._reject.substring(6,cause._reject.indexOf(' ',6)));
+ Allocation.Summary next=null;
+ for( CallNode call : (ArrayList<CallNode>)field(cause,"_calls") )
+ if( call._nid==id && call.fptr()._type instanceof TypeFunPtr fp && fp.isConstant() ) next=summaries[fp.fidx()];
+ if( next==null ) break;
+ cause=next;
+ }
+ int local=0,clz=0,variable=0,placed=0,placedClz=0;
+ for( CallNode call : (ArrayList<CallNode>)field(sum,"_calls") )
+ calls.append(name).append('\t').append(mode).append('\t').append(clean(unit)).append('\t').append(clean(fun._name)).append('\t').append(call._nid).append('\t').append(clean(call.name())).append('\t').append(clean(call.fptr()._type)).append('\n');
+ for( Node n : (ArrayList<Node>)field(sum,"_nodes") ) if( n instanceof NewNode a ) {
+ if( TypeStruct.startsClzPrefix(a._ts._name) ) clz++; else local++;
+ if( !(a.size()._type instanceof TypeInteger sz) || !sz.isConstant() ) variable++;
+ nodes.append(name).append('\t').append(mode).append('\t').append(clean(unit)).append('\t').append(clean(fun._name)).append('\t').append(a._nid).append('\t').append(clean(a.size()._type)).append('\t').append(clean(a._ts._name)).append('\n');
+ }
+ if( sum.supported() ) for( Allocation.Site site : sum._sites ) if( site._allocation!=null ) {
+ if( TypeStruct.startsClzPrefix(site._allocation._ts._name) ) placedClz++; else placed++;
+ sites.append(name).append('\t').append(mode).append('\t').append(clean(unit)).append('\t').append(clean(fun._name)).append('\t').append(clean(site._name)).append('\t').append(clean(site._allocation._ts._name)).append('\t').append(site._bytes).append('\t').append(clean(site.destination())).append('\n');
+ }
+ String status=sum.supported() ? "pass" : sum._reject.startsWith("call #") ? "blocked" : "direct";
+ rows.append(name).append('\t').append(mode).append('\t').append(clean(unit)).append('\t').append(clean(fun._name)).append('\t').append(fun.sig().fidx()).append('\t').append(status).append('\t').append(category(cause._reject)).append('\t').append(clean(cause._fun._name)).append('\t').append(cause._fun.sig().fidx()).append('\t').append(clean(cause._fun._compunit==null ? null : cause._fun._compunit._cname)).append('\t').append(local).append('\t').append(clz).append('\t').append(variable).append('\t').append(placed).append('\t').append(placedClz).append('\t').append(((IdentityHashMap<?,?>)field(sum,"_loops")).size()).append('\t').append(clean(sum._reject)).append('\n');
+ total++;
+ if( sum.supported() ) { pass++; if( placed>0 ) allocated++; }
+ }
+ Files.writeString(out.resolve("functions.tsv"),rows);
+ Files.writeString(out.resolve("sites.tsv"),sites);
+ Files.writeString(out.resolve("allocations.tsv"),nodes);
+ Files.writeString(out.resolve("calls.tsv"),calls);
+ System.out.println(name+" "+mode+": "+pass+"/"+total+" pass, "+allocated+" with user allocations; "+((System.nanoTime()-start)/1000000)+" ms");
+ }
+}
diff --git a/chapter33/docs/allocation-survey-functions.tsv b/chapter33/docs/allocation-survey-functions.tsv
new file mode 100644
index 00000000..80f22547
--- /dev/null
+++ b/chapter33/docs/allocation-survey-functions.tsv
@@ -0,0 +1,262 @@
+"program" "mode" "unit" "function" "id" "status" "category" "root_function" "root_id" "root_unit" "new_user" "new_class" "variable" "placed_user" "placed_class" "loops" "reason"
+"sys" "source" "sys" "class:sys.<clinit>" "2" "pass" "supported" "class:sys.<clinit>" "2" "sys" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.adt" "class:sys.adt.<clinit>" "3" "pass" "supported" "class:sys.adt.<clinit>" "3" "sys.adt" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.audio" "class:sys.audio.<clinit>" "4" "pass" "supported" "class:sys.audio.<clinit>" "4" "sys.audio" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.audio" "sys.audio.open" "11" "direct" "indirect call" "sys.audio.open" "11" "sys.audio" "0" "0" "0" "0" "0" "0" "opaque or indirect call #257"
+"sys" "source" "sys.audio" "sys.audio.load" "12" "direct" "raw address" "sys.audio.load" "12" "sys.audio" "0" "0" "0" "0" "0" "0" "raw address escapes lifetime tracking #274"
+"sys" "source" "sys.audio" "sys.audio.play" "13" "direct" "indirect call" "sys.audio.play" "13" "sys.audio" "0" "0" "0" "0" "0" "0" "opaque or indirect call #321"
+"sys" "source" "sys.audio" "sys.audio.boop" "14" "direct" "indirect call" "sys.audio.boop" "14" "sys.audio" "0" "0" "0" "0" "0" "0" "opaque or indirect call #361"
+"sys" "source" "sys.audio" "sys.audio.win" "15" "direct" "indirect call" "sys.audio.win" "15" "sys.audio" "0" "0" "0" "0" "0" "0" "opaque or indirect call #401"
+"sys" "source" "sys.audio" "sys.audio.lose" "16" "direct" "indirect call" "sys.audio.lose" "16" "sys.audio" "0" "0" "0" "0" "0" "0" "opaque or indirect call #441"
+"sys" "source" "sys.audio" "sys.audio.stop" "17" "direct" "indirect call" "sys.audio.stop" "17" "sys.audio" "0" "0" "0" "0" "0" "0" "opaque or indirect call #468"
+"sys" "source" "sys.audio" "sys.audio.playing" "18" "direct" "indirect call" "sys.audio.playing" "18" "sys.audio" "0" "0" "0" "0" "0" "0" "opaque or indirect call #495"
+"sys" "source" "sys.audio" "sys.audio.close" "19" "direct" "indirect call" "sys.audio.close" "19" "sys.audio" "0" "0" "0" "0" "0" "0" "opaque or indirect call #522"
+"sys" "source" "sys.ary" "class:sys.ary.<clinit>" "20" "pass" "supported" "class:sys.ary.<clinit>" "20" "sys.ary" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.ary" "sys.ary.capacity" "21" "pass" "supported" "sys.ary.capacity" "21" "sys.ary" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.ary" "sys.ary.copy" "22" "pass" "supported" "sys.ary.copy" "22" "sys.ary" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.ary" "sys.ary.cmp" "23" "pass" "supported" "sys.ary.cmp" "23" "sys.ary" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.aryi64" "class:sys.aryi64.<clinit>" "24" "pass" "supported" "class:sys.aryi64.<clinit>" "24" "sys.aryi64" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.aryi64" "sys.aryi64.<init>" "25" "pass" "supported" "sys.aryi64.<init>" "25" "sys.aryi64" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.aryi64" "sys.aryi64._grow" "26" "direct" "indirect call" "sys.aryi64._grow" "26" "sys.aryi64" "1" "0" "1" "0" "0" "1" "opaque or indirect call #1392"
+"sys" "source" "sys.aryi64" "sys.aryi64.add" "27" "blocked" "indirect call" "sys.aryi64._grow" "26" "sys.aryi64" "0" "0" "0" "0" "0" "0" "call #1495 -> sys.aryi64._grow: opaque or indirect call #1392"
+"sys" "source" "sys.aryi64" "sys.aryi64.get" "28" "pass" "supported" "sys.aryi64.get" "28" "sys.aryi64" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.aryi64" "sys.aryi64.str" "29" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "2" "0" "0" "0" "0" "1" "call #27695 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.aryi64" "sys.aryi64.swap" "30" "pass" "supported" "sys.aryi64.swap" "30" "sys.aryi64" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.aryi64" "sys.aryi64.<new>" "32" "pass" "supported" "sys.aryi64.<new>" "32" "sys.aryi64" "1" "0" "0" "1" "0" "0" ""
+"sys" "source" "sys.aryi64" "sys.aryi64.parseAryI64" "33" "blocked" "indirect call" "sys.aryi64._grow" "26" "sys.aryi64" "3" "0" "0" "0" "0" "6" "call #27372 -> sys.aryi64._grow: opaque or indirect call #1392"
+"sys" "source" "sys.aryi64" "sys.aryi64.copy" "34" "pass" "supported" "sys.aryi64.copy" "34" "sys.aryi64" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.aryu8" "class:sys.aryu8.<clinit>" "35" "pass" "supported" "class:sys.aryu8.<clinit>" "35" "sys.aryu8" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.aryu8" "sys.aryu8.<init>" "36" "pass" "supported" "sys.aryu8.<init>" "36" "sys.aryu8" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.aryu8" "sys.aryu8._grow" "37" "direct" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "1" "0" "1" "0" "0" "0" "opaque or indirect call #2466"
+"sys" "source" "sys.aryu8" "sys.aryu8.clear" "38" "pass" "supported" "sys.aryu8.clear" "38" "sys.aryu8" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.aryu8" "sys.aryu8.add" "39" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "0" "0" "0" "0" "0" "0" "call #2559 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.aryu8" "sys.aryu8.addAry" "40" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "0" "0" "0" "0" "0" "0" "call #2607 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.aryu8" "sys.aryu8.undo" "41" "pass" "supported" "sys.aryu8.undo" "41" "sys.aryu8" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.aryu8" "sys.aryu8.num" "42" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "0" "0" "0" "0" "0" "0" "call #2705 -> sys.text.integer: call #5950 -> sys.text.string: call #23308 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.aryu8" "sys.aryu8.write" "43" "blocked" "raw address" "sys.io.writeOff" "68" "sys.io" "0" "0" "0" "0" "0" "0" "call #2738 -> sys.io.writeOff: raw address escapes lifetime tracking #4102"
+"sys" "source" "sys.aryu8" "sys.aryu8.<new>" "45" "pass" "supported" "sys.aryu8.<new>" "45" "sys.aryu8" "2" "0" "0" "2" "0" "0" ""
+"sys" "source" "sys.aryu8" "sys.aryu8.atoi" "46" "pass" "supported" "sys.aryu8.atoi" "46" "sys.aryu8" "0" "0" "0" "0" "0" "2" ""
+"sys" "source" "sys.aryu8" "sys.aryu8.str0" "47" "direct" "indirect call" "sys.aryu8.str0" "47" "sys.aryu8" "1" "0" "1" "0" "0" "1" "opaque or indirect call #3085"
+"sys" "source" "sys.char" "class:sys.char.<clinit>" "48" "pass" "supported" "class:sys.char.<clinit>" "48" "sys.char" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.char" "sys.char.toupper" "49" "pass" "supported" "sys.char.toupper" "49" "sys.char" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.char" "sys.char.tolower" "50" "pass" "supported" "sys.char.tolower" "50" "sys.char" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.integer" "class:sys.integer.<clinit>" "51" "pass" "supported" "class:sys.integer.<clinit>" "51" "sys.integer" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.math" "class:sys.math.<clinit>" "52" "pass" "supported" "class:sys.math.<clinit>" "52" "sys.math" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.math" "sys.math.max" "60" "pass" "supported" "sys.math.max" "60" "sys.math" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.math" "sys.math.min" "61" "pass" "supported" "sys.math.min" "61" "sys.math" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.io" "class:sys.io.<clinit>" "62" "pass" "supported" "class:sys.io.<clinit>" "62" "sys.io" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.io" "sys.io.p" "63" "blocked" "raw address" "sys.io.writeOff" "68" "sys.io" "0" "0" "0" "0" "0" "0" "call #24576 -> sys.io.writeOff: raw address escapes lifetime tracking #4102"
+"sys" "source" "sys.io" "sys.io.p_noInline" "64" "blocked" "raw address" "sys.io.writeOff" "68" "sys.io" "0" "0" "0" "0" "0" "0" "call #23093 -> sys.io.writeOff: raw address escapes lifetime tracking #4102"
+"sys" "source" "sys.io" "sys.io.err" "65" "blocked" "raw address" "sys.io.writeOff" "68" "sys.io" "0" "0" "0" "0" "0" "0" "call #27466 -> sys.io.writeOff: raw address escapes lifetime tracking #4102"
+"sys" "source" "sys.io" "sys.io.read" "66" "direct" "raw address" "sys.io.read" "66" "sys.io" "4" "0" "1" "0" "0" "1" "raw address escapes lifetime tracking #3695"
+"sys" "source" "sys.io" "sys.io.write" "67" "blocked" "raw address" "sys.io.writeOff" "68" "sys.io" "0" "0" "0" "0" "0" "0" "call #4008 -> sys.io.writeOff: raw address escapes lifetime tracking #4102"
+"sys" "source" "sys.io" "sys.io.writeOff" "68" "direct" "raw address" "sys.io.writeOff" "68" "sys.io" "0" "0" "0" "0" "0" "1" "raw address escapes lifetime tracking #4102"
+"sys" "source" "sys.io" "sys.io.stdin" "69" "blocked" "raw address" "sys.io.read" "66" "sys.io" "0" "0" "0" "0" "0" "0" "call #4301 -> sys.io.read: raw address escapes lifetime tracking #3695"
+"sys" "source" "sys.io" "sys.io.getch" "70" "direct" "indirect call" "sys.io.getch" "70" "sys.io" "0" "0" "0" "0" "0" "0" "opaque or indirect call #4326"
+"sys" "source" "sys.io" "sys.io.create" "71" "direct" "raw address" "sys.io.create" "71" "sys.io" "0" "0" "0" "0" "0" "0" "raw address escapes lifetime tracking #26751"
+"sys" "source" "sys.io" "sys.io.open" "72" "direct" "raw address" "sys.io.open" "72" "sys.io" "0" "0" "0" "0" "0" "0" "raw address escapes lifetime tracking #25971"
+"sys" "source" "sys.io" "sys.io.close" "73" "direct" "indirect call" "sys.io.close" "73" "sys.io" "0" "0" "0" "0" "0" "0" "opaque or indirect call #4495"
+"sys" "source" "sys.io" "sys.io.remove" "74" "direct" "raw address" "sys.io.remove" "74" "sys.io" "0" "0" "0" "0" "0" "0" "raw address escapes lifetime tracking #26389"
+"sys" "source" "sys.gfx" "class:sys.gfx.<clinit>" "75" "pass" "supported" "class:sys.gfx.<clinit>" "75" "sys.gfx" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.gfx" "sys.gfx.open" "88" "direct" "raw address" "sys.gfx.open" "88" "sys.gfx" "0" "0" "0" "0" "0" "0" "raw address escapes lifetime tracking #4719"
+"sys" "source" "sys.gfx" "sys.gfx.present" "89" "direct" "raw address" "sys.gfx.present" "89" "sys.gfx" "0" "0" "0" "0" "0" "0" "raw address escapes lifetime tracking #4751"
+"sys" "source" "sys.gfx" "sys.gfx.width" "90" "direct" "indirect call" "sys.gfx.width" "90" "sys.gfx" "0" "0" "0" "0" "0" "0" "opaque or indirect call #4796"
+"sys" "source" "sys.gfx" "sys.gfx.height" "91" "direct" "indirect call" "sys.gfx.height" "91" "sys.gfx" "0" "0" "0" "0" "0" "0" "opaque or indirect call #4823"
+"sys" "source" "sys.gfx" "sys.gfx.presentSize" "92" "direct" "raw address" "sys.gfx.presentSize" "92" "sys.gfx" "0" "0" "0" "0" "0" "0" "raw address escapes lifetime tracking #4990"
+"sys" "source" "sys.gfx" "sys.gfx.poll" "93" "direct" "indirect call" "sys.gfx.poll" "93" "sys.gfx" "0" "0" "0" "0" "0" "0" "opaque or indirect call #5042"
+"sys" "source" "sys.gfx" "sys.gfx.mouseX" "94" "direct" "indirect call" "sys.gfx.mouseX" "94" "sys.gfx" "0" "0" "0" "0" "0" "0" "opaque or indirect call #5069"
+"sys" "source" "sys.gfx" "sys.gfx.mouseY" "95" "direct" "indirect call" "sys.gfx.mouseY" "95" "sys.gfx" "0" "0" "0" "0" "0" "0" "opaque or indirect call #5096"
+"sys" "source" "sys.gfx" "sys.gfx.button" "96" "direct" "indirect call" "sys.gfx.button" "96" "sys.gfx" "0" "0" "0" "0" "0" "0" "opaque or indirect call #5125"
+"sys" "source" "sys.gfx" "sys.gfx.key" "97" "direct" "indirect call" "sys.gfx.key" "97" "sys.gfx" "0" "0" "0" "0" "0" "0" "opaque or indirect call #5154"
+"sys" "source" "sys.gfx" "sys.gfx.close" "98" "direct" "indirect call" "sys.gfx.close" "98" "sys.gfx" "0" "0" "0" "0" "0" "0" "opaque or indirect call #5181"
+"sys" "source" "sys.gfx" "sys.gfx.wait" "99" "direct" "indirect call" "sys.gfx.wait" "99" "sys.gfx" "0" "0" "0" "0" "0" "0" "opaque or indirect call #5210"
+"sys" "source" "sys.draw" "class:sys.draw.<clinit>" "100" "pass" "supported" "class:sys.draw.<clinit>" "100" "sys.draw" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw" "sys.draw.rgb" "101" "pass" "supported" "sys.draw.rgb" "101" "sys.draw" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.text" "class:sys.text.<clinit>" "102" "pass" "supported" "class:sys.text.<clinit>" "102" "sys.text" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.text" "sys.text.begin" "103" "pass" "supported" "sys.text.begin" "103" "sys.text" "2" "0" "0" "2" "0" "0" ""
+"sys" "source" "sys.text" "sys.text.end" "104" "direct" "variable size" "sys.text.end" "104" "sys.text" "1" "0" "1" "0" "0" "1" "variable-size allocation #5612"
+"sys" "source" "sys.text" "sys.text._pad" "105" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "0" "0" "0" "0" "0" "1" "call #22342 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.text" "sys.text.string" "106" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "0" "0" "0" "0" "0" "3" "call #23308 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.text" "sys.text.integer" "107" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "1" "0" "0" "0" "0" "8" "call #5950 -> sys.text.string: call #23308 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.text" "sys.text.floating" "109" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "0" "0" "0" "0" "0" "0" "call #23862 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.text" "sys.text.int" "110" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "3" "0" "1" "0" "0" "1" "call #7146 -> sys.text.integer: call #5950 -> sys.text.string: call #23308 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.text" "sys.text.flt" "111" "direct" "indirect call" "sys.text.flt" "111" "sys.text" "3" "0" "1" "0" "0" "1" "opaque or indirect call #23783"
+"sys" "source" "sys.text" "sys.text.f32" "112" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "3" "0" "1" "0" "0" "1" "call #24296 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.text" "sys.text.f64" "113" "direct" "indirect call" "sys.text.f64" "113" "sys.text" "3" "0" "1" "0" "0" "1" "opaque or indirect call #22964"
+"sys" "source" "sys.text" "sys.text.char" "114" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "3" "0" "1" "0" "0" "1" "call #7450 -> sys.text.integer: call #5950 -> sys.text.string: call #23308 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.text" "sys.text.bool" "115" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "3" "0" "1" "0" "0" "1" "call #7526 -> sys.text.integer: call #5950 -> sys.text.string: call #23308 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.text" "sys.text.hex" "116" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "3" "0" "1" "0" "0" "1" "call #7602 -> sys.text.integer: call #5950 -> sys.text.string: call #23308 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.text" "sys.text.time" "117" "blocked" "raw address" "sys.time.local" "148" "sys.time" "0" "0" "0" "0" "0" "0" "call #27428 -> sys.time._format: call #10394 -> sys.time.local: raw address escapes lifetime tracking #9945"
+"sys" "source" "sys.time" "class:sys.time.<clinit>" "118" "pass" "supported" "class:sys.time.<clinit>" "118" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.now" "125" "direct" "indirect call" "sys.time.now" "125" "sys.time" "0" "0" "0" "0" "0" "0" "opaque or indirect call #7965"
+"sys" "source" "sys.time" "sys.time.monotonic" "126" "direct" "indirect call" "sys.time.monotonic" "126" "sys.time" "0" "0" "0" "0" "0" "0" "opaque or indirect call #7992"
+"sys" "source" "sys.time" "sys.time.nanoTime" "127" "direct" "indirect call" "sys.time.nanoTime" "127" "sys.time" "0" "0" "0" "0" "0" "0" "opaque or indirect call #8019"
+"sys" "source" "sys.time" "sys.time.sleep" "128" "direct" "indirect call" "sys.time.sleep" "128" "sys.time" "0" "0" "0" "0" "0" "0" "opaque or indirect call #8049"
+"sys" "source" "sys.time" "sys.time.sleepUntil" "129" "direct" "indirect call" "sys.time.sleepUntil" "129" "sys.time" "0" "0" "0" "0" "0" "0" "opaque or indirect call #8079"
+"sys" "source" "sys.time" "sys.time._scale" "130" "pass" "supported" "sys.time._scale" "130" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.seconds" "131" "pass" "supported" "sys.time.seconds" "131" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.minutes" "132" "pass" "supported" "sys.time.minutes" "132" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.hours" "133" "pass" "supported" "sys.time.hours" "133" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.days" "134" "pass" "supported" "sys.time.days" "134" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.toSeconds" "135" "pass" "supported" "sys.time.toSeconds" "135" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.toMinutes" "136" "pass" "supported" "sys.time.toMinutes" "136" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.toHours" "137" "pass" "supported" "sys.time.toHours" "137" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.toDays" "138" "pass" "supported" "sys.time.toDays" "138" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.fromNanos" "139" "pass" "supported" "sys.time.fromNanos" "139" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.toNanos" "140" "pass" "supported" "sys.time.toNanos" "140" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.remaining" "141" "pass" "supported" "sys.time.remaining" "141" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.leap" "142" "pass" "supported" "sys.time.leap" "142" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.monthDays" "143" "pass" "supported" "sys.time.monthDays" "143" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time._days" "144" "pass" "supported" "sys.time._days" "144" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.valid" "145" "pass" "supported" "sys.time.valid" "145" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.makeUTC" "146" "pass" "supported" "sys.time.makeUTC" "146" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.utc" "147" "pass" "supported" "sys.time.utc" "147" "sys.time" "1" "0" "0" "1" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.local" "148" "direct" "raw address" "sys.time.local" "148" "sys.time" "2" "0" "0" "0" "0" "0" "raw address escapes lifetime tracking #9945"
+"sys" "source" "sys.time" "sys.time.zoneName" "149" "direct" "raw address" "sys.time.zoneName" "149" "sys.time" "4" "0" "1" "0" "0" "2" "raw address escapes lifetime tracking #10204"
+"sys" "source" "sys.time" "sys.time._digits" "150" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "0" "0" "0" "0" "0" "0" "call #10353 -> sys.text.integer: call #5950 -> sys.text.string: call #23308 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.time" "sys.time._format" "151" "blocked" "raw address" "sys.time.local" "148" "sys.time" "3" "0" "1" "0" "0" "1" "call #10394 -> sys.time.local: raw address escapes lifetime tracking #9945"
+"sys" "source" "sys.time" "sys.time.elapsed" "152" "blocked" "indirect call" "sys.aryu8._grow" "37" "sys.aryu8" "3" "0" "1" "0" "0" "1" "call #22941 -> sys.text.integer: call #5950 -> sys.text.string: call #23308 -> sys.aryu8._grow: opaque or indirect call #2466"
+"sys" "source" "sys.time" "sys.time.format" "153" "blocked" "raw address" "sys.time.local" "148" "sys.time" "0" "0" "0" "0" "0" "0" "call #11574 -> sys.time._format: call #10394 -> sys.time.local: raw address escapes lifetime tracking #9945"
+"sys" "source" "sys.time" "sys.time.formatLocal" "154" "blocked" "raw address" "sys.time.local" "148" "sys.time" "0" "0" "0" "0" "0" "0" "call #11663 -> sys.time._format: call #10394 -> sys.time.local: raw address escapes lifetime tracking #9945"
+"sys" "source" "sys.time" "sys.time._number" "155" "pass" "supported" "sys.time._number" "155" "sys.time" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.time" "sys.time._parseZone" "156" "pass" "supported" "sys.time._parseZone" "156" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time" "sys.time.parse" "157" "pass" "supported" "sys.time.parse" "157" "sys.time" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.libc" "class:sys.libc.<clinit>" "158" "pass" "supported" "class:sys.libc.<clinit>" "158" "sys.libc" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.libc" "sys.libc.errno" "167" "direct" "indirect call" "sys.libc.errno" "167" "sys.libc" "0" "0" "0" "0" "0" "0" "opaque or indirect call #13351"
+"sys" "source" "sys.libc" "sys.libc.set_errno" "169" "direct" "indirect call" "sys.libc.set_errno" "169" "sys.libc" "0" "0" "0" "0" "0" "0" "opaque or indirect call #13383"
+"sys" "source" "sys.rt" "class:sys.rt.<clinit>" "172" "pass" "supported" "class:sys.rt.<clinit>" "172" "sys.rt" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.scan" "class:sys.scan.<clinit>" "173" "pass" "supported" "class:sys.scan.<clinit>" "173" "sys.scan" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.scan" "sys.scan.<init>" "174" "pass" "supported" "sys.scan.<init>" "174" "sys.scan" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.scan" "sys.scan.skip" "175" "pass" "supported" "sys.scan.skip" "175" "sys.scan" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.scan" "sys.scan.match" "176" "pass" "supported" "sys.scan.match" "176" "sys.scan" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.scan" "sys.scan.number" "177" "pass" "supported" "sys.scan.number" "177" "sys.scan" "0" "0" "0" "0" "0" "3" ""
+"sys" "source" "sys.scan" "sys.scan.<new>" "179" "pass" "supported" "sys.scan.<new>" "179" "sys.scan" "1" "0" "0" "1" "0" "0" ""
+"sys" "source" "sys.adt.bitset" "class:sys.adt.bitset.<clinit>" "180" "pass" "supported" "class:sys.adt.bitset.<clinit>" "180" "sys.adt.bitset" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.adt.bitset" "sys.adt.bitset.<init>" "181" "pass" "supported" "sys.adt.bitset.<init>" "181" "sys.adt.bitset" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.adt.bitset" "sys.adt.bitset.get" "182" "pass" "supported" "sys.adt.bitset.get" "182" "sys.adt.bitset" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.adt.bitset" "sys.adt.bitset._grow" "183" "direct" "variable size" "sys.adt.bitset._grow" "183" "sys.adt.bitset" "1" "0" "1" "0" "0" "2" "variable-size allocation #14313"
+"sys" "source" "sys.adt.bitset" "sys.adt.bitset.set" "184" "blocked" "variable size" "sys.adt.bitset._grow" "183" "sys.adt.bitset" "0" "0" "0" "0" "0" "0" "call #14413 -> sys.adt.bitset._grow: variable-size allocation #14313"
+"sys" "source" "sys.adt.bitset" "sys.adt.bitset.tset" "185" "blocked" "variable size" "sys.adt.bitset._grow" "183" "sys.adt.bitset" "0" "0" "0" "0" "0" "0" "call #14465 -> sys.adt.bitset._grow: variable-size allocation #14313"
+"sys" "source" "sys.adt.bitset" "sys.adt.bitset.clr" "186" "pass" "supported" "sys.adt.bitset.clr" "186" "sys.adt.bitset" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.adt.bitset" "sys.adt.bitset.clear" "187" "pass" "supported" "sys.adt.bitset.clear" "187" "sys.adt.bitset" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.adt.bitset" "sys.adt.bitset.<new>" "189" "pass" "supported" "sys.adt.bitset.<new>" "189" "sys.adt.bitset" "2" "0" "0" "2" "0" "0" ""
+"sys" "source" "sys.draw.Canvas" "class:sys.draw.Canvas.<clinit>" "190" "pass" "supported" "class:sys.draw.Canvas.<clinit>" "190" "sys.draw.Canvas" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.<init>" "191" "pass" "supported" "sys.draw.Canvas.<init>" "191" "sys.draw.Canvas" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.resize" "192" "direct" "indirect call" "sys.draw.Canvas.resize" "192" "sys.draw.Canvas" "1" "0" "1" "0" "0" "0" "opaque or indirect call #15078"
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.localX" "193" "pass" "supported" "sys.draw.Canvas.localX" "193" "sys.draw.Canvas" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.localY" "194" "pass" "supported" "sys.draw.Canvas.localY" "194" "sys.draw.Canvas" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.clear" "195" "pass" "supported" "sys.draw.Canvas.clear" "195" "sys.draw.Canvas" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.pixel" "196" "pass" "supported" "sys.draw.Canvas.pixel" "196" "sys.draw.Canvas" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.fillRect" "197" "pass" "supported" "sys.draw.Canvas.fillRect" "197" "sys.draw.Canvas" "0" "0" "0" "0" "0" "2" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.rect" "198" "pass" "supported" "sys.draw.Canvas.rect" "198" "sys.draw.Canvas" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.fillCircle" "199" "pass" "supported" "sys.draw.Canvas.fillCircle" "199" "sys.draw.Canvas" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.circle" "200" "pass" "supported" "sys.draw.Canvas.circle" "200" "sys.draw.Canvas" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas._circle" "201" "pass" "supported" "sys.draw.Canvas._circle" "201" "sys.draw.Canvas" "0" "0" "0" "0" "0" "2" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.line" "202" "pass" "supported" "sys.draw.Canvas.line" "202" "sys.draw.Canvas" "0" "0" "0" "0" "0" "2" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.text" "203" "pass" "supported" "sys.draw.Canvas.text" "203" "sys.draw.Canvas" "0" "0" "0" "0" "0" "3" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.Canvas" "204" "direct" "indirect call" "sys.draw.Canvas.Canvas" "204" "sys.draw.Canvas" "1" "0" "1" "0" "0" "0" "opaque or indirect call #17231"
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas.<new>" "205" "blocked" "indirect call" "sys.draw.Canvas.Canvas" "204" "sys.draw.Canvas" "1" "0" "0" "0" "0" "0" "call #17399 -> sys.draw.Canvas.Canvas: opaque or indirect call #17231"
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas._glyph" "206" "pass" "supported" "sys.draw.Canvas._glyph" "206" "sys.draw.Canvas" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Canvas" "sys.draw.Canvas._onLine" "207" "pass" "supported" "sys.draw.Canvas._onLine" "207" "sys.draw.Canvas" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Button" "class:sys.draw.Button.<clinit>" "208" "pass" "supported" "class:sys.draw.Button.<clinit>" "208" "sys.draw.Button" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Button" "sys.draw.Button.<init>" "209" "pass" "supported" "sys.draw.Button.<init>" "209" "sys.draw.Button" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Button" "sys.draw.Button.contains" "210" "pass" "supported" "sys.draw.Button.contains" "210" "sys.draw.Button" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Button" "sys.draw.Button.update" "211" "pass" "supported" "sys.draw.Button.update" "211" "sys.draw.Button" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Button" "sys.draw.Button.draw" "212" "pass" "supported" "sys.draw.Button.draw" "212" "sys.draw.Button" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.draw.Button" "sys.draw.Button.<new>" "214" "pass" "supported" "sys.draw.Button.<new>" "214" "sys.draw.Button" "1" "0" "0" "1" "0" "0" ""
+"sys" "source" "sys.time.DateTime" "class:sys.time.DateTime.<clinit>" "215" "pass" "supported" "class:sys.time.DateTime.<clinit>" "215" "sys.time.DateTime" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time.DateTime" "sys.time.DateTime.<new>" "217" "pass" "supported" "sys.time.DateTime.<new>" "217" "sys.time.DateTime" "1" "0" "0" "1" "0" "0" ""
+"sys" "source" "sys.time.DateTime" "sys.time.DateTime.empty" "218" "pass" "supported" "sys.time.DateTime.empty" "218" "sys.time.DateTime" "1" "0" "0" "1" "0" "0" ""
+"sys" "source" "sys.time.Timers" "class:sys.time.Timers.<clinit>" "219" "pass" "supported" "class:sys.time.Timers.<clinit>" "219" "sys.time.Timers" "0" "0" "0" "0" "0" "0" ""
+"sys" "source" "sys.time.Timers" "sys.time.Timers.<init>" "220" "pass" "supported" "sys.time.Timers.<init>" "220" "sys.time.Timers" "3" "0" "0" "3" "0" "0" ""
+"sys" "source" "sys.time.Timers" "sys.time.Timers._add" "221" "direct" "recursion" "sys.time.Timers._add" "221" "sys.time.Timers" "3" "0" "3" "0" "0" "2" "recursive call component"
+"sys" "source" "sys.time.Timers" "sys.time.Timers.afterAt" "222" "blocked" "recursion" "sys.time.Timers._add" "221" "sys.time.Timers" "0" "0" "0" "0" "0" "0" "call #20364 -> sys.time.Timers._add: recursive call component"
+"sys" "source" "sys.time.Timers" "sys.time.Timers.everyAt" "223" "blocked" "recursion" "sys.time.Timers._add" "221" "sys.time.Timers" "0" "0" "0" "0" "0" "0" "call #20399 -> sys.time.Timers._add: recursive call component"
+"sys" "source" "sys.time.Timers" "sys.time.Timers.after" "224" "direct" "indirect call" "sys.time.Timers.after" "224" "sys.time.Timers" "0" "0" "0" "0" "0" "0" "opaque or indirect call #22597"
+"sys" "source" "sys.time.Timers" "sys.time.Timers.every" "225" "direct" "indirect call" "sys.time.Timers.every" "225" "sys.time.Timers" "0" "0" "0" "0" "0" "0" "opaque or indirect call #23115"
+"sys" "source" "sys.time.Timers" "sys.time.Timers.cancel" "226" "pass" "supported" "sys.time.Timers.cancel" "226" "sys.time.Timers" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.time.Timers" "sys.time.Timers.nextDeadline" "227" "pass" "supported" "sys.time.Timers.nextDeadline" "227" "sys.time.Timers" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.time.Timers" "sys.time.Timers.poll" "228" "pass" "supported" "sys.time.Timers.poll" "228" "sys.time.Timers" "0" "0" "0" "0" "0" "1" ""
+"sys" "source" "sys.time.Timers" "sys.time.Timers.<new>" "229" "pass" "supported" "sys.time.Timers.<new>" "229" "sys.time.Timers" "1" "0" "0" "4" "0" "0" ""
+"RuntimeArgs" "source" "RuntimeArgs" "class:RuntimeArgs.<clinit>" "2" "pass" "supported" "class:RuntimeArgs.<clinit>" "2" "RuntimeArgs" "0" "0" "0" "0" "0" "0" ""
+"RuntimeArgs" "source" "RuntimeArgs" "simple_args" "6" "direct" "raw address" "simple_args" "6" "RuntimeArgs" "2" "0" "2" "0" "0" "1" "raw address escapes lifetime tracking #248"
+"A_helloWorld" "object" "A_helloWorld" "class:A_helloWorld.<clinit>" "2" "blocked" "raw address" "sys.io.writeOff" "95" "sys.io" "0" "0" "0" "0" "0" "0" "call #4079 -> sys.io.writeOff: raw address escapes lifetime tracking #3733"
+"BubbleSort" "object" "BubbleSort" "class:BubbleSort.<clinit>" "2" "pass" "supported" "class:BubbleSort.<clinit>" "2" "BubbleSort" "0" "0" "0" "0" "0" "0" ""
+"BubbleSort" "object" "BubbleSort" "sort" "202" "pass" "supported" "sort" "202" "BubbleSort" "0" "0" "0" "0" "0" "2" ""
+"BubbleSort" "object" "BubbleSort" "main" "203" "blocked" "raw address" "sys.io.writeOff" "95" "sys.io" "0" "0" "0" "0" "0" "0" "call #5100 -> sys.io.writeOff: raw address escapes lifetime tracking #4714"
+"BubbleSort" "object" "BubbleSort" "usage" "204" "blocked" "raw address" "sys.io.writeOff" "95" "sys.io" "0" "0" "0" "0" "0" "0" "call #5978 -> sys.io.writeOff: raw address escapes lifetime tracking #4714"
+"Capitalize" "object" "Capitalize" "class:Capitalize.<clinit>" "2" "pass" "supported" "class:Capitalize.<clinit>" "2" "Capitalize" "0" "0" "0" "0" "0" "0" ""
+"Capitalize" "object" "Capitalize" "main" "3" "blocked" "raw address" "sys.io.writeOff" "96" "sys.io" "1" "0" "1" "0" "0" "0" "call #4536 -> sys.io.writeOff: raw address escapes lifetime tracking #4076"
+"FileIO" "object" "FileIO" "class:FileIO.<clinit>" "2" "pass" "supported" "class:FileIO.<clinit>" "2" "FileIO" "0" "0" "0" "0" "0" "0" ""
+"FileIO" "object" "FileIO" "main" "3" "direct" "raw address" "main" "3" "FileIO" "2" "0" "0" "0" "0" "0" "raw address escapes lifetime tracking #6573"
+"FileIO" "object" "FileIO" "_error2" "203" "direct" "raw address" "_error2" "203" "FileIO" "2" "0" "0" "0" "0" "0" "raw address escapes lifetime tracking #6670"
+"FileIO" "object" "FileIO" "_error" "204" "direct" "indirect call" "_error" "204" "FileIO" "0" "0" "0" "0" "0" "0" "opaque or indirect call #6874"
+"Dijkstra" "object" "Dijkstra" "class:Dijkstra.<clinit>" "2" "pass" "supported" "class:Dijkstra.<clinit>" "2" "Dijkstra" "0" "0" "0" "0" "0" "0" ""
+"Dijkstra" "object" "Dijkstra" "shortestPath" "202" "blocked" "variable size" "sys.adt.bitset._grow" "48" "sys.adt.bitset" "3" "0" "1" "0" "0" "4" "call #7543 -> sys.adt.bitset._grow: variable-size allocation #6202"
+"Dijkstra" "object" "Dijkstra" "usage" "203" "blocked" "raw address" "sys.io.writeOff" "95" "sys.io" "0" "0" "0" "0" "0" "0" "call #7528 -> sys.io.writeOff: raw address escapes lifetime tracking #6699"
+"Dijkstra" "object" "Dijkstra" "main" "204" "blocked" "raw address" "sys.io.writeOff" "95" "sys.io" "2" "0" "0" "0" "0" "2" "call #7568 -> sys.io.writeOff: raw address escapes lifetime tracking #6699"
+"Graphics" "object" "Graphics" "class:Graphics.<clinit>" "2" "pass" "supported" "class:Graphics.<clinit>" "2" "Graphics" "0" "0" "0" "0" "0" "0" ""
+"Graphics" "object" "Graphics" "main" "3" "direct" "raw address" "main" "3" "Graphics" "1" "0" "0" "0" "0" "3" "raw address escapes lifetime tracking #6220"
+"Clock" "object" "Clock" "class:Clock.<clinit>" "2" "pass" "supported" "class:Clock.<clinit>" "2" "Clock" "0" "0" "0" "0" "0" "0" ""
+"Clock" "object" "Clock" "main" "3" "direct" "raw address" "main" "3" "Clock" "3" "0" "0" "0" "0" "1" "raw address escapes lifetime tracking #11014"
+"Clock" "object" "Clock" "_draw" "203" "blocked" "raw address" "sys.time.local" "185" "sys.time" "3" "0" "1" "0" "0" "2" "call #1002 -> sys.time.local: raw address escapes lifetime tracking #12253"
+"Clock" "object" "Clock" "_digit" "208" "pass" "supported" "_digit" "208" "Clock" "0" "0" "0" "0" "0" "1" ""
+"Clock" "object" "Clock" "_digital" "209" "pass" "supported" "_digital" "209" "Clock" "0" "0" "0" "0" "0" "1" ""
+"Clock" "object" "Clock" "_hand" "210" "direct" "indirect call" "_hand" "210" "Clock" "0" "0" "0" "0" "0" "0" "opaque or indirect call #2302"
+"Clock" "object" "Clock" "_analog" "211" "direct" "indirect call" "_analog" "211" "Clock" "0" "0" "0" "0" "0" "1" "opaque or indirect call #2540"
+"Breakout" "object" "Breakout" "class:Breakout.<clinit>" "2" "pass" "supported" "class:Breakout.<clinit>" "2" "Breakout" "1" "0" "0" "1" "0" "0" ""
+"Breakout" "object" "Breakout" "Breakout.Game.<init>" "3" "pass" "supported" "Breakout.Game.<init>" "3" "Breakout" "1" "0" "0" "1" "0" "1" ""
+"Breakout" "object" "Breakout" "_tick" "4" "pass" "supported" "_tick" "4" "Breakout" "0" "0" "0" "0" "0" "3" ""
+"Breakout" "object" "Breakout" "_cue" "5" "pass" "supported" "_cue" "5" "Breakout" "0" "0" "0" "0" "0" "0" ""
+"Breakout" "object" "Breakout" "_speed" "6" "pass" "supported" "_speed" "6" "Breakout" "0" "0" "0" "0" "0" "0" ""
+"Breakout" "object" "Breakout" "_paddle" "7" "pass" "supported" "_paddle" "7" "Breakout" "0" "0" "0" "0" "0" "0" ""
+"Breakout" "object" "Breakout" "_rebound" "8" "pass" "supported" "_rebound" "8" "Breakout" "0" "0" "0" "0" "0" "1" ""
+"Breakout" "object" "Breakout" "_brick" "9" "pass" "supported" "_brick" "9" "Breakout" "0" "0" "0" "0" "0" "0" ""
+"Breakout" "object" "Breakout" "_lostBall" "10" "pass" "supported" "_lostBall" "10" "Breakout" "0" "0" "0" "0" "0" "0" ""
+"Breakout" "object" "Breakout" "_reset" "11" "pass" "supported" "_reset" "11" "Breakout" "0" "0" "0" "0" "0" "1" ""
+"Breakout" "object" "Breakout" "_hud" "211" "pass" "supported" "_hud" "211" "Breakout" "0" "0" "0" "0" "0" "4" ""
+"Breakout" "object" "Breakout" "_bricks" "212" "pass" "supported" "_bricks" "212" "Breakout" "0" "0" "0" "0" "0" "1" ""
+"Breakout" "object" "Breakout" "_overlay" "213" "pass" "supported" "_overlay" "213" "Breakout" "0" "0" "0" "0" "0" "0" ""
+"Breakout" "object" "Breakout" "_draw" "214" "pass" "supported" "_draw" "214" "Breakout" "0" "0" "0" "0" "0" "1" ""
+"Breakout" "object" "Breakout" "_input" "215" "direct" "indirect call" "_input" "215" "Breakout" "0" "0" "0" "0" "0" "0" "opaque or indirect call #18288"
+"Breakout" "object" "Breakout" "debounce" "216" "direct" "indirect call" "debounce" "216" "Breakout" "0" "0" "0" "0" "0" "0" "opaque or indirect call #6273"
+"Breakout" "object" "Breakout" "_serve" "217" "pass" "supported" "_serve" "217" "Breakout" "0" "0" "0" "0" "0" "1" ""
+"Breakout" "object" "Breakout" "" "218" "direct" "indirect call" "" "218" "Breakout" "0" "0" "0" "0" "0" "0" "opaque or indirect call #18379"
+"Breakout" "object" "Breakout" "" "219" "pass" "supported" "" "219" "Breakout" "0" "0" "0" "0" "0" "0" ""
+"Breakout" "object" "Breakout" "Breakout.Game.<new>" "220" "pass" "supported" "Breakout.Game.<new>" "220" "Breakout" "1" "0" "0" "2" "0" "0" ""
+"Breakout" "object" "Breakout" "_number" "221" "pass" "supported" "_number" "221" "Breakout" "0" "0" "0" "0" "0" "1" ""
+"Breakout" "object" "Breakout" "_tone" "222" "direct" "raw address" "_tone" "222" "Breakout" "1" "0" "0" "0" "0" "1" "raw address escapes lifetime tracking #18921"
+"Breakout" "object" "Breakout" "_sqrt" "223" "pass" "supported" "_sqrt" "223" "Breakout" "0" "0" "0" "0" "0" "1" ""
+"Breakout" "object" "Breakout" "main" "224" "direct" "raw address" "main" "224" "Breakout" "4" "0" "1" "0" "0" "3" "raw address escapes lifetime tracking #19167"
+"TicTacToe" "object" "TicTacToe" "class:TicTacToe.<clinit>" "2" "pass" "supported" "class:TicTacToe.<clinit>" "2" "TicTacToe" "0" "0" "0" "0" "0" "0" ""
+"TicTacToe" "object" "TicTacToe" "main" "3" "blocked" "raw address" "sys.io.writeOff" "96" "sys.io" "4" "0" "1" "0" "0" "3" "call #9529 -> sys.io.writeOff: raw address escapes lifetime tracking #7910"
+"TicTacToe" "object" "TicTacToe" "_validMove" "207" "direct" "indirect call" "_validMove" "207" "TicTacToe" "3" "0" "1" "0" "0" "2" "opaque or indirect call #9266"
+"TicTacToe" "object" "TicTacToe" "_winner" "208" "pass" "supported" "_winner" "208" "TicTacToe" "0" "0" "0" "0" "0" "1" ""
+"TicTacToe" "object" "TicTacToe" "_finished" "209" "blocked" "raw address" "sys.io.writeOff" "96" "sys.io" "0" "0" "0" "0" "0" "1" "call #9491 -> sys.io.writeOff: raw address escapes lifetime tracking #7910"
+"TicTacToe" "object" "TicTacToe" "_threat" "210" "pass" "supported" "_threat" "210" "TicTacToe" "0" "0" "0" "0" "0" "1" ""
+"TicTacToe" "object" "TicTacToe" "_cpu" "211" "pass" "supported" "_cpu" "211" "TicTacToe" "0" "0" "0" "0" "0" "2" ""
+"TicTacToe" "object" "TicTacToe" "_draw" "212" "blocked" "opaque body" "sys.ary.capacity" "64" "sys.ary" "2" "0" "0" "0" "0" "2" "call #8785 -> sys.aryu8._grow: call #8389 -> sys.ary.capacity: opaque body: allocation contract unavailable"
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "class:TicTacToeGraphical.<clinit>" "2" "pass" "supported" "class:TicTacToeGraphical.<clinit>" "2" "TicTacToeGraphical" "0" "0" "0" "0" "0" "0" ""
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "main" "3" "direct" "raw address" "main" "3" "TicTacToeGraphical" "2" "0" "0" "0" "0" "4" "raw address escapes lifetime tracking #9861"
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "_sound" "203" "pass" "supported" "_sound" "203" "TicTacToeGraphical" "0" "0" "0" "0" "0" "0" ""
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "_reset" "204" "pass" "supported" "_reset" "204" "TicTacToeGraphical" "0" "0" "0" "0" "0" "1" ""
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "_square" "205" "pass" "supported" "_square" "205" "TicTacToeGraphical" "0" "0" "0" "0" "0" "0" ""
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "_move" "206" "pass" "supported" "_move" "206" "TicTacToeGraphical" "0" "0" "0" "0" "0" "2" ""
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "_finished" "207" "pass" "supported" "_finished" "207" "TicTacToeGraphical" "0" "0" "0" "0" "0" "1" ""
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "_winningLine" "208" "pass" "supported" "_winningLine" "208" "TicTacToeGraphical" "0" "0" "0" "0" "0" "1" ""
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "_winner" "209" "pass" "supported" "_winner" "209" "TicTacToeGraphical" "0" "0" "0" "0" "0" "0" ""
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "_threat" "210" "pass" "supported" "_threat" "210" "TicTacToeGraphical" "0" "0" "0" "0" "0" "1" ""
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "_cpu" "211" "pass" "supported" "_cpu" "211" "TicTacToeGraphical" "0" "0" "0" "0" "0" "2" ""
+"TicTacToeGraphical" "object" "TicTacToeGraphical" "_draw" "212" "pass" "supported" "_draw" "212" "TicTacToeGraphical" "0" "0" "0" "0" "0" "4" ""
+"LocalArray" "probe" "LocalArray" "class:LocalArray.<clinit>" "2" "blocked" "variable size" "work_noInline" "3" "LocalArray" "0" "0" "0" "0" "0" "0" "call #111 -> work_noInline: variable-size allocation #36"
+"LocalArray" "probe" "LocalArray" "work_noInline" "3" "direct" "variable size" "work_noInline" "3" "LocalArray" "1" "0" "1" "0" "0" "1" "variable-size allocation #36"
+"ReturnedArray" "probe" "ReturnedArray" "class:ReturnedArray.<clinit>" "2" "blocked" "variable size" "make_noInline" "3" "ReturnedArray" "0" "0" "0" "0" "0" "0" "call #53 -> make_noInline: variable-size allocation #36"
+"ReturnedArray" "probe" "ReturnedArray" "make_noInline" "3" "direct" "variable size" "make_noInline" "3" "ReturnedArray" "1" "0" "1" "0" "0" "0" "variable-size allocation #36"
+"OverwrittenSlot" "probe" "OverwrittenSlot" "class:OverwrittenSlot.<clinit>" "2" "blocked" "loop retention" "work_noInline" "8" "OverwrittenSlot" "0" "0" "0" "0" "0" "0" "call #206 -> work_noInline: loop#148 carries new#277:OverwrittenSlot.Thing across its backedge; collection/overlap destinations not implemented"
+"OverwrittenSlot" "probe" "OverwrittenSlot" "OverwrittenSlot.Thing.<new>" "5" "pass" "supported" "OverwrittenSlot.Thing.<new>" "5" "OverwrittenSlot" "1" "0" "0" "1" "0" "0" ""
+"OverwrittenSlot" "probe" "OverwrittenSlot" "OverwrittenSlot.Holder.<new>" "7" "pass" "supported" "OverwrittenSlot.Holder.<new>" "7" "OverwrittenSlot" "1" "0" "0" "1" "0" "0" ""
+"OverwrittenSlot" "probe" "OverwrittenSlot" "work_noInline" "8" "direct" "loop retention" "work_noInline" "8" "OverwrittenSlot" "2" "0" "0" "0" "0" "1" "loop#148 carries new#277:OverwrittenSlot.Thing across its backedge; collection/overlap destinations not implemented"
+"ReusedObject" "probe" "ReusedObject" "class:ReusedObject.<clinit>" "2" "pass" "supported" "class:ReusedObject.<clinit>" "2" "ReusedObject" "0" "0" "0" "0" "0" "0" ""
+"ReusedObject" "probe" "ReusedObject" "ReusedObject.Thing.<new>" "5" "pass" "supported" "ReusedObject.Thing.<new>" "5" "ReusedObject" "1" "0" "0" "1" "0" "0" ""
+"ReusedObject" "probe" "ReusedObject" "read_noInline" "6" "pass" "supported" "read_noInline" "6" "ReusedObject" "0" "0" "0" "0" "0" "0" ""
+"ReusedObject" "probe" "ReusedObject" "work_noInline" "7" "pass" "supported" "work_noInline" "7" "ReusedObject" "1" "0" "0" "1" "0" "1" ""
diff --git a/chapter33/docs/allocation-survey.md b/chapter33/docs/allocation-survey.md
new file mode 100644
index 00000000..eb803c78
--- /dev/null
+++ b/chapter33/docs/allocation-survey.md
@@ -0,0 +1,256 @@
+# Allocation survey: existing Simple programs
+
+Measured 2026-11-21, at TypeCheck with assertions enabled. This surveys the
+current analysis; it does not implement or validate stack allocation at runtime.
+
+The fixed-size plans handle useful object graphs and native borrowing.
+Variable-sized storage is now the broadest limitation; the original baseline
+below records the earlier native-call and raw-address blockers.
+
+## Update: lexical KeepAlive
+
+The parser now retains converted addresses through their lexical scope exits.
+This admits integer arguments forwarded through Simple wrappers and addresses
+stored and reloaded within that scope. Conditional conversions, overwritten
+locals, return/break/continue paths, implicit branch scopes, forward calls, and
+imported bodies are covered by the chapter tests. A returned integer does not
+promote its backing storage into the caller's lifetime.
+
+The large-program totals remain 134/179 accepted for `sys` source and
+52/68 for the examples' own functions. Those programs had already passed
+the simpler borrowing checks or encountered another blocker first.
+
+The current first-cause breakdown for the 45 rejected `sys` functions is:
+
+| Cause | Direct | Blocked callers |
+|---|---:|---:|
+| Variable-size allocation | 7 | 32 |
+| Recursion | 1 | 4 |
+| Native pointer result without an allocation contract | 1 | 0 |
+
+First-cause counts can change with optimization order when a function has several
+blockers. The native-result requirement remains; this is not permission to assume
+that a native-produced pointer is borrowed. The examples' remaining failures
+are eleven missing imported bodies, four variable-size plans, and one indirect
+callback.
+
+The next substantial gains need variable-size plans and allocation contracts
+for imported bodies. Recursion and Breakout's indirect callback remain separate
+work. `_exit` still needs the agreed nonreturning handling. KeepAlive is erased
+before scheduling; storage placement still uses function/iteration frames and
+does not yet change runtime allocation.
+
+## Update: native borrowing
+
+After adopting the native non-retention rule and tracking pointer-derived
+integer SSA values through calls, the same cohorts improve as follows. The
+remaining sections preserve the original survey and its baseline snapshot.
+
+| Cohort | Accepted before | Accepted now | With user allocations now |
+|---|---:|---:|---:|
+| `sys` source, 179 functions | 98 | 134 | 12 |
+| Examples' own 68 functions | 43 | 52 | 4 |
+
+Hello world's executable initializer now gets a supported plan. Clock's `_hand`
+and `_analog` pass. Breakout improves from 19/24 to 22/24; its `_tone` buffer is
+now accepted as scratch. `sys.time.local` now accepts the DateTime result and
+its temporary native buffer.
+
+Of the remaining 45 `sys` rejections, 38 stop at variable-sized allocation
+(seven direct, 31 callers), five at recursion (one direct, four callers), and
+two at native-produced Simple pointers without allocation contracts. No call
+or raw-address rejection remains the first cause in that source cohort.
+Precompiled-library examples still expose missing imported summaries, such as
+`sys.ary.capacity`, `sys.ary.copy`, and `sys.aryu8.str0`. Breakout's `debounce`
+also contains a genuinely indirect callback.
+
+This change is analysis-only. `_exit` is accepted under the native borrowing
+rule, but is not yet a nonreturning intrinsic. The ABI, allocation lowering,
+and default runtime allocation behavior are unchanged.
+
+## Original baseline
+
+| Cohort | Function summaries | Accepted | Accepted with user allocations |
+|---|---:|---:|---:|
+| `sys`, compiled from source | 179 | 98 | 11 |
+| Ten examples, their own functions only | 68 | 43 | 3 |
+| Native argument conversion, compiled separately | 2 | 1 | 0 |
+
+These counts include retained/exported functions and class initializers, not
+just functions reachable by direct calls from an entry point. Native declarations
+without a Simple body are not separate function summaries. A passing function
+can still call other passing functions that allocate. The last column counts
+fresh storage represented in that function's plan, including imported callee
+sites; it excludes compiler class objects. It is not a count of dynamic objects.
+All 87 other accepted `sys` functions have no remaining allocation sites.
+
+## What passes
+
+The accepted `sys` plans include 19 user-storage sites: 16 with result destinations
+and three retained through constructor receiver `arg2`.
+
+- `sys.time.utc` builds and returns a DateTime: a real fixed-size factory, with
+ calendar computation and conditional paths.
+- `sys.time.Timers.<new>` returns a timer object and its three fixed initial
+ arrays. The initializer puts the arrays in the receiver's lifetime; the factory
+ composes that into the returned graph.
+- `sys.aryu8.<new>` and `sys.text.begin` return a byte-vector object plus its
+ initial backing array. Growing that array is a separate, rejected operation.
+- Bitset construction, Button construction, and scanner construction pass.
+- All six `sys.scan` summaries and all six `sys.draw.Button` summaries pass.
+ Canvas has 15 passing summaries out of 18: the drawing operations work on
+ borrowed storage; construction and resizing encounter allocation/call barriers.
+- Breakout's Game factory returns the Game and its 192-element brick array.
+ Its initializer correctly gives the array the receiver's lifetime. Most game
+ logic and drawing routines pass too.
+
+The accepted `sys` functions contain 26 loop summaries. Ordinary loops over
+existing storage are not the main obstacle.
+
+## Where the library stops
+
+The pass records the first rejection in a function. A caller can then inherit
+that rejection. Following those call chains gives:
+
+| First underlying reason | Directly rejected functions | Blocked callers | Total |
+|---|---:|---:|---:|
+| Opaque or indirect call | 35 | 18 | 53 |
+| Raw-address conversion | 11 | 10 | 21 |
+| Variable-size allocation | 2 | 2 | 4 |
+| Recursion | 1 | 2 | 3 |
+| Total | 49 | 32 | 81 |
+
+These are first-cause counts, not independent fixes or predicted acceptance
+after removing a barrier. For example, `sys.aryu8._grow` accounts for 16 rejected
+summaries including itself. Its first rejection is the `_exit(1)` call used for
+overflow failure, but it also allocates a variable-sized array. Accepting that
+call alone would not make growth work.
+
+Independent inspection of the collected IR finds 21 variable-sized NewNodes
+across 19 `sys` functions. Only two functions currently report that as their
+first direct failure: `sys.text.end` and `sys.adt.bitset._grow`.
+
+There were no first-reported loop-retention, cyclic-field-path, or unmapped-origin
+failures in this library cohort. Earlier rejection barriers can hide them.
+
+## The examples
+
+These use the normal precompiled `sys` library. Counts include only each
+example's own functions, avoiding repeated counts of imported library exports.
+The compiler may load and inline imported bodies; some others remain opaque.
+
+| Example | Accepted / total | Accepted with allocations | Representative failure |
+|---|---:|---:|---|
+| Hello world | 0 / 1 | 0 | String address passed to output |
+| BubbleSort | 2 / 4 | 0 | Output; sorting itself passes |
+| Capitalize | 1 / 2 | 0 | Output; main also has a variable-sized array |
+| FileIO | 1 / 4 | 0 | Native I/O and raw addresses |
+| Dijkstra | 1 / 4 | 0 | Bitset growth; output |
+| Graphics | 1 / 2 | 0 | Raw address passed to graphics |
+| Clock | 3 / 7 | 0 | Graphics/time pointers; scalar libm calls |
+| Breakout | 19 / 24 | 3 | Input/audio/graphics calls |
+| TicTacToe | 4 / 8 | 0 | I/O, growth, an opaque imported `sys.ary.capacity` |
+| TicTacToeGraphical | 11 / 12 | 0 | Main's graphics boundary |
+
+No example's `main` receives a complete supported plan; hello world's executable
+class initializer is rejected too. High per-function acceptance is not yet a
+working automatically managed program.
+
+## Analysis improvements versus storage decisions
+
+| Case | What is missing | Likely action |
+|---|---|---|
+| Clock's `sin`/`cos`, clocks, input polling, `_exit` | Known native behavior is treated as opaque | Targeted native contracts/recognition; no application rewrite should be needed |
+| Array passed to synchronous I/O or copying audio loader | Lifetime/provenance is lost at conversion to `i64` | Wrapper contract and provenance tracking through the native call |
+| Opaque imported Simple function | No serialized allocation summary | Export/import lifetime summaries; avoid changing source merely to force inlining |
+| Runtime-sized local scratch array | Immediate rejection of nonconstant size | Keep the lifetime result and represent a runtime size; later lower a local reservation |
+| Finished variable-sized result, such as `sys.text.end` | Caller needs storage whose size the callee discovers | Destination/buffer/region choice under the agreed design; possibly a small library rewrite |
+| Replaced vector/Canvas backing array | Dynamic sizing plus proof that old aliases are no longer usable | Analysis for reclaiming old buffers; explicit storage policy where proof fails |
+| Fixed-size object repeatedly replacing `Holder.c` | Weak updates never kill the old reference | Overwrite/liveness analysis; this is not inherently unbounded storage |
+| `Timers._add` retries recursively after growing | SCC support, plus three variable-sized arrays | Defer SCCs; changing the retry to a loop alone would not solve storage |
+
+Native scalar signatures must not be accepted indiscriminately: an `i64` may
+carry a raw pointer. Contracts must describe the actual wrapper, including
+whether it retains a passed address or creates returned storage.
+
+One concrete native allocation requires attention:
+[`simple_text_float`](../src/main/c/simple_crt.c) uses `malloc` to create a
+Simple-format byte array and returns it. There is no Simple NewNode for that
+allocation. A non-retaining-call annotation is insufficient: the result needs
+an allocation/ownership contract, or the wrapper should write into caller-provided
+storage. This is a useful first native-interface design case.
+
+The separately compiled [`simple_args`](../src/main/smp/sys/rt/simple_args.smp)
+has two variable-sized allocation sites: an outer reference array and byte
+arrays created inside its initializer loop. Its first rejection is the raw
+destination passed to `memcpy`. Beyond that contract, it exercises the planned
+collection destination and variable-sized returned graph.
+
+## Small reductions
+
+The survey probe also compiles four isolated cases, without native calls:
+
+| Probe | Result |
+|---|---|
+| Allocate `i64[n]`, fill/read it, return a scalar | Rejected: variable-size allocation |
+| Return a freshly allocated `i64[n]` | Rejected for the same reason, despite a different storage problem |
+| Repeatedly replace `h.c` with a fresh fixed-size Thing, then read the last one | Rejected: Thing survives the backedge |
+| Allocate one mutable Thing before the loop, overwrite its scalar field, borrow it each iteration | Accepted: one Thing in the function frame |
+
+The overwrite reduction has no saved reference to an older Thing. It needs an
+analysis improvement, not a language prohibition. Reusing one mutable object
+is a possible rewrite for that particular program, not a general replacement
+for allocations with distinct observable identities.
+
+## Suggested next work
+
+First, admit a small audited set of scalar native calls and specify borrowing
+for the common array wrappers. Preserve those contracts across imported calls.
+That removes the largest observational barrier without tackling SCCs.
+
+Then distinguish local variable-sized scratch from returned/growing storage,
+and tackle the fixed-size overwrite proof. Re-run this survey after those steps;
+the first-cause distribution should become much more informative.
+
+For an initial lowering implementation, the passing Game, Timers, byte-vector,
+and DateTime factories already supply useful fixed-size object graphs. Use them
+alongside the existing scratch/winner poster children. Do not wait for every
+library operation to pass before validating real storage placement.
+
+## Reproduction and limitations
+
+[`AllocationSurvey.java`](AllocationSurvey.java) is a standalone observational
+probe. It reads private analysis collections by reflection rather than adding
+production compiler APIs. It does not change contracts, suppress rejections,
+link native code, run games, or lower allocation plans.
+The [function-level snapshot](allocation-survey-functions.tsv) contains the
+cohorts above and the four reductions, with first-cause chains and site counts.
+Full dumps, allocation sites, and call lists are written under
+`build/allocation-survey/<name>-<mode>/`.
+
+From `chapter33`, after building the Java compiler and the normal `sys` objects:
+
+```powershell
+javac -cp build/classes/main -d build/allocation-survey docs/AllocationSurvey.java
+java -ea -Xss16m -Xmx2g -XX:ActiveProcessorCount=2 -cp 'build/classes/main;build/allocation-survey' AllocationSurvey sys source
+java -ea -Xss16m -Xmx2g -XX:ActiveProcessorCount=2 -cp 'build/classes/main;build/allocation-survey' AllocationSurvey Clock object
+java -ea -Xss16m -Xmx2g -XX:ActiveProcessorCount=2 -cp 'build/classes/main;build/allocation-survey' AllocationSurvey OverwrittenSlot probe
+```
+
+Use each example's filename without `.smp`; modes are `source` and `object`.
+`RuntimeArgs source` compiles the native-startup helper. Probe names are
+`LocalArray`, `ReturnedArray`, `OverwrittenSlot`, and `ReusedObject`.
+On bash use `:` instead of `;` in the classpath.
+
+The auxiliary all-source run succeeds for hello world, BubbleSort, Capitalize,
+and Breakout. Breakout's own 19/24 result is unchanged with library source visible.
+The other six examples stop in Parse on qualified `sys` types, before Allocation;
+they are not counted as lifetime failures. The source-mode probe prepends a
+private `sys` binding to request library discovery; that does not resolve those
+type-name failures. A first all-source Breakout run exhausted the default Java
+stack in `Node._walk`; all reported runs use `-Xss16m`.
+
+Counts use seed 456 and optimized IR, so inlining and dead-code removal affect
+which sites and functions remain. They measure the current conservative analysis,
+not runtime allocation frequency, memory saved, or proof that future lowering is
+correct. Existing compiler files were not changed for this survey.
diff --git a/chapter33/docs/growing-array-rewrites.md b/chapter33/docs/growing-array-rewrites.md
new file mode 100644
index 00000000..4bb0d141
--- /dev/null
+++ b/chapter33/docs/growing-array-rewrites.md
@@ -0,0 +1,258 @@
+# Growing arrays: first source rewrites
+
+Design notes, 2026-11-21. Writable array length and the constructor return rules
+below are agreed; the parser and allocator do not implement these examples yet.
+They follow the
+[growing-array survey](growing-arrays-survey.md).
+
+The proposed rule is: `new E[]` creates an initially empty array whose growth
+belongs to the allocating lexical scope. Leaving that scope ends growth,
+including returning the array. Its storage can outlive that scope; its permission
+to grow cannot. Element mutation remains allowed. Returning from a helper that
+merely borrows someone else's builder does not end the owner's growth phase.
+
+## BrainFuck
+
+The interpreter body stays the same. The relevant old code in
+[BrainFuckTest](../src/test/java/com/seaofnodes/simple/BrainFuckTest.java) is:
+
+```text
+val output = new sys.aryu8();
+u8[] !data = new u8[100];
+// ... interpreter loop ...
+output.add(data[d]); // the '.' command
+// ...
+return output; // a growable wrapper
+```
+
+Proposed replacement:
+
+```text
+val data = new u8[100]; // fixed tape, before the growing tail
+val output = new u8[];
+// ... same interpreter loop ...
+output += data[d]; // the '.' command
+// ...
+return output; // ends this scope: result has fixed length
+```
+
+The caller changes from `brain_fuck().write(sys.libc.STDOUT)` to
+`sys.io.write(sys.libc.STDOUT, brain_fuck())`.
+`+=` appends to the existing array; it does not reassign the `val` binding.
+There is no wrapper, final trim-copy, or explicit finish operation.
+
+The proposed whole-array constructor gives the boundary a dedicated body:
+
+```text
+val data = new u8[100];
+val output = new u8[]{ ->
+ // ... interpreter; '.' does self += data[d] ...
+}; // length is now fixed
+sys.io.write(sys.libc.STDOUT, output);
+```
+
+The tape is scratch, while the output survives. Their placement still needs to
+permit reclaiming scratch without invalidating the output; ending growth alone
+does not establish that layout. The existing frozen BrainFuck workloads remain
+useful compiler regressions and need not be rewritten with the new example.
+
+## Agreed constructor scope and exits
+
+The whole-array body executes immediately as a lexical construction scope.
+It can read and write outer-scope variables, subject to their ordinary mutability
+and lifetime rules. It has its own return target and result destination, as if
+it were a function, but does not impose ordinary function capture restrictions.
+`self` is a fixed binding to the array being constructed.
+
+| Within `new E[]{ -> ... }` | Meaning |
+|---|---|
+| Reach the closing brace | Finish growth and yield `self`, regardless of the last statement's value |
+| `return self;` | Finish successfully now, skipping remaining constructor statements |
+| `return null;` | Abandon construction now and yield null |
+| `return anythingElse;` | Error in this context; the explicit result choices are self and null |
+| `return;` | Use `return self;` for explicit successful completion |
+| `break;` | Exit the innermost loop in this constructor; continue after that loop |
+| `continue;` | Continue the innermost loop in this constructor |
+
+The nearest function-like body owns a return. A constructor-local return does
+not return from the enclosing function. Conversely, returning from a helper
+called by the constructor returns only from the helper. Break and continue
+cannot cross the constructor boundary to a surrounding loop; without a local
+loop they are errors. EOF can therefore use `break` to reach final trimming,
+while a read failure uses `return null` to bypass the successful completion path.
+
+This fits the existing indexed generator's return scope:
+
+```text
+new int[N]{i -> if(i==0) return 7; return i*i;}
+```
+
+There, `return` supplies one element and the generator proceeds to the next
+index. In the zero-argument body it supplies the outcome of the whole-array
+construction. A null return in a generator of nullable elements remains a null
+element, not cancellation of the array. That distinction follows which body is
+executing; it must not depend on whether a loop happens to surround the return.
+The current indexed-generator parser rejects assignments to captured locals;
+that existing implementation restriction must not be carried over to the new
+whole-array construction scope.
+
+A whole-array body with a possible null exit has a nullable result. A body
+with no possible null exit has a non-null result. This does not change
+allocation-failure behavior or make every `new Foo` expression nullable.
+Generalizing fallible construction to ordinary classes is a separate choice;
+successful class construction would still have to satisfy initialization rules.
+
+Failure abandons the private construction storage, not its earlier side effects:
+file bytes already read remain consumed, and writes to outer locals and external
+state remain.
+Cleanup must preserve errno. References into abandoned storage must not survive
+its reclamation; the lifetime check includes the failure edge.
+
+### Other exit spellings considered
+
+- `self = null` with an implicit exit hides control flow in assignment; rejected.
+- `self = null; break` separates the failure marker from the exit, makes self
+ nullable inside the body, and normally breaks only the innermost loop. Avoid it.
+- `self# = -1; break` violates the valid-length invariant and overloads an unsigned
+ length with an error sentinel. Negative lengths remain invalid.
+- `break null` could be part of a general value-producing loop/block design, but
+ here it needs a new target rule: does it exit the loop or the constructor?
+ A labeled value-break could disambiguate it, at the cost of more syntax.
+
+The chosen forms are `return self` / `return null`, ordinary loop breaks, and implicit
+successful completion at the constructor's closing brace. No magic assignment,
+negative-length sentinel, or dedicated finish keyword is required.
+
+## Growing and trimming with `#`
+
+Try extending the existing length notation rather than adding a finish keyword:
+
+| Expression | Proposed meaning during construction |
+|---|---|
+| `buf#` | Current accessible element count |
+| `buf# = n` | Extend or trim the tail to checked length `n` |
+| `buf# += n` | Add `n` accessible elements at the end |
+| `buf# -= n` | Remove `n` elements; reject/check underflow |
+| `buf += value` | Append one initialized element |
+
+Length changes are permitted only while the allocating scope still owns growth,
+and when placement permits the tail adjustment. Exiting that scope removes the
+permission through all aliases. Ordinary `new E[N]` arrays never acquire it.
+Zero-length and same-length updates are legal; neither underflow nor length
+overflow wraps. Even a zero-length request to change a finished array's length
+uses an operation for which the growth permission is absent.
+
+For `u8`, extending the length gives initialized, zero-valued elements, consistent
+with current array construction. That keeps the entire visible array safe to
+read before the native call. A later optimization may omit initialization when
+it proves the bytes are overwritten or trimmed before observation. Zero-copy
+does not itself promise zero initialization cost. For inline objects without a
+default initializer, increasing `#` alone cannot construct valid elements; those
+arrays need append/construction into the new element destinations.
+
+## `io.read`: direct read into the growing tail
+
+The [current implementation](../src/main/smp/sys/io.smp) has three buffers over
+its lifetime: a fixed 8 KiB read chunk, the builder's replacement buffers, and
+the final exact-length array. Its data path is:
+
+```text
+libc.read(fd, chunkAddress, chunk#);
+buf._grow(count);
+ary.copy(buf.buf, buf.len, chunk, 0, count);
+buf.len += count;
+// At EOF:
+val out = new u8[buf.len];
+return ary.copy(out, 0, buf.buf, 0, buf.len);
+```
+
+Proposed replacement, including short reads, interrupts, errors, and the array
+length limit:
+
+```text
+val read = { i32 fd ->
+ return new u8[]{ ->
+ u32 used = 0;
+ while( true ) {
+ i64 room = sys.integer.MAX_U32 - used;
+ if( room > 8192 ) room = 8192;
+
+ // An exactly maximum-sized stream can still end successfully.
+ // Only this boundary case needs a separate byte for the EOF probe.
+ if( room == 0 ) {
+ val probe = new u8[1];
+ i64 ptr = probe;
+ i64 got = libc.read(fd, ptr, 1);
+ if( got < 0 ) {
+ if( libc.errno() == libc.EINTR ) continue;
+ return null;
+ }
+ if( got != 0 ) {
+ libc.set_errno(libc.EOVERFLOW);
+ return null;
+ }
+ break;
+ }
+
+ self# = used + room; // space for the next block, without moving self
+ i64 got = 0;
+ {
+ i64 ptr = self;
+ got = libc.read(fd, ptr + used, room);
+ } // end this raw-address borrowing scope
+ if( got < 0 ) {
+ if( libc.errno() == libc.EINTR ) continue;
+ return null; // abort this constructor
+ }
+ if( got == 0 ) break;
+ used += got; // native read promises 0 <= got <= room
+ }
+ self# = used; // drop unwritten tail; no data copy
+ }; // implicit success: yield finished self
+};
+```
+
+Here `used` counts input bytes and `self#` includes the writable tail. A short read
+advances `used` without shrinking on every iteration. The next length assignment
+restores up to 8 KiB of free tail. EINTR leaves `used` unchanged, so retry does not
+accumulate more space. EOF trims once. Empty input returns an empty array.
+The one-byte limit probe preserves acceptance of a stream whose length equals
+the maximum; reporting overflow before probing would wrongly reject it. On an
+oversized stream this version consumes one extra byte before failing, rather
+than the old implementation's possible full extra chunk.
+
+No regular read chunk and no final copy remain. Physical alignment or mapped-page
+slack can remain after trimming; the logical result length is exactly `used`.
+
+## What these examples settle, and what they do not
+
+Floating formatting uses the same extend/fill/trim pattern as direct I/O:
+remember the current length, extend by enough space for the requested format,
+let a bounded C helper fill that tail and return the actual count, then trim to
+the old length plus that count. This is an agreed interface direction; the helper
+name and signature are not yet implemented. Any snprintf terminator needs space
+in the writable tail but is excluded from the published length. No temporary
+formatted-string allocation or final copy is needed.
+
+An arbitrary expression within interpolation is ordinary code running while an
+array is growing. It must satisfy the same stack-allocation rules and leave the
+growing end free for the next extension; interpolation adds no special exemption
+or additional lifetime mechanism.
+
+Both examples have a natural end of growth, so neither needs `finish(buf)` or
+`stop growing` syntax. The proposed new operation is a checked, writable `#`
+while growth is allowed. Scope exit does not guess the number of bytes a native
+call wrote: `io.read` must explicitly set the final length from `used`.
+
+For a non-moving implementation, the returned storage must already be in an
+area that survives the callee, or its owning storage group must transfer to the
+result's destination. Ordinary callee-local RSP storage cannot simply survive a
+return. A chunk-chain handle can transfer ownership of storage, but a chain of
+nonadjacent chunks is not one contiguous `u8[]`. Neither syntax example resolves
+that placement choice by itself.
+
+Growing a non-moving array preserves existing interior references. Trimming is
+different: references into the removed tail must be gone before that storage is
+reclaimed or reused. For these byte programs there are no typed interior
+references, and the native borrow ends before the final trim. Future inline
+objects need that restriction; non-moving alone does not make shrinking safe.
diff --git a/chapter33/docs/growing-arrays-survey.md b/chapter33/docs/growing-arrays-survey.md
new file mode 100644
index 00000000..f8f7e2b1
--- /dev/null
+++ b/chapter33/docs/growing-arrays-survey.md
@@ -0,0 +1,222 @@
+# Growing arrays: where grow-in-place fits
+
+Surveyed 2026-11-21. Most current byte builders have a single construction
+phase and could finish as ordinary arrays. The persistent counterexamples are
+bitsets, timers, and canvas buffers. The choice belongs to a use of a collection,
+not to every instance of `aryu8` or `aryi64`.
+
+This is a source survey, not an implemented placement proof or a runtime profile.
+It covers chapter33's Simple library, examples, Simple programs embedded in Java
+tests, and retained regression workloads. Earlier chapter copies are not counted
+again. Compiler Java collections appear separately as future Simple-in-Simple
+requirements. No language or library behavior changed during the survey.
+The [first source rewrites](growing-array-rewrites.md) show BrainFuck and direct
+block reads using scope-ended growth and a proposed writable array length.
+
+## Construction that finishes
+
+“Candidate” below means growth has a recognizable end. It does not yet prove
+that the physical allocation end is free, or solve returning variable-sized data.
+
+| Code | Observed growth and subsequent use | Grow-in-place assessment |
+|---|---|---|
+| [Interpolation](../src/main/java/com/seaofnodes/simple/parser/Strings.java), [text.integer/string](../src/main/smp/sys/text.smp) | Parser creates one builder, appends literal pieces and formatted expressions, then calls `end`. Integer formatting uses a fixed 22-byte digit scratch array. | Strong candidate. Fixed scratch needs placement before/beside the growing storage; formatting helpers need to borrow the active builder. Arbitrary interpolation expressions can introduce nested allocation. |
+| [text.floating/time](../src/main/smp/sys/text.smp) | Both obtain a temporary string and append it to the outer builder. `floating` gets a native allocation; `time` calls another Simple formatter. | Candidate after arranging temporary storage or changing to destination-writing helpers. Not automatically one free growing end; see below. |
+| [aryi64.str](../src/main/smp/sys/aryi64.smp) | Appends brackets, numbers, and separators, removes the final separator, then returns the builder. [BubbleSort](examples/BubbleSort.smp) and [StreamIOTest](../src/test/java/com/seaofnodes/simple/StreamIOTest.java) append a newline afterwards. | Construction is localized, but its present API returns a still-growable value. Prefer an append-into-destination formatter, with the caller adding the newline before finishing. |
+| [parseAryI64](../src/main/smp/sys/aryi64.smp) | One scanner and one result vector; append parsed numbers, validate closing syntax, return. BubbleSort sorts the result; Dijkstra only reads it. Neither appends more numbers. | Strong candidate for a finished mutable `i64[]`. Freeze length, not element stores. Returned variable-sized storage still needs a destination. |
+| [io.read](../src/main/smp/sys/io.smp) | Allocates an 8 KiB scratch chunk before starting the builder. Reads until EOF, appends each received prefix, then copies to an exact-length result. Errors discard the partial result. | Strong candidate. The scratch buffer is already separate from the growing output. Finish could avoid the final copy if the result's lifetime and placement permit it. Keep short-read/EINTR/error behavior. |
+| [BrainFuckTest](../src/test/java/com/seaofnodes/simple/BrainFuckTest.java) | One output builder, one fixed 100-byte tape, no other growing collection in the interpreter. Output is consumed only after execution finishes. | Strong candidate. Place the fixed tape before the growing output, or in reserved fixed storage. Finish at interpreter exit; the current wrapper-return API needs changing or an explicit result destination. |
+| [TicTacToe._draw](examples/TicTacToe.smp) | Builds one board rendering and immediately writes it. No builder escapes. | Simplest local candidate. This particular rendering is exactly 60 bytes, so a fixed array also suffices. |
+| [FileIO](examples/FileIO.smp), [Dijkstra's diagnostic output](examples/Dijkstra.smp) | FileIO builds its message before opening/writing/reading the file, then compares it with the readback. Diagnostics build and write once. | Finish FileIO's message before later I/O allocations; its storage remains live for comparison. The literal message can also be sized exactly. Diagnostics are local builders. |
+| [time._format/elapsed/zoneName](../src/main/smp/sys/time.smp) | Formatters build and finish one result. `zoneName` first fills a fixed 128-byte buffer, learns `n`, then builds another buffer and copies again in `text.end`. | `_format`/`elapsed` are localized builders. `zoneName` needs no growing array: after the native call, allocate exactly `n` bytes and copy once. All returned results retain the destination question. |
+
+The [original BrainFuck workload](../src/test/java/com/seaofnodes/simple/spill/BrainFuckTest-testBrainFuck.smp)
+does `new u8[output# + 1]` and copies the old output on every `.` command.
+For N emitted bytes that copies N(N-1)/2 old bytes, in addition to writing the
+N new bytes. It is the clearest avoidable-copy example. The aryu8 version already
+uses geometric growth. Keep the historical workload if its purpose remains
+cross-target compiler comparison; add a new builder version alongside it.
+
+## Growth interleaved with continued use
+
+The production Simple library has five implementations that replace backing
+arrays to increase capacity: `aryu8`, `aryi64`, `bitset`, `Timers`, and `Canvas`.
+Timers replaces three arrays together. The first two support the construction
+cases above; the other three illustrate why we still need another storage choice.
+
+| Code | Why a single temporary construction scope is insufficient | Suitable direction |
+|---|---|---|
+| [adt.bitset](../src/main/smp/sys/adt/bitset.smp) | Random indexed `set`/`tset` can increase capacity between reads, clears, and other work. | General instance: retain a replaceable backing array or use chunks. [Dijkstra](examples/Dijkstra.smp) knows the bit universe from `nodes`, so reserve `(nodes+63)/64` words before its loop instead. |
+| [time.Timers](../src/main/smp/sys/time/Timers.smp) | IDs, deadlines, and periods grow together; registration, cancellation, and polling interleave. [TimeTest](../src/test/java/com/seaofnodes/simple/TimeTest.java) forces growth past eight slots. Clock itself registers only one timer. | A mini-arena owned by the Timers instance can hold replacement arrays. Alternatively, fixed chunks of inline timer entries would avoid copying and exercise value objects; that is a representation change, not just append syntax. Three independent arrays cannot all own one contiguous growing end. |
+| [draw.Canvas.resize](../src/main/smp/sys/draw/Canvas.smp) | Capacity increases across window events, interleaved with drawing, timers, and text formatting. Smaller sizes reuse capacity. On growth the old pixels are discarded, not copied. | Retain replacement-buffer behavior in the Canvas lifetime group. A deliberately reserved non-moving region is plausible for a small number of windows, but should be an explicit choice. Chunking pixels directly would change the contiguous graphics interface. |
+
+The generic aryu8 API also permits `clear`, `undo`, reads, and later appends.
+[StreamIOTest](../src/test/java/com/seaofnodes/simple/StreamIOTest.java) exercises
+that mutable-container behavior. The small `_Vec` in
+[Chapter21Test.testArmVectorGrowth](../src/test/java/com/seaofnodes/simple/Chapter21Test.java)
+is another explicit doubling/copy implementation outside sys. Its particular
+caller builds five integers in one expression; the generic type allows later
+growth. The frozen BubbleSort and seed-reproduction sources contain older copies
+of the same byte/integer vector pattern.
+
+## Two constraints exposed by the survey
+
+### Explicit containers for interleaved growth
+
+Discussion direction: infer one active growing end, with properly nested
+temporary work allowed. If multiple live arrays need interleaved extension at
+that end, reject with a concrete rewrite path. Do not automatically synthesize
+independent regions or a general collector to preserve the source representation.
+
+A proposed diagnostic at the failed extension:
+
+```text
+Cannot extend 'ids' here: live storage for 'due_ms' follows it.
+ 'ids' starts growing at ...
+ 'due_ms' is allocated at ... and is still needed at ...
+Use one array of inline timer entries, or explicit resizable containers
+such as aryu32 and aryi64 for independently growing buffers.
+```
+
+This diagnoses unavailable tail space while growth is still permitted. Trying
+to grow an array whose constructor has already ended instead reports that its
+length is fixed, with the constructor boundary and the attempted growth shown.
+
+For Timers the programmer can choose either representation:
+
+- Array of inline Timer entries containing id, due, and period, with explicit
+ resize logic. Under the previously agreed notation this is `new *Timer[8]`
+ (with appropriate element initialization), rather than an array of Timer
+ references. No per-entry object allocation or pointer chase is required;
+ padding and field-scan locality can still differ from struct-of-arrays.
+- Keep the struct-of-arrays layout, using three explicit container instances:
+ one aryu32 and two aryi64 collections. These containers need not own the
+ shared stack's growing end.
+
+Agreed allocator direction: growable containers use power-of-two backing arrays
+and deleted backing arrays are recycled through a buddy allocator. Resize obtains
+a larger chunk, copies the used elements, publishes the replacement, and calls
+`delete(old)` to retire the old backing allocation. This moving representation
+does not promise stable
+direct interior references through resize. Container/index handles and copied
+primitive/reference values remain useful interfaces.
+
+Agreed safety rule: a deletable array has a different type from an ordinary
+array; its spelling is still undecided. It disallows interior references and
+requires unique access and no escaping aliases. Deletion consumes the owning
+access, with no outstanding borrows or other usable aliases surviving it.
+The compiler checks this rule; it is not an unchecked promise by the library.
+Copied primitive elements and copied object references are not references into
+the backing storage. Container/index handles can resolve through the current
+buffer without retaining the retired one.
+
+In resize, replacing the container's backing field removes that owning access
+to the old buffer; the local `old` then supplies the access consumed by delete.
+If another usable alias remains, diagnose that alias and the attempted deletion.
+Ordinary arrays retain their automatic-lifetime behavior and cannot be deleted.
+Raw-address borrowing must also respect the no-surviving-use requirement.
+
+This differs from deletable class slots, whose stale references remain type-safe.
+Buddy splitting/coalescing can change the array extent and layout. An old array
+header can become element data after reuse, so even bounds checks can read the
+wrong length. Merely preserving the element type is not enough to inherit the
+class-slot post-delete guarantees. The agreed uniqueness rule excludes those
+stale accesses, allowing the buddy allocator to recycle the whole block.
+Moving the length field out of the allocation is therefore not needed for this
+safety argument; it remains a separate, useful layout optimization.
+
+`text.begin()` currently returns a newly created builder. For the proposed
+scope-owned growing array, interpolation should establish that storage in the
+expression's owning scope, then let helpers borrow it. Keeping `begin()` unchanged
+and hoping the inliner erases its call would make a language lifetime rule depend
+on optimization. The same issue applies to factories returning fresh growable
+wrappers; it is separate from a helper appending to an existing destination.
+
+One logical builder does not imply one free physical end. For example,
+[Clock._draw](examples/Clock.smp) interpolates `sys.time.formatLocal(...)` into
+an outer string. The outer builder is started before that expression is evaluated.
+The inner formatter returns its finished array, then the outer builder grows
+while reading that array. With both on the same growing end, the inner result
+still occupies the space the outer wants. This is not the easy nested case where
+the child has unwound before the parent resumes growing.
+
+Agreed follow-up: append time formatting directly into a supplied destination.
+For floating formatting, pre-grow the destination by a sufficient bound, pass
+the writable tail and its capacity to the C helper, and receive the actual byte
+count. Trim the unused tail afterwards. The helper fills the destination directly;
+it does not allocate a returned string or copy from an intermediate output array.
+The bound must account for the value, format, width, precision, and any terminating
+NUL needed by the C implementation. The NUL is not part of the final string length.
+The existing [simple_text_float](../src/main/c/simple_crt.c) still allocates;
+changing it to this interface remains implementation work.
+
+Arbitrary interpolation expressions follow the ordinary rules for code executing
+inside any growable-array constructor. Their allocation/lifetime plan must leave
+the required growing end free when extension resumes. If no legal plan exists,
+the normal allocation analysis rejects the program. There is no separate
+interpolation allocation rule. Helpers growing a caller's destination likewise
+use the general call-frame placement rules.
+
+Finished growth does not solve the return destination. `io.read`, parsed number
+arrays, formatted strings, and BrainFuck results can finish before returning,
+but the caller still does not know their size in advance. A chunk-backed lifetime
+group with a fixed-size handle is a candidate for the previously deferred result
+storage decision. An explicit copy/destination remains another option. We should
+not silently introduce returning a still-growing stack-tail array.
+
+## Aliases and future inline elements
+
+Backing-array references are already observable, even without interior pointers:
+
+- `aryi64` accepts a caller-provided backing array; it need not own the only reference.
+- `buf`/`pixels` are exposed. StreamIOTest saves `b.buf`; DrawTest saves old and
+ grown pixel arrays and checks reuse when resizing within capacity.
+- `text.end(b)` currently copies into a read-only array and leaves `b` usable.
+ A consuming finish operation changes that contract. Existing callers that are
+ done with `b` can migrate; the general API cannot silently change meaning.
+- `aryi64.str()` callers demonstrably continue growing the returned value.
+
+A mini-arena makes its allocated blocks stationary. It does not make a vector
+stationary if the vector later copies its contents into a larger block. An
+array of future inline objects can promise stable direct interior references
+only with the non-moving choice; those references also inherit the backing
+storage's lifetime. Movable containers can expose values or `(container,index)`
+handles instead. Truncating/clearing and reusing inline slots will need its own
+reference-validity rule, even when the storage address stays fixed.
+
+Old backing arrays cannot be recycled merely because the wrapper now points to
+a new array: another reference may still name the old one. Retaining all blocks
+until the lifetime group unwinds is the simple safe policy. Earlier recycling
+needs proof that those references are gone. Allocator chunk recycling here is
+distinct from the language's explicit `delete` and its weaker post-delete rules.
+
+## Compiler collections: future Simple-in-Simple cases
+
+| Existing Java use | Storage implication |
+|---|---|
+| [Node inputs/outputs](../src/main/java/com/seaofnodes/simple/node/Node.java), backed by [Ary](../src/main/java/com/seaofnodes/simple/util/Ary.java) | Many independently growing collections, mutated throughout optimization. Embedded small vectors plus overflow storage fit; one reserved growing region per Node does not. Entries currently hold references, not inline Nodes. |
+| [CodeGen linker/call/CFG lists](../src/main/java/com/seaofnodes/simple/codegen/CodeGen.java) | Broad lifetimes, but several lists grow interleaved. Being long-lived does not alone make their ends free. Separate explicit areas or a common chunk allocator are options. |
+| [Serialize.write](../src/main/java/com/seaofnodes/simple/codegen/Serialize.java), [Lexer.stringPart](../src/main/java/com/seaofnodes/simple/parser/Lexer.java) | Local output accumulation followed by a completed byte result. Candidates for finishable builders, subject to helper temporaries and the return destination. |
+| [Encoding](../src/main/java/com/seaofnodes/simple/codegen/Encoding.java), [BAOS](../src/main/java/com/seaofnodes/simple/util/BAOS.java) | Instruction bytes, constant data, and writable data have separate buffers; emission also creates metadata, patches earlier bytes, and can replace the instruction buffer during compaction. This needs an explicit layout plan or independent buffers, not blanket conversion of BAOS. |
+| [IntHashMap](../src/main/java/com/seaofnodes/simple/util/IntHashMap.java) | Growth rehashes entries. Reserving more address space does not remove that semantic relocation. A future inline-entry reference cannot promise stability through rehash. |
+
+The native MiniFB adapter has a separate resizable repaint buffer in
+[simple_minifb.c](../src/main/c/simple_minifb.c). It copies the Simple pixels;
+the retained native buffer is not a retained pointer into the Simple array.
+
+## Suggested first cases
+
+1. BrainFuck output: one unknown-length append stream, fixed scratch, finish;
+ first consume it within the same activation to isolate growth from return placement.
+2. `io.read`: chunked input, error unwind, and a finished variable-sized result.
+3. Integer/string interpolation, then nested time formatting: borrowed builder
+ helpers, fixed scratch, and the first real competing-temporary case.
+4. Timers: persistent growth and three coupled arrays; compare grouped replacement
+ buffers with chunks of inline entries rather than forcing it into the first case.
+
+Some current variable-size failures are not growing arrays at all: `str0`,
+`Canvas` construction, and `text.end` know their length when they allocate.
+Supporting runtime-sized fixed arrays is independently useful. This survey does
+not predict a new accepted-function count: the current pass also rejects loop
+retention, returned variable-sized storage, and recursive Timers._add before
+these proposed storage representations exist.
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java b/chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java
index 0c4feeee..ee83d3a4 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/codegen/Allocation.java
@@ -13,23 +13,34 @@ import java.util.*;
*/
public final class Allocation {
private final Summary[] _summaries;
+ private final Summary _entrySummary;
private final ArrayList<Summary> _postorder = new ArrayList<>();
- // Destination bits: result, static storage, then Call/Parm input indices.
+ // Destination bits: result, static storage, Call/Parm input indices, then
+ // borrowed field paths. A child's storage need not share its holder's owner.
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 NewNode _allocation; // null for borrowed or static storage
+ public final int _arg; // >=2: Parm index, -1: static, 0: fresh/path
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<>();
+ public Summary _frame; // activation creating this object
+ public Summary _scope; // scratch frame, null for an external destination
+ private CFGNode _birth; // allocation control, or importing call
+ private final ArrayList<String> _destinations;
+ private final HashMap<String,Site> _loads = new HashMap<>();
+ private Site _base; // borrowed field origin, e.g. arg3.c
+ private String _field;
+ private int _depth;
- private Site(NewNode allocation, int arg, String name) {
+ private Site(Summary sum, NewNode allocation, int arg, String name) {
_allocation=allocation; _arg=arg; _name=name;
+ _destinations=sum._destinations;
_bytes=allocation!=null && allocation.size()._type instanceof TypeInteger size && size.isConstant()
? size.value() : -1;
if( arg>=2 ) _owners.set(arg);
@@ -37,23 +48,43 @@ public final class Allocation {
}
public String destination() {
- if( _owners.isEmpty() ) return "frame";
+ if( _owners.isEmpty() ) return _scope==null || _scope._loop==null ? "frame" : _scope.name()+" iteration";
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(" & ");
+ if( _owners.get(RESULT) ) sb.p("result & ");
+ if( _owners.get(STATIC) ) sb.p("static & ");
+ ArrayList<String> names = new ArrayList<>();
+ for( int i=_owners.nextSetBit(2); i>=0; i=_owners.nextSetBit(i+1) )
+ names.add(_destinations.get(i));
+ Collections.sort(names); // Paths are discovered in arbitrary order.
+ for( String name : names ) sb.p(name).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. */
+ * Borrowed field paths describe incoming contents separately from stores. */
- // Per-function summary; allocation sites; failure reasons
+ // An activation summary: a function or one loop iteration. Loops share their
+ // enclosing function's SSA/Site vocabulary, so composition needs no cloning
+ // or argument substitution. Calls substitute that vocabulary in compose().
public static final class Summary {
- public final FunNode _fun;
+ public final FunNode _fun; // owning function, also for loop frames
+ public final LoopNode _loop; // null for a function activation
+ public Summary _parent;
+ public final ArrayList<Summary> _frames = new ArrayList<>();
public final ArrayList<Site> _sites = new ArrayList<>();
+ // Ports map formal/output identity to its value. Loop Phis are entry
+ // and continuation ports; captured SSA values name themselves. Memory
+ // ports are included; their retention effects are summarized below.
+ public final IdentityHashMap<Node,Node> _entry = new IdentityHashMap<>();
+ public final IdentityHashMap<Node,Node> _exit = new IdentityHashMap<>();
+ public final IdentityHashMap<Node,Node> _next = new IdentityHashMap<>();
public final HashSet<Site> _returns = new HashSet<>();
+ public final HashSet<Site> _retained = new HashSet<>();
+ public final HashSet<Site> _continues = new HashSet<>();
+ public final HashSet<Site> _scratch = new HashSet<>();
+ private final HashSet<Site> _escapes = 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
@@ -61,18 +92,38 @@ public final class Allocation {
// 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 final IdentityHashMap< Node,HashSet<Site>> _values;
+ // Call -> returned storage after substituting actuals and closing effects.
+ private final IdentityHashMap<CallNode,HashSet<Site>> _results;
+ private final BitSet _resolved;
+ private final BitSet _raw; // Scalar expressions feeding lexical lifetime endpoints
+ private final IdentityHashMap<LoopNode,Summary> _loops = new IdentityHashMap<>();
+ private final ArrayList<String> _destinations;
+ private final Site _static;
+ private int _pathLimit; // own reads plus the path depths imported at calls
+ private boolean _changed;
- private Summary(FunNode fun) { _fun=fun; }
+ private Summary(FunNode fun) {
+ _fun=fun; _loop=null;
+ _values=new IdentityHashMap<>();
+ _results=new IdentityHashMap<>();
+ _resolved=new BitSet();
+ _raw=new BitSet();
+ _destinations=new ArrayList<>(List.of("result","static"));
+ _static=new Site(this,null,-1,"static");
+ }
+ private Summary(Summary fun, LoopNode loop) {
+ _fun=fun._fun; _loop=loop;
+ _values=fun._values; _results=fun._results; _resolved=fun._resolved;
+ _raw=fun._raw;
+ _destinations=fun._destinations; _static=fun._static;
+ }
+ public String name() { return _loop==null ? _fun.label() : "loop#"+_loop._nid; }
// 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);
+ if( !supported() ) throw new IllegalStateException("Allocation "+name()+": "+_reject);
return this;
}
// Collect first rejection
@@ -81,9 +132,14 @@ public final class Allocation {
public Allocation(CodeGen code) {
_summaries = new Summary[code._linker._len];
+ Summary entry=null;
for( FunNode fun : code._linker )
- if( fun!=null && !fun.isDead() && !fun._type.isHigh() )
- _summaries[fun.sig().fidx()] = new Summary(fun);
+ if( fun!=null && !fun.isDead() && !fun._type.isHigh() ) {
+ Summary sum=new Summary(fun);
+ _summaries[fun.sig().fidx()] = sum;
+ if( code.entryClinitName().equals(fun._name) ) entry=sum;
+ }
+ _entrySummary=entry;
for( Summary sum : _summaries )
if( sum!=null )
visit(sum);
@@ -116,6 +172,14 @@ public final class Allocation {
// Collection interesting function body and call sites
collect(sum);
for( CallNode call : sum._calls ) {
+ if( nativeCall(call) ) {
+ // Native code borrows its arguments for this call only.
+ // Returned storage still needs an explicit origin contract.
+ Type ret=call.tfp().ret();
+ if( !(ret instanceof TypeInteger || ret instanceof TypeFloat) )
+ sum.reject("native result storage has no allocation contract at call #"+call._nid);
+ continue;
+ }
Summary callee = target(call);
if( callee==null ) sum.reject("opaque or indirect call #"+call._nid);
else {
@@ -140,6 +204,15 @@ public final class Allocation {
return idx>=0 && idx<_summaries.length ? _summaries[idx] : null;
}
+ // Unlike external(), this excludes unknown targets and mixed Simple/native
+ // target sets. Every possible target must obey the native borrowing rule.
+ private static boolean nativeCall(CallNode call) {
+ if( !(call.fptr()._type instanceof TypeFunPtr fp) || XInt.isHigh(fp.fidxs()) || fp.nfcns()==0 ) return false;
+ for( int idx=XInt.next(fp.fidxs(),-1); idx>=0; idx=XInt.next(fp.fidxs(),idx) )
+ if( CodeGen.CODE.externFunc(idx)==null ) return false;
+ return true;
+ }
+
// 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
@@ -147,8 +220,9 @@ public final class Allocation {
private void collect(Summary sum) {
BitSet seen = new BitSet();
ArrayDeque<Node> work = new ArrayDeque<>();
- // Start from the return
+ // Start at both ends: zero-exit loops cannot be reached from Return.
work.push(sum._fun.ret());
+ work.push(sum._fun);
// Repeat until entire function is walked
while( !work.isEmpty() ) {
Node n = work.pop();
@@ -156,6 +230,10 @@ public final class Allocation {
seen.set(n._nid);
// Add to function body
sum._nodes.add(n);
+ if( n instanceof CFGNode cfg && !(cfg instanceof ReturnNode) &&
+ (cfg==sum._fun || !cfg.isFunLeaf()) )
+ for( Node use : cfg._outputs )
+ if( use instanceof CFGNode next && !cfg.skip(next) ) work.push(next);
if( n instanceof CFGNode )
for( Node use : n._outputs )
if( use instanceof NewNode alloc && alloc.ctrl()==n ||
@@ -170,10 +248,7 @@ public final class Allocation {
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);
+ if( n instanceof LoopNode loop ) sum._loops.put(loop,new Summary(sum,loop));
// CLInit accesses static state, not caller parameters. Its body is
// analyzed separately; stores publishing local objects to static
@@ -188,35 +263,92 @@ public final class Allocation {
in._type instanceof TypeMem || pointer(in) || in instanceof NewNode) )
work.push(in);
}
+ keepOrigins(sum,seen);
}
+ // Follow the scope endpoint backwards, not all uses of an integer address.
+ // Memory round trips and wrapper calls need no provenance: the original
+ // conversion is kept here until its own lexical scope ends.
+ private static void keepOrigins(Summary sum, BitSet seen) {
+ ArrayDeque<Node> work=new ArrayDeque<>();
+ for( Node n : sum._nodes ) if( n instanceof KeepAliveNode ) work.push(n.in(1));
+ while( !work.isEmpty() ) {
+ Node n=work.pop();
+ if( pointer(n) || n instanceof ConstantNode || n instanceof CFGNode ||
+ n instanceof LoadNode || n.isFunLeaf() ||
+ n instanceof ProjNode || sum._raw.get(n._nid) ) continue;
+ sum._raw.set(n._nid);
+ if( !seen.get(n._nid) ) { seen.set(n._nid); sum._nodes.add(n); }
+ for( Node in : n._inputs ) if( in!=null ) work.push(in);
+ }
+ }
// Post-order work during the Call Graph visit
private void build(Summary sum) {
+ loopFrames(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);
+ Site site = new Site(sum,alloc,0,"new#"+alloc._nid+":"+alloc._ts._name);
+ site._birth=(CFGNode)alloc.ctrl();
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());
+ while( sum._destinations.size()<=parm._idx )
+ sum._destinations.add("arg"+sum._destinations.size());
+ Site site = new Site(sum,null,parm._idx,"arg"+parm._idx+":"+parm.label());
sum._sites.add(site);
sum._values.put(parm,set(site));
}
+ if( n instanceof LoadNode && pointer(n) ) sum._pathLimit++;
}
- 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);
+ // Import fresh storage once per call, even though its reference edges
+ // may need several local rounds. No repeated walk of a callee's IR.
+ IdentityHashMap<CallNode,IdentityHashMap<Site,HashSet<Site>>> imports=new IdentityHashMap<>();
+ for( CallNode call : sum._calls ) {
+ if( nativeCall(call) ) continue;
+ Summary callee=target(call);
+ IdentityHashMap<Site,HashSet<Site>> map=new IdentityHashMap<>();
+ imports.put(call,map);
+ sum._results.put(call,new HashSet<>());
+ map.put(callee._static,set(sum._static));
+ int depth=0;
+ for( Site site : callee._sites ) {
+ depth=Math.max(depth,site._depth);
+ if( site==callee._static ) continue;
+ HashSet<Site> values=new HashSet<>();
+ if( site._allocation!=null && !site._owners.isEmpty() ) {
+ Site copy=new Site(sum,site._allocation,0,"call#"+call._nid+"/"+site._name);
+ copy._birth=call;
+ if( site._owners.get(STATIC) ) copy._owners.set(STATIC);
+ sum._sites.add(copy);
+ values.add(copy);
+ }
+ map.put(site,values);
}
+ sum._pathLimit+=depth;
}
- sum._returns.addAll(refs(sum,sum._fun.ret().expr()));
+
+ // Loads, stores, and call effects depend on each other. Solve their weak
+ // unions before assigning owners: caching an early empty load would lose
+ // a later-discovered store. Targets, fields, and call results grow
+ // monotonically, including cyclic loop Phis. Each expression is visited
+ // once per round; a cycle uses the targets discovered so far.
+ do {
+ sum._changed=false;
+ sum._resolved.clear();
+ for( CallNode call : sum._calls ) if( !nativeCall(call) ) compose(sum,call,imports.get(call));
+ for( Node n : sum._nodes ) {
+ if( pointer(n) || sum._raw.get(n._nid) ) refs(sum,n);
+ if( n instanceof StoreNode store && pointer(store.val()) )
+ if( edge(refs(sum,store.ptr()),store._name,refs(sum,store.val())) ) sum._changed=true;
+ }
+ if( pointer(sum._fun.ret().expr()) && sum._returns.addAll(refs(sum,sum._fun.ret().expr())) ) sum._changed=true;
+ } while( sum._changed && sum._reject==null );
for( Site site : sum._returns ) site._owners.set(RESULT);
if( !sum._static._fields.isEmpty() ) sum._sites.add(sum._static);
@@ -232,6 +364,11 @@ public final class Allocation {
if( dst._owners.cardinality() != before ) work.push(dst);
}
}
+ if( sum._reject==null ) {
+ frameBoundaries(sum);
+ summarizeFrame(sum,sum,imports);
+ if( sum._reject==null ) placeFrames(sum);
+ }
// 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.
@@ -242,46 +379,301 @@ public final class Allocation {
return n!=null && (n._type instanceof TypeMemPtr || n._type instanceof TypePtr);
}
+ // LoopTree already establishes reducible nesting and each CFG's tightest
+ // containing loop. Allocation only supplies the corresponding frame summaries.
+ private static void loopFrames(Summary sum) {
+ for( Summary frame : sum._loops.values() ) {
+ CFGNode.LoopTree tree=frame._loop._ltree;
+ assert tree!=null && tree._head==frame._loop && tree._par!=null;
+ frame._parent=tree._par._head instanceof StartNode ? sum : sum._loops.get(tree._par._head);
+ assert frame._parent!=null : "Missing enclosing loop summary";
+ frame._parent._frames.add(frame);
+ }
+ }
+
+ // Everything reachable through stored references. Used both for backedge
+ // safety and for retaining a winner's entire object graph on loop exit.
+ private static HashSet<Site> reachable(HashSet<Site> roots) {
+ HashSet<Site> seen=new HashSet<>(roots);
+ ArrayDeque<Site> work=new ArrayDeque<>(roots);
+ while( !work.isEmpty() )
+ for( HashSet<Site> children : work.pop()._fields.values() )
+ for( Site child : children )
+ if( seen.add(child) ) work.push(child);
+ return seen;
+ }
+
+ // A store to storage not born in this iteration can carry its value into
+ // the next iteration. Stores within an iteration's private graph are fine;
+ // a surviving root will bring that entire graph into reachable() instead.
+ private static void retained(HashSet<Site> dst, HashSet<Site> src,
+ HashSet<Site> born, HashSet<Site> carried) {
+ for( Site base : dst )
+ if( !born.contains(base) ) { carried.addAll(src); return; }
+ }
+
+ // Memory reaching the backedge exposes stores that a pointer-Phi check alone
+ // misses, e.g. an array allocated before the loop collecting each candidate.
+ // Stop at this header: entry memory and exit-only stores do not execute on
+ // the repeated path. Weak updates deliberately do not kill earlier stores.
+ private static ArrayList<Node> backMemory(LoopNode loop) {
+ ArrayList<Node> nodes=new ArrayList<>();
+ BitSet seen=new BitSet();
+ ArrayDeque<Node> work=new ArrayDeque<>();
+ for( Node use : loop._outputs )
+ if( use instanceof PhiNode phi && phi.region()==loop && phi._type instanceof TypeMem )
+ work.push(phi.in(2));
+ while( !work.isEmpty() ) {
+ Node n=work.pop();
+ if( seen.get(n._nid) ) continue;
+ seen.set(n._nid);
+ if( n instanceof PhiNode phi && phi.region()==loop ) continue;
+ if( n instanceof ParmNode || n.isFunLeaf() ) continue;
+ nodes.add(n);
+ if( n instanceof ProjNode proj ) work.push(proj.in(0));
+ else if( n instanceof CallEndNode end ) work.push(end.call());
+ else for( Node in : n._inputs )
+ if( in!=null && in._type instanceof TypeMem ) work.push(in);
+ }
+ return nodes;
+ }
+
+ private static Summary enclosing(Summary sum, CFGNode ctrl) {
+ if( ctrl==null || ctrl._type.isHigh() ) return sum;
+ assert ctrl._ltree!=null : "Missing LoopTree for CFG #"+ctrl._nid;
+ if( ctrl._ltree._head instanceof StartNode ) return sum;
+ Summary frame=sum._loops.get(ctrl._ltree._head);
+ assert frame!=null : "Missing loop summary for CFG #"+ctrl._nid;
+ return frame;
+ }
+
+ // Earliest control for a boundary value/use, without scheduling or changing
+ // the IR. New's pointer AND private-memory projections inherit its control.
+ // Floating scalar calculations can finish before returning from a frame;
+ // only their scalar result then crosses the boundary.
+ private static CFGNode control(Node n, IdentityHashMap<Node,CFGNode> cache, BitSet active) {
+ if( n instanceof CFGNode cfg ) return cfg;
+ if( n instanceof PhiNode phi ) return phi.region();
+ if( n.isFunLeaf() ) return null;
+ if( cache.containsKey(n) ) return cache.get(n);
+ if( active.get(n._nid) ) return CFGNode.safeCFG(n);
+ active.set(n._nid);
+ CFGNode ctrl=null;
+ for( Node in : n._inputs )
+ if( in!=null ) ctrl=CFGNode.deepest(ctrl,control(in,cache,active));
+ active.clear(n._nid);
+ cache.put(n,ctrl);
+ return ctrl;
+ }
+
+ // Export a value from its producing activation to the common ancestor,
+ // then capture it down to the consuming activation. These explicit ports,
+ // not a later placement scan of uses, define what must survive cleanup.
+ private static void crossing(Node value, Summary from, Summary to) {
+ Summary common=from;
+ while( true ) {
+ Summary up=to;
+ while( up!=null && up!=common ) up=up._parent;
+ if( up!=null ) break;
+ common=common._parent;
+ }
+ for( Summary frame=from; frame!=common; frame=frame._parent ) frame._exit.put(value,value);
+ for( Summary frame=to; frame!=common; frame=frame._parent ) frame._entry.put(value,value);
+ }
+
+ // Build the function/iteration interfaces in the existing SSA vocabulary.
+ // A loop's backedge is a return into its next activation, with Phi inputs
+ // supplying the arguments. Breaks/fallout export through the normal interface.
+ private void frameBoundaries(Summary sum) {
+ IdentityHashMap<Node,CFGNode> controls=new IdentityHashMap<>();
+ BitSet active=new BitSet();
+ for( Site site : sum._sites ) if( site._birth!=null ) {
+ site._frame=enclosing(sum,site._birth);
+ for( Summary frame=site._frame; frame!=sum; frame=frame._parent ) frame._sites.add(site);
+ }
+ for( Summary frame : sum._loops.values() )
+ for( Node use : frame._loop._outputs )
+ if( use instanceof PhiNode phi && phi.region()==frame._loop ) {
+ frame._entry.put(phi,phi.in(1));
+ frame._next.put(phi,phi.in(2));
+ }
+ sum._exit.put(sum._fun.ret(),sum._fun.ret().expr());
+ sum._exit.put(sum._fun.ret().mem(),sum._fun.ret().mem());
+ for( Node n : sum._nodes ) if( n instanceof ParmNode ) sum._entry.put(n,n);
+ if( sum._loops.isEmpty() ) return;
+ for( Node n : sum._nodes ) {
+ boundaryInputs(sum,n,controls,active);
+ // collect() skips scalar arithmetic. Merge Phis still define exit
+ // ports, including scalar results loaded from reclaimed scratch.
+ if( n instanceof CFGNode )
+ for( Node use : n._outputs )
+ if( use instanceof PhiNode phi && phi.region()==n ) boundaryInputs(sum,phi,controls,active);
+ }
+ // Scalar users were deliberately omitted by collect(). Their pointer
+ // operands still need boundary ports (e.g. a load after an outside call).
+ for( var value : sum._values.entrySet() ) {
+ Node n=value.getKey();
+ if( !pointer(n) || n instanceof ConstantNode ) continue;
+ Summary producer=enclosing(sum,control(n,controls,active));
+ for( Node use : n._outputs ) {
+ if( use.isFunLeaf() || use instanceof PhiNode phi && phi.region() instanceof LoopNode ) continue;
+ crossing(n,producer,enclosing(sum,control(use,controls,active)));
+ }
+ }
+ }
+
+ private static void boundaryInputs(Summary sum, Node n, IdentityHashMap<Node,CFGNode> controls, BitSet active) {
+ if( n.isFunLeaf() || n instanceof PhiNode phi && phi.region() instanceof LoopNode ) return;
+ Summary consumer=enclosing(sum,control(n,controls,active));
+ for( Node in : n._inputs ) {
+ if( in==null || in instanceof ConstantNode || in instanceof CFGNode ) continue;
+ // Ordinary integer users do not extend the borrowing scope. Only
+ // the endpoint and its expression carry raw-address obligations.
+ if( sum._raw.get(in._nid) &&
+ !(n instanceof KeepAliveNode) && !sum._raw.get(n._nid) ) continue;
+ crossing(in,enclosing(sum,control(in,controls,active)),consumer);
+ }
+ }
+
+ // The same summary closure for function returns and loop exits. Effects on
+ // incoming storage escape the frame even without a returned pointer. Loops
+ // additionally describe the continuation's values and memory effects.
+ private void summarizeFrame(Summary sum, Summary frame,
+ IdentityHashMap<CallNode,IdentityHashMap<Site,HashSet<Site>>> imports) {
+ frame._state=1;
+ for( Summary child : frame._frames ) {
+ summarizeFrame(sum,child,imports);
+ if( child._reject!=null ) frame.reject(child._reject);
+ }
+ HashSet<Site> born=new HashSet<>();
+ for( Site site : frame._sites ) if( site._allocation!=null ) born.add(site);
+ for( Node value : frame._exit.values() )
+ if( frame._loop!=null || pointer(value) ) frame._returns.addAll(refs(sum,value));
+ for( Site site : sum._sites )
+ if( !born.contains(site) )
+ for( HashSet<Site> children : site._fields.values() ) frame._retained.addAll(children);
+ frame._escapes.addAll(frame._returns);
+ frame._escapes.addAll(frame._retained);
+ // Static allocations retain their absolute lifetime across substitution.
+ for( Site site : born ) if( site._owners.get(STATIC) ) frame._escapes.add(site);
+ frame._escapes.addAll(reachable(frame._escapes));
+ if( frame._loop!=null ) {
+ for( var port : frame._next.entrySet() )
+ if( pointer(port.getKey()) || sum._raw.get(port.getKey()._nid) )
+ frame._continues.addAll(refs(sum,port.getValue()));
+ for( Node n : backMemory(frame._loop) ) {
+ if( n instanceof StoreNode store && pointer(store.val()) )
+ retained(refs(sum,store.ptr()),refs(sum,store.val()),born,frame._continues);
+ if( n instanceof CallNode call && !nativeCall(call) ) {
+ var map=imports.get(call);
+ for( Site site : target(call)._sites )
+ for( HashSet<Site> children : site._fields.values() )
+ for( Site child : children ) retained(map.get(site),map.get(child),born,frame._continues);
+ }
+ }
+ frame._continues.addAll(reachable(frame._continues));
+ for( Site site : frame._continues )
+ if( born.contains(site) ) {
+ frame.reject(frame.name()+" carries "+site._name+" across its backedge; collection/overlap destinations not implemented");
+ break;
+ }
+ }
+ frame._state=2;
+ }
+
+ // Function and iteration cleanup use the same rule. Promote escaped storage
+ // to the enclosing frame until its interface no longer exports that storage.
+ // A function's external results already have symbolic owner requirements.
+ // No RSP adjustment or actual reclamation is emitted by this planning pass.
+ private static void placeFrames(Summary sum) {
+ for( Site site : sum._sites ) if( site._frame!=null ) {
+ Summary scope=site._frame;
+ while( scope!=null && scope._escapes.contains(site) ) scope=scope._parent;
+ site._scope=scope;
+ if( scope!=null ) scope._scratch.add(site);
+ }
+ }
+
// 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;
+ private static boolean edge(HashSet<Site> dst, String field, HashSet<Site> src) {
+ if( src.isEmpty() ) return false;
+ boolean changed=false;
for( Site site : dst )
- site._fields.computeIfAbsent(field,k -> new HashSet<>()).addAll(src);
+ changed |= site._fields.computeIfAbsent(field,k -> new HashSet<>()).addAll(src);
+ return changed;
}
+ // Select a field's possible values, not its containing object's storage.
+ // Fresh objects have only the stores we see. Borrowed objects also have an
+ // incoming value, named by a path. That path is a separate borrowed Site,
+ // substituted against the actual object's fields at each call.
+ private HashSet<Site> field(Summary sum, HashSet<Site> bases, String name) {
+ HashSet<Site> values=new HashSet<>();
+ for( Site base : bases ) {
+ if( base._allocation==null ) {
+ Site child=base._loads.get(name);
+ if( child==null ) {
+ // Weak updates can invent an unbounded path even in straight
+ // line code: p.next=p.next.next. Stop at the body's finite
+ // read count rather than silently truncate possible origins.
+ // Memory-ordered field updates go here.
+ if( base._depth>=sum._pathLimit ) {
+ sum.reject("cyclic field-path expansion at "+base._name+"."+name);
+ continue;
+ }
+ String path=(base._arg>=2 ? "arg"+base._arg : base._name)+"."+name;
+ child=new Site(sum,null,0,path);
+ child._base=base; child._field=name; child._depth=base._depth+1;
+ if( base==sum._static || base._owners.get(STATIC) ) child._owners.set(STATIC);
+ else {
+ child._owners.set(sum._destinations.size());
+ sum._destinations.add(path);
+ }
+ base._loads.put(name,child);
+ sum._sites.add(child);
+ sum._changed=true;
+ }
+ values.add(child);
+ }
+ Set<Site> stored=base._fields.get(name);
+ if( stored!=null ) values.addAll(stored);
+ }
+ return values;
+ }
// 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.
+ // compose's caller-side targets; a load selects one field's 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).
+ // through that separate object graph. Cyclic SSA values use the prior known
+ // targets; the next local round propagates any newly discovered ones.
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;
+ if( n==null || !(pointer(n) || sum._raw.get(n._nid)) ) return new HashSet<>();
+ HashSet<Site> old = sum._values.computeIfAbsent(n,k -> new HashSet<>());
+ if( n instanceof ParmNode || sum._resolved.get(n._nid) ) return old;
+ sum._resolved.set(n._nid);
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.
+ // have static backing; field() handles their incoming contents.
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()));
+ Set<Site> result=sum._results.get(end.call());
+ if( result==null ) sum.reject("foreign call #"+end.call()._nid);
+ else values.addAll(result);
+ } else if( n instanceof LoadNode load ) {
+ values.addAll(field(sum,refs(sum,load.ptr()),load._name));
} 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)));
@@ -290,108 +682,165 @@ public final class Allocation {
values.addAll(refs(sum,n.in(1)));
} else if( n instanceof ArrayInitNode ) {
values.addAll(refs(sum,n.in(2)));
+ } else if( sum._raw.get(n._nid) ) {
+ for( Node in : n._inputs ) values.addAll(refs(sum,in));
} 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;
+ if( old.addAll(values) ) sum._changed=true;
+ return old;
}
// 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.
+ // borrowed field -> actual field targets. Fresh Sites were imported once by
+ // build, tagged with this call. 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);
+ private void compose(Summary sum, CallNode call, IdentityHashMap<Site,HashSet<Site>> map) {
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.
+ // Grow substitutions before transferring edges. A later local round
+ // resolves forward references and aliasing actuals. For example, after
+ // f(a,b) { a.c=new Thing; return b.c; }, f(h,h) returns that new Thing too.
for( Site site : callee._sites ) {
if( site._arg>=2 ) {
- if( site._arg>=call.nIns()-1 ) {
+ 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));
- }
+ else if( map.get(site).addAll(refs(sum,call.arg(site._arg))) ) sum._changed=true;
+ } else if( site._base!=null )
+ if( map.get(site).addAll(field(sum,map.get(site._base),site._field)) ) sum._changed=true;
}
// 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;
+ HashSet<Site> dst=map.get(site);
+ if( dst.isEmpty() ) continue;
for( var field : site._fields.entrySet() ) for( Site child : field.getValue() ) {
- Set<Site> src=map.get(child);
+ HashSet<Site> src=map.get(child);
if( src==null ) sum.reject("unmapped retained storage at call #"+call._nid);
- else edge(dst,field.getKey(),src);
+ else sum._changed |= 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);
+ else sum._changed |= sum._results.get(call).addAll(returned);
}
- return result;
+ }
+
+ // Printing has its own rooted traversal: reversing the analysis's entire
+ // forest would put disconnected bodies (e.g. inlined constructors) first.
+ private void printPostorder(Summary sum, BitSet seen, ArrayList<Summary> post) {
+ if( sum==null || seen.get(sum._fun._nid) ) return;
+ seen.set(sum._fun._nid);
+ ArrayList<CallNode> calls=new ArrayList<>(sum._calls);
+ calls.sort(Comparator.comparingInt(n -> n._nid));
+ for( CallNode call : calls ) printPostorder(target(call),seen,post);
+ post.add(sum);
}
@Override public String toString() {
StringBuilder out = new StringBuilder("Allocation destinations (analysis only; no stack lowering)\n");
- for( Summary sum : _postorder ) {
+ BitSet seen=new BitSet();
+ ArrayList<Summary> order=new ArrayList<>();
+ printPostorder(_entrySummary,seen,order);
+ Collections.reverse(order);
+ int reachable=order.size();
+ ArrayList<Summary> other=new ArrayList<>();
+ for( Summary sum : _summaries ) printPostorder(sum,seen,other);
+ Collections.reverse(other);
+ order.addAll(other);
+ for( int i=0; i<order.size(); i++ ) {
+ if( i==reachable && _entrySummary!=null )
+ out.append("\nOther retained functions (not reachable by direct calls from entry):\n");
+ Summary sum=order.get(i);
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");
+ .append(callee==null ? nativeCall(call) ? "native (borrow; no retain)" : "?" : 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");
+ printFrames(out,sum,"| ");
+ printStorage(out,sum,"| ");
+ printSites(out,"| cleanup on return -> ",sum._scratch);
+ printSites(out,"`-- return -> ",sum._returns," | ");
}
return out.toString();
}
+
+ // Show storage in its owning frame, which may enclose its allocation site.
+ // Borrowed/external destinations remain at function level.
+ private static void printStorage(StringBuilder out, Summary frame, String indent) {
+ ArrayList<Site> sites=new ArrayList<>();
+ for( Site site : frame._sites )
+ if( site._scope==frame || (frame._loop==null && site._scope==null) ) sites.add(site);
+ sites.sort(Comparator.comparing(s -> s._name));
+ for( Site site : sites ) {
+ out.append(indent).append('[').append(site.destination()).append("] ").append(site._name);
+ if( site._allocation!=null ) out.append(" (").append(site._bytes).append(" bytes)");
+ if( site._frame!=null && site._frame._loop!=null && site._scope!=site._frame )
+ out.append("; ").append(site._frame.name()).append(" winner");
+ out.append('\n');
+ ArrayList<String> edges=new ArrayList<>();
+ for( var field : site._fields.entrySet() ) for( Site child : field.getValue() )
+ edges.add(indent+" ."+field.getKey()+" --> "+child._name+"\n");
+ Collections.sort(edges);
+ for( String edge : edges ) out.append(edge);
+ }
+ }
+
+ private static void printSites(StringBuilder out, String label, HashSet<Site> sites) {
+ printSites(out,label,sites,", ");
+ }
+ private static void printSites(StringBuilder out, String label, HashSet<Site> sites, String separator) {
+ out.append(label).append('{');
+ ArrayList<String> names=new ArrayList<>();
+ for( Site site : sites ) names.add(site._name);
+ Collections.sort(names);
+ for( int i=0; i<names.size(); i++ ) {
+ if( i>0 ) out.append(separator);
+ out.append(names.get(i));
+ }
+ out.append("}\n");
+ }
+
+ private static void printPorts(StringBuilder out, String label, IdentityHashMap<Node,Node> ports) {
+ out.append(label).append('{');
+ ArrayList<Node> keys=new ArrayList<>(ports.keySet());
+ keys.sort(Comparator.comparingInt(n -> n._nid));
+ for( int i=0; i<keys.size(); i++ ) {
+ Node port=keys.get(i), value=ports.get(port);
+ if( i>0 ) out.append(", ");
+ out.append(port.label()).append('#').append(port._nid);
+ if( port!=value ) out.append(" <- ").append(value.label()).append('#').append(value._nid);
+ }
+ out.append("}\n");
+ }
+
+ private static void printFrames(StringBuilder out, Summary parent, String indent) {
+ ArrayList<Summary> frames=new ArrayList<>(parent._frames);
+ frames.sort(Comparator.comparingInt(s -> s._loop._nid));
+ for( Summary frame : frames ) {
+ out.append(indent).append("+-- ").append(frame.name()).append(" frame; parent ").append(parent.name()).append('\n');
+ printPorts(out,indent+"| entry -> ",frame._entry);
+ printPorts(out,indent+"| continue values -> ",frame._next);
+ printSites(out,indent+"| continue refs -> ",frame._continues);
+ printPorts(out,indent+"| exit values -> ",frame._exit);
+ printSites(out,indent+"| return refs -> ",frame._returns);
+ printSites(out,indent+"| retain -> ",frame._retained);
+ printStorage(out,frame,indent+"| ");
+ printFrames(out,frame,indent+"| ");
+ printSites(out,indent+"`-- cleanup on continue and return -> ",frame._scratch);
+ }
+ }
}
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 f38305b2..3db16f8b 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -16,6 +16,7 @@ public class CodeGen {
// Last created CodeGen as a global; used all over to avoid passing about a "context".
public static CodeGen CODE;
+ private final long _typeGeneration;
// Location of built-in CPU ports
public static final String PORTS = "com.seaofnodes.simple.node.cpus";
@@ -27,11 +28,11 @@ 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
+ LoopTree, // Containing loops for allocation analysis
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
- LoopTree, // Build a loop tree; break infinite loops
Unlink, // Unlink call sites before machine code generation
Select, // Convert to target hardware nodes
Schedule, // Global schedule (code motion) nodes
@@ -136,6 +137,7 @@ public class CodeGen {
// of places. Probably becomes a TLS at some point.
CODE = this;
if( resetTypes ) Type.reset(); // Reset to recover from failed test
+ _typeGeneration = Type.resetGeneration();
_cwd = System.getProperty("user.dir")+"/";
_modDir = modDir == null ? _cwd : modDir;
@@ -197,6 +199,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.LoopTree, this::loopTree, dump);
step(target, Phase.Allocation, this::allocation, dump);
// Final error check - bad programs fail here
step(target, Phase.TypeCheck, this::typeCheck, dump);
@@ -205,9 +208,6 @@ public class CodeGen {
// Eval2 executes ideal operations, including CLInit, directly. Only
// machine compilation expands them before scheduling.
step(target, Phase.Lower, () -> { if( cpu!=null ) lower(); }, dump);
- // Compute the loop-tree, used for approximating exec frequencies for
- // scheduling and register allocation
- step(target, Phase.LoopTree, this::loopTree, dump);
// Detach call-graph edges; ideal execution retains unloaded summaries
// as dispatch targets and schedules their bodies on first use.
step(target, Phase.Unlink, () -> unlink(cpu!=null), dump);
@@ -522,14 +522,15 @@ public class CodeGen {
// Last check for bad programs
public Allocation _allocation;
public CodeGen allocation() {
- return phase(Phase.Allocation, _phase==Phase.FinalizeIR, () -> {
+ if( _phase==Phase.FinalizeIR ) loopTree();
+ return phase(Phase.Allocation, _phase==Phase.LoopTree, () -> {
_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();
+ if( _phase==Phase.FinalizeIR || _phase==Phase.LoopTree ) allocation();
return phase(Phase.TypeCheck, _phase==Phase.Allocation, () -> TypeCheck.run(this));
}
@@ -540,10 +541,11 @@ public class CodeGen {
}
// ---------------------------
- // Build the loop tree; break never-exit loops
+ // Build containing loops without changing control flow before TypeCheck
+ // and serialization. Scheduling adds exits to zero-exit loops later.
public CodeGen loopTree() {
- return phase(Phase.LoopTree, (_phase==Phase.Lower || _phase==Phase.TypeCheck || _phase==Phase.Serialize),
- () -> _start.buildLoopTree(_linker,_stop));
+ return phase(Phase.LoopTree, _phase==Phase.FinalizeIR,
+ () -> _start.buildLoopTree(_linker,_stop,false));
}
// ---------------------------
@@ -584,7 +586,11 @@ public class CodeGen {
unlink(true);
}
private void unlink(boolean removeImports) {
- phase(Phase.Unlink, _phase==Phase.LoopTree, () -> {
+ phase(Phase.Unlink, (_phase==Phase.Lower || _phase==Phase.TypeCheck || _phase==Phase.Serialize), () -> {
+ KeepAliveNode.erase(_start);
+ // Lower can change CFG membership. Rebuild for scheduling, now
+ // including synthetic exits for loops with no exits at all.
+ _start.rebuildLoopTree(_linker,_stop);
_start.setDef(2,null); // Releases the compiler-only escape analysis.
if( removeImports ) Unlink.run(this,true);
else Unlink.forEval(this,_start,_stop);
@@ -815,6 +821,8 @@ public class CodeGen {
// Debugging helper
@Override public String toString() {
+ if( _typeGeneration != Type.resetGeneration() )
+ return "IR unavailable: shared types were reset after this compilation.";
if( _stop == null )
return "No StopNode";
return IRPrinter.prettyPrint(this);
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter33/src/main/java/com/seaofnodes/simple/codegen/Serialize.java
index 9c43e029..0e61e434 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/codegen/Serialize.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/codegen/Serialize.java
@@ -106,7 +106,8 @@ public class Serialize {
// A - Print the C0DE header; last byte is the version number.
// Format 2: gradual packed ints, UTF-8 strings, sparse MemMerge edges,
// and wider singleton function IDs. Reject old cached objects clearly.
- baos.write('C').write('0').write('D').write('2');
+ // Format 3 retains lexical raw-address lifetime endpoints in bodies.
+ baos.write('C').write('0').write('D').write('3');
// Count unique Types
var types = new HashMap<Type,Integer>();
@@ -335,7 +336,7 @@ public class Serialize {
Type.TAGOFFS();
// A - Read a header
- if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='2' )
+ if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='3' )
throw new IllegalArgumentException("Unsupported serialized IR format; rebuild the object file");
// B - Packed read of #strings, then strings
@@ -368,7 +369,7 @@ public class Serialize {
String[] strs = elf._strs;
if( strs == null ) {
// A - Read a header
- if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != '2' )
+ if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != '3' )
throw new IllegalArgumentException( "Unsupported serialized IR format; rebuild the object file" );
// B - Packed read of #strings, then strings
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/codegen/Unlink.java b/chapter33/src/main/java/com/seaofnodes/simple/codegen/Unlink.java
index bb9a6196..bd876a01 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/codegen/Unlink.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/codegen/Unlink.java
@@ -9,6 +9,7 @@ abstract class Unlink {
// Disconnect compiler-only interprocedural edges before scheduling. Keep
// signatures in the linker; runtime calls resolve FIDXs, not graph edges.
static Ary<FunNode> forEval(CodeGen code, StartNode start, StopNode stop) {
+ KeepAliveNode.erase(start);
Ary<Node> nodes = new Ary<>(Node.class);
start.walk(n -> { nodes.add(n); return null; });
Ary<FunNode> funs = new Ary<>(FunNode.class);
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index ba744dc3..7cbf3f9b 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -200,7 +200,34 @@ public abstract class CFGNode extends Node {
// Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves
// also refer to *their* containing LoopNode, as well as have their depth.
// Start contains the function bodies at depth 0; real loops add depth.
+ public void rebuildLoopTree(Ary<FunNode> funs, StopNode stop) {
+ // Reset just these function bodies, not other graphs that Eval2 might
+ // already be executing. Call/Return links are not intraprocedural CFG.
+ BitSet seen=new BitSet();
+ Ary<CFGNode> work=new Ary<>(CFGNode.class);
+ for( FunNode fun : funs )
+ if( fun!=null && !fun.isDead() && !fun._type.isHigh() && fun.summary()==null ) {
+ work.push(fun);
+ if( fun.in(1) instanceof StartCUNode start ) start._pre=0;
+ }
+ while( !work.isEmpty() ) {
+ CFGNode cfg=work.pop();
+ if( seen.get(cfg._nid) ) continue;
+ seen.set(cfg._nid);
+ cfg._pre=0;
+ cfg._ltree=null;
+ if( cfg instanceof ReturnNode ) continue;
+ for( Node use : cfg._outputs )
+ if( use instanceof CFGNode next && !cfg.skip(next) ) work.push(next);
+ }
+ buildLoopTree(funs,stop);
+ }
+
public void buildLoopTree( Ary<FunNode> funs, StopNode stop) {
+ buildLoopTree(funs,stop,true);
+ }
+
+ public void buildLoopTree( Ary<FunNode> funs, StopNode stop, boolean forceExits) {
_ltree = stop._ltree = CodeGen.CODE.XCTRL._ltree = new LoopTree((StartNode)this);
Ary<FunNode> work = new Ary<>(FunNode.class);
@@ -221,17 +248,21 @@ public abstract class CFGNode extends Node {
}
for( int i=0; i<work._len; i++ )
- pre = work.at(i)._bltWalk(pre,work.at(i),stop, post, work);
+ pre = work.at(i)._bltWalk(pre,work.at(i),stop, post, work,forceExits);
post.clear();
}
- int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post, Ary<FunNode> work ) {
+ int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post, Ary<FunNode> work, boolean forceExits ) {
// Pre-walked?
if( _pre!=0 ) return pre;
_pre = pre++;
// Seed the function's outer tree before walking its body. Synthetic
// exits can be added before the post-order walk reaches the entry.
- if( this instanceof FunNode ) _ltree = stop._ltree;
+ if( this instanceof FunNode ) {
+ _ltree = stop._ltree;
+ // A zero-exit function's Return is not reachable through control.
+ fun.ret()._ltree = _ltree;
+ }
if( this instanceof ReturnNode ) {
_ltree = fun._ltree;
post.set(_nid);
@@ -243,7 +274,7 @@ public abstract class CFGNode extends Node {
if( skip( usecfg ) ) {
if( usecfg._pre==0 && usecfg instanceof FunNode fun2 && fun2.summary()==null ) work.add( fun2 );
} else
- pre = usecfg._bltWalk( pre, use instanceof FunNode fuse ? fuse : fun, stop, post, work );
+ pre = usecfg._bltWalk( pre, use instanceof FunNode fuse ? fuse : fun, stop, post, work,forceExits );
}
// Post-order work: find innermost loop
@@ -257,16 +288,21 @@ public abstract class CFGNode extends Node {
// Child visited but not post-visited?
if( !post.get(usecfg._nid) ) {
// Must be a backedge to a LoopNode then
+ assert usecfg instanceof LoopNode : "Simple CFGs must be reducible";
ltree = usecfg._ltree = new LoopTree((LoopNode)usecfg);
} else {
// Take child's loop choice, which must exist
ltree = usecfg._ltree;
// If falling into a loop, use the target loop's parent instead
if( ltree._head == usecfg ) {
- if( ltree._par == null )
+ if( ltree._par == null ) {
// This loop never had an If test choose to take its
// exit, i.e. it is a no-exit infinite loop.
- ltree._par = ltree._head.forceExit(fun,stop)._ltree;
+ // Analysis needs its nesting, but a synthetic exit
+ // must not change nonreturning summaries in .simple.
+ if( forceExits ) ltree._head.forceExit(fun,stop);
+ ltree._par = fun._ltree;
+ }
ltree = ltree._par;
}
}
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/KeepAliveNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/KeepAliveNode.java
new file mode 100644
index 00000000..7db31fe3
--- /dev/null
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/KeepAliveNode.java
@@ -0,0 +1,102 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.util.Ary;
+import java.util.BitSet;
+import java.util.ArrayDeque;
+
+/** A lexical lifetime endpoint. This is a control use, not a machine operand.
+ * Kept values may be raw addresses; Allocation follows them back to storage.
+ * Retained in .simple and through inlining; erased before scheduling. */
+public class KeepAliveNode extends CFGNode {
+ public KeepAliveNode(Node ctrl, Node value) { super(ctrl,value); }
+ @Override public Tag serialTag() { return Tag.KeepAlive; }
+ @Override public Type compute() { return in(0)._type; }
+ @Override public Node idealize() {
+ Node value=in(1);
+ if( value._type==TypeInteger.ZERO || value._type==Type.NIL || in(0)._type==Type.XCONTROL ) return in(0);
+ if( in(0) instanceof KeepAliveNode prior && prior.in(1)==value && addDep(prior).nOuts()==1 ) return prior;
+ // Pending parser edges count as uses too. Drop an expression only when
+ // none of its parts has a use outside the fences.
+ if( unused(value) ) return in(0);
+ return null;
+ }
+
+ private boolean unused(Node value) {
+ BitSet seen=new BitSet();
+ Ary<Node> nodes=new Ary<>(Node.class);
+ ArrayDeque<Node> work=new ArrayDeque<>();
+ work.push(value);
+ while( !work.isEmpty() ) {
+ Node n=work.pop();
+ if( n==null || n instanceof ConstantNode || n instanceof CFGNode || seen.get(n._nid) ) continue;
+ seen.set(n._nid);
+ nodes.add(n);
+ // Only inspect the address expression, not the object's fields or
+ // the allocation's memory. The pointer is the endpoint of tracing.
+ if( n instanceof PtrToIntNode ) continue;
+ if( n._type instanceof TypeMemPtr || n.isFunLeaf() ) return false;
+ for( Node in : n._inputs ) if( in!=null ) work.push(in);
+ }
+ for( Node n : nodes ) for( Node use : addDep(n)._outputs )
+ if( use==null || !(use instanceof KeepAliveNode) && !seen.get(use._nid) ) return false;
+ return true;
+ }
+
+ /** Parser-only accumulation of lifetime obligations. A scalar token lets
+ * ordinary Phis merge branches and loops; it is never evaluated as a number.
+ * Both inputs survive: replacing a variable must not forget its old object. */
+ public static class Values extends Node {
+ public Values(Node prior, Node value) { super(null,prior,value); }
+ @Override public Tag serialTag() { return Tag.KeepValues; }
+ @Override public Type compute() { return TypeInteger.BOT; }
+ @Override public Node idealize() {
+ if( in(1)._type==TypeInteger.ZERO ) return in(2);
+ if( in(2)._type==TypeInteger.ZERO || in(1)==in(2) ) return in(1);
+ return null;
+ }
+ }
+
+ public static void erase(StartNode start) {
+ Ary<Node> nodes=new Ary<>(Node.class);
+ BitSet candidates=new BitSet();
+ start.walk(n -> {
+ if( n instanceof KeepAliveNode || n instanceof Values ||
+ n instanceof PhiNode && !(n instanceof ParmNode) ) {
+ nodes.add(n);
+ candidates.set(n._nid);
+ }
+ return null;
+ });
+ boolean hasFence=false;
+ for( Node n : nodes ) if( n instanceof KeepAliveNode || n instanceof Values ) { hasFence=true; break; }
+ if( !hasFence ) return;
+ // GVN can share a pending Phi with an ordinary program Phi. Names do
+ // not distinguish them. Preserve every Phi with a real use, and its
+ // inputs; discard only the subgraph used exclusively by lifetime fences.
+ BitSet live=new BitSet();
+ ArrayDeque<Node> work=new ArrayDeque<>();
+ for( Node n : nodes ) if( !(n instanceof KeepAliveNode) )
+ for( Node use : n._outputs ) if( use==null || !candidates.get(use._nid) ) {
+ work.push(n);
+ break;
+ }
+ while( !work.isEmpty() ) {
+ Node n=work.pop();
+ if( live.get(n._nid) ) continue;
+ live.set(n._nid);
+ assert !(n instanceof Values) : "Lifetime token used as a program value";
+ for( int i=1; i<n.nIns(); i++ )
+ if( n.in(i)!=null && candidates.get(n.in(i)._nid) ) work.push(n.in(i));
+ }
+ // Loaded Eval2 bodies must not GVN into a different executing graph.
+ ConstantNode zero=ConstantNode.raw(TypeInteger.ZERO);
+ zero.setDef(0,start);
+ zero.keep();
+ for( Node n : nodes ) if( !n.isDead() && !live.get(n._nid) )
+ n.subsume(n instanceof KeepAliveNode ? n.in(0) : zero);
+ zero.unkill();
+ CodeGen.CODE.invalidateIDepthCaches();
+ }
+}
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 3688d6ea..6862b25c 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -77,7 +77,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
New,Never,Not,Or,Parm,Phi,Proj,PtrToInt,
ReadOnly,Return,Region,RoundF32,
Sar,Shl,Shr,Start,StartCU,StopCU,Stop,Store,Sub,
- ToInteger,ToFloat,XCtrl,Xor,F64Bits,F64FromBits,Mod;
+ ToInteger,ToFloat,XCtrl,Xor,F64Bits,F64FromBits,Mod,KeepAlive,KeepValues;
public static final Tag[] VALS = values();
public Node make( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) {
return switch(this) {
@@ -85,6 +85,8 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
case And -> { int mode=bais.packed1(); assert mode==1; yield new AndNode(null,null,null); }
case Div -> new DivNode(null,null,(byte)bais.packed1());
case Guard -> GuardNode.make(bais);
+ case KeepAlive -> new KeepAliveNode(null,null);
+ case KeepValues -> new KeepAliveNode.Values(null,null);
case If -> new IfNode(null,null);
case Loop -> new LoopNode(null,null,null);
case Minus -> new MinusNode(null,(byte)bais.packed1());
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter33/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 80d2aa0a..2fa551fb 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -18,6 +18,14 @@ import java.util.*;
*/
public class ScopeNode extends MemMergeNode {
+ // Parser root for pending lifetime uses. Real edges let Phi replacement
+ // update the pending values, just like the ordinary variable bindings.
+ private static class Pending extends Node {
+ @Override public Type compute() { return Type.BOTTOM; }
+ @Override public Node idealize() { return null; }
+ @Override public boolean eq(Node n) { return this==n; }
+ }
+
/**
* The control is a name that binds to the currently active control
* node in the graph
@@ -52,6 +60,7 @@ public class ScopeNode extends MemMergeNode {
}
public int _lexSize; // Number of Vars in this scope
+ public int _keepSize; // Lifetime scopes outside this lexical scope
}
public final Ary<Kind> _kinds;
// Lexical scope nesting depth
@@ -60,6 +69,8 @@ public class ScopeNode extends MemMergeNode {
// Extra guards; tested predicates and cast results
private final Ary<Node> _guards;
+ private Pending _keeps; // Materialized only when a scope has a real address use
+ private final Ary<Node> _emptyKeeps = new Ary<>(Node.class); // Zeroes and lazy loop sentinels
// A new ScopeNode
public ScopeNode() {
@@ -114,8 +125,66 @@ public class ScopeNode extends MemMergeNode {
public void push( Kind kind ) {
kind._lexSize = _vars.size();
+ kind._keepSize = keepDepth();
_kinds.push(kind);
+ pushKeep();
+ }
+
+ public int keepDepth() { return _keeps==null ? _emptyKeeps.size() : _keeps.nIns(); }
+ private Node keepAt(int i) { return _keeps==null ? _emptyKeeps.at(i) : _keeps.in(i); }
+ private void materializeKeeps(Node value) {
+ if( _keeps!=null || value==CodeGen.CODE.ZERO || value instanceof ScopeNode ) return;
+ _keeps=new Pending().keep();
+ for( Node n : _emptyKeeps ) _keeps.addDef(n);
+ _emptyKeeps.clear();
+ }
+ private void addKeep(Node value) {
+ materializeKeeps(value);
+ if( _keeps==null ) _emptyKeeps.add(value); else _keeps.addDef(value);
+ }
+ public void pushKeep() { addKeep(CodeGen.CODE.ZERO); }
+ private Node setKeep(int i, Node n) {
+ Node old=keepAt(i);
+ if( old!=n ) {
+ materializeKeeps(n);
+ if( _keeps==null ) _emptyKeeps.set(i,n); else _keeps.setDef(i,n);
+ }
+ return n;
+ }
+ private Node getKeep(int i) { return getKeep(i,false); }
+ private Node getKeep(int i, boolean writing) {
+ Node old=keepAt(i);
+ if( old instanceof ScopeNode loop ) {
+ Node def=loop.getKeep(i,writing);
+ // Reading an empty obligation needs no loop Phi. A conversion
+ // must create one before adding its address to this iteration.
+ if( def==CodeGen.CODE.ZERO && !writing ) return def;
+ old=def instanceof PhiNode phi && loop.ctrl()==phi.region() ? def :
+ loop.setKeep(i,new PhiNode("$keep",loop.ctrl(),def,null).init());
+ setKeep(i,old);
+ }
+ return old;
+ }
+ public void keepValue(Node value) {
+ int i=keepDepth()-1;
+ setKeep(i,new KeepAliveNode.Values(getKeep(i,true),value).peephole());
+ }
+ // Flush just the scopes being exited; outer obligations remain pending.
+ public void endKeeps(int first) {
+ for( int i=keepDepth()-1; i>=first; i-- ) {
+ if( ctrl()._type!=Type.XCONTROL ) {
+ Node value=getKeep(i);
+ if( value._type!=TypeInteger.ZERO )
+ ctrl(new KeepAliveNode(ctrl(),value).peephole());
+ }
+ setKeep(i,CodeGen.CODE.ZERO);
+ }
}
+ public void popKeepsTo(int size) {
+ endKeeps(size);
+ if( _keeps==null ) _emptyKeeps.setLen(size); else _keeps.popUntil(size);
+ }
+ public void popKeep() { popKeepsTo(keepDepth()-1); }
// Pop a lexical scope
public void pop() {
@@ -124,7 +193,9 @@ public class ScopeNode extends MemMergeNode {
}
// Pop a scope, no promote FRefs
public void _pop() {
- int n = _kinds.pop()._lexSize;
+ Kind kind=_kinds.pop();
+ popKeepsTo(kind._keepSize);
+ int n = kind._lexSize;
popUntil(n); // Pop off inputs going out of scope
_vars.setLen(n); // Pop off variables going out of scope
}
@@ -352,6 +423,7 @@ public class ScopeNode extends MemMergeNode {
dup._vars .addAll(_vars );
dup._kinds .addAll(_kinds );
dup._guards .addAll(_guards );
+ for( int i=0; i<keepDepth(); i++ ) dup.addKeep(loop ? this : keepAt(i));
// The dup'd guards all need dup'd keepers, to keep proper accounting
// when later removing all guards
for( Node n : _guards )
@@ -391,6 +463,11 @@ public class ScopeNode extends MemMergeNode {
_merge(that,r,nIns());
}
public void _merge(ScopeNode that, RegionNode r, int max ) {
+ for( int i=0; i<keepDepth(); i++ ) {
+ if( keepAt(i)==that.keepAt(i) ) continue;
+ Node lhs=getKeep(i), rhs=that.getKeep(i);
+ if( lhs!=rhs ) setKeep(i,new PhiNode("$keep",r,lhs,rhs).peephole());
+ }
for( int i = 1; i < max; i++)
if( in(i) != that.in(i) ) { // No need for redundant Phis
// If we are in lazy phi mode we need to a lookup
@@ -446,10 +523,23 @@ public class ScopeNode extends MemMergeNode {
back.kill(); // Loop backedge is dead
// Now one-time do a useless-phi removal
this._useless();
+ for( int i=0; i<keepDepth(); i++ )
+ if( keepAt(i) instanceof PhiNode phi ) {
+ Node n=phi.peephole();
+ if( n!=phi ) phi.subsume(n);
+ }
}
// Fill in the backedge of any inserted Phis
void _endLoop( ScopeNode scope, Node back, Node exit ) {
+ ScopeNode bscope=(ScopeNode)back, escope=(ScopeNode)exit;
+ for( int i=0; i<keepDepth(); i++ ) {
+ Node n=keepAt(i);
+ if( n instanceof PhiNode phi && phi.region()==scope.ctrl() && phi.in(2)==null ) {
+ phi.setDef(2,bscope.getKeep(i));
+ }
+ if( escope.keepAt(i)==scope ) escope.setKeep(i,n);
+ }
for( int i=1; i<nIns(); i++ ) {
if( !loopVar(var(i)) ) continue;
Node n = in(i);
@@ -654,8 +744,10 @@ public class ScopeNode extends MemMergeNode {
n.unkill();
_guards.clear();
// Can have lazy uses remaining
- if( isUnused() )
+ if( isUnused() ) {
+ if( _keeps!=null ) _keeps.unkill();
super.kill();
+ }
}
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java b/chapter33/src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java
index 079853cd..9f0b63f5 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java
@@ -168,6 +168,7 @@ final class ArrayInitializers {
// Saved paths share Var records with the active scope. Drop locals
// without promoting them, then copy forward references explicitly.
while( cur.depth()>_frame._depth ) cur._pop();
+ cur.popKeepsTo(_frame._kind._keepSize+1);
cur.balanceLoopFRefs(P._scope);
cur.update(_frame._value,value.unkeep());
if( _frame._returns==null ) _frame._returns=cur;
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/parser/ControlFlow.java b/chapter33/src/main/java/com/seaofnodes/simple/parser/ControlFlow.java
index 6c626669..95ae3168 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/parser/ControlFlow.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/parser/ControlFlow.java
@@ -32,6 +32,7 @@ final class ControlFlow {
P.ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection
P._scope.addGuards(ifT,pred,false); // Up-cast predicate
// Parse true-side flavor
+ if( fside.equals("else") ) P._scope.pushKeep();
Node lhs = switch( fside ) {
case "else" -> P.statements.parseStatement(); // if( pred ) stmts;
case ":" -> P.expressions.parseAssignment(); // pred ? asgn;
@@ -40,6 +41,7 @@ final class ControlFlow {
default -> throw TODO();
};
lhs.keep();
+ if( fside.equals("else") ) P._scope.popKeep();
P._scope.removeGuards(ifT);
// See if a one-sided def was made: "if(pred) int x = 1;" and throw.
@@ -57,6 +59,7 @@ final class ControlFlow {
P._scope.addGuards(ifF,pred,true);
// Parse false-side flavor
boolean doRHS = false; // RHS is optional for if/else and trinary
+ if( fside.equals("else") ) P._scope.pushKeep();
Node rhs = switch( fside ) {
case "else" -> (doRHS = P.match(fside)) ? P.statements.parseStatement() : P.con(lhs._type.makeZero());
case ":" -> (doRHS = P.match(fside)) ? P.expressions.parseAssignment() : P.con(lhs._type.makeZero());
@@ -65,6 +68,7 @@ final class ControlFlow {
default -> throw TODO();
};
rhs.keep();
+ if( fside.equals("else") ) P._scope.popKeep();
P._scope.removeGuards(ifF);
// The RHS of `||` is parsed on the false side, so retain its updated
// control, memory and locals just as an explicit else arm does.
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/parser/Conversions.java b/chapter33/src/main/java/com/seaofnodes/simple/parser/Conversions.java
index 72247ca6..cdba0c0f 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/parser/Conversions.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/parser/Conversions.java
@@ -21,10 +21,20 @@ final class Conversions {
if( expr instanceof FunPtrNode && t instanceof TypeFunPtr )
return expr;
// Auto-widen array to i64 (cast ptr to raw int bits)
- if( t == TypeInteger.BOT && expr._type instanceof TypeMemPtr tmp && tmp._obj.isAry() )
- return P.peep(new AddNode(P.peep(new PtrToIntNode(expr)),ConFldOffNode.make(tmp._obj,"[]")));
+ if( t == TypeInteger.BOT && expr._type instanceof TypeMemPtr tmp && tmp._obj.isAry() ) {
+ Node raw=P.peep(new AddNode(P.peep(new PtrToIntNode(expr)),ConFldOffNode.make(tmp._obj,"[]")));
+ P._scope.keepValue(raw);
+ return raw;
+ }
// Widen ints to floats, narrow wide types
- return P.peep(new ConvertNode(t,expr));
+ Type src=expr._type;
+ boolean possibleArray=!(expr instanceof ArithNode) && (src==Type.BOTTOM || src==TypeScalar.BOT);
+ Node converted=P.peep(new ConvertNode(t,expr));
+ // A forward call can acquire its array result type after parsing.
+ // ConvertNode will then introduce PtrToInt; save its endpoint now.
+ if( t==TypeInteger.BOT && possibleArray )
+ P._scope.keepValue(converted);
+ return converted;
}
// Inferred `var` declarations describe writable slots, not the exact
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/parser/Functions.java b/chapter33/src/main/java/com/seaofnodes/simple/parser/Functions.java
index a7726521..5064c479 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/parser/Functions.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/parser/Functions.java
@@ -389,6 +389,7 @@ final class Functions {
// travel in expr's private memory; only their scope layout is retained.
int lexN = P._scope.enclosingFuncOrDecl();
Kind.Func k = (Kind.Func)P._scope._kinds.at(lexN);
+ P._scope.endKeeps(k._keepSize);
if( FunNode.isInit(k._name) ) {
int nestedLexSize = lexN+1 < P._scope.depth() ? P._scope._kinds.at(lexN+1)._lexSize : P._scope.nIns();
if( k._name.endsWith(".<clinit>") )
@@ -412,6 +413,7 @@ final class Functions {
_returnScope = P._scope.dup();
while( lexN+1 < _returnScope.depth() )
_returnScope._pop(); // Pop a nested block scope until we hit the function scope
+ _returnScope.popKeepsTo(k._keepSize+1);
_returnScope.define("$expr", Conversions.inferredReturnType(expr._type), true, expr, null);
} else {
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/parser/Statements.java b/chapter33/src/main/java/com/seaofnodes/simple/parser/Statements.java
index 0c2a25f7..b27a5032 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/parser/Statements.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/parser/Statements.java
@@ -193,7 +193,9 @@ final class Statements {
// Our current scope is the body Scope
P.ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection
P._scope.addGuards(ifT,pred.unkeep(),false); // Up-cast predicate
+ P._scope.pushKeep(); // An unbraced body also has an iteration lifetime.
parseStatement().isKill(); // Parse loop body
+ P._scope.popKeep();
P._scope.removeGuards(ifT);
// Merge the loop bottom into other continue statements
@@ -206,8 +208,10 @@ final class Statements {
// Now append the next code onto the body code
if( doFor ) {
int old = P.pos(nextPos);
+ P._scope.pushKeep();
if( !P.peek(')') )
P.expressions.parseAssignment().isKill();
+ P._scope.popKeep();
if( P.pos() != nextEnd )
throw P.errorSyntax( "Unexpected code after expression" );
P.pos(old);
@@ -264,6 +268,7 @@ final class Statements {
// copy forward references into the jump scope with their own indices.
while( cur.depth() > _breakScope.depth() )
cur._pop();
+ cur.popKeepsTo(_breakScope.keepDepth());
cur.balanceLoopFRefs(P._scope);
// If this is a continue then first time the target is null
// So we just use the pruned current scope as the base for the
diff --git a/chapter33/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter33/src/main/java/com/seaofnodes/simple/type/Type.java
index 221de04c..41fe039f 100644
--- a/chapter33/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter33/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -235,8 +235,15 @@ public class Type /*implements Cloneable*/ {
public int nkids() { return 0; } // Number of kids
+ // Reset recycles Type objects still referenced by old compilation graphs.
+ // Debuggers must not inspect those types, even if they have been reused and
+ // look valid again. The generation lets a CodeGen detect that situation.
+ private static long RESET_GENERATION;
+ public static long resetGeneration() { return RESET_GENERATION; }
+
// Clear and re-insert the basic Type INTERN table
public static void reset() {
+ RESET_GENERATION++;
VISIT.clear();
FREES.clear();
if( INTERN0.isEmpty() ) {
diff --git a/chapter33/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter33/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
index 07e702c7..cbc86d92 100644
--- a/chapter33/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
+++ b/chapter33/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
@@ -14,8 +14,6 @@ import static org.junit.Assert.assertEquals;
public class BrainFuckTest {
@Test public void testBrainFuckAryu8() throws IOException {
-
-
String brain_fuck = "Hello World!\n";
String src =
"""
diff --git a/chapter33/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter33/src/test/java/com/seaofnodes/simple/Chapter18Test.java
index b1caae96..9cb5dacc 100644
--- a/chapter33/src/test/java/com/seaofnodes/simple/Chapter18Test.java
+++ b/chapter33/src/test/java/com/seaofnodes/simple/Chapter18Test.java
@@ -21,7 +21,16 @@ public class Chapter18Test {
"int x=0; while(arg) { if(arg==2) while(1) { x++; } x++; arg--; } return x;"
};
for( String src : sources ) {
- CodeGen code = new CodeGen(src).driver(CodeGen.Phase.LoopTree);
+ CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck);
+ code._stop.walk(n -> {
+ assertFalse("Analysis must not insert synthetic exits",n instanceof NeverNode);
+ if( n instanceof LoopNode loop && !(loop instanceof StartNode) ) {
+ assertSame(loop,loop._ltree._head);
+ assertNotNull(loop._ltree._par);
+ }
+ return null;
+ });
+ code.driver(CodeGen.Phase.Unlink);
int[] nevers = {0};
code._stop.walk(n -> {
if( n instanceof FunNode fun )
diff --git a/chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java b/chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java
index ff313c7e..7f79f2c0 100644
--- a/chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java
+++ b/chapter33/src/test/java/com/seaofnodes/simple/Chapter33Test.java
@@ -1,6 +1,11 @@
package com.seaofnodes.simple;
import com.seaofnodes.simple.codegen.*;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import com.seaofnodes.simple.util.Ary;
+import java.nio.file.Files;
+import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
@@ -118,7 +123,7 @@ public class Chapter33Test {
String dump=code._allocation.toString();
assertTrue(dump.contains("[arg3]"));
assertTrue(dump.contains(".c -->"));
- assertTrue(dump.indexOf("+-- make_noInline\n") < dump.indexOf("+-- fill_noInline\n"));
+ assertTrue(dump.indexOf("+-- fill_noInline\n") < dump.indexOf("+-- make_noInline\n"));
}
// A join requires BOTH possible owners; it must not pick whichever input
@@ -156,6 +161,7 @@ public class Chapter33Test {
Collections.sort(destinations);
assertEquals(List.of("result & arg3","result & arg4"),destinations);
assertEquals("1",Eval2.eval(borrow,0));
+ assertTrue(borrow.toString().contains("choose_noInline"));
CodeGen cycle=compile("""
struct Link { Link? !next; i64 x; new Link={ i64 n -> x=n; }; };
@@ -171,6 +177,10 @@ public class Chapter33Test {
assertEquals(2,sites.size());
for( var site : sites ) assertEquals("result",site.destination());
assertEquals("9",Eval2.eval(cycle,9));
+ assertTrue(cycle.toString().contains("cycle_noInline"));
+ // Compiling cycle reset and recycled borrow's types. Its debugger string
+ // must neither crash on cleared types nor print their reused contents.
+ assertEquals("IR unavailable: shared types were reset after this compilation.",borrow.toString());
}
// Scalar results must not hide allocations when arithmetic is skipped.
@@ -200,14 +210,10 @@ public class Chapter33Test {
@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]);"
+ "{ i64 -> int[] } native=\"C\"; val bad_noInline={ i64 n -> native(n); }; return bad_noInline(arg);"
};
- String[] reasons={"recursive", "loop destinations", "variable-size", "LoadNode", "opaque", "raw address", "raw address"};
+ String[] reasons={"recursive", "variable-size", "native result"};
for( int i=0; i<sources.length; i++ ) {
CodeGen code=compile(sources[i]);
var sum=code._allocation.summary("bad_noInline");
@@ -220,4 +226,783 @@ public class Chapter33Test {
assertTrue(code._allocation.toString().contains("REJECT:"));
}
}
+
+ // A borrowed child is a separate origin. Returning it through helpers must
+ // retain the Thing, not the temporary Holder used to reach it.
+ @Test public void testAllocationReturnField() {
+ CodeGen code=compile(THING+HOLDER+"""
+ val get_noInline = { Holder h -> h.c; };
+ val forward_noInline = { Holder h -> get_noInline(h); };
+ val work_noInline={ i64 n ->
+ val h = new Holder;
+ h.c = new Thing(n);
+ return forward_noInline(h);
+ };
+ return read_noInline(work_noInline(arg));
+ """);
+ for( String name : new String[]{"get_noInline","forward_noInline"} ) {
+ var sum=code._allocation.summary(name).requireSupported();
+ assertEquals(1,sum._returns.size());
+ var child=sum._returns.iterator().next();
+ assertEquals("arg3.c",child._name);
+ assertEquals("result & arg3.c",child.destination());
+ for( var site : sum._sites )
+ if( site._arg==3 ) assertEquals("arg3",site.destination());
+ }
+ var work=code._allocation.summary("work_noInline");
+ assertEquals("frame",allocations(work,"Holder").get(0).destination());
+ assertEquals(2,allocations(work,"Thing").size()); // weak update retains the default too
+ for( var site : allocations(work,"Thing") ) assertEquals("result",site.destination());
+ assertEquals("17",Eval2.eval(code,17));
+ }
+
+ // Retention through a loaded reference composes across a wrapper. The
+ // source holder stays local even though its child escapes to the argument.
+ @Test public void testAllocationCopyField() {
+ CodeGen code=compile(THING+HOLDER+"""
+ val copy_noInline={ !Holder dst, Holder src -> dst.c=src.c; return 0; };
+ val forward_noInline={ !Holder dst, Holder src -> copy_noInline(dst,src); };
+ val work_noInline={ !Holder dst, i64 n ->
+ val src=new Holder;
+ src.c=new Thing(n);
+ return forward_noInline(dst,src);
+ };
+ val dst=new Holder;
+ work_noInline(dst,arg);
+ return dst.c.x;
+ """);
+ for( String name : new String[]{"copy_noInline","forward_noInline"} ) {
+ var sum=code._allocation.summary(name).requireSupported();
+ boolean found=false;
+ for( var site : sum._sites ) {
+ if( site._name.equals("arg4.c") ) {
+ found=true;
+ assertEquals("arg3 & arg4.c",site.destination());
+ }
+ if( site._arg==4 ) assertEquals("arg4",site.destination());
+ }
+ assertTrue(found);
+ }
+ var work=code._allocation.summary("work_noInline");
+ assertEquals("frame",allocations(work,"Holder").get(0).destination());
+ assertEquals(2,allocations(work,"Thing").size());
+ for( var site : allocations(work,"Thing") ) assertEquals("arg3",site.destination());
+ assertEquals("23",Eval2.eval(code,23));
+ }
+
+ // An argument's child can itself receive allocations. Its lifetime is a
+ // distinct destination, resolved to the actual Holder at the next call.
+ @Test public void testAllocationStoreThroughField() {
+ CodeGen code=compile(THING+HOLDER+"""
+ struct Outer { !Holder h=new Holder; };
+ val fill_noInline={ !Outer o, i64 n -> o.h.c=new Thing(n); return n; };
+ val get_noInline={ Outer o -> o.h.c; };
+ val work_noInline={ i64 n ->
+ val o=new Outer;
+ fill_noInline(o,n);
+ return get_noInline(o);
+ };
+ return read_noInline(work_noInline(arg));
+ """);
+ var fill=allocations(code._allocation.summary("fill_noInline"),"Thing");
+ assertEquals(1,fill.size());
+ assertEquals("arg3.h",fill.get(0).destination());
+ var get=code._allocation.summary("get_noInline").requireSupported();
+ assertEquals("arg3.h.c",get._returns.iterator().next()._name);
+ var work=code._allocation.summary("work_noInline");
+ assertEquals("frame",allocations(work,"Outer").get(0).destination());
+ assertEquals("frame",allocations(work,"Holder").get(0).destination());
+ assertEquals(2,allocations(work,"Thing").size());
+ for( var site : allocations(work,"Thing") ) assertEquals("result",site.destination());
+ assertEquals("31",Eval2.eval(code,31));
+ }
+
+ // A store through one formal must reach a load through another when actuals
+ // alias. Keeping all fields as weak unions also covers a load before a store.
+ @Test public void testAllocationAliasedFieldLoad() {
+ CodeGen code=compile(THING+HOLDER+"""
+ val fill_noInline={ !Holder a, Holder b, i64 n -> a.c=new Thing(n); return b.c; };
+ val same_noInline={ i64 n ->
+ val h=new Holder;
+ return fill_noInline(h,h,n);
+ };
+ val different_noInline={ i64 n ->
+ val a=new Holder, b=new Holder;
+ return fill_noInline(a,b,n);
+ };
+ return read_noInline(same_noInline(arg))+read_noInline(different_noInline(arg));
+ """);
+ for( String name : new String[]{"same_noInline","different_noInline"} ) {
+ var sum=code._allocation.summary(name);
+ for( var site : allocations(sum,"Holder") ) assertEquals("frame",site.destination());
+ int returned=0;
+ for( var site : allocations(sum,"Thing") )
+ if( site.destination().equals("result") ) returned++;
+ assertEquals(name.equals("same_noInline") ? 2 : 1,returned);
+ }
+ assertEquals("41",Eval2.eval(code,41));
+ }
+
+ // Weak updates can create fictitious repeated reads. Reject this case
+ // instead of building infinite p.next.next... paths or silently dropping one.
+ @Test public void testAllocationCyclicFieldPaths() {
+ CodeGen code=compile("""
+ struct Link { Link? !next; i64 x; new Link={ i64 n -> x=n; }; };
+ val skip_noInline={ !Link p ->
+ val a=p.next;
+ if( a ) p.next=a.next;
+ return p;
+ };
+ val a=new Link(arg), b=new Link(arg+1);
+ a.next=b;
+ return skip_noInline(a).x;
+ """);
+ var sum=code._allocation.summary("skip_noInline");
+ assertFalse(sum.supported());
+ assertTrue(sum._reject,sum._reject.contains("cyclic field-path expansion"));
+ assertEquals("5",Eval2.eval(code,5));
+ }
+
+ // Array indices share one conservative field. Both possible children need
+ // result storage; the fixed-size backing array itself remains temporary.
+ @Test public void testAllocationArrayElementOrigins() {
+ CodeGen code=compile(THING+"""
+ val get_noInline={ Thing?[] ts, i64 n -> ts[n&1]; };
+ val work_noInline={ i64 n ->
+ val ts=new Thing?[2];
+ ts[0]=new Thing(n);
+ ts[1]=new Thing(n+1);
+ return get_noInline(ts,n);
+ };
+ val t=work_noInline(arg);
+ return t ? t.x : -1;
+ """);
+ var work=code._allocation.summary("work_noInline").requireSupported();
+ assertEquals(2,allocations(work,"Thing").size());
+ for( var site : allocations(work,"Thing") ) assertEquals("result",site.destination());
+ int arrays=0;
+ for( var site : work._sites )
+ if( site._allocation!=null && site._allocation._ts.isAry() ) {
+ arrays++;
+ assertEquals("frame",site.destination());
+ }
+ assertEquals(1,arrays);
+ assertEquals("8",Eval2.eval(code,7));
+ assertEquals("6",Eval2.eval(code,6));
+ }
+
+ // One temporary per iteration, including allocations imported from a helper.
+ @Test public void testAllocationLoopTemporary() {
+ CodeGen code=compile(THING+"""
+ val make_noInline={ i64 n -> new Thing(n); };
+ val work_noInline={ i64 n ->
+ i64 s=0;
+ while( n>0 ) {
+ val t=make_noInline(n);
+ s+=read_noInline(t);
+ n--;
+ }
+ return s;
+ };
+ return work_noInline(arg);
+ """);
+ var sites=allocations(code._allocation.summary("work_noInline"),"Thing");
+ assertEquals(1,sites.size());
+ var temp=sites.get(0);
+ assertNotNull(temp._frame._loop);
+ assertSame(temp._frame,temp._scope);
+ assertEquals(temp._frame.name()+" iteration",temp.destination());
+ assertTrue(temp._frame._scratch.contains(temp));
+ assertFalse(temp._frame._continues.contains(temp));
+ assertFalse(temp._frame._returns.contains(temp));
+ assertEquals("15",Eval2.eval(code,5));
+ assertEquals("0",Eval2.eval(code,0));
+ }
+
+ // A loop can retain a winner while reclaiming unrelated scratch every turn.
+ // The winner is built by a factory, so its destination crosses a call too.
+ @Test public void testAllocationLoopWinnerAndScratch() {
+ CodeGen code=compile(THING+"""
+ struct Scratch { i64 x; new Scratch={ i64 n -> x=n; }; };
+ val readScratch_noInline={ Scratch s -> s.x; };
+ val make_noInline={ i64 n -> new Thing(n); };
+ val find_noInline={ i64 n ->
+ Thing? !winner=null;
+ while( n>0 ) {
+ val scratch=new Scratch(n);
+ val candidate=make_noInline(readScratch_noInline(scratch));
+ if( read_noInline(candidate)==3 ) { winner=candidate; break; }
+ n--;
+ }
+ return winner;
+ };
+ Thing? t=find_noInline(arg);
+ return t ? t.x : -1;
+ """);
+ var sum=code._allocation.summary("find_noInline").requireSupported();
+ var winner=allocations(sum,"Thing").get(0);
+ var scratch=allocations(sum,"Scratch").get(0);
+ assertNotNull(winner._frame._loop);
+ assertSame(winner._frame,scratch._frame);
+ assertEquals("result",winner.destination());
+ assertNull(winner._scope);
+ assertSame(scratch._frame,scratch._scope);
+ assertEquals(scratch._frame.name()+" iteration",scratch.destination());
+ var frame=winner._frame.requireSupported();
+ assertSame(sum,frame._parent);
+ assertTrue(sum._frames.contains(frame));
+ assertTrue(frame._returns.contains(winner));
+ assertFalse(frame._continues.contains(winner));
+ assertFalse(frame._scratch.contains(winner));
+ assertTrue(frame._scratch.contains(scratch));
+ assertFalse(frame._entry.isEmpty());
+ assertFalse(frame._next.isEmpty());
+ assertFalse(frame._exit.isEmpty());
+ String dump=code._allocation.toString();
+ assertTrue(dump.contains(frame.name()+" winner"));
+ assertEquals(dump.indexOf("\n+-- "),dump.indexOf("\n+-- class:Test.<clinit>\n"));
+ int others=dump.indexOf("Other retained functions");
+ assertTrue(dump.indexOf("\n+-- find_noInline\n") < others);
+ assertTrue(dump.indexOf("\n+-- make_noInline\n") < others);
+ assertTrue(dump.indexOf("\n+-- Test.Scratch.<new>\n") > others);
+ assertEquals("3",Eval2.eval(code,5));
+ assertEquals("-1",Eval2.eval(code,2));
+ assertEquals("-1",Eval2.eval(code,0));
+ }
+
+ // A collection needs multiple generations of an allocation site. Neither a
+ // loop-carried pointer nor a pointer hidden in pre-existing memory is a winner.
+ @Test public void testAllocationLoopRetainedCandidates() {
+ String[] sources={
+ """
+ struct Link { Link? next; i64 x; new Link={ Link? p, i64 n -> next=p; x=n; }; };
+ val work_noInline={ i64 n ->
+ Link? !head=null;
+ while( n>0 ) { head=new Link(head,n); n--; }
+ return head;
+ };
+ val t=work_noInline(arg);
+ return t ? t.x : -1;
+ """,
+ THING+"""
+ val work_noInline={ i64 n ->
+ val ts=new Thing?[2];
+ while( n>0 ) { ts[n&1]=new Thing(n); n--; }
+ return ts;
+ };
+ val ts=work_noInline(arg);
+ val t=ts[1];
+ return t ? t.x : -1;
+ """,
+ 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;
+ while( n>0 ) { fill_noInline(h,n); n--; }
+ return h;
+ };
+ return work_noInline(arg).c.x;
+ """
+ };
+ for( String source : sources ) {
+ CodeGen code=compile(source);
+ var sum=code._allocation.summary("work_noInline");
+ assertFalse(sum.supported());
+ assertTrue(sum._reject,sum._reject.contains("across its backedge"));
+ assertEquals("1",Eval2.eval(code,3));
+ }
+ }
+
+ // Publishing on the exit arm is allowed. Publishing on the backedge was
+ // rejected above; both cases write through a pre-existing holder.
+ @Test public void testAllocationLoopWinnerStore() {
+ CodeGen code=compile(THING+HOLDER+"""
+ val fill_noInline={ !Holder h, i64 n ->
+ while( n>0 ) {
+ val t=new Thing(n);
+ if( read_noInline(t)==3 ) { h.c=t; break; }
+ n--;
+ }
+ return n;
+ };
+ val h=new Holder;
+ fill_noInline(h,arg);
+ return h.c.x;
+ """);
+ var sites=allocations(code._allocation.summary("fill_noInline"),"Thing");
+ assertEquals(1,sites.size());
+ assertEquals("arg3",sites.get(0).destination());
+ assertNotNull(sites.get(0)._frame._loop);
+ assertNull(sites.get(0)._scope);
+ assertTrue(sites.get(0)._frame._retained.contains(sites.get(0)));
+ assertEquals("3",Eval2.eval(code,5));
+ assertEquals("0",Eval2.eval(code,2));
+ }
+
+ // An inner winner can still be temporary in the enclosing iteration.
+ @Test public void testAllocationNestedLoopWinner() {
+ CodeGen code=compile(THING+"""
+ val work_noInline={ i64 n ->
+ i64 s=0;
+ while( n>0 ) {
+ Thing? !winner=null;
+ i64 i=3;
+ while( i>0 ) {
+ val t=new Thing(n+i);
+ if( read_noInline(t)==n+2 ) { winner=t; break; }
+ i--;
+ }
+ if( winner ) s+=read_noInline(winner);
+ n--;
+ }
+ return s;
+ };
+ return work_noInline(arg);
+ """);
+ var sites=allocations(code._allocation.summary("work_noInline"),"Thing");
+ assertEquals(1,sites.size());
+ var site=sites.get(0);
+ assertNotNull(site._frame._loop);
+ assertNotNull(site._scope);
+ assertSame(site._frame._parent,site._scope);
+ assertEquals(site._scope.name()+" iteration",site.destination());
+ assertTrue(site._frame._returns.contains(site));
+ assertFalse(site._frame._scratch.contains(site));
+ assertTrue(site._scope._scratch.contains(site));
+ assertEquals("12",Eval2.eval(code,3));
+ }
+
+ // The candidate's graph survives together, but the caller can consume that
+ // result locally. The helper's winner layout must not leak into its caller.
+ @Test public void testAllocationLoopWinnerGraph() {
+ CodeGen code=compile(THING+"""
+ struct Box { Thing child; new Box={ Thing t -> child=t; }; };
+ val use_noInline={ Box b -> b.child.x; };
+ val find_noInline={ i64 n ->
+ while( true ) {
+ val b=new Box(new Thing(n));
+ if( use_noInline(b)==3 ) return b;
+ n--;
+ }
+ };
+ val work_noInline={ i64 n -> use_noInline(find_noInline(n)); };
+ return work_noInline(arg);
+ """);
+ var find=code._allocation.summary("find_noInline").requireSupported();
+ for( String type : new String[]{"Thing","Box"} ) {
+ var winner=allocations(find,type).get(0);
+ assertEquals("result",winner.destination());
+ assertNotNull(winner._frame._loop);
+ assertNull(winner._scope);
+ var caller=allocations(code._allocation.summary("work_noInline"),type).get(0);
+ assertEquals("frame",caller.destination());
+ assertSame(code._allocation.summary("work_noInline"),caller._frame);
+ assertSame(caller._frame,caller._scope);
+ assertTrue(caller._frame._scratch.contains(caller));
+ }
+ assertEquals("3",Eval2.eval(code,5));
+ }
+
+ // Continuation ports can return borrowed references into the next activation.
+ // They do not require retaining any storage created by the iteration.
+ @Test public void testAllocationBorrowedContinuation() {
+ CodeGen code=compile(THING+"""
+ val work_noInline={ Thing a, Thing b, i64 n ->
+ Thing !p=a;
+ i64 s=0;
+ while( n>0 ) {
+ s+=read_noInline(p);
+ p=(n&1) ? a : b;
+ n--;
+ }
+ return s+read_noInline(p);
+ };
+ return work_noInline(new Thing(10),new Thing(20),arg);
+ """);
+ var fun=code._allocation.summary("work_noInline").requireSupported();
+ assertEquals(1,fun._frames.size());
+ var loop=fun._frames.get(0).requireSupported();
+ assertEquals(2,loop._continues.size());
+ for( var site : loop._continues ) {
+ assertNull(site._allocation);
+ assertTrue(site._arg==3 || site._arg==4);
+ assertTrue(loop._returns.contains(site));
+ }
+ assertTrue(loop._scratch.isEmpty());
+ assertEquals("50",Eval2.eval(code,3));
+ assertEquals("10",Eval2.eval(code,0));
+ }
+
+ // Both exits clean the same scratch. The normal result here is a scalar,
+ // loaded before cleanup; returning it does not retain the temporary object.
+ @Test public void testAllocationScalarLoopExit() {
+ CodeGen code=compile(THING+"""
+ val work_noInline={ i64 n ->
+ i64 result=-1;
+ while( n>0 ) {
+ val t=new Thing(n);
+ val x=read_noInline(t);
+ if( n==3 ) { result=x; break; }
+ n--;
+ }
+ return result;
+ };
+ return work_noInline(arg);
+ """);
+ var fun=code._allocation.summary("work_noInline").requireSupported();
+ var temp=allocations(fun,"Thing").get(0);
+ var loop=temp._frame.requireSupported();
+ assertSame(loop,temp._scope);
+ assertTrue(loop._scratch.contains(temp));
+ assertTrue(loop._returns.isEmpty());
+ assertTrue(loop._continues.isEmpty());
+ boolean scalar=false;
+ for( var value : loop._exit.values() )
+ if( value._type instanceof com.seaofnodes.simple.type.TypeInteger ) scalar=true;
+ assertTrue(scalar);
+ assertEquals("3",Eval2.eval(code,5));
+ assertEquals("-1",Eval2.eval(code,2));
+ }
+
+ // Returning from an inner loop exports through both enclosing interfaces;
+ // each exited frame has its own cleanup obligations.
+ @Test public void testAllocationNestedFrameReturn() {
+ CodeGen code=compile(THING+"""
+ struct Scratch { i64 x; new Scratch={ i64 n -> x=n; }; };
+ val readScratch_noInline={ Scratch s -> s.x; };
+ val find_noInline={ i64 n ->
+ while( n>0 ) {
+ val scratch=new Scratch(n);
+ i64 i=readScratch_noInline(scratch);
+ while( i>0 ) {
+ val candidate=new Thing(i);
+ if( read_noInline(candidate)==3 ) return candidate;
+ i--;
+ }
+ n--;
+ }
+ return null;
+ };
+ Thing? t=find_noInline(arg);
+ return t ? t.x : -1;
+ """);
+ var fun=code._allocation.summary("find_noInline").requireSupported();
+ var winner=allocations(fun,"Thing").get(0);
+ var scratch=allocations(fun,"Scratch").get(0);
+ var inner=winner._frame;
+ var outer=scratch._frame;
+ assertSame(outer,inner._parent);
+ assertSame(fun,outer._parent);
+ assertTrue(inner._returns.contains(winner));
+ assertTrue(outer._returns.contains(winner));
+ assertTrue(fun._returns.contains(winner));
+ assertNull(winner._scope);
+ assertSame(outer,scratch._scope);
+ assertTrue(outer._scratch.contains(scratch));
+ assertFalse(inner._scratch.contains(scratch));
+ assertEquals("3",Eval2.eval(code,5));
+ assertEquals("-1",Eval2.eval(code,2));
+ }
+
+ @Test public void testAllocationExitlessLoop() {
+ CodeGen code=compile(THING+"""
+ val spin_noInline={ i64 n ->
+ while( true ) {
+ val t=new Thing(n);
+ n=read_noInline(t)+1;
+ }
+ return 7;
+ };
+ spin_noInline(arg);
+ return 7;
+ """);
+ var fun=code._allocation.summary("spin_noInline").requireSupported();
+ assertEquals(1,fun._frames.size());
+ var loop=fun._frames.get(0).requireSupported();
+ assertNotNull(loop._loop);
+ assertSame(loop._loop,loop._loop._ltree._head);
+ assertSame(fun,loop._parent);
+ var temp=allocations(fun,"Thing").get(0);
+ assertSame(loop,temp._scope);
+ assertTrue(loop._scratch.contains(temp));
+ assertTrue(loop._returns.isEmpty());
+ assertTrue(loop._continues.isEmpty());
+ // No synthetic return before TypeCheck or serialization; scheduling
+ // supplies the exit later. The evaluator still cannot return.
+ assertSame(com.seaofnodes.simple.type.Type.XCONTROL,fun._fun.ret().ctrl()._type);
+ assertNull(Eval2.eval(code,0,10));
+ }
+
+ @Test public void testAllocationNativeBorrow() {
+ CodeGen code=compile("""
+ { i64 i64 -> i64 } native="C";
+ val work_noInline={i64 n ->
+ val a=new u8[16], b=new u8[16];
+ i64 pa=a, pb=b;
+ i64 p=n ? pa : pb;
+ return native(p+2,8);
+ };
+ return work_noInline(arg);
+ """);
+ var fun=code._allocation.summary("work_noInline").requireSupported();
+ int count=0;
+ for( var site : fun._sites ) if( site._allocation!=null ) {
+ count++;
+ assertSame(fun,site._scope);
+ assertTrue(fun._scratch.contains(site));
+ assertFalse(fun._returns.contains(site));
+ }
+ assertEquals(2,count);
+ assertTrue(code._allocation.toString().contains("native (borrow; no retain)"));
+ }
+
+ @Test public void testAllocationNativeLoopBorrow() {
+ CodeGen code=compile("""
+ { i64 i64 -> i64 } native="C";
+ val borrow_noInline={u8[] bytes ->
+ i64 p=bytes;
+ return native(p,bytes#);
+ };
+ val work_noInline={i64 n ->
+ i64 total=0;
+ while(n>0) {
+ val bytes=new u8[16];
+ total+=borrow_noInline(bytes);
+ i64 p=bytes;
+ total+=native(p+1,8);
+ n--;
+ }
+ return total;
+ };
+ return work_noInline(arg);
+ """);
+ code._allocation.summary("borrow_noInline").requireSupported();
+ var fun=code._allocation.summary("work_noInline").requireSupported();
+ int count=0;
+ for( var site : fun._sites ) if( site._allocation!=null ) {
+ count++;
+ assertNotNull(site._frame._loop);
+ assertSame(site._frame,site._scope);
+ assertTrue(site._scope._scratch.contains(site));
+ assertFalse(site._scope._continues.contains(site));
+ }
+ assertEquals(1,count);
+ }
+
+ @Test public void testAllocationRawAddressBoundaries() {
+ String[] bodies={
+ """
+ i64 p=0;
+ while(n>0) {
+ if(p) native(p);
+ val bytes=new u8[16];
+ p=bytes;
+ n--;
+ }
+ return 0;
+ """,
+ "val bytes=new u8[16]; i64 p=bytes; addresses[0]=p; return native(addresses[0]);"
+ };
+ for( int i=0; i<bodies.length; i++ ) {
+ CodeGen code=compile("{ i64 -> i64 } native=\"C\"; val addresses=new i64[1]; "+
+ "val work_noInline={i64 n -> "+bodies[i]+"}; return work_noInline(arg);");
+ var fun=code._allocation.summary("work_noInline").requireSupported();
+ for( var site : fun._sites ) if( site._allocation!=null ) {
+ // Carrying the integer across iterations does not carry its
+ // backing storage. The first program uses a stale raw address.
+ assertSame(site._frame,site._scope);
+ assertTrue(site._scope._scratch.contains(site));
+ }
+ }
+ }
+
+ private static List<KeepAliveNode> keeps(CodeGen code) {
+ var keeps=new ArrayList<KeepAliveNode>();
+ code._start.walk(n -> { if( n instanceof KeepAliveNode k ) keeps.add(k); return null; });
+ return keeps;
+ }
+
+ @Test public void testKeepAliveWrappersAndReplacement() {
+ CodeGen code=compile("""
+ { i64 -> i64 } native="C";
+ val forward_noInline={ i64 p -> native(p); };
+ val wrapper_noInline={ i64 p -> forward_noInline(p); };
+ val addresses=new i64[2];
+ val work_noInline={ i64 n ->
+ i64 raw=new u8[16];
+ addresses[0]=raw;
+ raw=new u8[32];
+ addresses[1]=raw;
+ return wrapper_noInline(addresses[n&1]);
+ };
+ return work_noInline(arg);
+ """);
+ var fun=code._allocation.summary("work_noInline").requireSupported();
+ int count=0;
+ for( var site : fun._sites ) if( site._allocation!=null ) {
+ count++;
+ assertSame(fun,site._scope);
+ assertTrue(fun._scratch.contains(site));
+ }
+ assertEquals(2,count);
+ assertEquals(1,keeps(code).size());
+ KeepAliveNode keep=keeps(code).get(0);
+ assertTrue(keep.in(1) instanceof KeepAliveNode.Values);
+ assertSame(keep,fun._fun.ret().ctrl());
+ assertTrue(keep.in(0) instanceof CProjNode);
+ }
+
+ @Test public void testKeepAliveConditionalAndErasure() {
+ CodeGen code=compile("""
+ { i64 -> i64 } native="C";
+ val work_noInline={ i64 n ->
+ i64 raw=0;
+ n && ((raw=new u8[16])!=null);
+ return native(raw);
+ };
+ return work_noInline(arg);
+ """);
+ var fun=code._allocation.summary("work_noInline").requireSupported();
+ assertEquals(1,keeps(code).size());
+ KeepAliveNode keep=keeps(code).get(0);
+ assertTrue(keep.in(1) instanceof PhiNode);
+ assertSame(keep,fun._fun.ret().ctrl());
+ CallNode call=((CallEndNode)keep.in(0).in(0)).call();
+ Node raw=call.arg(3);
+ KeepAliveNode.erase(code._start);
+ assertTrue(keeps(code).isEmpty());
+ assertSame(raw,call.arg(3)); // Shared ordinary Phi must survive erasure.
+ assertFalse(raw.isDead());
+ }
+
+ @Test public void testKeepAliveLoopExits() {
+ CodeGen code=compile("""
+ { i64 -> i64 } native="C";
+ val work_noInline={ i64 n ->
+ i64 total=0;
+ while(n>0) {
+ i64 raw=new u8[16];
+ total+=native(raw);
+ if(n==1) return total;
+ if(n==2) break;
+ n--;
+ if(n==3) continue;
+ total++;
+ }
+ return total;
+ };
+ return work_noInline(arg);
+ """);
+ var fun=code._allocation.summary("work_noInline").requireSupported();
+ assertFalse(keeps(code).isEmpty());
+ for( var site : fun._sites ) if( site._allocation!=null ) {
+ assertNotNull(site._frame._loop);
+ assertFalse(site._frame._continues.contains(site));
+ assertNotNull(site._scope);
+ }
+ }
+
+ @Test public void testKeepAliveOuterLoopScope() {
+ CodeGen code=compile("""
+ { i64 -> i64 } native="C";
+ val work_noInline={ i64 n ->
+ i64 raw=0;
+ while((raw=new u8[16]) && native(raw) && n-->0) { }
+ return n;
+ };
+ return work_noInline(arg);
+ """);
+ var fun=code._allocation.summary("work_noInline");
+ // Predicate conversions belong to the enclosing scope; every iteration
+ // adds storage to that scope, unlike a conversion in the loop body.
+ assertFalse(fun.supported());
+ assertTrue(fun._reject,fun._reject.contains("across its backedge"));
+ }
+
+ @Test public void testKeepAliveRawReturnAndUnused() {
+ CodeGen code=compile("""
+ val work_noInline={ ->
+ i64 raw=new u8[16];
+ return raw+17;
+ };
+ return work_noInline();
+ """);
+ var fun=code._allocation.summary("work_noInline").requireSupported();
+ assertTrue(fun._returns.isEmpty()); // Returned integer has no lifetime contract.
+ assertFalse(fun._scratch.isEmpty());
+ assertEquals(1,keeps(code).size());
+ code=compile("val work_noInline={ -> val a=new u8[16]; i64 unused=a; return 1; }; return work_noInline();");
+ assertTrue(keeps(code).isEmpty());
+ assertEquals("1",Eval2.eval(code,0));
+ }
+
+ @Test public void testKeepAliveImportedBody() throws Exception {
+ Path build=Path.of("build/objs/separate");
+ Files.createDirectories(build);
+ Path lib=Files.createTempDirectory(build,"keepalive-");
+ new CodeGen(null,lib.toString(),null,"Borrow","""
+ { i64 -> i64 } native="C";
+ val borrow={ u8[] a -> i64 raw=a; return native(raw); };
+ """,123,true,TypeInteger.BOT).driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false);
+ var paths=new Ary<>(new String[]{lib.toString()});
+ CodeGen code=new CodeGen(null,lib.toString(),paths,"BorrowClient",
+ "return Borrow.borrow(new u8[16]);",123,true,TypeInteger.BOT)
+ .driver(CodeGen.Phase.TypeCheck);
+ assertFalse(keeps(code).isEmpty());
+ code.driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false);
+ assertTrue(keeps(code).isEmpty());
+ }
+
+ @Test public void testKeepAliveForwardConversion() {
+ CodeGen code=compile("""
+ { i64 -> i64 } native="C";
+ val work_noInline={ -> i64 raw=make_noInline(); return native(raw); };
+ val make_noInline={ -> new u8[16]; };
+ return work_noInline();
+ """);
+ var fun=code._allocation.summary("work_noInline").requireSupported();
+ assertEquals(1,keeps(code).size());
+ assertFalse(fun._scratch.isEmpty());
+ assertTrue(fun._returns.isEmpty());
+ }
+
+ @Test public void testKeepAliveImplicitScopes() {
+ CodeGen code=compile("""
+ { i64 -> i64 } native="C";
+ val work_noInline={ i64 n ->
+ i64 raw=0;
+ if(n) raw=new u8[16]; else raw=new u8[32];
+ return native(raw);
+ };
+ return work_noInline(arg);
+ """);
+ code._allocation.summary("work_noInline").requireSupported();
+ // Each unbraced arm ends its own borrowing scope. The subsequent call
+ // deliberately uses stale integers; it must not move these endpoints.
+ assertEquals(2,keeps(code).size());
+ for( KeepAliveNode keep : keeps(code) ) {
+ assertTrue(keep.in(0) instanceof CProjNode);
+ assertTrue(keep.in(0).in(0) instanceof IfNode);
+ boolean merges=false;
+ for( Node use : keep._outputs ) if( use instanceof RegionNode ) merges=true;
+ assertTrue(merges);
+ }
+ }
+
+ @Test public void testKeepAliveNestedFunction() {
+ CodeGen code=compile("""
+ { i64 -> i64 } native="C";
+ val work_noInline={ i64 n ->
+ i64 raw=new u8[16];
+ val helper_noInline={i64 k -> while(k>0) k--; return k;};
+ helper_noInline(n);
+ return native(raw);
+ };
+ return work_noInline(arg);
+ """);
+ var fun=code._allocation.summary("work_noInline").requireSupported();
+ assertEquals(1,keeps(code).size());
+ assertSame(keeps(code).get(0),fun._fun.ret().ctrl());
+ assertFalse(fun._scratch.isEmpty());
+ }
}
diff --git a/chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java b/chapter33/src/test/java/com/seaofnodes/simple/PhaseTest.java
index b94b4f2c..2794fca9 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 Allocation TypeCheck LoopTree Unlink Schedule LocalSched",
+ assertEquals("Parse Iter Opto IterPostOpto FinalizeIR LoopTree Allocation TypeCheck Unlink Schedule LocalSched",
String.join(" ",phases));
assertNull(code._serial);
assertNull(code._mach);