diff options
Diffstat (limited to 'chapter28b')
12 files changed, 115 insertions, 42 deletions
diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 2852e23d..81d99190 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -395,6 +395,9 @@ public class CodeGen { // Start and Stop; end points of the generated IR public StartNode _start; public StopNode _stop; + // Iter creates this shared analysis result. Start's unused backedge slot + // roots it until Unlink; serialized Stops retain its escape facts instead. + public GlobalEscapeNode _globalEscapes; // Global Value Numbering. Hash over opcode and inputs; hits in this table // are structurally equal. @@ -427,6 +430,7 @@ public class CodeGen { public void link(FunNode fun) { int fidx = fun.sig().fidx(); _linker.setX(fidx,fun); + add(_globalEscapes); // A new or replacement summary may expose escapes. } // "Linker" mapping from constant TypeFunPtrs to heads of function. These @@ -627,6 +631,7 @@ public class CodeGen { } private void unlink(boolean removeImports) { phase(Phase.Unlink, _phase==Phase.LoopTree, () -> { + _start.setDef(2,null); // Releases the compiler-only escape analysis. if( removeImports ) Unlink.run(this,true); else Unlink.forEval(this,_start,_stop); }); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java index 1ce5b051..4085ebff 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java @@ -8,6 +8,9 @@ import com.seaofnodes.simple.util.Ary; // reuse the worklist and types produced by the preceding phase. public abstract class Iter { static void run(CodeGen code) { + assert code._globalEscapes==null; + code._globalEscapes = new GlobalEscapeNode(); + code._start.setDef(2,code._globalEscapes); // The phase shift closes all parser-in-progress states and freezes // unknown external inputs. Imported nodes carry post-Opto escape // precision, but Iter is a fresh pessimistic solve: memory escape diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index 32027cb5..98350a95 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -270,6 +270,8 @@ public class Serialize { Integer idx = def==null ? Integer.valueOf(0) : anodes.get(def); // Imported function constants retain their symbol, not a body. if( idx==null && n instanceof FunPtrNode && j==1 ) idx=0; + // Shared escape analysis belongs to this compilation only. + if( def instanceof GlobalEscapeNode ) idx=0; assert idx != null : "Missing serialized input for "+n+" input "+j+" def "+def; baos.packed2(idx); } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java index 12c7f1e3..29d4f6aa 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -23,7 +23,12 @@ public class CallNode extends CFGNode { // Source location for late reported errors public final Parser.Lexer _loc; - public CallNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc=loc; CodeGen.CODE._calls.add(this); } + public CallNode(Parser.Lexer loc, Node... nodes) { + super(nodes); + _loc = loc; + CodeGen.CODE._calls.add(this); + CodeGen.CODE.add(CodeGen.CODE._globalEscapes); + } public CallNode(CallNode call) { super(call); _loc = call._loc; } @Override public Tag serialTag() { return Tag.Call; } public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { @@ -97,10 +102,16 @@ public class CallNode extends CFGNode { 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); + if( _type.isHigh() ) return TypeMem.START; + // A broad scalar target can refine to a function pointer during Iter. + // It cannot yet promise that the call exposes nothing. + if( _type!=Type.CONTROL ) return TypeMem.BOT; + if( !(fptr()._type instanceof TypeFunPtr) ) + return fptr()._type.isHigh() ? TypeMem.START : TypeMem.BOT; + if( !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 TypeMem.make(1,Type.BOTTOM,false,false,false,escaped._escFs,escaped._escAs); } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/GlobalEscapeNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/GlobalEscapeNode.java new file mode 100644 index 00000000..dab48530 --- /dev/null +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/GlobalEscapeNode.java @@ -0,0 +1,40 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.*; + +// Escapes from calls and unloaded bodies, shared by all compilation units. +// These include paths which never Return. Iter creates this after parsing; +// the outer Start holds it until Unlink. Saved objects contain the resulting +// StopCU types instead. Dependencies wake this node when contributors change; +// Stops need waking only when the combined result changes. +public class GlobalEscapeNode extends Node { + public GlobalEscapeNode() { super(new Node[0]); _type = TypeMem.BOT; } + @Override public String label() { return "GlobalEscape"; } + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(label()); } + @Override public Node idealize() { return null; } + + @Override public TypeMem compute() { + TypeMem xmem = StopCUNode.priorEscapes(_type); + for( CallNode call : CodeGen.CODE._calls ) + if( !call.isDead() ) { + xmem = StopCUNode.publicBottom(xmem.escapes(call.exposed(this)),xmem); + // FULL memory normalizes to public bits. Preserve precise + // private arguments independently of that normalization. + if( call._type==Type.CONTROL && call.exposesArguments(this) ) + for( int i = 0; i<call.nargs(); i++ ) + xmem = StopCUNode.publicBottom(xmem.escapes(addDepForwards(call.arg(i+2))._type),xmem); + } + for( FunNode fun : CodeGen.CODE._linker ) + if( fun!=null && fun.summary()!=null && !fun.summary().isDead() ) { + xmem = StopCUNode.publicBottom(xmem.escapes(fun.summary().exposed(this)),xmem); + // A reachable unloaded body can call these targets, including + // private initializers. Its arguments are unavailable here. + if( fun._type==Type.CONTROL ) + for( int fidx : fun.summary()._classDependencyFIDXs ) + if( fidx!=0 ) xmem = xmem.makeFrom(XInt.meet(xmem._escFs,XInt.make(fidx)),xmem._escAs); + } + return xmem; + } +} diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/Node.java index 0c704a7d..515b29f4 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -717,7 +717,10 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { n._outputs = new Ary<>(Node.class); n._deps = null; n._hash = 0; - if( n instanceof CallNode call ) CODE._calls.add(call); + if( n instanceof CallNode call ) { + CODE._calls.add(call); + CODE.add(CODE._globalEscapes); + } return n; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java index 61970aa0..a6116e93 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java @@ -35,16 +35,7 @@ public class StopCUNode extends StopNode { StartCUNode start = start(); // Memory start from all returns - TypeMem xmem = TypeMem.START; - // Escape summaries are monotone discovery facts. In Opto, a Return - // can widen from a precise set to FULL; the public-only normalization - // below must not forget private bits already discovered precisely from - // that Return on an earlier SCCP step. - if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() && - CodeGen.CODE._phase.ordinal() <= CodeGen.Phase.Lower.ordinal() && - _type instanceof TypeTuple old && old.mem() instanceof TypeMem omem ) - xmem = xmem.makeFrom(XInt.meet(xmem._escFs,omem._escFs), - XInt.meet(xmem._escAs,omem._escAs)); + TypeMem xmem = priorEscapes(_type instanceof TypeTuple old ? old.mem() : _type); for( Node def : _inputs ) { ReturnNode ret = (ReturnNode)def; @@ -91,27 +82,11 @@ public class StopCUNode extends StopNode { xmem = (TypeMem)xmem.meet(publicBottom(tret.mem(),xmem)); } } - // Native and unknown-caller retention includes calls on paths with - // no Return. A class boundary must not hide it. - for( CallNode call : CodeGen.CODE._calls ) - if( !call.isDead() ) { - xmem = publicBottom(xmem.escapes(call.exposed(this)),xmem); - // FULL memory normalizes to public bits. Preserve precise - // private arguments independently of that normalization. - if( call._type==Type.CONTROL && call.exposesArguments(this) ) - for( int i = 0; i<call.nargs(); i++ ) - xmem = publicBottom(xmem.escapes(addDepForwards(call.arg(i+2))._type),xmem); - } - for( FunNode fun : CodeGen.CODE._linker ) - if( fun!=null && fun.summary()!=null && !fun.summary().isDead() ) { - xmem = publicBottom(xmem.escapes(fun.summary().exposed(this)),xmem); - // A reachable unloaded body can call these targets, including - // private initializers. Its arguments are unavailable here. - // Preserve these precise dependencies after normalizing FULL. - if( fun._type==Type.CONTROL ) - for( int fidx : fun.summary()._classDependencyFIDXs ) - if( fidx!=0 ) xmem = xmem.makeFrom(XInt.meet(xmem._escFs,XInt.make(fidx)),xmem._escAs); - } + // All units share escapes from calls and unloaded bodies, including + // paths with no Return. Revisit only when that shared result changes. + GlobalEscapeNode global = CodeGen.CODE._globalEscapes; + if( global!=null && !global.isDead() ) + xmem = publicBottom(xmem.escapes(addDepForwards(global)._type),xmem); assert xmem._alias==1 && !xmem._one; return TypeTuple.make(Type.CONTROL,xmem,Type.BOTTOM); } @@ -119,7 +94,7 @@ public class StopCUNode extends StopNode { // FULL escape sets arise from global BOTTOM. Across a compilation-unit // boundary global BOTTOM exposes every public field, while retaining any // private escapes already discovered precisely. - private TypeMem publicBottom(TypeMem mem, TypeMem prior) { + static TypeMem publicBottom(TypeMem mem, TypeMem prior) { // The pessimistic Iter pass naturally lifts transient FULL inputs to // precise finite sets. Replacing FULL early there would let a later // input refinement add bits, reversing Iter's monotonic direction. @@ -135,6 +110,18 @@ public class StopCUNode extends StopNode { return escFs==mem._escFs && escAs==mem._escAs ? mem : mem.makeFrom(escFs,escAs); } + // In Opto, a precise escape set can widen to FULL. Public-only + // normalization must retain private bits discovered on an earlier step. + static TypeMem priorEscapes(Type old) { + TypeMem mem = TypeMem.START; + if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() && + CodeGen.CODE._phase.ordinal() <= CodeGen.Phase.Lower.ordinal() && + old instanceof TypeMem prior ) + mem = mem.makeFrom(XInt.meet(mem._escFs,prior._escFs), + XInt.meet(mem._escAs,prior._escAs)); + return mem; + } + @Override public Node idealize() { int len = nIns(); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java index 426174e7..c22b4bdd 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java @@ -16,6 +16,7 @@ public class SummaryNode extends CFGNode implements MultiNode { super(inputs); _state = state; _classDependencyFIDXs = classDependencyFIDXs; + CodeGen.CODE.add(CodeGen.CODE._globalEscapes); } @Override public String label() { return "Summary"; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 9ae68bcf..d0fc3ee9 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -236,7 +236,10 @@ public class TypeMem extends Type { : XInt.meet(xs,ts.fidxs()); case TypeFunPtr tfp -> XInt.meet(xs,tfp.fidxs()); case TypeMem mem -> XInt.meet(xs,mem._escFs); - case Type tt -> tt == BOTTOM ? XInt.FULL : xs; + // An abstract pointer or scalar can refine to a concrete escaped + // object or function. Until then it must allow all of their bits. + case TypePtr ptr -> ptr.isHigh() ? xs : XInt.FULL; + case Type tt -> tt == BOTTOM || tt == TypeScalar.BOT ? XInt.FULL : xs; }; } @@ -247,7 +250,8 @@ public class TypeMem extends Type { ? XInt.FULL // Open structs can have any fields : XInt.meet(xs,ts.aliases()); case TypeMem mem -> XInt.meet(xs,mem._escAs); - case Type tt -> tt == BOTTOM ? XInt.FULL : xs; + case TypePtr ptr -> ptr.isHigh() ? xs : XInt.FULL; + case Type tt -> tt == BOTTOM || tt == TypeScalar.BOT ? XInt.FULL : xs; }; } } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 1001e691..66a318ae 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -216,7 +216,7 @@ for( int i=0; i<ary#-1; i++ ) return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """; testCPU(src,"x86_64_v2", "SystemV",-1,"return mov(.[]);"); - testCPU(src,"riscv" , "SystemV", 9,"return (add,.[],(mul,.[],1000));"); + testCPU(src,"riscv" , "SystemV", 7,"return (add,.[],(mul,.[],1000));"); testCPU(src,"arm" , "SystemV", 5,"return (add,.[],(mul,.[],1000));"); } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java index d5b41ac9..f1dc54e2 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -324,7 +324,7 @@ for( int i=0; i<ary#-1; i++ ) return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """; testCPU(src,"x86_64_v2", "SystemV",-1,"return mov(.[]);"); - testCPU(src,"riscv" , "SystemV", 9,"return (add,.[],(mul,.[],1000));"); + testCPU(src,"riscv" , "SystemV", 7,"return (add,.[],(mul,.[],1000));"); testCPU(src,"arm" , "SystemV", 5,"return (add,.[],(mul,.[],1000));"); } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java index 113676ff..bb08b5ac 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -7,6 +7,23 @@ import static org.junit.Assert.assertSame; public class TypeTest { + // Refining an unknown pointer must remove possible escapes, not add them. + // Inlining can expose the abstract self pointer before its concrete class. + @Test public void testAbstractPointerEscapes() { + TypeMemPtr object = TypeMemPtr.make(TypeStruct.make("EscapingCallback",false, + Field.make("callback",TypeFunPtr.TEST,2,false))); + for( Type precise : new Type[]{object,TypeFunPtr.TEST} ) + for( Type broad : new Type[]{Type.BOTTOM,TypeScalar.BOT,TypePtr.PTR,TypePtr.NPTR} ) { + Assert.assertTrue(precise.isa(broad)); + TypeMem unknown = TypeMem.START.escapes(broad); + assertSame(XInt.FULL,unknown._escFs); + assertSame(XInt.FULL,unknown._escAs); + Assert.assertTrue(TypeMem.START.escapes(precise).isa(unknown)); + } + for( Type empty : new Type[]{Type.TOP,TypeScalar.TOP,TypePtr.XPTR,TypePtr.XNPTR,TypeNil.NIL} ) + assertSame(TypeMem.START,TypeMem.START.escapes(empty)); + } + @Test public void testBoundedBits() { int[] sparse = XInt.make(XInt.make(2),65); for( int[] bits : new int[][]{XInt.EMPTY,XInt.FULL,sparse,XInt.dual(sparse)} ) |