From ac525dc59de1ae195c40f8e21b09485d0e5d9330 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 24 Oct 2026 09:38:56 -0700 Subject: module split --- chapter-escape/README.ja.md | 3 +- chapter-escape/README.md | 53 +++++++++--------- .../main/java/com/seaofnodes/simple/Parser.java | 48 +++++++++++++++-- .../java/com/seaofnodes/simple/node/ScopeNode.java | 27 +++++++--- .../java/com/seaofnodes/simple/type/Field.java | 6 +-- .../seaofnodes/simple/FinalConstructionTest.java | 63 ++++++++++++++++++++++ 6 files changed, 159 insertions(+), 41 deletions(-) create mode 100644 chapter-escape/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java (limited to 'chapter-escape') diff --git a/chapter-escape/README.ja.md b/chapter-escape/README.ja.md index 43bb4411..c496df4c 100644 --- a/chapter-escape/README.ja.md +++ b/chapter-escape/README.ja.md @@ -2,7 +2,8 @@ [English](README.md) | 日本語 -[前章: オブジェクトの構築と非公開メモリ](../chapter-construction/README.ja.md) +[前章: オブジェクトの構築と非公開メモリ](../chapter-construction/README.ja.md) | +[次: モジュールと遅延クラス初期化](../chapter-modules/README.ja.md) この章では、オブジェクトや関数のアドレスが、解析できない外部コードに届くかを追跡します。 関数のアドレスを既知の関数に渡すだけでは、未知の呼び出し元を残す必要はありません。 diff --git a/chapter-escape/README.md b/chapter-escape/README.md index 6098c72c..a1fda17b 100644 --- a/chapter-escape/README.md +++ b/chapter-escape/README.md @@ -2,14 +2,15 @@ English | [日本語](README.ja.md) -[Previous: Construction and Private Memory](../chapter-construction/README.md) +[Previous: Construction and Private Memory](../chapter-construction/README.md) | +[Next: Modules and Lazy Class Initialization](../chapter-modules/README.md) We run a simple form of escape analysis in this chapter, tracking both functions and some aliases across all calls and memory updates. One of the goals here is to discover when we've found *all* the callers of a function; at this point we can drop the conservative "unknown caller" input and run -constant propagation through a functions arguments. +constant propagation through a function's arguments. The preceding compiler kept an unknown caller for every surviving function address. That was safe, but it lost facts even when all uses stayed within the @@ -44,7 +45,7 @@ SCCP can then infer `base == 2`, including in its recursive body. The multiply by 2 can become a shift without inlining or cloning either recursive body - and we open ourselves up to further optimizations. -Passing `power` to an unknown caller, or passing it to a native function, +Passing `power` to an unknown callee, or passing it to a native function, changes the answer. The external caller may choose another base. The compiler must retain `power` and give its parameters their declared bounds. @@ -52,8 +53,8 @@ must retain `power` and give its parameters their declared bounds. ## Publishing an object and exposing it to unknown code The construction chapter's `EscapeNode` publishes initialized fields into -ordinary public memory. The completed object has not, yet, escaped; it -depends on what happens to the `self` pointer. +ordinary public memory. That alone does not expose the completed object to +unknown code; exposure depends on what happens to the `self` pointer. Escape analysis starts at the boundary with unknown code. Returning an object across that boundary exposes its field aliases. An exposed field can contain @@ -67,7 +68,7 @@ The same rule applies to arguments passed to native code. Native code may keep an address after the call returns, or use it on a path that never returns. `Stop` therefore also collects exposure directly from reachable native calls. A call to a known Simple function instead passes the values and memory to that -function's graph; its uses SCCP to determine what escapes. +function's graph; SCCP follows those uses to determine what escapes. This is a conservative analysis by field alias. Two instances of the same struct share their field aliases. Exposing one may therefore expose addresses @@ -75,7 +76,7 @@ stored in the same fields of another. It does not identify each allocation separately. Another way to think of this: this analysis is what we get "for free" from just -running SCCP. We extend and sharpen the lattice a litte more, to allow more +running SCCP. We extend and sharpen the lattice a little more, to allow more precise tracking. @@ -89,17 +90,15 @@ precise tracking. `XInt`, already used for function sets, represents both. An empty set means no address has been discovered; a full set is the conservative unknown case. Meeting summaries unions the sets. Dual types complement them, so the existing -lattice operations and tests still apply. The `XInt` utilities themselves just -track collections of immutable bits. They have no indirection, they are just -fly-weight wrappers around `int[]`s. The help support shared and immutable -`int[]`s so that these bit sets follow the same invariants as the rest of the -Types. +lattice operations and tests still apply. The `XInt` utilities operate directly +on shared, immutable `int[]` arrays; they add no wrapper object. Interning lets +these sets follow the same sharing rules as the rest of the Types. Stores record addresses carried by their values. Memory Phis combine those facts over live paths. `MemMergeNode` gathers the slices whose aliases are exposed, rather than making every locally stored callback externally callable. If an exposed field reveals another alias, that slice participates as well. In -short, we follow escaping values through memory using `Types` using the formal +short, we follow escaping values through memory using the existing `Node.compute` and `Type` machinery. The hidden constructor helpers still keep fields in local SSA values and use @@ -121,8 +120,8 @@ Start -> callable functions -> returns and exposed memory -> Stop ``` Before SCCP, parsing and pessimistic iteration keep conservative callers and -memory. During SCCP, functions lose their unknown-caller edges unless their -function pointer escapes and become unknown entry points. Concrete calls then +memory. During SCCP, functions other than the chosen entry points lose their +unknown-caller edges unless their function pointers escape. Concrete calls rebuild the known call graph. Stop combines the results and memory visible to external callers. Those @@ -133,22 +132,24 @@ parameter inputs. That function can reveal further addresses through its own calls and returns. The ordinary worklist repeats until types, exposure sets, and call edges agree - i.e. the normal SCCP reaches a fixed point. -If you have a `main` function, it starts discovery. Without `main`, the code -is assumed to be a library, and all public entry points are fair game. +An explicit `main`, or one synthesized for a top-level return, starts discovery. +Without one, the code is treated as a library: ordinary named functions outside `sys` +seed the unknown entry points. Module privacy refines this rule in the next +chapter. Once SCCP finishes, you might have ordinary public functions callable from anywhere, or functions called via their name (direct field load holding the -function point), or via a function pointer thats only used in a few locations, +function pointer), or via a function pointer that's only used in a few locations, or it might escape in a region and get mixed with other function pointers, or you might never call a function at all. If a function is getting called, but -never publically, its arguments can sharpen across the `meet` of all call sites -- perhaps allowing not-null-ness to be tracked precisely and avoid some -explicit tests. - -After optimization, `FinalizeIR` freezes the external summary - the escaped -values from `Start/Stop`, for tracking if a function gets a public entry in the -ELF file. `FinalizerIR` does a few more cleanups, including removing the -`Stop->Start` edge SCCP uses to track escapes across external calls. +never from unknown code, its arguments can sharpen across the `meet` of all +call sites, perhaps proving an argument non-null and avoiding explicit tests. + +After optimization, `FinalizeIR` freezes the external summary from `Start/Stop` +and removes the `Stop->Start` edge SCCP uses to track escapes across external +calls. This summary says which functions need unknown callers; it does not +control ELF symbol visibility. The current ELF writer emits every retained +named function as a global symbol. ## Construction boundary to review diff --git a/chapter-escape/src/main/java/com/seaofnodes/simple/Parser.java b/chapter-escape/src/main/java/com/seaofnodes/simple/Parser.java index f22b73f1..19dd1c29 100644 --- a/chapter-escape/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter-escape/src/main/java/com/seaofnodes/simple/Parser.java @@ -267,7 +267,7 @@ public class Parser { // Pre-call the function from Start, with worse-case arguments. This // represents all the future, yet-to-be-parsed functions calls and // external calls. - _scope.push(new Kind.Func()); + _scope.push(new Kind.Func(_privateFun!=null)); ctrl(fun); // Scope control from function // Unknown callers supply whole memory; field aliases are discovered lazily. _scope.mem(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,new ProjNode(_code._start,1,ScopeNode.MEM0).peephole()).peephole()); @@ -768,6 +768,7 @@ public class Parser { // The alloc() call added the allocation scope !_scope.canInit(def) ) throw error("Cannot reassign final '"+name+"'"); + checkSharedField(def); // Parse assignment expression checkCaptureWrite(def); @@ -869,6 +870,14 @@ public class Parser { throw error("a not-null/non-zero expression"); t = expr._type; if( !xfinal ) t = inferredType(t); // Widen if not final + // A final field is still a local variable during construction. + // Its constant default is a value, not a one-value declaration + // type: later assignments and loop Phis may change it. + else if( _scope.inConstructor() && !(t instanceof TypeFunPtr) ) { + Type wide=inferredType(t); + t = t instanceof TypeMemPtr ptr && ptr.notNull() + ? TypeMemPtr.make((byte)2,((TypeMemPtr)wide)._obj,false).withAccess(ptr._ro) : wide; + } } // expr is a constant function if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { @@ -948,7 +957,10 @@ public class Parser { Var v = _scope.var(index++); if( v.isFRef() ) continue; Node value = _scope.in(v); - boolean constant = v._final && v._init && value._type.isConstant(); + // Only function declarations are shared across instances. A final + // data field can change in a named or inline constructor, so a + // constant default does not justify folding every future read. + boolean constant = v._final && v._init && value._type instanceof TypeFunPtr && value._type.isConstant(); Field field = Field.make(v._name,v.type(),_code.getALIAS(),v._final,constant); shape=shape.add(field); TYPES.put(_nestedType,TypeMemPtr.make(shape)); @@ -1452,8 +1464,9 @@ public class Parser { if( name!=null ) { Var n = _scope.lookup(name); if( n != null && !(n.type() instanceof TypeMemPtr) ) { - if( n._final ) + if( n._final && !_scope.canInit(n) ) throw error("Cannot reassign final '"+n._name+"'"); + checkSharedField(n); Node expr = liftExpr(peep(new AddNode(_scope.in(n),con(delta))),n.type(),true); _scope.update(n,expr); return expr; @@ -1545,8 +1558,9 @@ public class Parser { if( ch==0 ) // Normal primary, check for postfix updates return parsePostfix(rvalue); // Assign-update direct into Scope - if( var._final ) + if( var._final && !_scope.canInit(var) ) throw error("Cannot reassign final '"+var._name+"'"); + checkSharedField(var); checkCaptureWrite(var); Node op = opAssign(ch,rvalue, var.type() ); _scope.update(var,op); @@ -1600,6 +1614,24 @@ public class Parser { throw error("Cannot assign captured variable '"+var._name+"' in an initializer"); } + // Inline constructors have local field slots too, but shared function + // declarations have no instance slot to publish. Do not silently discard + // an assignment to one of those declarations. + private void checkSharedField(Var var) { + if( !_scope.canInit(var) ) return; + if( _scope.kind(var) instanceof Kind.Define ) { + checkPrivateWrite(var._name); + return; + } + for( int i=_scope.depth()-1; i>0; i-- ) + if( _scope._kinds.at(i) instanceof Kind.Alloc alloc ) { + Field field=alloc._tmp._obj.field(var._name); + if( field!=null && field._one ) + throw error("Cannot reassign shared function '"+var._name+"'"); + return; + } + } + // Check for assign-update, "x += e0". // Returns "x + e0"; the caller assigns value. // if ch is postfix, then lhs is kept and caller will unkeep and return it. @@ -1980,6 +2012,7 @@ public class Parser { if( v.type() instanceof TypeFunPtr ctor && ctor.ret() instanceof TypeMem ) throw error("A constructor is only called by new"); if( matchOpx('=','=') ) { + checkPrivateWrite(name); Node value=parseAsgn().keep(); checkPublication(value); _scope.update(v,liftExpr(value,v.type(),false)); @@ -1990,6 +2023,7 @@ public class Parser { throw error("Cannot read uninitialized field '"+name+"'"); char ch=_lexer.matchOperAssign(); if( ch!=0 ) { + checkPrivateWrite(name); Node op=opAssign(ch,value,v.type()); checkPublication(op); _scope.update(v,op); @@ -2000,6 +2034,12 @@ public class Parser { return parsePostfix(value); } + private void checkPrivateWrite(String name) { + Field field=((TypeMemPtr)TYPES.get(_nestedType))._obj.field(name); + if( field!=null && field._one ) + throw error("Cannot reassign shared function '"+name+"'"); + } + // zero/sign extend. "i" is limited to either classic unsigned (min==0) or // classic signed (min=minus-power-of-2); max=power-of-2-minus-1. private Node zsMask(Node val, Type t ) { diff --git a/chapter-escape/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter-escape/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 3c1e9776..f65a822d 100644 --- a/chapter-escape/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter-escape/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -39,7 +39,10 @@ public class ScopeNode extends Node { // Basic block scoping public static class Block extends Kind { } // Function scope - public static class Func extends Kind { } + public static class Func extends Kind { + public final boolean _constructor; + public Func(boolean constructor) { _constructor=constructor; } + } // Struct definition, mapping types to fields public static class Define extends Kind { public Define(TypeMemPtr tmp) { _tmp=tmp; } public final TypeMemPtr _tmp; } // Struct allocation, mapping values to fields @@ -137,15 +140,25 @@ public class ScopeNode extends Node { } - // Allocation fields live in the scope immediately outside the constructor - // block. Nested blocks retain that permission; surrounding bindings do not. + // Fields are writable local values until construction ends, even when the + // published field is final. Ordinary methods and final local variables do + // not inherit that permission. This also decides which loop Phis we need. public boolean canInit(Var v) { - for( int i=_kinds._len-1; i>0; i-- ) - if( _kinds.at(i) instanceof Kind.Alloc ) + for( int i=_kinds._len-1; i>=0; i-- ) { + Kind k=_kinds.at(i); + if( k instanceof Kind.Alloc ) return v._idx >= _kinds.at(i-1)._lexSize && v._idx < _kinds.at(i)._lexSize; + if( k instanceof Kind.Define ) return kind(v)==k; + if( k instanceof Kind.Func fun ) + return fun._constructor && i>0 && _kinds.at(i-1) instanceof Kind.Define def && kind(v)==def; + } return false; } + private boolean loopVar(Var v) { + return !v._final || (canInit(v) && !v.type().isHighOrConst()); + } + public boolean inConstructor() { return _kinds.last() instanceof Kind.Define; } public boolean inAllocation () { return _kinds.last() instanceof Kind.Alloc ; } public boolean inFunction () { return _kinds.last() instanceof Kind.Func ; } @@ -294,7 +307,7 @@ public class ScopeNode extends Node { // Memory is one binding, with the same lazy loop Phi as scalar names. for( int i=1; i FREE = new Ary<>(Field.class); diff --git a/chapter-escape/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java b/chapter-escape/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java new file mode 100644 index 00000000..e91dc384 --- /dev/null +++ b/chapter-escape/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java @@ -0,0 +1,63 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.StoreNode; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FinalConstructionTest { + private static final String LOOP = """ + val step={int x -> x*2+1;}; + struct C { + val x=1; + new C={int n -> + x=0; x=1; + for(int i=0; ix;}; + }; + return new C(arg).get(); + """; + + @Test public void testFinalConstructorLocals() throws java.io.IOException { + var code=new CodeGen(LOOP).driver(CodeGen.Phase.LocalSched); + assertEquals("1",Eval2.eval(code,0)); + assertEquals("15",Eval2.eval(code,3)); + assertEquals("63",Eval2.eval(code,5)); + code._stop.walk(n -> { + if( n instanceof StoreNode st && st._name.equals("x") ) + assertEquals("Final field writes belong after the loop",0,st.cfg0().loopDepth()); + return null; + }); + String[] sources={ + "struct C { val x=1; new C={->x=1; x=2;}; }; return new C().x;", + "struct C { int ~x; new C={int n -> self.x=1; for(int i=0;i for(int i=0;ix=2.5;}; }; return new C().x;", + "struct C { val x=\"a\"; new C={int n -> for(int i=0;ix=new int[2]; x=new int[3];}; }; return new C().x#;" + }; + String[] results={"2","8","4","2.5","98","3"}; + for( int i=0; ival x=1; x=2;}; }; return new C();", + "struct C { val f={->1;}; new C={->f={->2;};}; }; return new C().f();" + }; + for( String src : rejected ) { + try { new CodeGen(src).driver(CodeGen.Phase.TypeCheck); fail(src); } + catch( Parser.ParseException e ) { assertTrue(e.getMessage(),e.getMessage().startsWith("Cannot")); } + } + + var dir=java.nio.file.Path.of("build/objs"); + java.nio.file.Files.createDirectories(dir); + java.nio.file.Files.writeString(dir.resolve("finalConstruction.smp"),"val buildFinal={int arg ->"+LOOP+"};"); + java.nio.file.Files.writeString(dir.resolve("finalConstruction.c"),""" + extern long long buildFinal(long long); + int main(void) { return buildFinal(0)!=1 || buildFinal(3)!=15 || buildFinal(5)!=63; } + """); + TestC.run("build/objs","finalConstruction","",-1); + } +} -- cgit v1.2.3