From ecd82ce8ebbefef223cd934cd87802f4d03c1867 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 26: Construction and Private Memory Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 2 + .../com/seaofnodes/simple/node/CallEndNode.java | 6 ++- .../java/com/seaofnodes/simple/node/CallNode.java | 26 +++++++--- .../com/seaofnodes/simple/node/EscapeMach.java | 12 +++++ .../com/seaofnodes/simple/node/EscapeNode.java | 58 ++++++++++++++++++++++ .../java/com/seaofnodes/simple/node/FunNode.java | 15 +++++- .../java/com/seaofnodes/simple/node/IfNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 50 +++++++++++++++++-- .../com/seaofnodes/simple/node/MemMergeNode.java | 15 ++++++ .../java/com/seaofnodes/simple/node/MemOpNode.java | 4 +- .../java/com/seaofnodes/simple/node/NewNode.java | 11 ++-- .../com/seaofnodes/simple/node/ReturnNode.java | 8 ++- .../java/com/seaofnodes/simple/node/ScopeNode.java | 27 +++++++--- .../java/com/seaofnodes/simple/node/StoreNode.java | 14 +++++- .../com/seaofnodes/simple/node/cpus/arm/arm.java | 3 +- .../seaofnodes/simple/node/cpus/riscv/riscv.java | 3 +- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 3 +- 17 files changed, 225 insertions(+), 34 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/node/EscapeMach.java create mode 100644 src/main/java/com/seaofnodes/simple/node/EscapeNode.java (limited to 'src/main/java/com/seaofnodes/simple/node') diff --git a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index 8399ed09..e6f70c64 100644 --- a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -101,6 +101,7 @@ public class BulkMemPhiNode extends PhiNode { case ConstantNode con -> 0; case MemMergeNode mmm -> missingAlias(mmm); case MemOpNode mem -> unsplit(mem._alias); + case EscapeNode esc -> unsplit(esc._field._alias); case BulkMemPhiNode bulk -> missingAlias(bulk); default -> throw new AssertionError("Unexpected memory input "+n); }; @@ -118,6 +119,7 @@ public class BulkMemPhiNode extends PhiNode { case MemMergeNode mmm -> missingAlias(mmm); case BulkMemPhiNode bulk -> missingAlias(bulk); case MemOpNode mem -> unsplit(mem._alias); + case EscapeNode esc -> unsplit(esc._field._alias); case MemPhiNode phi -> unsplit(phi._alias); default -> { assert use instanceof ReturnNode || use instanceof CallNode || use instanceof ParmNode diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index aa586b17..604bb9da 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -163,7 +163,8 @@ public class CallEndNode extends CFGNode implements MultiNode { } for( int i=0; iTINYBODY.length ) return 0; for( Node use : n._outputs ) { diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index b2708531..21f438da 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -6,6 +6,7 @@ import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.XInt; import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.util.Utils; @@ -16,9 +17,12 @@ public class CallNode extends CFGNode { // Source location for late reported errors public final Parser.Lexer _loc; + // A forward field call records its receiver before its declaration tells + // us whether this is a method or an ordinary function stored in a field. + public String _method; public CallNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; } - public CallNode(CallNode call) { super(call); _loc = call._loc; } + public CallNode(CallNode call) { super(call); _loc = call._loc; _method=call._method; } @Override public String label() { return "Call"; } @@ -90,6 +94,15 @@ public class CallNode extends CFGNode { public Node idealize() { CallEndNode cend = cend(); if( cend==null ) return null; // Still building + if( _method!=null ) { + if( !(arg(2)._type instanceof com.seaofnodes.simple.type.TypeMemPtr ptr) ) return null; + var field=ptr._obj.field(_method); + if( field==null ) return null; + if( !(fptr()._type instanceof TypeFunPtr sig) ) return null; + if( !field._final || CodeGen.CODE.externFunc(sig)!=null ) delDef(2); + _method=null; + return this; + } // Link: call calls target function. Linking makes the target FunNode // point to this Call, and all his Parms point to the call arguments; @@ -97,12 +110,11 @@ public class CallNode extends CFGNode { Node progress = null; if( fptr()._type instanceof TypeFunPtr tfp && tfp.nargs() == nargs() ) { // If fidxs is negative, then infinite unknown functions - long fidxs = tfp.fidxs(); - if( fidxs > 0 ) { + int[] fidxs = tfp.fidxs(); + if( !XInt.isHigh(fidxs) ) { // Wipe out the return which matching in the linker table - // Walk the (63 max) bits and link - for( ; fidxs!=0; fidxs = TypeFunPtr.nextFIDX(fidxs) ) { - int fidx = Long.numberOfTrailingZeros(fidxs); + // Walk the function identities and link each possible callee. + for( int fidx=XInt.next(fidxs,-1); fidx>=0; fidx=XInt.next(fidxs,fidx) ) { TypeFunPtr tfp0 = tfp.makeFrom(fidx); FunNode fun = CodeGen.CODE.link(tfp0); if( fun!=null && !fun._folding && !linked(fun) ) @@ -166,7 +178,7 @@ public class CallNode extends CFGNode { return Parser.error( "Argument #" + i + " isa " + arg(i+2)._type + ", but must be a " + tfp.arg(i), _loc ); } - if( tfp.fidxs() < 0 ) + if( XInt.isHigh(tfp.fidxs()) ) throw Utils.TODO(); // Infinite unknown TFPs? Should be fairly precise CG return null; diff --git a/src/main/java/com/seaofnodes/simple/node/EscapeMach.java b/src/main/java/com/seaofnodes/simple/node/EscapeMach.java new file mode 100644 index 00000000..b6ec04e9 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/EscapeMach.java @@ -0,0 +1,12 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.codegen.*; + +/** Publication orders memory; it needs no runtime instruction or register. */ +public class EscapeMach extends EscapeNode implements MachNode { + public EscapeMach(EscapeNode esc) { super(esc); _inputs.set(3,null); } + @Override public String op() { return label(); } + @Override public RegMask regmap(int i) { return null; } + @Override public RegMask outregmap() { return null; } + @Override public void encoding(Encoding enc) { } +} diff --git a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java new file mode 100644 index 00000000..75ecce64 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -0,0 +1,58 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.*; + +/** Publish one initialized field: {control, public memory, private memory, self}. + * This is an explicit construction boundary, not escape discovery. The next + * chapter will discover which objects and functions unknown code can reach. + */ +public class EscapeNode extends Node { + public Field _field; + private final Parser.Lexer _loc; + public EscapeNode(Parser.Lexer loc, Field field, Node ctrl, Node pub, Node priv, Node self) { + super(ctrl,pub,priv,self); + _field=field; + _loc=loc; + } + public EscapeNode(EscapeNode esc) { super(esc); _field=esc._field; _loc=esc._loc; } + public Node pub() { return in(1); } + public Node priv() { return in(2); } + public Node self() { return in(3); } + @Override public boolean isMem() { return true; } + @Override public String label() { return "Escape_"+_field._fname; } + + private Type value() { + return MemMergeNode.contents(priv(),_field._alias,this); + } + @Override public Type compute() { + if( in(0)._type.isHigh() || priv()._type.isHigh() || pub()._type.isHigh() ) return TypeMem.TOP; + return TypeMem.make(_field._alias,value().meet(MemMergeNode.contents(pub(),_field._alias,this)).join(_field._t)); + } + @Override public Node idealize() { + if( priv() instanceof MemMergeNode merge ) { + setDef(2,merge.alias(_field._alias)); + return this; + } + if( pub() instanceof MemMergeNode merge ) { + setDef(1,merge.alias(_field._alias)); + return this; + } + return null; + } + @Override public Parser.ParseException err() { + if( in(0)._type.isHigh() ) return null; + if( value()==Type.BOTTOM ) { + String name = self()._type instanceof TypeMemPtr p ? p._obj._name : "Object"; + return Parser.error("'"+name+"' is not fully initialized, field '"+_field._fname+"' needs to be set in a constructor",_loc); + } + return null; + } + @Override boolean _upgradeType(java.util.HashMap types) { + Field next = (Field)_field.upgradeType(types); + if( next==_field ) return false; + unlock(); _field=next; return true; + } + @Override public boolean eq(Node n) { return _field==((EscapeNode)n)._field; } + @Override int hash() { return _field.hashCode(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/FunNode.java b/src/main/java/com/seaofnodes/simple/node/FunNode.java index 1ba57e85..2850ba92 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.codegen.RegMask; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.type.TypeTuple; import com.seaofnodes.simple.util.SB; @@ -13,6 +14,9 @@ import java.util.BitSet; import static com.seaofnodes.simple.codegen.CodeGen.CODE; public class FunNode extends RegionNode { + // Generated allocation/initializer entry points cannot be called by users. + public boolean _constructor; + // When set true, this Call/CallEnd/Fun/Return is being trivially inlined boolean _folding; @@ -29,6 +33,7 @@ public class FunNode extends RegionNode { if( fun!=null ) { _sig = fun.sig(); _name = fun._name; + _constructor = fun._constructor; } else { _sig = TypeFunPtr.BOT; _name = ""; @@ -73,6 +78,13 @@ public class FunNode extends RegionNode { // Signature can improve over time public TypeFunPtr sig() { return _sig; } + // Hidden initializer captures are discovered while parsing its body, + // before any call or function address has been made for this function. + public void addParseArg(Type type) { + Type[] args=java.util.Arrays.copyOf(_sig._sig,_sig.nargs()+1); + args[args.length-1]=type; + _sig=TypeFunPtr.make((byte)2,false,args,_sig.ret(),_sig.fidxs()); + } public void setSig( TypeFunPtr sig ) { assert sig.isa(_sig); if( _sig != sig ) { @@ -114,7 +126,8 @@ public class FunNode extends RegionNode { } // Upgrade inferred or user-written return type to actual - if( _ret!=null && _ret._type instanceof TypeTuple tt && tt.ret() != _sig.ret() ) { + if( _ret!=null && _ret._type instanceof TypeTuple tt && + !(tt.ret() instanceof TypeMem) && tt.ret() != _sig.ret() ) { setSig(_sig.makeFrom(tt.ret())); return this; } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 3f21417e..f1b76dc2 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -46,7 +46,7 @@ public class IfNode extends CFGNode implements MultiNode { // If constant is 0 then false branch is reachable // Else true branch is reachable if( t.isConstant() ) - return (t==Type.NIL || t==TypeInteger.ZERO || (t instanceof TypeFunPtr tfp && tfp._fidxs==0) ) ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; + return (t==Type.NIL || t==TypeInteger.ZERO || (t instanceof TypeFunPtr tfp && tfp._fidxs==com.seaofnodes.simple.type.XInt.EMPTY) ) ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; // If adding a zero makes a difference, the predicate must not have a zero/null if( !t.makeZero().isa(t) ) return TypeTuple.IF_TRUE; diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 24a2f9b8..b9dd2af6 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -13,6 +13,7 @@ import java.util.BitSet; * in chapter 10 this means Struct fields. */ public class LoadNode extends MemOpNode { + private final boolean _private; /** * Load a value from a ptr.field. @@ -23,9 +24,13 @@ public class LoadNode extends MemOpNode { * @param off The offset inside the struct base */ public LoadNode(Parser.Lexer loc, String name, int alias, Node mem, Node ptr, Node off) { + this(loc,name,alias,mem,ptr,off,false); + } + public LoadNode(Parser.Lexer loc, String name, int alias, Node mem, Node ptr, Node off, boolean priv) { // The field declaration will supply storage width once the receiver // is known. A parser guess must not bound the value of this Load. super(loc, name, alias, true, Type.BOTTOM, mem, ptr, off); + _private=priv; } @Override boolean canDrop(MemOpNode other, Node dep) { @@ -62,9 +67,18 @@ public class LoadNode extends MemOpNode { if( ptr.nullable() ) return Type.BOTTOM; Field field = ptr._obj.field(_name); if( field==null ) return TypeScalar.BOT; + if( field._t instanceof TypeFunPtr ctor && ctor.ret() instanceof TypeMem ) return TypeScalar.BOT; Type t = field._t; if( t instanceof TypeConAry ary ) t=ary.elem(); if( _alias!=1 ) t=t.join(MemMergeNode.contents(mem(),_alias,this)); + // An unknown helper result does not mean the field is unwritten. + // Keep its declared bound until private memory proves otherwise; + // this Load can be forwarded into an ordinary typed value Phi. + if( uninitialized() ) t=Type.BOTTOM; + if( m instanceof TypeMem pm && pm._t instanceof TypeStruct shape ) { + Field value = shape.field(_name); + t = value==null ? Type.BOTTOM : value._t; + } if( ptr.isFinal() ) t=t.makeRO(); return t==Type.TOP ? TypeScalar.TOP : t==Type.BOTTOM ? TypeScalar.BOT : t; } @@ -87,6 +101,9 @@ public class LoadNode extends MemOpNode { } } if( _alias==1 ) return null; + // A required field has no value yet. In particular, do not turn a + // read of its calloc bytes into a legal null/zero value. + if( uninitialized() ) return null; if( mem() instanceof CastNode cast ) { setDef(1,cast.in(1)); @@ -146,6 +163,24 @@ public class LoadNode extends MemOpNode { return null; } + private boolean uninitialized() { + if( !_private || _alias==1 ) return false; + Node mem=mem(); + if( mem instanceof MemMergeNode merge ) mem=merge.alias(_alias); + return mem._type instanceof TypeMem m && + ((m._alias==_alias && m._t==Type.BOTTOM) || + (m._t instanceof TypeStruct s && s.field(_name)!=null && s.field(_name)._t==Type.BOTTOM)); + } + + @Override public Parser.ParseException err() { + if( ptr()._type instanceof TypeMemPtr ptr ) { + Field f=ptr._obj.field(_name); + if( f!=null && f._t instanceof TypeFunPtr ctor && ctor.ret() instanceof TypeMem ) + return Parser.error("A constructor is only called by new",_loc); + } + return uninitialized() ? Parser.error("Cannot read uninitialized field '"+_name+"'",_loc) : super.err(); + } + // Load a flavored zero from a New private Node zero(NewNode nnn) { TypeStruct ts = nnn._ptr._obj; @@ -165,6 +200,9 @@ public class LoadNode extends MemOpNode { switch( mem ) { case MemMergeNode merge: mem=merge.alias(_alias); break; case CastNode cast: mem=cast.in(1); break; + case EscapeNode esc: + mem = ptr==address(esc.self()) ? esc.priv() : esc.pub(); + break; case StoreNode st: // A symbolic Store may write this field. Wait for its alias; // skipping it can make a compound assignment read the old value. @@ -177,7 +215,11 @@ public class LoadNode extends MemOpNode { break; case ProjNode proj: if( !(proj.in(0) instanceof NewNode nnn) ) return null; - if( ptr instanceof ProjNode p && p.in(0)==nnn ) return nnn; + if( ptr instanceof ProjNode p && p.in(0)==nnn ) { + if( nnn.mem()==null && proj._type instanceof TypeMem m && + m._t instanceof TypeStruct shape && shape.field(_name)._t==Type.BOTTOM ) return null; + return nnn; + } if( !(ptr instanceof ProjNode p && p.in(0) instanceof NewNode) ) return null; mem=nnn.mem(); // Distinct allocations cannot overlap. break; @@ -222,7 +264,7 @@ public class LoadNode extends MemOpNode { } return folded(win).peephole(); } - LoadNode ld=new LoadNode(_loc,_name,_alias,mem,ptr,off()); + LoadNode ld=new LoadNode(_loc,_name,_alias,mem,ptr,off(),_private); ld.setDef(0,in(0)); return ld.peephole(); } @@ -255,11 +297,13 @@ public class LoadNode extends MemOpNode { // Read-Only is a deep property, and cannot be cast-away private Node castRO(Node rez) { - if( (ptr()._type.isFinal() || _declaredType.isFinal()) && !rez._type.isFinal() ) + if( (ptr()._type.isFinal() || (_declaredType instanceof TypeMemPtr p && p._ro)) && !rez._type.isFinal() ) return new ReadOnlyNode(rez).peephole(); return rez; } + @Override public boolean eq(Node n) { return _private==((LoadNode)n)._private && super.eq(n); } + // When a load bypasses a store, the store might truncate bits - and the // load will need to zero/sign-extend. private Node extend(Node val) { diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 7a329117..e405d152 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -42,6 +42,10 @@ public class MemMergeNode extends Node { if( mem instanceof CastNode cast ) return contents(cast.in(1),alias,dep); if( mem instanceof MemMergeNode merge ) return contents(merge.alias(alias),alias,dep); + if( mem._type instanceof TypeMem mt && mt._t instanceof TypeStruct shape ) { + int index = shape.findAlias(alias); + return index==-1 ? Type.BOTTOM : shape._fields[index]._t; + } if( mem instanceof ProjNode proj && proj.in(0) instanceof NewNode nnn ) { assert proj._idx==1 && nnn.field(alias)!=null; dep.addDep(nnn); @@ -69,6 +73,17 @@ public class MemMergeNode extends Node { @Override public Type compute() { + if( in(1)!=null && in(1)._type instanceof TypeMem base && base._t instanceof TypeStruct shape ) { + // At a helper boundary, package the independent field slices for + // the call result. Constructor loops themselves carry local values. + Field[] fields=shape._fields.clone(); + for( int i=0; i