diff options
Diffstat (limited to 'chapter25/src')
23 files changed, 567 insertions, 316 deletions
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java index a6afc91f..331ff05d 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java @@ -1342,6 +1342,10 @@ public class Parser { TYPES.put(typeName,tself = tself.defined()); } + // Class object keeps a runtime flag to signal the <clinit> has run. + if( isClz ) + TYPES.put(typeName,tself=tself.add(Field.make("$init",TypeInteger.BOOL,_code.alias(_ref._cname),false))); + // Signature of the default constructor TypeFunPtr sig = structInitSig(isClz,tself); // Function and argument names of default constructor @@ -2304,7 +2308,7 @@ public class Parser { Kind.Func func = (Kind.Func)_scope._kinds.at(_scope.enclosingFuncOrDecl()); if( (ts==null || ts==TypeStruct.BOT || ts.isHigh() || startsClzPrefix(ts._name)) && !(ts!=null && (ts._name+".<clinit>").equals(func._name)) ) - ctrl(new CLInitNode(loc(),name,ctrl(),expr).peephole()); + ctrl(new CLInitNode(loc(),ctrl(),expr).peephole()); // With no field, we will update the bulk memory int alias = fld==null ? 1 : fld._alias; @@ -2704,6 +2708,8 @@ public class Parser { } public String position() { return _line_number+":"+(_position-_line_start+1); } + // Numeric location for diagnostics that must survive without source text. + public long lineColumn() { return ((long)_line_number<<32) | (_position-_line_start+1); } /** * Record the source text for lexing diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java index 96bdbb33..0150219e 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java @@ -1,176 +1,184 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.*; import java.util.*; -/** Initialization requirements of the optimized, executable graph. */ -public final class ClassInitDependencies { - private final CodeGen code; - private ArrayList<CompUnit> order; - - private static final class Effects { - final FunNode fun; - final TreeMap<String,String> touches = new TreeMap<>(); - final LinkedHashMap<Effects,String> callers = new LinkedHashMap<>(); - boolean complete; - Effects(FunNode fun, boolean complete) { this.fun=fun; this.complete=complete; } - } +// Search for Class Initialization Cycles. - public ClassInitDependencies(CodeGen code) { this.code=code; } - public void invalidate() { order=null; } - - // Resolve named class objects, including static nested class objects in a file. - private CompUnit owner(String name) { - name=name.substring(Parser.CLZ.length()); - CompUnit best=null; - for( CompUnit cu : code._compunits.values() ) - if( cu._cname!=null && (name.equals(cu._cname) || name.startsWith(cu._cname+".")) && - (best==null || cu._cname.length()>best._cname.length()) ) best=cu; - return best; - } +// Done after Opto, so dead code does not make a cycle. + +// Build the inits-graph, a call-graph plus CLInits plus class parents. + +// (1) Scan all functions f, building _edges[f][]: the set of <cinit> fcns from +// CompUnits from CLInitNodes, and the set of fcn call targets in f and the +// class parent. These are all reported as fidxs (ints). +// +// (2) Walk the _edges graph using Tarjans SCC. Stop at cycles containing a +// <clint> (and continue with cycles NOT containing a <clinit>, which is +// ordinary recursive functions). +// +// (3) Report on <clinit> cycles +// +// +public class ClassInitDependencies { + private final CodeGen _code; + // Function FIDX -> callees, touched initializers, and parent initializer. + public final int[][] _edgess; + private final int[] _pres; + private final int[] _lows; + private final int[] _stk ; + private int _sp; + + + // Build once; tests can inspect the graph independently of cycle checking. + public ClassInitDependencies( CodeGen code ) { + _code = code; + assert code._phase.ordinal() >= CodeGen.Phase.Opto.ordinal(); + _pres = new int[code._linker._len]; + _lows = new int[code._linker._len]; + _stk = new int[code._linker._len]; + + // + BitSet visit = code.visit(); // Visit set per-fcn + Ary<CFGNode> work = new Ary<>(CFGNode.class); // Worklist per-fcn + IntHashMap iset = new IntHashMap(0); // dedup hash set per-fcn + _edgess = new int[code._linker._len][]; - private static String reason(FunNode fun, String what, Parser.Lexer loc) { - return fun._compunit._cname+" ("+fun.label()+"): "+what+ - (loc==null ? "" : " at "+loc.position()); + // For all functions, build the _edges array + for( FunNode fun : code._linker ) + if( fun!=null && !fun.isDead() ) + // Visit function and collect direct class touches and callees + _edgess[fun.sig().fidx()] = walk(code,fun,work,iset,visit); + visit.clear(); } - // Walk control forwards, not backwards from Return: a live touch before an - // infinite loop or nonreturning call must still contribute. Never cross a - // function boundary through Call -> Fun or Return -> CallEnd graph edges. - private void scan(Effects fx, TreeMap<Integer,Effects> functions) { - ArrayDeque<CFGNode> work=new ArrayDeque<>(); - BitSet seen=new BitSet(); - work.add(fx.fun); + // Return the outgoing init edge set for this function + private static int[] walk( CodeGen code, FunNode fun, Ary<CFGNode> work, IntHashMap iset, BitSet visit) { + // Walk function body, looking for outgoing init edges + assert iset .isEmpty(); // int hash set for de-dup + assert visit.isEmpty(); // needs a visit set, because loops + assert work .isEmpty(); // needs a worklist, because DAG, parallel explore paths + + // Children classes always dependent on parents + if( fun.isClz() && fun._compunit._par != null ) + iset.put(code.link(fun._compunit._par).sig().fidx(),1); + + work.push(fun); while( !work.isEmpty() ) { - CFGNode cfg=work.remove(); - if( seen.get(cfg._nid) || cfg._type.isHigh() ) continue; - seen.set(cfg._nid); + CFGNode cfg = work.pop(); + if( visit.get(cfg._nid) ) continue; // Been there, done that + visit.set(cfg._nid); + assert !cfg._type.isHigh(); + // Do not walk off end of function + if( cfg instanceof ReturnNode ) continue; + + // CLInit adds a class init requirement to this function + // (plus all parent classes) if( cfg instanceof CLInitNode init ) { - if( init.ptr()._type instanceof TypeMemPtr ptr && ptr._obj!=TypeStruct.BOT && !ptr._obj.isHigh() ) { - if( Parser.startsClzPrefix(ptr._obj._name) ) { - CompUnit target=owner(ptr._obj._name); - if( target==null ) fx.complete=false; - else fx.touches.putIfAbsent(target._cname,reason(fx.fun,"field "+init._field,init._loc)); - } - } else fx.complete=false; + FunNode clz = code.link(init.cu()); // <clinit> referred to + iset.put(clz.sig().fidx(),1); // Add to edge set } - if( cfg instanceof CallNode call ) { - String why=reason(fx.fun,"call",call._loc); - if( call.fptr()._type instanceof TypeFunPtr fp && !XInt.isHigh(fp.fidxs()) && fp.nfcns()>0 ) { - for( int id=XInt.next(fp.fidxs(),0); id>=0; id=XInt.next(fp.fidxs(),id) ) { - Effects callee=functions.get(id); - if( callee==null ) { fx.complete=false; continue; } - if( callee.fun.isClz() ) - fx.touches.putIfAbsent(callee.fun._compunit._cname,why); - else callee.callers.putIfAbsent(fx,why); - } - } else fx.complete=false; + + // Calls union all their fptr fidxs into the callee set + if( cfg instanceof CallNode call && call.fptr()._type instanceof TypeFunPtr fp ) { + assert !XInt.isHigh(fp.fidxs()) && fp.nfcns()>0; // Call is alive with valid targets + // Union call targets into the callee set + for( int dstx = XInt.next(fp.fidxs(),0); dstx>=0; dstx=XInt.next(fp.fidxs(),dstx) ) + iset.put(dstx,1); } - if( cfg instanceof ReturnNode ) continue; + + // Forward recursion to walk the whole function for( Node use : cfg._outputs ) { - if( !(use instanceof CFGNode next) || next instanceof FunNode || next instanceof StopNode ) continue; - if( next instanceof RegionNode r ) { - if( r._inputs.find(cfg)>0 ) work.add(r); - } else if( next.in(0)==cfg ) work.add(next); + // Do not walk into another function + if( !(use instanceof CFGNode cfg1) || use instanceof FunNode || use instanceof StopNode ) continue; + // Expect control flow edge is sensible + assert (use instanceof RegionNode r && r._inputs.find(cfg)>0) || use.in(0)==cfg; + if( !visit.get(cfg1._nid) ) // Small speed opt + work.add(cfg1); } } + + visit.clear(); + int[] edges = iset.isEmpty() ? null : iset.keySet(); + iset.clear(); + return edges; } - /** Reject post-Opto cycles; incomplete imports/native effects are NOT certified. */ - public void check() { - if( order!=null ) return; - assert code._phase.ordinal() >= CodeGen.Phase.Opto.ordinal(); - TreeMap<Integer,Effects> functions=new TreeMap<>(); - code._start.walk(n -> { - if( n instanceof FunNode fun && !fun.isDead() && !fun._type.isHigh() ) - functions.put(fun.sig().fidx(),new Effects(fun,code.owns(fun))); - return null; - }); - for( Effects fx : functions.values() ) scan(fx,functions); - - // Recursive ordinary functions converge; only class requirements form - // initialization edges. This uses final call targets, never old types. - ArrayDeque<Effects> work=new ArrayDeque<>(functions.values()); - HashSet<Effects> queued=new HashSet<>(functions.values()); - while( !work.isEmpty() ) { - Effects callee=work.remove(); - queued.remove(callee); - for( var edge : callee.callers.entrySet() ) { - Effects caller=edge.getKey(); - boolean changed=false; - for( var touch : callee.touches.entrySet() ) - if( caller.touches.putIfAbsent(touch.getKey(),edge.getValue()+"; then "+touch.getValue())==null ) changed=true; - if( caller.complete && !callee.complete ) { caller.complete=false; changed=true; } - if( changed && queued.add(caller) ) work.add(caller); - } + // Return an error string, or null for an acyclic class-init graph. + public String check() { + _pres[0] = 1; // Preorders stored in pres[0] and start at 1 + BitSet visit = _code.visit(); + + int idx = 0; + for( int fidx = 1; fidx < _edgess.length; fidx++ ) { + if( _pres[fidx] == 0 ) // Already visited + idx = scc(fidx); + if( idx != -1 ) break; // Found a clz cycle } - TreeMap<String,CompUnit> units=new TreeMap<>(); - // Reuse local initializer summaries for diagnostics; no witnesses are - // retained on CompUnit or on this checker after validation returns. - IdentityHashMap<CompUnit,TreeMap<String,String>> reasons=new IdentityHashMap<>(); - for( CompUnit cu : code._compunits.values() ) - if( cu._cname!=null ) { - units.put(cu._cname,cu); - cu._classInitDeps=null; - cu._initComplete=false; // Imported summaries arrive in checkpoint 2. - if( cu._par!=null ) cu.addClassInitDep(code,cu._par); - } - for( Effects fx : functions.values() ) - if( fx.fun.isClz() ) { - CompUnit cu=fx.fun._compunit; - cu._initComplete=fx.complete; - reasons.put(cu,fx.touches); - for( String target : fx.touches.keySet() ) cu.addClassInitDep(code,units.get(target)); + visit.clear(); + + // Error report for a clz heading a cycle + if( idx != -1 ) { + SB sb = new SB().p("Cyclic class initialization: "); + String first = null; + for( int i=idx; i<_sp; i++ ) { + FunNode fun = _code.link(_stk[i]); + if( fun.isClz() ) { + if( first==null ) first = fun._compunit._cname; + sb.p(fun._compunit._cname).p(" -> "); + } } - ArrayList<CompUnit> sorted=new ArrayList<>(), path=new ArrayList<>(); - IdentityHashMap<CompUnit,Integer> colors=new IdentityHashMap<>(); - for( CompUnit cu : units.values() ) visit(cu,colors,path,sorted,reasons); - for( CompUnit cu : sorted ) - if( cu._classInitDeps!=null ) - for( CompUnit dep : cu._classInitDeps ) cu._initComplete &= dep._initComplete; - order=sorted; - } + sb.p(first); + visit.clear(); + return sb.toString(); + } - // Temporary checkpoint lowering: retain existing runtime behavior. Later - // this becomes flag-and-call lowering, and obligations survive serialization. - public void eraseChecks() { - ArrayList<CLInitNode> checks=new ArrayList<>(); - code._start.walk(n -> { if( n instanceof CLInitNode init ) checks.add(init); return null; }); - for( CLInitNode init : checks ) - if( !init.isDead() ) init.subsume(init.in(0)); - code.invalidateIDepthCaches(); + return null; // No errors } - private void visit(CompUnit cu, IdentityHashMap<CompUnit,Integer> colors, - ArrayList<CompUnit> path, ArrayList<CompUnit> sorted, - IdentityHashMap<CompUnit,TreeMap<String,String>> reasons) { - Integer color=colors.get(cu); - if( color!=null ) { - if( color==2 ) return; - int start=path.indexOf(cu); - StringBuilder message=new StringBuilder("Cyclic class initialization: "); - for( int i=start; i<path.size(); i++ ) message.append(path.get(i)._cname).append(" -> "); - message.append(cu._cname); - for( int i=start; i<path.size(); i++ ) { - CompUnit from=path.get(i), to=i+1<path.size() ? path.get(i+1) : cu; - message.append("\n ").append(from._cname).append(" -> ").append(to._cname) - .append(": ").append(from._par==to ? "parent of "+from._cname : reasons.get(from).get(to._cname)); + // Tarjan SCC + int scc( int fidx ) { + // Assign pre-order number + _lows[fidx] = _pres[fidx] = _pres[0]++; + _stk[_sp++] = fidx; + // walk outbound edges + if( _edgess[fidx]!=null ) { + for( int edge : _edgess[fidx] ) { + if( edge >= _pres.length ) continue; // Out of bounds happens when calling C fcns + if( _pres[edge] == 0 ) { // Not visited + int idx = scc(edge); + if( idx != -1 ) return idx; // Found a cycle + _lows[fidx] = Math.min(_lows[fidx],_lows[edge]); + } else if( _edgess[edge]!=null && onStk(edge) ) { + _lows[fidx] = Math.min(_lows[fidx],_pres[edge]); + } } - throw Parser.error(message.toString(),null); } - colors.put(cu,1); - path.add(cu); - ArrayList<CompUnit> deps=new ArrayList<>(); - if( cu._classInitDeps!=null ) for( CompUnit dep : cu._classInitDeps ) deps.add(dep); - deps.sort(Comparator.comparing(dep -> dep._cname)); - for( CompUnit dep : deps ) visit(dep,colors,path,sorted,reasons); - path.removeLast(); - colors.put(cu,2); - sorted.add(cu); + // Found a cycle + if( _lows[fidx] == _pres[fidx] ) { + int idx = find(fidx); + if( hasClzCycle(idx) ) + return idx; // Found a class cycle + // Pop stack, including fidx + _sp = idx; + } + return -1; // No cycle + } + + private int find(int e) { + for( int i=0; i<_sp; i++ ) if( _stk[i] == e ) return i; + return -1; + } + private boolean onStk(int e) { return find(e) != -1; } + + private boolean hasClzCycle(int idx) { + if( idx+1 == _sp ) return false; // Cycle of 1 does not count + for( int i=idx; i<_sp; i++ ) + if( _code.link(_stk[i]).isClz() ) + return true; + return false; } - /** Prerequisite-first order of the known graph, not a completeness certificate. */ - public ArrayList<CompUnit> order() { check(); return new ArrayList<>(order); } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index bc86dc6d..ff0be213 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -80,9 +80,14 @@ public class CodeGen { // Current Working Directory; default module base private final String _cwd; - // Compilation Units in this compile; one per source/object file + // Compilation Units used in this compile; typically one per source/object + // file, although you can nest structs and get more than one. These are all + // required to compile, and are expected to have their source timestamps + // ahead of their obj file. Some of these may entirely be dead or inlined + // in this CompUnit and thus not needed in any linking stage. All the + // alive ones (inlined away or not) participate in class init cycle checks. public HashMap<String,CompUnit> _compunits; - public final ClassInitDependencies _classInitDeps = new ClassInitDependencies(this); + // Test shortcut for only one compilation unit public CompUnit compunit() { assert _compunits.size()==1; @@ -376,6 +381,13 @@ public class CodeGen { _linker.setX(fidx,null); fun = null; } return fun; } + // Return the <clinit> for a CompUnit + public FunNode link( CompUnit cu ) { + for( FunNode fun : _linker ) + if( fun!=null && fun._compunit == cu && fun.isClz() ) + return fun; + return null; + } // Insert linker mapping from constant function signature to the function // being called. @@ -536,28 +548,27 @@ public class CodeGen { long t0 = System.currentTimeMillis(); // Check for class-init cycles first; such a cycle can prevent other - // things from resolving types. Get the classes ordered and init'd - // before reporting other errors. - _classInitDeps.check(); + // things from resolving types. The dependency graph is temporary. + String clzInitCycle = new ClassInitDependencies(this).check(); + if( clzInitCycle != null ) + throw Parser.error(clzInitCycle,null); - final Ary<Node> errs = new Ary<>(Node.class); + Ary<Node> errs = new Ary<>(Node.class); _stop.walk( n -> { - if( n.err() != null ) - errs.add(n); - return null; + if( n.err() != null ) + errs.add(n); + return null; }); - String unresolved = unresolvedTypeName(); _times[Phase.TypeCheck.ordinal()] = System.currentTimeMillis() - t0; + if( !errs.isEmpty() ) { // 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( noBottomInputs(n) ) + { min = n; break; } if( min==null ) min = errs.at(0); for( Node n : errs ) @@ -573,12 +584,6 @@ public class CodeGen { if( _obs != null ) _obs.error(min, min.err().getMessage()); throw min.err(); } - if( unresolved != null ) { - var err = Parser.error("Unknown struct type '"+unresolved+"'",null); - if( _obs != null ) _obs.error(null, err.getMessage()); - throw err; - } - _classInitDeps.eraseChecks(); if( _obs != null ) _obs.phase("TypeCheck"); return this; } @@ -590,21 +595,9 @@ public class CodeGen { return true; } - // Forward-ref structs are open while parsing. They must all be resolved - // to closed structs before leaving type checking. - private String unresolvedTypeName() { - String[] unresolved = new String[1]; - _stop.walk(n -> { - TypeStruct ts = requiredStruct(n); - if( unresolved[0]==null && ts!=null && ts._fref ) - unresolved[0] = ts._name; - return null; - }); - return unresolved[0]; - } - public static TypeStruct requiredStruct(Node n) { - if( n instanceof NewNode alloc ) return alloc._ts; + // CNC: remove? cleanup? + if( n instanceof NewNode alloc ) return alloc._ts; if( n instanceof ConFldOffNode off ) return off._ts; if( n instanceof FldOffNode off && off.in(0)._type instanceof TypeMemPtr ptr ) return ptr._obj; return null; @@ -644,6 +637,13 @@ public class CodeGen { // turns them into external relocations. private void unlinkImports() { assert _phase.ordinal() <= Phase.Serialize.ordinal(); + // Imported function constants keep their symbolic identity, not an + // embedded copy of the other object's Return and body. + for( Node n : _start._outputs.asAry() ) + if( n instanceof FunPtrNode ptr && ptr.ret()!=null && !owns(ptr.fun()) ) { + ptr.liftType(ptr._type); + ptr.setDef(1,null); + } for( FunNode fun : _linker ) { if( fun==null || fun.isDead() || owns(fun) ) continue; @@ -651,6 +651,14 @@ public class CodeGen { if( fun.in(i) instanceof CallNode call ) call.unlink(fun,i--); } + for( int i=0; i<_stop.nIns(); i++ ) { + StopCUNode stop=(StopCUNode)_stop.in(i); + CompUnit cu=_compunits.get(stop.start()._fname); + if( cu._src==null ) _stop.delDef(i--); + } + // The whole-object wrappers now summarize only the emitted units. + _stop._type=_stop.compute(); + _start._type=_start.compute(); //_iter.iterate(this); } @@ -1028,9 +1036,10 @@ public class CodeGen { // Map from symbol string to ELFReader; most lookups // will miss and no need to unpack ElfReader types _externSymbols.putIfAbsent(elf._strs[1],elf); - for( String str : elf._strs ) - if( str.startsWith(Parser.CLZ) ) - _externSymbols.putIfAbsent(str,elf); + + // Publish definitions only; referenced classes belong to other objects. + for( String fname : elf._units ) + _externSymbols.putIfAbsent(Parser.addClzPrefix(fname.replace('/','.')),elf); break; default: throw Utils.TODO("should not reach here"); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java index 6d84c955..544ca27e 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java @@ -32,23 +32,6 @@ public class CompUnit { // dependencies may form a cycle. Ary<CompUnit> _deps; - // _classInitDeps records units whose initialization this initializer may - // require after Opto, including its parent; these edges must form a DAG. - // Initialization prerequisites are a subset of the units that must be - // available, but not necessarily of the direct _deps list: parent links - // and helper-call effects can add initialization edges to units discovered - // indirectly. - public Ary<CompUnit> _classInitDeps; - - // Set after completing the cycle analysis for the <clinit> (and - // prerequisites). - public boolean _initComplete; - - // This unit's own initializer is proven fully represented by static data - // and needs no execution; its ancestors may still need initialization. - // Reserved for static classification; currently always false. - public boolean _initStatic; - // Per-Compilation-Unit Start/StopNodes, keeping alive all exported Nodes. // Null means no code loaded (yet). public StartCUNode _start; @@ -141,16 +124,6 @@ public class CompUnit { code._stop.addDef(_stop); } - - public boolean addClassInitDep(CodeGen code, CompUnit target) { - if( _classInitDeps==null ) _classInitDeps=new Ary<>(CompUnit.class); - if( _classInitDeps.find(target)!=-1 ) return false; - _classInitDeps.add(target); - code._classInitDeps.invalidate(); - return true; - } - - @Override public String toString() { String x = "{"+_cname; if( _smp!=null && _smp.exists()) x += ",hasSMP"; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java index 534bb10f..10720300 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java @@ -30,6 +30,8 @@ public class ElfReader { public String[] _strs; // Dependent file names public String[] _deps; + // Compilation units defined by this object, independent of init analysis. + public String[] _units; // Only published symbol this file public TypeStruct _clz; // Canonical named types, distinct from optimized same-named graph states. diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 155066a4..bb123634 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -42,7 +42,6 @@ public abstract class ParseAll { if( cunit != null ) return cunit; String cname = par==null ? name : (par._cname + "." + name).intern(); code._compunits.put(fname, cunit = external ? new CompUnit(obj,par,fname,cname,name) : new CompUnit(par,fname,cname,name)); - code._classInitDeps.invalidate(); return cunit; } @@ -88,12 +87,6 @@ public abstract class ParseAll { // Load all pre-compiled CompUnits for( CompUnit cu : NEEDS_LOAD ) loadCompUnit(code,cu); - if( !NEEDS_LOAD.isEmpty() ) - code._stop.walk(n -> { - if( n instanceof CallNode ) - code.add(n); - return null; - }); // Many types will have been declared cyclically either internally or // across multiple compilation units. @@ -146,6 +139,9 @@ public abstract class ParseAll { // 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; } ); @@ -196,6 +192,8 @@ public abstract class ParseAll { CompUnit xcunit = findRequiredType(code,cunit,typeName); if( xcunit != null ) cunit.addDep(xcunit); + else + assert false : "expected to find required type"; } catch( IOException ioe ) { throw new RuntimeException(ioe); } @@ -219,16 +217,22 @@ public abstract class ParseAll { // Load IR after parsing if( NEEDS_LOAD.find(cunit) != -1 ) return; // Already on the to-be-loaded list? + for( CompUnit loaded : NEEDS_LOAD ) + if( loaded._obj.equals(cunit._obj) ) return; // Another class in the same object. try { NEEDS_LOAD.add(cunit); // Load dependent classes ElfReader elf = ElfReader.load(cunit._obj,cunit); elf.loadPublicSymbols(); + // Register bundled definitions before resolving dependencies or IR. + for( String fname : elf._units ) + makeCUnit(code,null,fname,cunit._obj); for( String fname : elf._deps ) { // Check CompUnit for being up to date - CompUnit sub = makeCUnit(code,null,fname,null/*depObj(code,cunit,fname)*/); + CompUnit sub = code._compunits.get(fname); + if( sub==null ) sub=makeCUnit(code,null,fname,depObj(code,cunit,fname)); // If not seen before or out of date, parse the new nested cunit - if( sub._clz == null && sub._par == null ) + if( sub._clz == null && WORK.find(sub)==-1 && NEEDS_LOAD.find(sub)==-1 ) WORK.add(sub); } } catch( IOException ioe ) { @@ -257,7 +261,8 @@ public abstract class ParseAll { // Extract published symbols and put them in the internal tables; // cross-references will pick them up there. ElfReader elf = ElfReader.load(cunit._obj,cunit); - cunit._clz = elf.loadSimple(code); + elf.loadSimple(code); + cunit._clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(cunit._cname)); StartNode lstart = (StartNode)elf._nodes.at(0); StopNode lstop = ( StopNode)elf._nodes.last(); @@ -283,8 +288,8 @@ public abstract class ParseAll { // Add the new top-level loaded class Parser.TYPES.put(cunit._clz._name,cunit._clz); Field inst = cunit._clz.field(cunit._name); - if( inst != null ) // Also the instance type, if a constructor exists - Parser.TYPES.put(cunit._cname, ((TypeMem)((TypeFunPtr)inst._t)._ret)._t); + if( inst != null && inst._t instanceof TypeFunPtr tfp && tfp._ret instanceof TypeMem mem ) + Parser.TYPES.put(cunit._cname,mem._t); } // Symbol not found in source code (or we would not be here). @@ -382,11 +387,8 @@ public abstract class ParseAll { throw new RuntimeException(ioe); } ElfReader typedElf = ElfReader.load(cunit._obj,cunit); - TypeStruct clz = typedElf == null ? null : typedElf.loadPublicTypes(code); - if( clz != null ) - Parser.TYPES.put(clz._name,clz); - else - clz = (TypeStruct)Parser.TYPES.get(clzName); + if( typedElf != null ) typedElf.loadPublicTypes(code); + TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); if( clz == null ) Parser.TYPES.put(clzName,clz = TypeStruct.make(clzName,true)); cunit._clz = clz; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index ce546318..1806be24 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -21,6 +21,12 @@ abstract public class Serialize { xdeps.add(cudep._fname); } String[] deps = xdeps.toArray(new String[xdeps.size()]); + Arrays.sort(deps); + Ary<String> owned = new Ary<>(String.class); + for( CompUnit cu : code._compunits.values() ) + if( cu._src!=null ) owned.add(cu._fname); + String[] units = owned.asAry(); + Arrays.sort(units); // Top-level clazz being reported String topName = code._srcName == null ? "Test" : code._srcName; @@ -37,14 +43,14 @@ abstract public class Serialize { TypeStruct[] pubTypes = named.values().toArray(new TypeStruct[0]); // Compress into bytes - BAOS baos = write(nodes, clz, pubTypes, deps, code._aliases, code._fidxs, code._rpcs, code._externFunc); + BAOS baos = write(nodes, clz, pubTypes, deps, units, code._aliases, code._fidxs, code._rpcs, code._externFunc); // --- Expensive bijection assert if( false ) { // Inflate into POJOs; renumbers everything ElfReader elf = new ElfReader(new BAOS(baos.toByteArray())); readAll(code,elf, code._aliases, code._fidxs, code._rpcs); - BAOS baos2 = write(elf._nodes,elf._clz,elf._pubTypes,elf._deps, code._aliases, code._fidxs, code._rpcs, code._externFunc); + BAOS baos2 = write(elf._nodes,elf._clz,elf._pubTypes,elf._deps,elf._units, code._aliases, code._fidxs, code._rpcs, code._externFunc); // Bi-jection for( int i=0; i<baos.size(); i++ ) @@ -58,7 +64,7 @@ abstract public class Serialize { } // -------------------------------------------------- - static BAOS write(Ary<Node> nodes, TypeStruct clz, TypeStruct[] pubTypes, String[] depobjs, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs, HashMap<Integer,String> externFunc) { + static BAOS write(Ary<Node> nodes, TypeStruct clz, TypeStruct[] pubTypes, String[] depobjs, String[] units, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs, HashMap<Integer,String> externFunc) { // Initialize the mapping from bits/tags to types Type.TAGOFFS(); @@ -85,6 +91,12 @@ abstract public class Serialize { if( n instanceof ParmNode parm ) parm._declaredType.gather(types); if( n instanceof TypeNode con ) con._con .gather(types); } + // A defined class remains importable even when its initializer body dies. + for( TypeStruct ts : pubTypes ) + if( Parser.startsClzPrefix(ts._name) && + Arrays.binarySearch(units,ts._name.substring(Parser.CLZ.length()).replace('.','/'))>=0 ) + ts.gather(types); + // Only record canonical declarations already reachable from this // object's graph. Pulling unrelated parser types into this closure // can include open or partially built types from other units. @@ -106,6 +118,7 @@ abstract public class Serialize { if( depobjs != null ) for( String fname : depobjs ) gather(strs,fname); + for( String fname : units ) gather(strs,fname); // Count strings from all types for( Type t : atypes ) { if( t instanceof Field fld ) gather(strs,fld._fname); @@ -139,6 +152,10 @@ abstract public class Serialize { for( String s : astrs ) baos.packedS(s); + // Defined units are loader metadata, not initialization dependencies. + baos.packed4(units.length); + for( String fname : units ) baos.packed4(strs.get(fname)); + // B.2 - Write the local->global mappings aliases.packed(baos,strs); fidxs .packed(baos,strs); @@ -232,6 +249,9 @@ abstract public class Serialize { elf._deps = new String[ndependents]; for( int i=0; i<ndependents; i++ ) elf._deps[i] = strs[1+i+1]; + elf._units = new String[bais.packed4()]; + for( int i=0; i<elf._units.length; i++ ) + elf._units[i] = strs[bais.packed4()]; } // -------------------------------------------------- @@ -260,6 +280,9 @@ abstract public class Serialize { elf._deps = new String[ndependents]; for( int i = 0; i < ndependents; i++ ) elf._deps[i] = strs[1 + i + 1]; + elf._units = new String[bais.packed4()]; + for( int i=0; i<elf._units.length; i++ ) + elf._units[i] = strs[bais.packed4()]; } // B.2 - Read the local->global mappings. Further down we will map @@ -409,6 +432,10 @@ abstract public class Serialize { for( Node n : nodes ) { if( n instanceof StopCUNode && !code.publicInterfaceFrozen() ) continue; + // Cross-object calls are relinked only after every body has + // loaded. Their saved return types cannot be recomputed yet. + if( n instanceof CallEndNode end && end.call().fptr()._type instanceof TypeFunPtr fp && + end.nIns()<=fp.nfcns() ) continue; Type nval = n.compute(); if( nval != n._type ) { System.err.println("Node "+n+" read in as "+n._type+" but computes as "+nval); @@ -506,7 +533,7 @@ abstract public class Serialize { // All the CompUnits for( CompUnit cu : code._compunits.values() ) { // Whole CompUnits have no users, went dead - if( cu._start != null && !cu._start.isDead() ) { + if( cu._src!=null && cu._start != null && !cu._start.isDead() ) { nodes.add(cu._start); // A memory-free, nonreturning unit can lose its memory projection. ProjNode mem=cu._start.proj(1); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CLInitNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CLInitNode.java index f00d8076..5131049e 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CLInitNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -2,29 +2,65 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.CompUnit; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; +import com.seaofnodes.simple.util.Utils; +import java.util.*; -/** An active class touch, retained in control until initialization validation. - * This checkpoint records the obligation only; flag/call lowering comes later. - */ +// Track class initializers - the code just after this point expects the named +// class to be initialized. If this code path dies, then the dependency dies +// also - dead code does not force class init. +// public class CLInitNode extends CFGNode { - public final Parser.Lexer _loc; - public final String _field; + public Parser.Lexer _loc; // For error reporting - public CLInitNode(Parser.Lexer loc, String field, Node ctrl, Node ptr) { + // For field references, the ptr might be the dst clz ptr or not. + public CLInitNode(Parser.Lexer loc, Node ctrl, Node ptr) { super(ctrl,ptr); - _loc=loc; - _field=field; + _loc = loc; } - public Node ptr() { return in(1); } + CLInitNode(BAOS bais) { super(null,null); } + @Override public Tag serialTag() { return Tag.CLInit; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + } + + public CLInitNode(CLInitNode init) { + super(init); + _loc = init._loc; + } + + Node ptr() { return in(1); } @Override public String label() { return "CLInit"; } - @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("CLInit ").p(ptr()); } + + // Best effort dst compunit, based on ptr - or null + public CompUnit cu() { + if( !(ptr()._type instanceof TypeMemPtr ptr && Parser.startsClzPrefix(ptr._obj._name)) ) + return null; + // Convert "class:sys.ary" into "sys/ary" and lookup CompUnit + String fname = ptr._obj._name.substring(6).replace(".","/"); + return CodeGen.CODE._compunits.get(fname); + } + + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + FunNode fun = fun(); + CompUnit cu = cu(); + return p.p("CLInit ").p(fun._name).p(" -> ").p(cu==null ? "---" : cu._cname); + } + + // Block head is Start, Region, CProj, but not e.g. If, Return, Stop + public boolean blockHead() { return true; } + @Override public Type compute() { return in(0)._type; } @Override public Node idealize() { // A receiver discovered to be an ordinary instance needs no class init. if( ptr()._type instanceof TypeMemPtr ptr && ptr._obj!=TypeStruct.BOT && - !ptr._obj.isHigh() && !Parser.startsClzPrefix(ptr._obj._name) ) return in(0); + !ptr._obj.isHigh() && !Parser.startsClzPrefix(ptr._obj._name) ) + return in(0); // Normal instance, no class init + if( ptr()._type == Type.NIL || ptr()._type.isHigh() ) + return in(0); return null; } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java index 4372e2d5..38117f23 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -22,11 +22,17 @@ 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; } + public CallNode(Parser.Lexer loc, Node... nodes) { this(loc,loc==null ? 0 : loc.lineColumn(),nodes); } + private CallNode(Parser.Lexer loc, long position, Node... nodes) { super(nodes); _loc=loc; } 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 ) { baos.packed1(nIns()); } - static Node make( BAOS bais ) { return new CallNode(null,new Node[bais.packed1()]); } + public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed1(nIns()); + } + static Node make( BAOS bais ) { + int nIns = bais.packed1(); + return new CallNode(null,new Node[nIns]); + } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { String fname = name(); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java index f94fa484..284220ea 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java @@ -71,4 +71,8 @@ public class ConFldOffNode extends ConstantNode { return _ts._name==off._ts._name && _fname.equals(off._fname) && super.eq(n); } @Override int hash() { return super.hash() * _ts._name.hashCode() * _fname.hashCode(); } + + @Override public Parser.ParseException err() { + return _ts._fref ? Parser.error("Unknown struct type '"+_ts._name+"'",null) : null; + } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FldOffNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FldOffNode.java index ef894929..a9f8d692 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FldOffNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FldOffNode.java @@ -45,4 +45,10 @@ public class FldOffNode extends TypeNode { return _fname.equals(off._fname) && super.eq(n); } @Override int hash() { return super.hash() * _fname.hashCode(); } + + @Override public Parser.ParseException err() { + if( in(0)._type instanceof TypeMemPtr tmp && tmp._obj._fref ) + return Parser.error("Unknown struct type '"+tmp._obj._name+"'",null); + return null; + } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java index 1e2ee10a..7f9a2819 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -49,6 +49,7 @@ public class FunNode extends RegionNode { baos.packed2(types.get(_sig)); // NPE if fails lookup baos.packed2(_name==null ? 0 : strs.get(_name)); baos.packed2(_approxUIDs); + // _compunit set from context on loading, do not write } static Node make( BAOS bais, String[] strs, Type[] types) { Node[] ins = new Node[bais.packed1()]; @@ -56,6 +57,7 @@ public class FunNode extends RegionNode { String name = strs[bais.packed2()]; FunNode fun = new FunNode(null,sig,name,null,ins); fun._approxUIDs = bais.packed2(); + // _compunit set from context on loading, do not read return fun; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 365157d2..373b8825 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -136,7 +136,6 @@ public abstract class MemOpNode extends TypeNode { if( off() instanceof ConFldOffNode && CodeGen.CODE._phase.ordinal() > CodeGen.Phase.Opto.ordinal() ) return Parser.error("Accessing unknown field '"+_name+"' from '*"+tmp._obj._name+"'",_loc); return null; - } // Memory writers which must follow this read. A packaging node is not a diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/NewNode.java index 5eedd0cd..fe80f690 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -1,12 +1,11 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; - +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.SB; - import java.util.HashMap; import java.util.IdentityHashMap; @@ -64,6 +63,12 @@ public class NewNode extends Node implements MultiNode { @Override int hash() { return _ts.hashCode(); } + + @Override public Parser.ParseException err() { + return _ts._fref ? Parser.error("Unknown struct type '"+_ts._name+"'",null) : null; + } + + // ------------ // MachNode specifics, shared across all CPUs public int _arg2Reg, _xslot; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java index 23a7e2c4..796965b5 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java @@ -70,20 +70,21 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { // Disk/serialized opcode tags public enum Tag { - Add,And,EQ,NE,LT,LE,ULT, - CallEnd,Call,ConFldOff,Con,CProj, - Div,Escape,Extern,Fun,FunPtr,If,Load,Loop, - MemMerge,Minus,Mul, - New,Never,Not,Or,Parm,Phi,Proj, + Add,And,BulkMemPhi,EQ,NE,LT,LE,ULT, + CallEnd,Call,ConFldOff,Con,CLInit,CProj, + Div,Escape,Extern,ExternOffset,Fun,FunPtr,Guard, + If,Load,Loop,MemMerge,MemPhi,Minus,Mul, + New,Never,Not,Or,Parm,Phi,Proj,PtrToInt, ReadOnly,Return,Region,RoundF32, - Sar,Shl,Shr,Start,Stop,Store,Sub,ToFloat, - XCtrl,Xor,StartCU,StopCU,Guard,MemPhi,BulkMemPhi,PtrToInt,ExternOffset,ToInteger; + Sar,Shl,Shr,Start,StartCU,StopCU,Stop,Store,Sub, + ToInteger,ToFloat,XCtrl,Xor; public static final Tag[] VALS = values(); public Node make( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) { return switch(this) { case Add -> new AddNode(null,null,(byte)bais.packed1()); case And -> { int mode=bais.packed1(); assert mode==1; yield new AndNode(null,null,null); } case Div -> new DivNode(null,null,(byte)bais.packed1()); + case Guard -> GuardNode.make(bais); case If -> new IfNode(null,null); case Loop -> new LoopNode(null,null,null); case Minus -> new MinusNode(null,(byte)bais.packed1()); @@ -104,7 +105,6 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { case ToInteger-> new ToIntegerNode(null); case XCtrl -> new XCtrlNode(); case Xor -> { int mode=bais.packed1(); assert mode==1; yield new XorNode(null,null,null); } - case Guard -> GuardNode.make(bais); case EQ -> new BoolNode.EQ (null,null,(byte)bais.packed1()); case NE -> new BoolNode.NE (null,null,(byte)bais.packed1()); @@ -114,23 +114,24 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { case Call -> CallNode.make(bais); case CallEnd-> CallEndNode.make(bais ,types); + case CLInit -> new CLInitNode(bais); case CProj -> CProjNode.make(bais,strs); case Con -> ConstantNode.make(bais ,types); case Escape-> EscapeNode.make(bais ,types); case Extern-> ExternNode.make(bais,strs,types); case ExternOffset-> new ExternOffsetNode(strs[bais.packed2()]); - case FunPtr-> FunPtrNode.make(bais, types); + case FunPtr-> FunPtrNode.make(bais, types); case Fun -> FunNode.make(bais,strs,types); case Load -> new LoadNode(bais,strs,types,fileAliases,aliases); case MemMerge->MemMergeNode.make(bais); - case MemPhi-> MemPhiNode.make(bais,strs,types,fileAliases,aliases); + case MemPhi-> MemPhiNode.make(bais,strs,types,fileAliases,aliases); case BulkMemPhi-> BulkMemPhiNode.make(bais,strs,types,fileAliases,aliases); case New -> NewNode.make(bais ,types); case Parm -> ParmNode.make(bais,strs,types); case Phi -> PhiNode.make(bais,strs,types); case Proj -> ProjNode.make(bais,strs); case Store -> new StoreNode(bais,strs,types,fileAliases,aliases); - case Stop -> StopNode.make(bais); + case Stop -> StopNode.make(bais); case StartCU-> StartCUNode.make(bais,strs,types); case StopCU -> StopCUNode.make(bais); case Region-> RegionNode.make(bais); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 92cad745..21d60d53 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,12 +1,11 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; - import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Var; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.codegen.ParseAll; import com.seaofnodes.simple.codegen.CompUnit; +import com.seaofnodes.simple.codegen.ParseAll; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index ff15fdad..23c4d530 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -282,6 +282,7 @@ public class x86_64_v2 extends Machine { case AddNode add -> add(add); case AndNode and -> and(and); case BoolNode bool -> cmp(bool); + case CLInitNode init -> new CLInitNode(init); case CProjNode c -> new CProjNode(c); case CallEndNode cend -> new CallEndMach(cend); case CallNode call -> call(call); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/util/IntHashMap.java b/chapter25/src/main/java/com/seaofnodes/simple/util/IntHashMap.java index 55aaa9f9..b356ec31 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/util/IntHashMap.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/util/IntHashMap.java @@ -17,6 +17,7 @@ public class IntHashMap { } public int size() { return _size; } + public boolean isEmpty() { return _size==0; } public void clear() { _size = 0; Arrays.fill(_es,_sentinel); @@ -29,7 +30,7 @@ public class IntHashMap { int old = _es[(slot<<1)+1]; if( old == _sentinel && val != _sentinel ) _size++; if( old != _sentinel && val == _sentinel ) _size--; - // Check cap + // Check cap, resize at 3/4 full if( _size > ((cap()>>1) + (cap()>>2)) ) { grow(); slot = probe(key); @@ -45,7 +46,7 @@ public class IntHashMap { return _es[(slot<<1)+1]; } - int probe( int key ) { + private int probe( int key ) { int mask = cap()-1; int slot = key & mask; while( _es[slot<<1] != _sentinel && _es[slot<<1] != key ) @@ -59,7 +60,28 @@ public class IntHashMap { _es = new int[_es.length<<1]; Arrays.fill(_es,_sentinel); for( int i=0; i<old.length; i+=2 ) - if( old[i] != _sentinel ) - put(old[i],old[i+1]); + if( old[i] != _sentinel ) { + int slot = probe(old[i]); + _es[ slot<<1 ] = old[i ]; + _es[(slot<<1)+1] = old[i+1]; + } + } + + // Just all the keys + public int[] keySet() { + int[] keys = new int[_size]; + int j=0; + for( int i=0; i<_es.length; i+=2 ) + if( _es[i] != _sentinel ) + keys[j++] = _es[i]; + return keys; + } + + @Override public String toString() { + SB sb = new SB().p("[ "); + for( int i=0; i<_es.length; i+=2 ) + if( _es[i] != _sentinel ) + sb.p('(').p(_es[i]).p(',').p(_es[i+1]).p(')').p(','); + return sb.unchar().p(']').toString(); } } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java index cdafb43b..cfffeb83 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -139,7 +139,7 @@ else return v; """); code.parse().opto(); - assertEquals("Stop[ return Test.Vector2D; return MEM[ 2:.x=0; 3:.y=0;]; return Test.Vector2D; ]", code.print()); + assertEquals("Stop[ return Test.Vector2D; return MEM[ 2:___ 3:.x=0; 4:.y=0;]; return Test.Vector2D; ]", code.print()); } @Test @@ -177,7 +177,7 @@ while (arg) { return bar.a; """); code.parse().opto(); - assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return MEM[ 2:.a=0;]; return Test.Bar; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return MEM[ 2:___ 3:.a=0;]; return Test.Bar; ]", code.print()); } @Test @@ -299,7 +299,7 @@ while( i.x < i.len ) { return sum; """); code.parse().opto(); - assertEquals("Stop[ return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum)); return MEM[ 2:.x=0; 3:.len=0;]; return Test.Iter; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum)); return MEM[ 2:___ 3:.x=0; 4:.len=0;]; return Test.Iter; ]", code.print()); } @@ -318,7 +318,7 @@ while(arg) { return ret; """); code.parse().opto(); - assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return MEM[ 2:.v0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return MEM[ 2:___ 3:.v0=0;]; return Test.s0; ]", code.print()); } @Test @@ -371,7 +371,7 @@ s0 b = new s0(); return a.x * 100 + b.x * 10 + cnt; """); code.parse().iter().opto(); - assertEquals("Stop[ return 112; return MEM[ 2:___ 3:.x=1;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return 112; return MEM[ 2:___ 3:___ 4:.x=1;]; return Test.s0; ]", code.print()); } @@ -414,7 +414,7 @@ else return new s0; if(new s0.f0) return 0; """); code.parse().iter().opto().typeCheck(); - assertEquals("Stop[ return Test.s0; return MEM[ 2:.f0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return Test.s0; return MEM[ 2:___ 3:.f0=0;]; return Test.s0; ]", code.print()); } @Test @@ -442,7 +442,7 @@ s0 v1 = v0; return v1; """); code.parse().opto(); - assertEquals("Stop[ return (const)Test.s0; return MEM[ 2:.f0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return (const)Test.s0; return MEM[ 2:___ 3:.f0=0;]; return Test.s0; ]", code.print()); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 07cd3831..40db6c4b 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -101,7 +101,7 @@ N n = new N(new M); return n.next; """); code.parse().opto(); - assertEquals("Stop[ return (const)Test.M; return MEM[ 2:.m=0;]; return Test.M; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:.next=Parm_m(Test.N.N,*Test.M {i64 !m; }); 7:.i=0;]; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:___ 7:.i=0;]; return Test.N; ]", code.print()); + assertEquals("Stop[ return (const)Test.M; return MEM[ 2:___ 3:.m=0;]; return Test.M; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:___ 7:.next=Parm_m(Test.N.N,*Test.M {i64 !m; }); 8:.i=0;]; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:___ 7:___ 8:.i=0;]; return Test.N; ]", code.print()); } @Test diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java index cb7d492f..2419dc2d 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -82,7 +82,7 @@ val hashCode = { !String self -> hashCode(new String("Hello, World!")); """; CodeGen code = new CodeGen(src).driver(Phase.LocalSched); - assertEquals("Stop[ return Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return MEM[ 2:___ 3:___ 4:.cs=Parm_s(Test.String.String,*[]u8[final]); 5:._hashCode=0;]; return MEM[ 2:___ 3:___ 4:___ 5:._hashCode=0;]; return Test.String; return Phi(Region,0,1,0,1); return Phi(Region,(!=0)._hashCode,Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code.print()); + assertEquals("Stop[ return Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return MEM[ 2:___ 3:___ 4:___ 5:.cs=Parm_s(Test.String.String,*[]u8[final]); 6:._hashCode=0;]; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:._hashCode=0;]; return Test.String; return Phi(Region,0,1,0,1); return Phi(Region,(!=0)._hashCode,Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code.print()); assertEquals("4029215624828139541", Eval2.eval(code, 2)); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java index 7522512e..30e1ed79 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -332,17 +332,8 @@ public class Chapter25Test { // Elf files are sane // Sys depends on io, libc, char, collections, and array utilities. - assertEquals(10,sys_elf._deps.length); - assertSame("sys/aryu8" ,sys_elf._deps[0]); - assertSame("sys/char" ,sys_elf._deps[1]); - assertSame("sys/io" ,sys_elf._deps[2]); - assertSame("sys/ary" ,sys_elf._deps[3]); - assertSame("sys/aryi64",sys_elf._deps[4]); - assertSame("sys/adt/bitset",sys_elf._deps[5]); - assertSame("sys", sys_elf._deps[6]); - assertSame("sys/scan" ,sys_elf._deps[7]); - assertSame("sys/adt" ,sys_elf._deps[8]); - assertSame("sys/libc" ,sys_elf._deps[9]); + assertArrayEquals(new String[]{"sys", "sys/adt", "sys/adt/bitset", "sys/ary", + "sys/aryi64", "sys/aryu8", "sys/char", "sys/io", "sys/libc", "sys/scan"},sys_elf._deps); assertSame("class:sys" ,sys_elf._clz._name); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java b/chapter25/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java index db7c7ae4..1dec3312 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java @@ -1,12 +1,16 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.codegen.CompUnit; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.FunNode; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFunPtr; +import com.seaofnodes.simple.type.Field; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; import java.nio.file.Files; import java.nio.file.Path; import java.util.ArrayList; +import java.util.BitSet; import java.util.Comparator; import java.util.Map; import org.junit.Rule; @@ -57,28 +61,59 @@ public class ClassInitDependenciesTest { for( long seed : new long[]{1,123,987654321} ) { try { compile(entry,sources,seed); fail("Expected initialization cycle"); } catch( Parser.ParseException ex ) { - assertTrue(ex.getMessage(),ex.getMessage().startsWith("Cyclic class initialization: "+expected)); - assertTrue("Include a source witness",ex.getMessage().contains(" at 1:")); + assertCycle(ex.getMessage(),expected); } } } - @Test public void testOrderAndPassiveReferences() throws Exception { + // The cycle can start at any member, but must follow dependency direction. + private void assertCycle(String message, String expected) { + String prefix="Cyclic class initialization: "; + assertTrue(message,message.startsWith(prefix)); + String actual=message.substring(prefix.length()).trim(); + String[] path=expected.split(" -> "); + for( int start=0; start<path.length-1; start++ ) { + ArrayList<String> rotated=new ArrayList<>(); + for( int i=0; i<path.length; i++ ) rotated.add(path[(start+i)%(path.length-1)]); + if( actual.equals(String.join(" -> ",rotated)) ) return; + } + fail("Expected cycle "+expected+" (up to rotation), got "+actual); + } + + // Follow ordinary helpers, stopping at the next initializer. This checks + // the class prerequisite relation without requiring a total init order. + private boolean touches(CodeGen code, ClassInitDependencies deps, String from, String to) { + int src=code.link(code._compunits.get(from)).sig().fidx(); + int dst=code.link(code._compunits.get(to)).sig().fidx(); + return touches(code,deps._edgess,src,dst,new BitSet()); + } + + private boolean touches(CodeGen code, int[][] edges, int src, int dst, BitSet seen) { + if( src>=edges.length || seen.get(src) || edges[src]==null ) return false; + seen.set(src); + for( int edge : edges[src] ) { + if( edge==dst ) return true; + FunNode fun=code.link(edge); + if( fun!=null && !fun.isClz() && touches(code,edges,edge,dst,seen) ) return true; + } + return false; + } + + @Test public void testEdgesAndPassiveReferences() throws Exception { CodeGen code = compile("A",Map.of("A","int value=B.value;", "B","int value=arg|1;"),123); - assertEquals("[Root, Root.B, Root.A]",code._classInitDeps.order().stream().map(c -> c._cname).toList().toString()); - assertTrue(code._compunits.get("Root/A")._initComplete); + ClassInitDependencies deps=new ClassInitDependencies(code); + assertTrue(touches(code,deps,"Root/A","Root/B")); code=compile("A",Map.of("A","val b=B;", "B","val a=A;"),123); - for( CompUnit cu : code._classInitDeps.order() ) { - if( cu._par==null ) assertNull(cu._classInitDeps); - else { - assertEquals(1,cu._classInitDeps.size()); - assertSame(cu._par,cu._classInitDeps.at(0)); - } - assertTrue(cu._initComplete); - } + deps=new ClassInitDependencies(code); + assertFalse(touches(code,deps,"Root/A","Root/B")); + assertFalse(touches(code,deps,"Root/B","Root/A")); + assertTrue(touches(code,deps,"Root/A","Root")); + assertTrue(touches(code,deps,"Root/B","Root")); } @Test public void testCycles() throws Exception { + cycle("A",Map.of("A","val get_noInline={ ->\n B.value;\n};\nint value=get_noInline();", + "B","int value=A.value;"),"A -> B -> A"); cycle("A",Map.of("A","int value=B.value;", "B","int value=A.value;"),"A -> B -> A"); cycle("A",Map.of("A","val get={ -> B.value; }; int value=get();", "B","int value=A.value;"),"A -> B -> A"); @@ -113,42 +148,159 @@ public class ClassInitDependenciesTest { CodeGen code=compile("A",Map.of( "A","val test_noInline={ -> false; }; int value=1; if(test_noInline()) value=B.value;", "B","int value=A.value;"),seed); - CompUnit a=code._compunits.get("Root/A"), b=code._compunits.get("Root/B"); - assertTrue(a._initComplete); - assertEquals(-1,a._classInitDeps.find(b)); - assertTrue(b._classInitDeps.find(a)>=0); + ClassInitDependencies deps=new ClassInitDependencies(code); + assertFalse(touches(code,deps,"Root/A","Root/B")); + assertTrue(touches(code,deps,"Root/B","Root/A")); code=compile("A",Map.of( "A","val test_noInline={ -> false; }; val f=test_noInline() ? { -> B.value; } : { -> 1; }; int value=f();", "B","int value=A.value;"),seed); - a=code._compunits.get("Root/A"); b=code._compunits.get("Root/B"); - assertTrue(a._initComplete); - assertEquals(-1,a._classInitDeps.find(b)); + assertFalse(touches(code,new ClassInitDependencies(code),"Root/A","Root/B")); // An unused helper's body must not become an initializer dependency. code=compile("A",Map.of("A","val unused={ -> B.value; }; int value=1;", "B","int value=A.value;"),seed); - assertEquals(-1,code._compunits.get("Root/A")._classInitDeps.find(code._compunits.get("Root/B"))); + assertFalse(touches(code,new ClassInitDependencies(code),"Root/A","Root/B")); } // Discarding the value of a field read cannot discard its active touch. cycle("A",Map.of("A","int value=1; B.value; return 0;", "B","int value=2; A.value; return 0;"),"A -> B -> A"); } - @Test public void testRecursionAndIncompleteEffects() throws Exception { + @Test public void testRecursionAndNativeCalls() throws Exception { CodeGen code=compile("A",Map.of("A","val f={int n -> n ? f(n-1) : B.value; }; int value=f(arg);", "B","int value=arg|1;"),123); - assertTrue(code._compunits.get("Root/A")._initComplete); - assertTrue(code._compunits.get("Root/A")._classInitDeps.find(code._compunits.get("Root/B"))>=0); + assertTrue(touches(code,new ClassInitDependencies(code),"Root/A","Root/B")); code=compile("A",Map.of("A","{int} native=\"C\"; return native();"),123); - assertFalse("Unknown native effects are not certified empty",code._compunits.get("Root/A")._initComplete); Path dir=tempDir("import-"); new CodeGen(null,dir.toString(),null,"B","int value=1;",123,true,TypeInteger.BOT) .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); code=new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), "A","return B.value;",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); - assertFalse("Imported summaries wait for checkpoint 2",code._compunits.get("B")._initComplete); - assertFalse(code._compunits.get("A")._initComplete); + assertTrue(touches(code,new ClassInitDependencies(code),"A","B")); + } + + private CodeGen object(Path dir, Path imports, String name, String source) { + return new CodeGen(null,dir.toString(),new Ary<>(new String[]{imports.toString()}), + name,source,123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + } + + private CodeGen module(Path dir, Path imports, String name, Map<String,String> sources) throws Exception { + Path src=tempDir("import-"); + for( var entry : sources.entrySet() ) { + Path file=src.resolve(entry.getKey()+".smp"); + Files.createDirectories(file.getParent()); + Files.writeString(file,entry.getValue()); + } + return new CodeGen(src.toString(),dir.toString(),new Ary<>(new String[]{imports.toString()}), + name,null,123,true,TypeInteger.BOT).driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + } + + @Test public void testImportedInitialization() throws Exception { + Path dir=tempDir("import-"), stubs=tempDir("import-"); + object(stubs,stubs,"A","int value=arg;"); + object(stubs,stubs,"B","int value=arg;"); + // Each object is independently acyclic. Combining their real bodies + // must recheck the graph rather than trust either object's local order. + object(dir,stubs,"A","int value=arg;\nvalue=B.value;"); + object(dir,stubs,"B","int value=arg; value=A.value;"); + for( String entry : new String[]{"A","B"} ) { + try { + new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Main","return "+entry+".value;",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + fail("Expected imported initialization cycle"); + } catch( Parser.ParseException ex ) { + assertCycle(ex.getMessage(),"A -> B -> A"); + } + } + } + + @Test public void testImportedDiamondAndHelpers() throws Exception { + Path diamond=tempDir("import-"); + CodeGen dcode=object(diamond,diamond,"D","int value=arg;"); + var data=dcode._encoding._data.entries().stream().filter(obj -> obj.symbol.equals("D.$class")).findFirst().orElseThrow(); + var dclz=dcode._compunits.get("D")._clz; + assertEquals(0,dcode._encoding._sdata.buf()[data.offset+dclz.offset(dclz.find("$init"))]); + object(diamond,diamond,"B","int value=D.value;"); + object(diamond,diamond,"C","int value=D.value;"); + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code=new CodeGen(null,diamond.toString(),new Ary<>(new String[]{diamond.toString()}), + "Main","int value=B.value+C.value;",seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + CompUnit b=code._compunits.get("B"), d=code._compunits.get("D"); + ClassInitDependencies deps=new ClassInitDependencies(code); + assertTrue(touches(code,deps,"B","D")); + assertTrue(touches(code,deps,"C","D")); + assertTrue(touches(code,deps,"Main","B")); + assertTrue(touches(code,deps,"Main","C")); + Field flag=d._clz.field("$init"); + assertSame(TypeInteger.U1,flag._t); + assertFalse(flag._final); + assertNotEquals(flag._alias,b._clz.field("$init")._alias); + // Loading just the header/types uses the same alias identity and + // does not require allocating any graph nodes. + ElfReader elf=ElfReader.load(diamond.resolve("D.o").toFile(),d); + assertEquals(flag._alias,elf.loadPublicTypes(code).field("$init")._alias); + assertNull(elf._nodes); + } + object(diamond,diamond,"Helper","val get={ -> D.value; }; val get_noInline={ -> D.value; };"); + for( String name : new String[]{"get","get_noInline"} ) { + CodeGen code=new CodeGen(null,diamond.toString(),new Ary<>(new String[]{diamond.toString()}), + "Main","return Helper."+name+"();",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + ClassInitDependencies deps=new ClassInitDependencies(code); + assertTrue(touches(code,deps,"Main","D")); + assertFalse(touches(code,deps,"Helper","D")); + } + object(diamond,diamond,"Wrapper","val get_noInline={ -> Helper.get_noInline(); };"); + CodeGen wrapped=new CodeGen(null,diamond.toString(),new Ary<>(new String[]{diamond.toString()}), + "Main","return Wrapper.get_noInline();",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + assertTrue(touches(wrapped,new ClassInitDependencies(wrapped),"Main","D")); + } + + @Test public void testInterleavedModules() throws Exception { + // Two objects, each providing a parent and children. Their orders + // must interleave: P.B precedes Q.A, which precedes P.A. + Path modules=tempDir("import-"), qstub=tempDir("import-"); + module(qstub,qstub,"Q",Map.of("Q","val A=A;", "Q/A","int value=arg;")); + module(modules,qstub,"P",Map.of("P","val A=A; val B=B;", + "P/A","int value=arg; value=Q.A.value;", "P/B","int value=arg;")); + module(modules,modules,"Q",Map.of("Q","val A=A;", "Q/A","int value=arg; value=P.B.value;")); + CodeGen combined=new CodeGen(null,modules.toString(),new Ary<>(new String[]{modules.toString()}), + "Main","return P.A.value;",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + ClassInitDependencies deps=new ClassInitDependencies(combined); + assertTrue(touches(combined,deps,"Q/A","P/B")); + assertTrue(touches(combined,deps,"P/A","Q/A")); + } + + @Test public void testCycleReportDirection() throws Exception { + cycle("A",Map.of("A","int value=B.value;", "B","int value=C.value;", + "C","int value=A.value;"),"A -> B -> C -> A"); + } + + @Test public void testOverlappingFunctionAndClassCycles() { + // Fixed function graph: Opto/inlining must not erase the overlap that + // exercises SCC traversal. f -> g -> f is legal; f -> A -> g -> f isn't. + CodeGen code=new CodeGen("return 0;").driver(CodeGen.Phase.Opto); + CompUnit cu=code._compunits.get("Test"); + code._linker.clear(); + String[] names={"f", "g", "A.<clinit>"}; + for( int i=0; i<names.length; i++ ) { + TypeFunPtr sig=TypeFunPtr.make1((byte)2,false,new Type[0],TypeInteger.BOT,i+2); + FunNode fun=new FunNode(null,sig,names[i],cu); + fun._type=Type.CONTROL; + code._linker.setX(i+2,fun); + } + ClassInitDependencies deps=new ClassInitDependencies(code); + deps._edgess[2]=new int[]{3}; // f -> g + deps._edgess[3]=new int[]{2}; // g -> f + assertNull("Ordinary mutual recursion is legal",deps.check()); + deps._edgess[4]=new int[]{3}; // A -> g + deps._edgess[2]=new int[]{3,4}; + String forward=deps.check(); + deps._edgess[2]=new int[]{4,3}; + String reverse=deps.check(); + assertTrue("Both successor orders must reject the class cycle: "+forward+", "+reverse, + forward!=null && reverse!=null); } } |