From 8f460340cfe01a4945635251bcd33b257b699bf7 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 5 Nov 2026 15:51:41 -0800 Subject: Remove a bunch of extra graph walks pre-Opto Removed most; moved a few into Opto setup pass. Lots of modest bug fixes --- .../simple/codegen/ClassInitDependencies.java | 4 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 30 ++++++--- .../java/com/seaofnodes/simple/codegen/Iter.java | 60 ++---------------- .../com/seaofnodes/simple/codegen/IterPeeps.java | 2 +- .../java/com/seaofnodes/simple/codegen/Opto.java | 73 ++++++++++++++++++---- .../com/seaofnodes/simple/codegen/ParseAll.java | 43 ------------- .../com/seaofnodes/simple/codegen/RegAlloc.java | 19 +++++- .../com/seaofnodes/simple/codegen/TypeCheck.java | 28 ++++++--- .../com/seaofnodes/simple/node/CLInitNode.java | 5 +- .../java/com/seaofnodes/simple/node/CallNode.java | 26 +++----- .../com/seaofnodes/simple/node/ConstructNode.java | 52 +++++++++++++-- .../com/seaofnodes/simple/node/ConvertNode.java | 1 + .../com/seaofnodes/simple/node/EscapeNode.java | 8 ++- .../java/com/seaofnodes/simple/node/FRefNode.java | 2 + .../com/seaofnodes/simple/node/FldOffNode.java | 8 +-- .../java/com/seaofnodes/simple/node/FunNode.java | 15 +++-- .../seaofnodes/simple/node/GlobalEscapeNode.java | 11 +--- .../java/com/seaofnodes/simple/node/LoadNode.java | 28 +++++++-- .../java/com/seaofnodes/simple/node/MulNode.java | 2 +- .../main/java/com/seaofnodes/simple/node/Node.java | 6 +- .../java/com/seaofnodes/simple/node/ParmNode.java | 13 +--- .../java/com/seaofnodes/simple/node/PhiNode.java | 43 ++++++++++--- .../com/seaofnodes/simple/node/PtrToIntNode.java | 2 + .../com/seaofnodes/simple/node/StopCUNode.java | 52 ++++----------- .../java/com/seaofnodes/simple/node/StoreNode.java | 15 +++-- .../com/seaofnodes/simple/node/ToFloatNode.java | 2 + .../com/seaofnodes/simple/node/ToIntegerNode.java | 2 + .../com/seaofnodes/simple/parser/Allocations.java | 17 +++-- .../com/seaofnodes/simple/parser/Construction.java | 69 ++++---------------- .../com/seaofnodes/simple/parser/Functions.java | 5 +- .../java/com/seaofnodes/simple/parser/Parser.java | 1 - .../java/com/seaofnodes/simple/parser/README.md | 4 +- .../com/seaofnodes/simple/parser/References.java | 23 +++---- .../java/com/seaofnodes/simple/parser/Structs.java | 43 ++----------- .../java/com/seaofnodes/simple/type/TypeMem.java | 10 +++ .../com/seaofnodes/simple/type/TypeStruct.java | 10 ++- 36 files changed, 365 insertions(+), 369 deletions(-) (limited to 'chapter29/src/main/java/com') diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java index 3547b86c..9c954197 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java @@ -100,7 +100,9 @@ public class ClassInitDependencies { // CLInit adds a class init requirement to this function // (plus all parent classes) - if( cfg instanceof CLInitNode init ) { + // An invalid receiver can still be Scalar.BOT here. Its Load + // reports the error at TypeCheck; it does not name a class to init. + if( cfg instanceof CLInitNode init && init.cu()!=null ) { FunNode clz = code.link(init.cu()); // referred to iset.put(clz.sig().fidx(),1); // Add to edge set if( sites!=null && sites.atX(clz.sig().fidx())==null ) sites.setX(clz.sig().fidx(),init._loc); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 6e1c0af5..ba7c0c1d 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -102,11 +102,10 @@ public class CodeGen { } private void gatherPublicFields(TypeStruct clz, boolean classFields) { - boolean hasCtor = clz.field("") != null; for( Field fld : clz._fields ) { - // With a user constructor, class:N.N is the private . + // Private-memory helpers are reached through their allocator. if( fld._fname.charAt(0)=='_' || fld._t==Type.TOP || - (hasCtor && clz.hiddenInit(fld)) ) continue; + clz.hiddenInit(fld) ) continue; if( classFields ) _publicAliases = XInt.make(_publicAliases,fld._alias); if( fld._t instanceof TypeFunPtr tfp ) _publicFIDXs = XInt.meet(_publicFIDXs,tfp._fidxs); @@ -125,14 +124,13 @@ public class CodeGen { } private int[] _publicFIDXs, _publicAliases; + private TypeMem _publicEscapes; /** - * Collect every possible public escape - after ParseAll is done - in case - * some code calls a generic function. Example: - * var apply = = { {int->int} f, int x -> f(x); }; // Generic apply() call - * The CallEnd from `f(x)` has to use generic TypeMem.BOT, which - * immediately escapes *everything* including known private functions. - * As weak as this is, its still sharper than "everything". + * Snapshot the public interface after ParseAll for interface checks and + * the default escapes of opaque external types. This is not an upper + * bound on all escapes: a public function can return a private object or + * callback. Escape flow preserves those actual values separately. */ void freezePublicInterface() { assert _publicFIDXs==null && _publicAliases==null; @@ -157,12 +155,21 @@ public class CodeGen { fidxs = XInt.make(fidxs,fidx); } _publicFIDXs = fidxs; + _publicEscapes = TypeMem.START.makeFrom(_publicFIDXs,_publicAliases); } public int[] publicFIDXs() { assert _publicFIDXs !=null; return _publicFIDXs; } public int[] publicAliases(){ assert _publicAliases!=null; return _publicAliases; } public boolean publicInterfaceFrozen() { return _publicFIDXs != null; } + // Before Opto upgrades the IR, a forward reference might still name a + // local class. Afterwards, unresolved names describe external objects. + public TypeMem publicEscapes() { + if( _phase==null || _phase.ordinal() { - // Type import can reconcile a constant's declaration. - n._type = n instanceof ConstantNode ? n.compute() - : hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); - code.add(n); - return null; - }); + // Parsing queues initialized nodes and phase-sensitive peepholes. + // Only the new escape summary needs seeding here. + code.add(code._globalEscapes); code._iter.iterate(code); // Expensive assert. assert !CodeGen.expensiveAssert() || Opto.fixedPointCheck(code); } - // Stabilize existing node types before releasing source error obligations. - // No rewrites: even an unused illegal Load must still be checked here. - public static void types(CodeGen code) { - // Definite initialization needs the optimistic solution around loops: - // an unchanged initialized field must not be stuck at its old BOT seed. - Ary typed = new Ary<>(Node.class); - code._start.walk(n -> { typed.add(n); n._type = Type.TOP; code.add(n); return null; }); - Node n; - while( (n = code._iter._work.pop())!=null ) { - if( n.isDead() ) continue; - Type t = n._type.meet(n.compute()); - if( t==n._type ) continue; - n._type = t; - code.addAll(n._outputs); - n.moveDepsToWorklist(); - } - code.addAll(typed); - } - - private static Type iterEscapeReset(Type t) { - if( t instanceof TypeMem mem ) - return mem._one ? mem : mem.makeFrom(XInt.FULL,XInt.FULL); - if( t instanceof TypeTuple tt ) { - TypeTuple rez = tt; - for( int i=0; i { // Ignore most in-progress things if( n.iskeep() ) return null; - // Types must be forwards, even if on the worklist. + // Types must lift, even if on the worklist. Type nval = n.compute(); assert nval.isa(n._type) : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+n; if( list.on(n) ) diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java index aa997204..0c37ce39 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.IterPeeps.WorkList; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; @@ -30,7 +31,8 @@ abstract public class Opto { WorkList deps = new WorkList<>(); WorkList changes = new WorkList<>(); Ary modes = new Ary<>(Node.class); - resetToTop(code,oldTypes,modes,deps); + Ary returns = new Ary<>(ReturnNode.class); + resetToTop(code,oldTypes,modes,deps,returns); unlinkStart(code); // OPTIMISTIC INTERPROCEDURAL SCCP @@ -50,24 +52,73 @@ abstract public class Opto { // After SCCP add everything changed to the worklist and see if // peepholes can make more progress. moveChangesToWorklist(code, oldTypes, changes); + // Unknown callers and concrete call edges have now been rediscovered. + for( ReturnNode ret : returns ) code.add(ret.unkeep()); } - // Reset Types before running the worklist algorithm - private static void resetToTop(CodeGen code, Ary oldTypes, Ary modes, WorkList deps ) { + // Transition from Iter's pessimistic graph to SCCP's optimistic solve in + // one walk. Parsing has closed the named types; install them in the IR + // and resolve forward references before resetting each value to TOP. + // Do not run peepholes here: neighboring nodes may not yet be upgraded or + // reset. SCCP sees the completed setup, and IterPostOpto handles rewrites. + // + // The same walk preserves Returns while call edges are rebuilt, remembers + // old types for incremental cleanup, and gathers numeric modes and phase + // dependencies. These are setup duties, not separate graph passes. + private static void resetToTop(CodeGen code, Ary oldTypes, Ary modes, WorkList deps, Ary returns ) { code._start.walk( x -> { + // A snapshot for change detection, not an upper bound: closing + // recursive declarations can change types in either direction. + oldTypes.setX(x._nid,x._type); + if( x.upgradeType(Parser.TYPES) ) deps.push(x); + if( x instanceof FRefNode fref ) resolveForward(code,fref); + // Rebuilding call edges must not DCE a temporarily uncalled body. + // Type-level function references can rediscover it later in SCCP. + if( x instanceof ReturnNode ret ) returns.add(ret.keep()); // Opto ends Parm.inProgress(), enabling constant folding even // when a parameter's type was already constant before SCCP. if( x instanceof ParmNode && x._type.isHighOrConst() ) deps.push(x); + // Construction identities may fold after the optimistic solve. + // Adds may need sorting after imported node IDs were assigned. + if( x instanceof ConstructNode || x instanceof AddNode ) deps.push(x); // SCCP adds call edges and default arguments, not numeric // operations. Gather unresolved modes on this required walk. if( x instanceof ModeNode mode && mode.mode()==0 ) modes.push(x); - oldTypes.setX(x._nid,x._type); // Compare the final SCCP type with Iter's type x._type = Type.TOP; // Reset all Nodes to TOP code._iter.add(x); // Visit everybody at least once; most Nodes produce better than TOP return null; } ); } + private static void resolveForward(CodeGen code, FRefNode fref) { + if( fref.nIns()!=1 ) return; + boolean alloc = fref._name.endsWith("."); + String clzName = alloc + ? fref._name.substring(0,fref._name.length()-".".length()).intern() + : fref._name; + TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); + if( clz==null ) return; + Node con; + if( alloc ) { + Field ctor = clz.field(""); + if( ctor==null || !(ctor._t instanceof TypeFunPtr tfp) ) { + String name = clzName.startsWith(TypeStruct.CLZ) + ? clzName.substring(TypeStruct.CLZ.length()) : clzName; + int dot = name.lastIndexOf('.'); + throw Parser.error("Unknown struct type '"+(dot==-1 ? name : name.substring(dot+1))+"'",fref._loc); + } + FunNode fun = code._link(tfp); + if( fun==null ) return; + con = new FunPtrNode(tfp,code._start,fun.ret()); + con._type = Type.BOTTOM; // No Iter bound; the Return may already be reset. + } else { + con = new ConstantNode(TypeMemPtr.make((byte)2,clz,true)); + } + // The new input is visited by the reset walk too. Let SCCP propagate + // its value; replacing the FRef is a later peephole. + fref.addDef(con); + } + // Only entry initializers start with unknown callers. Discover every // other function through calls or escaping values during SCCP. @@ -90,8 +141,9 @@ abstract public class Opto { // Unhook from Stop without treating the ReturnNode as // DEAD. It stays in limbo until Opto links when a caller // is discovered (or not, and the function is really dead). - stop._inputs.del(i--); - ret.delUse(stop); + // The reset walk keeps Returns alive. Use normal edge + // editing so cleanup also revisits an emptied StopCU. + stop.delDef(i--); } // Unlink the existing conservative call linkages. for( int j=1; j"); - String clzName = alloc - ? fref._name.substring(0,fref._name.length()-".".length()).intern() - : fref._name; - TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); - if( clz == null ) - return null; - Node con; - if( alloc ) { - Field ctor = clz.field(""); - if( ctor == null || !(ctor._t instanceof TypeFunPtr tfp) ) { - String name = clzName.startsWith(TypeStruct.CLZ) - ? clzName.substring(TypeStruct.CLZ.length()) : clzName; - int dot = name.lastIndexOf('.'); - throw Parser.error("Unknown struct type '"+(dot==-1 ? name : name.substring(dot+1))+"'",fref._loc); - } - FunNode fun = code.link(tfp); - if( fun == null ) return null; - con = new FunPtrNode(tfp,code._start,fun.ret()).peephole(); - } else { - // Class pointer constant: - TypeMemPtr clzptr = TypeMemPtr.make((byte)2,clz,true); - con = code.con(clzptr); - } - // Replace and optimize - fref.addDef(con); - code.add(fref); - } - // Adds sort by NIDs, which just got shuffled - if( n instanceof AddNode add ) - code.add(add); - // All imported bodies are loaded; link them before Iter checks types. - if( n instanceof CallNode call && !NEEDS_LOAD.isEmpty() ) - code.add(call).idealize(); - return null; - } ); - // The complete public interface is now known. Keep this independent // of later graph/linker liveness so SCCP computations remain local and // monotonic. - code.P.checkConstruction(); code.freezePublicInterface(); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index ac792988..f1aa18ef 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -425,6 +425,21 @@ public class RegAlloc { Node[] conflicts = lrg._selfConflicts.keySet().toArray(new Node[0]); Arrays.sort(conflicts, (x,y) -> x._nid - y._nid ); + // A commutative two-address tie may join a whole chain to a Phi even + // when only the Phi and an earlier def actually overlap. Reuse the + // failed-range walk to find those ties before inserting copies. + // A Split's single use is artificial: leave earlier splitting intact. + findAllLRG(lrg); + for( int i = 0; i<_ns._len; i++ ) { + Node n = _ns.at(i); + if( lrg(n)==lrg && n instanceof MachNode mach && mach.twoAddress()==1 && + mach.commutes() && !(n.in(2) instanceof SplitNode) && + n.in(2).nOuts()==1 && lrg(n.in(2))!=lrg ) + n.swap12(); + else _ns.remove(i--); + } + // Reuse the scratch list to remember just the ties we broke. + // First encounter with a loop Phi: try only cold splits this round. // Remember the Phi across rounds so a persistent self-conflict forces // the hot def/backedge splits on the next encounter. @@ -466,7 +481,9 @@ public class RegAlloc { insertBefore(phi,i,"use/self/phi",round,lrg); } // Split before two-address ops which extend the live range - if( def instanceof MachNode mach && mach.twoAddress()!= 0 ) + // A commuted operand already broke this tie. Rebuild it in the + // next normal coloring round instead of copying the old range. + if( def instanceof MachNode mach && mach.twoAddress()!=0 && _ns.find(def)==-1 ) insertBefore(def,mach.twoAddress(),"use/self/two",round,lrg); } return true; diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index abd8628d..30e1415e 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -19,10 +19,12 @@ abstract class TypeCheck { code._classInitDependencies = deps; // Serialize reuses this checked graph. Ary errs = new Ary<>(Node.class); + Ary constructs = new Ary<>(ConstructNode.class); code._stop.walk( n -> { if( n.err() != null ) errs.add(n); if( n instanceof CLInitNode ) code.add(n); + if( n instanceof ConstructNode con ) constructs.add(con); return null; }); @@ -30,25 +32,35 @@ abstract class TypeCheck { // Prefer an originating error over a secondary error caused by a // BOTTOM input. If all errors are downstream-poisoned, retain // the old first-error behavior. - Node min = null; - for( Node n : errs ) - if( noBottomInputs(n) ) - { min = n; break; } - if( min==null ) - min = errs.at(0); + Node min = errs.at(0); for( Node n : errs ) if( n!=min && - noBottomInputs(n) && + (errorRank(n)=0; fidx = XInt.next(tfp.fidxs(),fidx) ) { - FunNode fun = CodeGen.CODE._link(fidx); - if( fun!=null && !fun.isClz() ) { - dep.addDepForwards(fun); - if( fun.unknownCallers() ) return true; - } - } - return false; - } - // As in the escape chapter, native code may retain an argument even if // this path never returns. StopCU reads this independently of CallEnd. TypeMem exposed(Node dep) { @@ -165,7 +153,8 @@ public class CallNode extends CFGNode { // Walk the bits and link for( int fidx = XInt.next(fidxs,0); fidx > 0; fidx = XInt.next(fidxs,fidx) ) { FunNode fun = CodeGen.CODE.link(fidx); - if( fun!=null && !fun._folding && !linked(fun) ) + if( fun==null ) addDepForwards(CodeGen.CODE._start); + if( fun!=null && !addDep(fun)._folding && !linked(fun) ) progress = link(fun); } } @@ -256,6 +245,9 @@ public class CallNode extends CFGNode { // Check for args for( int i=0; i