diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/node')
10 files changed, 125 insertions, 26 deletions
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 |