diff options
Diffstat (limited to 'chapter28b')
18 files changed, 217 insertions, 74 deletions
diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java index 42e6695e..a018c3ee 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -334,17 +334,18 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public boolean isEmpty() { return _len==0; } - //Node[] asAry() { return Arrays.copyOf(_es,_len); } - //public void clear() { - // _len = 0; - // _on.clear(); - // _R.setSeed(_seed); - // _totalWork = 0; - //} + public void clear() { + Arrays.fill(_es,0,_len,null); + _len = 0; + _on.clear(); + _R.setSeed(_seed); + _totalWork = 0; + } } } 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/GlobalCodeMotion.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 42999894..a1ac4e67 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.Utils; import java.util.*; @@ -152,25 +153,53 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between objects, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final AryInt TOUCHED = new AryInt(); + private static final Ary<Node> PLACED = new Ary<>(Node.class); + private static final Ary<Node> ANTIDEPS = new Ary<>(Node.class); + private static final WorkList<Node> WORK = new WorkList<>(); + private static void schedLate( CodeGen code, StopNode stop ) { - CFGNode[] late = new CFGNode[code.UID()]; - Node[] ns = new Node[code.UID()]; - // Record Load NIDs at all their CFG block choices, then check against - // Store block choices to force a Load above an anti-dependent Store. - int[] anti = new int[code.UID()]; - Ary<Node> antideps = new Ary<>(Node.class); + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(stop,ns,late,anti, antideps); + // Early scheduling has released the shared visit bits. + breadth(stop,PLACED,LATE,ANTI,ANTIDEPS,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( int i=0; i<TOUCHED.len(); i++ ) + LATE[TOUCHED.at(i)] = null; + TOUCHED.clear(); + clear(PLACED); + clear(ANTIDEPS); + } + + // Ary.clear retains references; static scratch must release them as well. + private static void clear(Ary<Node> nodes) { + Arrays.fill(nodes._es,0,nodes._len,null); + nodes.clear(); + } + + private static Ary<Node> antiDeps(MemOpNode load, Ary<Node> antideps) { + clear(antideps); + return load.antiDeps(antideps); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti, Ary<Node> antideps) { + private static void breadth(Node stop, Ary<Node> placed, CFGNode[] late, int[] anti, Ary<Node> antideps, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -189,21 +218,23 @@ public abstract class GlobalCodeMotion { // Loads need their memory inputs' uses also done if( n instanceof MemOpNode ld && ld._isLoad ) - for( Node memuse : ld.antiDeps(antideps) ) + for( Node memuse : antiDeps(ld,antideps) ) if( late[memuse._nid]==null ) continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti,antideps); + _doSchedLate(n,placed,late,anti,antideps); } + TOUCHED.push(n._nid); // A use just finished; reconsider its inputs and waiting loads, // even when the shared memory input was already scheduled. for( Node def : n._inputs ) { if( def==null ) continue; if( late[def._nid]==null ) work.push(def); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -211,7 +242,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti, Ary<Node> antideps) { + private static void _doSchedLate(Node n, Ary<Node> placed, CFGNode[] late, int[] anti, Ary<Node> antideps) { // Walk uses, gathering the LCA (Least Common Ancestor) of uses CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0(); assert early != null; @@ -233,7 +264,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.push(n); late[n._nid] = best; } @@ -276,10 +307,11 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti, Ary<Node> antideps) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep - for( Node mem : load.antiDeps(antideps) ) { + for( Node mem : antiDeps(load,antideps) ) { if( mem instanceof PhiNode phi ) { // Inputs carrying different memory might overwrite this alias. // Raise the LCA for those paths; the unchanged-memory paths @@ -295,6 +327,10 @@ public abstract class GlobalCodeMotion { lca = anti_dep(load,late[mem._nid],mem.cfg0(),lca,mem,anti); } } + // This load's marks are no longer needed; leave scratch clean even + // when the next compilation reuses these node IDs. + for( CFGNode cfg = marked; cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/IFG.java index bcdb14bf..d15e66da 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -172,6 +172,16 @@ abstract public class IFG { // Check use-side for self-conflict; if so we MUST split selfConflict(alloc,def,lrg1); + // All operands are live together, regardless of their input order. + TMP.put(lrg1,def); + } + + // Check fixed-register uses after gathering every operand. An indirect + // call's target comes after its arguments, but must also avoid their + // fixed registers (and may need to move from its incoming register). + for( int i=1; i<n.nIns(); i++ ) { + Node def = n.in(i); + if( def==null || alloc.lrg(def)==null ) continue; // Look for a must-use single register conflicting with some other must-def. if( n instanceof MachNode m ) { RegMask ni_mask = m.regmap(i); @@ -190,10 +200,6 @@ abstract public class IFG { } } } - - // All inputs live - except in self conflicts, where we keep the prior def alive - // until it goes. - TMP.put(lrg1,def); } } 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/CFGNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 2e8c3ff9..cb406e5b 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -203,7 +203,7 @@ public abstract class CFGNode extends Node { _ltree = stop._ltree = CodeGen.CODE.XCTRL._ltree = new LoopTree((StartNode)this); Ary<FunNode> work = new Ary<>(FunNode.class); - BitSet post = new BitSet(); + BitSet post = CodeGen.CODE.visit(); int pre = 1; _pre = pre++; for( FunNode fun : funs ) { @@ -221,6 +221,7 @@ public abstract class CFGNode extends Node { for( int i=0; i<work._len; i++ ) pre = work.at(i)._bltWalk(pre,work.at(i),stop, post, work); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post, Ary<FunNode> work ) { 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/PhaseTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/PhaseTest.java index ee262d6c..f2d09c7c 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/PhaseTest.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/PhaseTest.java @@ -42,6 +42,29 @@ public class PhaseTest { } } + @Test public void testSchedulingScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + for( int i=0; i<5; i++ ) { + int old = xs[arg&1]; + xs[0] = i; + sum += old; + } + return sum; + """; + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(Phase.TypeCheck); + // A small graph after many earlier node allocations, then fresh + // compilations which reuse its IDs and scheduling scratch. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } + @Test public void testExplicitSerializationAndMemoryExport() { CodeGen code = new CodeGen(SRC).driver(Phase.Serialize); assertNotNull(code._serial); diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java index d56d5c89..fa14fc2c 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java @@ -134,7 +134,10 @@ public class SelectiveLoadingTest { @Test public void testUnknownCallbackEncoding() { for( String cpu : new String[]{"x86_64_v2","arm","riscv"} ) - new CodeGen("val apply = { {int->int} f,int n -> f(n); };") + new CodeGen(""" + val apply = { {int->int} f,int n -> f(n); }; + val apply_noInline = { {int->int} f,int n -> f(n); }; + """) .driver(CodeGen.Phase.Encoding,cpu,"SystemV"); } 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)} ) |