diff options
| author | Cliff Click <cliffc@acm.org> | 2026-11-21 22:00:10 -0800 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-11-21 22:00:10 -0800 |
| commit | 96f150b05516bc254c4035821c0119db1ecce301 (patch) | |
| tree | 0058ada01b43b8b42c3c999068c3adf1d2c3e92a | |
| parent | c201515eeb2e99cb6f0e820459662affc047c2ce (diff) | |
| download | Simple-96f150b05516bc254c4035821c0119db1ecce301.tar.gz Simple-96f150b05516bc254c4035821c0119db1ecce301.zip | |
Simple loops, loop escapes and loop scratchch33
Move LoopTree finding earlier.
KeepAlive to force raw ptr->int to keep bytes handed to native code alive.
(not sure this is worth it, alternative is to just pass the ptr)
27 files changed, 3048 insertions, 168 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); diff --git a/docs/automatic-memory-management-survey.md b/docs/automatic-memory-management-survey.md index 925fb6a2..d6fbd0c0 100644 --- a/docs/automatic-memory-management-survey.md +++ b/docs/automatic-memory-management-survey.md @@ -63,10 +63,15 @@ references, and array layouts reviewed and accepted 2026-11-19; see the - Classes explicitly opt into being deletable; the spelling is undecided. `delete` permits storage recycling rather than immediately invalidating the storage. Automatic reclamation still governs the enclosing region's lifetime. -- Arrays are never user-deletable. Their storage follows automatic lifetimes. - A container's obsolete backing storage may be internally recycled only when - the compiler proves no usable references into it survive. This is distinct - from class-slot recycling with permitted stale references after `delete`. +- Ordinary arrays are not deletable; their storage follows automatic lifetimes. + Agreed extension, 2026-11-21: deletable arrays have a distinct type (spelling + undecided), disallow interior references, and require unique access and no + escaping aliases. The compiler must establish that no usable aliases or + outstanding borrows survive `delete`; deletion consumes the owning access. + Growable library containers can use this type for power-of-two backing arrays, + explicitly deleting replaced buffers into a buddy allocator. Such arrays do + not permit the stale-reference behavior of deletable class slots. Separate + length storage remains a layout design, not a safety requirement for recycling. - `new E[N]` creates a fixed-length array, with N possibly computed at runtime. `new E[]` starts empty and permits append with `es += elem`. Access and indexed assignment are checked against the current length and do not extend @@ -238,6 +243,24 @@ the compiler can check those promises against its body; for native code the FFI declaration is trusted. A mismatch is a bug in the binding contract or its implementation, not a reason to weaken the ordinary call-site lifetime rules. +Update 2026-11-21: for the first native-call implementation, assume native code +borrows passed references only until the call returns. It does not hide, escape, +or retain them. Keep the existing pointer-to-integer ABI conversion (Plan A), +while preserving the storage lifetime through the native call. A raw address +does not itself grant a longer lifetime: using the containing lexical scope as +the keep-alive bound is acceptable, and storage may be reclaimed/reused when +that scope ends. This limitation belongs in the user documentation. Changing +native signatures to typed pointers with correctly extended machine arguments +is a fallback, not required for this first cut. + +The current analysis tracks raw-address SSA expressions, including arithmetic +and Phis, in its function/iteration frames. Brace-level lifetime markers are not +present after Opto. Raw-address returns, memory stores, and forwarding through +Simple integer parameters remain conservative rejections; typed-reference +wrappers can perform the conversion at the native boundary. Native-produced +Simple pointers still need a result-storage contract. These are implementation +limits, not a claim that all such programs inherently require unbounded storage. + #### Returned-borrow syntax and FFI boundary — agreed 2026-11-19 `from` introduces a result's borrowed-storage origin in a function type. diff --git a/docs/roadmap.md b/docs/roadmap.md index e012eae3..89504830 100644 --- a/docs/roadmap.md +++ b/docs/roadmap.md @@ -44,6 +44,15 @@ and the supporting libraries. ## Compilation and optimization +### Inferred global result storage + +Chapter 33's `testAllocationLoopWinnerAndScratch` exposes a pre-existing bug if +its top-level `Thing? t=find_noInline(arg)` is changed to `val t=...`. The nullable +winner's optimized result type is correct, but the canonical class field remains +`BOTTOM`; its Store never resolves a width and fails `StoreNode.err`. Reproduced +with the Allocation phase skipped. Fix inferred global field/layout finalization; +an explicit field type currently avoids the failure. + ### General cleanup Keep the recursive-descent path aligned with the grammar. Review moving `TYPES` @@ -55,8 +64,26 @@ convention. ### Phase ordering and incremental analysis +Required before closing Chapter 33 (deferred for now): + +- Insert NeverExits during the original LoopTree build, before Allocation. + Preserve nonreturning-function semantics through TypeCheck and serialization; + synthetic scheduling exits must not make a function appear to return. +- With those exits present, remove Allocation's special support for zero-exit + bodies, including the extra forward CFG traversal added for them. +- Maintain LoopTree membership with local edits when Lower changes the CFG; + remove the full loop-tree rebuild before scheduling. + Remaining work: +- Recognize `_exit` as nonreturning without dropping the call or its memory + dependencies. The current native-borrowing analysis accepts it, but does not + change CFG behavior. Preferred direction under discussion: connect a synthetic + live-control/TOP-value path to the function's existing Return merge, preserving + ordinary function walks, while killing the source continuation. Share the + NeverExit merge machinery if practical. Check synthetic-only return diagnostics, + serialization, and propagation through callers; do not merely set CallEnd to + dead control or introduce an unhandled edge to StopCU. - Review the remaining node-ID bitset costs in Eval2 scheduling. Scratch arrays now retain capacity and reset only touched entries, but bitsets still span previously allocated node IDs. Scheduling a newly loaded diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index 2c327292..dc6c549e 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -42,14 +42,73 @@ the first analysis pass after Opto and before TypeCheck, few new classes, ASCII debugging, conservative rejections, and 3-4 poster children. The agreed decisions and remaining questions are in [the survey's base design](../docs/automatic-memory-management-survey.md#agreed-base-design--2026-11-17). The initial implementation is `codegen/Allocation.java`, after FinalizeIR and -before TypeCheck. One call-DAG DFS composes symbolic summaries in postorder; +LoopTree, before TypeCheck. One call-DAG DFS composes symbolic summaries in postorder; local reference-edge closure uses a worklist. Four poster children and boundary checks live in Chapter33Test. The phase is analysis-only: existing allocation lowering is unchanged. `simple.alloc.dump` prints ASCII, `simple.alloc.check` requires all plans to be supported; otherwise unsupported summaries record a -rejection without blocking the existing allocator. Loops, SCCs, variable sizes, -opaque calls, raw addresses, and unresolved pointer-load origins are deferred. +rejection without blocking the existing allocator. SCCs, variable sizes, +opaque calls, and raw addresses are deferred. Pointer-valued loads now select +field targets; borrowed paths such as arg3.c have their own destination identity. +Local weak-union closure covers loads, stores, and call substitutions before +owner propagation. Actual aliases are resolved at calls; array indices share +one field. Fresh sites are imported once per call. Incoming borrowed paths are +separate from store edges: returning a child must not retain its holder. Weak +updates that expand paths beyond the body's reads plus imported path depths +reject instead of truncating; memory-ordered updates remain future work. +Loop Phis now join the same local monotone reference calculation. Allocation +uses CFG `_ltree` membership and LoopTree parent links, without rediscovering +loop bodies. Reducibility is asserted by LoopTree. The early tree build does +not insert synthetic exits: doing so would change nonreturning summaries before +serialization. Unlink rebuilds the tree after Lower's CFG changes and inserts +one synthetic exit only for loops with zero exits. Any fresh +allocation reachable across a backedge rejects the plan, via pointer Phis or +memory retention (including helper effects). Collection starts from both the +function entry and Return, so zero-exit bodies are analyzed without synthetic +exits. Exit-only winners get fixed storage +before the loop; unrelated scratch uses iteration storage. Inner-loop winners +can live in the outer iteration. Bound exemptions and overwrite/liveness proofs +are not implemented yet. Functions and loop iterations now use the same Summary +class, with entry/normal-exit/continuation ports, retention effects, and scratch +cleanup sets. One function-wide reference closure shares SSA/Site identities +with nested loop summaries; calls substitute those identities. Summary interfaces +drive promotion through parent frames, replacing the separate loop placement +scan. Continuation cleanup and normal-exit cleanup use the same scratch set. +Borrowed continuation references are supported. Tests include scalar exit values, +nested returns, mixed winner/scratch, helper allocations, exit-only stores, winner +graphs, and rejected linked/array/helper retention. No stack lowering is emitted. No new language syntax or serialized lifetime summaries are implemented yet. +Update 2026-11-21: Cliff requires the temporary LoopTree ordering above to be +replaced before closing Chapter 33, but explicitly deferred implementation. +Insert NeverExits in the original LoopTree build, then remove Allocation's +zero-exit-body support and its extra forward CFG traversal. Resolve the +nonreturning-summary issue rather than delaying synthetic exits. Lower should +maintain LoopTree with minor local edits, eliminating the full rebuild before +scheduling. Track completion in the roadmap's phase-ordering section. +The 2026-11-21 [allocation survey](../chapter33/docs/allocation-survey.md) +measures `sys` (98/179 supported summaries, 11 with user-storage sites) and ten +examples (43/68 own summaries, three with user-storage sites). First-cause +rejections are mostly native/opaque calls and raw addresses; they mask dynamic +arrays and potentially later failures. Scalar libm/clock calls need targeted +contracts; do not interpret arbitrary i64 arguments as pointer-free. The native +`simple_text_float` allocates its returned Simple byte array with malloc, outside +NewNode analysis, so needs an allocation contract or a caller-buffer interface. +Local variable-sized scratch and returned variable-sized arrays both reject; +fixed-size Holder overwrites reject while explicit object reuse passes. These +are survey findings, not authorization to change contracts or allocation lowering. +The standalone probe and function-level snapshot live beside the report. +Update 2026-11-21, native borrowing: Cliff authorized Plan A: native calls borrow +references through the call and do not hide, publish, or retain them. Allocation +now recognizes finite all-native target sets via externFunc, accepts scalar +results, and follows PtrToInt provenance through SSA arithmetic/Phis. Raw returns, +memory stores, and Simple integer-argument forwarding still reject; typed-pointer +wrappers work. Native Simple-pointer results still require origin contracts. +No ABI or runtime allocator changes. Scope lifetime is the documented upper +bound; brace-level scopes are absent here, so current plans use function/iteration +frames. Tests cover raw Phis/offsets, loop scratch, typed wrappers, and backedge +and memory escape rejection. `_exit` no-return CFG work remains open; Cliff's +Return-merge alternative is recorded in the roadmap. Do not use dead CallEnd +control alone: it can discard the very terminating path that must remain rooted. Update 2026-11-19: Cliff accepted the entire [embedded-object design](../docs/automatic-memory-management-survey.md#agreed-design-embedded-objects-values-and-references), including `*T` object values, `&` interior references, and `*(T[4])` embedded |
