diff options
Diffstat (limited to 'chapter28b/src')
33 files changed, 770 insertions, 80 deletions
diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/Parser.java b/chapter28b/src/main/java/com/seaofnodes/simple/Parser.java index 5ceda6a9..87a3570a 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/Parser.java @@ -213,7 +213,6 @@ public class Parser { } - /** * Parses a function body, assuming the header is parsed. */ @@ -255,12 +254,14 @@ public class Parser { } private ReturnNode _parseFunctionBody( String funName, TypeFunPtr sig, Lexer loc, java.util.BitSet finals, String[] ids) { + Constructor outerCtor=_pendingCtor; + _pendingCtor=null; boolean isInit = FunNode.isInit(funName); boolean isCtor = isInit || isExplicitConstructorName(funName); String typeName = isCtor ? ((TypeMemPtr)sig._sig[0])._obj._name : null; // Stack parser state on the local Java stack, and unstack it later - _scope.push(new Kind.Func(funName)); + _scope.push(new Kind.Func(funName,isCtor && !funName.endsWith(".<clinit>"))); ScopeNode breakScope = _breakScope; _breakScope = null; ScopeNode continueScope = _continueScope; _continueScope = null; ScopeNode returnScope = _returnScope; _returnScope = null; @@ -290,6 +291,20 @@ public class Parser { _scope.define(ids[i], t, (i==0 && ids[0]=="self") || (finals!=null && finals.get(i)), new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(t).peephole()).peephole(), loc); } + if( isCtor && !isInit ) { + int lex=_scope.klast()._lexSize; + TypeStruct shape=(TypeStruct)TYPES.get(typeName); + for( Field fld : shape._fields ) { + int idx=fieldVarIdxBefore(lex,fld._fname); + if( idx<0 ) continue; + Var v=_scope.var(idx); + if( v._fref || v._extern!=0 || v._uninit || _scope.in(v)._type.isConstant() ) continue; + Node value=convertExpr( + new LoadNode(loc,fld._fname,fld._alias,ctrl(),fun.parm(3),fun.parm(2),off(shape,fld._fname)).peephole(),v.type()); + _scope.update(v,value); + } + } + // The initializer owns its run-once flag store. Parent initialization // is a structural requirement, executed before this body by CLInit lowering. if( fun.isClz() ) { @@ -316,6 +331,9 @@ public class Parser { nvar = updateSelfAsFieldsDiscovered( typeName, nvar ); } + if( isInit ) finishConstructor(); + _pendingCtor=outerCtor; + ParmNode self = fun.parm(2); // Last expression is the return if( ctrl()._type==Type.CONTROL ) { @@ -456,6 +474,10 @@ public class Parser { Node val = _returnScope.in(vidx); if( upgrade && v._uninit && !initialized(val._type) ) continue; + // A numeric merge can still be untyped while parsing. Retain its + // declared conversion at the helper boundary, as assignments do. + if( fld._t instanceof TypeInteger || fld._t instanceof TypeFloat ) + val=convertExpr(val,fld._t); // Store value into extended struct Node prior = mmm.keep(); Node st = peep(new StoreNode(null, fld._fname, fld._alias, fld._t, null, prior, self, off(tself,fld._fname), val, fld._final)); @@ -597,6 +619,9 @@ public class Parser { } // Constructor declaration: new TypeName = { args -> body }; + private record Constructor(String name, Lexer body) {} + private Constructor _pendingCtor; + private Node parseConstructorDeclaration() { TypeStruct self = _scope.constructorSelf(); assert self != null; @@ -605,6 +630,43 @@ public class Parser { if( name != expect ) throw error("Constructor name '" + name + "' must match type name '" + expect + "'"); require("="); + if( _pendingCtor!=null ) throw error("Redefining constructor '"+name+"'"); + _pendingCtor=new Constructor(name,loc()); + // Parse the body after all field declarations are known, so self.x + // and x share a local slot even when x is declared below this body. + require("{"); + int depth=1; + while( depth>0 ) { + _lexer.skipWhiteSpace(); + if( _lexer.isEOF() ) throw error("Unclosed constructor body"); + char ch=_lexer.nextChar(); + if( ch=='{' ) depth++; + else if( ch=='}' ) depth--; + else if( ch=='"' || ch=='\'' ) { + char quote=ch; + while( !_lexer.isEOF() ) { + ch=_lexer.nextChar(); + if( ch=='\\' ) _lexer.nextChar(); + else if( ch==quote ) break; + } + } + } + require(";"); + return _code.ZERO; + } + + private void finishConstructor() { + if( _pendingCtor==null ) return; + Constructor ctor=_pendingCtor; + _pendingCtor=null; + Lexer after=_lexer; + _lexer=new Lexer(ctor.body()); + defineConstructor(ctor.name()); + _lexer=after; + } + + private void defineConstructor(String name) { + TypeStruct self=_scope.constructorSelf(); Node ctor = constructorFunc(name); TypeFunPtr sig = (TypeFunPtr)ctor._type; String clzName = addClzPrefix(self._name); @@ -614,7 +676,7 @@ public class Parser { throw error("Redefining constructor '" + name + "'"); Field fld = Field.make("<ctor>",sig,_code.alias(_ref._cname),true); TYPES.put(clzName,clz==null ? TypeStruct.make(clzName,true,fld) : clz.add(fld)); - return require(ctor,";"); + require(ctor,";"); } /** @@ -1006,9 +1068,9 @@ public class Parser { if( _scope.in(def._idx)._type!=Type.TOP && def._final && // Inside an allocation, final assign is OK, outside nope. // The alloc() call added the allocation scope - !(_scope.inConstructor() && def._idx >= _scope.klast()._lexSize) && - !inExplicitConstructor() ) + !_scope.canInit(def) ) throw error("Cannot reassign final '"+name+"'"); + checkSharedFunction(def); // Parse assignment expression Node expr = parseAsgn(); @@ -1082,6 +1144,15 @@ public class Parser { }; } + private Type constructorFieldType(Type t) { + if( t instanceof TypeMemPtr ptr && ptr._obj.isConAry() ) { + TypeStruct declared=(TypeStruct)TYPES.get(ptr._obj._name); + TypeStruct shape=typeAry(declared._fields[1]._t,ptr._obj._fields[1]._final); + return TypeMemPtr.make((byte)2,shape,false).withAccess(ptr._ro); + } + return mutableInferredType(t); + } + // Seed an inferred return merge with the declared numeric family instead // of a transient constant/range. Pointer nullability remains part of the // inferred function result and is combined by the later Phi. @@ -1163,6 +1234,11 @@ public class Parser { throw error("a not-null/non-zero expression"); t = expr._type; if( !xfinal ) t = mutableInferredType(t); + // Instance fields may change until the constructor finishes. + // Keep the declared family/access, not the default's constant + // value or string contents. Class constants remain static. + else if( _scope.klast() instanceof Kind.Func fun && FunNode.isInstance(fun._name) && !(t instanceof TypeFunPtr) ) + t = constructorFieldType(t); } // expr is a constant function @@ -1214,7 +1290,6 @@ public class Parser { } - /** * Parse a struct declaration, and return the following statement. * Structs cannot be redefined, but can be nested. @@ -1744,7 +1819,6 @@ public class Parser { } - /** * Parse an eq/ne expression */ @@ -1789,8 +1863,8 @@ public class Parser { return cmp.unkeep(); } - // rhs is keeped() and becomes lhs - // cmp is NOT keeped() and is the last test + // Keep the middle operand separately from the boolean result. + // The next test compares adjacent operands, not that boolean. Node ifNode = new IfNode(ctrl(), cmp.unkeep()).peephole(); Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole(); @@ -1806,9 +1880,9 @@ public class Parser { throw error("Mixing relational directions in a chained relational test"); // True side parses next arm of test ctrl(ifT.unkeep()); - lhs = rhs; // lhs is keeped() and is old RHS + lhs = rhs; // Reuse the previous RHS exactly once rhs = parseShift().keep(); - cmp = makeCompBool(dir,lhs.unkeep(),rhs); // Convert to a bool + cmp = makeCompBool(dir0,lhs.unkeep(),rhs); // Convert to a bool ifNode = new IfNode(ctrl(), cmp).peephole(); ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole(); @@ -1822,7 +1896,7 @@ public class Parser { ctrl(ifT.unkeep()); RegionNode r = fail.mergeScopes(_scope, loc()).init(); _scope = fail; - return new PhiNode("", r,_code.ZERO,con(1)).peephole(); + return new PhiNode("", r,con(0),con(1)).peephole(); } private int parseCompDir() { @@ -1833,12 +1907,11 @@ public class Parser { return 0; } - private Node makeCompBool( int dir0, Node lhs, Node rhs ) { - // Convert to a bool - if( Math.abs(dir0)==2 ) // Swap direction - { Node tmp = lhs; lhs = rhs; rhs = tmp; } - lhs = peep(dir0 < 0 ? new BoolNode.LE(lhs,rhs) : new BoolNode.LT(lhs,rhs)); - return peep(lhs); + private Node makeCompBool( int dir, Node lhs, Node rhs ) { + if( Math.abs(dir)==2 ) + { Node tmp=lhs; lhs=rhs; rhs=tmp; } + Node cmp = dir < 0 ? new BoolNode.LE(lhs,rhs) : new BoolNode.LT(lhs,rhs); + return peep(cmp); } /** @@ -1927,9 +2000,10 @@ public class Parser { if( n != null && !(n.type() instanceof TypeMemPtr) ) { if( n._extern!=0 ) return parsePostfixName(_scope.in(n),name,delta); - if( n._final ) + if( n._final && !_scope.canInit(n) ) throw error("Cannot reassign final '"+n._name+"'"); - Node expr = zsMask(peep(new AddNode(_scope.in(n),con(delta))),n.type()); + checkSharedFunction(n); + Node expr = convertExpr(peep(new AddNode(_scope.in(n),con(delta))),n.type()); _scope.update(n,expr); return expr; } @@ -2015,12 +2089,10 @@ public class Parser { return parsePostfixName(rvalue,id,0); if( var._fref ) return parsePostfix(rvalue); - // Required constructor fields begin as their declared pointer type - // widened to include null. Inside the explicit constructor, any read - // before all paths replace that value observes a partially initialized - // object. Ordinary methods run only after construction is complete; - // their enclosing declaration scope still carries the same Var marker. - if( inExplicitConstructor() && var._uninit && rvalue._type instanceof TypeNil tn && tn.nullable() ) + // A constructor may read the unfinished object, but each field it + // reads must already be initialized on every path. Read the current + // local value; other fields may still be waiting for their first write. + if( inExplicitConstructor() && var._uninit && missingInit(rvalue,new BitSet()) ) throw error("Field '"+id+"' might not be initialized",var._loc); // Check for an instance field load @@ -2029,13 +2101,13 @@ public class Parser { Kind kk = _scope._kinds.at(kx); Kind fk = _scope._kinds.at(fx); // Access instance field from 'self' - if( kx+1 == fx && kk instanceof Kind.Func inst && FunNode.isInstance(inst._name) && fk instanceof Kind.Func method ) + if( kx+1 == fx && kk instanceof Kind.Func inst && FunNode.isInstance(inst._name) && fk instanceof Kind.Func method && !inExplicitConstructor() ) return parsePostfixName(_scope.in(method._lexSize),id,0); // Check for a function-escaping variable; these require true // closures. Final constants are OK; final vars require a hidden var // argument; not-final fields can just use an explicit struct arg. - if( kx < fx && // Out of scope + if( kx < fx && !inExplicitConstructor() && // Out of scope !(var._final && rvalue._type.isConstant()) ) { // Not a final constant if( kx > 0 ) // Global scope is OK, only ever one of these (not one per function invoke) throw error("Variable '"+var._name+"' is out of function scope and must be a final constant"); @@ -2062,8 +2134,9 @@ public class Parser { return parsePostfixMethod(rvalue,_scope.in(_scope.update(_scope.var(selfx),null))); } // Assign-update direct into Scope - if( var._final ) + if( var._final && !_scope.canInit(var) ) throw error("Cannot reassign final '"+var._name+"'"); + checkSharedFunction(var); Node op = opAssign(ch,rvalue, var.type() ); _scope.update(var,op); return postfix(ch) ? rvalue.unkeep() : op; @@ -2261,6 +2334,58 @@ public class Parser { return parsePostfixName(expr,name,0,site); } + private boolean privateSelf(Node ptr) { + while( ptr instanceof ConvertNode || ptr instanceof ReadOnlyNode || ptr instanceof GuardNode ) ptr=ptr.in(1); + Node self=defaultSelf(); + while( self instanceof ConvertNode || self instanceof ReadOnlyNode || self instanceof GuardNode ) self=self.in(1); + return ptr==self; + } + + // An explicit self.x read sees the same current value as bare x. Loading + // the allocation here would miss updates still held in local SSA values. + private Node privateField(String name, int pre) { + int idx=fieldVarIdxBefore(_scope._kinds.at(_scope.enclosingFuncOrDecl())._lexSize,name); + if( idx<0 ) throw error("Cannot resolve field '"+name+"'"); + Var v=_scope.var(idx); + if( pre==0 && matchOpx('=','=') ) { + checkSharedFunction(v); + Node value=parseAsgn().keep(); + _scope.update(v,convertExpr(value,v.type())); + return value.unkeep(); + } + Node value=_scope.in(_scope.update(v,null)); + if( v._uninit && missingInit(value,new BitSet()) ) + throw error("Field '"+name+"' might not be initialized",v._loc); + char ch=pre==0 ? _lexer.matchOperAssign() : (char)pre; + if( ch!=0 ) { + checkSharedFunction(v); + Node op=opAssign(ch,value,v.type()); + _scope.update(v,op); + if( pre!=0 && postfix(ch) ) value.unkeep(); + return pre==0 && postfix(ch) ? value.unkeep() : op; + } + return parsePostfixMethod(value,defaultSelf()); + } + + private void checkSharedFunction(Var v) { + if( _scope.canInit(v) && v._final && v.type() instanceof TypeFunPtr t && t.isConstant() ) + throw error("Cannot reassign shared function '"+v._name+"'"); + } + + // A loop Phi is temporarily bottom before its backedge is parsed. That is + // not an unwritten field: follow its live inputs to the actual defaults. + private boolean missingInit(Node value, BitSet seen) { + if( value==null || seen.get(value._nid) ) return false; + seen.set(value._nid); + if( value instanceof PhiNode phi && !(value instanceof ParmNode) ) { + for( int i=1; i<phi.nIns(); i++ ) + if( phi.region().in(i)!=null && phi.region().in(i)._type!=Type.XCONTROL && missingInit(phi.in(i),seen) ) + return true; + return false; + } + return !initialized(value._type); + } + private Node defaultSelf() { int selfx = _scope._kinds.at(_scope.enclosingFuncOrDecl())._lexSize; return _scope.in(_scope.update(_scope.var(selfx),null)); @@ -2283,6 +2408,7 @@ public class Parser { } private Node parsePostfixName(Node expr, String name, int pre, Lexer site) { + if( inExplicitConstructor() && privateSelf(expr) ) return privateField(name,pre); // Keep expr across possible updates expr.keep(); @@ -2782,6 +2908,7 @@ public class Parser { _position = pos; } + public static void gather(Lexer loc, HashMap<String,Integer> strs) { if( loc==null || loc._cu==null ) return; Serialize.gather(strs,loc._cu._cname); 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 47ec0112..8302ede6 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -318,7 +318,7 @@ public class CodeGen { } public String entryClinitName() { - return Parser.addClzPrefix(_srcName==null ? "Test" : _srcName)+".<clinit>"; + return Parser.addClzPrefix(_srcName==null ? "Test" : _srcName.replace('/','.'))+".<clinit>"; } // Verbose printing during compilation @@ -463,6 +463,8 @@ public class CodeGen { // --------------------------- // Parser object + public final Ary<CallNode> _calls = new Ary<>(CallNode.class); + public final Parser P; // Parse ASCII text into Sea-of-Nodes IR diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java index 128c4136..71126795 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java @@ -57,7 +57,8 @@ public class CompUnit { _obj = new File( CODE._buildDir + "/" + fname + ".o" ); boolean mustCompile = _smp.exists() && // Has source to compile - ( !_obj.exists() || // No object file + ( fname.equals(CODE._srcName) || // Explicit input is a compilation request + !_obj.exists() || // No object file _smp.lastModified() > _obj.lastModified() || // Out-of-date with source? checkDependentObjs() ); // Out-of-date with other objs? _src = mustCompile ? new String(Files.readAllBytes(_smp.toPath())) : null; diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index ef222f60..3b3f9f19 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -145,8 +145,7 @@ abstract public class Opto { private static void linkStart( CodeGen code, FunNode fun ) { assert !fun.isDead(); StartCUNode start = fun._compunit._start; - if( fun.nIns() < 2 ) { - assert fun.nIns() < 2 || fun.in(1) != start; + if( !fun.unknownCallers() ) { assert !start.isDead(); code.keepInCompUnit(fun); // Function is reachable by any *remote* caller who gets the pointer! diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 7ce727fd..c55f9a90 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -81,11 +81,16 @@ public abstract class ParseAll { } } + private static void enqueue(CompUnit cu) { + if( cu._par!=null && (cu._par._src!=null || (cu._par._obj!=null && cu._par._obj.exists())) ) enqueue(cu._par); + if( cu._start==null && WORK.find(cu)==-1 ) WORK.add(cu); + } + private static void parseAll(CodeGen code, CompUnit cunit) { WORK.clear(); // Cleanup from prior tests NEEDS_LOAD.clear(); // Prime the pump with the first CompUnit - WORK.add(cunit); + enqueue(cunit); // Work through all unparsed compilation units and parse while( !WORK.isEmpty() ) { CompUnit cu = WORK.remove(0); @@ -245,7 +250,7 @@ public abstract class ParseAll { 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 && WORK.find(sub)==-1 && NEEDS_LOAD.find(sub)==-1 ) - WORK.add(sub); + enqueue(sub); } } catch( IOException ioe ) { throw new RuntimeException(ioe); @@ -370,7 +375,7 @@ public abstract class ParseAll { CompUnit sub = makeCUnit(code,cunit,symbol); // If not seen before or out of date, parse the new nested cunit if( sub._clz == null && WORK.find(sub) == -1 ) - WORK.add(sub); + enqueue(sub); return sub; } @@ -405,7 +410,7 @@ public abstract class ParseAll { Parser.TYPES.put(clzName,clz = TypeStruct.make(clzName,true)); cunit._clz = clz; if( WORK.find(cunit) == -1 && NEEDS_LOAD.find(cunit) == -1 ) - WORK.add(cunit); + enqueue(cunit); return cunit; } } 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 6a23252d..5a74ded2 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -110,9 +110,12 @@ abstract public class Serialize { stopType.gather(types); startType.gather(types); // A defined class remains importable even when its initializer body dies. + // Nested structs also need their class declaration: <new> and <ctor> + // can be absent from graph types even while their function bodies live. + // Keep the nearest file owner, so an imported child is not re-exported + // merely because its parent was compiled here. for( TypeStruct ts : pubTypes ) - if( Parser.startsClzPrefix(ts._name) && - Arrays.binarySearch(units,ts._name.substring(Parser.CLZ.length()).replace('.','/'))>=0 ) + if( ownedClass(ts,units) ) ts.gather(types); // Only record canonical declarations already reachable from this @@ -262,6 +265,18 @@ abstract public class Serialize { } // Returned array of *public* strings only. + private static boolean ownedClass(TypeStruct ts, String[] units) { + if( !Parser.startsClzPrefix(ts._name) ) return false; + String name=ts._name.substring(Parser.CLZ.length()).replace('.','/'); + while( true ) { + if( CodeGen.CODE._compunits.containsKey(name) ) + return Arrays.binarySearch(units,name)>=0; + int slash=name.lastIndexOf('/'); + if( slash<0 ) return false; + name=name.substring(0,slash); + } + } + static void read_public_strs(ElfReader elf) { BAOS bais = elf._bais; Type.TAGOFFS(); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 36a012e1..fc6effdc 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -127,7 +127,7 @@ public class CallEndNode extends CFGNode implements MultiNode { // A linked function for every concrete function TypeTuple state = hasExtern - ? TypeTuple.make(Type.CONTROL,TypeMem.BOT,tfp.ret()) + ? TypeTuple.make(Type.CONTROL,call.exposed(this),tfp.ret()) : TypeTuple.STATE.dual(); for( int i=1; i<nIns(); i++ ) state = (TypeTuple)state.meet(in(i)._type); 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 71f6d146..bcb756fa 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -22,7 +22,7 @@ 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) { super(nodes); _loc=loc; CodeGen.CODE._calls.add(this); } 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 ) { @@ -67,7 +67,25 @@ public class CallNode extends CFGNode { public TypeFunPtr tfp() { return (TypeFunPtr)fptr()._type; } // Call is to an externally supplied code - public boolean external() { return false; } + public boolean external() { + if( !(fptr()._type instanceof TypeFunPtr tfp) ) return false; + if( XInt.isHigh(tfp.fidxs()) ) return true; + for( int fidx=XInt.next(tfp.fidxs(),-1); fidx>=0; fidx=XInt.next(tfp.fidxs(),fidx) ) + if( CodeGen.CODE.externFunc(fidx)!=null ) 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) { + 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); + return TypeMem.make(1,Type.BOTTOM,false,false,false,escaped._escFs,escaped._escAs); + } // Find the Call End from the Call 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 77b43ba8..8718f351 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -715,6 +715,7 @@ 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); return n; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 21d60d53..694d5dcb 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -39,7 +39,12 @@ public class ScopeNode extends MemMergeNode { public final TypeStruct _self; } // Function scope - public static class Func extends Kind { public Func(String name) { _name=name;} public final String _name; } + public static class Func extends Kind { + public final String _name; + public final boolean _constructor; + public Func(String name) { this(name,false); } + public Func(String name, boolean constructor) { _name=name; _constructor=constructor; } + } public int _lexSize; // Number of Vars in this scope } @@ -184,10 +189,7 @@ public class ScopeNode extends MemMergeNode { } // Which lexical scope contains this Var? - public Kind kind( Var v ) { - int kx = kindx(v); - return kx == -1 ? null : _kinds.at(kx); - } + public int kindFcnx( Var v ) { for( int i=depth()-1; i>=0; i-- ) @@ -202,6 +204,21 @@ public class ScopeNode extends MemMergeNode { return kx == -1 ? null : _kinds.at(kx); } + // Final fields are writable local values inside their own initializer or + // constructor. Final parameters, local variables, and captured bindings + // remain final. Use the same rule when deciding which loop Phis to build. + public boolean canInit(Var v) { + int fx=enclosingFuncOrDecl(); + Kind.Func fun=(Kind.Func)_kinds.at(fx); + if( !fun._constructor || v._extern!=0 ) return false; + int dx=FunNode.isInstance(fun._name) ? fx : fx-1; + return dx>=0 && kindx(v)==dx && v._idx>=_kinds.at(dx)._lexSize+2; + } + + private boolean loopVar(Var v) { + return !v._final || (canInit(v) && !v.type().isHighOrConst()); + } + // Find name in reverse, return an index into _vars or -1. Linear scan // instead of hashtable, but probably doesn't matter until the scan // typically hits many dozens of variables. @@ -346,7 +363,7 @@ public class ScopeNode extends MemMergeNode { for( int i=2; i<nIns(); i++ ) // For lazy phis on loops we use a sentinel // that will trigger phi creation on update - dup.addDef(loop && !var(i)._final ? this : in(i)); + dup.addDef(loop && loopVar(var(i)) ? this : in(i)); return dup; } @@ -431,7 +448,7 @@ public class ScopeNode extends MemMergeNode { // Fill in the backedge of any inserted Phis void _endLoop( ScopeNode scope, Node back, Node exit ) { for( int i=1; i<nIns(); i++ ) { - if( var(i)._final ) continue; // Final vars did not get modified in the loop + if( !loopVar(var(i)) ) continue; Node n = in(i); if( var(i).type().isHighOrConst() && !(n instanceof PhiNode phi && phi.inProgress()) ) { // Cannot lift higher than a constant, so no Phi Node con = ConstantNode.make(var(i).type()).init(); 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 d3a356ed..43acf631 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java @@ -79,6 +79,11 @@ public class StopCUNode extends StopNode { // here as its effects are not visible to the outside world. addDepForwards(start); // Check again if function escapes if( pub || start.escapedFIDX(sig.fidx()) ) { + // External callers already hold their object arguments, so + // writes through those arguments expose addresses too. + for( Node use : fun._outputs ) + if( use instanceof ParmNode p && p._idx>=2 ) + xmem=publicBottom(xmem.escapes(addDepForwards(p)._type)); if( tret.ctl().isHigh() ) continue; // Return not reachable // Capture (precisely?) all escaping pointer aliases and fidxs. // Escaped fidxs means the linked world can call that function; @@ -88,6 +93,10 @@ public class StopCUNode extends StopNode { xmem = (TypeMem)xmem.meet(publicBottom(tret.mem(),xmem)); } } + // Native retention is shared by the whole program, including 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))); assert xmem._alias==1 && !xmem._one; return TypeTuple.make(Type.CONTROL,xmem,Type.BOTTOM); } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index cc958348..5fa0b99f 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -184,8 +184,12 @@ public class StoreNode extends MemOpNode { return this; } + // Private constructor memory describes the value that the next helper + // reads. Keep its conversion, even if a machine store could truncate it. + // This is the same rule as in the construction and escape chapters. + boolean priv = mem()._type instanceof TypeMem tm && tm._one; // Value is automatically truncated by narrow store - if( _size!=0 && val() instanceof AndNode and && and.in(2)._type.isConstant() ) { + if( !priv && _size!=0 && val() instanceof AndNode and && and.in(2)._type.isConstant() ) { int log = log_size(); if( log<3 ) { // And-mask vs narrow store long mask = ((TypeInteger)and.in(2)._type).value(); @@ -198,7 +202,7 @@ public class StoreNode extends MemOpNode { } // Store will chop high order bits off; math to change those bits can be dropped. - if( _size!=0 && val() instanceof SarNode shr && + if( !priv && _size!=0 && val() instanceof SarNode shr && shr.in(1) instanceof ShlNode shl && shr.in(2)._type.isConstant() && shl.in(2)._type.isConstant() ) { @@ -253,7 +257,7 @@ public class StoreNode extends MemOpNode { return switch( use ) { case MemOpNode mem -> mem._alias; case MemPhiNode phi -> phi._alias; - case EscapeNode esc -> throw Utils.TODO("Untested"); // esc.pub()==this ? esc.fld()._alias : 0; + case EscapeNode esc -> esc.pub()==this ? esc.fld()._alias : 0; default -> 0; }; } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/BoundaryTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/BoundaryTest.java new file mode 100644 index 00000000..b736ccb3 --- /dev/null +++ b/chapter28b/src/test/java/com/seaofnodes/simple/BoundaryTest.java @@ -0,0 +1,86 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import org.junit.Test; +import static org.junit.Assert.*; + +// The new module boundary must preserve the preceding chapters' examples. +public class BoundaryTest { + @Test public void testLocalConstruction() throws java.io.IOException { + String src="struct Counter { int x; int y; int z; new Counter={int n -> while(x<n) { int old=x; y=x+1; x=y+1; z=old; }}; }; val c=new Counter(arg); return c.x*100+c.z;"; + CodeGen code=new CodeGen(src).driver(CodeGen.Phase.LocalSched); + assertEquals("2018",Eval2.eval(code,19)); + assertEquals("0",Eval2.eval(code,0)); + code._stop.walk(n -> { + if( n instanceof StoreNode st ) assertEquals(0,st.cfg0().loopDepth()); + return null; + }); + code=new CodeGen("struct Byte { new Byte={int n -> self.x=n; self.x+=3;}; u8 x; }; return new Byte(255).x;").driver(CodeGen.Phase.TypeCheck); + assertEquals("2",Eval2.eval(code,0)); + // data is still unset when the constructor reads and updates x. + code=new CodeGen("struct Box { int x=7; int[] data; new Box={ -> self.x++; int n=self.x; data=new int[n]; }; }; return new Box().data#;") + .driver(CodeGen.Phase.TypeCheck); + assertEquals("8",Eval2.eval(code,0)); + for( String field : new String[]{"data","self.data"} ) { + try { + new CodeGen("struct Box { int[] data; new Box={ -> int n="+field+"#; data=new int[n]; }; }; return new Box();") + .driver(CodeGen.Phase.TypeCheck); + fail("An uninitialized field must not be read"); + } catch( Parser.ParseException e ) { + assertTrue(e.getMessage(),e.getMessage().contains("might not be initialized")); + } + } + java.nio.file.Path cfile=java.nio.file.Path.of("build/objs/constructionBoundary.c"); + java.nio.file.Files.createDirectories(cfile.getParent()); + java.nio.file.Files.writeString(cfile,""" + __attribute__((CALL_CONV)) extern long long count(long long); + int main(void) { return count(19)!=2018 || count(0)!=0; } + """); + TestC.run("val count={int arg ->"+src+"};","constructionBoundary",null,TestC.CALL_CONVENTION, + TestC.CALL_CONVENTION.equals("win64") ? "ms_abi" : "sysv_abi",cfile.toString(),"",-1); + } + + @Test public void testRecursiveCallback() { + String src=""" + val run={int n -> + val power={int base,int exponent -> if(exponent<=0) return 1; return base*power(base,exponent-1);}; + val sumPowers={int n,{int int -> int} f -> if(n<=0) return 0; return f(2,n)+sumPowers(n-1,f);}; + return sumPowers(n,power); + }; + return run(arg); + """; + for( long seed : new long[]{2,13,123} ) { + CodeGen code=new CodeGen(src,seed,true).driver(CodeGen.Phase.Opto); + ParmNode base=code._start.walk(n -> n instanceof ParmNode p && p._label.equals("base") ? p : null); + assertNotNull(base); + assertSame(TypeInteger.constant(2),base._type); + code.driver(CodeGen.Phase.TypeCheck); + assertEquals("14",Eval2.eval(code,3)); + } + } + + @Test public void testNativeExposure() { + for( String tail : new String[]{ + "retain(power); return power(2,n);", + "if(n) { retain(power); while(true) {} } return power(2,n);" + } ) { + String src="val run={int n -> val power={int base,int exponent -> if(exponent<=0) return 1; return base*power(base,exponent-1);}; { {int int -> int} -> int } retain=\"C\";"+tail+"}; return run(arg);"; + CodeGen code=new CodeGen(src).driver(CodeGen.Phase.Opto); + ParmNode base=code._start.walk(n -> n instanceof ParmNode p && p._label.equals("base") ? p : null); + assertNotNull(base); + assertSame(TypeInteger.BOT,base._type); + code.driver(CodeGen.Phase.TypeCheck); + } + } + + @Test public void testLazyTables() { + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code=new CodeGen("src/test/smp/lazy","build/objs",null,"App/Main",null,seed,true,TypeInteger.BOT) + .driver(CodeGen.Phase.TypeCheck); + assertEquals("0",Eval2.eval(code,0)); + assertEquals("125",Eval2.eval(code,1)); + } + } +} diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/ChainedComparisonTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/ChainedComparisonTest.java new file mode 100644 index 00000000..8db9c024 --- /dev/null +++ b/chapter28b/src/test/java/com/seaofnodes/simple/ChainedComparisonTest.java @@ -0,0 +1,37 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ChainedComparisonTest { + @Test public void testAdjacentOperandsAndOperators() { + String[] expressions = {"10 < arg < 20", "0 < arg <= 3", "3 >= arg > 0", + "0 <= arg < 3", "0 < arg <= 3 < 4"}; + String[][] expected = {{"0","0","1","0"}, {"0","1","0","0"}, + {"0","1","0","0"}, {"1","0","0","0"}, + {"0","1","0","0"}}; + int[] args = {0,3,15,30}; + for(int i=0;i<expressions.length;i++) { + CodeGen code = new CodeGen("return "+expressions[i]+";").driver(CodeGen.Phase.TypeCheck); + for(int j=0;j<args.length;j++) assertEquals(expressions[i],expected[i][j],Eval2.eval(code,args[j])); + } + } + + @Test public void testSingleEvaluationAndShortCircuit() { + for(int seed:new int[]{2,13,123}) { + CodeGen code = new CodeGen("int x=arg; int y=0; val b=0 < x++ <= (y+=3) < (y+=1); return x*100+y*10+b;",seed,true) + .driver(CodeGen.Phase.TypeCheck); + assertEquals("100",Eval2.eval(code,0)); + assertEquals("441",Eval2.eval(code,3)); + assertEquals("530",Eval2.eval(code,4)); + } + try { + new CodeGen("return 0 < arg > 1;").parse(); + fail("mixed directions"); + } catch(RuntimeException e) { + assertEquals("Mixing relational directions in a chained relational test",e.getMessage()); + } + } +} diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 08029c4b..4019fd38 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -300,7 +300,7 @@ A x = new A; for( String fields : new String[] { "!B !b; new A = { -> if (arg) b = new B; };", "!B !b; new A = { -> if (arg) return 0; b = new B; };", - "!B !b; new A = { !B b -> b = new B; };", // Argument shadows field + "!B !b; new A = { !B !b -> b = new B; };", // Argument shadows field "new A = { -> }; !B !b;", // Field declared later } ) { CodeGen code = new CodeGen("struct B {}; struct A { "+fields+" }; return 0;"); diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter18Test.java index ae1dca5f..632b9539 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -436,7 +436,7 @@ return s.x; catch( Exception e ) { assertEquals("Accessing unknown field 'x' from '*Test.S'",e.getMessage()); } } - @Test @Ignore + @Test public void testErr5() { CodeGen code = new CodeGen( """ @@ -450,8 +450,8 @@ return g(); } - // Mutual recursion. Fails without SCCP to lift the recursive return types. - @Ignore @Test + // Mutual recursion: check results, independent of how much gets inlined. + @Test public void testFcnMutRec() { CodeGen code = new CodeGen( """ @@ -460,7 +460,6 @@ val is_odd = { int x -> x ? is_even(x-1) : false; }; return is_even(arg); """); code.driver(CodeGen.Phase.TypeCheck); - assertEquals("Stop[ return #2; return Phi(Region,0,1,#2); ]", code.print()); assertEquals("1", Eval2.eval(code, 0)); assertEquals("0", Eval2.eval(code, 1)); assertEquals("1", Eval2.eval(code, 2)); diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 0458941e..cdfd16a7 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -202,7 +202,6 @@ flt farg = arg; return _test_sqrt_noInline(farg) + _test_sqrt_noInline(farg+2.0) } - @Test public void testArray1() { String src = @@ -257,9 +256,9 @@ val _hashCodeString = { !String self -> return hash; }; """; - testCPU(src,"x86_64_v2", "SystemV",21,null); - testCPU(src,"riscv" , "SystemV",8,null); - testCPU(src,"arm" , "SystemV",8,null); + testCPU(src,"x86_64_v2", "SystemV",12,null); + testCPU(src,"riscv" , "SystemV",6,null); + testCPU(src,"arm" , "SystemV",6,null); } @Test diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 07ae42eb..2fcf65e9 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -383,9 +383,9 @@ val _hashCodeString = { !String self -> return hash; }; """; - testCPU(src,"x86_64_v2", "SystemV",21,null); - testCPU(src,"riscv" , "SystemV",8,null); - testCPU(src,"arm" , "SystemV",8,null); + testCPU(src,"x86_64_v2", "SystemV",12,null); + testCPU(src,"riscv" , "SystemV",6,null); + testCPU(src,"arm" , "SystemV",6,null); } @Test public void testStringExport() throws IOException { @@ -422,7 +422,7 @@ val _hashCodeString = { !String self -> return hash; }; """; - TestC.runC(src, "stringHash", "",21); + TestC.runC(src, "stringHash", "",12); } @Test public void testLoop2() { diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java index 275be96a..31a616b5 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -412,7 +412,7 @@ public class Chapter25Test { @Test public void testHelloWorldDriver() throws Exception { String out = "build/objs/helloWorldDriver/"; - Simple.main(new String[]{"-L",SYS_BLDDIR,"-o",out,"--norun","docs/examples/A_helloWorld.smp"}); + Simple.main(new String[]{"-L",SYS_BLDDIR,"-o",out,"--norun","src/test/smp/examples/A_helloWorld.smp"}); assertTrue(Files.isRegularFile(Path.of(out,"A_helloWorld.o"))); } @@ -423,7 +423,7 @@ public class Chapter25Test { try( PrintStream capture = new PrintStream(output,true,StandardCharsets.UTF_8) ) { System.setOut(capture); Simple.main(new String[]{"-L",SYS_FILE.toString(),"-o","build/objs/helloWorldDriverLibFile/", - "docs/examples/A_helloWorld.smp"}); + "src/test/smp/examples/A_helloWorld.smp"}); } finally { System.setOut(saved); } @@ -471,7 +471,7 @@ return rez < buf# ? 0 : sys.libc._exit(-2); @Test public void testBubbles() throws IOException { - String src = Files.readString( Path.of("docs/examples/BubbleSort.smp")); + String src = Files.readString( Path.of("src/test/smp/examples/BubbleSort.smp")); String exe = TestC.compile(src,"BubbleSort",new Ary<>(new String[]{SYS_BLDDIR}), TestC.CALL_CONVENTION,null,null,-1); assertEquals("[-17, 2, 3, 999]\n", @@ -492,7 +492,7 @@ return rez < buf# ? 0 : sys.libc._exit(-2); @Test public void testCapitalize() throws IOException { - String src = Files.readString(Path.of("docs/examples/Capitalize.smp")); + String src = Files.readString(Path.of("src/test/smp/examples/Capitalize.smp")); String exe = TestC.compile(src,"Capitalize",new Ary<>(new String[]{SYS_BLDDIR}), TestC.CALL_CONVENTION,null,null,-1); assertEquals("Hello world\n",TestC.exec(exe,"hello world")); @@ -505,7 +505,7 @@ return rez < buf# ? 0 : sys.libc._exit(-2); @Test public void testDijkstra() throws IOException { - String src = Files.readString(Path.of("docs/examples/Dijkstra.smp")); + String src = Files.readString(Path.of("src/test/smp/examples/Dijkstra.smp")); String matrix = "[0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0]"; String exe = TestC.compile(src,"Dijkstra",new Ary<>(new String[]{SYS_BLDDIR}), TestC.CALL_CONVENTION,null,null,-1); @@ -520,7 +520,7 @@ return rez < buf# ? 0 : sys.libc._exit(-2); @Test public void testFileIO() throws IOException { - String src = Files.readString(Path.of("docs/examples/FileIO.smp")); + String src = Files.readString(Path.of("src/test/smp/examples/FileIO.smp")); String exe = TestC.compile(src,"FileIO",new Ary<>(new String[]{SYS_BLDDIR}), TestC.CALL_CONVENTION,null,null,-1); assertEquals("File I/O succeeded\n",TestC.exec(exe)); diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java new file mode 100644 index 00000000..f583e2d2 --- /dev/null +++ b/chapter28b/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java @@ -0,0 +1,65 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.StoreNode; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FinalConstructionTest { + private static final String LOOP = """ + val step={int x -> x*2+1;}; + struct C { + val x=1; + new C={int n -> + x=0; x=1; + for(int i=0; i<n; i++) x=step(x); + }; + val get={->x;}; + }; + return new C(arg).get(); + """; + + @Test public void testFinalConstructorLocals() throws java.io.IOException { + var code=new CodeGen(LOOP).driver(CodeGen.Phase.LocalSched); + assertEquals("1",Eval2.eval(code,0)); + assertEquals("15",Eval2.eval(code,3)); + assertEquals("63",Eval2.eval(code,5)); + code._stop.walk(n -> { + if( n instanceof StoreNode st && st._name.equals("x") ) + assertEquals("Final field writes belong after the loop",0,st.cfg0().loopDepth()); + return null; + }); + String[] sources={ + "struct C { val x=1; new C={->x=1; x=2;}; }; return new C().x;", + "struct C { int ~x; new C={int n -> self.x=1; for(int i=0;i<n;i++) self.x*=2;}; }; return new C(arg).x;", + "struct C { val x=1; new C={int n -> for(int i=0;i<n;i++) ++x;}; }; return new C(arg).x;", + "struct C { val x=1.5; new C={->x=2.5;}; }; return new C().x;", + "struct C { val x=\"a\"; new C={int n -> for(int i=0;i<n;i++) x=\"b\";}; }; return new C(arg).x[0];", + "struct C { val x=new int[1]; new C={->x=new int[2]; x=new int[3];}; }; return new C().x#;" + }; + String[] results={"2","8","4","2.5","98","3"}; + for( int i=0; i<sources.length; i++ ) + assertEquals(results[i],Eval2.eval(new CodeGen(sources[i]).driver(CodeGen.Phase.TypeCheck),3)); + + String[] rejected={ + "struct C { val x=1; }; val c=new C(); c.x=2; return c.x;", + "struct C { new C={->val x=1; x=2;}; }; return new C();", + "struct C { val f={->1;}; new C={->f={->2;};}; }; return new C().f();" + }; + for( String src : rejected ) { + try { new CodeGen(src).driver(CodeGen.Phase.TypeCheck); fail(src); } + catch( Parser.ParseException e ) { assertTrue(e.getMessage(),e.getMessage().startsWith("Cannot")); } + } + + var dir=java.nio.file.Path.of("build/objs"); + java.nio.file.Files.createDirectories(dir); + java.nio.file.Files.writeString(dir.resolve("finalConstruction.smp"),"val buildFinal={int arg ->"+LOOP+"};"); + java.nio.file.Files.writeString(dir.resolve("finalConstruction.c"),""" + extern long long buildFinal(long long); + int main(void) { return buildFinal(0)!=1 || buildFinal(3)!=15 || buildFinal(5)!=63; } + """); + TestC.run("val buildFinal={int arg ->"+LOOP+"};","finalConstruction",null,TestC.CALL_CONVENTION, + TestC.CALL_CONVENTION.equals("win64") ? "ms_abi" : "sysv_abi", + dir.resolve("finalConstruction.c").toString(),"",-1); + } +} diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java new file mode 100644 index 00000000..4576bc94 --- /dev/null +++ b/chapter28b/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java @@ -0,0 +1,90 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.util.Ary; +import java.nio.file.Files; +import java.nio.file.Path; +import org.junit.Test; +import static org.junit.Assert.*; + +public class SeparateCompilationTest { + @Test public void testImportedNativeExposure() throws Exception { + Path build=Path.of("build/objs/separate"); + Files.createDirectories(build); + Path lib=Files.createTempDirectory(build,"callbacks-"); + String src=""" + val run={int n -> + val power={int base,int exponent -> + if(exponent<=0) return 1; + return base*power(base,exponent-1); + }; + { {int int -> int} -> int } retain="C"; + retain(power); + return power(2,n); + }; + """; + new CodeGen(null,lib.toString(),null,"Callbacks",src,123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + CodeGen code=new CodeGen(null,null,new Ary<>(new String[]{lib.toString()}), + "Client","return Callbacks.run(arg);",123,true,TypeInteger.BOT) + .driver(CodeGen.Phase.Opto); + assertNull(code._compunits.get("Callbacks")._src); + ParmNode base=code._start.walk(n -> n instanceof ParmNode p && p._label.equals("base") ? p : null); + assertNotNull(base); + assertSame("Native code may call the saved callback with any base",TypeInteger.BOT,base._type); + code.driver(CodeGen.Phase.TypeCheck); + } + + // The client root contains no library source. The saved constructor must + // keep local loop values, and retained calls must use the library's storage. + @Test public void testImportedConstructorAndState() throws Exception { + Path fixtures=Path.of("src/test/smp/separate"); + Path build=Path.of("build/objs/separate"); + Files.createDirectories(build); + Path lib=Files.createTempDirectory(build,"library-"); + Path client=Files.createTempDirectory(build,"client-"); + new CodeGen(fixtures.resolve("library").toString(),lib.toString(),null, + "Counters",null,123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + assertTrue(Files.isRegularFile(lib.resolve("Counters.o"))); + assertFalse(Files.exists(fixtures.resolve("client/Counters.smp"))); + var paths=new Ary<>(new String[]{lib.toString()}); + for( long seed : new long[]{2,13,123} ) { + CodeGen code=new CodeGen(fixtures.resolve("client").toString(),client.toString(),paths, + "Main",null,seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + CompUnit imported=code._compunits.get("Counters"); + assertNotNull(imported); + assertNull("Library source must not be parsed",imported._src); + assertEquals(lib.resolve("Counters.o").toRealPath(),imported._obj.toPath().toRealPath()); + assertEquals("0",Eval2.eval(code,0)); + assertEquals("107",Eval2.eval(code,3)); + assertEquals("131",Eval2.eval(code,5)); + } + new CodeGen(fixtures.resolve("client").toString(),client.toString(),paths, + "Main",null,123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + Path driver=client.resolve("driver.c"); + Files.writeString(driver,""" + #include <stdio.h> + __attribute__((CALL_CONV)) extern long long run(long long); + int main(void) { + long long args[]={0,3,5,0,3}, expected[]={0,107,231,0,307}; + for(int i=0;i<5;i++) { + long long actual=run(args[i]); + if(actual!=expected[i]) { + printf("call %d: got %lld, expected %lld\\n",i,actual,expected[i]); + return 1; + } + } + return 0; + } + """); + String exe=client.resolve(TestC.OS.startsWith("Windows")?"test.exe":"test").toString(); + TestC.linkExe(client.resolve("Main.o").toString(), + TestC.CALL_CONVENTION.equals("win64")?"ms_abi":"sysv_abi",driver.toString(), + new Ary<>(new String[]{lib.resolve("Counters.o").toString()}),exe); + assertEquals("",TestC.exec(TestC.TEST_TIMEOUT_SECONDS,exe)); + } +} diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Simple.java b/chapter28b/src/test/java/com/seaofnodes/simple/Simple.java index 2d688bbe..7cfdf57d 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Simple.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Simple.java @@ -13,7 +13,6 @@ import java.io.InputStreamReader; import java.nio.file.Files; import java.nio.file.Path; import java.util.ArrayList; -import java.util.stream.Collectors; public class Simple { static void usage() { @@ -83,7 +82,11 @@ Options: static String getInput() { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); - return reader.lines().collect(Collectors.joining("\n")); + StringBuilder text=new StringBuilder(); + try { + for( String line; (line=reader.readLine())!=null; ) text.append(line).append('\n'); + } catch( IOException e ) { throw new RuntimeException(e); } + return text.toString(); } public static void main(String[] args) throws Exception { @@ -140,6 +143,9 @@ Options: case "-o": if (out != null || i + 1 >= args.length || args[i + 1].charAt(0) == '-') bad_usage(); out = args[++i]; do_codegen=true; break; + case "--root": if( root!=null || i+1>=args.length ) bad_usage(); + root=args[++i]; + break; case "-L": if (i + 1 >= args.length || args[i + 1].charAt(0) == '-') bad_usage(); libPaths.add(args[++i]); break; @@ -175,7 +181,8 @@ Options: if( modPath == null ) modPath = Path.of("."); } else { - throw Utils.TODO(); + modPath=Path.of(root); + inPath=modPath.resolve(inPath); } // Compute the module-relative paths for all sources @@ -184,7 +191,8 @@ Options: Path relPath = n==1 ? null : srcRelPath.subpath(0,n-1); // Compute source/class name String srcNameExt = srcRelPath.getName(n-1).toString(); - String srcName = srcNameExt.substring(0,srcNameExt.length()-4); + String srcName = srcRelPath.toString().replace('\\','/'); + srcName=srcName.substring(0,srcName.length()-4); // Compute the build path. Path outPath; @@ -219,15 +227,14 @@ Options: if( simpleHome != null && !simpleHome.isEmpty() ) libPaths.add(Path.of(simpleHome,cpu+"_"+abi).toString()); - // Read input file - try { - src = input_filename.isEmpty() ? getInput() : Files.readString(Path.of(input_filename)); - } catch( IOException e ) { throw bad("Cannot read input file: "+input_filename); } + // Keep file-backed units so discovery sees parents and siblings. + src = input_filename.isEmpty() ? getInput() : null; // Compilation pipeline Ary<String> externPaths = libPaths.isEmpty() ? null : new Ary<>(libPaths.toArray(new String[0])); CodeGen code = new CodeGen(modPath.toString(), outPath.toString(), externPaths, srcName, src, 456, true, TypeInteger.BOT ); - code.driver(Phase.LastPhase,cpu,abi, false, emit_main || do_run || do_eval, dump); + code.driver(do_eval && !do_codegen ? Phase.TypeCheck : Phase.LastPhase, + cpu,abi, false, emit_main || do_run || do_eval, dump); if( do_codegen && print_asm ) System.out.println(code.asm()); diff --git a/chapter28b/src/test/smp/examples/A_helloWorld.smp b/chapter28b/src/test/smp/examples/A_helloWorld.smp new file mode 100644 index 00000000..4ed6abdf --- /dev/null +++ b/chapter28b/src/test/smp/examples/A_helloWorld.smp @@ -0,0 +1,2 @@ +sys.io.p("Hello, World!\n"); +return 0; diff --git a/chapter28b/src/test/smp/examples/BubbleSort.smp b/chapter28b/src/test/smp/examples/BubbleSort.smp new file mode 100644 index 00000000..ca6906b5 --- /dev/null +++ b/chapter28b/src/test/smp/examples/BubbleSort.smp @@ -0,0 +1,36 @@ + +// An implementation of +// https://sampleprograms.io/projects/bubble-sort/ +// +// Bubble sort, with reading (parsing) and writing (formatting) the data. + +val sort = { !sys.aryi64 nums -> + sys.aryi64?! more = nums; + while( more ) { + more = null; + for( var i = 0; i < nums.len-1; i++ ) + if( nums.buf[i] > nums.buf[i+1] ) + more = nums.swap(i,i+1); + } +}; + +// Read one process argument of the form "[ 4, 3, 2, 1]" and print it sorted. +// args[0] is the executable name, as with native C argc/argv. +val main = { u8[~][] args -> + val usage = { -> + sys.io.p("Usage: please provide a list of at least two integers to sort in the format \"[1, 2, 3, 4, 5]\"\n"); + return 0; + }; + if( args# != 2 ) return usage(); + + var nums = sys.aryi64.parseAryI64(args[1]); + if( !nums ) return usage(); + if( nums.len < 2 ) return usage(); + + // Bubble sort array of integers + sort(nums); + + // Print the same bracketed array-list format accepted as input. + nums.str().add('\n').write(1); + return 0; +}; diff --git a/chapter28b/src/test/smp/examples/Capitalize.smp b/chapter28b/src/test/smp/examples/Capitalize.smp new file mode 100644 index 00000000..8e31c18f --- /dev/null +++ b/chapter28b/src/test/smp/examples/Capitalize.smp @@ -0,0 +1,22 @@ + +// An implementation of +// https://sampleprograms.io/projects/capitalize/ + +val main = { u8[~][] args -> + if( args# > 2 ) { + sys.io.p("Use quotes around multiple strings.\n"); + return 0; + } + if( args# != 2 || args[1]# == 0 ) { + sys.io.p("Usage: please provide a string\n"); + return 0; + } + + u8[~] input = args[1]; + var output = new u8[input# + 1]; + sys.ary.copy(output,0,input,0,input#); + output[0] = sys.char.toupper(input[0]); + output[input#] = '\n'; + sys.io.p(output); + return 0; +}; diff --git a/chapter28b/src/test/smp/examples/Dijkstra.smp b/chapter28b/src/test/smp/examples/Dijkstra.smp new file mode 100644 index 00000000..fd595eb5 --- /dev/null +++ b/chapter28b/src/test/smp/examples/Dijkstra.smp @@ -0,0 +1,72 @@ + +// An implementation of +// https://sampleprograms.io/projects/dijkstra/ + +val shortestPath = { !sys.aryi64 matrix, int nodes, int src, int dst -> + i64 infinity = (1 << 63)-1; + var dist = new i64[nodes]; + var visited = new sys.adt.bitset(); + // All nodes are infinitely far from each other + for( int i=0; i<nodes; i++ ) dist[i] = infinity; + // Starting point is zero far from starting point + dist[src] = 0; + + i64 result = -1; + int count = 0; + while( count < nodes && result < 0 ) { + int nearest = -1; + i64 best = infinity; + for( int node=0; node<nodes; node++ ) + if( !visited.get(node) && dist[node] < best ) { + nearest = node; + best = dist[node]; + } + if( nearest < 0 ) count = nodes; + else { + if( nearest == dst ) return best; + visited.set(nearest); + for( int node=0; node<nodes; node++ ) { + i64 weight = matrix.get(nearest*nodes + node); + if( weight > 0 && !visited.get(node) && best+weight < dist[node] ) + dist[node] = best+weight; + } + } + count++; + } + return result; +}; + +val usage = { -> + sys.io.p("Usage: please provide three inputs: a serialized matrix, a source node and a destination node\n"); + return 0; +}; + +val main = { u8[~][] args -> + // Exactly 3 args + if( args# != 4 ) return usage(); + // First is a serialized square matrix of positive numbers + var matrix = sys.aryi64.parseAryI64(args[1]); + if( !matrix ) return usage(); + if( !matrix.len ) return usage(); + // All numbers are positive + for( int i=0; i<matrix.len; i++ ) + if( matrix.get(i) < 0 ) return usage(); + // Matrix is square + int nodes = 0; + while( nodes*nodes < matrix.len ) nodes++; + if( nodes*nodes != matrix.len ) + return usage(); // Not a square matrix + + // src,dst are values within the matrix + i64 src = sys.aryu8.atoi(args[2]); + i64 dst = sys.aryu8.atoi(args[3]); + if( src < 0 || src >= nodes || dst < 0 || dst >= nodes ) + return usage(); // Source and destination land within the graph + + i64 cost = shortestPath(matrix,nodes,src,dst); + if( cost >= 0 ) { + new sys.aryu8().num(cost).add('\n').write(1); + return 0; + } + return usage(); +}; diff --git a/chapter28b/src/test/smp/examples/FileIO.smp b/chapter28b/src/test/smp/examples/FileIO.smp new file mode 100644 index 00000000..e48d435b --- /dev/null +++ b/chapter28b/src/test/smp/examples/FileIO.smp @@ -0,0 +1,50 @@ + +// An implementation of +// https://sampleprograms.io/projects/file-input-output/ + +val FILE = "output.txt"; + +val main = { u8[~][] args -> + var str = new sys.aryu8(); + str.addAry("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.\n"); + str.addAry("Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.\n"); + str.addAry("Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.\n"); + str.addAry("Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.\n"); + + // Create + i32 fd = sys.io.create(FILE); + if( fd == -1 ) return _error(); + // Write + int wrote = sys.io.writeOff(fd,str.buf,0,str.len); + if( wrote == -1 ) return _error(); + if( wrote != str.len ) return _error2(-2); + // Close + if( sys.io.close(fd) != 0 ) return _error(); + + // Open + i32 fd2 = sys.io.open(FILE); + if( fd2 == -1 ) return _error(); + // Read + var got = sys.io.read(fd2); + if( got# != str.len ) return _error2(-3); + // Close + if( sys.io.close(fd2) != 0 ) return _error(); + + // Check contents are equal + if( sys.ary.cmp(got,0,str.buf,0,str.len) ) + return _error2(-4); + + // Remove + if( sys.io.remove(FILE) != 0 ) return _error(); + + sys.io.p("File I/O succeeded\n"); + return 0; +}; + +val _error2 = { i32 errno -> + sys.io.remove(FILE); + new sys.aryu8().addAry("Failed with error code ").num(errno).add('\n').write(sys.libc.STDERR); + sys.libc._exit(errno); +}; + +val _error = { -> _error2(sys.libc.errno()); }; diff --git a/chapter28b/src/test/smp/lazy/App.smp b/chapter28b/src/test/smp/lazy/App.smp new file mode 100644 index 00000000..caf7b0c1 --- /dev/null +++ b/chapter28b/src/test/smp/lazy/App.smp @@ -0,0 +1,3 @@ +val Main=Main; +val Tables=Tables; +val Stats=Stats; diff --git a/chapter28b/src/test/smp/lazy/App/Main.smp b/chapter28b/src/test/smp/lazy/App/Main.smp new file mode 100644 index 00000000..2444f21b --- /dev/null +++ b/chapter28b/src/test/smp/lazy/App/Main.smp @@ -0,0 +1 @@ +return arg ? Tables.square(3)+Tables.square(4)+100*Stats.builds : Stats.builds; diff --git a/chapter28b/src/test/smp/lazy/App/Stats.smp b/chapter28b/src/test/smp/lazy/App/Stats.smp new file mode 100644 index 00000000..e2d9e02e --- /dev/null +++ b/chapter28b/src/test/smp/lazy/App/Stats.smp @@ -0,0 +1 @@ +int builds=0; diff --git a/chapter28b/src/test/smp/lazy/App/Tables.smp b/chapter28b/src/test/smp/lazy/App/Tables.smp new file mode 100644 index 00000000..0f32a118 --- /dev/null +++ b/chapter28b/src/test/smp/lazy/App/Tables.smp @@ -0,0 +1,4 @@ +Stats.builds++; +int[] _squares=new int[256]; +for(int i=0; i<256; i++) _squares[i]=i*i; +val square={u8 n -> _squares[n];}; diff --git a/chapter28b/src/test/smp/separate/client/Main.smp b/chapter28b/src/test/smp/separate/client/Main.smp new file mode 100644 index 00000000..077f6575 --- /dev/null +++ b/chapter28b/src/test/smp/separate/client/Main.smp @@ -0,0 +1,6 @@ +val run={int n -> + if(!n) return 0; + val c=new Counters.Counter(n); + return c.get()+100*Counters.next_noInline(); +}; +return run(arg); diff --git a/chapter28b/src/test/smp/separate/library/Counters.smp b/chapter28b/src/test/smp/separate/library/Counters.smp new file mode 100644 index 00000000..a3e36562 --- /dev/null +++ b/chapter28b/src/test/smp/separate/library/Counters.smp @@ -0,0 +1,12 @@ +// A library can keep shared state and publish instance constructors. +int calls=0; +val next_noInline={ -> calls++; return calls; }; + +struct Counter { + val value=1; + new Counter={int n -> + value=0; + for(int i=0; i<n; i++) value=value*2+1; + }; + val get={ -> value; }; +}; |