diff options
Diffstat (limited to 'src/main/java/com/seaofnodes')
16 files changed, 236 insertions, 64 deletions
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 45c429d8..145feb15 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -270,7 +270,7 @@ public class Parser { _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,con(TypeMem.BOT)).peephole()); + _scope.mem(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,new ProjNode(_code._start,1,ScopeNode.MEM0).peephole()).peephole()); // All args, "as-if" called externally for( int i=0; i<ids.length; i++ ) { Type t = sig.arg(i); @@ -1103,7 +1103,7 @@ public class Parser { fun._name=shape._name+".<new>"; fun._constructor=true; _code.link(fun); Node rpc=new ParmNode("$rpc",0,TypeRPC.BOT,fun,con(TypeRPC.BOT)).init(); - Node pub=new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).init(); + Node pub=new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,new ProjNode(_code._start,1,ScopeNode.MEM0).peephole()).init(); Node[] args=new Node[nargs+2]; for( int i=0; i<nargs; i++ ) args[i+2]=new ParmNode("arg"+i,i+2,types[i],fun,con(types[i])).init(); Node alloc=new NewNode(ptr,fun,null,off(shape," len")).init(); diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index a49299e1..d3895b08 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -101,6 +101,7 @@ public class CodeGen { _callingConv = null; _start = new StartNode(arg); _stop = new StopNode(src); + _start.setDef(1,_stop); _src = src; _arg = arg; _iter = new IterPeeps(workListSeed); @@ -145,6 +146,8 @@ public class CodeGen { // Start and stop; end points of the generated IR public StartNode _start; public StopNode _stop; + // Native calls are exposure roots even on paths with no live Return. + public final Ary<CallNode> _calls = new Ary<>(CallNode.class); // Global Value Numbering. Hash over opcode and inputs; hits in this table // are structurally equal. diff --git a/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java index 9e3b3e32..4adb2fa4 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java +++ b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java @@ -10,6 +10,10 @@ abstract class FinalizeIR { static void run(CodeGen code) { fieldSizes(code); code._iter.iterate(code); + // The external-world cycle is an analysis edge, not runtime control. + // Freeze its facts before replacing call edges with emission roots. + code._stop.close(); + code._start.close(); removeCallGraph(code); Arrays.sort(code._stop._inputs._es,0,code._stop.nIns(),(x,y) -> x._nid - y._nid); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 82646a25..3c34b44c 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -29,17 +29,9 @@ abstract public class Opto { Ary<Type> oldTypes = new Ary<>(Type.class); // Used for asserts only resetToTop(code,oldTypes); - // The whole-world assumption: we use it if compiling `main`, and not otherwise. - // The assumption is no unknown callers into functions: - // - during or past an Opto phase (but not before, since parse through - // pessimistic must assume somebody calls an unknown function which - // calls everybody). - // - Have a `main` to start tracing the Call Graph from - // - - True for most test cases - // - - False for lacking a main; we assume the linker will call all public functions - - // True if we can make the "whole world" assumption, which means we are - // compiling the program entry: `main`. + // Main seeds a whole program. Without main, named exported functions + // seed discovery. Either way, escaping addresses can add more unknown + // callers as Start and Stop reach their shared fixed point. boolean wholeWorld = code.link(code._main) != null; @@ -54,6 +46,9 @@ abstract public class Opto { resolveNumericModes(code); if( !code._iter._work.isEmpty() ) sccp(code, oldTypes); + ProjNode startMem=code._start.proj(1); + if( startMem!=null ) { startMem.unkeep(); code.add(startMem); } + // After SCCP add everything changed to the worklist and see if // peepholes can make more progress. moveChangesToWorklist(code, oldTypes); @@ -79,6 +74,8 @@ abstract public class Opto { // called unless they get linked (hence go dead and can be removed). If // not wholeWorld, keep only public methods (and not the std lib). private static void unlinkStart(boolean wholeWorld, CodeGen code) { + ProjNode startMem=code._start.proj(1); + if( startMem!=null ) startMem.keep(); for( FunNode fun : code._linker ) { if( fun != null && !fun.isDead() && !funIsPublic(code,wholeWorld,fun) ) { assert fun.in(1)==code._start; // Start always in slot 1 @@ -94,15 +91,15 @@ abstract public class Opto { // Function is public (callable from Start directly). // - Always true for main - // - True for function addresses used as values // - Otherwise false for stdlib or anonymous functions // - Named functions use `!wholeWorld` private static boolean funIsPublic( CodeGen code, boolean wholeWorld, FunNode fun ) { // Always true for main if( fun.sig().fidx() == code._main.fidx() ) return true; - // No escape analysis yet: a surviving address may be called from outside. + // Hidden allocation helpers are never external entry points. if( fun._constructor ) return false; - if( fun.hasPtr() ) return true; + // Taking an address does not expose it. Stop discovers escapes from + // reachable returns and memory; linkStart restores only those callers. // Never true for stdlib or anonymous functions if( fun._name == null || fun._name.startsWith("sys.") ) return false; @@ -114,8 +111,11 @@ abstract public class Opto { // into a Call, link the Call and Fun. private static void linkCG(CodeGen code, TypeFunPtr tfp, CallNode call) { if( tfp.nargs() != call.nargs() ) return; // Error calls hit this + if( XInt.isHigh(tfp.fidxs()) ) return; for( int fidx=XInt.next(tfp.fidxs(),-1); fidx>=0; fidx=XInt.next(tfp.fidxs(),fidx) ) { - FunNode fun = code.link(fidx); + // A disconnected function can still be revived by a discovered + // call or escaping address. Do not clean the linker entry here. + FunNode fun = code._link(fidx); // null here means an external function; i.e. this Call // calls to an outside library and all its arguments escape. if( fun != null && !call.linked(fun) ) { @@ -126,6 +126,24 @@ abstract public class Opto { } } + // Exposure is a call edge from the unknown world. Restore conservative + // declared arguments, never the narrower values inferred from known calls. + private static void linkStart(CodeGen code, TypeTuple state) { + for( FunNode fun : code._linker ) { + if( fun==null || fun.isDead() || fun._constructor || fun.unknownCallers() || + !XInt.bit(state.mem()._escFs,fun.sig().fidx()) ) continue; + fun.insertDef(1,code._start); + if( !code._stop._inputs.contains(fun.ret()) ) code._stop.addDef(fun.ret()); + code.add(fun); code.add(code._stop); + for( Node n : fun._outputs ) + if( n instanceof ParmNode parm ) { + Node def=parm._idx==1 ? code._start.proj(1) : new ConstantNode(parm._declaredType).peephole(); + parm.insertDef(1,def); + code.add(parm); + } + } + } + // The core SCCP algorithm private static void sccp( CodeGen code, Ary<Type> oldTypes ) { // Iter workList is empty at this point @@ -137,9 +155,9 @@ abstract public class Opto { count++; Type oval = n._type, nval = n.compute(); if( oval == nval ) continue; - assert oval.isa(nval); // Types start high and always fall - Type pesiVal = oldTypes.at(n._nid); - assert nval.isa(pesiVal); // Never fall worse than the pessimistic pass + assert oval.isa(nval) : n.label()+"#"+n._nid+" old="+oval+" new="+nval; // Types start high and always fall + Type pesiVal = oldTypes.atX(n._nid); + assert pesiVal==null || nval.isa(pesiVal) : n.label()+"#"+n._nid+" pessimistic="+pesiVal+" new="+nval; // Never fall worse than the pessimistic pass n._type = nval; // If a TFP adds a new function input to a call, link to the new Fun @@ -153,6 +171,8 @@ abstract public class Opto { if( n instanceof CallNode call && oval.isHigh() && !nval.isHigh() && call.fptr()._type instanceof TypeFunPtr ) linkCG(code,call.tfp(),call); + if( n instanceof StartNode && nval instanceof TypeTuple tt ) linkStart(code,tt); + // Since n._type changed, visit all output neighbors code._iter.addAll(n._outputs); n.moveDepsToWorklist(code._iter); @@ -165,7 +185,8 @@ abstract public class Opto { private static boolean check(CodeGen code) { code._start.walk( x -> { Type xval = x.compute(); - assert xval == x._type || (x._type.isa( xval ) && code._iter._work.on( x )); + assert xval == x._type || (x._type.isa( xval ) && code._iter._work.on( x )) + : x.label()+"#"+x._nid+" old="+x._type+" new="+xval+" queued="+code._iter._work.on(x); return null; }); return true; diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 604bb9da..86c6c79d 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -69,7 +69,29 @@ public class CallEndNode extends CFGNode implements MultiNode { ret = ti.same_but_slightly_wider_than(TypeInteger.BOT).join(tfp.ret()); } } - return TypeTuple.make(call._type,TypeMem.BOT,ret); + TypeMem mem=TypeMem.TOP; + for( int i=1; i<nIns(); i++ ) { + Type state=in(i)._type; + if( state instanceof TypeTuple tt ) mem=(TypeMem)mem.meet(tt._types[1]); + else if( !state.isHigh() ) mem=TypeMem.BOT; + } + boolean known=false, external=false; + if( ftype instanceof TypeFunPtr tfp && !XInt.isHigh(tfp.fidxs()) ) { + int locals=0; + for( int fidx=XInt.next(tfp.fidxs(),-1); fidx>=0; fidx=XInt.next(tfp.fidxs(),fidx) ) { + if( CodeGen.CODE.externFunc(tfp.makeFrom(fidx))!=null ) external=true; + else locals++; + } + known=locals==nIns()-1; + } + if( external || (ftype instanceof TypeFunPtr tfp && XInt.isHigh(tfp.fidxs())) ) { + // Unknown code may retain arguments and all addresses already + // exposed to it. Heap values are arbitrary after this call; + // exposure itself still has a useful finite summary. + mem=(TypeMem)mem.meet(call.exposed(this)); + } else if( !known && (CodeGen.CODE._phase.ordinal()<CodeGen.Phase.Opto.ordinal() || + CodeGen.CODE._phase.ordinal()>CodeGen.Phase.FinalizeIR.ordinal()) ) mem=TypeMem.BOT; + return TypeTuple.make(call._type,mem,ret); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index 21f438da..44ad8e83 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -8,6 +8,7 @@ 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.type.TypeMem; import com.seaofnodes.simple.util.Utils; /** @@ -21,7 +22,7 @@ public class CallNode extends CFGNode { // 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(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; CodeGen.CODE._calls.add(this); } public CallNode(CallNode call) { super(call); _loc = call._loc; _method=call._method; } @Override public String label() { return "Call"; } @@ -58,7 +59,25 @@ public class CallNode extends CFGNode { public TypeFunPtr tfp() { return (TypeFunPtr)fptr()._type; } // Call is to an externally supplied code - public boolean external() { return false; } + public boolean external() { + if( !(fptr()._type instanceof TypeFunPtr tfp) ) return false; + if( XInt.isHigh(tfp.fidxs()) ) return true; + for( int fidx=XInt.next(tfp.fidxs(),-1); fidx>=0; fidx=XInt.next(tfp.fidxs(),fidx) ) + if( CodeGen.CODE.externFunc(tfp.makeFrom(fidx))!=null ) return true; + return false; + } + + // Unknown code can retain arguments without ever returning. Stop uses + // this summary directly as well as through the call's memory result. + TypeMem exposed(Node dep) { + dep.addDepForwards(this); + dep.addDepForwards(fptr()); + if( _type!=Type.CONTROL || !external() ) return TypeMem.START; + Type input=dep.addDepForwards(mem())._type; + TypeMem escaped=input instanceof TypeMem m ? m : input.isHigh() ? TypeMem.TOP : TypeMem.BOT; + for( int i=2; i<nIns()-1; i++ ) escaped=escaped.escapes(dep.addDepForwards(arg(i))._type); + return escaped.withContents(1,Type.BOTTOM); + } // Find the Call End from the Call diff --git a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java index 75ecce64..849c552f 100644 --- a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -4,8 +4,8 @@ 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. + * This explicit construction boundary publishes a completed field. Stop and + * Start separately discover whether unknown code can reach that field. */ public class EscapeNode extends Node { public Field _field; @@ -27,7 +27,9 @@ public class EscapeNode extends Node { } @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)); + Type t=value().meet(MemMergeNode.contents(pub(),_field._alias,this)).join(_field._t); + TypeMem prior=pub()._type instanceof TypeMem m ? m : TypeMem.BOT; + return prior.withContents(_field._alias,t).escapes(value()); } @Override public Node idealize() { if( priv() instanceof MemMergeNode merge ) { diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index e405d152..a43667ff 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -84,10 +84,14 @@ public class MemMergeNode extends Node { } return TypeMem.makePrivate(TypeStruct.make(shape._name,shape._open,fields)); } - for( Node n : _inputs ) - if( n != null && !n._type.isHigh() ) - return TypeMem.BOT; - return TypeMem.TOP; + TypeMem mem=in(1)==null ? TypeMem.START : in(1)._type instanceof TypeMem m ? m : + in(1)._type.isHigh() ? TypeMem.TOP : TypeMem.BOT; + // Only memory visible outside this graph contributes to the external + // summary. Newly exposed aliases feed back through Start on the next + // SCCP visit, including chains of pointers stored in other objects. + for( int i=2; i<nIns(); i++ ) + if( in(i)!=null && XInt.bit(mem._escAs,i) ) mem=mem.escapes(in(i)._type); + return mem; } @Override public Node idealize() { diff --git a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java index ba53cfd8..bca85e0d 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -25,10 +25,13 @@ public class MemPhiNode extends PhiNode { return (region()._type==Type.XCONTROL || region()._type==Type.TOP) ? TypeMem.TOP : _type; if( r.inProgress() ) return r instanceof LoopNode ? TypeMem.make(_alias,Type.BOTTOM) : TypeMem.BOT; Type t = Type.TOP; + TypeMem escapes=TypeMem.START; for( int i=1; i<nIns(); i++ ) - if( addDep(r.in(i))._type!=Type.XCONTROL && r.in(i)._type!=Type.TOP ) + if( addDep(r.in(i))._type!=Type.XCONTROL && r.in(i)._type!=Type.TOP ) { t = t.meet(MemMergeNode.contents(in(i),_alias,this)); - return TypeMem.make(_alias,t); + escapes=escapes.escapes(in(i)._type); + } + return escapes.withContents(_alias,t); } @Override public Node idealize() { diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 52fe5704..37f049e5 100644 --- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -10,7 +10,7 @@ import com.seaofnodes.simple.type.TypeMemPtr; public class ParmNode extends PhiNode { // Argument indices are mapped one-to-one on CallNode inputs - private Type _declaredType; + public Type _declaredType; public final int _idx; // Argument index public ParmNode(String label, int idx, Type declaredType, Node... inputs) { @@ -39,7 +39,15 @@ public class ParmNode extends PhiNode { @Override public Type compute() { - Type t = inProgress() ? _declaredType : super.compute().join(_declaredType); + Type t; + if( _idx==1 && region() instanceof FunNode fun ) { + // Even an unknown caller supplies Start's discovered escape set. + // Its heap contents are arbitrary, but its addresses are not. + t=Type.TOP; + for( int i=1; i<nIns(); i++ ) + if( !addDep(fun.in(i))._type.isHigh() ) t=t.meet(in(i)._type); + t=t.join(_declaredType); + } else t = inProgress() ? _declaredType : super.compute().join(_declaredType); // Recursion is a loop in disguise. A Parm merges the first argument // with those from recursive calls, just as a loop Phi merges its entry // and backedge. Use the widening rule in PhiNode.compute here too. diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index ce3feef2..ecfd2cde 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -45,7 +45,7 @@ public class ReturnNode extends CFGNode { public Type compute() { if( inProgress () ) return TypeTuple.RET; // In progress // Inlining can delete the entry while callers still use this return. - return TypeTuple.make(ctrl()._type,TypeMem.BOT,expr()._type); + return TypeTuple.make(ctrl()._type,mem()._type,expr()._type); } @Override public Node idealize() { diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index e13d35c0..2c913b88 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,18 +3,29 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; -import java.util.HashSet; -import static com.seaofnodes.simple.util.Utils.TODO; -/** Start supplies control, whole memory, and the argument, in that order. */ +/** Unknown callers: control, exposed memory, and the entry argument. + * Stop feeds discovered addresses back here during SCCP. This closes the + * cycle between known code and unknown callers without a runtime loop. + */ public class StartNode extends LoopNode implements MultiNode { final Type _arg; + private TypeTuple _closed; public StartNode(Type arg) { super(null,null); _arg = arg; _type = compute(); } - public StartNode(StartNode start) { super(start); _arg = start==null ? null : start._arg; } + public StartNode(StartNode start) { super(start); _arg = start==null ? null : start._arg; _closed=start==null ? null : start._closed; } + + public void close() { + _closed=(TypeTuple)_type; + ProjNode mem=proj(1); + if( mem!=null ) mem.subsume(new ConstantNode(mem._type).peephole()); + // Stop is a graph root even after the analysis feedback edge is gone. + Node stop=in(1).keep(); + setDef(1,null); + stop.unkeep(); + } @Override public String label() { return "Start"; } @@ -37,7 +48,16 @@ public class StartNode extends LoopNode implements MultiNode { @Override public TypeTuple compute() { - return TypeTuple.make(Type.CONTROL,TypeMem.BOT,_arg); + if( _closed!=null ) return _closed; + TypeMem mem = in(1)==null || CodeGen.CODE._phase==null || + CodeGen.CODE._phase.ordinal()<CodeGen.Phase.Opto.ordinal() ? TypeMem.BOT : + in(1)._type instanceof TypeMem m ? m : in(1)._type.isHigh() ? TypeMem.START : TypeMem.BOT; + return TypeTuple.make(Type.CONTROL,mem,_arg); + } + + public boolean escapedFIDX(int fidx) { + if( !(_type instanceof TypeTuple tt) ) return !_type.isHigh(); + return XInt.bit(tt.mem()._escFs,fidx); } @Override public Node idealize() { return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 9f7a925b..83acc8e3 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -2,19 +2,22 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.util.Utils; public class StopNode extends CFGNode { public final String _src; + private Type _closed; + public void close() { _closed=_type; } public StopNode(String src) { super(); _src = src; _type = compute(); } - public StopNode(StopNode stop) { super(stop); _src = stop==null ? null : stop._src; } + public StopNode(StopNode stop) { super(stop); _src = stop==null ? null : stop._src; _closed=stop==null ? null : stop._closed; } @Override public String label() { @@ -53,7 +56,24 @@ public class StopNode extends CFGNode { @Override public Type compute() { - return Type.BOTTOM; + if( _closed!=null ) return _closed; + CodeGen code=CodeGen.CODE; + if( code._phase==null || code._phase.ordinal()<CodeGen.Phase.Opto.ordinal() ) return TypeMem.BOT; + TypeMem mem=TypeMem.START; + for( Node n : _inputs ) { + ReturnNode ret=(ReturnNode)n; + if( !ret.fun().unknownCallers() ) continue; + // An external caller already holds its arguments. Writes through + // those pointers are visible even if this function returns a scalar. + for( Node use : ret.fun()._outputs ) + if( use instanceof ParmNode p && p._idx>=2 ) + mem=mem.escapes(addDepForwards(p)._type); + if( !(ret._type instanceof TypeTuple tt) || tt._types[0].isHigh() ) continue; + mem=mem.escapes(tt.ret()).escapes(tt._types[1]); + } + for( CallNode call : code._calls ) + if( !call.isDead() ) mem=mem.escapes(call.exposed(this)); + return mem; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index caba7bdd..06ff51fc 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -48,10 +48,11 @@ public class StoreNode extends MemOpNode { // Initializing Stores are emitted at helper exits for a fresh object. // They replace this private field; Escape later joins it with public // memory. Keep an unwritten BOTTOM visible to the completion check. - if( _init ) return TypeMem.make(_alias,val); + if( _init ) return TypeMem.make(_alias,val,XInt.EMPTY,XInt.EMPTY).escapes(val); assert !_declaredType.isFRef(); Type t = val.join(_declaredType).meet(MemMergeNode.contents(mem(),_alias,this)); - return TypeMem.make(_alias,t); + TypeMem prior=mem()._type instanceof TypeMem m ? m : mem()._type.isHigh() ? TypeMem.TOP : TypeMem.BOT; + return prior.withContents(_alias,t).escapes(val); } @Override diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 5539e1cf..cc287922 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -20,12 +20,18 @@ public class TypeMem extends Type { public int _alias; public Type _t; // Scalar public contents, or private field values. + // Addresses reachable through this memory. EMPTY means no exposed address; + // FULL means any address. These discovery sets join by union, independently + // of the field contents. They use the same interned sets as function types. + public int[] _escFs, _escAs; + private static final Ary<TypeMem> FREE = new Ary<>(TypeMem.class); - private TypeMem(int alias, Type t) { super(TMEM); init(alias,t); } - private TypeMem init(int alias, Type t) { + private TypeMem(int alias, Type t, int[] fs, int[] as) { super(TMEM); init(alias,t,fs,as); } + private TypeMem init(int alias, Type t, int[] fs, int[] as) { assert alias>1 || (t==null || t==Type.TOP || t==Type.BOTTOM || t instanceof TypeStruct); _alias = alias; _t = t; + _escFs=fs; _escAs=as; return this; } @Override TypeMem free(Type t) { @@ -38,11 +44,14 @@ public class TypeMem extends Type { } @Override boolean isFree() { return _alias == -99; } - public static TypeMem malloc(int alias, Type t) { - return FREE.isEmpty() ? new TypeMem(alias,t) : FREE.pop().init(alias,t); + public static TypeMem malloc(int alias, Type t, int[] fs, int[] as) { + return FREE.isEmpty() ? new TypeMem(alias,t,fs,as) : FREE.pop().init(alias,t,fs,as); } public static TypeMem make(int alias, Type t) { - TypeMem f = malloc(alias,t); + return make(alias,t,t.isHigh() ? XInt.EMPTY : XInt.FULL,t.isHigh() ? XInt.EMPTY : XInt.FULL); + } + public static TypeMem make(int alias, Type t, int[] fs, int[] as) { + TypeMem f = malloc(alias,t,fs,as); TypeMem f2 = f.intern(); if( f2==f ) return f; return VISIT.isEmpty() ? f2.free(f) : f2.delayFree(f); @@ -50,7 +59,36 @@ public class TypeMem extends Type { // Private memory describes one allocation. It is passed explicitly to // initializers; it never joins the public heap until EscapeNode. - public static TypeMem makePrivate(TypeStruct shape) { return make(1,shape); } + public static TypeMem makePrivate(TypeStruct shape) { + return make(1,shape,XInt.EMPTY,XInt.EMPTY).escapes(shape); + } + + public TypeMem escapes(Type value) { + int[] fs=_escFs, as=_escAs; + if( value instanceof TypeMem m ) { + fs=XInt.meet(fs,m._escFs); as=XInt.meet(as,m._escAs); + } else if( value instanceof TypeFunPtr f ) { + fs=XInt.meet(fs,f.fidxs()); + } else if( value instanceof TypeMemPtr p ) { + return escapes(p._obj); + } else if( value instanceof TypeStruct s ) { + if( s._open && !s.isAry() ) return make(_alias,_t,XInt.FULL,XInt.FULL); + for( Field f : s._fields ) { + // A constructor has a hidden memory result, never a public + // callable address. Constant methods need no memory Store. + if( f._t instanceof TypeFunPtr fn && fn.ret() instanceof TypeMem ) continue; + as=XInt.make(as,f._alias); + if( f._one && f._t instanceof TypeFunPtr fn ) fs=XInt.meet(fs,fn.fidxs()); + } + } else if( value==Type.BOTTOM || value==TypeScalar.BOT ) { + fs=XInt.FULL; as=XInt.FULL; + } + return make(_alias,_t,fs,as); + } + + public TypeMem withContents(int alias, Type contents) { + return make(alias,contents,_escFs,_escAs); + } public static TypeStruct empty(TypeStruct shape) { Field[] fields = new Field[shape._fields.length]; @@ -71,9 +109,11 @@ public class TypeMem extends Type { public static final TypeMem TOP = make(1, Type.TOP ); public static final TypeMem BOT = make(1, Type.BOTTOM); + public static final TypeMem START = make(1,Type.BOTTOM,XInt.EMPTY,XInt.EMPTY); public static void gather(ArrayList<Type> ts) { ts.add(make(2,Type.NIL)); ts.add(make(2,TypeInteger.ZERO)); ts.add(BOT); + ts.add(START); ts.add(make(2,TypeInteger.ZERO,XInt.make(3),XInt.make(5))); ts.add(makePrivate(TypeStruct.TEST)); ts.add(makePrivate(empty(TypeStruct.TEST))); } @@ -86,19 +126,20 @@ public class TypeMem extends Type { if( that==BOT ) return BOT; // Different slices lose their alias and contents together. Their // scalar meet alone cannot describe the unsplit bulk memory. - if( _alias!=that._alias ) return BOT; - int alias = _alias; - Type mt = _t.meet(that._t); - return make(alias,mt); + int alias = _alias==that._alias ? _alias : + (_alias==1 && _t==Type.TOP) ? that._alias : + (that._alias==1 && that._t==Type.TOP) ? _alias : 1; + Type mt = _alias==that._alias || alias!=1 ? _t.meet(that._t) : Type.BOTTOM; + return make(alias,mt,XInt.meet(_escFs,that._escFs),XInt.meet(_escAs,that._escAs)); } @Override - Type xdual() { return _t._dual==_t ? this : malloc(_alias,_t.dual()); } + Type xdual() { return malloc(_alias,_t.dual(),XInt.dual(_escFs),XInt.dual(_escAs)); } @Override TypeMem rdual() { if( _dual!=null ) return dual(); assert !_terned; - TypeMem d = malloc(_alias,null); + TypeMem d = malloc(_alias,null,XInt.dual(_escFs),XInt.dual(_escAs)); (_dual = d)._dual = this; // Cross link duals d._t = _t._terned ? _t.dual() : _t.rdual(); return d; @@ -110,16 +151,16 @@ public class TypeMem extends Type { @Override boolean _isGLB(boolean mem) { return _t instanceof TypeStruct s ? s.isGLB2() : _t._isGLB(true); } @Override public Type _glb(boolean mem) { return make(_alias,_t instanceof TypeStruct s ? s.glb2() : _t._glb(true)); } - @Override int hash() { return 9876543 + _alias + _t.hashCode(); } + @Override int hash() { return 9876543 + _alias + _t.hashCode() + XInt.hash(_escFs) + XInt.hash(_escAs); } @Override boolean eq(Type t) { TypeMem that = (TypeMem) t; // Invariant - return _alias == that._alias && _t == that._t; + return _alias == that._alias && _t == that._t && _escFs==that._escFs && _escAs==that._escAs; } @Override boolean cycle_eq(Type t) { TypeMem that = (TypeMem) t; // Invariant - return _alias == that._alias && _t.cycle_eq(that._t); + return _alias == that._alias && _escFs==that._escFs && _escAs==that._escAs && _t.cycle_eq(that._t); } @Override int nkids() { return 1; } @@ -131,7 +172,9 @@ public class TypeMem extends Type { if( this==TOP ) return sb.p("MemTop"); sb.p("#"); if( _alias==0 ) return sb.p(_t._type==TTOP ? "TOP" : "BOT"); - return _t.print(sb.p(_alias).p(":"),visit,html); + _t.print(sb.p(_alias).p(":"),visit,html); + XInt.str(sb.p(" f="),_escFs); + return XInt.str(sb.p(" a="),_escAs); } @Override public String str() { return toString(); } @@ -149,6 +192,6 @@ public class TypeMem extends Type { } return makePrivate(TypeStruct.make(shape._name,shape._open,fields)); } - return make(_alias,_t._upgradeType(types)); + return make(_alias,_t._upgradeType(types),_escFs,_escAs); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 27a0a9d9..ed137182 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -7,6 +7,8 @@ import java.util.*; public class TypeTuple extends Type { + public TypeMem mem() { return (TypeMem)_types[1]; } + public Type[] _types; private static final Ary<TypeTuple> FREE = new Ary<>(TypeTuple.class); |