From f7fcac0ac9ebfc11549272fa8c166c26e5418e3f Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 28 Oct 2026 22:57:30 -0700 Subject: A more incremental StopCU Incremental summary of escape data in a single node, instead of repeated in StopCU over and over --- .../com/seaofnodes/simple/codegen/CodeGen.java | 5 +++ .../java/com/seaofnodes/simple/codegen/Iter.java | 3 ++ .../com/seaofnodes/simple/codegen/Serialize.java | 2 + .../java/com/seaofnodes/simple/node/CallNode.java | 21 ++++++--- .../seaofnodes/simple/node/GlobalEscapeNode.java | 40 +++++++++++++++++ .../main/java/com/seaofnodes/simple/node/Node.java | 5 ++- .../com/seaofnodes/simple/node/StopCUNode.java | 51 ++++++++-------------- .../com/seaofnodes/simple/node/SummaryNode.java | 1 + .../java/com/seaofnodes/simple/type/TypeMem.java | 8 +++- .../java/com/seaofnodes/simple/Chapter20Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 2 +- .../test/java/com/seaofnodes/simple/TypeTest.java | 17 ++++++++ 12 files changed, 115 insertions(+), 42 deletions(-) create mode 100644 chapter28b/src/main/java/com/seaofnodes/simple/node/GlobalEscapeNode.java (limited to 'chapter28b') 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 strs, HashMap types, IdentityHashMap 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 _print1(ExprPrinter 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 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= 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