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